Advanced

Verifying Global Minima for L2 Minimization Problems in Multiple View Geometry

Hartley, Richard; Kahl, Fredrik LU ; Olsson, Carl LU and Seo, Yongdeuk (2012) In International Journal of Computer Vision 101(2). p.288-304
Abstract
We consider the least-squares (L2) minimization

problems in multiple view geometry for triangulation, homography,

camera resectioning and structure-and-motion

with known rotatation, or known plane. Although optimal

algorithms have been given for these problems under an Linfinity

cost function, finding optimal least-squares solutions

to these problems is difficult, since the cost functions are not

convex, and in the worst case may have multiple minima.

Iterative methods can be used to find a good solution, but

this may be a local minimum. This paper provides a method

for verifying whether a local-minimum solution is globally

optimal, by... (More)
We consider the least-squares (L2) minimization

problems in multiple view geometry for triangulation, homography,

camera resectioning and structure-and-motion

with known rotatation, or known plane. Although optimal

algorithms have been given for these problems under an Linfinity

cost function, finding optimal least-squares solutions

to these problems is difficult, since the cost functions are not

convex, and in the worst case may have multiple minima.

Iterative methods can be used to find a good solution, but

this may be a local minimum. This paper provides a method

for verifying whether a local-minimum solution is globally

optimal, by providing a simple and rapid test involving the

Hessian of the cost function. The basic idea is that by showing

that the cost function is convex in a restricted but large

enough neighbourhood, a sufficient condition for global optimality

is obtained.

The method is tested on numerous problem instances of

real data sets. In the vast majority of cases we are able to

verify that the solutions are optimal, in particular, for small

to medium-scale problems. (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
reconstruction, Geometric optimization, convex programming
in
International Journal of Computer Vision
volume
101
issue
2
pages
288 - 304
publisher
Springer
external identifiers
  • wos:000314291600004
  • scopus:84873128136
ISSN
1573-1405
DOI
10.1007/s11263-012-0569-9
language
English
LU publication?
yes
id
2b0b8d9d-86a2-486e-afb8-fcc10e0bb4e6 (old id 3327286)
date added to LUP
2013-02-12 18:14:23
date last changed
2017-07-30 03:27:19
@article{2b0b8d9d-86a2-486e-afb8-fcc10e0bb4e6,
  abstract     = {We consider the least-squares (L2) minimization<br/><br>
problems in multiple view geometry for triangulation, homography,<br/><br>
camera resectioning and structure-and-motion<br/><br>
with known rotatation, or known plane. Although optimal<br/><br>
algorithms have been given for these problems under an Linfinity<br/><br>
cost function, finding optimal least-squares solutions<br/><br>
to these problems is difficult, since the cost functions are not<br/><br>
convex, and in the worst case may have multiple minima.<br/><br>
Iterative methods can be used to find a good solution, but<br/><br>
this may be a local minimum. This paper provides a method<br/><br>
for verifying whether a local-minimum solution is globally<br/><br>
optimal, by providing a simple and rapid test involving the<br/><br>
Hessian of the cost function. The basic idea is that by showing<br/><br>
that the cost function is convex in a restricted but large<br/><br>
enough neighbourhood, a sufficient condition for global optimality<br/><br>
is obtained.<br/><br>
The method is tested on numerous problem instances of<br/><br>
real data sets. In the vast majority of cases we are able to<br/><br>
verify that the solutions are optimal, in particular, for small<br/><br>
to medium-scale problems.},
  author       = {Hartley, Richard and Kahl, Fredrik and Olsson, Carl and Seo, Yongdeuk},
  issn         = {1573-1405},
  keyword      = {reconstruction,Geometric optimization,convex programming},
  language     = {eng},
  number       = {2},
  pages        = {288--304},
  publisher    = {Springer},
  series       = {International Journal of Computer Vision},
  title        = {Verifying Global Minima for L2 Minimization Problems in Multiple View Geometry},
  url          = {http://dx.doi.org/10.1007/s11263-012-0569-9},
  volume       = {101},
  year         = {2012},
}