Quentin Galvane

Rémi Ronfard

Christophe Lino

Marc Christie

Continuity Editing for 3D Animation

We describe an optimization-based approach for automatically creating well-edited movies from a 3D animation. While previous work has mostly focused on the problem of placing cameras to produce nice-looking views of the action, the problem of cutting and pasting shots from all available cameras has never been addressed extensively. In this paper, we review the main causes of editing errors in literature and propose an editing model relying on a minimization of such errors. We make a plausible semi-Markov assumption, resulting in a dynamic programming solution which is computationally efficient. We also show that our method can generate movies with different editing rhythms and validate the results through a user study. Combined with state-of-the-art cinematography, our approach therefore promises to significantly extend the expressiveness and naturalness of virtual movie-making. Jump Cuts Continuity errors Non-motivated shots and cuts Our solution Jump Cut Jump Cut left-to-right gaze direction screen

Introduction

The wide availability of high-resolution 3D models and the facility to create new geometrical and animated contents, using low-cost input devices, opens to many the possibility of becoming digital 3D storytellers. A convincing illustration is the rise of the machinima1 community, consisting in creating movies by relying on contents and rendering engines borrowed from computer games through ad-hoc techniques or dedicated modeling tools2 .

To date there is however a clear lack of accessible tools to easily create the cinematography (positioning the cameras to create shots) and perform the editing of such stories (selecting appropriate cuts between the shots created by the cameras). Creating a movie requires the knowledge of a significant amount of empirical rules and established conventions. In particular continuity editing -the creation of a sequence of shots ensuring visual continuity -is a complex endeavor. Most 3D animation packages lack continuity editing tools, calling the need for automatic approaches that would, at least partially, support users in their creative process [START_REF] Davis | Creativity support for novice digital filmmaking[END_REF].

Previous contributions in automatic film editing have focused on generative methods mixing artificial intelligence and computer graphics techniques. However, evaluating the quality of film editing (whether generated by machines or by artists) is a notoriously difficult problem [START_REF] Lino | How Do We Evaluate the Quality of Computational Editing Systems[END_REF]. Some contributions mention heuristics for choosing between multiple editing solutions without further details [START_REF] Christianson | Declarative camera control for automatic cinematography[END_REF] while other minimize a cost function which is insufficiently described to be reproduced [START_REF] Elson | A lightweight intelligent virtual cinematography system for machinima generation[END_REF]. Furthermore, the precise timing of cuts has not been addressed, nor the problem of controling the rhythm of cutting (number of shots per minute) and its role in establishing film tempo [START_REF] Adams | Toward automatic extraction of expressive elements from motion pictures: tempo[END_REF]. Most approaches yield a reactive style of editing known by professional editors as the dragnet style [START_REF] Murch | the blink of an eye[END_REF], which mechanically cuts to new speakers or actions.

In this paper, we propose a continuity editing model for 3D animations that provides a general solution to the automated creation of cinematographic sequences. Our model encodes the continuity editing process as a search for the optimal path through an editing graph. In this editing graph, a node represents a time-step (a temporal fragment of a shot), and an arc represents a transition between two cameras, going from a camera to either the same camera (no cut) or another camera (cut).

Our optimization uses dynamic programming to minimize, under a semi-Markovian hypothesis, the errors made along three criteria (see Figure 1): the quality of the shots (with respect to the unfolding actions), the respect of continuity editing rules and the respect of a well-founded model of rhythm (cutting pace). Semi-Markov models [START_REF] Murphy | Hidden semi-markov models[END_REF][START_REF] Yu | Hidden semi-markov models[END_REF]) have been used before in the context of information extraction [START_REF] Sarawagi | Semi-markov conditional random fields for information extraction[END_REF], speech generation [START_REF] Zen | A hidden semi-markov model-based speech synthesis system[END_REF]) and computer vision [START_REF] Shi | Discriminative human action segmentation and recognition using. semi-markov model[END_REF]. To the best of our knowledge, this is the first time they are suggested as a computational model for film editing.

Our contributions are: (i) a detailed formalization of continuity editing for 3D animation, encompassing a thorough number of visual properties and continuity rules (ii) an optimal algorithm for automatic editing in which parameters such as pacing can be controlled, thereby significantly increasing the expressiveness of editing tools, and (iii) a validation of our model through a user evaluation comparing the original edit of an existing movie with our optimal edit and Figure 1: Editing errors in a short sequence of a movie. From top to bottom: jump cut errors; breaking the continuity errors; nonmotivated shots and cuts. The last edit is the output of our system.

with degraded approaches.

Related work

The problem of generating movies from 3-D animation can be decomposed into the problems of (i) choosing shots and placing cameras (the cinematography problem), and (ii) deciding when to assemble those shots into a movie (the film editing problem). In this section, we review previous work on the film editing problem chronologically. [START_REF] Christianson | Declarative camera control for automatic cinematography[END_REF] introduce the declarative camera control language (DCCL) as a general framework for generating idiom-based solutions to cinematography and film editing problems. Film idioms [START_REF] He | The virtual cinematographer: a paradigm for automatic real-time camera control and directing[END_REF] are recipes for obtaining good cinematography and editing in any given situation, similar to cases in case-based reasoning. As a result, DCCL uses a conversation idiom for filming conversations, a fighting idiom for filming fights, etc. DCCL then builds a film tree, as a result of filming each scene in all available idioms, and includes a heuristic evaluator for checking the visual quality of sequences, choosing the one with the highest quality. The evaluation criteria are only briefly mentioned, and in comparison, we offer a full description of a scoring function that can be used to find optimal editing solutions using all available cameras in a principled and reproducible fashion. [START_REF] Tomlinson | Expressive autonomous cinematography for interactive virtual environments[END_REF] propose a fully automatic method for generating expressive cinematography. Their system uses autonomous cameras with emotional states and goals, that choose between a number of visual targets -such as a specific character, or two characters interacting with each other, or one character interacting with its environment. Though their system interestingly motivates the shots both emotionally and visually, the rules of montage (editing) are not enforced, and the pacing of the shots is re-solved by ad hoc rules. [START_REF] Kennedy | Planning animation cinematography and shot structure to communicate theme and mood[END_REF] directly address the problem of planning a complete sequence of shots for a given sequence of actions which must be known in advance. Users can choose between fast or slow editing in two different styles. Authors use a depth-first forward chained planner which can only evaluate a small number of possible plans and enforce a single continuity editing rule ("not crossing the line of action").

Unlike previous work, Darshak [START_REF] Jhala | Intelligent machinima generation for visual storytelling[END_REF]) takes as input an explicit declarative representation of the story goals, including all actions, causal links between actions, and ordering constraints. Story goals are defined in terms of a small number of dramatic situations, and a hierarchical partial-order causal link planner computes a camera plan, consisting of a sequence of shots that achieves the desired story goals. Darshak goes a long way into motivating the shots, but the actual cinematography and editing are not evaluated. Cambot [START_REF] Elson | A lightweight intelligent virtual cinematography system for machinima generation[END_REF]) is a movie-making system where the choice of shots is found as a solution to an optimization problem using dynamic programming. The scene is expressed as a sequence of nonoverlapping dramatic beats and their approach evaluates different placement of characters (blockings) and camera choices for each beat. Though we also make use of dynamic programming, our method is very different from [START_REF] Elson | A lightweight intelligent virtual cinematography system for machinima generation[END_REF]. Firstly, we search a much larger set of possible solutions, by evaluating a higher number of shot transitions at a finer level of granularity (every frame, rather than every beat). As a result, our method makes it possible to choose the precise cutting point between shots, and to maintain control over the rate of shot changes (cutting pace). Secondly, we describe in detail a cost function which implements an extensive set of film editing rules. Our cost function has a semi-Markov property which allows to efficiently optimize over this larger solution space. Thirdly, our method does not require the scene to be decomposed into a linear sequence of beats, and works equally well with overlapping actions and dialogues. [START_REF] Assa | The virtual director: a correlation-based online viewing of human motion[END_REF] propose a fully automated editing process that performs cuts in real-time between multiple cameras viewing human motions. The ranking between shots is computed by measuring for each camera the correlation between human motions in the 3D scene, and the on-screen 2D projection of these motions (the larger the correlation, the better the shot). A measure of erosion of the current view is employed to motivate the cuts between the viewpoints, while enforcing continuity rules (jump-cut and crossing the line of action). In a similar context of realtime cinematography, [START_REF] Lino | A real-time cinematography system for interactive 3d environments[END_REF] propose a system that automatically computes for each frame a collection of distinct viewpoints through spatial partitions. The editing process is then performed by encoding continuity rules as filtering operators that remove inconsistent viewpoints. [START_REF] Markowitz | Intelligent camera control using behavior trees[END_REF] extend the film idiom approach by replacing finite state machines with behavior trees. They enforce the 180 degree rule and the 30 degree rule, assuming a single line of interest at any given time in the scene. Similar to film idioms, their approach remains reactive, resulting in an editing style that immediately follows the action and cannot easily control the pacing or style of the editing.

System overview

In this paper, we cast the problem of film editing as an optimization problem over a space of semi-Markov chains. Our system takes as input a 3D animation scene, comprising a flow of world events, and a set of rushes taken from different cameras and covering the whole scene. We then rank possible edits on three key aspects: (i) how much shots convey unfolding actions, (ii) how much continuity editing rules are enforced and (iii) how much an input cutting rhythm is respected.

Given a 3D animated scene with arbitrarily complex actions a and a choice of rushes (i.e. unedited footage) from M cameras, a semi-Markov chain is a sequence of states (shots) s j with durations d j , chosen according to a probability model over s j , d j and a. The probability of the next shot s j+1 of duration d j+1 and starting at time t j+1 depends only on the previous shot s j and the actions a in the segment

[t j+1 , t j+1 + d j+1 ].
We here introduce the notion of editing graph, the graph of all possible shots and transitions. In this graph, a node represents a time-step (one frame) of a rush and an arc represents a transition from frame i of a rush (camera) to frame i + 1 of a rush (same or different). The output of our system is then a full edit list of the scene, computed as the continuous path through our editing graph minimizing the errors on these three key aspects.

The first input of our system is an ordered list of durative world events (that we refer to as actions), expressed in the form (subject, verb, object). In the following, we consider that the subject and object of all actions are characters, and we refer to the set of all characters as C. We use four main categories of actions: speaking actions performed by the character's mouth, reacting actions performed by the character's eyes, manipulating actions performed by the character's hands, and moving actions performed by the character's feet. As a result, a character can be the subject of at most four different actions at any given time and the object of an unlimited number of actions.

