RANSAC

RANSAC (random sample consensus) estimates the parameters of a model from data in which a large fraction of the points are gross errors. Instead of fitting all the data at once, it repeatedly fits the model to a small random subset, counts how many points agree with each candidate, and keeps the candidate with the largest agreement. In computer vision it is the standard way to estimate geometry from putative correspondences between detected features: homographies, fundamental and essential matrices, and camera poses are all routinely computed inside a RANSAC loop, as in the geometric verification step of feature matching.

Martin Fischler and Robert Bolles of SRI International introduced RANSAC in a 1981 paper in Communications of the ACM. Their application was the location determination problem: given an image of landmarks with known positions, find the point in space from which the image was taken. This article describes the method as it is used today; the original formulation differed in details, such as stopping once a consensus set reaches a preset size.

Problem

Least squares treats every measurement as a noisy version of the truth. Feature matchers and detectors instead produce some measurements that are simply wrong, such as a descriptor matched to the wrong instance of a repeated window. Because the squared penalty grows without bound, one such outlier can drag a least-squares fit far from the correct answer. Fischler and Bolles described least squares as an averaging technique with no internal mechanism for rejecting gross errors. The task is to fit a model while deciding which points to trust, without knowing which or how many are outliers.

Intuition

Most random samples of $s$ points contain an outlier and produce a wrong model, but a wrong model is rarely supported by many other points, because outliers are not consistent with each other. A sample made entirely of inliers produces a model that the other inliers agree with. Drawing enough samples makes it very likely that at least one is outlier-free, and the size of its agreeing set, the consensus set, identifies it.

Algorithm

Given $n$ data points, a solver that computes the model from a minimal sample of $s$ points, a point-to-model error, an inlier threshold $t$ , and a confidence $p$ , RANSAC returns the model and its inliers:

Randomly select a minimal sample of $s$ points.
Compute the model from the sample.
Compute the error of every point under this model, and mark as inliers the points with error below $t$ .
If this model has more inliers than the best so far, store it and its inlier set, and update the required number of iterations $N$ from the new inlier ratio.
Repeat steps 1–4 until $N$ iterations have been run.
Re-estimate the model from all inliers of the best model, by least squares.

best_inliers ← ∅;  N ← ∞;  i ← 0
while i < N:
    S ← random sample of s points
    M ← fit_minimal(S)
    I ← { x : error(x, M) < t }
    if |I| > |best_inliers|:
        best_inliers ← I
        w ← |I| / n
        N ← log(1 − p) / log(1 − w^s)
    i ← i + 1
return fit_least_squares(best_inliers), best_inliers

Mathematical Formulation

Number of iterations

Let $w$ be the fraction of inliers in the data. A minimal sample of $s$ points is all inliers with probability $w^s$ , so all of $N$ independent samples are contaminated with probability $(1 - w^s)^N$ . Requiring this to be at most $1 - p$ gives the number of samples needed to draw at least one outlier-free sample with confidence $p$ :

N = \frac{\log(1 - p)}{\log\left(1 - w^{s}\right)}.

Fischler and Bolles derived this expression, along with the expected number of trials until the first all-inlier sample, $1/w^{s}$ . The table gives $N$ , rounded up, for $p = 0.99$ :

Sample size $s$	$w = 0.9$	$w = 0.7$	$w = 0.5$	$w = 0.4$	$w = 0.3$	$w = 0.2$
2 (line)	3	7	17	27	49	113
4 (homography)	5	17	72	178	567	2,876
5 (essential matrix)	6	26	146	448	1,893	14,389
7 (fundamental matrix)	8	54	588	2,809	21,055	359,777
8 (eight-point)	9	78	1,177	7,025	70,188	1,798,893

$N$ grows roughly like $w^{-s}$ : halving the inlier ratio multiplies the cost by about $2^{s}$ , which is why minimal solvers matter.

Adaptive termination

The inlier ratio is rarely known in advance. Hartley and Zisserman give the standard adaptive scheme used in the pseudocode above: start with $N = \infty$ and, whenever a model with more inliers is found, set $w$ to its inlier fraction and recompute $N$ . The best inlier count can only increase, so the estimate of $w$ grows and $N$ shrinks as better models are found. Early estimates are pessimistic, which errs toward drawing more samples; outliers that happen to fall within the threshold can make the final estimate slightly optimistic.

