When is Rotations Averaging Hard?
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
- PDF / 2,210,884 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 24 Downloads / 240 Views
Washington College, Chestertown, MD, USA [email protected] 2 Google Inc., Mountain View, CA, USA 3 Cornell University, Ithaca, NY, USA {bindel,snavely}@cs.cornell.edu
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 L2 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.
1
Introduction
Rotations averaging is the problem of assigning a rotation matrix to every vertex in a graph, in a way that best respects given relative rotations on each edge. This problem has become a staple of recent global Structure from Motion (SfM) methods, where the vertices represent cameras and the rotation matrices are their orientations [1–4]. In many global SfM approaches, camera orientations and positions of many photographs are recovered by (1) estimating relative poses among pairs or triplets of cameras, (2) computing camera orientations via rotations averaging, and (3) computing camera positions from translation direction constraints. Despite the practical success of recent rotations averaging methods, they largely come without guarantees. Indeed, the cost functions in question are nonconvex. Both L1 and L2 formulations of rotations averaging can have local minima. Beyond these facts, little is known about the practical properties of rotation averaging problems—in particular, what makes a problem easy or hard? Electronic supplementary material The online version of this chapter (doi:10. 1007/978-3-319-46478-7 16) contains supplementary material, which is available to authorized users. c Springer International Publishing AG 2016 B. Leibe et al. (Eds.): ECCV 2016, Part VII, LNCS 9911, pp. 255–270, 2016. DOI: 10.1007/978-3-319-46478-7 16
256
K. Wilson et al.
Fig. 1. In Structure from Motion, each vertex in a rotations averaging problem represents a camera’s orientation. Edges are measurements of the relative rotation between two cameras. Some real rotations averaging problems have complicated graph structure, such as the Arts Quad problem pictured above [5].
An instance of the rotation averaging problem is a graph wi
Data Loading...
