Imene Lahyani

Lamia Ben Amor
email: lamia.benamor@redcad.org

Mohamed Jmaiel
email: mohamed.jmaiel@enis.rnu.tn

Khalil Drira

Christophe Chassot
email: chassot@laas.fr

Analytical framework for QoS aware publish/subscribe system deployed on MANET

In this paper, we propose an analytical framework for monitoring and analyzing QoS of publish/subscribe systems on MANET. Our framework copes with intermittent connectivity frequently occurring in MANET and provides statistical methods allowing detecting QoS degradations affecting links between brokers at the middleware layer. Besides, our analytical framework identifies QoS degradation source which enables to repair the system. The proposed framework is extensively evaluated with simulation experiments. Simulations results show its efficiency.

I. INTRODUCTION

A publish/subscribe (Pub/Sub) [START_REF] Eugster | The many faces of publish/subscribe[END_REF] system is a networked communication infrastructure where messages are provided by publishers and then delivered to receivers whose subscriptions match the messages. The broker, named also dispatcher or channel manager, represents the most important component in the system. It has to perform the matching between the incoming events and subscriptions in the system and it also has to send to the subscribers all the events for which they have expressed interest. Such a communication paradigm is promising in mobile environments owing to its decoupling nature ensuring anonymity and decoupling between communicated entities. However, deploying pub/sub systems on MANET [START_REF] Khakpour | Designing and prototyping an event-based communication system on mobile ad hoc networks[END_REF] is a challenging task due to QoS degradation problems caused by node's mobility especially for delay sensitive applications. In order to face QoS degradations, network routing protocols in MANET always search for a route connecting brokers. However, there is no guarantee to find this route and it is possible that the route found does not fit application requirements. Thus, network routing protocols cannot always solve QoS degradation problems occurring at this layer. Consequently, a solution should be introduced at the middleware layer. Facing this problem, several studies [START_REF] Kim | Efficacy of techniques for responsiveness in a wide-area publish/subscribe system[END_REF] react at this level by taking into account some QoS parameters. These studies seek to address the challenge of managing latency performance for pub/sub systems deployed on MANET. However, they did not provide an efficient solution to this problem since they compare parameters values with fixed threshold and are restricted to a specific subscription language or to a specific topology.

In this paper, we deal with these problems and we propose a delay-aware dynamic framework aiming at providing best adapted QoS in the system according to the available resources by managing a permanent connectivity guarantee between brokers. To achieve the mentioned goal, adaption can be accomplished by migrating a faulty broker to another node in the network ensuring better QoS. Adaption may also be achieved by splitting an overloaded broker in order to minimize his load.

The proposed analytical framework integrates in each node modules which extract QoS parameters and analyzes them in order to detect QoS degradations and identify its causes. The first step of our approach is monitoring QoS parameters by intercepting events. Second, statistical indicators of failure occurring in the system are computed by the analysis module. This module does not refer to fixed thresholds. However, we use an adaptive procedure in order to update the threshold values according to the latest available information. The statistical method used in the analysis step to detect failures is based on the Extreme Values Theory (EVT) [START_REF] Castillo | Extreme Value Theory in Engineering[END_REF] as well as the test of Shapiro and Wilk [START_REF] Rakotomalala | Tests de normalite : Techniques empiriques et tests statistiques[END_REF]. Our approach approximates QoS measured parameter with Gumbel [START_REF] Giorgi | Detection of Anomalous Behaviors in Networks From Traffic Measurements, Instrumentation and Measurement[END_REF] and Gaussian distributions [START_REF] Giorgi | Detection of Anomalous Behaviors in Networks From Traffic Measurements, Instrumentation and Measurement[END_REF], then tracks mean and max values of the QoS traces by following fluctuations in the time series using updated thresholds. This enables to identify system state: well, acceptable or not well. Once failures are detected, the analysis module identifies their sources using the correlation method [12] which studies the dependence between latency increase and possible factors. In order to validate our approach, we carry on simulations experiments. Simulation results show that our approach provides QoS guarantee for pub/sub systems on MANET and detect failure which preserves system survivability. As a result, our framework is not restricted to a specific topology or a specified subscription language. However, it 's a generic framework which may be used in cooperative applications.

The rest of the paper is organized as follows. The design and analysis of our analytical framework is described in Section II. Section III presents the performance evaluation of our approach under different link failure conditions. Section IV summarizes the related work and Section V concludes the paper.

II. THE ANALYTICAL FRAMEWORK

In this paper, a QoS based framework is proposed for QoS insurance of Pub/Sub systems on MANET. The major goal of the proposed framework is to bypass link failures and increase the chance to meet QoS requirement for such systems. The proposed approach monitors QoS parameter values by intercepting events. Then, analyzes these values in order to decide about system state. Finally, it reasons about an occur degradation source whenever a QoS degradation is identified. Our framework based on mathematical models relies on statistical methods to analyze the system state and provides a strong QoS support. It approximates latency values with Gaussian and Gumbel distributions, then compute adaptive thresholds. Failures are detected by comparing latency values with appropriate thresholds. Moreover, QoS degradation source is identified using the correlation method as a measure of dependency between two distributions. Figure 1 describes the proposed approach.

A. Monitoring

Monitoring constitutes a fundamental step in the proposed framework. It has to provide to the analysis level the information useful for its operation. A first level of Monitoring step is calculating latency values relying on event system messages. In fact, a monitoring module integrated in each broker intercepts event when translating between neighboring brokers. However, if there is no event delivery during a long time, specific messages are used in order to analysis QoS link state. Latency is calculated locally by the broker receiving the event. It' is defined as the time elapsed between the time, T1, when the first broker B1 sends the first bit of a packet to his neighbor B2 and the time, T2, when the second receives the last bit of that packet at T 1 + ∆T . Thus, the latency that takes the event between B1 and B2 is defined with the following formula:

latency(B 2 , B 1 ) = T 2 -T 1 ± (of f set) (1)
where the clock offset refers to difference in the time reported by the two clocks. After computing latency values, the monitoring module saves these values in a log file.

B. Analysis approach

QoS analysis lays on the monitoring step. It exploits QoS parameters extracted from log files in order to analyze the system and detect QoS degradation. Implementing effective analysis needs to reason about the degradation source once QoS violations are noticed. In fact, identifying source failure creates opportunities to execute the appropriate reparation action in order to repair the system. Statistical analysis is used to detect QoS degradation. It's based on comparing QoS values with adaptive thresholds. Thresholds should be adaptive to the changes in network conditions (such as delay and failures), and are computed dynamically referring to latency series approximation with Gumbel and Gaussian distributions. Finally, when QoS degradations are detected, the correlation method is used to study the relation between latency increase and other perturbation factors.

A) Mathematical models for QoS analysis: Let the analyzed QoS parameter be described by a sequence collected over time and denoted QoS(t). The sequence is divided into periods composed of M samples. Then, the max, as well as mean values are extracted from each period. In this way, two new time series are obtained from the sequence of periods forming QoS(t) as follows:

(QoS max (i)) = max QoS iM+k ( 2
)
Maximal values where k in [0,M-1]

QoS(i) = (1/M )ΣQoS iM+k ( 3
)
Mean values where k in [0,M-1] Statistical properties of the max, and the mean are approximated by empirical distributions. In fact, the Gumbel distribution for the max and the Gaussian distribution for the mean sequence. Approximations enable to calculate initial thresholds for each series. Failure detection is then performed by comparing latency values with thresholds.

In order to prove that the series can be approximated with empirical distributions, we start with a first step named transitory regime.

1) Transitory regime: Demonstrating the perfect matching with the Gaussian distribution requires executing a normality test. So, we resort to the test of "SHAPIRO and Wilk" [START_REF] Rakotomalala | Tests de normalite : Techniques empiriques et tests statistiques[END_REF].

However, in order to prove that max values are best suited to the Gumbel distribution, we execute the following steps: First of all, we have to note that the cumulative distribution function is defined as:

F (x) = e -e (-(x-x 0 )/S)) (4)
where x 0 is the location parameter and S is the scale one.

Hence we have to:

• Sort the n samples forming our max distribution QoS max (i) where i belongs to [1,n] in an increasing order;

• attribute a rank r to each value;

• measure the empirical frequency defined as: ef = (r -0, 5)/n (5)

• calculate the Gumbel reduced variable defined as:

u = -ln(-ln(F (x)) (6)
• plot the curve defined by (u i , QoS max (i)) couples.

Once we can fit the plotted point by a straight line, then, we make sure that our distribution is well suited to the Gumbel one.

In order to extract the Gumbel parameters, we calculate both the scale parameter S and the location parameter x 0 using the method of moments as shown in the following formulas .

x 0 = µ -Sγ ( 7
)
where µ is the mean of the QoS max distribution and γ is the Euler constant defined as γ= 0,5772.

S = √ 6 π σ (8)
where σ denotes the standard deviation of the QoS max distribution Based on the extracted parameter values, we can at the end of the first step, calculate initial threshold values as denoted in the following table.

G(z) = T h QoS max = values exp(-exp(-(z -x 0 )/S) x 0 -S ln[ln( 1 p )] Mean F (z) = T h QoS mean = values Φ((z -µ QoS mean )/ f (φ -1 (p), µ QoS mean , σ QoS mean σ QoS mean )
A simple method to detect the presence of peaks in this phase consists in setting thresholds. Appropriate threshold values are first obtained by calculating the conditional mean and the associated confidence interval. These values are calculated using the following formulas.

QoS = 1 n n-1 i=0 QoS i (9)
CI + = QoS + t α σ/ √ n (10)
The first formula defines the mean calculated at a point of time, however, the second presents the confidence interval relative to that mean at the same instant.

In order to perform an occur analysis, chronicles are used to detect QoS degradations in this phase. In fact, after N successive QoS violations, our analysis module triggers an alarm. A key question to ask is whether it is possible to mathematically compute N, by considering that the probability of N messages in failed state is less than the probability of failure tolerated by the user [START_REF] Halima | Providing Predictive Self-Healing for Web Services: A QoS Monitoring and Analysis-based Approach[END_REF]. Let :

• N :denotes the number of successive violations leading to QoS degradation detection.

• LV : corresponds to a measured Latency higher than a threshold

• LOK: corresponds to a measured value under the threshold.

• Risk is the defect probability specified by the user. In order to determinate a precise value of N, we use the following expression :

P [N succLV ] Risk (11)
In

Besides, the probability of obtaining N successive violations is equal to the probability to reach a LV state, after leaving any state, multiplied by the probability of staying in LV state (N-1) times:

P [N succLV ] = P [anystate → LV ] * P [LV → LV ] N -1 (13)
When we replace the probability P [N succ → LV ] in the first inequality, we obtain the following expression providing the lower bound for N:

P [anystate → LV ] * P [LV → LV ] N -1 ≤ (Risk) (14)
Thus, we obtain N ≥ λ where

λ = 1 + ln Risk P [anystate→LV ] ln(P [LV → LV ]) (15)
When we choose an N's value greater than the smallest one,we accurate the degradation detection rate.

2) Permanent regime: Towards detecting the out of range values and deciding about system state, latency values are compared to the corresponding thresholds. Adaptive thresholds are dynamically updated using the exponential weighted moving average formula [START_REF] Lucas | Exponentially weighted moving average control schemes: properties and enhancements[END_REF]:

T h i = λΣ(1 -λ) j * QoS i-j + (1 -λ) i * T h 0 ( 16
)
where j in {1, i -1} and T h 0 denotes the initial Threshold.

Using the same formula used in the previous phase, chronicles are computed in order to perform an occur analysis. Thus, degradation detection algorithm trigger alarms when N successive violations happen denoted by M ax N br Succ V iolation in Algorithm 1. As illustrated in Algorithm 1, to each measured latency value (line 5), the detection algorithm increases the number of violations N b V iolation, in (line 7) whenever the new value exceeds the Algorithm 1 failure detection algorithm 1: max threshold = Gumbel.update threshold (maxV alues, initial max thres) 2: mean threshold = Gauss.update threshold (meanV alues, initial mean thres) 3: Idle: N b V iolation = 0 4: loop 5:

On N ew M easured Latency()

6:
if (Latency > max threshold) then end if 14: end loop threshold value (line 6). In case of non successive violations (line 9), the execution will jump to the initialization at line 3. Otherwise, it increments the number of successive violation until triggering alarms and reasoning about degradation source (line 12).

B)Degradation source identification approach:diagnostic approach

After detecting a QoS degradation, we start the reasoning about its source. We start by identifying degradation category which may be either mobility or overload. Finally, we identify precisely the factor causing the failure. Table 2 resumes possible failure causes that may degrade QoS of the link between two brokers denoted by B 1 and B 2 . The key idea of source degradation identification is to study the dependency to any statistical relationship between two random variables or two sets of data. Doing this, we use the correlation method [12] towards studying the relation between latency value variation and parameters affecting latency such as hop count variation or overload variation.

Correlation method requires two steps. The first one consists in computing the Pearson correlation coefficient P CC value studying the dependency between two distributions X1 and X2 as described in the following equation.

P CC

end if 16: end if

The second step consists in executing a significance test of the correlation coefficient by comparing the computed coefficient with a theoretical value issued from the table of the critical value of the P CC. Thus, if P CC(X1, X2) is positive and greater than theoretical PCC , this means that X1 and X2 are positively and significatively correlated.

The proposed approach executes in parallel two algorithms studying correlation between latency variation and hop count variation as well as between latency variation and load variation. According to the significance of the correlation coefficient computed between these distributions, our algorithm proceeds in three different scenarios.

1) If latency and hop count distributions are significatively

and positively correlated, then we can deduce that hop count variation is one among the factors that causes QoS degradation. Thus, as described in algorithm 2, the first possible source causing the degradation may belong to the mobility category (line 2). We move then to identify the occur source causing hop count variation by looking to nodes positions (line 4,10) and speeds (line 6,12). Node speeds are compared with adaptive threshold updated using the EWMA formula. 2) If latency and load distributions are significatively and positively correlated, then we can notice that load variation is one among the factors that causes QoS degradation. 3) Otherwise, if correlation between all these parameters distributions is not significative, we can deduce that degradation is caused by other sources as described in Table 2.

III. EVALUATION

This section shows the performance evaluation of our approach using simulations with various settings.

A. Simulation Setup

To simulate dynamic network environment, we use JiST/SWANS simulator (Java in Simulation Time/Scalable Wireless Ad hoc Network Simulator) [START_REF] Barr | Scalable wireless ad hoc network simulation,handbook on theoretical and algorithmic aspects of sensor, Ad hoc Wireless, and Peer-to-Peer Networks[END_REF]. We resort also to the content based publish/subscribe system named SIENA [START_REF] Carzaniga | Design and evaluation of a wide-area event notification service[END_REF](Scalable Internet Event Notification Architecture) to which we add our monitoring and analysis modules. In all simulations, we use 802.11b as the medium access control protocol and AODV (Ad hoc On-demand Distance Vector) as routing protocol which is a reactive one. During simulation, we measure the latency between two neighboring brokers called B 1 and B 2 at each event delivery.

Simulation experiments consist in two parts. Part 1 provides an explanation of how monitoring and analysis modules succeed in detecting failures and identifying the occur source of failure. In part 2, we estimate our analytical framework overhead.

B. Part 1: Efficiency of our approach

To evaluate the performance of the proposed modules, we consider a network of 200 broker nodes, equipped with 802.11 radio interfaces, roam in a 2000 * 3000m 2 area. The model for mobility is continuous random walk with pause time equal to 30s and max speed equal to 30m/s. Size of event notifications is about 120 Bytes. The radio transmission range of each node is approximately 300 meters. Each simulation spans about 9000 seconds of simulation time. A first scenario consists in highlighting the monitoring module results. So, we trigger the nodes mobility with a low speed varying from 1m/s up to 5 m/s. The traces files describing QoS parameters issued from monitoring module allow us to draw the curve depicted by Figure 2. In fact, in this figure, our system works well.i.e. a failure free one. At t = 6350 s in simulation time, we inject a failure by moving quickly broker B 2 far from his neighbors frequently. This causes a high latency values varying from 95519µ s to 75610µ s. Another failure is injected at t= 7820 s in simulation time, This causes also latency variation from 29029µ s to 81567µ s. As shown in Figure 3, latency oversteps the max threshold value for three consecutive times. Consequently, our failure detector generates alarms. The following log generated by our analysis algorithm describes source degradation identification (Table3).

In second scenario, we inject failure in the system by overloading the broker B 1 . This causes also latency variation from 8235µs to 9503µs.

As shown in Figure 4, latency oversteps the max threshold value for three consecutive times. Consequently, our failure detector generates alarms. The following log generated by our analysis algorithm describes source degradation identification (Table 4). We notice from experiments that our algorithm detects QoS degradations and identifies its cause which is a hop count variation in the first scenario and load variation in the second scenario. This illustrates the efficiency of our approach. This part aims to estimate the overhead of the monitoring and the analysis modules.

C. Part 2:Analytical framework overhead

To reach this goal, we perform simulations experiments with and without the proposed framework and we measure the execution time when sending periodically messages in the system. The noticed overhead represents the time needed to execute the added framework. We can see for instance, as represented in Figure 5, that the latency is about 5840,47µs and 4310,45µs with and without additional components, respectively, when message size . Thus, this overhead stills relatively low compared to the execution time.

IV. RELATED WORK

Failures are inevitable in a distributed system built over a mobile ad hoc network. So that, they should be detected instantly to avoid the whole system failure and to ensure the system survivability. In the following, we present works dealing with failures detection techniques and diagnosis methods used to locate failures.

Several studies addressed the issue of QoS analysis for pub/sub systems in order to detect failures. Researches on failure detection (FD) approaches for pub/sub systems are concentrating on two main topics: FD based on specific messages exchange and FD based on fixed threshold. In the first category, each node sends a specific message such as PING and Heartbeat to its neighbors. If the latter doesn't receive the message within a fixed timeout, then the target node is considered failed. [START_REF] Marco | A Cross-Layer Approach for Publish/Subscribe in Mobile Ad Hoc Networks[END_REF] [13] use PING message and [START_REF] Khedher | A Novel Overlay-Based Failure Detection Architecture for MANET Applications[END_REF] [15] rely on Heartbeat message to identify node failure. However using a fixed timeout is not adapted to MANET and so can lead to false detections. Moreover, these techniques don't deal with link failure.

Contrary to the above techniques, our approach doesn't rely on specific messages but rather uses pub/sub messages to detect system failure.

In the second category, the idea consists in comparing QoS parameter value with a fixed threshold. If QoS parameter exceeds the threshold value then an alarm is triggered. In [?], authors propose a messaging system called Harmony. Separately, for each message topic, Harmony specifies latency requirements. Therefore, this restrained applying this approach in content based systems. Our approach, however, is not limited to a specific subscription language and is considered as a generic approach. Contrarily to the explained approaches, we use adaptive threshold according to the requirements of applications and the variation of the network. After detecting a failure, we need to reason about source failure which defines diagnosis methods.

Diagnosis methods have been increasingly developed especially for dynamic systems. These methods concern the task to identify and isolate faults in such systems. In the literature, there are two main categories of diagnosis methods: a model based diagnosis and a free model based diagnosis.

Model based diagnosis methods can be categorized into two subclasses: Diagnosis based on quantitative model from the FDI Community [START_REF] Cordier | AI and Automatic Control Approaches of Model-Based Diagnosis : Links and Underlying Hypotheses[END_REF] relaying on mathematical model describing the behavior of the system, and diagnosis based on qualitative model.

In the second subclass, qualitative models are used such as graphs or if-then rules to describe the system's behavior. These approaches are suitable for systems with qualitative faults [START_REF] Baniardalani | Qualitative Model Based Fault Diagnosis Using a Threshold Level[END_REF] like discrete-event systems, hybrid systems. Although them advantages, model based diagnosis are not usable in some applications where it is difficult or even impossible to obtain the system model. Indeed, only free model based diagnosis are operational in such applications.

Free model based diagnosis are based on information from previous experience and they generally use artificial intelligence [START_REF] Chandra | Neuro-Fuzzy approach fr fault location and diagnosis using online learning system[END_REF] and statistical methods [START_REF] Sp | Combining Visualization and Statistical Analysis to Improve Operator Confidence and Efficiency for Failure Detection and Localization[END_REF] to identify faults. In our approach, it's impossible to establish a model that reflects the behavior of the system due to applications requirements and the variation of the network. Thus, we refer to the free model based diagnosis.

V. CONCLUSION

This paper proposes a generic and dynamic framework for QoS aware pub/sub systems deployed on MANET. Different from traditional approaches utilizing a fixed threshold for topics, our framework dynamically update thresholds using statistical methods in order to bypass link failures and increase the chance of delivering messages within the delay requirement. Our study focused on QoS aware pub/sub systems by providing monitoring and analysis modules allowing to continuously supervising the system, detecting QoS degradations and reasoning about source failure. Our approach is evaluated using simulations with various network settings and is shown to present a reasonable performance. Work is also underway to incorporate other QoS parameters to maintain good system performance, while still providing connectivity between brokers. Parallel efforts to evaluate the proposed QoS based framework in a real deployment using android are under development as well.

Fig. 1 .

 1 Fig. 1. The proposed approach

Fig. 2 .

 2 Fig. 2. latency function of simulation Time

  the simulator. Besides, we consider that the tolerated risk proposed by the user is equal to 0.01%. Thus, we obtain :P [anystate → LV ] = 0,118 With P [LOK] = 0, 74, P [LV ] = 0, 236, P [LOK → LV ] = 0, 127, and P [LV → LV ] = 0, 104 Consequently, N ≥ 2.2. Thus, N must at least be equal to 3.

Fig. 3 .

 3 Fig. 3. Reactive analysis

Fig. 4 .

 4 Fig. 4. Reactive analysis

Fig. 5 .

 5 Fig. 5. Overhead introduced by the analytical framework

  addition, the probability that the next message is in violation state denoted by LV , is equal to the probability of being in acceptable state LOK multiplied by the probability of going from this state to the state LV added to the probability of being in state LV multiplying the probability of staying in this state in the next instant.

P [anystate → LV ] = P [LOK] * P [LOK → LV ]+ P [LV ] * P [LV → LV ]

TABLE IV

 IV

	LOG FILE DESCRIBING SOURCE DEGRADATION IDENTIFICATION(SECOND
	SCENARIO)
	Time detection	256 s
	Number of successive violations	3
	latency value at t-2	8235 µs
	latency value at t-1	8460 µs
	latency value at t	9503 µs
	load at t-2	164 msg/s
	load at t-1	191 msg/s
	load at t	233 msg/s
	PCC	0.9879
	PCC theoretical value	r = 0.9877
	failure category	load


