Advanced

Numerically Stable Optimization of Polynomial Solvers for Minimal Problems

Kuang, Yubin LU and Åström, Karl LU (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 7-13, 2012, Proceedings, Part III) 7574. p.100-113
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 state-of-the-art 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 state-of-the-art 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:
author
organization
publishing date
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 7-13, 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
0302-9743
1611-3349
ISBN
978-3-642-33711-6 (print)
3642337112
978-3-642-33712-3 (online)
DOI
10.1007/978-3-642-33712-3_8
language
English
LU publication?
yes
id
eda580cc-9fbf-4bf2-b93f-081963907d39 (old id 3424815)
alternative location
http://link.springer.com/chapter/10.1007/978-3-642-33712-3_8
date added to LUP
2013-05-07 15:19:12
date last changed
2017-02-19 03:22:28
@inproceedings{eda580cc-9fbf-4bf2-b93f-081963907d39,
  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 state-of-the-art 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 7-13, 2012, Proceedings, Part III)},
  editor       = {Fitzgibbon, Andrew},
  isbn         = {978-3-642-33711-6 (print)},
  issn         = {0302-9743},
  keyword      = {polynomial equations,computer vision,geometry},
  language     = {eng},
  pages        = {100--113},
  publisher    = {Springer},
  title        = {Numerically Stable Optimization of Polynomial Solvers for Minimal Problems},
  url          = {http://dx.doi.org/10.1007/978-3-642-33712-3_8},
  volume       = {7574},
  year         = {2012},
}