Ke E Xie

Hao Yang

Shengqiu Huang

Dani Lischinski

Marc Christie

Kai Xu

Minglun Gong

Daniel Cohen-Or

Hui Huang

Creating and Chaining Camera Moves for Quadrotor Videography

Keywords: Quadrotor videography, trajectory planning, camera control, scene navigation, visual exploration

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Fig. 1. Given several landmarks (red areas on the satellite image) and a pair of start and end views (brown camera icons), we generate a suitable camera move (in yellow) for capturing each landmark, and optimally connect them into a continuous and smooth path using transition trajectories (in blue).

Capturing aerial videos with a quadrotor-mounted camera is a challenging creative task, as it requires the simultaneous control of the quadrotor's motion and the mounted camera's orientation. Letting the drone follow a pre-planned trajectory is a much more appealing option, and recent research has proposed a number of tools designed to automate the generation of feasible camera motion plans; however, these tools typically require the user to specify and edit the camera path, for example by providing a complete and ordered sequence of key viewpoints.

In this paper, we propose a higher level tool designed to enable even novice users to easily capture compelling aerial videos of largescale outdoor scenes. Using a coarse 2.5D model of a scene, the user is only expected to specify starting and ending viewpoints and designate a set of landmarks, with or without a particular order. Our system automatically generates a diverse set of candidate local camera moves for observing each landmark, which are collision-free, smooth, and adapted to the shape of the landmark. These moves are guided by a landmark-centric view quality field, which combines visual interest and frame composition. An optimal global camera trajectory is then constructed that chains together a sequence of local camera moves, by choosing one move for each landmark and connecting them with suitable transition trajectories. This task is formulated and solved as an instance of the Set Traveling Salesman Problem.

CCS Concepts: • Computing methodologies → Computer graphics; Interest point and salient region detections; Graphics systems and interfaces;

INTRODUCTION

As quadrotor unmanned aerial vehicle (UAV) technology advances and the prices of drones go down, their use is becoming increasingly ubiquitous for a wide variety of tasks. In particular, quadrotors are increasingly used by professional, as well as amateur, photographers and cinematographers for capturing aerial imagery and videos.

However, manual capture of high quality aerial video footage with drones is highly challenging, even for experienced cinematographers. In addition to controlling the trajectory of the drone, one must simultaneously control the camera's degrees of freedom. The common practice requires two persons to capture a drone video, one to pilot the drone, and another to control the camera at the same time [START_REF] Diaz | Lights, drone[END_REF]]. Furthermore, limited battery life and quickly changing lighting conditions make it difficult to rehearse the flight, or repeat the capture, if mistakes were made during the first attempt.

Recently, researchers have addressed problems such as designing smooth drone trajectories that interpolate userspecified keyframes [START_REF] Joubert | An interactive tool for designing quadrotor camera shots[END_REF], and ensuring that planned trajectories are dynamically feasible [START_REF] Roberts | Generating Dynamically Feasible Trajectories for Quadrotor Cameras[END_REF]. In this work, we also consider drone trajectory design. We, however, introduce a higher level design tool, intended to enable even novice users to plan a complete and smooth camera trajectory for capturing the desired visual content, and based on fairly minimal user input.

More specifically, the goal of this work is to automate the drone videography process for complex large-scale outdoor scenes consisting of several landmarks of interest. The input to our system is a coarse 2.5D model of a scene, a set of designated landmarks, with or without a particular order in which they should be visited, and the starting and ending camera positions. The model should also include any potential obstacles or areas that must be avoided. From this input, our approach automatically generates a continuous drone trajectory, which is collision-free, visits all of the landmarks, and satisfies several quality criteria. An example of such a trajectory is shown in Fig. 1, and more in Section 6.

Our approach starts by automatically generating a diverse set of candidate local camera moves for observing each landmark, which effectively sample the huge search space of all possible trajectories around the landmark. The camera moves are guaranteed to avoid collisions with the landmarks and any of the other specified obstacles. The trajectories are smooth, adapted to the overall shape of the landmark, and are guided by a novel landmark-centric quality view field, which accounts for visual interest and frame composition.

Next, we produce a single continuous trajectory that visits all of the landmarks, by selecting a single camera move for each landmark, and chaining them together using smooth transition trajectories (shown in blue in Fig. 1). These transitions are also designed with collision avoidance, smoothness, and view quality in mind. The task of selecting an optimal ordered sequence of alternating transition and local trajectories is formulated as an instance of the Set Traveling Salesman Problem, a generalized version of the Traveling Salesman Problem, where the set of cities is partitioned into several clusters, and the salesman must follow a minimal cost path that visits exactly one city from each cluster.

We tested our planning tool on five large-scale outdoor scenes. To evaluate the quality, we have also conducted a user study, where for each of four scenes, three different versions of aerial videos produced in three different ways are compared. The analysis drawn from 160 samples (80 participants with 2 repetitions) clearly shows the superiority of our technique over manually created trajectories, as well as trajectories created with a classical GPS waypoint tool.

RELATED WORK 2.1 Virtual Camera Control

The control of a camera in a virtual 3D environment is strongly guided by the type of tasks to perform together with the target application, and has been addressed by a wide variety of techniques; see [START_REF] Christie | Camera control in computer graphics: models, techniques and applications[END_REF][START_REF] Christie | Camera control in computer graphics[END_REF]. Below, we review a few techniques most closely related to our approach.

The automated computation of single viewpoints has first been addressed by [START_REF] Blinn | Where am I? What am I looking at[END_REF], who proposed an efficient iterative technique to compute the position and orientation of a camera from the specification of on-screen properties. The problem has then been expressed in a more general framework, where visual properties in the image space (position and orientation of targets) are translated into constraints or costs applied on the degrees of freedom of the camera, and solved through a range of optimization techniques [START_REF] William | A Model for Constraint-based Camera Planning[END_REF][START_REF] Steven | Intelligent camera control in a virtual environment[END_REF][START_REF] Ranon | Improving the Efficiency of Viewpoint Composition[END_REF]. Aspiring to generate more cinematographic viewpoints and trajectories, researchers have been formalizing elements of the filmic language into properties to be enforced on the cameras. [START_REF] He | The virtual cinematographer: a paradigm for automatic real-time camera control and directing[END_REF] first presented a set of heuristics to pose virtual cameras based on visual composition principles. The use of different camera representations such as the Toric Space simplifies the expression and solving of such problems [START_REF] Lino | Intuitive and efficient camera control with the toric space[END_REF].