Marc Christie
email: marc.christie@inria.fr

Christophe Lino
email: christophe.lino@inria.fr

Rémi Ronfard

Rémi Ronfard Film Editing For Third

Remi Ronfard
email: remi.ronfard@inria.fr

Film Editing for Third Person Games and Machinima

Keywords: Camera Planning, Automatic Film Editing, Film Grammar, Optimization Methods

INTRODUCTION

In many applications, it is useful to present 3D animation in a cinematic style, which means selecting appropriate cameras and appropriate inter-cutting between cameras to properly convey a narrative. In third-person games and machinima, cameraworks and editing are key elements to convey dimensions such as mood and tension, which in turn provide a greater feeling of immersion through the re-use of well-known cinematic techniques. This creative task requires both a strong knowledge of these techniques and the ability to handle complex animation and editing tools.

Game engines provide little support for cinematography and film editing techniques. Even with advanced machinima tools such as Moviestorm1 and iClone2 , the control of cameras and cross-cutting remains a complex task (though Moviestorm provides a number of convenient control features for screen composition). One exception is the Magicam option in the online machinima system Text-to-Movie by Xtranormal3 which automatically chooses cameras and cuts in two-person dialog scenes. Yet the system provides limited flexibility in choosing editing or camera styles. This paper proposes a general computational framework which provides the user with an interactive process to generate a cinematic editing of a 3D animation. Our framework proposes scores for shots and cuts, independently of the film idioms used to generate them. The score for a shot is based on the Hitchcock principle of showing action from the best angle [START_REF]Hitchcock-Truffaut[END_REF] and the score for a transition between shots is based on the working practices of film and television [START_REF] Thompson | Grammar of the Edit[END_REF][START_REF] Thompson | Grammar of the Shot[END_REF]. In contrast to related work, we account for a precise enforcement of pacing (rhythm at which cuts are performed) and study in detail the best moment to perform cuts. This framework has been implemented as part of a system for controlling multiple virtual cameras in real time while the scene animation is computed, and evaluating the footage generated from each camera against a mathematical model of film grammar.

We cast the problem of film editing as selecting a path in time through a collection of takes (a take is a continuous sequence of images from a given camera) and precisely deciding when to cut in and out the takes. We propose an algorithm suitable for online editing which uses an efficient best-first search technique. The algorithm relies on shortterm anticipation to improve quality in cuts and produce movies consistent with the rules of cinematography and editing, including shot composition, continuity editing and pacing.

Our approach work in three succesive steps. We first procedurally compute a collection of takes from the events occurring in the 3D animation (the collection of takes is large enough to make the search problem strongly combinatorial by generating many different camera configurations -80 in average per action). All takes are cut into fragments of duration ∆t and individually evaluated to establish their fragment quality. In a second step, a graph is constructed (referred to as the editing graph), in which nodes represent a fragment of a take, and arc represent either cut-arcs or shot-arcs. A cut-arc represents a cut from a take i at time t to a take j = i at time t + δt. A shot-arc represents continuity (i.e. no cut) in a take i between time t and time t + ∆t. In a final step, a search process is performed through this graph to compute a traversal of the animation sequence.

The paper is organized as follows. First, we review related work and compare it to our method. Then we introduce a cost function for shots, transitions and pacings, illustratedwith many examples. Then, we provide a fast method for computing the minimum-cost edit in near-real-time. Finally, we present some results and provide directions for future work.

RELATED WORK

In one of the first contributions to automated camera planning, He et al. [START_REF] He | The virtual cinematographer: a paradigm for automatic real-time camera control and directing[END_REF] proposed hierarchical state machines (HFSM) for camera placement and cross-cutting between cameras. Their approach assumes a finite number of film idioms suitable for prototypical situations in the animated scene. The higher levels in the HFSM are responsible for choosing the appropriate film idioms and camera setups, while the lower levels are responsible for cutting between the cameras in each setup. Film idioms can be effective in cases where the configuration space for actors and their actions can be enumerated. But even in such case, they tend to be repetitive and predictable, and attract attention away from the immersive experience of the game or the story. If the configuration space becomes large, as in scenarios with multiple stages and actors, the cost of encoding every possible idiom becomes too large.

For simple scenes with only one or two actors, film idioms provide a sensible solution because (1) the full vocabulary of possible shots is As noted by many researchers and film analysts, a story can be broken down into dramatic beats, i.e. primitive actions. Dramatic beats typically involve only one or two actors at any given time. Each beat defines a line of action around which a film idiom can be defined. That approach was taken by Lino et al [START_REF] Lino | A real-time cinematography system for interactive 3d environments[END_REF] with good results, but film idioms cannot guarantee that the resulting movie will be adequate, because secondary actors (not part in the primary action) may now interfere with the primary actors and furthermore create misleading shot transitions.

In this paper, we propose to combine a film idiom approach similar to [START_REF] Lino | A real-time cinematography system for interactive 3d environments[END_REF] with an introspection mechanism that allows to alleviate this problem by generating a large number of candidate idioms, and computing a score for the shots and cuts proposed by each idiom. That strategy allows to detect poor shot composition and transition choices and combine candidate idioms into a single, consistent editing solution. Furthermore, we introduce novel constraints for controlling the pacing of the editing.

Our work can be closely related to the Virtual Director of Assa et al [START_REF] Assa | The virtual director: a correlation-based online viewing of human motion[END_REF] but in a very different context. Their method focusses on showing the physical motion present in the scene, rather than its narrative content. As a result, their criteria for choosing views is based on the correlation between motion in the 3D scene motion and motion in each view. To control shot duration, the authors introduce an accumulated view erosion function resulting in a decay in the score of each view after a given amount of time but is not consistent with previous work in film aesthetics.

