In computer vision, "messy" data is the norm. Whether you are estimating the movement of a self-driving car or reconstructing a 3D scene from photos, your input—feature matches between images—is often dominated by "outliers." These are incorrect correspondences caused by repetitive textures, moving objects, or sensor noise.
The standard tool for handling this is RANSAC (Random Sample Consensus). However, as datasets grow and environments become more crowded, the "random" part of RANSAC has become a massive computational bottleneck. Modern research is shifting toward more efficient, often deterministic, strategies to find the "needle" of a geometric model in a "haystack" of outliers.
The Exponential Bottleneck of Randomness
The intuition behind RANSAC is simple: pick a tiny subset of data points, calculate a model (like a camera's rotation), and see how many other points agree with it. If you pick a subset that contains even one outlier, the resulting model will be "garbage."
The probability of picking a "clean" subset of $k$ points depends on the inlier ratio $w$ (the fraction of good data). The number of iterations $N$ required to find a good model with high confidence is:
$$N = \frac{\log(1 - p)}{\log(1 - w^k)}$$
As Torsten Sattler and Leif Kobbelt note in Efficient & effective image-based localization, this relationship is exponential. If 90% of your data is outliers ($w=0.1$) and you need 5 points to solve your model, you might need millions of iterations. This makes real-time performance impossible in high-noise environments.
Shrinking the Sample Size
The most direct way to break this exponential curve is to reduce $k$—the number of points needed to generate a hypothesis. If you only need one point instead of five, your chances of hitting an inlier jump from near-zero to 10%.
Researchers have achieved this by squeezing more information out of every single feature match. Instead of treating a match as a simple $(x, y)$ coordinate, "affine correspondences" include local shape information (like the scale and orientation of a SIFT keypoint). Daniel Barath and Levente Hajder demonstrate in Relative planar motion for vehicle-mounted cameras from a single affine correspondence that by exploiting the fact that cars move on a 2D plane, a vehicle's motion can be estimated from just a single match.
Similarly, Jonathan Ventura and Zuzana Kukelova show that leveraging the scale and orientation data already provided by common detectors can reduce the points needed for absolute pose estimation from three down to one or two Absolute Pose from One or Two Scaled and Oriented Features.
Guided Sampling and Spatial Consistency
If we can't reduce the sample size, we can at least stop sampling "blindly." Standard RANSAC treats every data point as equally likely to be an inlier. Guided sampling methods use heuristics or learned priors to pick better points first.
One powerful heuristic is spatial consistency. Inliers tend to "stick together" geometrically. Torsten Sattler introduced SCRAMSAC SCRAMSAC: Improving RANSAC's efficiency with a spatial consistency filter, which prunes matches whose neighbors don't move in a consistent way before the sampling even begins.
More recently, researchers have turned to deep learning to "learn" what a good match looks like. Kwang Moo Yi and Eduard Trulls developed networks that use context normalization to understand global geometric patterns, filtering out outliers up to 17x faster than traditional methods Learning to Find Good Correspondences. Chang Nie even framed the sampling process itself as a Reinforcement Learning problem in RLSAC RLSAC: Reinforcement Learning enhanced Sample Consensus for End-to-End Robust Estimation, allowing an agent to learn the most efficient sampling strategy for a given scene.
Deterministic Alternatives to the Dice Roll
Some researchers argue that we should move away from sampling entirely. If finding the best model is a search problem, why not use more structured search techniques?
- Voting: Fabien Delattre and colleagues use Hough-like voting mechanisms to find camera rotations in crowded scenes Robust Frame-to-Frame Camera Rotation Estimation in Crowded Scenes. By treating the parameter space as a grid and letting every match "vote" for a rotation, they avoid the need for iterative sampling.
- Graph Theory: Álvaro Parra and Tat-Jun Chin treat the problem as finding the Maximum Clique in a graph of consistent matches A Practical Maximum Clique Algorithm for Matching with Pairwise Constraints. This allows them to find exact solutions even when outliers exceed 95%.
- Deterministic Fitting: Yan Yan and David Suter proposed SDF, which uses superpixels to guide a "fit-and-remove" process Superpixel-based Two-view Deterministic Fitting for Multiple-structure Data, providing consistent results without the randomness of RANSAC.
The Reality Check
Despite these advances, robust fitting remains fundamentally difficult. Tat-Jun Chin and Frank Neumann provided a theoretical "reality check" by proving that consensus maximization is NP-hard Robust Fitting in Computer Vision: Easy or Hard?. This explains why, despite its flaws, RANSAC remains the industry standard: in the worst-case scenario, a "roll of the dice" is often as good as any other strategy. The goal of modern research is to ensure that for real-world scenes, we don't have to rely on luck alone.