A Martínez-González

C F Méndez-Barrios

S I Niculescu
email: silviu.niculescu@lss.supelec.fr

J Chen
email: jichen@cityu.edu.hk

Some Remarks on the Asymptotic Behavior for Quasipolynomials with Two Delays

Keywords: Quasi-polynomial, Retarded systems, Newton Diagram, Weierstrass Polynomial

This paper proposes an analytical method to characterize the behavior of critical multiple roots for quasi-polynomials with two delays. The proposed approach is based on the Weierstrass polynomial, that is employed as a tool to analyze the stability behavior of such characteristic roots with respect to small variations on the delay parameters. The proposed results are illustrated by considering a numerical example.

INTRODUCTION

The stability analysis of linear time-invariant (LTI) systems with time-delay have been studied for a long time, and there exists an abundant literature covering this subject, see, for example, [START_REF] Gu | Stability of time-delay systems[END_REF], [START_REF] Michiels | Stability, Control, and Computation for Time-Delay Systems. An Eigenvalue-Based Approach[END_REF] and the references therein. Even though delays have been associated with "undesired" behaviors (as, for examples, oscillations, bandwidth sensitivity), recently has been shown that in some situations the presence of delays may induce stability, where the classical example was presented in [START_REF] Abdallah | Delayed positive feedback can stabilize oscillatory systems[END_REF], where a simple oscillator is controlled by one delay "block" (gain, delay), with positive gains and extremely small delay values. As discussed in [START_REF] Michiels | Stability and Stabilization of Time-Delay Systems[END_REF], such a property opens an interesting perspective in using delays as control parameters in some situations, as, for example in, [START_REF] Niculescu | Stabilizing a chain of integrators using multiple delays[END_REF] (stabilizing chains of integrators by using delays), [START_REF] Kharitonov | Static output feedback stabilization: Necessary conditions for multiple delay controllers[END_REF] (multiple delay blocks), and [START_REF] Mazenc | Global asymptotic stabilization for chains of integrators with a delay in the input[END_REF] (bounded input, single delay). Nonetheless, the approach appears conservative in other cases; see, for instance, [START_REF] Michiels | Stability and Stabilization of Time-Delay Systems[END_REF]; [START_REF] Sipahi | Stability and stabilization of systems with time delay[END_REF].

In the works of [START_REF] Chen | An eigenvalue perturbation approach to stability analysis, part II: when will zeros of time-delay systems cross imaginary axis[END_REF], the above observations have been explored in detail for a general retarded LTI delay system with multiple commensurate delays. Specifically, they have first, fully characterized the stability properties of such systems by proposing conditions to find the set of critical delay values, at which the system's characteristic quasi-polynomial has critical zeros on the imaginary axis. Secondly, considering the delay as a variable parameter and by adopting an operator basedapproach (see, for instance, Chen et al. (2010a)) they have expanded the solutions of the quasi-polynomial in terms of a Taylor (or Puiseux) series, allowing them to analyze the behavior of the solutions as the delay varies around a critical delay value.

It is well recognized [START_REF] Chen | An eigenvalue perturbation approach to stability analysis, part II: when will zeros of time-delay systems cross imaginary axis[END_REF]) that even in the case of a fixed delay, the testing of stability for a time-delay system is not a simple task. Furthermore, it is well known that delay systems (and in consequence, quasi-polynomials) have always infinitely many solutions (see, for further details, [START_REF] Gu | Stability of time-delay systems[END_REF] and the references therein), however in general, we will only be interested in analyzing the behavior of a critical zero of finite multiplicity.

Multiple delays can also be presented in a more general form, as non-commensurate delays, that is, all delays are assuming to be independent of each other. In this case, the stability of the related quasi-polynomial becomes more complex and is less studied. For the case of solutions of multiplicity two, in [START_REF] Irofti | Some insights into the migration of double imaginary roots under small deviation of two parameters[END_REF] the authors have proposed two sectors to study the behavior of these roots when delays are subject to small deviations and restricted to such sectors. In this vein, it is worth to mention that unlike the case of a single parameter, in the multiparameter case there exist some singular and unexpected behaviors (see, the motivating examples section) which have to be taken into account (see, for instance [START_REF] Monforte | Formal laurent series in several variables[END_REF]), in order that the problem is well-posed. In other words, the Puiseux type arguments cannot be extended straightforwardly from one parameter to multiparameter case.

Based on the above arguments, the main goal of this paper is two-fold. First, give conditions that guarantee the existence of a convergent Puiseux (or Taylor) series solution around roots of multiplicity m > 1. Second, extend the use of the well known Newton diagram to the case of two parameters.

The remaining part of the paper is organized as follows: Section II introduces some preliminary results, motivating examples and the problem formulation. Section III is devoted to the main results; specifically we present a method to compute the Weierstrass Polynomial, and an algorithm to find Newton polygon. Furthermore, necessary conditions to obtain Generalized Puiseux series are presented. Finally, section IV a numerical example illustrates the proposed results. The contribution ends with some concluding remarks.

Notations: In the sequel, the following notations will be adopted: C is the set of complex numbers, i := √ -1. Next, R + denotes the set of positive real values. The order of a power series f (x, y) = a i,j x i y j will be denoted by ord (f ) and defined as the smallest number n = i + j such that a i,j = 0. The ring of complex formal power series is denote by C[[x]], with subring C{x} of convergent power series. Finally, given two polynomials f (z) = n j=0 a n-j z j and g(z) = m j=0 b m-j z j , the resultant of f , g is defined as the determinant of Sylvester matrix as follows

R (f, g) := det              a 0 a 1 a 2 • • • a n a 0 a 1 • • • • • • a n . . . . . . . . . . . . a 0 a 1 • • • • • • a n b 0 b 1 b 2 • • • b m b 0 b 1 • • • • • • b m . . . . . . . . . . . . b 0 b 1 • • • • • • b m             
, with n rows of a i and m rows of b i .

PRELIMINARIES

Retarded Linear Time-Invariant Systems

Consider a retarded LTI system with h a -delays τ k , as

ẋ (t) = A 0 x (t) + ha k=1 A k x (t -τ k ) , τ k ≥ 0, (1)
with characteristic function given by the quasi-polynomial:

f (s, τ ) = ha k=0 p k (s)e -τ k s , τ k ≥ 0, (2)
where the polynomials p k are given by

p 0 (s) = s n + n-1 =0 a 0 s , p k (s) = n-1 =0 a k s , k = 1, . . . , h a .
In order to perform an asymptotic behavior analysis of multiple imaginary roots, we will make use of the following results and definitions.

Local Representation of Analytic Functions

It it possible to reduce the analytic properties of f (x, y) to algebraic ones. To this purpose, let us consider the following result (for further details see [START_REF] Mailybaev | On the Weierstrass Preparation Theorem[END_REF]). Theorem 1. (Weierstrass Preparation Theorem). Let f(z, x) be an analytic function vanishing at the singular point z 0 ∈ C, x 0 ∈ C n , where z = z 0 is an m-multiple root of the equation f (z, x) = 0, i.e.,

f (z 0 , x 0 ) = ∂f ∂z = • • • = ∂ m-1 f ∂z m-1 = 0, ∂ m f ∂z m = 0.
where derivatives are evaluated at (z 0 , x 0 ). Then, there exist a neighborhood U 0 ⊂ C n+1 of the point (z 0 , x 0 ) ∈ C n+1 in which the function f (z, x) can be expressed as

f (z, x) = W (z, x) b (z, x) , (3) where W (z, x) is given by (z -z 0 ) m + w m-1 (x) (z -z 0 ) m-1 + • • • + w 0 (x) ,
and w 0 (x),. . . ,w m-1 (x), b (z, x) are analytic functions uniquely defined by the function f (z, x), and

w i (x 0 ) = 0, b (z 0 , x 0 ) = 0. Remark 2. The holomorphic function W (z, x) = z m + w m-1 (x) z m-1 + • • • + w 0 (x) , (4
) is known as the Weierstrass polynomial (for further details on Weierstrass polynomials, see, for instance, [START_REF] Wall | Singular points of plane curves[END_REF]). Remark 3. It can be seen from Theorem 1, that since b (z, x) is an holomorphic non vanishing function at (z 0 , x 0 ), then, there must exist some neighborhood U ⊂ C n at which b(z, x) preserves the same property. Hence, based on this observation we can ensure that the roots behavior of a given quasi-polynomial f in the neighborhood U will be completely described by the roots behavior of W (z, x).

Newton Diagram Method

It is well known that solutions of the equation f (x, y) = 0 with x, y ∈ C can be computed term by term by means of the Newton Diagram Method. Thus, in order to use such a procedure, let us introduce the following notation (for more details, see, for instance, [START_REF] Vainberg | Theory of branching of solutions of non-linear equations[END_REF]). Let f (x, y) be a pseudo-polynomial in y, i.e.,

f (x, y) = n k=0 a k (x)y k , (5)
where the corresponding coefficients are given by,

a k (x) = x ρ k ∞ r=0 a rk x r/q , (6)
a rk ∈ C, x and y are complex variables, ρ k are nonnegative rational numbers, q is an arbitrary natural number, a n (x) ≡ 0, and a 0 (x) ≡ 0.

Since by simple translation, any point on a curve can be moved to the origin, we will consider expansions of the solution of (5) f (x, y) = 0 around the origin, in the following form