The second input of our system is a list of M rushes from different cameras filming the scene for a total duration of N video frames. We are agnostic about how the rushes are obtained. Though in this paper a number of cameras were placed manually by a human expert, they could equally be computed by an automatic camera planner such as [START_REF] Drucker | Camdroid: A system for implementing intelligent camera control[END_REF][START_REF] He | The virtual cinematographer: a paradigm for automatic real-time camera control and directing[END_REF][START_REF] Markowitz | Intelligent camera control using behavior trees[END_REF][START_REF] Elson | A lightweight intelligent virtual cinematography system for machinima generation[END_REF] or any other method.

The output of our system is a movie, described as an edit decision list (EDL) defined as a sequence of shots s j in the form of triplets (r j , t j , d j ). Note that in this paper, we only consider chronological EDLs where time is preserved (t j+1 = t j + d j ). In this limited context, the EDL can be reconstituted using the rush selection function r(t) which gives the rush index as a function of time.

We here propose to cast the editing process into a mathematical model accounting for three criteria: (i) how much shots convey unfolding actions, (ii) the continuity editing principles and (iii) the cutting rhythm of the movie. To do so, we use a log-linear model where the probability of choosing a particular sequence of shots s j is taken to be the exponential of a linear cost function C(s, a). The cost function C(s, a) is further decomposed into three terms which separately measure (i) errors in conveying unfolding actions in each shot, (ii) violations of continuity editing rules in each cut and (iii) errors in choosing shot durations.

C(s, a) = j tj ≤t≤tj +dj C A (r j , t) + 1≤j C T (r j-1 , r j , t j ) + j C R (d j )
In this equation, the first term is a sum over all frames of all shots of a cost function C A related to actions in the scene. The second term is a sum over all cuts of a cost function C T related to transitions between shots. Those two term are further decomposed into weighted sums of features, i.e.

C A (r j , t) = k w A k C A k (r j , t) and C T (r i , r j , t) = k w T k C T k (r i , r j , t).
The third term is a sum over all shots of a cost function C R related to editing rhythm. In the following sections, we explain each of those terms, and refer to the Appendix for mathematical details.

Symbolic projection

During the shooting of a virtual scene, all cameras capture images which are perspective projections of the world scene into their own frame of reference. In parallel to the computation performed by the graphics pipeline, we perform a symbolic projection of the actions which keeps a record of how much of the action is visible in each rush at every single frame. This is performed as follows. First, each action is decomposed into its constituents -verb, subject and object. Based on the verb category (speaking, reacting, moving or manipulating), we then compute the bounding boxes of involved body parts (e.g. mouth, eyes, hands and feet) of the subject and object characters. We then compute the screen size of their projection in each frame of a rush. 0 Second, to evaluate how much of these actions are visible, we compute the visible and occluded areas of characters. To do so, for each face f of each body part b of a character, we compute its projected size (or area) S(f, r, t) at time t in rush r. This projected size is measured relatively to the screen size, and comprises both the on-screen and off-screen projections of f . We then define the visible and occluded sizes of f as follows. Its occluded size O(f, r, t) corresponds to the cumulative size of its areas that are either occluded or appear off-screen, while its visible size V (f, r, t) is the complementary value computed such that S(f, r, t) = V (f, r, t) + O(f, r, t). We finally define the projected size and the visible size of each character c as the sum of corresponding values on each face of its body parts:

V (c, r, t) = b∈c f ∈b V (f, r, t)
This method is further easily extended to the case of non-character objects (we use their bounding boxes) and multiple-characters.

Narrative importance

To each action a holding at time t, a narrative importance I(a) is attributed depending on whether a is a foreground or a background action. We then firstly distribute the importance according to the different roles in the action (subject and object). Note that this defines the narrative importance of each character I(c, t) at time t. We secondly distribute the importance given to each role proportionally into the individual body parts of the character filling the role. For instance, in a speak action the subject's and object's visual targets are their heads; in a manipulate action the subject's visual target is its head and chest; in a move action, the subject's visual target is its full body. We finally non-uniformly distribute the importance of a body part on its front, back and side faces to obtain the narrative importance of each face I(f, t) of a character at time t.

Shot selection

Based on the symbolic and geometric data related to unfolding actions of a given frame, we rank every frame of every shot on three aspects: the action visibility, the action proximity and the action ordering (also known as the Hitchcock principle).

The action visibility term evaluates how much of unfolding actions is visible. To fully satisfy this criteria, each important body part of a character taking part in an unfolding action should be on-screen and fully visible. The cost associated to action visibility is computed as the sum, on each face f of each body part b of each character c, of the occluded proportion of the face weighted by its narrative importance:

C A V (r, t) = c∈C b∈c f ∈b I(f, t) • O(f, r, t) S(f, r, t)
The action proximity term evaluates how immersed the camera is in the unfolding actions, i.e. how much the screen is filled by actions. The cost (or penalty) associated to poor action proximity is then given by the proportion of the screen filled by the characters:

C A P (r, t) = 1 - c V (c, r, t)
The action ordering term evaluates how much the onscreen importance of a character matches its narrative importance. This is also known as the Hitchcock principle, which states that the size of a character should be proportional to its narrative importance in the story [START_REF] Truffaut | Truffaut/Hitchcock[END_REF][START_REF] Hawkins | Real-Time Cinematography for Games[END_REF][START_REF] Deloura | Real Time Cameras, A Guide for Game Designers and Developers[END_REF]). Our implementation considers all characters present in the scene, not just the characters present in each shot, or the characters participating in the main action. This has the benefit to easily rule out prominent shots of unimportant characters and favor prominent shots of important characters, focusing on its important body parts (mouth while speaking, eyes while reacting, hands while manipulating, feet while moving). The cost associated to the Hitchcock principle is computed as the sum of all deviations of the on-screen visibility of a character compared to its narrative importance:

C A H (r, t) = c∈C I(c, t) c I(c , t) - V (c, r, t) c V (c , r, t)

Continuity editing

We rank all possible transitions between rushes based on a computational model of continuity-editing. Continuityediting is the most commonly used editing style in filmmaking. It relies on a set of well established rules: avoiding jump cuts, enforcing the screen, motion and gaze continuity and maintaining the left-to-right ordering of on-screen characters [START_REF] Dmytryk | On Film Editing: An Introduction to the Art of Film Construction[END_REF][START_REF] Thompson | Grammar of the Edit[END_REF].

Jump cuts When the same character appears in two consecutive shots (i.e. before and after a cut), there must be sufficient change in either its apparent size or its profile angle in the two shots, so that the audience perceives the cut as a change in viewpoint, rather than a sudden change in the character's pose, also known as a jump cut. To prevent such cuts, we penalize such errors through a cost function over all characters appearing in successive shots, whose formula is detailed in Section Jump cuts of the appendix.

Screen, motion and gaze continuity

The main goal of continuity editing is to enforce continuity on screen positions, motion directions and gaze directions of all characters across the cut. To prevent discontinuities, we penalize them through a non-linear combination of the differences in screen position, gaze direction and motion direction of all characters appearing in successive shots. The formulas of these cost functions are detailed in Sections Screen continuity, Motion continuity and Gaze continuity of the appendix.

Left-to-right ordering The left-to-right ordering of characters is another important factor to enforce visual continuity. Characters whose relative screen positions are reversed after a cut appear to be jumping around, which attracts attention to the cut [START_REF] Smith | An Attentional Theory of Continuity Editing[END_REF]) -this criteria is also known as the 180 degree rule. For every pair of character (c, c ) appearing on-screen before and after the cut, we then penalize the reversion (cost=1) iff their oriented difference of onscreen position ∆P x (c, c ) (taken on the x axis) is of opposite sign. The overall cost on left-to-right continuity is then computed as the sum of this penalty on all pairs of character appearing on-screen before and after the cut. The formula of this cost function is detailed in Section Left-to-right ordering of the appendix.

Cutting rhythm

Cutting rhythm is an important element of film editing style [START_REF] Bordwell | On the History of Film Style[END_REF]. Cutting between cameras produces visual rhythm. Fast cutting as in an action scene can change cameras as often as every half second. The cutting rhythm has been studied extensively by film scholars [START_REF] Salt | Film Style and Technology: History and Analysis[END_REF][START_REF] Cutting | Attention and the Evolution of Hollywood Film[END_REF] who have shown that it is well approximated with a time-varying log-normal distribution of shot durations [START_REF] Limpert | Log-normal distributions across the sciences: Keys and clues[END_REF]. Parameters of the log-normal distribution are the mean µ and standard deviation σ of the log-transformed durations log d j , which result in a skewed distribution of durations with average shot length ASL = exp µ + σ 2 and variance V ar = exp 2µ + σ 2 (exp σ 2 -1) . Rather than making automatic decisions, our system is designed to let the user/director choose the average shot length (ASL) which dictates the rhythm of editing, and hence the editing style.

To enforce those values, we compute a cost measuring, for each shot s j of duration d j , the deviation of its duration from the log-normal distribution

C R (d j ) = (log d j -µ) 2 2σ 2 + log d j

Optimization-based film editing

We evaluate the cost of an arbitrary edit decision list of shots s j with a weighted sum of simple feature functions.

To do so, we use a dynamic programming approach to find the minimum cost solution by storing partial solutions [START_REF] Mitchell | On the complexity of explicit duration hmm's[END_REF][START_REF] Murphy | Hidden semi-markov models[END_REF].

We define B(r, t) to be the cost of the best sequence of shots ending at time t with a shot using rush r. One important result that follows from our choice of cost functions is the following recurrence relation

B(r, t) = min t0 < t r0 = r B(r 0 , t 0 ) + C T (r 0 , r, t 0 + 1) + t t =t0+1 C S (r, t ) + C R (t -t 0 )
In plain words, the best sequence ending on rush r at time (frame) t can be computed by comparing all combinations Rush 1 Rush 2

Rush 3

Rush 4 Rush M ...

t t3 t2 t1 t0 B(3,t)
Figure 3: Illustration of our dynamic programming algorithm, using semi-Markov decisions. The best edit in which a shot ends in Rush 3 at time t is computed as the best combination (drawn in red) of an edit in which a shot ends in Rush r0 = 3 at a prior time ti < t then a shot using Rush 3 between ti and t.

of a shot ending on rush r 0 at time t 0 < t, followed by a cut from rush r 0 to rush r between frames t 0 and t 0 +1, followed by a shot of duration t -t 0 using rush r (see Figure 3).

