Keywords:

Terminology. Different terms are used for the same idea:

-data compression = source coding, -protection against channel noise = channel coding, -protection against channel disturbances = protection against noise, but also against any other disturbances such as: multipath in wireless transmissions, or multiuser interferences, ...

Universal communication: a separable problem into source and channel coding.

For the classical model (see Fig. 1.1) of a source with a single output and a channel with a single input and a single output, [START_REF] Shannon | A mathematical theory of communication, Part I, Part II[END_REF] showed that separation between (i) source coding, (where all the redundancy in the source is removed) and (ii) channel coding (where a minimum of redundancy is added in order to remove the effect of the channel noise) is optimal. In other words, optimizing the two problems separately and connecting the two solutions obtained in series (as in Fig. 1.2) is optimal. Moreover, this separation principle holds quite generally, even when the source and channel statistics are unknown [46, compression theorem is a consequence of the AEP, which shows that there exists a "small" subset (of size 2 nH ) of all possible source sequences that contain most of the probability and that we can therefore represent the source with a small probability of error using H bits per symbol.

The data transmission theorem is based on the joint AEP; it uses the fact that for long block lengths, the output sequence of the channel is very likely to be jointly typical with the input codeword, while any other codeword is jointly typical with probability ≈ 2 -nI . Hence, we can use about 2 nI codewords and still have negligible probability of error. The source-channel separation theorem shows that we can design the source code and the channel code separately and combine the results to achieve optimal performance.

SUMMARY

Channel capacity. The logarithm of the number of distinguishable inputs is given by C = max p(x)

I (X; Y ).

Examples

• Binary symmetric channel: C = 1 -H (p).

• Binary erasure channel: C = 1α.

• Symmetric channel: C = log |Y| -H (row of transition matrix).

Properties of C

1. 0 ≤ C ≤ min{log |X|, log |Y|}.

I (X; Y ) is a continuous concave function of p(x).

Joint typicality. The set A (n) of jointly typical sequences {(x n , y n )} with respect to the distribution p(x, y) is given by source coding and channel coding.

A (n) = (x n , y n ) ∈ X n × Y n : (7.151) - 1 n log p(x n ) -H (X) < , ( 7
Challenges for the universal compression of visual data. The question of universal data compression has been dealt with statistics and information theory. It was shown that, when the source probability distribution is unknown, the data can still be compressed. Moreover, the compression rate is the same with or without the probability distribution knowledge, when the length of the data tends to infinity. This is the case, in particular, with the Lempel-Ziv codes [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF][START_REF]Compression of individual sequences by variable rate coding[END_REF]. At finite length, however, universality has a cost of the order of O(log(n)/n) [START_REF] Csiszar | Information theory and statistics: A tutorial[END_REF]Th. 7.5], where n is the length of the data sequence to be processed. This is a positive result as this cost is small, and vanishes as the length n tends to infinity. However, this extra amount O(log(n)/n) of data to be transmitted due to universality holds only for very restricted classes of probability distributions. In particular, there exists no universal code for the class of stationary ergodic processes [START_REF] Shields | Universal redundancy rates do not exist[END_REF]. Instead, for certain subclasses, such as the identically and independently distributed (i.i.d.), or the order k Markov processes, this cost is O(log(n)/n), where the multiplicative scaling factor depends on the number of parameters needed to identify a distribution within the class [START_REF] Csiszar | Information theory and statistics: A tutorial[END_REF]Th. 7.5]. This is a negative result for visual data, which are notoriously neither stationary nor ergodic. Therefore the challenges in compressing visual data are to efficiently (i) model the visual data, (ii) code the model, and (iii) code the data according to the model. These problems will be discussed in Chap. 2.

Challenges for the universal transmission of data. If universality does not incur any loss in data compression (at least asymptotically), this is not the case for the transmission over noisy channels. Indeed, when the channel statistics are not known, the best performance is determined by the worst channel [START_REF] Han | Information-spectrum methods in information theory[END_REF]Th. 3.2.1]. To compensate for this negative result, a feedback channel, if possible, is used to inform the encoder of the channel statistics. This method consists in (for the more complex case of multipath channels) (i) sending a learning sequence known by both the encoder and decoder, (ii) estimating of the channel characteristics (noise level, channel impulse response) at the receiver, and finally (iii) sending information about the channel from the receiver to the encoder through a feedback channel. However, with the advent of turbo-codes [START_REF] Berrou | Near Shannon limit error-correcting coding and decoding: Turbo-codes[END_REF], this approach had to be revisited. Indeed, turbo-codes were the first practical codes to operate at the optimal level predicted by C. Shannon in [START_REF] Shannon | A mathematical theory of communication, Part I, Part II[END_REF]. In other words, they were able to operate at a much higher noise level than all its predecessors, such that the whole communication chain, in particular the channel estimation, had to operate at a higher noise level to benefit from the decoding performance of turbo-codes.

Therefore, the challenges for the universal transmission of data are to efficiently (i) estimate the channel even for high noise level and (ii) dimension the system. These problems will be discussed in Chap. 3.

Challenges for the universal transmission of visual data, when the separation principle does not hold. The separation principle holds if the system is unconstrained in terms of complexity (source and channel code are indeed optimal), or delay (adding the necessary amount of redundancy to combat the channel noise is possible) [START_REF] Duhamel | Joint Source-Channel Decoding: A Cross-Layer Perspective with Applications in Video Broadcasting over Mobile and Wireless Networks[END_REF]Sec. 2.2]. For constrained systems, joint source channel coding/decoding must be applied instead. This problems will be discussed in Sec. 3.2.

Notations:

-Upper case letters X, Y, . . . refer to random variable, random process or a source, -Calligraphic letters X , Y, . . . refer to alphabet, the subset of R in which the random variable takes its values -|A| is the cardinality of the set A -X j i = (X i , X i+1 , . . . , X j ) is a (j-i+1)-sequence of random variables or a random vector X n = (X 1 , X 2 , . . . , X n ), the index in the above notation is dropped when i = 1, -Lower case x, y, . . . and x n , y n , . . . mean realization of a random variable, or realization of a random vector. -A * is the set of finite strings over the alphabet A.

Chapter 2

Compression and universality

Universal compression, or universal source coding, is the problem of compressing a data source without knowledge of the source probability distribution. This occurs in particular when images and videos have to be compressed. A natural question to ask is whether universality has a cost compared to the case where the statistics are known. A second question is whether practical codes exist, which achieve the optimal performance of universal source coding. Surprisingly, the latter question is rarely covered in references on source coding for image and video. This text offers a review of these ideas. The presentation does not follow a historical order. It is rather focused on the application to image and video, by first presenting the theory of universal source coding and then describing practical implementations used in video coding. This review constitutes a contribution per se.

This chapter is organized as follows. First, Section 2.1 reviews the problem of lossless data compression under the condition that the probability distribution is perfectly known. Section 2.2 reviews that, in universal lossless data compression, there is an excess rate (in bits per source symbol), which vanishes as the sequence length goes to infinity. This excess rate is of the order of O(log(n)/n) for a large variety class of stationary ergodic sources, where n is the source input length. Then, two practical implementations are presented which achieve the same excess rate. Section 2.4 presents fundamental principles for image and video coding. Finally, Section 2.5 introduces my contributions, which are detailed in Sections 2.6 to 2.9. For easier reading, each main result is first summarized in a sentence in bold, and then further developed.

Lossless data compression

Let us consider a source X on the discrete alphabet X . This source generates a random process, which is defined as a sequence of random variables (X n ) n≥0 with probability distribution P . Let P n be the marginal distribution on X n of the distribution P . Now, a source sequence is encoded with a code C n defined by an encoding function f n and a decoding function g n . In this section, the probability distribution P is known at both the encoder and the decoder such that the code mappings f n , g n depend inherently on P .

Different types of codes C n exist to compress the input data sequence x n . It can be with fixed (FL) or variable length (VL), and without error for all lengthsn (zero error) or only asymptotically (see Table 2.1 for the definitions of the properties of the code).

For a FL code, the encoding function assigns to each source sequence of length n, x n , a fixed-length codeword. In other words, given the source sequence length, all codewords have the same length, such that each codeword can be seen as an index taken from an set.

CHAPTER 2. COMPRESSION AND UNIVERSALITY

Property

Definition FL fixed length the length of the coded sequence is the same for all input sequences VL variable length the length of the coded sequence depends on the input sequence zero error ∀n∀x n , g n (f n (x n )) = x n asymptotically the probability of error P n e tends to zero error free as the input sequence length n → ∞ The compression rate R ∈ R + is the ratio between the codeword length in bits and the source sequence length, and is therefore expressed in bits per source symbol : R = number of bits to represent a codeword n bits per source symbol.

(2.1)

The encoding and decoding functions depend explicitly on the compression rate and are f n : X n → {1, . . . , 2 nR }, g n : {1, . . . , 2 nR } → X n , respectively. For ease of presentation, we assume that the entries of the codewords are bits. Generalization to larger alphabets requires a scaling factor to take into account the codeword alphabet size. For a VL code, the encoding and decoding functions are f n : X n → {0, 1} * and g n : {0, 1} * → X n . Indeed, the encoding function assigns to each source sequence x n , a codeword, whose length depends on the sequence x n . The compression rate is defined as the ratio between the average length of the codewords and the input sequence length:

R = log E X n [ (f n (X n ))] n bits per source symbol (2.2)
where (.) stands for the function giving the binary length of the codeword. Finally, for both FL and VL codes, the probability of error denoted P n e depends on the input length n, and is the probability that the decoded sequence differs from the input sequence:

P n e = P (g n (f n (X n )) = X n ) . (2.
3)

The goal of lossless source coding is to find the lowest compression rate R such that the probability of decoding error decays asymptotically to zero with the input length n, or even such that there is no error (f n (g n (.)) is the identity). In the class of stationary ergodic sources defined on a discrete alphabet, the optimal compression rate for lossless encoding while knowing the probability distribution, is the entropy rate. This holds for FL and VL codes. If the source X is stationary and ergodic, defined on a discrete alphabet X , with probability distribution P known at both encoder and decoder, then the optimal compression rate for FL codes [START_REF] Han | Information-spectrum methods in information theory[END_REF]Th 1.3.1,Ex. 1.3.2] and VL codes [START_REF] Han | Information-spectrum methods in information theory[END_REF]Th 1.7.1,Rk. 1.7.3.] are both equal to:

H(P ) = lim n→∞ 1 n H(X n ) = lim n→∞ 1 n H(X n |X n-1 )
bits per source symbol, (2.4) with H(X n ) = -

X n ∈X n P n (X n ) log 2 P n (X n ). (2.5)
H(X n ) is called the entropy of the random vector X n with joint distribution P n and H(P ) is the entropy rate. The second equality in (2.4) follows because the source is stationary. Optimality here means that not only there exists a code that achieves this rate, but also that there is no code that can achieve a smaller rate. For instance, in the special case of a an i.i.d. source, the compression rate in (2.4) reduces to the entropy of the source ). These optimal VL codes are zero error, whereas the optimal FL code is only asymptotically error free.

H(X) = - x∈X P (x)

Universal source coding and its theoretical cost

This section tackles the more realistic and interesting setup, where the distribution of the source is known neither at the encoder nor at the decoder. This problem is referred to as universal source coding. The goal of the section is to review the optimal compression rate that can be achieved for universal source coding, and compare it to the case where the probability distribution is known. If the probability distribution is available at both encoder and decoder, the code will be called distribution-aware code, or aware code. Similarly, when the distribution is neither available at the encoder nor at the decoder, we will call the code a distribution-unaware code, or an unaware code. In this context, a distribution unaware code is said to be universal if it achieves the same asymptotic compression rate as a distribution aware code.

The discussion concerns stationary ergodic sources as in the previous section, where the probability distribution of the source is known (see Sec. 2.1). However, two restrictions to this distribution ensemble will be made. First, the alphabet is not only discrete as in the previous section, but it even needs to be finite. Indeed, the necessary and sufficient condition [START_REF] Kieffer | A unified approach to weak universal source coding[END_REF] for approaching a distribution, and therefore for the existence of a universal code, is not satisfied for discrete distributions even with finite entropy [START_REF] Gassiat | Codage universel et identification d'ordre par sélection de modèles[END_REF]Th. 3.2.1]. Second, the class of distributions can not be too large. Indeed, there exists no universal code for the class of stationary ergodic processes [START_REF] Shields | Universal redundancy rates do not exist[END_REF] or for the class of Markov processes of an unknown finite order [START_REF] Shields | Universal redundancy rates for the class of b-processes do not exist[END_REF].

