https://anr.fr/Projet-ANR-19-CE43-0003 Olivier Chapleur • What is the stability of anaerobic microbial bioprocess in front of environmental perturbations?

Nouvelles perspectives dans les déterminants de la stabilité des bioprocédés anaérobies en couplant des approches multi-omiques et statistiques

• 4 triplicates of semi-continuous anaerobic digesters • 138 samples from anaerobic digesters (replicated time-series)

End of perturbation

Scenarii of perturbations

• Oxford Nanopore Technologies

•

  Assembly and binning individually for each sample • POOL-SAMPLES: Co-assembly and binning • POOL-CONSENSUS: Assembly per sample and co-binning • Assembly & Polishing • canu genomeSize=5m • minimap2 + racon --include-unpolished + 2 × medaka_consensus • Binning • metabat2 --minContig 1500 --maxEdges 500 • Pool MAGs and dereplication • dRep dereplicate --S_algorithm fastANI --P_ani 0.9 Number of reads and bases per sample, group per sequencing run (chronologically) • Quality and depth depend on runs and increases over our experience • 220308_Stabilics1 made on the same (bad) extraction than 211215• After preprocessing, we only loose short reads

MAGs Annotation -GTDB-Tk • Snakemake workflow

• Open to fork (and to advice) !

• Versionning on ForgeMIA

• https://forgemia.inra.fr/cedric.midoux/nanosnake

• Running on MIGALE cluster • Some steps required bigmem.q (2To RAM)

• Runtime = 10 days

• Including 4.6 days for eggNOG mapper (on bigmem.q)

• The assemblies require a lot of time (112 * few hours and 22h for coassembly) but they can be executed in parallel

• We tried to upgrade the basecalling to "high accuracy" but it's really long (20 days for 4 runs and not over) • Statistical issues

• How to normalize counts?

• MAG/gene catalog cleaning and validation

• Data integration

• … with physico-chemical measurements

• Workflow valorization? Standalone paper?

Current work


Introduction

To model real-life problems and perform computations we must deal with uncertainty and inexactness; they are due to measurement, due to simplification of physical models, due to variations of the parameters of the system, and finaly due to computational errors. Interval analysis is an efficient and reliable tool that allows us to handle the aforementioned problems, even in the worst case where all together are encoutered simultaneously. The input quantities are given with some interval estimation, and the algorithms output verified intervals as results, that, even though they usually have the drawback of overestimation, they cover all the possibilities for the input quantities.

In this paper we are interesting in the interval real eigenvalue problem. That is, given a family of matrices, that is an interval matrix, the task is to estimate the set of all possible eigenvalues. Moreover, there is a need to distinguish general interval matrices from the symmetric ones. Applications arise mostly in the field of mechanics and engineering. We name, for instance, automobile suspension system [START_REF] Qiu | An approximate method for the standard interval eigenvalue problem of real non-symmetric interval matrices[END_REF], mass structures [START_REF] Qiu | Bounds of eigenvalues for structures with an interval description of uncertain-but-non-random parameters[END_REF], vibrating systems [START_REF] Dimarogonas | Interval analysis of vibrating systems[END_REF], robotics [START_REF] Chablat | An interval analysis based study for the design and the comparison of 3-dof parallel kinematic machines[END_REF], and even principal component analysis [START_REF] Gioia | Principal component analysis on interval data[END_REF] and independent component analysis [START_REF] Comon | Independent component analysis, a new concept?[END_REF], which could be considered as a statistics oriented applications. Using the well-known Jordan-Wielandt transformation [START_REF] Golub | Matrix computations. 3rd ed[END_REF][START_REF] Horn | Matrix analysis[END_REF][START_REF] Meyer | Matrix analysis and applied linear algebra[END_REF], given a solution to the interval real eigenvalue problem, we can provide and approximation for the singular values and the condition number; both of which have numerous applications.

The first general results for the interval real eigenvalue problem are due to Deif [START_REF] Deif | The interval eigenvalue problem[END_REF], and Deif & Rohn [START_REF] Rohn | On the range of eigenvalues of an interval matrix[END_REF]. However, their solution depends on theorems that have very strong assumptions. Later, Rohn [START_REF] Rohn | Interval matrices: Singularity and real eigenvalues[END_REF], introduced a boundary point characterization of the eigenvalue set. Approximation methods were addressed by Qiu et al. [START_REF] Qiu | An approximate method for the standard interval eigenvalue problem of real non-symmetric interval matrices[END_REF] and by Hladík et al. [START_REF] Hladík | An algorithm for the real interval eigenvalue problem[END_REF]. The latter work is based on a branch and prune approach and yields results that depend on a given, arbitrarily high, accuracy.

The symmetric eigenvalue problem is very important in practice. However, it is hard to handle it, in its interval form, since the correlations between the entries of the matrices, make the algorithms that depend on interval analysis to overestimation, usually a lot, the results. The symmetric case was pioneered by Deif [START_REF] Deif | The interval eigenvalue problem[END_REF]. Another theoretical result is due to Hertz [START_REF] Hertz | The extreme eigenvalues and stability of real symmetric interval matrices[END_REF], see also [START_REF] Rohn | A handbook of results on interval linear problems[END_REF], for determining two extremal points of the eigenvalue set. Diverse approximation algorithms has also been developed. An evolution strategy method by Yuan et al. [START_REF] Yuan | An evolution strategy method for computing eigenvalue bounds of interval matrices[END_REF] yields inner approximation of the eigenvalues set. Matrix perturbation theory was used by Qiu et al. [START_REF] Qiu | Bounds of eigenvalues for structures with an interval description of uncertain-but-non-random parameters[END_REF], who proposed an algorithm for approximating the bounds, and by Leng & He [START_REF] Leng | Computing eigenvalue bounds of structures with uncertain-but-non-random parameters by a method based on perturbation theory[END_REF] for outer estimation of the eigenvalue set. Outer bounds that are easy and fast to compute were presented by Hladík et al. [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF]. Outer estimation for general parametric case was considered by Kolev [START_REF] Kolev | Outer interval solution of the eigenvalue problem under general form parametric dependencies[END_REF].

In this paper, we propose a filtering method for reducing the overestimation produced by many methods. Generally, filtering is very useful approach used in constrained programming, but few is known for the interval eigenvalue problem. We can, of course, apply any filtering for the interval nonlinear system of equations arising from eigenvalue definition, but no such approach has been successful yet; cf. [START_REF] Hladík | An algorithm for the real interval eigenvalue problem[END_REF]. To the best of our knowledge, there is only one paper by Beaumont [START_REF] Beaumont | An algorithm for symmetric interval eigenvalue problem[END_REF] giving an iterative algorithm based on convex approximation of eigenpairs. We present a new filtering method which is more simple and applicable for both the symmetric and unsymmetric case. Because we do not take into account eigenvectors, the filtering is much more efficient.

The rest of the paper is structure are follows. In the next section we present the basic definitions and our main theoretical result. In Sec. 3 we present our algorithm, while in Sec. 4 we exploit it on numerical examples. Sec. 5 presents our conclusions.

Basic definitions and main theorem

Let us introduce some notions from interval analysis. An interval matrix is defined as a family of matrices

A := [A, A] = {A ∈ R m×n ; A ≤ A ≤ A},
where A, A ∈ R m×n , A ≤ A, are given matrices, and the inequality is considered element-wise. By

A c := 1 2 (A + A), A ∆ := 1 2 (A -A)
we denote the midpoint and radius of A, respectively. Let A ⊆ R n×n be a square interval matrix. Its eigenvalue set is defined as

Λ(A) := {λ ∈ R; Ax = λx, x = 0, A ∈ A}.
An outer approximation of Λ(A) is any set having Λ(A) as a subset.

