Efficient Detection of Long Consistent Cycles and its Application to Distributed Synchronization

Shaohan Li, Yunpeng Shi, Gilad Lerman

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:

  1. 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.
  2. 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.
  3. 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

Abstract

Group synchronization plays a crucial role in global pipelines for Structure from Motion (SfM). Its formulation is nonconvex and it is faced with highly corrupted measurements. Cycle consistency has been effective in addressing these challenges. However, computationally efficient solutions are needed for cycles longer than three, especially in practical scenarios where 3-cycles are unavailable. To overcome this computational bottleneck, we propose an algorithm for group synchronization that leverages information from cycles of lengths ranging from three to six with a time complexity of order O(n3) (or O(n2.373) when using a faster matrix multiplication algorithm). We establish non-trivial theory for this and related methods that achieves competitive sample complexity, assuming the uniform corruption model. To advocate the practical need for our method, we consider distributed group synchronization, which requires at least 4-cycles, and we illustrate state-of-the-art performance by our method in this context.
BibTeX
@inproceedings{li2024efficient,
  author = {Shaohan Li and Yunpeng Shi and Gilad Lerman},
  title = {{Efficient Detection of Long Consistent Cycles and its Application to Distributed Synchronization}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2024},
}
Figure