Our approach is also related to the Cambot machinima system of Elson and Riedl [START_REF] Elson | A lightweight intelligent virtual cinematography system for machinima generation[END_REF]. Similar to our system, Cambot receives a sequence of narrative goals from an external narrative engine. The authors also cast the problem of film editing as a shortest-path problem in a graph of candidate film takes. The score of a shot sequence is computed from userprovided aesthetic constraints. As an offline system, Cambot computes a global solution given the entire script, using a combination of breadth-first and dynamic programming techniques. We improve on this system in several respects. First, we introduce a set of generic aesthetic constraints consistent with established working cinematic practices [START_REF] Thompson | Grammar of the Shot[END_REF] and film editing [START_REF] Thompson | Grammar of the Edit[END_REF] and provide a detailed computational model implementing such constraints. Second, we place constraints on shot durations, allowing to more precisely set the in and out cutting point for each shot. Such constraints make the problem harder to solve with dynamic programming techniques. Third, we propose a fast algorithm allowing to find a suboptimal solution for both online and offline situations.

FILM GRAMMAR RULES

Our approach to film editing consists in enumerating all possible combinations of camera choices and evaluating them with a cost function. In this section, we review the components of our cost function. We make the assumption that the cost function is additive, i.e. the cost of a sequence is a simple sum over succesive frames in the sequence. The cost per fragment (a fragment is a part of a take of duration ∆t) is evaluated as a weighted sum of all violations of the rules of frame composition. And similarly, the cost of a cut is evaluated as a weighted sum of all violations of the rules of editing. In this simplified scheme, the rules of fim grammar are directly translated into a global cost function.

Thus the cost associated with shot i at time t is given by C SHOT (i), and the cost associated with a cut from shot i to shot j at time t is given by C CU T (i, j):

C SHOT (i) = k w k cost k (i, t) C CU T (i, j) = l w l cost l (i, j, t)
We further assume that the cost of a complete sequence

s(t) ∈ [1, M ], t ∈ [1, N ]
of N fragments using M takes is the sum of the costs for all of its fragments and cuts :

C(s) = t k w k C SHOT k (s(t), t) + l w l C CU T l (s(t), s(t + 1), t)
Note that we have made a number of strong assumptions. To fairly represent the editing process, the scoring of next shots and cuts should obviously depend on the past history of all previous shots. At this step we only consider the previous shot. Though restrictive, this hypothesis enables an efficient search process which can run online (directly selecting the best view and cut as actions occur) or offline.

A last term we add in the evaluation of a sequence is a score for the pacing of cuts and the duration of shots, which are important factors in the rhythmic perception of films [START_REF] Salt | Film Style and Technology: History and Analysis[END_REF]. When cutting from camera i to camera j at time t, this additional term takes into account the previous cutting time u(t) to estimate if the duration t -u(t) of the closing shot is right. The additional term can be written as a sum over all cuts:

C P ACE = s(t) =s(t+1)
C P ACE (t -u(t))

Shot composition

The scoring of a fragment is computed as a weighted sum over scores on action, visibility, and composition of characters on the screen.

Action

The Action term measures the amount of the scene action which is missed in the given fragment. We define a cost table A[a, s, p] which specifies the effectiveness of a shot size s and a profile angle p conveying an action a. For example, one can prefer framing a character speaking using a medium closeup from a front viewpoint. The computation of the Action term over fragment k is expressed with a weighted sum over all actions a occuring during this fragment. The weighting is expressed by the importance imp(a) of an action in the scene (type(a) represents the type of the action). s a,k represents the size of the shot for main character involved in action k and p a,k profil angle of main character involved in action k.

C ACT ION (k) = a imp(a)A[type(a), s a,k , p a,k ]
With a suitable choice of the A[a, s, p] coefficients, the action cost term can serve to enforce the Hitchcock principle, which states that the screen size of actors should be proportional to their importance in the scene [START_REF]Hitchcock-Truffaut[END_REF]. In our implementation, we tabulate the values in A[a, s, p] with four action types: facial actions (speak, listen, watch, turn, nod), hand actions (lift, pour, drink, eat), feet actions (walk, sit down, stand up) and no action (idle). Figure 1 illustrates the preferences for shot sizes and profiles for the special case of two hand actions : pour and drink.

Visibility

A good shot is a shot which maximises the visibility of the actions performed by the protagonists. To account for this, we express a visibility cost C V IZ which measures the overlapping area between projected bounding boxes of protagonists:

C V IZ = i,j area(boxi ∩ boxj)
where boxi is the projection of the bounding box of actor i on the screen. Figure 2 displays three shots with increasing visibility scores in a scene with two actors.

Look room

Following common practice, we favor shot composition where each actor is given enough screen space relative to the image frame, especially in the direction where he is looking. This is easily computed with the following cost function o

C LOOK = i δ(ei + λ(si)gi)
where ei is the screen position for the middle of the actor's eyes, gi is the screen vector of the actor's gaze direction, λ is a scalar function of the actor's screen size si and δ is the indicator function for being on-screen (within the image frame).

Shot transitions

A transition between shots always causes discontinuity. The art of the editor is to choose transitions minimally intrusive transitions by selecting appropriate shots and moments for cutting. A complete theory of what makes a cut intrusive is not currently available, although there has been work in film aesthetics [8, 9, 2] and cognitive psychology [START_REF] D'ydewalle | Perceptual and cognitive processing of editing rules in film[END_REF][START_REF] Smith | An Attentional Theory of Continuity Editing[END_REF][START_REF] Zacks | Film, Narrative, and Cognitive Neuroscience[END_REF] on the subject. For our purpose, we have found useful to compute the cost of a cut as a sum of terms measuring typical grammatical errors according to the classical style of continuity editing (continuities in the screen positions, gaze directions and motion directions of actors).

