# Optimizing Elimination Templates by Greedy Parameter Search

arXiv: https://arxiv.org/abs/2203.14901 · HTML: https://mlsanity.com/paper/2203.14901/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 60 references that are in the map.
- First posted on arXiv 28 Mar 2022.

## Builds on (most cited first, 9 of 9)

- [Beyond Gr"obner Bases: Basis Selection for Minimal Solvers](https://mlsanity.com/paper/1803.04360/) (2018)
- [A clever elimination strategy for efficient minimal solvers](https://mlsanity.com/paper/1703.05289/) (2017)
- [Galois/monodromy groups for decomposing minimal problems in 3D reconstruction](https://mlsanity.com/paper/2105.04460/) (2021)
- [A sparse resultant based method for efficient minimal solvers](https://mlsanity.com/paper/1912.10268/) (2019)
- [On the Two-View Geometry of Unsynchronized Cameras](https://mlsanity.com/paper/1704.06843/) (2017)
- [Distortion Varieties](https://mlsanity.com/paper/1610.01860/) (2016)
- [On the Existence of Epipolar Matrices](https://mlsanity.com/paper/1510.01401/) (2015)
- [Efficient Relative Pose Estimation for Cameras and Generalized Cameras in Case of Known Relative Rotation Angle](https://mlsanity.com/paper/1901.11357/) (2019)
- [Self-Calibration of Cameras with Euclidean Image Plane in Case of Two Views and Known Relative Rotation Angle](https://mlsanity.com/paper/1807.11279/) (2018)

## Built on by (most cited first, 8 of 8)

- [Snapshot of Algebraic Vision](https://mlsanity.com/paper/2210.11443/) (2022)
- [Six-Point Method for Multi-Camera Systems with Reduced Solution Space](https://mlsanity.com/paper/2402.18066/) (2024)
- [Order-One Rolling Shutter Cameras](https://mlsanity.com/paper/2403.11295/) (2024)
- [Sparse resultant based minimal solvers in computer vision and their connection with the action matrix](https://mlsanity.com/paper/2301.06443/) (2023)
- [Automatic Solver Generator for Systems of Laurent Polynomial Equations](https://mlsanity.com/paper/2307.00320/) (2023)
- [MinBackProp -- Backpropagating through Minimal Solvers](https://mlsanity.com/paper/2404.17993/) (2024)
- [Simulator HC: Regression-based Online Simulation of Starting Problem-Solution Pairs for Homotopy Continuation in Geometric Vision](https://mlsanity.com/paper/2411.03745/) (2024)
- [Elimination Templates in Macaulay2](https://mlsanity.com/paper/2605.00278/) (2026)

## Abstract (arXiv)

We propose a new method for constructing elimination templates for efficient polynomial system solving of minimal problems in structure from motion, image matching, and camera tracking. We first construct a particular affine parameterization of the elimination templates for systems with a finite number of distinct solutions. Then, we use a heuristic greedy optimization strategy over the space of parameters to get a template with a small size. We test our method on 34 minimal problems in computer vision. For all of them, we found the templates either of the same or smaller size compared to the state-of-the-art. For some difficult examples, our templates are, e.g., 2.1, 2.5, 3.8, 6.6 times smaller. For the problem of refractive absolute pose estimation with unknown focal length, we have found a template that is 20 times smaller. Our experiments on synthetic data also show that the new solvers are fast and numerically accurate. We also present a fast and numerically accurate solver for the problem of relative pose estimation with unknown common focal length and radial distortion.