Using Sparse Elimination for Solving Minimal Problems in Computer Vision
Janne Heikkila
(University of Oulu, Finland)
Abstract:
Finding a closed form solution to a system of polynomial equations is a common
problem in computer vision as well as in many other areas of engineering and
science. Gröbner basis techniques are often employed to provide the solution,
but implementing an efficient Gröbner basis solver to a given problem requires
strong expertise in algebraic geometry. One can also convert the equations to a
polynomial eigenvalue problem (PEP) and solve it using linear algebra, which is
a more accessible approach for those who are not so familiar with algebraic
geometry. In previous works PEP has been successfully applied for solving some
relative pose problems in computer vision, but its wider exploitation is limited
by the problem of finding a compact monomial basis.
In this talk, I present a new algorithm for selecting the basis that is in
general more compact than the basis obtained with a state-of-the-art algorithm
making PEP a more viable option for solving polynomial equations. Two minimal
problems are also presented for camera self-calibration based on homography, and
it is demonstrated experimentally using synthetic and real data that our
algorithm can provide a numerically stable solution to the camera focal length
from two homographies of unknown planar scene.