Computing sequences of viewpoints (camera trajectories) imposes new challenges, such as collision and visibility over time, but also smoothness along trajectories. When a priori knowledge of the 3D environment is available, techniques rely on the construction of environment abstractions such as roadmaps, and then compute paths through roadmap traversal techniques and trajectory smoothing; see [START_REF] Salomon | Interactive navigation in complex environments using path planning[END_REF] or [START_REF] Nieuwenhuisen | Motion Planning for Camera Movements[END_REF]. Several visibilityaware camera planning techniques have been proposed. [START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF] attempted to enforce visibility of targets along the path, by precomputing visibility between pairs of targets and computing a camera path using an A * planner, which is then smoothed. [START_REF] Lino | A Real-time Cinematography System for Interactive 3D Environments[END_REF] perform a real-time potential visibility set computation.

In dynamically changing environments, local motion strategies for camera control have been explored, based on incremental hierarchical solving [START_REF] Halper | A Camera Engine for Computer Games: Managing the Trade-Off Between Constraint Satisfaction and Frame Coherence[END_REF], local roadmaps [START_REF] Tsai | Real-Time Camera Planning for Navigation in Virtual Environments[END_REF], or cinematographic behavior strategies [START_REF] Galvane | Steering behaviors for autonomous cameras[END_REF].

For visualization of animated volume data, [START_REF] Hsu | A Multi-Criteria Approach to Camera Motion Design for Volume Data Animation[END_REF] proposed a dynamic camera motion planning mechanism that incorporates multiple quality criteria into a single system.

Scene Navigation and Exploration

Scene navigation approaches address the problem of generating a guided tour of a 3D environment, generally constrained by visiting a set of given landmarks. By contrast, scene exploration provides means for the user to interactively explore 3D environments, while avoiding non-relevant areas or viewpoints. Scene exploration has largely been addressed in the context of interactive virtual museum tours [START_REF] Gran Andújar | Way-Finder: Guided Tours Through Complex Walkthrough Models[END_REF][START_REF] Chittaro | Guiding Visitors of Web3D Worlds Through Automatically Generated Tours[END_REF][START_REF] Steven | Intelligent camera control in a virtual environment[END_REF]. Scene navigation and exploration techniques are founded on the visual interest of the 3D environment, a characteristic that may be predefined (e.g., a preset of good views of landmarks), or computed automatically through visual interest metrics. [START_REF] Vázquez | Viewpoint Selection using Viewpoint Entropy[END_REF] introduced viewpoint entropy in an attempt to quantify the amount of information that a viewpoint conveys about a 3D scene, and use this concept to automate the computation of good views. In scene navigation, similar visual metrics can be exploited to automate the computation of camera paths, an approach followed by [START_REF] Sokolov | Virtual world explorations by using topological and semantic knowledge[END_REF]. Given a set of good viewpoints, the authors generate a path that interpolates the viewpoints by solving a Traveling Salesmen Problem (TSP) where the cities to traverse are viewpoints and the cost is a combination of the Euclidean distance between the viewpoints and the visual quality along the path. The approach has been extended by considering a semantic distance metric between the good views, whose goal is to avoid transitions between unrelated landmarks. [START_REF] Serin | Automatic path generation for terrain navigation[END_REF] applied a similar approach for the specific task of navigation on a 3D terrain. TSPs have also been used in scene exploration to design interactive guided tours [START_REF] Niklas Elmqvist | Tour generation for exploration of 3D virtual environments[END_REF]].

While our contribution also relies on the use of TSP techniques to construct a camera path, the problem we address is more complex: first a large collection of suitable camera moves around landmarks is generated, which attempt to satisfy a number of safety and quality requirements, and then a global path is designed, which selects the best camera move for each landmark and connects them together.

Aerial Cinematography and Trajectory Planning

Mounting cameras on UAVs has triggered the development of techniques to assist users in the complex task of simultaneously controlling the drone and the camera. Applications range from automated surveillance tasks to area coverage [START_REF] Fan | Optimal path planning and control of quadrotor unmanned aerial vehicle for area coverage[END_REF]], scanning of unknown environments [START_REF] Dunkley | Visual-Inertial Navigation for a Camera-Equipped 25g Nano-Quadrotor[END_REF], capture of aesthetic aerial shots of buildings [START_REF] Joubert | An interactive tool for designing quadrotor camera shots[END_REF], or human subjects performing an activity outdoors [START_REF] Joubert | Towards a Drone Cinematographer: Guiding Quadrotor Cameras using Visual Composition Principles[END_REF]. All approaches compute camera paths that must be physically realizable by the UAV.

Assisting the design of camera trajectories for aesthetic aerial videography has received increasing attention [START_REF] Gebhardt | Airways: Optimization-Based Planning of Quadrotor Trajectories According to High-Level User Goals[END_REF][START_REF] Joubert | An interactive tool for designing quadrotor camera shots[END_REF][START_REF] Roberts | Generating Dynamically Feasible Trajectories for Quadrotor Cameras[END_REF]. The process consists of prototyping a trajectory in a 3D simulator before executing it automatically in the real environment. The virtual trajectory is designed by creating an ordered collection of manually positioned look-from/look-at viewpoints (keyframes). [START_REF] Joubert | An interactive tool for designing quadrotor camera shots[END_REF] also required the user to specify the timing of the keyframes. A specific 𝐶 4 continuous trajectory, represented as a 7th degree piecewise polynomial, is created between the keyframes. This representation was found to produce the smoothest and most reasonably bounded control signals for quadrotors [START_REF] Joubert | Towards a Drone Cinematographer: Guiding Quadrotor Cameras using Visual Composition Principles[END_REF][START_REF] Joubert | An interactive tool for designing quadrotor camera shots[END_REF]. 7th degree polynomials are also used in the robotics literature [START_REF] Mellinger | Minimum snap trajectory generation and control for quadrotors[END_REF][START_REF] Richter | Polynomial Trajectory Planning for Aggressive Quadrotor Flight in Dense Indoor Environments[END_REF]. The feasibility of this trajectory is then analyzed and reported to the user, so he/she can iteratively alter the keyframe timings. More recent work addresses the feasibility issue in an automated way [START_REF] Roberts | Generating Dynamically Feasible Trajectories for Quadrotor Cameras[END_REF] using an optimized time-warping of the trajectory.

Similarly to [START_REF] Joubert | An interactive tool for designing quadrotor camera shots[END_REF], [START_REF] Gebhardt | Airways: Optimization-Based Planning of Quadrotor Trajectories According to High-Level User Goals[END_REF] proposed a design tool where a camera path can be drawn and edited in a virtual environment and then optimized to ensure its feasibility. Given the multiple constraints (such as avoiding collisions), the optimization process does not guarantee to respect the user inputs: a trade-off is necessary between user inputs and conflicting constraints.