Using the above recurrence, we build the table of B(r, t) in time M 2 N 2 and space M N , where M is the number of rushes and N is the number of video frames. We additionally store a back-pointer to retrieve the actual path yielding the minimum-cost solution. Note that the method can also be used to retrieve sub-optimal solutions ending in other cameras. This can be useful in cases where the final shot is chosen by the director. To improve our system efficiency, we further restrain the search in our algorithm to a constant horizon H (longest allowable shot duration) of 30 seconds. This leads to compute a solution in time M 2 N H [START_REF] Mitchell | On the complexity of explicit duration hmm's[END_REF][START_REF] Murphy | Hidden semi-markov models[END_REF], which is sufficient for our purpose. For longer sequences with more rushes, an algorithm by [START_REF] Datta | On efficient viterbi decoding for hidden semi-markov models[END_REF] can be used to compute an exact and unbounded solution in time M N (M + N ).

Experimental results

To validate our approach, we have recreated the animation of a well-known scene from Robert Zemeckis' movie "Back to the future". The average shot length (ASL) in the original version is 6.6 seconds. The distribution of shot lengths in the original version is well approximated with a log-normal law of mode m = 2.28 and standard deviation σ = 0.82. This short (80 seconds) scene is a moderately complex interior scene, with four main characters, all engaging in a variety of actions, including two-way and three-way dialogues, physical contacts, and everyday activities such as sweeping the floor and serving food. All animations were manually annotated to provide (subject, verb, object) descriptions at the right time-codes. Twenty-five cameras were manually placed for the whole duration of the sequence (sixteen of them closely approximating the actual cameras from the original movie, and nine providing alternative angles).

The evaluation of editing is a general and challenging problem [START_REF] Lino | How Do We Evaluate the Quality of Computational Editing Systems[END_REF] since no ground truth is available for objective comparisons. As a consequence, the quality of an edit can only be measured subjectively through indirect user evaluations. Therefore, to demonstrate the soundness of our model, we have experimentally compared our method (O) to the original edit of the scene (Z) reproduced from Zemeckis' movie (which serves as a reference for comparison with expert cinematographers) and to three degraded versions: a degraded version (Ds) where the content of shots is not considered (i.e. the shot cost is removed), a degraded version (Dp) where the enforcement of the specified cutting rhythm is not considered (i.e. the rhythm cost is removed), a degraded version (Dc) where visual discontinuities are enforced (i.e. the cut cost is reversed).

We performed a subjective evaluation of our method by designing a perceptual user-study. Twenty-one participants volunteered for this experiment. They were 27.5 (± 5.7) years old (range: 20 to 42). They were naive with respect to the purpose of the experiment. All had normal or correctedto-normal vision. They gave written and informed consent and the study conformed to the declaration of Helsinki. We prepared 5 stimuli (a fully edited version of 80 seconds per method). Participants were asked to observe the video stimuli while seated in front of a desk. After each stimulus viewing, participants were asked to rank the global film-making quality3 on a discrete scale ranging from 0 (very bad) to 10 (very good). In total, they repeated this task 20 times (5×4 repetitions). Stimuli were presented in a randomized order. The total duration of the experiment was about 30 minutes.

We tested three hypotheses. H1: editing has an impact on the perceived quality of the observed video stimulus; H2: each of the three terms in our cost function (shot content, continuity rules and cutting rhythm) has a positive impact on perceived quality; H3: the perceived quality of the version done by an expert cinematographer is significantly higher than our method. The dependent variable in this study was the participants' score given to each version. Figure 4 illus-trates the scores obtained for each version.

Hypothesis H1 was confirmed using a non-parametric Friedman test (p < 0.05). Post-hoc comparisons summarized in Figure 4 confirm hypothesis H2 that the consideration of each of the three key aspects has a positive impact on subjective quality, but discard hypothesis H3 that the version done by an expert cinematographer is significantly better scored than the one generated by our system (though Zemeckis' version globally obtained better scores).

To further illustrate and validate our method, we have also generated two new versions of the scene with ASLs of resp. 2 seconds (fast cutting style) and 10 seconds (slow cutting style). The choice of shots is very different in those different styles. In fast cutting style, there is a preference for close-ups and medium shots. In slow cutting style, there is a preference for medium long shots and full shots. For evaluation purposes, we are making our experimental data (including rushes and their annotations) and our experimental results publicly available4 .

Limitations and future work

Our model is currently limited to the case of linear editing, where the chronology of events is maintained. In future work, we would like to remove this limitation by allowing temporal ellipses and re-ordering of events. Another limitation is that we are restricted to a limited choice of cameras. Future work is needed to optimize over camera positions and framings. In addition, the proposed model only enables to control the pacing. Other style parameters such as shot composition (flat vs. deep staging), camera movements (static shots, dolly shots, crane shots), transitions (reverse shots) and lighting preferences would favor user creativity. Our model of shot selection is based on bounding boxes of the character's body parts and a primitive classification of their actions. Objects and places in the scene, as well as character's moods and intentions, should also play a part. Finally, we should note that the semi-Markov assumption has limitations of its own. Important film editing patterns such as book-ending, separation or parallel action [START_REF] Sharff | The elements of cinema. Towards a theory of cinesthetic impact[END_REF]) cannot be taken into account by such a memory-less model. The investigation of higher-order Markov models or context-free grammars will be pursued to overcome such limitations.

Conclusion

In this paper, we have presented a continuity-editing approach to the automated creation of cinematographic sequences for 3D animations. We have introduced the notion of editing graph and showed how dynamic programming can be used to compute an optimal edit under a semi-Markov hypothesis. We have provided a thorough description of means to rank shots and edits, and to measure the distance to a specified cutting rhythm. Our solution is supported by subjective evaluations obtained in a perceptual user study. The proposed approach performs a clear shift from existing techniques such as idiom-based representations, with a level of expressiveness not addressed by previous contributions. Finally, this work provides the foundations to address novel challenges in automated cinematography, such as learning and reproducing cinematic styles from real-movies. where P (c, i) and P (c, j) represent the 2D screen position of character c resp. before and after the cut. φ S is a nonlinear function which takes as input the distance between both positions. It then returns the minimum penalty (0) for two identical positions, and the penalty increases with their distance.

Motion continuity

An illustration of the motion continuity rule is given in Figure 7. We penalize such a discontinuity by summing, on each single character, its change of apparent motion direction. Practically, this penalty is computed as follows

C T M (i, j, t) = c v(c) • φ M (M (c, i), M (c, j))
where M (c, i) and M (c, j) are 2D vectors representing the on-screen motion direction of character c resp. before and after the cut. φ M is a non-linear function which takes as input these two consecutive motion directions. It then returns the minimum penalty (0) when the two vectors are close enough (e.g. a character moving in a given direction keeps moving in a similar direction after the cut), and the penalty increases as these vectors differ from each other.

Gaze continuity

An illustration of the gaze continuity rule is given in

Left-to-right ordering

An illustration of the left-to-right continuity rule is given in Figure 9. We penalize such a discontinuity by summing, on each pair of characters (c, c ), their change in relative onscreen position (from left to right, this is also known as the 180 degree rule). To do so, we define a new weighting factor v(c, c ) computed as the product v(c) • v(c ) of the weights of both characters. We then give no importance to a pair of characters where at least one is off-screen either before or after the cut, little importance to a pair of background characters, and much importance to a pair of foreground characters. Practically, this penalty is computed as follows

C T L (i, j, t) =

  Figure 2: The relative narrative importance of a character is computed from all actions where it plays a role. It correlates with the screen size of the characters in both the Zemekis movie (linear correlation coefficient of 0.56) and our solution (0.73).

Figure 4 :

 4 Figure 4: The scores obtained by the five stimuli, each represented with a whisker plot. The central point represents the median score, the box represent the scores between the first and third quartiles, and the bottom and top lines represent the minimum and maximum scores.

  (a) Change in apparent size (b) Change in view angle (c) Insufficient change in both size and view angle

Figure 5 :

 5 Figure 5: Examples of cuts with sufficient change in size (top), sufficient change in view angle (middle), and an example of jump cut (bottom).

Figure 6 :

 6 Figure 6: Examples of cuts respecting (top) or violating (bottom) the screen continuity.

  . In a similar way to the motion continuity, we penalize such a discontinuity by summing, on each single character, its change of apparent gaze direction. Practically, this penalty is computed as followsC T G (i, j, t) = c v(c) • φ G (G(c, i), G(c, j))where G(c, i) and G(c, j) are 2D vectors representing the on-screen gaze direction of character c resp. before and after the cut. φ G is a non-linear function which takes as input these two consecutive gaze directions. It then returns the minimum penalty (0) when the two vectors are close enough (e.g. a character looking in a given direction keeps looking in a similar direction after the cut), and the penalty increases as these vectors differ from each other.

  c ) • φ L (L(c, c , i), L(c, c , j))where L(c, c , i) and L(c, c , j) are two real values representing the relative position of characters c and c resp. before and after the cut (practically, this relative position is computed as the signed difference of their on-screen horizontal coordinates). φ L is a non-linear function taking as input these two reals. It then returns the minimum penalty (0) when both values are of same sign (i.e. the relative position of characters is enforced) and the maximum penalty (1) when the two values are of opposite sign (i.e. the relative position of characters is reversed).

Figure 7 :

 7 Figure 7: Examples of cuts respecting (top) or violating (bottom) the motion continuity.

Figure 8 :

 8 Figure 8: Examples of cuts respecting (top) or violating (bottom) the gaze continuity.

Figure 9 :

 9 Figure 9: Examples of cuts respecting (top) or violating (bottom) the left-to-right ordering continuity (also known as 180 degree rule).

contraction of machine and cinema

see iClone http://www.reallusion.com/iclone/ or Moviestorm http://www.moviestorm.co.uk/ tools

We additionally proposed a number of criteria that participants could consider to score each version: the enhancement of characters performance, the synchronization of cuts with the scene content, the aesthetic of shots.

https://team.inria.fr/imagine/continuity-editing/

Rémi Ronfard, automated cinematographic editing tool, Xtranormal Technologies, May 2009.

Acknowledgments

The research presented in this paper benefited from the assistance of many people. Laura Paiardini and Estelle Charleroy created the assets and the animation for the example sequence. Adela Barbulescu helped create the facial animation. Anne-Hélène Olivier and Michael Gleicher gave precious help on experimental design and evaluation of the user study. We also thank the volunteers who participated in the user study.

A preliminary version of this work was developed by the second author as part of the patented Text-to-Movie application by Xtranormal Technologies 5 .

This work has been funded by the French Agency for Research (ANR) through projects CHROME and CINECITTA and the European Research Council (ERC) through the project EXPRESSIVE.

Appendix

We here provide the formulas of our cost functions related to continuity-editing rules. We first introduce v(c), a weighting factor defined as the minimum visible area of character c in two consecutive frames. In details, it is computed as follows

This factor is used to weight costs on each single character. We then give no importance to off-screen characters, little importance to background characters, and more importance to foreground characters (since they are the focus of attention).

Jump cuts

