Towards Linear-Time Incremental Structure from Motion

TLDR

Incremental structure from motion is traditionally O(n⁴) in camera count, but recent improvements to bundle adjustment via preconditioned conjugate gradient suggest its speed may be revisited. The study introduces a novel bundle adjustment strategy that balances speed and accuracy. It achieves this by regularly re‑triangulating feature matches that initially fail to triangulate. Algorithm analysis and experiments show that incremental SfM can run in O(n) time on many major steps, achieving state‑of‑the‑art performance on large photo collections and video sequences, and the algorithm is available in VisualSFM.

Abstract

The time complexity of incremental structure from motion (SfM) is often known as O(n^4) with respect to the number of cameras. As bundle adjustment (BA) being significantly improved recently by preconditioned conjugate gradient (PCG), it is worth revisiting how fast incremental SfM is. We introduce a novel BA strategy that provides good balance between speed and accuracy. Through algorithm analysis and extensive experiments, we show that incremental SfM requires only O(n) time on many major steps including BA. Our method maintains high accuracy by regularly re-triangulating the feature matches that initially fail to triangulate. We test our algorithm on large photo collections and long video sequences with various settings, and show that our method offers state of the art performance for large-scale reconstructions. The presented algorithm is available as part of VisualSFM at http://homes.cs.washington.edu/~ccwu/vsfm/.