An important class of matrices is that of symmetric ones. Its generalization to interval matrices is as follows. A symmetric interval matrix is defined as

A S := {A ∈ A | A = A T },
and its eigenvalue set is denoted similarly to generic case, that is

Λ(A S ) := {λ ∈ R; Ax = λx, x = 0, A ∈ A S }.
A symmetric interval matrix A S is a proper subset of A, and so its eigenvalue set, Λ(A S ), is in general a subset of Λ(A).

Since a real symmetric matrix A ∈ R n×n has always n real eigenvalues, we can sort them in a non-increasing order as follows

λ 1 (A) ≥ λ 2 (A) ≥ • • • ≥ λ n (A).
We extend this notation for symmetric interval matrices, that is

λ i (A S ) := λ i (A) | A ∈ A S .

INRIA

These sets form n compact intervals, which can be disjoint or may overlap, see for example [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF]. The union of these interval results Λ(A S ). We denote their outer approximations by

ω i (A S ) ⊇ λ i (A S ), i = 1, . . . , n.
Let ρ(•) be the spectral radius, and |•| the matrix absolute value, understood componentwise. Our main theoretical result is the following. It employs the sufficient regularity conditions by Beeck [START_REF] Beeck | Zur Problematik der Hüllenbestimmung von Intervallgleichungssystemen[END_REF] and Rump [START_REF] Rump | Solving algebraic problems with high accuracy[END_REF]; compare Rex & Rohn [START_REF] Rex | Sufficient conditions for regularity and singularity of interval matrices[END_REF].

Theorem 1. Let λ 0 ∈ Λ(A) and define M := A -λ 0 I. Then (λ 0 + λ) ∈ Λ(A) for all real λ satisfying |λ| < 1 -1 2 ρ |I -QM c | + |I -QM c | T + |Q|M ∆ + M T ∆ |Q| T 1 2 ρ (|Q| + |Q| T ) , ( 1
)
where Q ∈ R n×n , Q = 0, is an arbitrary matrix.

Proof. It suffices to prove that every λ satisfying (1) the interval matrix M -λI = Aλ 0 I -λI is regular, i.e., consists of nonsingular matrices only. It is known [START_REF] Rex | Sufficient conditions for regularity and singularity of interval matrices[END_REF] that an interval matrix B is regular if for any matrix

Q one has ρ(|I -QB c | + |Q|B ∆ ) < 1.
Substituting B := M -λI we obtain a sufficient condition for λ not to be an eigenvalue

ρ(|I -Q(M c -λI)| + |Q|M ∆ ) < 1.
By theory of non-negative matrices [START_REF] Horn | Matrix analysis[END_REF], ρ(A) ≤ ρ(B) provided 0 ≤ A ≤ B. In our case, we have

ρ(|I -Q(M c -λI)| + |Q|M ∆ ) ≤ ρ(|I -QM c | + |λ||Q| + |Q|M ∆ ).
It holds [START_REF] Horn | Topics in matrix analysis[END_REF] that ρ(B) ≤ 1 2 ρ(B + B T ) for any B ≥ 0. Thus, we obtain

ρ(|I-QM c |+|λ||Q|+|Q|M ∆ ) ≤ 1 2 ρ |I -QM c | + |I -QM c | T + |λ|(|Q| + |Q| T ) + |Q|M ∆ + M T ∆ |Q| T .
The resulting matrix in the right-hand side is symmetric, thus we can exhibit the well-known Weyl's theorem [START_REF] Golub | Matrix computations. 3rd ed[END_REF][START_REF] Horn | Matrix analysis[END_REF][START_REF] Meyer | Matrix analysis and applied linear algebra[END_REF][START_REF] Wilkinson | The algebraic eigenvalue problem[END_REF] on spectral radius of sum of two symmetric matrices: For A, B symmetric,

ρ(A + B) ≤ ρ(A) + ρ(B). Thus 1 2 ρ(|I -QM c | + |I -QM c | T + |λ|(|Q| + |Q| T ) + |Q|M ∆ + M T ∆ |Q| T ) ≤ 1 2 |λ| ρ |Q| + |Q| T + 1 2 ρ |I -QM c | + |I -QM c | T + |Q|M ∆ + M T ∆ |Q| T .
Now, the sufficient condition states as follows

≤ 1 2 |λ| ρ |Q| + |Q| T + 1 2 ρ |I -QM c | + |I -QM c | T + |Q|M ∆ + M T ∆ |Q| T < 1.
By eliminating |λ| we get the final form [START_REF]CLAPACK -Linear Algebra PACKage written for C[END_REF]. Note that the denominator is zero iff Q = 0.

Note that M ∆ = A ∆ and M c = A cλ 0 I, so one can simply rewrite (1) by means of A and λ 0 .

By putting

Q := M -1 c
we have the most convenient and simple form of the formula (1) as stated below. Note however that using floating point arithmetics may affect validity of these conditions. Thus, from the numerical stability point of view, it is recommended to use the original form with Q being an approximate inverse of M c .

Corollary 1. Let λ 0 ∈ Λ(A) and define M := A -λ 0 I. Then (λ 0 + λ) ∈ Λ(A) for all real λ satisfying |λ| < 1 -1 2 ρ |M -1 c |M ∆ + M T ∆ |M -1 c | T 1 2 ρ |M -1 c | + |M -1 c | T . ( 2
)
Another simple consequence is obtained for the case of a symmetric interval matrix and its unsymmetric counterpart. Indeed, for A and A S the results are the same as long as A ∆ and A c are symmetric.

Corollary 2. Let λ 0 ∈ Λ(A S ) and define M S := A S -λ 0 I. Then (λ 0 + λ) ∈ Λ(A S ) for all real λ satisfying |λ| < 1 -1 2 ρ (|I -QM c | + |I -M c Q| + |Q|M ∆ + M ∆ |Q|) 1 2 ρ(|Q|) , (3)
where Q ∈ R n×n , Q = 0, is an arbitrary symmetric matrix.

These results allow us to propose an efficient filtering method for reducing outer estimations of the eigenvalue set. The detailed algorithm is presented in the following section.

Algorithm

In this section we propose a filtering algorithm which is based on Theorem 1. Let an interval a = [a, a] be given. A filtering method is a method which iteratively cuts off some parts (margins) from a that do not include any eigenvalue. Finally, we obtain an interval b ⊆ a such that (a \ b) ∩ Λ(A) = ∅.

To avoid infinitely many iterations we limit the number by a constant T . To omit the steps that cut off very narrow pieces, we repeat the main loop while the reduction is significant; that is, we prune away at least εa ∆ part of the interval, where ε ∈ (0, 1) is given accuracy. The pseudo-code that follows presents our filtering method that "filter" the input intervals from above. Filtering from below is analogous.

The filtering method is quite straightforward. The input interval a could be any initial outer estimation of Λ(A), or we can split such an outer estimation into several pieces and call the filtering algorithm for all of them. The former approach does not detect gaps which are inside the non-convex set Λ(A), while the latter is able to identify them, provided some genericity condition for the splitting.

Algorithm 1 is also applicable for the symmetric eigenvalue problem, but the filtering of Λ(A S ) yields the same result, as in the generic case, Λ(A). The only advantage of the symmetric case is that we can filter directly outer approximations of the eigenvalue sets λ i (A S ), i = 1, . . . , n. These eigenvalue sets have no gaps inside, so it is the most convenient utilization of the filtering. However, the filtering is applicable only for non-overlapping parts; if they overlap, then we will cut off nothing. As we will see in Section 4, the filtering runs very fast, and the reduction is significant. However, it does not converge to the optimal boundaries in general, because it is based on the sufficient condition for interval matrix regularity.

Numerical results

Herein we present some examples and numerical results illustrating properties of the proposed filtering method. In all the examples, we call Algorithm 1 with the accuracy coefficient ε := 0.01 and the maximum number of iterations T := 100.

