Rotation averaging
How hard is it to combine pictures to understand scene geometry?
Summary
Many millions of tourists visit Rome each day, and many of them take pictures. How hard is it to reconstruct the three-dimensional geometry of famous Roman landmarks from these pictures? A key subproblem in such a reconstruction is figuring out how the camera was oriented in space when each picture was taken. This is the problem of rotation averaging: given estimates of the relative rotations between the cameras for many pairs (or triplets) of images, how can we assign camera rotations for each image in a way that is most consistent with the data? In our work, we explore the local convexity of such problems by making novel use of techniques from spectral graph theory.
Papers
@inproceedings{2016-rotations,
author = {Wilson, Kyle and Bindel, David and Snavely, Noah},
booktitle = {Proceedings of ECCV 2016},
title = {When is Rotations Averaging Hard?},
month = oct,
year = {2016}
}
Abstract:
Rotations averaging has become a key subproblem in global Structure from Motion methods. Several solvers exist, but they do not have guarantees of correctness. They can produce high-quality results, but also sometimes fail. Our understanding of what makes rotations averaging problems easy or hard is still very limited. To investigate the difficulty of rotations averaging, we perform a local convexity analysis under an $L_2$ cost function. Although a previous result has shown that in general, this problem is locally convex almost nowhere, we show how this negative conclusion can be reversed by considering the gauge ambiguity.
Our theoretical analysis reveals the factors that determine local convexity—noise and graph structure—as well as how they interact, which we describe by a particular Laplacian matrix. Our results are useful for predicting the difficulty of problems, and we demonstrate this on practical datasets. Our work forms the basis of a deeper understanding of the key properties of rotations averaging problems, and we discuss how it can inform the design of future solvers for this important problem.