RANSAC

RANSAC

RANSAC (Random Sample Consensus) is a robust model-fitting algorithm that recovers the parameters of a geometric model from data contaminated by a large fraction of outliers. It is the dominant outlier-rejection scheme in computer vision and underlies robust homography, fundamental-matrix, and pose estimation inside every feature-based pipeline.

Given a data set $\mathcal{D}=\{d_i\}$ and a model class $\mathcal{M}(\theta )$ whose fit requires at least $s$ data points, RANSAC proceeds iteratively:

1. Sample. Randomly select a minimal subset of $s$ points from $\mathcal{D}$.
2. Fit. Compute the candidate model $\theta$ from this minimal sample.
3. Score. Count the inliers: points in $\mathcal{D}$ whose residual under $\theta$ is below a threshold $t$.
4. Keep. If the inlier count exceeds the best so far, store $\theta$.
5. Repeat for $N$ iterations, then refit the final $\theta$ on all inliers.

The number of iterations needed to find at least one outlier-free sample with probability $p$ is
$N=\frac{\log (1-p)}{\log (1-(1-ϵ{)}^s)},$
where $ϵ$ is the expected outlier ratio and $s$ is the minimal sample size. RANSAC handles outlier rates above 50% gracefully — the bottleneck is the minimal sample size $s$, not the outlier fraction.

Intuition

Standard least-squares fitting averages over all data points. A single gross outlier can pull the fit arbitrarily far from the true model — the breakdown point of least squares is essentially zero. In feature-based vision, “outliers” are the norm: descriptor-based matches mistake repeated textures, moving objects, and local image ambiguity for correct correspondences.

RANSAC sidesteps the problem by gambling on small subsets. Most small random samples contain at least one outlier and produce garbage models, but occasionally a sample lands on $s$ genuine inliers, producing a model that many other inliers also support. That model wins the consensus vote. The trick is that we only need to be lucky once in $N$ tries, and the success probability compounds favorably.

The key parameters — minimal sample size $s$, threshold $t$, and iterations $N$ — are all determined by the geometry: $s$ by the degrees of freedom of the model, $t$ by the expected measurement noise, and $N$ by the target success probability and the worst-case outlier ratio.

Properties

Algorithm Parameters

(Minimal sample size) $s$ is the smallest number of points that determines the model uniquely.

For a 2D line, $s=2$; a homography, $s=4$; an essential matrix via the 5-point algorithm, $s=5$; a fundamental matrix via the 8-point algorithm, $s=8$; a 3D rigid transform via P3P, $s=3$. Smaller $s$ dramatically reduces the iterations needed.

(Inlier threshold) $t$ is chosen so that inliers agree with the model to within the expected measurement noise.

A common rule: set $t$ to $\sigma \sqrt{{\chi }_k^2}$, where $\sigma$ is the per-measurement noise (e.g., 1-2 pixels for SIFT matches) and ${\chi }_k^2$ is the 95th-percentile chi-square value for $k$ residual degrees of freedom. For 2D pixel error with two DoF, $t\approx 2.45\sigma$.

(Iteration count) $N$ is set from the target success probability $p$ and the assumed outlier ratio $ϵ$.

For $p=0.99$, $s=8$, and $ϵ=0.5$, $N\approx 1177$. For $s=4$ (homography) with the same $ϵ$, $N\approx 72$. RANSAC is cheap when the minimal sample is small.

Performance Characteristics

(Adaptive iteration count) The outlier ratio is rarely known in advance; RANSAC can update $N$ online as better consensuses are found.

Start with $N=\infty$ (or a large ceiling). Each time a better model is found, re-estimate $ϵ$ as the fraction of outliers in the current best fit, and recompute $N$. Exit once the iteration counter reaches the new $N$.

(Graceful degradation with outliers) RANSAC works well up to very high outlier rates but requires more iterations.

At $ϵ=0.8$, $s=8$, $p=0.99$, the required $N$ explodes past $10^6$. Modern feature-matching pipelines use degeneracy-aware or guided-sampling variants (PROSAC, LO-RANSAC) to reduce this bound.

(Minimal-sample bias) Fitting on only $s$ points yields a noisy model; the final refit on all inliers is essential.

The initial minimal-sample fit is used only to score inliers. Once the best consensus is found, the model is re-estimated from all its inliers by least squares — this is where the numerical quality of the final fit comes from.

Variants and Extensions

(MSAC / MLESAC) Replace the 0/1 inlier count with a bounded residual cost to make the inlier threshold less sharp.

MSAC scores each point as $\min (r^2,t^2)$, turning the inlier count into a clipped squared-error sum. MLESAC models outliers as uniform and inliers as Gaussian, giving a probabilistic likelihood to maximize. Both outperform vanilla RANSAC when the threshold is hard to tune.

(PROSAC) Uses match quality (e.g., SIFT ratio-test score) to sample better matches first.

Draws minimal samples preferentially from the top-ranked correspondences, which converges faster in practice while retaining the RANSAC guarantees in the worst case.

(Locally Optimized RANSAC — LO-RANSAC) After finding a good consensus, refits on the inliers and iterates locally.

Adds a local refinement step inside the RANSAC loop that tightens the model before moving on, reducing the total iteration count.

Application Patterns

(Robust homography for mosaicing) $s=4$ point correspondences; inlier threshold $\sim 2$ px.

Used to align overlapping images for panoramas. The 4-point minimal sample makes this very fast.

(Robust essential / fundamental matrix) $s=5$ (calibrated) or $s=8$ (uncalibrated); inlier threshold based on epipolar distance.

A match $(x,x^{\prime })$ is an inlier iff the point-to-line distance from $x^{\prime }$ to $Fx$ (and its symmetric counterpart) is below $t$. This is the outlier-rejection step inside every SfM pipeline.

(Robust pose estimation — PnP + RANSAC) $s=3$ (P3P) 2D-3D correspondences; inlier threshold on reprojection error.

Used when registering a new image to an existing reconstruction. Outliers include descriptor mismatches and points on moving objects.

Examples

Line Fitting with Outliers

Given $50$ points in ${\mathbb{R}}^2$, where $30$ lie near a true line and $20$ are uniform noise:

1. $s=2$: sample two points, fit the line through them.
2. Threshold $t=1$: count points within perpendicular distance $1$.
3. Expected outlier ratio $ϵ=0.4$; for $p=0.99$, $N=\log (0.01)/\log (1-0.6^2)\approx 10$.

After 10 iterations, the best sample almost certainly lies on the true line, yielding an inlier set of $\sim 30$ points. The final fit is the least-squares line through these 30 inliers, which ignores the 20 outliers entirely.

See Also

• 4.4. Feature Matching — the noisy matches that motivate RANSAC
• 3.4. Homographies — the 4-point minimal model for planar alignment
• 5.3. Epipolar Geometry — the 8-point / 5-point epipolar model
• SfM — where RANSAC wraps PnP for view registration