Formally, let X be a source on the finite alphabet X with stationary ergodic distribution P . Let P n be the marginal distribution on X n of the distribution P . In the following, we will consider subclasses P of the class of stationary ergodic distributions. In the context of universal coding, it is clearer to write the entropy (2.6) of a source as a function of the distribution: [START_REF] Han | Mathematics of Information and Coding[END_REF]Th. 3.21] from the one formulated above. More precisely, [START_REF] Han | Mathematics of Information and Coding[END_REF]Th. 3.21] concludes the existence of FL universal codes. This is due to the fact that in the latter Theorem, it is assumed that the probability distribution is not known but that its entropy is known, which allows to determine the compression rate. Then, since the coding scheme is FL and does not depend on the probability distribution but on its rate only, it is concluded that there exists universal FL code. Here instead, it is assumed that when the distribution is not known, neither the distribution nor any statistics are known. In particular, the entropy of the true distribution is not known.

H(P ) = - x∈X P (x) log 2 P (x) (2.
Optimizing a VL code is equivalent to optimizing a probability distribution for decoding. VL coding can lead to ambiguity while decoding a sequence of codewords, since the parsing may not be unique. Since the goal is lossless compression, only injective encoding functions are considered, which are referred to as uniquely decodable VL codes. Then, [START_REF] Cover | Elements of information theory[END_REF]Th. 5.5.1.] states that there is a one-to-one correspondence between a uniquely decodable VL code with codeword set C and the set of codeword lengths { (c), c ∈ C} satisfying the Kraft inequality c∈C 2 -(c) ≤ 1.

(2.9)

Formally, -For any uniquely decodable code C, the set of codeword lengths satisfies (2.9) -Conversely, if the mapping : C → N satisfies (2.9), then there exists a uniquely decodable code with length mapping : C → N. Moreover, this length mapping defines a probability distribution. Indeed, -if the mapping : C → N satisfies (2.9), then

Q(c) = 2 -(c) is a quasi-probability distribution since c∈C Q(c) = c∈C 2 -(c) ≤ 1.
One only needs to add a codeword s.t. c Q(c) = 1 on the extended set to build a probability distribution. -Conversely, if Q is a probability distribution on C, then (c) =log 2 (Q(c) is a length mapping that satisfies (2.9), since c∈C 2 -(c) ≤ c∈C Q(c) = 1. Therefore, there is a one-to-one correspondence between probability distributions and uniquely decodable codes. Optimizing a code is thus equivalent to finding the best probability distribution for decoding.

There exists a practically implementable VL code, called arithmetic code, that is optimal. Indeed this code belongs to the the set of prefix codes, a subset of uniquely decodable codes, but still achieves the same compression gain as uniquely decodable codes. Moreover, it is a practical scheme as it allows to encode a sequence sequentially and use a distribution learned on the fly. A prefix code is such that no codeword is a prefix of any other codeword. Consequently, the code allows instantaneous or more precisely sequential decoding, and the set of prefix codes is a subset of the uniquely decodable code set. Interestingly, prefix codes and uniquely decodable codes achieve the same optimum compression gains. Indeed, prefix codes and uniquely decodable codes satisfy the Kraft inequality [26, Th. 5.2.1, Th. 5.5.1]. So, without loss of optimality, we can consider prefix codes.

One possible prefix code is the arithmetic code [START_REF] Cover | Elements of information theory[END_REF]Sec. 13.3] that encodes a sequence using fixed-precision arithmetic. This method is appreciated for its complexity that is linear in the length of the sequence, but also because it allows to encode sequentially and use a source distribution that is learned on the fly. Therefore arithmetic coding is naturally used in universal compression.

Criteria for optimal VL universal code. To evaluate the quality of a code built from an arbitrary distribution Q n , we compute the difference between the codeword lengths obtained with the encoding distribution Q n , and the optimal code (built from the true distribution P n ). This leads to the loss: -The universal code optimal according to the Minimax regret (worst case over the sequence and over the distribution) is given by the Normalized Maximum Likelihood (NML) distribution.

L(x n ) = -log Q n (x n ) + log P n (x n ) bits
First, the loss is computed for the worst input sequence, which is called the regret (see Table 2.2). Then, this regret is evaluated for the worst distribution of the class. The reason for computing this Maximum regret is that it allows to analyze uniform convergence over the distribution class P. Finally, the code distribution that minimizes the Maximum regret, is called the optimal distribution for the Minimax regret, which is defined in Table 2.2.

Criterion Definition Regret R * (Q n |P n ) = max x n log P n (x n ) Q n (x n ) Maximum regret R * (Q n |P) = sup P ∈P max x n log P n (x n ) Q n (x n ) Minimax regret R * (P) = inf Qn sup P ∈P max x n log P n (x n ) Q n (x n )
P n (x n ) Q n (x n ) = Q NML n : z n → sup P ∈P P n (z n ) y n sup P ∈P P n (y n ) (2.11)
So, in practice, given a set of distributions P, the optimal code that achieves Minimax regret (uniformly over the class P) can be computed by: 1. for each input sequence z n , compute the length of the coded sequencelog Q NML n (z n ) 2. find the codewords as in [26, Th. 5.5.1.] (Kraft inequality) -The universal code optimal according to the Minimax redundancy (average case over the sequence and worst case over the distribution) is given by a mixture distribution.

The regret computes the worst case loss. One can instead compute the average loss, which is also called the redundancy. Then, as for the regret, the Minimax redundancy is derived, see Table 2.3, where D(P n ||Q n ) stands for the Kullback-Leibler divergence between the probability distributions P n and Q n .

Criterion Definition Redundancy R(Q n |P n ) = E X n ∼Pn log P n (X n ) Q n (X n ) = D(P n ||Q n ) Maximum Redundancy R(Q n |P) = sup P ∈P D(P n ||Q n ) Minimax Redundancy R(P) = inf Qn sup P ∈P D(P n ||Q n )
Table 2.3: Definition of the Minimax redundancy.

The Maximin theorem allows to compute the optimal distribution [27, Sec 7.2]. If the set of probability distribution is equipped with a probability measure µ, the inf and sup can be exchanged (second equality in (2.12)). Then, the infimum is attained for the mixing measure (2.14). This estimate is analog to the Bayesian method in statistics. Finally, the optimal coefficients μ for the mixture are obtained by solving the supremum (2.13).

R(P) = inf

Qn sup

P ∈P D(P n ||Q n ) = sup µ inf Qn P D(P n ||Q n )dµ(P n ) (2.12) = sup µ D(P n ||Q * n (µ)) = D(P n ||Q * n (μ)) (2.13)
where

Q * n (µ) = P P n dµ(P n ) (2.14)
When the class of distributions is parametrized by a parameter θ, the optimal mixing measure μ in (2.13) is the input distribution achieving the capacity of a channel with input θ and output x n , the sequence to be compressed [START_REF] Cover | Elements of information theory[END_REF]Th 13 For a large variety of stationary ergodic processes, Minimax regret and minimax redundancy grow as # of parameters universal coding does not incur any asymptotic loss with respect to distribution aware coding. In this paragraph, a function which is asymptotic equivalent to the minimax regret and to the minimax redundancy is reviewed. To do so, we can first notice that minimax redundancy Rn (P) and regret R * n (P) satisfy ∀n, ∀P

Rn (P) ≤ R * n (P) (2.15)
which follows from the definition of the redundancy (average case), and of the regret (worst case). Then, the strategy will be to derive a lower bound for the minimax redundancy, and then an upper bound for the regret, by mean of a specific code construction. However, to do so, we need to restrict to a subclass of probability distributions P within the class of stationary ergodic processes, since the redundancy does not exist [START_REF] Shields | Universal redundancy rates do not exist[END_REF] for the whole class of stationary ergodic sources.

A lower bound for minimax redundancy. For the parametric class of processes [START_REF] Csiszar | Information theory and statistics: A tutorial[END_REF]Th. 7.4], the minimax redundancy is bounded below by

P = {P θ , θ ∈ Θ ⊆ R k } [
k 2 log n -K ≤ Rn (P) (2.16)
where K is a constant, provided there exists an estimator θn :

X n → Θ, whose error is upperbounded by O(1/n).
In other words, provided that the class of distribution P is learnable, a lower bound of the minimax redundancy scales as # of parameter 2 log n. This result can be instantiated for many subclasses, such as those in Table 2.4: i.i.d., Markov and compound process [START_REF] Han | Mathematics of Information and Coding[END_REF]Sec. 3.1.9.]. Given a family of memoryless probability distributions P = {P (.|s), s ∈ S} defined on the alphabet X , a compound source is such that a probability distribution is chosen and used from the beginning to the end.

An upper bound for minimax regret. The upper bound follows an achievability argument. More precisely, the code based on the NML distribution is used, and by definition of the minimum, the minimax regret is necessarily smaller than the Maximum regret achieved by NML. Interestingly, the resulting upper bound for minimax regret achieves the same growth rate as (2.16). Therefore, the minimax regret and redundancy are asymptotically equivalent and satisfy [27, Th. 7.5.]

r(n) -K 1 ≤ Rn (P) ≤ R * n (P) ≤ r(n) + K 2 (2.17)
where the function r(n) and the constants K 1 , K 2 depend on the class of distributions considered P, see Table 2

CHAPTER 2. COMPRESSION AND UNIVERSALITY

An important consequence of this result is that, for all the classes of processes in Table 2.4, the excess rate (in bit per source symbol) vanishes asymptotically:

lim n→∞ 1 n Rn (P) = lim n→∞ 1 n R * n (P) = 0, (2.18)
and the convergence rate of the excess rate is

# of parameters 2 • log n n . (2.19)
So, VL universal coding does not incur any asymptotic loss with respect to distribution aware coding.

The two-part algorithm (estimate the distribution, encode it, and encode the data with the estimated distribution) achieves the same growth rate as the minimax regret for a large variety of probability class P. Unfortunately, the direct implementation of the one-part code using NML distributions, which achieves the optimal redundancy, is impractical. Indeed,

{Q NML n } n does not define a process distribu- tion, since Q NML n is not the marginal of Q NML n+1
. So, a practical scheme based on NML must process the sequence as a whole. More precisely, for a given input sequence length n, one needs to (i) compute the probability distribution Q NML n , (ii) determine the length of each input sequence (i.e. ∀x n , computelog Q NML n (x n )), and finally (iii) find the codewords as in [START_REF] Cover | Elements of information theory[END_REF]Th. 5.5

.1.] (Kraft inequality).

Instead, the two-part algorithm (also called two stage in [START_REF] Csiszar | Information theory and statistics: A tutorial[END_REF]), is the very simple and natural way to implement universal coding [START_REF] Rissanen | Modeling By Shortest Data Description[END_REF]. It consists of:

-estimating the distribution, and encoding it.

-encoding the data sequence x n according to the estimated distribution. The difficulty of the two-part algorithm lies in the encoding of the distribution [45, p.16, chap. 5]. First attempts to solve this problem considered avoiding encoding the distribution, which led to the one-part universal coding scheme (2.14) and (2.11). Fortunately, the distribution encoding problem has been solved in [START_REF] Barron | Minimum complexity density estimation[END_REF]. This allowed to show that the two-part algorithm achieves the same growth rate as in Table 2.4 for a large variety of distribution class [45, chap. 15]. For instance, for the class of i.i.d. processes, the optimal distribution estimate is the type (that counts the occurrence of each symbol), and the growth rate is

|X |-1 2 log n [27, Example 6.1].
Historically, the two-part algorithm was proposed in [START_REF] Rissanen | Modeling By Shortest Data Description[END_REF], before the one-part algorithm [START_REF]Universal coding, information, prediction and estimation[END_REF]. Indeed, coding in two parts seems a very natural and practical way to tackle universality. However, it leads to the difficult problem of finding a good code for the distribution. This was the motivation for finding a one part code, that avoids to code the distribution.

Another practical and minimax optimal two-part algorithm: encode the ith symbol based on the distribution estimated from the first i -1 symbols. Another practical scheme consists in a sequential learning and encoding approach. At iteration i, -estimate the distribution based on the first i -1 symbols of the sequence, -encode the i-th symbol of the sequence based on the estimated distribution. Without loss of optimality, the encoding of the sequence can be performed with a prefix code which allows sequential encoding such as arithmetic coding (see the Paragraph on prefix codes p. 12), such that the decoder, upon decoding of the i-th symbol has access to the first i -1 symbols and can reconstruct the distribution estimate. Therefore, there

UNIVERSAL SOURCE CODING IN A WIDE SET OF DISTRIBUTIONS

is no need to encode the distribution estimate. This represents a gain with respect to the two-part algorithm described above. However, the encoding is suboptimal since the distribution estimate is less accurate. On the whole, both effects compensate, and it is shown that this sequential encoding achieve the same growth rate as the NML scheme, [START_REF] Csiszar | Information theory and statistics: A tutorial[END_REF]Th. 6.3] for i.i.d. processes, and [27, Th. 6.5, Th 6.6] for Markov processes.

Universal source coding in a wide set of distributions: the model selection problem and the minimum description length principle

Universal coding over large distribution sets (for which minimax criteria don't exist) leads to a model selection problem. Universal coding refers to the problem of compressing an input sequence with minimum coding length, when the distribution of the input sequence is unknown. Section 2.2 showed that we can construct universal codes, i.e. codes whose length has the same growth rate as a distribution-aware code, according to a minimax criterion, i.e. with uniform convergence over the set of possible distributions.

Unfortunately optimizing with the minimax criterion can only be solved within a rather small set of distribution. Indeed, for large classes such as the set of ergodic stationary processes [START_REF] Shields | Universal redundancy rates do not exist[END_REF] or the set of Markov processes of an unknown finite order [START_REF] Shields | Universal redundancy rates for the class of b-processes do not exist[END_REF], quantitative characterizations of minimax criteria do not exist. Instead, the search spaces must be small set of distributions, (for instance the set of i.i.d processes, or the set of Markov processes of order m, for some fixed m).

One way to deal with larger classes, is to remove the uniform convergence condition. The goal becomes: seek a code that achieves the same asymptotic length as a distributionaware code, but non-uniformly i.e. with a convergence rate that depends on the distribution. Such a code is said to be weakly universal, and by contrast a strongly universal code refers to a universal code with uniform convergence over the distribution set. For instance, the Lempel-Ziv code [START_REF] Ziv | A universal algorithm for sequential data compression[END_REF][START_REF]Compression of individual sequences by variable rate coding[END_REF] is weakly universal over the set of stationary ergodic processes defined over a finite alphabet [43, p. 31].

There is another way to construct a universal code ranging over a wide set of distributions without completely sacrificing strong universality. It consists in selecting nonuniformly the best distribution class, while selecting uniformly the distribution within the class. This method is referred to as the Minimum Description Length (MDL) principle [START_REF] Rissanen | Modeling By Shortest Data Description[END_REF][START_REF] Grunwald | The Minimum Description Length Principle[END_REF][START_REF] Barron | The minimum description length principle in coding and modeling[END_REF], and is one way to solve the more general model selection problem.

To formalize MDL, we review some terminology. Following [45, p. 15] [86, p. 14], a model refers to a set of probability distributions of the same form, e.g. the "i.i.d. model", or the "first-order Markov model". A model class instead refers to a family of models, e.g. "the Markov class" (the model class of all Markov chains of each order). An hypothesis, (also called point hypothesis in [45, p. 15]) is an instantiation of a model. It refers to a single distribution, e.g. a Markov chain of a fixed order, with all parameter values specified.

The idea behind MDL is that "the statistical model best fitting to the data is the one that leads to the shortest description, taking into account that the model itself must also be described" [START_REF] Csiszar | Information theory and statistics: A tutorial[END_REF]Sec. 8.2]. This principle can be instantiated with a two part universal CHAPTER 2. COMPRESSION AND UNIVERSALITY code, and the optimal model is then:

q M DL = arg min q∈Q L(q) one model + L(Q q )
one distribution within the model one hypothesis

+ L(x n |Q q ) data (2.20)
where L(q) bits allow to identify the model M q within the model class, L(Q q ) bits allow to identify one distribution Q q within the model M q , L(x n |Q q ) bits allow to encode the sequence x n using the coding distribution Q q . The notation L refers to both coding and counting the length of the coded sequence. To illustrate these definitions with an example, we can consider the Markov class {M q } q∈Q , where q stands for the order of the Markov distribution. Here, model selection is therefore equivalent to identifying the chain order that best fits the data. To identify an hypothesis, i.e. a distribution, first the order has to be coded with L(q) bits, and then the parameter of the distribution with L(Q q ) bits. If the chosen order is 0 (i.i.d. process), the parameters of the distribution are the type (the histogram). Finally, the data sequence x n = (x 1 , ..., x n ) is compressed, with an arithmetic code [START_REF] Cover | Elements of information theory[END_REF]Sec. 13.3].

The MDL principle can also be implemented with a one part universal code [START_REF]Universal coding, information, prediction and estimation[END_REF] and the model selection becomes:

q M DL = arg min q∈Q L(q) one model + L(x n |M q ) data (2.21)
where L(x n |M q ) is the codelength of the data obtained with a minimax optimal code. However, in the following, we will rather focus on two-part universal code, as there exists practical implementations of these two-part codes, that remain minimax optimal.

The model selection problem results from the fact that there is no redundancy rate for large classes of processes. The question of model selection arises in many problems where a task has to be performed, which depends on the distribution of the data, and when this distribution is unknown. Compression, as discussed here, is an example, but any learning task such as prediction or classification are other examples. A very natural approach is then to first estimate the distribution or the function (for prediction, classification), and then process the data. The estimation then poses a new question: how many parameters in the function, or in the distribution should be chosen? The discussion about universal compression and the construction of the one part universal code shows that there is no need to estimate the distribution, and therefore no need to estimate the order of the model if the set of the possible distributions is limited. In other words, it is only because redundancy rates don't exist for large classes of processes that indeed model selection is a problem.

Universal compression of real data: image and video

Compressing images and videos is a universal compression problem, as the joint distribution of the pixels is not known. However, image and video compression have three more specificities that have not been tackled in Sec. 2.2:

1. The model of the data is unknown and definitely far more complex than stationary ergodic. For instance, the pixels are highly dependent (within an image but also between successive images), and this dependence is not stationary. 2. The encoding and mostly decoding complexities must be low.

The compression is lossy.

Efficient lossy compression can be realized with uniform scalar quantization followed by lossless compression. This incurs a loss of only 1.53 dB or 0.255 bit/sample with respect to the optimal rate-distortion (RD) function irrespective of the distribution. Lossy coding refers to the case where the decoded vector is only an approximation of the original source. Rate Distortion (RD) theory derives the information theoretical bounds for lossy compression. In particular, the RD function R(D) gives, for a given maximum average distortion D, the smallest compression rate among all possible codes. It also shows that vector quantizer achieves the optimal RD performance, provided the vector size tends to infinity. However, complexity of vector quantization prevents its use in practical system such as video compression algorithms. A remarkable fact [44, page 2334] is that, at high rates, uniform scalar quantization with VL coding (see the scheme in Fig. 2.2) attains performance within 1.53 dB (or 0.25 bit/sample for low distortion) of the best possible RD function. Moreover the result holds quite generally: for any source distribution, for sources with memory, for any distortion function (nondecreasing in the error magnitude). Last but not least, the result holds even approximately when the rate is not too large (see Fig. 2.3), and holds exactly for exponential densities (provided the quantization levels are placed at the centroids). Due to these results, uniform scalar quantization with VL coding (also called entropy-constrained scalar quantization) is extensively used in modern video coding.

Figure 2.3: RD functions for a Gaussian source. At high rates, the RD curve of the uniform scalar quantizer with VL coding (dashed line) is 1.53 dB above the optimal RD curve (solid line). Moreover, the highrate regime occurs for relative small values of R (R > 2).

CHAPTER 2. COMPRESSION AND UNIVERSALITY

The complexity issue and the pixel dependence issue are tackled with a divide and conquer approach: Transform coding, where the transform removes the dependencies between the pixels, and the entropy coder the redundancy due to the non-uniformity of the pixel intensity distribution. Motivated by its quasioptimality (within 1.53 dB), we stick to uniform scalar quantization with VL code. A consequence is that the VL code becomes the element that needs to exploit the dependency of the quantized samples. Indeed, not exploiting the memory incurs a loss. More precisely, the independence bound on entropy [26, Th. 2.6.6] states, that for a random discrete vector X n , representing the quantized samples, the joint entropy satisfies

H(X n ) ≤ H(X 1 ) + . . . + H(X n ) (2.22)
with equality iff the random variables X 1 , . . . , X n are mutually independent. So, lower compression rate can be achieved when the data are jointly compressed (joint entropy (LHS)), rather than separately (sum of the individual entropies (RHS)). However, this is a negative result with respect to the complexity. Indeed, to achieve the joint entropy as a compression rate, one needs to store the joint probability distribution, and this storage grows exponentially with the number of symbols considered. The complexity here is mostly a storage issue, as an efficient implementation based on conditional probability distributions and arithmetic code exists.

A positive interpretation of (2.22) exists, by exploiting the condition of equality. Indeed, if the vector x n is transformed with an invertible mapping T : x n → y n = T x n such that the transformed coefficients are nearly independent, then

H(X n ) = H(Y n ) H(Y 1 ) + . . . + H(Y n ) (2.23)
where the first equality is the case of equality in the data processing equality [ Less known is the optimality of KLT in RD theory. More precisely, among all linear transforms and at a given rate, the Karhunen-Loève transform (KLT) minimizes the expected distortion of a Gaussian vector [52, prop 7.2]. Then, each component of the transformed vector can be encoded separately using uniform scalar quantization and VL code [START_REF] Kovacevic | Wavelets and Subband Coding, ser. Prentice-Hall signal processing series[END_REF]prop 7.2][26,Th. 10.3.3]. The rate allocation between the components is determined by the eigenvalues of the covariance matrix, and more rate is allocated to the components corresponding to the largest eigenvalues. Optimality of KLT is shown for Gaussian vectors because closed form expression of the RD function of Gaussian vector exists. However, it may hold for more general processes. Indeed, in approximation theory, the optimality of KLT holds irrespective of the signal distribution. Therefore, this technique, called transform coding, is widely used in image and video coding.

Universal transform. When the distribution is not known, the covariance matrix can be estimated from the data, and KLT is used with this estimated covariance matrix. This is called PCA (principal component analysis). However, the estimated covariance matrix needs to be sent, which might be very costly in the case of non stationary sources. Instead, a preferred technique in video coding is to use an approximation of the KLT, the discrete cosine transform (DCT), which is signal independent (no need to send any information about the transform), and is optimal for Markov chains of order 1, with high correlation [52, p. 389].

Predictive coding. Another divide and conquer approach is predictive coding. Exploiting the memory is not based on a linear transform, but on a linear filter. There, a linear prediction based on past reconstructed values is removed from the samples and the resulting prediction residual is quantized. The primary goal is to decorrelate the samples, as in Transform coding. Another interpretation, is that the predictor reduces the variance of the variable to be scalar quantized [44, page 2331]. Finally, both transform and predictive coding are equivalent asymptotically i.e. when the number of coefficients of the transform and of the prediction filter both go to infinity [52, p. 403].

CHAPTER 2. COMPRESSION AND UNIVERSALITY (a)

Scalar Quantization 11

Q Q -1 y(n) x(n) + + - + + + x(n) y(n) v(n) A′(z) Figure 1.3.

Outline of the principle of predictive scalar quantization

We can immediately see that, in a real-world application of coding, this scheme is not very realistic since the signal v(n) must also be transmitted to the decoder, but let us wait until the end of the chapter before demonstrating how we go from a open-loop scheme to a more realistic, but more complicated to analyze, closed-loop scheme.

If we subtract a value from the signal before encoding it and add it back after decoding, the quantization error q(n) = y(n)ŷ(n) and reconstruction error q(n) = x(n)x(n) must always be equal because:

q(n) = y(n) -ŷ(n) = x(n) -v(n) -[x(n) -v(n)] = q(n)
Hence their respective powers are identical. Since the main interest of the user of the complete system is to have the smallest possible reconstruction error power, the problem becomes simply the reduction of the quantization error power. If we assume an optimized scalar quantization of y(n), we know that the quantization error power can be expressed as:

σ 2 Q = c σ 2 Y 2 -2b
From this, we conclude that seeking to minimize the reconstruction error power σ 2 Q leads us back to minimize σ 2 Y from y(n).

We have a great range of choices for v(n). If we take v(n) in the form:

v(n) = - P i=1 a i x(n -i)
while introducing P parameters, we speak of linear prediction of order P . The signal y(n) is the prediction error which is expressed as:

y(n) = x(n) -v(n) = x(n) + P i=1 a i x(n -i)
www.it-ebooks.info

(b)

In this configuration, the quantizer requires the transmission at each instant n of the number i(n), the result of the calculation of the prediction error y(n), as well as of another number which is associated with the prediction quantization v(n) itself. This quantization configuration, known as open-loop quantization configuration, is not realistic because we are not interested in multiplying the information to be encoded, at a constant resolution. The application of a closed-loop quantization is preferred as shown in Figure 1.4 since we can devote all the binary resources available to quantifying the prediction error y(n). The transmission of v(n) to the receiver is no longer necessary since v(n) now represents the prediction of the reconstructed signal x(n). This prediction can be produced in an identical manner at the transmitter. All that is needed at the transmitter is a copy of the signal processing carried out at the receiver. We can speak of local decoding (at the transmitter) and of distance decoding

+ + + Q + + - - Q -1 Q -1 Q -1 + + + A(z) A(z) A(z) x(n) x(n) x(n) Q + + + + + v(n) x(n) r(n) r(n) r(n) r(n)
In this configuration, the quantizer requires the transmission at each instant n of the number i(n), the result of the calculation of the prediction error y(n), as well as of another number which is associated with the prediction quantization v(n) itself. This quantization configuration, known as open-loop quantization configuration, is not realistic because we are not interested in multiplying the information to be encoded, at a constant resolution. The application of a closed-loop quantization is preferred as shown in Figure 1.4 since we can devote all the binary resources available to quantifying the prediction error y(n). The transmission of v(n) to the receiver is no longer necessary since v(n) now represents the prediction of the reconstructed signal x(n). This prediction can be produced in an identical manner at the transmitter. All that is needed at the transmitter is a copy of the signal processing carried out at the receiver. We can speak of local decoding (at the transmitter) and of distance decoding A prediction v(n) of the current symbol x(n) is computed from the input sequence {x(n)} n , with the filter A (z), and is subtracted from the current symbol x(n) to yield the residue y(n). This residue is then quantized, and this is the compressed version of x(n). This scheme is however impractical as it requires to send the prediction v(n). To avoid sending additional data, the prediction is computed on the quantized coefficients at the decoder (b), but this scheme is still not satisfactory as it requires a feedback loop. Finally, the feedback loop is avoided in (c), by duplicating the decoder at the encoder. This scheme also avoids sending any additional data (neither feedforward nor feedback).

+ + + Q + + - - Q -1 Q -1 Q -1 + + + A(z) A(z) A(z) x(n) x(n) x(n) Q + + + + + v(n) x(n) r(n) r(n) r(n) r(n)
Figure 2.6: Overall video compression scheme.

My contributions to universal compression: introduction

Compression for images and videos requires to construct, for each part of the image where the distribution is assumed to be stationary and ergodic, a universal code that consists of: the identification of the model (q ∈ Q), then the identification of the distribution within the model (Q q ∈ M q ) and finally the encoding of the sequence with this distribution as in (2.20). Here, the word model is used in the sense in which it is usually employed in statistics, i.e. a family of distributions. By contrast in information theory, a model refers to a single distribution and a model class to a family of distributions [45, p. 175]. In the following, I will use the information theoretical terminology unless otherwise specified, because it allows to use the classical denomination "model based coding".

MY CONTRIBUTIONS TO UNIVERSAL COMPRESSION: INTRODUCTION 23

With this new terminology, the length of the description (2.20) becomes

L(q)

one class

+ L(Q q ) one distribution one model + L(x n |Q q ) data = (C Q (q)) + (C q (Q q )) one model + (C(x n |Q q )) data (2.24)
where C Q stands for the code of the class, C q stands for the code of the distribution within the class, and C for the code of the data sequence. To make it more concrete, (C Q , C q ) can, for instance, include the identification of the predictor within a set of predefined predictors (intra mode), the motion vectors, a flag bit to determine whether a block is inter coded or rather intra coded. C contains all the encoding steps of the data sequence: prediction, transform, entropy coder.

Statistics suggest to use a worst case criterion with respect to the true distribution of the data (see Sec. 2.2). In information theory instead, a classical criterion is rather an average criterion. For instance, in video standardization, the overall compressed length is averaged over a set of typical videos which is determined at the beginning of the standardization process. The optimization can then be written as:

min C Q ,Cq,C P ∈P E X n   min q∈Q (C Q (q)) + (C q (Q q )) one model + (C(X n |Q q )) data   (2.25)
There are many difficulties in solving this optimization problem. The first open issue is the optimal code C for the data sequence under complexity constraint. In fact, when there is no complexity constraint, the optimal code C for the data sequence is well known: it is an entropy coder, which exploits both redundancies due to the distribution and the memory. If the complexity must be low, then a divide and conquer approach is applied (see Sec. 2.4). There, the redundancy due to the memory is exploited by a transform, and/or a predictor. However, the memory is not optimally exploited as the images are not Gaussian distributed and the conditions for the optimality of the KLT are not satisfied. In other words, after the transform, the data are decorrelated but not independent. So to compensate for the suboptimality of the divide and conquer approach, the entropy coder takes into account remaining dependencies, but in a limited way as only local dependencies are exploited in the context based arithmetic coder Cabac [START_REF] Marpe | Context-Based Adaptive Binary Arithmetic Coding in the H.264/AVC Video Compression Standard[END_REF].

The second difficulty is to find a good code (C Q , C q ) for the model [45, p 17]. This difficulty was indeed a motivation for the work on the one part code [START_REF]Universal coding, information, prediction and estimation[END_REF], which avoids the encoding of the model. Another difficulty related to the code (C Q , C q ) for the model, is that it requires to determine the set of possible models Q. Hence the challenges in compressing visual data are to efficiently:

(i) determine a model class Q relevant for visual data, (ii) code the model (C Q , C q ), and (iii) code the data according to the model C. My contributions were to propose processing tools adapted to the images by trading between the description lengths of the model and the data. Extreme cases were developed, where either all the description was devoted to the model only, or to the data only. Moreover, I developed user-centric video compression schemes where the characteristics of the user are taken into accounts. These characteristics can be additional limitations, such as low complexity at the decoder side (distributed video coding), or, rather new functionalities offered to the user such as free navigation within a multiview scene (free viewpoint television). The model of an image requires a long description, because the model is complex, but also because it changes rapidly, such that sending the model is very costly. Therefore, fixed transforms are used in order to avoid sending the model. For instance, Jpeg image compression uses DCT, and Jpeg 2000 wavelets. The drawback of these transforms is that they are optimal for very restricted distribution families: DCT is optimal in the RD sense for Gaussian Markov processes of order 1 with high correlation [52, p. 389 et Prop 7.2], and wavelets for sparse Markov processes of order 1 [START_REF] Pad | Optimality of operator-like wavelets for representing sparse ar(1) processes[END_REF]. However, pixels do not satisfy these optimality conditions. So, additional transforms have been proposed to further decorrelate the transform coefficients, by exploiting the distribution of the transform coefficients. For instance, the coding schemes [START_REF] Rolon | generalized lifting for sparse image representation and coding[END_REF][START_REF] Rolon | Modeling of contours in wavelet domain for generalized lifting image compression[END_REF] are nonlinear wavelet transforms based on the Generalized lifting scheme [START_REF] Sole | Generalized lifting prediction optimization applied to lossless image compression[END_REF]. To avoid sending the model, the parameters of the filter are learned for a class [START_REF] Rolon | image compression with generalized lifting and partial knowledge of the signal pdf[END_REF] (in that case, the coding scheme is specific to a type of images such as remote sensing images), or derived from the context [START_REF] Rolon | Generalized lifting with adaptive local pdf estimation for image coding[END_REF]. In all these schemes, the filters are designed such as to reduce the encoding rate (more precisely the energy of the coefficients), but not in a RD sense.

We therefore proposed to learn a transform with a deep neural network (Deep NN) architecture on a large image dataset, where the transform is learned in order to optimize a RD criterion. Moreover, the characteristics of the uniform scalar quantizer are explicitly used in the learning. The learning is performed offline, and the optimized transform is stored at both the encoder and the decoder. One drawback of learned NNs is that they are very much dedicated to a task. For instance, previous constructions of NN based transform were tuned for one RD tradeoff. Therefore, we also constructed a unique transform for the whole range of distortions.

A first remarkable fact regarding the RD performance of our NN based transform coding scheme (see Fig. 2.7), is that the learned transform outperforms Jpeg2000. Indeed, Fig. 2.7 shows the RD performance of a compression scheme based on different learned transforms (yellow, green, and red curves), that all outperform Jpeg2000 (black curve). The learned transform coding still cannot bridge the gap with predictive coding (intra coding of H265), except at very low bitrate, but in Intra coding the compression not only relies on a transform but also on prediction, which is known to outperform the transform coding scheme. A second remarkable fact is that both Jpeg2000 and H265 use contextbased entropy coders, where the context allows to take into account some memory in the data at the VL encoder input. In our approach instead, a very simple symbolwise entropy coder is used. Alternatively, the information the j th feature map of Y encodes, j ∈ [|1, m|], can be seen as follows. ∀i ∈ [|1, m|], all the coefficients in the i th feature map of Y are set to µ i . This way, the feature maps of Y contains no significant information. Then, a single coefficient in the j th feature map of Y is set to α ∈ R and X = g d (Q (Y) ; φ) is displayed. α is selected such that it is near one of the two tails of the Laplace distribution of the j th feature map of Y. Figure 4 shows the 64 × 64 crop at the top-left of X when the single coefficient is located at the top-left corner of the j th feature map of Y, j ∈ {50, 125}. We see that the 50 th feature map of Y encodes a spatially localized image feature whereas its 250 th feature map encodes a spatially extended image feature. Moreover, the image feature is turned into its symmetrical feature, with respect to the mean pixel intensity, by moving α from the right tail of the Laplace distribution of the j th feature map of Y to the left tail. This linear behaviour is observed for each feature map of Y.

It is interesting to see that, given the fitting in Section 3.1, Y is similar to the DCT coefficients for blocks of prediction error samples in H.265 [9] in terms of distribution. However, when looking at the information each feature map of Y encodes, Y has nothing to do with these DCT coefficients.

EXPERIMENTS

We now evaluate in terms of rate-distortion performances: (i) whether the way of learning the quantization matters, (ii) whether, at test time, it is efficient to quantize the coefficients obtained with the learned transform using quantization step sizes which differ from those in the training stage. This is done by comparing three cases.

The 1 st case follows the approach in [START_REF] Berrou | Near Shannon limit error-correcting coding and decoding: Turbo-codes[END_REF]. One transform is learned per rate-distortion point, the bit allocation being learned via the normalizations. In details, an autoencoder is trained for each γ ∈ S = {10000.0, 12000.0, 16000.0, 24000.0, 40000.0, 72000.0, 96000.0}. During the training and at test time, the quantization step size is fixed to 1.0.

