Source-linked AI summary
Submodular Trajectory Optimization for Aerial 3D Scanning
Mike Roberts, Debadeepta Dey, Anh Truong, Sudipta Sinha, Shital Shah, Ashish Kapoor, Pat Hanrahan, Neel Joshi
TL;DR
Existing automatic flight planners may not use scene geometry, limiting their ability to meet multi-view stereo’s coverage and viewpoint needs. This paper plans trajectories from a coarse geometry estimate using a submodular coverage model that jointly accounts for reward and travel cost. Across real outdoor scenes and a simulator, it reports higher-quality reconstructions than baseline methods.
Problem
Existing automatic flight planners do not exploit all available scene information, while multi-view stereo needs thorough coverage and diverse viewing angles.
Source: §1 · pp. 1–2Method
The method uses a coarse geometry estimate and a submodular coverage model to plan trajectories that jointly account for non-additive coverage rewards and travel costs.
Source: §1 · p. 2Results
Takeaways & Limitations
Submodularity supports a computationally efficient trajectory planner that reasons jointly about coverage rewards and travel costs.
Source: §7 · p. 8Camera-orientation choices are globally coupled through the coverage function, so existing submodular orienteering algorithms that assume no such extra choices are not directly applicable.
Source: §5 · p. 5
Abstract
from arXiv · showhide
Drones equipped with cameras are emerging as a powerful tool for large-scale aerial 3D scanning, but existing automatic flight planners do not exploit all available information about the scene, and can therefore produce inaccurate and incomplete 3D models. We present an automatic method to generate drone trajectories, such that the imagery acquired during the flight will later produce a high-fidelity 3D model. Our method uses a coarse estimate of the scene geometry to plan camera trajectories that: (1) cover the scene as thoroughly as possible; (2) encourage observations of scene geometry from a diverse set of viewing angles; (3) avoid obstacles; and (4) respect a user-specified flight time budget. Our method relies on a mathematical model of scene coverage that exhibits an intuitive diminishing returns property known as submodularity. We leverage this property extensively to design a trajectory planning algorithm that reasons globally about the non-additive coverage reward obtained across a trajectory, jointly with the cost of traveling between views. We evaluate our method by using it to scan three large outdoor scenes, and we perform a quantitative evaluation using a photorealistic video game simulator.
1. Introduction
Aerial 3D scanning must meet multi-view stereo’s dense-coverage and viewpoint requirements within limited flight time, which existing planners may not satisfy. The paper plans geometry-aware, budget-constrained trajectories using a submodular coverage model and reports higher-quality reconstructions than strong baselines.
1. Introduction
- Multi-view stereo needs dense scene coverage and views from multiple viewpoints, at appropriate distance and angular separation, while consumer-drone battery life is only 10–15 minutes.Existing autonomous planners do not always satisfy these requirements.Source: §1 · p. 1
- Geometry-unaware lawnmower and orbit routes can oversample rooftops while undersampling facades, overhangs, and fine details, sacrificing reconstruction quality.Commercial tools generate these conservative trajectories while attempting to respect flight time.Source: §1 · pp. 1–2
- The method uses coarse scene geometry to maximize coverage under a travel budget, with a submodular model capturing globally coupled, diminishing-return rewards.The trajectory problem is formulated as submodular orienteering and transformed into an additive orienteering problem for optimization.Source: §1 · p. 2
- The method produced noticeably higher-quality reconstructions than strong baselines; Figure 1 shows more detail than overhead trajectories under controlled acquisition conditions.The comparison controls flight time, battery consumption, image count, and reconstruction quality settings.Source: Figure 1 · p. 1, §1 · p. 2
2. Related Work
Prior work addresses mapping, view selection, and path planning, but the paper distinguishes its approach by targeting multi-view stereo requirements and jointly optimizing view rewards and travel costs. It evaluates reconstruction performance directly.
2. Related Work
- Commercial scanning tools use conservative lawnmower or orbit routes, while this algorithm aims to cover the scene more thoroughly for higher-quality reconstructions.Related reconstruction and real-time mapping methods do not themselves generate drone trajectories.Source: §2 · p. 2
- Exploration and coverage strategies generally do not account explicitly for multi-view stereo’s diverse-view requirements or directly evaluate reconstruction quality on that task.The paper contrasts its direct multi-view stereo evaluation with these existing strategies.Source: §2 · p. 2
- Prior multi-view stereo planners select next-best views before routing between them, whereas this method jointly optimizes view selection and routing.The paper says this unified global optimization enables more rewarding trajectories and ultimately higher-quality reconstructions.Source: §2 · p. 2
- Active-vision work includes selecting sensor views and connecting them efficiently; Wang et al. use unified view-and-travel optimization, while this paper imposes a hard travel budget.The paper identifies the hard constraint as an important safety requirement for drone trajectories.Source: §2 · pp. 2–3
- Some multi-view stereo view-selection and scene-coverage methods do not model travel costs, while this method constrains the selected path’s travel cost.Source: §2 · p. 3
- Prior submodular coverage path planning shares a coverage-approximation technique, but this work adds multi-view stereo requirements and directly evaluates reconstruction performance.The related formulation is attributed to Heng et al..Source: §2 · p. 3
3. Technical Overview
The system first estimates scene geometry, then uses it to plan and fly a scanning route. Its coverage model rewards diverse viewing angles while the planner respects limited flight time.
3. Technical Overview
- An initial safe flight gathers images that a multi-view stereo pipeline uses to estimate coarse scene geometry and conservative free space.This explore phase supplies the information used for later planning.Source: §3 · p. 3
- Using the additional scene information, the exploit phase plans a trajectory to maximize reconstruction fidelity while respecting flight time, then captures images for detailed reconstruction.The acquired imagery is processed by the multi-view stereo pipeline.Source: §3 · p. 3
- The coverage model measures usefulness by the solid angle of viewing directions covered around surface points; nearby camera angles add diminishing returns.Coverage is summed across surface points, encouraging diverse observations of scene geometry.Source: Figure 2 · p. 3
4. Coverage Model for Camera Trajectories
The coverage model approximates a trajectory’s usefulness by measuring weighted coverage of the scene’s sampled surface geometry. It encodes view distance and angle preferences, and its diminishing-returns structure supports optimization.
Formal Definition
- The model scores a trajectory by integrating non-negative weights over the regions it covers on oriented hemispheres sampled from approximate scene geometry.The trajectory and surface points are uniformly sampled; each visible camera pose covers an angular region on a surface-point hemisphere.Source: §4 · pp. 3–4
- For each surface point, camera poses contribute disks to its hemisphere, and the covered region is the union of those disks.A camera that cannot see the surface point contributes a zero-radius disk, and disk extent is truncated at the hemisphere’s equator.Source: §4 · p. 4
- Disk radii decay with camera distance and hemisphere weights decay away from the pole, favoring close-up and fronto-parallel views.These design choices encode multi-view stereo acquisition practices in the coverage model.Source: §4 · p. 4
Submodularity
- The model is submodular, so each added camera provides diminishing marginal coverage as more cameras are included.The authors note that the model approximates true reconstruction usefulness, but is easy to evaluate, requires only coarse geometry, and can be efficiently maximized.Source: §4 · pp. 3–4
5. Generating Optimal Camera Trajectories
The trajectory planner turns scene coverage into a graph optimization problem with globally coupled rewards and camera orientations. It uses submodularity to reduce the problem to additive orienteering, then solves that formulation approximately.
5. Generating Optimal Camera Trajectories
- The planner searches a camera-pose graph for a high-reward closed path under a travel budget, but node rewards are non-additive and depend on the full set of visited poses.The graph is built from sampled camera positions and look-at vectors, with positions pruned to known free space; the path starts and ends at a designated root.Source: §5 · pp. 4–5
- Because camera orientations are globally coupled through coverage, existing submodular-orienteering methods do not directly apply; the authors first optimize orientations without path constraints, then construct an additive approximation.The resulting additive problem is solved as a standard orienteering problem.Source: §5 · p. 5
5.1. Solving for Optimal Camera Orientations
- A greedy algorithm selects camera orientations by marginal coverage while enforcing at most one orientation per graph node, achieving a 50% global-optimality guarantee.The guarantee relies on coverage being monotone; submodularity can reduce computation from multiple hours to a couple of minutes for the paper’s problems.Source: §5.1 · p. 5
5.2. Additive Approximation of Coverage
- The additive approximation assigns each pose its marginal reward in a permutation, is exact for permutation prefixes, and underestimates coverage for other subsets.The permutation reuses the greedy ordering, placing poses with greater marginal reward first.Source: §5.2 · p. 6
5.3. Orienteering as an Integer Linear Program
- The additive orienteering problem is encoded as a compact integer linear program whose constraints enforce valid paths, then passed to a commercial solver.With a five-minute time limit, Gurobi returns a feasible solution and optimality gap; the authors report gaps typically below 10%.Source: §5.3 · p. 6
6. Evaluation
The evaluation compares trajectories on three real outdoor scenes and a photorealistic synthetic scene, with controlled flight and reconstruction settings. The method produces higher-quality reconstructions and, on the synthetic scene, earns more submodular reward than next-best-view planning at the same travel budget.
Real-World Reconstruction Performance
- The real-world evaluation scans a barn, an office building, and an industrial site, comparing the proposed method with overhead and random trajectories.The flights use a 960-meter budget and generate roughly 275 images at 2 meters per second, unless otherwise noted.Source: §6 · p. 6
- The three-scene real-world experiment used an early implementation with diagonal graph edges, which were later excluded to help the integer-programming formulation scale.The implementation difference applies to this experiment; the passage does not claim a resulting performance effect.Source: §6 · p. 6
- Real-world reconstructions contain noticeably fewer visual artifacts than overhead and random baselines across two scenes.Flight time, battery consumption, image count, and reconstruction quality settings are controlled across experiments.Source: §6 · p. 6, Figure 4 · p. 7
Reconstruction Performance on a Synthetic Scene
- The synthetic evaluation uses a photorealistic simulator to compare overhead, random, next-best-view, and proposed trajectories against known geometry and appearance.Geometric quality is assessed against a ground-truth point cloud, and visual quality against ground-truth RGB renderings.Source: §6 · pp. 7–8
- The synthetic-scene method outperforms baseline trajectories geometrically and visually, including in accuracy, completeness, and mean per-pixel visual error.All Table 1 columns are lower-is-better; the supplied passage does not provide the individual values.Source: §6 · p. 7, Table 1 · p. 8
Submodular Orienteering Performance
- At 960 meters, the proposed algorithm obtains 20% more reward than next-best-view planning, while remaining more computationally expensive.The p-SPIEL Orienteering algorithm failed to consistently find a solution; where it did, computation took over four hours.Source: Figure 6 · p. 8
7. Conclusions
The paper concludes that its submodular coverage model supports computationally efficient trajectory planning that jointly accounts for coverage rewards and travel costs. Evaluations across three real scenes and a photorealistic simulator found higher-quality reconstructions than baseline methods, geometrically and visually.
7. Conclusions
- The method combines a submodular coverage model with trajectory planning that jointly reasons about coverage reward and travel cost.The authors report evaluations on three real-world scenes and one photorealistic simulator scene, with higher-quality geometric and visual reconstructions than baselines.Source: §7 · p. 8
- The authors envision trajectory optimization and geometric reasoning supporting future individual and cooperative drone scanning at larger scales.These are proposed future possibilities, not evaluated outcomes.Source: §7 · p. 8