Choosing the threshold

If inlier measurements are corrupted by zero-mean Gaussian noise with standard deviation $\sigma$ , the squared distance $d^2$ from an inlier to the true model is $\sigma^2$ times a chi-squared variable with $m$ degrees of freedom, where $m$ is the codimension of the model: 1 for a line in the plane or for the epipolar constraint of a fundamental matrix, 2 for a homography or a camera matrix mapping points to points. Following Hartley and Zisserman, the threshold is chosen to accept a fraction $\alpha$ of true inliers:

t^2 = F_m^{-1}(\alpha)\,\sigma^2,

where $F_m$ is the chi-squared cumulative distribution function. For $\alpha = 0.95$ this gives $t^2 = 3.84\,\sigma^2$ for $m = 1$ and $t^2 = 5.99\,\sigma^2$ for $m = 2$ .

Parameters

Inlier threshold $t$ . Too small and true inliers are rejected; too large and outliers enter the consensus set, and wrong models can tie with the correct one.
Confidence $p$ . Usually 0.99 or 0.999. Because $N$ depends on $\log(1-p)$ , raising $p$ from 0.99 to 0.999 multiplies $N$ by only 1.5.
Maximum iterations. A hard cap on running time, at the price of the confidence guarantee.

Minimal Samples in Vision

The sample size $s$ is the smallest number of points that determines the model. A 2D line needs two points. A homography between two images needs four point correspondences. The fundamental matrix needs seven correspondences with the seven-point algorithm, which can return up to three solutions, or eight with the linear eight-point algorithm. The essential matrix of calibrated cameras needs five. The absolute pose of a calibrated camera from 2D–3D correspondences, the perspective-n-point problem, needs three points in its minimal form (P3P), which has up to four solutions; Fischler and Bolles named the perspective-n-point problem and analyzed P3P in their RANSAC paper. Each solution of a multi-solution solver is scored separately.

The model from the best minimal sample uses only $s$ points and is noisy, so the final step refits it to all inliers by least squares, optionally re-classifying inliers and repeating. When the linear estimate minimizes an algebraic error, as for a homography from the direct linear transform, it then initializes a nonlinear minimization of a geometric error such as reprojection error.

Implementation

The example fits a line to 100 points, 60 of them outliers, with ordinary least squares and with RANSAC (adaptive termination, chi-squared threshold, total least-squares refit on the inliers).

import numpy as np

rng = np.random.default_rng(1)

# 40 inliers near y = 2x + 1 (noise sigma = 0.3) and 60 outliers spread uniformly.
n_in, n_out, sigma = 40, 60, 0.3
x_in = rng.uniform(0, 10, n_in)
y_in = 2 * x_in + 1 + rng.normal(0, sigma, n_in)
x_out = rng.uniform(0, 10, n_out)
y_out = rng.uniform(-5, 25, n_out)
pts = np.column_stack([np.r_[x_in, x_out], np.r_[y_in, y_out]])

def fit_line(p):
    """Total least squares: line n.x = d with unit normal n (perpendicular distances)."""
    c = p.mean(axis=0)
    _, _, vt = np.linalg.svd(p - c)
    n = vt[-1]                      # direction of least spread is the normal
    return n, n @ c

def slope_intercept(n, d):
    return -n[0] / n[1], d / n[1]

# Ordinary least squares on all points.
A = np.column_stack([pts[:, 0], np.ones(len(pts))])
ls, *_ = np.linalg.lstsq(A, pts[:, 1], rcond=None)
print(f"least squares, all points: slope {ls[0]:.3f}, intercept {ls[1]:.3f}")

# Number of iterations for w = 0.4, s = 2, p = 0.99.
w, s, p = 0.4, 2, 0.99
print(f"N from formula: {np.log(1 - p) / np.log(1 - w**s):.1f}")

# Threshold: perpendicular residual is 1-D Gaussian, so t^2 = 3.84 sigma^2.
t = np.sqrt(3.84) * sigma