In the 2 nd case, a unique transform is learned location being done by learning a quantization st feature map. More precisely, a single autoencode for γ = 10000.0 and {δ i } i=1...m is learned, see At test time, the rate varies as the quantization are equal to the learned quantization step sizes mu β ∈ B = {1.0, 1.25, 1.5, 2.0, 3.0, 4.0, 6.0, 8.0, 10.

In the 3 rd case, a unique transform is learned location being learned via the normalizations. I single autoencoder is trained for γ = 10000.0 and training, the quantization step size is 1.0. At test tim varies as the quantization step size spans B.

In the 2 nd case, the autoencoder has the archi scribed at the beginning of Section 3. In the 1 st and GDN is also placed after g e and a IGDN is placed The autoencoders are trained on 24000 luminance size 256×256 that are extracted from ImageNet. T time, the 24 luminance images from the Kodak s serted into the autoencoders. The rate is estimated pirical entropy of the quantized coefficients, assum quantized coefficients are i.i.d. Note that, for the 3 rd case, we have also implemented a binarizer an arithmetic coder to compress the quantized coeffi lessly, see the code 1 . The difference between the rate and the exact rate via the lossless coding is alw than 0.04 bbp. Figure 5 shows the rate-distortion c aged over the 24 luminance images. The JPEG20 obtained using ImageMagick. The H.265 [START_REF] Coluccia | Lossy compression of distributed sparse sources: a practical scheme[END_REF] cu puted via the version HM-16.15. There is hardly ence between the 2 nd and the 3 rd case. This means plicit learning of the transform and the quantizatio is equivalent to learning the transform and the norm while the quantization step size is imposed. Note 2 nd case, the learning of {δ i } i=1...m involves 128 whereas, in the 3 rd case, that of {ϕ e , ϕ d } involves rameters. The 2 nd and the 3 rd case perform as we case. The minimization (4) and the training in learned transforms which can be used with variou tion step sizes at test time. It is convenient not t autoencoder per compression rate as a single tra 4 days on a NVIDIA GTX 1080. Finally, we s learned transforms yield better rate-distortion pe than JPEG2000. The quality of image reconstruc experiment in Figure 5 and another experiment on images created from the BSDS300 [START_REF] Coluccia | Exact Performance Analysis of the Oracle Receiver for Compressed Sensing Reconstruction[END_REF] can be see

CONCLUSION

Using a unique transform learned via autoencode ious quantization step sizes at test time, it is compress as well as when learning one transform distortion point at a given quantization step size. the learned transformed outperform other image co algorithms based on transforms. In conclusion, motivated by the fact that models of images are complex and change very rapidly, we developed a strategy based on a fixed transform to avoid sending the model, which may require a long description due to both its complexity and its dynamic. Unlike previous standards, the transform is not longer optimized for a class of theoretical distributions for which optimality results can be derived. Instead, the transform is learned, to get closer to the true model of images. Also a deep architecture is used for its approximation power. Finally, the fixed deep transform, which we designed, and which does not require to send any information about the model, outperforms classical transform such as DCT and Wavelets, even if a very simple symbolwise entropy coder is used (whereas both Jpeg and Jpeg2000 use context based entropy coders).

Coding by sending the model only:

super-resolution based video coding This video compression scheme based on SR can occur in different scenarios. For instance, it may be a choice to send compressed videos as in Fig. 2.8. Or, it results from the network constraints. Indeed, to adapt to the variations in the network bandwidth in video streaming, the video compression rate is lowered by reducing the spatial resolution. To compensate for this variation in resolution, SR is used to increase the resolution when the received resolution is low, and therefore propose a constant resolution whatever the network state is.

SR based video compression is an "all in the model" compression scheme. The SR algorithm first builds a dictionary of pairs of LR and HR patches from the two KF which surround the GOP of LR frames. Then, LR patches are decomposed onto the LR dictionary (column b, steps 1 and 2 in Fig. 2.9), and the SR algorithm uses both this LR decomposition and the dictionary to enhance the resolution (column b, step 3 in Fig. 2.9). More precisely, for each patch of the current LR frame, a nearest neighbor search is performed (column b, step 1 in Fig. 2.9) in the LR dictionary built from the KF. Note that the patches in the dictionary have different characteristics. Indeed, they can represent either a smooth area, an edge or a texture. Each type of patch has a different complexity since the number of DCT coefficients to sufficiently well approximate a patch varies and depends on the type of the patch, see Fig. 2.10. In a way, the type of the patch (smooth/edge/texture) is similar to a class of distributions, and the NN search is similar to selecting a distribution within the class distribution. The second step consists in computing weights to better approximate a LR patch, which can be seen as specifying the distribution within the class. (Note that another originality of the proposed method in [START_REF]Video super-resolution via sparse combinations of key-frame patches in a compression context[END_REF] is to not only consider the current frame but also corresponding patches in the KF (column c. in Fig. 2.9). This insures some temporal consistency.) Finally, the weights are used with the HR dictionary to generate the HR patch. So here, the KFs act as the description of the model class, and the LR image as the identification of one distribution within the class. KF and LR are the only transmitted data. Indeed, no residue is sent between the true and super-resolved image. Therefore, this scheme is an all in the model compression scheme. The second remarkable fact about this compression approach is that the code of the model is the one used for the data. Indeed, the distribution is sent as an empirical distribution i.e. samples. Accordingly, the encoding of this empirical distribution is done using a video compression scheme (HEVC in this setup).

Interestingly, this proposed compression algorithm based on SR achieves similar compression efficiency as HEVC while sending possibly two spatial resolutions [START_REF]Video super-resolution via sparse combinations of key-frame patches in a compression context[END_REF]. This is noticeable since scalable video encoders suffer some penalty [START_REF] Wien | Performance Analysis of SVC[END_REF] (12.8% for the all intra configuration and 13.7% for the RandomAccess configuration [START_REF] Suehring | JCT-VC AHG report: HEVC HM, SCM, SHM and HDRTools software development and software technical evaluation (AHG3). Doc. JCTVC-AD0003[END_REF]). The penalty of scalable video encoders is sometimes explained by the redundant sampling of predictive video coders: indeed to encode a high resolution frame, the number of residue samples equals the resolution of the enhanced but also base layer. This is the reason why wavelet based scalable video compression schemes were proposed since they are non-redundant CHAPTER 2. COMPRESSION AND UNIVERSALITY [START_REF] Bottreau | A fully scalable 3d subband video codec[END_REF][START_REF] Pesquet-Popescu | Three-dimensional lifting schemes for motion compensated video compression[END_REF][START_REF] Tillier | 3d, 3-band, 3-tap temporal lifting for scalable video coding[END_REF]. These coding schemes indeed only experienced little penalty with respect to the non scalable H.264 AVC scheme [START_REF] Schelkens | A comparative study of scalable video coding schemes utilizing wavelet technology[END_REF], but had the drawback to not be compatible with H264 AVC. Interestingly, the SR based compression scheme is compatible with the standardized H.26x coding schemes, and shows similar compression results to the ones of H.265 HEVC the latest of the standardized coding schemes. So, it shows that we need to go to a significant subsampling of the residue to cancel the scalability penalty of standardized video coding schemes.

In conclusion, the proposed video compression scheme, based on SR, allowed us to analyze an all-in-the-model compression scheme. The all-in-the-model compression scheme allows to draw several conclusions. First, coding the model is considered to be a difficult problem. The SR based video compression scheme shows that this can be circumvented by coding the model as data. Second, it is widely believed that scalable video compression schemes are suboptimal [START_REF] Suehring | JCT-VC AHG report: HEVC HM, SCM, SHM and HDRTools software development and software technical evaluation (AHG3). Doc. JCTVC-AD0003[END_REF], especially when they are based on the standardized hybrid coding schemes (H.26x). This SR based algorithm shows that, on the contrary, a video can be scalably encoded without any additional penalty.

Other contributions: Super-resolution efficient both in terms of distortion and complexity.

We proposed novel techniques capable of producing a high-resolution (HR) image from a single low-resolution (LR) image. A first algorithm with complexity constraint (external dictionary) was proposed that improves the PSNR by at least 1 dB with respect to state of the arts methods. The innovations were efficient image patch representation [8], patch estimation [9] and dictionary learning [10,12]. Then, relaxing the complexity constraint, we proposed a method based on an internal dictionary, that improved state-of-the art methods by about 0.8dB [14].

Distributed source coding: model selection and impact of mismatch model

Publications related to this topic: [START_REF] Toto-Zarasoa | Maximum Likelihood BSC parameter estimation for the Slepian-Wolf problem[END_REF] V. Toto-Zarasoa, A. [START_REF] Roumy | Rate-adaptive turbo-syndrome scheme for Slepian-Wolf Coding[END_REF][START_REF] Toto-Zarasoa | Rate-adaptive codes for the entire Slepian-Wolf region and arbitrarily correlated sources[END_REF][START_REF] Toto-Zarasoa | Robust and Fast Non Asymmetric Distributed Source Coding Using Turbo Codes on the Syndrome Trellis[END_REF][START_REF] Toto-Zarasoa | On Distributed Arithmetic Codes and Syndrome Based Turbo Codes for Slepian-Wolf Coding of Non Uniform Sources[END_REF][START_REF] Herzet | Error-resilient non-asymmetric Slepian-Wolf coding[END_REF][START_REF]Non-uniform source modeling for Distributed Video Coding[END_REF][START_REF]Hidden Markov model for Distributed Video Coding[END_REF][START_REF]Non-asymmetric Slepian-Wolf coding of non-uniform Bernoulli sources[END_REF][START_REF] Dupraz | Source Coding with Side Information at the Decoder: Models with Uncertainty, Performance Bounds, and Practical Coding Schemes[END_REF][START_REF]Codage Distribué dans des Réseaux de Capteurs avec Connaissance Incertaine des Corrélations[END_REF][START_REF]Codage de Sources avec Information Adjacente et Connaissance Imparfaite de la Corr élation : le problème des cadrans[END_REF][START_REF]Source Coding with Side Information at the Decoder and Uncertain Knowledge of the Correlation[END_REF][START_REF]Universal Wyner-Ziv Coding for Gaussian Sources[END_REF][START_REF]Practical Coding Scheme for Universal Source Coding with Side Information at the Decoder[END_REF].

Distributed source coding (DSC) refers to the compression of many correlated sources without communication between the sources. An instance of this problem is source coding with side information (SI) at the decoder. Here, two correlated source sequences x n and y n are given and the source sequence x n needs to be compressed. Upon compression, the side information y n is not known. By contrast, the decoder knows y n and receives the compressed version of x n (SW coding scheme in Fig. 2.11). Surprisingly, Slepian and Wolf (SW) [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF] showed that the schemes with (predictive, Fig. 2.11) and without (SW, Fig. 2.11) SI at the encoder, achieve the same compression rate. However, the two encoding schemes are completely different, as the predictive encoder can use explicitly the realization of the other source y n , whereas the SW encoder relies only on the joint distribution between X n and Y n , referred to as the model. Therefore, SW coding is also called model-based coding. More precisely, the model is used at both encoder and decoder but in a different way:

-to determine the code and the compression rate, at the encoder, -to estimate x n from y n , at the decoder. Knowing the model is a key assumption, for not needing the SI at the encoder in the SW scheme. Indeed, without this knowledge, the compression rate increases from H(X|Y ) to H(X) (for memoryless sources), i.e. as for a scheme without SI. However, in practical systems, the model may not be known. Therefore, when the encoding function is linear [START_REF] Stankovic | On code design for the Slepian-Wolf problem and lossless multiterminal networks[END_REF], we first showed that this model can be efficiently inferred at the decoder. The trick consists in deriving the maximum likelihood estimate of the model parameters knowing degraded versions of the information available at the decoder (i.e. the compressed version of the SI y n and not the SI itself), and refining it with an Expectation Maximization (EM) algorithm. Indeed, the originality of the methods relies in the initialization. Indeed, a direct implementation of the model parameter estimation problem with respect to all information available at the decoder relies on a hidden variable, the source sequence. And this problem can either be solved jointly (sequence and parameter) with a prohibitive compelxity or with an EM algorithm, but where the initialization is tricky. Instead, the model parameter estimation with respect to the compressed version of the SI, and not the SI itself, can be solved according to a ML criterion. This approach holds quite generally for binary memoryless sources with an additive channel [START_REF] Toto-Zarasoa | Maximum Likelihood BSC parameter estimation for the Slepian-Wolf problem[END_REF], non-binary sources [START_REF]Source Coding with Side Information at the Decoder and Uncertain Knowledge of the Correlation[END_REF], sources with memory and back or reverse correlation channel [102]. Moreover, we characterized the effect of an imperfect knowledge of the model at the encoder on the compression rate and proposed practical schemes to achieve these rates [START_REF]Practical Coding Scheme for Universal Source Coding with Side Information at the Decoder[END_REF]. Indeed, the lack of model knowledge can significantly degrade the performance since the optimal compression rate is reduced to a worst case [START_REF]Source Coding with Side Information at the Decoder and Uncertain Knowledge of the Correlation[END_REF]. The degradation was evaluated for different source models Both results (possibility to learn the model the decoder, and significant degradation at the encoder without model) motivates the use of a feedback channel to tune the compression rate in practical systems.

As an application, we considered Distributed Video Coding (DVC), a video compression system that builds upon the idea of distributed source coding in order to achieve efficient video compression while maintaining a low complexity at the encoder. Despite recent advances, distributed video compression rate-distortion performance is not yet at the level CHAPTER 2. COMPRESSION AND UNIVERSALITY of predictive coding. The key issues we considered to bring DVC to a level of maturity closer to predictive coding were:

1. finding a new model well suited for the sources in DVC. The new model includes (i) two classes: new (inter) correlation model (i.e. between the sources), (ii) the non uniformity of each source [START_REF]Non-uniform source modeling for Distributed Video Coding[END_REF], (iii) the memory of each source (Hidden Markov models are used) [START_REF]Hidden Markov model for Distributed Video Coding[END_REF]. 2. finding the information theoretical compression rates for these models 3. estimating the model parameters [START_REF] Toto-Zarasoa | Maximum Likelihood BSC parameter estimation for the Slepian-Wolf problem[END_REF] and the model class (correlation type). Note that the novelty in the approach results from the integration of memory and nonuniformity in the entropy coder. Indeed, integration of these properties are straightforward in source codes such as arithmetic code [START_REF] Cover | Elements of information theory[END_REF]Sec. 13.3]. However, due to the duality between channel coding and DSC [START_REF] Slepian | Noiseless coding of correlated information sources[END_REF][START_REF] Chen | On the duality between Slepian-Wolf coding and channel coding under mismatched decoding[END_REF], the entropy coder is here a channel code, which requires special handling. The Distributed Video Coding system [102] that integrates the enhancement that we propose here demonstrates a quality-versus-rate improvement by up to 10.14%, with respect to its elder version. A simplified model with non-uniform sources is also proposed that achieves an improvement by up to 5.7%.

In DSC, the lack of model knowledge at the encoder can significantly degrade the compression performance. However, even achieving these degraded performances is challenging, since the decoder also needs the model knowledge. It was shown that the lack of model knowledge at the decoder can be circumvented. The trick consists in estimating the source parameters optimally according to the ML criterion but with respect to a subset of the information available at the decoder. This estimate allows to efficiently initialize an EM algorithm, known to be very sensitive to the initialization. As for the application to DVC, we proposed new models and their model estimation methods, that achieved up to 10.14% bitrate saving with respect to state-of-the-arts DVC implementations. The novelty here resided in the integration of non-uniformity and memory in the entropy coder for DSC, which turns out to be a channel code. This setup occurs for instance in Free-viewpoint television (FTV). Indeed, one user chooses a viewpoint, i.e. an image, and can change it at anytime. Compression is performed offline, the compressed video is stored at a server, and the users make requests to the server. When an image is compressed, the encoder knows that the decoder can have in memory a previously requested image, but does not know which one, since this depends on the navigation of the user. In this case, the optimal compression is determined by the least correlated image that could be in the users memory.

To lower the compression rate, the server could decode the whole video, and reencode the requested images. However, this would lead to an extreme complexity at the server. It is however possible to achieve the same compression rate, while maintaining a low complexity at the server [76]. The idea consists in allowing the server to extract bits from the compressed bitstream see Fig. Uncertainty on which SI is available at the decoder occurs in the context of FTV, where users can freely choose and change their viewpoint at anytime. This uncertainty can significantly degrade the compression performance. However, we have shown that this can be circumvented if the server is allowed to extract samples from the bitstream, corresponding to the compressed bitstream.

Chapter 3 Transmission and universality

Universal transmission, or universal channel coding, is the problem of sending data over a noisy channel without knowledge of the channel transition probability. If universality does not incur any loss in data compression (at least asymptotically), this is not the case for the transmission over noisy channels. Indeed the lack of knowledge has two possible impacts. More precisely, for the case of a memoryless channel with a single path:

-the transmitter can not predict the rate to encode the data, because the channel statistics are not known. Therefore, the best performance is determined by the worst channel [START_REF] Han | Information-spectrum methods in information theory[END_REF]Th. 3.2.1]. To compensate for this negative result, a feedback channel, if possible, is used to inform the encoder of the channel statistics. If not, then an outage will occur, i.e. cases where no transmission is possible. This problem has been studied in [START_REF] Piantanida | Outage behavior of discrete memoryless channels under channel estimation errors[END_REF]. -the lack of knowledge has also an impact on the decoder. Indeed, if the decoder uses a wrong decoding metric, then the performance might be degraded. Unfortunately, the optimal performance under mismatched decoding [START_REF] Merhav | On information rates for mismatched decoders[END_REF] is still an open problem. However, there exists cases where the decoding metric has no impact on the performance. This occurs for an erasure channel. This also occurs if sequencewise ML decoding is performed, and if the channel is either a binary symmetric channel (BSC) or a finite alphabet input Additive White Gaussian Noise Channel (AWGN). Indeed, in both cases, the ML decoding is equivalent to minimizing a distance (Hamming for BSC and Euclidean for AWGN). So the impact of the lack of channel knowledge is well studied when the channel has a single path. However, many questions remain regarding the case of multipath channels. Therefore, we studied the question of imperfect channel knowledge in the context of multipath channels (Sec. 3.1).

Moreover, the solution of a feedback channel to circumvent the lack of knowledge at the transmitter may not always be usable, for instance if there is a delay constraint. For these cases, the source has to be adapted to the channel. This is studied in Sec. 3.2.

Multipath channels occur in wireless scenarios where the omnidirectional waveform sent is reflected (against building for instance) and the receiver gets multiple and delayed copies of the emitted signal. This occurs much more in urban areas. After sampling, the receivers gets a discrete convolution of the input signals and needs to deconvolve the input. This deconvolution, usually referred to as equalizer, can be performed either optimally in the sense of the maximum a posteriori (MAP) criterion with a complexity that grows exponentially with the number of multipath or with a linear filter with or without feedback loop. In the latter case, the complexity grows only linearly with the number of multipaths [START_REF] Proakis | Digital Communications[END_REF]. More formally, let X stand for the random vector that models the input of the channel, H be the vector of the channel coefficients (i.e. the coefficients of the filter), Y be the output of the channel, and x, y, h their realizations. Let us further assume that the channel is fixed during the transmission of the block X. The classical MAP equalizer solves x = arg max

x P(X = x|Y = y, H = h)

These equalizers all assume that the coefficients of the channel are perfectly known. If this is not the case, then a learning sequence known by both the encoder and the decoder is sent, which allows the receiver to first estimate the coefficients of the channel. Then, the algorithm becomes x = arg max

x P(X = x|Y = y, H = ĥ)

(3.2)
where ĥ is the estimate of the channel.

For infinite length learning sequence, the channel can be perfectly estimated. However, for the sake of efficiency, the whole bandwidth can not be used for learning the channel, (the primary goal is to send data). So, the learning sequence is finite and the estimation is thus not perfect (due to the additive thermal noise).

Another solution is to consider the problem on the whole This problem can be solved with an iterative solution such as the expectation maximization. The algorithm introduces the hidden variable h and iterates between the computation of the symbol densities and the estimation of the channel coefficients. This algorithm is however very sensitive to the initialization as, the problem (3.3) is not convex. Therefore the need for a first good estimate of the channel. But if an initialization is provided, through for instance a learning sequence, then the statistical characteristics of this channel estimate should be taken into account. This leads to the following optimization problem:

x = arg max x P(X = x|Y = y, Ĥ = ĥ)

We proposed an iterative solution to this problem in [85].

A second contribution is the analysis [82] of a MAP equalizer, which receives an estimate of the channel coefficients. The difficulty in this analysis relies on the fact that the receiver does not perform linear transformations, but rather performs an exhaustive search among all possible input sequences. This search can be made in an efficient way, such that the computation grows linearly with the length of the sequence (the exponentially growing cost is in the length of the channel only). Still to perform an analysis, all possible errors need to be considered. Our analysis follow the same line and a closed form expression of the probability of error at the equalizer output as a function of the accuracy of the channel estimate is derived. The analysis was then extended to the case of a turbo-detector (iterative receiver MAP equalizer and MAP channel decoder) [START_REF] Sellami | Performance analysis of the MAP equalizer within an iterative receiver including a channel estimator[END_REF] and to the case of MIMO receivers [START_REF] Chaabouni | Lower bounds on the performance of the MAP equalizer with a priori over MIMO systems[END_REF].

This analysis was the starting point to design the system and perform resource allocation. In particular, we optimized the training sequence length and showed that the shortest is the better. Indeed, using more symbols to learn the channel will lower the error rate of the equalizer but also lower the data throughput. [50] shows that on the whole the shortest the training sequence the better. This analysis was performed under realistic assumption of an efficient receiver. First, a turbo detector (concatenation of a MAP equalizer and convolutional decoder, shown to get rid of the channel) was used. Second, the channel estimate is also improved as the symbols are estimated (Least mean square estimate). In order to estimate the channel, the observation vector y is approximated as follows:

y ≈ Xh + n, ( 3
)
where X is the estimated version of the matrix X containing 2 Research Letters in Communications 2L -1, where L is the channel memory. Notice that a similar result was found in [START_REF] Barron | The minimum description length principle in coding and modeling[END_REF] by maximizing a lower bound on the training-based channel capacity when the training and data powers are allowed to vary. Throughout this letter, scalars and matrices are lower and upper case, respectively, and vectors are underlined lower case. The operator (•) T denotes the transposition.

Transmission System Model

As shown in Figure 1, the input information bit sequence is encoded with a convolutional code, interleaved and mapped to the symbol alphabet A. In this letter, we consider the BPSK modulation (A = {-1, 1}). The symbols are then transmitted over a multipath channel. We assume that transmissions are organized into bursts of T symbols. The channel is assumed to be invariant during the transmission. The received baseband signal sampled at the symbol rate at time k is

y k = L-1 l=0 h l x k-l + n k , ( 1
)
where L is the channel memory and x k are the transmitted symbols. In this expression, n k are modeled as independent and identically distributed (iid) samples from a random variable with normal probability density function (pdf) N (0, σ 2 ), where N (α, σ 2 ) denotes a Gaussian distribution with mean α and variance σ 2 . The term h l is the lth tap gain In order to estimate the channel, the observation vector y is approximated as follows:

y ≈ Xh + n, ( 3
)
where X is the estimated version of the matrix X containing the hard decisions on the coded symbols at the output of the decoder. The iteration process can be repeated several times and here the matrix X corresponds to the estimated symbols at the last iteration.

The least square estimate h = ( h 0 , . . . , h L-1 )

T of h is given by [START_REF]Call for Evidence on Free-Viewpoint Television: Super-Multiview and Free Navigation[END_REF] Finally, the tools developed to analyze the negative effect of parameter uncertainties can also quantify the positive effect of some side information (for instance a priori information in a turbo scheme). We could then analyze the convergence of a turbo detector and show that the effect of a multipath channel can be removed [83]. This is a well know result when there is no noise. And it is interesting to see that the result still holds in the presence of noise, provided a channel code is used, and that a turbo scheme is used at the receiver.

Uncertainty of the channel was studied under the assumption that only the channel coefficients are unknown but the noise level is known at both encoder and decoder. This setup was motivated by the fact that there exist indeed ways to avoid the impact of an uncertainty on the noise level. It was shown that the fact that a channel has multipath is not harmful. In fact, when the coefficients of the mutipath channel are not known, the effect on the channel can completely be compensated even in the presence of noise. Moreover, when the channel coefficients need to be estimated, then it was shown that the length of the training sequence can be as short as possible.

Networks experience packet losses at the Internet Protocol (IP) level. Indeed, the physical layer introduces impairments in the form of symbol errors. Then, check sum are applied at the data link and/or physical layer that rejects the damaged frames. If the physical layer is wireless, the packet loss ratio (called Block Error Rate in [START_REF]Speech and video telephony terminal acoustic test specification, 3rd Generation Partnership Project (3GPP) Std[END_REF]) can be rather high. For instance, 3GPP [2, Annex E] adopted different end-to-end profiles leading to a packet loss rate between 0.2375 % (for wideband calls) and 2.6375 % (for super-wideband calls) [START_REF] Majed | Delay and quality metrics in Voice over LTE (VoLTE) networks: An end-terminal perspective[END_REF].

