Felipe Aguirre

Mohamed Sallak

Walter Schön

Generalized expressions of reliability of series-parallel and parallel-series systems using the Transferable Belief Model

Probability theory is well suited to treat uncertainties when their origin comes only from the natural variability of components' failure (aleatory uncertainty). On the other hand, if the uncertainties are due to incompleteness, imprecision or ignorance of the reliability data (epistemic uncertainty), several theories can be used. Previous studies have shown that the Transferable Belief Model (TBM) which is an interpretation of the Dempster Shafer theory is a well suited framework to treat both types of uncertainties. Nevertheless, past experiences have proven that the computational cost of the TBM based model grows exponentially with the size of the system. To overcome this situation, generalized expressions were defined so as to have a more efficient way to study the systems' reliability of series-parallel and parallel-series configurations. Through the use of these expressions, there is no need to go by the TBM operations (conjunctive rule, extensions, etc.) to evaluate the overall system's reliability.

INTRODUCTION

Over the last two decades, many researchers have used other theories different from probability theory, in reliability and risk assessments to treat uncertainties.

There are different ways of classifying uncertainty. One of the most widely used is to divide it in two different types: aleatory uncertainty and epistemic uncertainty. The former, also called irreducible uncertainty, arises from natural stochasticity or environmental variation across space or through time. The latter, also called reducible uncertainty, arises from incompleteness or ignorance of knowledge or data [START_REF] Oberkampf | Challenge problems: uncertainty in system response given uncertain parameters[END_REF].

For many years, the probability theory has been used as the primary tool in reliability and risk assessments. However, in the presence of epistemic uncertainty, other theories are better suited than probability theory. Moreover, it has been proven that uncertainties in reliability and risk assessments are mainly epistemic [START_REF] Drouin | Guidance on the Treatment of Uncertainties Associated with PRAs in Risk-informed Decision making[END_REF]. The most promising theories to treat aleatory and epistemic uncertainty are:

• Probability bound analysis [START_REF] Moore | Methods and Applications of Interval Analysis[END_REF]).

• Upper and lower previsions [START_REF] Walley | Statistical reasoning with imprecise probabilities[END_REF].

• Fuzzy set theory [START_REF] Zadeh | Fuzzy sets[END_REF]).

• Possibility theory [START_REF] Zadeh | Fuzzy sets[END_REF]).

• Dempster-Shafer theory [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]).

From the above theories, the Dempster-Shafer (D-S) theory has been proven as a well suited theory for the treatment of aleatory and epistemic uncertainty in the reliability analysis [START_REF] Sallak | The Transferable Belief Model for reliability analysis of systems with data uncertainties and failure dependencies[END_REF], Aguirre et al. 2010), furthermore, it allows also the modelisation of failure dependencies between components. D-S theory generalizes both the probability theory and sets theory, even though the mechanics of operations in these three theories are completely different. The D-S theory has several interpretations: Dempsters model [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF], the theory of hint (Kohlas and Monney 1995), the probability of modal propositions model [START_REF] Ruspini | The logical foundations of evidential reasoning[END_REF]) and the Transferable Belief Model (TBM) [START_REF] Smets | The transferable belief model[END_REF]. In this work, the TBM has been chosen because it is a model developed outside the scope of probability theory and avoids the criticisms that the D-S theory is understood as a special form of upper and lower probability theory [START_REF] Aven | Interpretations of alternative uncertainty representations in a reliability and risk analysis context[END_REF].

Past experiences have proven that the computational cost of the TBM based model grows rapidly with the size of the system. This is due to the fact that the cardinality of the domain where the resulting mass function is defined is equal to 3 n , with n being the size of the system. To overcome this situation, generalized expressions are introduced on the paper so as to have a more efficient way to study the reli-ability of systems. These expressions can be used to study series-parallel, parallel-series and combinations of series-parallel and parallel-series systems.

The expressions were obtained using the method of minimal cuts and the general expressions of reliability of series and parallel systems presented in [START_REF] Sallak | The Transferable Belief Model for reliability analysis of systems with data uncertainties and failure dependencies[END_REF]. The advantage of this equations is that any system that can be represented as a parallelseries or series-parallel system can be studied easily and faster. This way, there is no need to go by the TBM operations, like the conjunctive rule of combination, thus, avoiding the exponential growth of the TBM.

Section 2 presents an introduction to the TBM theory and explains the mechanics of the TBM reliability assessment model. Section 3 talks about the computational cost of the TBM based model and discusses possible optimization methods. Section 4 introduces the generalized expressions for series-parallel and parallel-series systems. Finally, section 5 exposes two applications of the expressions and section 6 finishes with some conclusions.

TBM BASED RELIABILITY MODEL

The TBM was introduced by [START_REF] Smets | The transferable belief model[END_REF] as a subjectivist interpretation of D-S theory. The D-S theory, also called evidence theory, was first described by [START_REF] Dempster | Upper and lower probabilities induced by multivalued mapping[END_REF] with the study of upper and lower probabilities and extended by [START_REF] Shafer | A Mathematical Theory of Evidence[END_REF]. The TBM represents a unique framework for representing and manipulating aleatory and epistemic uncertainties. In a finite discrete space, the TBM can be interpreted as a generalization of probability theory where probabilities can be assigned to any subsets instead of singletons only. In this section, basic notions, extended operations, and terminology of TBM are explained. For a more detailed exposition see [START_REF] Smets | The transferable belief model[END_REF].

Basic Probability Assignment (BPA)

A Basic Probability Assignment (BPA) on the frame of discernment Ω, also called Basic Belief Assignment (BBA), is a function, m Ω : 2 Ω → [0, 1], which maps belief masses not only on events but also on subsets of events (The power set 2 Ω ), such that:

A∈2 Ω m Ω (A) = 1
(1)

As an example, let's consider Ω = {x 1 , x 2 , x 3 } as our frame of discernment. Then, x 1 , x 2 and x 3 are elementary propositions and mutually exclusive to each other. Through the use of the TBM, a piece of evidence represented by a BPA allocates beliefs to the subsets belonging to the power set

2 Ω = {{∅}, {x 1 }, {x 2 }, {x 3 }, {x 1 , x 2 }, {x 1 , x 3 }, {x 2 , x 3 }, Ω}
in such a way that equation 2.1 is respected.

Every subset A to which a belief different from zero is allocated (m Ω (A) = 0) is called a focal element and this value represents the belief that the answer is in A [START_REF] Smets | The transferable belief model[END_REF]. A BPA having a singleton {x} (x ∈ Ω) as a unique focal set represents full knowledge. A BPA having only singletons as focal sets is equivalent to probabilities. A BPA having Ω as a unique focal set represents complete ignorance and is called vacuous. In addition, BPAs has further properties, which distinguishes it from being a probability function:

• It is not required that m(Ω) = 1. • It is not required that m(A) ≤ m(B) when A ⊆ B.
• There is no relationship between m(A) and m( Ā).

• m(A) + m( Ā) does not always have to be 1.

Conjunctive combination rule

The conjunctive combination rule is used to combine two distinct pieces of evidence m Ω i and m Ω j that are reliable and come from two different sources i and j [START_REF] Smets | The transferable belief model[END_REF]. The rule is implemented using the following equation:

