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.