Partial matching of planar polygons under translation and rotation

Abstract

Curve matching is an important computational task for domains such as: reconstruction of archaeological fragments, forensics investigation, measuring melodic similarity, and model-based object recognition. There are a variety of measures and algorithmic approaches used to address the curve matching problem including: shape signature strings with substring matching, geometric hashing, and Hausdorff distance approaches. In this paper we propose an approach that uses a turning function representation of the shape and also uses a L 2 measure for comparing matches. The novel algorithm presented finds the best match along a fixed length portion of two polygon's perimeters where the polygons may be arbitrarily translated and rotated. The algorithm's time complexity is O(mn(n + m)) where n and m are the numbers of vertices in the perimeters being matched. The utility of the algorithm is demonstrated in the reconstruction of a small jigsaw puzzle. Show more