To account for more cinematographic properties on quadrotors, [START_REF] Fleureau | Generic Drone Control Platform for Autonomous Capture of Cinema Scenes[END_REF] presented a tool to automatically maintain visual on-screen properties (orientation, composition) on moving targets, and automatically compute transitions between viewpoints with moving targets. The approach relies on the Toric Space representation [START_REF] Lino | Intuitive and efficient camera control with the toric space[END_REF] to express cinematographic properties (distance to target, angle on target, screen positions of targets) and perform interpolations in the Toric Space to maintain or transition between visual properties. [START_REF] Galvane | Automated Cinematography with Unmanned Aerial Vehicles[END_REF] introduce an interactive tool that allows a user to produce well composed shots of moving actors in real time, by only specifying high level cinematographic commands; however, this tool assumes a fully captured indoor environment. [START_REF] Nägeli | Real-time Planning for Automated Multiview Drone Cinematography[END_REF] described a high-level drone trajectory planning tool aimed at dynamic and cluttered environments. We target a different scenario of large-scale outdoor scenes containing static landmarks of interest.

While our approach shares some ideas with [START_REF] Gebhardt | Airways: Optimization-Based Planning of Quadrotor Trajectories According to High-Level User Goals[END_REF][START_REF] Joubert | An interactive tool for designing quadrotor camera shots[END_REF], we propose a higher level and more automated design tool. Our tool requires users to provide neither viewpoints (except starting and ending), nor timings. Only the set of landmarks of interest needs to be specified, and our tool automatically proposes and selects among camera moves typical of aerial video sequences. This makes our tool particularly well suited for novice users. [START_REF] Olov Andersson | Deep Learning Quadcopter Control via Risk-Aware Active Learning[END_REF] proposed an active learning approach for quadrotor collision avoidance in the presence of non-cooperative moving obstacles. In this work, we assume that obstacles are static and compute a collision-free optimal trajectory offline.

OVERVIEW

The goal of our tool is to enable even novice users to easily capture smooth and visually compelling aerial videos covering multiple landmarks in a complex large-scale outdoor environment. We assume that a rough 2.5D or 3D scene model that includes all the landmarks of interest is available. This model should also include any potential obstacles that must be avoided. Fig. 2 shows an overview of our method, which is comprised of two main phases: creating local (landmarkcentric) camera moves (Section 4), and chaining them together into a single continuous trajectory (Section 5).

In the first phase, we compute, for each landmark, a set of camera trajectory candidates. The guiding principles for creating such local camera moves are driven by requirements identified by the media production industry [START_REF] Messina | Multidrone media production requirements[END_REF]] and include: i) avoiding any collisions with the landmark or any other obstacles in the scene; ii) adapting to the overall shape of the landmark; iii) maximizing the visual interest of video frames captured along the trajectory; and iv) maximizing smoothness and minimizing rotations along the trajectory. To meet these goals, we construct a volumetric landmark-centric view quality field in the obstacle-free space around the target landmark (Section 4.1). Guided by this field, a number of possible local shape-aware camera moves are generated that maximize the view quality and trajectory smoothness (Section 4.2).

In the second phase, our goal is to select a single local camera move for each landmark and generate a continuous and smooth trajectory that chains together the selected local moves. To this end, we compute a set of possible transition trajectories that connect together endpoints of local moves from different landmarks (Section 5.1). Each local move and each transition trajectory has an associated cost, with smaller cost corresponding to higher quality. The task of selecting a maximal quality ordered sequence of alternating transition and local trajectories is formulated as an instance of the Set Traveling Salesman Problem (STSP), where the local moves are nodes in the same set, while the transitions are edges connecting nodes from different sets (Section 5.2). A near-optimal solution for the STSP is then obtained using an existing algorithm [START_REF] Helsgaun | Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm[END_REF]]. Examples of the resulting global drone camera trajectories are shown in Figs. 1 and2.

CREATING LOCAL CAMERA MOVES

In this section, we describe the construction of local camera moves around a given landmark. Our challenge here is to produce safe (collision-free) trajectories, which could be considered good from a cinematographic standpoint, based only on a coarse model of the scene. Our key ideas consist of: (i) assessing the visual interest of a given view on a landmark by computing a saliency field on the landmark surface, which may then be rendered from any viewpoint; (ii) using a weight map based on well known photographic composition principles to weigh the visual interest map for a given view, yielding a landmark-centric view quality field; (iii) reducing the search space of possible trajectories around each landmark to a manageable size; and (iv) proposing a strategy for generating a small number of diverse promising camera move candidates.

Landmark-Centric View Quality Field

No-fly zone. When planning drone trajectories, safety is our first priority. To avoid the drone colliding into landmark structures or other potential obstacles under inaccurate G-PS readings, we generate a no-fly zone for each indicated structure in the scene. Under the assumption that each such structure 𝑎 is represented using its 2D footprint polygon 𝑃𝑎 and its height ℎ𝑎, the no-fly zone is generated by first computing the Minkowski sum in 2D between 𝑃𝑎 and a disk with a radius of 𝑟𝑠 (20 meters by default). The resulting dilated 2D contour is then extruded into a 3D volume with a height of ℎ𝑎 + 𝑟𝑠. The drone trajectory is prohibited from entering any of the no-fly zones in the scene (Fig. 3), while the volume outside of these no-fly zones is considered safe for flying.

Landmark viewing space. When generating a local trajectory that focuses on a given landmark 𝑚, it does not make sense to place the drone too far away from 𝑚. Hence, a maximum viewing distance is computed based on the dimensions of the landmark 𝑚 and the camera's field of view, such that the landmark occupies no less than 2/3 of the frame, when viewed from the maximum viewing distance. The volume within the maximum viewing distance while excluding all no-fly zones is referred as the landmark viewing space 𝑆(𝑚).

To find a variety of good viewpoints within the viewing space, we discretize 𝑆(𝑚) into cubic cells (voxels) and evaluate the view quality at each voxel center. To simplify the task, we assign a default viewing direction for each voxel center 𝑣. That is, so long as 𝑣 is higher than the geometric centroid of landmark 𝑚 (referred to as 𝐶𝑚), the view direction is set to point at 𝐶𝑚. Otherwise, the view direction is set to point horizontally towards the ground plane projection of 𝐶𝑚, since most drone cameras cannot be tilted upward.

Salient features.

Based on the rough model for landmark 𝑚, we now predict the quality of the view captured from the center of each voxel 𝑣 under the default view direction. This yields a view quality field, denoted as 𝑄𝑚, which fills the viewing space 𝑆(𝑚). For each voxel center 𝑣 ∈ 𝑆(𝑚), the view quality 𝑄𝑚(𝑣) measures the landmark's shape-aware visual interest based on its visually important features (salient features). That is, we favor those views from which more salient features of the landmark's shape are visible. The salient features include the landmark's silhouettes, sharp edges of the landmark shape's surface, as well as the medial region of the shape's top surface(s), which we refer to as the skeletal region. The reason for including the latter is that for large area landmarks, such as a stadium or a harbor, observing the landmark from around its perimeter may not be as effective as flying above the landmark's area, which affords better views of the central region of the landmark.

