Divide and conquer: A hierarchical approach to large-scale structure-from-motion

In this paper we present a novel pipeline for large-scale SfM. We first organise the images into a hierarchical tree built using agglomerative clustering. The SfM problem is then solved by reconstructing smaller image sets and merging them into a common frame of reference as we move up the tree in a bottom-up fashion. Such an approach drastically reduces the computational load for matching image pairs without sacrificing accuracy. It also makes the resulting sequence of bundle adjustment problems well-conditioned at all stages of reconstruction. We use motion averaging followed by global bundle adjustment for reconstruction of each individual cluster. Our 3D registration or alignment of partial reconstructions based on epipolar relationships is both robust and reliable and works well even when the available camera-point relationships are poorly conditioned. The overall result is a robust, accurate and efficient pipeline for large-scale SfM. We present extensive results that demonstrate these attributes of our pipeline on a number of large-scale, real-world datasets and compare with the state-of-the-art.