RANSAC & robust estimation

Least squares assumes every measurement is a slightly noisy version of the truth. Feature matching violates that assumption catastrophically: a routine image pair produces 40–70% gross mismatches, and a single one of them can move a least-squares fit arbitrarily far. RANSAC inverts the logic — instead of fitting all the data and hoping, it repeatedly fits the smallest possible subset and asks how much of the data agrees. This page derives the trial-count formula, the threshold, the scoring variants, and the degeneracy that produces a confident wrong answer.

Symbols used on this page are defined in the Nomenclature → optimisation & robust fitting.

Companion pages: PnP and structure from motion both run inside a RANSAC loop; ICP solves the same robustness problem by a different route.

1 · Why least squares fails, quantitatively

1.1 The breakdown point

The breakdown point of an estimator is the smallest fraction of arbitrarily corrupted data that can drive the estimate to an arbitrary value. For the sample mean and for ordinary least squares it is exactly

$$ \varepsilon^\star_{\text{LS}} = \frac{1}{n} \;\xrightarrow[n\to\infty]{}\; 0 . $$

This is worth stating plainly: least squares has asymptotically zero robustness. More data does not help — it makes the breakdown point worse. The reason is structural. Least squares minimises

$$ J_{\text{LS}}(\boldsymbol\theta) = \sum_{i=1}^{n} r_i(\boldsymbol\theta)^2 , $$

and the quadratic has unbounded influence: the derivative of $r^2$ is $2r$, which grows without limit. A residual of 500 px contributes 10 000 times the gradient of a residual of 5 px, so the solution is dominated by whichever points fit worst. That is precisely backwards from what we want.

1.2 The influence function

The sensitivity of an M-estimator to a single datum is captured by the influence function $\psi(r) = \partial\rho/\partial r$, where $\rho$ is the loss. Comparing the common choices:

Note the pattern: robustness comes from bounding, then eliminating the influence of distant points. RANSAC is the extreme case — its implicit loss is a step function,

$$ \rho_{\text{RANSAC}}(r) = \begin{cases} 0, & |r| \lt t \\ 1, & |r| \ge t \end{cases} $$

so an outlier contributes a constant and has zero gradient. The cost of that ideal robustness is that the objective is no longer differentiable or convex, which is why RANSAC must search rather than descend.

2 · The algorithm

2.1 The loop

Fischler and Bolles (1981) stated it in essentially this form, and it has barely changed:

Three design choices are doing all the work, and each gets its own section below: how many trials (§3), what threshold (§4), and how to score (§5).

2.2 Why the sample must be minimal

It is tempting to draw more than $s$ points per trial for a better-conditioned fit. This is a mistake, and the reason is a probability calculation. The chance that a sample of size $k$ is all-inlier is $w^k$, where $w$ is the inlier fraction. With $w = 0.5$:

The probability decays geometrically in the sample size. Better conditioning per trial is bought at an exponential cost in the number of trials, and it is never worth it — conditioning is recovered for free at the end by refitting on the full consensus set. This is also the practical argument for the 5-point essential-matrix algorithm over the 8-point one: at $w=0.4$ it needs roughly an order of magnitude fewer trials.

3 · How many trials

3.1 The standard formula

Let $w$ be the inlier fraction, $s$ the sample size, and $p$ the desired probability of drawing at least one all-inlier sample. Sampling with replacement, the probability that a given trial is not all-inlier is $1-w^s$, so after $N$ independent trials

$$ P(\text{no clean sample in } N) = (1-w^s)^N \;\le\; 1-p , $$

which rearranges to the formula every implementation uses:

$$ \boxed{\;N \;=\; \left\lceil \frac{\log(1-p)}{\log\!\left(1-w^{s}\right)} \right\rceil\;} $$

3.2 What the numbers actually look like

For $p = 0.99$, the required $N$ grows roughly as $w^{-s}$:

Read the bottom-right corner carefully. Estimating a fundamental matrix with 20% inliers by plain RANSAC needs on the order of $3.6\times10^{5}$ trials — which is why heavily contaminated wide-baseline matching does not use plain RANSAC. It uses guided sampling (§5.4), or a better front end so that $w$ is higher to begin with. Improving $w$ is always cheaper than improving the search.

3.3 Adaptive termination

$w$ is not known in advance, so the practical version starts with $N=\infty$ and tightens it using the best consensus found so far, $\hat w = |I_{\text{best}}|/n$:

This is self-limiting in a useful way: an easy problem terminates in a handful of iterations, while a hard one keeps going. Two guards matter in practice. Clamp $N$ to a maximum so a pathological frame cannot stall a real-time loop, and clamp $\hat w$ away from 1 so that $\log(1-\hat w^s)$ cannot underflow to zero.

A subtlety in the derivation: the formula assumes sampling with replacement and independent trials. Both are mild approximations. The probability is also only about drawing one clean sample — it says nothing about whether that sample yields a good model, which is the subject of §6.

3.4 The sim

The simulation below runs the loop live. Two things are worth doing deliberately: drag the inlier fraction down and watch the required trial count explode while the point count stays fixed, and compare the amber least-squares line against the blue RANSAC line at 50% contamination — the amber line is visibly wrong even though it is the maximum-likelihood estimate under the wrong noise model.

4 · Choosing the threshold

4.1 The principled derivation

The threshold $t$ should not be guessed. If inlier residuals are zero-mean Gaussian with standard deviation $\sigma$ per coordinate, then the sum of squared residuals over $\nu$ independent coordinates is $\chi^2$ with $\nu$ degrees of freedom. Choosing a per-point false-rejection rate $\alpha$ gives

$$ t^2 = \sigma^2\,\chi^2_{\nu,\,1-\alpha} . $$

With $\alpha = 0.05$ the standard table gives:

So the familiar "about $2\sigma$ to $3\sigma$" is not folklore — it falls out of the $\chi^2$ quantile, and the exact multiplier depends on the dimensionality of the residual. Getting $\nu$ wrong is a common quiet bug: using the point-to-point multiplier for a point-to-line residual makes the threshold 25% too loose.

4.2 The trade-off, and why it is not symmetric

Threshold selection is the same false-alarm/missed-detection trade that governs fault detection elsewhere on this site (see FDI decision functions), but the two error directions have very different consequences here:

The asymmetry says: when in doubt, err tight. A tight threshold costs compute; a loose threshold costs correctness while inflating your confidence in it.

4.3 Estimating $\sigma$ when you do not know it

If the measurement noise is genuinely unknown, estimate it robustly from the residual distribution itself. The standard tool is the median absolute deviation, rescaled for consistency with the Gaussian:

$$ \hat\sigma = 1.4826 \cdot \operatorname{med}_i\left|r_i - \operatorname{med}_j r_j\right| . $$

The constant is $1/\Phi^{-1}(0.75)$ and makes $\hat\sigma$ an unbiased estimate of the standard deviation for clean Gaussian data. The MAD has a 50% breakdown point, so it survives the same contamination RANSAC is designed for. A further refinement, MLESAC and its relatives, models the residuals explicitly as a mixture of a Gaussian inlier component and a uniform outlier component and fits the mixing parameter by expectation-maximisation — which gives both $\sigma$ and $w$ without a hand-set threshold.

5 · Scoring variants

5.1 MSAC — stop throwing away the residual magnitude

Plain RANSAC's score is a bare count, so a point at $0.01t$ and a point at $0.99t$ contribute equally. That discards real information and makes the cost surface flat, with many models tying at the same count. MSAC (M-estimator SAC) keeps the same threshold but scores with a truncated quadratic:

$$ C_{\text{MSAC}} = \sum_i \rho(r_i), \qquad \rho(r) = \begin{cases} r^2, & |r| \lt t \\ t^2, & |r| \ge t \end{cases} $$

Inliers are scored by how well they fit; outliers are all capped at the same constant, so they cannot drag the solution. This is a strict improvement over the count — it costs nothing extra, breaks ties sensibly, and in practice gives a noticeably better model at the same trial count. If you are writing RANSAC from scratch, write MSAC.