Screen continuity

The score of screen continuity in transitions prevents actors who appear in two successive shots to jump around the screen. Because the actor's eyes are the most important center of attention, we favor transitions which maintain the actor's eyes at the same screen location. We weight this term with the screen size of actors, so that continuity in the C SCREEN = 0.596 foreground receives a larger reward than in the background. As a result, screen continuity is enforced by minimizing:

C SCREEN = 0
C SCREEN = i∈S 1 ∩S 2 aijφ(|ei1 -ei2|)
where S1 ∩ S2 represents the set of actors shared between shots S1 and S2, e ik is the screen location of the middle of the eyes of actor i in image k and φ is a non-linear function of the screen distance such as a sigmoid or threshold function.

Each term in the sum is weighted with the average screen size ai = (si1 + si2) of the actor in the two images. Figure 3 shows examples of two cuts with increasing screen continuity scores.

Gaze continuity

Another important focus of attention when watching a movie is the gaze direction of actors. We propose a cost function that penalizes camera changes that cause apparent reversals in the actor's gaze directions. This cost is defined by:

C GAZE = i∈S 1 ∩S 2 aiδ(sign(xgi1) -sign(xgi2))
where xg ik is the x coordinate of the gaze direction for actor i in image k and δ is the Kroneker symbol. Figure 4 shows the examples of two cuts with increasing gaze continuity scores.

Motion continuity

Motion direction of actors in two successive shots represents another focus of attention. The corresponding transition cost penalizes camera changes that cause apparent reversals in the actor's motion, defined as:

C M OT ION = i∈S 1 ∩S 2 aiδ(sign(xmi1) -sign(xmi2))
where xm ik is the screen motion of the actor's eyes in image k measured in the x direction, and δ is the Kroneker symbol. Figure 5 shows examples of two cuts with increasing motion continuity scores.

C M OT ION = 1 C M OT ION = 0

Left to right ordering

The left to right ordering of actors is another important factor for ensuring screen continuity. Actors whose relative screen position are reversed appear to be jumping around, which attracts attention to the cut. We penalize such situations with the following penalty cost:

C ORDER = i,j∈S 1 ∩S 2 aijδ(sign(xei1-xej1)-sign(xei1-xej1))
where xe ik is the x coordinate of the actor's eyes in image k and δ is the Kroneker symbol. As in previous cases, each term is weighted with the average screen size aij = 2 k=1 (s ik + s jk ) of the actors in the two images. Figure 6 shows examples of two cuts with increasing left to right ordering scores.

Profile and size change

A type of transition which should be avoided is when the apparent size and profile angle of an actor remains the same in a sequence of two shots. The cut is interpreted as a sudden change in the actor's pose, also known as a jump cut. We model this transition cost as follows:

C JU M P = i∈S 1 ∩S 2 aiδ(si1 -si2)δ(|θi1 -θi2| ≤ 30)
where θ ik is the profile angle of actor i in image k. Thus, transitions on an actor with the same screen size and profile in both shots receive a penalty (see Figure 7).

We also penalize excessive changes in shot sizes, i.e. between a long shot and a close-up, because they make it more difficult for the viewer to recognize correspondences between actors in the two shots. This is enforced with the simple cost term where φ is a non-linear function of the size difference, such as a sigmoid or threshold function (see Figure 8).

C SIZE = i∈S 1 ∩S 2 φ(si1 -si2) C JU M P = 1 C JU M P = 0

Action line continuity

In addition to preserving the continuity of actors between successive shots, it is equally important to preserve the direction of the line of action between actors (usually the world line between their eyes). Thus, when cutting between actors A and B, the direction of the (AB) line needs to be preserved, even if the two actors are not simultaneously visible on-screen. This typical case occurs when actors are looking at each other: the cut is good when gaze directions cross each other in the successive shots, which we model as:

C LIN E = i∈S 1 ,j∈S 2 aijδ(sign(xei1-xej1)-sign(xei2-xej2))
where xe ik is x coordinate of the actor's eyes in image k and δ is the Kroneker symbol. Figure 9 shows examples of two cuts with increasing action line continuity scores.

Shot durations

In his book History of Film Style and Technology, Barry Salt asserts that shot durations in movies generally follow lognormal distributions, similar to sentence lengths in natural language [START_REF] Salt | Film Style and Technology: History and Analysis[END_REF] and proposes to use the parameters of the lognormal distribution as a signature of film editing styles.

Because shot durations are such an important element of film editing style, we introduce a duration cost per shot, measuring the deviation from a log normal law, where d is the duration of the shot, µ and σ are resp. the mean and the standard deviation of the log normal law

C P ACE (d) = (log(d) -µ) 2 2σ 2
The values for µ andσ can be left under the control of the user, be inferred from the pacing of actions, or be inferred from example movie scenes. Putting everything together, we now build the cost function for an arbitrary sequence of key shots, as a weighted sum of all its features. We choose the weights with a linear discriminant analysis (LDA) of shots and cuts labeled as 'grammatical' and 'ungrammatical'. LDA finds linear combinations of the cost features that minimize the overlap of the transformed distributions [START_REF] Duda | Pattern Classification[END_REF]. We separately set the weights with a first LDA for the shot terms using shot examples, then for the cut terms using cut examples. Finally, we arbitrarily set the relative weights W SHOT , W CU T and W P ACE to 2, 1 and 1, respectively representing the weighting of C SHOT , C CU T and C P ACE

Feature weight selection

C LIN E = 1 C LIN E = 0

BEST-FIRST SEARCH

