An efficiently computable metric for comparing polygonal shapes
- 1 March 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 13 (3) , 209-216
- https://doi.org/10.1109/34.75509
Abstract
Model-based recognition is concerned with comparing a shape A, which is stored as a model for some particular object, with a shape B, which is found to exist in an image. If A and B are close to being the same shape, then a vision system should report a match and return a measure of how good that match is. To be useful this measure should satisfy a number of properties, including: (1) it should be a metric, (2) it should be invariant under translation, rotation, and change-of-scale, (3) it should be reasonably easy to compute, and (4) it should match our intuition (i.e., answers should be similar to those that a person might give). We develop a method for comparing polygons that has these properties. The method works for both convex and nonconvex polygons and runs in time O(mn logmn) where m is the number of vertices in one polygon and n is the number of vertices in the other. We also present some examples to show that the method produces answers that are intuitively reasonable.Keywords
This publication has 9 references indexed in Scilit:
- Recognize The Similarity Between Shapes Under Affine TransformationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- An improved model-based matching method using footprintsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On curve matchingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1990
- Computing the minimum Hausdorff distance for point sets under translationPublished by Association for Computing Machinery (ACM) ,1990
- Optimal matching of convex polygonsPattern Recognition Letters, 1989
- Identification of Partially Obscured Objects in Two and Three Dimensions by Matching Noisy Characteristic CurvesThe International Journal of Robotics Research, 1987
- Curve Similarity via SignaturesPublished by Elsevier ,1985
- A combinational approach to polygon similarityIEEE Transactions on Information Theory, 1983
- Organization of Relational Models for Scene AnalysisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982