The silhouette can be directly extracted from the landmark's 2D footprint and sharp vertical edges can be detected based on the angle between the footprint edges, or the dihedral angle between faces, if the landmark's 3D mesh is given. The skeletal region captures the medial region of the top area (flat field or rooftop) of a landmark. One could simply compute the medial axis of the top face polygon. However, due to the noise-prone nature of medial axis, we instead opt to erode the top polygon(s). The resulting eroded region approximates the skeleton of the original polygon.

The silhouette edges, sharp edges, and skeletal regions are assigned with a saliency value of 1, inducing a saliency field across the landmark's shape via a Gaussian decay mapping; see e.g., Fig. 4.

View quality. To compute the view quality at a given view point 𝑣, we render each landmark's shape using the intrinsic and extrinsic parameters of the drone camera, with each point colored according to its saliency value, as shown in Fig. 4. This results in a visual interest map, 𝐼𝑚(𝑣), for each view point 𝑣.

To achieve an aesthetically pleasing composition, we encourage interesting content to appear in the central region of the frame or to follow the well-known Rule of Thirds in photography, which suggests dividing an image into nine parts by equally spaced horizontal and vertical gridlines, and placing important elements along these lines or their intersections. To this end, we define a composition weight map, 𝐼 𝜔 , representing the importance of the central region and the vertical and horizontal gridlines, as shown in Fig. 5 (top). The final view quality score is then computed as the dot product of the visual interest and the composition weight maps:

𝑄𝑚(𝑣) = 𝐼𝑚(𝑣) • 𝐼 𝜔 , (1)
e.g., as the sum of the values in the bottom right image in Fig. 5.

Field-Guided Local Camera Moves

Guided by the landmark-centric view quality field, our goal now is to generate a few promising local camera moves passing through the viewing space 𝑆(𝑚). Since it is infeasible to enumerate and rank all of the possible trajectories through 𝑆(𝑚), we apply a number of a priori constraints from the literature [START_REF] Messina | Multidrone media production requirements[END_REF] to define a more manageable search space. First, given that the camera moves are intended to explore the landmark, we require that each trajectory should be sufficiently long and feature a significant change either in the altitude or the angle from which the landmark is viewed. Second, view quality along the trajectory should be high. Third, the trajectories should adapt to the shape

(0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) (0, 6) (1, 0) (1, 1)
(1, 2)

(1, 3)

(1, 4)

(1, 5)

(1, 6)

(2, 0)

(2, 1)

(2, 2)

(2, 3)

(2, 4)

(2, 5)

(2, 6) of the landmark, while being smooth and avoiding sharp or sudden turns. Finally, a diverse set of moves satisfying the constraints above should be considered.

Viewing regions, cells, and key views. Taking the above considerations into account, we divide the viewing space 𝑆(𝑚) into several viewing regions defined by radial sectors around the landmark, and an additional region above the landmark. Each of these regions is further split into vertically stacked view cells, and a single locally best key view is selected inside each view cell; see Fig. 6(a).

To ensure that the landmark is observed from a substantial range of views, we only consider smooth trajectories between pairs of key views, which traverse no less than a prescribed minimal number of view cells along the way. For each trajectory in this reduced set, we compute a cost which accounts for the view quality along the trajectory, compatibility with the landmark's shape, and the amount of camera view changes. Finally, we classify all the trajectories into five categories, based on how many regions they traverse. Trajectories traversing a small number of regions are mostly vertical, thereby covering a variety of viewing altitudes, while those traversing more regions are more horizontal, covering a wider variety of radial views. From each category we select the trajectory with the highest score as a candidate local camera move to be considered by the trajectory chaining stage (Section 5).

More specifically, we divide 𝑆(𝑚) into S + 1 viewing regions: S radial sectors around the landmark, and one region above it. The radial regions are further divided into L vertically stacked slices, forming L view cells per radial view region. The vertical stacking starts from the lowest flying altitude of the drone, ℎmin = 𝑟𝑠 by default, and the height of each layer is set by default to max{ℎmin, (ℎ𝑚 + 𝑟𝑠)/L}, where ℎ𝑚 is the height of the landmark 𝑚. Two more layers of the same height are then added onto the top above the landmark, forming the top view region, which is divided into 2S view cells, as shown in Fig. 6. In practice, we found that S = 4 radial sectors split into L = 5 slices suffice for generating a sufficiently diverse set of moves. Thus, we have at most 28 view cells (up to 7 layers times 4 sectors) arranged in 5 viewing regions around each landmark. This grouping is visualized using different colors in Fig. 6(b). Within each view cell, we select a single locally best key view, while avoiding choosing two key views which are too close to each other. This is achieved using a greedy algorithm, which first picks the viewpoint with the highest quality score across all cells. Then all candidate viewpoints within 𝑟𝑠 radius of selected viewpoints are eliminated, before the next best viewpoint is selected for another cell. Fig. 6(a) shows the candidate key views selected within surrounding viewing space of a given landmark.

Trajectory generation. Based on the key views computed in the previous stage, we generate candidate camera moves around the landmark. Considering each key view as a starting point, we generate all of the trajectories that traverse at least four cells before reaching an ending key view. Thus, we avoid considering short trajectories, and all of the considered trajectories traverse a significant range of altitudes, or angles around the landmark, or both. Fig. 6(b) shows all the possible ending cells for a trajectory starting at the bottom left cell (indicated with a blue dot).

Given a pair of starting and ending camera key views, we generate a smooth trajectory represented by a 5th degree B-spline curve, which goes from the starting pose to the ending pose, through 4 intermediate poses. While previous works [START_REF] Joubert | Towards a Drone Cinematographer: Guiding Quadrotor Cameras using Visual Composition Principles[END_REF][START_REF] Joubert | An interactive tool for designing quadrotor camera shots[END_REF] advocated the use of 7th degree splines in order to generate smooth control signals for quadrotors, we chose to use 5th degree splines, since we use the manufacturer's waypoint SDK to control the drone, rather than generating the control signals directly ourselves. This is explained in more detail in Section 6.

Each camera pose is specified using the tilt angle 𝜑 and the heading angle 𝜓 with respect to the landmark's centroid, as well as the distance of the camera from the landmark's no-fly zone. The angles and the distances of the intermediate poses are obtained by linearly interpolating those of the starting and ending camera poses (Fig. 7(a)), and a 5th degree B-spline curve is fit to the resulting sequence of six camera poses. The camera's view direction is also linearly interpolated. Since the heading may be interpolated in two different ways (clockwise and counter-clockwise), each pair of starting and ending poses gives rise to two possible camera trajectories, as shown in Figs. 7(b-c).

