Marie Chavent
email: marie.chavent@math.u-bordeaux1.fr

Jérôme Saracco
email: jerome.saracco@math.u-bordeaux1.fr

On central tendency and dispersion measures for intervals and hypercubes

Keywords: Clustering, Hausdorff Distance, Multidimensional Interval Data

The uncertainty or the variability of the data may be treated by considering, rather than a single value for each data, the interval of values in which it may fall. This paper studies the derivation of basic description statistics for interval-valued datasets. We propose a geometrical approach in the determination of summary statistics (central tendency and dispersion measures) for interval-valued variables.

Introduction

In descriptive statistics, summary statistics are used to synthesize a set of real observations. They usually involve:

-a measure of location or central tendency, such as the arithmetic mean, median, interquartile mean or midrange, -a measure of dispersion like the standard deviation, range, interquartile range or absolute deviation.

In this paper, we focus on obtaining basic descriptive statistics as central tendency and dispersion measures for interval-valued data. Such data are often met in practice, they typically reflect the variability and/or uncertainty that underly the observed measurement. Interval data is a special case of 'symbolic data', which also comprises set-valued categorical and quantitative variables as described, e.g., in Bock and Diday (2000).

Empirical extensions of summary statistics to the calculation of the mean and variance for interval valued-data have been given by [START_REF] Bertrand | Descriptive statistics for symbolic data[END_REF] and for histogram-valued data by [START_REF] Billard | From the statistics of data to the statistics of knowledge: Symbolic data analysis[END_REF].

In this paper, we propose a geometrical determination of summary statistics (mean, median, variance, absolute deviation,....) for interval-valued variables. This approach mimics the case of real-valued variables, with the absolute value of the difference between two real numbers being replaced by a distance between two intervals.

For real-valued variables, a geometrical way for defining a central value c of a set {x 1 , x 2 , ...., x n } of n real observations is to choose c ∈ R as close as possible to all the x i 's. Let us define the function S p :

S p (c) = x -c p = ( n i=1 | x i -c | p ) 1/p for p < ∞, max i=1...n | x i -c | for p = ∞, (1)
where x ∈ R n is the vector of the n observations x i , • p is the L p norm on R n , and c = cI n with I n the unit vector. Then one can use

ĉ = arg min c∈R S p (c), (2)
as a central value and S p (ĉ) as the associated dispersion measure. The above minimization problem has an explicit solution for p = 1, 2, ∞.

• When p = 1, the central value is ĉ = x M (the sample median) and the corresponding dispersion is

S 1 (x M ) = n i=1 | x i -x M |= ns M
where s M is the average absolute deviation from the median.

• When p = 2, the central value is ĉ = x (the sample mean) and the cor-

responding dispersion is S 2 (x) = n i=1 (x i -x) 2 = (n -1)
s where s is the sample standard deviation.

• When p = ∞, the central value is ĉ = x R (the midrange) and the corresponding dispersion is S ∞ (x R ) = max i=1...n | x i -x R |= 1 2 w
where w is the sample range.

The pairs (x, s 2 ), (x M , s M ) and (x r , w) are then consistent with the use of respectively the L 1 , L 2 and L ∞ norms in the function S p .

For interval-valued variables, we will use the above geometrical approach to define coherent measures of central tendency and dispersion of a set [α, β] defined in order to be as close as possible to all the xi 's. Replacing in (1) the terms | x i -c | by a distance d(x i , c) between two intervals leads to the function S p defined by:

{x 1 , x2 , ...., xn } of n intervals xi = [a i , b i ] ∈ I = {[a, b] | a, b ∈ R , a ≤ b}. A measure of central tendency c is now an interval c =
S p (c) = ( n i=1 d(x i , c) p ) 1/p for p < ∞, max i=1...n d(x i , c) for p = ∞.
(3)

The central interval ĉ = [α, β] is then defined as

ĉ = arg min c∈I S p (c), (4)
and the corresponding dispersion measure is S p ( ĉ).

In the following, after a brief recall of some definitions of distances between intervals (section 2), we exhibit in section 3 particular cases of value p and distance d for which explicit formula of the lower and upper bounds of central intervals ĉ have already been developed. Then we resolve in section 4 the case where p = 2 and d is the Hausdorff distance and we show how the corresponding central interval can be computed in a finite number of operations proportional to n 3 . We generalize in section 5 all these results to hypercubes. Finally, concluding remarks are given in section 6.

Distances between intervals

Many distances between intervals have been proposed. They vary from simple ones to the more elaborated ones. Elaborated distances taking into account both range and position have been proposed in the framework of symbolic data analysis (see for instance, Chapter 8 and 11.2.2 of Bock and Diday, 2000[START_REF] De | Extension based proximities coefficients between boolean symbolic objects[END_REF][START_REF] Ichino | Generalized Minkowski metrics for mixed feature type data analysis[END_REF]. Simple distances commonly used to compare x1 = [a 1 , b 1 ] and x2 = [a 2 , b 2 ] are the L p distances between:

• the two vectors a 1 b 1 and a 2 b 2 of the lower and upper bounds,

• or the two vectors m 1 l 1 and m 2 l 2 of the midpoints m i = a i + b i 2 and the half-lengths

l i = b i -a i 2 .
General distances between sets like the Hausdorff distance (see [START_REF] Nadler | Hyperspaces of sets[END_REF], can also be used to compare two intervals. In the case of two intervals

x1 = [a 1 , b 1 ] and x2 = [a 2 , b 2 ],
the Hausdorff distance has the property to simplify to:

d(x 1 , x2 ) = max(| a 1 -a 2 |, | b 1 -b 2 |) . (5)
By replacing in (5) the lower bound a i by (m i -l i ) and the upper bound b i by (m i + l i ), and according to the following property defined for x and y in R,

max(|x -y|, |x + y|) = |x| + |y|,
one can show that the Hausdorff distance can be written as:

d([a 1 , b 1 ], [a 2 , b 2 ]) =| m 1 -m 2 | + | l 1 -l 2 | . (6)
The Hausdorff distance between intervals has then the interesting property to be, at the same time, -a distance between sets, -equal to the L ∞ distance between the vectors

a 1 b 1 and a 2 b 2 , -equal to the L 1 distance between the vectors m 1 l 1 and m 2 l 2 .
3 Existing results on central intervals

Explicit formula of the central interval ĉ = [α, β] = arg min c∈I S p (c) can be found in some particular cases. We remind these results already obtained and used in previous works (see for instance [START_REF] Chavent | Dynamical Clustering of interval data. Optimization of an adequacy criterion based on Hausdorff distance[END_REF][START_REF] Chavent | An Hausdorff distance between hyper-rectangles for clustering interval data[END_REF][START_REF] De | Dynamic Clustering for Interval Data Based on L 2 Distance[END_REF].

L 1 combination of Hausdorff distances

When p = 1 and d is the Hausdorff distance, S p (c) reads:

S 1 (c) = n i=1 (| m i -µ | + | l i -λ |) , (7)
μ = median{m i | i = 1, . . . , n}, λ = median{l i | i = 1, . . . , n}. (8)

L ∞ combination of Hausdorff distances

When p = ∞ and d is the Hausdorff distance, S p (c) reads:

S ∞ (c) = max i=1,...,n max | a i -α |, | b i -β | , (9)
i.e.

S ∞ (c) = max max i=1,...,n | a i -α | , max i=1,...,n | b i -β | .
α = a (n) -a (1) 2 , β = b (n) -b (1) 2 , ( 10
)
where a (n) (resp. b (n) ) is the largest lower bound (resp. upper bound) and a (1) (resp. b (1) ) is the smallest lower bound (resp. upper bound).

3.3

L 2 combination of L 2 distances For p = 2, an explicit solution is easily defined when d is the L 2 distance between either the middles and half lengths of the intervals or between their lower and upper bounds. For instance in the first case, S p (c) reads:

S 2 (c) = n i=1 d(x i , c)) 2 = n i=1 (| m i -µ |) 2 + (| l i -λ |) 2 . ( 11
)
Theorem 3 In case of an L 2 combination of L 2 distances between midpoints and half lengths, the midpoint μ and the half-length λ of the central interval ĉ are:

μ = 1 n n i=1 m i and λ = 1 n n i=1 l i .
In case of an L 2 combination of L 2 distances between lower and the upper bounds, the lower and upper bounds of the intervals of the central interval ĉ are:

α = 1 n n i=1 a i and β = 1 n n i=1 b i .

Main result

We study here the case of an L 2 combination of Hausdorff distances. When p = 2 and d is the Hausdorff distance, S p (c) reads:

S 2 (c) 2 = n i=1 (max(| a i -α |, | b i -β |) 2 . ( 12
)
Theorem 4 In case of an L 2 combination of Hausdorff distances, the central interval c which minimizes (12) can be computed in a finite number of operations proportional to n 3 .

Proof: The square is an increasing function over positive numbers, so formula (12) can be rewritten:

S 2 (c) 2 = n i=1 max (a i -α) 2 , (b i -β) 2 . ( 13
)
On the other hand, using midpoints and half-lengths, one obtains:

(a i -α) 2 -(b i -β) 2 = -4(m i -µ)(l i -λ) .
So we see that the maximum in ( 13) is

(a i -α) 2 if (m i -µ)(l i -λ) ≤ 0, and (b i -β) 2 if (m i -µ)(l i -λ) ≥ 0.
Let us denote by (m (1) , . . . , m (n) ), resp. (l (1) , . . . , l (n) ), the sample of the midpoints, resp. the half-lengths, organized in increasing order. Let us define the intervals:

M j = [m , m (j+1) ], j = 0, . . . , n, L k = [l (k) , l (k+1) ], k = 0, . . . , n, (14)
with

m (0) = l (0) = -∞ and m (n+1) = l (n+1) = +∞. For all (µ, λ) in any rectangle Q j,k = M j × L k , the product (m i -µ)(l i -λ
) has a given sign, for each i = 1, . . . , n. So the formula (13) for S 2 (c)

2
simplifies over such a rectangle to:

S j,k (c) = i∈I a,j,k (a i -α) 2 + i∈I b,j,k (b i -β) 2 , (15)
where:

I a,j,k = i ∈ {1 . . . n}| m i - m (j) + m (j+1) 2 l i - l (k) + l (k+1) 2 ≤ 0 , ( 16
)
I b,j,k = i ∈ {1 . . . n}| m i - m (j) + m (j+1) 2 l i - l (k) + l (k+1) 2 > 0 . ( 17
)
Hence the minimization of S 2 (c) 2 over R 2 is equivalent to the resolution, for j, k = 0, 1 . . . n, of the (n + 1) 2 constrained quadratic problems:

(P j,k )      find (α, β) = ( αj,k , βj,k ) which minimizes S j,k (α, β) under the constraints: 2m (j) ≤ α + β ≤ 2m (j+1) and 2l (k) ≤ β -α ≤ 2l (k+1) (18)
whose resolution is described in the Appendix.

The central interval ĉ = [α, β] is then given by: ( α, β) = arg min j,k=0,1...,n S j,k ( αj,k , βj,k ).

(

) 19
Because the number of operations in the resolution of ( 18) is proportional to n, the number of operations for the calculation of ( α, β) is proportional to n 3 .

The multidimensional case

We consider now a set of n k-dimensional intervals {x 1 , . . . ,

xn } with xi = [a i , b i ] and a i , b i ∈ R k . A k-dimensional interval xi can also be viewed as a regular hyperparallelepiped xi = k j=1 xj i with xj i = [a j i , b j i ] where a j i (resp. b j i ) is the jth coordinate of a i (resp. b i )
. By misuse of language the xi 's will be called hypercubes in the rest of the paper. The above geometrical approach can then be used to define a central hypercube (also called centrocube or prototype) of a set of n hypercubes {x 1 , . . . , xn }, which is now a k-dimensional interval c = [α, β] with α and β in R k . Replacing in (3) the terms d(x i , c) by a distance D(x i , c) between two hypercubes leads to the function S p defined by:

S p (c) = ( n i=1 D(x i , c) p ) 1/p for p < ∞, max i=1...n D(x i , c) for p = ∞. (20)
The centrocube c = [α, β] is then be defined by ĉ = arg min c∈I

S p (c). (21)

There exists many possible distances between hypercubes (see for instance [START_REF] Bock | Clustering methods and kohonen maps for symbolic data[END_REF]. Once again, depending on the distance D and on the value p in S p (c), the centrocube is more or less difficult to calculate.

A first distance D that could be used is the Hausdorff distance between two hypercubes:

D(x 1 , x2 ) = max(h(x 1 , x2 ), h(x 2 , x1 )) (22) with h(x 1 , x2 ) = sup a∈x 1 inf b∈x 2 δ(a, b) ( 23
)
where δ is an arbitrary metric on R k . We have seen that in the onedimensional case, the Hausdorff distance simplifies to (5) but the calculation of this distance for higher dimensions is more involved and depends of the choice of the metric δ. If δ is the Euclidean metric for instance, there exist algorithms that compute the Hausdorff distance between two hypercubes in a finite number of steps (see e.g., [START_REF] Bock | Optimization in Symbolic Data Analysis: Dissimilarities, Class Centers, and Clustering[END_REF] but as far as we know, there exist no algorithm to compute the centrocube. If δ is the L ∞ metric, an explicit solution of the centrocube exists when p = ∞ (see [START_REF] Chavent | An Hausdorff distance between hyper-rectangles for clustering interval data[END_REF]. In other cases, the definition of centrocubes for the original Hausdorff distance between hypercubes still remains a subject to investigate. Another approach which makes explicit definitions of centrocubes easier to find, is to use a distance D that is a combination of coordinate-wise onedimensional interval distances d:

D(x 1 , x2 ) = ( k j=1 d(x j 1 , xj 2 ) q ) 1/q for q < ∞, max j=1...k d(x j 1 , xj 2 ) for q = ∞. ( 24
)
When p = q, S p (c) p reads:

S p (c) p = n i=1 k j=1 d(x j i , cj ) p ( 25
)
Because d(x j i , cj ) ≥ 0, it sufficient to find for each component j the central interval ĉj which minimizes n i=1 d(x j i , cj ) , so that the centrocube is the product of the central intervals of each variable. The results presented in sections 3 and 4 concerning central intervals can then be applied directly to define this 'coordinate-wise' centrocube.

Concluding remarks

In this paper, we proposed different solutions for the determination of central intervals and hypercubes. These results have applications in clustering. Indeed, the existence of explicit formula for the computation of the centrocube is useful in dynamic clustering (see [START_REF] Diday | Clustering Analysis[END_REF], because it ensures the decreasing at each iteration of the criterion S p . 'Coordinate-wise' centrocubes have been defined as prototype in several dynamical clustering algorithms of interval data. The 'coordinate-wise' centrocube for p = q = 1 is used with the Hausdorff distance in [START_REF] Chavent | Dynamical Clustering of interval data. Optimization of an adequacy criterion based on Hausdorff distance[END_REF] and with the L 1 distance between the lower and the upper bounds in [START_REF] De Souza | Clustering of interval data based on city-block distances[END_REF]. The case p = q = 2 is used by [START_REF] De | Dynamic Clustering for Interval Data Based on L 2 Distance[END_REF] with the L 2 distance between the lower and upper bounds. The algorithm proposed in section 4 for the determination of the central interval in the case of L 2 combination of Hausdorff distances gives a solution for the case p = q = 2 and the Hausdorff distance.

Another application of these results concern the data scaling. Dealing with scalar variables measured on very different scales is already a problem when comparing two objects globally on all the variables. For instance, the Euclidean distance or more generaly the L q distance will give more importance to variables of strong dispersion and the comparison between objects will only reflect their differences on those variables. A natural way to avoid this effect is to use a normalized distance. A L q normalized component-wise distance between hypercubes could then be:

D(x 1 , x2 ) =    ( k j=1 ( d(x j 1 ,x j 2 ) S( ĉj ) ) q ) 1/q for q < ∞, max j=1...k d(x j 1 ,x j 2 ) S( ĉj ) for q = ∞. ( 26
)
where S( ĉj ) is the dispersion measure associated to a central interval ĉj . For coherency reasons, it seems reasonable to use the same exponent (q = p):

-to aggregate the intervals in the search of the central interval and the evaluation of the dispersion for each variable (exponent p in (3)),

We describe now the corresponding algorithm. We have eliminated the consideration of some dead-end cases by taking advantage of the convexity of the problem: when the solution (μ, λ) of (P) is on one edge of Q (possibly at a corner of Q) , the unconstrained minimizer (μ, λ) of S and the center of Q are necessarily on different sides of the line containing this edge. Hence the edges of Q which can possibly contain the solution (μ, λ) are those which contain the L 2 -projection of (μ, λ) on Q.

We suppose for simplicity that the midpoints and half-length of all intervals are distinct:

m (1) < m (2) < . . . < m (n) l (1) < l (2) < . . . < l (n) ( 30
)
One computes first, in a loop from i to n over the samples:

     n a = i∈Ia 1 , n b = i∈I b 1 , A = i∈Ia a i , B = i∈I b b i , A 2 = i∈Ia a 2 i , B 2 = i∈I b b 2 i , (31)
with the convention that the sum is zero if the set I a or I b of indices is empty. Notice that n a is the number of indices in I a , and n b is the number of indices in I b , so that n = n a + n b . With these notations, the gradient of S:

∇ S(µ, λ) = 2 -i∈Ia (a i -µ + λ) -i∈I b (b i -µ -λ) + i∈Ia (a i -µ + λ) -i∈I b (b i -µ -λ) .
simplifies to:

∇ S(µ, λ) = 2 -A -B + (n a + n b )µ -(n a -n b )λ +A -B -(n a -n b )µ + (n a + n b )λ . (32)
The minimizer (μ, λ) of problem (P) can be computed as follows:

1. If n a = 0 (a similar reasoning can be done if n b = 0), then function S reduces over Q to:

S(µ, λ) = i=1,...,n (b i -µ -λ) 2 ,
and the level lines of S degenerate to the straight lines µ+λ = constant. The unconstrained minimizers (μ, λ) of S are then on the line:

(L) n(µ + λ) = B .
If the line (L) goes through Q, problem (P) has an infinite number of solutions, with at least one of them (in general two) being on the boundary of Q. If (L) does not hit Q, the unique solution of (P) is located at the corner of Q closest to (L). In both cases, (P) admits at least one solution (μ, λ) on one edge of Q. If we denote by Q * the rectangle on the other side of this edge (for which ña = 1 = 0), one sees that (μ, λ) ∈ Q * , so that the minimum S * min of S over Q * will necessarily be smaller than Smin , the minimum of S over Q (as (μ, λ) ∈ Q * ). So there is no point in computing Smin , and we can skip the resolution of problem (P).

2. If n a > 0 and n b > 0, the unconstrained minimizer (μ, λ) of S is unique.

It is given by:

i∈Ia a i = n a (μ -λ) = n a α, i∈I b b i = n b (μ + λ) = n b β. ( 33
)
If (μ, λ) ∈ Q then set μ = μ , λ = λ, and problem is solved.

If not, go to the next step.

3. Compute the L 2 -projection ( μ, λ) of (μ, λ) on Q : Then set:

μ =      m -if μ ≤ m - μ if m -≤ μ ≤ m + m + if m + ≤ μ , λ =      l -if λ ≤ l - λ if l -≤ λ ≤ l + l + if l + ≤ λ (
μ = m -, λ =        l -if λ ≤ l -, λ if l -≤ λ ≤ l + , l + if m + ≤ λ , , (36)
and problem is solved.

5. If the projection is at a corner of Q, say for example μ = m -, λ = l - (lower-left corner), evaluate the gradient ∇ S = (g µ , g λ ) at the corner.

• If g µ ≥ 0 and g λ ≥ 0, set μ = m -, λ = l -, and problem is solved.

• If g µ < 0 and g λ ≥ 0, (the objective function is decreasing when one leaves the lower-left corner to the right on the lower edge of Q), determine λ which zeroes the component of ∇ S along this edge (here the first component as the edge is parallel to the first axis λ = 0):

- i∈Ia a i + n a ( μ -l -) - i∈I b b i + n b ( μ + l -) = 0. ( 37
)
Then set:

μ = μ if m -< μ ≤ m + , m + if m + ≤ μ , , λ = l -, (38)
and problem is solved.

• If g µ ≥ 0 and g λ < 0, similarly determine μ which zeroes the component of ∇ S along the left edge of Q:

+ i∈Ia a i -n a (m --λ) - i∈I b b i + n b (m -+ λ) = 0 (39)

Theorem 1

 1 where µ and λ are the midpoint and the half-length of c = [α, β].Minimization of S 1 (c) boils down to the two minimization problems: In case of an L 1 combination of Hausdorff distances, the midpoint μ and the half-length λ of the central interval ĉ are:

  Minimization of S ∞ (c) boils down to the two minimization problems: min α∈R max i=1,...,n |a i -α| and min β∈R max i=1,...,n |b i -β| . Theorem 2 In case of an L ∞ combination of Hausdorff distances, the lower bound α and the upper bound β of the central interval ĉ are:

  the projection is on a edge of Q, say for example μ = m -, l -< λ < l + (left edge), determine λ which zeroes the component of ∇ S along this edge (here the second component as the edge is parallel to the second axis µ = 0):+ i∈Ia a i -n a (m --λ) -i∈I b b i + n b (m -+ λ) = 0.(35)

Acknowledgments

The authors thank G. Chavent for his helpful contribution to the resolution of problem (P j,k ) in the Appendix. They would like also to thank the associate editor and the reviewers for their useful comments.

-and to evaluate the distance between objects (exponent q in (26)).

To conclude, a natural extension of these results concerns weighted central tendency and dispersion measures. This point is currently under investigation.

Appendix: Resolution of problem (P j,k )

We describe here the resolution of one of the minimization problems (P j,k ) of equation ( 18). We drop the subscripts j, k, and we write m -instead of m (j) , m + instead of m (j+1) , l -instead of l (j) and l + instead of l (j+1) . We use the midpoint and half-length variables µ = (α + β)/2 and λ = (β -α)/2, and we denote by Q the rectangle

With these notations, the problem to solve is now:

(P) find (μ, λ) which minimizes S(µ, λ) over Q,

where the objective funtion is:

with I a and I b defined respectively in ( 16) and ( 17) This objective function is convex and quadratic (the level lines of S are -possibly degenerated -ellipses with axis parallel to the directions λ = µ and λ = -µ), and the constraints in ( 27) are linear, so that the resolution of (P) is equivalent to that of the associated Kuhn-Tucker system of necessary conditions.

Then set:

and problem is solved.

• The case g µ < 0 and g λ < 0 cannot happen.

The minimum value S min of S over Q is then:

where α = μ -λ and β = μ + λ.


Marie Babel

Benoît Parrein

Olivier Déforges

Nicolas Normand

Jean-Pierre Guédon

Véronique Coat

Joint source-channel coding: secured and progressive transmission of compressed medical images on the Internet

Keywords: medical image compression, LAR method, Mojette transform, scalability, priority encoding system

The joint source-channel coding system proposed in this paper has two aims: lossless compression with a progressive mode and the integrity of medical data, which takes into account the priorities of the image and the properties of a network with no guaranteed quality of service. In this context, the use of scalable coding, Locally Adapted Resolution (LAR) and a discrete and exact Radon transform, known as the Mojette transform, meets this twofold requirement. In this paper, details of this joint coding implementation are provided as well as a performance evaluation with respect to the reference CALIC coding and to unequal error protection using Reed-Solomon codes.

INTRODUCTION

Through the development of PACS (Picture Archiving and Communication Systems), health care systems have come to rely on digital information. Furthermore, future medical applications will have to integrate access to generalized databases that contain the personal medical information of each patient. Efficient image management consequently becomes a key issue in designing such a system. Given this situation, two main elements must be considered at the same time: compression and security strategies specific to image handling [START_REF] Norcen | Confidential storage and transmission of medical image data[END_REF].

Naturally, teleradiology systems integrate the notion of security [START_REF] Sneha | Strategies for Working with Digital Medical Images[END_REF]. In particular, they must guaran- * Corresponding author.

Email addresses: Marie.Babel@insa-rennes.fr (Marie Babel), Benoit.Parrein@polytech.univ-nantes.fr (Benoît Parrein).

tee the integrity (to prevent the alteration of data), authentication (to check the sender) and the confidentiality (to prevent unauthorized access) of the medical data at all times. The availability of the information can be ensured by the Internet Protocol (IP). Moreover, wireless transmissions play an increasingly important part in the achievement of this goal, [START_REF] Pedersen | Wireless Technology Applications in a Rural Hospital[END_REF][START_REF] Pattichis | Wireless Telemedicine Systems: An Overview[END_REF][START_REF] Vucetic | Telemedicine: The Future of Wireless Internet Applications[END_REF] especially in the context of emergency medicine [START_REF] Hashmi | A sensorbased, web service-enabled, emergency medical response system[END_REF]. However, this access to information must be accompanied by security primitives. For privacy and authentication purposes, the traditional security solutions integrated in the DICOM standard cover encryption processes and digital signatures [START_REF] Oosterwijk | The DICOM standard, overview and characteristics[END_REF].

To the best of our knowledge, very few publications cover the loss of entire IP packets in medical data transmissions [START_REF] Mohr | Unequal Loss Protection : Graceful degradation of image quality over packet erasure channels through forward error correction[END_REF]. In a more general framework such as image transmission, most studies relate to the implementation of error control coding e.g. Reed-Solomon codes to compensate for packet loss by avoiding retransmissions [START_REF] Mohr | Unequal Loss Protection : Graceful degradation of image quality over packet erasure channels through forward error correction[END_REF] [START_REF] Dufaux | JWL: JPEG 2000 for wireless applications[END_REF]. By adjusting the correction capacities and, thus, the rates of redundancy, it is possible to adapt to both a scalable source and an unreliable transmission channel. This is the purpose of Unequal Error Protection (UEP) codes which are now mature and proposed in standardization processes [START_REF] Jpeg | JPEG 2000 image coding system -Part 11: Wireless JPEG2000 Committee Draft[END_REF]. The specific problem of medical image integrity is very often the volume of the data being transmitted (cf lossless coding, 3D-4D acquisition etc.). Within this framework, UEP must meet algorithmic complexity requirements to satisfy real time constraints. With this in mind, we propose in this paper the use of an exact and discrete Radon transform, the Mojette transform, to compensate for IP packet loss.

With regard to compression, archiving implies lossless compression. Indeed, lossless compression is required either from a legal point of view (relative to each country), or from the radiology point of view (to avoid any misdiagnosis) [START_REF] White | Legal issues in teleradioogy -distant thoughts![END_REF]. The most efficient lossless compression schemes, such as CALIC [START_REF] Wu | Context-based, adaptive, lossless image codec[END_REF] or Edge Directed Prediction based solution [START_REF] Li | Edge-Directed Prediction for Lossless Compression of Natural Images[END_REF], do not provide any progressive transmission of the information yet this can be useful for transmissions on low bitrate networks, in particular on the wireless channel. Few schemes are dedicated to medical image compression. Among them the SSM coder [START_REF] Pzrelaskowski | Lossless Encoding of Medical Images: Hybrid Modification of Statistical Modelingbased Conception[END_REF] outperforms other solutions on some particular classes of images (US images) at the expense of complexity (selection between several coders, successive optimization steps of many parameters for each image classes).

The DICOM standard dedicated to medical image compression, has recently integrated the JPEG-2000 standard file format [START_REF]DICOM (Digital Imaging and Communications in Medicine), PS 3.5 Part 5: Data Structures and Encoding[END_REF]. Preliminary work has indeed stressed the need for a compression method that provides both scalability and advanced functionalities such as Region Of Interest (ROI) coding [START_REF] Foos | JPEG 2000 compression of medical imagery[END_REF]. The Interleaved S+P algorithm, based on the LAR (Locally Adaptive Resolution) coding method [START_REF] Babel | Interleaved S+P Pyramidal Decomposition with Refined Prediction Model[END_REF], produces better coding results than the JPEG-2000 lossless mode. Moreover, thanks to and "intelligent" scalable semantic representation of the image, it provides high scalability together with advanced services.

This paper describes combination of the two methods (the LAR scalable coding scheme and the Mojette transform) which offers an efficient algorithm for the secure and progressive transmission of compressed medical images. The idea is to use and to preserve the intrinsic hierarchy of the Inter-leaved S+P coder. An UEP system is then built using the Mojette transform to provide protection against the loss of entire streams (IP packets) that represent essential information.

The structure of the paper is as follows. We begin by describing the LAR coding scheme and the associated semantic representation. The section 3 details the scalable Interleaved S+P solution. In the section entitled 4, we develop the different coding modes that are available before moving on to present the Mojette transform is presented (section 5) and explaining the entire joint LAR-Mojette method (section 6).

LAR METHOD FOR LOSSY GREYSCALE IMAGE COMPRESSION

The LAR method was first designed for the purposes of low bit-rate greyscale image coding [START_REF] Déforges | Nonuniform Sub-Sampling using Squares Elements : a Fast Still Image Coding at Low Bit-Rate[END_REF]. Recent research has led to the construction of scalable encoding schemes based on original pyramidal predictive descriptions, that are efficient for both lossless and lossy compression purposes [START_REF] Babel | Interleaved S+P Pyramidal Decomposition with Refined Prediction Model[END_REF][START_REF] Babel | Lossless and Lossy Minimal Redundancy Pyramidal Decomposition for Scalable Image Compression Technique[END_REF]. In this section, we describe the basic principles of the LAR scheme.

Principles

In general, image representation and image compression are two distinct topics in the image processing field. However, the LAR method tries to link these two processes. The concept has in fact two major benefits. First, good representation naturally leads to the building of a better coding scheme. Secondly, advanced functionalities such as Region Of Interest coding can be easily implemented.

The LAR compression method is a two-layer codec: a flat codec and a complementary spectral one. This follows the idea developed in particular in [START_REF] Meyer | TMW : a new Method for Lossless Image Compression[END_REF], where images are considered to be the superposition of global information and texture (local information). The flat LAR codec is designed to provide a low bit-rate compressed image, whereas the spectral one encodes the texture. The originality of the proposed method lies in the fact that our scheme provides a content-based image coding method.

The following two paragraphs describe these flat and spectral coders respectively. Note that the quality of the low resolution LAR image has already been evaluated and recognized to be better than JPEG-2000 [START_REF] Déforges | Region of Interest Coding for Low Bit-Rate Image Transmission[END_REF].

Flat coder

The basic idea is that local resolution, in other words pixel size, can depend on local activity. This leads to the construction of a variable resolution image based on a quadtree data structure. The final size of blocks (typically from 16 × 16 to 2 × 2) is computed using an estimation of a local morphological gradient: each block is then reconstructed by its average luminance. Thanks to this type of block decomposition, their size implicitly gives the nature of the said block. Small blocks are naturally located on contours whereas large ones are situated in smooth areas. Discrimination between areas is clearly visible on figure 1.b and 1.d. In a lossy context, this image content information controls a quantization of the luminance that is in accordance with visual perception: large blocks require fine quantization (in uniform areas, human vision is strongly sensitive to brightness variations) while coarse quantization (low sensitivity) is sufficient for small blocks.

To sum up, this coder has two main distinctive characteristics. Firstly, it provides a very fast and efficient tool for high compression ratios, and secondly, the method simplifies the image source by removing the local texture while preserving object boundaries. Perceptible block artefacts in homogenous areas are easily removed by efficient post-processing: in particular, an adaptive interpolation based on the optimal recovery theory can be implemented [START_REF] Muresan | Optimal Recovery Approach to Image Interpolation[END_REF].

For color images, another improvement was achieved by the representation of self-extracting regions. Natural extensions of this particular process have also made it possible to address medium and high quality encoding and the region-level encoding of chromatic images [START_REF] Déforges | Supervised Segmentation at Low Bit Rates for Region Representation and Color Image Compression[END_REF].

Spectral coder

The flat LAR coder is clearly dedicated to lowbit rate image coding. To obtain higher image quality, the texture (whole error image) can be encoded through the spectral coder (second layer of the LAR coding scheme) which uses a DCT adaptive blocksize approach [START_REF] Chen | Adaptive transform coding via quad-tree based variable block-size DCT[END_REF]. In this case, both the size and the DC components are provided by the flat coder. The use of adapted block size naturally allows for a semantic scalable encoding process. For example, edge enhancement can be made by only transmitting the AC coefficients of small blocks. Further refinements can be envisaged by progressively sending larger block information.

SCALABLE LOSSLESS CODING: INTERLEAVED S+P METHOD

In medicine, only the lossless coding of images is authorized for archiving purposes. The DICOM standard has recently integrated the JPEG-2000 standard file format [START_REF]DICOM (Digital Imaging and Communications in Medicine), PS 3.5 Part 5: Data Structures and Encoding[END_REF]: it enables scalable coding of a picture together with Region Of Interest (ROI) encoding. A new method, Interleaved S+P supported by the LAR concepts, is described in this section.

General principles

The "Interleaved S+P" algorithm is designed to provide a lossless representation of images. This new method keeps the same main structure as the LAR method (presented in section 2), namely a two-layer codec, so that the first part of the compressed bitstream allows the reconstruction of the LAR block image. A major improvement lies in the fact that the LAR pyramidal decomposition is based on an adaptation of the Wu predictor [START_REF] Wu | A Context-based, Adaptive, Lossless/Nearly-Lossless Coding Scheme for Continuous-Tone Images (CALIC)[END_REF]. For full resolution images, errors are coded by means of triple interlaced sampling of the original image. Consequently, we tend to obtain a spatial configuration of a 360˚type neighborhood surrounding a given pixel so that the resulting prediction error is drastically reduced.

The Interleaved S+P algorithm is achieved in two main steps. The first stage consists of applying the 1D S-Transform on the 2 vectors formed by 2 diagonally adjacent pixels in a 2 × 2 block, as depicted in figure 2.

In the following, z 0 and z 1 denote the Stransformed coefficients in such a way that if (u 0 , u 1 ) is a pair of values, we have:

z 0 = (u 0 + u 1 )/2 , z 1 = u 1 -u 0 .
(

) 1
The second step constitutes the prediction process. The prediction is in turn achieved in three successive passes. We also denote z k i , where i ∈ {0, 1} and k ∈ {1, 2, 3} constitute the z i coefficient coded through the k th pass.

The first prediction pass uses a traditional DPCM system to encode a uniform subsampled image formed by the average of two diagonally adjacent pixels (first diagonal) within each 2x2 block (z 1 0 transformed coefficients). Then the second pass predicts the z 2 1 transformed coefficients in order to reconstruct the value of the two pixels of the first diagonal, taking into account the fact that the mean value is already known (Fig. 3). At this stage, the 360˚type prediction consists of the already known values of the current pass and the diagonal means coded by the first pass. Finally, the third pass encodes the remaining half of the original image composed of the set of z 3 0 and z 3 1 S-coefficients. Once again, thanks to the reconstructed pixels resulting from the two previous passes, a completely spatially enclosing and adjacent context is available to predict the transformed pixel.

Pyramid construction -Interleaving

In the previous paragraph, we described the basic elements of our algorithm. The Interleaved S+P method simply results from the extension of this scheme. We define here the pyramid construction as well as its interleaving property. Let J the original image be of size N x × N y . The multiresolution representation of an image is described by the set {Y l } lmax l=0 , where l max is the top of the pyramid and l = 0 the full resolution image. As an extension of the Wu method, four blocks N 2 × N 2 are gathered into one block N × N valued by the average of the two blocks of the first diagonal (first S-pyramid on fig. 4). This produces the following equation:

Blocks n X n Blocks n/2 X n/2 Blocks n/4 X n/4 Level l+1 Level l Level l+2
First S-Pyramid Second S-Pyramid

l = 0, Y 0 (i, j) = J(i, j); l > 0, Y l (i, j) = Y l-1 (2i,2j)+Y l-1 (2i+1,2j+1) 2 , ( 2
) with 0 ≤ i ≤ N l x , 0 ≤ j ≤ N l y ,
where N l x = N x /l and N l y = N y /l. The transformation of the second diagonal of a given 2 × 2 block can also be seen as a second Spyramid, where the pixel values depend on the values existing on the lower level of the first S-pyramid. This specific construction of the algorithm can be interpreted as an interleaved process, with the second S-pyramid depending entirely on the first one.

Interleaved S+P Pyramid Decomposition -Refined prediction model

The Interleaved S+P pyramidal decomposition process results from the extension of the previously described prediction method to the whole pyramid. As mentioned in section 2, the decomposition is realized in two successive processes. The first one is aimed at obtaining the block image, while the second one enables the reconstruction of the texture information. The LAR specific grid is used for this purpose, as depicted in figure 5. An image denoted Siz is introduced: it contains the size information (the block size, i.e. from 2 to 16) worked out from Quadtree partition.

For a given level l, when only processing the pixels of size Siz(x × l, y × l) ≤ 2 l , the codec reconstructs the LAR low resolution image. This block image is then obtained after the first pyramidal decomposition. The second pyramidal decomposition then makes it possible to recover texture information and an estimation process is applied to pixels of size Siz(x × l, y × l) > 2 l . Implemented predictors differ according to: -the nature of the coefficients (z 0 and z 1 ), -the location of pixels (first or second S-pyramid), -the nature of local information, i.e. blocks image or texture.

Compression results

In [START_REF] Babel | Interleaved S+P Pyramidal Decomposition with Refined Prediction Model[END_REF] we have already emphasized the superiority of the Interleaved S+P over the state-of-the-art lossless compression method in terms of first-order entropy for natural images. In this paragraph, we present some results on medical images 1 .

Table 1 shows the first-order entropy resulting from the application of Interleaved S+P. This entropy can be directly compared with the ones obtained when using the S+P [START_REF] Said | Reversible Image Compression via Multiresolution Representation and Predictive Coding[END_REF] and CALIC [START_REF] Wu | Context-based, adaptive, lossless image codec[END_REF] state-of-the-art methods. CALIC is considered to be the reference for lossless medical images compression in terms of performance [START_REF] Clunie | Lossless Compression of Grayscale Medical Images: Effectiveness of traditional and state-oftheart Approaches[END_REF]. Note that no entropy encoder was used here.

Clearly, our coder widely outperforms both S+P and CALIC equivalents. The Interleaved S+P coder presents an average entropy equal to 3.02 bpp, whereas CALIC and S+P reach 3.20 and 3.16 bpp respectively. The Interleaved S+P coder provides its best results on mammograms and MRI images. In addition, our method offers an image encoder that is scalable in terms of both resolution and quality.

The performances of our algorithm stem from the initial quadtree partition. As it is perfectly correlated to the local activity, the method uses the information to adapt the prediction process in such a way as to decrease coding cost. Moreover, we split the bitstreams into different substreams according to the nature, location and local activity of the corresponding pixel. Implicit context modeling is then used, and this drastically reduces the final entropy. This is particularly true when applied to medical images. Indeed, mammogram or MRI images typically contain two distinct areas: a large black zone (background) and a strongly textured area. The variable size block representation peculiar to LAR coders provides an efficient representation of these images and enables efficient compression of the information. For example, the prediction errors relative to large blocks (located in uniform areas) are much lower than the others, and the resulting entropy is quite low.

FUNCTIONALITIES -MODES OF ENCODING

Near-lossless encoding

Among the common encoding modes, the one known as "near-lossless" essentially consists of applying small quantization to result in undetectable errors. As Interleaved S+P derives from the scalable extension of the basic LAR scheme, it appears that its ability to preserve natural content easily adapts quantization to human visual perception. For example, figure 6 shows the result of pyramidal decomposition where a quantization step equal to 4 is applied to contours (2 × 2 blocks) and a step equal to 2 is applied to flat areas. As no visual distortion is noticeable, it is easy to imagine this functionality being used in the context of remote database access: the image is sufficient for initial medical reporting but the coding cost is lower.

Scalable representation

The pyramidal description of the images resulting from Interleaved S+P encoding provides various scalability levels. The conditional decomposition (the constraint of two successive descent processes by the initial quadtree partition of the image) provides a highly scalable representation in terms of both resolution and quality. Figure 7 shows an example of this outstanding characteristic of our method and it is a major advantage for applications such as remote database consultation, teleradiology or other advanced client-server solutions.

Self-extracting region representation -Region of interest

As mentioned above, the integration of JPEG-2000 into the DICOM standard was also motivated by useful functionalities such as Region Of Interest coding. Typically, only a small portion of the medical image contains relevant and diagnostically useful information, while the remaining portion is displayed only as a visual background [START_REF] Anastassopoulos | JPEG2000 ROI Coding in Medical Imaging Applications[END_REF][START_REF] Clunie | Lossless Compression of Grayscale Medical Images: Effectiveness of traditional and state-oftheart Approaches[END_REF]. Through the definition of a Region of Interest (ROI), images can be lossly compressed overall and losslessly encoded locally. Combined with a progressive encoding scheme, region scalability allows faster access to significant data.

However, the JPEG-2000 ROI coding process is totally constrained by tile description. The LAR scheme enables more flexible solutions in terms of ROI shape and size. Indeed, an ROI can be simply described at both the coder and decoder as a set of blocks resulting from the quadtree partition. As the ROI is built from the variable block size representation, its enhancement (texture coding) is straightforward: it merely requires execution of the Interleaved S+P codec for the validated blocks, i.e. ROI internal blocks. A simple example of this scheme is shown in figure 6. Unlike traditional compression techniques, the LAR low resolution image does not introduce strong distortions on the ROI contours. Such distortion usually makes the image too unreliable to be used.

Previous work centres on the definition of an original hierarchical self-extracting region representation based on the initial LAR partition [START_REF] Déforges | Region of Interest Coding for Low Bit-Rate Image Transmission[END_REF]. This advanced scheme can be combined with the Interleaved S+P coding technique to introduce another level of scalability. In addition to the pyramidal representation described in section 3, this hierarchical representation of regions provides a highly scalable scheme with a wide spectrum of services. Figure 8 shows an example of ROI encoding. In it, a ROI is represented by a set of regions obtained through our self-extracting region representation process.

ERROR RESILIENCE CODING BY MOJETTE TRANSFORM

In this section, we take the process of LAR coding for transmission purposes a little further and propose a reliable communicating multimedia system. In addition to the heart of the compression ma- Fine granularity can be obtained for good adaptation both to the hierarchy of the image and to the channel properties that we define in this paper as joint source channel coding.

A great deal of research work has been done in this area over the past decade. The working draft of JPEG2000 WireLess (JPWL) [START_REF] Jpeg | JPEG 2000 image coding system -Part 11: Wireless JPEG2000 Committee Draft[END_REF] proposes concentrated unequal protection on the main header and the tile header with the characteristic that any error on these part of the stream is fatal for decoding. Error sensitivity is characterized by the PSNR. Conventional Reed-Solomon error correction codes are applied to a symbol level to provide protection. In [START_REF] Dufaux | JWL: JPEG 2000 for wireless applications[END_REF], the codes (160,64), (80,25) and (40,13) are chosen and given redundancy rates of between 150% and 220% with some 500 bytes for headers. This very strong protection obviously improves the chances of success in decoding when binary losses occur but it also guarantees the integrity of the headers whether the properties of the channel are good or very bad. Furthermore, performance evaluation and protection on a symbol level are far removed from the real channels like wireless channels as can be seen for example through the variations in the protocol IEEE802.xx (WLAN or WiMax). More precisely, the approach never considers the effectiveness of the mechanisms operated on the level of Media Access Control (MAC) layer and physical (PHY) layer such as the hybrid ARQ (Automatic Query Request) combining efficient channel coding (turbo-code) and retransmission. Likewise, the working draft does not consider the exploratory research carried out over the past ten years on unequal error protection [START_REF] Albanese | Priority Encoding Transmission[END_REF] or the new representations based on a multiple description of information [START_REF] Wolf | Source coding for multiple description[END_REF].

In this section, we consider the PHY and MAC layers as effective to deliver true symbols so as to focus all our attention of unequal protection at the transmission unit level i.e the packet level. Protection is provided for the whole LAR coding stream. It depends on the sensitivity of each substream and the packet loss rate. The core joint source channel coding uses the Mojette transform.

The direct Mojette transform

The Mojette transform [START_REF] Guédon | The Mojette transform: the first ten yearsn[END_REF] is an exact and discrete Radon transform. It may seem strange that we should be using a conventional medical imaging tool for image communication but it easily describes an image in terms of a finite set of 1D-projections that will be our transport units in the following section of the article. Each angle of projection θ is defined as a couple of integers (p, q), relatively primes, with q p = tan θ. The direct Mojette transform of an image f (k, l), denoted by Mf , represents a set of N projections M p,q f such as

Mf = {proj pi,qi , i = 1, 2...N }.
(

To compute this transform, we simply use additions in directions determined by the couple of integers (p, q). The resulting projections are formed by a set of elements called bins. The value of a projection bin m is calculated by the sum of pixels f (k, l) located on the line determined by m = -qk + pl. The following equations stand for the definition of the Mojette transform:

proj pi ,qi (m) = k l f (k, l)Δ(m + kq -pl), ( 4
)
where Δ is the Krönecker function2 .

Since each pixel contributes to one bin, the order of complexity is necessarily O(I) for any projection and for I pixels. If we want to compute a N projections set, the order of complexity is O(IN ), linear with the number of pixels and with the number of projections.

The Mojette transform is linear with the number of pixels and the number of projections, in the same way as the Fourier and Meyer (wavelet) transforms. Unlike them, however, Radon and Mojette 0 otherwise transforms do not aim to obtain an orthogonal decomposition of the signal; they are designed to obtain a frame. They produce useful redundancy for reconstruction. In fact, we consider this to be the fundamental difference between these two families of transforms: while the Fourier and Meyer transforms provide a hierarchical order of coefficients, the bins resulting from the application of Radon and Mojette transforms to a signal carry all the same weight. However, a given projection carries a quantity of information that is relative to its capacity to recover a portion of the original area. Moreover, each element contains the mean value (the sum of all projections bins), whereas in the case of orthogonal transform, this information is always contained in the first coefficient, but absent in the others. This fundamental property of frames is a very useful feature for the direct and inverse implementation of Mojette transforms, indicating that the user can be left to choose the order of construction and reconstruction. The frame-like definition allows redundancies that can be further used for image description and image communication.

The inverse Mojette transform

Algorithm

The Mojette reconstruction algorithm is based on the fact that not all bins correspond to the same number of projected pixels. It is obvious that the value of a bin corresponding to a single pixel is identical to the pixel value. When such a one-to-one correspondence is found, the pixel value is copied from the bin value. The pixel is then removed from all the projections i.e. and its value is subtracted from all the bins where it projects. At this stage, the remaining bins represent the Mojette transform of the unreconstructed part of the image.

Reconstructing the image from a set of projections is then a process that iteratively:

(i) finds a reconstructible bin i.e. a bin projected from a single pixel, (ii) "backprojects" its value onto the origin pixel, (iii) updates the projections, until the reconstruction is completed or no one-toone correspondence between a bin and a pixel is found.

Reconstruction criterion

A rectangular image P × M can be reconstructed from a set of projections with directions {(p i , q i )} if and only if:

⎧ ⎨ ⎩ i |p i | ≥ P or i |q i | ≥ M . ( 5
)
When building a set of reconstructible projections, we can choose to comply with either of the two conditions. For example, if we set all q i to 1, a P × M image will require exactly M projections to be reconstructed whatever its width P . From this reconstructible set of M projections, we can build a redundant set by adding new projections. With N -M extra projections, any subset of M projections among the total N is enough to reconstruct the image.

Multiple description by Mojette transform

Within the framework of communication systems, the Mojette transform can be applied to multiple description (MD) codes. These codes are precisely overviewed in [START_REF] Goyal | Muliple Description Coding: Compression Meets the Network[END_REF]. MD code consists of separating an original source by means of several independent descriptions which give a degraded but useful version. Making descriptions individually good, yet not too similar, is the fundamental tradeoff of MD coding [START_REF] Goyal | Muliple Description Coding: Compression Meets the Network[END_REF]. The Mojette transform can be simply used to realize this tradeoff [START_REF] Parrein | Multimedia Forward Error Correcting Codes[END_REF]. We describe here the mechanism of the packetization strategy that converts the prioritized multiresolution (or layered) coding into an N unprioritized description using the Mojette transform.

Each element of a source bitstream is allocated to a 2D support which can be considered as a geometrical buffer in our communication system. Application of the direct Mojette transform to this buffer produces the descriptions. Each description in the MD stream fills an entire network packet: the terms "descriptions", "packets" and "projections" are thus used indifferently. The method, which uses several geometrical buffers, is described even if these buffers can be concatenated in order to optimize the stretch factor of the code i.e. the transmitted and original information ratio [START_REF] Parrein | Multiple Description of Information by Mojette Transform[END_REF]. However, the separated design builds the protection scheme with a simpler partition of the data. It is based on separable geometrical buffers for each stream and priority. The Mojette transform of each support is then simultaneously computed. The number of necessary projections indicates the priority level supported by a buffer. Let ρ be the protection function that maps each geometrical buffer to a number of projections i.e. ρ i projections are necessary to reconstruct the i th buffer. Figure 9 gives an example of protection. Three rectangular supports have distinct reconstruction properties to obtain three scalable protection levels. Sub-streams 1, 2 and 3 are allocated respectively to geometrical buffers 1, 2 and 3. Support 1 (resp. 2 and 3) is reconstructible by means of two projections (resp. three and four) taken from the projection set S = {(-2, 1), (-1, 1), (0, 1), (1, 1)}. For this example, ρ = {2, 3, 4}. Packet 1 then contains all projections of angle (0, 1) whereas packet 4 contains projections of angle (-2, 1). This involves variable sizes of packets while simplifying the insertion of angle labels.

This method presents a solution to the need to protect scalability. The Mojette transform produces descriptions which are equivalent for the transmission network. For any given priority level, if the transmission is composed of M projections and N -M redundant projections, it is possible to rebuild the layer in a deterministic way, starting with any M packets received from among N . Using this mechanism, we have supported the hierarchy of the source over a best-effort channel.

Optimal redundancy allocation

In a simple manner, the Mojette transform can provide a redundant description of initial information. The purpose of optimal redundancy allocation is to determine the number of redundant projections according to the description of error sensibility and the probability of receiving the original information. In the case of a scalable source composed of hierarchical substreams, optimisation gives the overall number of sufficient projections for each substream: the protection function ρ.

Let s be the substream index going from 1 to L where L is the number of resolutions (or quality layers). The progressive reconstruction of the source assumes that substream s is usable only if substream s -1 is rebuilt. It is not useful to provide greater protection for substream s -1 than for substream s. The ρ function is thus monotonically increasing:

ρ 0 = 0 ρ 1 ρ 2 ... ρ L ( 6
)
Let Q s be the quality measurement associated with the image reconstructed from substreams 1 to s. Given the source scalability, we suppose Q s Q s-1 . We can define a quality increment easily, ΔQ s , positive or null by:

Geometrical buffer 1 p 1,
ΔQ s = Q s -Q s-1 , (7)
where ΔQ 0 = Q 0 . Let X be the random variable representing the number of received projections. The optimal ρ function maximizes the expected quality E[Q] at the decoding stage:

E[Q] = L s=0 Q s P [ρ s X < ρ s+1 ]. (8)
If

Q s = s j=0 ΔQ j , E[Q] = L s=0 ⎛ ⎝ s j=0 ΔQ j ⎞ ⎠ P [ρ s X < ρ s+1 ], = L j=0 L s=j ΔQ j P [ρ s X < ρ s+1 ], = L j=0 ΔQ j L s=j P [ρ s X < ρ s+1 ], = L j=0 ΔQ j P [X ρ j ]. (9)
From a practical point of view, the algorithm considers the E[Q] change for each enable redundant value. Initially, no substream is transmitted: the protection level is equal to N + 1. The number of projections required to rebuild each substream is then decremented. This increases the protection and, therefore, the global rate. The expected quality corresponding to unequal protection for a given channel loss profile is calculated for each protection level.

The maximisation of expected quality constitutes the link between source and channel coding by jointly considering the properties of the source (quality increments) and the feedback from the channel (reception probabilities).

JOINT LAR AND MOJETTE IMAGE CODING

Image transmission applications need compression and secured transmission of sensitive data simultaneously. The securization process is applied here to preserve the integrity of the data. In some ways, the securization process can also preserve the progressive mode provided by the source coding. This section presents the results of the joint source channel image coding implemented by LAR and Mojette image coding.

Application to image transmission

The general joint coding scheme is represented in figure 10. Our application relates to the transmis-sion of the test image 'Angiot' (512 × 512, 8 bits). For that purpose the LAR compression scheme is used together with a simple arithmetic coder of zero order. An exponential distribution is retained for packet loss in order to validate our approach in the memory channel environment. A simple PSNR is used as a measurement of quality.

Lossless LAR coding is applied to the test image. The total rate is 5.05 bpp which can be divided into 6 substreams corresponding to 6 major steps of the Interleaved S+P compression. The first substream integrates both encoded data corresponding to the grid computed by the spatial coder, and the information resulting from level 4 of our multiresolution representation. Streams 2, 3 and 4 encode the estimation errors obtained during the first pyramidal decomposition for level 3, 2 and 1 of the pyramid respectively. At this stage, the reconstructed image corresponds to the LAR low resolution image. Adding bitstream 5 (texture information) recovers the half-resolution image (level 1, second pyramidal decomposition). Finally, bitstream 6 encodes the full resolution information losslessly. In this way, these six substreams correspond to the granularity of the protection where unequal redundant rates are allocated. Table 2 summarizes the properties of each substream in terms of size and quality increments. From this scalable description of the source, we carry out the optimal redundancy allocation described at §5.4, taking into account the increments in quality and the exponential loss profile.

Unequal protection is then applied to the entire stream (header and image data). In case of a geometrical Mojette code, it is characterized by the number of sufficient projections chosen from among the number N of sent projections. N is set here to 16 projections.

Figure 11 summarizes the rate distortion analysis for two joint source-channel coding : a reference one using Maximum Distance Separable (MDS) codes to which the Reed-Solomon codes belong and our scheme using Mojette transform. The analysis is performed in the lossy area for a mean packet loss equal to 10%. The three singularities observed correspond to the decision of the protection system to transmit an additional substream in order to achieve the target quality.

For example, an expected quality of 27.00 dB3 can be obtained by the protection function ρ = {9, 11, 14, 16, 17, 17}. The last two substreams are not transmitted here to reach this target. The size of projections is equal to 2400 bytes on average for an overall joint source channel coding rate equivalent to 1.172 bpp. This rate can be compared to the original LAR rate (1.07 bpp), giving a redundancy rate of 9%. This rate allows decoding even if the first packets are loss.

In a second example, the channel could provide a guaranteed and fixed bandwidth. In the lossless area, which is not given in the curve, if a redundancy rate of 6% is accepted for protection, i.e. an overall rate of 5.34 bpp, the lossless quality is expected thanks to the protection function ρ = {8, 10, 14, 14, 15, 16}. In this example, the loss of half of the transport units is compensated for in order to rebuild stream 1 (the most important part of the LAR coding). In this case, all substreams are transmitted.

Interleaved S+P

Scalable source coding

Mojette Transform & geometrical buffering

Performances

The low density of parity checks allows fast iterative decoding by the inverse Mojette transform. Critical substreams are naturally rebuilt first. Contrary to original LAR coding, the loss of the first projections is not prohibitive for decoding. Degradations are progressive whatever the position of erasure in the image flow. Projections have the same rebuilding capacity. Consequently, our method bears a resemblance to the MDS. For these coding systems, any M code words selected from among the N transmitted are enough to rebuild the message. The system presented is of the (1 + ε) MDS type where ε represents the necessary overhead for decoding. In the example depicted figure 11, the average overhead is about 2.78% . This overhead can be reduced when mean packet loss increases. At 20%, the overhead is 2.45% even if the protection increases. Geometrically speaking, if source rates are the same, the length of the geometrical buffer increases as protection reducing overhead. For infinite geometrical buffers, Mojette transform has MDS property. Typically, ε is about 2% for the transmission of a 512×512 image. But the complexity is linear with the number of information elements, I, and the number of projections, N , both for encoding and decoding whereas MDS decoding presents a complexity in O(Ilog 2 I) [START_REF] Lacan | Reed-Solomon Forward Error Correction (FEC)[END_REF]. In addition, the transform offers greater flexibility given that MDS codes are strongly constrained by the algebra of the Galois fields. So the Mojette transform more efficiently supports the highly gran-ular hierarchy delivered by LAR or any scalable coding.

Performances are also distinguishable when comparing the unequal error protection scheme (UEP) with the equal error equivalent (EEP). In packet transport mode, the use of forward error correcting (FEC) codes like Reed-Solomon (RS) codes authorizes the loss of units without compromising the transmission of the information. Their correction capacity for the whole stream can, in certain cases, include the following property: it is possible to rebuild the original stream in a deterministic way as soon as any M packets from among N are received. That describes the EEP: one equal level of redundancy for the whole stream. Decoding fails if more than N -M packets are lost. When exact rebuilding is impossible, it can be preferable to compensate for the errors rather than to correct them. This is the worthwhile feature of UEP which can deliver a degraded version when transmission is particularly disturbed.

Previous works have shown that the use of a lossily compressed image remains still an interesting feature for medical image purposes. As soon as the inherent distortions do not too much deteriorate the visual perception of the image, lossy compression appears as a suitable solution for telemedicine systems [START_REF] Oh | Medical Image Processing: from Lossless to Lossy Compression[END_REF]. Thanks to our adapted UEP strategy, our scheme assures a quality of service in terms of image quality, even in case of hard conditions of transmission: the reconstructed images can be exploited by medical experts for diagnosis purposes.

CONCLUSION

The LAR image coding method is a new scalable method which is not only efficient in terms of image quality for low bit-rates but also achieves an excellent compression ratio for losslessly encoded images. Each bitstream is associated with both a particular resolution level of the pyramid and a specific type of information (smooth areas or contours). This being so, losing a given bitstream leads to the reconstruction of the image at a limited resolution level. The LAR coder has the advantage of recovering low bitrate encoded images with good visual quality (e.g. no blocks or ringing effect).

The Mojette transform is then applied to each compressed bitstream provided by the LAR coder, providing hierarchical cost-controlled protection. All the projections and added redundancies are dispatched among the whole set of IP packets. Thus, as the cost of a Mojette transform only depends on the number of packets received and not on their contents, the decoder immediately launches a reconstruction process upon reception of each packet.

An original joint source-channel coding, based on LAR compression and Mojette transform, has been especially designed for Internet transmissions. In the application, a LAR encoder feeds data to the Mojette coder which behaves as a priority encoding system. The use of Mojette transforms to link the LAR to the priority encoding system provides a guarantee of end-to-end Quality of Service.

Fig. 1 .

 1 Fig. 1. Visualization of the grid produced by the spatial coder of the LAR method.

Fig. 2 .

 2 Fig. 2. Original application of the S-Transform pyramidal decomposition allows for a highly scalable transmission of compressed data.LAR pyramidal decomposition is based on an adaptation of the Wu predictor[START_REF] Wu | A Context-based, Adaptive, Lossless/Nearly-Lossless Coding Scheme for Continuous-Tone Images (CALIC)[END_REF]. For full resolution images, errors are coded by means of triple interlaced sampling of the original image. Consequently, we tend to obtain a spatial configuration of a 360˚type neighborhood surrounding a given pixel so that the resulting prediction error is drastically reduced.

Fig. 3 .

 3 Fig. 3. Second and third pass of the transformed coefficients prediction process.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Construction of the pyramid through two interleaved S-pyramids

Fig. 6 .Fig. 7 .

 67 Fig. 6. Near-lossless encoded image (1.966 bpp) and example of the ROI selection. Resolution Scalabity

Fig. 8 .

 8 Fig. 8. ROI coding using the self-extracting region representation. (a) LAR low resolution image (first descent, 0.55 bpp) -(b) 124 regions representation -(c) background encoded at low bit rate, ROI losslessly encoded

Fig. 11 .

 11 Fig.11. Rate/quality analysis of joint source channel coding for memory channel (mean packet loss of 10%) and PSNR measurement. The output rate includes LAR coding and MDS or Mojette protection. Three singularities correspond to the decisions to transmit refinement streams significantly improving the expected quality.

Fig. 10 .

 10 Fig. 10. General joint LAR-Mojette coding scheme.

Table 1 First

 1

			Entropy (bpp)
	Image	Size	S+P CALIC Int. S+P
	colon	512 × 512	3.53	3.33	2.87
	angiot	512 × 512	5.20	5.19	4.99
	us	512 × 448	3.78	3.60	3.55
	angio	512 × 512	3.11	3.10	3.10
	cr	1744 × 2048	3.30	3.30	3.27
	echo	720 × 496	3.28	3.41	3.44
	x ray	2048 × 1680	2.39	2.27	2.36
	mr head p	256 × 256	4.27	4.26	4.08
	mr thorax	256 × 256	4.60	4.71	4.61
	ct abdomen fr 512 × 512	2.61	2.54	2.61
	ct abdomen tr 256 × 256	3.43	3.38	3.43
	mdb001	1024 × 1024	1.64	1.60	1.26
	mdb005	1024 × 1024	2.19	2.13	1.80
	mdb007	1024 × 1024	1.91	1.86	1.53
	mdb023	1024 × 1024	2.11	2.04	1.83
	an01	512 × 512	3.22	3.03	2.75
	an02	512 × 512	3.13	3.19	3.30
	hd01	512 × 512	3.23	3.17	2.61
	ex03	512 × 512	3.88	3.88	3.97
	Average		3.20	3.16	3.02

-order entropy (bit/pixels) of the proposed Interleaved S+P (Int. S+P), CALIC and S+P.

  Fig.9. Three-level protection scheme with geometrical buffer separation. One packet construction is realized by concatenating the same angle projections. p a,b stands for the b th projection of the a th geometrical buffer.

						p 3,4
			p 2,4
	p 1,4	1 p 1,2	p 2,3	p 2,1	p 2,2	p 3,3	p 3,1	p 3,2
	p 1,3
			Geometrical buffer 2		Geometrical buffer 3
						Geometrical buffer projections
	Packet 1 = header + [p 1,1 , p 2,1 , p 3,1 ]	header
	Packet 2 = header + [p 1,2 , p 2,2 , p 3,2 ]	header
	Packet 3 = header + [p 1,3 , p 2,3 , p 3,3 ]	header
	Packet 4 = header + [p 1,4 , p 2,4 , p 3,4 ]	header
							Packets construction

Table 2

 2 Properties of the LAR substreams for the test image "Angiot" (512 × 512).

	Substream	1	2	3	4	5	6
	Size of layers	1.97 1.91 7.04 24.05 30.32 100.05
	(kbytes)
	Source	rate	0.06 0.12 0.33 1.07 1.99 5.05
	(w/o	protec-
	tion) (bpp)
	Quality incre-	23.05 2.00 0.92 2.95 1.09 20.00
	ments s (dB)

Tested images can be found on the following web site: http://eelmpo.cityu.edu.hk/imagedb/ and http://www. cis.rit.edu/htbooks/mri/inside.htm

Δ(m) = 1 if m = 0

The difference between resolutions explains the low level of PSNR.


Véronique Humbertclaude

Florence Riant

Benjamin Krams

Valérie Zimmermann

Nicolas Nagot

Daniel Annequin

Bernard Echenne

Elisabeth Tournier-Lasserve

Agathe Roubertie

Chrystelle Bonnemains

Cognitive impairment in children with CACNA 1A mutations

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


Ian O'connor

Zlatan Stanojevic

Oskar Baumgartner

Chhandak Mukherjee

Guilhem Larrieu

Jens Trommer

Cristell Maneux

Analysis of Energy-Delay-Product for a 3D Vertical Nanowire FET Technology for Logic Applications

published or not. The documents may come

L'archive ouverte

I. ENERGY DELAY PRODUCT

Energy-delay product (EDP) is a useful metric to compare the speed of energy-efficient circuits. While the power Delay Product (PDP) only measures the energy per function, it does not satisfactorily capture the speed. The EDP is written as, 𝐸𝐷𝑃 = 𝑃𝐷𝑃 * 𝑡 ! (1), where t p represents the propagation time. In a classical CMOS circuit, the PDP (or the switching energy) for a 0-to-1-to-0 computation cycle is defined by:

𝑃𝐷𝑃 = 𝐶 ! 𝑉 !! ! (2),
where C L represents the load capacitance on the gate output, and V DD represents the supply voltage.

The switching or propagation time can also be computed by

𝑡 ! = ! ! ! !! ! (3),
Here, I represents the current drawn from the voltage supply or sunk to ground to change the output voltage state (on-current). For the purposes of this comparison, we will assume that the transistor through which the current is flowing is primarily in the saturation region and that this on-current equates to the saturation current I sat of the transistor.

One can now write an expression for the EDP using (1)-(3):

𝐸𝐷𝑃 = 𝑃𝐷𝑃 * 𝑡 ! = ! ! ! ! !! ! ! !"# (4).

II. EDP IMPROVEMENT EQUATIONS

The EDP improvement of the VNWFET technology over the FinFET technology can therefore be expressed as:

𝐺 !"# = !"! ! !"! ! = ! !" ! ! !!" ! ! !"#$ ! !"#$ ! !" ! ! !!" ! (5)
where the subscripts f and v stand for the FinFET and VNWFET, respectively. We will assume that supply voltage values for both technologies are identical (i.e. V DDf = V DDv ), which simplifies (5) further:

𝐺 !"# = ! !" ! ! !" ! ! !"#$ ! !"#$ (6)

A. On-current (I sat ) considerations

We also assume that material current density and doping levels are identical for both technologies. This then implies that the transistor saturation current can be approximated as

𝐼 !"# = 𝜅 ! ! ! ! (7)
where κ is a constant that takes into account technology parameters and operating conditions, W g represents the effective width of the transistor channel under the gate orthogonal to current flow, and L g represents the length of the channel under the gate, i.e. the distance between source and drain. This also assumes that the transistor channel material is fully depleted (i.e. the channel occupies all the space available in the given geometrythis implies that the radius of the nanowire is sufficiently small, which may be a limiting technological factor). We can calculate W g according to the geometry of both FinFET and VNWFET devices:

𝑊 !" = 2 ℎ ! = 𝑤 ! , 𝑊 !" = 2𝜋𝑟 ! (8)
where W gf and W gv represent the effective widths of the Thus, the ratio between the saturation currents of both devices can be written as:

! !"#$ ! !"#$ = ! !" ! !" ! !" ! !" = !! ! ! ! !! ! ! !" ! !" (9)
In nanowire-based devices, the ratio of channel length L gv to channel diameter 2r v should be kept constant at 2:1 to preserve desirable behavior in the off state [STA16]. It is also important to avoid degradation of both ballistic and dissipative currents, which occurs with decreasing device size. In fact, ballisticity the ratio of dissipative to ballistic current) also degrades for very small devices, with channel lengths below around 10nm.

Both constraints combine to give:

L gv ≥ 10nm, r v = L gv / 4 ≥ 2.5nm (10) (a) (b)

B. Load capacitance (C L ) considerations

In terms of capacitance, we will, in a first approach, consider that load capacitance is composed of the input gate capacitance C in of F (fanout) logic gates on the output node, as well as interconnect capacitance C w . Hence,

C L = F(C in + C w ) (11)
Input gate capacitance is in turn composed of direct gate-channel capacitance C gc linked to the gate-channel area, and gate-source capacitance C gs linked to the spacer geometry, as written by,

C in = C gc + C gs (12)
1. Gate-channel capacitance The gate-channel capacitance can be expressed in terms of channel geometry for both devices as:

𝐶 !"# = ! !" ! !" ! ! ! !! ! !"# 𝐶 !"# = ! !" ! !" !!! ! !"# (13)
Here, C gcf and C gcv represent the gate-channel capacitance for FinFET and VNWFET devices, respectively; 𝜀 !" and EOT represent the dielectric permittivity for standard SiO 2 and the equivalent oxide thickness for the gate dielectric material, respectively. We assume that the gate dielectric material is identical for both technologies. EOT, defined as:

𝐸𝑂𝑇 = 𝑡 !!"!!! ! !" ! !!"!!! (14),
is around 0.89nm in current technologies.

Gate-source capacitance

The gate-source capacitance can be expressed in terms of spacer geometry for both devices as:

𝐶 !"# = ! ! !! !" !! !" !! ! !! ! ! !" 𝐶 !"# = ! ! ! ! !" !! ! ! !!! ! ! ! !" (15)
where C gsf and C gsv represent the gate-source capacitance for FinFET and VNWFET devices, respectively; t gf and t gv represent the gate material thickness for FinFET and VNWFET devices, respectively and can be typically assumed to be between 10nm-20nm; L sf and L sv represent the spacer length (between gate and source) for FinFET and VNWFET devices, respectively, and can be typically assumed to be around 8nm; 𝜀 ! represents the spacer material dielectric permittivity. We assume that the spacer material (typically Si 3 N 4 ) is identical for both technologies and that there are no fabrication issues for different dielectric materials for the gate (high-k) and for the spacer. We also assume that the gate material surrounds the channel with uniform thickness (overlap) equal to t gf for the FinFET (although the lateral thickness is actually defined by FinFET pitch); and is a square centered around the nanowire with minimum overlap equal to t gv for the VNWFET. Note that this expression does not take into account fringing capacitances (a reasonable assumption since this is not the dominant component). Hence one can write,

𝐶 !"# = ! !" ! !" ! ! ! !! ! !"# + ! ! !! !" !! !" !! ! !! ! ! !" 𝐶 !"# = ! !" ! !" !!! ! !"# + ! ! ! ! !" !! ! ! !!! ! ! ! !" ( 16
)
3. Wire capacitance Wire capacitance is considered for local (gate-to-gate) interconnect, expressed as:

𝐶 ! = ! !" ! ! ! !! ! !" (17)
where w m and L gg represent the width and length of local (gate-to-gate) interconnect respectively; and t ox represents the metal-substrate oxide thickness for interlayer dielectric SiO 2 . L gg can be directly linked to circuit compactness since it represents the lateral distance (pitch) between two gates. For a given improvement in compactness A c between VNWFET and FinFET (i.e

. A c = A f /A v ), ! !!" ! !!" = 𝐴 ! (18)
For this analysis, we assume that A c is a constant and of the order of 5 according to [MUK20], although it is anticipated that it will vary (negatively) with increasing number of fins per FinFET / nanowires per VNWFET. This will require further analysis once an automated 3D place and route tool is available. This tends also to support the view that a) VNWFET-based design performance improves for lower numbers of nanowires per VNWFET -not only for the pitch overhead, but also because the oncurrent varies sublinearly with the number of nanowires per VNWFET. b) computing should be kept local to enable short interconnect and limit energy consumption in parasitic elements (particularly important for mobile low power applications). The N 2 C 2 (neural network compute cube) concept is exactly this -a regular 3D matrix of individual compute functions where intracube interconnect is short due to both the limited complexity of the N 2 C 2 circuit and the targeted limited number of nanowires per VNWFET. While the locality of computing is a known technique to limit the impact of interconnect delay on computing, the N 2 C 2 concept goes beyond current planar state of the art by extending this principle to 3 dimensions.

Assuming identical values for 𝜀 !" , t ox and w m between the FinFET and VNWFET technologies, we can also write:

! !" ! !" = 𝐴 ! (19)
4. Overall expressions for the load capacitances Leveraging (19) one can write the expression for the load capacitances in the two cases as,

𝐶 !" = 𝐹 𝐶 !"# + 𝐶 !"# + 𝐶 !" 𝐶 !" = 𝐹 𝐶 !"# + 𝐶 !"# + ! !" ! ! (20)
where C Lf and C Lv represent the load capacitances on FinFET and VNWFET logic gate outputs, respectively. Thus, the ratio between the load capacitances of both devices can be written as:

! !" ! ! !" ! = ! !"# !! !"# !! !" ! ! !"# !! !"# ! ! !" ! ! ! (21)
finally, the EDP gain can be expressed as,

𝐺 !"# = ! !" ! ! !" ! ! !"#$ ! !"#$ = ! !"# !! !"# !! !" ! ! !"# !! !"# ! ! !" ! ! ! ! !"#$ ! !"#$ (22)
Which can be further re-written in terms of geometric parameters as,

𝐺 !"# = ! !" ! !" ! ! ! !! ! !"# ! ! ! !! !" !! !" !! ! !! ! ! !" !! !" ! ! !" ! !" !!! ! !"# ! ! ! ! ! !" !! ! ! !!! ! ! ! !" ! ! !" ! ! ! !! ! ! ! !! ! ! !" ! !" (23)
III.

EDP GAIN ANALYSIS

For a FinFET aspect ratio (h f /w f ) value of 60nm/7nm with 20nm physical FinFET gate length L gf , and by varying the value of physical VNWFET gate length L gv between 10nm-20nm for a nanowire radius r v of 4nm, the EDP gain value varies as shown in Fig. 3. The results show that (for example) 10x gain in EDP between VNWFET and 7nm FinFET technology can be achieved for L gv =14nm.

Fig. 1 :

 1 Fig. 1: FinFET geometry (a) 3D view (b) lateral view.

Fig. 2 :

 2 Fig. 2: VNWFET geometry (a) 3D view (b) lateral view

Fig. 3 :

 3 Fig. 3: EDP-gain versus VNWFET gate length