We present a learning-based approach to solving hard minimal problems in geometric computer vision. Minimal problems arise as the core algorithmic engines in RANSAC-based robust estimation pipelines, where a polynomial system must be solved for each hypothesized minimal sample. Existing solvers either enumerate all solutions (including many spurious complex ones) or rely on problem-specific algebraic tricks. We propose an alternative: combine homotopy continuation with a learned classifier that selects a promising start problem-solution pair (anchor) from a precomputed set, then track a single real solution path to the target problem. Our approach achieves solving times under 70 microseconds for the challenging three-camera four-point (Scranton) problem, demonstrating speedups exceeding 10x compared to prior approximation methods.

Minimal problems are fundamental building blocks of modern 3D reconstruction and visual localization pipelines. In the RANSAC framework, a minimal sample of correspondences is drawn, a polynomial system encoding geometric constraints is solved, and the resulting hypothesis is scored against all data. This inner loop is executed thousands to millions of times, making the speed of the minimal solver a critical bottleneck. For well-studied problems such as the five-point relative pose problem, highly optimized solvers exist. However, many important problems — particularly those involving radial distortion, multi-camera systems, or partially calibrated setups — yield polynomial systems that are orders of magnitude harder, with hundreds of solutions.

The standard approach to solving minimal problems is the action matrix method from computational algebraic geometry. Given a polynomial system, one constructs an elimination template that reduces the problem to computing eigenvalues of a matrix. While effective, these templates grow rapidly: for the Scranton problem (four points in three calibrated cameras), the system has 272 solutions, leading to extremely large elimination templates and slow solvers. An alternative is homotopy continuation (HC), which numerically tracks solution paths from a known start system to the target system. Classical HC tracks all solution paths (both real and complex), which is wasteful when only real solutions are needed.

We propose a "Pick & Solve" paradigm that reverses the traditional "Solve & Pick" approach. Instead of computing all solutions and then selecting the geometrically valid one, we first use a learned MLP classifier to predict which precomputed anchor (start problem-solution pair) is most likely to lead to the correct solution, and then track only that single real homotopy path. The anchors are constructed offline via a greedy dominating set algorithm on a graph of problem-solution pairs. At runtime, the classifier requires only approximately 8 microseconds, and the subsequent homotopy tracking adds a few additional microseconds, yielding total solving times that are orders of magnitude faster than existing approaches for hard problems.

Minimal solvers have been a central topic in geometric computer vision for decades. The five-point algorithm by Nister provides an efficient solution to the relative pose problem using action matrix techniques. Subsequent work by Kukelova, Bujnak, and Pajdla introduced automatic generator frameworks that systematically produce Groebner basis solvers for a wide range of minimal problems. These methods work well when the number of solutions is moderate (up to a few tens), but become impractical as the solution count grows into the hundreds, due to the cubic scaling of the eigenvalue computation in the template size.

Homotopy continuation is a numerical method for solving polynomial systems by deforming a start system with known solutions into the target system. Classical approaches, implemented in software such as Bertini, PHCpack, and HomotopyContinuation.jl, typically use total-degree start systems and track all paths in complex arithmetic. Recent work by Duff, Leykin, and others has explored monodromy-based methods for constructing more efficient start systems. The key observation motivating our work is that for real-world RANSAC applications, only real solutions matter — yet classical HC wastes enormous computation tracking complex paths that will never yield real solutions.

The intersection of machine learning and geometric vision has grown rapidly, with learned feature matching, learned pose estimation, and learned outlier rejection achieving strong results. However, most learning-based approaches replace the geometric solver entirely with a neural network, sacrificing the mathematical guarantees of algebraic methods. Our approach is fundamentally different: we use learning only to guide the selection of starting points, while the actual geometric computation is performed by rigorous numerical continuation. This preserves the accuracy of classical methods while dramatically reducing computation through intelligent initialization.

A minimal problem can be formalized as a parametric polynomial system F(p, s) = 0, where p denotes the problem parameters (derived from input data such as image correspondences) and s denotes the solution variables (e.g., camera parameters or depths). The set of all valid problem-solution pairs (p, s) forms a smooth manifold M, and the projection from M to the parameter space P is generically a finite covering map. For instance, the five-point relative pose problem involves 10 polynomial equations in 9 unknowns (after fixing one depth to normalize scale), and the generic number of complex solutions is 80 (or 160 for the relaxed formulation used here).

We adopt a depth-based formulation of minimal problems. For N points observed in K cameras, the unknowns are the depths at which each ray intersects the corresponding 3D point. The polynomial equations arise from distance preservation constraints: the Euclidean distance between any two reconstructed 3D points must be consistent across all camera views. Specifically, for cameras k, m and points i, j, we require that the squared distance between point i and point j reconstructed from view k equals the corresponding squared distance from view m. This yields a sparse polynomial system with degree-two equations, which is particularly amenable to efficient Jacobian computation in the continuation step.

Homotopy continuation solves the target problem by continuously deforming a known start problem into the target. Given a start pair (p₀, s₀) where F(p₀, s₀) = 0 is satisfied, we define a linear homotopy path p(t) = (1-t)p₀ + tp for t in [0, 1], where p is the target problem. The solution s(t) evolves continuously along this path on the problem-solution manifold M. We track this path using a predictor-corrector scheme: a fourth-order Runge-Kutta predictor advances along the tangent direction, followed by up to three Newton refinement steps to snap back to the manifold. The step size is adaptively controlled based on the success of the Newton corrections.