The results were carried on an Intel Pentium(R) 4, CPU 3.4 GHz, with 2GB RAM, and the program was written in C++. We use GLPK v.4.23 [START_REF] Makhorin | GLPK -GNU Linear Programming Kit[END_REF] for solving linear programming problems, CLAPACK v.3.1.1 for its linear algebraic routines, and PROFIL/BIAS v.2.0.4 [START_REF] Knüppel | PROFIL/BIAS -a C++ class library[END_REF] for interval arithmetic and basic operations. We have to notice, however, that routines of GLPK and CLAPACK [START_REF]CLAPACK -Linear Algebra PACKage written for C[END_REF] do not produce verified solutions, and for real-life problems preferably verified software or interval arithmetic should be used.

Example 1. Let us adopt an example by Hladík et al. [12]

A =            
. The Rohn's outer estimation [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF][START_REF] Rohn | Bounds on eigenvalues of interval matrices[END_REF] It was obtained by the algorithm of Hladík et al. [START_REF] Hladík | An algorithm for the real interval eigenvalue problem[END_REF]. We see that the filtered approximation is very tight. There is still one gap remaining which we cannot detect unless we divide the initial approximation into more sub-intervals.

Example 2. Consider the example given by Qiu et al. [START_REF] Qiu | Bounds of eigenvalues for structures with an interval description of uncertain-but-non-random parameters[END_REF] (see also [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF][START_REF] Yuan | An evolution strategy method for computing eigenvalue bounds of interval matrices[END_REF]):

A S =     [2975, 3025] [-2015, -1985] 0 0 [-2015, -1985] [4965, 5035] [-3020, -2980] 0 0 [-3020, -2980] [6955, 7045] [-4025, -3975] 0 0 [-4025, -3975] [8945, 9055]     S .

INRIA

To call the filtering method we need some initial outer approximation of the eigenvalue sets. We use the following one by [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF] ω Even though this approximation is quite tight, the filtering makes it more tighter. Calling Algorithm 1 we get in only ten iterations and the total number of iteration is 13. We can compare this outer approximation with the exact description [START_REF] Hladík | Bounds on eigenvalues and singular values of interval matrices[END_REF] λ Again, we see that the filtering method converges quickly to the tight solution.

ω f 1 (A S ) = [
Moreover, the results are not sensitive to the initial estimation chosen.

Example 3. To be fully convinced about the quality of the filtering method we carried out number of randomly generated examples. Components of the midpoint matrix A c are taken randomly with uniform distribution in [-20, 20]. Components of the radius matrix A ∆ are taken randomly with uniform distribution in [0, R], where R is a given positive real number. We applied our algorithm on the interval matrix M := A T A since such kinds of symmetric interval matrices often appear in practice. The filtering method was called for all the eigenvalue sets λ(M S ) = λ 1 (M S ), . . . , λ n (M S ) T .

The results are displayed in Table 1. Each row shows results of a series of 100 tests carried out for a given dimension n and the parameter R. We provide average cut off and its standard deviation, number of iterations (for all parts of an outer approximation together) and average running time. The cut off provides information about the filtering efficiency. It is measured by the ratio

1 - e T ω f ∆ (M S ) e T ω ∆ (M S )
,

where e = (1, . . . , 1) T denotes the vector of all ones, ω f (M S ) an initial outer approximation of λ(M S ), and ω f (M S ) the result of the filtering procedure. This quotient says how much we cut off from the whole outer approximations of the eigenvalue sets, but the real efficiency (how much we eliminate from the overestimation addition) is much better. The results show that the proposed filtering method is not only very fast, but also efficient and eliminates quite large parts of given outer approximation of eigenvalue sets. This is particularly true when the input intervals of A are narrow. If they are wide then the filtering method is not so successful, partially because some of the eigenvalue sets overlap.

Conclusion

We propose a filtering method for improving an outer approximation of the eigenvalue set of an interval matrix. Our method is applicable for both generic and symmetric matrices. Even though the proposed algorithm does not converge always to the optimal bounds, our numerical experiments show that in general they compute very fast, quite accurate results. The algorithm performs well even when the initial (input) outer approximation is not very tight, thus it is not sensitive with respect to the input estimation. A drawback of our approach is that it can not detect (possible) gaps inside the initial outer approximation. Such cases should be handled by splitting into smaller sub-intervals or using another kind of initial approximation. This is problem that further research is needed.

INRIA Algorithm 1 (

 1 Filtering a from above) 1: b := a; 2: t := 0; 3: λ := εb ∆ + 1; 4: while λ > εb ∆ and t < T do end while 16: return b.

  1 (A S ) = [12560.6296, 12720.2273], ω 2 (A S ) = [6990.7616, 7138.1800], ω 3 (A S ) = [3320.2863, 3459.4322], ω 4 (A S ) = [837.0637, 973.1993].

  1 (A S ) = [12560.8377, 12720.2273], λ 2 (A S ) = [7002.2828, 7126.8283], λ 3 (A S ) = [3337.0785, 3443.3127], λ 4 (A S ) = [842.9251, 967.1082],

INRIA

  of Λ(A) is[-22.1040, 35.4999]. Calling Algorithm 1 we obtain the following sequences of improvement: from above: 35.4999 → 28.0615 → 25.6193 → 24.7389 → 24.4086; from bellow: (-22.1040) → (-18.4018) → (-17.8239) → (-17.7346). So we need only seven iterations to achieve the much more tighter outer approximation [-17.7346, 24.4086]. Using Proposition 2 of [12] we have an outer approximation [-24.4860, 4.5216]∪ [12.1327, 29.3101]. We will filter both the intervals. In the former case we obtain from above: 4.5216 → 2.4758 → 0.8342 → (-0.0951) → (-0.5335) → (-0.7149); from bellow: (-24.4860) → (-18.8351) → (-17.8926) → (-17.7438); and in the latter one from above: 29.3101 → 26.0645 → 24.9010 → 24.4704 → 24.3053 → 24.2412; from bellow: 12.1327 → 13.4809 → 14.4703 → 15.1443 → 15.5761 → 15.8462 → 16.0127 → 16.1143 → 16.1760. Thus, we have in 21 iterations the filtered outer approximation [-17.7438, -0.7149]∪ [16.1760, 24.2412]. We can compare this result with the exact solution Λ(A) = [-17.5116, -13.7578] ∪ [-6.7033, -1.4582] ∪ [16.7804, 23.6143].

  What if we start with another initial outer approximation? We use that produced by of the method of Leng & He[START_REF] Leng | Computing eigenvalue bounds of structures with uncertain-but-non-random parameters by a method based on perturbation theory[END_REF] ω 1 (A S ) = [12550.53, 12730.53], ω 2 (A S ) = [6974.459, 7154.459], ω 3 (A S ) = [3299.848, 3479.848], ω 4 (A S ) = [815.1615, 995.1615].

	12560.8129, 12720.2273], ω f 2 (A S ) = [6999.7862, 7129.2716],
	ω f 3 (A S ) = [3332.7164, 3447.4625], ω f 4 (A S ) = [841.5328, 968.5845].
	Although this estimation is not so tight we obtain tighter result
	ω f 1 (A S ) = [12560.8129, 12720.2472], ω f 2 (A S ) = [6999.8026, 7129.2716],
	ω f 3 (A S ) = [3332.7944, 3447.4628], ω f 4 (A S ) = [841.5328, 968.5505],

