In computer vision, reconstructing a 3D scene from 2D images relies heavily on solving "minimal problems"—estimating camera positions, orientations, focal lengths, or lens distortions from the absolute minimum number of geometric features. Mathematically, these constraints are formulated as systems of multivariate polynomial equations. In an ideal world with exact arithmetic and perfect data, algebraic geometry tools like Gröbner bases or resultants offer elegant, closed-form solutions.
However, real-world vision pipelines operate on floating-point arithmetic and noisy pixel measurements. As Olivier D. Faugeras et al. noted in their foundational work on multi-view geometry, a wide gap exists between symbolic theory and practical application. Purely algebraic formulations frequently break down when confronted with measurement noise. Understanding why these polynomial solvers fail under empirical conditions—and how to stabilize them—is a core focus of modern geometric computing.
The Anatomy of Algebraic Instability
To understand why minimal solvers are so fragile, we must look at how they translate polynomial equations into linear algebra. The standard pipeline relies on constructing an elimination template: a large matrix where rows represent the original polynomial equations multiplied by various monomials. By performing elimination steps (like Gauss-Jordan elimination or QR decomposition) on this matrix, the solver isolates variables and reduces the system to a univariate polynomial or an eigenvalue problem.
This translation introduces two primary failure modes:
1. Template Inflation and Rounding Errors
When a problem requires solving for multiple camera parameters simultaneously—such as joint pose, focal length, and radial distortion—the degree of the polynomial system skyrockets. As Zuzana Kukelova et al. demonstrate, this complexity forces the elimination templates to become massive and ill-conditioned.
Janne Heikkilä explains that these oversized matrices act as amplifiers for floating-point rounding errors. During elimination, thousands of sequential floating-point operations accumulate tiny precision losses. If the input data contains even sub-pixel noise, the matrix coefficients shift slightly, causing the elimination process to diverge catastrophically from the true geometric solution.
2. The Root-Finding Trap
Once the template is reduced, the final step typically involves extracting roots via a generalized eigenvalue problem or an action matrix. Snehal Bhayani et al. observe that this step is highly prone to producing spurious or numerically unstable solutions when the input coefficients are perturbed.
Furthermore, Mikael Persson et al. show that when the roots of these high-degree polynomials are located close to one another—a frequent occurrence in practical camera configurations—solvers experience a severe loss of precision. Under noise, real-valued physical solutions can easily drift into the complex plane, leaving the system with no valid geometric answer (Ady Ecker et al.).
The Hidden Role of Data Conditioning
We often view robust estimation frameworks like RANSAC purely as tools for filtering out incorrect feature matches (outliers). However, Hongyi Fan et al. revealed a deeper mathematical reality: standard minimal solvers (such as the 5-point and 7-point relative pose algorithms) can fail even when provided with perfect, outlier-free data if the spatial configuration of the points is poorly conditioned.
[Noisy Image Features] ──> [Oversized Elimination Template] ──> [Accumulated Rounding Errors] ──> [Unstable Eigenvalues / Complex Roots]
RANSAC succeeds in production environments not just because it removes outliers, but because it acts as an implicit numerical filter. It repeatedly samples subsets of data until it accidentally selects a point configuration that is numerically well-conditioned, shielding the fragile polynomial solver from catastrophic precision loss.
Strategies for Building Robust Solvers
To bypass these limitations, researchers have developed several paradigms to bridge the gap between abstract algebra and stable numerical computing (kim batselier et al.; Philippe Dreesen et al.).
Shrinking the Elimination Templates
The most direct way to reduce rounding error accumulation is to minimize the size of the elimination template. Janne Heikkilä introduced sparse elimination strategies that exploit the sparsity structure of the polynomial equations to construct significantly smaller matrices. Building on this, Snehal Bhayani et al. utilized sparse resultant theory to automatically generate solvers that bypass the bloated templates typical of traditional Gröbner basis methods, yielding faster and more stable execution.
Geometric Decomposition and Approximations
Instead of forcing a single, massive polynomial solver to handle every camera parameter at once, problems can be broken down geometrically. Martin Bujnak et al. demonstrated that splitting absolute pose estimation into separate planar and non-planar scenes yields simplified, highly stable minimal solvers.
Taking this philosophy further, Viktor Kocur bypassed complex algebraic solvers entirely for the notoriously difficult 3-view relative pose problem. By substituting the high-degree polynomial formulation with an approximate geometric strategy built from simpler, inherently stable 2-view solvers, the author achieved state-of-the-art robustness without the numerical baggage of elimination templates.
Numerical Homotopy Continuation
When symbolic elimination methods remain too sensitive to coefficient perturbations (Jean B. Lasserre et al.), numerical path-tracking offers an alternative. Chiang-Heng Chien et al. developed a massively parallelized GPU implementation of Homotopy Continuation (HC).
Instead of constructing a static algebraic template, HC starts with a known solution to a simplified base system and continuously deforms the equations until they match the target problem, tracking the numerical paths in parallel. This completely avoids the floating-point pitfalls of symbolic elimination templates, enabling robust, real-time solutions for highly complex geometric problems.
Key Foundational Work
An analytic solution for the perspective 4-point problem (1989) — contributed 1 concept elements to this direction.
On the Geometry and Algebra of the Point and Line Correspondences Between N Images (1995) — contributed 1 concept elements to this direction.