# Parallel Structure from Motion for UAV Images via Weighted Connected Dominating Set

arXiv: https://arxiv.org/abs/2206.11499 · HTML: https://mlsanity.com/paper/2206.11499/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 58 references that are in the map.
- First posted on arXiv 23 Jun 2022.

## Builds on (most cited first, 6 of 6)

- [Image Matching across Wide Baselines: From Paper to Practice](https://mlsanity.com/paper/2003.01587/) (2020)
- [Graph-Based Parallel Large Scale Structure from Motion](https://mlsanity.com/paper/1912.10659/) (2019)
- [Domain-Size Pooling in Local Descriptors: DSP-SIFT](https://mlsanity.com/paper/1412.8556/) (2014)
- [Hierarchical structure-and-motion recovery from uncalibrated images](https://mlsanity.com/paper/1506.00395/) (2015)
- [ENFT: Efficient Non-Consecutive Feature Tracking for Robust Structure-from-Motion](https://mlsanity.com/paper/1510.08012/) (2015)
- [Efficient Structure from Motion for Oblique UAV Images Based on Maximal Spanning Tree Expansions](https://mlsanity.com/paper/1705.03212/) (2017)

## Built on by (most cited first, 11 of 11)

- [3D reconstruction from spherical images: A review of techniques, applications, and prospects](https://mlsanity.com/paper/2302.04495/) (2023)
- [3D Reconstruction of Spherical Images based on Incremental Structure from Motion](https://mlsanity.com/paper/2306.12770/) (2023)
- [Efficient Match Pair Retrieval for Large-scale UAV Images via Graph Indexed Global Descriptor](https://mlsanity.com/paper/2307.04520/) (2023)
- [CVD-SfM: A Cross-View Deep Front-end Structure-from-Motion System for Sparse Localization in Multi-Altitude Scenes](https://mlsanity.com/paper/2508.01936/) (2025)
- [Incremental Rotation Averaging Revisited](https://mlsanity.com/paper/2309.16924/) (2023)
- [DeepAAT: Deep Automated Aerial Triangulation for Fast UAV-based Mapping](https://mlsanity.com/paper/2402.01134/) (2024)
- [Style Alignment based Dynamic Observation Method for UAV-View Geo-localization](https://mlsanity.com/paper/2407.02832/) (2024)
- [Efficient feature matching for UAV images based on compact GPU data scheduling](https://mlsanity.com/paper/2505.22089/) (2025)
- [UAVPairs: A Challenging Benchmark for Match Pair Retrieval of Large-scale UAV Images](https://mlsanity.com/paper/2505.22098/) (2025)
- [Accelerating SfM-based Pose Estimation with Dominating Set](https://mlsanity.com/paper/2506.03667/) (2025)
- [3D Gaussian Splatting for Fine-grained Urban Scene Reconstruction via Semantic-guided Density Control and Loss Design](https://mlsanity.com/paper/2610.16292/) (2026)

## Abstract (arXiv)

Incremental Structure from Motion (ISfM) has been widely used for UAV image orientation. Its efficiency, however, decreases dramatically due to the sequential constraint. Although the divide-and-conquer strategy has been utilized for efficiency improvement, cluster merging becomes difficult or depends on seriously designed overlap structures. This paper proposes an algorithm to extract the global model for cluster merging and designs a parallel SfM solution to achieve efficient and accurate UAV 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 node selection and enables the successful reconstruction of the global model. Third, the match graph is simultaneously divided into compact and non-overlapped clusters. After the parallel reconstruction, cluster merging is conducted with the aid of common 3D points between the global and cluster models. Finally, by 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 SfM 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 GSD (Ground Sampling Distance) value in the horizontal and vertical directions, respectively. For parallel SfM, the proposed solution is a more reliable alternative.