Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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 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
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Image Analysis, Proceedings
volume
5575
pages
686 - 695
publisher
Springer
conference name
16th Scandinavian Conference on Image Analysis
conference location
Oslo, Norway
conference dates
2009-06-15 - 2009-06-18
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
2016-04-01 11:56:27
date last changed
2024-01-08 02:12:53
@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}},
}