Minimal Solvers for Efficient Robust Geometric Estimation

This direction is split into other directions: minimal solver for uncalibrated cameras, RANSAC iteration reduction. Its last version stays readable and citable here.

Version 1 of 1129 papers190 conceptsfrozen 2026-10-04

In computer vision, determining how a camera has moved or where it is located requires solving systems of geometric equations. Traditionally, these equations are solved using a set of feature matches between images. However, real-world data is messy; most matches are "outliers" (incorrect correspondences). To handle this, researchers use RANSAC (Random Sample Consensus), an iterative process that picks a small random subset of matches, computes a potential solution, and checks how many other matches agree with it.

The computational cost of RANSAC is the primary bottleneck in real-time 3D reconstruction and navigation. This cost is not linear—it grows exponentially with the number of points required to form a hypothesis. The research direction represented here focuses on creating minimal solvers: algorithms that use the absolute minimum amount of data to solve for camera geometry, thereby slashing the number of RANSAC iterations required from hundreds of thousands to just a handful.

The Combinatorial Explosion of RANSAC

The intuition behind minimal solvers is simple: the fewer points you need to pick to guess a solution, the more likely you are to pick a set that contains no outliers.

If 50% of your matches are wrong and you need to pick 7 points to solve for a Fundamental Matrix, the probability of all 7 being correct is $(0.5)^7 \approx 0.0078$. You would need hundreds of iterations to be confident. However, if you can solve the same problem with only 3 points, the probability jumps to $(0.5)^3 = 0.125$.

As Paul A. Beardsley and Andrew Zisserman noted in their early work on 3D Model Acquisition, reducing the required points by even one can exponentially decrease the iterations needed for robust estimation. This efficiency gain is the "holy grail" for real-time systems like self-driving cars and drones.

Reducing Degrees of Freedom with Priors

To reduce the number of points needed, researchers "cheat" by using extra information from the environment or other sensors to fix certain variables.

  • Gravity Priors: Modern smartphones and drones have IMUs that tell us which way is "down." By leveraging this gravity vector, researchers like Yaqing Ding and Zuzana Kukelova have developed solvers for panoramic stitching and relative pose that require as few as 3 or 4 points, compared to the standard 5 or 8.
  • Motion Constraints: Cars usually move on flat ground. Gim Hee Lee and Marc Pollefeys demonstrated that by assuming planar motion (the Ackermann steering model), the number of points needed for egomotion drops to just two.
  • Relative Depth: Recent work by Yaqing Ding shows that even relative depth ratios (from monocular depth models) can be used as a constraint to simplify the fundamental matrix estimation.

Beyond Points: Affine Correspondences

A standard point match $(x, y) \leftrightarrow (x', y')$ provides two constraints. However, an Affine Correspondence (AC) includes the local warping (rotation, scale, and shear) of the image patch around that point.

Researchers like Daniel Barath and Ivan Eichhardt have shown that one AC provides significantly more geometric information than a single point. In Affine Correspondences Between Central Cameras, Eichhardt demonstrates that the relative pose of two cameras can be solved with just two ACs.

The ultimate expression of this is the 1-point solver. By combining an affine correspondence with a known vertical direction or planar motion, researchers have created solvers that require only a single match. When you only need one match, RANSAC becomes so efficient it can sometimes be replaced by deterministic methods like histogram voting, making the system incredibly robust even when 90% of matches are wrong.

Solving for the "Messy" Reality of Sensors

Minimal solvers are also being extended to handle the specific hardware quirks of consumer devices:

  1. Rolling Shutter Distortion: Most smartphones don't capture the whole image at once; they scan it row by row. If the camera moves during this scan, the image warps. Tomáš Pajdla and colleagues have identified 31 distinct minimal problems for rolling shutter cameras, allowing for accurate 3D reconstruction despite this motion blur.
  2. Unknown Calibration: Often, we don't know the camera's focal length. Solvers like P3.5P by Changchang Wu and work by Snehal Bhayani on hybrid correspondences allow systems to estimate both the camera's pose and its internal settings simultaneously from a minimal set of points.

By reducing the data requirements of geometric solvers, this field transforms 3D vision from a heavy, offline process into a lightweight, real-time capability suitable for everything from smartphone AR to high-speed drone navigation.

Papers in this version

Showing 60 of 129 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_minimal_solvers_for_efficient_robust_geo_6ca3a971,
  title = {Minimal Solvers for Efficient Robust Geometric Estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimal-solvers-for-efficient-robust-geometric-estimation/rdr_6ca3a97106d9404cb6267347506f5bec},
  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_minimal_solvers_for_efficient_robust_geo_6ca3a971_v1,
  title = {Minimal Solvers for Efficient Robust Geometric Estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimal-solvers-for-efficient-robust-geometric-estimation/rdr_6ca3a97106d9404cb6267347506f5bec/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}