Efficient Robust Fitting for Geometric Vision

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2137 papers140 conceptsfrozen 2026-10-04

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?

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.

Papers in this version

Showing 60 of 137 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 123 papers
  2. Version 1 · 2026-10-04 · 137 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_combinatorial_explosion_in_robust_estima_90f7c191,
  title = {combinatorial explosion in robust estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-explosion-in-robust-estimation/rdr_90f7c19176514af9bc146d44757cf7ab},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_efficient_robust_fitting_for_geometric_v_90f7c191_v1,
  title = {Efficient Robust Fitting for Geometric Vision},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/efficient-robust-fitting-for-geometric-vision/rdr_90f7c19176514af9bc146d44757cf7ab/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}