y(x) = y 1 x 1 + y 2 x 2 + y 3 x 3 + • • • , (7) where 1 < 2 < 3 < • • • and y 1 = 0.
To determine the possible values of 1 , y 1 , 2 , y 2 , . . ., it is necessary to consider the Newton's diagram. Definition 4. (Newton's Diagram and Polygon). Given a pseudo-polynomial of the form (5) with coefficients given by ( 6), plot k versus ρ k for k = 0, 1, . . . , n (if a k (•) ≡ 0, the corresponding point is disregarded). Denote each of these points by π k = (k, ρ k ) and let Π = {π k : a k (•) = 0} , be the set of all plotted points. Then, the set Π will be called the Newton diagram, and the Newton polygon associated with f (x, y) will be given by the lower boundary of the convex hull of the set Π.

For a given f (x, y), Fig. 1 simply illustrates Definition 4. Thus, the leading term of the expansion (7) of the solutions have exponents given by = γ where γ is the slope between two points of the Newton polygon. The coefficients are given by the non-zero solutions of the polynomial equation

P(y ) := i a 0,i y i = 0, (8)
where the sum runs over the terms satisfying ρ k + γk = ν with constant ν ∈ Q. For equations f (x, y) = 0, the Newton Diagram Method can be formalized by the following theorem ( see [START_REF] Wall | Singular points of plane curves[END_REF]). Theorem 5. (Puiseux Theorem). The equation f (x, y) = 0, with f given in formal power series such that f (0, 0) = 0, posses at least one solution in power series of the form:

x = t q , y = ∞ i=1 c i t i , q ∈ N.
The procedure described above can be generalized to more than one parameter, to this end, we consider the following definitions.

Generalized Puiseux Series and Cones

When we deal with singularities of greater dimension, we must use a ring of multi-variable fractional power series.

In [START_REF] Mcdonald | Fiber polytopes and fractional power series[END_REF] the author defines fractional power series ring that contains the solutions of algebraic hypersurfaces. This is done through formal power series defined in a geometric way, by taking infinite power series

∞ i=1 c a i x ai/d , where x a = x a1 1 • • • x an n ,
where the exponents a are taken from a fixed convex cone with a structure related to its Newton polytopes, Ziegler (2012). We will use fractional iterated power series of several variables as Generalized Puiseux Power Series (see [START_REF] Soto | The newton procedure for several variables[END_REF][START_REF] Neumann | On Ordered Division Rings[END_REF]), denoted by K x,d . This series can be constructed by induction, taking as a bases the univariate case K x1,d and then, proceed with the field of power series in x 1/d 1 with power series coefficients in

x 1/d 2 • • • x 1/d n such that K x,d = C x 1/d 1 • • • x 1/d n .

Motivating Examples

Even though we can reduce the analysis of a given entire function f to the study of an algebraic function W , in this section we aim to point out some difficulties that arise in regarding multiparameter functions. In order to illustrate such arguments, let us consider the following motivating example. Example 6. Consider the following polynomial

P (z, 1 , 2 ) = z 2 + 3 1 z + 2 2 1 + 2 2 2 , (9)
where 1 and 2 are considered as perturbation parameters. It is clear to see, that for 1 = 2 = 0, z = 0 is a root of multiplicity two. In this case, the solutions z 1,2 ( ) are not analytic at := ( 1 , 2 ) = (0, 0) = 0. Furthermore, z 1,2 ( ) does not have a unique representation as a power series which is convergent in some punctured neighborhood of the origin. In order to illustrate this assertion, let us consider the region | 1 | < | 2 |, in this region the solutions admit the following representation

z 1,2 ( ) = - 1 2 (3 1 ± i4 2 ) + 1 16 1 ±i 1 2 ± i 64 1 2 3 + ± i 2048
z k ( )=-2 k-1 1 +(-1) k 4 2 2 1 +4 2 1 3 + 32 2 1 5 + O 1 2 5 .
The above arguments clearly have shown that some further considerations must be taken into account in the case of multiparameter functions. Next, as mentioned in previous sections, in the single parameter case, the Newton diagram is a powerful tool to analyze the asymptotic behavior for the solutions of pseudo-polynomials. However, in order to be able to apply such a procedure to the multiparameter case, some special situations must be taken into consideration. In order to motivate the above arguments, let us consider the following.

Example 7. Consider the polynomial P (z, ) :

= z 5 + 1 3 2 + 2 1 2 2 z 3 + 2 1 2 2 + 3 1 2 z 2 + 4 1 2 .
Clearly, z = 0 is a 5-multiple root at = (0, 0). Now, let us form the Newton diagram with respect to 1 , obtaining Π = {(0, 4), (2, 2), (3, 1), (5, 0)}, illustrated in Fig. 2(a). The slope β 0 = 1 determines 3-solutions with respect to 1 , and coefficients that are solutions of the polynomial P(ξ) = 2 + 2 2 ξ 2 + 3 2 ξ 3 = 0. In this case, it is clear that the solutions cannot be easily computed. In order to compute solutions by applying the Newton procedure, we seek for a monic polynomial. Thus, with the aim of overcoming such difficulty, let us consider the change of variables (blowing-ups)

ζ := ξ 1 = v 1 2 2 = v 2 , and v 1 = y 1 v 2 v 2 = y 2 .
In addition, these changes of variables will enable us to avoid horizontal segments in the subsequent steps of the process. The resulting polynomial P (y 1 , y 2 ) posses the same Newton polygon, and the segment with β 0 = 1 has a monic polynomial y -5 2 P (ξ, y 2 ) = y 4 2 + y 2 ξ 2 + ξ 3 = 0. Applying the Newton procedure, (see figure 2(b)) to the above equation, we derive the fractional power series solution of P :

ζ 1 (y 1 , y 2 ) = -y 2 y 1 + o (y 1 y 2 ) , ζ 2,3 (y 1 , y 2 ) = ±iy 2/3 2 y 1 + o y 1 y 1/3 2 .

Problem Formulation

The present work is focused on computing the first approximation of the solution of quasi-polynomials around multiple imaginary roots. In this vein, we will focus in the following problems:

(i) compute an approximation of the associated Weierstrass polynomial; (i) extend the Newton diagram procedure to Weierstrass polynomial of several variables; (iii) obtain conditions that allow obtaining Puiseux series solutions s(τ 1 , τ 2 ) = c(τ

1/d 2 )τ β 1 + o(τ 1/d 1 τ 1/d
2 ), where β = α/d and α ∈ N.

MAIN RESULTS

Computation of Weierstrass Polynomial

In [START_REF] Mailybaev | On the Weierstrass Preparation Theorem[END_REF], the authors propose a method to compute the Weierstrass polynomial for an holomorphic function. This method is based on its partial derivatives and combinatorial factors related in a recursive way. For the case of holomorphic function, f (z, x) of complex variables with x = (x 1 , x 2 ) and z = 0 a mmultiple root at (x 1 , x 2 ) = (0, 0) the computation is given as follows. The coefficients w i in (4) are analytic, w i (0, 0) = 0 and can expressed in the form of Taylor series:

w i (x 1 , x 2 ) = ∞ h1+h2=1 1 h 1 !h 2 ! w i,h x h1 1 x h2 2 ,
where h = (h 1 , h 2 ). The following notation is used:

w i,h = ∂ h1+h2 w i ∂x h1 2 ∂x h2 1 (0,0) , F j,h = ∂ h1+h2 F j ∂x h1 2 ∂x h2 1 (0,0)
.

Since the analytic function locally satisfy f = W b, thus its partial derivatives satisfy the following recursive relations

w i,h = i j=0 α ij F j,h , (10)
F j,h = f j,h - j k=0 h +h =h c (j, k; h , h ) w k,h b j-k,h ,
with h = 0, h = 0 and constant coefficients:

α jj = m! j!f m,0 , α ij = - m! f m,0 i-1 k=j f m+i-k,0 α kj (m + i -k)! , c (j, k; h 1 , h 2 ) = j! (j -k)! 2 s=1 (h s + h s )! h s !h s ! , and for h = 0, k = k + m, b k,h is given by k! (m+k)!   f k ,h - m-1 j=0 h +h =h c (k , j; h , h ) w j,h b k -j,h   .
Since we are only interested in the leading terms of w i , namely a first approximation of the Weierstrass polynomial, we adopt the following notation.

Definition 8. Let the natural numbers n

(j) i , for i ∈ {0, 1, • • • , m -1} and j = 1, 2, denote the first non zero partial derivative in (z, x 1 , x 2 ) of f , such that the following conditions hold f (0, 0, 0) = ∂ i f ∂z i = • • • = ∂ i+n (j) i -1 f ∂z i ∂τ n (j) i -1 j = 0, ∂ i+n (j) i f ∂z i ∂τ n (j) i j = 0,
with derivatives evaluated at (0, 0). For n

(j) i = ∞ we have derivatives ∂ i f ∂z i = • • • = ∂ i+n i -1 f ∂z i ∂τ n i -1 2 = 0, ∂ i+n i f ∂z i ∂τ n i 2 = 0, evaluated at (z, x) = (0, 0, 1).
Leading terms of coefficients w i can be easy found up to the n (j) i

