University of Oulu

J. Heikkilä, "Using Sparse Elimination for Solving Minimal Problems in Computer Vision," 2017 IEEE International Conference on Computer Vision (ICCV), Venice, 2017, pp. 76-84. doi: 10.1109/ICCV.2017.18

Using sparse elimination for solving minimal problems in computer vision

Saved in:
Author: Heikkilä, Janne1
Organizations: 1Center for Machine Vision and Signal Analysis, University of Oulu, Finland
Format: article
Version: accepted version
Access: open
Online Access: PDF Full Text (PDF, 0.6 MB)
Persistent link:
Language: English
Published: Institute of Electrical and Electronics Engineers, 2017
Publish Date: 2020-02-25


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 paper, we propose 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. Another contribution is that we present two minimal problems for camera self-calibration based on homography, and demonstrate 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.

see all

ISBN Print: 978-1-5386-1032-9
Pages: 76 - 84
DOI: 10.1109/ICCV.2017.18
Host publication: 2017 IEEE International Conference on Computer Vision (ICCV)
Conference: IEEE International Conference on Computer Vision
Type of Publication: A4 Article in conference proceedings
Field of Science: 113 Computer and information sciences
213 Electronic, automation and communications engineering, electronics
Copyright information: © 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.