Each camera trajectory generated as described above is adapted to the shape of the landmark, since the intermediate poses are obtained by interpolating the distances to the landmark's no-fly zone. Nevertheless, this alone cannot guarantee that the trajectory does not penetrate the no-fly zone of the landmark or those of other obstacles in the scene. Thus, for each generated trajectory, we verify that it is indeed collisionfree, and discard it otherwise. Only collision-free trajectories are considered from this point onward.

Trajectory cost. Given a trajectory 𝑇𝑠,𝑒 from viewpoint 𝑠 to 𝑒, we define its associated cost 𝐸 local (𝑇𝑠,𝑒) as a sum of three terms:

𝐸 local (𝑇𝑠,𝑒) = 𝐸 quality + 𝐸axis + 𝐸rot (2)
The first term 𝐸 quality defines the cost based on the average quality of views sampled along 𝑇𝑠,𝑒:

𝐸 quality = 1 - 1 |𝒱𝑠,𝑒| ∑ 𝑣∈𝒱𝑠,𝑒 𝑄𝑚(𝑣), (3)
where |𝒱𝑠,𝑒| is the cardinality of the set of sample views along trajectory 𝑇𝑠,𝑒 and 𝑄𝑚(𝑣) is the view quality field value at 𝑣. We have also considered computing the cumulative view quality along the trajectory, rather than using the average view quality, however, we found that cumulative quality tended to result in somewhat more boring and redundant trajectories.

The second term measures how well the trajectory is aligned with the dominant axis of the landmark:

𝐸axis = 1 - |(𝑝𝑠 -𝑝𝑒) • 𝐷𝑚| max(‖𝑝𝑠 -𝑝𝑒‖ 2 , ‖𝐷𝑚‖ 2 ) , (4)
where 𝑝𝑠 and 𝑝𝑒 are the trajectory's starting and ending positions, and 𝐷𝑚 is the dominant principle direction of landmark 𝑚.

The third term 𝐸rot penalizes the rate of change in the camera view direction, as it travels from 𝑠 to 𝑒 along the trajectory 𝑇𝑠,𝑒:

𝐸rot = 1 𝛾(𝑇𝑠,𝑒) (1 -(𝑞𝑠 • 𝑞𝑒)), (5)
where 𝑞𝑠 and 𝑞𝑒 are unit view direction vectors at 𝑠 and 𝑡, respectively, and 𝛾(𝑇𝑠,𝑒) denotes the arc length of the trajectory.

We classify all trajectories into at most S + 1 categories, based on the number of viewing regions they crossed. Then for each category, we pick the trajectory with the smallest score in Eq. ( 2) as a local camera move candidate. In other words, for each landmark, the final output of this stage is the top 𝐾 ≤ S + 1 camera moves that sample a diverse set of trajectories through the landmark's safe viewing space. As mentioned earlier, in practice 𝐾 ≤ 5; see e.g., Fig. 2(top).

CHAINING CAMERA MOVES

Having established a set of top-𝐾 candidate local camera moves 𝒯 𝑚 = {𝑇 𝑚 𝑗 } 𝐾 𝑗=1 for each landmark 𝑚, our next task is to compute a set of transition trajectories connecting pairs of local trajectories of two given landmarks. An optimal trajectory for the entire flyby is then generated by chaining together selected local and transition trajectories in alternating order, so as to maximize the total quality (i.e., minimize the cost) of the resulting trajectory.

Constructing Transition Trajectories

A good transition trajectory 𝑇 𝑚𝑚 ′ 𝑗𝑗 ′ that connects two local camera moves, 𝑇 𝑚 𝑗 for the source landmark 𝑚 and 𝑇 𝑚 ′ 𝑗 ′ for the destination landmark 𝑚 ′ , should satisfy several requirements. It should be collision-free and efficient (i.e., short), saving time and battery power. To better convey the overall structure of the scene, we prefer to have either the source or the target landmark to be visible during most of the transition. Finally, as with local camera moves, we would like the camera motion to be smooth, avoiding fast camera rotations and unnecessary turning. Below we describe how we formalize these requirements.

Safety and efficiency.

As with local camera moves, we require each transition trajectory to be collision-free. To this end, we construct a visibility graph between the starting and ending points of the transition and the no-fly zone surfaces of the landmarks and the obstacles in the scene. Over this graph, we compute the shortest path between the starting and ending points using a classic algorithm proposed in [START_REF] Alt | Visibility graphs and obstacleavoiding shortest paths[END_REF]. The two local moves for landmark 𝑚 and 𝑚 ′ together with this shortest path in-between are smoothed to form one transition trajectory, which is obstacle-avoiding.

Transition trajectory cost. Similarly to local trajectories, each transition trajectory is also assigned an associated cost 𝐸trans, defined as a sum of three terms: The view quality term 𝐸 quality differs from the local move case in that it takes into account both the start landmark 𝑚, and the destination landmark 𝑚 ′ . Specifically, we for each viewpoint 𝑣 along the trajectory a joint view quality:

