RECORD
GPU-Based Homotopy Continuation for Minimal Problems in Computer Vision
Computer Vision and Pattern Recognition · Submitted 7 Dec 2021
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim GPU-HC opens the door to easy formulation and solution of a range of computer vision problems.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Systems of polynomial equations arise frequently in computer vision, especially in multiview geometry problems. Traditional methods for solving these systems typically aim to eliminate variables to reach a univariate polynomial, e.g., a tenth-order polynomial for 5-point pose estimation, using clever manipulations, or more generally using Grobner basis, resultants, and elimination templates, leading to successful algorithms for multiview geometry and other problems. However, these methods do not work when the problem is complex and when they do, they face efficiency and stability issues. Homotopy Continuation (HC) can solve more complex problems without the stability issues, and with guarantees of a global solution, but they are known to be slow. In this paper we show that HC can be parallelized on a GPU, showing significant speedups up to 26 times on polynomial benchmarks. We also show that GPU-HC can be generically applied to a range of computer vision problems, including 4-view triangulation and trifocal pose estimation with unknown focal length, which cannot be solved with elimination template but they can be efficiently solved with HC. GPU-HC opens the door to easy formulation and solution of a range of computer vision problems.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Systems of polynomial equations arise frequently in computer vision, especially in multiview geometry problems. | background 1.00 | 0.04 | 0.01 | asserted 0.98 |
| s1 | Traditional methods for solving these systems typically aim to eliminate variables to reach a univariate polynomial, e.g., a tenth-order polynomial for 5-point pose estimation, using clever manipulations, or more generally using Grobner basis, resultants, and elimination templates, leading to successful algorithms for multiview geometry and other problems. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s2 | However, these methods do not work when the problem is complex and when they do, they face efficiency and stability issues. | gap 0.74 | 0.07 | 0.02 | asserted 1.00 |
| s3 | Homotopy Continuation (HC) can solve more complex problems without the stability issues, and with guarantees of a global solution, but they are known to be slow. | background 0.90 | 0.05 | 0.05 | asserted 0.99 |
| s4 | In this paper we show that HC can be parallelized on a GPU, showing significant speedups up to 26 times on polynomial benchmarks. | result 0.53 | 0.96 | 0.62 | asserted 1.00 |
| s5 | We also show that GPU-HC can be generically applied to a range of computer vision problems, including 4-view triangulation and trifocal pose estimation with unknown focal length, which cannot be solved with elimination template but they can be efficiently solved with HC. | result 0.66 | 0.95 | 0.21 | asserted 1.00 |
| s6 | GPU-HC opens the door to easy formulation and solution of a range of computer vision problems. | interpretation 1.00 | 0.40 | 0.42 | asserted 0.75 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Systems of polynomial equations arise frequently in computer vision, especially in multiview geometry problems. Traditional methods for solving these systems typically aim to eliminate variables to reach a univariate polynomial, e.g., a tenth-order polynomial for 5-point pose estimation, using clever manipulations, or more generally using Grobner basis, resultants, and elimination templates, leading to successful algorithms for multiview geometry and other problems. However, these methods do not work when the problem is complex and when they do, they face efficiency and stability issues. Homotopy Continuation (HC) can solve more complex problems without the stability issues, and with guarantees of a global solution, but they are known to be slow. In this paper we show that HC can be parallelized on a GPU, showing significant speedups up to 26 times on polynomial benchmarks. We also show that GPU-HC can be generically applied to a range of computer vision problems, including 4-view triangulation and trifocal pose estimation with unknown focal length, which cannot be solved with elimination template but they can be efficiently solved with HC. GPU-HC opens the door to easy formulation and solution of a range of computer vision problems.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 3 sentences without a confident label
Cites as background 1 paper
-
There are also approaches based on numerical linear algebra techniques, mainly on eigenvalue computations e.g., [ref] .
Yet another eigenvalue algorithm for solving polynomial systems · Methods for Solving Polynomial Systems · 0.86
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.