Skip to main content
The robust methods of the previous section all improve a fit they already have. They reweight the data around a current estimate, so they fail when that estimate is already pulled toward the outliers. Random sample consensus (RANSAC), introduced by Fischler and Bolles in 1981, needs no starting estimate. It fits the model many times, each time to a randomly chosen subset just large enough to determine it, and keeps the fit that the most data points agree with. This section derives how many random subsets are enough, how to set the threshold that decides which points agree, and how to score and refine the winning fit. It applies RANSAC to a line and explains why it does not work for the 82-parameter grid model of the previous section. The notation follows the previous section: data (x(i),y(i))(x^{(i)}, y^{(i)}) for i=1,…,mi = 1, \ldots, m, parameters θ\boldsymbol\theta, residuals ei=y(i)−θ⊤ϕ(x(i))e_i = y^{(i)} - \boldsymbol\theta^\top\boldsymbol\phi(x^{(i)}) and inlier noise variance σ2\sigma^2. Three symbols are new. The inlier fraction is π\pi, the mixing coefficient of the inlier component in the EM inlier and outlier mixture. The size of a minimal sample, the number of data points that determine the model, is ss. The number of random trials is LL.

​
Sample, fit, score

RANSAC repeats three steps LL times:
  1. Draw a minimal sample of ss data points at random.
  2. Fit the model to those points exactly. For a line, s=2s = 2 points determine θ\boldsymbol\theta.
  3. Score the fit on all the data. The basic score is the size of the consensus set, the number of points whose residual satisfies ∣ei∣<τ|e_i| < \tau for a threshold τ\tau.
It keeps the fit with the largest consensus set and finally refits the model to that set by least squares. A sample that contains even one outlier gives a wrong line, which few points agree with. A sample of two inliers gives a line close to the true one, which all the inliers agree with. RANSAC only needs to draw one such sample. The data below have the line y=1+0.5xy = 1 + 0.5x with noise σ=0.3\sigma = 0.3, as before, but the 24 outliers among 60 points are not scattered. They lie along a second line at the right end of the range, where they have high leverage. Outliers that agree with each other are the hard case of the previous section.
The number of trials and the threshold are derived in the next two parts. The function below takes them as inputs. It also accepts a degeneracy test: two points with the same xx do not determine a line of the form θ0+θ1x\theta_0 + \theta_1 x, and the solver must reject such a sample instead of fitting it.
Scatter of 60 points: inliers along a rising line and a cluster of outliers along a falling line at the right. The RANSAC line, with a shaded band of width tau on each side, follows the inliers; the dashed least squares line is tilted toward the outlier cluster. RANSAC on a line with 24 structured outliers among 60 points. The shaded band is the inlier threshold ±τ\pm\tau around the refit line. For comparison, the code runs the methods of the previous section on the same data, each started from the least squares fit.
Least squares is tilted toward the outlier cluster, to a slope of 0.795, and the Huber and Cauchy fits stay near it. The outliers agree with each other, so once the fit leans toward them their residuals are moderate and their weights stay high. On this data EM does better: its slope is 0.506, although it puts the inlier fraction at 0.53 instead of 0.60. RANSAC needed no start, only one trial out of its 50 in which both points were inliers.

​
How many trials

When all ss of its points are inliers, a minimal sample consists only of inliers. If the points are drawn independently and the inlier fraction is π\pi, this happens with probability πs\pi^s. The probability that a trial fails to draw an all-inlier sample is 1−πs1 - \pi^s, and the probability that all LL independent trials fail is (1−πs)L(1 - \pi^s)^L. Requiring at least one all-inlier sample with probability PP means (1−πs)L≤1−P(1 - \pi^s)^L \le 1 - P, so L=⌈ln⁡(1−P)ln⁡(1−πs)⌉.L = \left\lceil \frac{\ln(1 - P)}{\ln(1 - \pi^s)} \right\rceil. PP is a confidence you choose, often 0.99 or 0.999, and every quoted number of trials depends on it. Drawing without replacement makes the true probability of an all-inlier sample slightly smaller than πs\pi^s; for mm much larger than ss the difference is negligible.
The number of trials grows quickly with ss when π\pi is low, because πs\pi^s shrinks geometrically. At P=0.999P = 0.999 and half the data wrong, the five-point solver for the essential matrix needs 218 trials and the eight-point solver 1,765. A model that can be determined from fewer points needs far fewer trials, which is the reason to prefer minimal solvers such as the five-point algorithm. The MIT vision book (Foundations of Computer Vision, n.d.) gives the same formula (Torralba, Isola and Freeman, Section 41.3.2, Eq. 41.8) and works an example: a line, s=2s = 2, with 2 outliers among 11 points, and confidence 0.95. It substitutes 0.18, the outlier fraction, for the fraction that is raised to the power ss, and reports 91 trials. The formula needs the inlier fraction, 9/11≈0.829/11 \approx 0.82.
With the inlier fraction, the formula gives three trials. With 82% inliers, two random points are both inliers with probability 0.822≈0.670.82^2 \approx 0.67, and three independent trials all fail with probability about 0.333≈0.0350.33^3 \approx 0.035, which is below 1−0.951 - 0.95. In practice π\pi is unknown. RANSAC can start with a pessimistic value and update LL whenever it finds a larger consensus set, using that set’s size divided by mm as the estimate of π\pi. The run below starts with L=1000L = 1000 on the structured line data and records each update.

