Two dimensional projective point matching

Abstract

Point matching is a problem which occurs in several forms in computer vision and other areas. Solving practical point matching problems requires that a point matching algorithm allow for an appropriate class of geometric transformations between the points in the model and their instance in the data. Many real world point matching problems require a two dimensional projective transformation to relate the model to the data. Point matching under this class of transformations has received little attention, and existing algorithms are inadequate. Existing, general, polynomial time point matching algorithms by Baird, Cass, and Barrel are formulated for lower order transformation classes and have difficulty scaling. The RANSAC algorithm, which represents the current best solution to the problem under the projective transformation, cannot solve the problem when there are significant amounts of noise and clutter in the data sets; a condition likely to occur in many real problem instances. Presented here is a new algorithm for point matching based on local search. This algorithm is a general solution to the two dimensional point matching problem under all transformation classes; although the focus is on the projective transform case. This algorithm gracefully deals with more clutter and noise than the existing algorithms, while still providing an efficient solution to easier problem instances. A randomized version of the algorithm is presented, and a superior version which uses a key feature algorithm to identify partial matches which may be a part of the optimal solution is detailed. The effectiveness of these algorithms is validated for image registration and model recognition problems using data obtained from real imagery; point sets of various sizes containing varying amounts of noise and clutter.