Towards Linear-Time Incremental Structure from Motion

Authors

Changchang Wu

Year

2013

Conference Paper

Algorithm

Linear-Time Incremental SfM

Source

International Conference on 3D Vision

Identifiers

DOI 10.1109/3DV.2013.25

Abstract¶

The time complexity of incremental structure from motion (SfM) is often known as O(n4) 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/.

Summary¶

Reworks incremental SfM to scale much closer to linearly by combining preemptive matching, a geometric bundle-adjustment schedule, preconditioned conjugate-gradient solving, and periodic retriangulation. The paper is one of the practical foundations behind large-scale incremental SfM systems such as VisualSFM.