Outliers, RANSAC and robust estimation

One bad point, and the line goes with it

Imagine forty points scattered around the line y = 1 + 1.2x, each nudged by small measurement noise, plus a handful of gross errors that land far below the line. The least-squares fit chooses the slope and intercept that minimise the sum of squared vertical gaps. Every honest point contributes a term of order a tenth; each gross error contributes a term of order a hundred. The optimiser does the rational thing: it moves the line down, sacrificing a little accuracy everywhere to claw back a lot of squared error in the few bad spots. The fit you wanted is gone, and the culprit is not the arithmetic but the loss.

Notice how asymmetric the trade is. Halving a large residual cuts its contribution to a quarter; halving many small residuals barely changes the total. So the optimiser always prefers to shave the biggest gap, no matter how many small gaps it spoils. This is the fingerprint of unbounded influence: push one data point to infinity and the least-squares line chases it there, at a speed that never drops to zero. Statisticians say the breakdown point of least squares is zero — it takes exactly one contaminated observation to destroy the estimate, whatever the sample size.

The Gaussian story explains why we ever put up with this. If the errors really were Gaussian, huge residuals really would be astronomically unlikely, and squaring them would be the correct likelihood. Least squares would then be not just reasonable but optimal, attaining the Cramér–Rao bound. The trouble is that real sensors, real annotations and real correspondences do not have Gaussian tails. They have tails heavy enough that a large error is merely unusual rather than impossible, and the quadratic loss badly misprices those events.

So the question this part answers is concrete: given data you cannot fully trust, how do you recover the line the honest majority implies? Two strategies follow, and they are complementary. One throws suspicious points away before fitting, by searching for the largest set of points that agree on a single model. The other keeps every point but redesigns the loss so that a large residual is simply not worth chasing.

Least squares is a likelihood in disguise

Write the model as $y_i = x_i^\top\beta + \varepsilon_i$ with the errors assumed independent and Gaussian, $\varepsilon_i\sim\mathcal N(0,\sigma^2)$. The likelihood of the data is a product of bell curves, one per observation. Take its logarithm and the product becomes a sum, and the only term that depends on the parameters is the sum of squared residuals, divided by $2\sigma^2$ and negated. Maximising the likelihood is therefore exactly minimising $\sum_i r_i^2$. The familiar normal equations, the closed-form slope and intercept, the whole apparatus falls out of a single modelling assumption.

That assumption is also the vulnerability. A Gaussian density decays like $e^{-r^2/2\sigma^2}$, so a residual of ten standard deviations is assigned a probability a bookmaker would treat as zero. The likelihood "believes" such a point cannot occur, so when it does occur the fit pays a price proportional to r^2 to reduce it — a price that grows without bound. In the language of robust statistics, the influence function of the squared loss is 2r, which is proportional to the residual and therefore unbounded: the further the point, the harder it pulls, forever.

There is a second, subtler cost. Even with no gross errors, Gaussian noise is a strong claim about how often moderate residuals appear. Real error distributions are often better described by a Student-t or a mixture: mostly small errors, with a definite sprinkle of larger ones. Under such a distribution the quadratic loss is no longer the maximum-likelihood choice, and a robust loss with a bounded influence function is both more efficient and far less fragile.

The demo below makes the failure visceral. The cloud on the left is the honest data; the slider drops a growing clump of gross errors below it. Watch the solid least-squares line peel away from the dashed true line even though the majority of the points never move. The last readout is the total squared error: it grows, not linearly with the number of bad points, but with the square of how far they sit, which is the unbounded sensitivity made arithmetic.

One should not conclude that least squares is a bad method. Given clean Gaussian data it is the best linear unbiased estimator, and it is fast and differentiable, which matters enormously in the gradient-based pipelines that fit large models. The lesson is narrower and more useful: the squared loss is a bet on thin tails, and you should check that bet before you rely on it. When the tails are fat, a bounded-influence loss or an explicit consensus search keeps you honest.

Trust the largest agreeing set, not the average

If a few points are wrong, the cleanest defence is to fit to a subset that excludes them — but you do not know which subset. RANSAC, for RANdom SAmple Consensus, sidesteps the question by guessing. It repeatedly draws the smallest number of points that determines a model, fits that model exactly, and then counts how many of the remaining points agree with it within a tolerance. The model with the most agreeing points is declared the consensus, and the inliers supporting it are used for a final fit. A line needs two points; a homography needs four; the principle is the same at every scale.

The remarkable part is that the number of guesses needed is a closed-form function of two things you can estimate: the fraction w of inliers and the size s of the minimal sample. A single draw contains only inliers with probability w^s. The chance that at least one of N independent draws is all-inlier is 1-(1-w^s)^N, and setting that equal to a target confidence p and solving for N gives the iteration budget every vision textbook quotes.

