Keywords
structure-from-motion, unmanned aerial vehicles, uav, remote sensing, set-covering problem, algorithms, greedy algorithm, carousel greedy algorithm, grid independence, photogrammetry, optimization
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.
Original Publication Citation
https://www.mdpi.com/2072-4292/12/14/2285/htm
BYU ScholarsArchive Citation
Hammond, Joshua; Vernon, Cory; Okeson, Trent; Barrett, Benjamin; Arce, Samuel; Newell, Valerie; Janson, Joseph; Franke, Kevin; and Hedengren, John, "Survey of 8 UAV Set-Covering Algorithms for Terrain Photogrammetry" (2020). Faculty Publications. 6181.
https://scholarsarchive.byu.edu/facpub/6181
Document Type
Peer-Reviewed Article
Publication Date
2020-07-16
Permanent URL
http://hdl.lib.byu.edu/1877/8910
Publisher
MDPI
Language
English
College
Ira A. Fulton College of Engineering
Department
Chemical Engineering
Copyright Status
Open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright Use Information
https://lib.byu.edu/about/copyright/