An illustration of the avoidance of jump cuts is given in Figure 5. We penalize a jump cut by summing, on each single character, the degree of similarity between the two frames before and after the cut. Practically, this penalty is computed as follows

where ∆S(c) and ∆θ(c) are the differences in resp. apparent size and view angle of character c between the two frames. φ J is a non-linear function taking these two parameters as input. It considers a minimum acceptable change in apparent size ∆S min , as well as a minimum acceptable change in view angle θ min (often set to 30 degree). φ J then returns the maximum penalty when no change occurs neither in apparent size nor view angle of character c, and the penalty decreases as the change in either apparent size or view angle increases.

Screen continuity

An illustration of the screen continuity rule is given in Figure 6. We penalize such a discontinuity by summing, on each


Carlos Canudas De Wit

Fabio Morbidi

Luis Leon Ojeda

Alain Kibangou

Iker Bellicot

Pascal Bellemain

Grenoble Traffic Lab: An experimental platform for advanced traffic monitoring and forecasting

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Grenoble Traffic Lab

An experimental platform for advanced traffic monitoring and forecasting Carlos Canudas de Wit, Fabio Morbidi, Luis León Ojeda, Alain Y. Kibangou, Iker Bellicot, Pascal Bellemain "The start from the Ocean House was something marvelous to see. The drivers stormed and scolded, the women shrieked and cried, wheels locked at intervals of perhaps ten minutes.

Occasionally, too, a carriage would capsize, and be hauled over to the fence for repairs . . . [It was] like a huge funeral procession, crawling along at a snail's pace. It was a feat to get to the city at all." This is the report of newspaper The Examiner of what happened when a multitude of attendants and their carriages turned to leave at the same time after the end of a horse race at Ingleside Race Track near San Francisco, California, on November 16, 1873, probably one of the oldest traffic jams on record. Nowadays, motor traffic jams in road networks occur regularly and have a critical impact on modern cities in terms of productivity loss, air pollution and wasteful energy consumption [START_REF] Schrank | TTI's 2011 Urban Mobility Report[END_REF]. According to the INRIX Traffic Scorecard Report [2], in 2013 French drivers wasted, on average, 35 hours in traffic, and France tied for third place with Germany in Europe, in terms of traffic jams (after Belgium and the Netherlands). The situation is not better in the United States, where the top three worst traffic cities in 2013 were Los Angeles, Honolulu and San Francisco where drivers have spent 64, 60 and 56 hours in traffic jams, respectively. In order to address the traffic issue, since the '80s intelligent transportation systems (ITS) have emerged to enhance the infrastructure efficiency and provide congestion relief. ITS applications, such as 1 dynamic route guidance with variable message panels, highway access control and travel-time forecasting, are now being employed successfully worldwide.

Several technologies are available today for collecting traffic data: stationary detectors such as Doppler radars, single and double inductive-loop detectors, laser, infrared sensors, magnetometers and video cameras, are now routinely used in the field, and they have being gradually supplemented by a growing amount of data obtained from mobile detectors or tracing vehicles: this includes continuous tracers (floating car data, FCD, i.e. satellite geolocalization, and floating mobile data, FMD, i.e. localization via the mobile-phone network), and point-to-point tracers (Bluetooth tags from telephones and onboard radios, radio-frequency identification for electronic toll collection, WiFi positioning system, WPS, i.e. localization from WiFi hotspots) [START_REF] Geroliminis | Existence of urban-scale macroscopic fundamental diagrams: Some experimental findings[END_REF]- [START_REF] Treiber | Traffic Flow Dynamics: Data, Models and Simulation[END_REF]. Data from stationary detectors, also known as "cross-sectional data", complements, in several respects, that coming from mobile detectors: in fact, while stationary sensors provide a better temporal coverage of traffic, continuous tracers are able to produce highly-accurate trajectories for single vehicles. However, the former are typically more expensive to install but easier to operate in the long term. The problems of fusing data from heterogeneous sources and of data assimilation have become increasingly important in recent years, and are the subject of active research, see [START_REF] Treiber | Traffic Flow Dynamics: Data, Models and Simulation[END_REF]Ch. 5.3] and [START_REF] Blandin | On sequential data assimilation for scalar macroscopic traffic flow models[END_REF]. Data assimilation is the process by which observations are incorporated into a model of a real system. It is a cyclic procedure: in each cycle, measurements of the current (and possibly past) state of a system are combined with the results from a model (the forecast) to produce an analysis, which is considered as the "the best" estimate of the current state of the system. The model is then advanced in time and its result becomes the forecast in the next analysis cycle [START_REF] Treiber | Traffic Flow Dynamics: Data, Models and Simulation[END_REF]. A major breakthrough in highway traffic modeling came from the discovery of a relationship between traffic density and flow at a certain location, through the fundamental diagram. This diagram is at the basis of the first fluid-dynamic macroscopic model proposed by Lighthill, Whitham and Richards in the '50s, the LWR model, for details, see "Fluid-Dynamic Macroscopic Models for Highway Traffic".

More recently, the cell transmission model (CTM) [START_REF] Daganzo | The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory[END_REF] and the related switching mode model (SMM) [START_REF] Munoz | Traffic density estimation with the cell transmission model[END_REF] have attracted considerable attention in the transportation and control literatures.

The SMM is a piecewise-affine state-dependent discrete-time system based on the CTM which is well suited for model-based traffic estimation [START_REF] Munoz | Traffic density estimation with the cell transmission model[END_REF]- [START_REF] Sun | A Distributed Local Kalman Consensus Filter for Traffic Estimation[END_REF] and control [START_REF] Sun | Highway traffic state estimation using improved mixture Kalman filters for effective ramp metering control[END_REF]- [START_REF] Ferrara | Freeways as Systems of Systems: A Distributed Model Predictive Control Scheme[END_REF]: in fact, it represents a good compromise between mathematical simplicity and modeling accuracy (see the second case study below).

In spite of the aforementioned technological and theoretical advances, the mathematical physics community, which has been developing increasingly-sophisticated dynamical traffic models, and the traffic engineering community, which is more concerned with the collection, statistical analysis and interpretation of real traffic data, have not been able to establish durable links and a common language so far. In particular, despite the numerous ITS initiatives worldwide, to the best of the authors' knowledge there do not exist, at present, easy-to-use experimental platforms which allow to test and compare the performance of advanced traffic management and monitoring algorithms on highway data. In order to fill this gap and provide a standardized testbed for the validation of new theoretical work, the NeCS team, a joint CNRS (GIPSA-lab) and Inria team-project, has recently developed the Grenoble traffic lab (GTL). A source of inspiration for GTL was Caltrans Performance Measurement System (PeMS) and Tools for Operational Planning (TOPL) [START_REF] Chow | TOPL: Tools for operational planning of transportation networks[END_REF], [START_REF] Kurzhanskiy | Active traffic management on road networks: a macroscopic approach[END_REF]. GTL is an innovative platform for online collection of traffic data coming from a dense wireless sensor network (130 magnetometers over 10.5 km) installed in the south ring of the city of Grenoble in France, "Rocade sud" in French. It is worth pointing out here that differently from a sophisticated and general-purpose system such as PeMS (which can be virtually operated in any road-network topology, directly imported from Google Maps), GTL works on a smaller scale and fully covers a single peri-urban corridor: however, this specificity constitutes also one of its distinctive strengths. GTL is the culmination of a four-year research effort and it became operative in winter 2013: the full potential of the system was demonstrated during a Show Day on traffic modeling, estimation and control, organized at Grenoble in May 2014.

The synergy with the local traffic authorities which endorsed the large-scale deployment of a novel sensor technology, and the characteristic daily congestion experienced at the interchange "Rondeau" (see Fig. 1), make the south ring of Grenoble well-suited for traffic studies and an attractive working environment for students, practitioners and researchers in the control, applied mathematics, and transportation communities.

The goal of this paper is to present the main functional components of GTL, with a special emphasis on traffic estimation and forecasting problems. Space constraints forced us to omit extensive research on ramp-metering control in the south ring, conducted with state-of-the-art traffic simulators [18]: for more details, the reader is referred to [START_REF] Pisarski | Optimal Balancing of Freeway Traffic Density: Application to the Grenoble South Ring[END_REF], [START_REF] Bianchi | Networked Model Predictive Traffic Control with Time Varying Optimization Horizon: The Grenoble South Ring Case Study[END_REF]. In what follows, we will proceed to describe in more detail the site of interest and the architecture of GTL.

After presenting the results of statistical analyses on the magnetometer data, we will focus on two relevant control systems applications, and conclude the article by highlighting some promising directions for future research.

Site of Interest and GTL Architecture

Grenoble covers an area of 18.13 km 2 and with a total population of 159953 (as of January 2014, source INSEE) is the 16th largest city in France. The city is relatively flat with an average elevation of 221 meters. The surface circulation is made difficult by the presence of mountains enclosing the city in the north, west, and south-east sides, and by the confluence of the Isère and Drac rivers in the north-west side in the direction of Lyon. These natural boundaries have prevented the construction of a highway surrounding the city, thus making vehicle circulation problematic especially during the peak hours: Grenoble was the third most congested city in France in 2013, with 41 hours wasted on average by the drivers in traffic [2].

The south ring of Grenoble, "route nationale 87", is a highway enclosing the southern part of the city from A41 to A480, completed in 1985. It consists of two carriageways with two lanes, it has 10 on-ramps and 7 off-ramps in the internal roadway, and it stretches between the satellite city of Meylan (45.20531 • N, 5.78353 • E), and the interchange Rondeau (45.15864 • N, 5.70384 • E), for an overall length of about 10.5 km, see Fig. 2. The south ring is a crucial transportation corridor for Grenoble. The total usage of both directions is about 90000 vehicles per day, with peaks of up to 110000. About 5% of the traffic is trucks. The highway is operated by the Direction Interdépartementale des Routes Centre-Est (DIR-CE) and the speed limit ranges between 70 km/h and 90 km/h. Because of its higher criticality for vehicular circulation and In the remainder of this section, we will describe the different functional levels of GTL.

The reader is referred to Fig. 3 for a workflow diagram of GTL architecture.

Level 1: Physical Layer

The south ring has been equipped with 54 pairs of Sensys Networks VDS240 3-axis wireless magneto-resistive sensors embedded in the middle of the fast/slow lanes 4.5 meters apart, plus 20 sensors in the on-/off-ramps (cf. Fig. 4 and Fig. 5, and I). Calibration issues related to the vehicle-counting task and problems of data consistency over time were also encountered, cf. the section "Platform Operation and Data Validation" below. I.

Level 2: Data Processing and Applications

Level 2 consists of an upper and lower layer, which are here described in detail. OPTICAL FIBER, "f", OR GPRS, "g".

