Algebraic Methods in Computer Vision

Abstract

Many problems in computer vision require efficient solvers for solving systems of non-linear polynomial equations. For instance relative and absolute camera pose computations and estimation of the camera lens distortion are examples of problems that can be formulated as minimal problems, i.e. they can be solved from a minimal number of input data and lead to solving systems of polynomial equations with a finite number of solutions. Often, polynomial systems arising from minimal problems are not trivial and general algorithms for solving systems of polynomial equations are not efficient for them. Therefore, special algorithms have to be designed to achieve numerical robustness and computational efficiency. In this thesis we review two general algebraic methods for solving systems of polynomial equations, the Groebner basis and the resultant based methods, and suggest their modifications, which are suitable for many computer vision problems. The main difference between the modified methods and the general methods is that the modified methods use the structure of the system of polynomial equations representing a particular problem to design an efficient specific solver for this problem. These modified methods consist of two phases. In the first phase, preprocessing and computations common to all considered instances of the given problem are performed and an efficient specific solver is constructed. For a particular problem this phase needs to be performed only once. In the second phase, the specific solver is used to efficiently solve concrete instances of the particular problem. This efficient specific solver is not general and solves only systems of polynomial equations of one form. However, it is faster than a general solver and suitable for applications that appear in computer vision and robotics. Construction of efficient specific solvers can be easily automated and therefore used even by non-experts to solve technical problems leading to systems of polynomial equations. In this thesis we propose an automatic generator of such efficient specific solvers based on the modified Groebner basis method. We demonstrate the usefulness of our approach by providing new, efficient and numerical stable solutions to several important relative pose problems, most of them previously unsolved. These problems include estimating relative pose and internal parameters of calibrated, partially calibrated (with unknown focal length), or completely uncalibrated perspective or radially distorted cameras observing general scenes or scenes with dominant plane. All these problems can be efficiently used in many applications such as camera localization, structure-from-motion, scene reconstruction, tracking and recognition. The quality of all presented solvers is demonstrated on synthetic and real data.

Gallery

3D reconstructions

Radial Distortion

Selected Publications

Journal Articles

Conference Papers

Included in the thesis

Conference papers realted to the thesis

Downloads

PhD Thesis

PhD Thesis - Algebraic methods in Computer Vision

Thesis statement

Doctoral Thesis Statement

Presentation

Powerpoint Presentation

CV

Curriculum Vitae

Contact Information

Zuzana Kukelova

Karlovo namesti 13, 121-35 Praha 2, 
Czech Republic
Tel.: +420-224-355-725
Fax: +420-224-357-385
ICQ: 213-365-550
E-mail: kukelova(at)cmp.felk.cvut.cz

Center for Machine Perception
Department of Cybernetics
Faculty of Electrical Engineering
Czech Technical University in Prague