Fit a line with ordinary least squares and one bad measurement can wreck it. Because OLS minimises the sum of squared residuals, a lone far-off point — whose squared error is enormous — pivots the whole line toward itself. Its breakdown point is zero: corrupt one observation and the estimate is arbitrarily wrong. RANSAC throws that whole approach away and does something almost cheeky instead. I built it from scratch in the browser; here's the idea.
Guess from the smallest possible sample
Instead of trusting every point at once, RANSAC hypothesises a model from the minimum number of points it takes to define one — for a line, just two. Fit that line exactly through the pair. Then count how many of the other points fall within a threshold band of it. That count is the consensus. The key move: because each guess is built from a clean minimal sample, outliers never get averaged into the fit — they simply fail to fall in the band, so they fail to vote.
best = none
repeat N times:
pick 2 random points, fit the exact line through them
count points within ±threshold of that line # the consensus set
if count > best.count: best = this model
refit least squares on best's inliers only # final polish
Keep the widest agreement, then refit
Across many random 2-point samples, the hypothesis with the widest agreement wins. But you don't ship that raw two-point line — once RANSAC knows which points are inliers, it runs a final ordinary least-squares pass on those inliers alone. That's the trick that makes it both robust and precise: RANSAC finds the clean subset, plain OLS sharpens the line through it. Outliers were never fitted; they only ever failed to consent.
Watch OLS get dragged while RANSAC holds
Side by side on the same points, the contrast is brutal. Pin inliers to a hidden line of slope 0.55, drop a cluster of outliers off to the side, and slide it up and down: the least-squares line swings wildly, chasing the cluster, while the RANSAC line barely moves. That's the breakdown point made visual — OLS breaks with a single high-leverage outlier; RANSAC keeps working as long as a clean minimal sample is still findable in reasonable time, tolerating well over half the data as outliers.
How many random tries do you need?
This is the part I love, because it's a tidy closed form. One random sample is all-inlier with probability w^s, where w is the inlier fraction and s the sample size. So it fails with probability 1 - w^s, and N independent samples all fail with probability (1 - w^s)^N. Demand that this be at most 1 - p (succeed at least once with confidence p) and solve for N:
N = ⌈ log(1 - p) / log(1 - w^s) ⌉
Two things fall out of that formula, and both explain how RANSAC behaves. N grows exponentially in the sample size s — which is exactly why RANSAC loves minimal samples (2 for a line, not 20). And N blows up as w → 0 — as outliers come to dominate, the tries you need explode, which is where RANSAC finally struggles. At w = 0.5, s = 2, p = 0.99 you need only ~16 iterations; drop w to 0.2 and it rockets into the hundreds.
The one knob you have to tune
The formula hands you N, but the threshold — how far a point can sit from the candidate line and still count as an inlier — is yours to pick, and it's the whole ballgame. Set it too tight and even honest points (with their normal measurement noise) fail to vote, so no hypothesis wins a real consensus. Set it too loose and outliers sneak into the band, dragging the final refit back toward the thing you were trying to reject. It should track the expected noise of the inliers, nothing more. That's why the demo exposes threshold, iterations and outlier count as live sliders — you can feel the trade instead of guessing it.
That's the whole method: sample a minimal set, fit, count the consensus, keep the best, refit on its inliers. No outlier ever gets a say in the fit — it just fails to make the band. Everything below runs live: scatter heavy outliers (click to add your own), watch the random 2-point samples animate with their inlier bands and per-iteration counts, and see OLS dragged off course for contrast:
Top comments (0)