Accession Number:

ADA210106

Title:

On Planar Point Matching under Affine Transformation

Descriptive Note:

Technical rept.

Corporate Author:

CORNELL UNIV ITHACA NY DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Hopcroft, John E.
• Huttenlocher, Daniel P.

Report Date:

1989-04-01

Pagination or Media Count:

15.0

Abstract:

An important geometric matching problem in machine vision and robotics is to determine whether there exists an affine transformation a general linear transformation and a translation that maps each point of a set A onto a corresponding point of a set B. In the case of matched cardinality point sets, we have developed an optimal Theta n log n algorithm for determining the existence of such a transformation. The method makes use of the fact that an affine transformation preserves the center gravity of a point set, as well as the ratios of triangle areas. If abs. val. A abs. val. B then there can be n- cubed affine transformations from A to B. In general the number of transformations will be much smaller, so we have developed an output sensitive algorithm that runs in time On-sq log n tmlog n, where m abs. val. A, n abs. val. B, and t depends on the number of transformations. The method relies on the affine properties that intersection points and length ratios along a line are preserved.

Descriptors:

• *TRANSFORMATIONS(MATHEMATICS)
• *MATCHING
• OUTPUT
• RATIOS
• CENTER OF GRAVITY
• ROBOTICS
• TRIANGLES
• LENGTH
• PLANAR STRUCTURES
• GEOMETRY
• TRANSFORMATIONS
• LINEAR SYSTEMS
• ALGORITHMS
• SENSITIVITY

Subject Categories:

• Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE