On Planar Point Matching under Affine Transformation

Abstract

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.