• Upper layer: the raw macroscopic traffic data coming every 15 seconds from the Sensys magnetometers (see Level 1) are stored in a database and then passed through a suite of signal-processing algorithms (green box in Fig. 3), which perform:

-Imputation and diagnostics: if some data are lost or erroneous (for instance, as a result of communication problems or temporary sensor malfunction), suitable imputation algorithms [START_REF] Smith | Exploring Imputation Techniques for Missing Data in Transportation Management Systems[END_REF], [START_REF] Muralidharan | Imputation of Ramp Flow Data for Freeway Traffic Simulation[END_REF] are run for filling in the missing data with estimated values, see Level 3. In this respect, each magnetometer is evaluated not as a standalone but together with its neighbors and their past measurement history (see [START_REF] Ojeda | Short-term multi-step ahead traffic forecasting[END_REF] and "Vehicle counting" under "Data analysis" in [24]).

-Aggregation: high-resolution traffic data tend to be noisy. In order not to capture dynamics that are not physically meaningful, it is then fundamental to aggregate the data into time slots of 1, 5 or 6 minutes, depending on the scenario under investigation.

Even after the aggregation of the raw traffic data, high-frequency oscillations might still be present because of data-collection latency and intrinsic measurement noise: it may be then opportune to apply a low-pass filter with an appropriate cut-off frequency (e.g. a first-order low-pass Butterworth filter).

-Model calibration: if model-based algorithms are utilized in the lower layer for computing the traffic indicators (see below), the parameters of the (fluid-dynamic) models are automatically estimated from the data: for example, a least-squares based method inspired by [START_REF] Dervisoglu | Automatic calibration of the fundamental diagram and empirical observations on capacity[END_REF] is employed for computing the parameters of the fundamental diagram in the SMM, which is in turn used for traffic-density estimation.

• Lower layer: in this layer the pre-processed data is utilized to compute, at the present time [g/100km] emissions for an average family car and the safety index [s] (see the magenta boxes in Fig. 3). The fuel consumption and CO 2 emissions are estimated using a physicsbased modal consumption model [START_REF] Treiber | Traffic Flow Dynamics: Data, Models and Simulation[END_REF]Sect. 20.4] for a diesel-powered vehicle (61.3% of French private cars were diesel in January 2013, according to the INSEE), while for the NO x emissions we relied on the statistical modal model proposed in [START_REF] Int Panis | Modelling instantaneous traffic emission and the influence of traffic speed limits[END_REF]. Finally, the safety index is computed according to a constant time-headway spacing policy with a nominal time headway of two seconds as a reference [START_REF] Martinez | A safe longitudinal control for adaptive cruise control and stop-and-go scenarios[END_REF]. As it is known, the "twosecond distance rule" tells a driver the minimum distance needed to reduce the risk of collision with the vehicle directly in front, under ideal driving conditions: two seconds is a safety buffer, and the rule attempts to respect a distance which is consistent with human reaction time (approximately 1.5-2 s). For the sake of simplicity, the algorithms developed by the our group, are given in the forthcoming "Case studies" section.

Level 3: Results Display

The indicators computed by the algorithms in Level 2 can be visualized using different media, including a:

• Web interface: the interface includes four panels, see Fig. the user can select an on-ramp and an off-ramp of the south ring and compute the forecast arrival/departure times. Four alarms, in the form of flashing images, are also displayed in this portion of the interface. Finally, the lower-right panel, which has been partially built upon Google Maps, shows the collection points in the south ring, and the color-coded average traffic speed in each road segment. For demonstration purposes, the web interface is available at the address in [START_REF]GTL web interface[END_REF].

• Mobile device: an Android smartphone application called "GTLMobile" has been developed in collaboration with the Institut Carnot LSI of Grenoble, to display salient traffic information (forecast travel time and CO 2 emissions) to the drivers. The functionalities of the application have been defined by collecting the traveling preferences of over 200 commuters of the south ring via an online questionnaire.

• Showroom: the four panels of the web interface, plus additional diagnostic information about data quality (vehicle-counting performance), are displayed around the clock in seven monitors in a dedicated room at Inria Grenoble Rhône-Alpes.

Platform Operation and Data Validation

In this section we describe the traffic profiles of a typical weekday in the south ring, and present the results of a statistical data analysis that we conducted to test the performance of the network of magnetometers. These studies were instrumental in developing and setting up the GTL platform.

Analysis of Typical Traffic Patterns

In order to design effective and reliable traffic estimation and forecasting algorithms, it is crucial to be fully aware of the physical limits of the infrastructure and of recurrent traffic 3:00 in the morning and that four traffic regimes, R1, R2, R3, R4, can be identified in a typical working day (see Table II): regime R1 corresponds to light traffic conditions (early morning and late evening), R3 to the highway operating near the maximal capacity φ M , and R4 is relative to the morning and afternoon traffic peaks, where speed drops below 40 km/h. Finally, in the intermediate regime R2, the traffic load is moderate (see also "Speed calendar" under "Data analysis" in [24]). The four regimes are also displayed in Fig.

Ä φ -c v -d ä a ä
, where a (even), b, c, d are positive parameters to be determined. The tip of this curve approximately represents the maximal capacity of the highway at location 16, i.e. the maximal number of vehicles that can cross this location in one hour.

Magnetometers Versus Inductive-Loop Detectors: Performance Comparison

In order to assess the performance of the magnetic sensors, we compared the flow/speed measurements of Sensys magnetometers with the corresponding measurements of two SIREDO inductive double-loop detectors which belong to a nation-wide traffic-monitoring network [START_REF]' Écologie du Développement durable et de l' Énergie[END_REF].

These two detectors, which are not part of the GTL platform, are located between collection points 9 and 10, and 11o and 12, at 4.319 km and 5.9 km from Meylan, respectively.

They cover the fast and slow lanes, and provide independent flow, speed and occupancy measurements, with an aggregation time of 6 minutes. In our tests, we considered the days between September 2 and September 20, 2013, weekends excluded. During the working hours : however, the data from the loop detectors appeared to be, overall, more correlated and smoother. These findings are consistent with previously published studies [START_REF] Su | Evaluation of Sensys Networks Equipment: Stage 3, Tests on Monash Freeway[END_REF]- [START_REF]Count Accuracy Assessment of the Sensys TM Wireless Vehicle Detection System by the Texas Transportation Institute[END_REF].

Flow-Error Analysis

An additional test was performed to assess the counting performance of Sensys magnetometers in the south ring. In order to make the presentation of the results precise, it is convenient to introduce here some terminology regarding network flow theory [START_REF] Rockafellar | Network Flows and Monotropic Optimization[END_REF]. A network G is a triple consisting of two sets E and N , the set of arcs and of nodes, respectively, and a function that assigns to each j ∈ E a pair (i 1 , i 2 ) ∈ N ×N such that i 1 = i 2 . Node i 1 is called the initial node of j and i 2 the terminal node. The arc j is said to be incident to i 1 and i 2 , where these nodes, by virtue of the existence of such an arc, are said to be adjacent to each other. We henceforth Mathematically, the flow of an arc j is a real nonnegative number which we denote by φ j .

In order to analyze what happens to a flow at a certain node i, in particular if the node "leaks", it is useful to introduce the notion of divergence. Given a network G, the divergence of the flow at node i ∈ N , denoted by y i , is the quantity y i = j ∈ E e ij φ j , that is, the total flow departing from node i minus the total flow arriving at i. Let φ = [φ 1 , . . . , φ m ] T be the flow vector. A node i is said to be a source for the flow vector φ if y i > 0 and a sink if y i < 0. If y i = 0, the flow is conserved at i. Note that if we call y = [y 1 , . . . , y n ] T the divergence vector associated with the flow vector φ, we have that y = E φ. In a network, the total amount of flow created at the sources always equals the total amount destroyed at the sinks. This is expressed by the total divergence principle:

i ∈ N y i = 0 for y = E φ.
The flows φ in G such that E φ = 0, i.e. φ is conserved at every node, are called circulations (note that analogously, in physics, a vector field with constant zero divergence is called incompressible or solenoidal). The set of all circulations forms a linear subspace of IR m , the circulation space C = ker(E), where ker(•) denotes the kernel of a matrix.

Let us now return to the task of evaluating the counting performance of the magnetometers in the south ring of Grenoble. Consider the graphical representation of the south ring in Fig. 5(b), and assume that the 26 Sensys collection points represent the nodes of a network G SR and the arrows the arcs of G SR (through which vehicles flow). It is then easy to verify that the incidence matrix E of G SR has 26 rows and 70 columns, from which we can compute the daily divergences in the south ring by using the measured daily flows φ j , j ∈ {1, 2, . . . , 70}. In order to simplify the analysis, let us introduce the relative divergence of the daily flow at location i (in %)

y % r,i = 100 × y i max ¶ | j ∈ E : e ij = -1 e ij φ j | , j ∈ E : e ij = 1 e ij φ j © .
Note that according to this definition, y % r,i is a signed quantity. Unfortunately, we will never have y % r,i = 0 in the real world, since a counting error will always be present, due to the technological limitation of sensors or to vehicles stuck in a road section: we can then only hope that |y % r,i | < γ, ∀ i, where γ is a suitable small threshold. From an inspection of Table III in which we reported the average, standard deviation, minimal and maximal relative divergence of the daily flow over 10 days in February 2014 (because of the space constraints, Table III does not show the flow of all days), we can notice that except for two locations in which environmental disturbances and vehicle lane-changing are important sources of uncertainty, the absolute value of average relative divergence is always smaller than 7%, see "Vehicle counting" under "Data analysis"

in [24]. The counting performance appeared to significantly depend on the sensor calibration accuracy and, notably, on the sensitivity threshold over the three axes of the magnetometers.

Case studies

GTL provides direct access to real traffic data, which allows, in turn, to synthesize and test new algorithms with unprecedented rapidity and accuracy. In this section we report two examples of recently-developed algorithms which use tools of control systems theory: the first one relies on the adaptive Kalman filter and speed measurements for short-term multi-step ahead travel-time forecasting [START_REF] Ojeda | Online Dynamic Travel Time Prediction using Speed and Flow Measurements[END_REF], and the second one leverages a Luenberger-like observer based on the CTM for traffic-density estimation [START_REF] Canudas De Wit | Graph Constrained-CTM observer design for the Grenoble south ring[END_REF] in the south ring. The development of these algorithms has greatly benefited from the unique features of the GTL platform.

Multi-Step Ahead Travel-Time Forecasting

