RANSAC (Random Sample Consensus)

RANSAC operates by repeatedly selecting a minimal sample set (MSS) of data points—the smallest number required to instantiate the model parameters. For example:

• A line requires 2 points.
• A homography matrix requires 4 point correspondences.
• A fundamental matrix requires 8 point correspondences (7 for the normalized 7-point algorithm). A model is fitted to this small, randomly chosen subset, forming a candidate hypothesis. This random sampling is the first defense against outliers, as the probability of an outlier-free MSS determines the number of iterations needed.

For each generated hypothesis, RANSAC evaluates the entire dataset to find the consensus set (CS) or inliers. A user-defined distance threshold (ε) determines if a data point agrees with the model. Any point whose error (e.g., reprojection error for geometric models) is less than ε is considered an inlier. The hypothesis that yields the largest consensus set is considered the best current model. This step distinguishes RANSAC from least-squares fitting, which is highly sensitive to outliers because it tries to fit all data points.

RANSAC is non-deterministic but provides a probabilistic guarantee of success. The number of iterations (N) is not fixed but calculated to ensure, with a certain probability (p, typically 0.99), that at least one outlier-free minimal sample is selected. The formula is: N = log(1 - p) / log(1 - w^k) where:

• w is the estimated inlier ratio (inliers / total points).
• k is the size of the minimal sample set. This adaptive iteration count allows RANSAC to run efficiently on relatively clean data while spending more time on highly contaminated datasets.

Once the iteration loop terminates, RANSAC performs a final refinement step. The parameters of the best model are re-estimated using all inliers in the largest consensus set, typically via a least-squares optimization. This refines the model's accuracy using all available, verified good data. For instance, in bundle adjustment pipelines, RANSAC is often used for initial camera pose estimation and fundamental matrix calculation to filter outlier feature matches before a final, global non-linear optimization over all inliers.

In Structure from Motion (SfM) and Visual SLAM, RANSAC is fundamental for robust geometry estimation in the presence of incorrect feature matches. Key applications include:

• Estimating the Essential Matrix from putative point correspondences between two views to recover relative camera pose.
• Computing a homography for planar scene segments.
• PnP (Perspective-n-Point) solvers for camera localization given 3D-2D correspondences. Without RANSAC, these pipelines would fail due to even a small percentage of mismatched SIFT or ORB features.

Classic RANSAC has inspired numerous variants that address its limitations:

• MSAC (M-estimator SAmple Consensus): Uses a robust cost function instead of a binary inlier/outlier threshold, providing a smoother objective.
• PROSAC (PROgressive SAmple Consensus): Samples are not drawn uniformly but from a progressively larger pool of high-quality data (e.g., feature matches ordered by descriptor similarity), drastically reducing iterations.
• LO-RANSAC (Locally Optimized RANSAC): Adds a local optimization step where a non-linear refinement is applied to promising models during the iteration loop, not just at the end.
• USAC (Universal RANSAC): A modern framework integrating multiple strategies like PROSAC sampling, SPRT testing for early rejection of bad models, and LO optimization.

Structure from Motion is a foundational photogrammetry technique that simultaneously estimates the 3D structure of a scene and the camera poses from a set of unordered 2D images. It is the overarching pipeline within which RANSAC often operates.

• Core Process: It solves the 'chicken-and-egg' problem of not knowing the 3D points or camera positions by alternating between estimating one while holding the other fixed.
• RANSAC's Role: RANSAC is used within SfM pipelines to robustly estimate the fundamental matrix or essential matrix from noisy feature matches, which is critical for initializing camera poses before global bundle adjustment.

Bundle adjustment is a non-linear optimization process that refines the 3D coordinates of scene points, camera poses, and intrinsic parameters to minimize the total reprojection error across all images. It is the final, precise refinement step after RANSAC provides an initial, robust estimate.

• Relationship to RANSAC: RANSAC provides an initial model (e.g., camera pose) that is free from outlier corruption. Bundle adjustment then takes this clean initialization and performs a maximum-likelihood estimation over all inliers to achieve optimal accuracy.
• Key Difference: While RANSAC is robust to outliers but approximate, bundle adjustment is sensitive to outliers but highly accurate when given good inliers. They are used sequentially for optimal results.

Feature matching is the process of establishing correspondences between distinctive local keypoints (like SIFT, ORB, or SuperPoint features) detected in two or more images. It provides the raw, noisy data that RANSAC is designed to filter.

• The Data Problem: Matches from algorithms like FLANN or brute-force descriptor matching are inherently noisy, containing a high percentage of incorrect outlier correspondences.
• RANSAC's Purpose: RANSAC's primary application in 3D vision is to take this set of putative feature matches and robustly estimate a geometric model (e.g., a homography or fundamental matrix), thereby identifying the inlier matches that are geometrically consistent and discarding the outliers.

Reprojection error is the geometric distance, measured in pixels, between a projected 3D point and its corresponding measured 2D image feature. It is the fundamental cost function optimized in both RANSAC and bundle adjustment.

• In RANSAC: For a hypothesized model (like a camera pose), the reprojection error is calculated for each data point (feature match). Points with an error below a threshold (e.g., 2-5 pixels) are counted as inliers for that model.
• Quantitative Measure: It provides a pixel-level metric for model fitness. A successful RANSAC iteration finds a model that minimizes the reprojection error for the largest consensus set of data points.

Visual SLAM (Simultaneous Localization and Mapping) is the real-time process where an agent (like a robot or AR device) builds a map of an unknown environment while simultaneously tracking its own location within it. RANSAC is a critical component for robustness.

• Robust Tracking: In visual odometry, the front-end of a SLAM system uses feature matching between consecutive frames. RANSAC is employed to estimate the camera's egomotion (pose) from these matches while rejecting outliers caused by moving objects or incorrect matches.
• Loop Closure: When the agent revisits a location, RANSAC can help verify potential loop closures by robustly estimating the geometric transformation between the current view and the mapped location.

Multi-View Stereo is the process of generating dense 3D geometry (a point cloud or mesh) from multiple calibrated images of a static scene. It relies on accurate camera poses, which are often estimated using SfM pipelines that utilize RANSAC.

• Prerequisite Calibration: MVS requires highly accurate camera poses and intrinsics as input. Errors in these parameters, often estimated via RANSAC-driven SfM, propagate directly into the quality of the dense reconstruction.
• Dense Correspondence: While RANSAC works on sparse feature matches, MVS algorithms perform dense matching for every pixel, but the underlying geometric principles of epipolar constraints, initially validated by RANSAC, still apply.