Ronan P Soares

Fractional Combinatorial Games on Graphs †

Keywords: Graph, Surveillance, Fractional Surveillance, Approximation

De nombreux jeux impliquant deux joueurs dans un graphe ont été étudiés en théorie des graphes : Gendarmes et voleur, Ange et Démon, Observeur et surfeur, Dominants universels, etc. Outre la capture d'un fugitif ou la lutte contre le feu, ces jeux ont aussi des applications dans les réseaux de télécommunications car, d'une part, ils permettent de mieux appréhender les structures des réseaux, et d'autre part, ils permettent de modéliser et d'étudier des problèmes de ces réseaux (e.g., problème de cache dans l'internet). Dans tous ces jeux, chaque joueur contrôle des jetons sur les sommets du graphe et selon les jeux, les joueurs peuvent: déplacer des jetons le long des arêtes du graphe, ajouter/supprimer des jetons, etc. Dans ce travail, nous proposons une approche générale en définissant un jeu qui constitue, entre autre, une relaxation fractionnaire de tous les jeux mentionnés ci-dessus. Pour ce jeu générique, nous montrons qu'il existe un algorithme en temps polynomial, en le nombre de sommets du graphe et le nombre de maximum de tours de jeu autorisés, pour décider si un des joueurs a une stratégie gagnante. Cet algorithme permet de calculer une stratégie efficace (approximation à un facteur log n près), gagnante avec forte probabilité, pour le problème de cache.

Introduction

In graph theory, various combinatorial games played on graphs have been studied. On the one hand, they provide a better understanding of graph structures which helped to design efficient algorithms to solve problems in telecommunication networks [START_REF] Kosowski | k-chordal graphs: From cops and robber to compact routing via treewidth[END_REF]. On the other hand, such games provide nice theoretical models for telecommunication network problems themselves [FGJM + 12]. In this paper, we present a new approach, based on fractional relaxation of linear programming, for studying these problems. In particular, it leads to a polynomial-time algorithm that computes lower bound for these problems.

Combinatorial games. A combinatorial game refers to a turn-by-turn game played by two players, C and R , on a (di)graph. In graph theory, many such games have been studied and share several properties.

In Cops and Robbers games [START_REF] Aigner | A game of cops and robbers[END_REF], Player C controls a team of k ∈ N * cops and R controls one robber. C starts by choosing vertices of G to put its cops, then R chooses a vertex of G to put its robber. Then, turn-by-turn, first C may move each of its cops along one edge, then R may do the same with its robber. C wins if its cops are able to capture the robber, i.e. if a cop occupies the same vertex as the robber. The objective of R is to avoid capture indefinitely. A winning strategy for C is a function that describes the next move for C to win. It assigns to every state (positions of the cops and of the robber) the moves that must be done by the cops to ensure the capture of the robber whatever its moves may be. The main question is to decide if there is a winning strategy for C using a predetermined number of cops. The structural characterization of graphs for which C with k cops wins has led to many studies [START_REF] Bonato | The Game of Cops and Robbers on Graphs[END_REF] and applications in telecommunication networks [START_REF] Kosowski | k-chordal graphs: From cops and robber to compact routing via treewidth[END_REF]. Unfortunately, deciding the smallest k such that C wins in a graph is PSPACE-complete [START_REF] Mamino | On the computational complexity of a game of cops and robbers[END_REF].

Another example of such a game has been defined to model the web-page caching and, more generally, prefetching problems [FGJM + 12]. In the surveillance game, C first marks a node where R must place its token. Then, turn-by-turn, C marks at most k ∈ N * nodes and R may move its token along an edge. C wins if it can mark all nodes before R reaches an unmarked vertex. Computing the smallest k such that C has a winning strategy is PSPACE-complete [FGJM + 12]. † A full version of this paper can be found in [START_REF] Giroire | Fractional combinatorial games[END_REF].

The idea of a fractional game and results presented in this work can be applied to many other combinatorial games such as variants of Cops and Robber games [START_REF] Mamino | On the computational complexity of a game of cops and robbers[END_REF], Angels and Devils [START_REF] Berlekamp | Winning Ways, for Your Mathematical Plays: Games in particular. Winning Ways[END_REF], Eternal Dominating Sets [BCG + 04] and Eternal Vertex Cover [START_REF] Klostermeyer | Graphs with equal eternal vertex cover and eternal domination numbers[END_REF]. All these games can be described in an unified way. Initially, both players place some tokens, then, turn-by turn, first C plays then R plays. The goal of C is to reach some particular state while R wants to perpetually avoid it.

Fractional games. In order to unify and provide some solutions for these combinatorial games, we define the notion of Fractional Combinatorial Game. Specifically, we propose a framework for a combinatorial game where C and R are allowed to use fractions of tokens on the vertices of a graph of order n.

For instance, in a 4-node cycle C 4 , it is easy to see that 2 cops are necessary to capture one robber in the integral (classical) game. On the other hand, if C initially places half-cops on three nodes of C 4 (i.e., using 3/2 cops in total), we can prove that C can capture one splittable robber (exercise left to the reader).

Our results. We define the notion of a fractional game in which both players can split their tokens, of semi-fractional game in which only C can split its tokens and of integral games in which tokens are not splittable. In particular, all above mentioned games are integral games.

The main characteristic of these fractional games is that they satisfy some convexity property. Thanks to this property, we are able to design an algorithm that, given a fractional game in a n-node graph, decides whether there is a strategy for C to win in t ∈ N turns and, if C can win, that computes a corresponding winning strategy. This algorithm is polynomial in t and in the size of the game. In all above mentioned games, the size of the game is polynomial in n and, therefore, our algorithm can decide in time polynomial in n if C can win the fractional game in a number of turns polynomial in n.

Our second result is that, under a weak additional assumption which is satisfied in all games mentioned, C wins the fractional game in t ≥ 0 turns if and only if it wins the semi-fractional game in t turns. Since if C wins the integral game, then it wins the semi-fractional game, this implies that C wins the integral game only if it wins the fractional game. Therefore, our algorithm computes lower bounds for the optimization problems corresponding to the integral games.

Lastly, in the surveillance game, we show an integral strategy, that wins against R with high probability.

Moreover, the expected cost of this integral strategy is in O(log n) factor from the fractional strategy.

Fractional Games (Fractional Surveillance Game)

We define a family of Fractional Combinatorial Games in a n-node graph G (with vertex-set V (G) = {1, . . . , n}) in which two players turn-by-turn modify a real vector representing their positions on G (the state of the game). In a Fractional Combinatorial Game, the moves allowed for each player are described as "convex" operators on vectors in R O(n) . The game is also defined by various convex sets of R O(n) : the set W C of winning states, the set I of initial states, the set V of valid states. C wins the game if it reaches a state in W C before t ∈ N turns. R wins otherwise or if it reaches a state not in V .

Due to space restrictions, and for an easier description, we focus on the Surveillance Game. We describe the fractional variant of this game and the main guidelines of our algorithm to solve it.

The amount of tokens belonging to C on each vertex i of G is represented as a vector c ∈ R n + in which c i is the amount of tokens on vertex i. Similarly, the amount of tokens of R is represented as a vector r ∈ R n

+ . A state of the game is a pair (c, r) ∈ R n + × R n + .
At each turn, C is allowed to place fractions of marks on nodes of G but must place at most k marks in total. The set of possible moves for C is the set X C (k) of vectors x ∈ R n + such that ∑ n i=1 x i ≤ k. In other words, during its turn, C can move the current state of the game (c, r) to a state (c + x, r) with x ∈ X C (k).

The set of possible moves for R is the set ∆ R of matrices δ ∈ [0, 1] n × [0, 1] n such that it satisfies these two restrictions: if (i, j) is not an arc of G then δ i, j = 0 and ∑ n i=0 δ i, j = 1 for all j ∈ V (G). In other words, during its turn, R can move the game from state (c, r) to the state (c, δr) with δ ∈ ∆ R and if δ is a matrix in ∆ R , then δ i, j represents the amount of tokens of R that moves from vertex j to vertex i during a move of R .

The fractional surveillance game played on a digraph G with initial state (c, r) is a turn-by-turn game starting with player C where C , during its turn, moves the current state (c, r) to (c + x, r) with x ∈ X C (k) and R , during its turn, moves the current state (c, r) to (c, δr) with δ ∈ ∆ R . The game is won by R as soon as there exists i ∈ V (G) such that r i > c i in the current state of the game. Otherwise, C wins when c i ≥ 1 for all i ∈ V (G).

Fractional Combinatorial Games on Graphs

The fractional surveillance number, fsn(G, v), is the minimum k such that C can always win the fractional surveillance game against R regardless of its moves where the initial state (c v , r v ) is given by c v = r v = 1 and for all other vertices i we have c i = r i = 0. Let a round be composed of one turn of C and one turn of R .

One simple remark is that the game is over in at most (|V (G)| -1)/k rounds. This is a direct consequence from the fact that, at each step that is not the last, C can use all its k marks.

The integral surveillance game is the restriction of the fractional game when the states of the game are vectors of N n × N n , the moves of C are vectors of N n and the moves of R are {0, 1} n×n matrices.

Polynomial-time Algorithm for the Fractional Game

The main ideas to design a polynomial-time algorithm are as follows. We use a set of linear inequality (i.e., a linear program) to describe the set C t of states from which C can win in t > 0 rounds. Then, in polynomial time, we compute the linear program describing C t+1 . More precisely, we prove: Theorem 1. For any digraph G and initial vertex v ∈ V (G), there is a polynomial-time (in n) algorithm that decides if C can win a fractional game. If the answer is positive, our algorithm computes the corresponding winning strategy for C . Let R 0 be the set of winning states for C , i.e., the set of states (c, r) with c i ≥ 1, for any i ≤ n. Let i > 0 and C i (resp., R i ) be the set of the states (c, r) such that, starting from (c, r) and if the first move is done by C (resp., by R ), C can win the game, in at most i rounds and using at most k marks per turn.

By induction on i > 0, we build a description of C i from the one of R i-1 , then a description of R i is obtained from the one of C i . These descriptions have size (number of variables and inequalities) polynomial in n. This process is repeated until a description of C F is obtained. Finally, C wins starting from v if and only if (c v , r v ) ∈ C F which can be checked in polynomial time. Obtaining C t from R t-1 . Assume that R t-1 is described by a linear program with polynomial number of variables and inequalities. Note that R 0 = {(c, r) ∈ R 2n + | ∀i ≤ n, c i ≥ 1, and ∑ i≤n r i = 1}. It is not difficult to prove that: Lemma 2. The state (c, r) belongs to C t ⇔ c i ≥ r i for all i ∈ V (G) and there is x ∈ X C (k) such that (c + x, r) belongs to R t-1 .

Roughly, Lemma 2 states that C can win in t rounds if and only if C can do a move (∃x ∈ X C (k)) to reach a state (c + x, r)R t-1 in which C wins in t -1 rounds when R starts playing.

Let L R be the linear program describing R t-1 . Assume that L R has (among others) variables c t-1 i and r i , 1 ≤ i ≤ n, that represent the state of the game. To describe C t , we add to L R new variables c t i , i ≤ n, describing the configuration of C at this turn and variables x i (i ≤ n) representing the amount of marks that must be added at node i by C at this turn. Then we add the following inequalities

x i ≥ 0, c t i ≥ 0, c t i + x i = c i , c t i ≥ r i for all i ∈ V (G) and ∑ n i=1 x i ≤ k. Clearly, a vector satisfying L C is such that (c t 1 , . . . , c t n , r 1 , . . . , r n ) ∈ C t .
Moreover, the number of new variables and inequalities is polynomial in n.

Obtaining R t from C t . In what follows, to obtain a linear program describing R t assume that there is a linear program describing C t that has size polynomial in n. It is not difficult to prove that:

Lemma 3. The state (c, r) belongs to R t ⇔ c i ≥ r i for all i ∈ V (G) and for all δ ∈ ∆ R we have that (c, δr) belongs to C t .

That is, a state (c, r) is in R t if for every possible move δ of R the state (c, δr) satisfies all inequalities describing C t . In other words, (c, r) ∈ R t means that whatever the move of R is, it reaches a state in C t where C wins in t rounds.

A state (c, r) is in R t if for every possible move δ of R the state (c, δr) satisfies all inequalities describing C t . Let A i (c, r) ≤ b i be an inequality in the linear program describing C t . The main tool used in the proof of Lemma 3 is that there are specific elements δ i ∈ ∆ R such that if A i (c, δ i r) ≤ b i then A i (c, δr) ≤ b i for all other elements δ ∈ ∆ R . In other words, for each inequality describing C t there is a "best" move for R in order to violate this inequality. Another important property of these specific elements is that they can be found in time polynomial in n.

The linear program for R t is obtained by taking each inequality, A i (c, r) ≤ b i , describing C t and rewriting it in the following manner. Let (B 1 , B 2 ) be equal to A i . We can rewrite A i (c, r) ≤ b i as B 1 c + B 2 r ≤ b i . Then, in the linear program for R t , the inequality

Integral Surveillance and Integral Winning Strategy

Let the semi-fractional surveillance game be the game where the states are given by vectors in R n + × N n , the moves of C by vectors in R n + and the moves of R by {0, 1} n×n matrices. In other words, only R is not allowed to split itself. Let sfsn(G, v) be the minimum number of marks such that C always wins regardless of the moves made by R in the semi-fractional surveillance game.

Clearly, C wins in the semi-fractional game only if C wins in the fractional game (because R is less powerful in the semi-fractional game). On the other hand, C wins in the integral game only if C wins in the semi-fractional game (since C is less powerful in the integral game). The "best" move for C that we identified in the previous section appears to be integral. It follows that: Theorem 4. For any digraph G and v ∈ V (G) we have:

This is a direct result from the fact that among the specific elements for inequality A i (m, s) ≤ b i describing C t there is always one δ i that is integral. This roughly means that the best strategy for R is to, during its turn, either move all its tokens on a vertex to one of its neighbors or to pass its turn.

Theorem 5. If C wins the fractional surveillance game with k marks in an n-node graph, then C wins the Surveillance Game with high probability if it is allowed to use O(k log n) marks.

To show how C can win with high probability, let (c, r) be the current state of the game before each turn of C . If x i is the amount of marks that a fractionary C uses in i ∈ V (G) when the initial state is given by (c, r), then the integral C repeats O(log n) times a test with probability x i ; if any of these tests gives a positive result then C marks vertex i. Then, by follwing the proof of the O(log n)-approximation for set cover in [START_REF] Vazirani | Approximation Algorithms[END_REF], this strategy has the desired properties.

Conclusion

We think that such an approach can lead to approximation algorithms for other games compatible with this framework. For instance, this approach could lead to new insights into solving the Meyniel's conjecture (O( √ n) cops can capture one robber in any n-node graph). An important question is to know whether the games related to tree-decompositions can fit this framework.


Vineet Gandhi
email: vineet.gandhi@inria.fr

Remi Ronfard
email: remi.ronfard@inria.fr

Detecting and Naming Actors in Movies using Generative Appearance Models

We introduce a generative model for learning person and costume specific detectors from labeled examples. We demonstrate the model on the task of localizing and naming actors in long video sequences. More specifically, the actor's head and shoulders are each represented as a constellation of optional color regions. Detection can proceed despite changes in view-point and partial occlusions. We explain how to learn the models from a small number of labeled keyframes or video tracks, and how to detect novel appearances of the actors in a maximum likelihood framework. We present results on a challenging movie example, with 81% recall in actor detection (coverage) and 89% precision in actor identification (naming).

Introduction

Detecting and naming actors in movies is important for content-based indexing and retrieval of movie scenes and can also be used to support statistical analysis of film style. Additionally, detecting and naming actors in unedited footage can be useful for post-production. Recent advances in face detection, upper-body detection and full-body detection have already been applied to this problem but such detectors are designed to be generic and they discard person specific and costume-specific features. Methods for learning such features are desired to improve the recall and precision of actor detection in long movie scenes where the appearance of actors is consistent over time.

Contributions We propose a complete framework to learn view-independent actor models using maximally stable color regions (MSCR) [START_REF] Forssen | Maximally stable colour regions for recognition and matching[END_REF] with a novel clustering algorithm. The actor's head and shoulders are represented as constellations of color blobs where the appearance of each blob is represented in a 9 dimensional space combining color, size, shape and position relative to the actor's coordinate system, together with a frequency term. Based on such a model we propose a detection framework with two stages. The first stage is a search space reduction using the k-nearest neighbours corresponding to the actor by just using the appearance of the blobs in the model. The second stage is a sliding window search for the best localization of the actor in position and scale. By repeating those two steps for all actors at all sizes, we obtain detection windows and actor names that maximize the posterior likelihood of each video frame.

Organization The remainder of the paper is structured as follows. First, we briefly review related work in generic and specific actor detection in movies. Then Section 3 describes the proposed statistical model and how it can be learned from examples. Section 4 describes the corresponding detection algorithms. Experimental results and evaluation of the method are presented in section 5. Finally, Section 6 draws some conclusions and discusses directions for future work.

Related work

Much previous work on actor detection and recognition has been based on face detection. Everingham et al. [START_REF] Everingham | Hello! My name is... Buffy" -automatic naming of characters in TV video[END_REF] use scripts and subtitles to learn the association between character names and faces in television drama using a frontal face detector. Sivic et al. [START_REF] Sivic | Who are you?" -learning person specific classifiers from video[END_REF] demonstrate a much improved coverage (recall) by using profile views. In one of their examples, they report that 42% of actor appearances are frontal, 21% profile and 37% are actors facing away from the camera. Drawing on that observation, they suggest that future work on increasing coverage must go beyond the use of face detection as a first step. Indeed, generic methods for detecting upper-body or full-body actors have been proposed by Dalal et al. [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], Eichner and Ferrari [START_REF] Eichner | Better appearance models for pictorial structures[END_REF] and Felzenswalb et al. [START_REF] Felzenszwalb | Object detection with discriminatively trained partbased models[END_REF], among others. While such methods can potentially increase the coverage of actor detectors by detecting actors in profile and back views, they also suffer from the higher variability of actor appearances in such views.

Extending the work in [START_REF] Sivic | Who are you?" -learning person specific classifiers from video[END_REF], Ramanan et al. [START_REF] Ramanan | Leveraging archival video for building face datasets[END_REF] demonstrate that color histogram of body appearance can be used as a strong cue to group detected faces into tracks. They show that given the unconstrained nature of the video, peo- ple can be tracked only about 50% of the time using such an approach. While the work in [START_REF] Sivic | Who are you?" -learning person specific classifiers from video[END_REF] and [START_REF] Ramanan | Leveraging archival video for building face datasets[END_REF] focuses on first obtaining tracks and later classifying or hand labeling them, our method can directly perform actor specific detections on individual frames. Closer to our approach, Sivic et al. represent people in a scene with a simple pictorial structures with 3 rectangular image regions (face, hair and torso) and use that model for finding the same people in repeated shots of the same scene [START_REF] Sivic | Finding people in repeated shots of the same scene[END_REF] . Starting from face detection regions, they use likely positions for the hair and torso regions and cluster them into actors. Instead, we use a training set containing front views, side views and even back views of actors, as shown in Figure 1. Our actor model is simpler since we only model two body parts (head and shoulders) but each part is an arbitrarily complex constellation model of color blobs. Our generative model of actor's appearance is closely related to recent work in object detection and recognition [START_REF] Weber | Viewpoint-invariant learning and detection of human heads[END_REF][START_REF] Fergus | A sparse object category model for efficient learning and exhaustive recognition[END_REF]. In the classical constellation model, image features are generated in the vicinity of detected interest points and the features are clustered using k-means, which builds a visual vocabulary of "object part appearances". Appropriate feature detectors are then trained using these clusters, which can be used to obtain a set of candidate parts from images. It is difficult to apply such models to actor appearances because interest points and their image features are typically not very stable on actors, due to fast motion and complex clothing patterns, and the density of interest points and their features can be very low. We resolve this issue by representing parts of actors with color regions rather than local features. Color regions have been shown to give good results on the problem of person re-identification [START_REF] Farenzena | Person re-identification by symmetry-driven accumulation of local features[END_REF], where the goal is to identify a person given its detection window. We extend such previous work to the more difficult problem of "re-detecting" actors where the generic detectors fail due to variations in pose and viewpoints, partial occlusions, etc. This is similar to the recently-proposed Implicit Shape Model [START_REF] Leibe | Robust object detection with interleaved categorization and segmentation[END_REF][START_REF] Leibe | Combined object categorization and segmentation with an implicit shape model[END_REF] which builds a star shaped structural model, where the position of each local part is only dependent on the object center. While the models in [START_REF] Leibe | Robust object detection with interleaved categorization and segmentation[END_REF] are view specific, we build a single view-independent model of each actor's appearance.

1 (a) (b) (c) (d)

Generative model

In this section, we introduce our generative model for the appearance of actors and describe a method for learning the model from a small number of individual keyframes or short video tracks. Our model is designed to incorporate the costume of the actor and to be robust to changes in viewpoint and pose. We make one important assumption that the actor is in an upright position and that both the head and the shoulders are visible. As a result, we model the actor with two image windows for the head and shoulders, in a normalized coordinate system with the origin at the actor's neck, and with unit size set to twice the height of the actor's eyes relative to the origin. The head region 3. Appearance models for all 8 actors in the movie "Rope" [START_REF] Hitchock | The rope[END_REF] extends from (-1, -1) to (1, 0) and the shoulder region extends from (-1, 0) to [START_REF] Andriluka | Pictorial structures revisited: People detection and articulated pose estimation[END_REF][START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF]. Examples are shown in Figures 1 and3.

More specifically, we associate with each actor a visual vocabulary of color blobs C i described in terms of their normalized coordinates x i , y i , sizes s i , colors c i and shapes m i , and their frequencies H i . Color blobs above the actor's origin are labeled as "head" features and color blobs under the origin are labeled as "shoulder" features. Contrary to previous work [START_REF] Ronfard | Learning to parse pictures of people[END_REF][START_REF] Micilotta | Real-time Upper Body Detection and 3D Pose Estimation in Monoscopic Images[END_REF][START_REF] Andriluka | Pictorial structures revisited: People detection and articulated pose estimation[END_REF][START_REF] Ferrari | Pose search: Retrieving people using their pose[END_REF], our head and shoulder models are not based on a fixed number of body parts but on an arbitrary number of salient color regions. This allows to accommodate ample clothing not revealing the body parts, and to incorporate optional or even unusual costume elements such as glasses, hats and helmets, to name just a few.

Formally, our generative model for each actor consists in the following three steps:

1. Choose screen location and window size for the actor on the screen, using the detections in the previous frame as a prior.

2. Choose visible features C i in the "head" and "shoulder" regions independently, each with a probability H i 3. For all visible features C i , generate color blob B i from a gaussian distribution with mean C i and covariance Σ i , then translate and scale to the chosen screen location and size

In effect our model is an AN D/OR graph with one AN D node and multiple OR nodes [START_REF] Zhu | Max margin and/or graph learning for parsing the human body[END_REF]. Example of randomly generated blob images are shown in Fig 4. We learn the model parameters from image examples by computing maximal color regions in all examples, clustering those regions in x, y, s, c, m space and counting the frequency H i of appearance for each cluster.We now describe each of those steps in more details.

Maximally stable color regions

The maximally stable color regions (MSCR) feature is a color extension of the maximally stable extremal region (MSER) feature [START_REF] Forssen | Maximally stable colour regions for recognition and matching[END_REF]. It is an affine covariant region detector which uses successive time steps of an agglomerative clustering of pixels to define a region. The raw moments up to order two are calculated for each detected region, which are then used to calculate the regions area, the centroid, the inertia matrix and the average color. Each region is thus represented by 9 parameters i.e. the centroid, average color and 4 raw moments representing the size and the shape of the region. An approximated ellipse is then defined over each detected region. These approximated ellipses are termed as color blobs in the later part of the text. Examples of detected MSCR features over an image are shown in Fig 1.

Clustering

We build a view-independent model of an actor's appearance by choosing a small number of front views, side views and back views for training (Fig. 2). The actual choice of samples is not very important, as long as we cover the entire range of appearances of the actor (we try to keep the training set equally sampled across different views i.e. front, back and side views). Ideally a sequence of each actor performing a 360 degree turn would be sufficient to build such models. We manually draw the upper body bounding boxes for all training examples and label them with the actor's names.

We compute the MSCR features over all keyframes in the training set. We then collect the color blobs in all training windows, center and resize them, and assign them to ac- tors. We cluster the blobs for all actors using a constrained agglomerative clustering. For every actor in n training images we get n set of blobs (f 1 , f 2 , ...., f n ) with varying number of blobs in each set, where each blob is represented as a 9 dimensional vector in normalized actor coordinates. An example of this process is illustrated in Fig 1 . Each blob in the first set f 1 is initialized as a singleton cluster. We then compute pairwise matching between those clusters and the blobs in the next set f 2 . At each step, for each cluster, we assign at most one blob (its nearest neighbor) if it is closer than a threshold. Each cluster is represented by the mean value of its blobs. Blobs not assigned to an existing cluster are assigned to their own singleton cluster. The process is repeated for all frames and for all actors. Finally, we eliminate the remaining singleton clusters. The cardinality of a cluster is the number of its occurrences in the training set. We interpret this value as a frequency, i.e. the probability of the cluster being visible in the actor. Note that the number of clusters per actor is variable. As a result, actors with more complex appearances can be represented with a larger number of clusters. The appearance models for eight different actors are shown in Fig 3.

Actor detection

Given the learned appearance models for a cast of actors, we now describe a framework for detecting them in any given video frame. Our framework searches for actors over a variety of scales, from foreground (larger scales) to background (smaller scales). For each actor we first perform a search space reduction using kNN-search. Then, we scan a sliding window and search for the most likely location for the actor. Then we perform a multi-actor non maxima suppression over all the detected actors. Finally, we report the best position and scale for each detected actor. The complete detection process is illustrated in Fig 5.

Search space reduction

Given an input frame first we calculate the maximally stable color regions over it as illustrated in This is further used to build inverted indices i.e. for each unique blob B ′ in the kNN refined set IDX, we store corresponding clusters in C a and respective distances, ensuring that the distance is less then a threshold τ 1 . This boosts the efficiency of the matching step in two ways. Firstly for each blob within the sliding window we only require to compare it with its corresponding entries in the inverted index table instead of doing an exhaustive search. Secondly, the distances in appearance are pre-calculated and distance in position D 2 can be directly added to calculate the full distance. An example of pre-refinement is illustrated in Fig 5(d). The figure shows the refinement for a particular scale but this is performed independently for each scale in sliding window search.

After the search space reduction, only sparse set of features remain for the matching step which leads to the speed up of the detection process in two ways, firstly many windows can be rejected without any processing using a importance term based on a binary map as shown in which can be efficiently implemented using integral images. Secondly, it reduces the number of matches to be performed by a large margin over a naive exhaustive matching. Notice that the number of required comparisons become independent of number of features in the image after the kNN refinement, which is done once in the beginning. Hence, the efficiency will go higher with increasing number of features. In addition to computational benefits, kNN refinement also makes the matching step much more robust by filtering out the background clutter, which is a major benefit while using low dimensional features like MSCR.

Sliding window search

We now proceed to define the detection scores for all actors at all positions and scales using a sliding window approach. Each actor detection score is based on the likelihood that the image in the sliding window was generated by the actor model using the previous frame detections as prior information. In practice we compute MSCR features in the best available scale and then shift and scale the blobs respectively while searching at different scales. Remember that the model was normalized to a fixed scale during training. During recognition, we similarly normalize the size, shape and position of blobs relative to the sliding window. This ensures that all computations are performed in reduced actor coordinates. The detection procedure is illustrated in Algorithm 1.

We represent B as the set of all blobs detected in the image and C a as the set of cluster centers in the model for a given actor a. Given a sliding window at position (x, y) and scale s, we find all blobs centered within the sliding window and assign the blobs indices J head and J shoulders . Using these indices and a matching function m ij , we define the score as:

score(x, y, s, a) = k ( j∈J k P (B j , m ij , a))
which is a product of parts, where each part is a sum of optional MSCR regions. Only two parts i.e. the head and the shoulder are considered in this case. The term P (B j , m ij , a) is the similarity function between the model cluster C a i and the corresponding matched blob B j in nine dimensional space (position, size, color and shape), which is defined as follows:

P (B j , m ij , a) = i H i •m ij •exp -(C a i -B j ) T Σ a i -1 (C a i -B j )
where C a i is the center for cluster i in the actor model and Σ a i is its covariance matrix. A distinctive feature of our detection framework is that it requires us to find a partial assignment m ij between blobs in the the sliding window and clusters in the model. More precisely, we compute m ij such that each blob in the sliding window is assigned to at most one cluster, each cluster is assigned to at most one blob, and the assignment maximizes the total likelihood k ( j∈J k P (B j , m ij , a)) of the matched blobs. Although potentially more computationally intensive, we have found that this method produces significantly better results than computing the average score over all possible blobto-cluster assignments, where the same blob may be assigned to multiple clusters, and the same cluster to multiple blobs, which is prone to detection errors. A key to our algorithm is therefore a fast approximate solution to the assignment/matching problem for evaluating the detection score benefiting from a pre-refinement step.

We further benefit from the previous frame detections D t-1 to modify the scores as follows:

score(x, y, s, a) = l 1,1 • score(x, y, s, a) • pr t,t-1 if a ∈ D t-1 l 0,1 • score(x, y, s, a) otherwise.
where, l 1,1 and l 1,0 measures the probability that the same actor is observed in consecutive frames. When the actor is not present in the previous frame, all positions in next frame are equally probable. When the actor is present in both frames, we assume the new position to be close to the previous position, within some covariance term Σ pos . Empirically, we have found that the terms l 1,1 , l 1,0 and Σ pos are in fact independent on the choice of actor or movie. The term pr t,t-1 is defined using the covariance term as follows:

pr t,t-1 = exp -(pt -p t-1 ) ′ Σ -1 pos (pt -p t-1 )
The above procedure is repeated for all actors individually and after non maximal suppression over score(x, y, s, a) we get the potential detections for each actor. Benefiting from the fact that an actor can only appear once on a frame, we then search for the best possible positions [x * (a), y * (a), s * (a)] which maximizes the total score over all actors. A threshold t 0 is used to reject all the detections with score below a threshold value.

Experiments

Dataset

As mentioned earlier the previous work in actor specific models have focused on obtaining tracks and then performing classification on the obtained tracks. And in datasets related to the re-identification problem, the bounding boxes are provided and the goal is only to identify the pedestrians. Our method on the other hand can perform direct detection using actor specific models, even on keyframes which is a much harder task than classifying tracks and we target the scenario where it is difficult to obtain face or upper body tracks.

Due to this reason, for a detailed evaluation of our method we propose the ROPE dataset 1 which is set of 1 http://imagine.inrialpes.fr/people/vgandhi/CVPR 2013/ Figure 7. Comparison of recall with increasing number of actors in UBD, CBD and combined cases keyframes at equal intervals, a frame every 10 seconds from the movie "Rope" [START_REF] Hitchock | The rope[END_REF] by Alfred Hitchcock. This dataset presents significant scale and viewpoint variations for each actor with presence of motion and focus blur. There is significant camera movement and constant background variations from flat regions to cluttered patterns. The lighting changes considerably during the movie and the clothing appearance of all the actors remains consistent which makes it suitable for our experiments. The movie is composed of a single shot and choosing a frame every 10 seconds gives about 443 frames. There are 8 different actors in the entire movie (except the initial victim and Alfred Hitchcock himself). All of them were considered in our experiments. The number of appearances per actor vary between 38 and 275. All 443 frames were hand labeled with the names and screen locations for all actors to serve as ground truth. Table 1. Actor identification results for all 8 actors in Rope dataset (percentages).

Results

A1

This section describes the results on the proposed dataset. We ran our detection and recognition algorithm using the built actor models, on all 443 frames and compared the results with the ground truth. Fig 6 shows the results on recall and precision of actor detection using the proposed method (CBD) and it is compared with the state of the art Upper Body Detector (UBD) 2 and the combined case where we merged the detections obtained from both the methods individually. Results demonstrate an increase in recall from about 57 percent in UBD to 70 percent in proposed Color blob detector (CBD) to about 81 percent in combined approach for a similar precision. Thus, the coverage is significantly improved keeping the same false positive rate. In Recognition results on the detected actors are presented in Table 5.2. As can be seen, our method not only increases the average recall rate for all actors, but also correctly names all actors with an average precision of 89 percent despite the large number of back views and partial occlusions. Some of the example detections results are shown in Fig 8 and they demonstrate how our method performs well even with severe cases of occlusions, viewpoint scale and pose variations in a multi actor scenario. Fig 9 shows some failure cases. Most failure cases are caused by insufficient illumination or severe occlusions. In 9(a) the blobs in the torso region of the undetected actor gets merged with the background, heavy blur causes mis-detection in 9(b), torso is largely occluded in 9(c). In fourth instance 9(d), the hand gets detected as the head and blobs below as torso, leading to a false detection. Note that there is very little temporal coherence between frames in our dataset. As a result, we cannot rely on context to resolve such problems. Detecting actors at a finer temporal scale (every second or every frame) may help alleviate the problem but that requires a stronger model of temporal coherence, taking into account the inter-frame motion of actors, the temporal coherence of the blobs, and the probability of visual events such as entrances and exits. This is left for future work.

(c) (d) (e) (f) (g) (h) (i) (j) (k) (l) (m) (n) (o)

Conclusions

We have presented a generative appearance model for detecting and naming actors in movies that can be learned from a small number of training examples. We have shown that low dimensional features like MSCR that were previously used for actor re-identification can also support actor detection, even in difficult multiple actors scenarios. Results show significant increase in coverage (recall) for actor detection maintaining high precision. To our knowledge, this is the first time that a generative appearance model is demonstrated on the task of detecting and recognizing actors from arbitrary viewpoints. Our method also appears to be a good candidate for tracking multiple actors constantly changing viewpoints and occluding each other in long video sequences such as "Rope", which include important application scenarios, such as unedited, raw video footage and recordings of live performances. We also plan to investigate weakly supervised methods by extracting actor labels from temporally aligned movie scripts [START_REF] Ronfard | A framework for aligning and indexing movies with their script[END_REF][START_REF] Cour | Movie/script: Alignment and parsing of video and text transcription[END_REF]. One obvious limitation of our method is that it only handles cases where the appearance of actors does not change much over time. In future work, we are planning to investigate extensions with mutually-exclusive appearances per actor, so that actors can change their appearances and costumes over time. Because each appearance requires so few training examples to be learned, we believe this extension is in fact possible.

Acknowledgment

This work was supported by Region Rhone Alpes (project Scenoptique), ANR Corpus (project Spectaclenlignes) and ERC advanced grant EXPRESSIVE.

Figure 1 .

 1 Figure 1. Illustration of training process of an actor, for each row (a) Given training frame. (b) Detected upper body and the MSCR features. The red window shows the upper body detection and green window shows the extended window to include the torso, when available. (c) The blobs chosen for training shown with the head and the torso partition. (d) The color blobs scaled and shifted to the normalized actor coordinate system which is represented by the red axis.

Figure 2 .

 2 Figure 2. Training images from different viewpoints are merged to obtain an actor model.

  Mrs. Wilson (e) Mrs. Atwater (f) Rupert (g) Mr. Kentley Figure

Figure 4 .

 4 Figure 4. Example of two independent randomly generated blob images given the actor and background models. (a) Brandon and Janet. (b) Brandon, Janet and Kenneth

  Fig 5(b) and Fig Algorithm 1 Detection and localization algorithm 1: Given actor models(C a , Σ a , H a ) and the image features B. 2: for each actor a do 3: for each scale s do 4: Normalize image features w.r.t scale.5: [IDX, D7] = kNN-SEARCH(B,C a ,k).

6 :

 6 Build inverted index i.e. for each unique blob B ′ in the Knn refined set, store corresponding clusters in C a and respective distances using IDX and D7.

7 :

 7 for each position (x, y) do 8: Find blob indices J head and J shoulders 9: Compute m ij using blob indices and inverted indices 10: score(x, y, s, a) = k ( j∈J k P (B j , m ij , a)) end for [x * (a), y * (a), s * (a)] = argmax a (score(x, y, s, a) -t0) 5(c). This gives us a initial set of blobs B over which we perform a refinement step using kNN search given the actor model and the particular scale. This pre-refinement is done only based on the color, size and shape parameters. The kNN-SEARCH(B,C a ,k), calculates k nearest neighbours in B for each cluster center in C a by performing an exhaustive search over the euclidean distances in the 7 dimensional space of appearance. It returns IDX and D 7 , both N × k matrices, where N is the number of clusters in the given actor model. Each row in IDX contains the indices of the k closest neighbours in B corresponding to the k smallest distances in D 7 .

Fig 5 Figure 5 .

 55 Figure 5. Illustration of the detection process. (a) Given Actor model. (b) Input frame and obtained detection for given Actor model with the proposed method. (c) MSCR features on the input frame. (d) Refined set of blobs for the given actor at given scale, based on appearance. (e) Binary map which can be used to reject some of the windows without processing, in practice we use separate binary maps for head and torso features. (f) The features in the image which were finally matched and considered for scoring for the final detection window as shown in (b). (g) The corresponding matched cluster centers in the given actor model.

Figure 6 .

 6 Figure 6. Comparison of results on recall and precision for actor detection using Upper body detector(UBD), Color Blob detector(CBD) and Combined method (UBD-CBD)

  [x * (a), y * (a), s * (a)] = argmax a (score(x, y, s, a) -t 0 )

Figure 8 .Figure 9 .

 89 Figure 8. Some detection results from Rope dataset using proposed method CBD (in red) with recognized actor names on top left, UBD (in yellow) and not detected by both (in green). Notice how our method is able to detect and identify the actors in the presence of multiple actors with partial occlusions [e.g. (a), (d), (e), (o)], varying viewpoint and posture [e.g. (f), (m), (g), (j)], varying illumination [e.g. (b), (l)], motion blur [e.g. (h)] etc.

Fig 7

 7 Fig 7 we plot recall rates for both UBD and CBD and combined case, with different number of actors present in the frame and it shows that the proposed method gives consistent results with varying number of actors.Recognition results on the detected actors are presented in Table5.2. As can be seen, our method not only increases the average recall rate for all actors, but also correctly names all actors with an average precision of 89 percent despite the large number of back views and partial occlusions. Some of the example detections results are shown in Fig8and they demonstrate how our method performs well even with severe cases of occlusions, viewpoint scale and

http://www.vision.ee.ethz.ch/∼calvin/calvin upperbody detector/


Remi Ronfard
email: remi.ronfard@inria.fr

Vineet Gandhi
email: vineet.gandhi@inria.fr

Laurent Boiron
email: laurent.boiron@inria.fr

The Prose Storyboard Language A Tool for Annotating and Directing Movies

Keywords: Applied computing [Arts and humanities]: Media arts Film Theory, Machinima, Context-Free Grammar, Timed Petri Net Virtual Cinematography

The prose storyboard language is a formal language for describing movies shot by shot, where each shot is described with a unique sentence. The language uses a simple syntax and limited vocabulary borrowed from working practices in traditional movie-making, and is intended to be readable both by machines and humans. The language is designed to serve as a high-level user interface for intelligent cinematography and editing systems.

INTRODUCTION

In movie production, directors often use a semi-formal idiom of natural language to convey the shots they want to their cinematographer. Similarly, film scholars use a semi-formal idiom of natural language to describe the visual composition of shots in produced movies to their readers. In order to build intelligent and expressive virtual cinematography and editing systems, we believe the same kind of high-level descriptions need to be agreed upon. In this paper, we propose a formal language that can serve that role. Our primary goal in proposing this language is to build software cinematography agents that can take such formal descriptions as input, and produce fully realized shots as an output [START_REF] Christie | Film Editing for Third Person Games and Machinima[END_REF][START_REF] Ronfard | A Review of Film Editing Techniques for Digital Games[END_REF]. A secondary goal is to perform in-depth studies of film style by automatically analyzing real movies and their scripts in terms of the proposed language [START_REF] Ronfard | A framework for aligning and indexing movies with their script[END_REF][START_REF] Ronfard | Reading movies: an integrated dvd player for browsing movies and their scripts[END_REF].

The prose storyboard language is a formal language for describing shots visually. We leave the description of the soundtrack for future work. The prose storyboard language separately describes the spatial structure of individual movie frames (compositions) and their temporal structure (shots). Our language defines an infinite set of sentences (shot categories), which can describe an infinite set of shots.

In film analysis, there is a frequent confusion between shots and compositions. A medium shot describes a composition, not a shot. If the actor moves towards the camera in the same shot, the composition will change to a close shot and so on. Therefore, a general language for describing shots cannot be limited to describing compositions such as medium shot or close shot but should also describe screen events which change the composition during the shot.

Our language can be used indifferently to describe shots in pre-production (when the movie only exists in the screenwriter and director's minds), during production (when the camera records a continuous "shot" between the times when the director calls "camera" and "cut"), in post-production (when shots are cut and assembled by the film editor) or to describe existing movies. The description of a entire movie is an ordered list of sentences, one per shot. Exceptionally, a movie with a single shot, such as Rope by Alfred Hitchcock, can be described with a single, long sentence.

In this paper, we assume that all shot descriptions are manually created. We leave for future work the important issue of automatically generating prose storyboards from existing movies, where a number of existing techniques can be used [START_REF] Brand | The "inverse hollywood problem": From video to scripts and storyboards via causal analysis[END_REF][START_REF] Veneau | From video shot clustering to sequence segmentation[END_REF][START_REF] Dony | Techniques for automated reverse storyboarding[END_REF][START_REF] Goldman | Schematic storyboarding for video visualization and editing[END_REF][START_REF] Gandhi | Detecting and naming actors in movies using generative appearance models[END_REF]. We also leave for future work the difficult problems of automatically generating movies from their prose storyboards, where existing techniques in virtual camera control can be used [START_REF] L.-W. He | The virtual cinematographer: a paradigm for automatic real-time camera control and directing[END_REF][START_REF] Christianson | Declarative camera control for automatic cinematography[END_REF][START_REF] Jhala | Representational requirements for a plan based approach to automated camera control[END_REF][START_REF] Christie | Camera control for computer graphics[END_REF].

PRIOR ART

Our language is loosely based on existing practices in moviemaking [START_REF] Thompson | Grammar of the Shot[END_REF][START_REF] Thompson | Grammar of the Edit[END_REF] and previous research in the history of film style [START_REF] Bordwell | On the History of Film Style[END_REF][START_REF] Salt | Film Style and Technology: History and Analysis[END_REF]. Our language is also related to the common practice of the graphic storyboard. In a graphic storyboard, each composition is illustrated with a single drawing. The blocking of the camera and actors can be depicted with a conventional system of arrows within each frame, or with a separate set of floor plan views, or with titles between frames.

In our case, the transitions between compositions use a small vocabulary of screen events including camera actions (pan, dolly, crane, lock, continue) and actor actions (speak, react, move, cross, use, touch). Although the vocabulary could easily be extended, we voluntarily keep it small because our focus in this paper is restricted to the blocking of actors and cameras, not the high-level semantics of the narrative.

We borrow the term prose storyboard from Proferes [START_REF] Proferes | Film Directing Fundamentals -See your film before shooting it[END_REF] who used it as a technique decomposing a films script into a sequence of shots, expressed in natural language The name catches the intuition that the language should directly translate to images. In contrast to Proferes, our prose storyboard language is a formal language, with a well defined syntaxx and semantics, suitable for future work in intelligent cinematography and editing.

Our proposal is complementary to the Movie Script Markup Language (MSML) [START_REF] Rijsselbergen | Movie script markup language[END_REF], which encodes the structure of a movie script. In MSML, a script is decomposed into dialogue and action blocks, but does not describe how each block is translated into shots. Our prose storyboard language can be used to describe the blocking of the shots in a movie in relation to an MSML-encoded movie script.

Our proposal is also related to the Declarative Camera Control Language (DCCL) which describes film idioms, not in terms of cameras in world coordinates but in terms of shots in screen coordinates [START_REF] Christianson | Declarative camera control for automatic cinematography[END_REF]. The DCCL is compiled into a film tree, which contains all the possible editings of the input actions, where actions are represented as subject-verb-object triples. Our prose storyboard language can be used in coordination with such constructs to guide a more extensive set of shot categories, including complex and composite shots.

Our approach is also related to the work of Jhala and Young who used the movie Rope by Alfred Hitchcock to demonstrate how the story line and the director's goal should be represented to an automatic editing system [START_REF] Jhala | Representational requirements for a plan based approach to automated camera control[END_REF]. They used Crossbow, a partial order causal link planner, to solve for the best editing, according to a variety of strategies, including maintaining tempo and depicting emotion. They demonstrated the capability of their solver to present the same sequence in different editing styles. But their approach does not attempt to describe the set of possible shots. Our prose storyboard language attempts to fill that gap.

Other previous work in virtual cinematography [START_REF] Shen | Intelligent digital filmmaker dmp[END_REF][START_REF] Jhala | A discourse planning approach to cinematic camera control for narratives in virtual environments[END_REF][START_REF] Friedman | Automated cinematic reasoning about camera behavior[END_REF][START_REF] O'neill | Towards intelligent authoring tools for machinima creation[END_REF][START_REF] Lino | Computational model of film editing for interactive storytelling[END_REF][START_REF] Markowitz | Intelligent camera control using behavior trees[END_REF] has been limited to simple shots with either a static camera or a single uniform camera movement. Our prose storyboard language is complementary to such previous work and can be used to define higher-level cinematic strategies, including arbitrarily complex combinations of camera and actor movements, for most existing virtual cinematography systems.

REQUIREMENTS

The prose storyboard language is designed to be expressive, i.e. it should describe arbitrarily complex shots, while at the same being compact and intuitive. Our approach has been to keep the description of simple shots as simple as possible, while at the same time allowing for more complex descriptions when needed. Thus, for example, we describe actors in a composition from left to right, which is an economical and intuitive way of specifying relative actor positions in most cases. As a result, our prose storyboard language is very close to natural language (see Fig. 6).

It should be easy to parse the language into a non ambiguous semantic representation that can be matched to video content, either for the purpose of describing existing content, or for generating novel content that matches the description. It should therefore be possible (at least in theory) to translate any sentence in the language into a sketch storyboard, then to a fully animated sequence.

It should also be possible (at least in theory) to translate existing video content into a prose storyboard. This puts another requirement on the language, that it should be possible to describe existing shots just by watching them. There should be no need for contextual information, except for place and character names. As a result, the prose storyboard language can also be used as a tool for annotating complete movies and for logging shots before post-production. Since the annotator has no access to the details of the shooting plan, even during post-production [START_REF] Murch | In the blink of an eye[END_REF][START_REF] Ondaatje | The Conversations: Walter Murch and the Art of Film Editing[END_REF], we must therefore make it possible to describe the shots in screen coordinates, without any reference to world coordinates.

SYNTAX AND SEMANTICS

The prose storyboard language is a context-free language, whose terminals include generic and specific terms. Generic terminals are used to describe the main categories of screen events including camera actions (pan, dolly, cut, dissolve, etc.) and actor actions (enter, exit, cross, move, speak, react, etc.). Specific terminals are the names of characters, places and objects that compose the image and play a part in the story. Non-terminals of the language include important categories of shots (simple, complex, composite), sub-shots and image compositions. The complete grammar for the language is presented in Fig. 9 in extended BNF notation.

The semantics of the prose storyboard language is best described in terms of a Timed Petri Net (TPN) where actors and objects are represented as places describing the composition ; and screen events (such as cuts, pans and dollies) are represented as Petri net transitions. TPNs have been proposed for representing the temporal structure of movie scripts [START_REF] Rijsselbergen | Movie script markup language[END_REF], character animation [START_REF] Magalhaes | Animation modeling with petri nets[END_REF][START_REF] Blackwell | Petri net script: a visual language for describing action, behaviour and plot[END_REF], game authoring [START_REF] Balas | Hierarchical petri nets for story plots featuring virtual humans[END_REF] and turn-taking in conversation [START_REF] Chao | Timing multimodal turn-taking for human-robot cooperation[END_REF]. Transitions in a TPN usually have non-zero duration. In some cases, transitions change the composition from an initial state to a final state. In those cases, the language does not attempt to describe the composition during the transition. In other cases, transitions maintain the composition while they are executed. Between transitions, the screen composition can be infered by inspecting the state of the TPN places (actors and objects ) and their attributes between successive screen events. This TPN semantics is useful for generating prose storyboards from movies, and for generating movies from prose storyboards. This will be described in future work.

IMAGE COMPOSITION

Image composition is the way to organise visual elements in the motion picture frame in order to deliver a specific message to the audience. In our work, we propose a formal way to describe image composition in terms of the actors and objects present on the screen and the spatial and temporal relations between them.

Following Thomson and Bowen [START_REF] Thompson | Grammar of the Shot[END_REF], we define a composition as the relative position and orientation of isual elements called Subject, in screen coordinates.

In the simple case of flat staging, all subjects are more or less in the same plane with the same size. Thus, we can describe this flat composition as follows: where Size is one of the classical shot size illustrated in Fig. 1 and Subject is generally an actor name. The Profile and Screen terms describe respectively the orientation and the position of the subject in screen space. See full grammar in Fig. 9 for more details.

In the case of deep staging, different subjects are seen at different sizes, in different planes. We therefore describe such shot with a stacking of flat compositions as follows:

<F l a t C o m p o s i t i o n > { , <F l a t C o m p o s i t i o n >} *
As a convention, we assume that the subjects are described from left to right. This means that the left-to-right ordering of actors and objects is part of the composition. Indeed, because the left-to-right ordering of subjects is so important in cinematography and film editing, we introduce a special keyword cross for the screen event of one actor crossing over or under another actor. Shot sizes are used to describe the relative sizes of actors independently of the camera lens as illustrated in Fig. 3.

The Screen term describe the subject position in screen coordinate. It allows to slightly modify the generic framing by shifting the subject position to the left or right corner as shown in Fig. 4. Thus, we can describe a more harmonious composition with respect to the head room and look room or the rules of thirds. We can also describe unconventional framing to create unbalanced artistic composition or to show other visual elements from the scene.

SHOT DESCRIPTIONS

Based on the taxonomy of shots proposed by Thomson and Bowen [START_REF] Thompson | Grammar of the Shot[END_REF], our prose storyboarding language distinguishes three main categories of shots :

• A simple shot is taken with a camera that does not move or turn. If the composition changes during a simple shot, it can only be the effect of actors movement relative to the camera.

• A complex shot is taken with a camera that can pan, tilt and zoom from a fixed position. We introduce a single camera action (pan) to describe all such movements. Thus the camera can pan left and right, up and down (as in a tilt), and in and out (as in a zoom).

• A composite shot is taken with a moving camera. We introduce two camera actions (dolly and crane) to describe typical camera movements. Panning is of course allowed during dolly and crane movements.

In each of those three cases, we propose a simplified model of a shot, consisting in a sequence of compositions and screen events. Screen events can be actions of the camera relative to the actors, or actions of the actors relative to the camera. A shot is therefore a sequence of compositions and screen events. Screen events come in two main categories -those which change the composition (events-to-composition) and those which maintain the composition (events-with-composition).

In our model, we can be in only one of four different states:

1. Camera does not move and composition that does not change. In case (1), the shot can be described with a single composition. In case (2), we introduce the special verb lock to indicate that the camera remains static while the actors move, leading to a new composition. In case (3), we use the constructions pan with, dolly with and crane with to indicate how the camera moves to maintain the composition. In case (4), we use the constructions pan to, dolly to and crane to to indicate how the cameras moves to change the composition, and we introduce a special verb continue to to indicate that the composition changes due to a combination of actor and camera movements. All three cases are illustrated in Fig. 5, Fig. 6 and Fig. 7.

EXPERIMENTAL RESULTS

As a validation of the proposed language, we have manually annotated scenes from existing movies covering different styles and periods. In this paper, we illustrate the prose storyboard language on a particularly difficult example, a short sequence from the single-shot movie Rope by Alfred Hitchcock, where actor and camera movements interfere to produce a rich and dynamic visual composition. The prose storyboard for the example is presented in Fig. 7 and Fig. 6. Despite the complexity of the scene, the prose storyboard is quite readable and was relatively easy to generate.

This example also illustrates how default values are used to describe simple cases. For instance, default values for a two-shot are supplied by assuming that the two actors are both facing the camera and placed at one-third and two-third of the screen. Such default values are stored in a stylesheet, which can be used to accommodate different cinematographic styles, i.e. television vs. motion pictures, or musical vs. film noir.

CONCLUSION

We have presented a language for describing the spatial and temporal structure of movies with arbitrarily complex shots. The language can be extended in many ways, e.g. by taking into account lens choices, depth-of-field and lighting. Future work will be devoted to the dual problems of automatically generating movies from prose storyboards in machinima environments, and automatically describing shots in existing movies. We are also planning to extend our framework for the case of stereoscopic movies, where image composition needs to be extended to include the depth and disparity of subjects in the composition. We believe that the proposed language can be used to extend existing approaches in intelligent cinematography and editing towards more expressive strategies and idioms and bridge the gap between real and virtual movie-making.

Figure 1 :

 1 Figure 1: Shot sizes in the prose storyboard (reproduced from [27]).

  <S i z e > on <S u b j e c t > [< P r o f i l e >][ < S c r e e n >] { and <S u b j e c t > [< P r o f i l e >][ < S c r e e n ] } *

Figure 2 :

 2 Figure 2: The profile angle of an actor defines his orientation relative to the camera. For example, an actor with a left profile angle is oriented with his left side facing the camera.

Figure 3 :

 3 Figure 3: Shot size is a function of the distance between the camera and actors, as well as the camera focal length.

Figure 4 :

 4 Figure 4: The horizontal placement of actors in a composition is expressed in screen coordinates.

Figure 5 :

 5 Figure 5: Two shots from the movie Back to the future with the description in Prose Storyboard Language (red) and their associated parse trees. Top : Simple Shot with a fixed camera. The composition changes due to actor movements. Bottom: Composite shot. The composition changes due to camera motion. In both examples the actors are named by the corresponding letters in green.

Figure 6 :

 6 Figure 6: Prose storyboard for two short sequences from the single-shot movie Rope.

Figure 7 :

 7 Figure 7: Floor plan view of the first sequence in Fig.6

Figure 8 :

 8 Figure 8: Artist sketch of the second sequence in Fig.6

  <Scene > : : = <Shot> * <Cue> : : = At <t i m e r e f > | As <Actor> <A c t i o n > | t h e n <Shot> : : = [ < t r a n s i t i o n >] t o [ <Camera >] <C o m p o s i t i o n > {<Fragment >} * <Fragment> : : = <Cue> (<RenameAction> | <ReframeAction >) <RenameAction> : : = ( l o c k | c o n t i n u e ) t o <C o m p o s i t i o n > <ReframeAction > : : = <CameraAction> ( t o | w i t h ) <C o m p o s i t i o n > <C o m p o s i t i o n > : : = [ < a n g l e >] {< F l a t C o m p o s i t i o n >}+ <F l a t C o m p o s i t i o n >::= < s i z e > on <S u b j e c t >[ < p r o f i l e > ] [ <s c r e e n >] { and <S u b j e c t >[ < p r o f i l e > ] [ <s c r e e n > ] [ i n ( back | f o r e ) ground ] } * <CameraAction >::= [ Speed ] pan [ l e f t | r i g h t | up | down ] | d o l l y [ i n | o u t | l e f t | r i g h t ] | c r a n e [ up | down ] <Speed> : : = s l o w | q u i c k | f o l l o w i n g :( < Actor >|< O b j e c t >) <S u b j e c t > : : = (< Actor >|< O b j e c t >)+ < t r a n s i t i o n > : : = c u t | d i s s o l v e | f a d e i n <a n g l e > : : = ( h i g h | low ) a n g l e < s i z e > : : = ECU |BCU|CU|MCU|MS| MLS | FS | LS | ELS < p r o f i l e > : : = 34 l e f t b a c k | l e f t | 3 4 l e f t | f r o n t | 3 4 r i g h t | r i g h t | 3 4 l e f t b a c k | back <s c r e e n > : : = s c r e e n ( c e n t e r | l e f t | r i g h t ) <A c t i o n > : : = <Look >|<Move>|<Speak >|<Use >|< C r o s s >|<Touch >|< React> <Look> : : = l o o k s a t <S u b j e c t > <Move> : : = moves t o <S c r e e n >|< P l a c e >|< S u b j e c t > <Speak> : : = ( s p e a k s | s a y s < s t r i n g >) [ t o <S u b j e c t >] <Use> : : = u s e s <O b j e c t > <C r o s s > : : = c r o s s e s [ o v e r | under ] <S u b j e c t > <Touch> : : = t o u c h e s <S u b j e c t > <React> : : = r e a c t s t o <S u b j e c t > <P l a c e > : : = from s c r i p t <Actor> : : = from s c r i p t <O b j e c t > : : = from s c r i p t

Figure 9 :

 9 Figure 9: EBNF grammar of the prose storyboard language.