The problem of highway travel-time forecasting has been widely studied and several solutions have been proposed in the literature depending on how the available historical and current-time traffic information is handled [START_REF] Lin | A Gaussian maximum likelihood formulation for short-term forecasting of traffic flow[END_REF]- [START_REF] Ojeda | Adaptive Kalman Filtering for Multi-Step ahead Traffic Flow Prediction[END_REF]. In this section, we briefly present the main features of a novel travel-time forecasting algorithm based on the noise-adaptive Kalman filter (AKF) (for further details, see [START_REF] Ojeda | Short-term multi-step ahead traffic forecasting[END_REF], [START_REF] Ojeda | Online Dynamic Travel Time Prediction using Speed and Flow Measurements[END_REF]). Our algorithm considers progressive traffic conditions, i.e. it accounts for the spatial and temporal conditions encountered by a potential driver along the road, for details, see "Travel Time Forecasting". Fig. 9 shows the main functional blocks of the forecasting algorithm. Three typologies of data, obtained from the available speed measurements, feed the algorithm: the historical travel-time information ("Historical data") from all M = 21 links of the south ring (a link is defined as the stretch between two collection points, recall Table I), the travel-time information at present time k p in the link i, and the travel-time information from midnight of the current day up to time k p in the link i ("Sameday past data"). In order to reduce spatial complexity and maximize correlation, the historical data has been clustered into five time zones (00:00-7:00, 7:00-10:00, 10:00-16:00, 16:00-19:00, and 19:00-24:00) using the standard k-means algorithm (as a preliminary step, a separation into working and non-working days, i.e. Sundays and holidays, is also performed). The clustered data are used to produce pseudo-observations via two predictors which rely on the average of historical data, and on the data at the present time and historical increment, respectively, and to estimate the covariance matrix of the observation noise R(k) ∈ IR 2×2 for k ∈ {k p , k p + 1, . . . , k p + H}, where H is the forecasting horizon. Note that by introducing pseudo-observations the forecasting problem is conveniently converted into a standard filtering problem. Matrix R(k) and the covariance of the process noise q(k) ∈ IR, which is estimated from the forcing residuals [39, Sect. minutes. From the figures, we notice that the proposed method always outperforms the average of historical data, and that the congestion build-up and phase-out times are correctly captured by the algorithm. For cross-validating the proposed algorithm, let us now introduce the estimated cumulative travel time from the current link i to the destination link j (i = j ∈ {1, 2, . . . , M}) at when k p varies between 6:00 and 22:00 for 15 working days. As it is evident in Figs. 11(a)-(c), the smaller H the more accurate the forecasting: moreover, although the performance of the proposed algorithm is always comparable or superior than that obtained with the historical average, for large H, as expected, the differences between the two approaches become negligible.

Traffic-Density Estimation

In this final section, we illustrate the performance of a recently-developed Luenbergerlike traffic density estimator based on the graph-constrained SMM: for the detailed mathematical formulation, the reader is referred to [START_REF] Canudas De Wit | Graph Constrained-CTM observer design for the Grenoble south ring[END_REF], [START_REF] Morbidi | Robust mode selection for highway traffic density estimation[END_REF], [START_REF] Ojeda | Short-term multi-step ahead traffic forecasting[END_REF]. The south ring has been subdivided in 48 cells with average length of 220 meters and the density in each cell has been reconstructed using the model-based observer and the available flow measurements: the data have been aggregated to 1 minute and then resampled to 5 seconds, and the SMM has been automatically calibrated using a robust algorithm similar to the one proposed in [START_REF] Dervisoglu | Automatic calibration of the fundamental diagram and empirical observations on capacity[END_REF], cf. "Level 2" above. Figs. 12(b),(d) show the density contour estimated by the proposed observer on Friday, February 28, 2014 (the eve of French student holidays, when the south ring was heavily congested all afternoon), and on Friday, March 7, 2014, respectively. Figs. 12(a), (c) report the corresponding measured densities, that is the densities reconstructed from the available flow and speed measurements in the collection points of the south ring (our ground truth). The gray vertical stripes in Fig. 12(a) correspond to three collection points (Meylan, Gabriel Péri entrance 1, SMH Centre exit) which were not operative on February 28. In spite of the missing data, we observe a satisfactorily agreement between the measured and estimated densities.

Conclusions and Future Work

In this article we have described the Grenoble traffic lab (GTL), a novel experimental platform for advanced traffic research, and we have presented some activities built around it that our group has recently carried out.

GTL is an ongoing and living research project, which serves as a basis for more ambitious forthcoming undertakings: in the near future, we aim at customizing the GTL web interface for Researcher successively with the I3S Laboratory, Sophia Antipolis, the LAAS, Toulouse, and the GIPSA-lab, Grenoble. His research interests include distributed estimation, structural network analysis, multiway array data analysis, signal processing for communications, traffic prediction, system identification, nonlinear filtering, and consensus problems. This potentially makes the magnetometer as accurate as or better than an inductive loop detector at counting vehicles. However, magnetometers are not precise at locating the perimeter of a is the time at which the vehicle reaches the upstream boundary of rectangle i. Note that (S3) accounts for the traffic progression along the road. Equations ( S2) and (S3) define the progressive travel time (PTT). This differs from the instantaneous travel time (ITT), frequently encountered in the literature, which assumes that the conditions in each rectangle remain the same as at the entry time t p , i.e. t 0 = t p + n i=1 Δ x i v i (tp) (in other words, time is "frozen"). Note that while the PTT is consistent with the traffic conditions that a driver encounters along the road, the computation of ITT is based on an assumption that is not necessarily verified in the real world, and which becomes more critical as the width of the rectangles Δ x i increases. Let us now determine the forecast arrival time t f of the vehicle at the point x f , given the current time t 0 and current position x 0 (see Fig. S2). By using (S2) and (S3), and assuming a space discretization in M rectangles, we obtain

t f = t 0 + M i=1 Δ x i v i ( η(Δ x i )) , η(Δ x i ) = t 0 + i-1 j=1 Δ x j v j ( η(Δ x j ))
. By defining τ i (k) as the forecast PTT in rectangle i at the discrete time k, and τ x 0 →i (k) as the cumulative PTT from the entry point x 0 to the downstream boundary of rectangle i at the discrete time k, we

find τ x 0 →i (k) = τ x 0 → i-1 (k) + τ i (k + τ x 0 → i-1 (k)), τ i (k) = Δ x i v i ( τ x 0 → i-1 (k))
where i ∈ {1, . . . , M}, k ∈ {k 0 + 1, . . . , k 0 + H} and H is the forecasting horizon.

Figure 1 .

 1 Figure 1. The south ring of Grenoble. (a) View of a stretch of the south ring, direction north-east

  Figure 2. Traveling the south ring of Grenoble. (a) Spatial trajectory, and (b), (c) time

3 Figure 3 .Figure 4 .

 334 Figure 3. Three-level architecture of GTL. Level 1: physical layer, Level 2: data processing

Figure 5 .

 5 Figure 5. Sensor disposition in the south ring. (a) Location of the collection points, blue flags

  and in the future, several traffic indicators: the travel time [min], the number of vehicles, the congestion length [km], the fuel consumption [L/100km], and CO 2 [kg/100km], NO x

  that generate the aforementioned indicators are coded as Simulink blocks: MEX files are used to interface the blocks with the database on one side and with the result-visualization tools (see Level 3, below) on the other. The MATLAB/Simulink environment offers great flexibility and modularity, and allows the user to easily add or delete connections between the blocks and implement new traffic-management algorithms. The instantaneous and forecast indicators yielded by our Simulink blocks are stored in a dedicated database. More details about two algorithms for traffic density estimation and travel-time forecasting recently

6 .Figure 6 .

 66 Figure 6. The four panels of GTL web interface. Clockwise from top left: 1) gauges displaying

patterns. Fig. 7 (Figure 7 .

 77 Figure 7. Typical traffic patterns in the south ring. (a) Speed contour of January 16, 2014:

  7(c), where we plotted vehicle speed against traffic flow (red dots) for five weekdays, January 7, 8, 9, 10 and 16, 2014, at location 16. The black curve in the figure has been obtained via least-squares fitting using an (implicit) exponential function of flow and speed, F (φ, v) = a exp Ä -b

( 8 :

 8 00-18:00), we observed a good matching between the average-flow (Figs. 8(a), (c)) and average-speed measurements over the 15 days (Figs. 8(b), (d))

  assume that |N | = n and |E| = m, where | • | denotes the cardinality of a set. The node-arc incidence matrix E = [e ij ] of G is defined as follows: e ij = 1 if i is the initial node of the arc j, e ij = -1 if i is the terminal node of the arc j, and e ij = 0 otherwise. Note that E is an n × m matrix, and that each column of E has exactly one +1 and one -1. The flow of an arc is a variable that measures the quantity of material flowing through an arc of the network.

Figure 8 .

 8 Figure 8. Magnetometers versus inductive-loop detectors. Comparison between the measure-

Figure 9 .

 9 Figure 9. Block diagram of the traffic forecasting algorithm based on the Kalman filter from [23].

4. 7 ]

 7 , are used to compute a revised gain K(k) ∈ IR 2×2 for the Kalman filter which outputs the estimated travel-time τ i (k) in link i for k ∈ {k p , k p + 1, . . . , k p + H}. Fig. 10 reports the results of several tests that we conducted under typical traffic conditions. In particular, Figs. 10(a), (c) show the forecast travel time provided by the proposed method (purple solid, circle) against the travel time computed from a simple average of the historical data (blue dashed, cross), and the ground truth (black solid, star) at k p = 8 : 45 on September 17, 2013 and at k p = 17 : 15 on September 11, 2013, respectively. Figs. 10(b), (d) report the corresponding forecast trajectories in the (space, time)-speed plane against the ground truth for departure times at intervals of 15

Figure 10 .

 10 Figure 10. Performance of the travel-time forecasting algorithm. (a) Forecasting at k p = 8 : 45 on September 17, 2013 (the forecasting step and horizon H are 5 and 45 minutes, respectively),

Fig. 11 reportsFigure 11 .

 1111 Fig. 11 reports the cumulative distribution function (CDF) of the APE for different forecasting horizons H's using the proposed algorithm (black) and the average of historical data (red),

•

  scheme[S2]. The discrete version of the LWR model with triangular fundamental diagram, is

Figure S1 .Figure S2 .

 S1S2 Figure S1. From right to left: perturbation of Earth's magnetic field (red lines) produced by a

