Verifying Global Minima for L2 Minimization Problems in Multiple View Geometry
(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:
https://lup.lub.lu.se/record/3327286
- author
- Hartley, Richard ; Kahl, Fredrik LU ; Olsson, Carl LU and Seo, Yongdeuk
- organization
- publishing date
- 2012
- 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
- 2016-04-01 11:06:34
- date last changed
- 2022-04-28 07:15:25
@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}},
keywords = {{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}},
doi = {{10.1007/s11263-012-0569-9}},
volume = {{101}},
year = {{2012}},
}