High Speed Minimal Solvers for Robust Computer Vision

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

Version 1 of 266 papers69 conceptsfrozen 2026-10-04

In computer vision, estimating the geometry of a scene—where a camera is, how a lens is distorted, or how two 3D scans align—is rarely a direct calculation. Because real-world data is "noisy" and full of incorrect matches (outliers), we rely on robust estimation frameworks like RANSAC.

RANSAC works by playing a numbers game: it repeatedly picks a "minimal set" of data points (the smallest number needed to define a model), solves for the parameters, and checks how many other points agree. To find the correct model in a sea of outliers, RANSAC might need to test thousands or even millions of hypotheses. Consequently, the entire system's speed is dictated by the efficiency of the minimal solver—the mathematical engine that calculates a model from those few points.

The Algebraic Bottleneck

Most geometric problems, such as estimating a camera's absolute pose from 3D-to-2D points (the P3P problem), boil down to solving systems of non-linear polynomial equations. Traditionally, these are solved using complex algebraic methods like Gröbner bases. While mathematically rigorous, these solvers often require large "elimination templates"—dense matrices that are computationally expensive to process in real-time.

Researchers like Zuzana Kukelova and Tomáš Pajdla have pioneered ways to make these solvers faster. In A Clever Elimination Strategy for Efficient Minimal Solvers, they demonstrated that much of the heavy algebraic lifting can be moved to an "offline" pre-processing step. By optimizing the elimination templates ahead of time, the "online" solver used during RANSAC becomes significantly leaner.

Building on this, Viktor Larsson introduced GAPS, a tool that automatically generates highly optimized C++ solvers. These tools allow developers to bridge the gap between theoretical geometry and the microsecond-level latency required for robotics.

Simplifying Geometry with Prior Knowledge

One of the most effective ways to speed up a solver is to reduce the number of variables it has to find. If we know the camera's vertical orientation (from an IMU) or the scale of the features, the math becomes much simpler.

For example, Marcus Valtonen Örnhag and Mårten Wadenbäck showed in Efficient Real-Time Radial Distortion Correction for UAVs that by aligning a camera with the direction of gravity, they could estimate focal length and radial distortion in under 150 microseconds—fast enough to run on low-power hardware like a Raspberry Pi.

Similarly, Jonathan Ventura and colleagues demonstrated in Absolute Pose from One or Two Scaled and Oriented Features that leveraging the scale and orientation data already provided by feature detectors (like SIFT) allows for pose estimation with just one or two points. Reducing the "minimal set" size from three points to one exponentially reduces the number of RANSAC iterations needed, leading to massive speedups in high-outlier environments.

Iteration and Approximation over Exactness

Sometimes, the "perfect" algebraic solution is the enemy of the "fast" practical solution. In Improved RANSAC performance using simple, iterative minimal-set solvers, Edward Rosten and his team argued that simple iterative optimization (like Gauss-Newton) often outperforms complex polynomial solvers. By prioritizing numerical stability and speed over finding every possible mathematical root, they achieved more reliable results in real-world vision tasks.

This philosophy of "approximate geometry" is also seen in the work of Charalambos Tzamos and Yaqing Ding. In Practical Solutions to the Relative Pose of Three Calibrated Cameras, they replaced unstable algebraic solvers with a strategy that combines simpler 2-view solvers, making the system faster and easier to implement without losing accuracy.

The most recent frontier involves using machine learning to bypass the search process entirely or to guide it more intelligently.

In Learning to Solve Hard Minimal Problems, Petr Hruby and Timothy Duff introduced a "pick & solve" strategy. Instead of finding all possible solutions to a geometric problem (many of which are physically impossible), they trained a neural network to predict a single promising starting point. This point is then refined using numerical homotopy, achieving speedups of up to 1000x for complex 3D reconstruction.

Other frameworks like 3DRegNet and SRPose attempt to replace the RANSAC loop entirely with deep neural networks that regress poses directly. While these methods offer blistering speed, the field continues to find that the most robust systems often combine the strengths of both: using deep learning to filter data and high-speed minimal solvers to provide the final geometric certificate.

Papers in this version

Showing 60 of 66 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_minimal_solver_efficiency_de8317ed,
  title = {minimal solver efficiency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/minimal-solver-efficiency/rdr_de8317edd5694e9d8a2b112615e879f5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_high_speed_minimal_solvers_for_robust_co_de8317ed_v1,
  title = {High Speed Minimal Solvers for Robust Computer Vision},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/high-speed-minimal-solvers-for-robust-computer-vision/rdr_de8317edd5694e9d8a2b112615e879f5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}