Table I

 I

	), for details, see
	"How Do Magnetic Sensors Detect a Passing Vehicle?". The magnetometers have a sampling rate
	of 128 Hz and are powered with non-rechargeable primary lithium thionyl chloride (Li-SOCl 2 )
	3.6 V, 7.2 Ah batteries which guarantee 10 years of operation and up to 300 million vehicle
	detections. The magnetometers provide macroscopic information, such as flow φ [veh/h], time-
	mean speed v [km/h] and occupancy [%] (the fraction of time during which the cross-section
	is occupied by a vehicle) as well as microscopic information, such as single-vehicle speed,
	inter-vehicle time gap and vehicle length. The latter piece of information can be used, for
	example, for safety or vehicle-class distribution analyses: however, for the sake of simplicity,
	in the rest of this article we will exclusively deal with macroscopic data. Notice that since
	φ = ρ v, the density ρ [veh/km] can be estimated from the available flow and speed measurements.
	The magnetometers use an ultra-low power 2.4 GHz TDMA protocol to communicate with a
	nearby access point (configured and remotely operated with Sensys software "TrafficDOT2"),

Traffic regime Flow [veh/h] (2 lanes) Aver. speed [km/h] Approx. time interval

	R1, Light	0 ≤ φ < 1500	v > 60	21:00-7:00
	R2, Fluid	1500 ≤ φ < 2500	v > 60	9:30-13:00, 19:00-21:00
	R3, Intense	2500 ≤ φ ≤ φ M	v > 60	13:00-17:00
	R4, Congested	1500 ≤ φ ≤ φ M	v ≤ 60	7:00-9:30, 17:00-19:00

TABLE II THE

 II FOUR TRAFFIC REGIMES IN THE SOUTH RING.

15 Feb. 16 Feb. 17 Aver. Std

										Min Max
	1 → 2	n.a.	n.a.	• • •	n.a.	n.a.	n.a.	n.a.	n.a.	n.a.	n.a.
	2 → 3	0.1	0.5	• • •	0.9	0.1	0.4	0.04 0.57	-0.8	0.9
	3 → 4	0.5	-0.03 • • •	0.5	0.3	0.5	0.33 0.23 -0.04 0.7
	4 → 5	-0.1	0.1	• • •	0.1	-0.05	0.02	0.01	0.1	-0.19 0.1
	5 → 6	0.9	0.3	• • •	-7.6	0.2	-1.2	-0.94 2.51	-7.6	0.9
	6 → 7	n.a.	n.a.	• • •	n.a.	n.a.	n.a.	n.a.	n.a.	n.a.	n.a.
	7 → 8	n.a.	n.a.	• • •	n.a.	n.a.	n.a.	n.a.	n.a.	n.a.	n.a.
	8 → 9	-0.5	0.8	• • •	-13.6	-0.5	-3.4	-6.31 6.54 -15.4 0.8
	9 → 10	0.1	0.01 • • •	-0.2	-0.3	-0.2	-0.19	0.2	-0.5	0.1
	10 → 11	-0.6	-0.4	• • •	-0.1	-0.4	-0.6	-0.39 0.16	-0.6 -0.1
	11 → 11o	-2	-1.4	• • •	-1.9	-1.4	-0.4	-1.6	0.44	-2	-0.4
	11o → 12	2.9	2	• • •	2.4	2.1	0.8	2.14 0.52	0.8	2.9
	12 → 13	0.2	-0.04 • • •	0.1	0.2	0.1	0.01 0.23	-0.5	0.2
	13 → 14	-1.7	-1.5	• • •	13	-0.4	1	4.43 6.48	-1.7 13.2
	14 → 15	-3.1	-1.8	• • •	-14	-1	-4.9	-8.23 7.03	-19	-1
	15 → 15o	-1.3	-0.2	• • •	0.02	-0.04	-1.3	-0.75 0.53	-1.3 0.02
	15o → 16	0.4	0.2	• • •	0.2	-0.2	0.4	0.23 0.23	-0.2	0.6
	16 → 17	0.1	0.7	• • •	-11.5	-1	-2.1	-5.23	6.1	-13.7 1.7
	17 → 18	-1	-0.1	• • •	-0.7	-0.2	-0.5	-0.62 0.32	-1.1 -0.1
	18 → 19	-15.2	-19.8 • • •	-28	1.8	-6.8	-9.09 10.24 -28	9.5
	19 → 20	-23	16.8 • • •	23.6	-1.6	-25.5	-3.56 21.78 -50.5 23.6

Location Feb. 7 Feb. 8 • • • Feb.

TABLE III STATISTICAL

 III

ANALYSIS OF THE RELATIVE DIVERGENCE OF DAILY FLOWS [%] IN THE SOUTH RING OVER 10 DAYS (FROM FEBRUARY 7 TO FEBRUARY 17, 2014). "n.a." STANDS FOR "NOT AVAILABLE".

•

  Alain Y. Kibangou has been Associate Professor at the University Grenoble Alpes, France, since 2009. He received the Ph.D. degree in control, signal, and image processing from the University of Nice Sophia Antipolis in 2005. Then, he was a Postdoctoral

Acknowledgements

This research has been supported by the EU FP7/2010-14 HYCON2 NoE under grant agreement no. 257462, by the project MOCoPo "Measuring and mOdelling traffic COngestion and POllution" through the PREDIT, by the "Fonds d'Intervention de l'UJF", pôle scientifique MSTIC, and by the Carnot iC LSI project "Mobile Devices for Intelligent Road Traffic Prediction". The authors would like to thank the DIR-CE, Service Régional d'Explotation et d'Ingégnerie, District de Grenoble, for their support in the design of GTL data-acquisition system, and Karrus ITS for the installation and maintenance of the sensor network.

different categories of vehicles, e.g. fire trucks, ambulances, police and passenger cars. Looking further into the future, we also plan to extend our network of sensors to the major urban arterials of Grenoble in order to have a wider city-level coverage of traffic behavior, and to combine traffic data coming from heterogeneous sensors (e.g., magnetometers and GPS-equipped vehicles). By subdividing [x p , x 0 ] into n rectangles of width Δ x i and assuming that the speed is constant in each rectangle (see Fig. S2), we can rewrite equation (S1) as

Author Information

where v i (η(Δ x i )) is the space-mean speed in the i-th rectangle and


Juan Antonio Lossio-Ventura

Clement Jonquet
email: jonquet@lirmm.fr

Mathieu Roche
email: mathieu.roche@cirad.fr

Maguelonne Teisseire
email: maguelonne.teisseire@teledetection.fr

BIOTEX: A system for Biomedical Terminology Extraction, Ranking, and Validation

Term extraction is an essential task in domain knowledge acquisition. Although hundreds of terminologies and ontologies exist in the biomedical domain, the language evolves faster than our ability to formalize and catalog it. We may be interested in the terms and words explicitly used in our corpus in order to index or mine this corpus or just to enrich currently available terminologies and ontologies. Automatic term recognition and keyword extraction measures are widely used in biomedical text mining applications. We present BIOTEX, a Web application that implements state-of-the-art measures for automatic extraction of biomedical terms from free text in English and French.

Introduction

Within a corpus, there is different information to represent, with different communities to express that information. Therefore, the terminology and vocabulary is often very corpus specific and not explicitly defined. For instance in medical world, terms employed by lay users on a forum will necessarily differ from the vocabulary used by doctors in electronic health records. We thus intend to offer users an opportunity to automatically extract biomedical terms and use them for any natural language, indexing, knowledge extraction, or annotation purpose. Extracted terms can also be used to enrich biomedical ontologies or terminologies by offering new terms or synonyms to attach to existing defined classes. Automatic Term Extraction (ATE) methods are designed to automatically extract relevant terms from a given corpus. 1 . Relevant terms are useful to gain further insight into the conceptual structure of a domain. In the biomedical domain, there is a substantial difference between existing resources (ontologies) in English and French. In English there are about 7 000 000 terms associated with about 6 000 000 concepts such as those in UMLS or BioPortal [START_REF] Noy | BioPortal: ontologies and integrated data resources at the click of a mouse[END_REF]. Whereas, in French there are only about 330 000 terms associated with about 160 000 concepts [START_REF] Neveol | Language Resources for French in the Biomedical Domain[END_REF]. French ontologies therefore have to be populated and tool like BIOTEXwill help for this task. Our project involves two main stages: (i) Biomedical term extraction, and (ii) Ontology population, in order to populate ontologies with the extracted terms.

In this paper, we present BIOTEX, an application that performs the first step. Given a text corpus, it extracts and ranks biomedical terms according to the selected stateof-the-art extraction measure. In addition, BIOTEX automatically validates terms that already exist in UMLS/MeSH-fr terminologies. We have presented different measures and performed comparative assessments in other publications [START_REF] Lossio-Ventura | Towards a Mixed Approach to Extract Biomedical Terms from Text Corpus[END_REF][START_REF] Lossio-Ventura | Yet another ranking function to automatic multi-word term extraction[END_REF]. In this paper, we focus on the presentation of BIOTEX and the use cases it supports.

Related work and available extraction measures

Term extraction techniques can be divided into four broad categories: (i) Linguistic approaches attempt to recover terms via linguistic patterns [START_REF] Gaizauskas | Term recognition, classification in biological science journal articles[END_REF]. (ii) Statistical methods focus on external evidence through contextual information. Similar methods, called Automatic Keyword Extraction (AKE), are geared towards extracting the most relevant words or phrases in a document. These measures, such as Okapi BM25 and TF-IDF, can be used to automatically extract biomedical terms, as we proposed in [START_REF] Lossio-Ventura | Towards a Mixed Approach to Extract Biomedical Terms from Text Corpus[END_REF]. These two measures are included in BIOTEX. (iii) Machine Learning is often designed for specific entity classes and thus integrate term extraction and term classification. (iv) Hybrid methods. Most approaches combine several methods (typically linguistic and statistically based) for the term extraction task. This is the case of C-value [START_REF] Frantzi | Automatic recognition of multiword terms: the Cvalue/NC-value Method[END_REF], a very popular measure specialized in multi-word and nested term extraction.

In [START_REF] Lossio-Ventura | Towards a Mixed Approach to Extract Biomedical Terms from Text Corpus[END_REF], we proposed the new hybrid measures F-TFIDF-C and F-OCapi, which combine C-value with TF-IDF and Okapi respectively to extract terms and obtain better results than C-value. In [START_REF] Lossio-Ventura | Yet another ranking function to automatic multi-word term extraction[END_REF], we propose LIDF-value measure based on linguistic and statistical information. We offer all of these measures within BIOTEX. Our measures were evaluated in terms of precision [START_REF] Lossio-Ventura | Towards a Mixed Approach to Extract Biomedical Terms from Text Corpus[END_REF][START_REF] Lossio-Ventura | Yet another ranking function to automatic multi-word term extraction[END_REF] and obtained the best results over the top k extracted terms (P @k) on several corpora (LabTestOnline, GENIA, PubMed). For instance, on a GENIA corpus, LIDF-value achieved 82% for P @100, thus improving the C-value precision by 13%, and 66% for P @2000, with an improvement of 11%. BIOTEX allows users to assess the performances of measures with different corpora.