The formula is brutally sensitive to w and s. With half the points inliers and s=2, a ninety-nine percent confidence costs about seventeen draws. Drop to a quarter inliers and the same confidence costs about seventy-three. Raise s to four, as a homography forces you to, and a quarter-inlier problem needs nearly six thousand ones. This is why RANSAC is paired with a cheap way to raise w: loose thresholds initially, local-feature pruning, or a coarse model that removes obvious mismatches first.

The threshold matters as much as the count. Too tight and honest points fall outside the consensus, so the count is noisy; too loose and outliers are welcomed in, so the best model is corrupted. In practice the threshold is set from the measurement noise — a few pixels of reprojection error, a couple of millimetres of range error — and a squared-distance test inside the loop avoids needless square roots. The animation below lets you set it by hand and watch the inlier highlight change shape as you do.

Two refinements are worth knowing. First, when the inlier ratio is unknown you can update w from the best consensus found so far and recompute N on the fly, stopping early once the budget for the current estimate is exhausted — the animation shows this adaptive count in the readout. Second, the final model should be re-fit to all inliers rather than kept from the minimal sample, because a line through two points has no redundancy. RANSAC finds the consensus; a least-squares fit over that consensus, now with the outliers gone, supplies the accuracy.

Keep every point, but let it pull only so hard

RANSAC discards points. A gentler idea keeps them all and changes the price of a large residual. Replace the quadratic $\rho(r)=\tfrac12 r^2$ with any function that grows more slowly, and minimise $\sum_i\rho(r_i)$. The derivative $\psi=\rho'$ is the influence function: it sets how hard a point of residual r pulls the fit. For the squared loss $\psi(r)=r$, unbounded. Robust losses are designed so that $\psi$ is bounded, or even falls back to zero, so that no single point can ever dominate.

The Huber loss is the mildest repair. It stays exactly quadratic for small residuals, so it keeps the smoothness and efficiency of least squares where it matters, and switches to a straight line of slope $\delta$ beyond that point. Its influence function is r up to $\delta$ and then flat at $\delta$: every outlier, however far, pulls with the same bounded force. The parameter $\delta$ is the scale at which you stop believing the error is Gaussian; setting it near one or two standard deviations of the honest noise is a common choice.

The Cauchy loss is more aggressive: its influence function is $\psi(r)=r/(1+(r/c)^2)$, which rises, peaks at r=c, and then decays back to zero. In robust-statistics language it is redescending — at some point additional distance makes a point matter less, not more. The heavier-tailed Student-t likelihood produces a closely related loss, which is why t-distributed error models and Cauchy M-estimators feel like the same tool seen from two sides. Tukey's biweight goes all the way: it gives a residual beyond c literally zero weight, so flagrant outliers are ignored completely.

How do you minimise a loss with a bounded influence function? With iteratively reweighted least squares, or IRLS. Start from any fit, compute each residual, convert it to a weight $w_i=\psi(r_i)/r_i$ — one for small residuals, smaller for large ones, zero for the rejected ones — and solve a weighted least-squares problem. The weights change, so iterate until the fit stops moving. A few dozen iterations always suffice, and each step is as cheap as the closed-form least-squares solve. The price of a non-convex loss such as Tukey's is that the answer can depend on where you start; beginning from the least-squares fit, or from a RANSAC consensus, removes the ambiguity.

The three demos below share one set of controls. The first canvas shows the loss $\rho(r)$, the second the weight w(r) each method assigns to a residual of size r, and the third runs IRLS on contaminated regression data so you can compare the robust fit with the least-squares fit directly. Drag $\delta$ and c, and switch the highlighted loss, to see how the weight you keep translates into a line you can trust.

Nothing here is a free lunch. Huber gains robustness to outliers while giving up some efficiency under perfect Gaussian noise, and choosing $\delta$ is a bet about scale. Cauchy and Tukey are more resistant still but non-convex, so they reward a good starting point and can settle on different answers from different initialisations. The honest summary is that robustness is a modelling choice: you are replacing the claim "errors are Gaussian" with the claim "errors are heavy-tailed and a fraction of the data is wrong", and each loss expresses a slightly different version of that second claim.

Robustness wherever data is cheap and dirty

Every formula in one place

Where to go deeper

• P. J. Huber, Robust Statistics, Wiley, 1981 — the Huber loss and the influence-function machinery that frames the whole subject.
• P. J. Rousseeuw and A. M. Leroy, Robust Regression and Outlier Detection, Wiley, 1987 — least median of squares, breakdown points, and the Tukey biweight in practice.
• M. A. Fischler and R. C. Bolles, "Random Sample Consensus", Communications of the ACM, 1981 — the original RANSAC paper, including the iteration formula.
• R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, chapter 4 — RANSAC for the eight-point algorithm and for homography estimation.
• F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw and W. A. Stahel, Robust Statistics: The Approach Based on Influence Functions, Wiley, 1986 — redescending estimators and the theory of their multiple minima.