An Efficiently Computable Metric for Comparing Polygonal Shapes
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 log mn) where m is the number of vertices in one polygon and n is the number of vertices in the other. Some examples are presented that show the method produces answers that are intuitively reasonable.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1989
- Accession Number
- ADA210105
Entities
People
- Daniel P. Huttenlocher
- Esther M. Arkin
- Joseph S. Mitchell
- Klara Kedem
- L. P. Chew
Organizations
- Cornell University