Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/133077
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Rotation averaging with the chordal distance: global minimizers and strong duality |
Author: | Eriksson, A. Olsson, C. Kahl, F. Chin, T.J. |
Citation: | IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021; 43(1):256-268 |
Publisher: | Institute of Electrical and Electronics Engineers (IEEE) |
Issue Date: | 2021 |
ISSN: | 0162-8828 1939-3539 |
Statement of Responsibility: | Anders Eriksson, Carl Olsson, Fredrik Kahl, and Tat-Jun Chin |
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 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 by a large margin and compares favourably to current state-of-the-art. Further, our approach is able to handle the large problem instances commonly occurring in structure from motion settings and it is trivially parallelizable. Experiments are presented for a number of different instances of both synthetic and real-world data. |
Keywords: | Rotation averaging; structure from motion; lagrangian duality; graph laplacian; chordal distance |
Rights: | © 2019 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information. |
DOI: | 10.1109/TPAMI.2019.2930051 |
Grant ID: | http://purl.org/au-research/grants/arc/FT170100072 |
Published version: | http://dx.doi.org/10.1109/tpami.2019.2930051 |
Appears in Collections: | Electrical and Electronic Engineering publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.