Table 1 :

 1 Filtering procedure for outer estimates of eigenvalue sets of random interval symmetric matrices A T A.

	n	R	cut off quotient	iterations	time
			average	std. deviation
	5 0.001 0.186185	0.034635	15.25	0.0012 s
	5 0.01	0.182395	0.042879	16.23	0.0010 s
	5 0.1	0.142715	0.041260	16.51	0.0011 s
	5 1	0.015686	0.011977	3.99	0.0004 s
	10 0.001 0.233480	0.022064	33.41	0.0062 s
	10 0.01	0.207711	0.032813	37.63	0.0068 s
	10 0.1	0.074682	0.024832	22.13	0.0031 s
	10 1	0.003388	0.002995	1.42	0.0005 s
	15 0.001 0.242457	0.021210	54.13	0.0239 s
	15 0.01	0.181559	0.022123	56.44	0.0250 s
	15 0.1	0.025517	0.010055	13.48	0.0082 s
	15 1	0.001410	0.001704	0.94	0.0011 s
	20 0.001 0.243601	0.017704	76.69	0.0650 s
	20 0.01	0.154207	0.021279	67.92	0.0595 s
	20 0.1	0.009844	0.006030	7.42	0.0114 s
	20 1	0.000493	0.000890	0.60	0.0012 s
	25 0.001 0.238694	0.016706	97.15	0.1373 s
	25 0.01	0.122852	0.017385	73.67	0.1122 s
	25 0.1	0.004785	0.003815	3.84	0.0123 s
	25 1	0.000117	0.000369	0.33	0.0033 s
	30 0.001 0.232266	0.015133	117.90	0.2679 s
	30 0.01	0.093589	0.015072	74.07	0.1812 s
	30 0.1	0.002288	0.001849	2.78	0.0121 s
	30 1	0.000031	0.000150	0.09	0.0036 s
	50 0.001 0.194401	0.011126	184.75	1.5238 s
	50 0.01	0.028148	0.006065	48.19	0.5169 s
	50 0.1	0.000428	0.000545	1.05	0.0225 s
	50 1	0.000000	0.000000	0.00	0.0166 s

RR n 7057


Jean Le Feuvre

SVG Extensions for 3D displays Enabling SVG on auto-stereosciopic displays

His research focuses on multimedia systems architecture, including authoring, transport and rendering. He is the project leader of the GPAC open-source project, a framework offering various tools for delivery and playback of multimedia content, including W3C SVG and MPEG-4 BIFS.

Bibliography

Introduction

3D displays, allowing natural perception of depth by the viewer, are increasingly gaining acceptance, on mobile as well as on digital TV markets. 3D display technologies rely on stereopsis, the ability for the brain to reconstruct depth information from different views of an object on the two retinas. This effect enhances the depth perception given by other cues such as perspective (further objects look smaller) or motion parallax (further objects seem to move slower). In these displays, each view is redirected to the target eye through an optical system, such as lenticular or polarized sheets on top of the screen, or mechanical system such as liquid crystal shutter glasses ref1. While most displays are stereoscopic only systems (e.g., only two different views are presented), some systems, called auto-stereoscopic, may present several views of the content, providing horizontal parallax to the viewer, which allows looking around the objects on the screen. Both types of displays enable placing objects in front or behind the screen plane. The range of the perceived depth position of objects depends on the display physical characteristics: while quite large in 3D movie theater system, this effect is reduced with TV displays, even more with mobile displays. We refer to this volume as the "stereoscopic box".

Extensive research has been done in 3D video compression, and several approaches exist to represent 3D video data ref2:

Stereo pair for each frame, Texture and depth information for each frame, A combination of the above.

The depth information, or depth map, gives the position of each pixel of the video on the z-axis. Depth information simplifies the process of generating views from different angles, for example when using auto-stereoscopic displays or when moving the 3D video further or closer from the viewer. The generation of different images based on depth and color information is called DIBR ref3 for depth-image-based rendering.

Most synthetic 3D representation languages, such as Collada or X3D, are already suitable candidates for usage with 3D displays, as they already carry depth information. This is however not the case with standard 2D multimedia used all over the web, especially (X)HTML or SVG: these language are depth agnostic and do not allow authors to use the stereoscopic nature of the screen.

In order to allow for conception of efficient and attractive 2D multimedia content for (auto-)stereoscopic displays, an author may want the multimedia language to be able to: display 3D video and 3D still images, display synthetic objects such as UI items or text labels at any depth, dynamically modify the depth range of 3D video and images as well as synthetic 2D graphics for visual effects, generate synthetic objects with arbitrary, non-uniform depth information.

In this paper, we present a complete multimedia system handling stereo and auto-stereoscopic displays. The system is designed with low-end CE devices in mind, with a focus on 2D graphics and associated visual effects on stereoscopic displays. It furthermore integrates rendering of 3D data through software or a dedicated GPU. Our approach is to re-use as much as possible existing technologies, without breaking the rendering or animation model of the underlying languages considered. Moreover, the porposed solution will have to be independent from the display type (stereoscopic or auto-stereoscopic).

The rest of this paper is organized as follows. Section 2 presents the architecture of the system. Section 3 details our contribution on depth effects in SVG content. Section 4 gives some notes on the implementation. We conclude this paper and present future work in Section 5.

System Architecture

Our system, described in Figure Figure 1, "Figure 1. Systems Architecture", is divided in two core components: a software multimedia player and hardware DIBR renderer. test caption.

Hardware Renderer

The BIBR hardware renderer is in charge of generating the different views from the different objects present in the multimedia scene. The choice for a DIBR hardware renderer was justified by its ability to handle stereoscopic as well as auto-stereoscopic displays easily, with a fixed computational cost independent from the number of views to generate. The hardware architecture derives from ref4.

The hardware manipulates texture objects decoded or generated by the software module. The texture color data can be in RGB or YUV formats. Each object can have its own depth or alpha 8-bit plane. It must be noted that the system does not currently allow for both depth and alpha planes at the same time, but instead may use a depth plane where the higher bit of each component acts as a shape mask. Each object has depth offset and depth gain coefficients, allowing redrawing of the 3D scene without modifying the textures and depth maps.

The hardware is also in charge of interleaving the pixels on the display e.g., placing (sub)-pixel of each view at the correct location depending on the optical system).

Multimedia Player

The multimedia player used is GPAC ref5. It can handle various multimedia languages such as SVG, VRML or BIFS, as well as video formats such as MPEG-4 SP or AVC/H264 and still images such as JPEG and PNG. Multimedia data can be read from various sources such as RTP, MPEG-2 TS and MP4/3GP files, commonly used in Digital TV and Mobile worlds.

The software is in charge of decoding video, images and multimedia scenes. The compositor task can be decomposed as follows:

Compute spatial 2D and depth positioning of objects, If needed, generate synthetic graphics and depth maps, Send the objects to the DIBR hardware, Execute timers and user interactions.

Currently, the prototype hardware does not handle hardware accelerated vector graphics such as OpenVG, therefore the rasterization process is performed in software on off-screen surfaces which are then passed to the hardware. The rendering engine supports several declarative formats for interactive services(W3C SVG, MPEG-4 BIFS), which have all been extended to allow for depth information.

Although our prototype also supports 3D languages such as X3D, in the rest of this paper we will focus on the SVG language, especially the SVG 1.2 Tiny profile since our prototype is more oriented towards embedded systems.

Depth Effects

Objects in a typical depth-aware 2D interactive service can be separated in two categories:

Objects with a constant depth where all pixels are at the same distance from the viewer. We refer to these objects as "flat objects" Objects with non-uniform depth, such as video, images or complex ynthetic graphics. We refer to these objects as "3D objects"

Depth Offset

The first depth effect to use on 2D content is the ability to position an object such as a menu item or a sprite in a game, at any depth. All pixels of this object will then share the same depth. This enables pushing 2D objects in front of the screen or behind the screen. This effect can also be used to adjust the depth of a set of objects with different depth offsets. This allows depth translation of some parts of the content, which is very useful in transitions and animations.

