M-estimators approach robustness by down-weighting outliers—reducing their influence on the final estimate. But what if you could simply ignore outliers entirely? What if, instead of trying to accommodate bad data, you could find the good data and estimate from that alone?

RANSAC (Random Sample Consensus), introduced by Martin Fischler and Robert Bolles in 1981, takes exactly this approach. It represents a fundamental paradigm shift: rather than treating all data as coming from one (possibly contaminated) distribution, RANSAC explicitly models data as a mixture of inliers (data that fits the model) and outliers (data that doesn't).

The key insight is beautifully simple: if you randomly select a small subset of data points, there's a reasonable probability that subset contains only inliers. From that clean subset, you can fit a perfect model—and then identify which other points are also inliers by checking consistency.

RANSAC has achieved legendary status in computer vision, where it solved problems that had resisted decades of traditional approaches. Fitting lines to edge detections, estimating camera transformations, matching features across images—tasks where 50% or more of the data might be spurious—became tractable through RANSAC.

This page provides complete coverage of RANSAC: the algorithm, its theoretical foundations, parameter selection, variants, and practical implementation considerations.

The Core Algorithm:

RANSAC operates through repeated random sampling and hypothesis testing. Here's the complete procedure:

Input:

• Data points ${(\mathbf{x}i, y_i)}{i=1}^n$
• Minimum sample size $s$ (minimum points needed to fit model)
• Inlier threshold $t$ (maximum residual for point to be considered inlier)
• Number of iterations $k$
• Minimum inlier count $d$ (optional, for early termination)

Algorithm:

best_model ← null
best_inliers ← ∅
best_error ← ∞

for iteration = 1 to k:
    # Step 1: Randomly select s points
    sample ← random_sample(data, size=s)
    
    # Step 2: Fit model to the sample
    candidate_model ← fit_model(sample)
    
    # Step 3: Find all inliers (points consistent with model)
    inliers ← {i : |y_i - predict(candidate_model, x_i)| < t}
    
    # Step 4: If enough inliers, refit and evaluate
    if |inliers| ≥ d:
        refined_model ← fit_model(data[inliers])
        error ← compute_error(refined_model, data[inliers])
        
        if |inliers| > |best_inliers| or error < best_error:
            best_model ← refined_model
            best_inliers ← inliers
            best_error ← error

return best_model, best_inliers

Intuition:

Each iteration takes a bet: "Maybe these $s$ points are all inliers." If they are, the fitted model will be correct, and checking against all points will reveal many more inliers. If the sample included an outlier, the model will be wrong, few points will be consistent, and we move on.

By trying many random samples, we maximize the probability of eventually finding a purely inlier sample.

The most important parameter in RANSAC is $k$, the number of iterations. Too few iterations and you might never sample all inliers; too many and computation is wasted.

Probabilistic derivation:

Let $w$ be the probability that any randomly selected point is an inlier (the "inlier ratio"). For a sample of size $s$:

• Probability that all $s$ points are inliers: $w^s$
• Probability that at least one is an outlier: $1 - w^s$

After $k$ iterations:

• Probability of never finding an all-inlier sample: $(1 - w^s)^k$

We want this failure probability to be at most $p$ (typically $p = 0.01$ or $p = 0.001$):

$$(1 - w^s)^k \leq p$$

Solving for $k$:

$$k \geq \frac{\log(p)}{\log(1 - w^s)}$$

The formula in practice:

$$k = \left\lceil \frac{\log(p)}{\log(1 - w^s)} \right\rceil$$

Adaptive iteration count:

In practice, we don't know $w$ in advance. A clever adaptation estimates $w$ on the fly:

1. Start with a conservative $k$ (e.g., based on worst-case $w = 0.5$)
2. When a new best model is found, estimate $w$ as |inliers|/n
3. Recompute $k$ using this new $w$ estimate
4. Continue until $k$ iterations completed or confidence threshold met

This adaptive approach often terminates much faster than worst-case bounds suggest.

The threshold $t$ determines which points are classified as inliers. This parameter critically affects RANSAC performance:

• $t$ too small: True inliers may be incorrectly rejected as outliers
• $t$ too large: Outliers may be incorrectly accepted as inliers

Statistical approach:

Under a Gaussian noise model with standard deviation $\sigma$:

• 95% of inliers have $|r| < 1.96\sigma$
• 99% of inliers have $|r| < 2.576\sigma$
• 99.7% of inliers have $|r| < 3\sigma$

A common choice is $t = 2.5\sigma$ (covers ~99% of inliers under Gaussian noise).

When σ is unknown:

Estimate $\sigma$ from:

1. Prior knowledge about measurement noise
2. Median Absolute Deviation (MAD) of residuals from an initial robust fit
3. Scale of the data (domain knowledge)

Chi-squared approach (for multi-dimensional errors):

When errors are multi-dimensional (e.g., 2D point distances), use the Mahalanobis distance:

$$d^2 = \mathbf{e}^\top \Sigma^{-1} \mathbf{e}$$

Under Gaussian errors, $d^2 \sim \chi^2_m$ where $m$ is the dimension. Set threshold using $\chi^2$ quantiles:

• $t^2 = \chi^2_{m, 0.95}$ includes 95% of inliers

RANSAC and M-estimators represent fundamentally different philosophies for handling outliers. Understanding when to use each is crucial for effective robust estimation.

The basic RANSAC algorithm has inspired numerous variants addressing its limitations:

1. MSAC (M-estimator Sample Consensus)

Instead of counting inliers (hard threshold), use a robust score:

$$\text{Score} = \sum_{i=1}^n \rho(r_i)$$

where $\rho$ is a truncated quadratic: $$\rho(r) = \min(r^2, t^2)$$

Inliers contribute their squared residual; outliers contribute $t^2$. This creates smoother score landscapes.

2. MLESAC (Maximum Likelihood Estimation Sample Consensus)

Models data as mixture of inliers (Gaussian) and outliers (uniform):

$$P(r_i) = \gamma \cdot \mathcal{N}(r_i; 0, \sigma^2) + (1-\gamma) \cdot U(r_i; a, b)$$

Maximizes likelihood instead of counting inliers. Automatically estimates inlier fraction $\gamma$.

3. LO-RANSAC (Locally Optimized RANSAC)

When a good model is found, perform local optimization on nearby samples before continuing. Finds better models with fewer iterations.

4. PROSAC (Progressive Sample Consensus)

Uses prior quality scores on points (e.g., feature match confidence). Samples high-quality points first, finding good models faster when quality information is available.

What's next:

We've now covered the two main paradigms for robust estimation: M-estimators (which down-weight outliers) and RANSAC (which identifies and removes them). The next page introduces breakdown point—the formal measure of how much contamination an estimator can tolerate before completely failing. This theoretical concept provides rigorous foundations for comparing robustness across methods.