Advanced

Projective Least-Squares: Global Solutions with Local Optimization

Olsson, Carl LU ; Kahl, Fredrik LU and Hartley, Richard (2009) IEEE-Computer-Society Conference on Computer Vision and Pattern Recognition Workshops, 2009 In CVPR: 2009 IEEE Conference on Computer Vision and Pattern Recognition p.1216-1223
Abstract
Recent work in multiple view geometry has focused on obtaining globally optimal solutions at the price of computational time efficiency. On the other hand, traditional bundle adjustment algorithms have been found to provide good solutions even though there may be multiple local minima. In this paper we justify this observation by giving a simple sufficient condition for global optimality that can be used to verify that a solution obtained from any local method is indeed global. The method is tested on numerous problem instances of both synthetic and real data sets. In the vast majority of cases we are able to verify that the solutions are optimal, in particular for small-scale problems. We also develop a branch and bound procedure that... (More)
Recent work in multiple view geometry has focused on obtaining globally optimal solutions at the price of computational time efficiency. On the other hand, traditional bundle adjustment algorithms have been found to provide good solutions even though there may be multiple local minima. In this paper we justify this observation by giving a simple sufficient condition for global optimality that can be used to verify that a solution obtained from any local method is indeed global. The method is tested on numerous problem instances of both synthetic and real data sets. In the vast majority of cases we are able to verify that the solutions are optimal, in particular for small-scale problems. We also develop a branch and bound procedure that goes beyond verification. In cases where the sufficient condition does not hold, the algorithm returns either of the following two results: (i) a certificate of global optimality for the local solution or (ii) the global solution. (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
in
CVPR: 2009 IEEE Conference on Computer Vision and Pattern Recognition
pages
1216 - 1223
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
IEEE-Computer-Society Conference on Computer Vision and Pattern Recognition Workshops, 2009
external identifiers
  • wos:000279038000156
  • scopus:70450203323
ISSN
1063-6919
DOI
10.1109/CVPR.2009.5206864
language
English
LU publication?
yes
id
96f82c79-ba4c-4516-8238-441751555c6e (old id 1628606)
date added to LUP
2010-07-23 10:49:58
date last changed
2017-02-19 03:45:48
@inproceedings{96f82c79-ba4c-4516-8238-441751555c6e,
  abstract     = {Recent work in multiple view geometry has focused on obtaining globally optimal solutions at the price of computational time efficiency. On the other hand, traditional bundle adjustment algorithms have been found to provide good solutions even though there may be multiple local minima. In this paper we justify this observation by giving a simple sufficient condition for global optimality that can be used to verify that a solution obtained from any local method is indeed global. The method is tested on numerous problem instances of both synthetic and real data sets. In the vast majority of cases we are able to verify that the solutions are optimal, in particular for small-scale problems. We also develop a branch and bound procedure that goes beyond verification. In cases where the sufficient condition does not hold, the algorithm returns either of the following two results: (i) a certificate of global optimality for the local solution or (ii) the global solution.},
  author       = {Olsson, Carl and Kahl, Fredrik and Hartley, Richard},
  booktitle    = {CVPR: 2009 IEEE Conference on Computer Vision and Pattern Recognition},
  issn         = {1063-6919},
  language     = {eng},
  pages        = {1216--1223},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  title        = {Projective Least-Squares: Global Solutions with Local Optimization},
  url          = {http://dx.doi.org/10.1109/CVPR.2009.5206864},
  year         = {2009},
}