Two crucial implementation choices yield dramatic speedups. First, since we only need real solutions for RANSAC, we perform all arithmetic in real numbers rather than complex numbers. This eliminates the overhead of complex multiplication and provides an approximately 14x speedup over complex-arithmetic HC. Second, the depth-based sparse formulation produces Jacobian matrices with known sparsity patterns, enabling closed-form solutions in the linear algebra subroutines (rather than generic dense solvers). This sparsity exploitation yields an additional approximately 5x speedup. Combined, these two optimizations achieve roughly 70x acceleration compared to naive complex-arithmetic dense HC, making real-time operation feasible.

The core of our learning approach is the construction and selection of anchors — precomputed problem-solution pairs that serve as starting points for homotopy continuation. We build a graph G where vertices represent problem-solution pairs from a training set and edges connect pairs that can be reached from each other via HC tracking. We then apply a greedy dominating set algorithm to select a small subset of vertices (anchors) such that most vertices in the graph are adjacent to at least one anchor. For the five-point problem with 10,000 training pairs, approximately 70 anchors suffice to cover 90% of problems. For the Scranton problem, 134 anchors achieve similar coverage.

At runtime, we need to quickly decide which anchor to use for a given target problem. We train a multi-layer perceptron (MLP) classifier with 6 hidden layers of 100 neurons each to map from normalized problem parameters to anchor scores. The classifier outputs a probability distribution over the set of anchors plus a special "TRASH" class indicating that the problem is unreachable from any anchor. Training uses approximately one million problem-solution pairs generated synthetically, with labels assigned by attempting HC from every anchor to each training problem. The MLP is trained with cross-entropy loss and SGD optimization for 80 epochs, selecting parameters that maximize validation success rate. Classification requires only approximately 8 microseconds.

The success of the learned classifier depends critically on input normalization. Raw problem parameters (image correspondences) exhibit high variability due to camera rotation, scene scale, and point ordering ambiguities. We apply a sequence of canonical transformations: rotating coordinate frames based on mean ray directions and extreme ray angles, swapping cameras to enforce a canonical ordering, and reordering point correspondences counterclockwise. These normalizations dramatically reduce the input variability that the classifier must handle, effectively exploiting the symmetry group of each problem to create a more compact representation. Without normalization, the classifier's success rate drops significantly.

We evaluate on two challenging minimal problems. For the five-point relative pose problem, our method achieves a success rate of 29.0% on individual test instances with an average solving time of 7.6 microseconds per instance. The effective time per successful solve is 26.1 microseconds when accounting for failed attempts. On the CVPR 2020 RANSAC benchmark, the success rate is approximately 25%, requiring roughly 4x more RANSAC iterations than the classical Nister solver. However, each iteration is dramatically faster, yielding competitive or superior total pipeline time for scenarios with high inlier ratios. The anchor coverage saturates at approximately 10,000 training pairs, with 28 anchors achieving 75% coverage at the 75% threshold.

For the significantly harder Scranton (four-point three-view) problem, which has 272 solutions in its relaxed formulation, our method achieves a success rate of 26.3% on isolated instances with a solving time of 16.3 microseconds. In the RANSAC context, an average of 4 samples are needed per successful solve, yielding a total effective time of 61.6 microseconds. This represents a speedup exceeding 10x compared to the prior best approximation method, which operates in the millisecond range. The 134 anchors required for the Scranton problem — compared to 70 for the five-point problem — reflect the greater topological complexity of the solution manifold. Notably, the method generalizes across different 3D scene reconstructions and handles noisy data and outliers typical in real-world vision applications.

Ablation studies reveal the contribution of each component. The input normalization is critical: without the canonical transformations that exploit problem symmetries, the classifier accuracy drops by over 15 percentage points. The sparse Jacobian exploitation provides roughly a 5x speedup in the continuation step, while real (vs. complex) arithmetic contributes approximately 14x. The number of anchors exhibits a saturation effect: increasing beyond the selected set yields diminishing returns in coverage. We also analyze failure modes: the most common cause of failure is path crossing — where the tracked path diverges to infinity or jumps to a different solution branch. These failures are inherent to the single-path tracking approach and cannot be eliminated entirely, but are effectively mitigated by the RANSAC framework's tolerance for solver failures.

We have presented a learning-based framework for solving hard minimal problems that combines homotopy continuation with a learned anchor selection classifier. The "Pick & Solve" paradigm fundamentally changes how minimal solvers operate: rather than exhaustively computing all solutions, we predict a single promising start point and track one real solution path. Our experiments on the five-point and Scranton problems demonstrate that this approach yields solving times in the microsecond range, representing order-of-magnitude speedups for problems previously considered intractable for real-time RANSAC. The framework is general and can be applied to any minimal problem expressible as a parametric polynomial system, opening the door to practical deployment of many hard solvers identified in recent multiview geometry classification studies.

Looking forward, several exciting directions emerge. The anchor construction could be improved using more sophisticated graph algorithms or by learning the anchors themselves end-to-end. The classifier architecture could incorporate geometric inductive biases, such as equivariance to the problem's symmetry group, potentially improving generalization. The current approach does not guarantee finding a solution, and developing methods to certify solvability or provide fallback strategies would enhance reliability. Finally, extending the framework to overconstrained systems and non-minimal solvers could broaden its impact beyond the RANSAC setting.