ANSAC: Adaptive Non-minimal Sample and Consensus
This addresses a bottleneck in computer vision for tasks like image matching, though it is incremental as it builds on RANSAC.
The paper tackles the problem of RANSAC-based methods being slow due to noise in correct image correspondences, introducing ANSAC which adaptively uses more than minimal correspondences to generate hypotheses, resulting in faster convergence and outperforming state-of-the-art methods in homography and fundamental matrix estimation.
While RANSAC-based methods are robust to incorrect image correspondences (outliers), their hypothesis generators are not robust to correct image correspondences (inliers) with positional error (noise). This slows down their convergence because hypotheses drawn from a minimal set of noisy inliers can deviate significantly from the optimal model. This work addresses this problem by introducing ANSAC, a RANSAC-based estimator that accounts for noise by adaptively using more than the minimal number of correspondences required to generate a hypothesis. ANSAC estimates the inlier ratio (the fraction of correct correspondences) of several ranked subsets of candidate correspondences and generates hypotheses from them. Its hypothesis-generation mechanism prioritizes the use of subsets with high inlier ratio to generate high-quality hypotheses. ANSAC uses an early termination criterion that keeps track of the inlier ratio history and terminates when it has not changed significantly for a period of time. The experiments show that ANSAC finds good homography and fundamental matrix estimates in a few iterations, consistently outperforming state-of-the-art methods.