Robust Estimation: RANSAC & Friends

Motivation

The eight-point algorithm (Part 6), DLT for a homography, and Nistér's five-point solver for E all end the same way: stack a linear (or least-squares) system from a set of correspondences and solve it in one shot, typically by minimizing a sum of squared residuals Σ⁏ ri². That squaring is the problem. A correspondence that's correct contributes a small residual; a correspondence that's wrong — a mismatched feature, a moving object caught by a matcher expecting a static scene, a repeated texture that fooled the matcher entirely — can contribute a residual a hundred times larger. Because the cost is squared, one such outlier can dominate the entire sum and drag the fitted F, H, or E arbitrarily far from the truth, even with hundreds of good matches sitting right next to it.

And outliers are not a rare edge case. Real feature matchers (SIFT, ORB, or a learned matcher like SuperGlue — the front end that produces the correspondences fed to every estimator in this series is its own topic and not this page's job) routinely mismatch 10–50% of their proposed pairs, especially under repetitive texture, wide baselines, or motion. Every linear estimator built so far in this series needs something wrapped around it that can tolerate that.

The algorithm

RANSAC's idea: instead of fitting one model to all the data, fit many candidate models, each from the smallest possible subset of points, and keep whichever candidate the most of the rest of the data agrees with. A minimal subset drawn entirely from inliers gives an exact, uncorrupted model — you just don't know in advance which draws are lucky, so you draw many and let each one vote.

Step 1 needs a minimal sample size s — just enough correspondences to pin the model down exactly, with no slack for a least-squares average. This series has already met every one of these minimal solvers:

Smaller s is better for RANSAC in one specific way — it makes an all-inlier draw more likely — which is exactly why the minimal solvers matter here, not just as a curiosity: RANSAC is the reason anyone bothered inventing a 5-point solver for E (the five-point algorithm, treated in Part 13) instead of always using 8 correspondences with the linear route.

How many iterations, exactly?

The one number RANSAC can't skip is N, the iteration count. Here's where it comes from. Let w be the (unknown, estimated) fraction of correspondences that are inliers. The probability that one randomly drawn minimal sample of size s is entirely inliers is wₛ (each of the s draws independently needs to land on an inlier). So the probability a single sample fails to be all-inliers is 1 − wₛ, and the probability that all N independent samples fail is (1 − wₛ)ᵉ — that's the probability RANSAC never once gets a clean sample in N tries. Demanding that this failure probability be at most 1 − p, for a desired confidence p (e.g. 99%) of having drawn at least one all-inlier sample, and solving for N:

This grows brutally as either w shrinks or s grows, because wₛ sits in the denominator's argument and shrinks fast. Fixing p = 0.99: at s = 8 (8-point F) with half the data being inliers (w = 0.5), wₛ = 0.0039 and N ≈ 1,179 — already a lot of samples for one estimate. Drop to w = 0.2 (80% outliers, not unusual for wide-baseline wide matching) and wₛ = 2.56×10⁻⁶, so N ≈ 1.8 million — the exact reason minimal solvers with small s matter so much: the same drop from w=0.5 to w=0.2 at s = 4 (homography) only pushes N from about 74 to about 2,878, not into the millions.

Interactive

Every point below is really an inlier (near the hidden true line) or an outlier (uniformly scattered); RANSAC doesn't know which. Click New data to resample, then Step to run one iteration by hand, or Run to let it go automatically. Each iteration draws 2 random points (orange), fits the line through them via the same cross-product duality trick from Part 0 (l = x̃₁ × x̃₂), and counts how many of all the points fall within τ of that line. Green highlights the current best model's inlier set; the solid line is the best model so far, the dashed line is the current sample's fit.

Notice the readout's N (est.) line: it's the same N = ln(1−p)/ln(1−wₛ) formula from above, evaluated live at s=2, p=0.99, and w = 1 − outlier ratio. Drag the outlier ratio slider up and watch that estimate climb steeply — the same climb that makes F/H RANSAC expensive on badly-matched image pairs.

Beyond the textbook loop

Plain RANSAC scores a model by a hard count: a point is an inlier if its residual is below τ, and don't-care otherwise. That throws away information — two models with the same inlier count can fit those inliers very differently well, and vanilla RANSAC can't tell them apart. Three refinements fix different parts of this:

MSAC (M-estimator SAmple Consensus) keeps the same loop but replaces the 0/1 inlier count with a truncated squared residual cost, summed over all points:

An outlier (ri > τ) still contributes a flat, bounded penalty τ² — it can't dominate the sum, same as plain RANSAC's don't-care treatment — but an inlier now contributes how well it fits (ri²), not just a vote. Lower cost is better. This makes the score smoother and better correlated with true model quality, at essentially zero extra computation over counting.

LO-RANSAC (locally-optimized RANSAC) changes the outer loop itself: whenever a new best model is found, before continuing to sample, immediately re-fit that model with ordinary least squares on its entire current inlier set (a non-minimal, well-conditioned fit, not another minimal draw), then re-count inliers under the refit model. This local refinement step converges to noticeably better final models, and in practice needs far fewer outer-loop iterations to get there — because a well-fit "best so far" model recruits more true inliers on the next inlier count, tightening the estimate quickly instead of waiting for a lucky minimal sample to land near-perfectly.

MAGSAC / MAGSAC++ attacks a different weak point: every variant above still needs the user to pick τ, and getting it wrong silently degrades results — too tight and true inliers get discarded (weaker fit, less data used); too loose and outliers leak in (biased fit). MAGSAC removes that choice by not committing to a single noise scale at all: instead of thresholding at one τ, it marginalizes the model's quality over a whole range of plausible noise scales, weighting each point's contribution by how it would be scored across that range rather than by a hard cutoff at one guessed value. The result is a method with no τ to tune and no single wrong guess to silently degrade the fit.

Interactive

Drag confidence p, inlier fraction w, and sample size s; the readout recomputes N = ln(1−p)/ln(1−wₛ) live. The plot shows N (log scale) as a function of w for two fixed sample sizes — s=4 (homography) and s=8 (8-point F) — at the current p, with your exact (w, s) marked.

Interactive

The pink curve is the formula from the previous step, evaluated at every iteration count k up to N. The blue curve is measured: for each of M independent trials, RANSAC draws N minimal samples of s correspondences from a synthetic pool in which a fraction w are inliers, and the trial counts as a success if any one of its N draws lands entirely on inliers. A single draw is all-inlier with probability wₛ, the draws are independent, so the fraction of trials succeeded by iteration N should land on 1 − (1 − wₛ)ᵉ — and the gap should shrink as M grows.

Every trial is generated by a seeded mulberry32 RNG, so a given slider setting and seed always reproduces the same curve; Resample advances the seed by one so you can eyeball how much of the remaining gap is pure sampling noise. With M = 200 the empirical curve wobbles around the theory; push M to 500 and the wobble visibly narrows.

The threshold is only as good as the distance it's measured in

Everything above assumed a residual r you can threshold against τ in pixels. For RANSAC-on-F, the obvious candidate is the same quantity the 8-point algorithm minimizes, the algebraic error from Part 6:

The problem: this number is not in pixel units, and it doesn't scale like a distance — a correspondence far from the epipolar line but where Fx̃₁ happens to be small in magnitude can score a tiny algebraic error despite being a bad match, while another point close to the line but where Fx̃₁ is large can score a big one. Thresholding on it directly bakes an arbitrary, scene-dependent scale into τ, which defeats the whole point of choosing τ in interpretable pixel units.

The fix used by essentially every real RANSAC-for-F implementation is the Sampson distance, a first-order (linearized) approximation to the true geometric distance from a point to its epipolar line — cheap to compute (no iterative reprojection needed) but far closer to actual pixel error than the raw algebraic residual:

where (Fx̃₁)₁, (Fx̃₁)₂ denote just the first two components of the 3-vector Fx̃₁ (the line's a, b coefficients — its third component, the line's c, is left out), and similarly for Fᵀx̃₂. It comes from linearizing the true point-to-epipolar-line Euclidean distance around the current estimate of F: the numerator is the same algebraic error, and the denominator rescales it by (approximately) the local steepness of the two epipolar lines involved, converting an otherwise-arbitrary algebraic quantity into something that behaves like squared pixel distance. It's this Sampson distance, not raw x̃₂ᵀFx̃₁, that real libraries (OpenCV, COLMAP, and the rest) actually threshold against when running RANSAC over F or E.

Recap