𝐸trans(𝑇 𝑚𝑚 ′ 𝑗𝑗 ′ ) = 𝐸 quality + 𝐸rot + 𝐸turn. ( 6
𝑄 𝑚𝑚 ′ (𝑣) = 𝑤𝑚𝑄𝑚(𝑣) + 𝑤 𝑚 ′ 𝑄 𝑚 ′ (𝑣), (7)
where

𝑤𝑚 = 𝑒 - 𝑑 2 (𝑣,𝑚) 𝜎𝑑 2 (𝑚,𝑚 ′ ) and 𝑤 𝑚 ′ = 𝑒 - 𝑑 2 (𝑣,𝑚 ′ )
𝜎 ′ 𝑑 2 (𝑚,𝑚 ′ ) are weights used to balance the influence of the two landmarks. Here 𝑑 is the Euclidean distance between a viewpoint and a landmark's center. We set 𝜎 = 0.05 and 𝜎 = 0.3, thereby biasing the quality score to be influenced more by the destination landmark.

The 𝐸 quality term of a transition trajectory is then defined as the average of the joint view quality along the trajectory:

𝐸 quality = 1 - 1 |𝒱 𝑚,𝑚 ′ | ∑ 𝑣∈𝒱 𝑚,𝑚 ′ 𝑄 𝑚𝑚 ′ (𝑣), ( 8
)
where |𝒱 𝑚,𝑚 ′ | is the cardinality of the set of sample views along the trajectory.

The second term is identical to the rotation speed penalty term that we use for local moves in Eq. ( 5).

The third term, 𝐸turn, is introduced in order to discourage zig-zag trajectories. This term penalizes the amount of turning when transitioning from one local trajectory to another. As an extremely simple measure of the amount of turning we Start End Fig. 9. Top: each pair of local trajectories may be connected using four different transition trajectories. Bottom: The local trajectories for each landmark define a cluster of nodes in the graph. Given the start (big blue dot) and end (big purple dot) views, as well as a landmark visiting order (optional), the final global optimal path shown in green is computed via solving the STSP, which visits exactly one node in each cluster.

examine the angles of a coarse polyline approximation of the transition. Specifically, let d𝑚, d𝑚𝑡, d 𝑡𝑚 ′ and d 𝑚 ′ denote the vectors of a polyline connecting the midpoints and endpoints of the starting, transition, and ending trajectories, as shown in Fig. 8. The term 𝐸turn is then defined as:

𝐸turn = 1 4 (2 -(d𝑚 • d𝑚𝑡) -(d 𝑡𝑚 ′ • d 𝑚 ′ )). (9)
As illustrated in Fig. 8, this term discourages the first pair of segments (d𝑚, d𝑚𝑡) from having opposing directions, and similarly for the second pair (d 𝑡𝑚 ′ , d 𝑚 ′ ).

Global Trajectory Planning

At this point we have several local camera move candidates around each landmark, and a collection of transition trajectories connecting different pairs of local moves. Given a starting and an ending camera position, our goal is to produce a single trajectory which includes one local move for each landmark, in an optimal order, with the appropriate transition trajectories between each pair of moves. We solve this difficult combinatorial optimization problem by formulating it as a generalized version of the Traveling Salesman Problem (TSP), also known as the Set TSP (STSP).

Given a graph with several disjoint subsets (clusters) of nodes, as well as a set of edges for each pair of adjacent node clusters, the goal of STSP is to find a minimal cost (i.e., maximal quality) tour, which visits each cluster exactly once. The standard TSP may be viewed as a special case of STSP, with only one node per cluster. This implies that the STSP problem is also NP-hard.

In our case, each landmark is to be visited once, and therefore the local moves around a single landmark form a single cluster of nodes in the graph. More specifically, each local camera move contributes to two nodes in the cluster, since its trajectory may be traversed in two directions. The cost of a node is given by 𝐸 local (𝑇𝑠,𝑒) in Eq. ( 2), computed along the corresponding local candidate trajectory.

The transition trajectories 𝑇 𝑚𝑚 ′ 𝑗𝑗 ′ that connect the end of a local trajectory 𝑇 𝑚 𝑗 of landmark 𝑚 to the beginning of a local trajectory 𝑇 𝑚 ′ 𝑗 ′ of landmark 𝑚 ′ , correspond to edges connecting nodes from two different clusters, one cluster containing the local moves around landmark 𝑚 and another containing the local moves around landmark 𝑚 ′ ; see an illustration in Fig. 9. The cost of an edge is defined by 𝐸trans(𝑇 𝑚𝑚 ′ 𝑗𝑗 ′ ) in Eq. (6), evaluated along the corresponding transition trajectory.

Each transition trajectory corresponds to one directed edge if the visiting order of landmarks is given by the user, otherwise to two directed edges in the graph, each with a different cost ( 6), since it is non-symmetric. Therefore, the graph contains at most 2𝐾𝑀 +2 nodes, where each of the 𝑀 landmarks has 2𝐾 nodes representing the endpoints of its 𝐾 local trajectories. Two additional nodes are used to represent the starting and ending point of the drone's flight. The trajectories connecting these points to each of the local moves can be computed and evaluated similarly to the transition trajectories, as described in Section 5.2. The number of edges is capped at (2𝐾) 2 (𝑀 -1) + 4𝐾 when the visiting order is specified by the user, and (2𝐾𝑀 ) 2 + 4𝑀 𝐾 when the order is unknown.

In summary, each local move defines a node in the graph, whose cost is given by Eq. ( 2) and each transition defines an edge between different node clusters, whose cost is given by Eq. ( 6). A minimal cost path in this graph corresponds to an alternating sequence of transition trajectories and local moves, whose quality is maximal. Such a path is approximately found by solving the STSP problem, using the software package developed by [START_REF] Helsgaun | Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm[END_REF].

RESULTS AND EVALUATION 6.1 Drone System

We use the DJI Phantom 4 Pro, a portable yet powerful drone, to capture our aerial videos. The drone's flying movements consist of forward, backward, left or right along a horizontal plane, increasing or decreasing its altitude, and changing its heading clockwise or counterclockwise (Fig. 10 i.e., pitch angle, may be controlled in the range of [-90 ∘ , 0 ∘ ]; see Fig. 10(right)).

Our current implementation uses the DJIWaypointMission SDK in order to program the drone and the camera to follow the trajectory generated by our method. With this SDK it is possible to specify a sequence of up to 99 waypoints (physical locations to which the drone will fly). The desired camera heading and tilt may be specified for each waypoint. The drone then travels from one waypoint to the next at a preset speed, adjusting altitude, heading, and camera tilt as it advances. Thus, given a trajectory to follow, we place up to 99 samples along the trajectory. The overall speed at which the trajectory is executed is therefore controlled by the DJI software. The locations, camera headings and tilts at these sample points are computed and used to set waypoints. Effectively, this means that the drone follows a roughly piecewise linear approximation of our smooth planned trajectory.

Furthermore, the accuracy and the smoothness of the actual camera motion also depends on the accuracy of the drone's GPS. While our results demonstrate that the resulting aerial videos are reasonably smooth, in the future we plan to implement and use our own lower level drone control program that would be able to follow a planned trajectory in a more precise manner. The tool we designed also proposes a virtual preview of the flight sequence by using the smoothed computed trajectory. The speed of the preview is set to the autoFlightSpeed value of the DJI SDK.

Aerial Videos

Let us start by re-iterating that even a seemingly simple camera move around a single landmark can be difficult to execute when piloting the drone using manual controls. For example, Fig. 11 shows a simple task of viewing around a building. An experienced drone operator was not able to pilot the drone in a smooth and accurate manner along a desirable trajectory, even after several attempts, the best of which is included in the supplementary video. In contrast, our tool Fig. 11. Given a pair of starting and ending views (brown camera icons) looking at a building, a spiral-like smooth camera move can be easily interpolated using our method illustrated in Fig. 7. successfully produced a smooth spiral-like trajectory by using interpolation in the safe viewing space.

We further tested our trajectory design tool on five largescale outdoor scenes; see Figs. 1,2,12,13,and 14,respectively. As shown, the test scenes contain landmarks of different shapes and sizes. More detailed statistics about these five tests are summarized in Table 1.

In addition to a fully auto planning, our algorithm can easily incorporate the user's preference. For example, as shown in Fig. 15, if a user indicated a mandatory key view that he/she wants to include in the resulting flyby, we add it into our candidate set of key views and select the best five (by default) local camera moves that pass through it. The global optimal trajectory generated accordingly will then contain the views that users prefer to see.

The resulting captured aerial video sequences are included in the supplementary materials, sped up by a factor of ×4 or ×8. Even with the accelerated playback, the camera motion is quite smooth, and most of the transitions between landmarks appear natural.

It takes our current implementation roughly 5-10 minutes to generate each final global optimal trajectory. As may be seen from Table 1, almost all of the computation time is spent on the computation of the view quality fields, a process that can be performed once during the pre-processing and re-used for multiple local and global trajectory construction.

User Study

User evaluations are conducted to measure the quality of the videos generated by our tool in comparison with i) videos created by an experienced drone pilot, and ii) videos created through the DJI GS Pro design tool1 .