The computation of an optimal sequence of shots consists in searching the path of least cost in our editing graph. Algorithms to solve these classes of problems (dynamic programming, A*-based algorithms) remain computationally complex in practice. Additionally, the problem we address displays a very large collection of solutions which yield similar costs (e.g. consider the case of symmetric viewpoints around an actor), and for which an optimal computation seems unnecessary.

We propose a sub-optimal best-first search through the editing graph. Given that the quality of the overall sequence strongly depends on the output of this search process, we propose to enhance the search by proposing an informed best-first search. This informed search uses a sliding observation window over the next fragments to locally reason on the best moment for a transition.

At a given depth in the search process (i.e. advancement in time over the fragments), a critical decision needs to be made whether to stay within the current shot, or to perform a transition to another shot. To inform this decision, we rely on this observation window over the next w fragments.

We study within this window the best transition to be performed, given the knowledge of the shots to come. If the best transition occurs immediately, the cut is performed. If the best transition occurs later in the observation window, we shift the window a fragment ahead and start the process over.

To compute the best moment for a transition inside the observation window we use an incremental scanning process. The process is illustrated in Figure 10. Given the current shot is c, for a given time t in the observation window and for each shot i = c, we compute the cost C CU T of a possible transition from shot c to shot i, and we compare it to the cost C N OCU T of staying in the current shot. If the Figure 10: Searching for the optimal transition in the observation window to decide whether to cut or stay in the shot. Each green/blue rectange represents a fragment of a shot. On the top image, the current optimal shot sequence is drawn in red and recommends to cut at time t. A scanning process over the observation window (window in light blue) is performed to seek for a possible better moment. On the bottom image, a sequence with a better cost is found (displayed in red). The observation window is then shifted ahead one fragment in time and the process starts over.

cost of staying in the current shot c is the minimal cost (ie C N OCU T (c) ≤ miniC CU T (c, i)), we extend its duration by ∆t and the observation window is shifted a fragment ahead. If there exists a shot i such that C CU T (c, i) < C N OCU T (c) at time t, we need to know whether to cut at the current time t to shot i, or to wait for a better moment. To implement this, the process explores the successive fragments at t + ∆t, t + 2∆t, ..t + w∆t in the observation window until a cost lower than CCUT (c, i) is found. In such case, the best cut occurs later and the observation window can be shifted a fragment ahead. Otherwise, t represents the best moment for a transition and a cut is performed towards shot i. We fixed the size of the observation window to the mod m of the log normal law (m = log(µ)): w = m/∆t. Indeed, the evaluation over the window only considers one possible transition between shots, which optimally occurs every m seconds. Any window size larger than the mod would provide an erroneous estimation (considering one cut when two may occur) and any size smaller would not fully consider the cost of the pacing over the next shot.

EXPERIMENTAL RESULTS

Experimental results have been generated using our system on the 1984 animation content and annotated scene 4 . The duration of the animation is 3 minutes, with over 70 actions occurring with overlaps.

Currently, the duration ∆t of a fragment is set to 250ms (i.e cuts between shots may occur every 250ms). For each action occurring in the scene, we generate between 50 shots (single-character actions) and 80 shots (two-character actions), corresponding to classical cinematic viewpoints.

Figure 11 presents a snpashot of our system in action, with details on the current action and values of all cost functions. When executed offline, our fully automatic method takes 15 seconds on the three-minute sequence in 1984. When executed online, our method works in real-time with a latency of approximately two seconds.

CONCLUSION

We have introduced a novel framework for virtual cinematography and editing which adds an evaluation function to previous approaches. Experimental results demonstrate that our approach is efficient in separating correct from incorrect shot sequences. Furthermore, we have introduced an efficient search strategy for finding the best sequence of shots from a large number of candidates generated by traditional film idioms.

In future work, we would like to extend the approach to higher-level criteria, including story advancement, repetition and rhythm and possibly even emotion. More generally, an important research issue is the discovery of film idioms and styles from examples. We believe the proposed approach makes it possible to add style-specific terms in the evaluation function and we will investigate varying the scoring function to generate movies with varying styles.

C 2 C 2 Figure 1 :Figure 2 :

 2212 Figure 1: Action scores. Top: Action Drink. Bottom: Action Pour. Left: Poor. Middle: Better. Left: Best.

Figure 3 :Figure 4 :

 34 Figure 3: Screen continuity scores. Left: cutting from left to right has the leftmost character jumping to the screen center resulting in a poor cut. Right: keeping the center character in the same screen location produces a smooth cut.

Figure 5 :

 5 Figure 5: Motion continuity score. Left: the main character's head is oriented differently in left and right shots, resulting in a poor cut. Right: keeping the head orientations consistent results in a better cut.

Figure 6 :

 6 Figure 6: Left to right ordering scores. Left: the foremost character moves from the rightmost position to the leftmost position, resulting in a poor cut. Right: keeping the relative ordering of all characters results in a better cut.

Figure 7 :Figure 8 :

 78 Figure 7: Jump cut score: transitions with insuffisant change in size or orientation wrt actors do not make good cuts (left) while transitions with significant changes make good cuts (right).

Figure 9 :

 9 Figure 9: Line of action score. Top: In the left image, the gaze direction of the main actor defines the line of action. Bottom: the gaze direction changes because the camera has crossed the line, resulting in a poor cut. Bottom: keeping the line of action result in a smooth cut

Figure 11 :

 11 Figure11: Snapshot of our system in action, showing the on-going actions (bottom part), the costs (middle part) and the selected shot (top part). The illustrated shot clearly displays the action (the character is eating), and respects head-rooom and lookroom., with a sufficient visibility even if another character is in the frame.

www.moviestorm.co.uk

www.reallusion.com/iclone

http://www.xtranormal.com

kindly made available by the authors of[START_REF] Lino | A real-time cinematography system for interactive 3d environments[END_REF] at http://www. cameracontrol.org/1984-content