ransac

RANSAC, Random Sample Consensus, introduced by Martin Fischler and Robert Bolles in 1981, is a robust method for fitting a model to data that is contaminated with outliers, points that simply do not obey the model. This is exactly the situation after feature matching: a large fraction of the proposed correspondences are wrong, and ordinary least-squares fitting would be wrecked by them because least squares tries to satisfy every point, including the nonsense ones. RANSAC's insight is to flip the strategy: instead of fitting all the data and hoping outliers average out, repeatedly fit tiny random subsets and let the data vote on which fit is best.

The algorithm is a loop. Randomly pick the minimum number of points needed to define the model (for a line, 2 points; for a homography, 4 point correspondences). Fit the model exactly to that minimal sample. Then test every other data point against this candidate model and count how many agree with it within a tolerance; the agreeing points are the inliers, and their count is the model's consensus. Repeat for many random samples, keeping the model with the largest consensus set. Finally, refit the model using all of its inliers (by least squares) for a precise estimate. The winning model is the one most points endorse, and outliers, being inconsistent and uncorrelated, never form a large consensus by chance.

The beautiful part is that the number of iterations needed is predictable and modest. If a fraction of the data are inliers, the probability that a random minimal sample is entirely free of outliers can be computed, and from it the number of trials required to draw at least one clean sample with high confidence (say 99 percent). Crucially, this depends on the inlier ratio and the sample size, not on the total number of points, so RANSAC scales to large datasets. A smaller minimal sample (fewer points needed) makes clean samples far more likely, which is why minimal solvers are so valued.

RANSAC has a few knobs that govern its behaviour: the inlier threshold (how close a point must be to count as agreeing), the confidence level, and the maximum iterations. Set the threshold too tight and you reject good inliers; too loose and outliers sneak in. Many improved variants exist: MLESAC weights inliers by likelihood rather than just counting them, PROSAC samples promising matches first to converge faster, LO-RANSAC adds a local optimization step, and MAGSAC++ removes the need to choose a hard threshold. RANSAC and its descendants are indispensable wherever robust geometric estimation is needed, including homography and fundamental-matrix estimation, camera pose (PnP), point-cloud registration, and SLAM.