For the SVG case, we defined a new attribute "depth-offset" for that purpose. Although there is no restriction for the target element supporting this attribute, we restricted ourselves to the <g> element for implementation purposes.

Depth Scaling

Another useful depth effect is the ability to scale the depth values of an object. This is especially needed for objects with depth maps, as it allows stretching and shrinking effects on 3D objects without having to modify their associated depth map. It can be particularly useful when UI elements get or loose focus, or combined with a color revealing/fading transition.For that purpose, we defined a new attribute "depth-scale", which is applied to the <g> element.

Following SVG transformation hierarchy design, "depth-offset" and "depth-scale" attributes of a <g> element are applied to its descendent. Nested <g> elements with depth properties can be used.

Depth Calibration

The depth values in our architecture are by default in the range -1.0, which is the farthest point viewable on the display z axis, to 1.0, which is the nearest point. Such a range may not always be convenient for an author; especially, being able to work with depth units closer to pixel units might be desired. We added a depth calibration attribute to the <svg> element, "depth-viewbox"; allowing an author to specify the minimal and maximum depth value used in the content. As with "viewBox" attribute, this attribute can be modified (scripting, <animate> element).

The following example shows the compination of the different depth rendering attributes introduced. The result is a rectangle floating in front of the screen and a text in front of the rectangle. The "depth-scale" attribute of the 'button1' <g> element can typically be animated on mouse or focus in/out. <?xml version="1.0" ?> <svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:ev="http://www.w3.org/2001/xml-events" width="160" height="160" depth-viewbox="-100 100"> <title>Depth UI item</title> <desc>Shows usage of depth extension tools.</desc> <g id="button1" transform="translate(20,20)" depth-offset="30" depth-scale="0.5"> <rect width="100" height="30" fill="blue"/> <g depth-offset="30"> <text x="20" y="20">Click!</text> </g> </g> </svg>

Depth Maps

Objects with non-uniform depth are either bitmap-based objects coming from <video> or <image> elements, or synthetic graphics. In order to generate synthetic graphics with depth information, we defined a new SVG filter called "feDepthComponent". This filter uses the RGBA source image and produces an RGBA+depth image to be used with the renderer. The depth image used is specified using a <feImage> as a secondary RGBA source, and one component of the secondary source is then transfered to the depth component of the filter result, using either <feFuncA>, <feFuncR>, <feFuncG>, <feFuncB>. This technique enables computing complex synthetic depth maps uncorrelated with the color information.

<?xml version="1.0" ?> <svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:ev="http://www.w3.org/2001/xml-events" width="160" height="160"> <title>Depth Image</title> <desc>Producing a depth image with feDepthComponent</desc> <defs> <radialGradient xml:id="MyGradient" r="0.1"> <stop offset="0" stop-color="blue"/> <stop offset="1" stop-color="red"/> </radialGradient> <rect xml:id="depthRect" fill="url(#MyGradient)" width="100" height="30"/> <filter xml:id="depthFilter"> <feImage xlink:href="url(#depthRect)" result="depth"/> <feDepthComponent in="SourceGraphic" in2="depth"> <feFuncR type="linear" slope="-1" intercept="1"/> </feDepthComponent> </filter> </defs> <g filter="url(#depthFilter)" transform="translate(20,20)"> <rect width="100" height="30" fill="blue"/> <text x="20" y="20">Click!</text> </g> </svg> This code shows an example of the proposed feDepthComponent filter wich uses a red and blue gradient and composes the depth map from the red component of the gradient. Such a gradient could be used to simulate waving of a surface. The gradient looks like this and the resulting depth map looks like this:

Since the proposed filter work in color coordinates, the depth calibration introduced previously is ignored for depth map and the components are automatically mapped to the interval [0, 1.0] where 0 is the far plane of the stereoscopic box and 1 the near plane.

Depth filter values are however affected by "depth-scale" and "depth-offset" attributes, which are remaped by the implementation to [0 1] range according to the "depth-viewbox" attribute.

Note that the <feDepthComponent> can also be used to add depth information to raster image or video, or replace existing depth information.

Experimental Results

In order to display 3D still images, we had to define new formats for images: PNGD: PNG where alpha channel acts as depth channel PNGDS: PNG where alpha channel acts as depth channel with the high-order bit acting as a shape mask

We have also demonstrated playback of video sequences according to the MPEG-C standard, with dedicated video and depth streams both coded in MPEG-4 Simple Profile. All the effects proposed have been successfully tested. We have even demonstrated a combination of 3D models (using X3D language) with 2D user interface using SVG depth effect and <foreignObject> element.

One problematic we faced during this work was the respect of the SVG rendering model. Using depth effects will indeed change the rendering order of objects, which is no longer compatible with SVG. The impact on the SVG viewing model have been discussed in the elaboration of the SVG Transform specification. Several approaches are possible: let the author organise the elements as needed, strictly following the painter's algorithm.

let the player organise the elements as needed, with a z-sorting of all elements present in the composition allow a mix of both cases, where only subparts of the composition are z-sorted.

Our first implementation only supported the first case, and the author is responsible for avoiding overlaps of object. This also reflects our hardware architecture which doesn't perform depth sorting of the various objects.

We are currently working on the mixed use-case to hide this complexity from the author. While this is clearly not problematic for flat objects or non-overlapping objects, the problem is more complex when mixing objects with at least one non-uniform depth map, since they can overlap one another along the depth axis and can no longer be sorted according to their depth.

Conclusion

In this paper, we have identified the lack of support for 3D displays in most 2D UI and rich-media standards. This situation is problematic as more and more 3D displays (steroscopic or auto-stereoscopic) are deing commercially deployed by the home entertainment industry. We have defined the minimal depth effects that multimedia authors would need to adress these displays. We have presented an SVG multimedia player running on such displays, and proposed extensions to the language supporting the proposed effects. We have shown intergation of simple UI effects and more complex depth-map based 3D effects, and shown the problematic of using objects with complex depth-map in the SVG rendering model. In future work, we will further investigate this problematic and extend our work to support SVG Transform. We will also conduct user trials to evaluate the visual quality of the proposed effects.

Bibliography

Figure 1 .

 1 Figure 1. Figure 1. Systems Architecture

14/10/11 14:55


Jean Le Feuvre
email: jean.lefeuvre@telecom-paristech.fr

Cyril Concolato
email: cyril.concolato@telecom-paristech.fr

Hybrid Broadcast Services using MPEG DASH

Keywords: Hybrid, broadcast, broadband, adaptive streaming, Future TV

The emergence of new multimedia services such as super high definition or free viewpoint TV will put a very large bandwidth pressure on the broadcast networks. In order to offer these services while maintaining quality, service provider will have to use other delivery mechanisms. In this context, enhancing broadcast services with broadband media may be one key to low cost deployment of new services. This paper studies the problem of hybrid broadcast and broadband delivery of audio-visual content and reviews existing solutions. With the growing importance of HTTP streaming services, and the adoption of MPEG-DASH by the TV industry, a solution for hybrid broadcasting based on this standard is proposed. Implementation is presented and evaluated, and future work directions are discussed.

INTRODUCTION

