Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging

Álvaro Parra, Shin-Fang Ch'ng, Tat-Jun Chin, Anders P. Eriksson, Ian D. Reid

Abstract

Rotation averaging is a fundamental problem in 3D computer vision, essential for Structure-from-Motion (SfM) and Simultaneous Localization and Mapping (SLAM). While Semidefinite Programming (SDP) relaxations offer global optimality, they are often computationally prohibitive for large-scale datasets due to quadratic complexity. This paper introduces Rotation Coordinate Descent (RCD), a novel algorithm that leverages "gauge freedom" to achieve global optimality with linear complexity per iteration. By maintaining valid rotations throughout the optimization, RCD enables the integration of local solvers (RCDL), resulting in significant speedups—up to 100x—over state-of-the-art methods like Shonan Averaging, particularly on dense SfM graphs.

Introduction

In 3D reconstruction, we often start with relative rotations between pairs of cameras. The rotation averaging problem seeks to find the absolute orientations of all cameras in a single global coordinate system. This is a non-convex optimization problem where traditional local solvers frequently converge to suboptimal local minima. Global optimality can be guaranteed using Semidefinite Programming (SDP) relaxations, but the previous gold standard, Block Coordinate Descent (BCD), requires maintaining a massive $3n \times 3n$ matrix, leading to $O(n^2)$ complexity that limits scalability as the number of cameras ($n$) grows into the thousands.

Proposed Method: Rotation Coordinate Descent (RCD)

The core innovation of RCD is the exploitation of gauge freedom. Since absolute rotations are relative to an arbitrary global frame, the full $3n \times 3n$ matrix used in prior SDP approaches is redundant. By fixing one camera as a reference, RCD directly maintains and updates $n$ valid $3 \times 3$ rotation matrices.

Linear Complexity and Global Optimality

RCD reduces the cost per iteration from $O(n^2)$ to $O(n)$ by updating only the "effective" variables. Despite this simplification, the authors provide a mathematical proof that RCD converges to the same globally optimal solution as the full SDP relaxation.

RCDL: Accelerating Convergence

Unlike BCD, which only reaches valid rotations at convergence, RCD maintains feasibility within the $SO(3)$ space at every step. This allows for the integration of standard local optimization routines, a hybrid approach called RCDL. RCDL can take massive "jumps" toward the global minimum, often converging in just a few epochs (passes through the data).

Convergence of RCD and RCDL showing objective reduction and pose evolution from initialization to local update.

Experimental Evaluation

The authors evaluated RCD across synthetic data, standard SLAM benchmarks (e.g., garage, sphere), and large-scale real-world SfM datasets (e.g., Alcatraz Tower, Spilled Blood Cathedral).

Key Results

  • Speed and Scalability: RCD demonstrates superior performance on dense graphs. On the San Marco dataset (1,498 cameras), RCD achieved a 68x speedup over Shonan Averaging. For the Spilled Blood Cathedral, it found the global optimum in 0.79 seconds, compared to 37 seconds for the previous state-of-the-art.
  • SfM vs. SLAM Performance: While methods like Shonan Averaging perform well on sparse SLAM chains, they struggle with the dense interconnections typical of SfM. RCD maintains high efficiency in both scenarios, as shown in the performance comparisons across varying camera counts.
Performance comparison of BCD, RCD, and Shonan Averaging (SA) across SfM and SLAM datasets of varying sizes ($n=100, 200, 1000$).

Discussion and Limitations

RCD represents a major advancement in balancing global guarantees with real-time performance. However, challenges remain:

  • Outlier Sensitivity: The current formulation uses squared chordal distance, which is not robust to outliers. Preprocessing is required to filter bad measurements.
  • Noise Thresholds: Global optimality via SDP relaxation holds under "mild noise." In extremely noisy environments, the "strong duality" property may fail, potentially leading to physically incorrect solutions.

Conclusion

Rotation Coordinate Descent (RCD) provides a faster path to global optimality in rotation averaging. By reducing complexity to $O(n)$ and enabling hybrid local-global optimization, it allows for the efficient reconstruction of large-scale 3D scenes without sacrificing mathematical rigor.

Summary updated

Abstract

Under mild conditions on the noise level of the measurements, rotation averaging satisfies strong duality, which enables global solutions to be obtained via semidefinite programming (SDP) relaxation. However, generic solvers for SDP are rather slow in practice, even on rotation averaging instances of moderate size, thus developing specialised algorithms is vital. In this paper, we present a fast algorithm that achieves global optimality called rotation coordinate descent (RCD). Unlike block coordinate descent (BCD) which solves SDP by updating the semidefinite matrix in a row-by-row fashion, RCD directly maintains and updates all valid rotations throughout the iterations. This obviates the need to store a large dense semidefinite matrix. We mathematically prove the convergence of our algorithm and empirically show its superior efficiency over state-of-the-art global methods on a variety of problem configurations. Maintaining valid rotations also facilitates incorporating local optimisation routines for further speed-ups. Moreover, our algorithm is simple to implement; see supplementary material for a demonstration program.
BibTeX
@inproceedings{parra2021rotation,
  author = {Álvaro Parra and Shin-Fang Ch'ng and Tat-Jun Chin and Anders P. Eriksson and Ian D. Reid},
  title = {{Rotation Coordinate Descent for Fast Globally Optimal Rotation Averaging}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2021},
  doi = {10.1109/cvpr46437.2021.00428},
}
Figure