Optimal Correspondences, Geometry and the Vertex Cover Problem

Fredrik Kahl
(Lund University, Sweden)

The correspondence problem appears as a subtask in many computer vision applications such as object recognition, merging partial 3D reconstructions and image alignment. Automatically matching features from appearance only is a difficult problem and therefore geometric consistency is also used to remove incorrect correspondences. Typically heuristic methods like RANSAC and EM-type algorithms are employed for solving this problem, but they risk getting trapped in local optima and have no guarantee of finding the best solution.

In this talk, I will illustrate how graph methods for the vertex cover problem can be used to efficiently find optimal correspondences. These ideas are implemented on several basic geometric problems: 3D-3D registration, 2D-3D registration and relative camera oriention. The developed scheme can handle a large rate of outliers. Despite the combinatorial explosion of hypotheses, the resulting algorithm yields competitive running times compared to the state-of-the-art.