RANSAC

The defining feature of RANSAC is its robustness. Unlike standard least-squares estimators, which are highly sensitive to outliers, RANSAC explicitly assumes the data is composed of inliers (data that fits the model) and outliers (gross errors or noise). It works by iteratively selecting random minimal subsets of data to hypothesize a model, then evaluating that model against the entire dataset to find a consensus set. The final model is estimated from the largest consensus set found, effectively ignoring the outliers.

• Key Mechanism: Separates inliers from outliers during the estimation process.
• Typical Use: Essential in computer vision where feature matching often produces many incorrect correspondences.

RANSAC operates through a repeated hypothesize-and-verify loop. Each iteration consists of two main steps:

1. Hypothesis Generation: A minimal sample set (MSS) is randomly selected from the data. For a line, this is 2 points; for a homography, it's 4 point correspondences. Model parameters are computed exactly from this minimal set.
2. Consensus Evaluation: The hypothesized model is tested against all data points. Points within a pre-defined error tolerance (threshold) are counted as part of the model's consensus set (inliers).

The algorithm runs for a fixed number of iterations or until a stopping criterion is met, retaining the model with the largest consensus set.

RANSAC's efficiency and success probability are governed by key parameters:

• Minimal Sample Set (MSS): The smallest number of data points required to uniquely determine the model parameters. Using the MSS minimizes the probability of selecting an outlier in the hypothesis stage.
• Stopping Criterion: The number of iterations, N, is not arbitrary. It is adaptively computed to ensure, with a high probability (e.g., 99%), that at least one sample is free of outliers. The formula is: N = log(1 - p) / log(1 - w^s) where p is the desired confidence, w is the inlier ratio (estimated), and s is the size of the MSS. This makes RANSAC adaptive to data quality.

RANSAC is part of a family of robust estimators and is often used in conjunction with other techniques:

• vs. Least Squares: Least squares minimizes the sum of squared errors for all data, making it fragile to outliers. RANSAC identifies and uses only the inliers for final model fitting, often using least squares on the final consensus set.
• Predecessor - Hough Transform: Both are voting schemes robust to outliers. The Hough Transform uses a dense accumulator in parameter space, while RANSAC uses sparse, random sampling, making it more efficient for high-dimensional parameter spaces (like homographies).
• Successor - M-estimators: M-estimators are iterative reweighted least-squares methods that can be more efficient but require a good initial guess, which RANSAC can provide.

RANSAC is a workhorse algorithm in computer vision pipelines where data is noisy:

• Homography Estimation: For image stitching (panoramas) or planar object detection, finding the transformation between two views of a plane from noisy matched features.
• Fundamental/Essential Matrix Estimation: Computing the epipolar geometry between two uncalibrated/calibrated cameras from putative feature matches, many of which are incorrect.
• 3D Plane Fitting: Extracting dominant planar surfaces (e.g., ground plane, walls) from noisy 3D point clouds obtained from LiDAR or depth sensors.
• Outlier Rejection in SLAM/VO: Filtering erroneous feature tracks or loop-closure candidates in Visual Odometry and SLAM systems before bundle adjustment.

Several algorithms improve upon basic RANSAC's speed, accuracy, or determinism:

• MLESAC (Maximum Likelihood Estimation S.A.C.): Uses a probabilistic model to evaluate the consensus set, not just its size, leading to more accurate parameter estimates.
• PROSAC (Progressive S.A.C.): Samples are not drawn uniformly at random but from a progressively larger pool of high-quality data (e.g., feature matches sorted by descriptor similarity), drastically reducing runtime.
• USAC (Universal S.A.C.): A modern, efficient framework that integrates PROSAC-like sampling, SPRT for early rejection of bad models, and local optimization (like LO-RANSAC) on promising models.
• LO-RANSAC (Locally Optimized R.A.N.S.A.C.): After finding a good model, it performs an iterative local optimization (e.g., non-linear refinement) on its inliers to improve accuracy.

