Robust point correspondence by concave minimization

摘要

We propose a new methodology for reliably solving the correspondence problem between points of two or more images. This is a key step in most problems of Computer Vision and, so far, no general method exists to solve it.Our methodology is able to handle most of the commonly used assumptions in a unique formulation, independent of the domain of application and type of features. It performs correspondence and outlier rejection in a single step, and achieves global optimality with feasible computation. Feature selection and correspondence are first formulated as an integer optimization problem. This is a brute force formulation, which considers the whole combinatorial space of possible point selections and correspondences. To find its global optimal solution we build a concave objective function and relax the search domain into its convex-hull. The special structure of this extended problem assures its equivalence to the original one, but it can be optimally solved by efficient algorithms that avoid combinatorial search.