Efficient Correspondance Based Algorithm for 2D and 3D Model Based Recognition.

摘要

This paper presents a polynomial time algorithm (pruned correspondence search, PCS) with good average case performance for solving a wide class of geometric maximal matching problems, including the problem of recognizing three dimensional objects from a single two dimensional image. Given two finite sets of geometric features with error bounds and a polynomial time algorithm that determines the feasibility of individual matchings, it finds a maximal matching. The algorithm is based on a pruned depth-first search for correspondences. Pruning is accomplished by representing regions of search space that have already been explored using an 'adjoint list' of correspondences between image and model points. The PCS algorithm is connected with the geometry of the underlying recognition problem only through calls to a verification algorithm. The analysis of the PCS algorithm demonstrates clearly the effects of the various combinatorial and geometric constraints on the complexity of the recognition problem. Efficient verification algorithms, based on a linear representation of location constraints, are given for the case of affine transformations among vector spaces and for the case of rigid 2D and 3D transformations with scale. Among the known algorithms that solve the bounded error recognition problem exactly and completely, the PCS algorithm currently has the lowest complexity. Some preliminary experiments suggest that PCS is a practical algorithm. Its similarity to existing correspondence based algorithms means that a number of existing techniques for speedup can be incorporated into PCS to improve its performance.