Advanced

Tractable Algorithms for Robust Model Estimation

Enqvist, Olof LU ; Ask, Erik LU ; Kahl, Fredrik LU and Åström, Karl LU (2015) In International Journal of Computer Vision 112(1). p.115-129
Abstract
What is the computational complexity of geometric model estimation in the presence of noise and outliers? We show that the number of outliers can be minimized in polynomial time with respect to the number of measurements, although exponential in the model dimension. Moreover, for a large class of problems, we prove that the statistically more desirable truncated L2-norm can be optimized with the same complexity. In a similar vein, it is also shown how to transform a multi-model estimation problem into a purely combinatorial one—with worst-case complexity that is polynomial in the number of measurements but exponential in the number of models. We apply our framework to a series of hard fitting problems. It gives a practical method for... (More)
What is the computational complexity of geometric model estimation in the presence of noise and outliers? We show that the number of outliers can be minimized in polynomial time with respect to the number of measurements, although exponential in the model dimension. Moreover, for a large class of problems, we prove that the statistically more desirable truncated L2-norm can be optimized with the same complexity. In a similar vein, it is also shown how to transform a multi-model estimation problem into a purely combinatorial one—with worst-case complexity that is polynomial in the number of measurements but exponential in the number of models. We apply our framework to a series of hard fitting problems. It gives a practical method for simultaneously dealing with measurement noise and large amounts of outliers in the estimation of low-dimensional models. Experimental results and a comparison to random sampling techniques are presented for the applications rigid registration, triangulation and stitching. (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
Outliers Geometry Optimization 3D reconstruction Image registration
in
International Journal of Computer Vision
volume
112
issue
1
pages
115 - 129
publisher
Springer
external identifiers
  • wos:000350361500006
  • scopus:84924022008
ISSN
1573-1405
DOI
10.1007/s11263-014-0760-2
language
English
LU publication?
yes
id
8bbe9fb5-f855-43e7-a348-cdb2d86ecb48 (old id 5142569)
date added to LUP
2015-03-09 10:48:59
date last changed
2017-09-03 03:14:26
@article{8bbe9fb5-f855-43e7-a348-cdb2d86ecb48,
  abstract     = {What is the computational complexity of geometric model estimation in the presence of noise and outliers? We show that the number of outliers can be minimized in polynomial time with respect to the number of measurements, although exponential in the model dimension. Moreover, for a large class of problems, we prove that the statistically more desirable truncated L2-norm can be optimized with the same complexity. In a similar vein, it is also shown how to transform a multi-model estimation problem into a purely combinatorial one—with worst-case complexity that is polynomial in the number of measurements but exponential in the number of models. We apply our framework to a series of hard fitting problems. It gives a practical method for simultaneously dealing with measurement noise and large amounts of outliers in the estimation of low-dimensional models. Experimental results and a comparison to random sampling techniques are presented for the applications rigid registration, triangulation and stitching.},
  author       = {Enqvist, Olof and Ask, Erik and Kahl, Fredrik and Åström, Karl},
  issn         = {1573-1405},
  keyword      = {Outliers Geometry Optimization 3D reconstruction Image registration},
  language     = {eng},
  number       = {1},
  pages        = {115--129},
  publisher    = {Springer},
  series       = {International Journal of Computer Vision},
  title        = {Tractable Algorithms for Robust Model Estimation},
  url          = {http://dx.doi.org/10.1007/s11263-014-0760-2},
  volume       = {112},
  year         = {2015},
}