Quentin Galvane

Christophe Lino

Marc Christie

Julien Fleureau

Fabien Servant

Directing Cinematographic Drones

Keywords: animation, cinematography, drones, interactive control Concepts:, Human-centered computing → User centered design, •Computing methodologies → Multi-agent planning, Motion path planning, •Applied computing → Media arts

: We introduce a set of interactive tools for filming dynamic targets with quadrotor drones. We first propose a specific camera parameter space (the Drone Toric Space) together with on-screen viewpoint manipulators compatible with the physical motion constraints of a drone (see green quadrotor). We then propose a real-time path planning approach in dynamic environments which ensures both cinematographic properties in viewpoints along the path and feasibility of the path by a quadrotor drone. We also present a sketching tool that generates feasible trajectories from hand drawn input paths (see red quadrotor). Finally we propose to coordinate positions and motions of multiple drones around some dynamic targets to ensure the coverture by drones of cinematographic distinct viewpoints (see blue quadrotors).

Introduction

With the advent of stable and powerful quadrotors, coupled with high quality camera lenses mounted on controllable gimbals, quadrotors are becoming new cinematographic devices in the toolbox of both professional and amateur filmmakers. However, mastering the control of such devices to create desired sequences in possibly evolving environments requires a significant amount of time and practice. Indeed, synchronizing the quadrotor and camera motions while ensuring that the drone is in a safe position and satisfies desired visual properties remains challenging. Professional film crews actually rely on two operators who coordinate their actions: a pilot focuses on the drone motion and a cinematographer focuses on the camera orientation.

To ease the process of creating qualitative footage, consumer drone quadrotors have been proposing features such as follow-me, in which the drone automatically follows and frames a moving target (using a GPS or vision-based tracking algorithms). More evolved approaches propose to design virtual trajectories in 3D environments, ensuring their feasibility by drones before executing them in the real world [START_REF] Roberts | Generating dynamically feasible trajectories for quadrotor cameras[END_REF][START_REF] Joubert | An interactive tool for designing quadrotor camera shots[END_REF]Gebhardt et al. 2016]. While such approaches lead to useful prototyping tools, they do not consider moving targets, and are therefore limited to static or close-to-static guided tour scenes. Collision constraints are not considered (except for [Gebhardt et al. 2016]), personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. c 2018 ACM. and avoidance trajectories must be designed manually [START_REF] Roberts | Generating dynamically feasible trajectories for quadrotor cameras[END_REF]. In addition, little control of the visual properties is provided, such as maintaining a framing, distance or camera angle on a target.

In contrast, the computer graphics community has been focusing on how to enforce the visual properties of a virtual camera related to framing, distance or orientation w.r.t. dynamic targets, and also enforce such properties over camera motions. Automated viewpoint computation tools can (i) solve such problems in real-time [START_REF] Ranon | Improving the efficiency of viewpoint composition[END_REF], (ii) perform transitions between viewpoints by interpolating cinematographic properties [START_REF] Lino | Intuitive and efficient camera control with the toric space[END_REF]] and (iii) automatically edit sequences from multiple viewpoints [START_REF] Galvane | Continuity Editing for 3D Animation[END_REF]].

Recent approaches have been considering the application of such cinematographic visual properties to drones through mechanisms to ensure their satisfaction in static scenes [START_REF] Joubert | Towards a drone cinematographer: Guiding quadrotor cameras using visual composition principles[END_REF]] and mechanisms to follow pre-designed camera paths using local avoidance techniques and react to dynamic targets [Nägeli et al. 2017b].

There are, however, limited contributions to fully dynamic planning techniques that can interactively plan the coordination of multiple drones in relation to dynamic targets. Indeed, the design of a cinematographic drone system with the ability to enforce visual properties on dynamic targets requires to address a number of challenges. First, the formalization of cinematographic film principles needs to be adapted to quadrotor drone constraints (limited view angles, path feasibility). Second, safety must be ensured at any time, which in turn requires the adaptation of interactive manipulation tools. Third, the coordination of multiple drones requires to plan, maintain and dynamically reposition cameras to ensure complementary cinematographic viewpoints around moving targets.

We address these three challenges by proposing:

• a dedicated parametric representation for placing drones in relation to targets -the Drone Toric Space -which both ensures the feasibility of drone positions around targets and ensures safety constraints are satisfied with regards to these targets;

• a through-the-lens interactive drone manipulation tool, which offers cinematographic control of viewpoints through target manipulations in the screen space;

• a dedicated real-time path planning technique for dynamic environments, which enables the creation of cinematographic trajectories optimized to ensure their feasibility by quadrotor drones;

• a coordination technique to orchestrate the placement of multiple drones around dynamic targets using min-conflict optimization.

Our system provides both interactive and automated cinematographic control on one or multiple quadrotor drones for the specific task of framing dynamic targets. This enables to envision smarter design tools for the creation of cinematographic sequences, where users would essentially focus on the aesthetic choices. This also opens perspectives towards controlling autonomous groups of drones with cinematographic behaviors which would enable the prototyping of film sequences or the shooting of documentaries.

Related Work

Automated camera control in virtual environments

The problem of controlling a camera in a virtual 3D environment has been addressed by a wide range of techniques and is strongly guided by the type of tasks to perform and the target application. An overview is presented in [START_REF] Christie | Camera control in computer graphics: models, techniques and applications[END_REF][START_REF] Christie | Camera control in computer graphics[END_REF]] gathering automated, reactive and interative approaches to virtual camera control, including specific techniques for planning paths, managing occlusions and modeling high-level communicative goals.

We here restrict our overview to techniques closely related to our approach. The automated computation of viewpoints has first been addressed by Blinn [START_REF] Blinn | Where am i? what am i looking at?(cinematography)[END_REF]] who proposed an efficient iterative technique to compute the position and orientation of a camera from the specification of on-screen positions and visual properties. The problem has been expressed in a more general framework where visual properties in the image space (position an orientation of targets) are expressed as constraints on the degrees of freedom of the camera, and been solved through a range of techniques including stochastic, regular sampling or quadratic programming [START_REF] Drucker | Intelligent camera control in a virtual environment[END_REF]Bares et al. 2000b;[START_REF] Ranon | Improving the efficiency of viewpoint composition[END_REF]. Recently, a different camera representation has been proposed, the Toric Space, that simplifies the expression and solving of viewpoint computation problems [START_REF] Lino | Intuitive and efficient camera control with the toric space[END_REF].

The computation of camera paths imposes challenges such as collision with complex 3D environments, visibility of multiple targets, and also smoothness over the trajectory. In [START_REF] Salomon | Interactive navigation in complex environments using path planning[END_REF]], the authors present an approach for interactive navigation in complex 3D synthetic environments using path planning. A collisionfree and constrained path between two user specified locations can be computed on demand by relying on a prior construction of a global roadmap of the environment using randomized motion planning and graph search techniques (here an IDA* depth-first search). Smoothness is enforced by simply cutting corners along the path. More recently, Oskam et al. presented an approach that generates camera paths and enforces visibility of a target along the path when possible [START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF]]. The process relies on a prior spheresampling stage in which the visibility between every pair of spheres is precomputed. Adjacent spheres are used to construct a graph then traversed by using an A* planner. The cost on the arcs is a combination of distance and visibility. A specific smoothing process is applied which maximises the visibility along the trajectory

To the best of our knowledge, no approach has coupled path planning techniques to maintain or to interpolate visual properties in the context of cinematographic drones. Furthermore, specific constraints on the continuity of the generated paths must be set to ensure the feasibility by a drone, which requires a strong adaptation of existing techniques.

Viewpoint control in image space

In computer graphics, different approaches have been proposing Through-the-lens camera control techniques, which are interactions that occur in the screen space to constrain the camera parameters [START_REF] Gleicher | Through-the-lens camera control[END_REF][START_REF] Sudarsanam | Cube-Cam: A Screen-space Camera Manipulation Tool[END_REF][START_REF] Lino | Intuitive and efficient camera control with the toric space[END_REF]. The problem is generally expressed as a minimization between the user's specification and the current view properties. The techniques have been designed to control virtual cameras and to the best of our knowledge have not been applied to drone control (apart from straighforward forms of control such as look-from/look-at).

Trajectory planning for drones Adding to UAVs (unmanned aerial vehicles) the capacity to take photos and shoot sequences has triggered the development of a number of techniques. Applications range from automated surveillance tasks to area coverage, scanning of unknown environments, or capture of aesthetic shots of buildings, landscapes and characters. All approaches have in common the computation of trajectories that have to obey the physical characteristics of the UAV motion.

For scanning unknown environments, different strategies have been applied: [START_REF] Dunkley | Visual-inertial navigation for a camera-equipped 25g nano-quadrotor[END_REF] perform autonomous hovering with a quadrotor drone using a visual-inertial SLAM (simultaneous localization and mapping) system, [START_REF] Nuske | Autonomous exploration and motion planning for an unmanned aerial vehicle navigating rivers[END_REF] propose a system that detects and maps a specific visual feature (river), and plans paths around three-dimensional (3D) obstacles (such as overhanging tree branches) only with onboard sensing and no GPS nor prior map.

In approaches where the environment is known, research has also been focusing on the generation of optimal safe trajectories while satisfying constraints on velocities and accelerations bounds for one drone [START_REF] Mellinger | Minimum snap trajectory generation and control for quadrotors[END_REF] or for a set of drones, each with a specific goal state [START_REF] Turpin | Goal assignment and trajectory planning for large teams of aerial robots[END_REF]. [START_REF] Deits | Efficient mixed-integer planning for uavs in cluttered environments[END_REF] present an approach to the design of smooth trajectories for quadrotor UAVs, which are free of collisions with obstacles along their entire length.

Multiple approaches have been addressing the problem of spatially coordinating entities [START_REF] Pereira | Formation control with configuration space constraints[END_REF], to maintain specific spatial configurations for drones [START_REF] Schiano | A Rigidity-Based Decentralized Bearing Formation Controller for Groups of Quadrotor UAVs[END_REF] or for drone collaborative tasks [START_REF] Mellinger | Minimum snap trajectory generation and control for quadrotors[END_REF], through centralized or decentralized systems.

The specific problem of assisting the design of drone trajectories for aesthetic aerial videography has received limited attention. Current approaches focus on the design of feasible trajectories that link user-defined viewpoints [START_REF] Joubert | An interactive tool for designing quadrotor camera shots[END_REF]Gebhardt et al. 2016;[START_REF] Roberts | Generating dynamically feasible trajectories for quadrotor cameras[END_REF]. The process consists in 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 look-from/look-at viewpoints (keyframes) manually positioned. In [START_REF] Joubert | An interactive tool for designing quadrotor camera shots[END_REF], the timing of the keyframes is also specified by the user. A specific C 4 continuous trajectory is then created between the keyframes (C 4 property ensures the path obeys the physical equations of motion). The resulting trajectory is then analyzed to detect the infeasible sections along the path (sections where the velocity or control force to be applied are too important), so the user can iteratively alter the keyframe timings. The work has later been extended to address this feasibility issue automatically [START_REF] Roberts | Generating dynamically feasible trajectories for quadrotor cameras[END_REF]. The technique consists in performing a time-warping of the trajectory, altering the speed between the viewpoints without altering the trajectory nor the keyframes.

Another quadrotor trajectory design tool has been proposed in [Gebhardt et al. 2016]. The principle is similar to [START_REF] Joubert | An interactive tool for designing quadrotor camera shots[END_REF]]: a camera path can be drawn and edited in a virtual environment, and then optimized to ensure its feasibility. However given the multiple constraints (including preventing collisions with the environment), the optimization process does not guarantee to respect the user inputs (a tradeoff between user inputs and conflicting constraints is performed). The system offers an intuitive tool for novice users to create quadrotor based use-cases without requiring deep knowledge in either quadrotor control or the underlying constraints of the target domain.

Such approaches however do not account for more cinematographic properties on the viewpoints nor on the camera path. [START_REF] Fleureau | Generic drone control platform for autonomous capture of cinema scenes[END_REF] recently presented a tool to automatically maintain visual on-screen properties (orientation, composition) on moving targets, and automatically compute transitions between viewpoints with moving targets [START_REF] Galvane | Airways: Optimization-based planning of quadrotor trajectories according to high-level user goals[END_REF]]. The approach relies on the Toric Space representation [START_REF] Lino | Intuitive and efficient camera control with the toric space[END_REF] to efficiently express cinematographic properties (distance to target, angle on target, screen positions of targets) and perform interpolations in the Toric Space rather than in the Cartesian space to maintain visual properties along the trajectory. adopted a local optimization approach to motion planning for UAVs. Their online optimization scheme computes drone control inputs under a receding horizon based on visual properties. They extended this work in [Nägeli et al. 2017b] to include the possibility of controlling multiple drones and following constrained trajectories -referred to as virtual camera rails. Their solution locally adjusts the flight plan with a given time horizon and ensures its feasibility. Their system allows the tracking and avoidance of dynamic targets including other drones. This work however does not propose a solution for the computation of the virtual rails taken as input -it only performs local optimization -and does not provide any high level coordination strategy for the placement of multiple dronesi.e. each drone is separately given its own input.

In these approaches, while the generated trajectories satisfy the feasibility criteria, either the cameras are guided by users through keyframes and are limited to static scenes or they do not enable the autonomous planning of paths in dynamically changing environments. By contrast, the method we propose is fully automated, plans paths globally, works in a dynamic context and provides the foundations for collaborative motions of drones.

Overview

Our system is structured around two components: the director and the coordinator (see Figure 2). The director component holds the high-level user specifications for the master drone such as a sketched trajectory to follow, or a visual framing to achieve in relation to targets. Specifications are fed into a Planner component that plans an appropriate drone path to fulfill the specifications. A Navigator component then computes the control commands to steer the drone along the computed path. The path planner constantly checks the validity of the path (i.e. the respect of director specifications with relation to the targets) and replans a new path when necessary. The director component only controls the Master drone.

The coordinator component is in charge of orchestrating the motion of the other drones (named slave drones) in relation to the Master drone, in a way to offer complementary views on the scene. The system is connected to a tracker (an optical localization tool) that performs the real-time 6-DOF tracking of drones, targets and dynamic obstacles. The poses are used to update a roadmap representation of the environment used by the planner.

The specificity of our approach lies in that the planning is performed in a new parametric space, the Drone Toric Space (DTS), rather than in a Cartesian space. This space, presented in Section 4, is a re-parameterization of the Toric Space (a camera representation to express and manipulate viewpoints in virtual environments). We show how this space can be exploited to propose through-the-lens manipulation techniques dedicated to quadrotor drones (Section 5), and how planning can be performed to avoid variations of on-screen properties (Section 6). We finally present how to orchestrate the motion of multiple drones to ensure cinematographic coverage of a 3D scene with dynamic targets by exploiting this Drone Toric Space (Section 7).

DTS: a parametric space for drone control

We introduce the Drone Toric Space (DTS), a representation dedicated to the manipulation and planning of cinematographic drones.

Our representation builds on the Toric Space representation [START_REF] Lino | Intuitive and efficient camera control with the toric space[END_REF], proposed for the control of virtual cameras. The Toric Space is an expressive camera model in which the visual properties of two targets can be easily expressed, and the corresponding camera configuration can be efficiently computed. The power of this model is that it directly encodes the screen positions of targets in the representation. Given two desired screen positions, the set of possible camera viewpoints is a 2-parametric surface (a Toric surface) -a spindle torus on which every viewpoint enforces the same angle α (computed from the screen positions) between the two targets and the camera. The position and orientation of the camera onto this surface is parameterized through two Euler angles, ϕ and θ, denoting vertical and horizontal angles around targets respectively. In the Toric Space, any camera viewpoint is therefore described as a 3d vector (α, ϕ, θ). Our Drone Toric Space is designed to overcome limitations of the original Toric Space. Specifically, it accounts (i) for the safety of targets (i.e. we enforce a safety distance dS to targets) and (ii) for the constraints and limitations of quadrotor drones (e.g. fixed or gimbal camera, limited tilt angle).

In the following we denote a drone configuration, for which the filming camera is the end-effector (see Figure 3), as a 7d vector q(x, y, z, ρ, γ, ψ, λ). The drone position is represented by a 3d vector ω(x, y, z) in Cartesian space. The orientation is represented by three Euler angles (ρ, γ, ψ) respectively encoding its roll, pitch and yaw angles. The camera's additional orientation is determined by the Euler angle λ corresponding to the tilt of the gimbal holding the camera. We finally assume for the sake of simplicity that the drone and the filming camera positions coincide. A target is an object (typically a person) on which a number of visual properties can be enforced. A target is characterized by its position and orientation p (xp, yp, zp, φp, θp, ψp).

ψ (yaw) γ (pitch) ρ (roll) λ (tilt)
Figure 3: Our drone configuration (where the filming camera is considered as the end-effector) is expressed as a 7d vector q(x, y, z, ρ, γ, ψ, λ), where the 3d vector ω(x, y, z) represents the drone's location, the 3d vector (ρ, γ, ψ) the drone's orientation and λ the gimbal rotation. In our representation, we also assume that the camera position and the drone position coincide, as in practice the distance between them is negligible.

