Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography

“Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography” is a paper by Martin A. Fischler and Robert C. Bolles of SRI International, published in the Graphics and Image Processing section of Communications of the ACM in June 1981. The work was supported by DARPA, and an earlier version appeared in 1980 as SRI Technical Note 213 and in the proceedings of the DARPA Image Understanding Workshop. The paper introduced RANSAC, a way to fit a model to data containing gross errors, and devoted most of its length to one application, the location determination problem (LDP): finding the point in space from which an image of known landmarks was taken.

Problem

Classical estimators such as least squares fit a model to all the data. The authors call them averaging techniques with no internal mechanism for rejecting gross errors, resting on a “smoothing assumption” that there will always be enough good values to average out a bad one.

The common remedy was to fit all the data, delete the point that agrees least with the fit, and repeat until the largest deviation falls below a threshold. Figure 1 of the paper shows this failing on seven points, six on a line and one gross error at (10, 2), with a tolerance of 0.8: the procedure stops after four iterations with four points, the gross error among them, fitted by the wrong line.

The source of gross errors in image analysis is the local feature detector. Its measurement errors, small mislocations, are roughly normal and average out; its classification errors, features reported where there are none, do not. In photogrammetric practice a human operator established correspondences between image points and control points; a fully automated system has no such screen.

Contribution

• The RANSAC paradigm. Instead of starting from as much data as possible and pruning, start from the smallest set that determines the model and enlarge it with consistent data.
• Rules for its three parameters: the error tolerance, the number of trials, and the size of an acceptable consensus set.
• An analysis of what the paper calls the perspective-$n$-point problem: the minimum number of landmarks for a finite set of solutions, a closed-form solution for three points, and examples showing that solutions are not always unique.
• A RANSAC-based LDP system, tested on synthetic and real data.

Method

The paradigm

Given a model that needs a minimum of $n$ points to instantiate, randomly select $n$ points, instantiate the model, and find the points within some error tolerance of it, the consensus set. If the consensus set has at least $t$ members, refit the model to it, possibly by least squares, and stop. Otherwise draw a new sample. After a predetermined number of trials, either fit the largest consensus set found or report failure.

The paper suggests two refinements: a deterministic choice of samples when the problem gives a reason to prefer some points, and, once a good consensus set is found, adding all newly consistent points and refitting.

Parameters

The error tolerance can sometimes be derived analytically; otherwise the paper suggests perturbing the data, recomputing the model, and setting the tolerance one or two standard deviations beyond the measured average error. Because measurement errors are small compared with gross errors, one tolerance for all data is often enough.

For the number of trials, let $w$ be the probability that a selected point is within tolerance of the model. A sample is error-free with probability $w^n$, so the number of draws $k$ until the first error-free sample has expected value and standard deviation

$$E(k) = w^{-n}, \qquad SD(k) = \frac{\sqrt{1 - w^{n}}}{w^{n}}.$$

Since $SD(k)$ is close to $E(k)$, the authors suggest two or three times $E(k)$ trials. Alternatively, to obtain at least one error-free sample with probability $z$,

$$k = \frac{\log(1 - z)}{\log(1 - w^{n})}.$$

For $w = 0.5$ and $n = 4$, $E(k) = 16$ and 90 percent assurance needs $k = 35.7$ trials. This formula, with $z$ usually written $p$, remains the standard way to set the number of RANSAC iterations.

The consensus threshold $t$ has two jobs: to ensure that the model is correct and to supply enough points for the final fit. If $y$ is the probability that a point falls within tolerance of a wrong model, $y^{t-n}$ should be small; assuming $y < 0.5$, the paper notes that $t - n = 5$ gives better than 95 percent assurance. On the seven-point example, sampling pairs finds the six valid points within two or three expected trials, and all 21 pairs can simply be tried.

The perspective-n-point problem

The paper notes that the LDP is also known as determining exterior camera orientation or as the camera calibration problem. Assuming known 3D control points and a known focal length and principal point (see camera parameters), the angle between the rays to any two control points follows from the image, and the LDP reduces to finding the lengths of the rays from the center of perspective to the control points: the perspective-$n$-point problem, PnP.

