Advanced

Optimal Geometric Fitting Under the Truncated L-2-Norm

Ask, Erik LU ; Enqvist, Olof LU and Kahl, Fredrik LU (2013) 26th IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013 p.1722-1729
Abstract
This paper is concerned with model fitting in the presence of noise and outliers. Previously it has been shown that the number of outliers can be minimized with polynomial complexity in the number of measurements. This paper improves on these results in two ways. First, it is shown that for a large class of problems, the statistically more desirable truncated L-2-norm can be optimized with the same complexity. Then, with the same methodology, it is shown how to transform multi-model fitting into a purely combinatorial problem-with worst-case complexity that is polynomial in the number of measurements, though exponential in the number of models. We apply our framework to a series of hard registration and stitching problems demonstrating... (More)
This paper is concerned with model fitting in the presence of noise and outliers. Previously it has been shown that the number of outliers can be minimized with polynomial complexity in the number of measurements. This paper improves on these results in two ways. First, it is shown that for a large class of problems, the statistically more desirable truncated L-2-norm can be optimized with the same complexity. Then, with the same methodology, it is shown how to transform multi-model fitting into a purely combinatorial problem-with worst-case complexity that is polynomial in the number of measurements, though exponential in the number of models. We apply our framework to a series of hard registration and stitching problems demonstrating that the approach is not only of theoretical interest. It gives a practical method for simultaneously dealing with measurement noise and large amounts of outliers for fitting problems with low-dimensional models. (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
host publication
2013 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
pages
1722 - 1729
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
26th IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013
conference location
Portland, OR, United States
conference dates
2013-06-23 - 2013-06-28
external identifiers
  • wos:000331094301099
  • scopus:84887322776
ISSN
1063-6919
DOI
10.1109/CVPR.2013.225
language
English
LU publication?
yes
id
2bb87afc-5a4b-4012-91af-f5c124f83de7 (old id 4376276)
date added to LUP
2014-04-14 13:38:48
date last changed
2019-03-17 04:15:58
@inproceedings{2bb87afc-5a4b-4012-91af-f5c124f83de7,
  abstract     = {This paper is concerned with model fitting in the presence of noise and outliers. Previously it has been shown that the number of outliers can be minimized with polynomial complexity in the number of measurements. This paper improves on these results in two ways. First, it is shown that for a large class of problems, the statistically more desirable truncated L-2-norm can be optimized with the same complexity. Then, with the same methodology, it is shown how to transform multi-model fitting into a purely combinatorial problem-with worst-case complexity that is polynomial in the number of measurements, though exponential in the number of models. We apply our framework to a series of hard registration and stitching problems demonstrating that the approach is not only of theoretical interest. It gives a practical method for simultaneously dealing with measurement noise and large amounts of outliers for fitting problems with low-dimensional models.},
  author       = {Ask, Erik and Enqvist, Olof and Kahl, Fredrik},
  issn         = {1063-6919},
  language     = {eng},
  location     = {Portland, OR, United States},
  pages        = {1722--1729},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  title        = {Optimal Geometric Fitting Under the Truncated L-2-Norm},
  url          = {http://dx.doi.org/10.1109/CVPR.2013.225},
  year         = {2013},
}