We considered four different locations (Sea World, University, City Bay, Sunny Beach). For each location a number of landmarks were identified; see Table 1. Landmarks were communicated to our experienced drone pilots whose task was to fly the drone to "highlight the landmarks and to perform good transitions between the landmarks". Each drone pilot had a direct visual feedback from the camera, using a tablet connected to the DJI GO APP 2 . For each location, the drone pilot shot multiple takes and proposed his preferred one for the user study. Resulting videos represent the Manual condition. Two different but both experienced pilots created the videos, either working alone or together. This landmark information was also given to our experienced drone pilots who used the DJI GS Pro iPad application to create a virtual trajectory by designing a sequence of waypoints on a 3D map (tap and waypoint flight mode) and then flying along them automatically. The resulting videos represent the DGS condition. Finally, we used these landmarks to generate videos with our tool, referred to as the Auto condition. The videos for the three conditions were shot in different weather and lighting conditions, which may have affected the perception of viewers. To perform such recordings with very similar color and lighting conditions remains challenging. It is important to note that for each question, there were multiple 2 https://www.dji.com/goapp scenes compared, therefore the lighting conditions may have influenced both our method as well as the others.

Our hypotheses are: the videos created by our tool are more pleasing to watch than the others (H1), provide a clearer overview of the landmarks than the others (H2), follow a more reasonable route than the others (H3), provide better transitions between landmarks (H4), and create smoother drone trajectories (H5).

To evaluate these hypotheses, we ran multiple side-by-side video comparisons rather than individual ratings [START_REF] Yannakakis | Rating vs. Preference: a comparative study of self-reporting[END_REF]. Each side-by-side comparison consisted in watching two videos of the same location generated by different flying methods and then answering 5 questions on a 5-point Likert scale. A 2D view of the scene was displayed above the videos with the landmarks highlighted in red. Users had full control over the videos (start, pause, stop and navigate in time). A total of 80 participants were recruited (age varies from under 20 to over 40, with majority fall into the range of 20-30). There is a total of 12 videos (4 locations and 3 methods per location). Each participant watched 6 side-by-side video comparisons:

• two versions of Auto vs. Manual, one version per location • two versions of Auto vs. DGS, one version per location • two versions of Manual vs. DGS, one version per location Each video is 1-2mins in time, and the total experiment time for a user was around 25mins. Each user answered a total of 30 questions.

In these experiments, we emit the hypothesis that the results are not influenced by the locations and therefore aggregated the results over different locations. Running the comparisons on two versions ensured repeatability. While we were not interested in the results of Manual vs. DGS, we ran these comparisons to ensure each condition was viewed exactly 4 times by each user. The left-to-right ordering of videos was determined randomly. Order of comparisons was shuffled between participants. For one given condition, the size of the statistical sample is 160 (80 participants with 2 repetitions).

The questions were: (Q1) the left video was more pleasing to watch than the right video on a 5 point Likert scale ranging from "completely agree" to "completely disagree", displaying "neutral" in the middle; (Q2) the left video provided a clearer overview of the landmarks than the right one; (Q3) the left video follows a more reasonable route than the right one; (Q4) the transitions between the landmarks are more pleasing on the left video and (Q5) the trajectory of the drone was smoother in the left video.

Fig. 16 displays the results of our user evaluation for questions Q1 to Q5, in comparing our Auto approach v.s. the Manual approach (left chart), and our Auto approach vs. the DGS approach (right chart). Given that we are performing side by side comparisons, we relied on Wilcoxon signed rank tests. A post-hoc Bonferroni correction was applied with 𝑛 = 3 (the number of pairwise comparisons for the 3 conditions). The applied correction value is therefore 𝑝 = 0.013. On question Q1, the hypothesis that our video is preferred over the Manual version is ensured (Wilcoxon signed rank test with 𝑝 = 0.0127). On the same question Q1 when comparing with DGS, the null hypothesis could not be rejected (Wilcoxon signed rank test with 𝑝 = 0.0281) however being above the non-corrected threshold value (𝑝 = 0.05). For H2 (providing a better overview), the null hypothesis can be rejected both when comparing Auto v.s. Manual (𝑝 = 0.0088), and Auto v.s. DGS (𝑝 = 0.0101). For H3 (following a more reasonable route), the null hypothesis can also be rejected (Auto v.s. Manual with 𝑝 = 0.0071, Auto v.s. DGS with 𝑝 = 0.0092). For H4 (providing better transitions), the conclusions are the same (Auto v.s. Manual with 𝑝 = 0.0040, Auto v.s. DGS with 𝑝 = 0.0031), as well as for H5 (creating smoother drone trajectories) with Auto v.s. Manual with 𝑝 = 0.0001, Auto v.s. DGS with 𝑝 = 0.0113). We also ensured that the location does not influence the results of the users. A Wilcoxon rank sum test shows that the hypothesis of a difference does not hold on all questions (𝑝 = 0.01052).

In addition to these statistical results, the experienced drone pilots (1.5 years experience each) mentioned during discussions that the design of the drone trajectories in the Manual condition was a complex task to perform due to the combination of multiple objectives: avoiding collision, maintaining visibility on the drone, maintaining drone velocity, and framing the landmarks while ensuring a smooth trajectory. Smoothness in the trajectory and camera angle was the most difficult task over such long flights, and many takes were required. In opposition, the DJI GS Pro application simplified the process, however, some iterations between designing the path in the tool and flying the drone were required to adjust camera angles around landmarks. One experienced drone pilot commented on the results to our Auto approach by mentioning "Some generated moves are quite impressive and well respect the shapes of landmarks", highlighting the benefits of our solution.

CONCLUSION AND FUTURE WORK

We have introduced a new high level drone trajectory design tool, which generates a smooth trajectory for capturing a continuous flyby video of a collection of nearby landmarks. The tool takes as input a rough 2.5D models for the landmarks to be visited and additional obstacles that the drone should avoid.

Our method uses landmark-centric cylindrical coordinates to produce a set of local candidate moves that are smooth, collision-free, and adapted to the shape of each landmark. Global combinatorial optimization based on a generalized TSP solver is then used to produce a single continuous flyby trajectory by chaining together a sequence of selected local camera moves, one for each landmark.

