StaRSaC: Stable random sample consensus for parameter estimation

We address the problem of parameter estimation in presence of both uncertainty and outlier noise. This is a common occurrence in computer vision: feature localization is performed with an inherent uncertainty which can be described as Gaussian, with unknown variance; feature matching in multiple images produces incorrect data points. RANSAC is the preferred method to reject outliers if the variance of the uncertainty noise is known, but fails otherwise, by producing either a tight fit to an incorrect solution, or by computing a solution which includes outliers. We thus propose a new estimator which enforces stability of the solution with respect to the uncertainty bound. We show that the variance of the estimated parameters (VoP) exhibits ranges of stability with respect to this bound. Within this range of stability, we can accurately segment the inliers, and estimate the parameters, the variance of the Gaussian noise. We show how to compute this stable range using RANSAC and a search. We validate our results by extensive tests and comparison with state of the art estimators on both synthetic and real data sets. These include line fitting, homography estimation, and fundamental matrix estimation. The proposed method outperforms all others.