​
The threshold as a chi-squared gate

The threshold τ\tau should accept a known fraction of the inliers. Under the inlier model the residual is Gaussian, ei∼N(0,σ2)e_i \sim \mathcal N(0, \sigma^2), so ei2/σ2e_i^2/\sigma^2 follows a χ2\chi^2 distribution with one degree of freedom. When the residual is a vector of dimension dd with independent components of variance σ2\sigma^2, such as the 2D reprojection error of a homography, ∥ei∥2/σ2\lVert \mathbf e_i \rVert^2/\sigma^2 follows χd2\chi^2_d. To accept an inlier with probability 1−α1 - \alpha, set τ=σχd2(1−α),\tau = \sigma\sqrt{\chi^2_d(1 - \alpha)}, where χd2(1−α)\chi^2_d(1 - \alpha) is the 1−α1 - \alpha quantile. The threshold then follows from the same noise model as the least squares fit. A larger τ\tau accepts more inliers and also lets more outliers fall inside the band.

​
Scoring: MSAC and MLESAC

Counting inliers treats every point inside the band alike and every point outside alike. Two refinements by Torr and Zisserman (2000) score hypotheses more finely. MSAC charges each point its squared residual, capped at τ2\tau^2: CMSAC(θ)=∑i=1mmin⁡(ei2,τ2).C_{\text{MSAC}}(\boldsymbol\theta) = \sum_{i=1}^{m} \min(e_i^2, \tau^2). Among hypotheses with the same consensus set it prefers the one that fits the inliers better. MLESAC goes further and scores each hypothesis by the likelihood of the inlier and outlier mixture of the EM section, −∑i=1mln⁡{π N(ei∣0,σ2)+(1−π) U},-\sum_{i=1}^{m} \ln\Big\{\pi\, \mathcal N(e_i \mid 0, \sigma^2) + (1 - \pi)\,\mathcal U\Big\}, with σ\sigma known and π\pi estimated for each hypothesis by a few EM steps on π\pi alone: compute the responsibilities γ(zi)\gamma(z_i), set π\pi to their mean, repeat. Counting inliers is the hard version of this: the test ∣ei∣<τ|e_i| < \tau replaces the responsibility γ(zi)\gamma(z_i) by 0 or 1, as the k-means indicator rikr_{ik} replaces the responsibilities γ(zik)\gamma(z_{ik}) of a Gaussian mixture. The experiment below compares the three scores on 300 data sets with the same line, 60 points and half of them uniform outliers. Each run uses 30 trials, and the code records the slope error of the best hypothesis before any refit.
MSAC and MLESAC reduce the median slope error from 0.033 to 0.030 and 0.031. The gain is small here because the line has only two parameters and the refit that follows removes most of the difference. The scores matter more when the threshold is loose, so that many hypotheses tie on the count.

​
Refinement

The winning hypothesis was fitted to only ss points, so its accuracy is that of ss noisy measurements. The final step refits the model to the whole consensus set by least squares, which uses all the inliers. Because the refit line can change which points fall inside the band, the refit and the inlier test can be repeated until the consensus set stops changing. Starting EM on the inlier and outlier mixture from the RANSAC fit goes one step further, and replaces the hard consensus set by responsibilities. It gives EM the uncontaminated start that the grid example of the previous section lacked.
Most modern variants change one of the steps above. PROSAC draws samples from the best-matching data first instead of uniformly. LO-RANSAC runs a local optimization, such as the refit above, inside the loop whenever a new best hypothesis appears. MAGSAC++ removes the single threshold by marginalizing the score over a range of noise levels.

​
Where RANSAC stops working

The grid model of the previous section has 82 columns. A minimal sample would be s=82s = 82 hours, and the probability that 82 random hours are all inliers is π82\pi^{82}. The code compares the number of trials with that of a line, at P=0.99P = 0.99.
At 95% inliers 82 hours already need 307 trials, at 90% about 26,000, and at 80% about 4×1084 \times 10^8. The storm of the previous section made about 10% of the hours outliers. A second problem is that a minimal sample must determine the model, and almost no sample of 82 hours does. Each hour of the day has its own indicator and two interaction columns, so the sample needs at least three hours at every hour of the day. Three of the 82 columns are also linear combinations of the others (the 24 hour indicators and the 7 day indicators both sum to one, and the hour-by-temperature columns sum to the temperature columns), so the design has rank 79 and no sample can determine all 82 parameters. The code builds the same 82 columns for every hour from 1 December to 19 February, with temperatures drawn at random, and counts how often a random sample of 82 hours reaches the rank of the full design.
None of the 20,000 samples had three hours at every hour of the day, and none reached the rank of the full design. RANSAC needs a minimal sample that is both all inliers and well posed, and for this model neither is available. Minimal samples work for models with few parameters, such as lines, planes, homographies, essential matrices and poses. For a regression with many parameters, the reweighting methods of the previous section are the practical choice, started from a fit you have reason to trust. The next section applies RANSAC to a plane in a point cloud, to the homography of an earlier section, and to the registration of point clouds together with ICP. Key references: (Hartley & Zisserman, 2004; Foundations of Computer Vision, n.d.; Bishop, n.d.)

​
References

  • Hartley, R., Zisserman, A. (2004). Multiple View Geometry in Computer Vision.
  • (n.d.). Foundations of Computer Vision.
  • Bishop (n.d.). Pattern Recognition and Machine Learning.
Found an error on this page? Report an issue.