The Fundamental Matrix (F) is a 3x3 matrix of rank 2 that encapsulates the epipolar geometry between two uncalibrated cameras. It satisfies the equation x'ᵀ F x = 0 for any pair of corresponding image points x and x'. RANSAC is critically used to robustly estimate F from a set of putative feature matches, many of which may be incorrect (outliers).

• Role of RANSAC: Given the sensitivity of the 8-point algorithm (a linear method for computing F) to mismatches, RANSAC iteratively selects random subsets of 8 correspondences to hypothesize a matrix, then evaluates its support by counting inliers based on the Sampson distance.

Bundle Adjustment is a non-linear optimization that jointly refines 3D point coordinates, camera poses, and often intrinsic parameters by minimizing the total reprojection error. It is the final, precise step after an initial robust estimation.

• RANSAC's Role: Provides the initial, outlier-free set of correspondences and a rough camera pose estimate required to bootstrap bundle adjustment. Without RANSAC's robust front-end, bundle adjustment would likely converge to an incorrect local minimum due to outlier contamination.
• Workflow: RANSAC (robust initialization) → Triangulation (initial 3D points) → Bundle Adjustment (precise, global refinement).

Iterative Closest Point (ICP) is an algorithm for aligning two 3D point clouds by iteratively estimating a rigid transformation (rotation and translation). It assumes a one-to-one correspondence between points, which is often unknown and estimated in each iteration.

• Robust Variants: Standard ICP is highly sensitive to incorrect correspondences and partial overlaps. Robust ICP variants integrate a RANSAC-like paradigm within the iteration loop.
• How it Works: In each iteration, after finding nearest-neighbor correspondences, a RANSAC step can be used to estimate the transformation from a minimal subset (e.g., 3 points) before applying it to all points, making the alignment process resistant to outliers and noise.

Perspective-n-Point (PnP) is the problem of estimating the 6DoF pose (rotation and translation) of a calibrated camera from a set of n known 3D points and their corresponding 2D image projections.

• Minimal Solutions: Efficient PnP solvers like P3P require only 3 point correspondences to generate up to 4 possible pose hypotheses.
• RANSAC Integration: This minimal property makes PnP an ideal candidate for RANSAC. The standard pipeline for camera pose estimation from 3D-2D matches is:
  1. Use a minimal PnP solver (e.g., P3P, EPnP) inside the RANSAC loop to generate pose hypotheses from random samples of 3 or 4 correspondences.
  2. Evaluate each hypothesis by projecting all 3D points and counting inliers (points with reprojection error below a threshold).
  3. Refine the winning pose with all inliers using a non-linear optimizer.

The Direct Linear Transform (DLT) is a linear, non-iterative algorithm used to estimate transformation matrices (like a homography or camera projection matrix P) from point correspondences by solving a homogeneous linear system.

• Sensitivity to Noise: The standard DLT is a least-squares estimator, meaning it is highly sensitive to outliers. A single incorrect correspondence can severely distort the estimated matrix.
• RANSAC as a Wrapper: RANSAC is routinely used as a robust wrapper around DLT. The iterative process is:
  1. Randomly select a minimal sample (e.g., 4 points for a homography).
  2. Compute the transformation matrix using DLT on this sample.
  3. Test the model against all data points to find inliers. This combination provides a robust estimate that the DLT alone cannot achieve.

Singular Value Decomposition (SVD) is a fundamental matrix factorization technique used extensively within the inner loops of both RANSAC hypotheses generation and model verification.

• In Hypothesis Generation: Many minimal solvers used inside RANSAC rely on SVD.
  • Essential Matrix: The 8-point algorithm uses SVD to solve for the essential matrix E from normalized correspondences.
  • Homography: The DLT solution for a homography involves finding the null space of a matrix, typically done via SVD.
• In Model Verification: To evaluate a hypothesized essential matrix E, it is common to decompose it via SVD (E = U diag(1,1,0) Vᵀ) to extract the four possible relative camera pose configurations, which are then tested for cheirality (positive depth).