Ensuring safe drone locations

The Drone Toric Space is designed to avoid collisions with the drone's targets by construction. Assuming that a Toric surfacei.e. a Toric Space where parameter α is fixed becomes a Toric suface -is defined around two targets A and B, some camera viewpoints on this surface do not enforce the safety distance (e.g. viewpoints close to A or B see Figure 4). We therefore reformulate the Toric Space in a way to replace these viewpoints (i.e. drone positions forming a continuous surface) by two surfaces E A S and E B S (respectively for A and B). These surfaces are tangent to both the remaining Toric surface and a safety sphere of center T and radius d S (security distance) ensuring in practice that the drone has a distance to any target at least greater than d S .

In practice, we define r as the radius of the original Toric surface (Figure 4 shows a cross section of a Drone Toric Space). To determine the surface E A S , we rely on the 1-parametric line (of abscissa x) whose origin is target A and whose directing vector points towards B. Depending on dS, three types of Drone Toric surfaces can be distinguished:

Type #1: d S < r -AB
2 . E A S belongs to a sphere, centered at a point CA of abscissa x = -r 2 -δ 2 2(δ-r sin α) (where δ = r -d S ) and with radius x -d S .

Type #2:

d S > r -AB 2 . E A S belongs to a sphere, centered at a point CA of abscissa x = AB 2 + δ 2 -r 2 2(δ-r sin α) (where δ = d S + AB -r), and with radius x + d S . Type #3: d S = r -AB
2 . E A S belongs to a plane, orthogonal to the line (AB), and passing through a point LA of abscissa -d S . It corresponds to the limit between type #1 and #2 (i.e. when |x| tends toward ∞).

NB: surfaces of type #1 are concave, while surfaces of type either #2 or #3 are convex (see figure 4).

The Drone Toric surface is then parametrized through a pair of ratios (ϕ, θ) ∈ [-1; +1] 2 representing the horizontal and vertical angles around targets. We have designed these ratios in a meaningful way: practically θ = 0 and θ = ±1 provides a view from behind B and a view from behind A, respectively. Then, ϕ = 0, ϕ = +1 and ϕ = -1 provide a view from the targets' height, from above and from below targets, respectively. Further, following Arijon's trian- gle principle [START_REF] Arijon | Grammar of the Film Language[END_REF]], the view angles can be split into two main regions : external views (where the camera should stay behind one target while framing the other) and apex views (where the camera should stay at equi-distance to both targets). We also define an intermediate region which we refer to as external-apex views. In practice, we represent these characteristic camera regions through predefined intervals (of width 0.25) on the axis θ (see Figure 5).

A B α r C A C B A B r α C A C B Type #1 Type #2 A B r α L A L B Type #3
Note that, in the case of filming a single target, we can also build a Drone Toric surface, reduced to a sphere around the target, whose radius is never smaller than the safety distance. For the sake of simplicity, in this case we use the symbol α to refer to the sphere radius. Further, we accordingly parametrize this sphere through the same pair of ratios (ϕ, θ), where θ = 0 and θ = ±1 provide a view from the front and from behind the target, respectively.

In the remaining, we will refer to such a re-parametrized surface as a Drone Toric surface and to the continuous set of these surfaces defined around one or more targets as a Drone Toric Space, parametrized through a triplet (α, ϕ, θ).

Ensuring feasible camera orientations

Given a possible drone location on the Drone Toric Space, we provide a mean to compute a feasible drone orientation. A feasible drone orientation exists when the drone is in a stationary location. Indeed, as soon as either the drone's roll (ρ) or pitch (γ) is non null then the drone is set in motion (see Figure 3). In a stationary location, the possible variations on the end-effector camera orientation is limited to two degrees of freedom: its yaw (ψ) representing the yaw of the drone, and tilt (λ) rotations representing the tilt of the camera.

Further, to account for the physical limits of the gimbal rotation, λ must be within an interval I λ of feasible tilt rotations; in particular when no gimbal is used, I λ = [0]. We here propose an iterative two-step algorithm that, given a stationary drone location and the desired screen positions of an arbitrary number of targets, computes a feasible drone orientation, i.e. values for the drone's yaw and camera's tilt parameters (its pseudo-code is given in Algorithm 1).

In a first stage, we will assume that the initial camera orientation is feasible (i.e. ρ = 0, γ = 0 and λ ∈ I λ ); we shall explain how to compute this initial orientation later. From then on, we optimize the two degrees of freedom ψ and λ to best match the desired onscreen positioning of the filmed targets, while ensuring that the new orientation remains feasible. Practically, for a given camera orientation, we determine the error (horizontally or vertically) on their on-screen positioning. We express these errors as angular variations ∆ψ (yaw angle error) and ∆λ (tilt angle error) that we will apply on ψ and λ. In our algorithm, we iterate on correcting each degree of freedom separately, while the other is left fixed, until both errors become lower than a predefined threshold .

The computation of ∆ψ and ∆λ is performed as follows. We can define the camera orientation as an Euclidian frame (xc, yc, zc) (i.e. an east-north-up frame), centered at the camera's location ω, which can be determined from the 4d rotation vector (ρ, γ, ψ, λ). Note that a key feature of a feasible camera orientation (whose roll is null) is that the east component xc is aligned with the horizon (i.e. it must be orthogonal to the world up vector, which we refer to as zw). Thus, a variation of its yaw angle will correspond to a rotation around axis zw and a variation of its tilt angle to a rotation around axis xc. We build on this feature to ensure the camera orientation remains feasible.

We assume that we want each target T to be positioned at a 2d point pT on the screen. Note that, in the world space, all 3d world points projecting at pT on the screen are located on a half-line (whose origin is the camera); in particular, we will refer to its directing vector as v d T . We then compute the tilt and yaw errors for target T (referred to as ∆ψT and ∆λT ). To do so, we rely on the difference between two vectors: (i) the desired direction v d T and (ii) the actual direction v a T from the camera to the target T . Practically,

∆ψT = zw Πz w (v d T ), Πz w (v a T )
where Πn(v) is a projection operator, which projects vector v in the plane whose normal is n; and n [v1, v2] is the directed angle (in the plane whose normal is n) between two vectors v1 and v2.

We then compute ∆ψ as the average of all ∆ψT ; and apply the variation ∆ψ to ψ. In a way similar,

∆λT = xc Πx c (v d T ), Πx c (v a T )
We compute ∆λ as the average of all ∆λT , and apply the variation ∆λ to λ. To account for the range of feasible tilt values, we then clamp λ to the interval I λ , and we clamp ∆λ to reflect the actual variation that was applied. After each separate correction, we also recompute the frame (xc, yc, zc), as well as all vectors v d T to match the new camera orientation.

To compute the initial feasible camera orientation, we denote (xc, yc, zc) as a look-at orientation applied to all targets. We first compute the vector yc as the average of all normalized vectors vT; this will balance targets around the center of the screen. We then compute xc and zc accordingly (i.e. xc = yc × zw and zc = xc × yc). We finally compute the 4d vector (ρ, γ, ψ, λ) as follows:

ρ = 0 γ = 0 ψ = zw [Πz w (yw), Πz w (yc)] λ = xc [Πz w (yc), yc]
where the frame (xw, yw, zw) represents the default look-at orientation of the drone (i.e. with ρ = 0, γ = 0, ψ = 0 and λ = 0).

Through-the-lens control of drones

To perform a through-the-lens interaction (i.e. controlling the position of the drone by interacting with the locations of on-screen targets), we propose to implement dedicated manipulation operators adapted to the drone's constraints. From discussions with an expert drone cinematographer 1 , we have extracted two key behaviors for all target T in targets do ∆λi := λi -λi-1 24: until ∆ψi < and ∆λi < that are strongly expected when manipulating a viewpoint around targets:

• when starting from a given viewpoint (with features such as screen position, size, and view angle on targets) and when manipulating one feature, the camera is expected to move while maintaining similar values for the other features;

• any viewpoint manipulation should be reversible (i.e. when manipulating back to the initial screen composition the user would expect the camera to come back to its initial location).

While obvious, such features are not ensured by the manipulators proposed in [START_REF] Lino | Intuitive and efficient camera control with the toric space[END_REF]. We redefine such manipulators to better fit these behaviors as well as incorporate constraints linked to drones' physical limits.

Through-the-lens manipulators

View angle manipulator