m Ω i∩j (H) = A∩B=H m Ω i (A)m Ω j (B), ∀A, B, H ⊆ Ω (2)
Other combination rules exit (see [START_REF] Sentz | Combination of evidence in dempster-shafer theory[END_REF] but, in this paper, only the conjunctive rule of combination is needed

Operations on Joint Spaces

The marginalisation of a BPA m ΩxΩy↓Ωx on the frame of discernment Ω x is defined by:

m ΩxΩy↓Ωx (A) = B⊆ΩxΩy/P roj(B↓Ωx)=A m ΩxΩy (B) ∀A ⊆ Ω x (3) Where P roj(B ↓ Ω x ) = {x ∈ Ω x /∃y ∈ Ω y , (x, y) ∈ B}.
The inverse operation is a particular instance of vacuous extension. Consider a BPA m Ωx defined on Ω x . Its vacuous extension on Ω x Ω y is defined by:

m Ωx↑ΩxΩy (B) = m Ωx (A) if B = A × Ω y 0 otherwise. ∀ A ⊆ Ω x (4)

Belief and plausibility functions

The belief Bel and plausibility Pl functions for a subset A are defined as follows:

Bel(A) = B⊆A m Ω (B) (5) P l(A) = B∩A =∅ m Ω (B) ∀ A ⊆ Ω, ∀ B ⊆ Ω (6)
Bel(A) is the degree to which the evidence supports A and P l(A) is the maximal degree of support that could be assigned to A if there were more available evidence. P l(A) may also be defined as the extent to which we fail to disbelieve the hypothesis of A. [Bel(A), P l(A)] can be viewed as the interval that describes the uncertainty of A. The functions Bel and P l, although being also function mapping events A into [0, 1] and mapping ∅ into 0 and Ω into 1, do not fulfill in the general case the sub-additivity properties given for probability.

Reliability assessment

A proper reliability model using the TBM was introduced by [START_REF] Sallak | The Transferable Belief Model for reliability analysis of systems with data uncertainties and failure dependencies[END_REF] and further studied in [START_REF] Aguirre | Transferable belief model for incorporating failure dependencies in reliability analysis under data uncertainties[END_REF][START_REF] Aguirre | Prise en compte des incertitudes dans les études de fiabilité : Comparaison entre le modèle de croyances transférables et les méthodes de simulations de Monté-Carlo[END_REF]. In these works, different points are treated concerning the elicitation of reliability masses, the representation of the system's configuration, the failure dependencies between components and a comparison with other methods is made. Expressed in words, the reliability analysis through the use of the TBM can be defined as follows:

1. A binary state is considered. Components' states and the system states are defined over a frame of discernment Ω = {F i , W i }, with i being a number that represents a component or s for the system.

2. The reliability of each component is expressed in the form of a mass function m Ω i that maps the power set

2 Ω i = {(F i ), (W i ), (F i , W i )} to the interval [0, 1].
The masses given to F i and W i represents, respectively, the belief on the Failure state and on the Working state. The mass given to (F i , W i ) represents the epistemic uncertainty, that is, a measure of the ignorance about a components state. The elicitation process of this masses is based on experts' opinions.

m Ω i ({F i }) = f i m Ω i ({W i }) = w i m Ω i ({W i , F i }) = 1 -w i -f i i = 1, 2 . . . n (7)
Note that if m Ω i ({W i , F i }) = 0, the mass is called bayesian mass function and if this holds for every component i, then, the TBM model will yield the same results as the classical probability reliability analysis. Here there are two things to notice: first, this proves that probability theory is a particular case of the D-S theory (in our case we use the TBM interpretation). Second, the epistemic uncertainty is represented by the value assigned to m Ω i ({W i , F i }), therefore, this value being equal to zero means that only aleatory uncertainty is present for the given component.

3. The configuration of the system is then represented by a categorical mass function m Ω Conf ig . This type of mass is simply a mass containing only one focal element and represents the certitude that the truth can be found in this focal element. As it is consider that the system configuration is well known, this certitude is expressed by coding the truth table of the system configuration to a focal element and giving it a mass of 1. The focal element will contain every possible combined states and will act as a filter that keeps only the states representing the given system. 4. Once the reliability of components and the system's configuration are expressed by a mass function, all these masses are combined so as to obtain at the end the system's reliability. First, each reliability mass m Ω i must be extended to the product space Ω 1 Ω 2 • • • Ω n Ω S using Eq. ( 4). Then, all of the components' reliability masses and the system's configuration mass m Ω Conf ig are combined using the conjunctive rule of combination (Eq. 2). Finally, the obtained mass is projected to the frame of discernment of the system's states Ω s using Eq. ( 3). This process is represented by Eq. ( 8)

m Ω S = (⊕ n i=1 m Ω i ↑Ω 1 Ω 2 •••ΩnΩ S ⊕ m Ω 1 Ω 2 •••ΩnΩ S Conf ig
) ↓Ω S (8)

The system's reliability R S is expressed in terms of a belief and a plausibility measure obtained from the resulting mass m Ωs using Eqs. ( 5) and ( 6). It will be bounded by:

R S ∈ [Bel({W S }), P l({W S })] (9)
For further detail of the TBM reliability model, see [START_REF] Sallak | The Transferable Belief Model for reliability analysis of systems with data uncertainties and failure dependencies[END_REF].

COMPUTATIONAL COST OF THE TBM MODEL

The TBM reliability model and the classical probability reliability model have their differences. From one side, the TBM model is capable of treating epistemic uncertainty about the reliability of components, about the systems configuration and even about the dependencies between the failure of components. This capability is one of the most important things the TBM has to offer in comparison to the classical probability model, a proper treatment of epistemic uncertainty, not leaving a side off course the aleatory uncertainty. However, it is a capability that has a cost in terms of computational time. Indeed, the computational cost of the model grows exponentially with the size of the studied system. From Eq. ( 7), it can be seen that the reliability mass m Ω i of each component is defined over 3 focal elements. As depicted in step 4 of section 2.5, each m Ω i is extended to the product space Ω 2 • • • Ω n Ω S and then, all the m Ω i are combined with each other

(⊕ n i=1 m Ω i ↑Ω 1 Ω 2 •••ΩnΩ S ).
As each component is defined over three focal elements, and thanks to the nature of the conjunctive combination rule, the resulting mass after combination is defined over 3 n focal elements with each of the focal elements having from 2 to 2 n+1 elementary events (defined over the product space

Ω 2 • • • Ω n Ω S ).
To start with, doing the calculation by hand can be a pretty hard task for a system of as little as four components. The resulting mass would have 81 focal elements with up to 32 elementary events. As a response to this inconvenient, a Matlab TBM Toolbox has been created capable of doing a reliability analysis using the TBM model, hence, avoiding the tough task of doing this by hand. The toolbox makes a numerical and analytical analysis. However, as the computational cost grows exponentially (Figure 1) a clever way to combine the masses and treat the model has to be implemented.

In order to optimize the TBM operations and saving time and space, some computation algorithms were given in [START_REF] Shafer | Propagating belief functions in qualitative markov trees[END_REF][START_REF] Almond | Graphical belief modeling[END_REF]. The idea of these algorithms lies in doing local calculations in smaller product spaces so as to reduce the exponential growth of the TBM. For the case of reliability analysis, the idea of the algorithms is to divide the system in subsystems and to analyze the reliability of each subsystem to further calculate the reliability of the whole system. This approach can go as deep as needed and even divide the subsystems in more subsystems substantially extending the computational limit of the size of the system.

On the other hand, [START_REF] Smets | Belief functions: The disjunctive rule of combination and the generalized bayesian theorem[END_REF] introduced a different approach that propagates conditional belief functions over a directed acyclical network called belief network. The advantage is that the edges of the graphs are weighted by conditional belief functions and not by joint belief functions over a product space, thus, its a more optimal method in terms of computational cost. The approach is less general but, the loss of generality doesn't affect the reliability analysis, plus, its also more natural to asses conditional belief functions than joint probabilities over a product space. Using this method, fault trees analysis could be extended in a proper way to integrate belief functions to model the gates and the failure occurrences. [START_REF] Smets | The application of the matrix calculus to belief functions[END_REF] introduced matrix calculus using the Möbius transformation to the TBM. This approach simplifies greatly the development of software and optimizes the computational time but, there is still the problem of the exponential growth.

To overcome the computational time limit, generalized expressions were defined so as to have a more efficient way to study the reliability of systems. These expressions can be used to study series-parallel, parallel-series.

GENERALIZED EXPRESSIONS FOR SERIES-PARALLEL AND PARALLEL-SERIES SYSTEMS USING THE TBM

The expressions were obtained using the method of minimal cuts and minimal paths. The advantage of this equations is that any system that can be represented as a parallel-series or series-parallel system can be studied easily and faster. This way, there is no need to go by the TBM operations each time you want to compute the reliability of a system, thus, the inherent exponential growth of the TBM is avoided.

The system success can be represented trough the use of minimal cuts S cut or minimal paths S path with the following equations:

S path = N T i=1 n(T i ) j=1 W T i (j) S cut = N C i=1 n(C i ) j=1 W C i (j) (10)
Starting from the generalized equations of the parallel and series systems (Table 1) and from the principle of minimal paths and minimal cuts (Eqs. 10), the generalized reliability expressions shown in table 2 are obtained. The system reliability will be bounded by R s ∈ [Bel{W S }, P l{W S }]. The following notation is used:

N T Nb. of minimal paths in the system N C Nb. of minimal cuts in the system n(T i ) Nb. of components in the i th minimal path n(C i ) Nb. of components in the i th minimal cut T i Index set of the i th minimal path C i Index set of the i th minimal cut (1

-m{W i }) n i=1 m{W i } P l(W S ) 1 - n i=1 m{F i } n i=1
(1 -m{F i })

Minimal cuts

Bel(W S )

N C i=1   1 - n(C i ) j=1 1 -m{W C i (j) }   P l(W S ) N C i=1   1 - n(C i ) j=1 m{F C i (j) }  

Minimal paths

Bel(W S ) 1 -

N T i=1   1 - n(T i ) j=1 m{W T i (j) }   P l(W S ) 1 - N T i=1   1 - n(T i ) j=1 1 -m{F T i (j) }  
It has to be taken into account that the presented expressions are limited to series-parallel and parallelseries systems (Kuo 2001, pp. 13-16). In the case of repeated events, the correct way to proceed is to use disjoint cuts or paths. In this work, we use the minimal paths expressions for the series-parallel systems and the minimal cuts expressions for the parallel-series systems.

For the case were all of the components have the same reliability values (m Ω i ({W i }) = w, m Ω i ({F i }) = f ) and the system is symmetrical (e.g., fig. 2, system b), the expressions are reduced to those shown in table 3.

Furthermore, if the reliability belief functions for the components are bayesian belief functions (m Ω i ({W i , F i }) = 0, ∀i = 1, 2 . . . n), the system reliability will also be defined by a bayesian belief function and the following equality will hold: Bel(W S ) = P l(W S ).

Table 3: Generalized reliability belief functions through the use of minimal cuts and minimal paths. Special case where the system is symmetric and its components have the same reliability Minimal cuts

Bel(W S ) 1 -(1 -w) n(C) N C P l(W S ) 1 -f n(C) N C Minimal paths Bel(W S ) 1 -1 -w n(T ) N T P l(W S ) 1 -1 -(1 -f ) n(T ) N T

APPLICATION

In order to demonstrate the applicability of the expressions and the advances in computational time that can be achieved, a reliability analysis of the two different systems depicted in figure 2 is performed. For simplicity, all of the components have the same reliability, however the expressions can be used for the more general case where all of the components have different reliabilities. System (a) is composed of three subsystems, two series subsystems and one series-parallel subsystem. Using the generalized expressions from table 2, the obtained belief and plausibility on the working state of the system is:

Bel(W S ) = (1 -(1 -w) 2 (1 -w 2 ))w 4 = w 5 (w 3 -2w 2 + 2) P l(W S ) = (1 -f 2 (1 -(1 -f ) 2 ))(1 -f ) 4 = (1 -f ) 4 (f 4 -2f 3 + 1) (11)
System (b) is a parallel-series system, using the generalized expressions from table 3, The belief and plausibility on the working state of the system is:

Bel(W S ) = (1 -(1 -w) 3 ) 3 P l(W S ) = (1 -f 3 ) 3 (12)

Comparison

Using the Matlab TBM toolbox, the same results are obtained as in Eqs. ( 11) and ( 12) but, at a higher computational cost. For the system (a), the time of calculation is of approximately one hour and for system (b) it is of approximately ten minutes (launched in a server with 32 Gb of RAM and an octo dual core Opteron 8218). On the other hand, using the general expressions the computational cost is insignificant (a fraction of a second). The reliability of both of the proposed systems can be easily studied by hand using the proposed general expressions, whereas by the means of the TBM reliability model it would be an long task for systems of these sizes or bigger. Note that thanks to the nature of the TBM reliability model, the computational time depends very little on the architecture of the system compared to the computational cost of the TBM. In fact, the computational time depends greatly on the size of the system, as shown in the application, a system of 8 components takes 10min and a system of 9 components takes 1hr. Furthermore, a system of 10 components takes 5hr. It can be noted that the computational time grows exponentially with the size of the system. In contrast, using a simple code that implements the presented generalized expressions, the computational limit is significantly higher. For example, a parallelseries system of 10 million components can still be studied in a fraction of a second.

CONCLUSIONS

Generalized reliability expressions for parallel-series and series-parallel systems using the TBM have been presented. The expressions represent a significant advance in terms of the computational limit of the theory. More precisely, they allow us to study systems with a considerably higher number of components. However, even if the TBM reliability model has a higher computational cost, it still represents a formal framework to continue the advances in the application of the TBM theory in the reliability analysis. Moreover, the model can be further optimized by using graphical methods based on local computations on reduced product spaces or by the implementation of conditional belief functions.

Figure 1 :

 1 Figure 1: Computational time as a function of the size of the system (launched in a server with 32 Gb of RAM and an octo dual core Opteron 8218)

Figure 2 :

 2 Figure 2: Reliability block diagram of the studied systems.

Table 1 :

 1 Reliability belief function of parallel and series systems with n components

	Parallel system	Series system
	n
	Bel(W S ) 1 -
	i=1

Table 2 :

 2 Generalized reliability belief functions through the use of minimal cuts and minimal paths.


O Legendre

H Bertin

O Garel

H Mathias

S Megherbi

K Jafari

J Juillard

E Colinet

A Low-Cost, Built-In Self-Test Method for Resistive MEMS sensors

This paper illustrates the experimental application of the LIMBO method, an identification method based on binary observations dedicated to the (self-) test of integrated electronic and electromechanical systems, such as MEMS. The tested MEMS device is a micro-wire used as a heating resistor, inserted in a Wheatstone bridge. We show how the impulse response and the offset of the micro device are estimated only using binary inputs and outputs and straightforward calculations, which can easily be implemented on an FPGA. This approach only requires a 1-bit ADC and a 1-bit DAC, which makes it very amenable to integration and highlights its suitability for the test of systems based on resistive sensor and/or actuator.

Motivation and results

Self-testing and self-adjustment are very desirable features for micro-fabricated devices, because, as characteristic dimensions of electronic devices and systems become smaller, these devices become even more subject to dispersions, mostly due to variations in the fabrication process, or to changes in the operating conditions (temperature, ageing, etc.). However, most existing system identification methods [START_REF] Ljung | System identification -theory for the user[END_REF][START_REF] Walter | Identification of parametric models from experimental data[END_REF] rely on a high-resolution digital measurement of the system's output using an N-bit ADC (N>>1), which is not cost effective in terms of scaling and design time. On the other hand, LIMBO (LMS-based Identification Method using Binary Observations) requires only a 1-bit ADC [START_REF] Jafari | A recursive system identification method based on binary measurements[END_REF][START_REF] Juillard | Estimation paramétrique monobit online[END_REF]. As pictured in Fig. 1, the system is stimulated with a (binary) random sequence and its Finite Impulse Response (FIR) and its offset are estimated by comparing the sign of the output signal to that of a parametric model, updated online (Fig. 2) so as to minimize data storage requirements.

We show here the very first implementation of LIMBO within an experimental setup. A two-wire resistive device, based on microwire heating resistors, shown in Fig 3, is a natural start candidate, because of its great ease of use. The value of the gauge resistance is sensitive to the ambient temperature, to the heating induced by the bias voltage and its transient behaviour, which determines the system bandwidth, may also be subject to environmental variations [START_REF] Osisik | Boundary value problem of heat conduction[END_REF][START_REF] Legendre | High resolution micro-Pirani gauge with transient response processing[END_REF][START_REF] Mailly | Micromachined thermal accelerometer[END_REF]. LIMBO is used to evaluate the time constant of the system (hence its bandwidth) and the offset at the output of a Wheatstone bridge, in which the gauge is placed.

The bridge is biased with a DC voltage V b , to which a binary random input sequence v in =±v is added. The output signal V out is amplified and digitized with, on one hand, a 1-bit ADC and, on the other hand, a 16-bit ADC for comparison of a classical correlation-based parameter estimation method to the results obtained with LIMBO. The measurement setup and its typical values are given in Fig. 4.

Experimental results show that the bandwidth of the trial device are estimated with 0.4% accuracy, the offset with 7% accuracy. Evaluation of the performances shows that LIMBO yields results comparable to those obtained with a standard parametric estimation method based on the 16-bit output signal (Fig. 56).

?

k u k s k y k θ ˆ k y ˆ k s ˆ Update rule Experimental setup ? ˆk k s s  1 -Define   T L k k k u u 1 1     φ . 2 -Calculate k T k k y θ φ  . 3 -Update k θ ˆ depending on   k k y sign s  a - k k k k s s θ θ 1     . b - k k T k k k k k k y s s φ φ φ θ θ 2 1       4 -Normalize 1 ˆ k θ .

Fig. 1 -

 1 Fig. 1 -Block diagram of the LIMBO method. The measured output s k are 1  . The inputs u k may also be binary.

Fig. 2 -Fig. 3 -

 23 Fig. 2 -At sample k, the offset at the input of the 1-bit ADC is given by   1 ˆk θ , the unknown impulse response by   1 : 2 ˆ L k θ .

Fig. 4 -

 4 Fig. 4 -Experimental setup. The resistor in the upper-right branch is used to adjust the offset.

Fig. 5 -

 5 Fig. 5 -Impulse response estimated with LIMBO (continuous line) based on 2×10 4 samples (1s) of u k

Fig. 6 -

 6 Fig. 6 -Histograms of the offset and time constant estimated with LIMBO, based on 50 1s-long measurements. Increasing the observation length results in an increased accuracy.


Elodie Hatchi

Laurent Le Cam

Geneviève Rodier

Claude Sardet

Genevi Ve Rodier

E4F1 dysfunction results in

Keywords: Animals, Autophagy, Cell Survival, Cell Transformation, Neoplastic, pathology, Disease Models, Animal, Humans, Leukemia, Myeloid, metabolism, pathology, Mice, RNA, Small Interfering, metabolism, Reactive Oxygen Species, metabolism, Repressor Proteins, metabolism E4F1, histiocytic sarcoma, mitochondria, autophagy, cell death, leukemic cells, reactive oxygen species

suggesting it is an important component of these two gatekeeper tumor suppressor pathways that are commonly altered during tumorigenesis. However, genetic data support the notion that E4F1 cellular functions extend beyond these 2 essential oncogenic pathways, leading us to address the unknown p53-and pRb-independent functions of E4F1 during tumorigenesis. To answer this question, we used a genetically engineered mouse model based on the null and conditional knockout (KO) alleles. To circumvent the potential Ink4a/Arf E4F1 defects associated with inactivation in the whole organism, we generated a hematopoietic-specific tumor prone mouse model by E4F1 transplanting hematopoietic stem cells (HSC) harvested from compound mice into lethally irradiated Ink4a/Arf KO; E4F1 flox, Cre-ER wild-type recipient animals. Using this strategy, we generated a fully penetrant mouse model of histiocytic sarcoma, a myeloid leukemia originating from the monocyte/macrophage lineage. In this model, could be specifically and acutely inactivated in the hematopoietic E4F1 system and HS upon 4-hydroxy-tamoxifen (4OHT) administration (4OHT activates the latent Cre-ER recombinase). Our data show that inactivation delays tumor progression in this mouse model and induces tumor regression in established HS. E4F1

Cellular and molecular analyses of HS cell lines derived from this animal model indicatet that dysfunction induces E4F1

mitochondrial defects that lead to overproduction of superoxide anions (ROS) followed by autophagic cell death. This autophagic response is abolished in the presence of ROS scavengers or activators of cellular anti-oxidant defenses, indicating that these ROS are the cause of cell death rather than an indirect consequence of the loss of viability. Importantly, similar mitochondrial defects are also observed in various human myeloid leukemic cell lines upon shRNA-mediated depletion of E4F1. These mitochondrial defects correlate with functional alterations of the electron transport chain characterized by increased consumption of 0 but inefficient ATP production.

2 Surprisingly, whereas these mitochondrial dysfunctions lead to massive autophagic cell death in transformed cells, they have minor consequences on normal differentiated hematopoeitic cells. Although we currently do not know the exact reasons for this differential sensitivity, these results suggest that cancer cells are addicted to E4F1 control on mitochondria, an addiction that could reflect metabolic " "

adaptations associated with cell transformation. Consistent with this notion, our pilot study on human AML bone marrow samples suggests that the E4F1 protein is overexpressed in leukemic cells. The metabolic alterations that render cancer cells sensitive to E4F1-depletion and that require its overexpression for survival may represent a very interesting Achilles heel of tumor cells that could be the basis for new ' anti-tumor strategies.

The role(s) of ROS and autophagy during tumorigenesis remains controversial. On one hand it has been suggested that low ROS levels promote transformation by inducing genomic alterations. On the other hand, ROS can have more beneficial roles by acting as second messengers that modulate cellular pathways involved in metabolism and differentiation. In addition, high levels of ROS are also clearly associated with cell death and the pro-oxidant properties of many anticancer drugs are undoubtly involved in their efficiency. Autophagy can also play dual roles during the process of tumorigenesis, and experimental evidence supports both tumorigenic and tumor suppressive functions of autophagy. Under hypoxic, oxidative-and/or metabolic-stress conditions, autophagy likely promotes tumor development by clearing damaged organelles and protein aggregates, thereby attenuating the immune response and providing essential metabolites required for cancer cell survival. However, inhibition of autophagy might also promote tumorigenesis as illustrated by the increased tumor incidence observed in inactivated mice. beclin-Our data identify the multifunctional E4F1 protein as a novel essential regulator of this complex mitochondria-ROS-autophagy network that is implicated in cell survival of leukemic cells with deficiencies in the p53 and pRb-pathways. Our findings are of potential therapeutic interest to develop novel anticancer treatments based on ROS-induced autophagic cell death, in particular in tumors harboring genetic alterations of the apoptotic machinery. Nevertheless, given the pleiotropic functions of E4F1 during early embryonic development and in adult tissue homeostasis, notably through its role in epidermal stem cell maintenance, there is an urgent need to identify the full " repertoire of E4F1 targets (transcriptional targets and substrates of its E3-ligase activity) involved in mitochondrial homeostasis and " metabolism in order to help in designing more subtle anticancer strategies altering some but not all E4F1-associated activities. Further work will be necessary to demonstrate that E4F1 is a real therapeutic target, but our data suggest for the first time that some E4F1-regulated metabolic activities are essential for cell survival of transformed cells.

Acknowledgements:

Supported by funding from the Centre National de la Recherche Scientifique, the Agence Nationale pour la Recherche, the Association pour la Lutte contre le Cancer, the INSERM Avenir program, the Leukemia Program from the Fondation de France, the British Association for International Cancer Research foundation, and la Fondation pour la Recherche M dicale. é


Christophe Lino
email: christophe.lino@inria.fr

Marc Christie
email: marc.christie@inria.fr

Roberto Ranon
email: roberto.ranon@uniud.it

William Bares
email: bareswh@millsaps.edu

A Smart Assistant for Shooting Virtual Cinematography with Motion-Tracked Cameras

Keywords: H.5.1 [Multimedia Information Systems]: Animations, Video Virtual Cinematography, Motion-Tracked Virtual Cameras, Virtual Camera Planning

This demonstration shows how an automated assistant encoded with knowledge of cinematography practice can offer suggested viewpoints to a filmmaker operating a hand-held motion-tracked virtual camera device. Our system, called Director's Lens, uses an intelligent cinematography engine to compute, at the request of the filmmaker, a set of suitable camera placements for starting a shot that represent semantically and cinematically distinct choices for visualizing the current narrative. Editing decisions and hand-held camera compositions made by the user in turn influence the system's suggestions for subsequent shots. The result is a novel virtual cinematography workflow that enhances the filmmaker's creative potential by enabling efficient exploration of a wide range of computer-suggested cinematographic possibilities.

INTRODUCTION

Creating camera edits and movements for computer generated animation remains time-consuming and largely manual endeavor requiring cinematographic skill and experience with 3D animation packages. Some technically-savvy filmmakers are now using motion-sensing devices to capture complex virtual camera movements rather than key-framing the camera [START_REF] Autodesk | The new art of virtual moviemaking[END_REF]. However, these existing devices operate as plugins to animation packages such as Maya that offer an infinity of expressive animation power, but with a corresponding steep learning curve and an interface which is not designed around cinematographic concepts.

Researchers in automated virtual cinematography systems have produced increasingly sophisticated algorithms that can generate virtual 3D camera work that mimics textbook guidelines [START_REF] Mcdermott | Storyboard frame editing for cinematic composition[END_REF][START_REF] Elson | A lightweight intelligent virtual cinematography system for machinima generation[END_REF][START_REF] Lino | A Real-time Cinematography System for Interactive 3D Environments[END_REF]. But in succeeding to reduce human effort, these automated systems also limit the input of creative human filmmakers and as a result produce cinematography of little creative value. Our Director's Lens system introduces a novel workflow that combines the creative human intelligence with the computational power of an automated cinematography system, to enable a filmmaker to explore a variety of automatically suggested virtual camera compositions (see Figure 2), that represent a variety of cinematically distinct ways one might film a given shot and which are consistent in user-specified continuity properties with the previous shot. For computing its suggestions, the system exploits an annotated screenplay which provides the narrative context in the form of text descriptions of locations, subjects, and time-stamped actions, with links to the 3D models employed in the scene. Moreover, the system tries to mimic user's composition from previous shots.

With the help of a motion-tracked virtual camera (see Figure 1), the cinematographer can easily refine and use the suggestions as a starting point to craft his or her own cinematic compositions. Consequently, the expert is able to rapidly consider many more alternatives and the novice is guided towards options that conform to established cinema convention.

NOVELTY AND BENEFITS

This demonstration represents the very first coupling between motion-tracked camera devices -a fundamental technique in virtual cinematography -and automated viewpoint computation to support a filmmaker in his creative choices. The demonstration highlights both the creative potential the tool provides (movies can be made very rapidly) and the ease to play and explore the cinematic possibilities of a scenario. Figure 1: Our hand-held virtual camera device with custom-built dual handgrip rig and button controls, a 7-inch LCD touch-screen.

DEMONSTRATION

In this interactive demonstration of our Director's Lens system, a user operates a small hand-held touchscreen LCD screen equipped with motion sensors and custom-built button and joystick controls (see Figure 1) to record virtual camera movements (i.e., shots) to visualize a recreation of a scene from Michael Radford's film version of Orwell's 1984. The application runs on a notebook PC with a USB cable to communicate with the device's buttons, joysticks, and touchscreen, and an HDMI cable to mirror the PC's display on the handheld LCD. Three optical motion capture cameras mounted on tripods track the position and orientation of a rigid body marker cluster affixed to the device, which in turn map to the position and orientation of the virtual camera. We will also show a second version built from a Microsoft XBOX 360 gamepad and the same type of LCD touchscreen, but with a gyroscope sensor to drive camera orientation and the gamepad thumb sticks the camera's position.

A user can record a movie by iterating the following workflow: (i) identify the instant in the movie produced so far where a cut should be introduced (initially, at the beginning of the animation); (ii) ask the system to compute suggestion to start a new shot; (iii) browse the suggestions by cinematic properties (see Figure 2); (iv) choose the one that is closest to what the user likes; (v) possibly aim the virtual camera device to refine the composition, and start shooting, moving the the device like a real camera. An alternative, simpler workflow can very rapidly produce a sequence of static shots by simply exploring and selecting suggestions, without using the tracked device.

When browsing suggestions the user explore variations in shot distance, height, and angle in addition to whether or not suggestions conform to or differ from the previous shot in continuity, size, and angle. In this way the user can rapidly explore many different possible ways to film a given shot and assume manual control to improve upon the system's compositions and movements.

Figure 2 :

 2 Figure 2: Screenshot of the interface in Explore Suggestions mode. The Line of Interest visual filter is selected, and thus only suggestions respecting the line of interest with respect to the previous shot last frame (pictured in the bottom left) are visualized.


Christophe Lino
email: christophe.lino@inria.fr

Marc Christie
email: marc.christie@irisa.fr

Roberto Ranon
email: roberto.ranon@uniud.it

William Bares
email: bareswh@millsaps.edu

William Bares The

The Director's Lens: An Intelligent Assistant for Virtual Cinematography

Keywords: H.5.1 [Multimedia Information Systems]: Animations, Video Algorithms, Human Factors Virtual Cinematography, Motion-Tracked Virtual Cameras, Virtual Camera Planning

We present the Director's Lens, an intelligent interactive assistant for crafting virtual cinematography using a motiontracked hand-held device that can be aimed like a real camera. The system employs an intelligent cinematography engine that can compute, at the request of the filmmaker, a set of suitable camera placements for starting a shot. These suggestions represent semantically and cinematically distinct choices for visualizing the current narrative. In computing suggestions, the system considers established cinema conventions of continuity and composition along with the filmmaker's previous selected suggestions, and also his or her manually crafted camera compositions, by a machine learning component that adapts shot editing preferences from user-created camera edits. The result is a novel workflow based on interactive collaboration of human creativity with automated intelligence that enables efficient exploration of a wide range of cinematographic possibilities, and rapid production of computer-generated animated movies.

INTRODUCTION

Despite the numerous advances in the tools proposed to assist the creation of computer-generated animations, the task of crafting virtual camera work and edits for a sequence of 3D animation remains a time-consuming endeavor requiring skills in cinematography and 3D animation packages. Issues faced by animators encompass: (i) creative placement and movement of the virtual camera in terms of its position, orientation, and lens angle to fulfill desired communicative goals, (ii) compliance (when appropriate) with established conventions in screen composition and viewpoint selection and (iii) compliance with continuity editing rules which guide the way successive camera placements need to be arranged in time to effectively convey a sequence of events.

Motivated in part to reduce this human workload, research in automated virtual camera control has proposed increasingly sophisticated artificial intelligence algorithms (e.g. [START_REF] Drucker | Camdroid: a system for implementing intelligent camera control[END_REF][START_REF] Bares | Virtual 3D camera composition from frame constraints[END_REF][START_REF] Courty | A cinematography system for virtual storytelling[END_REF][START_REF] Jhala | Cinematic discourse generation[END_REF][START_REF] Amerson | Real-time cinematic camera control for interactive narratives[END_REF][START_REF] Lino | A real-time cinematography system for interactive 3D environments[END_REF]) that can in real-time generate virtual camera work that mimics common textbook-style cinematic sequences. However, this combination of increased automation and decreased human input too often produces cinematography of little creative appeal or utility since it minimizes the participation of filmmakers skilled in "taking ideas, words, actions, emotional subtext, tone and all other forms of non-verbal communication and rendering them in visual terms" [START_REF] Brown | Cinematography: Theory and Practice: Image Making for Cinematographers, Directors, and Videographers[END_REF]. Additionally, existing systems rely on precoded knowledge of cinematography and provide no facility to adapt machine-computed cinematography to examples of human-created cinematography.

This paper introduces the Director's Lens, whose novel workflow is the first to combine the creative intelligence and skill of filmmakers with the computational power of an automated cinematography engine.

Overview

Our Director's Lens system follows a recent trend in previsualization and computer-generated movies, by including a motion-tracked hand-held device equipped with a small LCD screen that can be aimed like a real camera (see Figure 4) to move a corresponding virtual camera and create shots depicting events in a virtual environment.

In the typical production workflow, the filmmaker would film the same action from different points of view, and then later select, trim and combine shots into sequences and ultimately create a finished movie. Our system instead proposes a workflow in which shooting and editing are combined into the same process. More specifically, after having filmed a shot with the motion-tracked device, the filmmaker decides where a cut should be introduced (i.e. trim the shot) and the system will compute a set of suitable camera placements for starting the subsequent shot. These suggestions represent semantically and cinematically distinct choices for visualizing the current narrative, and can keep into account consistency in cinematic continuity and style to prior shots. The filmmaker can visually browse the set of suggestions (using the interface shown in Figure 1), possibly filter them with respect to cinematographic conventions, and select the one he or she likes best. Once a suggestion is selected, it can be refined by manually moving the virtual camera into a better position, angle, or adjusting lens zoom, and shooting can start again. In addition, movies with shots composed of still cameras can be quickly generated with just keyboard and mouse.

The system exploits an annotated screenplay which provides the narrative context in the form of text descriptions of locations, subjects, and time-stamped actions, with links to the 3D models employed in the scene. The system uses the screenplay to provides on-screen information about timing of actions and dialog while shooting and provides our cinematography engine requisite knowledge about the 3D geometry and animation being shot. To generate the suggestions, the cinematography engine leverages both its knowledge of classical cinematography rules [START_REF] Arijon | Grammar of the Film Language[END_REF], and the knowledge it gets by analyzing the compositions created by the filmmaker.

Contributions and Outline

In the emergent Virtual Moviemaking approach [START_REF] Autodesk | The new art of virtual moviemaking[END_REF], realtime 3D graphics and motion-tracked virtual cameras are used in all production phases to provide creative team members with the ability of both reduce the time needed for previsualization, and to enable them to enjoy immediate and direct control of the process, from pre-production to production. For example, designed virtual sets can be interactively explored to accurately plan shots and refine creative ideas or virtual props before actual shooting takes place.

Our system aims at improving Virtual Moviemaking processes by introducing, for the first time, the combination of manual control of the virtual camera with an intelligent assistant. This provides a filmmaker with a way to interactively and visually explore, while shooting, a wide variety of possible solutions for transitioning from a shot to another, including some perhaps not considered otherwise, and instantly see how each alternate would look like without having to walk and turn around with the motion-tracked device (or move a virtual camera around with keyboard and mouse). In addition, in the innovative production workflow we propose, shooting and editing are combined in a seamless way, thus enabling very rapid production of animated storyboards or rough movies for previsualization purposes.

Furthermore, a novice filmmaker could use the system as a hands-on learning tool to quickly create camera sequences that conform to the textbook guidelines of composition and continuity in cutting from one shot to the next.

Finally, our work constitutes the first effort towards automatically learning cinematography idioms from live human camera work, and therefore building systems that are able to learn from examples of human experts, instead of trying to pre-encode a limited number of situations. This paper is structured as follows. In Section 2 we review related work. Section 3 describes how the system computes the suggestions, while Section 4 illustrates the Director's Lens interface layout and functionality. Section 5 discusses implementation details, limitations and results from preliminary users' feedback. Finally, Section 6 concludes the paper and outlines future work.

RELATED WORK

Cinematographers over time developed a rich canon of conventions for filming commonly recurring types of shots (a continuous take of camera recording) and sequences (an ordered series of shots). For example, cinematic convention suggests that in filming two characters facing one another in conversation, alternating shots of the two characters should depict one gazing left-to-right and the other right-to-left. In filming the first shot of such a sequence, the camera is placed on one side of an imaginary line-of-interest passing through the characters, and successively placing the camera on the same side of this line preserves continuity by repeating the established facing directions of the characters. [START_REF] Arijon | Grammar of the Film Language[END_REF].

In composing the visual properties of a shot, a cinematographer may vary the size of a subject in the frame or the relative angle or height between camera and subject. Shot sizes include extreme close-up, close-up, medium, long, and extreme long in which a subject's size in the frame appears progressively smaller or more distant. A filmmaker can also use editing decisions such as shot duration and the frequency of cuts to artful effect. [START_REF] Arijon | Grammar of the Film Language[END_REF].

Automated Virtual Camera Planning

The research field of automated camera planning, which combines expertise in Computer Graphics and Artificial Intelligence has sought to reduce the burden of manually placing and moving virtual cameras by bringing to bear increasingly sophisticated intelligence to emulate the composition and editing decisions found in traditional film.

Early efforts in automated camera control computed virtual camera locations from pre-programmed displacement vectors relative to the subject(s) being viewed, e.g. [START_REF] Feiner | Apex: An experiment in the automated creation of pictorial explanations[END_REF]. Attempts to model the editing transitions between shots have relied on idiom-based approaches which encode established conventions for filming common scenarios (e.g. groups of actors in conversation) using hierarchical state machines to model and transition between commonly used shot types [START_REF] He | The virtual cinematographer: a paradigm for automatic real-time camera control and directing[END_REF]. These approaches fall short when a user needs to film scenarios not anticipated by the pre-coded state machines.

Seeking to better handle unanticipated scenarios and arbitrary user-specified viewing goals, constrained-optimization camera planners compute virtual camera placements from user-specified declarative constraints on how subjects should appear by view angle, size and location in the frame, and avoidance of occlusion. Typically, heuristic search-based or optimization techniques repeatedly generate and evaluate the quality of candidate camera shots until a satisfactory camera placement is found [START_REF] Drucker | Camdroid: a system for implementing intelligent camera control[END_REF][START_REF] Bares | Virtual 3D camera composition from frame constraints[END_REF]. To reduce the computational complexity, the 3D scene space can be partitioned into regions that yield semantically distinct shots by distance, view angle, and relative position of subjects [START_REF] Christie | A semantic space partitioning approach to virtual camera control[END_REF]. Extensions to tackle camera path-planning problems have been proposed in offline [START_REF] Christie | Modeling camera control with constrained hypertubes[END_REF] or online contexts [START_REF] Halper | A camera engine for computer games: managing the trade-off between constraint satisfaction and frame coherence[END_REF]. The quality of the output often depends on carefully formulating the constraint parameters and importances making it difficult for users to obtain a specific desired shot.

Automatically producing virtual camera behavior coupled with narrative planning entails encoding and reasoning about coherent narrative discourse and cinematography to visualize a story. Along this line, a few systems have been proposed, e.g. CamBot [START_REF] Elson | A lightweight intelligent virtual cinematography system for machinima generation[END_REF] and Darshak [START_REF] Jhala | Cinematic discourse generation[END_REF] which can compute a full movie from a script while maintaining consistent rhetorical structure. These approaches however operate in offline contexts.

A recent proposal [START_REF] Lino | A real-time cinematography system for interactive 3D environments[END_REF] combines all these lines of research and is able to, starting from a script of the movie, compute camera motion and edits in real-time by partitioning the 3D scene space into Director Volumes that combine semantic and visibility information about subjects, and then searching optimal cameras (also enforcing composition rules) inside the best volume.

In summary, existing automated virtual camera planners can in realtime generate camera placements, movements, and edits to visualize sequences of live or pre-recorded events in virtual 3D worlds. The resulting computer-generated camera work is generally adequate for mechanically reproducing cinematic sequences that conform to anticipated textbook scenarios such as groups of virtual actors in conversation. However, crafting truly artful cinematography often requires human judgement of when and how to creatively depart from textbook rules (see [START_REF] Peterson | Learning to See Creatively[END_REF]). Unfortunately, existing automated virtual camera planners provide little or no facility for a human filmmaker to interject his or her creativity into the planner's operation.

Passos et. al. [START_REF] Passos | Neuronal editor agent for scene cutting in game cinematography[END_REF] also recognize the need to look beyond relying on programmers to encode cinematography knowledge in their system, which uses a neural network, to enable users to train an editing agent by selecting between a small set of virtual cameras each filming a moving car from different vantage points. Our system instead uses a much deeper model of cinematography accounting for continuity, cinematic style, and composition constraints and utilizes an intuitive motion-tracking and touch-screen interface that allows a user to craft his own compositions.

Computer-based Assistants for Movie Production

Commercial systems like FrameForge 3D [START_REF][END_REF] enable a user to create a virtual set and place cameras for producing storyboards and previsualization, but do include intelligent automated assistance to find suitable camera angles and framings or to plan camera paths.

Intelligent storyboarding research systems provide assistance in creating storyboards. For example, Longboard [START_REF] Jhala | Longboard: A sketch based intelligent storyboarding tool for creating machinima[END_REF] integrates a sketch-based tablet interface to a discourse and camera planner. The user defines a script and then sketches a storyboard, from which the system produces animatics and renders scenes, possibly adding shots and actions if the user or the script did not specify them. In a form of interplay similar to that of our system, the user has the possibility of either accepting or rejecting the suggested shots by specifically adding constraints on certain frames or by adding new frames to the storyboard. However, Longboard is meant to be used as an offline generator, not as a shooting assistant.

Adams and Venkatesh [START_REF] Adams | Director in your pocket: holistic help for the hapless home videographer[END_REF] have proposed a mobile assistant for amateur movie makers where the user selects a narrative template and a style, and the system displays shot directives (i.e. how to film a specific part of the event) by generating 3D simplified first-person renderings that illustrate what the camera should frame and how. The renderings are meant to assist the user while shooting in the field.

Motion-tracked Cameras for Movies

Early virtual reality researchers studied different user interaction metaphors for users to control the position and orientation of a virtual camera by moving a six-degree of freedom motion sensor [START_REF] Ware | Exploration and virtual camera control in virtual three dimensional environments[END_REF]. This technique of animating a virtual camera using a hand-held motion sensor has found high-profile application in the previsualization (planning) and filming of feature films including Polar Express (2004), Beowulf (2007), and Avatar (2009). Computer game productions such as Command and Conquer: Red Alert 3, and Resident Evil 5 have also used these devices to create ingame cinematics. Commercially-available systems (e.g., Intersense VCAM, NaturalPoint Insight VCS) couple cameralike bodies or camera mounts with 3DOF (orientation) or 6DOF (orientation and position) sensors, whose readings are mapped onto the virtual camera parameters (position, orientation) and provide buttons or levers to adjust lens zoom angle. These devices have replaced typical mouse, keyboard, and joystick camera controls with intuitive motion-sensing control, but they operate with the same complex software interfaces of 3D modeling tools, which are not designed around cinematic organizational concepts of scene, sequence, and shot. Nor can they easily manage and browse a variety of alternate cinematic visualizations side-by-side.

COMPUTING SUGGESTIONS

The core of our system relies on the automated generation of a large range of suggested cameras and on the ranking of these suggestions according to the last frame of the current shot.

In order to generate appropriate shots with relation to the story, our system requires the provision of an annotated screenplay. This screenplay specifies a set of actions (possibly overlapping in time) as they occur in a sequence of scenes by specifying, for each one, the starting and ending times, the involved subjects/objects (if any), a relevance value, and a textual description of the action. Actions may be attached to a character or an object (e.g. "Parsons walks to the table"), or describe any general event (e.g. "Characters are entering the canteen"). In addition, the screenplay includes the names of particular 3D model parts for the subjects, which are required to perform appropriate screen composition in computing suggestions (e.g. for a character, body part, head part and eyes parts). An excerpt of the annotated screenplay for a scene from Michael Radford's 1984 is provided below:

Screenplay "1984"
Scene "Canteen" Location "Canteen" Actor Smith body "SmithBody" head "SmithHead" leftEye "SmithLeftEye" rightEye "SmithRightEye" Actor Syme ... Action "A pours gin" Relevance 5 begin 0 end 4

Character "Smith" Action "A drinks gin" Relevance 5 begin 4 end 12 Character "Smith" Action "A turns" Relevance 3 begin 10 end 18 Character "Smith" Action "A speaks to B" Relevance 9 begin 18 end 21 Character "Smith" Character "Syme" ... end screenplay

As the user requests a list of suggestions (at time in the movie we denote ts) our system performs a three-step computation:

• from the screenplay the system selects the list of all actions overlapping time ts or occurring within a second after time ts (this enables to suggest a shot which anticipates an action);

• for each selected action, the set of key subjects (characters, objects, buildings) is extracted and a dynamic spatial partitioning process generates a wide collection of viewpoints ensuring both a complete coverage of the key subjects and actions as well as significant enough difference between viewpoints (see detailed description in next Section). Each viewpoint represents a suggested starting point for a shot;

• each suggestion is then ranked by considering the enforcement of cinematic continuity rules between the current viewpoint and the suggested viewpoint, the quality of the composition in the shot (how elements are spatially organized on the screen), the relevance of the suggestion with relation to the action and the quality of the transition between the current shot and the suggestion.

Dynamic Spatial Partitions

We employ Director Volumes, a technique proposed by [START_REF] Lino | A real-time cinematography system for interactive 3D environments[END_REF] to compute dynamic spatial partitions in the space of viewpoints around key subjects (a key subject may be a character or any object of the environment). As displayed in Figure 3, the area around some subjects configurations (a typical two-character configuration in the Figure, but one, three or more character configurations are also considered) is partitioned with relation to shot distance (Close-Up, Medium Shot, Long shot, Extreme Long Shot) and with relation to relative angle of the camera against the key subjects (Internal, External, Apex, Parallel and Subjective see [START_REF] Arijon | Grammar of the Film Language[END_REF]). For a one-subject shot this would be Front, Left, Right, Profile, 3/4 Left, 3/4 Right. These dynamic spatial partitions are based on Binary Space Partitions (BSPs) which are recomputed every time a change occurs in the 3D environment (due to character or object motion). Each partition is qualified with a semantic tag representing its shot distance and relative angle to subjects.

In a parallel step, we compute a second level of dynamic spatial partitions to identify visibility of key-subjects. We analyze the 3D environment to build a visibility graph [START_REF] Teller | Visibility preprocessing for interactive walkthroughs[END_REF] (a graph which connects convex cells extracted from the environment which share a common portal, the portal representing a potential occluder). We use the graph to propagate full visibiltiy, partial visibility and no visibility for each key-subject and tag spatial partitions accordingly.

Finally, we rely on BSP-tree merging techniques to compose the information from the Director Volumes and the visibility graph into a single representation. Using this technique, all regions generated by the partitions represent viewpoints with different tags, meaning that whatever viewpoint is selected in a region, it will yield a similar result in terms of shot distance, relative angle to framed subjects and visibility.

For each region, our process generates three suggestions: a high-angle shot, a low-angle shot, and a medium angle shot, and for each of these suggestions, a default screen composition is computed by enforcing the rule of the thirds (keysubjects are spatially arranged on the screen to appear at the intersection of the line of the thirds [START_REF] Arijon | Grammar of the Film Language[END_REF]).

The overall process is described in Figure 2.

Ranking Suggestions

Once a set of suggestions is computed (for a two-subject configuration, over 240 shots are generated and for a onesubject configuration, 120 shots are generated), our system performs a quality ranking process, whose result is used when displaying the suggestions to the user (see Section 4).

The quality qs > 0 of a suggestion s is defined as the product of qualities assessing specific features of s:

qs = Qcont(s) • Qcomp(s) • Qr(s) • Qt(s) with Qcont(s) = Q loi (s) • Q change (s)
where Qcont measures the enforcement of continuity rules, Q loi measures compliance with line-of-interest rule and last, Q change measures compliance with the change-in-angle-orsize rule. Qcomp represents the satisfaction of composition rules, Qr represents the relevance of the suggestion with relation to the current action's relevance, and Qt represents the quality of the transition between the current shot and the suggestion. All the Qi(s) functions return positive real values.

In the following subsection, we detail how Qi(s) functions are computed.

Respecting Continuity in the Cut

Cinematographic conventions related to continuity in cuts are well established. Such conventions typically maintain the spatial coherency in cuts (do not invert key subjects on the screen), the motion coherency (key subjects moving in the same direction on successive shots) and the composition continuity (successive shots of the same subjects will maintain similar composition). We rely on the following continuity rules to establish the ranking Qcont(s):

• Line-of-interest continuity: in actions which involve two or more key subjects, once the camera is located on one side of the line-of-interest (imaginary line linking two key subjects), the camera should not cross this line in successive shots, unless using an extreme long shot (that re-establishes the key subjects in relation to the environment). The system ranks all suggestions on the opposite side of the Line-of-interest with a low value.

• Change in angle or size: When considering two shots portraying the same subject, there should be at Director Volumes (see [START_REF] Lino | A real-time cinematography system for interactive 3D environments[END_REF]).

least a thirty-degree difference in orientation with relation to the key subject, or a notable difference in the size of the subject in the shot. For this purpose we compute the difference in angle and size between the current shot and the suggested shot. Only suggestions with noticeable difference in size are ranked positively (here we consider a change of at least two units in size, a unit being a step between two shots in the range of Extreme Close Shot, Close Shot, Medium Close Shot, Long Shot and Extreme Long Shot). Suggestions that subtend an angle lower than 30 degrees to the subject are ranked with a low value.

Respecting Classical Composition Rules

Suggestions computed by the system try to enforce the classical rule of the thirds. When considering characters, the composition is set so that their eyes (an element to which spectators look at in priority when gathering elements in a picture) are located at the intersection of two equally spaced horizontal lines and two equally spaced vertical lines on the screen. We thus measure as an Euclidean distance the difference between the ideal composition and the composition computed by the system to asses the quality of a viewpoint. Bad compositions are ranked with low values.

Relevance of the Shot w.r.t. Current Action

Relevance is measured by exploring the capacity of the shot to enhance a viewer's comprehension of the action. Each action has a relevance value that encodes its importance for the story (e.g. representing whether the action is a foreground action, an establishing action, or a background action). Shots that depict more relevant actions, from relevant viewpoint enforce the comprehension of the story and will have a higher quality.

Quality in Transitions Between Shots

Quality in transitions (a transition is a cut between shots) is measured by using transition matrices. A transition matrix is a stochastic matrix used to describe the transitions of a Markov chain. We encode our transitions with a right stochastic matrix, i.e a square matrix where each row consists of nonnegative real numbers summing to 1. Each value tij of the matrix T (i being the row index, and j the column index) corresponds to the probability of performing a cut from Director Volume i to Director volume j. We use three different matrices depending on whether the transition is performed inside the same action, between related actions, or between unrelated actions. The quality of the transition is given by an affine function y = ax + b, where a > 0, b > 0 and x is equal to the value t k ij related to the transition in the corresponding matrix T k . The values in the matrices therefore represent user preferences in performing cuts, and in our approach, the values are updated by a learning process described in Section 3.3.

Learning from the User Inputs

We rely on a simple reinforcement learning technique to update the probabilities in the transition matrices, using the cuts already performed by the user. Three distinct transition matrices are encoded depending on whether the transition is performed:

1. during the same action (matrix TA): the two consecutive shots are conveying the same action;

2. between related actions (matrix TR): the two consecutive shots are conveying two different actions, but the actions have a causal link (e.g. in case of dialog, the first action being "Syme speaks Smith" and the second one "Smith answers to Syme" for instance). A causal link is established when the two actions share the same key subjects;

3. between unrelated actions (matrix TU ): the two consecutive shots are conveying two different actions, and there is no causal link between them;

These transition matrices actually define preferences in using some transitions between shots over others. A shot is identified by its type (orientation to subject) and its size (extreme long to extreme close-up). Our system learns the transition matrices from the user inputs, by analyzing the successive choices in shot types performed by the user. The learning process operates as follows. Each time the user selects a suggestion as the new shot, we first determine the transition matrix T k to consider by analysing whether (1) the successive conveyed actions are the same, (2) the actions are different but are causally linked, or (3) the actions are different and they have no causal link. Then all the values t k ij of the row i of the corresponding matrix T k (where i is the shot type of the current shot), are updated in the following way: let the newly selected shot be of type n, the value t k in will be increased, and the values t k ij , j = n of row i will be accordingly updated such that i tij = 1.

The probabilities in the matrices influence the quality of a shot by ranking preferred cuts higher (the quality of transition Qt(s) is expressed as a function of t k ij ).

THE DIRECTOR'S LENS SYSTEM

In this Section, we describe the interface and user interactions with the Director's Lens system. To demonstrate the system, we will use as example a reconstruction from a sequence of Michael Radford's 1984 movie, together with a set of 70 actions which describe in details the events occurring over the scene. The scene is composed of 5 key subjects (Syme, Parsons, Julia, Smith and an anonymous member of the party).

User Input Devices

The Director's Lens system features a 7-inch HD LCD touch-screen mounted to a custom-built dual handgrip rig (see Figure 4) that can be paired with either a 3DOF or 6DOF motion sensor. When used with a 3DOF sensor (rotation controls camera aim direction), the two thumb sticks control camera position, and buttons adjust lens zoom, movement/zoom speed, and record/playback functions. When paired with an optical 6DOF tracking system, a rigid cluster of reflective markers is fixed to the device and one of the thumb sticks is configured to increase or decrease lens zoom angle. The spatial configuration (position/orientation) read by the tracking sensor is synchronized with the spatial configuration of the virtual camera in the system, so that (besides a distance scaling factor that can be adjusted) movements of the motion-tracked device will correspond to analogous movements of the virtual camera in the 3D scene.

The system can also be used with just a desktop or notebook computer and a mouse. In this mode, the preferred workflow is primarily one of clicking to select a suggested camera placement for each shot to very rapidly compose a virtual 3d movie made with shots featuring static cameras.

User Interface and Interaction

The user's interaction with Director's Lens is divided into two interface modes: (i) explore suggestions (Figure 1) and (ii) camera control/movie playing (Figure 5).

Explore Suggestions Interface

The explore suggestions interface (Figure 1) displays the suggestions for beginning a new shot from any instant in the recorded movie. The suggestions are presented as small movie frames, arranged in a grid whose rows and columns correspond to visual composition properties of the suggested cameras. More specifically, the horizontal axis from left-toright varies by decreasing shot length (or distance) in order of extreme long, long, medium, close-up, and extreme close-up. The vertical axis from top-to-bottom presents suggestions from a variety of camera heights in order of high, medium, and low. For example, Figure 1 shows the suggestions that are proposed to transition from a shot depicting the actions "Syme eats" to a new shot where two parallel actions occur: "Syme eats" (which continues from the previous shot) and "Smith speaks to Syme" (the last frame of the previous shot is shown in the reel at the bottom left). Notice, for example, that all suggestions in the top row are viewed by cameras positioned above the virtual actors.

When more than one suggestion is generated for each shot length and camera angle, the system displays a stack of frames in that grid position, where the top one is the most highly ranked (of all the suggestions in the stack). If the user wishes to explore a stack (s)he can expand the actually displayed suggestions for a grid column, row, or cell, by clicking on the corresponding column/row heading. For example, Figure 5 shows the suggestions grid expanded to display all suggestions for medium length / medium angle shots.

When the suggestions do not refer to the first instant in the movie (i.e., there are previous shots), the system allows the user to visually filter the presented suggestions on the basis of respect of cinematography rules, namely the line of interest, and minimum change in angle or size with respect to the previous shot's last frame. For example, in Figure 1 we have selected to display only suggestions that respect the line of interest rule (i.e., the camera is on the same side of the line of interest as in the previous shot last frame), while Figure 5 shows just suggestions where the camera is at least 30 • difference in orientation with relation to the key subject (with respect to the previous shot of the last frame).

The user selects a suggested shot by touching its icon in the grid. The larger image framed in the reel at the bottom left represents the previous shot to assist the user in choosing or modifying a suggestion to best follow its predecessor, and shows the currently selected suggestion to its right. The user finally confirms his or her choice and goes to the camera control/movie playing interface.

Camera Control / Movie Playing Interface

The camera control/movie playing screen (see Figure 6) allows the filmmaker to view the recorded movie or manually take control of the camera to record a shot. The interface features a single large viewport to display the 3D scene as viewed from a virtual camera corresponding to the filmmaker's choice for the current instant in the movie or corresponding to the position/orientation of the motion-tracked device (when the tracking of the device is enabled).

When camera tracking is not enabled, the Play button allows one to play-pause the animation, and visualize it from the currently recorded shots, while Previous Shot and Next Shot buttons enables to move in the recorded movie by shot. With these functionalities, the user can review the recorded movie, and decide where to introduce a cut -this is implicitly introduced when one asks the system to explore suggestions.

When camera tracking is enabled, the virtual camera is driven by the motion tracking and lens zoom controls of the hand-held device. The tracking starts from the currently used camera, so that, if the user is coming from the explore suggestions interface after having selected a suggestion, tracking starts from the virtual camera in the configuration associated with that suggestion. By using the Turn on Recording button, the user starts/Stops recording of the stream of virtual camera position, orientation, and lens angle input data. Starting recording also starts playback of the pre-produced animated character action and digitized audio dialog.

A graphic overlay can appear over the camera image to display an animated timeline of the unfolding character actions and dialog. Horizontal bars along each row represent one character's actions or dialog. The length of each bar represents the duration of that event. Bars scroll by as the animation plays to indicate the passage of time. This allows the filmmaker to move the camera at the precise time in anticipation of an upcoming screenplay action or spoken dialog event. The overlay also displays the framing properties (e.g. medium, low, etc.) of the current camera view. Figure 7 demonstrates an example in which the system suggests shots which match the composition of the user's previous shot. In this scene, Smith pours a bottle while seated facing Syme. The user has composed a shot (shown in the right image in the Figure ) in which Smith fills the rightmost third of the frame and gazes to the left and the camera is to his lefthand side. Consequently, when we click to enable the line of interest filter, the system generates suggestions in which no viewpoints violate the line of interest by placing the camera on Smith's righthand side. Furthermore, all shots display Smith on the rightmost third of the frame. Also note suggested compositions leave more room ahead of Smith's face, as did the user's composition.

RESULTS

Our system is coded in C++ and uses the OGRE real-time rendering engine, and a custom-written abstraction layer to interface to a variety of button and joystick input devices and motion trackers. In our tests we used 6DOF rigid body reflective markers with an A.R.T. optical tracker with 16 cameras covering a workspace of 4 × 8 meters. The application runs on a computer whose video output is routed over an HDMI cable to the small LCD touch screen. The largest computational cost of the cinematography engine is in finding visibility and director's volumes, which depend on the geometric complexity of the scene and the variations in position of the key subjects. In the pictured example, the computation of suggestions takes around a second on a Intel Core i7 2.13 GHz notebook, which is acceptable since this computation is not required to happen in real-time.

Applicability to Other Scenarios

The examples shown in the paper features mostly dialog actions involving two or three characters, and also generic actions (e.g. "Parsons walks to the table") for which proper suggestions are computed. In general, the system can model any event where one character or object, or group of objects (e.g., cars driving, architectural elements) is involved, and propose suggestions to properly frame it using different angles and shot lengths. Note that for many situations (e.g. shooting of architecture, or crowds) there are not many cinematographic conventions other than using establishing shots first, and then closer shots. However, in general, the cinematography knowledge the system uses can be expanded by designing additional Director Volumes for specific cases or using the automatically learned tables of transitions. For situations that involve, in the same instant, more than three characters, the system could be extended by employing the method of hierarchical lines of action [START_REF] Kardan | Virtual cinematography of group scenes using hierarchical lines of actions[END_REF].

Scenes involving very fast action can be a bit problematic as the system might generate suggestions that are good for the considered instant, and decrease in quality after a short delay, for example because the framed character moves aways or is covered by some moving objects. This kind of situation would require the system either to consider animations occurring in an interval of time, instead of an instant, or to suggest camera movements, instead of just starting frames. However, this would be of much greater computational cost than deriving suggestions for single instants. In these cases, however, the filmmaker can at worst ignore the suggestions and deal with the situation by taking manual control.

Finally, the system computes all suggestions using a single fixed lens field of view. However, the user can quickly adjust the field of view by manual control. The system's search algorithm can be extended by taking into account variations on lens angle. In practice, the set of lens angles to consider would be limited to model the cinematography practice of using a small number of user-selected "prime" or standard lenses.

User Feedback

While we do not currently have results from formal and extensive user evaluations, a few videographers have tried the system, reporting great satisfaction in using it.

In general, users found the system workflow refreshing compared to mouse-based solutions, were very willing to try it, and could rapidly use it to produce results. In our tests, after a very brief introduction to the system, users familiar with camerawork could shoot a 3 minutes video of the 1984 scene in around 10-15 minutes, including taking decisions on camera angles and cuts. For comparison, producing a video for same animation sequence took an expert user a few hours of work using 3DS Max. The reason for the huge difference in time comes from the fact that with typical animation software tools one is forced to a workflow where cameras have to be manually positioned and animated, and then the shot can be watched, and often one has to go back and forth between cameras modifications and testing the result. Furthermore, there's the complexity of manually keeping track of timings and motion curves, making sure that edits occur in the correct place and time.

While the use of a motion-tracked virtual camera is surely pivotal in reducing the amount of time needed, we can hypothesize that suggestions also played a role, as in general users needed to make very small movements to refine the suggestions and find their ideal starting camera positions. Moreover, from our feedback with professionals in the development of motion-tracked virtual cameras, we know that having to walk around in the tracked space to explore angles and distances is perceived as a real issue. Finally, users more experienced in real cameras work appreciated on-screen information overlays of character actions and their timing while shooting.

The interface for browsing suggestions by shot distance and height was considered easy to learn and effective for a videographer, and the possibility of quickly visualizing many alternatives was very appreciated, though not all users agreed with each suggestion. This is expected since the perceived quality of a suggestion is a subjective factor, which changes from one videographer to another. However, users' attitude towards the cinematography engine work was positive, mainly because the the system does not force one to any shooting or editing style, and suggestions can be ignored: however, many times they caused the videographer to consider solutions he had not thought about, thus enhancing creative thinking and exploration.

CLOSING REMARKS

While a few experiments have been done in combining human expertise with automatic camera planners, we believe that this work is the first attempt at innovating the shooting process of CG animations by providing intelligent and adaptive automatic support in creating shots. In the shooting of CG movies, videogame cinematic scenes and machinima, the system has the potential of making the process much easier and quicker than current methods. From our early tests, unlike existing automated systems which rely on pre-coded cinematic knowledge to cover all anticipated scenarios, our interactive approach proves effective even if no suggested viewpoint is "perfect" in the user's creative judgement.

Future work includes conducting extensive user evaluations to precisely assess the user satisfaction of the various system features, and measure task completion time with and without the automated assistance capability.

We plan also to focus on methods to improve the recorded camera tracks. For example, one could think of a "steadycam" filter to avoid using a tripod for non-handheld camera style, or apply post-processing algorithms to recorded video to improve apparent camera movement as proposed by Gleicher and Liu [START_REF] Gleicher | Re-cinematography: improving the camera dynamics of casual video[END_REF]. Motion-sensing virtual cameras offer an opportunity to easily capture shots in the context of screenplay actions providing a rich corpus for machine learning. Further work in this novel direction could eliminate the re-programming needed to encode knowledge for new numbers and arrangements of actors, shots, and transitions, and also provide an effective way to incorporate more sophisticated stylistic capabilities into automatic camera planners.

Figure 1 :

 1 Figure 1: Screenshot of Director's Lens user interface in Explore Suggestions mode.

Figure 2 :

 2 Figure 2: The automated computation of suggestions. Each selected action in the screenplay leads to the computation of a set of spatial partitions (each partitionned area represents a typical shot of the action). Suggestions are computed and ranked for each area.

Figure 3 :

 3 Figure 3: Spatial partitions around two subjects define areas of characteristic viewpoints referred to as Director Volumes (see[START_REF] Lino | A real-time cinematography system for interactive 3D environments[END_REF]).

Figure 4 :

 4 Figure 4: Our hand-held virtual camera device with custom-built dual handgrip rig and button controls, a 7-inch LCD touch-screen.

Figure 5 :

 5 Figure 5: Screenshot of the interface in Explore Suggestions mode with expansion of medium shots and medium camera angles that were visualized in Figure 1, with additional enabling of the Change in Angle visual filter. Compare the resulting suggestions with the last frame of the previous shot that is shown in the bottom left part of Figure 1.

Figure 6 :

 6 Figure 6: Screenshot of the interface in Camera Control / Movie Playing mode. The overlay horizontal bars show an animated timeline of screenplay events and their duration, together with an indication of the camera angle and framing that is currently being used in the movie.

Figure 7 :

 7 Figure 7: Given user's composition for the current shot (shown in the left image), the system suggests shots (right image) which satisfy continuity rules of editing.

6.1 Acknowledgements Thanks to Dean Wormell of InterSense for discussions on the use of motion-sensing virtual cameras in movie productions. Thanks to Nick Buckner, Tyler Smith, Alex Olinger, and Lihuang Zhu for constructing our virtual camera device. William Bares acknowledges support of a Millsaps College sabbatical award. Roberto Ranon acknowledges the financial support of the PRIN project Descriptive Geometry and Digital Representation: intelligent user interfaces to support modeling and navigation in 3D graphics application for architecture and design. This work has been funded in part by the European Commission under grant agreement IRIS (FP7-ICT-231824).