Advanced

Global Optimization through Rotation Space Search

Hartley, Richard I and Kahl, Fredrik LU (2009) In International Journal of Computer Vision 82(1). p.64-79
Abstract
This paper introduces a new algorithmic technique for solving certain problems in geometric computer vision. The main novelty of the method is a branch-and-bound search over rotation space, which is used in this paper to determine camera orientation. By searching over all possible rotations, problems can be reduced to known fixed-rotation problems for which optimal solutions have been previously given. In particular, a method is developed for the estimation of the essential matrix, giving the first guaranteed optimal algorithm for estimating the relative pose using a cost function based on reprojection errors. Recently convex optimization techniques have been shown to provide optimal solutions to many of the common problems in structure... (More)
This paper introduces a new algorithmic technique for solving certain problems in geometric computer vision. The main novelty of the method is a branch-and-bound search over rotation space, which is used in this paper to determine camera orientation. By searching over all possible rotations, problems can be reduced to known fixed-rotation problems for which optimal solutions have been previously given. In particular, a method is developed for the estimation of the essential matrix, giving the first guaranteed optimal algorithm for estimating the relative pose using a cost function based on reprojection errors. Recently convex optimization techniques have been shown to provide optimal solutions to many of the common problems in structure from motion. However, they do not apply to problems involving rotations. The search method described in this paper allows such problems to be solved optimally. Apart from the essential matrix, the algorithm is applied to the camera pose problem, providing an optimal algorithm. The approach has been implemented and tested on a number of both synthetically generated and real data sets with good performance. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Global optimization, Essential matrix, Branch-and-bound algorithm
in
International Journal of Computer Vision
volume
82
issue
1
pages
64 - 79
publisher
Springer
external identifiers
  • wos:000262986100004
  • scopus:59149100446
ISSN
1573-1405
DOI
10.1007/s11263-008-0186-9
language
English
LU publication?
yes
id
b1c4e168-d744-42a0-87da-46a7a651434e (old id 1311470)
date added to LUP
2009-03-17 09:54:37
date last changed
2017-10-22 03:33:58
@article{b1c4e168-d744-42a0-87da-46a7a651434e,
  abstract     = {This paper introduces a new algorithmic technique for solving certain problems in geometric computer vision. The main novelty of the method is a branch-and-bound search over rotation space, which is used in this paper to determine camera orientation. By searching over all possible rotations, problems can be reduced to known fixed-rotation problems for which optimal solutions have been previously given. In particular, a method is developed for the estimation of the essential matrix, giving the first guaranteed optimal algorithm for estimating the relative pose using a cost function based on reprojection errors. Recently convex optimization techniques have been shown to provide optimal solutions to many of the common problems in structure from motion. However, they do not apply to problems involving rotations. The search method described in this paper allows such problems to be solved optimally. Apart from the essential matrix, the algorithm is applied to the camera pose problem, providing an optimal algorithm. The approach has been implemented and tested on a number of both synthetically generated and real data sets with good performance.},
  author       = {Hartley, Richard I and Kahl, Fredrik},
  issn         = {1573-1405},
  keyword      = {Global optimization,Essential matrix,Branch-and-bound algorithm},
  language     = {eng},
  number       = {1},
  pages        = {64--79},
  publisher    = {Springer},
  series       = {International Journal of Computer Vision},
  title        = {Global Optimization through Rotation Space Search},
  url          = {http://dx.doi.org/10.1007/s11263-008-0186-9},
  volume       = {82},
  year         = {2009},
}