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).
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.
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