RANSAC

The fundamental innovation of RANSAC is its explicit model for handling outliers. Unlike least-squares methods that minimize error for all data points, RANSAC operates on the assumption that data consists of inliers (which fit the model) and outliers (which do not).

• It randomly samples a minimal subset of points needed to instantiate a model (e.g., 2 points for a line).
• It evaluates how many data points in the full set consent to this model within a pre-defined error tolerance (the consensus set).
• The model with the largest consensus set is considered the best estimate. This makes it exceptionally robust to data corruption, sensor noise, and incorrect feature matches.

RANSAC is a hypothesis-and-test loop, not a direct optimizer. Each iteration performs three steps:

1. Hypothesis Generation: Randomly select the minimum number of data points required to define the model (e.g., 3 points for a plane, 5+ for a fundamental matrix).
2. Hypothesis Evaluation: Apply the hypothesized model to the entire dataset. Count the number of data points that are within the inlier threshold (epsilon). These points form the consensus set.
3. Model Selection: After many iterations, the model with the largest consensus set is chosen. A final least-squares refit is typically performed using only the inliers from this best model to obtain a precise, polished estimate.

RANSAC provides a probabilistic guarantee of finding the correct model. The required number of iterations (N) is not fixed but calculated to ensure, with a certain probability (p, e.g., 0.99), that at least one sample is free of outliers.

It is calculated as: N = log(1 - p) / log(1 - w^k) Where:

• w is the estimated inlier ratio (e.g., 0.6 for 60% inliers).
• k is the minimum sample size.
• This means performance degrades exponentially as the inlier ratio decreases or the model complexity (k) increases. For real-time systems, a maximum iteration cap is often enforced.

In robotics and embedded vision, RANSAC is a workhorse for geometric verification where data is noisy and outlier-prone.

• Visual Odometry / SLAM: Estimating camera pose from 2D-3D point correspondences, where many feature matches are incorrect.
• Point Cloud Registration: Finding the rigid transformation (rotation & translation) between two LiDAR scans using algorithms like Sample Consensus Initial Alignment (SAC-IA).
• Plane Detection: Extracting dominant planar surfaces (e.g., floor, walls) from depth images or 3D point clouds for navigation.
• Fundamental / Essential Matrix Estimation: Calculating the epipolar geometry between two camera views for 3D reconstruction.

While powerful, RANSAC has key limitations that engineers must design around:

• Computational Cost: The random search can be slow for complex models (high k) or low inlier ratios, as the required iterations skyrocket.
• Parameter Sensitivity: Performance depends heavily on choosing a good inlier threshold (epsilon). Too small rejects good data; too large includes outliers.
• Degenerate Samples: Random samples may be collinear or coplanar, producing invalid models. Checks for degeneracy are required.
• Single Model Assumption: Classic RANSAC finds only one dominant model. Variants like MultiRANSAC or PEARL are needed for multiple instances (e.g., detecting multiple planes).
• Non-Determinism: As a randomized algorithm, results can vary between runs, which is undesirable for deterministic systems.

Several algorithms build upon the RANSAC framework to address its weaknesses:

• MLESAC (Maximum Likelihood Estimation SAmple Consensus): Uses a probabilistic model to evaluate hypotheses, not just a binary inlier count, often yielding more accurate results.
• PROSAC (PROgressive SAmple Consensus): Samples are not drawn uniformly at random but from a progressively larger pool of high-quality data points (e.g., based on feature match score), drastically reducing iterations.
• LO-RANSAC (Locally Optimized RANSAC): Adds a local optimization step where the best model is iteratively refined using its inliers, improving precision.
• USAC (Universal RANSAC): A modern, modular framework that integrates PROSAC-like sampling, degeneracy checks, and LO-RANSAC refinement into a single, highly efficient pipeline.

Outlier rejection is the general process of identifying and removing data points that deviate significantly from the majority of a dataset, which is the core problem RANSAC solves. While RANSAC is a specific iterative algorithm, other methods exist:

• Statistical filtering: Using measures like the median absolute deviation.
• Clustering-based methods: Such as DBSCAN, which can isolate dense regions of inliers.
• Model-based verification: Fitting a preliminary model and discarding points with high residual error. RANSAC is distinguished by its probabilistic approach to finding a consensus set without requiring an initial clean dataset.

Least squares is a foundational parameter estimation method that minimizes the sum of squared residuals between observed data and a model's predictions. It is the optimization core inside RANSAC's inner loop. Once RANSAC selects a minimal sample and generates a hypothesis model, it typically uses a least squares fit on the entire consensus set to refine the model parameters.

Key Contrast: Standard least squares is highly sensitive to outliers, as a single bad data point can skew the result. RANSAC's innovation is using random sampling to find a subset of data (the inliers) where least squares can be applied safely and robustly.

Model fitting is the overarching task of finding a mathematical model that best describes a set of data points. RANSAC is a robust model-fitting algorithm designed for scenarios where the data is contaminated. Common models fitted in robotics and computer vision include:

• Homography matrices for planar scene mapping between camera views.
• Fundamental/Essential matrices for stereo camera geometry.
• Plane equations from 3D point clouds for ground plane detection.
• Polynomial curves for path planning. RANSAC excels when the model to be fitted is known (e.g., a line, circle, or specific transform) but the data is noisy and contains irrelevant structures.

RANSAC is a canonical example of the hypothesize-and-test algorithmic paradigm. This approach involves two repeated phases:

1. Hypothesize: Generate a potential model solution from a minimal, randomly selected subset of data.
2. Test: Evaluate the hypothesis against the entire dataset to find its consensus set (inliers). The hypothesis with the largest consensus set is selected. This paradigm is powerful for problems with multiple potential solutions (multi-model fitting) and is also used in other algorithms like Hough Transform for line and shape detection, though Hough Transform uses a voting scheme in a parameter space rather than direct random sampling.

PROSAC is a major enhancement to RANSAC that improves sampling efficiency. Instead of sampling data points uniformly at random, PROSAC samples from a progressively enlarged set of the top-ranked data points. It requires a preliminary quality measure for each data point (e.g., a feature matching score).

How it works:

• Data points are sorted by this quality measure.
• Early iterations only draw samples from the highest-quality points.
• The sample set is gradually expanded if no good model is found. This approach finds the correct model with far fewer iterations than standard RANSAC, especially when there is a correlation between point quality and the likelihood of being an inlier.

MLESAC modifies RANSAC's scoring function to improve the robustness of the final model selection. While standard RANSAC scores a hypothesis by the size of its consensus set (number of inliers), MLESAC uses a maximum likelihood framework.

Key difference:

• It models inlier error with a Gaussian distribution and outlier error with a uniform distribution.
• The score is the sum of likelihoods for all data points given the current model hypothesis.
• This probabilistic scoring can be more accurate than a simple inlier count, particularly when inlier noise is significant or the inlier/outlier threshold is ambiguous, leading to a better final model after least squares refinement.