Abstract
This paper introduces a highly scalable, parallel Structure from Motion (SfM) system capable of reconstructing city-scale environments from over a million high-resolution images. By combining a novel overlapping camera clustering algorithm with a hybrid motion averaging framework, the system achieves state-of-the-art accuracy while drastically reducing the memory footprint required for massive datasets.
Introduction
Structure from Motion (SfM)—the process of estimating 3D structures from 2D image sequences—faces a massive "memory wall" when scaling to city-sized datasets. Standard pipelines often require more RAM than a single computer can provide. Previous strategies like skeletal graphs or exclusive clustering often discard significant connectivity, leading to jittery or inaccurate reconstructions. This work addresses the challenge of performing SfM in parallel without sacrificing the dense connectivity needed for high-quality results.
Methodology
The proposed system utilizes a three-stage pipeline designed for distributed computing:
- Interdependent Camera Clustering: Using a normalized-cut algorithm, the system creates clusters with significant overlap (completeness constraint). This ensures sufficient shared information to accurately stitch clusters processed in parallel.
- Hybrid SfM Formulation: The system performs robust Incremental SfM within each cluster for high-quality relative poses, followed by Global Motion Averaging to solve for all camera poses simultaneously across the entire dataset.
- Robust Translation Averaging: Camera positioning is formulated as a convex $\ell_1$ optimization problem, allowing simultaneous solving for positions and unknown cluster scales, enhancing resilience to outliers.
- Parallel Implementation: A hierarchical tree structure manages track generation and distributed bundle adjustment across a computer cluster.
Evaluation and Results
The system was evaluated on standard benchmarks, internet datasets (e.g., Roman Forum, Piccadilly), and four massive city-scale datasets.
- Unprecedented Scale: The system successfully reconstructed 1.21 million camera poses and 1.68 billion 3D points for "City-A".
- Superior Accuracy: On the Roman Forum dataset, the system achieved a median camera position error of 0.4 meters, outperforming other state-of-the-art global SfM pipelines.
- Memory Efficiency: For City-A, the system required only 34.6 GB of peak memory for track generation, compared to an estimated 2.9 TB for standard pipelines.
- Speed: Using a cluster of 10 computers, 138,000 images were reconstructed in less than 24 hours.
Key Insights
- Connectivity is King: Enforcing a "completeness ratio" ($\delta_c = 0.7$) during clustering maintains global consistency without exceeding memory limits.
- Hybrid Robustness: Combining local incremental SfM with global motion averaging mitigates both local matching errors and long-distance drift.
- Optimization: Using $\ell_1$ optimization for translation averaging provides superior robustness against noisy large-scale data compared to standard least-squares approaches.
Limitations and Future Work
While highly parallelized, the Global Motion Averaging step currently runs on a single machine. Although memory-efficient, this remains a potential bottleneck for datasets significantly larger than 1 million images. Future research will explore truly distributed versions of motion averaging.
Summary updated