Parallel Structure From Motion for UAV Images via Weighted Connected Dominating Set

Incremental structure from motion (ISfM) has been widely used for unmanned aerial vehicle (UAV) image orientation. Its efficiency, however, decreases dramatically due to iterative bundle adjustment (BA). Although the divide-and-conquer strategy has been used for efficiency improvement, cluster merging becomes difficult or depends on seriously designed common image poses or 3-D points. This article proposes an algorithm to extract the global model for cluster merging and designs a parallel ISfM solution to achieve efficient and accurate image orientation. First, based on vocabulary tree retrieval, match pairs are selected to construct an undirected weighted match graph, whose edge weights are calculated by considering both the number and distribution of feature matches. Second, an algorithm termed weighted connected dominating set (WCDS) is designed to achieve the simplification of the match graph and build the global model, which incorporates the edge weight in the graph vertex selection and enables the successful reconstruction of the global model. Third, the match graph is simultaneously divided into compact and nonoverlapped clusters. After parallel reconstruction, cluster merging is conducted with the aid of the global model. Finally, using three UAV datasets that are captured by classical oblique and recent optimized views photogrammetry, the validation of the proposed solution is verified through comprehensive analysis and comparison. The experimental results demonstrate that the proposed parallel ISfM can achieve 17.4 times efficiency improvement and comparative orientation accuracy. In absolute BA, the geo-referencing accuracy is approximately 2.0 and 3.0 times the ground sampling distance (GSD) value in the horizontal and vertical directions, respectively. For parallel ISfM, the proposed solution is a more reliable alternative.