As the user manipulates the view angle on the targets, the process should maintain the targets sizes and their on-screen positions. This can be ensured by moving the drone on the current Drone Toric surface. Note that in the specific case of moving on a surface of type #1 (concave), when the camera gets close to the axis created by the two targets, the size of the closest target changes significantly (to ensure the framing). Using such a surface would then create a non aesthetic motion behind this target. In this specific case, we thus propose to extend the safety distance in such a way to instead move onto a surface of type #3 (i.e. the closest convex DTS). With this modification, the framing is slightly altered but this avoids unaesthetic motions and preserves the C 1 continuity of the camera motion.

Position manipulator

As the user manipulates the framing of one target (i.e. on-screen positions of a target), the on-screen position of the other target should be maintained, as well as the view angle and sizes should be coher- ent with the initial viewpoint semantics (apex, external, externalapex).

In Lino & Christie [2015], the computation of a new camera configuration only maintains the targets on-screen positions. This is performed with a local search optimization on the Toric surface, looking for a viewpoint that optimally matches both targets onscreen specifications. In transposing this to the Drone Toric Space, the regions close to the axis created by two targets will not contain optimal solutions (i.e. perfectly matching both targets on-screen locations), as illustrated in Figure 6.a. In addition, their method is non-reversible, and does not keep the view angle coherent with the initial viewpoint. Finally, their position manipulator does not account for constraints such as keeping the drone in-between a floor and a ceiling height.

We improve the approach by computing the camera orientation so that, from a given position in a DTS, it best satisfies the desired targets screen locations by using the original viewpoint computation in [START_REF] Lino | Efficient composition for virtual camera control[END_REF]; in this formulation the roll angle of the camera is left free. We then search, on the current DTS, for a viewpoint with a feasible orientation (i.e. whose roll angle is null). With this method, though the framing may not always be optimally satisfied, we ensure that a feasible drone configuration can always be found, even in regions close to the axis formed by the two targets (see Figure 6.b).

Secondly, we account for floor and ceiling constraints. Note that such constraints are difficult to express directly in terms of DTS parameters. In order to provide an estimate of these constraints we start from a strong assumption: targets are at the same height in the scene. In such a situation the set of positions to avoid form centered ellipses on the top and bottom of the parameter space of a DTS (illustrated in Figure 6.c). These constraints are re-evaluated in a further step to account for targets at different heights, but provide a good estimate (see section 5.2). Lastly, the drone must be maintained in a camera region coherent with the semantics of the initial viewpoint (i.e. when starting the manipulation).

By building upon the above assumptions and constraints, we propose a novel position manipulator which (i) enforces the new target's on-screen positions, (ii) keeps the new viewpoint coherent in terms of the initial view angle, (iii) ensures the manipulation is reversible, and (iv) avoids violating floor or ceiling constraints. We rely on five control spaces (external A, external-apex A, apex, external-apex B, external B) for which we ensure a smooth transition between their behavior. Each control space relies on the search of a new viewpoint onto a search curve, bounded to the corresponding camera region (see figure 5). Starting from an initial viewpoint at position (ϕ0, θ0), we use a dichotomous search (Golden Section Search) performed on each segment of this curve separately. This ensures that we can find a solution in a deterministic way, onto the current DTS, from any initial viewpoint and manipulation.

For an external view, the search curve is made of two segments (one on each side of the 180 • line), designed as the lines θ = |θ0| and θ = -|θ0| (which preserve both the sizes and the view angle on targets). Note that, for external views, floor and ceiling constraints can be considered as negligible. For an apex or an external-apex region, the search curve is made of a series of ellipse segments that ensure the following features: (i) the search curve contains the initial viewpoint point (ϕ0, θ0), (ii) it is made of a symmetry with regards to the 180 • line, (iii) it intersects as less as possible the floor and ceiling constraints and (iv) to obtain a C 1 curve, adjacent segments are joined at points where their tangents are equal. For the apex view, the control space is designed to also overlap the two external-apex regions; this ensures a better collision avoidance while it preserves a similar viewpoint semantics. We also subdivide this control space into two sub-spaces, handled in a symmetric way: apex views from above or from below targets. For external-apex views the control space has a behavior that smoothly transitions between the behavior of the external and apex control spaces.

Dolly manipulator

The user can also manipulate the size of a target. The dolly-in / dolly-out manipulator provides a camera motion that makes a selected target bigger or smaller, while it preserves its view angle. This manipulator is implemented as a motion (forward or backward) in the direction of the target.

World-space manipulators To enable more subtle interactions on the viewpoint, we also offer a set of existing world-space manipulators to move the drone forward, left or up, as well as to pan or tilt the drone. These manipulators are common in most 3D modelers; they can be viewed as moving the camera along a rail, with a creane, or rotating it with a pedestal.

Collision Avoidance

As we mentioned earlier, a hard constraint is that, during the viewpoint manipulation, we must output a valid drone configuration, i.e. a feasible drone configuration that is not colliding with a static (object) or dynamic (target) obstacle and is located within the physical bounds of the scene.

At this step, we assume a desired new viewpoint has been computed to fit a given screen manipulation (as explained in section 5). If this new viewpoint collides with any entity, a natural solution is then to push or pull the drone to avoid this collision. We propose to apply this push/pull mechanism along a half-line H passing through the desired new viewpoint and whose origin is the target linked to the current screen manipulation (this mechanism is illustrated in Figure 8). We intersect H with all (static or dynamic) obstacles and with the bounds of the scene. This provides us with a set of segments I onto which the drone could be placed along H. Finally, to avoid large variations in the drone location (e.g. jumping around an obstacle), we select the new drone location so that (i) it belongs to one segment of I and (ii) it is as close as possible to the previous drone location. When no potential location can been found (i.e. I = ∅), the default behavior is to not move the drone. This ensures safety not only with regards to obstacles but also targets; in particular moving targets then have the possibility to safely avoid the drone.

The key challenge in filming dynamic targets with drones is to compute collision-free paths of cinematographic quality. To this end, we first propose a method to compute the shortest collision-free path between two drone configurations by introducing a novel composite distance metric expressed partly in the Drone Toric Space (to ensure continuity of cinematographic properties over targets) and partly in the Cartesian space (to avoid variations on the altitude of the drone). We then propose an algorithm to plan a collision-free path from a user sketch, which draws inspiration from [Gebhardt et al. 2016] but handles dynamic obstacles. Finally we present a novel path-smoothing technique which, when applied on the computed paths, outputs C 4 -continuous drone trajectories.

Planning cinematographic collision-free paths

The planning of collision-free paths first relies on the choice and computation of a roadmap which samples the free space of a 3D environment. We rely on a visibility-aware roadmap construction similar to [START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF]] in which a prior sphere-sampling stage of the static free space is performed, and the visibility between every pair of spheres is precomputed using raytracing. Adjacent spheres are then connected with arcs in order to construct a roadmap (which we refer to as R). The roadmap is dynamically updated at every frame with moving obstacles (nodes that intersect the obstacles are tagged non traversable).

Generating a qualitative path in this roadmap (in terms of cinematographic properties) rarely means computing the shortest one in the Cartesian space. We propose a novel metric to express shortest paths in the space of visual properties, a shorter path meaning that there are less variations over these properties. Interestingly, our Drone Toric Space already represents visual properties such as distance to targets, angle and composition. Also, to minimize variations in the drone altitude along the path, we extend the space with a dimension z (a small variation of ϕ onto a DTS may lead to a strong change in altitude). Hence, we cast our path planning problem as a search for the shortest path in the roadmap by expressing nodes in a 4d space (α, ϕ, θ, z) (which we refer to as the τ -space) and by relying on Euclidian distances between nodes. The cost of an arc between two nodes in the roadmap is then computed by weighting the distance τ -space with the visibility of targets. The computation of the path is performed by considering the targets as static. If the targets move, or if obstacles move, the path is recomputed to account for the changes.

Given two drone configurations qs (starting viewpoint) and qe (ending viewpoint) and given targets, the process consists in first adding qs and qe as nodes in the roadmap, and then expressing these configurations in τ -space. We further account for the drone's current acceleration and speed in order to temporarily tag all nodes that would not be reachable by the drone (considering its maximum speed and acceleration) as non traversable. We then rely on a classical A* process to search the roadmap. The distance metric in this search is computed as a combination between the distance in screen properties, height of the drone, and visibility.

Evaluating the variation in screen properties. This variation is expressed as the sum of the normalized differences in angles between two nodes ni and nj for angles ϕ and α. For θ given that θ = -1 and θ = 1 represent the same configuration, the smallest distance dm is expressed as dm(θi, θj) = min(2-|θi -θj|, |θi -θj|)

D 2 s (ni, nj) = αi -αj 2π 2 + ϕi -ϕj 2 2 + dm(θi, θj) 2 2
Evaluating the variation in height. Height difference is computed as a normalized difference, given ceiling and floor limits:

D 2 h (ni, nj) = |zi -zj| |zc -z f | 2
where zc and z f represent the ceiling and floor limits. The length of an arc in the τ -space is then expressed as:

Dτ (ni, nj) = D 2 s (ni, nj) + D 2 h (ni, nj)
Visibility. In a way similar to [START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF], we rely on the computed visibility stored for each couple of nodes in the roadmap. This cost O(i, j) is normalized (0 is fully visible and 1 fully occluded).

The length L of an arc in the roadmap therefore aggregates the variation of the screen properties and the variation in height, weighted by the visibility of targets, and is expressed as:

L(ni, nj) = [1 + wo.O(ni, nj)] .Dτ (ni, nj)
where wo defines the weight (wo ∈ [0, 1]) associated to visibility.

Planning collision-free sketched paths

We now consider the problem of planning a collision-free path inside our roadmap from a manually sketched trajectory. Gebhardt et al. . [Gebhardt et al. 2016] proposed a similar sketching interaction mode but restricted to static scenes. Our approach tracks dynamic targets when moving along the trajectory and avoids dynamic obstacles. Furthermore, we provide the user with a control of the speed at which the drone moves along the path, while clamping it's value so that the path remains feasible.

As illustrated in Figure 9, the user sketches a raw path, then refines the height along the path and our system computes a collision-free trajectory that can be executed with a drone. The sketched trajectory (which we refer to as S) is composed of an ordered list of 3D positions. We therefore need to compute the closest path to S through the roadmap R. Running a simple A* algorithm in the roadmap R is insufficient as it would not be able to handle loops (the user may specify self intersecting trajectories). We propose a straightforward adaptation through the definition of an oriented graph structure G based on R. Each node v (which we refer to as a virtual node) in G is a pair (n, m) where n is a node in R and m is an index representing a position along the sketched trajectory S. A node v1(n1, m1) is considered a predecessor of another node v2(n2, m2) in G if and only if (1) n1 and n2 are directly connected in R and (2) m2 > m1.

A traditional A* can then be applied on the structure G: a list of potential nodes (referred to as P) is used, and is updated by adding the neighbors of the current best node v b (n b , m b ). The score of a node is evaluated through a cost function and a heuristic function estimating the accumulated error distance to the sketched trajectory S. The process stops as soon as the final node is found or when P becomes empty. The graph G is constructed in a lazy way (i.e. nodes are only created when evaluated). In practice, we only evaluate successor nodes vs of v b for which the value ms is comprised in the interval m b + 1, m b + W (where W is our search window along trajectory S), i.e. we search for successor nodes that are close enough in terms of indices along the sketched trajectory S. One should note that constraining the search in this predefined window ensures that the algorithm detects intentional loops. We compute the cost of such a successor vs as and the heuristic cost of vs by using an average distance error: hc(vs) = c(vs)/ms

Generating C 4 continuous paths

Once a path is computed in the roadmap, a smoothing process is required to create a C 4 -continuous trajectory. This requirement ensures the trajectory is feasible by a drone [START_REF] Mellinger | Minimum snap trajectory generation and control for quadrotors[END_REF]. Comparatively, [START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF] only compute a C 2continuous splines by Hermite interpolation between nodes of the roadmap. In contrast we propose a C 4 -continuity smoothing by relying on a piecewise polynomial representation of degree 5. These polynomials Pi are expressed as:

Pi(t) = ai + bi.t + ci.t 2 + di.t 3 + ei.t 4 + fi.t 5 (1)
where t ∈ [0, 1].

The raw path is composed of N key-points ki, each representing a node traversed by this path. Our smoothed path is then composed of N -1 polynomials, each satisfying the following constraints:

Pi(0) = ki, ∀i ∈ [1 . . N -1] Pi(1) = ki+1, ∀i ∈ [1 . . N -1] (2)
and

P i (1) = P i+1 (0), ∀i ∈ [1 . . N -2] P i (1) = P i+1 (0), ∀i ∈ [1 . . N -2] P (3) i (1) = P (3) i+1 (0), ∀i ∈ [1 . . N -2] P (4) i (1) = P (4) i+1 (0), ∀i ∈ [1 . . N -2]
(3) Equation 1 contains 6(N -1) unknown coefficients, while Equations 2 and 3 provide only 6N -10 equations corresponding to all C 4 continuity constraints. To fully determine our system, we constrain the first and second derivatives of the first and last polynomials to be null, that is :

P 1 (0) = 0, P 1 (0) = 0, P N -1 (1) = 0 and P N -1 (1) = 0 (4)
The solution of this system is a C 4 -continuous trajectory passing through each of the initial key-points (center of the portals). However, depending on the density of nodes in the roadmap, the obsta-cles in the scenes and the relative configurations (positions and orientations) of the targets, the smoothed path may still display some variations in visual properties.

While current approaches focus on minimizing the curvature along a path to improve its quality [START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF], we propose to minimize the variations of the curvature to generate more homogeneous motions. In addition, optimizing the curvature variations reduces the use of the drone's actuators which might also result in battery saving. To solve the problem, we take advantage of the characteristics of our roadmap [START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF]. A node represents a portal between two intersecting spheres. This portal is a disk, representing all possible keypoints through which a path may connect these two adjacent spheres. We therefore cast our problem as the search of all optimal keypoints ki within each of the N portal disks that minimizes curvature variations while ensuring the C 4 -continuity of the final path.

Our optimization problem is therefore expressed as the computation of all coefficients of the N -1 polynomials so as to minimize the absolute curvature variations, i.e. : This sum must be optimized subject to the constraints defined above (equations 3), and the following additional constraints to account for the portals radius and orientation:

P1(0) -k1 = 0 Pi(0) -ki -ri ≤ 0, ∀i ∈ [1 . . N -1] PN-1(1) -kN-1 = 0 (Pi(0) -ki) • ni = 0, ∀i ∈ [1 . . N -1]
where ni and ri are respectively the normal and radius of the i th traversed portal.

This nonlinear constrained optimization problem is solved using an Interior Point solver. The solver is initialized with the N -1 polynomials computed with Equations 2, 3 and 4 using the center of the traversed portals as the initial keypoints.

Following C 4 paths

Once a C 4 curve D (defining the drone trajectory) is computed, the task consists for the drone to follow this curve as closely as possible. This is performed using the control scheme proposed in [START_REF] Fleureau | Generic drone control platform for autonomous capture of cinema scenes[END_REF]]. Based on a Linear Quadratic Regulator, this scheme ensures that the control input sent to the drone will always be feasible ensuring the drone is able to precisely follow the trajectory (see section 8.4 for detailed error measurements).

At run-time, the roadmap is continuously checked for dynamic obstacles along the planned path (i.e. checking that all nodes on the planned path still belong to the free space). As a potential collision may occur, the path is recomputed from the current drone configuration. In a similar way, if the end viewpoint configuration qe has changed (e.g. when following a dynamic obstacle) the path is recomputed to reflect this change.

In addition to providing a full automated mode, we also allow provides means for the user to interactively control the framing of the targets along the path as well as the progress along this path. More precisely, we let the user control the acceleration to avoid jerky motions due to the remote controller device. To compute the drones positions along the path based on an input acceleration, we start by an arc-length re-parametrization of the path so that every point is defined by:

S(u), u ∈ [0, L]
where L is the total curvilinear length of the path. Then for a given time t, and a given drone position ω, we compute the curvilinear index ut along the trajectory so that S(ut) is the closest to the drone; in practice this is performed by minimizing S(ut) -ω such that ut is taken in a local neighborhood of ut-1 and with ut ≥ ut-1.

From ut, we can compute a new goal position S(ut) for the drone along the curve using the input speed and acceleration. To ensure that the drone does not deviate from the trajectory both the input speed and acceleration require to be clamped. As shown in Section 8.4, using the same LQR strategy, the error distance to the trajectory remains sufficiently low (less than 0.4m) to ensure user's safety (the safety distance being set to 1.5 meters in the experiments).

