Numerical Methods for Geometric Vision: From Minimal to Large Scale Problems
(2010) Abstract
 This thesis presents a number of results and algorithms for the numerical solution of problems in geometric computer vision. In geometric computer vision one tries to extract geometric information about the world and the observer from a sequence of images. Estimation of scene structure and camera motion using only image data has been one of the central themes of research in photogrammetry, geodesy and computer vision. It has important applications for robotics, autonomous vehicles, cartography, architecture, the movie industry, photography etc. Images inherently provide ambiguous and uncertain data about the world. Hence, geometric computer vision turns out to be as much about statistics as about geometry. Basically we consider two types... (More)
 This thesis presents a number of results and algorithms for the numerical solution of problems in geometric computer vision. In geometric computer vision one tries to extract geometric information about the world and the observer from a sequence of images. Estimation of scene structure and camera motion using only image data has been one of the central themes of research in photogrammetry, geodesy and computer vision. It has important applications for robotics, autonomous vehicles, cartography, architecture, the movie industry, photography etc. Images inherently provide ambiguous and uncertain data about the world. Hence, geometric computer vision turns out to be as much about statistics as about geometry. Basically we consider two types of problems: Minimal problems where the number of constraints exactly matches the number of unknowns and large scale problems which need to be addressed using efficient optimization algorithms. Solvers for minimal problems are used heavily during preprocessing to eliminate outliers in uncertain data. Such problems are usually solved by finding the zeros of a system of polynomial equations.
The numerical solution of general systems of polynomial equations is largely an open problem. In this thesis we present several new results on techniques for solving systems of polynomial equations in computer vision. \gb techniques for equation solving have been applied successfully to several geometric computer vision problems. However, in many cases these methods are plagued by numerical problems.
In this work we show that an extension of the current state of the art is possible by relaxing many of the restrictions imposed by requiring properly defined \gbs and monomial orderings. This unlocks substantial freedom which can be used to derive new, numerically more stable algorithms. These new techniques are studied on some of the latest reported uses of \gb methods in computer vision and we demonstrate dramatically improved numerical stability. Finally, the new techniques are applied to a set of previously unsolved computer vision problems and we show that efficient and stable algorithms for numerical solution of these problems can now be given.
Bundle adjustment is a key component of almost any feature based 3D reconstruction system, used to compute accurate estimates of calibration parameters and structure and motion configurations. These problems tend to be very large, often involving thousands of variables. Thus, efficient optimization methods are crucial. The traditional LevenbergMarquardt algorithm with a direct sparse solver can be efficiently adapted to the special structure of the problem and works well for small to medium size setups. However, for larger scale configurations the cubic computational complexity makes this approach prohibitively expensive.
An alternative to this approach is to apply the conjugate gradients algorithm in the inner loop. This is appealing since the main computational step of the CG algorithm involves only a simple matrixvector multiplication with the Jacobian. In this work we improve on the latest published approaches to bundle adjustment with conjugate gradients by making full use of the least squares nature of the problem and adressing the difficult question of preconditioning. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1600423
 author
 Byröd, Martin ^{LU}
 supervisor

 Karl Åström ^{LU}
 opponent

 Professor Fitzgibbon, Andrew, Microsoft
 organization
 publishing date
 2010
 type
 Thesis
 publication status
 published
 subject
 keywords
 Minimal Problems, Bundle Adjustment, Computer Vision, Polynomial Equations
 pages
 160 pages
 publisher
 Centre for Mathematical Sciences, Lund University
 defense location
 Lecture hall MH:C, CEntre for Mathematical Sciences, Sölvegatan 18, Lund UniversityFaculty of Engineering
 defense date
 20100611 13:15
 ISBN
 9789162880910
 language
 English
 LU publication?
 yes
 id
 da5f569e80ad43a69654822775b64468 (old id 1600423)
 date added to LUP
 20100518 15:30:16
 date last changed
 20160919 08:45:09
@phdthesis{da5f569e80ad43a69654822775b64468, abstract = {This thesis presents a number of results and algorithms for the numerical solution of problems in geometric computer vision. In geometric computer vision one tries to extract geometric information about the world and the observer from a sequence of images. Estimation of scene structure and camera motion using only image data has been one of the central themes of research in photogrammetry, geodesy and computer vision. It has important applications for robotics, autonomous vehicles, cartography, architecture, the movie industry, photography etc. Images inherently provide ambiguous and uncertain data about the world. Hence, geometric computer vision turns out to be as much about statistics as about geometry. Basically we consider two types of problems: Minimal problems where the number of constraints exactly matches the number of unknowns and large scale problems which need to be addressed using efficient optimization algorithms. Solvers for minimal problems are used heavily during preprocessing to eliminate outliers in uncertain data. Such problems are usually solved by finding the zeros of a system of polynomial equations.<br/><br> <br/><br> The numerical solution of general systems of polynomial equations is largely an open problem. In this thesis we present several new results on techniques for solving systems of polynomial equations in computer vision. \gb techniques for equation solving have been applied successfully to several geometric computer vision problems. However, in many cases these methods are plagued by numerical problems.<br/><br> <br/><br> In this work we show that an extension of the current state of the art is possible by relaxing many of the restrictions imposed by requiring properly defined \gbs and monomial orderings. This unlocks substantial freedom which can be used to derive new, numerically more stable algorithms. These new techniques are studied on some of the latest reported uses of \gb methods in computer vision and we demonstrate dramatically improved numerical stability. Finally, the new techniques are applied to a set of previously unsolved computer vision problems and we show that efficient and stable algorithms for numerical solution of these problems can now be given.<br/><br> <br/><br> Bundle adjustment is a key component of almost any feature based 3D reconstruction system, used to compute accurate estimates of calibration parameters and structure and motion configurations. These problems tend to be very large, often involving thousands of variables. Thus, efficient optimization methods are crucial. The traditional LevenbergMarquardt algorithm with a direct sparse solver can be efficiently adapted to the special structure of the problem and works well for small to medium size setups. However, for larger scale configurations the cubic computational complexity makes this approach prohibitively expensive.<br/><br> <br/><br> An alternative to this approach is to apply the conjugate gradients algorithm in the inner loop. This is appealing since the main computational step of the CG algorithm involves only a simple matrixvector multiplication with the Jacobian. In this work we improve on the latest published approaches to bundle adjustment with conjugate gradients by making full use of the least squares nature of the problem and adressing the difficult question of preconditioning.}, author = {Byröd, Martin}, isbn = {9789162880910}, keyword = {Minimal Problems,Bundle Adjustment,Computer Vision,Polynomial Equations}, language = {eng}, pages = {160}, publisher = {Centre for Mathematical Sciences, Lund University}, school = {Lund University}, title = {Numerical Methods for Geometric Vision: From Minimal to Large Scale Problems}, year = {2010}, }