5.2 LMedS — no threshold at all

Least median of squares minimises the median squared residual:

$$ \hat{\boldsymbol\theta} = \arg\min_{\boldsymbol\theta} \operatorname{med}_i r_i(\boldsymbol\theta)^2 . $$

It needs no threshold, which is genuinely appealing, and it has a 50% breakdown point. But that 50% is a hard ceiling — by construction, if more than half the data is bad the median residual is an outlier residual and the method fails. Since vision routinely exceeds 50% contamination, LMedS is the right choice mainly when the noise scale is unknown and contamination is known to be under half.

5.3 Comparing the scores

5.4 PROSAC — sample the promising matches first

Uniform sampling throws away a strong prior: the matcher already ranked its correspondences by descriptor similarity, and a better-ranked match is more likely to be an inlier. PROSAC sorts the matches by that quality score and draws early samples from a growing prefix of the sorted list, relaxing toward uniform sampling as trials accumulate. When the ranking is informative this is dramatic — often one to two orders of magnitude fewer trials — and because it degrades to plain RANSAC in the worst case, it is nearly free to adopt.

5.5 LO-RANSAC — a local optimisation inside the loop

A key observation: a model from a clean minimal sample is correct but imprecise, because it was fitted to only $s$ noisy points. Its consensus set is therefore smaller than the true inlier set, which makes the adaptive termination rule pessimistic. LO-RANSAC adds an inner refinement whenever a new best model appears — refit on the current inliers, re-classify, iterate a few times, sometimes with a shrinking threshold. The refined model finds more inliers, $\hat w$ rises, and $N$ collapses. The accepted wisdom is that LO-RANSAC gets closer to the theoretical trial count than plain RANSAC does, and it is cheap because the refinement only triggers on improvement.

6 · Degeneracy — the failure that looks like success

6.1 What goes wrong

Everything above assumes an all-inlier sample produces a good model. That assumption breaks when the sample is geometrically degenerate: the points are all correct, but they do not constrain the model. Canonical cases:

• Fundamental matrix from coplanar points. If the 7 or 8 sampled points lie on a plane, the epipolar geometry is not determined — a whole family of fundamental matrices explains them exactly. Any member of that family may score well, and the one chosen is essentially arbitrary.
• Homography from collinear points. Four points on a line do not fix a homography.
• Essential matrix under pure rotation. With no translation there is no parallax and no epipolar geometry to find; the correct answer is "translation is unobservable," but the solver returns a number anyway.
• PnP from a shallow target. Nearly coplanar 3-D points admit a two-fold pose ambiguity — see the PnP page.
• Line fit from two nearly coincident points. The direction is set by noise alone.

6.2 What to do about it

Three complementary defences, in increasing order of effort:

1. Reject degenerate samples before fitting. Cheap algebraic tests catch most of it: check that sampled points are not collinear (cross-product magnitude above a floor), not coincident (pairwise distance above a floor), and adequately spread. This costs a few flops per trial and should always be present.
2. Check the conditioning of the solve. If the minimal fit reduces to a linear system, look at the ratio of the smallest two singular values. A near-tie means the solution is not unique and the sample should be discarded.
3. Test explicitly for the known degenerate configuration. This is what DEGENSAC does for the coplanar-fundamental-matrix case: when a candidate's inliers turn out to be dominated by a single plane, it detects that, fits the plane's homography, and uses the off-plane points to resolve the remaining ambiguity — or reports that the geometry is undetermined.

There is a fourth, architectural defence: do not ask for a model the data cannot support. If a monocular front end cannot distinguish pure rotation from small translation, the system should have a parallax test that declines to triangulate, rather than a RANSAC loop that always returns something. The SfM page develops this.

7 · Cost, and how to make it fast

7.1 Where the time goes

The total cost is

$$ T \;=\; N\Big(t_{\text{sample}} + t_{\text{fit}} + n\,t_{\text{residual}}\Big) + t_{\text{refit}} , $$

