Numerically Stable Optimization of Polynomial Solvers for Minimal Problems
(2012) 12th European Conference on Computer Vision (ECCV 2012) In Lecture Notes in Computer Science (Computer Vision ECCV 2012, 12th European Conference on Computer Vision, Florence, Italy, October 713, 2012, Proceedings, Part III) 7574. p.100113 Abstract
 Numerous geometric problems in computer vision involve the solu tion of systems of polynomial equations. This is particularly true for so called minimal problems, but also for finding stationary points for overdetermined prob lems. The stateoftheart is based on the use of numerical linear algebra on the large but sparse coefficient matrix that represents the original equations multi plied with a set of monomials. The key observation in this paper is that the speed and numerical stability of the solver depends heavily on (i) what multiplication monomials are used and (ii) the set of so called permissible monomials from which numerical linear algebra routines choose the basis of a certain quotient ring. In the paper we show that... (More)
 Numerous geometric problems in computer vision involve the solu tion of systems of polynomial equations. This is particularly true for so called minimal problems, but also for finding stationary points for overdetermined prob lems. The stateoftheart is based on the use of numerical linear algebra on the large but sparse coefficient matrix that represents the original equations multi plied with a set of monomials. The key observation in this paper is that the speed and numerical stability of the solver depends heavily on (i) what multiplication monomials are used and (ii) the set of so called permissible monomials from which numerical linear algebra routines choose the basis of a certain quotient ring. In the paper we show that optimizing with respect to these two factors can give both significant improvements to numerical stability as compared to the state of the art, as well as highly compact solvers, while still retaining numerical stabil ity. The methods are validated on several minimal problems that have previously been shown to be challenging (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/3424815
 author
 Kuang, Yubin ^{LU} and Åström, Karl ^{LU}
 organization
 publishing date
 2012
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 polynomial equations, computer vision, geometry
 in
 Lecture Notes in Computer Science (Computer Vision ECCV 2012, 12th European Conference on Computer Vision, Florence, Italy, October 713, 2012, Proceedings, Part III)
 editor
 Fitzgibbon, Andrew and
 volume
 7574
 pages
 14 pages
 publisher
 Springer
 conference name
 12th European Conference on Computer Vision (ECCV 2012)
 external identifiers

 scopus:84867876540
 ISSN
 03029743
 16113349
 ISBN
 9783642337116 (print)
 3642337112
 9783642337123 (online)
 DOI
 10.1007/9783642337123_8
 language
 English
 LU publication?
 yes
 id
 eda580cc9fbf4bf2b93f081963907d39 (old id 3424815)
 alternative location
 http://link.springer.com/chapter/10.1007/9783642337123_8
 date added to LUP
 20130507 15:19:12
 date last changed
 20170219 03:22:28
@inproceedings{eda580cc9fbf4bf2b93f081963907d39, abstract = {Numerous geometric problems in computer vision involve the solu tion of systems of polynomial equations. This is particularly true for so called minimal problems, but also for finding stationary points for overdetermined prob lems. The stateoftheart is based on the use of numerical linear algebra on the large but sparse coefficient matrix that represents the original equations multi plied with a set of monomials. The key observation in this paper is that the speed and numerical stability of the solver depends heavily on (i) what multiplication monomials are used and (ii) the set of so called permissible monomials from which numerical linear algebra routines choose the basis of a certain quotient ring. In the paper we show that optimizing with respect to these two factors can give both significant improvements to numerical stability as compared to the state of the art, as well as highly compact solvers, while still retaining numerical stabil ity. The methods are validated on several minimal problems that have previously been shown to be challenging}, author = {Kuang, Yubin and Åström, Karl}, booktitle = {Lecture Notes in Computer Science (Computer Vision ECCV 2012, 12th European Conference on Computer Vision, Florence, Italy, October 713, 2012, Proceedings, Part III)}, editor = {Fitzgibbon, Andrew}, isbn = {9783642337116 (print)}, issn = {03029743}, keyword = {polynomial equations,computer vision,geometry}, language = {eng}, pages = {100113}, publisher = {Springer}, title = {Numerically Stable Optimization of Polynomial Solvers for Minimal Problems}, url = {http://dx.doi.org/10.1007/9783642337123_8}, volume = {7574}, year = {2012}, }