On Planar Point Matching under Affine Transformation
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 O(n-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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1989
- Accession Number
- ADA210106
Entities
People
- Daniel P. Huttenlocher
- John E. Hopcroft
Organizations
- Cornell University