and n i derivatives, as a first observation we give the following result. Proposition 9. Suppose that the Weierstrass polynomial has first non-zero partial derivative, such that

n (j) i > n (j) i+1 , 0 ≤ i < m and j = 1, 2.
Then, the leading terms of w i (x) are given by

w i (x 1 , x 2 ) = α ii f i,(n (1) i ,0) x n (1) i 1 + α ii f i,(0,n (2) i ) x n (2) i 2 + • • • . If n (j) i = ∞ we get w i (x 1 , x 2 ) = α ii f i,(n i ,η) x n i 1 x η 2 + • • • . Remark 10.
There may be a case in which

f i,(h1,h2) (0,0,0) = 0 ∀ h 1 , h 2 ∈ N.
Since w i are analytic functions, this is equivalent to w i (x) ≡ 0 for 0 ≤ i ≤ κ -1. Thus, according to Theorem 1 f has the following local structure:

z κ z m-κ + w m-κ (x)z m-κ-1 + • • • + w κ (x) b(z, x).

The Newton Diagram Method for Two Parameters

Consider the monic pseudo-polynomial f (z, x) of the form

z m + a m-1 (x 1 , x 2 )z m-1 + • • • + a 0 (x 1 , x 2 ), (11) with a i (x) ∈ C [[x]
], such that f (0, 0) = 0. The equation f = 0 can be solved by applying the Newton diagram method, this is done taking into account just one variable, say x 1 , and proceeding iteratively. We take the point π k as the order of a k in x 1 , taking x 2 as an element of C ((x 2 )). For such a purpose, the following definition will be useful

ρ k := ord x1 (a k (x 1 , x 2 )) = ord (a k (x 1 , 1)) .
(12) Then, the Newton Polygon of f (z, x), with respect to x 1 , is defined by the lower boundary of the convex hull of the points (k, ρ k ) ∈ Π (see, Definition 4). In order to apply the the Newton diagram procedure, according to Section 2.4, the solution z will take the following structure

z(x 1 , x 2 ) = i c i (x 2 )x i/d 1 ,
where the coefficient c i (x 2 ), is in general, given by an univariate Puiseux series in x 2 .

First

Step into the Newton Procedure Let us suppose that we have determined the Newton diagram of the Weierstrass polynomial (11) of f . Since we are dealing with monic polynomials, the Newton polygon has a finite number of segments, each one with a corresponding set of points Π ( ) and rational numbers β ≥ 0 satisfying

β 0 > β 1 > • • • > β r .
Therefore, the segments are presented in two possible ways. The first one corresponds to a Newton polygon with a horizontal segment with β i = 0, and the second one where β j > 0 (for i = j). In this vein, for 0 ≤ < m, the Newton Diagram Π is given as the set Π = Π ∪Π : {(0, ρ 0 ), . . . , ( , 0)} ∪ {( , 0) , . . . , (k, ρ k ), . . . , (m, 0)} .

Lets take at the first step of the process a horizontal segment with slope β r = 0. We have the next two propositions. Proposition 11. Let f (z, x) be a pseudo-polynomial with the same structure as (11). Suppose that at least one coefficient a i (x) posses order ρ i = 0. Then, the equation P(ξ, x 2 ) = 0 (8) of the corresponding horizontal segment has solutions c k (x 1/d 2 ) in the form of Puiseux series. Now, at the first step of the process, the case with negative slope is considered. Hence, applying to f the change of variables z = ζ, x 1 = y a1 1 and x 2 = y a2 2 we get f (ζ, y 1 , y 2 ). Proposition 12. Assume that f has the same structure as (11) and assume that the first Newton diagram posses a segment with negative slope. Then, there exist a change of variables (z, x 1 , x 2 ) → (ζ, y 1 , y 2 ) such that the polynomial P(ξ, y 2 ) has Puiseux series solutions c k (y

1/d 2 ).
The iterative process continues by solving P = 0, using the usual Newton diagram procedure.

Newton Polygon Algorithm

Let us consider the points π = ( , ρ

(1) ) ∈ Π to get the Newton polygon, obtaining a finite number of segments with slopes -β r . Now, based on the Newton procedure Algorithm 1 Auxiliary Puiseux Series Expansion Let f (s, τ ) have a root s * = iω * of multiplicity m at τ = (τ * 1 , τ * 1 ). Consider the initial values as r := 0, i -1 := κ, -1 := n κ . 1) Set E r := -r-1 ir-1-i : (i, ) ∈ Π, and i > i r-1 . 2) Let β r := max E j and Π (r) r) . 4) Set m r := i r -i r-1 and r = r + 1. 5) If i r-1 < m go to step 1. Otherwise the algorithm ends. introduced in Section 2.3 we propose Algorithm 1. In the algorithm, κ is defined according to Remark 10.