While our results indicate that our method can greatly assist users in capturing aerial videos, there are a number of promising directions for future work. First of all, our current approach follows cinematographic composition guidelines by encouraging visually interesting features appear in the center of the frame or along the one-third lines. However, it does not take into account the lighting conditions and the relative positions between foreground and background objects. To film a landmark under a desired composition or from a desired orientation with respect to the lighting at the time, users could insert mandatory key views, but no effort is made to maintain these lighting or composition conditions along the generated trajectory. Future work should develop metrics for assessing lighting condition and quality of frame composition for intermediate views along the generated trajectories. Such metrics should be taken into account by the optimization process in order to yield aerial videos of higher cinematographic quality.

Another promising direction is to perform a study on the camera moves used by professional aerial videographers, and compile a diverse collection of parameterized interesting camera moves. Armed with an arsenal of such moves, given a specific landmark with a set of potential key-views, as well as other constraints, local trajectory candidates could be generated by optimizing the parameters so as to best fit the shape of the landmark and the constraints. Such an approach would make it even easier for inexperienced users to generate high-quality professional looking aerial videos.

Fig. 2 .

 2 Fig. 2. A 2.5D model of a large-scale scene with landmarks highlighted in red. Top: several candidate moves generated for each of the four landmarks. Bottom: a continuous drone trajectory generated by chaining together the most suitable local trajectories (in yellow) using smooth transition trajectories (in blue).

Fig. 3 .

 3 Fig. 3. No-fly zone generation. Top left: based on the 2D contours of landmarks (red) and obstacles (gray) provided as input, we dilate each contour curve (top right) to account for map or GPS inaccuracies. Each dilated contour is extruded based on the height of the corresponding structure to form the no-fly zones (transparent red in bottom figure).

Fig. 4 .

 4 Fig. 4. Visualization of saliency features of the landmarks from Fig. 3. Darker shades indicate lower saliency.

Fig. 5 .

 5 Fig. 5. Estimating the view quality of a given frame based on a rough model of the landmark. Top: a weight map is generated that assigns higher weights based on proximity to the center and the Rule of Thirds lines. Bottom: the saliency scores assigned to the landmark's 3D surfaces (shown in red) are projected to the camera view and multiplied by the weight map.

Fig. 6 .

 6 Fig. 6. (a) The viewing space is partitioned into multiple stacks of pie-shaped cells defined using cylindrical coordinates with origin at the centroid of the landmark footprint. A single candidate key view is selected for each cell and shown with a camera icon. (b) A 2D table arrangement of the view cells with rows corresponding to layers and columns to radial sectors. Different colors indicate the grouping of cells into five regions. A candidate local trajectory that starts from the bottom left cell must traverse at least four cells before reaching its ending point. Thus, it must end in one of the cells surrounded by the red frame, also illustrated with red camera icons in (a).

Fig. 7 .

 7 Fig. 7. Trajectory interpolation. (a) Given a pair of starting (in blue) and ending (in green) camera poses, we compute four intermediate poses in order to fit a 5th degree B-spline curve. The intermediate poses are defined by linearly interpolating the tilt angle 𝜑 to the landmark centroid, the heading 𝜓 to the landmark centroid, and the shortest distance to the landmark's no-fly zone surface. Since the heading may be interpolated in two different ways (clockwise and counter-clockwise), two possible outcomes of camera pose (b) and view direction (c) interpolation are shown.

Fig. 8 .

 8 Fig.8. Estimation the amount of turning for transition trajectories (blue). The overall trajectory is approximated by a coarse four-segment polyline. The opposing directions in the first and the second pair of line segments in the bottom indicate a significant amount of turning, corresponding to an undesirable zig-zag trajectory.

  (left)). It is equipped with a 4K/60fps 20 megapixel camera, stabilized by a 3-axis (pitch, roll, yaw) mechanical gimbal. The camera tilt, a DJI drone camera, the controllable heading range (left) is [-180 ∘ , 180 ∘ ] and the tilt range (right) is [-90 ∘ , 0 ∘ ].

Fig. 12 .

 12 Fig. 12. City Bay: this flyby has three landmarks (highlighted in red) of very different shapes. Please see the supplementary video.

Fig. 15 .

 15 Fig.15. User can also specify a mandatory key view that he/she wants to include in the flyby, e.g., here indicated by the pink camera icon. He/She can also change the starting and/or ending view accordingly, as shown by the rightmost brown camera icon. This will result in a must-choose local camera move and thus alter the whole global optimal trajectory. Compare with the fully auto one shown in Fig.14, and the corresponding video has been submitted as supplementary material.

Fig. 14 .

 14 Fig. 14. Sea World: this flyby has five landmarks (highlighted in red), where four of them are very close to each other. Please see the supplementary video.

( a )

 a Fig. 16. Boxplot visualizations of the user evaluation comparing (a) Auto vs. Manual videos, and (b) Auto vs. DGS videos. On the scale, 0 corresponds to a neutral answer, -2 corresponds to completely disagree and +2 corresponds to completely agree on questions Q1 to Q5. Blue dashes represent minimum and maximum values answered, and the red dash represents the median value. The boxes stretch from the first quartile (bottom) to the third quartile (top), meaning that 25% of the values are below the first quartile and 75% are equal or above the third quartile.

Figure

  Figure #𝑚 Time 𝑓 Time 𝑙 Time𝑔 Distance Fig. 1 3 5m 15s 10s 2475 Fig. 2 4 7m 37s 15s 2179 Fig. 12 3 5m 18s 15s 3190 Fig. 13 4 10m 41s 38s 3806 Fig. 14 5 8m 50s 31s 2998

Table 1 .

 1

Test scene statistics: number of landmarks (#𝑚), the total time for computing view quality fields, local trajectory construction time, global optimization time, and distance of the global optimal trajectory in meters.

ACM Transactions on Graphics, Vol. 37, No. 4, Article 88. Publication date: August 2018.

https://www.dji.com/ground-station-pro ACM Transactions on Graphics, Vol. 37, No. 4, Article 88. Publication date: August

ACKNOWLEDGMENTS

We thank the reviewers for their valuable comments. This work was supported in part by NSFC (61522213, 61761146002, 6171101466, 61532003, 61622212), China Postdoc Foundation (2017M622780), 973 Program (2015CB352501), Guangdong Science and Technology Program (2015A030312015), Shenzhen Innovation Program (KQJSCX20170727101233642, J-CYJ20151015151249564), ISF-NSFC Joint Research Program (2217/15, 2472/17), and NSERC (293127).

APPENDIX Downloads for our high-resolution aerial videos:

http://vcc.szu.edu.cn/drone1/download/