Retransmission and Forward Error Codes (FEC) can cope with erasures but introduce delays. Several solutions exist in the transport layer and above, to ensure that the client can recover the data in the presence of packet losses; for instance, retransmission (in unicast with the TCP protocol [START_REF] Postel | Transmission Control Protocol[END_REF]; in multicast, with the Reliable Mutlicast Transport Protocol [START_REF] Paul | Reliable multicast transport protocol (RMTP)[END_REF], where lost packets are also recovered with local retransmission thanks to a designated receiver to avoid acknowledgment implosion) or protection with Forward Error Codes (FEC) [START_REF] Luby | The Use of Forward Error Correction (FEC) in Reliable Multicast[END_REF][START_REF] Watson | Forward Error Correction (FEC) Framework[END_REF]. Both strategies implies delays which may not always be compatible with real time streaming:

TRANSMISSION WITH ADAPTATION TO THE CHANNEL AND THE SOURCE37

-delay for retransmission is at least the Round Trip Time (RTT); -delay with FEC is the time needed to send all the encoded packets, which can be up to the number of encoded packets defined by the smallest code rate: R min = k nmax , if there is no feedback to stop transmission, when a sufficient number of packets is received.

Unequal erasure protection helps meeting a tighter delay constraint. Indeed, there is another degree of freedom: the amount of source data. Indeed, if the source can be split into importance subfiles (for instance scalable video encoding [START_REF]JTC1[END_REF], or data of interframe versus intraframe in a video), it is possible to further decrease the delay with UEP. UEP can be implemented with retransmission [START_REF] Bouchireb | Transmission Schemes for Scalable Video Streaming in a Multicast Environment[END_REF] or FEC [START_REF] Bouabdallah | Dependency-aware unequal erasure protection codes[END_REF][START_REF] Vukobratovic | Unequal error protection random linear coding strategies for erasure channels[END_REF]3,79]. Here we consider solutions based on FEC codes because:

-delays incurred by retransmission are always bigger than delays by FEC (due to RTT) -FEC based protocols can easier scale up and deal with a large number of receivers than retransmission based protocols More precisely, in UEP, the original k packets of the source are split into a base layer (k 1 packets) and some enhancement layers (k 2 , ...). Then, each layer is protected with a different erasure channel code, the base layer being more protected than the other layers:

R min = k nmax = R 1 = k 1 n 1 ≤ R 2 = k 2 n 2 .
Therefore, assuming that R min = R 1 and since by construction k 1 ≤ k, we have n 1 = k 1 k n ≤ n, introducing a smaller delay for the base layer.

Existing solutions to achieve unequal erasure protection are equivalent in terms of erasure resilience. They differ in terms of computational complexity and memory consumption.

-joint encoding of all layers: [START_REF] Bouabdallah | Dependency-aware unequal erasure protection codes[END_REF], [START_REF] Vukobratovic | Unequal error protection random linear coding strategies for erasure channels[END_REF] (with expanding window), -separate encoding of the layers and joint packetization of the encoded data: as in Priority Encoding Transmission (PET) [3] -separate encoding of the layers and separate packetization: as in Generalized Object Encoding (GOE) [79] Separate encoding of the layers is asymptotically optimal over an erasure channel [START_REF] Boucheron | About priority encoding transmission[END_REF], so all methods listed above perform the same in terms of erasure resilience. However, the methods differ in terms of computational complexity and memory consumption. First, joint encoding is more complex than separate encoding as the data of all layers have to be jointly processed. Second, joint packetization [3] is more complex than separate encoding [79] as all encoded data need to be stored and concatenated, by taking into account the amount of data in each layer (k i ) and its protection level (R i ). Moreover, PET [3] suffer more from rounding than GOE and requires to recompute the data partition each time the size of the source data changes.

Interestingly the GOE approach can also handle small source packet sizes. Transport protocol have fixed packet size. In the case of small source packet sizes, the packets might be rather empty, as classical protocols consider to put the data of a single source in each packet. Thanks to a new abstraction level, the GOE signalization can also handle concatenate small packets, saving badnwidth. This approach can be seen as a variable to fixed length code.

Unequal erasure protection (UEP) is a tool to adapt a priori to the channel losses, while meeting a delay constraint. Since the adaption is done prior to transmission, the system must be dimensioned to the worst case. But different levels of protection are provided such that the delay can be lowered. GOE is a framework to implement UEP with separate encoding and packetization. The novelty lies in the introduction of a new level of abstraction that allows to deal with different parts of an object to be sent over the network. This is done through the GOE signalization compatible with any transport protocol with or without feedback (TCP, ALC) and is therefore backward compatible. It is as efficient as state of the art methods in terms of erasure efficiency but less complex in terms of computation and memory. Notably, GOE can also handle small packets and concatenate them with an appropriate signalization.

Chapter 4

Conclusion and perspectives

This manuscript presented the main research results obtained since completing my PhD. A general conclusion can now be drawn: the model is central to the design of efficient compression and transmission schemes. The term "model" is used here in its information theoretical meaning, see Sec. 2.3. An interesting question concern the accuracy of the model, i.e. how well the model should capture the data, in the case of compression, or the channe,l in the case of transmission. Indeed, the most accurate model is not necessarily the one that leads to the best performance. This is seen for instance in the case of universal source coding performed with a single distribution, or with a unique transform, whatever the image to be compressed is, Sec. 2.6. Similarly, in the case of transmission, it was shown that the optimal description of the channel with a turbo detector, is the shortest one, Sec. 3.1. Nevertheless, in some cases, a better model can improve. For instance, in the case of DVC, our results showed that a model that better fits the signal characteristics, improves significantly the compression performance, see Sec. 2.8.

This leads to the question raised in the title of the manuscript: "is it necessary to send the model?" And it can now be concluded that there is no unique answer. Indeed, in the case of compression, it was shown that two extreme compression schemes with or without sending the model (see Sec. 2.6 and Sec. 2.7) achieve comparable performance. The fact that there is no unique answer to this question is to be welcomed as it allows to adapt to the application constraints (complexity, delay, ...). However, it is important to stress that not sending the model does not mean not modeling. Indeed, in the deep transform, the model is learned from a database. But, the model has properties which depend on the choice to send or not the model. More precisely, when the model is not sent, the model must avoid overfitting to be able to generalize to any king of image. By contrast, when the model is sent, overfitting is a welcomed property (especially, when the data is not sent as in Sec. 2.7).

To summarize, there are two main issues concerning the model. The first one is related to the design of algorithms dedicated to a large variety of processing tasks. For instance, it includes the estimation of the model, and then the processing of the data according to this model. In the case of compression, these tasks are the construction of the entropy coder, the transform, the predictor, and the distribution estimator. For the transmission, it means estimating the channel and decoding the data according to the estimated channel. The second issue is to evaluate the impact of the model. In the case of compression, this means to develop a code for the data according to the model, and measure the codelength of this code. Measuring the impact of the model in the case of transmission requires to decode the data according to the channel, and to evaluate the performance of the decoder. These tasks require skills in coding/information theory, but also signal processing, and Perspectives. My research program addresses the challenges faced by the emergence of new types of data, new imaging modalities, and also new practices in terms of user interaction [START_REF] Bertin | New generation of audiovisual sensors and the challenge of dimensionality (nouvelle génération de capteurs audiovisuels : les défis de dimensionalités)[END_REF]. This creates the need for efficient and possibly new algorithms and their analysis, which I will tackle, building on the achieved results, and on the acquired skills.

Compression and diffusion for interactive user experience: Massive Random Access to large databases. Video traffic represents 80% of the data exchanged over the Internet in 2018 1 . Moreover, the amount of these videos exchanged, might triple from 2016 to 2021 1 . Internet of Things (IoT) brings even more data exchange increase, since these data are not only created and requested by human beings but also by objects and machines. Indeed, it is anticipated that, in 2018, the total generated data will be 400 ZB (1 ZB=10 21 B) 2 .

One characteristic of these data is their high redundancy. For the case of videos, multiview acquisition is now widely used, with a tremendous number of possible views: at least 100 views are considered for FTV [START_REF]Call for Evidence on Free-Viewpoint Television: Super-Multiview and Free Navigation[END_REF], which leads to a raw datarate of about 124 Gbit/s (for HD videos at 50Hz). Note that the number of 100 is chosen for testbed experiments but practical implementation will consider significantly more views. Moreover, the resolution of visual sensors keeps increasing, and new modalities have emerged (plenoptic, 360 o cameras) [START_REF] Bertin | New generation of audiovisual sensors and the challenge of dimensionality (nouvelle génération de capteurs audiovisuels : les défis de dimensionalités)[END_REF], leading to high correlation within the pixels but also among the views. Regarding IoT for SmartCities, it is usually deployed with overinstrumentation, which leads to highly spatially and temporally correlated data. It is therefore of great importance to exploit these redundancies to reduce the traffic and the storage.

My research project aims at compressing these large databases. The high redundancy of the data suggests to compress the data together, which leads to a single and noncuttable compressed bistream. On the other hand, the database is so big that users may not be interested in the whole database. This occurs exactly in the context of FTV. Users visualize one view at a time. This also applies for databases collecting data from a largescale sensor network (such as Smart Cities). In fact these two problems are instances of a more general problem that can be called massive random access (MRA) to large databases. Indeed, MRA concerns databases that are so large that, to be stored on a single server, the data have to be compressed efficiently, meaning that the redundancy/correlation between the data have to be exploited. The dataset is then stored on a server and made available to users that may want to access only a subset of the data. Such a request for a subset of the data is indeed random, since the choice of the subset is user-dependent. Finally, massive requests are made, meaning that, upon request, the server can only perform low complexity operations (such as bit extraction but no decompression/compression).

Compression rates have been derived under simple model assumptions [START_REF]Universal lossless coding with random user access: the cost of interactivity[END_REF], see Sec. 2.9. It has been shown that the data can be sent at the same compression rate as if there were no random access to the database. The cost of the interactivity is in the storage only: the data has to be stored according to the least correlated SI. This cost is rather limited, as it stays in the same order of magnitude as the compression rate without interactivity. In particular, it does not scale with the number of possible SIs i.e. the number of navigation paths allowed. However, to construct practical systems, many issues remain open. I 1 Cisco Visual Networking Index:

Forecast and Methodology, 20162021 https://www. cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/ complete-white-paper-c11-481360.html 2 Cisco Global Cloud Index: Forecast and Methodology, 20162021 White Paper, Fig. 24 https: //www.cisco.com/c/en/us/solutions/collateral/service-provider/global-cloud-index-gci/ white-paper-c11-738085.html#_Toc503317525

Image Video compression based on learned models. Despite significant improvements obtained with the video compression standard HEVC, there is still a need to further compress the data. One of the goals is to have a single decoding algorithm that could handle any new modalities such as High Dynamic Range, 360 o videos. Indeed, a project, called Versatile Video Coding5 (VVC), has been launched in April 2018 to develop a new video coding standard. The very good performance obtained with the learning of the transform suggests that it may be fruitful to introduce learning in other processing tasks, such as the prediction, the entropy coder, or the bit allocation problem.

Acquisition adapted to the sensed signal and optimization according to information theoretical criteria. Compressed sensing (CS) is an efficient acquisition scheme, where the acquisition is made through random linear measurements of the data while performing dimensionality reduction. The reconstruction is performed by solving underdetermined linear systems under a sparsity a priori constraint, i.e. the data can be transformed in a domain such that only very few coefficients are non zero. CS is of particular interest when the classical acquisition scheme already multiplexes the signal, and when the signal is sparse in some basis. In that case, it is possible to subsample the acquired measurements and still reconstruct the signal. This is exactly the case in Magnetic resonance imaging (MRI). Another possible application is when the sampling is performed in raster mode, and that there is a physical way to perform multiplexing. This is the case with the single pixel camera.