A detailed study of related work revealed that most existing systems implementing statistical methods are made to extract keywords and, to a lesser extent, to extract terminology from a text corpus. Indeed, most systems take a single text document as input, not a set of documents (as corpus), for which the IDF can be computed. Most systems are available only in English. Table 1 shows a quick comparison with TerMine (C-value), the most commonly used application, and FlexiTerm, the most recent one. BIOTEX is an application for biomedical terminology extraction which offers several baselines and new measures to rank candidate terms for a given text corpus. BIO-TEX can be used either as: (i) a Web application taking a text file as input, or (ii) as a Java library. When used as a Web application, it produces a file with a maximum of 1200 ranked candidate terms. Used as a Java library, it produces four files with ranked candidate terms found in the corpus, respectively, unigram, bigram, 3-gram and all the 4+ gram terms. BIOTEX supports two main use cases:

(1) Term extraction and ranking measures: As illustrated by the Web application interface, Figure 1 (1), BIOTEX users can customize the workflow by changing the following parameters:

-Choose the corpus language (i.e., English or French), and the Part-of-Speech (PoS) tagger to apply. Note that we tested three POS-tagger tools but currently only TreeTagger is available within BIOTEX. -Select a number of patterns to filter out the candidate terms (200 by default).

Those reference patterns (e.g., noun-noun, noun-prep-noun, etc.) were built with terms taken from UMLS for English and MeSH-fr for French. They are ranked by frequency. -Select the type of terms to extract: all terms (i.e., single-and multi-word terms)

or multi-word terms only. -Select the ranking measures to apply.

(2) Validation of candidate terms: After the extraction process, BIOTEX automatically validates the extracted terms by using UMLS (Eng) & MeSH-fr (Fr). As illustrated in Figure 1 (2), these validated terms are displayed in green, specifying the used knowledge source and the others in red. Therefore, BIOTEX allows someone to easily distinguish the classes annotating the original corpus (in green) from the terms that maybe also considered relevant for their data, but need to be curated (in red). The last ones may be considered candidates for ontology enrichment.

Conclusions and Future Work

In this article, we present the BIOTEX application for biomedical terminology extraction. It is available for online testing and evaluation but can also be used in any program as a Java library (POS tagger not included). In contrast to other existing systems, this system allows us to analyze a French corpus, manually validate extracted terms and export the list of extracted terms. We hope that BIOTEX will be a valuable tool for the biomedical community. It is currently used in a couple of test-beds within the SIFR project (http://www.lirmm.fr/sifr). The application is available at http://tubo.lirmm.fr/biotex/ along with a video demonstration http: //www.youtube.com/watch?v=EBbkZj7HcL8. For our future validations, we will enrich our validation dictionaries with BioPortal [START_REF] Noy | BioPortal: ontologies and integrated data resources at the click of a mouse[END_REF] terms for English and CISMeF [START_REF] Darmoni | Multiple Terminologies in a Health Portal: Automatic Indexing and Information Retrieval[END_REF] terms for French. In the future, we will offer disambiguation features using the Web to find the context in order to populate biomedical ontologies with the new extracted terms (red terms), while looking into the possibility of extracting relations [START_REF] Abacha | Automatic extraction of semantic relations between medical entities: a rule based approach[END_REF] between new terms and already known terms.

Fig. 1 .

 1 Fig. 1. (1) Interface: term extraction. (2) Interface: term validation. Users can export the results for offline processing.

Table 1 .

 1 Brief comparison of biomedical terminology extraction applications.

		BioT ex	T erM ine	F lexiT erm
	Languages	en/fr	en	en
	Type of Application	Desktop/Web	Web	Desktop
	License	Open	Open	Open
	Processing Capacity	No Limits / < 6 MB	< 2 MB	No Limits
	Possibility to save results	XML	-	CSV
	POS tool	TreeTagger	Genia/TreeTagger Stanford POS
	# of Implemented Measures	8	1	1
	http://www.nactem.ac.uk/software/termine/
	http://users.cs.cf.ac.uk/I.Spasic/flexiterm/

We refer to ATE when terms extracted are not previously defined in existing standard ontologies or terminologies. We refer to 'semantic annotation' when term extracted can be attached or match to an existing class (URI) such as in[START_REF] Jonquet | NCBO Annotator: Semantic Annotation of Biomedical Data[END_REF]. Both approaches are related to Named Entity Recognition (NER), which automatically extracts name of entities (disease, person, city).

Acknowledgments. This work was supported in part by the French National Research Agency under JCJC program, grant ANR-12-JS02-01001, as well as by University of Montpellier 2, CNRS, IBC of Montpellier project and the FINCyT program, Peru


Daria Mishchenko

On some aspects of the representation of sentential actants in Looma

(1) È zo-gɛ̀ lase-su.

2SG.BASE мочь-RES плавать-SUP

'Ты умеешь плавать'.

(

  кодирования сентенциальных актантов в лоома 1 В докладе рассматриваются способы выражения сентенциальных актантов (СА) в языке лоома (юго-западные манде). Основное внимание будет уделено зависимости способа выражения СА от семантики матричного предиката и вариативности кодирования СА. СА в лоома могут быть выражены при помощи финитной клаузы и при помощи супина. Актанты, которые выражаются образованным путѐм конверсии отглагольным именем, строго говоря, следует относить к числу именных, а не сентенциальных актантов. Тем не менее, в лоома имеется ряд предикатов с ситуационной валентностью, таких, как kpeǵ 'прекращать', maá́ lɛlɛ 'обучать' или nɛ̀ 'нравиться', для которых кодирование участника со значением ситуации при помощи отглагольного имени является единственно возможной стратегией. Кроме того, интересным представляется анализ вариативности кодирования актантов определѐнных глаголов при помощи финитной клаузы или супина и при помощи отглагольного имени, а потому именные актанты, выраженные отглагольным именем, будут обсуждаться в докладе наряду с СА и для простоты будут объединены с ними под названием СА. Выбор способа оформления СА предиката коррелирует с положением последнего на шкале связанности [Givoń 1980], однако зависимость между способом оформления СА и семантическими свойствами предиката носит односторонний характер. Действительно, при помощи отглагольного имени и супина оформляются СА предикатов, расположенных низко на шкале связанности, однако обратное утверждение неверно. СА многих предикатов, расположенных низко на шкале связанности, выражаются при помощи зависимой финитной клаузы. Так, СА модального глагола sog 'мочь' может кодироваться при помощи супина (1) или отглагольного имени, но не может быть выражен финитной клаузой. Модальный же глагол maá́ nɛ́ 'быть должным', для которого ожидается сходное поведение, допускает оформление своего СА при помощи финитной клаузы (2):

  СА выражается финитной клаузой, синтаксические отношения между двумя клаузами могут быть различными. Некоторые предикаты, к примеру, folɛsɛg 'заставлять', kɛ̀ 'сказать' или kiśiá́ 'планировать', вводят формально самостоятельное предложение. В этом случае две клаузы равноправны и в клаузе, выражающей СА, может употребляться любая Givoń 1980 -Givoń, T. The binding hierarchy and the typology of complements // Studies in Language 4,1980. Pp. 333-377.

	Если СА выражен финитной клаузой, значимой может быть и конкретная ТАМ-
	конструкция, использующаяся в ней. Так, если в (6) для выражения ирреального
	апрехензивного значения используются конструкция ирреалиса и нейтральная конструкция с
	эксплетивным отрицательным показателем miǹa, в (7), с нейтральной конструкцией, тот же
	ТАМ-конструкция, например, дуративная конструкция, как в (3): предикат выражает уже реальное значение и, соответственно, высокую степень
	(3) Kɛɛ̀ уверенности:	ɣɛ̀	toá́	liì-zù	liíńà	dɔbɔ-y	zu.
	1SG.PI\отец сказать 3SG.NPST идти-IPFV завтра REF\лес-DEF в (7) Naà̀ ińɛíǹɛ-sù zuńɔ́ gà nú Ø là	sɛʋɛ-y	ní
	'Мой отец сказал, что завтра идѐт в лес'. 1SG.NPST беспокоиться-IPFV очень что REF\человек 3SG.BASE NEG REF\-DEF
	Таким образом, несмотря на обязательность семантического ситуационного актанта, этот
	по-видимому, следует признать, что обязательной синтаксической валентностью на СА ɣaĺa.
	такие предикаты не обладают. читать
	'Я сильно опасаюсь, что никто не прочитал эту книгу'.
	Список литературы
	(4) Naà̀	luẁa-zù	gà	Zezé Ø			ʋa.
	Для некоторых матричных предикатов характерна вариативность выражения СА; она
	может проявляться либо на уровне выбора общего средства кодирования СА, либо, если СА
	выражается при помощи финитной клаузы, на уровне выбора глагольной конструкции. В
	некоторых случаях значение предиката в сочетаниях с СА, оформленными различным
	образом, значительно отличается, что позволяет рассматривать сочетание «предикат + СА»
	как конструкцию в терминологическом смысле. К примеру, сочетание ińɛíǹɛg с отглагольным
	именем выражает значение 'сомневаться в чѐм-л.' (5), а с финитной клаузой -значение
	'опасаться чего-л.' (6):
	(5) Akoý ɣà	ińɛíǹɛ-sù	di-ʋe-y		zù dɔẃɔ-y	zu.
	Акои 3SG.NPST беспокоиться-IPFV 3SG.PI\идти-RES-DEF в REF\рынок-DEF в
	'Акои сомневается, идти ли на рынок'.
	(6) … toá́	ińɛíǹɛ-sù	gà	nà	Ø	miǹà	lo,	á	ʋà
	2) Wo-maà̀ 3SG.NPST беспокоиться-IPFV что тот 3SG.BASE PROH падать 3SG.IRR приходить nɛ-ʋɛ̀ wò nu-í pɛ́ tuẃɔ.
	2PL.PI-поверхность быть.приятным-RES 2PL.BASE REF\человек-DEF все guĺo-y wu-ya.
	приветствовать REF\масло-DEF литься-PRF
	'Вы должны со всеми здороваться'.

1 Исследование проведено в рамках гранта РГНФ 13-34-01015 «Глагольные системы языков манде в контексте типологических и ареальных исследований».

Если

Другие матричные предикаты, например, duẁà 'бояться' или pɔǵ 'хотеть', вводят зависимую клаузу с помощью союза ga. В составе такой клаузы могут употребляться только две глагольные конструкции: нейтральная конструкция, как в (4), и конструкция ирреалиса:

1SG.NPST бояться-IPFV что Зезе 3SG.BASE приходить 'Я боюсь, что Зезе придѐт'.

[Себага послала свою дочь на рынок продавать красное масло], 'она беспокоится, как бы та не упала и не разлила масло'.