for Solving Polynomial Systems in Computer Vision Applications

CVPR 2024 Seattle

1:30 -- 6:00 PM PT

**Ben Kimia**(Brown)**Tim Duff**(UW)**Ricardo Fabbri**(IPRJ/UERJ)**Hongyi Fan**(Cognex)

**1:30 -- 2:00**(Kimia) Motivation and Need**2:00 -- 2:30**(Fan) Approaches to solving polynomial problems Slides**2:30 -- 3:00**(Duff) General Introduction to Homotopy - Continuation (Part 1). Slides**3:00 -- 4:00**Coffee Break**4:00 -- 4:30**(Duff) General Introduction to Homotopy Continuation (Part 2)**4:30 -- 4:50**(Fabbri) Efficient Implementation of Homotopy Continuation Slides**4:50 -- 5:10**(Fan) GPU Implementation of HC for Real-Time Usage Slides**5:10 -- 5:50**(Fabbri) Building your own fast Homotopy Continuation solver: Solver
**5:50 -- 6:00**(Kimia) Closing Remarks

Minimal problems and their solvers play an important role in RANSAC-based approaches to several estimation problems in vision. Minimal solvers solve systems of equations, depending on data, which obey a “conservation of number principle”: for sufficiently generic data, the number of solutions over the complex numbers is constant. Homotopy continuation (HC) methods exploit not just this conservation principle, but also the smooth dependence of solutions on problem data. The classical solution of polynomial systems using Gröbner bases, resultants, elimination templates, etc. has been largely successful in smaller problems, but these methods are not able to tackle larger polynomials systems with a larger number of solutions. While HC methods can solve these problems, they have been notoriously slow. Recent research by the presenters and other researchers has enabled efficient HC solvers with the ability for real-time solutions.

The main objective of this tutorial is to make this technology more accessible to the computer vision community. Specifically, after an overview of how such methods can be useful for solving problems in vision (e.g., absolute/relative pose, triangulation), we will describe some of the basic theoretical apparatus underlying HC solvers, including both local and global “probability-1” aspects. On the practical side, we will describe recent advances enabled by GPUs and how to build your own HC-based minimal solvers.