Advanced

Rotation Averaging and Strong Duality

Eriksson, Anders ; Olsson, Carl LU ; Kahl, Fredrik LU and Chin, Tat Jun (2018) 31st Meeting of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2018 p.127-135
Abstract

In this paper we explore the role of duality principles within the problem of rotation averaging, a fundamental task in a wide range of computer vision applications. In its conventional form, rotation averaging is stated as a minimization over multiple rotation constraints. As these constraints are non-convex, this problem is generally considered challenging to solve globally. We show how to circumvent this difficulty through the use of Lagrangian duality. While such an approach is well-known it is normally not guaranteed to provide a tight relaxation. Based on spectral graph theory, we analytically prove that in many cases there is no duality gap unless the noise levels are severe. This allows us to obtain certifiably global solutions... (More)

In this paper we explore the role of duality principles within the problem of rotation averaging, a fundamental task in a wide range of computer vision applications. In its conventional form, rotation averaging is stated as a minimization over multiple rotation constraints. As these constraints are non-convex, this problem is generally considered challenging to solve globally. We show how to circumvent this difficulty through the use of Lagrangian duality. While such an approach is well-known it is normally not guaranteed to provide a tight relaxation. Based on spectral graph theory, we analytically prove that in many cases there is no duality gap unless the noise levels are severe. This allows us to obtain certifiably global solutions to a class of important non-convex problems in polynomial time. We also propose an efficient, scalable algorithm that outperforms general purpose numerical solvers and is able to handle the large problem instances commonly occurring in structure from motion settings. The potential of this proposed method is demonstrated on a number of different problems, consisting of both synthetic and real-world data.

(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
Proceedings - 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2018
article number
8578119
pages
9 pages
publisher
IEEE Computer Society
conference name
31st Meeting of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2018
conference location
Salt Lake City, United States
conference dates
2018-06-18 - 2018-06-22
external identifiers
  • scopus:85062884498
ISBN
9781538664209
DOI
10.1109/CVPR.2018.00021
language
English
LU publication?
yes
id
37073e8e-70b7-4d3c-97e9-222953400dfa
date added to LUP
2019-04-01 09:55:46
date last changed
2020-12-29 03:38:11
@inproceedings{37073e8e-70b7-4d3c-97e9-222953400dfa,
  abstract     = {<p>In this paper we explore the role of duality principles within the problem of rotation averaging, a fundamental task in a wide range of computer vision applications. In its conventional form, rotation averaging is stated as a minimization over multiple rotation constraints. As these constraints are non-convex, this problem is generally considered challenging to solve globally. We show how to circumvent this difficulty through the use of Lagrangian duality. While such an approach is well-known it is normally not guaranteed to provide a tight relaxation. Based on spectral graph theory, we analytically prove that in many cases there is no duality gap unless the noise levels are severe. This allows us to obtain certifiably global solutions to a class of important non-convex problems in polynomial time. We also propose an efficient, scalable algorithm that outperforms general purpose numerical solvers and is able to handle the large problem instances commonly occurring in structure from motion settings. The potential of this proposed method is demonstrated on a number of different problems, consisting of both synthetic and real-world data.</p>},
  author       = {Eriksson, Anders and Olsson, Carl and Kahl, Fredrik and Chin, Tat Jun},
  booktitle    = {Proceedings - 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2018},
  isbn         = {9781538664209},
  language     = {eng},
  month        = {12},
  pages        = {127--135},
  publisher    = {IEEE Computer Society},
  title        = {Rotation Averaging and Strong Duality},
  url          = {http://dx.doi.org/10.1109/CVPR.2018.00021},
  doi          = {10.1109/CVPR.2018.00021},
  year         = {2018},
}