Accession Number:

ADA210105

Title:

An Efficiently Computable Metric for Comparing Polygonal Shapes

Descriptive Note:

Technical rept.

Corporate Author:

CORNELL UNIV ITHACA NY DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Arkin, Esther M.
• Chew, L. P.
• Huttenlocher, Daniel P.
• Kedem, Klara
• Mitchell, Joseph S.

Report Date:

1989-05-01

Pagination or Media Count:

22.0

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 Omn 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.

Descriptors:

• *IMAGE PROCESSING
• *PATTERN RECOGNITION
• CONVEX BODIES
• VISION
• POLYGONS
• SHAPE

Subject Categories:

• Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE