Advanced

Globally Optimal Least Squares Solutions for Quasiconvex 1D Vision Problems

Olsson, Carl LU ; Byröd, Martin LU and Kahl, Fredrik LU (2009) 16th Scandinavian Conference on Image Analysis In Image Analysis, Proceedings 5575. p.686-695
Abstract
Solutions to non-linear least squares problems play an essential role in structure and motion problems in computer vision. The predominant approach for solving these problems is a Newton like scheme which uses the: hessian of the function to iteratively find a, local solution. Although fast, this strategy inevitably leeds to issues with poor local minima, and missed global minima. In this paper rather than trying to develop all algorithm that is guaranteed to always work, we show that it is often possible to verify that a local solution is in fact; also global. We present a simple test that verifies optimality of a solution using only a few linear programs. We show oil both synthetic and real data that for the vast majority of cases we are... (More)
Solutions to non-linear least squares problems play an essential role in structure and motion problems in computer vision. The predominant approach for solving these problems is a Newton like scheme which uses the: hessian of the function to iteratively find a, local solution. Although fast, this strategy inevitably leeds to issues with poor local minima, and missed global minima. In this paper rather than trying to develop all algorithm that is guaranteed to always work, we show that it is often possible to verify that a local solution is in fact; also global. We present a simple test that verifies optimality of a solution using only a few linear programs. We show oil both synthetic and real data that for the vast majority of cases we are able to verify optimality. Further more we show even if the above test fails it is still often possible to verify that the local solution is global with high probability. (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
Image Analysis, Proceedings
volume
5575
pages
686 - 695
publisher
Springer
conference name
16th Scandinavian Conference on Image Analysis
external identifiers
  • wos:000268661000070
  • scopus:70350626791
ISSN
1611-3349
0302-9743
language
English
LU publication?
yes
id
a20253bd-6ed9-4391-a93b-7f7976b594ff (old id 1460148)
date added to LUP
2009-08-25 11:58:37
date last changed
2017-06-04 03:35:27
@inproceedings{a20253bd-6ed9-4391-a93b-7f7976b594ff,
  abstract     = {Solutions to non-linear least squares problems play an essential role in structure and motion problems in computer vision. The predominant approach for solving these problems is a Newton like scheme which uses the: hessian of the function to iteratively find a, local solution. Although fast, this strategy inevitably leeds to issues with poor local minima, and missed global minima. In this paper rather than trying to develop all algorithm that is guaranteed to always work, we show that it is often possible to verify that a local solution is in fact; also global. We present a simple test that verifies optimality of a solution using only a few linear programs. We show oil both synthetic and real data that for the vast majority of cases we are able to verify optimality. Further more we show even if the above test fails it is still often possible to verify that the local solution is global with high probability.},
  author       = {Olsson, Carl and Byröd, Martin and Kahl, Fredrik},
  booktitle    = {Image Analysis, Proceedings},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {686--695},
  publisher    = {Springer},
  title        = {Globally Optimal Least Squares Solutions for Quasiconvex 1D Vision Problems},
  volume       = {5575},
  year         = {2009},
}