With the emergence of new multimedia technologies such as ultra-HD (UHD) or 3D displays, the TV broadcasting industry is facing new challenges regarding the optimization of the broadcast network, be it satellite or terrestrial. Moreover, user demand for richer services, such as free viewpoint selection or high definition audio enhancement (language selection, multichannel streams), also impacts the network occupancy. Although new broadcasting standards such as DVB-S2 [START_REF] Morello | DVB-S2: The second generation standard for satellite broadband services[END_REF] or DVB-T2 [START_REF] Vangelista | Key technologies for next-generation terrestrial digital television standard DVB-T2[END_REF] offer more bandwidth, and the new HEVC [START_REF] Sullivan | Recent developments in standardization of high efficiency video coding (HEVC)[END_REF] video compression standard allows for higher compression ratios, long is the road until broadcaster may offer full UHD 3D services to their customers. Another interesting aspect lies in the non-uniformity of the end-user equipment. 3DTV are not widespread; UHD displays are at the experimental stage and will not hit the mass consumer market any time soon. Moreover, not all users equipped with 3D TVs are willing to pay for 3D broadcast services, limiting their 3D experience to home video. Considering all these issues, one might easily understand the reluctance of TV broadcasters to waste precious broadcast bandwidth only to address a very small subset of their users. Nevertheless, if this subset is willing to pay for such services, a solution should be found to help for the deployment of new services. With the growing adoption of connected TVs or set-top boxes, it is worth investigating whether enhancement to broadcast services could be delivered through a broadband link; this would allow broadcasters to address their complete user base through their broadcast network, thereby minimizing their broadcast costs, while offering premium services of various kinds to specific users; we can cite many use cases:

• Switching a SD/HD service into a HD/UHD using SVC or the upcoming HEVC Scalable standard; • Switching a 2D service into a 3D one using MVC or service-compatible AVC enhancement stream; • Switching views in a live sport event; • Switching audio to any possible language or high definition version. The common point between these scenarios is the ability to synchronize the broadband and broadcast streams in a very fine way, requiring frame-accurate synchronization for 3D or spatial enhancements, or even at the audio sample level if using a multistream audio representation. Delivering a multimedia content over both broadcast and broadband is usually referred to as "hybrid broadcasting", and the synchronization process needed is referred to as "hybrid synchronization". The work presented in this paper is a follow-up of previous work [START_REF] Concolato | Synchronized delivery of multimedia content over uncoordinated broadcast broadband networks[END_REF], and presents a solution for such hybrid use cases based on the new MPEG DASH standard. This paper is organized as follows; in Section 2, we will review the specificities of hybrid broadcasting and the problems induced by the broadcast environment; in Section 3, existing approaches to solve these issues are explained; in Section 4, a quick overview of MPEG DASH in the context of hybrid networking is presented; our solution is explained in section 5; Section 6 discusses the experiments and Section 7 concludes this paper and presents future work directions.

HYBRID BROADCASTING

As shown in [START_REF] Concolato | Synchronized delivery of multimedia content over uncoordinated broadcast broadband networks[END_REF], hybrid broadcasting raises two interesting questions: the bootstrapping resolution, or how a client discovers that media distributed over different deliveries can be consumed together; and the synchronization of these media.

Discovery of Hybrid Enhancement

There are two general situations for the discovery of hybrid content: program guide indications or inband indications. In the first case, add-on enhancements are available through broadband information, such as an electronic program guide or any proprietary mechanism in the DTV receiver, in order to describe which broadcast channel may be enhanced. In the second case, signalling is included in the broadcast stream, for example through an HbbTV [START_REF]Hybrid Broadcast Broadband TV[END_REF] application, to provide the description of the broadband media. In order not to rely on service guide or third-party servers, we based our solution on inserting the enhancement description in the broadcast content in the form of an URL to minimize bandwidth occupancy.

Media Synchronization

Multimedia synchronization is a fairly simple process that can be described as follows: media frames (video, audio, subtitles, …) are compressed and assigned a timestamp, indicating the time at which the unit has to be presented on the display or at the output of the speakers. These timestamps refer to a timeline, which is usually not the intrinsic media timeline (e.g. time 0 for the first frame of a movie), but rather expressed with a random origin and frequency. Some standards such as RTP use one timeline per media, and indicate the relationship between timelines through a specific mechanism (RTCP reports for the RTP case). In the broadcast world, MPEG-2 TS is used as the media unit delivery mechanism, and its timing mechanism can be described as follows:

• All media streams of a program (TV channel) refer to the same timeline; • This timeline is described by the Program Clock Reference, and is computed through PCR timestamps inserted in the transport stream, usually carried by the video stream; • Time origin of the PCR is meaningless; • PCR may suffer discontinuities at any time.

The main issue with MPEG-2 TS in hybrid scenarios comes from this last property; most of the deployed equipment (statistical multiplexer, transcoders, splitters…) will rewrite PCR and timestamps throughout the chain, without the content provider being aware of this transformation. In order to achieve hybrid synchronization at the frame level as previously explained, one would need to adjust the timestamp in the broadband stream to align them with the PCR. This requires realtime feedback from the equipment, for each discontinuity happening on the PCR. These modifications would then require a rewriting of the broadband content, making offline production or content distribution optimizations almost impossible. If several devices may modify the PCR in the broadcast chain, as is usually the case, such a solution is simply impractical. Hybrid broadcasting also requires handling of broadband network jitter and downlink transmission time [START_REF] Concolato | Synchronized delivery of multimedia content over uncoordinated broadcast broadband networks[END_REF] [6][9]. This is not in the scope of this paper, since we assume that the broadband enhancement is available ahead of time; our experiments were only conducted on preproduced content. This implies that the client can fetch broadband data starting from some point ahead in time, typically several times the downlink transmission time.

RELATED WORK

Several approaches exist towards synchronization of broadcast and broadband content. This section reviews a few of them.

Timeline Estimation Techniques

Multiple solutions have been found to try to overcome the existing lack of synchronization support when designing add-ons to TV, without modifying existing broadcast streams. One solution is fingerprinting [START_REF] Haitsma | Robust Audio Hashing for Content Identification Robust Audio Hash Definition[END_REF] [START_REF] Howson | Second screen TV synchronization[END_REF]. Fingerprinting means extracting relevant parameters (the fingerprint) from an audio stream, captured by the microphone of a smartphone or tablet standing in front of an active TV set. The fingerprint is sent to a server, where it is compared with the fingerprints of all TV channels. The fingerprint match allows for: • Identification of the channel the TV set is tuned into • Timing information recovery, which depends on the fingerprinting parameters but can reach a precision of 10ms [START_REF] Haitsma | Robust Audio Hashing for Content Identification Robust Audio Hash Definition[END_REF]. Fingerprinting works well to get a single timing indication, and to some extend may be used to provide near lip-sync support. However, it is not precise enough to cover frame-accurate precision, needed in hybrid delivery of hierarchically coded scalable streams, for which one frame delay between streams will lead to decoding errors. It is also sensitive to ambient noise, and server load may delay responses beyond usability with a growing number of users.

Best Effort Timeline Techniques

Another approach consists in using existing timing information from the broadcast content. As explained previously, using the PCR values is not possible due to clock discontinuities. [START_REF] Concolato | Synchronized delivery of multimedia content over uncoordinated broadcast broadband networks[END_REF] shows that it is possible to use UTC timing conveyed in DVB networks through the TDT table. This information is sufficient for some use cases, such as triggering recordings or overlaying some applicative data (stock exchange, interactive quiz…) with loose synchronization requirements. However, existing equipment do not maintain a strict synchronization between the multiplex time (therefore the PCR) and the TDT; drift can be as high as couple of seconds in existing DVB-T networks, as shown in Figure 1. This implies that frame-accurate synchronization cannot be achieved this way without impacting most of the broadcast chain. Moreover, this solution would require very fine synchronization between the broadcast chain and the broadband provider to avoid drift in their respective UTC clock. Finally, using a UTC based timeline makes synchronization more complex, since broadband servers have to signal how to map the broadcast UTC time to the timeline of pre-produced broadband content.

Timeline Data Streaming

Another approach to solve the synchronization issue is to send another timeline in the MPEG-2 TS, along with the PCR. Such a timeline is not modified by PCR discontinuities and can therefore be used as a synchronization reference by the broadband content. This approach is standardized in [START_REF]carriage of synchronized auxiliary data in DVB transport streams[END_REF], and covers many use cases including recomposing of a movie timeline after removal of ads. The design principle is simple: the timeline is sent as a PES stream, and the payload of the PES packet contains the timeline value corresponding to the PTS value coded in the PES header. This ensures that all media (audio, video) timestamps can be transposed in this additional timeline regardless of PCR discontinuities. Since this timeline is inserted by the content producer and is not altered by the broadcasting chain, broadband content can be synchronized in the most accurate way desired (frame accuracy, audio sample accuracy) by selecting a proper resolution for this timeline. This work has been demonstrated in [START_REF] Howson | Second screen TV synchronization[END_REF]. While this approach fits our needs, it still lacks tools to identify the location of the broadband data, as well as accurate description of the current TV show. Our solution is based on this design principle, but proposes MPEG-DASH compatible tools to enable hybrid broadcasting.

A DASH APPROACH

The DASH-oriented design of our solution was driven by two arguments:  DASH is designed for delivery and synchronization of multiple media streams over various path, and has all the tools required to synchronize streams coming from different broadband servers;  DASH is getting a growing adoption by TV standards such as HbbTV [START_REF] Hbbtv | Hybrid Broadcast Broadband TV[END_REF], and it should not be long until TVs are DASH-enabled.

While the standard is designed for HTTP based delivery, it is being adopted in other contexts such as mobile broadcasting (eMBMS), thanks to its expressivity.

Especially, DASH has done a fairly complete review of how hierarchically coded streams and alternate streams can be described in an efficient way, covering both scalable coding, multiview coding and service-compatible 3D coding. Another interesting feature of DASH is its ability to handle streams coming from different origins, possibly in different formats, and therefore not using the same timeline to express their timestamps. DASH provides tools to map timelines of each media to a global time, even if these timelines do not share the same time origin. The presentation time of each media depends on the underlying media format, MPEG-2 TS or MP4. For MPEG-2 TS case, the presentation time info is usually conveyed through segment indexes, which are not present in the TS. When not present, clients rely on PCR information and period start time, which is problematic in our scenario as explained in Section 2. By overriding the notion of presentation time in live broadcast with the approach given in the previous section, we can provide a continuous TS timeline which can be mapped to other media described in the DASH session, regardless of PCR re-stamping or discontinuities happening in the network.

DASH HYBRID BROADCASTING

Our solution consists in delivering DASH MPD location inside the broadcast stream for each program carry the PresentationTime of the program as well as the period information in a dedicated PID. An overview of the architecture of this hybrid system is given in Figure 2. In a first design, the DASH information was embedded in an MPEG-2 TS section, such as PMT or AIT. However, this impacts existing multiplexers, as they have to maintain tight synchronization between PES data and PMT/AIT, especially when sudden period switch happen. We therefore decide to embed the DASH description within the PES stream carrying the timeline information to limit the impact on the infrastructure and provide more robustness in case of DASH period switching. The link between the MPD media streams and the MPEG-2 TS depends on the nature of the enhancement. For non-scalable media enhancement, no explicit link given, and media composition is decided by the digital TV terminal. For scalable media enhancement (spatial, 3D), the dependencyId attribute of the enhancement layers described in the MPD are set to point to the base layer in the MPEG-2 TS, through a custom URL scheme pid://PID. The solution has therefore no impact on the XML validation of the MPD and does not modify the URL resolver algorithm of the DASH client. We also defined a new stream type for our DASH timeline stream, called DASHTime, and defined its payload as shown in Table 1. This fixed payload is designed to fit in a TS packet, including PES header and optional adaptation fields of the TS packet. It carries the presentation time of all streams in the program, by associating this value with the PTS value given in the PES header of the packet. The DASH packet may be sent at any time, but our implementation only sends them at the beginning of each frame or after every packet containing a PCR. The packet also indicates the location of the DASH MPD as well as the current period id in order to properly handle period changes. Finally, the packet includes an activation countdown announcing that the given URL will not be valid until the indicated time, allowing a client to prefetch media data before the actual period switch occurs. Once the broadcasted content can be identified in the MPD, the client can process the MPD as usual, following DASH rules for representation selection and MPD updates, and a regular DASH session can, then take place for broadband media, as shown in Figure 2.

Our solution provides a generic mechanism allowing broadband add-ons to be synchronized with MPEG-2 TS broadcast, regardless of the add-on type; MPEG DASH is of course a main use case for our solution, but other enhancements such as plain files, RTP streams or MMT content could be synchronized with this proposal.

EXPERIMENTS

We have experimented with this design using multicast TS as a broadcast simulator and an HTTP server, using [START_REF] Le Feuvre | GPAC: open source multimedia framework[END_REF] as the underlying platform for content generation (DASH and TS) and playback. Our experiment shows that the timeline reconstruction works perfectly and gives us a frame accurate playback. However, we only experienced with non-live broadband content, and the player always had the ability to fetch broadband data ahead of time, typically one second. This increases the hybrid setup delay, but ensures that broadband data to add was already available for decoding before broadcast data arrived. As in most broadcast use cases, we did not want to consider the pausing of the broadcast stream to cope with initial buffering. Future work will investigate the possibilities to perform this experiment in live conditions, with the smaller production delay possible. Another limitation of our system is the live-only design; we still have to investigate how performing trick-modes on recorded or time-shifted broadcast could be enhanced with the tools that DASH provides.

CONCLUSION

In this paper, we have presented some use cases for hybrid broadcasting, reviewed the different approaches towards solving these scenarios and explained how the MPEG-DASH standard provides most of the tools needed to fulfil them. We have proposed a light solution compatible with existing infrastructure ensuring a frameaccurate synchronization between broadcast and broadband stream. This work is under investigation for standardization by the MPEG committee, with a work plan targeting both explicit technical tools for the MPEG-2 transport stream and generic transport guidelines for achieving multi-container synchronization. In future work, we will investigate usage of DASH trick modes for broadcasted content as well as low delay live hybrid broadcasting.

Figure 1 :

 1 Figure 1: TDT/PCR drift in DVB-T multiplex

Figure 2 :

 2 Figure 2: Proposed DASH-based hybrid broadcasting architecture

Table 1 : DASHTime PES payload format

 1

	DASHTime_PES_Payload {
	bit(64) presentation_time;
	bit(64) activation_countdown;
	byte mimeType;
	byte URL_location;
	}

Acknowledgment

This work was partially funded by the European Commission in the course of the CELTIC project H2B2VS and by the French Research Agency in the course of the OptiSaT2 project.


Alexander I Sukhinov

Elena V Alexeenko

Alexander E Chistyakov

Bernard Roux

Dominique Fougère

Paul G Chen

Samuel Meulé

D Fougere

Turbulent mixing in shallow water basin ; parameterization of vertical turbulent exchange coefficient

Keywords:

come

Introduction

Turbulence is an important mechanism in the mixing of heat, salt, momentum and suspended and dissolved matter in the coastal zone. Turbulent fluxes of material occur as a result of correlated, small-scale fluctuations in current velocity and the transported quantity itself. In the coastal zone, mean shear is typically generated by winds and/or tides, but also by surface waves and baroclinic flows. In deep water, the friction has a smaller effect on the tides, as compared with the deflection force of rotation of the Earth, while for shallow water the bottom friction is important and has to be accounting for. Here, we are mainly interested by shallow water basins which can be roughly characterized by the condition [START_REF] Chapalain | Observed and modeled resonantly interacting progressive water-waves[END_REF]: kh 1 < (2πh<1), where kwave number of the wave, h -height of the water column, λ -wave length.

There exist three main layers in the vertical structure of water column: bottom boundary layer (BBL), surface boundary layer (SBL) and intermediate current zone. Bottom boundary layer (BBL) spans the vertical distance between the no-slip bottom boundary condition and outer, free stream motion. The height of the boundary layer is related to the magnitude of the free-stream velocity, bottom roughness and the time available for boundary layer development. Surface boundary layer (SBL) is a part of the sea that directly exposed to the atmosphere, through which atmospheric properties are transmitted into the water interior. Near-surface turbulence creates a mixed layer immediately below the surface, in which quantities such as temperature and dissolved and particulate material are relatively uniform in the vertical. Between surface and bottom boundary layers an intermediate current zone is situated. In the deep water all layers are separated, each one has different properties and different turbulent parametrizations [START_REF] Burchard | Observational and numerical modelling methods for quantifying coastal ocean turbulence mixing[END_REF].

In shallow water, the influence of surface waves may penetrate right to the bed and create a wave bottom boundary layer that can interact with the mean tidal (pressure-gradient-driven [START_REF] Burchard | Observational and numerical modelling methods for quantifying coastal ocean turbulence mixing[END_REF]. That is why we can't separate for every layer turbulent approximation, and have only one universal approach for determining effects of vertical turbulent exchange for all parts of water column.

Because of their statistical character, turbulent fluxes are difficult to be measured, and must usually be quantified by indirect strategies. Numerical models usually incorporate parameterizations for quantifying turbulent fluxes. The validity of these parameterizations is checked by their ability to reproduce certain observable turbulent behavior.

In modern numerical models, the coefficient of vertical turbulent exchange is often mentioned as a fitting parameter, a choice, which can be achieved fairly good agreement of the observations and numerical modelling. But its value is often chosen for reasons of computational stability of the account for long periods, and may, at the orders surpass him physically reasonable estimates for the real sea. There are various strategies for modeling turbulence, each of them resolving a different interval of the type of the flow dynamics: 1) Direct numerical simulation (DNS); 2) Large eddy simulation (LES); 3) Statistical turbulence modeling and 4) Empirical turbulence modeling [START_REF] Burchard | Observational and numerical modelling methods for quantifying coastal ocean turbulence mixing[END_REF][START_REF] David | Turbulence Modeling for CFD[END_REF]. Each one strategy has a good application for exact problem. We concentrated on the problem of parameterization of vertical exchange in shallow water reservoirs, where chaotic fluctuations of velocities in vertical direction are significant and define all hydrodynamic processes in the sea. Subgrid scale techniques (analog of LES) are designed for simulating the impact of turbulence and small-scale mixing on the larger scales with reasonable computer effort. These methods are based on the definition of turbulent flow as averaged in space or time (correlation) of products of deviations of flow velocity and portability of a physical quantity. For subgrid methods of assessment of characteristics of vertical turbulence, there is a problem which is associated with the need for large amounts of data in long and expensive in situ measurements.

The main difficulty is thus to determine an approach which will give us agreement between results of model simulations and experimental data measured in situ. The present work consists of two parts: (1) experimental part: the calculation of turbulence parameters using expedition data by different approaches and the choice of the approach which shall give more realistic results according to physics of the process; (2) simulation part: the computation of currents with the chosen approach to be included in the hydrodynamic model developed in TIT-Russia, and also the comparison of results with MARS3D developed by Ifremer. The computations of turbulence coefficients were performed in two shallow water basins: Etang de Berre, Etang de Bolmon.

Two approaches of parameterization of vertical turbulent exchange coefficient

Several subgrid scales and statistical approaches were used for calculation of the coefficient of vertical turbulent exchange in the water column, ) (z ν , in two adjacent shallow water basins: Etang de Berre and Etang de Bolmon. In this work we shall consider two approaches to determine ) (z ν :

1. The Monin [START_REF] Monin | Turbulence and a microstructure at ocean[END_REF] approach:

2 2 ) ( ) ( ) ( z z z yz xz ν ν ν + =
, where

z z U w u z xz ∂ ∂ ′ ′ - = ) ( ) ( ν and z z V w v z yz ∂ ∂ ′ ′ - = ) ( ) ( ν ) (z ν
-coefficient of turbulent exchange for the fixed point in the plane (x,y).

w v u ′ ′ ′ , ,
-velocity fluctuations, V U , -horizontal components of velocity averaged in time. [START_REF] Belotserkovsky | Turbulence. New approaches[END_REF] approach:

The Belotserkovsky

2 / 1 2 2 2 ) ( ) ( ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ∂ ∂ + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ ∂ ∂ Δ = z V z U z C z ν
, where C=0.1-0.2

Both lagoons can be considered as shallow water basins, in particular near the coastline. For the deeper laggon, Etang de Berre, the mean depth is about 6m, and the wavelength of the order of 10m [START_REF] Bernard | Changements à long terme des peuplements de magnoliophytes d'un étang sous forte influence anthropique : l'étang de Berre[END_REF].

Measurement in situ

In September 2006 and in July 2008, field campaigns took place in the two lagoons: Etang de Berre and Etang de Bolmon, separated by a sandspit (lido du Jaï). During these campaigns, the velocity fluctuations have been measured in some mooring points with an Acoustic Doppler Profiler (ADCP RDI 600Khz); see the scheme in Fig. 1. Computation of vertical turbulent coefficient was done on the basis of each approach using ADCP data; distributions coefficients of vertical turbulent exchange for two lagoons Berre and Bolmon were obtained. The analysis of the obtained distributions has shown that subgrid scale methods allow similar distributions (order of values and locations of points of maximum and minimum) of coefficient of a vertical turbulent exchange. However, the Belotserkovsky [START_REF] Belotserkovsky | Turbulence. New approaches[END_REF] method yields to the results which are the most physically relevant for shallow water bassins (the method 2 doesn't give strong increasing of coefficient value near the bottom layer).

Numerical simulation and comparison

The Belotserkovsky approach was included as a module for parameterization of the coefficients of vertical turbulent exchange in the software Azov3D [START_REF] Chistyakov | Numerical experiments with mathematical models of turbulent exchange in shallow water basins[END_REF][START_REF]Software package «three dimensional mathematical model of movement of water in shallow water reservoirs[END_REF] developed in the TIT SFU for modeling currents in shallow water bassins. In Fig. 2 Consider also the vector field obtained by well-known software MARS3D, developed in the Ifremer [10][START_REF] Lazure | An external-internal mode coupling for a 3D hydrodynamical model at regional scale (MARS)[END_REF][START_REF] Fiandrino | Bacterial contamination of Mediterranean coastal seawater as affected by riverine inputs: simulation approach applied to a shellfish breeding area (Thau lagoon, France)[END_REF], and adopted to shallow water basins, like Etang de Berre and Etang de Bolmon. Also computations of currents were done using software MARS3D for different meteorological data (dominate winds and different inflows of fresh water in rivers and channels, different turbulent closures). For structure of currents in the lagoon Etang de Berre streams of fresh water and strong NW wind are significant and dominate during all year, so for the case with these parameters (NW wind 5 m/s and inflow of EDF channel 200 m 3 /s) we obtained stable currents (vortexes in the middle of the lagoon which are not changing in time after period of stabilization -72 hours, see Fig.

Conclusions

An adequate parameterization of coefficient of vertical turbulent mixing is crucial for realistic simulations of hydrodynamics in shallow water basin. We have implemented the two most used methods in the hydrodynamic simulation models and found the Belotserkovsky method to be better appropriate in capturing the dynamics in lagoon of Etang de Berre.

FIG. 1 .

 1 FIG.1. (a) Scheme of the field campaign in September 2006 in Etang de Berre; (b) Ensemble of measured current magnitude, at exact point, as a function of depth (vertical coordinate) and time (horizontal coordinate)

Fig. 2 .

 2 FIG.3 Barotropic currents for the western wind 5m/s. (meteorological data in September 2006)

4 )FIG. 4

 44 FIG.4 Barotropic vector fields of Azov3D(left picture) and Mars3D (right picture) 72 hours after the beginning of simulations; N-W wind of 5 m/s