best_inliers, N, i = None, np.inf, 0
while i < N:
    sample = pts[rng.choice(len(pts), s, replace=False)]
    n, d = fit_line(sample)
    inliers = np.abs(pts @ n - d) < t
    if best_inliers is None or inliers.sum() > best_inliers.sum():
        best_inliers = inliers
        w_hat = inliers.mean()      # adaptive: re-estimate the inlier ratio
        N = np.log(1 - p) / np.log(1 - w_hat**s) if w_hat < 1 else 0
    i += 1

n, d = fit_line(pts[best_inliers])  # refit on all inliers
m, c = slope_intercept(n, d)
print(f"RANSAC: {i} iterations, {best_inliers.sum()} inliers "
      f"({best_inliers[:n_in].sum()} of the {n_in} true inliers)")
print(f"RANSAC refit on inliers:   slope {m:.3f}, intercept {c:.3f}")

Output:

least squares, all points: slope 0.527, intercept 7.609
N from formula: 26.4
RANSAC: 23 iterations, 43 inliers (40 of the 40 true inliers)
RANSAC refit on inliers:   slope 2.000, intercept 1.034

Least squares returns a slope of about 0.5 instead of 2, pulled toward the outlier cloud. RANSAC recovers the line from 23 samples; the formula with the true inlier ratio of 0.4 asks for 27, and the adaptive rule stopped slightly earlier because its best consensus set includes three outliers that lie within the threshold band, overestimating $w$ . All 40 true inliers are found.

Properties and Behavior

Randomized. Runs can differ; the only guarantee is probability $p$ of drawing an outlier-free sample.
Robust to a majority of outliers. Least median of squares, a robust estimator from the same era, fails once more than half the data are outliers, because the median residual is then determined by outliers. RANSAC has no such limit: it succeeds as long as the correct model has the largest consensus set, which can hold well beyond 50% outliers when the outliers are not mutually consistent, as with the 60% in the example above.
Cost. $N$ depends on $w$ and $s$ , not on $n$ ; scoring each hypothesis costs $O(n)$ , so the total is $O(Nn)$ .
Model-agnostic. RANSAC needs only a minimal solver and an error function.

Limitations

Threshold sensitivity. Results depend on the user-set threshold, and the chi-squared rule needs a noise level that is often unknown.
Degenerate configurations. A sample can be all inliers yet not determine the model uniquely, for example correspondences on a single scene plane when estimating a fundamental matrix. Such samples can produce a wrong model with large support, and plain RANSAC has no way to detect them.
Inlier count as score. A point just inside the threshold counts as much as a point on the model, so models can tie and the winner is not necessarily the most accurate.
Noisy minimal samples. A model from an all-inlier but noisy minimal sample is often not consistent with all inliers, so in practice more samples are needed than the formula predicts.
One model. Several structures, such as multiple planes or independently moving objects, need repeated or multi-model variants.

Variants

MSAC and MLESAC. Torr and Zisserman (2000) pointed out that inlier counting gives inliers zero cost and outliers a constant cost. MSAC, from their earlier work and described again in this paper, instead scores each inlier by its squared error and caps the cost of outliers, which breaks ties between models at no extra cost. MLESAC, the paper’s new estimator, scores a hypothesis by its likelihood under a mixture of Gaussian inlier noise and uniformly distributed outliers.
LO-RANSAC. Chum, Matas, and Kittler (2003) addressed noisy minimal samples with a local optimization step, run only when a new best model is found, that refines the model using its inliers. They reported two- to threefold speedups and 10–20% more inliers in their epipolar-geometry and homography experiments.
PROSAC. Chum and Matas (2005) exploit the ranking of correspondences by match quality, such as descriptor similarity from SIFT: samples are drawn from progressively larger sets of top-ranked matches rather than uniformly. In the worst case the procedure converges toward RANSAC; the authors reported that on their wide-baseline matching experiments it was often much faster, by more than a hundred times in some cases.
USAC. Raguram and colleagues (2013) organized these improvements into a framework of stages and released USAC-1.0, a C++ implementation combining PROSAC sampling, early rejection of bad models with a sequential probability ratio test, degeneracy detection for the fundamental matrix, and local optimization.
MAGSAC. Barath, Matas, and Noskova (2019) remove the user-defined threshold: instead of fixing $\sigma$ , their σ-consensus marginalizes over a range of noise scales, and the model is refined by weighted least squares with weights from that marginalization.