One or two points leave infinitely many solutions; for two points, the center lies anywhere on a circle through them rotated about their chord. Three points give three law-of-cosines equations in the unknown leg lengths $a$, $b$, $c$ of a tetrahedron whose base is the known triangle:

$$R_{ab}^2 = a^2 + b^2 - 2ab\cos\theta_{ab},$$

and two more for the pairs $ac$ and $bc$. By the product of the degrees, the system has at most eight solutions; because every term has degree zero or two, each positive solution has a mirror solution with all signs negated, so there are at most four positive solutions. The paper constructs an example that attains four, an equilateral base with legs of length 4, and Appendix A derives a closed form by reducing the system to a quartic in the ratio $x = b/a$.

For four points, the paper gives a technique that always produces a unique solution when the control points are coplanar (Appendix B), and an example with two solutions when they are not. A five-point example also has two solutions. Six points in general position give a unique solution, through a linear solve for the $3 \times 4$ projection matrix (see the pinhole camera model).

RANSAC/LD

The full algorithm selects triples of correspondences quasirandomly, to spread them out in space, solves P3P for each, and treats multiple solutions as separate samples. Perturbing the three image points gives an error estimate for the camera position, from which error ellipses decide which other correspondences join the consensus set. A consensus set of at least $t$, nominally between 7 and $mw$ for $m$ correspondences, goes to a least-squares routine for the final camera location and orientation.

Results

The paper reports three experiments. In a 20-landmark problem with five gross errors of more than 10 pixels and one-pixel noise on the rest, the worst-residual pruning heuristic removed two gross errors, then stopped and returned a solution based on 18 correspondences, three of them wrong. RANSAC found the correct solution on its second triple, with a final consensus set containing every good correspondence and no gross errors.

On 50 synthetic problems with 30 correspondences each, viewed from overhead and obliquely, a table of ten typical problems with $w = 0.8$ and $w = 0.6$ shows that RANSAC kept gross errors out of the final consensus set in every case, after between one and eleven triples. The authors reported about one second per camera position considered.

In the cartographic test, cross-correlation located 25 landmarks in an aerial image taken from about 4,000 feet and digitized at 2,000 by 2,000 pixels, roughly 2 feet per pixel; three locations were wrong. RANSAC found a consensus set of 17 on its first triple and extended it to all 22 good correspondences after an initial least-squares fit. The reported standard deviations of the camera position were 0.1, 6.4, and 2.1 feet, and those of heading, pitch, and roll between 0.01 and 0.12 degrees.

Impact

Fitting minimal samples and scoring them by consensus became the standard way to estimate geometric models from putative matches: homographies, fundamental matrices, essential matrices, and camera poses are routinely computed inside a RANSAC loop, as in the geometric verification step of feature matching. Raguram and colleagues (2013) call RANSAC one of the most popular tools for robust estimation. In their review of three-point pose estimation, Haralick and colleagues (1994) credit the paper as the computer vision community’s first, independently derived, direct P3P solution.

The short Python script below reproduces two worked examples from the paper: the trial counts for $w = 0.5$, $n = 4$, and the P3P example with four solutions, built from the paper’s quartic coefficients (Eqs. A19–A23).

import numpy as np

# Number of trials (Section II.B): w = 0.5, n = 4, z = 0.90.
w, n, z = 0.5, 4, 0.90
b = w**n
print(f"E(k) = {1 / b:.1f}, SD(k) = {np.sqrt(1 - b) / b:.1f}, "
      f"k = {np.log(1 - z) / np.log(1 - b):.1f}")

# P3P example of Figure 5: equilateral base of side 2*sqrt(3), all legs 4.
Rab = Rac = Rbc = 2 * np.sqrt(3)
cab = cac = cbc = (4**2 + 4**2 - Rab**2) / (2 * 4 * 4)   # cos = 5/8
K1, K2 = Rbc**2 / Rac**2, Rbc**2 / Rab**2                 # (A10)

# Coefficients of the quartic in x = b/a, Eqs. (A19)-(A23).
G4 = (K1*K2 - K1 - K2)**2 - 4*K1*K2*cbc**2
G3 = (4*(K1*K2 - K1 - K2)*K2*(1 - K1)*cab
      + 4*K1*cbc*((K1*K2 + K2 - K1)*cac + 2*K2*cab*cbc))