Along the path, the framing may be dynamically controlled by the user, choosing which target(s) should be framed and at which locations in the screen. This process has two main advantages: (i) the user can adjust the execution of the trajectory to the live evolution of the scene (i.e. targets' performance) and (ii) the user is relieved from the hard task of manually controlling the drone position and orientation to avoid obstacles while also maintaining a given framing on targets at the same time.

Coordinating cinematographic drones

Our objective is to coordinate the positions and motions of mutliple drones around dynamic targets by (i) covering distinct cinematographic views of the targets at the same time, and (ii) avoiding conflicts between the drones. The challenges to address here, in a system where targets move freely in the environment, are actually to (i) minimize possible conflicts between drones while ensuring a good cinematographic covering of the scene, (ii) dynamically reassigning locations to drones as conflicts arise.

To tackle these challenges, we first rely on a master/slave relation hypothesis between drones: at any time, the system has a unique master drone (the drone that is currently shooting the scene), and multiple slave drones not currently shooting but either ready to shoot the scene, or moving towards positions where these would be ready to shoot from. The purpose of the slave drones is to propose at any time alternate and complementary viewpoints on the targets while avoiding visibility conflicts with the master drone (ie each slave should not be in the view frustum of the master's camera). This hypothesis draws its inspiration from editing rooms in TV shows where a director controls which camera is the live feed (the master), knows or controls how the other camera are placed (slaves) and decides when to switch to another camera. As with editing rooms, when switching to another camera, ie switching to a slave drone ready to shoot and without conflicts, the slave drone becomes a master drone and and the master becomes a slave.

Then, to ensure the computation of cinematographic views of targets, we propose to empower the drones with elements of cinematographic knowledge expressed as a collection of possible framings.

A framing is a specification of viewpoint properties expressed in the cinematographic language PSL (Prose Storyboard Language [START_REF] Ronfard | The prose storyboard language: A tool for annotating and directing movies[END_REF]]) relative to one or two targets.These framings correspond to classical shot angles from film literature (eg shots like apex, over-the-shoulder, medium close-up).

As the targets evolve, the drones move to maintain the framing features. On onset of conflicts, a dynamic reassignment process is performed which minimizes the number and cost of changes to perform using local repair techniques. In the sequel, we present the details of this approach.

From framings to framing instances

To each drone, master or slave, is associated some cinematographic knowledge, expressed as a collection of 17 possible framings. A framing f is a specification of viewpoint properties expressed in the cinematographic language PSL (Prose Storyboard Language [START_REF] Ronfard | The prose storyboard language: A tool for annotating and directing movies[END_REF]]) relative to one or two targets. These framings correspond to classical shot angles in film literature (eg over-theshoulder shots, medium close-up shots, apex shots). While multiple languages have been proposed for the purpose of controlling a virtual camera [Bares et al. 2000a;[START_REF] Halper | A Camera Engine for Computer Games: Managing the Trade-Off Between Constraint Satisfaction and Frame Coherence[END_REF][START_REF] Ranon | Improving the efficiency of viewpoint composition[END_REF], only the PSL specification language is strongly tied to cinematography. Designed for both annotating film shots and expressing specifications for computational cinematography, the language only finds partial implementations as [START_REF] Ronfard | The prose storyboard language: A tool for annotating and directing movies[END_REF][START_REF] Galvane | Narrative-driven camera control for cinematic replay of computer games[END_REF].

For a framing f with a list l of targets, the positions of which are known, we define a framing instance operator which computes a geometric instance of the framing f . This instance I f,l is computed and expressed as a volume of possible drone positions in which each position τ in the Drone Toric Space shares the cinematographic properties of f . The idea is founded on the notion of Director Volumes [START_REF] Lino | A Real-time Cinematography System for Interactive 3D Environments[END_REF]] which represent a convex volume to which multiple semantic tags are associated, each tag representing a visual cinematographic property such as visibility, camera angle, shot size, etc. The dynamic computation of these regions was performed using BSPs, a computationally expensive process to be performed in real-time especially when considering visibility with complex scene geometries. In contrast, we express this volume as a convex 3D region defined in the Safe Manifold Surface coordinates. A framing instance I f,l corresponds to a region τ = ϕ, θ, α where ϕ, θ, α are intervals of values. 17 distinct regions around one and two targets are defined, each region corresponding to cinematographically distinct framing. In our case, the bounds of each region have been easily designed by hand from the film literature (ie setting ϕ, θ, α).

Conflicts between drones

Three types of conflicts with two natures of conflicts were identified. Hard conflicts should be avoided at any time, and soft conflicts should be avoided whenever possible, and introduce some flexibility in a problem that otherwise easily becomes over-constrained.

Collision conflicts are always hard conflicts and enforce a minimal distance between two drones to avoid perturbations due to air thrusts and ground effects. Collision conflicts also occur between the drone and environment constraints (boundaries of the scene or scene geometry). Collision conflicts are handled by performing Euclidean distance computations (in case of collisions between drones), and queries in the roadmap in case of collisions with the static scene geometry.

Visibility conflicts (having a drone viewing another drone in it's viewport) is a hard conflict when applied to the master drone (no other drone should be visible in its viewport). But it is a soft conflict between slave drones, or between a slave drone and the master drone (i.e. the slave may have the master in it's viewport). Visibility conflicts are detected in a straightforward way when computed between drone configurations using frustum tests. However visibility conflicts also need to be computed between two frame instances (when multiple drones need to select frames instances (e.g. during the initial assignment), or between a frame instance and a done position (see Figure 10). Conflict detection is performed in two different stages: (i) when assigning framings to each drone (region to region visibility computation), and (ii) when the scene is evolving (drone to region visibility computation) to check if a region is still valid or to evaluate valid regions. Since the intersection between the framing instance region and the frustum cannot be performed algebraically, a straightforward dichotomous search is performed along the edges of the 3D Drone Toric Space (similar to the marching cube technique). For each edge, we approximate the possible intersection with the frustum. A region is then fully visible by another region, partially visible, or non visible at all.

Initial assignment using min-conflict

Ideally, all conflicts should be avoided between all the drones at any time. However, given the wideness of the view angles we consider (diagonal angle is 92 on the parrot, and 94 on the DJI Phantom 3), the dynamic orchestration of multiple drones around moving targets in a constrained environment while preventing all conflicts quickly becomes in practice an intractable problem. Hence, the motivation behind our master/slave hypothesis -and beyond the idea of reproducing a TV show editing room-is also to avoid locked situations where too many simultaneous conflicts limit the possibilities and reduce the practical applicability of the approach and as a side effect, to reduce the overall computational complexity due to pairwise conflict testing between drones.

The overall approach consists in selecting consistent framings for the master and all the slave drones, so as to avoid visibility conflicts with the master, collision conflicts between all the drones, and minimize angle and visibility conflicts between the slaves. This is a straightforward combinatorial assignment problem, easily expressed as a CSP (Constraint Satisfaction Problem). However, we aim at more than just a consistent assignment. First, when there are multiple consistent assignments possible (ie multiple solutions where there are no conflicts), it is preferable to select the one that requires the least energy for the global system (i.e. selecting among possible solutions the one for which the total length between current drone positions and target regions are the shortest). Second, when there is no consistent assignment, it is preferable to select an assignment that minimizes the conflicts. To this end, we rely on a min-conflict local search technique [START_REF] Minton | Solving large-scale constraint-satisfaction and scheduling problems using a heuristic repair method[END_REF]], which from a first initial assignment, iteratively selects the drone which has the most conflicts and for this drone selects a candidate framing which minimizes all conflicts. Interestingly the min-conflict strategy can provide a locally best solution at any time.

The process can be formalized as follows. Let's define a drone d to which can be associated one camera specification f among a set of possible specifications F. We provide a function c(d) which computes the number of conflicts the drone d has with other drones, and a second function f (di, sj) which computes the cost for a drone di to move to a region corresponding to a specification sj. This cost is the length of the path in the roadmap from a the drone's position to the center of it's destination region. Computing max ic(di) selects the drone with most conflicts, and the largest cost. The selection of the best framing candidate then relies on searching for the framing j that minimizes min jc(d) + f (di, sj).

Once an initial assignment is performed, we decide a destination position in each region, computed as the center of the region in the Drone Toric Space coordinate system, and then converted into a drone configuration. When regions are partially visible (i.e. intersect a frustum), the center of the largest visible volume is computed in the Drone Toric space. We then rely on our drone path planning technique (Section 6) to compute a path to the destination position. To this end, the roadmap is dynamically updated by penalizing nodes inside the frustum of the master drone with high traversal cost. Slave drone trajectories therefore avoid crossing the frustum (see Figure 11), but can still plan paths in the frustum if needed (e.g. when a master drone swifts around quickly).

Dynamic assignment using local repair

At any time, as the scene evolves (ie the master drone moves or targets move), the systems maintains the camera framings when possible. When targets move, the framing instances are updated and the drones move towards the center of their updated framing instance. As conflicts appear (eg a framing instance is in conflict), a new combination of framings needs to be assigned to one or multiple drones. To this end, we rely on local repair techniques, a well-known heuristic in dynamic planning problems [START_REF] Miguel | Dynamic flexible constraint satisfaction and its application to AI planning[END_REF]] which minimize the amount of changes in assignments. The process is the following: a list L containing the drones in conflict at time t is created. The minconflict is then applied to the drones in L and gives a subset list L of the drones still in conflict. All the drones in conflict with each drone of L are then added to the list L over which min-conflict is re-applied. The process ends when no conflicts are found, or when the minconflict has been applied to all the slave drones in the scene. In the best case, only the salve drones in conflict will be re-assigned a new framing. In the worst case, all slave drones will be reassigned a framing.