and because $N$ and $n$ multiply, the consensus evaluation dominates for any non-trivial data size. For 2000 matches and 500 trials that is a million residual evaluations, against 500 tiny fits. Optimisation effort therefore belongs in the scoring loop and in reducing $N$ — not in micro-optimising the minimal solver.

7.2 The standard accelerations

7.3 A worked budget

A concrete case: a visual-odometry front end with 1200 matches, essential-matrix estimation ($s=5$), and an observed inlier fraction of 0.6. The adaptive rule gives $N = 57$ for $p=0.99$. Each trial costs one 5-point solve — which can return up to 10 real solutions, each needing its own scoring pass — plus 1200 residual evaluations per candidate. Order of magnitude:

$$ 57 \text{ trials} \times \sim4 \text{ candidate solutions} \times 1200 \text{ residuals} \;\approx\; 2.7\times10^{5} \text{ residual evaluations}. $$

At a few nanoseconds each that is well under a millisecond — comfortably real-time. Now drop the inlier fraction to 0.3: $N$ jumps to 1893, and the same budget becomes $9\times10^{6}$ evaluations, tens of milliseconds, and the frame is late. The inlier fraction is the single parameter that decides whether a RANSAC-based front end meets its deadline, which is a strong argument for investing in the matcher rather than the solver.

8 · Practical checklist

• Refit on all inliers at the end. The minimal-sample model is only a hypothesis generator; the estimate you ship comes from the least-squares refit. Skipping this leaves accuracy on the table for no reason.
• Iterate the refit once or twice. After refitting, re-classify inliers with the better model and refit again. This usually recovers a few more inliers and converges in 2–3 rounds.
• Normalise coordinates before any linear fit. Hartley normalisation — translate to zero mean, scale so the mean distance from the origin is $\sqrt2$ — is not optional for fundamental/homography estimation. Without it the linear system is badly conditioned and the result is visibly worse.
• Score with MSAC, not a count. Free, and it breaks ties correctly.
• Derive the threshold from $\sigma$ and the residual dimension via the $\chi^2$ quantile (§4.1); do not copy a magic number from another codebase with a different residual.
• Guard against degeneracy explicitly (§6.2). This is the failure that produces confident nonsense.
• Cap the trials and report failure when the cap is hit.
• Fix the seed in tests. RANSAC is randomised, so an unseeded implementation gives irreproducible results and flaky tests. Seed deterministically per frame.
• Record $\hat w$ as a health metric. A falling inlier fraction is an early, sensitive indicator of a front-end problem — bad exposure, motion blur, a dirty lens — long before the pose itself looks wrong.

9 · Further reading

• Fischler & Bolles (1981), "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography," Comm. ACM 24(6). The original; still worth reading for the framing.
• Hartley & Zisserman, Multiple View Geometry in Computer Vision, 2nd ed. The standard reference for RANSAC in a geometric-vision context, including threshold selection and normalisation.
• Torr & Zisserman (2000), "MLESAC: A New Robust Estimator with Application to Estimating Image Geometry." Introduces MSAC and MLESAC.
• Chum & Matas (2005), "Matching with PROSAC — Progressive Sample Consensus."
• Chum, Matas & Kittler (2003), "Locally Optimized RANSAC."
• Chum, Werner & Matas (2005), "Two-View Geometry Estimation Unaffected by a Dominant Plane" — the DEGENSAC paper, and the clearest treatment of degeneracy.
• Raguram et al. (2013), "USAC: A Universal Framework for Random Sample Consensus," IEEE TPAMI. Unifies the variants and is the right starting point for a modern implementation.
• Barath et al. (2020), "MAGSAC++, a Fast, Reliable and Accurate Robust Estimator." Removes the threshold by marginalising over the noise scale.
• Rousseeuw (1984), "Least Median of Squares Regression," JASA 79. The statistics-side origin of LMedS and the breakdown-point framing.

Related pages: ICP & registration · PnP · Structure from motion · Bundle adjustment · FDI decision functions