Generalized RANSAC Framework for Relaxed Correspondence Problems

Finding correspondences between two (widely) separated views is essential for several computer vision tasks, such as structure and motion estimation and object recognition. In the wide-baseline matching using scale and/or affine invariant features the search for correspondences typically proceeds in two stages. In the first stage a putative set of correspondences is obtained based on distances between feature descriptors. In the second stage the matches are refined by imposing global geometric constraints by means of robust estimation of the epipolar geometry and the incorrect matches are rejected as outliers. For a feature in one view, usually only one "best" feature (the nearest neighbor) in the other view is chosen as corresponding feature, despite the fact that several match candidates exist. In this paper, we will consider multiple candidate matches for each feature, and integrate this choice with the robust estimation stage, thus avoiding the early commitment to the "best" one. This yields a generalized RANSAC framework for identifying the true correspondences among sets of matches. We examine the effectiveness of different sampling strategies for sets of correspondences and test the approach extensively using real examples of hard correspondence problems caused by a large motion between views and/or ambiguities due to repetitive scene structures.