G2 = ((2*K2*(1 - K1)*cab)**2
      + 2*(K1*K2 + K1 - K2)*(K1*K2 - K1 - K2)
      + 4*K1*((K1 - K2)*cbc**2 + (1 - K2)*K1*cac**2
              - 2*K2*(1 + K1)*cab*cac*cbc))
G1 = (4*(K1*K2 + K1 - K2)*K2*(1 - K1)*cab
      + 4*K1*((K1*K2 - K1 + K2)*cac*cbc + 2*K1*K2*cab*cac**2))
G0 = (K1*K2 + K1 - K2)**2 - 4*K1**2*K2*cac**2
print("quartic coefficients:", np.round([G4, G3, G2, G1, G0], 6))

roots = np.roots([G4, G3, G2, G1, G0])
real = roots[np.abs(roots.imag) < 1e-6].real    # 1 is a double root
print("real roots x:", np.round(np.sort(real), 6))
xs = np.unique(np.round(real, 6))

# Leg lengths: a from (A24), b = a x, then y = c/a from (A5); keep (a, b, c)
# that also satisfy (A3).
solutions = set()
for x in xs[xs > 0]:
    a = Rab / np.sqrt(x**2 - 2*x*cab + 1)
    for y in np.roots([1, -2*cac, 1 - Rac**2 / a**2]):
        if abs(y.imag) > 1e-9 or y.real <= 0:
            continue
        lb, lc = a * x, a * y.real
        if abs(lb**2 + lc**2 - 2*lb*lc*cbc - Rbc**2) < 1e-6:
            solutions.add((round(a, 6), round(lb, 6), round(lc, 6)))
for a, lb, lc in sorted(solutions, reverse=True):
    print(f"legs a = {a:g}, b = {lb:g}, c = {lc:g}")

Output:

E(k) = 16.0, SD(k) = 15.5, k = 35.7
quartic coefficients: [-0.5625    3.515625 -5.90625   3.515625 -0.5625  ]
real roots x: [0.25 1.   1.   4.  ]
legs a = 4, b = 4, c = 4
legs a = 4, b = 4, c = 1
legs a = 4, b = 1, c = 4
legs a = 1, b = 4, c = 4

The coefficients, roots, and four leg-length solutions match the paper. The double root $x = 1$ yields two solutions, which is why the paper notes that the quartic alone does not establish the bound of four.

Limitations

The paper’s historical claims were incomplete. Its conclusion states that the photogrammetric literature offered no analytic solution to perspective-$n$-point problems beyond least-squares variants and the iterative Church method. Haralick and colleagues (1994) trace direct solutions back to the German mathematician Grunert in 1841, followed by solutions in the German and then American photogrammetric literature. They also showed that the accuracy of closed-form P3P solutions depends on the order of substitutions, with relative errors differing by over a thousand to one, an issue the 1981 paper does not consider.

The error tolerance, the inlier probability $w$, and the consensus threshold $t$ are all left to the user, and stopping as soon as a consensus set reaches $t$ accepts the first adequate model rather than the best one. Consensus size is a coarse score: every point within tolerance counts equally. The maximum number of solutions for four and five non-coplanar points was left open, and the evaluation was limited to synthetic problems and one aerial image.

What Came After

Torr and Zisserman’s MLESAC (2000) kept random sampling but chose the hypothesis that maximizes likelihood rather than the number of inliers. Chum, Matas, and Kittler (2003) observed that RANSAC needs considerably more samples than its model predicts and added a local optimization of the best-so-far hypotheses (LO-RANSAC). PROSAC (Chum and Matas, 2005) replaced uniform sampling with sampling from progressively larger sets of correspondences ranked by match quality; it converges to RANSAC in the worst case, and the authors reported speedups of more than a hundred times in some wide-baseline matching experiments. Raguram and colleagues (2013) organized these and other improvements into the USAC framework with a C++ library. MAGSAC (Barath, Matas, and Noskova, 2019) removed the user-defined inlier threshold by marginalizing over a range of noise scales.