CS stems from the signal processing community and first analyses mostly concern the ability to recover the data. More precisely, these analyses are worst case as they consider a deterministic signal and look for properties on the measurement matrix that guarantee necessary and/or sufficient conditions for perfect reconstruction of any possible sparse vector [START_REF] Foucart | A Mathematical Introduction to Compressive Sensing[END_REF]. Another question of interest is the study of CS as a communication tool. To do this, average analysis over the signal is required, where conditions are computed such that perfect recovery occurs with high probability. We already obtained preliminary results regarding the analysis of CS as a communication tool [START_REF] Coluccia | Exact Performance Analysis of the Oracle Receiver for Compressed Sensing Reconstruction[END_REF][START_REF]Mismatched sparse denoiser requires overestimating the support length[END_REF] and distributed CS [START_REF]Operational Rate-Distortion Performance of Single-source and Distributed Compressed Sensing[END_REF] under the hypothesis that the support is perfectly known. (For distributed CS, we also proposed practical schemes [START_REF] Coluccia | Lossy compression of distributed sparse sources: a practical scheme[END_REF].) A remaining question is under which conditions can the support of the sparse signal be recovered with high probability. Such average analyses have been performed for reconstruction algorithms, where the reconstructed signal at convergence can be characterized. For instance, Basis Pursuit [START_REF] Tropp | Signal recovery from random measurements via Orthogonal Matching Pursuit[END_REF], Matched Filter and linear MMSE [START_REF] Reeves | Approximate Sparsity Pattern Recovery: Information-Theoretic Lower Bounds[END_REF], thresholded linear MMSE [START_REF] Tulino | Support Recovery with sparsely sampled free random matrices[END_REF], Maximum Likelihood and Approximate message passing in [START_REF] Reeves | Approximate Sparsity Pattern Recovery: Information-Theoretic Lower Bounds[END_REF], Symbol-by-Symbol MAP and thresholded Lasso in [START_REF] Tulino | Support Recovery with sparsely sampled free random matrices[END_REF]. When the reconstruction is based on a greedy algorithm (matching pursuits, etc...), the analysis is very tricky due to the iterative nature of the algorithm, which introduces dependence among iterations. An interesting question is therefore under which conditions (size of the measurement matrix, distribution of the coefficients) can the support of the sparse signal be recovered by a greedy and iterative algorithm such as orthogonal matching pursuit.

Chapter 1 Introduction

 1 My research lies in the area of signal and image processing, digital communication, information theory, computer vision and machine learning. It tackles the question of universality in digital communication: digital communication refers to the problem of a source sending a digital (or digitalized) data over a noisy channel (see Fig. 1.1), and universality means that neither the source statistics, nor the channel statistics are known a priori. Another characteristic of my research is to consider the problem of communicating visual data: image and video.

Figure 1 . 1 :

 11 Figure 1.1: Scheme of a digital communication system as drawn in the seminal paper [87, Fig. 1].

Figure 1 . 2 :

 12 Figure 1.2: Separate source and channel encoding is optimal [26, Fig. 7.15].

Figure 2 . 1 :

 21 Figure 2.1: Source coding scheme.

Figure 2 . 2 :

 22 Figure 2.2: Efficient lossy compression: Uniform scalar quantizer and VL lossless compression.

Figure 1 . 4 .

 14 Figure 1.4. Closed-loop predictive quantizer

Figure 1 . 4 .

 14 Figure 1.4. Closed-loop predictive quantizer

Figure 2 . 5 :

 25 Figure 2.5: Predictive coding explained in Figures, from[START_REF] Moreau | Tools for Signal Compression[END_REF] Fig. 1.3 and 1.4]. The principle of predictive coding is best explained with (a). A prediction v(n) of the current symbol x(n) is computed from the input sequence {x(n)} n , with the filter A (z), and is subtracted from the current symbol x(n) to yield the residue y(n). This residue is then quantized, and this is the compressed version of x(n). This scheme is however impractical as it requires to send the prediction v(n). To avoid sending additional data, the prediction is computed on the quantized coefficients at the decoder (b), but this scheme is still not satisfactory as it requires a feedback loop. Finally, the feedback loop is avoided in (c), by duplicating the decoder at the encoder. This scheme also avoids sending any additional data (neither feedforward nor feedback).

CHAPTER

Fig. 5 :

 5 Fig. 5: Rate-distortion curves averaged over the 24 luminance images from the Kodak suite.

Figure 2 . 7 :

 27 Figure 2.7: RD performance of Transform coding, with a deep transform learned with a RD criterion on a dataset of images [32, Fig. 5]. Performance averaged over 24 images.

CHAPTER 2 .

 2 COMPRESSION AND UNIVERSALITY Processing, vol. 23, pp. 5334-5347, Dec. 2014. Major publication: [13] M. Bevilacqua, A. Roumy, C. Guillemot, and M.-L. Alberi Morel, "Video superresolution via sparse combinations of key-frame patches in a compression context," in 30th Picture Coding Symposium (PCS), Dec. 2013.The two Previous Sections proposed schemes where the model is not send. Another extreme consists in sending the model only. Consider a video scheme, in which the receiver mostly receives Low Resolution (LR) images and sometimes High Resolution (HR) images, called KeyFrames (KF) (Fig.2.8). At the receiver, super-resolution (SR) is used to increase the resolution, such that HR is the final rendered resolution.

Figure 2 . 8 :

 28 Figure 2.8: Sent and received Image Sequence in the SR based video coding scheme. The receiver extrapolates the LR frames and renders a full HR sequence.

Figure 2 . 9 :

 29 Figure 2.9: Principle of the SR algorithm.

Figure 2 . 10 :

 210 Figure 2.10: Patches in an image have different types (smooth area, edge, and texture) and therefore have different complexities measured as the number of DCT coefficients required to efficiently approximate a patch.

2. 8 .

 8 DISTRIBUTED SOURCE CODING: MODEL SELECTION AND MISMATCH 29

Figure 2 . 11 :

 211 Figure 2.11: Source coding with SI at the encoder and the decoder (predictive coding). Source coding with SI at the decoder only (Slepian Wolf (SW) coding).

Figure 2 . 12 :

 212 Figure 2.12: Source coding with SI at the decoder and set of SIs at the encoder (Compound code CC).

  4.1.

Figure 2 . 13 :

 213 Figure 2.13: Source coding with bitextraction at the server.

  x = arg max x P(X = x|Y = y) (3.3) 3.1. TRANSMISSION WITHOUT PERFECT CHANNEL KNOWLEDGE 35 to introduce the hidden variable h and to iterate between the computation of the symbol densities and the estimation of the channel coefficients. xi+1 = arg max x P(X = x|Y = y, H = ĥi ) (3.4) ĥi+1 = E P(X=x i+1 |Y=y,H= ĥi ) [LM S(x i+1 )] (3.5)

Figure 2 :

 2 Figure 2: Receiver structure.

  Figure 1: Transmitter structure.

Figure 2 :

 2 Figure 2: Receiver structure.

Figure 3 . 1 :

 31 Figure 3.1: Transmitter and Turbo receiver.

40 CHAPTER 4 .

 404 CONCLUSION AND PERSPECTIVESvision, areas in which I contributed.

Table 2 .

 2

1: Properties of lossless source codes

  Th. 3.4. p 55], where each typical sequence is assigned a distinct codeword, and all non-typical sequences are assigned the same codeword, -a VL [26, Th. 3.2.1], where the typical sequences are encoded with nH(X n ) bits, the non typical sequences with length n log 2 |X | bits, and a flag bit is used to indicate if the sequence is typical or not, -a VL code, where more probable symbols (or input sequences) are encoded with shorter codewords (like Huffman, Shannon [26, Sec 5.4.-5.8] or Arithmetic code [26, Sec 13.3.]

	log 2 P (x)	bits per source symbol,	(2.6)
	and can be achieved by either:
	-a FL code [42,

7 )

 7 FL unaware codes of memoryless sources with finite alphabet experience an excess compression rate, compared to distribution aware codes. Therefore, universal coding focuses on VL codes. Consider a memoryless source with distribution P ∈ P. Here, P is the subclass of i.i.d. sources. Further assume that the set Q ⊆ P to which P belongs, is known. With a FL code, the optimal compression rate is the worst (highest) compression rate sup Q∈Q H(Q)[START_REF] Cover | Elements of information theory[END_REF] Th. 11.3.1] [46, Th. 1.3.1]. This leads to an excess rate with respect to optimal distribution aware coding: As was seen above, even for the simple case of i.i.d. sources, there exists no FL universal codes. Therefore, universal coding focuses on VL codes.At this stage of the development, it is important to be precise about the notion of distribution knowledge. The statement[START_REF] Cover | Elements of information theory[END_REF] Th. 11.3.1] [46, Th. 1.3.1] is given a different interpretation in

	Excess Rate = sup Q∈Q	H(Q) -H(P )	bits per source symbol.	(2.8)

Table 2 .

 2

	2: Definition of the Minimax regret

  .4.

	Class P	Asymptotic equivalent function r(n)
	i.i.d. process [27, Th. 7.5]	|X | -1 2	log n
	mth order Markov process [27, Th. 7.5]	|X | m |X | -1 2	log n

compound process with |S| states from [27, Th. 7.4] |S| |X | -1 2 log n Table 2.4: Asymptotic equivalent function to the Minimax regret and Minimax redundancy for some class of processes.

  2. COMPRESSION AND UNIVERSALITY 2.6 Coding without sending the model: a fixed transform learned on the data

	Publications related to this topic:
	[30] T. Dumas, A. Roumy, and C. Guillemot, Shallow sparse Autoencoders versus sparse coding
	algorithms for image compression, in IEEE International Conference on Multimedia and
	Expo (ICME), 2016.
	[31] T. Dumas, A. Roumy, and C. Guillemot, Image compression with stochastic Winner-Take-
	All Autoencoder, in ICASSP (IEEE International Conference on Acoustics, Speech, and
	Signal Processing), 2017.
	[32] T. Dumas, A. Roumy, and C. Guillemot, Autoencoder based Image compression: can the
	learning be quantization independent? in ICASSP (IEEE International Conference on Acous-
	tics, Speech, and Signal Processing), 2018.

  Roumy, and C. Guillemot, "Maximum Likelihood BSC parameter estimation for the Slepian-Wolf problem," IEEE Communications Letters, vol. 15, no. 2, pp. 232-234, Feb. 2011. [40] E. Dupraz, A. Roumy, and M. Kieffer, "Source Coding with Side Information at the Decoder and Uncertain Knowledge of the Correlation," IEEE Transactions on Communications, vol. 62, no. 1, pp. 269 -279, Jan. 2014.

	Major publication:
	[102] V. Toto-Zarasoa, A. Roumy, and C. Guillemot, "Source modeling for Distributed
	Video Coding," IEEE Trans. on Circuits and Systems for Video Technology, vol.
	22, no. 2, Feb. 2012.
	Also

log n. Therefore, for these classes, VL

https://intercom.cominlabs.u-bretagneloire.fr/

Note that the compression of meteorological data is far from anecdotal. In 2017, the weather channel websites received every minute a deluge of 18 million forecast requests -an increase of 22 % from the previous year, https://www.domo.com/blog/data-never-sleeps-5/.

https://news.itu.int/versatile-video-coding-project-starts-strongly/

A database, containing highly correlated data, is compressed into a single file in order to exploit the redundancy. Users can access any subpart of the database. The requested subpart is delivered without transmitting the whole database, and also without encoding/decoding the data at the server. am currently leading a project called InterCom, for Interactive Communication 3 on this research topic. The first goal is to derive optimal compression rates in terms of storage rate but also transmission rate in more realistic scenarios (see Fig. 4.1). The second goal is to construct practical schemes for both applications: FTV and IoT.

Open problems are:

-Building an entropy coder for MRA. The entropy coder is the core of the compression algorithm. The proof in [START_REF]Universal lossless coding with random user access: the cost of interactivity[END_REF] relies on the construction of embedded codes, and this suggests the use, in practice, of variable rate channel codes. Here, and by contrast with existing codes, the characteristics of the data, i.e. the correlation between the sources, have to be taken into account. -Zero error vs vanishing error rate. The proof relies [START_REF]Universal lossless coding with random user access: the cost of interactivity[END_REF] on a vanishing error argument. However, in practice, the scheme must provide zero error for any length. This is of great importance for lossless applications (building health monitoring, for instance). This is also needed to avoid error propagation in the context of lossy video compression implemented with a divide and conquer approach (Sec. 2.4). -Universal coding. We have shown that, at infinite length, the lack of model knowledge does not impact the compression rates [START_REF]Transmission and Storage Rates for Sequential Massive Random Access[END_REF]. However, to answer the question of universal MRA coding, and select the optimal model class, there is a need to characterize the impact of a wrong model on the compression performance at finite length. -Real data have to be preprocessed before being entropy coded. Indeed, in a practical system, the entropy coder can only tackle limited and remaining dependencies. Therefore a need for preprocessing to handle most of the redundancy. Moreover, this preprocessing tasks will depend on the type of data (image, video vs meteorological data 4 ), and on their representation (point cloud, meshes, pixel values).