Submodular Trajectory Optimization for Aerial 3D Scanning

Mike Roberts1,2

Debadeepta Dey2

Anh Truong3

Sudipta Sinha2

Shital Shah2

Ashish Kapoor2

Pat Hanrahan1

Neel Joshi2

1Stanford University

2Microsoft Research

3Adobe Research

International Conference on Computer Vision (ICCV) 2017

Figure: 3D reconstruction results obtained using our algorithm for generating aerial 3D scanning trajectories, as compared to an overhead trajectory. Left column: Google Earth visualizations of the trajectories. Middle and right columns: results obtained by flying a drone along each trajectory, capturing images, and feeding the images to multi-view stereo software. Our trajectories lead to noticeably more detailed 3D reconstructions than overhead trajectories. In all our experiments, we control for the flight time, battery consumption, number of images, and quality settings used in the 3D reconstruction.

arXiv | Code (coming soon...) | Data (coming soon...)

Abstract: Drones equipped with cameras have become 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.

@inproceedings{roberts:2017,
    author       = {Mike Roberts AND Debadeepta Dey AND Anh Truong AND Sudipta Sinha AND
                    Shital Shah AND Ashish Kapoor AND Pat Hanrahan AND Neel Joshi},
    title     = {Submodular Trajectory Optimization for Aerial 3D Scanning},
    booktitle = {International Conference on Computer Vision (ICCV) 2017},
    year      = {2017}
}

Acknowledgements: We thank Jim Piavis and Ross Robinson for their expertise as our safety pilots; Don Gillett for granting us permission to scan the barn scene; 3D Robotics for granting us permission to scan the industrial scene; Weichao Qiu for his assistance with the UnrealCV Python library; Jane E and Abe Davis for proofreading the paper; and Okke Schrijvers for the helpful discussions. This work was supported by a generous grant from Google.