Evaluation and Discussion

To evaluate our system, we used a set of Parrot ARDrone2 equipped with an onboard camera. While these drones do not provide any form of stabilizing gimbal -which also prevents from controlling the tilt of the camera -they currently remain consumer market drones that are safe enough to be used at very close range. The experiments were conducted in a 30×20 meter room where a Vicon motion capture system was set up to manage the real-time tracking of drones, dynamic objects and targets in the scene. The final tracking volume was approximately 15×10×5 meters. Different configurations of this volume were created with various static obstacles placed in the scene. For each configuration, a 3D model of the scene was built and the visibility roadmap was generated as detailed in section 6.

Our tool is designed as a Unity 5 plugin under Linux, linked to the control system of each drone through a Wi-Fi connection. It also provides a simulation mode allowing to simulate the drone behavior, based on its physical model. With this mode a user can train on the tool, without having to fly the drone, and has the possibility to interactively move targets and obstacles in the 3d scene.

User evaluation

We here evaluate the relevance of our tool to create drone shots, in a known environment with static and dynamic obstacles. We have conducted a user study, in which we have compared both our image-space manipulation tool (referred to as the framing tool, described in section 6.1) and our sketching tool (described in section 6.2) with a traditional drone control device -in our study, we used a controller with two analog sticks. We recruited twelve novice users with no prior knowledge in cinematography nor drone piloting. After a short demonstration of the three modes (i.e. framing, sketching and manual piloting), they were given 10 minutes of training on each mode. They were then assigned a series of 3 tasks, to perform both manually (M) and with our tool (T). Firstly, given a target on-screen composition of two actors (i.e. a screenshot), they had to (i)M manually maneuver the drone and (i)T use our framing tool, to move the drone to a viewpoint closely matching this target composition. Secondly, they had to maintain a given framing over the actors as they moved around in the scene, with (ii)M the manual mode and (ii)T our framing mode. Thirdly, to evaluate our sketching mode, we asked the participants to perform a series of trajectories (zoom in, traveling, turn around the actors) while maintaining the camera oriented towards the actors. They had to complete it by (iii)M manually flying the drone with the controller and (iii)T by using our sketching tool. Finally, each participant had to complete a full questionnaire. For all three tasks, they had to evaluateon a Likert scale from one (worst) to five (best) -their familiarity with each type of tool, the ease of use, the perceived fluidity of the created camera motions, the precision and their personal satisfaction over the obtained results. In addition, they all provided verbal feedback on each mode. Figure 12: Results of our user evaluations, conducted with twelve participants, to compare manual flight with our sketching and framing tools. On a scale from one to five, each participant evaluated their degree of familiarity with each type of tool (a), their ease of use (b), the fluidity of the drone motion (c), the ease to maintain the framing over one or a group of actors (d), the precision of the tool (e) and their satisfaction over the resulting shot (f).

Although most participants were more familiar with traditional manual controllers (see Figure 12a), they clearly favored our tool on every aspect (see Figures 12b to 12f). In addition to the graded evaluation, many expressed their satisfaction over the results and they found both that our tool is easier to use and that its resulting output is more precise (i.e. better fits their intentions). Some referred to our tool as very promising, very interesting or fun. One drawback of our framing mode, highlighted by some participants, is the lack of control on the drone trajectory. Some suggested that the addition of means to specify a series of key shots could help better craft trajectories. In the sketching mode a complaint was that, though the height of the sketched path can be manipulated, it is not possible to make modifications on its shape. Users must redraw a new path. However, considering this path can be modeled as a spline curve, we could easily include spline manipulators in our sketching tool.

From this study, we made several other observations. Not surprisingly, none of the participants were able to produce qualitative footage by manually flying the drone -i.e. tasks (i)M , (ii)M and (iii)M -in a simple constrained environment. As we expected, this task actually requires much more training. Participants were also able to complete tasks (i)T , (ii)T and (iii)T in just a few trials. They were in general more comfortable with the sketch-based approach, as it allows more freedom than the screen-space manipulation mode. Further, all participants provided good feedback. They were particularly surprised to see how easily they could produce good-looking footage despite their inexperience in both cinematography and drone piloting.

Expert feedback

In a separate session, we invited an expert cinematographer (film producer and camera drone pilot) to experiment our tool. After a rapid overview of the tool, he was given 30 minutes to take over the different interaction modes. He was then asked to perform the same tasks as novice users (see section 8.1). We finally asked him to provide us with his feedback on this experiment. Following his advice, we also tested our tool on a variety of other scenarios (the corresponding footage are provided in the accompanying video). These scenarios demonstrate our contributions: onscreen manipulation, cinematographic path planning from screen composition, dynamic obstacle avoidance and drone coordination. These tests were performed in the same environment, comprising multiple obstacles, up to three moving targets, and up to three quadrotor drones.

The expert especially appreciated having to interact with the drone through only a single degree of freedom (its velocity) compared to the 7 degrees of freedom he usually has to interact with when manually flying the drone. He also appreciated not having to handle the avoidance of obstacles, and being able to easily and precisely control the framing. He however expressed some frustration due to the unavailability of a simple controller for the tilt of the camera; and he found the creation of an extremely precise trajectory difficult with our sketching tool, when actors are dynamically evolving within the environment. More specifically, his main issue was the precise synchronization of the drone motion with the actors motions during a staged sequence -in a way similar to a real camera operator, which is currently almost impossible for a single drone pilot.

Footage from these experiments are included in the companion video and illustrated in Figures 13 and14.

Qualitative evaluation

We also conducted an objective study, to assess the relevance of our Drone Toric Space compared to a Euclidian space (as used in most previous techniques) in planning cinematographic paths. We extracted and analyzed the evolution of visual properties along a drone trajectory, performed with the different modalities. Similar to task (i)T in Section 8.1, we computed a drone path (from its current position to a desired viewpoint) by using our path planning algorithm (i.e. the shortest path in Toric space) and compared it with the method in [START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF]] (i.e. the shortest path in world space). For the sake of the evaluation, we also asked a user to manually perform the same path. The experiment was conducted within the simulator. This guaranteed that the initial state of the drone and actors were always the same, thus ensuring that results were not affected by external stimuli.

Figure 15 shows the performed trajectories in each scenario. As expected, the automated solutions produce smooth trajectories and avoid obstacles (i.e. the actors). Conversely, the manual flight resulted in a very noisy trajectory. In terms of visual satisfaction, Figure 16 highlights the main issues encountered with the manual flight and the shortest path solutions. When manually flying the drone, the user had difficulties to handle the drone position and the framing of the actors simultaneously. When using [START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF]], the drone is not able to maintain the visibility of the actors during the whole flight. As illustrated in Figure 16b, when flying towards the target viewpoint, the drone reaches a position where it cannot frame both actors. When using our solution based on the Toric space, this constraint is satisfied: the drone continuously maintains the visibility over both actors during the whole flight (see Figure 16c).

The interest of our Drone Toric Space is highlighted in Figures 17a to 17c that show the evolution of visual properties along time. We here analyze the onscreen positions, sizes and view angles of actors -more precisely, for each feature, we have computed the distance between their desired and actual values.

As previously observed, visibility issues can also be noticed in Figure 17a. While our approach is limited to small errors in terms of onscreen positions of targets, [START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF]] fails as the camera gets too close to the actors. The same observation can be made on the variation of actors' sizes (Figure 17b). Conversely, our solution provides a smooth interpolation from the initial to the target viewpoint whereas the shortest path suffers from important variations of the actors sizes. In a similar way, for the view angle on actors (Figure 17c), our solution produces an almost linear interpolation between the initial and target viewpoints. In the case of [START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF] variation is slow at the beginning, then increases strongly, and finally stabilizes to its target value. Footage from these experiments is shown in the companion video.

Performance

Path planning. Avoiding dynamic obstacles requires the ability to perform path planning tasks in reactive time. To demonstrate the performance of our system and its capacity to avoid dynamic objects, we tested it on different scene configurations. Due to the limitation of the real environment and to provide a more extensive benchmark, we conducted part of this evaluation with the simulator -which has no impact on the performances of our computations. Performances of our path planning process are presented in Table 1. These results clearly show that all computation times remain lower than 200ms.

