Survey of 8 UAV Set-Covering Algorithms for Terrain Photogrammetry
Open Access
- 16 July 2020
- journal article
- research article
- Published by MDPI AG in Remote Sensing
- Vol. 12 (14) , 2285
Abstract
Remote sensing with unmanned aerial vehicles (UAVs) facilitates photogrammetry for environmental and infrastructural monitoring. Models are created with less computational cost by reducing the number of photos required. Optimal camera locations for reducing the number of photos needed for structure-from-motion (SfM) are determined through eight mathematical set-covering algorithms as constrained by solve time. The algorithms examined are: traditional greedy, reverse greedy, carousel greedy (CG), linear programming, particle swarm optimization, simulated annealing, genetic, and ant colony optimization. Coverage and solve time are investigated for these algorithms. CG is the best method for choosing optimal camera locations as it balances number of photos required and time required to calculate camera positions as shown through an analysis similar to a Pareto Front. CG obtains a statistically significant 3.2 fewer cameras per modeled area than base greedy algorithm while requiring just one additional order of magnitude of solve time. For comparison, linear programming is capable of fewer cameras than base greedy but takes at least three orders of magnitude longer to solve. A grid independence study serves as a sensitivity analysis of the CG algorithms (iteration number) and (percentage to be recalculated) parameters that adjust traditional greedy heuristics, and a case study at the Rock Canyon collection dike in Provo, UT, USA, compares the results of all eight algorithms and the uniqueness (in terms of percentage comparisons based on location/angle metadata and qualitative visual comparison) of each selected set. Though this specific study uses SfM, the principles could apply to other instruments such as multi-spectral cameras or aerial LiDAR.
Keywords
Funding Information
- National Science Foundation (IIP-1650547)
This publication has 53 references indexed in Scilit:
- Automated 3D Reconstruction Using Optimized View-Planning Algorithms for Iterative Development of Structure-from-Motion ModelsRemote Sensing, 2020
- Sequential Earthquake Damage Assessment Incorporating Optimized sUAV Remote Sensing at Pescara del TrontoGeosciences, 2019
- Achieving Tiered Model Quality in 3D Structure from Motion Models Using a Multi-Scale View-Planning Algorithm for Automated Targeted InspectionSensors, 2019
- Unmanned Aerial Vehicles (UAVs): A Survey on Civil Applications and Key Research ChallengesIEEE Access, 2019
- Potential Benefits of Combining Anomaly Detection with View Planning for UAV Infrastructure ModelingRemote Sensing, 2017
- Comparison of SfM computer vision point clouds of a landslide derived from multiple small UAV platforms and sensors to a TLS-based modelJournal of Unmanned Vehicle Systems, 2016
- Unmanned Aerial Systems (UAS) for Construction Safety Applications2016
- Evolutionary View Planning for Optimized UAV Terrain Modeling in a Simulated EnvironmentRemote Sensing, 2015
- Survey of advances in guidance, navigation, and control of unmanned rotorcraft systemsJournal of Field Robotics, 2012
- Building Rome in a day2009