:= {(i r-1 , r-1 )} ∪ (i, ) ∈ Π : β r ≡ -r-1 ir-1-i . 3) Set (i r , r ) ∈ Π (r) such that i r ≥ i, ∀(i, ) ∈ Π (

Puiseux Series for Quasi-Polynomials with two delays

Since any critical solution (s * , τ * 1 , τ * 2 ) can always be translated to the origin by appropriate shifts s

→ s -s * , τ 1 → τ 1 -τ * 1 , τ 2 → τ 2 -τ * 2
, hereinafter we will assume that (s * , τ * 1 , τ * 2 ) = (0, 0, 0). Proposition 13. Consider the following quasi-polynomial f (s, τ 1 , τ 2 ) = p 0 (s) + p 1 (s)e -sτ1 + p 1 (s)e -sτ2 , (13) with s = 0 a m-multiple root at τ = (0, 0) and local representation f (s, τ ) = W (τ )b(s, τ ). If n (j) i = 0 for i = 0, 1, . . . , k then, the k +1 coefficients of the Weierstrass polynomial W satisfy w m-i (τ ) ≡ 0, i ∈ {0, 1, . . . , k}. Proposition 14. Let quasi-polynomial f (s, τ ) have a mmultiple roots s = 0 at τ = (0, 0), with associated Weierstrass polynomial W . Assume that R W, ∂W ∂s = τ a1 1 τ a2 2 U(τ 1 , τ 2 ) such that U(0, 0) = 0, where (a 1 , a 2 ) ∈ Z 2 ≥0 \ {0}, U ∈ C{τ 1 , τ 2 }. Then, f = 0 posses m solutions given by a generalized Puiseux series.

Finally, the following result gives some conditions to have a regular Newton diagram. Proposition 15. Let W (s, τ 1 , τ 2 ) be the Weierstrass polynomial of a given quasi-polynomial f (τ 1 , τ 2 ). Assume that for a given -segment of the Newton diagram, be -β < 0 its slope with corresponding points Π ( ) = {(k 1 , ρ k1 ), (k 2 , ρ k2 ), . . . , (k s , ρ ks )}. Then, the equation P can be solved without any change of variables if the leading terms of the coefficients w ki satisfy w ki,(ρ k i ,η k i ) = 0 whenever η ki > η ks , i < s. .

NUMERICAL EXAMPLE

Example 16. Consider the following quasi-polynomial f (s, τ ) = s 2 -2s + 1 -2e -sτ1 + 2πse -sτ2 + e -2sτ2 , with τ = (1, π), we have a triple root at s = 0. In order to apply the proposed results, let us consider f (s, τ ) := f (s, τ 1 + 1, τ 2 + π). Now, by the Weierstrass Preparation Theorem, we know that the local behavior around the solution 0 of f , are captured by the solutions of s 3 + w 2 (τ ) s 2 +w 1 (τ ) s+w 0 (τ ). Since, the first non-zero partial derivatives are such that n

(1) 0

= n

(2) 0 = ∞, for h 1 = (1, 0), h 2 = (0, 1), we have according to Remark 10 the natural numbers n (j) 1 f 1,hj = (-1) j+1 2 ⇒ n (j) 1 = 1, j = 1, 2. Similarly, for n (j) 2 we have f 2,h1 = -4, f 2,h2 = 4π ⇒ n (j) 2 = 1. Thus, applying Proposition 9 we obtain

w 1 (τ ) = 6 1 -π 3 τ 1 - 6 1 -π 3 τ 2 + • • • w 2 (τ ) = -3 3 + 4π 3 (π -1)
2 (π 3 -1)

2 τ 1 + 3 (4π -1) 2 (π 3 -1) τ 2 + • • • .
Now, by taking the set of points Π = {(1, 0), (2, 0), (3, 0)} as input of Algorithm 1, we get a horizontal segment with β 0 = 0, deriving the polynomial P(ξ, τ 2 ). Hence, applying the Newton method to P(ξ, τ 2 ) = w 1 (0, τ 2 ) + w 2 (0, τ 2 )ξ + ξ 2 , we derive the leading terms of the solutions. Then, following the Newton procedure we get the points Π = {(0, 1)(1, 1), (2, 0)}. Thus, its Newton polygon has slope γ = 1/2 and associated polynomial P(ξ) := -6 1 -π 3 + ξ 2 = 0. Therefore, we conclude that the first terms of solutions of f around 0 are given by s 1 (τ 1 , τ 2 ) = 0,

s 2,3 (τ 1 , τ 2 ) = ± 6 1 -π 3 τ 1/2 2 + o τ 1/2 1 τ 1/2 2 .

CONCLUSION

In this paper, we have considered some issues concerning the asymptotic behavior of multiple critical roots for quasi-polynomials with two delays. The presented method is based on the Weierstrass Preparation Theorem which allows to deeply analyze the local behavior of a given solution. The proposed approach, using an extended Newton diagram method, can be effectively applied to find power series solutions in the form of generalized Puiseux series. Finally, we gave some conditions in which the solutions possess a regular behavior in the form of Puiseux series.

  Fig. 1. The Newton Diagram for f (x, y).

  instead of the previous region, we consider the region | 2 | < | 1 |, then for k ∈ {1, 2} the solutions admit the following representation

  Newton polygon with respect to y 2 .

Fig. 2 .

 2 Fig. 2. Newton polygons for P (z, ) in Example 7.

ACKNOWLEDGEMENTS

The research of J. Chen was supported in part by the Hong Kong RGC under Projects F-HK006/11T and CityU 11260016; the work of Martínez-González is financially supported by CONACyT, Mexico; the work of Méndez-Barrios has been supported by Centrale Supélec, France and partially supported by COPOCyT, Mexico.


Hui-Yin Wu

Marc Christie

Francesca Palù

Roberto Ranon

Thinking Like a Director: Film Editing Pa erns for Virtual Cinematographic Storytelling

Keywords: CCS Concepts:, Computing methodologies → Animation, Virtual reality, •Human-centered computing → Interactive systems and tools, •Applied computing → Media arts, lm storytelling, editing, virtual cinematography, assisted creativity, 3D animation

is paper introduces Film Editing Pa erns (FEP), a language to formalize lm editing practices and stylistic choices found in movies. FEP constructs are constraints, expressed over one or more shots from a movie sequence that characterize changes in cinematographic visual properties such as shot sizes, camera angles, or layout of actors on the screen. We present the vocabulary of the FEP language, introduce its usage in analyzing styles from annotated lm data, and describe how it can support users in the creative design of lm sequences in 3D. More speci cally, (i) we de ne the FEP language, (ii) we present an application to cra lmic sequences from 3D animated scenes that uses FEPs as a high level mean to select cameras and perform cuts between cameras that follow best practices in cinema and (iii) we evaluate the bene ts of FEPs by performing user experiments in which professional lmmakers and amateurs had to create cinematographic sequences.

e evaluation suggests that users generally appreciate the idea of FEPs, and that it can e ectively help novice and medium experienced users in cra ing lm sequences with li le training.

INTRODUCTION

"Good artists borrow, great artists steal. " Cinematography o en takes inspiration from other lms. Best practices for camera placement, movement, and editing have been wri en into lm textbooks, and are used over and over again in movies in various genres, because they are e ective in conveying speci c actions or emotions. e same knowledge widely used in lms can also bene t storytelling in 3D animated scenes, which are becoming increasingly popular, for example, to pre-visualize lms for reducing the cost and time on a real set, to pitch creative ideas, and to add cinematic sequences to video games and educational media. 1. By changing the camera angles, and hence the on-screen layout of characters, di erent emotional hints can be conveyed. Here the CG sequence replicates shots and edits observed in a real movie (film screen shots from Pulp Fiction).

To provide a more creative support for 3D cinematography, we propose Film Editing Pa erns (FEP), a language to formalize lm editing practices and common editing techniques (called idioms) used in lm, using vocabulary from lm textbooks. FEP constructs are constraints expressed over one or more shots that act on elements of visual style such as size, layout, and angle of actors on the screen. For example, FEPs enable one to encode typical shot-reverse-shot pa erns (i.e. switching the camera between two people who are looking at each other, as in Figure 1) that are common when lming dialogues, with ne control over actors' position and size in the frame. In addition to proposing such a language, we provide an algorithm that, given a set of FEPs applied to multiple shots, is able to select the cameras for each shot that make the sequence conform to the speci ed FEPs.

To investigate the potential of our proposal, we have created a tool for shooting and editing 3D animated sequences (i.e., a basic animated storyboarding / previsualization tool) where users, while still having manual control over the edited sequence, can use FEPs as a way of rapidly experimenting with creative and stylistic possibilities. To assess the acceptance and practical usefulness of our approach, we have conducted an evaluation with both professional lmmakers and amateurs with li le to no lmmaking experience. e rest of the paper is organized as follows. Section 2 presents related work. We then provide in Section 3 an overview of the FEP language with examples. Section 4 introduces automated lm analysis as a possible usage for FEPs, while Section 5 presents our editing tool and the algorithm for solving FEP constraints over multiple shots. In Section 6, we present our user evaluation, and in Section 7 we discuss the limitations of our work and future improvements.

RELATED WORK

Various techniques have been developed to instill lm knowledge into virtual cinematography systems. In general, the approaches developed so far concentrate on how actors are arranged on the scene (i.e. frame composition), basic lm idioms, and continuity rules that de ne how shots can be ordered as to maintain spatial and temporal continuity, without confusing the viewer. Most existing approaches do not consider stylistic editing choices over multiple shots.

Drucker [START_REF] Drucker | Intelligent camera control in a virtual environment[END_REF] was one of the rst to propose an idiom-like language for constraint-based cinematography that allows a smooth navigation of the camera through a complex virtual environment, like a museum room. Other early examples include Christianson et al. [START_REF] Christianson | Declarative camera control for automatic cinematography[END_REF], who introduced the DCCL language for planning sequences of camera movements, and He et al. [START_REF] He | e virtual cinematographer: a paradigm for automatic real-time camera control and directing[END_REF], who encoded lm idioms as nite state machines. Bares [START_REF] William | Realtime constraint-based cinematography for complex interactive 3D worlds[END_REF] introduced a constraint-based system for camera placement, gathering information about the occurring story events and making decisions on how to best show the ongoing actions. Similarly, Bares et al. [START_REF] William H Bares | A Model for Constraint-Based Camera Planning[END_REF] developed a constraint-based approach to framing and camera positioning for virtual cinematography, where the user can specify a number of constraints on the depth, angle, distance, region, occlusion, and the system will nd framings that satisfy those constraints. Notably, the Prose Storyboard Language (PSL) [START_REF] Ronfard | e Prose Storyboard Language[END_REF] was designed based on actual lm practice on shot composition, including vocabulary for elements like size, region, or movement. In the implementation by Galvane et al. [START_REF] Entin Galvane | Steering Behaviors for Autonomous Cameras[END_REF] for autonomous camera steering and composition, a search is conducted for camera positions based on PSL constraints. In a later work, they use semi-Markov chains to optimize a number of parameters in camera shot and cut decisions [START_REF] Entin Galvane | Continuity Editing for 3D Animation[END_REF], motivated by lm practice of evaluating narrative importance of actors, visual continuity, and rhythm in the edits. e approach developed by Lino et al. [START_REF] Lino | A Real-time Cinematography System for Interactive 3D Environments[END_REF] is another example of a system that is able to autonomously edit a sequence by choosing where to position cameras and how to perform edits that conform to continuity rules. Recently, Leake et al. [START_REF] Leake | Computational Video Editing for Dialogue-Driven Scenes[END_REF] proposed an automated editing system that would interactively generate an edit, from a number of clips of a same dialogue scene, based on idioms that best interpret the emphasis or desired feeling of the user. Compared to existing idiom-based systems, our approach provides a vocabulary and syntax based on elements of visual style in order to de ne a range of idioms potentially larger than existing work.

In interactive storytelling, planning techniques [START_REF] Amerson | Real-time cinematic camera control for interactive narratives[END_REF] and [START_REF] Jhala | Cinematic Visual Discourse : Representation , Generation , and Evaluation[END_REF] have proposed camera placement algorithms that correspond to the current story context. Film idioms and their associated storytelling meanings are encoded, and a planner chooses the best camera position for each event, while optimizing transitions between shots to improve the uency of the whole sequence. Elson and Riedl [START_REF] Elson | A Lightweight Intelligent Virtual Cinematography System for Machinima Production[END_REF] adopted the idea of blockings from lm practice, which involves the absolute placement of a number of characters and a camera in a non-occluded environment. e database of blockings, stages, and shots can be expanded. e camera is placed in pre-calculated relative positions in relation to the actors and stage, based on what is happening in the scene (e.g. how many actors are involved, scene type, action type). Constraints are also placed on how shots can be sequenced to avoid violating continuity rules.

e vast majority of virtual cinematography systems developed so far are non-interactive, and thus are not meant as tools to support users' creativity, with some notable exceptions, e.g. [START_REF] Lino | e director's lens: an intelligent assistant for virtual cinematography[END_REF], which however only considers continuity rules between adjacent shots. A number of applications in the market, mainly devoted to pre-visualization, allow a user to position cameras and perform editing on 3D animated scenes. However, in these applications users need to control camera positioning and editing at low level, and no knowledge of cinematography practices exist to assist users in their task.

is kind of assistance would at least bene t novice users, as shown by a Wizard-of-Oz study conducted by Davis et al. [START_REF] Davis | Creativity support for novice digital lmmaking[END_REF], where novice lmmakers could make fewer editing errors by bene ting from guidance about violated cinematography rules.

Our work is also related with computational techniques for lm analysis work. With respect to this, video and image processing currently have re ned methods for shot boundary detection [START_REF]Structured Representation and Automatic Indexing of Movie Information Content[END_REF] and genre analysis [START_REF] Rasheed | On the use of computable features for lm classi cation[END_REF]. Scene and event boundaries provide information on how a lm is structured, while genre identi es crucial emotional or story-archetype features. is has strong applications to categorization and recommendation systems of streaming services. Another aspect of cinematographic analysis focuses on the aesthetics of framing composition such as detecting shot types [START_REF] Svanera | Over-the-shoulder shot detection in art lms[END_REF] or meaningful sequences using continuity rules [START_REF] Wang | A cinematic-based framework for scene boundary detection in video[END_REF] [START_REF] Tavanapong | Shot Clustering Techniques for Story Browsing[END_REF].

Current approaches both in analytical and generative systems already address de ning lm idioms and style over shot sequences. We hope to expand accessibility of lm knowledge in automated lm analysis and creativity tools with a lmmaking-friendly language that allows exible de nition and expansion of lm idioms that operate over multiple shots.

FILM EDITING PATTERNS

Film Editing Pa erns (FEP) is a language to formalize lm editing practices that span multiple shots. More speci cally, FEP constructs are constraints on the visual features of a sequence of shots. ese constructs are assembled from simple properties or relations that act on the visual features of a single shot (framing properties), or on the relation between subsequent shots (shot relations). In addition, one can restrict the length of shot sequences or require the presence of certain sub-sequences. Hereina er, for simplicity, we use the term FEP to denote either the language or a construct built with the language. e current language is extended from a previous version published in [START_REF] Wu | Analysing Cinematography with Embedded Constrained Pa erns[END_REF]. Here, we de ne the vocabulary of the language, and syntax of FEP.

Framing Properties

Framing properties de ne how actors are arranged on-screen (the on-screen layout), using four visual features: actors' size, an le, re ion, and number of actors. Each of these features has precise de nitions in lm literature [START_REF] Ze | Sight, sound, motion: Applied media aesthetics[END_REF]. We adopt a broad de nition of actors that incorporates humans, animated creatures, and objects.

Size. Shorter shots (i.e., closer cameras for a given lens) display bigger actors, increasing their importance; conversely, longer shots make the actors smaller and thus less important, or more in relation with their environment. We use the 9 shot size scale [START_REF] Ompson | Grammar of the Shot[END_REF] with the upper half body lling the frame as the median Medium Shot. Figure 2 shows all the shot sizes in the FEP language.

Angle. e camera uses horizontal, vertical, and roll angles with respect to actors to convey inner emotional states of actors, and express power relations between characters. For example, shooting actors from a lower angle creates a feeling that they are powerful, towering over the audience, whereas shooting actors from a high angle, with them looking up to the camera, gives the audience a feeling of dominance over the actors. Roll angles, more rarely used, give o a feeling of instability, since the ground is not parallel to the frame. Figure 3 shows all the angles provided in the FEP language.

Region. Framing region refers to how actors are arranged in the frame. Good arrangements improve aesthetics and can convey the inner state of actors or relations between actors. Our language provides a number of ways to describe the region of an actor in the frame: e regions are visualized in Figure 4. To decide the region, we focus on the most important aspects of actors: their head and eye positions, and possibly limb positions in scenes with interactions.

Fig. 4. The region in which actors appear can be described based on a 4-split (blue lines) or 9-split (red lines) of the screen. They can also be described in terms of the 2 or 3 split of the screen vertically and horizontally. As an example, the nose of Jennifer Lawrence (the right-most actor) can be described as appearing in the regions R4 2, R9 3, R2 RIGHT , R2 U PPER, R3 U PPER, and R3 RIGHT (shot from Hunger Games movie).

Number of actors. e number of actors indicates the relative importance of actors in the shot.

If each shot conveys equal amount of information, the more actors there are on-screen, the less important each of them is to the current event.

Shot Relations

Shot relations establish relationships between framing properties of two or more shots, like size, angle, or region. For example, we may describe a shot sequence that moves gradually closer to actors; or a shot sequence where actors appear in the same region in the frame. Shot relations provide FEP with the ability to de ne sequences following such constraints. Size. Changing the size from one shot to another can show the di erence in importance of actors in the scene, as well as intensify or relax the atmosphere by moving closer or further to actors respectively. e Size relations can be closer, further, or remain the same. Examples of size relations can be seen in Figure 5. Angle. Changing angles between shots can imply the relative strength of di erent actors, or change of emotional state for one actor. Angle relations can be either higher, lower, or the same. Examples of angle relations can be seen in Figure 6. Region. When actors appear in the same regions on the screen across shots, it o en means an agreement, compassion, or mutual recognition, while laying out actors across the horizontal axis (i.e. le and right) carries the meaning of opposition. Region relations can be same or di , with respect to the 9-split, 4-split, or horizontal/ ertical in 2-and 3-split standard. Examples of horizontal region relations can be seen in Figure 7.

Actors. Two consecutive shots can show the same actors (such as to narrate a continuous action that an actor is carrying out) or di erent actors to show a connection between two actors. Our language de nes that actor relations can either be actor-same or actor-di erent.

Continuity. Continuity rules ensure that the audience maintains spatial and temporal continuity from one shot to another. For example, the motion continuity rule states that if something is moving from the le to the right on the screen, it should still move le to right on the screen in the next shot. Another rule is the 180 degree rule, which states that when lming two actors, the camera should always stay on the same side of the line formed by the two actors (thus, in the same 180 degree range) maintaining their relative le /right positions. e line is referred to as the index line, and helps to ensure index continuity.

ough they are less systematically applied in modern lms, we still provide a de nition of most common rules as well as the vocabulary in the FEP language to express relations on motion/index continuit /discontinuit . Examples are provided in Figure 8.

FEP Language Syntax

Using the FEP vocabulary, we can de ne a variety of FEP constructs which correspond to actual lmmaking idioms. A FEP construct can contain multiple framing properties and shot relations, plus constraints on the length of a sequence (in terms of number of shots), or on the presence of a Index continuity keeps the camera on the same side of the index line between two actors, maintaining the relative on-screen positions of actors, while motion continuity maintains the actor's direction of motion on-screen. In violation of these rules, the actor positions and motions are sometimes discontinuous from one shot to another (screenshots from the films Ga aca, The Shining, The Curious Case of Benjamin Bu on, and The Constant Gardener).

certain sub-sequence. is section presents the incremental construction of the intensify FEP-an editing technique where the camera gradually approaches the actors over a number of shots-to illustrate how a FEP construct is structured. intensify{ size-relation: closer } is FEP, which applies to sequences of any number of shots, states that all shots must have a shot size relatively shorter than the previous shot. is de nition of intensify would be able to match a sequence of shot sizes like

[Long][Medium][Close-up], but it would reject [Long][Medium][Medium]
[Close-up], since the two middle shots are not closer in relation. Yet, a lm analyst would still consider this an intensify, since the shot size gradually increases over the whole sequence.

To overcome this limitation, we introduce the concept of embedded sub-sequences. Embedded sub-sequences are continuous sequences of shots that follow the constraints of some FEP, such that these shots can be grouped together in a parent FEP. In other words, individual shots in the sub-sequence are not evaluated by the relation set by the parent FEP. Using this concept, the de nition of intensify becomes: intensify{ size-relation: closer sub-sequence: same-size{ size-relation: same } } In this case, the above-described sequence would be considered as intensify. If not speci ed, the sub-sequence is a single shot.

If the user would like a constraint to be enforced on speci c shots or sub-sequences (e.g. shots 1, 3 should be Close Ups, and 2, 4 should be Long Shots), this can be achieved by se ing ranges.

e range parameter can either be continuous [x-], discrete < x, , z... >, or one of the keywords between initial (equal to < 1 > in the discrete list representation), all (all sub-sequences), none (a strong negating constraint on all sub-sequences), or end (the last sub-sequence). By default, the range of a constraint is all. With ranges, we can re ne our de nition of intensify to add the requirement that the rst shot is a Medium Shot (MS): Length. We can also restrict the length of an FEP, which checks the number of sub-sequences-and not the number of shots-in the sequence. Here we add a length constraint to intensify: We can exibly limit a sub-sequence to a single shot or an embedded FEP, creating complex FEPs that capture recurring changes over sequences. Since the evaluation of relations allows observations only between sub-sequences, the number of sub-sequences on which a relation constraint is evaluated is much more meaningful than the actual number of shots in the FEP.

Examples of Common FEPs

e FEP language provides a rich and exible vocabulary to de ne a number of stylistic rules or conventions directors commonly use in their lms. Here we present some examples of lming and editing techniques from lm textbooks de ned using our FEP constructs.

Composition and Continuity Rules.

Rule of thirds. A common framing composition rule for both lm and photography that states the main character's head (or main target object) must appear in the upper-third of the frame. Here we provide the de nitions of the four stylistic FEPs using the syntax described above. Shot-reverse-shot. Two di erent actors appear individually in two consecutive shots of the same size with both actors looking o screen in opposite directions to indicate that they perceive each other. Shot-reverse-shot is a complex pa ern with a strong psychological aspect (i.e. gaze, perception). Without story context or a 3D reconstruction of the scene, there is no way to know if two actors are actually looking at each other, but the framing aspect of the technique can be modelled as: shot-reverse-shot{ length: == 2 size-relation: same (range: all) actor-relation: actor-different (range: all) framing-actor-num: == 1 (range: all) } e example in Figure 9 shows that directors frequently overlap FEPs to communicate complex emotions and meanings throughout the lm. Table 1 summarizes these ve FEPs.

FEP FOR FILM ANALYSIS

A rst usage of FEP is lm analysis on annotated lm data. As an example, we can investigate how much the FEPs presented in the previous section are employed in cinematography. To do that, we have constructed a database of 22 clips, each of roughly 5 to 10 minutes in length, from 18 well-known movies, spanning di erent genres and a time frame between 1955 and 2012. e clips were usually the most memorable or famous sequences from each movie, based on YouTube searches. In total, our database contains 1018 annotated shots, and is publicly available at: h ps://github.com/husky-helen/FilmAnnotation. is data set was rst published in [START_REF] Wu | Analysing Cinematography with Embedded Constrained Pa erns[END_REF] with detailed analysis on FEP related features in [START_REF] Wu | Analyzing Elements of Style in Annotated Film Clips[END_REF]. Here we provide a broad overview of what the database contains and how we have used FEPs to analyze these movie clips.

For each shot in the database, at least one framing was annotated, reporting:

• the frame number (from the lm clip)

• list of all the actors in the framing • the head, le eye, and right eye positions of each character in the framing

• other signi cant body parts, such as hand, foot, when the head and eye positions were not available • non-animate objects crucial to the story • the angle of the camera relative to the main character e head was annotated in terms of its size, position, and azimuth angle with respect to the camera, while other elements were annotated for their on-screen x and y positions, respectively as a ratio of the width and height of the frame space.

We can then use FEPs as a mean to analyze lm style. We analyzed the database for occurrences of four FEPs presented in the previous section: same-size, intensify, opposition, and frameshare. In this analysis, shot-reverse-shot was le out. Due to the di culty in determining if two characters are indeed looking at each other (as explained in the previous section), the FEP's matches are not that meaningful in this context, since they cannot con rm nor indicate the psychological connection between two targets.

As de ned before, each FEP has (i) a set of framing properties, e.g. framing-size: MCU, (ii) a set of shot relations, e.g. size-relation: closer, and (iii) a set of sub-sequence constraints, e.g. sub-sequence: FEP, and represents a query that a user can perform over an annotated lm clip.

e solving process is an extension of the Knuth-Morris-Pra algorithm [START_REF] Knuth | Fast Pa ern Matching in Strings[END_REF], expressed as a search over a sequence S of annotated frames. Since in our annotated data, multiple keyframes are annotated in each shot, the rst keyframe is selected to represent the shot in S. e search iterates through S and tries at each iteration to match the given FEP starting from frame i (where 1 < i < Card (S )). e solver returns a set R = {r 1 , .., r n } of sub-sequences such that r n = [f I , f F ] where f I and f F represent respectively the starting and ending frames of the sequence that match the FEP.

For the sake of performance (i.e. avoiding re-evaluation of the satisfaction of framing properties, shot relations and sequence constraints), the search is run in two stages. e rst stage builds a cache of valid solutions as three sets of frame sequences FC, RC and SC. e rst represents the sets of frames that satisfy each of the framing properties mentioned in the FEP. e second represents the sets of successive frames [f i , f i+1 ] that satisfy the shot relations, and the last represents the set of frame sequences SC = {s 1 , .., s m } where s i = [f I , f F ] and where f I and f F represent respectively the starting and ending frames that satisfy the speci ed sub-sequence.

e search algorithm (FEPRecurse) relies on the function isValidFrame() to evaluate whether the frame f i is within the set of valid frames FC. e same process occurs with isValidRelation() and isValidSubsequence().

e function isValidSequence() simply checks that the given length of the sequence is valid (since all frames, relations and subsequences are valid).

en, in a second stage, the process iterates over all frames f i of the sequence S (see Algorithm 2). At each iteration a double recursive depth search is performed from the current frame with a simple idea: the next frame is retrieved from the sequence S, and if valid, is either considered as part of a subsequence (see line 4) or part of the sequence (see line 6).

e algorithm is then applied to our annotated database of clips. We found that all clips used at least one of the four FEPs, with more than half of the shots in each clip using one or more FEPs. • for each shot, select a framing (i.e., a camera) among a framing database, which is dynamically computed by the system on the basis of the 3D position of actors at the cut point (or at any time inside the shot, chosen by the user); • apply a FEP to a selection of shots in the sequence, and as a result, reduce the choice of available framings to the ones that satisfy the FEP. Any action of the user, for example selecting a certain framing for a shot, results in the system re-applying the FEPs to ensure that the resulting sequence always satis es them.

e idea is that the user can creatively experiment with di erent editing choices by thinking in terms of stylistic choices, emotion building, and relations between actors, instead of worrying about lower level aspects such as camera position and basic continuity rules.

Figure 13 shows the interface of the system, developed in Unity, which resembles popular editing applications like Adobe Premiere of Final Cut Pro. For a demonstration of the application, please view the accompanying video. Our system is composed of the interpreter for FEP vocabulary and the interactive solver. On the system side, the inputs are the definitions for the FEPs and also annotated film data. Based on interactions from the user, the solver then proposes framings for each shot in the sequence. The 3D environment geometry is analyzed by the solver, and framing recommendations are returned to the user via the application interface.

At an architectural level, the system is composed of:

• the interpreter for the FEP language; • a database of lm framings, which considers situations with one or two actors at all possible camera lengths and angles;

• a solver that: (i) computes actual framings based on the positions of actors in the scene at a certain instant; (ii) restricts the possible framings to the ones that respect the constraints de ned in a speci ed FEP.

Figure 12 provides an overview of the architecture of our system. In the following section, we explain how the FEP solver works. FEPs can be applied to a number of shots in the sequence in order to filter the framings to those that can fulfill the applied pa ern. In the figure, an intensify pa ern has been applied to three shots.

FEP Solver

e solver uses the Toric manifold method [START_REF] Lino | Intuitive and E cient Camera Control with the Toric Space[END_REF] which provides an algebraic computation of virtual camera positions based on a number of desired visual features, such as size of actors on screen, vantage angles, and on-screen position of one or two targets (e.g. two actors, or the le and right eye of the same actor). For example, we can compute a camera showing two actors, where one is on the le side of the frame, while the other is on the right side, and their heads are in the same vertical region. We refer the reader to [START_REF] Lino | Intuitive and E cient Camera Control with the Toric Space[END_REF] for details on the calculation.

In this paper, we concentrate on the other function of the solver: given a list of FEPs applied to speci c shots, propose for each shot a selection of framings from the database that ful ll all the FEPs applied to the sequence. First, the solver initializes each shot with a list of candidate framings.

e main algorithm of the solver (Algorithm 3) is a constraint propagation method that maintains and updates an active list of FEP instances that are yet to be solved. Each FEP instance contains an FEP and an ordered list of shots S [x, ] to which the FEP is applied. Algorithm 3 iterates on the list of FEP instances, and incrementally lters the framing candidates for each shot in the FEP instance by calling Algorithm 4. us at each iteration, Algorithm 3 produces the subset of framing candidates that ful lls the considered FEP instance and all the preceding FEP instances. If Algorithm 4 removes framings in shots that overlap with other solved FEP instances, the constraints must be propagated by adding those a ected instances back to the active list of FEP instances so that they can be re-solved. In this case, all overlapping FEP instances with p must be re-evaluated Fig. 14. The solver is called to calculate an initial solution and in response to a user's action. This figure shows how the solver filters the available framings for intensify on a five shot sequence, where each shot has the choice of a long (LS), medium (MS), and close-up shot (CU). In the initial solution, all framings that have a path from the first shot to the last are validated. Three types of interactions can follow the initial solution:

(1) applying another FEP, same-size, to shots 3 and 4, the LS option is removed from shot 3 (2) deleting shot 4 from the sequence, the solver re-evaluates intensify for the remaining shots. (3) selecting a LS framing for Shot 3, shots 2 and 4 are filtered again to only allow framings that have a valid path through the LS framing of Shot 3. for each shot de ned in S [x, ] to ensure that the changes made by Algorithm 4 still uphold for the other overlapping FEPs. Algorithm 3 iterates either until there are no more FEPs in the list, indicating all FEPs are solved, or until Algorithm 4 returns false, indicating that the combination of FEPs cannot be solved. e actual validation of constraints de ned in FEP p is carried out by Algorithm 5. We solve each FEP p by evaluating whether each frame in the whole sequence S [x, ] ful lls the framing and relation constraints, and whether the sequence can be split into a number of sub-sequences that ful ll the sub-sequence constraints (described in Section 3.3). Each possible framing f i from the candidate framings must be either validated or rejected as a candidate for s j in the considered FEP instance based on the following condition: if there exists a sequence of framings f x , f x +1 , ...f i , ...f for each shot S [x, ] that ful lls the constraints set by the FEP (Algorithm 5), then f i is validated, which means the framing should be available for selection. If no combination containing f i can be validated, then f i is rejected. At the end of the process, the remaining framings for each shot are made available to the user for interactive selection.

Suppose there is a framing database of n framing speci cations over a sequence of m shots, the complexity of the algorithm would be at the worst case n m , which makes the algorithm quite slow, since it is a full search over all possibilities. However, typically users work with 2-3 shots at a time, making the algorithm able to respond at interactive rates.

e solver is called when a new FEP instance is added by the user, when shots are added or removed from one or more FEP instances, or when a framing is selected for a shot in one ore more FEP instances. e solver reacts to these three types of actions as following:

A new FEP instance is added: When a new FEP e is added to a number of selected shots, e is added to the FEPInstanceList P of Algorithm 3. If when solving e, the solver removes framing propositions from shots with another FEP instance e , then e is added to the FEPInstanceList P. In this manner, the constraints of e are propagated to all other overlapping FEPs as well as those indirectly overlapping. us the solver continues to solve for each instance in P until the algorithm converges, or until no solution can be found for a speci c instance.

Adding/Removing of a cut or a shot: e shot s is added/removed from the range of all overlapping FEP instances, and all the FEP instances are pushed into the FEPInstanceList P in Algorithm 3 to be re-evaluated. If no solution exists for an FEP, the FEP is removed. Each time an FEP is removed or if the FEP removes proposed framings from a shot, all overlapping FEPs are pushed into the FEPInstanceList P to be re-evaluated.

A framing F m is selected for a shot S n : F m is set as a new constraint and propagated to overlapping FEP instances. All framing proposals as well as selected framings for other shots must have a validated path through F m for S n , which means in Algorithm 4, the list of candidate framings can include only the user-selected framing when other shots would like to validate their candidate framings. However, if we simply set F m as a hard constraint by removing all other framings of S n from the candidate framings list, this would result in only one available framing F m to select from for S n , preventing the user from changing to another framing that can also be validated by the whole sequence. Instead, we would still want to be able to propose for S n an augmented set of framings where, despite not the selected framing of the user, still have a valid solution through framings of other shots that have been validated by all other FEPs and constraints. To accommodate this, we simply add an additional condition to Algorithm 5 to return true only when the FEP is validated, and when all other framings in Sequence F are selected framings (where available). is allows us to "validate" a framing that is not selected by the user, but still contains a valid solution in the sequence. is also prevents other shots to use this augmented set to validate their own framings, since Algorithm 5 will only return true when all other framings apart from the one at Position pos of Algorithm 4 must be a selected framing, if the user has selected one. Figure 14 shows how a user action of selecting a framing for a single shot would trigger the solver, and what the solver would do to uphold the FEPs on the new sequence.

else if isValidSequence(p, C ∪ { f i }) then 8 return ValidateFEP(p, { f i }, F \ { f i });

USER EVALUATION

To assess the e ectiveness and acceptability of using FEPs in editing tasks, we designed an experiment in which participants were asked to use our application to produce an edited sequence of a given animation. e considered animation is a 3D reconstruction of a scene of 80 seconds taken from the Robert Zemeckis movie Back to the Future, composed of four main characters (Marty, George, Goldie, Lou). e animated scene faithfully reproduced the movements of the characters, and included original audio from the movie, which was converted from stereo to mono, to avoid any inconsistencies between audio cues (a character heard on the le ) and visual cues (the same character framed on the right), hence enabling any editing choice.

ere were a total of 17 participants: 6 experienced lm professionals (4 of which had 10+ years of experience in lmmaking), and 11 amateur participants with only basic video editing experience.

e participants' ages were between 20 and 46. Two of the lm professionals had experience with 3D animation so ware, while most participants in the amateur group had some experience with 3D animation and graphics so ware. All participants had previously seen the Back to the Future movie, and could re-watch the selected clip before starting with the experiment.

Experimental procedure

First, participants were introduced to the experiment and were informally trained about FEPs by showing examples of their application in well-known movies. en, the functioning of the system was brie y explained, and a pre-evaluation survey, to collect demographic and user experience information, was administered. We then showed them once the lm original of the clip that they were to edit. is rst part took about 15 minutes. en, participants were asked to produce their best edited sequence by starting from an initial editing of the Back to the Future clip comprised of 23 shots (approximately one every 4-5 seconds), where, for each shot, a random framing among the ones in the database was chosen. e users were asked to meet three criteria within the limitations of the tool:

(1) A framing must be selected for each shot (2) the selected framing should express what is currently happening in the scene (3) the overall edit should be coherent and aesthetically pleasing roughout the task, they could remove cuts, add extra cuts, select framings for each shot, and apply or remove FEPs. ere was no time limit set for the task. Participants could choose whether or not to use FEPs for the task.

A er the task, a post-test questionnaire was lled to gather feedback on the application, and on the usefulness of FEPs.

Results

Some edited sequences produced by participants can be seen in the accompanying video. On average, users completed their task in about half an hour, with a maximum time of about 40 minutes. e sequences produced by the participants varied greatly from the original lm clip, generally with shorter shot lengths, and a larger variety of framing choices.

In the post-task questionnaire, we asked participants to rank on a Likert scale of 1 (strongly disagree) to 5 (strongly agree) the following statements:

• A. Concerning the application: (1) I'm satis ed with the output (2) e tool is easy to use (3) It's easy to predict the e ect of commands (4) e tool is e ective in creating sequences. • B. Concerning FEPs: (5) It's easy to work with FEPs (6) FEPs did not limit creativity [START_REF] Drucker | Intelligent camera control in a virtual environment[END_REF] FEPs produced good results (8) I understand how to apply FEPs (9) FEPs helped convey emotions. e overall impression of the tool was mostly positive. Figure 15 and 16 summarize the results of the post-survey questionnaire. One lm professional chose not to use the FEPs and felt that he was thus unable to evaluate statements (5) to [START_REF] Entin Galvane | Steering Behaviors for Autonomous Cameras[END_REF]. Table 2 shows how many times each FEP was applied in total for each group, and in parentheses, the number of people from the group that used the FEP.

e amateur group was more enthusiastic in terms of applying FEPs, each person using an average of 4.6 FEPs for a sequence of 23 shots. ough two participants commented on the di culty to understand how to apply the FEPs, the general feedback for this group was positive, appreciating the pedagogical aspect of FEPs, and mentioning that they in uenced the framings they chose and allowed them to explore ideas they never had before. It was noted that a large number of participants did not nd it easy to work with FEPs. is could be expected, as the concept of lm cinematography language would be relatively new to them. Nevertheless, as shown in the accompanying demo video, we found that with the assistance of the application, amateur video editors were able to make use of FEPs to create sequences that had similar shots as professionals, but with their own distinct styles. Users with some professional 3D animation and graphics backgrounds found the interface accessible and easy to use, and were moderately pleased with the tool, though many recommended adding more advanced functions to edit and create their own framings. Opinions of professional lmmakers were more polarized. Most of them felt that the editing functions were limited, and the provided FEPs too rigid for professional use, and as a result, they relied on them much less than the amateurs (Table 2). e feedback was within our expectations, as professional users with su cient lm knowledge would probably already have a desired edit to the sequence without aid from the system, and as the system was designed to be as simple as possible, it provides limited editing functions for ne-tuning each shot. Despite this, all the participants in this group reacted warmly towards the idea of incorporating lm knowledge as FEPs, and the ease of creating an acceptable edit. In the post-task survey, one lm director re ected positively that the FEPs "represent some of the most used cinematographic conventions since the beginning of the story of editing. " It was also mentioned multiple times how easy it was to make a edit and the experimental aspect of FEPs, which would especially bene t novices of lm editing. eir response validated that FEPs is a good representation of lm knowledge for the purpose of assisted creativity, and that FEPs can express common lm idioms and editing techniques that these professionals frequently use in their lms.

Indeed, the number and types of FEPs provided was probably too limited to cover all user styles and preferences. is suggests that an application should provide users with the possibility of designing their own FEPs, or maybe even automatically detect them from user-provided examples.

LIMITATIONS AND FUTURE WORK

e Film Editing Pa erns language provides a simple way to de ne complex editing constraints for automatic detection and enforcement of cinematographic pa erns. However, the visual features currently available in the vocabulary are limited to the size, position, angle and number of actors on-screen, and there are many other features that are essential to cinematographic storytelling, including lighting, sound, and staging, that we currently do not take into account when designing pa erns. With respect to camerawork, another notable limitation is the absence of properties and relations that refer to camera movement. While, for previsualization tasks and rough edits, camera movement might not be fundamental, we plan to overcome this limitation by expanding the FEP vocabulary with common movement properties, and incorporating the idea of camera path keyframes in the framing database that can be implemented by various camera movement algorithms.

Our interactive application was designed with ease of use and familiarity of the lm language in mind. As a prerequisite though, the application requires pre-designed 3D animations and assets, which may be hard to come by. However, given the growing availability of 3D content in asset stores, this seems less and less of a concern.

e editing pa erns presented in this paper are just examples that mainly come from lm textbooks. We foresee that our techniques can be improved and extended greatly with the collection of data through video processing techniques, and learning techniques to discover other common editing pa erns that directors use in lms. By releasing both our dataset and the animated scene, we hope that easily accessible resources for this application can be expanded on in the future.

Technically, extra FEPs and framings can be easily achieved by modifying the XML les that de ne our framing and FEP database.

In our evaluation, we targeted a diverse user group incorporating people of various levels of editing experience. In the post-task questionnaire, we found that our tool is best targeted towards people with mid-to low-professional experience in lmmaking: students of lm, amateur lmmakers, 3D animators. Our professional users, though the response towards the tool was mostly positive, commented also on the restrictions of the tool, notably the inability to design their own camera positions, or design di erent FEPs. Others suggestions mentioned elements non-related to the editing (e.g. audio, animation, staging). e addition of non-editing features will require closer future collaboration with lm educators and practitioners to tailor the tool to their speci c needs.

Fig.

  Fig.1. By changing the camera angles, and hence the on-screen layout of characters, di erent emotional hints can be conveyed. Here the CG sequence replicates shots and edits observed in a real movie (film screen shots from Pulp Fiction).

Fig. 2 .

 2 Fig.2. The nine framing sizes in the FEP language all appear in the same sequence in The Good, The Bad, and the Ugly.

Fig. 3 .

 3 Fig. 3. Angles of characters on the screen can be categorized into vertical, horizontal, and roll angle.

• 9 -

 9 split: the screen is split into three equal regions horizontally and vertically, and regions are named R9 1 to 9, with R9 1 being the upper-le of the frame, and R9 9 being the lower-right, as labelled in red on the example in Figure4. • 4-split: the screen is split into two equal regions horizontally and vertically, and regions are named R4 1 to R4 4, with R4 1 being the upper-le quarter of the frame, and R4 4 being the lower-right quarter, as labelled in blue on the example Figure 4. • 3-split horizontal/vertical: the screen is split into three equal regions horizontally/vertically, and named R3 U PPER, R3 MI DDLE V ER, and R3 LOW ER in a vertical split, and R3 LEFT , R3 MI DDLE HOR, and R3 RIGHT in a horizontal split, as indicated in the green labels on the outer rim of Figure 4. • 2-split horizontal/vertical: the screen is split into two equal regions horizontally/vertically, named R2 U PPER and R2 LOW ER in a vertical split, and R2 LEFT and R2 RIGHT in a horizontal split, as indicated in the yellow labels on the outer rim of Figure 4.

Fig. 5 .

 5 Fig. 5. A shot size relation can be relatively further (longer distance between actor and camera), closer (shorter camera-actor distance), or the same (screenshots from the film Ga aca).

Fig. 6 .

 6 Fig. 6. Example of shot angle relation being relatively higher or lower. The red line in the figures is a rough estimate of the horizon for illustration purposes (screenshots from the film The Hunger Games).

Fig. 7 .

 7 Fig. 7. Example of region relations between two successive shots (same region on the le , di erent regions on the right). Shots from Infernal A airs.

Fig. 8 .

 8 Fig.8. Continuity relations help the audience maintain spatial and temporal continuity between two shots. Index continuity keeps the camera on the same side of the index line between two actors, maintaining the relative on-screen positions of actors, while motion continuity maintains the actor's direction of motion on-screen. In violation of these rules, the actor positions and motions are sometimes discontinuous from one shot to another (screenshots from the films Ga aca, The Shining, The Curious Case of Benjamin Bu on, and The Constant Gardener).

  intensify{ framing-size: MS (range: initial) size-relation: closer (range: all) sub-sequence: same-size{ size-relation: same (range: all) } }

  intensify{ length: >= 3 sub-sequence: same-size{ length: >= 1 sub-sequence: shot{ size-relation: same (range: all) } } size-relation: closer (range: all) }

  Figure4is a good demonstration of the rule of thirds, where all three main characters' heads appearing on the upper third of the framing.

3. 4 . 2

 42 Stylistic FEPs. From lm textbooks, we identi ed ve commonly used FEPs that are used in lm storytelling, to invoke certain emotions among viewers, such as intensify, introduced in the previous section. Examples of all ve FEPs can be seen in a clip from Hunger Games in Figure9.

Fig. 9 .

 9 Fig. 9. Five FEPs with examples from an extracted film clip from Hunger Games: intensify, frameshare, opposition, shot-reverse-shot, and same size.

  Same-size. Actors appear the same size on screen over a sequence of 2+ shots. Used in dialogues and calm situations. same-size{ length: >= 2 size-relation: same (range: all) } Opposition. Actors appear individually in opposite horizontal regions over a sequence of 2+ shots. Used to express enmity, disagreement between the actors.

  opposition{ length: >= 2 region-relation: R2_HOR_Diff (range: all) framing-actor-num: ==1 (range: all) } Frameshare. Actors appear individually in the same horizontal regions over a sequence of 2+ shots. Used to express agreement or compassion between the actors. frameshare{ length >= 2 region-relation: R2_HOR_Same (range: all) framing-actor-num: ==1 (range: all) }

ALGORITHM 1 :

 1 FEPSearch (FEP p, Sequence S) 1 ResultSet R = ∅; while S not empty do 2 f i = f irst (S); FEPRecurse(p, ∅, S, i, R); S = S \ f i ; 3 end 4 return R ACM Transactions on Multimedia Computing, Communications and Applications, Vol. 0, No. 0, Article 0. Publication date: August 2018.

Fig. 11 .

 11 Fig. 11. Average length (in seconds) for all FEPs (embedded constraint pa ern) used through shot sequences in the film clips.

Fig. 12 .

 12 Fig.12. Our system is composed of the interpreter for FEP vocabulary and the interactive solver. On the system side, the inputs are the definitions for the FEPs and also annotated film data. Based on interactions from the user, the solver then proposes framings for each shot in the sequence. The 3D environment geometry is analyzed by the solver, and framing recommendations are returned to the user via the application interface.

Fig. 13 .

 13 Fig.[START_REF] Knuth | Fast Pa ern Matching in Strings[END_REF]. The application we developed contains basic functions to edit a sequence and view the result in real time. Framings are proposed for each shot (upper right corner), dynamically calculated from our framing database and generally covering each actor in the scene, or their combination, at di erent sizes and angles. FEPs can be applied to a number of shots in the sequence in order to filter the framings to those that can fulfill the applied pa ern. In the figure, an intensify pa ern has been applied to three shots.

ALGORITHM 3 : 7 forall 8 forall 10 P

 37810 ConstraintPropagate (FEPInstanceList P) 1 FEPListCopy P'=P; 2 while P'.count!=0 do 3 FEPInstance e=P'.pop(); 4 FEP p = e.F EP; 5 ShotSequence S = e.S [x, ] ; 6 FEPFilter(p,Empt Set,0,S); FEPInstance ei ∈ P do Shots s ∈ S do 9 if s∈ei.S [x, ] and ei P' then

  Algorithm 4 evaluates each FEP, and reduces the framings selection among the candidate framings for all shots s j ∈ S [x, ] .

Fig. 15 .

 15 Fig. 15. Users general impressions on the tool (easy of use, e ectiveness) and on the perceived quality of their produced sequence.

Fig. 16 .

 16 Fig. 16. Users general impressions on FEPs.

Table 1 .

 1 Summary of the 5 stylistic FEPs.

	FEP	length	description	usage
	Same-size	2+ shots	actors are the same-size across shots	dialogue, calm scenes
	Intensify	3+ sub-sequences a sequence of shots moving gradually closer build emotion
	Frameshare	2+ shots	actors in the same horizontal region	agreement, compassion
	Opposition	2+ shots	actors in opposite horizontal regions	enimity, disagreement
	Shot-Reverse-Shot	2 shots	two actors looking at each other in two shots perception

Table 2 .

 2 Number of times each FEP was used by each group (and in parentheses, the number of participants in the group that used the FEP).

	FEP	Professionals Amateurs
	Same-size	1 (1)	6 (5)
	Intensify	0 (0)	13 (8)
	Frameshare	0 (0)	8 (5)
	Opposition	2 (2)	18 (5)
	Shot-Reverse-Shot	4 (2)	6 (4)

ACM Transactions on Multimedia Computing, Communications and Applications, Vol. 0, No. 0, Article 0. Publication date: August 2018.

CONCLUSION

In this paper, we have proposed the concept of Film Editing Pa erns, which are evolving elements of visual style over (long) sequences of shots. We have shown how the language and design of FEPs is linked to actual lm theory and studies both by detecting the lm editing pa erns in annotated data, and by creating an editing application that uses them for smart editing guidance. Our application was evaluated by both lm professionals and amateurs. e evaluation has provided encouraging results, especially for non-expert users.

ALGORITHM 2: FEPRecurse (FEP p, CurrentSequence C, Sequence S, Index s, ResultSet R) is algorithm allows us to make quantitative observations on the evolution of average FEP lengths (in terms of the number of shots in the sequence) over these lm clips such as in Figure 11 or the usage of these techniques over the entire dataset, as shown in Figure 10. On average, intensify and same-size sequences can be much longer than any other FEP, applied to more than 5 shots in the sequence, as seen in e Good, the Bad, and the Ugly, American History X, and Pulp Fiction.

In the clip from Pulp Fiction, three types of sequences (intensify, same-size, and opposition) also cover more than 80% of the shots in the clip, which clearly shows that all three techniques can be used in parallel throughout a whole scene.

From this analysis, we can see that FEPs are very frequently used by lm directors, and our de nition is exible enough to successfully detect their occurrences in annotated lm data.

FEP FOR INTERACTIVE EDITING

Having con rmed that FEPs are indeed widely used in movies, we then designed an editing application that assists the user in creating an edited sequence from a 3D animated scene, and allows them to apply FEPs. More speci cally, the application allows the user to:

• cut the animation sequence into a number of shots;