P4-T4 — Robust Estimation and RANSAC

Learning objectives

After this lesson, you should be able to:

• Describe the RANSAC algorithm and the role of the minimal sample, the inlier threshold and the number of iterations.
• Compute the number of iterations needed for a desired confidence from the inlier ratio and sample size.
• Choose the inlier threshold from the measurement noise.
• Name RANSAC variants and limits, and explain how to use it in a perception pipeline.

The idea: let the data vote on a guess

Suppose you are estimating the shift between two images from 40 matches, and half are wrong. Pick one match at random and assume it is right: it suggests a shift. Count how many of the other matches agree with that shift. If you happened to pick a wrong match, almost nobody agrees. If you picked a right one, all the right matches agree. Repeat with another random pick. After enough tries the largest group of agreeing matches is almost certainly the set of correct ones.

1. Sample: choose the minimal number s of correspondences that determines the model (2 for a rotation plus shift; 4 for a homography).
2. Fit: compute the model from the sample.
3. Score: count the correspondences whose residual under the model is below the threshold t: the consensus set.
4. Keep the model with the largest consensus set so far, and repeat for N iterations.
5. Refit the model on the consensus set of the best model by least squares (Lab P4-L3, Stage 3), and optionally repeat the inlier test.

RANSAC does not identify wrong data. It finds a model that explains a large part of the data, and the wrong data are the part that remains.

The mathematics: how many tries, and what threshold

Number of iterations

Let w be the fraction of inliers. A random sample of s points is clean (all inliers) with probability w^s. The probability that all N samples contain at least one outlier is (1 − w^s)^N. To have confidence p that at least one sample is clean:

p

the desired probability of drawing at least one clean sample, typically 0.99 or 0.999.

w

the inlier ratio: fraction of correspondences that are correct. It is usually unknown and estimated while running.

s

the size of the minimal sample: 2 (similarity), 3 (affine), 4 (homography), 5 (essential matrix, calibrated cameras), 7 or 8 (fundamental matrix).

N

the number of samples to try.

The figure shows the dependence. Because of w^s, every extra point in the minimal sample costs a factor w in the chance of a clean sample, which is why models with small minimal samples are preferred and why prior knowledge (such as a known rotation from a gyroscope) that reduces s helps enormously.

Adaptive stopping

The inlier ratio is unknown at the start. A standard solution assumes the worst (N = ∞), and after each iteration updates w to the best consensus fraction seen so far, then recomputes N. The loop ends when the number of iterations done reaches N. A good model found early quickly drives N down.

The inlier threshold

The threshold t separates inliers from outliers by residual. If inlier residuals are Gaussian with standard deviation σ in each of the two image coordinates, the squared distance (d_x² + d_y²)/σ² follows a χ² distribution with 2 degrees of freedom. The 95% quantile of that distribution is 5.99, so

With σ = 0.5 pixel this gives t = 1.22 pixels. Too low a threshold rejects correct matches and leaves too little to fit; too high lets wrong matches in and makes every model look good (Lab P4-L3, Stage 1).

Variants

A worked example: iteration counts for realistic problems

For 99% confidence (p = 0.99), the number of iterations needed:

Read two rows. With 50% inliers and a two-point model the answer is 17 iterations, as in Lab P4-L3. With 50% inliers and an eight-point model it is 1177: about 69 times more samples than for pairs, for the same data quality. With 30% inliers and a homography (4 points) the number is 567, a lot of work, which explains why very poor matching can make RANSAC impractical in real time.

Adaptive stopping in action

After the first 10 samples the best consensus has 14 of 40 matches (w ≈ 0.35). With s = 4, N = 305. Sample 30 finds a model with 31 inliers, w ≈ 0.78: now N = 10, already exceeded, so the loop stops after 30 iterations instead of the 305 originally predicted. Real-time systems rely on this.

Choosing the threshold

