Partial Matching of Planar Polygons Under Translation and Rotation
Eric C. McCreath · ANU Open Research (Australian National University) · 2008
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 Hausdor 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 nds the best match along a xed 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.