Advanced

Efficient algorithms for robust estimation of relative translation

Fredriksson, Johan LU ; Larsson, Viktor LU ; Olsson, Carl LU ; Enqvist, Olof and Kahl, Fredrik LU (2016) In Image and Vision Computing 52. p.114-124
Abstract

One of the key challenges for structure from motion systems in order to make them robust to failure is the ability to handle outliers among the correspondences. In this paper we present two new algorithms that find the optimal solution in the presence of outliers when the camera undergoes a pure translation. The first algorithm has polynomial-time computational complexity, independently of the amount of outliers. The second algorithm does not offer such a theoretical complexity guarantee, but we demonstrate that it is magnitudes faster in practice. No random sampling approaches such as RANSAC are guaranteed to find an optimal solution, while our two methods do. We evaluate and compare the algorithms both on synthetic and real... (More)

One of the key challenges for structure from motion systems in order to make them robust to failure is the ability to handle outliers among the correspondences. In this paper we present two new algorithms that find the optimal solution in the presence of outliers when the camera undergoes a pure translation. The first algorithm has polynomial-time computational complexity, independently of the amount of outliers. The second algorithm does not offer such a theoretical complexity guarantee, but we demonstrate that it is magnitudes faster in practice. No random sampling approaches such as RANSAC are guaranteed to find an optimal solution, while our two methods do. We evaluate and compare the algorithms both on synthetic and real experiments. We also embed the algorithms in a larger system, where we optimize for the rotation angle as well (the rotation axis is measured by other means). The experiments show that for problems with a large amount of outliers, the RANSAC estimates may deteriorate compared to our optimal methods.

(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
Branch and bound, Epipolar geometry, Structure from motion, Two-view geometry
in
Image and Vision Computing
volume
52
pages
11 pages
publisher
Elsevier
external identifiers
  • scopus:84974658584
  • wos:000383818400009
ISSN
0262-8856
DOI
10.1016/j.imavis.2016.05.011
language
English
LU publication?
yes
id
46f16c3d-749b-4c8a-95fe-f5a8779a4fa5
date added to LUP
2016-12-13 10:29:11
date last changed
2017-02-02 10:25:59
@article{46f16c3d-749b-4c8a-95fe-f5a8779a4fa5,
  abstract     = {<p>One of the key challenges for structure from motion systems in order to make them robust to failure is the ability to handle outliers among the correspondences. In this paper we present two new algorithms that find the optimal solution in the presence of outliers when the camera undergoes a pure translation. The first algorithm has polynomial-time computational complexity, independently of the amount of outliers. The second algorithm does not offer such a theoretical complexity guarantee, but we demonstrate that it is magnitudes faster in practice. No random sampling approaches such as RANSAC are guaranteed to find an optimal solution, while our two methods do. We evaluate and compare the algorithms both on synthetic and real experiments. We also embed the algorithms in a larger system, where we optimize for the rotation angle as well (the rotation axis is measured by other means). The experiments show that for problems with a large amount of outliers, the RANSAC estimates may deteriorate compared to our optimal methods.</p>},
  author       = {Fredriksson, Johan and Larsson, Viktor and Olsson, Carl and Enqvist, Olof and Kahl, Fredrik},
  issn         = {0262-8856},
  keyword      = {Branch and bound,Epipolar geometry,Structure from motion,Two-view geometry},
  language     = {eng},
  month        = {08},
  pages        = {114--124},
  publisher    = {Elsevier},
  series       = {Image and Vision Computing},
  title        = {Efficient algorithms for robust estimation of relative translation},
  url          = {http://dx.doi.org/10.1016/j.imavis.2016.05.011},
  volume       = {52},
  year         = {2016},
}