A center-driven image set partition algorithm for efficient structure from motion

This paper proposes a novel center-driven image set partitioning method dedicated for efficient Structure from Motion (SfM) on unevenly distributed images. First, multiple base clusters are found at places with high image density. Instead of building a small initial model from two images, we build multiple initial base models from these base clusters. This promises that the scene is reconstructed from dense places to sparse areas, which can reduce error accumulation when images have weak overlap. Second, the whole image set is divided into several region clusters to decide which images should be reconstructed from the same base model. In this step, the base models are treated as centers and the affinity between an image with each of them is measured by the reconstruction path length. To enable faster speed, images in each region cluster are further divided into several sub-region clusters so that they could be added to the same base model simultaneously. Based on the above partitioning results, the partial 3D models are reconstructed in parallel and then merged. Experiments show that the proposed method achieves remarkable speedup and better completeness than state-of-the-art methods, without significant accuracy deterioration. (C) 2018 Elsevier Inc. All rights reserved.