Multi-drone. Given the low number of drones used in practice (2 to 4), the computational cost of the min-conflict process remains tractable. The number of combinations for two targets is n a tentative framing instance), when computing an initial assignment (smoothing is not performed). 18 illustrates the average distance (i) between the drone trajectory to follow and the drone location along time, then (ii) between the desired framing and the actual framing. These results were taken from all the experiments we have conducted with the drones. It demonstrates the precision in world space, and proves the ability of our system to both produce a feasible trajectory and move a drone to closely follow it.

Limitations

The system is currently limited in several aspects. First, from a purely hardware standpoint, the choice of the Parrot ARDrone clearly impaired our system capacities. While this drone remains one of the best options in terms of users' safety, the lack of camera tilt, the absence of any form of stabilization and the noisy propellers make it a poor choice for cinematographic tasks. In future work, we plan to integrate the more recent Parrot Bebop drone. Less noisy, this drone is equipped with a full HD wide angle camera that allows numerical tilt and stabilization. Much smaller, it also creates less air perturbations. Regarding the planning process, while our solution is fast enough to allow real-time recomputations of the path, the framing of highly dynamic targets remains challenging. Investigating anticipation schemes appears as a good lead for more advanced path planning strategies. Finally, our path following method could be improved. As we let the user manually control the drone's velocity along the trajectory, we could further improve the flight accuracy by integrating the local optimization scheme proposed by [Nägeli et al. 2017b]. Though we were not aware of their work when writing this paper, their optimization scheme is complementary to our path planning technique.

Conclusion

We presented a system to intuitively control one or more cinematographic drones in dynamic scenes. Our system empowers quadrotor drones with cinematographic knowledge, to then enable the design and execution of quadrotor shots, as well as the automated coordination of autonomous drone cinematographers covering a set of moving targets. Through this paper, we have introduced a model dedicated to the control of drones which ensures the feasibility of drone positions and the safety of targets. We have proposed a complete real-time computation pipeline that enables generating and interactively executing feasible drone trajectories. We have presented a cinematographic through-the-lens control method adapted to the specificity of controlling quadrotor drones in real environments. We finally proposed an automated technique to orchestrate, in real-time, the simultaneous placement of multiple drones to follow dynamic targets in a cinematographically-sound manner. To the best of our knowledge, this is the first system to provide both interactive and automated cinematographic control on one or multiple quadrotor drones with dynamic targets. We also feel that this kind of systems allows to envision great perspectives towards prototyping and creation of cinematographic sequences, where users would essentially focus on aesthetic choices.

Figure 2 :

 2 Figure2: Overview of our drone system. First, poses of drones and targets are tracked in real-time and exploited to update a collisionfree roadmap thats abstracts the real environment. The user then has multiple ways to input specifications in a Director module. A path-planning process (planner) creates feasible trajectories in this roadmap from the Director specifications, and then relies on a control loop (navigator) to follow the path. At last, a coordination component (coordinator) orchestrates the motions of the non-master drones to create complementary viewpoints.

Figure 4 :

 4 Figure 4: Red areas represent drone configurations which are unsafe for a target, i.e. closer than a safety distance dS. The Toric Surface representation is locally adapted such that drone viewpoints enforce the safety distance and remains C 1 continuous. The local adaptation of the surface (in green) depends on (i) the radius r and the distance between the targets (ii) the safety distance dS around targets.

Figure 5 :

 5 Figure 5: Our Drone Toric Space parametrization (top). Classical horizontal view angles used in cinematography are cast into 3 semantic regions (external, external-apex, apex) modeled as intervals on parameter θ (bottom).

Figure 6 :

 6 Figure 6: Our through-the-lens target re-positioning technique needs to rely on a minimization of the drone's roll angle performed on the Drone Toric Surface (ϕ, θ), while satisfying the users' re-positioning inputs. To better highlight the solution, we here display the dual space of satisfaction (i.e. 1 -|roll| /π), which we want to maximize. Red regions represent the drone positions with a roll value closer to zero, blue regions furthest to zero. As displayed in image (b), the parametrization of the Drone Toric Surface provides favors a roll value close to zero even when placed behind target A or B (i.e. value θ = 0 or θ = 1 in b), a possibility not available in Lino & Christie [2015] as displayed in image (a). Image (c) displays the intersection of the Drone Toric Surface with floor and ceiling boundaries of the real environment.

Figure 8 :

 8 Figure 8: While interactively manipulating the on-screen properties of a target, we strictly avoid collisions by pushing or pulling the drone to a non-colliding location.

Figure 9 :

 9 Figure 9: Our sketch-based path design: (a) the user sketches a trajectory (in red) without accounting for obstacles, (b) the trajectory's height can be manually adjusted along the path, (c) a collision-free and feasible drone path is computed (in green). A path is also computed from the current drone's position to the beginning of the computed path (blue).

  .di.ei + 20.di.fi + 16.e 2 i + 60.ei.fi + 60.f 2 i

Figure 10 :

 10 Figure 10: Visibility conflicts are detected using extreme points of the framing instances. The intersection between a frustum and a region is computed using a marching cube dichotomous search in the 3D Drone Toric Space.

Figure 11 :

 11 Figure11: When coordinating multiple drones, the roadmap is dynamically updated by tagging nodes inside the master drone's frustum as non traversable. If a drone is inside the view frustum of the master drone, a path is computed which avoids non traversable nodes.

Figure 13 :

 13 Figure 13: Shot captured with the drone as the expert is flying a trajectory crafted with our sketch based tool. The top view (a) shows the trajectory computed (in green) from the drawn trajectory (in red). (b), (c), (d) and (e) give different viewpoints taken at different times along the trajectory.

( a )

 a Desired shot composition (b) Virtual top view of the scene (c) Initial framing (d) Final framing

Figure 14 :

 14 Figure 14: Shot captured with the drone as the expert is flying a trajectory computed with our framing tool.

Figure 15 :

 15 Figure15: Trajectories followed by the drone to reach a specific viewpoint while framing two actors, in manual mode, with[START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF]] and with our path planning solution.

Figure 16 :

 16 Figure16: Shots captured with the simulated drone as the user tries to reach a given framing in manual mode (a), with the method proposed in[START_REF] Oskam | Visibility transition planning for dynamic camera control[END_REF]] (b) and with our cinematograpic path planning solution (c).

Figure 17 :

 17 Figure 17: The evolution of on screen properties along a drone path. The distance (from 0 when properties values match to 2 when they are of opposite value) between the current framing and the desired framing is displayed along three features: screen position (a), screen size (b) and view angle (c). For each feature, values are computed as the average distance over both actors.

  |F | dwhere n d represents the number of drones, and |F| the number of framings. For n d = 3 there are 4913 configurations, and for n d = 4 there are 83521 configurations.

Figure 18 :

 18 Figure 18: Error in meters on the drone's position with regards to a generated trajectory to follow.

  Computation of a feasible orientation for N targets

	1: // Initialize orientation
	2: (ρ0, γ0, ψ0, λ0) := computeInitialOrientation(ω, targets)
	3: clamp λ0 to I λ
	4:
	5: // Iterate on correcting ψi and λi
	6: repeat
	7:	// Correct yaw
	8:

1 Filmaker Corto Fajal, http://www.imdb.com/name/nm1109092/ Algorithm 1

Table 1 :

 1 Table2presents the computation times for distance, visibility and angle conflict detection as well as for tentative path planning (to evaluate the cost of moving to Computational performances of our two path planning techniques (framing and sketching).

			Environment resolution				12m x 18m x 4 18m x 18m x 4m 18m x 18m x 4m 30m x 30m x 5m
			# spheres in the roadmap					1222	2320	1979	2551
			# nodes in the roadmap					8020	17247	13873	22446
			Scene complexity						medium	low	high	high
			Path length in framing mode (# nodes)			14	9.7	13.4	8.1
			Planning duration in framing mode (ms)		55	67	69	64
			Path length in sketching mode (# nodes)		16.1	36.8	31.2	43.4
			Planning duration in sketching mode (ms)		98	87	124	107
			Path optimization duration (ms)			76	58	59	78
		0.2
		0.18
		0.16
		0.14
	Frequency (%)	0.08 0.1 0.12
		0.06
		0.04
		0.02
		0	0	0.05	0.1	0.15	0.2	0.25	0.3	0.35	0.4
					Distance to the trajectory (m)

Table 2 :

 2 Computation times in ms for the min-conflict optimization in the initial assignment stage for 2 and 4 drones. The last column represents the average time per frame (in ms) of the dynamic local repair reassignement.

	Process	2 drones (ms) 4 drones (ms) local repair
	Distance	1	3	1
	Angle	1	4	1
	Visibility	47	130	4
	Planning	30	460	3
	Min-conflict	92	980	-
	Precision. Figure