Abstract
Rotation synchronization is a fundamental problem in computer vision, particularly within Structure from Motion (SfM) pipelines. While cycle consistency is a standard tool for filtering corrupted relative rotations, traditional methods are often limited to 3-cycles (triangles) due to the exponential computational cost of searching for longer paths. This paper introduces LongSync, an algorithm that enables the use of cycles up to length 6 with $O(n^3)$ complexity—the same as triangle-based methods. By vectorizing cycle inconsistency calculations through matrix powers, LongSync provides a robust solution for distributed synchronization and sparse graph scenarios where 3-cycles are insufficient or absent.
Introduction
In the field of computer vision, Structure from Motion (SfM) aims to reconstruct 3D scenes from collections of 2D images. A pivotal step in this process is rotation synchronization: estimating the absolute orientation of cameras given a set of noisy and potentially corrupted relative rotations between camera pairs.
To identify and remove outlier data, researchers typically rely on the principle of cycle consistency. In a noise-free environment, the composition of relative rotations along any closed loop (cycle) in the camera graph should result in the identity matrix. While 3-cycles are computationally efficient to evaluate, they are not always available. In distributed SfM—where cameras are partitioned into clusters—or in grid-like structures such as those found in large-scale jigsaw puzzles, the graph may be sparse or bipartite, rendering 3-cycles rare or non-existent. Historically, utilizing longer cycles (lengths 4, 5, or 6) has been computationally prohibitive, as the number of cycles grows exponentially ($O(n^c)$) with the cycle length $c$.
Methodology: The LongSync Algorithm
LongSync addresses the computational barrier of long-cycle consistency through a scalable variant of the Cycle Edge Message Passing (CEMP) framework. The algorithm's efficiency stems from three primary innovations:
- Vectorization via Matrix Powers: Rather than explicitly enumerating every possible cycle, the authors demonstrate that cycle inconsistency measures can be computed using a sequence of matrix operations, including matrix multiplication and Hadamard products. This shift reduces the complexity from $O(n^c)$ to a manageable $O(n^3)$ for cycles up to length 6.
- Weighted Quadratic Averaging: By employing a quadratic average of cycle inconsistencies instead of a standard weighted average, the mathematical formulation allows the inconsistency measure to be expressed as a series of matrix power terms (e.g., $P^{c-1}$). This "unfolding" of the math is what enables the $O(n^3)$ vectorization.
- Chordal Distance Utilization: The algorithm utilizes the chordal distance on the Special Orthogonal group $SO(d)$. Because this distance is linear with respect to the rotation matrices, it further simplifies the vectorization process and maintains computational efficiency.
Theoretical and Practical Advantages
The "Long Cycle" Advantage
The authors provide theoretical proof that increasing the cycle length $c$ improves "sample complexity." Essentially, as the cycle length increases, the algorithm requires fewer clean edges to successfully recover the ground truth rotations. This moves the practical performance of synchronization closer to the absolute information-theoretic bounds.
Necessity in Bipartite Graphs
In distributed synchronization scenarios, the connections between different camera clusters often form a bipartite graph. Since bipartite graphs contain no odd-length cycles (and thus no 3-cycles), 4-cycles represent the minimum requirement for consistency checks. LongSync makes the use of these 4-cycles (and longer) practical for the first time in large-scale applications.
Experimental Results
The performance of LongSync was evaluated using both synthetic models and real-world benchmarks.
- Synthetic Evaluation: Testing under the Uniform Corruption Model (UCM) and the newly proposed Uniform Bipartite Corruption Model (UBCM) demonstrated that LongSync achieves near-perfect recovery in high-corruption scenarios where 3-cycle methods fail entirely.
- Real-World Benchmarks: On the PhotoTourism dataset—comprising 15 large-scale image sets of landmarks like Notre Dame and the Roman Forum—LongSync outperformed other distributed synchronization baselines in 13 out of 15 cases. Notably, in the Notre Dame dataset, it reduced mean error by over 28% compared to the previous state-of-the-art.
- Efficiency: Despite the added complexity of processing longer cycles, LongSync is highly optimized. It operates in less than 6% of the time required by leading non-distributed solvers (such as MPLS) while maintaining or exceeding their accuracy.
Conclusion and Future Work
LongSync represents a significant advancement in making long-cycle consistency a viable tool for large-scale synchronization. While the algorithm significantly narrows the gap between practical performance and theoretical limits, the authors note that a small gap remains. Future research will focus on automating heuristic preprocessing steps and exploring the application of long-cycle consistency in other domains, such as Cryo-Electron Microscopy (Cryo-EM) and solving massive jigsaw puzzles, where sparse graph structures are common.
Summary updated