A feature detector is accurate to about 0.7 pixel (σ). For the squared 2-D residual with σ = 0.7: t = 2.45 × 0.7 = 1.7 pixels. If you instead use 8 pixels, the region that counts as agreement around each predicted point has an area (π × 64 ≈ 200 pixels²) that is a hundred times larger than at 1.7 pixels (π × 2.9 ≈ 9 pixels²), so a wrong match lands inside it by chance a hundred times more often.

When RANSAC fails

• Too few inliers: if w is small (below about 0.2 for a 4-point model) the number of iterations explodes and a time budget ends the loop before a clean sample is found.
• Degenerate samples: sample points that are collinear, nearly identical or on a plane for a model that needs general 3D structure give a model that fits everything on that line or plane. Reject degenerate samples.
• A consistent wrong model: if many matches follow another consistent motion (a large moving object, a plane at infinity), RANSAC finds that one with equal enthusiasm.
• Wrong noise level: a threshold far from the true σ gives a poor split, however many iterations.
• Non-determinism: two runs on the same data may give slightly different inlier sets near the threshold. Refit and re-score to reduce this, and fix the random seed in tests.

Engineering implications and limitations

Use the smallest model that does the job. The cost grows as w^−s. If a gyroscope gives rotation, estimate only the translation direction; if the robot moves on a plane, use a planar model; if the camera mostly rotates, use a rotation or a homography.

Set the threshold from your noise. Measure the detector’s localisation error on data with known correspondences, then use about 2.5 σ in pixels (or the corresponding value for your model’s residual dimension). Do not copy a value from another system.

Make runs reproducible. Seed the random generator in tests, log the seed in the field, and store the inlier count and the best model so that failures can be replayed.

Bound the run time. Put a hard limit on iterations or milliseconds, and define what the system does if it ends without a good model: report “no estimate” and fall back to prediction from motion, not a guess.

Always refit and check. After RANSAC, re-estimate on all inliers, re-score with the refit model, and require a minimum number and spread of inliers (Lesson P4-T3). A model supported by 8 inliers clustered in one corner is a coincidence waiting to be a wrong pose.

Use priors to rank and gate. Sort candidates by descriptor quality (PROSAC) and gate by an odometry prediction: both raise the clean-sample probability for free.

Common misconceptions

Engineering takeaways

1. RANSAC: fit minimal random samples, count the consensus set within threshold t, keep the best, then refit on its inliers.
2. N ≥ ln(1 − p) / ln(1 − w^s): each extra point in the minimal sample multiplies the difficulty by w. For w = 0.5, s = 2, p = 0.99 it is 17 (16.0 rounded up).
3. Threshold: t ≈ 2.45 σ for 2-D residuals (95%); too low loses inliers, too high admits outliers.
4. Adaptive stopping updates w from the best consensus found so far; variants (MSAC, PROSAC, LO-RANSAC) improve scoring, speed and accuracy.
5. It fails with very low inlier ratios, degenerate samples, a dominant wrong motion and a poor threshold; bound its time and handle “no model”.

References and further reading

The iteration table was computed for this lesson from the formula.

• Fischler, M. A. and Bolles, R. C. (1981). Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM 24(6): the original paper.
• Hartley, R. and Zisserman, A. (2004). Multiple View Geometry in Computer Vision, 2nd ed. Cambridge University Press: section 4.7, robust estimation, the iteration formula and the threshold from the χ² distribution.
• Chum, O. and Matas, J. (2005). Matching with PROSAC: progressive sample consensus. CVPR.
• Chum, O., Matas, J. and Kittler, J. (2003). Locally optimized RANSAC. DAGM.
• Torr, P. H. S. and Zisserman, A. (2000). MLESAC: a new robust estimator with application to estimating image geometry. Computer Vision and Image Understanding 78(1).

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: geometric constraints that the right model must satisfy, and how to use them to verify matches.

Related content

Nothing below is required to finish this lesson.

• Before
  P4-T3: Correspondences and Outliers

  Define a correspondence, separate inliers and outliers and measure their effect.

• Lab
  P4-L3: Reject Incorrect Correspondences and Measure the Improvement

  Add RANSAC and a geometric check to a matcher and quantify the gain.