Dr Wenbin Zou

Dr Weizhi Lu

Dr Jinglin Zhang

Dr Xiaohui Yi

Dr Yu Zhao

Dr Cong Bai

Wei Liu

Han Yuan

Xiao Fan

Dandan Yao

Yang Yang

Qingyuan Gu

Zhigang Yao

Liang Tang

Hua Fu

Jia Fu

Tian Xia

Shibo Liu

Yanping Wang

Jiali Xu

Xu Zhang

Hengyang Wei

Hua Lu

for the pleasure time in Rennes.

Thanks to my parents, grandparents and other family

Résumé en français

Au cours de ces dernières décennies, l'image numérique en tant que média fut un moyen particulièrement efficace pour le stockage et la transmission de l'information. Pour des utilisations académiques, les documents, les archives d'art, et les images médicales ont été numérisés afin de faciliter le stockage et la recherche. En outre, la production massive d'images numériques émerge dans les applications multimédias. Récemment, la société internet Yahoo a affirmé que pas moins de 880 milliards photos ont été prises en 2014. Selon les sources issues du SEC(U.S. Securities and Exchange Commission), plus de 250 millions des photos sont téléchargées par Facebook tous les jours. Afin de réduire les ressources de stockage pour la représentation d'une image, l'organisation internationale de normalisation (ISO) a établi et publié de nombreux standards de compression d'image, tels que JPEG, JPEG, JPEG2000 et JPEG XR. En plus des normes, il existe ensuite de nombreuses méthodes de compression efficaces, telles que CALIC ou SPIHT. Les contributions présentées dans cette thèse se situent dans le contexte du codage LAR (Locally Adaptive Resolution). Ce projet de recherche doctoral vise à proposer solution améliorée du codec de codage d'images LAR, à la fois d'un point de vue des performances de compression et de la complexité. L'étude présentée dans cette thèse concerne principalement les techniques d'optimisation débit/distorsions (RDO) pour LAR. Avec un double objectif d'efficacité de codage et de basse complexité, un nouveau schéma de codage LAR est également proposé dans le mode sans perte (compression entièrement réversible).

Chapitre 1 la Technologie de Compression d'image

Afin de dresser le contexte de cette thèse, ce chapitre donne une introduction générale à la compression d'image. est la décorrélation qui permet de réduire la redondance spatiale. Cette redondance représente la similitude des pixels locaux. Les techniques utilisées sont la prédiction, la transformation, la mise en correspondance, etc. La deuxième étape, la quantification, est classiquement utilisée en compression avec pertes. A l'issue de l'étape précédente, il existe de très nombreuses valeurs autour de zéro, permettant de réduire la dynamique des coefficients, ce qui induit la redondance statistique. Cette redondance est réduite par l'étape suivante, le codage de la entropie. une image basse résolution, et le codeur spectral traitant de la texture (Fig. 2). L'originalité de l'algorithme repose sur le principe suivant : la résolution locale, i.e. la taille des pixels, peut varier en fonction de l'activité locale. Ainsi, les pixels de petite taille se situent naturellement sur les contours de l'image, alors que les zones uniformes sont représentées par un bloc de grande taille. Cette grille de résolution spécifique s'appuyant sur le Quadtree déterminé par un Résumé étendu en français gradient morphologique. En outre, une technique, l'interleaved S+P, a été utilisée pour la propriété de scalabilité de codage de la source. Elle est constituée de deux parties : la construction et la décomposition de la pyramide. est donnée par l'ensemble {I l } l max l=0 , où l max désigne le sommet de la pyramide et l = 0 la pleine résolution. Quatre blocs sont représentés au niveau supérieur par un bloc de valeur égale à la moyenne des deux blocs sous-jacents de la première diagonale (Fig. 3).

           I 0 (i, j) = Y(i, j), l = 0; I l (i, j) = I l-1 (2i, 2 j) + I l-1 (2i + 1, 2 j + 1) 2 , l > 0, (1)
avec 0 ≤ i ≤ N l x , 0 ≤ j ≤ N l y , où N l x = N x /l and N l y = N y /l. La transformation de la deuxième diagonale d'un bloc 2×2 donné peut en effet aussi être vue comme la réalisation d'une seconde pyramide.

Le processus de décomposition dyadique de la pyramide résulte de l'extension de la méthode de prédiction. Pour la première pyramide, la valeur de la moyenne étant déjà connue (niveau supérieur de la première pyramide). Il faut ainsi estimer la valeur gradient de la première diagonale d'un bloc 2 × 2 :

2 Gl (i, j) =2.1 0.9I l+1 (i, j) + 1 6 I l (2i + 1, 2 j -1) + I l (2i -1, 2 j -1)

+ I l (2i -1, 2 j + 1) -0.05 I l (2i, 2 j -2) + I l (2i -2, 2 j) -0.15 I l+1 (i, j + 1) + I l+1 (i + 1, j) -I l+1 (i, j)

.

Résumé étendu en français 7

Pour la deuxième pyramide, l'estimation de la moyenne de la deuxième diagonale fait intervenir une prédiction :

3 Ml (i, j) = 1 4 β 0 0 I l (2i -1, 2 j + 1) + I l (2i, 2 j + 2) -I l (2i + 2, 2 j) + I l (2i + 1, 2 j -1)

+ β 1 0 1 M l (i, j) , (3)
où (β 0 0 , β 1 0 ) = (0.25, 0.75), et 1 Ml (i, j) représente la valeur reconstruite du coefficient I l+1 (i, j). La valeur gradient de la deuxième diagonale se calcule selon :

3 Gl (i, j) =β 0 1 I l (2i -1, 2 j + 1) + I l (2i, 2 j + 2) -I l (2i + 1, 2 j -1) -I l (2i + 2, 2 j) -β 0 1 I l (2i -1, 2 j) + I l (2i -1, 2 j + 2) -I l (2i, 2 j -1) -Ĩl (2i, 2 j + 1) ,

où (β 0 1 , β 1 1 ) = (3/8, 1/8). Ĩl (2i, 2 j + 1) correspond à la prédiction du Wu de la troisième passe appliquée au pixel I l (2i, 2 j + 1).

La réalisation de la deuxième phase de décomposition de la pyramide permet la reconstruction de la texture. Soit m e (u 1 , u 2 , ..., u n ) la valeur médiane d'un ensemble (u 1 , u 2 , ..., u n ) de n valeurs. La valeur estimée du gradient de la première diagonale situe dans une zone de texture est donnée par 2 Gt (i, j) = 1 4 m e I l (2i -2, 2 j), I l (2i, 2 j -2), I l (2i -1, 2 j -1)

+ m e I l+1 (i + 1, j), I l+1 (i, j + 1), I l+1 (i + 1, j + 1) .

(5)

Pour la deuxième diagonale, les valeurs de moyennes sont traitées par l'application de la relation Eq. (3), où (β 0 0 , β 1 0 ) = (0.37, 0.63). Quant aux gradients, leur estimation est obtenue après application de Eq. ( 4).

Comme le codec LAR est un codec prédictif, il nécessite que les valeurs des erreurs de prédiction soient entièrement reconstruites. Le codeur arithmétique est implémenté dans le codec LAR pour effectuer un codage entropique efficace.

Chapitre 3 Le modèle RDO pour le codec LAR

Au début de cette étude, le codec LAR ne mettait pas en oeuvre de techniques d'optimisation débit/distorsions (RDO). Ainsi dans ce travail, il s'agit dans un premier temps de caractériser l'impact des principaux paramètres du codec sur l'efficacité de compression, sur la Résumé étendu en français caractérisation des relations existantes entre efficacité de codage, puis de construire des modèles RDO pour la configuration des paramètres afin d'obtenir une efficacité de codage proche de l'optimal.

                                              T hr 2,1 = H G α (quqp + ∆ • β) T hr 2,2 = H G α (quqp + ∆ • β) + 10 , si quqp ≥ 53              T hr 1,1 = H G α (1 + ∆ • β 53 ) quqp T hr 1,2 = H G α (1 + ∆ • β 53 ) quqp + 10 , si 0 < quqp < 53 (6)
Où H G est l'entropie du gradient, (α, β) = (17.93, 121.07), ∆ est un coefficient du gradient.

(T hr i,1 , T hr i,2 ) sont les valeurs sont définies pour T hr et fonction.

De plus, basée sur ces modèles RDO, une méthode de « contrôle de qualité » est introduite qui permettant de coder une image à une cible MSE donnée. Cette méthode se fonde un modèle

Y l (i, j) =                I(i, j) , l = 0           1 4 1 k=0 1 m=0 Y l-1 (2i + k, 2 j + m)           , l > 0 (9)
Résumé étendu en français 11 Où 0 ≤ i ≤ N x /2 l . . signifie l'arrondi vers le bas.

Pour la prédiction multi-niveaux, l'estimation de la moyenne des deux diagonales est Gd,l (2i, 2 j) = α 4 G d,l (2i -2, 2 j -2) + G d,l (2i + 2, 2 j -2)

+ β Y l+1 (i -1, j -1) + Y l+1 (i + 1, j + 1) -Y l+1 (i -1, j + 1) -Y l+1 (i + 1, j -1) (10)
Où α = 0.3, β = 0.035. L'estimation de la gradient de la première diagonale fait intervenir une prédiction :

G1,l (2i, 2 j) = 0.153 1.5 Y l (2i -1, 2 j -1) -M 1,l (2i + 2, 2 j + 2)

+ 0.5 M 1,l (2i -2, 2 j) + M 1,l (2i, 2 j -2) -M 1,l (2i, 2 j + 2) -M 1,l (2i + 2, 2 j) (11)
La valeur gradient de la deuxième diagonale se calcule selon :

G2,l (2i, 2 j) = α 2 Y l (2i, 2 j) -Y l (2i -1, 2 j + 1) + Y l (2i + 2, 2 j) -Y l (2i + 1, 2 j + 1)

+ 1 -α 2 Y l (2i + 1, 2 j -1) -Y l (2i, 2 j) + Y l (2i + 1, 2 j + 1) -Y l (2i, 2 j + 2) (12) Où G2,l (2i, 2 j) = 3 8 Y l (2i + 1, 2 j -1) + Y l (2i + 2, 2 j) -Y l (2i -1, 2 j + 1) -Y l (2i, 2 j + 2) - 1 8 Y l (2i, 2 j -1) + Y l (2i + 2, 2 j -1) -Y l (2i -1, 2 j) -X l (2i + 1, 2 j) (13)
Après la prédiction, les erreurs sont classées en quatre groupes, afin de réduire l'entropie de la séquence à coder. Cette classification se fonde sur le fait que l'entropie de la source diminue quand la source est séparée en deux sous-sources avec les différentes distributions de probabilité. La Figure . 8 présente un exemple pour la gradient de la première diagonale de l'image « bike ».

Le LAR-LLC utilise le codeur Huffman pour effectuer un codage entropique efficace.

Résumé étendu en français

Introduction

In nowadays, digital images are commonly captured by digital cameras, smart-phones, tablets and so on. The main usage of the digital image is to record the visual information for the conservation and communication. In the academic field, the digital imaging has been a practical tool for the storage of important documents, art archives, and medical images. Besides, the massive production of digital images emerges in multimedia applications. The internet corporation Yahoo claimed that as many as 880 billion photos were taken in 2014 [pop13]. According to the quote directly from the SEC doc [SC12], on average more than 250 million photos per day were uploaded to Facebook in the three months ended December 31, 2011. That's almost 3,000 photos per second. All those photos take up a lot of space on servers, stored more than 100 petabytes (100 million gigabytes) [pop12]. Meanwhile, for popular photo sharing games, the transmission of digital images also occupies the bandwidth of the telecommunication.

In this context, the image compression technique is required. The aim of this technique is to reduce the bit resource for the representation of an image. In practical cases, the image compression codec should be able to perform lossless and lossy compressions. The lossless coding is mainly used for the original archive and other important cases where any losses are not allowed. The lossy coding aims at a high compression ratio and is commonly applied to the commercial multimedia, such as videos and images for the entertainment in internet. In the case of social networking, different targeted devices exhibiting different screen resolutions have to be considered. Moreover, those terminals have also different computational abilities.

Therefore, there is a need for the codec with both resolution and computation scalability.

With the development of digital cameras, computer entertainments and internet communications, different image codecs have been proposed. The mostly used one is JPEG which has been standardized by the JPEG committee in 1992 [START_REF]Information Technology -Digital Compression and Coding of Continuous-tone still Images -Requirements and Guidelines[END_REF]. It is based on the Discrete Cosine Transform (DCT) with a dedicated quantization process. This coding method has a low computational complexity and has been well implemented in both software and hardware.

The drawbacks are the limited quality of the decoded image and the lack of the lossless co-Introduction ding function. For the lossless function, JPEG-LS was standardized in 1998 [START_REF]Information technology -Lossless and near-lossless compression of continuous-tone still images -Baseline[END_REF]. It adopts a predictive coding method which is different from the JPEG. In 2002, JPEG committee standardized JPEG2000 which supports both the lossy and the lossless coding [START_REF]Information technology -JPEG 2000 image coding system : Core coding system[END_REF]. Compared with JPEG, its decoded images have better objective qualities, such as PSNR, at the same compression ratios. Besides, JPEG2000 supports the multiresolution, the rate control functions and so on. However, JPEG2000 requires high computation, limiting its application. Then, JPEG XR was created by Microsoft and standardized in 2009 [START_REF]JPEG XR image coding system -Part 2 : Image coding specification[END_REF]. It has a lower computational complexity than that of JPEG2000 and better coding quality than JPEG.

Besides these standards, other image coding methods were proposed to improve the compression performance such as CALIC and SPIHT which are introduced in Section 1.3. The LAR (Locally Adaptive Resolution) codec, which is explained in Chapter 2, was also designed as an image coding solution. It is the base for the study in this thesis.

The contributions presented in this thesis aim at the improvement of the coding performance of the LAR codec. Although the LAR codec has a complete structure, its coding steps are still under a rough configuration and need a further analysis to achieve a preferable performance. The first research aims at the study of the distortion caused by different configurations. This work gives a better choice of parameters for the rate distortion optimization. The second research focuses on a more efficient coding solution with a low computational cost.

The thesis is organized as follows. The commonly used image compression methods are firstly presented in Chapter 1. Next, Chapter 2 introduces the LAR codec. The rate distortion optimization scheme for the LAR codec is proposed in Chapter 3. In Chapter 4, the lowcomplexity lossless image codec is designed and tested. Finally, the conclusion and prospects are presented in Chapter 5.

Image compression technology

The commonly applied image coding structure and methods are presented. Based on these methods, the standardized schemes and some non-standardized codecs are briefly introduced.

Their lossy and lossless coding performance finally are compared respectively.

Introduction to LAR codec

The coding steps of the LAR codec are presented. In this chapter, the framework of the LAR codec is introduced step by step. The quadtree partition is firstly used to detect the local activity of pixels of the image and draw a quadtree map which is determined by a threshold.

Based on the map, the image is degraded from the full resolution to lower resolutions level by level, generating to a pyramidal structure. Then, a decomposition starts from the lowest resolution level to higher resolution levels, until the full resolution image is reconstructed.

The prediction and the quantization of the prediction errors are used in the decomposition.

Finally, the quantized prediction errors are coded. Although the LAR has the complete coding framework, the coding parameters have not been well configured to find the optimal coding performance. In order to relieve this limitation, a Rate-Distortion-Optimization (RDO) model is proposed in Chapter 3.

Rate-Distortion-Optimization (RDO) model for LAR codec

In this chapter, the distortions caused by the change of the quantization factor and the quadtree partition threshold are studied to understand the rate-distortion performance of the LAR codec. Next, the relationship between the optimal coding efficiency and changes of the parameters are analyzed in order to propose a RDO model for the LAR codec. The RDO model is tested and the experimental results are discussed. Based on the RDO model, a linear quality control (QC) model is also built. This QC model is used to constraint the distortion of the coded image to the target one which is set before the coding by the user. Besides, a locally adaptive scheme of the RDO model is proposed to improve the perceptual quality of the decoded image.

Finally, the coding performance of optimized LAR codec is compared with other image coding schemes.

A low complexity lossless image codec : LAR-LLC

The LAR codec has the lossless coding function. However, the coding performance is not as efficient as the one of JPEG2000. Therefore, we propose a new lossless coding method aiming at improving the compression ratio and reducing the computational complexity. This method still uses the framework of the LAR, but changes each coding steps. It adopts a new transform for the resolution scalability and reconstructs images in different resolutions according to new context models for prediction. Besides, it exploits the remaining correlation of the prediction errors, and a classification process is proposed to improve the compression efficiency. Finally the lossless coding efficiency of the codec is compared with standard codecs and recently proposed image codecs.

Conclusion and Prospects

The contributions of the thesis are based on a predictive image codec. An RDO model is firstly proposed to this codec, then a quality constraint scheme and a locally subjective quality Introduction enhancement scheme are introduced. After, a new complete lossless image coding method is proposed to achieve an efficient compression ratio with a low computational complexity.

Thanks to the study presented in this thesis, different ideas are proposed as prospects for the image coding. Firstly a scheme of the lossy coding based on the characters of the Human Visual System is designed. This envisage can be seen as an extension of the locally adaptive scheme of the RDO model introduced in Chapter 3, but the idea can be a reference for other image coding solutions. Another idea is to improve the efficiency of the classification step used in the lossless codec introduced in Chapter 4. More analysis and experiments are required to design a new pre-coding scheme.

Chapter 1

Image compression technology

Modern industry employs images extensively. As an important medium, the image is a common form used for the storage and transmission of the visual information. Besides the traditional photography, the image is also applied for the technical drawing, art archiving, medical imaging, film production and so on. These extensive applications bring a massive storage of images. This requirement encourages researchers on the image compression technology to make use of the limited storage and communication capacity efficiently.

A digital image is a rectangular array of picture elements, arranged in m rows and n columns. The size m × n refers to the resolution of the image and the elements are called pixels. In an image, especially for the natural image, some adjacent pixels probably have the same or very similar colors. These pixels are highly correlated. This correlation is also called spatial redundancy. Image compression technologies mainly focus on the reduction of the spatial redundancy to save the required capacity of the image.

Y i-1 Y i-2 Y i-3 Y i-4 Y i-5 Y i-6 Y i-7 Y i-8 Y i-9 Y i-10 Y i-11 Y i-12
Reference space Predicted pixel In order to exploit the spatial redundancy, a feasible scheme is to use the context of a pixel to predict its value. Fig. 1.2 illustrates the position of the context and the predicted pixel X i .

Pixels Y i , which are adjacent to X i , form a reference space. Pixels in the reference space can be selected out to arranged into a context model. This context model can be a first-order linear combination of Y i [START_REF] Wu | Lossless compression of continuous-tone images via context selection, quantization, and modeling[END_REF] [CH09], as defined in Eq. (1.1), where X is the estimated value of X.

X(i) = p j=1 a j Y(i -j) (1.1)
The linear model is easy to calculate. However, the correlation between X and Y is variable and probably not linear. One solution is to use non-linear model [START_REF] Zhang | Nonlinear prediction for gaussian mixture image models[END_REF]. This model adopts two or higher order relations to describe the non linear correlation. Another solution is still apply the linear one, but select it from a linear context model set [PKC + 10]. Both solutions make efforts to give a precise predicted value for X i . It leads to a low amplitude prediction error for each pixel. The reason why the prediction is helpful for the compression can be shown by the change of entropy. Assuming that the pixel of the image is from a set of X = {X 1 , X 2 , X 3 , ..., X n }, the probability of occurrence of X is {p 1 , p 2 , p 3 , ..., p n }. The uncertainty of the pixel can be represented by the entropy H(X).

H(X) = H(p 1 , p 2 , p 3 , ..., p n ) = - n i=1 p i log p i (1.2)
If we consider the pixels Y of the reference space in order to predict X, the image entropy becomes H(X|Y). It means the uncertainty of X when Y has been known. Because after prediction, the prediction error replaces the pixel, H(X|Y) can also be seen as the entropy of the prediction error. In information theory, it exits that

H(X|Y) ≤ H(X) (1.3)
and the equality exits only when Y is independent to X. Because Y is correlated to X, H(X|Y) must be less than H(X). Another fact is that the entropy also represents the required least average codeword length by the entropy coding. Thus, after the prediction step, the information of the image needs less codeword resource than that without the prediction by the entropy coding. As a result, the prediction is an effective process to reduce the spatial redundancy.

Transform

Transform is another way to convert the pixels (which are correlated) of an image to a more compact representation where they are decorrelated. One proper method of the transform is the spatial rotation. Take the image "lena" as an example. We scan the image in raster order and groupe pairs of adjacent pixels (x, y). Next we plot pairs (x, y) of pixels in two-dimensional space. For the correlation of adjacent pixels, x and y normally have similar values. Most pairs (x, y) locate on the line y = x. We rotate the image by multiplying all points with a 45 • clockwise rotation matrix (1.4). And then we plot the new (x , y ) in the space. The rotated pairs chapter 1

decoder X i ... ... Y i-1 Y i-2 Y i-3 Y i-4 Y i-5 Y i-6 Y i-7 Y i-8 Y i-9 Y i-10 Y i-11 Y i-12
Reference space Predicted pixel R Before rotation

After rotation (x , y ) = (x, y)

        cos 45 • -sin 45 • sin 45 • cos 45 •         = (x, y)
In lossy coding, less important tranformed coefficients are quantized to get many 0 elements which are helpful for the entropy coding. This loss does not change the original image a lot. The discrete cosine transform (DCT) [START_REF] Xiong | A dct-based embedded image coder[END_REF] [LG00] and the discrete wavelet transform (DWT)

[ABMD92] [XROZ99] [DWW + 07] are common used transforms for the image coding.

Matching

Matching also takes advantage of the spatial correlation. As the reference space in the prediction, there is a searching space for matching. But the matching deals with a set of pixels instead of only one in one time. Neighbors of a pixel X tend to have the same value of X or very similar values to it. As a result, if X is the leftmost pixel in a target set S t , its left neighbors will have close values to X, and a set of neighbouring pixels (searching set) on the left, or in chapter 1

the searching space, will probably also match the target set S t .

R

After rotation

X

Searching space

Searching set

Target set S t ... ... Besides the pixels on the left and above X, the pixels on the right and above X are also available. It is reasonable to use an around target set S t for the comparison. In practice, M × M blocks of pixels are often used, instead of individual pixels X and this method is called block matching [START_REF] Parsiani | State of the art iterated block matching fractals in image compression[END_REF].

Scalar Quantization

Quantization is a common approach in digital signal processing. It aims at assigning a variable quantity to discrete values rather than to a continuous set of values . In data compression, quantization is often used to convert large values of the data to smaller ones which need less space for storage or transmission. Consider a data signal with a data range [-N, N], partition the signal range into M disjoint intervals {I q }. Within each interval, a point xq is selected as the output value of this interval I q , as shown in Fig. 1.6. Quantization is a procedure using index q to represent values in I q , its inverse procedure is to output xq according to the index q. For example, let x be a given value contained in the interval I q , the quantization Q(x) and dequantization Q -1 (x) can be expressed as

I q = [t q , t q+1 ), q = 0, 1, ..., M -1 with -N = t 0 < t 1 < ... < t M = N (1.10) HH 2 HL 2 LL 2 LH 2 LL 1 HL 1 Tile HH 1 LH 1 Resolution R 2 Resolution R 1 Resolution R 0 R / L D 0 L j L j -1 D j D j -1 ...
Q(x) = q Q -1 (q) = xq (1.11)

Variable length coding

Variable length coding (VLC) is a kind of coding methods mainly used in the entropy coding which aims at the lossless compression of specific data streams. Let {X n } be a data stream with an alphabet A X and probability distribution p X . VLC methods allocate a distinct codeword c x to each element x ∈ A X . The length of the c x is variable and often decided by p X . The sequence of the outcomes x n from the random process are represented by the codewords c x n . The chapter 1

x n p x n c 1

x n c 2

x n

x 1 0.05 000 000 (1.12)

x
H(X n ) = -
The entropy indicates the least number of bits required on average. If using 2-bit fixed-length codewords 00, 01, 10 and 11 to assign the four symbols, the redundancy caused by this coding is R(2bit) = 2 -H(X n ) = 0.5095. The VLC mode, as c 1 x n and c 2

x n in Table 1.1, has a redundancy

R(V LC) = (3 × 0.05 + 3 × 0.1 + 0.25 × 2 + 0.6 × 1) -H(X n ) = 1.55 -1.4905 = 0.0595 (1.13)
which is much less than R(2bit). However, the code stream formed by c 1 x n is not decodable. When decoder reads the code "011", it can not recognize which symbols this code stands for, "x 3 x 4 " or "x 2 " only. To facilitate efficient decoding, the VLC only adopts "prefix codes". A prefix code is one in which no codeword is the prefix of any other codeword. This property requires that once a certain bit pattern has been assigned as the code of a symbol, no other codes should start with that pattern. As shown in the codewords c 2

x n , Once the string "1" was assigned as the code of x 4 , no other codes could start with 1. Once "01" was assigned as the code of x 3 , no other codes could start with 01. This is why the codes of x 1 and x 2 had to start with 00 and became 000 and 001.

From the example above, it can be found that VLC has two properties : (1) The length of Still image coding standards 29 the codeword is variable. Assigning short codes to symbols which occur more frequently in order to reduce required average codeword length ; (2) Codewords have the prefix property.

The classic design of VLC, such as Huffman coding, Golomb coding and Arithmetic coding, are common methods used in data compression. In practical image coding schemes, the classic methods are combined with other processes to make up a complex VLC approach. As noted above, the probability of the symbol is important for the coding ratio. However, the statistic of probability delays the overall coding and goes against the parallel processing. One solution is to set context states which identify the most probable symbol. The context state is adaptive during the coding. This approach can be found in MQ coder [START_REF] Saidani | Implementation of jpeg 2000 mq-coder[END_REF] and context-based adaptive binary arithmetic coding (CABAC) [START_REF] Marpe | Context-based adaptive binary arithmetic coding in the h.264/avc video compression standard[END_REF].

Conclusion of common methods

Image compression methods are not limited to the approches above. Some methods are designed for specific type of images or application scenarios. For example, the fractal coding is suited for images which have parts looking like other ones [START_REF] Wohlberg | A review of the fractal image coding literature[END_REF]. Progressive coding is adaptive to the storage and transmission capacity for the multiresolution. Modern image compression schemes have distinctive coding procedures to each other. One scheme can adopt several coding concepts and use two or more methods for different parts of the image, or in different stages during the procedure. The International Organization for Standardization (ISO) and International Telecommunication Union (ITU) have announced image compression standards for practical applications. Four widely used JPEG series will be introduced in Section 1.2.

Still image coding standards 1.2.1 JPEG

JPEG is the first international compression standard for the continuous tone still images, both grayscale and color images [START_REF] Wallace | The JPEG still picture compression standard[END_REF] [START_REF]Information Technology -Digital Compression and Coding of Continuous-tone still Images -Requirements and Guidelines[END_REF]. It includes two basic compression methods.

A DCT (Discrete cosine transform) based method is specified for lossy compression, and a predictive method for lossless compression. The lossless mode of JPEG has not been very successful in the coding efficiency, so ISO has proposed another standard for the lossless image compression. This standard is known as JPEG-LS and will be introduced in Subsection 1.2.2.

The lossy mode of JPEG has been widely used for natural image coding due to its acceptale 1. Color images are transformed from RGB to a luminance/chrominance color space, such as YCbCr. This step is skipped for grayscale images. Because the eye is more sensitive to luminance changes than to chrominance changes, the latter can be highly compressed without great visible changes to the image.

2. Each 8×8 pixels are grouped to a unit, and each unit is transformed to an 8×8 map of the frequency components by DCT. This DCT map represents the average value and different frequency information of the image pixels. Next, a probability distribution is selected out from a distribution set. This distribution is used to encode the prediction error with a special Golomb code.

JPEG-LS has two modes in prediction. As shown in Fig. 1.8, the encoder firstly examines the adjacent pixels of x, and then decide to encode x in the run mode or in the regular mode.

If the following pixels y, z... are identical, the run mode is used. Encoder starts at x to find the longest run of pixels whose values are close to that of the pixel a. Since a has been coded

and known in the decoder, the length of the run is the only key to be encoded.

Besides the run mode, the encoder adopts the regular mode. As JPEG, for color images, JPEG2000 needs to convert them from RGB components to luminance and chrominance components. It is not required for gray images. Each component is partitioned into rectangular regions called tiles. The tile can be any size, but once the size is chosen, all the tiles have the same size during the coding. Each tile is compressed individually in four main steps.

The first step is to apply the wavelet transform to the tile to get subbands of wavelet coefficients. JPEG2000 uses the one-dimensional wavelet transform in the horizontal and vertical directions to form a two-dimensional transform. The achieved coefficients are located in four blocks and describe the horizontal and vertical characteristics of the original tile component : one is the low resolution representation (LL), one responds strongly to vertical edges and line segments (HL), one responds to horizontal edges and line segments (LH), and one responds primarity to diagonally oriented features (HH). The low resolution one LL can be transformed further to get the more low resolution image blocks. This process is then repeated several times until a certain low resolution is achieved. This procedure can be seen as a decomposition of the image block and illustrated in Fig. 1 This operation is lossy. The larger Q is, the coarser the coefficients are quantized, and the lower bitrate can be achieved. For the lossless coding, Q is essentially set to 1.0 and the coefficients are integers produced by the reversible transform. The third step is using an arithmetic coding which is called MQ coder to encode the quantized wavelet coefficients. The coder encodes the bits of coefficients, starting with the most significant bits and progressing to less significant ones by a process called EBCOT (Embedded Block Coding with optimal Truncation) [START_REF] Taubman | High performance scalable image compression with EBCOT[END_REF].

The last step is the construction of the bitstream. The bitstream is composed of packets and many "markers". The marker is a sign of certain code parts. By the use of markers, the deocoder can skip some parts of the bitstream to decode a certain code part, and display certain regions of the image before others. The bitstream is also organized by layers. Each layer contains a certain resolution information and the decoder can achieve the image progressively by releasing the layers one by one.

Besides the high coding eddiciency and scalable coding on quality and resolution, the Rate-Distortion Optimizatin (RDO) technique, which is involved in EBCOT, is also an important advantage. This technique is achieved by a post-compression rate-distortion (PCRD) optimization algorithm which can truncate each of the independent "code-block" bit-streams in an optimal way so as to minimize distortion subject to a target bitrate [START_REF] Taubman | High performance scalable image compression with EBCOT[END_REF] [START_REF] Taubman | JPEG2000 Image Compression Fundamentals, Standards and Practice : Image Compression Fundamentals, Standards and Practice[END_REF]. In EBCOT, each subband is partitioned into relatively small blocks (e.g., 64×64 or 32×32 samples), which are called "code-blocks". Each code-block, B i , is coded independently, producing an elemen-chapter 1 tary bitstream c i . It is assumed that the overrall distortion of the reconstructed image can be represented as a sum of distortions from each code-block. Let D i denote the distortion contributed by the block B i , if its elementary bitstream is truncated to the length L i , the overall length of the final compressed bitstream is constrained as L max , the selection of the set of trunction

points {z i } should have i L (z i ) i ≤ L max (1.14)
and can minimize the overall distortion D.

D = i D (z i ) i (1.15)
In order to combine Eq.(1.14) and Eq.(1.15), a quantity λ is involved. Let {z i,λ } be the set of truncation points which minimizes

D(λ) + λL(λ) = i D (z i,λ ) i + λL (z i,λ ) i (1.16)
Where λ > 0. The truncation points {z i,λ } are optimal, when the distortion D cannot be further reduced. Thus, it is desired to find a value of λ such that the truncation points {z i,λ } which can minimize Eq. (1.16) yield L(λ) = L max . Since the set of available truncation points is discrete, the suitable λ could not be found to make L(λ) be exactly equal to L max . Nevertheless, the code-blocks are relatively small and there are typically many truncation points to find λ to meet L(λ) ≤ L max . PCRD does not try to find the optimal truncation points z opt of Eq.(1.16)

directly, but focuses on D

(z i,λ ) i + λL (z i,λ ) i
for each code-block B i respectively. For a given λ > 0 :

1. Initialize z opt = 0. 2. For j = 1, 2, ..., set ∆L = L j i -L z opt i , and ∆D = D z opt i -D j i .
∆L is the increment of the length, and ∆D is the decrement of the distortion if z opt is replaced by j. If ∆D/∆L > λ, replace z opt by j. This step guarantees that D

(z opt ) i + λL (z opt ) i ≤ D (z) i + λL (z) i for all z ≤ t. 3. Set z i,λ = z opt .
Because the number of code-blocks may be very large, and the searching for z opt needs to be executed under many different λ, a subset H i which contains feasible truncation points should be found to reduce unnecessary computation. following discussion). Thus, the distortion-rate slope, S j i , which is defined as

S j i = ∆D j i ∆L j i = D j-1 i -D j i L j i -L j-1 i
(1.17) should be decreasing strictly while j increases. As a result, if S j+1 i ≥ S j i , the corresponding truncation point z j i could not be used in the searching method above. Other points which conform to Eq.(1.17) are included in H i .

PCRD can search optimal results in terms of rate-distortion. However, heavy computational resources are needed for the iteration procedure. Several methods for reducing the complexity have been proposed in the literature. One approach is to carry out the sample data coding and RDO at the same time [START_REF] Sanguankotchakorn | A new approach to reduce encoding time in ebcot algorithm for jpeg[END_REF] [KKTA05] [START_REF] Yu | Efficient rate control for jpeg-2000[END_REF]. This approach encodes some "coding passes" only included in the final code-stream. The drawback of the method is that it is required to maintain the wavelet data in the memory in order to stop and restart the coding of codeblocks. To overcome this drawback, methods collecting statistics from the already encoded code-blocks to decide which "coding passes" are needed to be encoded in the remaining codeblocks are proposed in [START_REF] Taubman | Software architectures for jpeg[END_REF] [START_REF] Chebil | Pre-compression rate allocation for jpeg2000 encoders in power constrained devices[END_REF]. In [QYZ + 04] [VVS05], methods which aim at the estimation of the rate-distortions of the code-blocks before the encoding process are introduced.

These methods may have some lost of the coding performance due to possible non optimal accuracy of estimations. Besides that, the complementary problem of the optimization of the bitrate for a target quality is addressed in [START_REF] Liu | Jpeg2000 encoding with perceptual distortion control[END_REF] [CFC + 06]. Compared with JPEG, JPEGXR also shows a better quality at an equivalent compression ratio. Its compression efficiency is close to, but not exceeds that of JPEG2000 [DSOD + 07].

JPEGXR

In

Although JPEG2000 has provided high coding ratios, it is not put into wide application for the reason of the high computation complexity, especially caused by EBCOT. JPEGXR was proposed to offer a low complexity coding solution. It has same capabilities as JPEG2000, such as the same processing steps for both lossless and lossy coding, and coding images by segmented tile regions.

JPEGXR uses an integer transform adopting a lifting scheme [TSS + 08]. This transform is close to a 4×4 DCT but is lossless. JPEGXR allows an optional overlap step. This step operates on 4×4 blocks which are offset by 2 samples in each direction from the 4×4 core transform blocks. Its purpose is to improve compression capability and reduce block-boundary artifacts at low bitrates. At high bitrates, when the block-boundary artifacts are not obvious, this overlap step is skipped for reducing the encoding and decoding time.

JPEGXR format (.JXR) is popularized mainly by Microsoft, it is supported in Adobe Flash

Player 11, Windows Imaging Component, Windows operating systems, such as Windows Vista, Windows 7 and 8, Internet Explorer from 9 to 11.

Nonstandard still image coding methods

Besides the standards, there are many other image coding methods. Some of them deal with lossy compression trying to achieve high qualities of decoded images as far as possible [START_REF] Zheng | Multilevel dct-based zerotree image coding[END_REF] ; some concentrate on the bitrate only for lossless coding [START_REF] Wei | Lossless image and video coding based on h.264/avc intra predictions with simplified interpolations[END_REF], and also one general coder performing lossless and lossy coding is desirable [START_REF] Pearlman | Efficient, low-complexity image coding with a set-partitioning embedded block coder[END_REF]. Most contributions are published in literature, but a few of them provide reference programmes. In this section we present two efficient image coding methods which have been tested by researchers and practitioners.

CALIC

The name "CALIC" stands for Context-based, Adaptive, Lossless Image Compression CALIC operates in two modes : Binary mode and Continuous-tone mode. This optional scheme allows CALIC to distinguish between binary and continuous-tone types of images on a local, rather than a global, basis. This distinction between the two modes is important due to the vastly different compression methodologies employed within each mode. In the continuoustone mode, CALIC uses predictive coding, whereas the binary mode codes pixels directly. The selection of the mode depends on whether or not the local neighborhood of the current pixel has more than two distinct pixel values. The two-mode design contributes to the universality and robustness of CALIC over a wide range of images.

In the continuous-tone mode, the procedure of the coding has four major parts : prediction, context selection and quantization, context-based bias cancellation of prediction errors, and conditional entropy coding of prediction errors. The input pixel y is predicted by a gradient adjusted description (GAP). The predict value y p is further adjusted via bias cancellation procedure that involves an error feedback loop of one-step delay. The feedback value is the sample mean of prediction errors ē which are conditioned on the current context. As a result, an adaptive, context-based, nonlinear predictor is achieved y ap = y p + ē. These operations are completed in "bias cancellation" function as shown in Fig. 1.12. The bias corrected prediction error is finally entropy coded based on few estimated conditional probabilities in different conditioning states or coding contexts. The context quantization generates a small number of In the binary mode, the CALIC encoder firstly checks six neighbor pixels around the current one y as shown in Fig. 1.13. If these six pixels have no more than two different values, then binary mode is taken, otherwise the encoder turns to the continuous-tone mode. In the binary mode, the system sets two reference values s 1 and s 2 , and then y is coded as one of three symbols by comparing it to s 1 and s 2 .

T =                  0, i f y = s 1 1, i f y = s 2 2, otherwise
b k =          0, i f y k = s 1 1, i f y k = s 2 , 1 ≤ k ≤ 6 (1.19)
After that, the binary number B is cosed by an adaptive ternary arithmetic coder driven by conditional probabilities [START_REF] Wu | Context-based lossless interband compressionextending calic[END_REF].

SPIHT

The SPIHT (Set Partitioning in Hierarchical trees) method was firstly introduced in [START_REF] Said | A new, fast, and efficient image codec based on set partitioning in hierarchical trees[END_REF].

It was designed for optimal progressive transmission, as well as for compression. One important features of SPIHT is that, at any point during the decoding of an image, the quality of the displayed image is the best that can be achieved for the number of bits input by the decoder up to that moment. Another feature is its embedded coding. If two files are produced by the encoder, a large one with size M and a small one with size m, and then the small one must be k 1 2 3 4 5 6 sign s s s s s s 14 1 1 0 0 0 0 13 a b 1 1 0 0 12 c d e f SPIHT encodes from the largest absolute value to the smallest, from the most significant bit to the least for one value in order to realize the progressive coding starting with the most important information. Considering an array of coefficients {c n , 1 ≤ n ≤ 6} to be coded, the first step is sorting coefficients from large to small, and the sorting information is contained in another data array s, such that |c s(k) | > |c s(k+1) |. Assuming that each coefficient is represented as a 16-bit number with the most significant sign bit (bit 15) and remaining 15 bits (bit 14 to 0) constituting the magnitude, as shown in Table 1.2.

The 6 signs are need to be transmitted, after that, the encoder starts a loop, where in each iteration, a sorting step and a refinement step are performed. In the first iteration, a number len = 2 is transmitted. It means |c s(1) | and |c s(2) | have bit "1" in the bit 14 position. This is the first sorting pass which transmits the information that enables the decoder to construct approximate versions of the 16 coefficients as follows : coefficients c s(1) and c s(2) are constructed as 16-bit numbers s100...0. The left 14 coefficients are constructed as all zeros. The refinement pass in the first iteration is not required.

In the second iteration, the sorting pass transmits the number l = 2. It means |c s(3) | and |c s(4) | have bit "1" in the bit 13 position. In the refinement, the two bits "a" and "b" are transmitted.

The information received so far enables the decoder to improve the 16 approximate coefficients constructed in the previous iteration. (1.20)

Because SPIHT uses the wavelet transform, the coefficients are derived from the transform on pixels.

The method above is simple, since the coefficients had been assumed to be sorted before the chapter 1 loop started. In practice, there may be more than a million coefficients, so sorting all of them is very time-consuming. Instead of sorting the coefficients, SPIHT uses the fact that sorting is done by comparing two elements at a time, and each comparison results in a simple yes/no result. Therefore, if both encoder and decoder use the same sorting algorithm, the encoder can send the decoder the sequence of yes/no results, and the decoder can use those to duplicate the operations of the encoder.

Image compression performance

In this section, we compared the compression efficiencies of different methods. For the lossy coding, the criterion is to compare the quality (PSNR) of decoded images at one specific coding bitrate (bits per pixel). For the lossless, it is to compare the required bitrates after the coding. The images for the comparison are shown in Fig. 1.16. Because CALIC and JPEG-LS have been more specially designed for the lossless coding issue, we consider the comparison only between JPEG, JPEG2000, JPEGXR and SPIHT solutions.

Lossy compression performance

The implementations of coding methods are derived from Independent JPEG Group [Gro] for JPEG codec, Jasper [Ada] for JPEG 2000, JPEG XR reference [ITU] software for JPEG XR and demo program [ASX] for SPIHT.

The parameters of reference softwares are introduced here : SPIHT : the command line is "codetree s.raw o.sp M N n bitrate". s.raw is the source image and o.sp is the compressed file. M and N are the size of the image. n is the number of bytes per pixel. bitrate is the rate (bits per pixel). For the lossy coding, SPIHT uses the wavelet transform and the arithmetic entropy coding. The S+P prediction method and the arithmetic coding are applied in the lossless coding mode. Fig. 1.14 and 1.15 show the lossy coding performances of different methods on gray and color images. For the gray ones, JPEG2000 has the least distortion of the decoded image at a specific bitrate in most cases. SPIHT, which also adopts the wavelet transform, has the close performance to JPEG2000. The following method is JPEGXR, which has similar the quality curve trend. The JPEG curves are lower than others, especially at low bitrates which are less than 0.25 bpp. For the color images, JPEG2000 also achieves the superior quality. JPEGXR follows JPEG2000 closely. Because the available software of SPIHT does not support the coding of the color image, its performance is not included in this group.

Lossless compression performance

JPEG is commonly used in lossy coding. "Lossless JPEG" (LJPEG) is an addition to JPEG standard by the Joint Photographic Experts Group to enable lossless compression in 1993. The implementation of LJPEG is available in [HS], the one of JPEGLS is from [UBC] and CALIC is available in [XW]. Besides, Kim et al. proposed a hierarchical prediction and context adaptive coding for lossless color image compression (LCIC) [START_REF] Kim | Hierarchical prediction and context adaptive coding for lossless color image compression[END_REF]. They offered the reference execution [KC].

Table 1.3 and 1.4 give the lossless coding results. For the gray images, CALIC needs the least bit resource during the coding, the followed one is SPIHT. In JPEG series, JPEGLS performs best, while the results of JPEG2000 are close to the ones of JPEGLS. For the color images, CALIC reference software does not support this mode and its performance is not tested. JPEG2000 gains bits the most for images "bike crop", "woman crop" and "green crop", but costs more than JPEGLS for "TOOLS".

From the lossy and lossless tests, it can be found that, SPIHT performs very well for both

LAR

Quadtree Partitioning

Quadtree is used for a partition on an image so as to achieve a variable-size block representation of the image. It is an effective way to sign and identify the local activity of pixels.

It is often applied to the image coding with a specific compression method [TN96][CCX00].

In the LAR codec, the criterion for the partition is based on the edge detection. This detection checks the difference between maximum and minimum luminance values in a given block, and compares the absolute value D of the difference with a threshold T hr. If D is greater than T hr, the current block should be separated to 4 equal sized sub-blocks.

Let I(x, y) represent a pixel in an image with size N x × N y , I(b N (i, j)) be the block b N (i, j)

of size N × N in I such as b N (i, j) = {(x, y) ∈ N x × N y , where N × i ≤ x < N × (i + 1), N × j ≤ y < N × ( j + 1)} (2.1)
Let a Quadtree partition be P [N max ...N min ] , where N max represents the largest allowable block size Interleaved Pyramid Construction 47 and N min is the smallest one. Let the I(b N (i, j)) min the minimum and I(b N (i, j)) max the allowed maximum value in the block I(b N (i, j)). For the pixel I(x, y), the size of the block in which it is is shown as

S ize (x, y) =                max(N), ∃ N ∈ [N min ...N max ], i f I b N x N , y N max -I b N x N , y N min ≤ T hr N min , otherwise (2.2)
After the Quadtree partitioning, the image is segmented to a map which is composed of blocks with different sizes. The smallest block with N min are mainly located in areas of highly local activity of pixels, such as contours and highly textured areas.

For color images, the RGB color space is firstly conversed to YCbCr space, and then the Quadtree partition is taken in each color component. The smallest size among the results of the components is chosen as the size of the block.

S ize(x, y) = min S ize Y (x, y), S ize Cr (x, y), S ize Cb (x, y)

(2.3)
For the gray images, the luminence Y is the only component used for the partition. The threshold T hr is pre-defined before coding in the LAR coder.

Interleaved Pyramid Construction

The pyramid structure (2.2) is designed for the multiresolution function. For the implementation in a reversible and fast way, the main process adopts the S transform [START_REF] Said | Reversible image compression via multiresolution representation and predictive coding[END_REF] which can be completed by the integer operation. If (a 0 , a 1 ) is a couple of value, the mean value z 0 and the gradient value z 1 are given by

z 0 = a 0 + a 1 2 , z 1 = a 0 -a 1 .
(2.4)

where . means rounding downwards.

During the pyramid building process, the S transform is applied on 2 vectors in a 2 × 2 block. Each vector is formed by 2 diagonally adjacent pixels, as depicted in Fig. 2.3. z 0,1 is the mean value and z 1,1 is the gradient value of the S transform in the 1st diagonal ; while z 0,2 is the mean value and z 1,2 is the gradient value of the S transform in the 2nd diagonal. Some notations are defined here :

a 0,1 a 1,1 a 0,2 a 1,2 z 0,1 z 1,1 z 0,2 z 1,2

Pixels

Transformed coefficients S transform on 1st diagonal S transform on 2nd diagonal Let 1M be the image composed of the z 0,1 such as 1M(i, j) = z(2i, 2 j), 2G be the image composed of the z 1,1 such as 2G(i, j) = z(2i + 1, 2 j + 1), 3M be the image composed of the z 0,2 such as 3M(i, j) = z(2i + 1, 2 j), 3G be the image composed of the z 1,2 such as 3G(i, j) = z(2i, 2 j + 1).

Let Y be the original image with size N x × N y . The multiresolution representation of an image is described by the set {I l } l max l=0 , where l max is the top of the pyramid and l = 0 is the full resolution image. The pixels of upper level l + 1 are derived from the 1M in the current level l.

It can be expressed in the following equation.

           I 0 (i, j) = Y(i, j), l = 0; I l (i, j) = I l-1 (2i, 2 j) + I l-1 (2i + 1, 2 j + 1) 2 , l > 0, (2.5) with 0 ≤ i ≤ N l x , 0 ≤ j ≤ N l y ,

Pyramid Decomposition and Prediction Model

After building the pyramid resolution structure, the coding starts from the top level (lowest resolution) to the bottom level (full resolution) level by level. The decomposition has two decent processes. One is the LAR block process, and is based on the Quadtree Partition. The pixels of upper level give the mean value of the first diagonal of the current level. If the corresponding 2 × 2 block has been seen as a whole (the difference D is less than the threshold T hr in the Quadtree Partition), the value of upper pixel I l+1 (i, j) is copied directly to the four pixels I l (i, j), I l (i + 1, j + 1), I l (i + 1, j) and I l (i, j + 1) of the block in the current level. Otherwise, the pixels of the block are predicted and the prediction errors are coded. This process can be depicted in Fig. 2.5. The other process is for the texture. In the LAR process, if the non-prediction situation is proposed, the texture process still takes a prediction to this block and encodes errors in order to get a more precise representation of the block. This process is not requisite for coding but offers a quality progressive function to each resolution.

In the following part, the prediction ways used in the decomposition are introduced. Before that, some parameters are renoted here. Fig. 2.6 shows the positions of pixels in a 2 × 2 block.

chapter 2

On the level l, the S transform is applied on the first diagonal so that

1M l (i, j) = I l (2i, 2 j) + I l (2i + 1, 2 j + 1) 2 , 2G l (i, j) = I l (2i, 2 j) -I l (2i + 1, 2 j + 1).
(2.6)

The transform on the second diagnal is

3M l (i, j) = I l (2i + 1, 2 j) + I l (2i, 2 j + 1) 2 , 3G l (i, j) = I l (2i + 1, 2 j) -I l (2i, 2 j + 1).
(2.7)

It can be noticed that the pixel in the upper level equals to 1M l (i, j)

1M l (i, j) = I l+1 (i, j).
(2.8)

LAR block process

At the top level of the pyramid, the classical mean predictor [START_REF] Weinberger | The LOCO-I lossless image compression algorithm : principles and standardization into JPEG-LS[END_REF] is used to encode the pixels. The prediction errors are needed to be sent to the decoder in a lossy or lossless context.

For the lower levels, the pixels are coded by the linear prediction models. The level l + 1 provides the mean value of the two pixels of the first diagonal in the level l. The difference of them is estimated by

2 Gl (i, j) =2.1 0.9I l+1 (i, j) + 1 6 I l (2i + 1, 2 j -1) + I l (2i -1, 2 j -1) + I l (2i -1, 2 j + 1) -0.05 I l (2i, 2 j -2) + I l (2i -2, 2 j) -0.15 I l+1 (i, j + 1) + I l+1 (i + 1, j) -I l+1 (i, j) (2.9)
For the second diagonal, the estimation of 3M l uses inter-and intra-level prediction from reconstructed values, so that

3 Ml (i, j) = 1 4 β 0 0 I l (2i -1, 2 j + 1) + I l (2i, 2 j + 2) -I l (2i + 2, 2 j) + I l (2i + 1, 2 j -1) + β 1 0 1 M l (i, j) , (2.10)
where (β 0 0 , β 1 0 ) = (0.25, 0.75), and 1 Ml (i, j) is the reconstructed value of 1M l (i, j). For the Quantization 51 3G l (i, j), its estimation is

3 Gl (i, j) =β 0 1 I l (2i -1, 2 j + 1) + I l (2i, 2 j + 2) -I l (2i + 1, 2 j -1) -I l (2i + 2, 2 j) -β 0 1 I l (2i -1, 2 j) + I l (2i -1, 2 j + 2) -I l (2i, 2 j -1) -Ĩl (2i, 2 j + 1) , (2.11)
where (β 0 1 , β 1 1 ) = (3/8, 1/8). Ĩl (2i, 2 j + 1) can be obtained by the Wu predictor [START_REF] Wu | Lossless compression of continuous-tone images via context selection, quantization, and modeling[END_REF] for the third pass to the pixel I l (2i, 2 j + 1).

Texture block process

The decomposition of the texture block (second pyramidal decomposition process) is still processed in two diagonals. In the texture block, the difference of pixels is not so large as be in the LAR block, the coefficients used for the estimation are more balanced.

Let m e (u 1 , u 2 , ..., u n ) be the median value of n values (u 1 , u 2 , ..., u n ). The estimation of

2G(i, j) in a texture block is 2 Gt (i, j) = 1 4 m e I l (2i -2, 2 j), I l (2i, 2 j -2), I l (2i -1, 2 j -1)
+ m e I l+1 (i + 1, j), I l+1 (i, j + 1), I l+1 (i + 1, j + 1) .

(2.12)

For the second diagnal, the 3M t is estimated by the equation 2.10, but with (β 0 0 , β 1 0 ) = (0.37, 0.63). 3G t is predicted by 2.11, with (β 0 1 , β 1 1 ) = (1/4, 0).

Quantization

In the lossy coding mode, the prediction errors are scalar quantized. The index data obtained after the quantizition is sent to the entropy coding part. The prediction error is uniformly quantized. Let the error be e p , a quantization factor is Q, the index data i is expressed by

i =              e p + Q 2 Q , e p ≥ 0 e p - Q 2 Q , e p < 0 , (2.13)
where . stands for rounding downward.

Since the image is processed in a pyramidal multi-level structure, each level produces prediction errors to be quantized. The quantization factor Q l of level l is determined by a global

Q l = quqp • f l , 0 ≤ l ≤ N (2.14)
{ f l , 0 ≤ l ≤ N} represnets a fixed coefficient set which adjust the quantization distortion in each level. It allocates integer values between 1 and quqp to Q l .

Entropy coding

In LAR coder, the entropy coding part is implemented by a symbol-oriented QM coding

[Pas11] [XHGH07]
. The JPEG2000 entropy coder uses a bit-plane oriented coding [START_REF] Saidani | Implementation of jpeg 2000 mq-coder[END_REF].

The bit plane oriented coding firstly encodes all most significant bits from all values, then the next less significant bit plane until it reaches the least significant bits. As JPEG2000 uses the wavelet transform, the interesting information to reconstruct the pixels can be given from the few first bits already decoded. Such a bit plane coding can be used as part of a rate control.

LAR codec is a prediction method. It requires fully reconstructed prediction error values.

A bit plane oriented coding needs the whole input stream to be available to start encoding. In the case of the LAR codec, prediction errors are computed one after another following a raster scan. This way, the bit plane oriented coder has to wait that all predictions have been realized before starting and therefore does not allow parallelism between prediction and entropy coding.

As a result, LAR coder uses a symbol-oriented QM coding. This method sees all bits of an input value as a symbol and codes it. After that, it starts the encoding of the symbol of the next value.

The symbol-oriented one has three different passes : magnitude, sign and refinement coding, as shown in Fig. 2.7.

The magnitude coding has two functions in the coding. The first one is coding the number of bits needed to represent the symbol to be encoded. The second one is to adjust the complexity of the overall entropy coding by minimizing the number of coding passes needed. The magnitude coding firstly computes the minimal number of bits Ā to represent the symbol A. Then, the bits Ā are coded through unary coding with a dictionnary containing the length of the codeword.

Finally, each bit from the unary codeword is encoded with the QM Coder.

The sign is directly coded after the magnitude coding and the algorithm is not different from the bit plane oriented QM Coding. At last, the remaining bits are encoded in the refinement coding. The number of the refinement bits has been determined by the magnitude coding pass.

Conclusion

The LAR framework tends to associate the compression efficiency and the content-based representation. It relies on an S transform based multiresolution representation. The coding scheme involves the prediction, quantization and entropy coding of the quantized prediction errors. The implementation of the LAR codec can complete both lossy and lossless coding under the same coding structure.

Although the LAR codec has the complete and independent coding structure, it is not optimized for the rate-distortion. For the implementation, there are key parameters, such as the Thr of the quadtree partition and the quqp of the quantization, play important roles for the compression efficiency. The optimal collocations of parameters are not determined during the coding. As a result, the coding efficiency is much limited. Since the original version of the LAR codec aims at coding functionalities, the computation comlexity causes a more time consumption than JPEG 2000. These problems make the LAR be not standardized successfully in the JPEG-AIC response.

The main drawbacks of LAR codec are about its limited coding efficiency and the computation complexity. In my work, I firstly analyzed the main coding steps of LAR, next tried to build models to describe the relation of key parameters and keeped the LAR codec work under a configuration which is close to the optimal choice. Further, the subjective measurement is taken into consideration and perceptual quality is improved at high bitrates.

Aiming at a low complexity efficient image codec, a new coding scheme is proposed and achieved in lossless mode under the LAR framework. In this context, coding steps are changed for better coding performance, and a classification module is introduced to decrease the entropy chapter 2

of the prediction errors. The QM coding is also replaced by the classic Huffman coding for less computation cost. This new coding scheme achieves a better lossless image compression efficiency which is equivalent to the one of JPEG2000, while has much lower coding latency.

Chapter 3

Rate-distortion-optimization (RDO) model for LAR codec

The rate-distortion-optimization (RDO) is an important issue for the image coding techniques. Studies have been conducted on state of the art codecs to understand their behaviors in terms of quality and/or rate. Such studies are often a step of a rate distortion optimization design. For example, the impacts of quantization on the DCT coefficients for the JPEG codec [START_REF] Yovanof | Statistical analysis of the dct coefficients and their quantization error[END_REF], and an improved algorithm for RDO in JPEG2000 [XGC + 06].

Given a particular compression framework, there are often two ways to study the possible optimization methods. One is to focus on the statistic properties of inside functions. It tries to monitor each coding unit and adjust parameters during the coding so as to achieve a desirable performance at a specific bitrate, such as the PCRD used in JPEG2000 1.2.3. This process is effective but involves large of computation and possible required memory. Another way is looking for the best operating points for that specific system. For example, consider a scalar quantizer followed by an entropy coder. If all the quantization choices have been considered, an operational rate-distortion curve can be defined and plotted by pairs of each bitrate and the distortion achieved by designing the best codec for this bitrate. This curve can distinguish between the best achievable operating points and those which are sub-optimal or unachievable. A particular case is shown in Fig. To perform rate distortion optimization on LAR codec, the second scheme is adopted to design a low computation complexity RDO coding plan. This study is presented in six sections.

The first one is to present the effects of key parameters for the rate-distortion performance. The second section analyzes the relationship between the optimal coding efficiency and parameters, and builds description models. The third section shows and discusses the experiments of this model. The fourth part indicates a linear quality control (QC) model and checks its performance. The fifth section discusses the application of the RDO model aiming at improving the subjective quality of the decoded image. Finally, the coding performance of optimized LAR codec is compared with other image coding methods.

Parameter effects on distortion

In lossy coding of LAR coder, the distortion is caused by two functions : Quadtree partitio- Although the two kinds of distortion have different visible effects, we need an uniform criteria to evaluate them. The objective metric Mean Square Error (MSE) is firstly considered.

Let x i be the value of the pixel, xi be the restored one, N represents the number of pixels, the MSE of a decoded image is expressed by

MSE = 1 N N i=1 ( xi -x i ) 2 . ( 3.1)
A large MSE stands for a high distortion. Further, the Peak Signal-to-Noise Ratio (PSNR) is

PSNR = 10 • log 10 MAX 2 MSE , (3.2)
where MAX is the maximum pixel value of the image. It is noticed that a large PSNR indicates a high quality of the decoded image. For the range of 8 bits/pixel, MAX is 255.

The lossless mode of LAR is achieved by setting T hr = 0 and quqp = 1, which represent full resolution reconstruction and no quantization lost, respectively. Increasing quqp while keeping T hr as a constant, the augment of MSE reflects the distortion resulting from the quantization. Fig. 3.3. gives an example of the distortion curves. Each point represents a distortion caused by the a combination of T hr and quqp. In each curve, the points have the same T hr.

It is noticed that the best operating points, which have the lowest MSE at particular bitrates, are not located in only one curve, as the red points in the figure . In order to achieve optimal rate-distortion performance, it is interesting to extract the optimal points out and analyze the relationship existing in their corresponding optimal pairs of T hr and quqp.

Optimal Thr-quqp model

H G = - g p(g) • log 2 p(g). (3.4)
Table 3.1 gives the contrast entropies of the four images. The values correspond to the slopes of the belts approximately. "green crop" has the largest one, the followed images are "bike crop", "p26 crop" and "sky".

The entropy H G does not concern the amplitudes of the gradients. However, in some parts, such as the interlaced texture and the contour of the object, the large difference between adjacent pixels possibly causes great prediction errors and costs more bitrate. For the image "sky", most parts are homogeneous and has less changes of pixels. Increasing the T hr does not affect the Quadtree partition a lot. The distortion is more related to the quantization. In contrast, the Quadtree partition has more influence to images with much texture. Fig. 3.6 gives the partition grids at two T hr. Most blocks in the grid of "sky" have been 8 × 8. Their sizes keep unchange.

The smallest blocks 2, which exit a lot in "bike crop" and "green crop", combine together during the increasing of T hr. This combination raises the clarity distortion which is not controlled by the quantization. Therefore, the amplitude of the gradient is another issue considered for the model. The gradient represents the values of the gradient g. The r(i) is defined as

r(i) = i g=0 p(g).
(3.5)

If an image has large portions of the same color and moderate transitions, most gradients have small values and the r(i) curve rises more quickly as the "sky" one. The cumulation curve becomes close to 1 even the gradient is only 10. after that, since r(i) is no more than 1, the increasing of the curve becomes very small. For the "green" one, the curve rises much slower and r(i) reaches 0.9 at Gradient = 50. The rate of rise is obvious and comparable before reaching the flat part where r(i) is close to 1. There are two choices to reflect the rising speed. One is to fix a threshold, such as r(i) = 0.9. Each image has its own value of i when its r(i) curve reaches 0.9. The images with much texture information have a wide range of the gradient. The curve increases slowly and get a large i, as the one of "green crop" in Fig. 3.7. However, the threshold are not constant exactly. The r(i -1) may be lower than 0.9 but r(i) rises to 0.92 or more, especially for the simply structured image with the sharp rising of r(i). It is not fair for the comparison. The other solution used here is choosing a range of the gradient [i d , i u ] and calculate the difference of r(i). A large difference indicates that lots of gradients fall in this range. In Fig. 3.7, the curves become more steady after i = 45. Before that, the curves rise in different speeds and locate separately. The difference between r(0) and r(45) would be a choice to represent their speeds. However, r(0) is quite small for the textured images. The difference between r(0) and r(45) mainly depends on the values of r(45) which do not differ much between images. In order to distinguish the difference between [i d , i u ] obviously, the lower bound i d is increased to 7 and the difference between r(45) and r( 7) is used to evaluate the slope of a r-curve. From the Fig. 3.7, the "green crop" has the largest difference while the "sky" one is the least.

∆ = r(45) -r(7) (3.6)
According to the study above, the RDO linear model is firstly formed as

T hr = H G α (quqp + ∆ • β). (3.7)
H G contributes to the slope. For images with less textures, ∆ has a small value in order to slow the augment of T hr. α and β are coefficients trying to map the models according with the distribution of the optimal belt. These coefficients are constant and achieved by the curve fitting.

Optimal Thr-quqp model

63

The objective of curve fitting is to theoretically describe experimental data with a model (function or equation) and to find the parameters associated with this model. In this section, the curve fitting is applied to find the values of the coefficients, α and β, which make the RDO model match the data of the optimal quqp-T hr belt as closely as possible. The best values of the coefficients are the ones that minimize the value of the summed square of residuals, which is given by

SR = n i=1 (y i -ŷi ) 2 (3.8)
where y is a fitted value for a given point, y i is the measured data value for the point, n is the number of data points included in the fit and SR is the sum of square of residuals.

T hr = H G α (1 + ∆ • β 53 ) quqp. (3.9)
Since the belt has the width, a distance, 10, in the T hr direction is used to shift the linear model so as to cover the possible area of the belt. The proposed RDO model is expressed as

                                              T hr 2,1 = H G α (quqp + ∆ • β) T hr 2,2 = H G α (quqp + ∆ • β) + 10 , i f quqp ≥ 53              T hr 1,1 = H G α (1 + ∆ • β 53 ) quqp T hr 1,2 = H G α (1 + ∆ • β 53 ) quqp + 10 , i f 0 < quqp < 53 (3.10)
where T hr i,1 is the model 1 for the region i (i = 1, 2) and T hr i,2 is the model 2. The two models try to simulate the boundaries of the belt. During the practical coding, the average value of model 1 and 2 is chosen as T hr.

T hr = (T hr i,1 + T hr i,2 )/2 (3.11) and T hr i,2 can be calculated out by (3.10). In the Fig. 3.8 (a), the area limited by the T hr i,1 and T hr i,2 lines covers most parts of the optimal belt. When quqp is greater than 125, the estimating area is higher than the optimal belt, leading to a little deviation. The average of T hr i,1 and T hr i,2 is chosen as the parameter T hr for coding. The rate-distortion results with the chosen (quqp, T hr) are indicated in Fig. 3.8 (b). The proposed points locate closely to the optimal positions. As the "bike crop" is included in the training set, images out of the training set should be tested to confirm the effectiveness of the model. Therefore, more examples and discussions are provided in the next section. The "p26 crop" is from the training set, while "flower", "leaves", "louvre", "TOOLS" and "rokounji" are out of the training set. Since the RDO model is derived from the distortion curves, the performance of the RDO model is firstly presented in MSE, and then in PSNR which is widely applied to evaluate the coding efficiency. The optimal curve represents the best results can be achieved by the LAR lossy coding. It is drawn by a totally searching from all the possible R-D points. The points of the "proposed method" are the coding results of the RDO model. close to the optimal curve in both MSE and PSNR. The maximum difference in PSNR is 0.06 dB at 0.26 bpp. Fig. 3.11 and 3.12 show the efficiency for the image "flower" (H G = 2.332). The coding for "flower" has a less distortion, but the RDO model shows a deviation to the optimal curve. In Fig. 3.11, the deviation is obvious at low bitrates. For example, the MSE of the optimal curve is 12.1 approximately at 0.0927 bpp, while the modeled one is 14.2 at the same bitrate. This difference causes a gap of 0.7 dB in PSNR, where the optimal one is about 37.3 dB and the modeled is 36.6 dB. Fig. 3.13 and 3.14 give the results of "leaves" (H G = 5.017). As shown for the image "p26 crop", most of the modeled points are in the optimal curve and others are also very close to it. When the bitrate is lower than 0.5 bpp, the modeled points are exactly in the optimal curve.

Experiment of the RDO model

The maximum difference in MSE occurs at 0.735 bpp where the modeled one is 20.8 and the optimal one is about 20. The largest difference in PSNR is 0.18 dB at 2.39 bpp, where the modeled point is 39.57 dB and the optimal one is 39.75 dB.

According to the experimental results, the RDO model can follow the optimal curve and finds the optimally efficient coding points in most cases, while the other coding results of the RDO model are also close to the optimal ones. For different images, the coding results are better for images with higher H G than the ones with lower H G . Because a textured image brings difficulties for the prediction and often causes a high distortion in the decoded image at a low bitrate. In this case, a small deviation from the optimal curve does not generate a large relative error in MSE. In contrast, for the images with less texture, a small difference of MSE leads to a obvious deviation from the optimal curve, as shown by Fig. 3.11 and 3.12 for the image "flower". Another factor is that, for images with less texture information, some optimally coding points require T hr = 0, even their quqp have large values. This feature is beyond the simulation of the RDO model. Besides, QC is also an important function. For the data storage and quality preferred applications, such as the archive recording, medical imaging and High Definition Television (HDTV), the quality of the decoded image is the most concerning issue to the users. Recent works of QC mostly focus on the perceptual quality metric. In [START_REF] Liu | Jpeg2000 encoding with perceptual distortion control[END_REF], a vision model was proposed to incorporate various masking effects of human visual perception and a perceptual distortion metric. This model was applied into JPEG2000 to control the embedded bit-plane coding in order to meet the desired target perceptual quality. Similarly, Gao and Yuan proposed a quality metric called weighted normalized mean square error of wavelet subbands (WNMSE) [START_REF] Gao | Quality constrained compression using DWT-Based image quality metric[END_REF]. Besides, they also introduced a compression algorithm, quality constrained scalar quantization (QCSQ), to compress the image to a desired visual quality measured by WNMSE. Because the perceptual evaluation of the image is still a developing issue. The novel metrics are proved by examples in the papers, but it is hard to say that they have answered all the questions for measuring the human visual system (HVS) and can work well for other images. Besides, considering only the HVS is not affair for the objectively detecting application. For the medical imaging and the areal relief mapping, the visual system based metrics may be insensitive to some distortion, which contains the valuable information, and give a "lossless" score. In this case, the objective quality metrics, MSE and PSNR, are better choices to find any distortion of the decoded image.

Rate

By applying the Quadtree partition, the quantization of the LAR codec focuses on the small blocks, which often appear in the texture parts and edges, where HVS are not sensitive. Thus, the LAR codec also puts the effects of the HVS into consideration. For a wide application in both objectively and visually oriented metrics, the QC method introduced for LAR is still aiming at the targeted MSE and PSNR.

MSE Determination Model

Depending on the RDO model, the quqp becomes the decisive parameter. Besides, an approximately linear relationship between the distortion in MSE and quqp is observed. Fig. 3.21

gives four examples. Similarly, this section also tries to construct linear models to describe the relationship. With the RDO model, quqp and T hr have been be linked by linear equations. Thus, T hr should also have a linear relationship with MSE. For images with much texture parts, they often have higher MSE than the ones with less texture parts at a particular quqp. This feature indicates that the H G can also reflect the slope of the linear relationship in Fig.

The quality model is firstly defined as

MSE = α • H 2 G • quqp + β • T hr . ( 3
               MSE est = 0.058H 2 G -0.9 H G α quqp -0.9 H G α ∆ -4.5 , quqp ≥ 53 MSE est = 0.058H 2 G - 0.9 α H G 1 - ∆ 53 β quqp -4.5 , 0 < quqp < 53

MSE constraint method

With equation (3.13), we can estimate the Quality (MSE) from a given quqp.

                   quqp = MSE set + 0.9∆ H G α + 4.5 0.058H 2 G -0.9 H G α , MSE set ≥ MSE boundary quqp = MSE set + 4.5 0.058H 2 G -0.9 α H G 1 -∆ 53 β , 0 < MSE set < MSE boundary (3.14)
With quqp and T hr, the LAR codec have then enough parameters to complete the coding. The steps of the MSE setting method are shown below.

Step 1. Analyze the image to be coded, calculate the probilities of the gradients of blocks in order to get the entropy H G and ∆ ;

Step 2. Compute the MSE boundary according to the equation (3.13) with quqp = 53 ;

Step 3. Compare the MSE set with MSE boundary , choose which formulation in (3.14) should be used and calculate the suitable quqp exp ;

Step 4. Substitute quqp exp into the equation (3.10) to get T hr 1 and T hr 2 , the average value of them is chosen as the suitable T hr exp for Quadtree partition ;

Step 5. Start the coding with quqp exp and T hr exp .

Experiments of the MSE setting method

In this part, the images "p06 crop", "flower", "leaves" and "louvre" which are out of the training set are put into the tests of the MSE setting method. This MSE setting method provides a quality constraint scheme for the LAR codec. Although at high bitrates, the ratio of the error and the MSE set is not stable and possible larger than 10%, the absolute value of the error is not large and the MSE obtained is not far from the set one. The ratio reduces at low bitrates which have more MSE and keeps below 10%. As this method depends on the proposed RDO model, it also assures an optimal or sub-optimal coding efficiency.

Locally perceptual quality enhancement

The simplest and most widely used quality metric is MSE, along with PSNR. for a wide range of the luminance values. That is to say, the HVS is sensitive to the relative luminance change, and not the absolute luminance change. For example, in Fig. 3.32b, the stripe in the white and gray background reflects a strong relative differences in brightness and the loss of the stripe results in a noticeable distortion. While the noise in the bright background is less perceptible in Fig. 3.32a. Thus, it is not proper take a high threshold of the Quadtree Partition in the brightly monotonous background. Another fact of the HVS is that the human eyes are less sensitive to noise in strong texture areas than the less textured areas [START_REF] Zhiweil | Steganography based on wavelet transform and modulus function[END_REF]. The classic LAR codec has concentrated the quantization on the texture parts. For the Quadtree partition, a suitable improvement for the perceptual quality would be transferring the blurring distortion from the flat part to the texture part. Noticing that the proposed RDO model is based on the detection of the texture, one solution is to separate the source image into different parts and allocate each part a local threshold T hr for the Quadtree Partitioning. The RDO model is applied to each part to get the local T hr, rather than the whole image as introduced in previous sections. This is an adaptive T hr allocation scheme. In practice, the image is firstly separated into blocks with size before the coding and used for all the 64 × 64 blocks. A block with a greater luminance represents a higher T hr and vice versa. In Fig. 3.33b, the T hr tend to be large on the rotation shaft, leaves and dishes, where have much texture information. In contrast, the T hr equals to 34 when using the RDO model directly to the image. Fig. 3.33c and 3.33d show a comparison of the grids of the Quadtree partition. A small block of the grid indicates that a change of pixels is detected, while a larger block will treat the pixels in it as a whole and provide the same value to pixels in the block in the decoded image. Therefore, a large block in the grid probably causes the blurring distortion. Fig. 3.33c gives the Quadtree grid drawing with the adaptive T hr scheme.

It is noticed that the strip of the ground is well detected while the strip is lost in Fig. 3.33d. The similar T hr allocation also occurs in the image "woman crop" in Fig. 3.34. Large T hr values appear in the hair, and on the sweater. For the face and finger, most 64 × 64 blocks have the small T hr. From Fig. 3.34c and 3.34d, we can see that some details of the finger and face are kept. This feature is helpful to weaken the visible blurring distortion.

The Structure Similarity (SSIM) quality assessment

In order to evaluate the efficiency of the adaptive T hr allocation scheme for improving the perceptual quality of the decoded image, we need a quality metric to measure the image. As other. µ is the mean intensity of the signal, such as

SSIM(x, y)

= (2µ x µ y + C 1 ) (2σ xy + C 2 ) (µ 2 x + µ 2 y + C 1 ) (σ 2 x + σ 2 y + C 2 ) . ( 3
µ x = 1 N N i=1 x i . (3.16)
σ is the standard deviation (the square root of variance) as an estimate of the signal contrast.

Its an unbiased estimate is given by

σ x =         1 N -1 N i=1 (x i -µ x ) 2         1 2 (3.17) σ xy is the covariance of x and y. Coefficients C 1 = K 1 L, C 2 = K 2 L, where K 1 << 1 and
µ x = N i=1 w i x i σ x =         N i=1 w i (x i -µ x ) 2         1 2 σ xy = N i=1 w i (x i -µ x )(y i -µ y ). (3.18)
In each window, the SSIM measure uses the default coefficient setting : K 1 = 0.01 ; K 2 = 0.03.

According to the local quality measurement, a single overall quality measure of the entire image, the mean SSIM (MSSIM) index, is given to evaluate the overall image quality

MSSIM(X, Y) = 1 M M j=1 SSIM(x j , y j ) (3.19)
where X and Y are the reference and the distorted images. x j and y j are the pixels in the jth Their subjective quality is measured by MSSIM. We can find that the decoded images with the adaptive scheme have the visible improvement for the texture parts on the bright background.

For example, the stripe in "bike crop", the details on the face and the hand in "woman crop" are reserved better than the one without the scheme. The improved images also achieve better scores in MSSIM. In order to exam the effectiveness of the adaptive scheme, more images are tested and the results of the bpp-MSSIM are shown in the next part.

Experiments of the adaptive Thr allocation scheme

Five images are shown in Fig. 3.38. They are used to test the performance of the adaptive T hr scheme. Each image is coded with or without the allocation scheme, and the decoded images are compared by the MSSIM scores at a range of the bitstream. The results are drawn from the Fig. 3.39 to 3.43.

From the test results, it can be noticed that the adaptive T hr allocation scheme improves the subjective quality of the decoded image measured by MSSIM at a certain bitrate. For the images "bike crop" and "woman crop", the amelioration is limited and the improved results are around 1 dB better than the ones without the adaptive scheme. The enhancement of the perceptual quality is large for the image "p06" and has the improvement by 4 to 6 dB. The adaptive one reproduces the structure of the car and the reflection on the door more clearly as shown in Fig. 3.44 . For "louvre" and "leaves", the recovered images have about 2 dB in advantage with the adaptive T hr scheme.

The adaptive T hr scheme can ameliorate the perceptual quality of the coding image. Its impact on the objective quality also needs to be tested. The following experiments are performed by PSNR. The performance of the standards, "JPEG", "JPEGXR" and "JPEG2000" are also compared with the ones of the LAR codec. The results are shown from the Fig. 3.45 to 3.48 .

According to these comparisons, JPEG2000 has the best objective quality of the lossy coding. JPEGXR follows the JPEG2000 closely and is lower than JPEG2000 by 0.5 to 1 dB. For the LAR codec, the adaptive T hr allocation scheme does not differ the quality a lot measured by PSNR. Thus, the adaptive T hr scheme can improve the perceptual quality of the decoded image while keep the objective quality. With the RDO model, the LAR codec achieves a better PSNR score than the JPEGXR for "p06", but for other images, the performance is lower than JPEG2000 by 1 dB and JPEGXR by 0.5 dB respectively. JPEG shows the lowest coding quality in PSNR. It is designed much earlier than JPEG2000 and has been well developed for the The proposed RDO model can help the LAR codec achieve the optimal or sub-optimal coding performance, but the results are lower than those of JPEG2000. Thus, it is necessary to change the inside coding steps of the LAR codec to improve the coding efficiency.

Conclusion

In this chapter, a rate distortion optimization (RDO) model is designed for the LAR codec.

Two important coding processes, the Quadtree Partition and the quantization for the prediction error, are considered to analyze their influences on the coding efficiency of the LAR codec.

The optimal coding performance is firstly selected out to extract the corresponding pairs of the parameters which are seen as the target parameters. Next, by analyzing the texture complexity of the image, a RDO model is constructed to calculate the target parameters. Based on this model, the LAR codec can code the image with a lowest objective distortion which the LAR codec is able to achieve. Besides, a distortion constraint method for the LAR codec is also proposed. It depends on a linear relationship between the quantization and the distortion.

In order to improve the perceptual quality of the decoded image, the RDO model is applied in a locally adaptive way. The experimental results show that this adaptive scheme bring a better subjective quality while the objective quality measured by PSNR is close to the result obtained without the scheme. The comparison with the JPEG series shows that the LAR codec has a lower coding performance than JPEG2000 and JPEGXR. Thus, the coding steps of the LAR codec should be modified to construct a new image coding method in order to achieve a higher compression efficiency which is equivalent or better than the one of JPEG2000.

Chapter 4

A low complexity lossless image codec :

LAR-LLC

Due to the fast development of multimedia industry, the increasing demand of the media data encourages the studies on promising technologies in order to efficiently make use of the limited storage and communication capacity. Image compression plays an important role in this field. In this chapter, the statement focuses on the scalable lossless image compression with low complexity. Despite the wide use of lossy coding, for some applications, such as technical drawing, art archiving, medical imaging and film post-production, the lossless compression is more suitable for these high fidelity scenes. Therefore, the image coding standards, such as the JPEG, JPEGXR and JPEG2000 also provide the lossless mode.

The compression ratio is the main indicator for evaluating the image compression method, since the compression essentially aims at reducing the image storage space and the transmission capacity. For practical applications, the complexity is also a considerable performance factor. In multimedia entertainment, such as Internet and High-definition television (HDTV), high resolution images are generally desired by users. However, large size images need much computations at the end which aggravate the coding latency. As a result, an efficient scalable coding method with less computation is required to reduce the time-delay and adjust the image resolution according to the channel capacity and user requirements. When implementing compression techniques used in embedded systems such as digital cameras, and smart phones, the low complexity coding algorithm is also preferable in order to reduce the electrical power consumption and the processing time. In this context, reduced coding solutions are required for both encoding and decoding parts. The compression methods often rely on two main stages : In this chapter, a lossless image coding method is introduced. It has the compression efficiency equivalent to JPEG2000, but lower computational complexity. This method is based on the LAR (Locally Adaptive Resolution) framework. The extensions to the LAR codec are also presented in [START_REF] Déforges | The RWHT+P for an improved lossless multiresolution coding[END_REF] and [START_REF] Babel | Interleaved s+p pyramidal decomposition with refined prediction model[END_REF] to implement the functions of the multi-resolution and the lossless coding. The two articles introduce different pyramidal representations of the image with the dyadic decomposition scheme for the multi-resolution. In [START_REF] Babel | Interleaved s+p pyramidal decomposition with refined prediction model[END_REF], the proposed transform/prediction scheme called "Interleaved S+P" is directly derived from the "S transform and Prediction (S+P) method" introduced in [SP93]. This scheme has been adopted as the implementation of the LAR codec introduced in the chapter 2. Another dyadic decomposition which is proposed in [START_REF] Déforges | The RWHT+P for an improved lossless multiresolution coding[END_REF] is based on the 2 × 2 block Walsh-Hadamard, with a specific reversible mode (R-WHT) in the lossless context. This transform provides better decorrelation performances than the "Interleaved S+P", but at the expense of complexity.

The previous LAR codec did not achieve the compression efficiency as excellent as the JPEG2000, and also required a medium computation cost about the same with JPEG2000.

Therefore, it is reasonable to design different coding stages based on the previous works in order to raise the compression ratio while keeping the time consumption lower than those of the standards. In this chapter, the proposed LAR-LLC (Lossless Low Complexity) coding method adopts a 2×2 block transform called "Hierarchical Diagonal S Transform" (HD-ST). It combines the advantages of the R-WHT and "S+P" for high decorrelation and low complexity, respectively. A new inter and intra-levels prediction scheme is also introduced, with a very For the VLC stage, the context adaptive arithmetic coders are generally preferred as they provide significant gain by catching a part of the residual redundancy between symbols. However, these methods are also time-consuming [START_REF] Said | Comparative analysis of arithmetic coding computational complexity[END_REF], [START_REF] Shahbahrami | Evaluation of huffman and arithmetic algorithms for multimedia compression standards[END_REF]. The static Huffman coding is a ideal choice for the low computational solution. In order to compensate the inherent loss of compression efficiency compared with the arithmetic coder, a context modeling/classification step before the VLC coding is introduced. Context modeling is an open problem in the image coding, which has been widely analyzed in [START_REF] Wu | Lossless compression of continuous-tone images via context selection, quantization, and modeling[END_REF], [PKC + 10]. To avoid the problem of context dilution and to reduce the complexity, a simple while efficient method of classification is introduced. Based on the probability of distribution of the data source, we use a fixed context model to classify the error stream into four sub-classes. The classification criterion is directly deduced from the prediction error values, so the proposed scheme does not add significant processing time overhead. Experiments show that the proposed low complexity lossless codec achieves a compression ratio equivalent to JPEG2000, whereas it has much less coding latency.

The chapter is organized as follows. In Section 4.1, the general procedure of the proposed lossless image coding method is presented. Section 4.2 introduces HD-ST transform to build a pyramid structure for the multi-resolution. Section 4.3 introduces the prediction process applied for the reconstruction of the coded image based on lower resolution levels. Section 4.4 discusses the classification method for entropy coding. Results of the lossless coding efficiency and the analysis of the complexity are provided in Section 4.5. Finally, this paper is concluded in Section 4.6.

Framework of Coding Scheme

The proposed coder offers a scalable multi-resolution lossless image coding implementation. version. Then, the next step is a top-down dyadic decomposition with prediction. From the top level (lowest resolution), the higher resolution image is restored level by level until the full resolution is achieved. In each level, the prediction error values are classified into sub-classes, in order to decrease the total information entropy. Finally, each subsequence is separately coded.

              Y Db Dr               =               1 / 4 1 / 2 1 / 4 0 -1 1 1 -1 0                             R G B               ⇔               R G B               =               1 -1 / 4 3 / 4 1 -1 / 4 -1 / 4 1 3 / 4 -1 / 4                             Y Db Dr               (4.1)

HD-ST Transform and Pyramid

The 2D Walsh-Hadamard Transform (WHT 2×2 ), whose kernel is given in (4.2), is suitable for hardware implementation, since it requires only simple operations.

W 2×2 = 1 √ 2         1 1 1 -1         (4.2)
A pyramidal representation based on this particular transform is straightforward. Let I(i, j)

represent the pixel in an image I of size N x × N y , l is the level number, the full resolution image is in the l = 0 level. The pyramid structure {Y l } can be expressed in (4.3).

Y l (i, j) =                I(i, j) , l = 0           1 4 1 k=0 1 m=0 Y l-1 (2i + k, 2 j + m)           , l > 0 (4.3)
where 0 ≤ i ≤ N x /2 l . . stands for rounding downward. In this case, the upper lever pixel is the mean value of its four sons as shown in Fig. 4.2. However, the WHT 2×2 is not fully reversible, due to the rounding operations. In [START_REF] Déforges | The RWHT+P for an improved lossless multiresolution coding[END_REF], a solution was provided to the reversibility aspect.

It can refine the sum of elements from the rounded average value plus an addition bit. This bit records the remainder of the division and is separately encoded from the other coefficients. This solution offers ideal first-order entropy based on the reversible pyramid structure. The major drawback is that it adds a significant complexity for the correlation/decorrelation process. An alternative solution was proposed in [START_REF] Babel | Interleaved s+p pyramidal decomposition with refined prediction model[END_REF], with the "Interleave S+P" pyramid which is based on the S transform [START_REF] Said | Reversible image compression via multiresolution representation and predictive coding[END_REF]. S transform considers that a sequence of integers C(n) can be represented reversibly by two sequences M(n) and G(n) in the equation (4.4). M(n) and G(n)

are the mean and gradient values of the two pixels, respectively.

         M(n) = C(2n) + C(2n + 1) 2 G(n) = C(2n) -C(2n + 1)          C(2n) = M(n) + G(n) + 1 2 C(2n + 1) = C(2n) -G(n) (4.4)
In [START_REF] Babel | Interleaved s+p pyramidal decomposition with refined prediction model[END_REF], the S transform is applied on the two pixels on the first diagonal. The achieved mean value is used for the upper level, and the gradient is coded. Then, the S transform is applied on the second diagonal, and the two transformed coefficients (mean + gradient) are coded for this stage. The major drawback is that the value associated to a block is the mean value of the diagonal pixels inside the block, instead of the mean estimated over all the pixels.

The major advantage of the method is that, besides the addition and subtraction operation, the transform only needs the division by 2, which can be implemented by shifts. Thus, it has a low computation complexity. In order to combine advantages of both methods, a Hierarchical Diagonal S Transform (HD-ST) is proposed in this section.

It is reasonable to use all the pixels in a block to compose the pixel in the upper level.

Besides, the WHT 2×2 is easy for the implementation. Therefore, we still apply (4.3) to build the scalable structure. In order to make the transform reversible, it is achieved by the S transform in two steps. As illustrated in fig. 4.3, the first step of the decomposition consists of applying the S transform on two diagonals respectively. For each diagonal, the S transform produces one mean coefficient M l and one gradient coefficient G l . In the second step, the S transform is applied on the two mean coefficients (DC) M 1,l from the first diagonal, and M 2,l from the second diagonal. The resulting DC value M d,l is used as the pixel of the upper level, and three gradients are coded : two (G 1,l , G 2,l ) in the step 1, and one (G d,l ) in the step 2. Different transformed coefficients are defined as follows.

Step 1.

         M 1,l (2i, 2 j) = Y l (2i, 2 j) + Y l (2i + 1, 2 j + 1) 2 G 1,l (2i, 2 j) = Y l (2i, 2 j) -Y l (2i + 1, 2 j + 1)          M 2,l (2i, 2 j) = Y l (2i + 1, 2 j) + Y l (2i, 2 j + 1) 2 G 2,l (2i, 2 j) = Y l (2i + 1, 2 j) -Y l (2i, 2 j + 1) (4.5) Pyramidal Prediction 97 Step 2.          M d,l = M 1,l (2i, 2 j) + M 2,l (2i, 2 j) 2 G d,l = M 1,l (2i, 2 j) -M 2,l (2i, 2 j) (4.6)
Where M d,l represents the estimated DC value for the upper pixel. The pyramid can be written in (4.7).

Y l (i, j) =              I(i, j) , l = 0 1 2 M 1,l-1 (2i, 2 j) + M 2,l-1 (2i, 2 j) , l > 0 (4.7)
Since the S transform is reversible and the HD-ST is composed of the uses of the S transform in three times, the HD-ST is also reversible and the converse process is referred in 4.4.

Details are presented in Section 4.3. It does not need an additional bit to decide whether DC is odd or even for the reconstruction as did in [START_REF] Déforges | The RWHT+P for an improved lossless multiresolution coding[END_REF]. We can note in 4.7 that the mean value is computed from all the pixels in the block. The decomposition process is fully asymmetrical, starting from step 2 to step 1. The total amount of operations per pixel can be easily estimated for composition/decomposition between two levels of the resolution : 1.5 add/sub and 0.75 shift operations only.

The next section will present the associated prediction process.

Pyramidal Prediction

x a b c X l (2i + 1, 2 j + 2) , X l (2i -1, 2 j + 1) -X l (2i + 2, 2 j + 2) , X l (2i + 1, 2 j) -X l (2i + 2, 2 j + 1) and X l (2i, 2 j -1) -X l (2i + 1, 2 j) . The G1,l (2i, 2 j) is expressed as (10).

=                  min{b, c}, i f a ≥ max{b, c} max{b, c}, i f a < min{b, c} b + c -a . ( 4
G1,l (2i, 2 j) = 1 6 Y l (2i -1, 2 j -1) -X l (2i, 2 j)

+ X l (2i + 1, 2 j + 1) -X l (2i + 2, 2 j + 2) + 1 k=0 X l (2i -1 + k, 2 j + k) -X l (2i + k, 2 j + 1 + k) + 1 n=0 X l (2i + n, 2 j -1 + n) -X l (2i + 1 + n, 2 j + n) (4.11)
X l (2i + 1, 2 j) and X l (2i, 2 j + 1) are removed for the addition and subtraction. X l (2i + 2, 2 j + 2)

is estimated by M 1,l (2i + 2, 2 j + 2). Other X l pixels are evaluated by the average of four nearby pixels as shown in fig. 4.5 (b). The difference, X l (2i, 2 j) -X l (2i + 1, 2 j + 1), is equal to the G1,l (2i, 2 j). After simplification, G1,l becomes (4.12).

G1,l (2i, 2 j) = 0.153 1.5 Y l (2i -1, 2 j -1) -M 1,l (2i + 2, 2 j + 2) By coding the prediction error, G 1,l (2i, 2 j) can be calculated out and the pixels Y l (2i, 2 j) and Y l (2i + 1, 2 j + 1) in the first diagonal are available according to (4.13).

+ 0.5 M 1,l (2i -2, 2 j) + M 1,l (2i, 2 j -2) -M 1,l (2i, 2 j + 2) -M 1,l (2i + 2, 2 j) (4.12) LAR-LLC el , 2j-2 X l 2i+2,2j+2 l 2j-1 l 2j+2 X l 2i+2,2j+1 Y l 2i+2,2j-2 X l l 2j+1 l , 2j ixels (b) Evaluation of X Y l 2i, 2j Y l 2i+2,2j+2 Y l 2i+1,2j+1 Y l 2i-1, 2j Y l 2i-1, 2j-1 Y l 2i+1, 2j-1 X l 2i+1,2j+2 X l 2i+2,2j+1 Y l 2i-1,2j+1 Y l 2i, 2j-1 Y l 2i+2, 2j-1 Y l 2i,2j+2 Y l 2i+2, 2j X l 2i-1, 2j+2 X l 2i+1, 2j X l 2i, 2j+1
         Y l (2i, 2 j) = M 1,l (2i, 2 j) + G 1,l (2i, 2 j) + 1 2 Y l (2i + 1, 2 j + 1) = Y l (2i, 2 j) -G 1,l (2i, 2 j) (4.13) 4.3.3 Prediction for G 2,l
The previous step enables to decode values in the first diagonal. Then, the prediction of G 2,l (2i, 2 j), which is used to recover pixels Y l (2i+1, 2 j) and Y l (2i, 2 j+1), can take advantage of a rich context. The prediction is anisotropic when a horizontal or vertical direction is adopted, otherwise it is isotropic. Fig. 4.6 presents the neighbourhood space for the analysis. We introduce di f _h and di f _v as the gradient estimations for the horizontal and vertical directions, given as (4.14). The di f _h is used to evaluate the similarity of the pixels in the horizontal direction while the di f _v is in the vertical direction.

di f _h = 2M 2,l (2i, 2 j) - 1 2 Y l (2i, 2 j) + Y l (2i -1, 2 j + 1) + Y l (2i + 2, 2 j) + Y l (2i + 1, 2 j + 1) di f _v = 2M 2,l (2i, 2 j) - 1 2 Y l (2i + 1, 2 j -1) + Y l (2i, 2 j) + Y l (2i + 1, 2 j + 1) + Y l (2i, 2 j + 2) (4.14)
where |.| denotes the absolute value here and after. The di f _h represents the absolute diffe-Pyramidal Prediction 101 rence between the second mean value M 2,l (2i, 2 j) and the average of the adjacent pixels in the horizontal direction, and the di f _v represents the one in the vertical direction. A large value of di f _h or di f _v is often due to the presence of an edge. In that case, a better estimation can be achieved by a directional prediction. Therefore, the prediction of G 2,l (2i, 2 j) is treated for the "flat" part and "edge" part respectively. In this implementation, we set a threshold to 20 to separate the prediction into two branches. We set this threshold value in order to keep a weight coefficient α no less than 95.5% when di f _h = 1 for the "edge" prediction in the Branch 1. α is given by

α = di f _v di f _h + di f _v . (4.15)
Similarly, (1 -α) is not less than 95.5% when di f _v = 1.

Branch 1 : If one of di f _h and di f _v, or both are greater than the threshold, this block is considered in an "edge" part. The proposed predictor is defined as (4.16). When di f _h is greater than di f _v, it probably means the "edge" is in vertical direction. Thus, the contribution from the vertical direction is favored 1 -α is greater than α.

G2,l (2i, 2 j) = α 2 Y l (2i, 2 j) -Y l (2i -1, 2 j + 1) + Y l (2i + 2, 2 j) -Y l (2i + 1, 2 j + 1) + 1 -α 2 Y l (2i + 1, 2 j -1) -Y l (2i, 2 j) + Y l (2i + 1, 2 j + 1) -Y l (2i, 2 j + 2) (4.16)
Branch 2 : If both di f _h and di f _v are not greater than the threshold, a smoother prediction is suited to G2,l (2i, 2 j), given in (4.17).

G2,l (2i, 2 j) = 3 8 Y l (2i + 1, 2 j -1) + Y l (2i + 2, 2 j) -Y l (2i -1, 2 j + 1) -Y l (2i, 2 j + 2) - 1 8 Y l (2i, 2 j -1) + Y l (2i + 2, 2 j -1) -Y l (2i -1, 2 j) -X l (2i + 1, 2 j) (4.17) X l (2i + 1, 2
j) is estimated by Wu's predictor for the third pass [START_REF] Wu | Lossless compression of continuous-tone images via context selection, quantization, and modeling[END_REF].

Xl (2i + 1, 2 j) = 3 8 Y l (2i, 2 j) + Y l (2i + 1, 2 j -1) + Y l (2i + 2, 2 j) + Y l (2i + 1, 2 j + 1) - 1 4 Y l (2i, 2 j -1) + Y l (2i + 2, 2 j -1) (4.18)
The floating-point operations are much more complex and time-consuming than the integer ones for both software and hardware implementations [START_REF] Chen | Hardware Software Co-Design of a Multimedia SOC Platform[END_REF]. Thus, we approximate the floating-point multiplication by simple integer operations, such as the add/sub and shift. The

LAR-LLC

division by 2 m (m ≥ 0, m is an integer) can be achieved by right-shift in m times, denoted by (>> m), while the multiplication with 2 n (n ≥ 0, n is an integer) can be achieved by left-shift in n times, denoted by (<< n). For the prediction of the Gd,l , the coefficient 0.

.3 • X ≈ (X >> 2) + (X >> 3) -(X >> 4) 0.035 • X ≈ (X >> 5) + (X >> 8) 0.153 • X ≈ (X >> 3) + (X >> 5) -(X >> 8) (4.19)
where X represents the multiplier. The division operation is only required for G2,l in (4.16).

After this step, pixels in the second diagonal are available in (4.20).

         Y l (2i + 1, 2 j) = M 2,l (2i, 2 j) + G 2,l (2i, 2 j) + 1 2 Y l (2i, 2 j + 1) = Y l (2i + 1, 2 j) -G 2,l (2i, 2 j) (4.20)

Entropy Pre-coding and Coding of Prediction Errors

Context adaptive arithmetic coders are efficient solutions for VLC encoding. However, the complexity is still considered to be higher than the Huffman one [START_REF] Said | Comparative analysis of arithmetic coding computational complexity[END_REF]. For the "ultrafast" mode of JPEG2000, T. Ritcher et al. replaced the EBCOT coding by a simple Huffmanrunlength one [START_REF] Richter | Towards high-speed, low-complexity image coding : variants and modification of JPEG 2000[END_REF]. Similarly, a Pre-coding+Huffman scheme is adopted in this section.

For the Huffman coding, we adopt the classic static mode rather than the adaptive mode.

The former generates a non-adaptive codebook from the data source, and then codes symbols by pre-fixed codebook elements. The latter often uses the feedback loop and delays the coding because of the limitation on the amount of symbols to be each time handled. Before the Huffman coder, a pre-coding step consisting in a pre-classifying symbols is applied to increase the coding gain. This concept is based on the source separation theory : the global entropy of a source can be reduced if the source is "well" separated into sub-sources with different Probability Distributions (PD) [START_REF] Huang | Prioritized DCT for compression and progressive transmission of images[END_REF]. The implementation of pre-coding is dependent on the overall coding scheme. After prediction, most residual errors have small amplitudes, and the distribution function is symmetric around zero. A suitable classification solution would be to separate errors according to their amplitude. The following part gives an analysis on the change of the source entropy by the use of the amplitude classification. The error stream can be considered as a finite input sequence A of a discrete memoryless source with a alphabet set U = {a 1 , a 2 , ..., a n }. The sequence A has a length N. N i is the amount of the symbol a i (1 ≤ i ≤ n) in this sequence. Let the probability of a symbol a i be

p A (a i ) = N i N , 1 ≤ i ≤ n. (4.21)
The entropy of the sequence can be expressed by Eq. (4.22). H(A) gives the lower bound of the average code length L for each symbol to losslessly encode A.

H(A) = - n i=1 p A (a i ) • log 2 p A (a i ) (4.22)
The least totally required code length is NH(A). Consider any subsequence A 1 with a length N 1 and A 2 with a length N 2 , A 1 ∈ U 1 = {a 1 , a 2 , ..., a n1 } and A 2 ∈ U 2 = {a n1+1 , a n1+2 , ..., a n }.

Then U = U 1 ∪ U 2 and U 1 ∩ U 2 = ∅. It has N = N 1 + N 2 ,
and the least required code length can be expressed by (4.23) when coding A 1 and A 2 separately.

N 1 H(A 1 ) + N 2 H(A 2 ) = -N 1 n1 j=1 p A 1 (a j ) • log 2 p A 1 (a j ) -N 2 n k=n1+1 p A 2 (a k ) • log 2 p A 2 (a k ) (4.23)
where p A 1 (a j ) is the probability of a j in subsequence A 1 and p A 2 (a k ) is the probability of a k in A 2 . Notice that N 1 p A 1 (a j ) equals to N p(a j ), and N 2 p A 2 (a k ) equals to N p(a k ). Let α = (N 1 /N) (0 < α < 1), then (4.23) can be simplified as The side information will be needed for the decoder in order to recover the sub-sequences exactly during the decoding process. For instance, in this binary classification, 1 bit is required to indicate which class has been chosen for the current prediction error. The side information increases the bitrate and overbalances the potential benefit of the entropy reduction. To avoid this side information, we prefer a prior classification, and the pre-coding in LAR-LLC mainly consists of defining good error amplitude estimation based on the information around the current position.

N 1 H(A 1 ) + N 2 H(A 2 ) =N          - n1 j=1 p A (a j ) • log 2 p A (a j ) - n k=n1+1 p A (a k ) • log 2 p A (a k )          + N          n1 j=1 p A 1 (a j ) • log 2 N 1 N + n k=n1+1 p A 2 (a k ) • log 2 N 2 N          =NH(A) + N α • log 2 α + (1 -α) • log 2 (1 -α) (4.24) Let [ -α • log 2 α -(1 -α) • log 2 (1 -α)] be β, it can be achieved that LAR-LLC N 1 H(A 1 ) + N 2 H(A 2 ) = N H(A) -β ≤ N H(A) (4
In order to find an efficient, but not computationally complex estimation method, we have investigated different criteria such as the amplitude of the gradient prediction, co-located errors for previous gradient, and errors of the upper level. Eventually, the available prediction errors from adjacent positions at current level and the corresponding one at upper level are considered together for a notable improvement in the coding efficiency. The classification method based on it is introduced in the following.

Let e l (2i, 2 j) be the current prediction error of any G component in a block. The evaluated value of its amplitude ȇl_apt (2i, 2 j) is defined as (4.26).

                     Coe adjacent = 1 4 e l (2i -2, 2 j) + e l (2i, 2 j -2) + e l (2i -2, 2 j -2) + e l (2i + 2, 2 j -2)
Coe upper = e l+1 (i, j)

⇒ ȇl_apt (2i, 2 j) = 3
X l 2i-1, 2j Y l 2i-1, 2j-1 Y l 2i-2, 2j-2 Y l 2i, 2j-2 Y l 2i+1, 2j-1 X l 2i+1,2j+2 X l 2i+2,2j+1 Y l 2i-2, 2j Y l 2i-1,2j+1 X l 2i, 2j-1 Y l 2i+2,2j-2 X l X l 2i, 2j X l 2i+1, 2j+1 X l 2i+1, 2j X l 2i, 2j+1 (a) Positions of referred pixels (b) Evaluation of X X l 2i+2,2j+2 X l 2i-1, 2j Y l 2i-1, 2j-1 Y l 2i-2, 2j-2 Y l 2i, 2j-2 Y l 2i+1, 2j-1 X l 2i+1,2j+2 X l 2i+2,2j+1 Y l 2i-2, 2j Y l 2i-1,2j+1 X l 2i, 2j-1 Y l 2i+2,2j-2 X l X l 2i, 2j X l 2i+1, 2j+1 X l 2i+1, 2j X l 2i, 2j+1 (

Compression Performance

In this section, the effectiveness of the proposed LAR-LLC is compared with those of still image compression standards in compression efficiency and coding speed. These standards are still current references for image coding and their complete reference solutions are available : the JPEG2000 (JPEG2K) implementation is available in [Ada] ; the JPEGXR reference software is generated from [ITU] ; JPEGLS is from [UBC] and Lossless JPEG is offered in [HS]. Because this work focuses on the complexity, although some other image coding methods report better compression ratios with heavier computations, they are not compared in detail in this section. Kim et al. proposed a hierarchical prediction and context adaptive coding for lossless color image compression (LCIC) [START_REF] Kim | Hierarchical prediction and context adaptive coding for lossless color image compression[END_REF]. They offered the reference execution [KC]. They pointed out that their coding method LCIC can show an average bit rate reduction over JPEG2K, but it needs slightly more computation time than JPEG2K. Therefore, we also take this referenced method into the comparison. 16 images (RGB 24 bit/pixel) with different content/features are chosen mainly from the set of ISO/ITU reference images. They cover contents of objects, human and surrounding views. Test images are presented in Fig. 4.10.

Compression Efficiency

This subsection firstly shows the effectiveness of the classification scheme used in the Precoding part. and N 4 be the numbers of elements in H(A 1 ), H(A 2 ), H(A 3 ) and H(A 4 ). H class is calculated by LLC can achieve the equivalent lossless compression efficiency of JPEG2K, while be 76.11% faster than JPEG2K for encoding and 75.94% faster for decoding. JPEGLS has the least time consumption on coding. However, it costs 7.02% bpp more than JPEG2K and about 8.08% more than LAR-LLC, and has fluctuations for the compression ratio compared with LAR-LLC. LAR-LLC has less coding latency than JPEGXR, and saves 8.67% bpp of JPEGXR.

H class = H(A 1 ) • N 1 + H(A 2 ) • N 2 + H(A 3 ) • N 3 + H(A 4 ) • N 4 N 1 + N 2 + N 3 + N 4 . ( 4
Besides, LAR-LLC also supports the spatial scalability as JPEG2K does for multi-resolution application.

The LAR-LLC currently runs in a mono thread configuration, but has potential parallel processing ability in multi-threading. For the pyramid building process in Section 4.2, the DC component for blocks at each level is independently estimated. Then, the global process can be performed in a SIMD approach, with one thread processing one part of the image. Besides, during the pyramidal decomposition, the image coding process involves three main pipelined steps : prediction, classification and Huffman coding. These stages are performed for each level and for three coefficients per level. It means that the last Huffman coding step in level l + 1 can run simultaneously with the prediction step in level l, both handled by different threads. Some parallel processing is also possible for JPEG2K for the Discrete Wavelet Transform (DWT) part [START_REF] Shahbahrami | SIMD architectural enhancements to improve the performance of the 2D discrete wavelet transform[END_REF] or the EBCOT module [START_REF] Menichelli | Performance evaluation of JPEG2000 implementation on VLIW cores, SIMD cores and multi-cores[END_REF]. Recently, new parallel processing methods and advanced graphic processing units are also applied to JPEG2K for a significant speedup in the execution time [START_REF] Roto Le | A novel parallel tier-1 coder for JPEG2000 using GPUs[END_REF][WCL12].

Conclusion

In this chapter, a low complexity scalable lossless image compression method LAR-LLC is introduced to decrease the latency of encoding and decoding while remaining high compression efficiency. Based on a Hierarchical Diagonal S Transform, coding starts at a top-down dyadic decomposition with targeted prediction processes. For each process, the predictor runs in one pass and avoids the latency caused by the feedback action. Because the prediction errors are coded from the low resolution to the full resolution level, this coding structure offers the scalable resolution ability in the bit stream. The receiving terminal can decode the image in progressive-resolution according to the channel capacity and user requirements. After the prediction, a classification step is applied to reduce the entropy of prediction errors for increasing the coding efficiency.

LAR-LLC

Experiments showed that, the pre-coding scheme including the classification action really decreases the entropy of the error sequence, and it is beneficial for the following entropy coding step. For the lossless coding of the nature color images, LAR-LLC achieves the coding efficiency equivalent to JPEG2K, and as good as the latest non-standard coding method. Besides, LAR-LLC has less coding latency in both encoding and decoding parts than the ones of JPEG2K. Due to the space scalability, low complexity and notable compression ratio, LAR-LLC is a good image compression solution with high quality for the multimedia storage and communication, implementing both in hardware and in software.

Chapter 5 Conclusion and Perspectives

In this manuscript we introduced a RDO (Rate-distortion-optimization) model, an objective quality control model and an enhancement scheme of the subjective quality for the lossy coding based on LAR the (Locally Adaptive Resolution) image codec. Besides, a new lossless image codec, LAR-LLC (Locally-adaptive resolution, lossless low complexity), is introduced to achieve a coding efficiency equivalent to that of JPEG2000, while having a lower computational complexity in order to reduce the coding latency. The contributions of the novelties are presented in the conclusion section in detail.

Conclusion of the thesis work

Rate-distortion-optimization model for LAR codec

The classic LAR codec has complete lossy and lossless coding structures. In the lossy coding mode, two functions, the Quadtree partitioning and the quantization of the prediction errors, are designed to miss the information of the image in order to economize the bitrate.

Meanwhile, the Quadtree partition is controlled by a threshold Thr, and the Quantization is regulated by a parameter quqp. The study firstly analysed the different distortions derived from the Thr and the quqp, next selected the optimal pairs of the Thr and the quqp. Based on the characters of adjacent pixels, a RDO model is built to describe the relationship of the Thr and the quqp of the optimal pairs. According to the model, a suitable Thr corresponding to a set quqp can be chosen. With the modeled Thr and quqp, the LAR codec can achieve an optimal or closely optimal lossy coding efficiency. The RDO model is introduced in Section 3. Moreover, because the RDO model is sensitive to the change of pixels, it is used in adjacent regions in order to allocate a series of Thr which is adaptive to local change of pixels. This allocation meets the fact that the human visual system is less sensitive to noise in strong texture areas than the less textured areas. After this adaptive Thr allocation, the decoded image has a better perceptual quality and higher subjective score measured by the Structure Similarity (SSIM) than the one without the allocation scheme. Meanwhile, this allocation scheme brings a little influence on the objective quality measured by the Peak signal-to-noise ratio (PSNR).

The relative analysis is given in Section 3.5.

Lossless Low-complexity codec LAR-LLC

Due to the limited compression efficiency and high computational complexity, the classic LAR codec shows a lower performance than that of the standard JPEG2000. In Chapter 4, a new lossless image coding method LAR-LLC which is based on the LAR framework is introduced. This method still supports the multi-resolution function which is realized by a HD-ST Transform. This transform is reversible and easy to be implemented. The coding process is similar with the classic LAR codec, and starts from the lowest resolution level. It uses the correlation of intra and inter levels to reconstruct higher resolution images, until the full resolution image is achieved. The reconstruction procedure depends on three prediction steps. The prediction errors need to be coded for the decoder to recover the image. The prediction errors should be lossless coded. In order to improve the compression efficiency of the entropy coders for the prediction errors, a pre-coding step is added to reduce the entropy of the error sequence. The experiments are introduced in Subsection 4.5.1. The experimental results firstly confirm that the pre-coding step decreases the entropy of the sequence of the prediction errors, next, according to the comparison of different codecs on the compression efficiency, LAR-LLC shows an equivalent performance to the one of JPEG2000 : the average bitrate of LAR-LLC is 0.98% less than the one of JPEG2000, this result is a little better than the one (0.67%) of the codec derived from the recent proposed lossless image coing method LCIC [START_REF] Kim | Hierarchical prediction and context adaptive coding for lossless color image compression[END_REF]. LAR-LLC also has relative stable compression ratios as JPEG2000 does in the comparison with JPEGLS. In the complexity test, LAR-LLC shows the less coding latency than JPEG2000 : 76.11% faster than JPEG2000 in the encoding and 75.94% in the decoding.

Perspectives

This section presents some ideas that could be prospects of the future research. These ideas are derived from the study of the LAR, and could be benefit for other image codecs or data compression techniques.

Distortion control based on the perceptual quality in the lossy coding

The metrics of the objective quality are still the most widely used methods to evaluate the decoded images. They can detect any distortions in the reconstructed image and give corresponding quality "scores" for the image. Many lossy coding methods aim at the reduction of the objective distortion, and design their RDO and rate control (RC) schemes. However, this strategy is not suitable in some cases for the natural images. Although some kinds of distortions may reduce largely the objective quality, such as PSNR, they do not bring much visible uncomfortable effects to the decoded image, as examples discussed in Section 3.5. A human viewer is the final judge of the image quality in most applications, therefore, it is advantageous to take into account the properties and characteristics of the Human Visual System (HVS) that affect the image quality as judged by human viewers when one is designing an image compression algorithm and assessing picture quality.

The objective quality measures are mainly used because of their simple analysis and the lack of other available and accepted standardized quality measures [EF95] [START_REF] Silverstein | The relationship between image fidelity and image quality[END_REF]. Meanwhile, for the subjective measurement, the images are often rated based on the visibility of the distortion artefacts according to a predetermined scale [START_REF] Silverstein | The relationship between image fidelity and image quality[END_REF]. Although the test is reliable, it requires specialized viewing conditions [START_REF] Carnec | An image quality assessment method based on perception of structural information[END_REF] and can not be used as a real-time scheme to improve the coding. There has been considerable amount of research done to develop objective metrics which incorporate the perceived quality measurement by considering HVS characteristics [START_REF] Silverstein | The relationship between image fidelity and image quality[END_REF], [START_REF] Gao | A de-blocking algorithm and a blockiness metric for highly compressed images[END_REF], [START_REF] Zhou Wang | Image quality assessment : from error visibility to structural similarity[END_REF]. Similarly, for the LAR codec, it is possible to modify the lossy coding under the consideration of the perceived quality. As described in Chapter 3, the RDO model is derived from the analysis on the objective distortion measurement. The subjective enhancement scheme has been based on the fact that the edge lying in a textured region is less visible to a human observer compared to the edge in a plain background.

In the future work, another factor needs to be considered for the visual sensitivity is the background luminance : the visibility of the edge is often affected by the surrounding regions.

For example, the edge lying in a darker region is less visible compared to the edge in the brighter region [KK95] [START_REF] Venkatesh Babu | An hvs-based no-reference perceptual quality assessment of jpeg coded images using neural networks[END_REF]. It indicates that the distortion in the dark region is more

Conclusion and Perspectives

tolerable than the one in the bright region. Therefore, it is more important to record the changes of pixels in the plain and bright region rather than in the textured and darker region. Take the Fig. 3.34 as an example, with the adaptive Thr allocation scheme, the Quadtree grid uses small blocks to reserve the details on the face and hand, but in the hair and the gray background, the Quadtree grid does not need to allocate a lot of small blocks to record the changes of pixels. This idea requires a luminance detection before the adaptive Thr allocation. For the dark region, a fixed Thr is directly applied to the Quadtree partition. It can be seen as an extension of the locally adaptive Thr allocation scheme in order to modify the Thr map.

Moreover, in the future work, the distortion derived from the quantization needs to be controlled. As indicated in Subsection 3.5.1, the magnitude of a justly noticeable luminance change ∆I is approximately proportional to the background luminance I for a wide range of the luminance values. In the quantization step, the difference between the original pixel and the de-quantized one is weighted by the Weber's law as did in [START_REF] Wang | Modern image quality assessment[END_REF] [TVDY12]. This model has accurate rates about 60% to 70% in the tests. The entropy coding efficiency can be enhanced with a higher accuracy. One possible method is to build a context model set and choose a suitable model adaptively during the classification. This method requires a local analysis on the direction of pixels in order to decide which prediction error, such as e l (2i -2, 2 j -2), e l (2i, 2 j -2), e l (2i + 2, 2 j -2), e l (2i -2, 2 j) and e l+1 (i, j), should has a higher weight. Indeed, more latency of the coding is caused by this analysis.

Better context model for the classification in the Pre-coding process

Another solution is to use a data sequence to record the information of the accurate classification. This side sequence needs to be coded. Notice that the side sequence has a very limited alphabet, the symbols probability repeats frequently. A Run-length plus Huffman coding is considered to code this side information. The run-length coding generates the successive symbols onto one new symbol and the sequence the new generated symbols is coded by the Huffman coding. The total entropy is not reduced, but the side information sequence is quite simple to achieve an efficient coding ratio.

4 Résumé

 4 Tous d'abord, les éléments communs à la compression d'image sont présentés. Un schéma global pour la compression et décompression est Figure. 1. Pour l'encodeur, la première étape

Figure 1 -

 1 Figure 1la procédure de la compression et la décompression d'image.

Figure 2 -

 2 Figure 2 -LAR codec à deux couches

Figure 3 -

 3 Figure 3 -Construction de la pyramide par deux pyramides

Figure 4 -

 4 Figure 4 -Combinaisons optimales des paramètres pour 'bike crop'

  Figure 5 -Comparaison des images décodées avec quqp = 45. (a) MSSIM = 0.9898 (39.8670 dB) ; (b) MSSIM = 0.9875 (38.0621 dB).

Figure 6 -Figure 7 -

 67 Figure 6 -Comparaison des images décodées avec quqp = 45. (a) MSSIM = 0.9766 (32.6064 dB) ; (b) MSSIM = 0.9739 (31.6630 dB).

Figure 8 -Contents 2

 82 Figure 8 -Distributions de sous séquences et la séquence d'erreur original de G 1 sur l'image « bike ».

  Figure 1.1 -Image compression and decompression procedure.

Figure 1 . 2 -

 12 Figure 1.2 -Pixels for prediction.

Figure 1 . 3 -

 13 Figure 1.3 -Rotation of pixel pairs.

Figure 1 . 4 -

 14 Figure 1.4 -Matching process.

Figure 1

 1 Figure 1.5 -Template matching.

Figure 1

 1 Figure 1.6 -Scalar quantization.

4 n=1 p x n log 2

 42 p x n = -0.05 log 2 0.05 + 0.1 log 2 0.1 + 0.25 log 2 0.25 + 0.6 log 2 0.6 = 1.4905

Figure 1

 1 Figure 1.7 -JPEG mainly coding steps

Figure 1

 1 Figure 1.8 -Prediction for x

Figure 1 . 9 -

 19 Figure 1.9 -Decomposition on the tile by the wavelet transform

3 .

 3 Uniform coding method for lossy and lossless compressions -Unlike JPEG, JPEG2000 completes lossless and lossy coding based on the wavelet transform in one compression architecture.

Figure 1

 1 Figure 1.10 -Example of decomposition on image

Fig. 1 .

 1 Fig. 1.11 illustrates an example of rate distortion curve. It can be noticed that the distortion D dicreases while the bitrate R increases (the length of the bit-stream L will replace R in the

Figure 1

 1 Figure 1.11 -Example of rate distortion curve

  July 2007, the Joint Photographic Experts Group and the Microsoft put the HD photo into consideration for a new JPEG standard. In 2009, JPEGXR passed an ISO/IEC Final Draft chapter 1 International Standard (FDIS) ballot to be a new still image compression standard and file format for continuous tone photographic images [ISO09]. JPEGXR is based on the technology developed by Microsoft under the name HD Photo[STZ + 07].

[

  WM96] [WM97]. It is one of the best performing practical and general purpose lossless image coding techniques.

Figure 1

 1 Figure 1.12 -Schematic description of CALIC

Figure 1

 1 Figure 1.13 -Neighbor pixels

T

  = 2 is the escape case. It makes the encoder switch from the binary mode to the continuoustone mode. When entering the binary mode, encoder quantizes the context C = {y 1 , y 2 , ..., y 6 } to a 6-bit binary number B = b 6 b 5 ...b 1

c s( 1 )

 1 = s1a0...0, c s(2) = s1b0...0, c s(3) = s010...0, c s(4) = s010...0, c s(5) = s000...0, c s(6) = s000...0.

Figure 1

 1 Figure 1.14 -Performance curves of the lossy coding on gray images

Figure 1

 1 Figure 1.15 -Performance curves of the lossy coding on color images

Figure 2 .

 2 Figure 2.1 -Two-layer LAR coder

Figure 2 . 2 -

 22 Figure 2.2 -Framework of the LAR coder

Figure 2 .Figure 2 . 4 -

 224 Figure 2.3 -S transform on two diagonally adjacent pixels

  where N l x = N x /l and N l y = N y /l. Similarly, the transform on the second diagonal can form another pyramid structure asPyramid Decomposition and Prediction Model

Figure 2 .Figure 2 . 6 -

 226 Figure 2.5 -Decomposition of the LAR block process

Figure 2 . 7 -

 27 Figure 2.7 -Example of the symbol-oriented coding

Figure 3 . 1 -

 31 Figure 3.1 -Convex hull of operating points

ConvexFigure 3 . 2 -

 32 Figure 3.2 -Examples of distortion from the Quadtree and quantization

Figure 3 . 3 -

 33 Figure 3.3 -Examples of distortion curves of bike crop

Fig. 3 .Figure 3 . 4 -Figure 3 . 5 - 2

 334352 Fig. 3.4 illustrates the optimal pairs of T hr and quqp. It can be seen that they are not in a mass, but located in a belt which has an inflexion approximately at quqp = 53. The inflexion points also exist in the belts of other images. While the values of the inflexions are around quqp = 53. Thus, in order to describe the belt with low difficulty, piecewise linear functions are considered. The belt is firstly divided into 2 regions by quqp = 53. In each region, two linear equations are designed to simulate the area of the belt. The following part introduces important

Fig. 3 .

 3 Fig.3.7 presents curves of cumulative probability distribution functions of the four images.

Figure 3

 3 Figure 3.6 -Quadtree partition grids of images

  8 cropped images from the ISO 12640 JPEG test set and 12 free images in high resolution are taken out to form a training set. The RDO model is trained for each image to get a pair of corresponding α and β by the curve fitting. Indeed, the values of (α, β) of images are different but wave in a small range. Therefore, the average value of α and the average one of β, α = 17.93 and β = 121.07, are chosen as the coefficients of the model. Noticing the equation (3.7) does not go through the original point, it is used for the region II. However, this equation can provide the crossover point C (quqp = 53, T hr = T hr quqp=53 ), which should exit in both linear models of the region I and II. Considering the two points (0, 0) and C, the linear model for the region I can also be obtained

Figure 3

 3 Figure 3.8 -Performance of the RDO model for "bike crop"

Fig. 3 .

 3 Fig.3.9 to 3.20 give six examples of coding efficiencies of the LAR codec by the use of the RDO model. The "p26 crop" is from the training set, while "flower", "leaves", "louvre",

Fig. 3 .

 3 Fig.3.9 and 3.10 are the results of "p26 crop" (H G = 4.495). The modeled points are very

Figure 3 .

 3 Figure 3.9 -Coding efficiencies of the RDO model in MSE on "p26 crop"

Figure 3 .

 3 Figure 3.10 -Coding efficiencies of the RDO model in PSNR on "p26 crop"

Fig. 3 .Figure 3 .Figure 3 .

 333 Fig. 3.15 and 3.16 are for the image "louvre" (H G = 5.045). The largest difference in MSE is 8.25 at 0.168 bpp, where the optimal one is 266.75 and the modeled one is 275. This diffe-

Figure 3 .Figure 3 .

 33 Figure 3.13 -Coding efficiencies of the RDO model in MSE on "leaves"

Figure 3 .Figure 3 .Figure 3 .Figure 3 .Fig. 3 .

 33333 Figure 3.15 -Coding efficiencies of the RDO model in MSE on "louvre"

Figure 3 .Figure 3 .

 33 Figure 3.19 -Coding efficiencies of the RDO model in MSE on "rokounji"

Figure 3 .

 3 Figure 3.21 -Examples of the linear relationship between MSE and quqp

  .12) Since the proposed RDO model adopts the piecewise function, this MSE model also has different forms for two regions. Firstly considering the region II which represents the area of quqp > 53, by the use of the curve fitting to the training set, we can get a practical pair of (α, β), α = 0.058 and β = -0.9. With the equation (3.10), the relationship between MSE and quqp can be expressed by

( 3 Figure 3 .

 33 Figure 3.22 -The comparison between the MSE obtained and the estimated by the MSE model

  Figure 3.23 -MSE constraint on "bike crop"

Fig. 3 .

 3 Fig. 3.23 shows the examples of the quality (MSE) constraint on the image "bike crop".The obtained MSE is close to the constrained one.

Figure 3 .

 3 Figure 3.24 -Comparison between the MSE set and MSE obtained for "p06 crop"

Figure 3 .

 3 Figure 3.25 -Comparison between errors and MSE set for "p06 crop"

Fig 3 .

 3 24 to 3.31 show the comparisons between the MSE set and MSE obtained. The errors of the MSE obtained are also compared with the MSE set.

Fig 3 .Fig. 3 .Figure 3 .Figure 3 .

 3333 Fig 3.24 is the comparison for "p06 crop". The MSE obtained curve is close to the targeted MSE set curve. At high bitrates, they match well, but the obtained curve raises faster than the set one and causes a larger error. This trend is also indicated in Fig 3.25. With the increase of the MSE set, the absolute error becomes larger. However, the ratio of the absolute error and MSE set keeps stable at about 10% when MSE set is larger than 60. Fig.3.26 and 3.27 show the results of "flower". At high bitrates, the difference between

Fig 3 .

 3 Fig 3.28 and 3.29 are the results of "leaves". The two curves matches well in Fig 3.28. Thelargest difference is around 0.5 bpp and the absolute value is about 6, which occupies the MSE less than 14%, but most points have small ratios which less than 10% even to 4%.

Fig 3 .

 3 Fig 3.30 and 3.31 are for the last image "louvre". The errors are all less than 6 and the ratio decreases steadily to below 5%.

Figure 3 .Figure 3 .

 33 Figure 3.28 -Comparison between the MSE set and MSE obtained for "leaves"

Figure 3 .Figure 3 .

 33 Figure 3.30 -Comparison between the MSE set and MSE obtained for "louvre"

  (a) Distortion caused by the quantization (b) Distortion caused by the Quadtree

Figure 3 .

 3 Figure 3.32 -Comparison of the distortions on "bike crop", MSE = 50

Fig. 3 .

 3 33 and 3.34 give two examples of the adaptive scheme. Fig.(b) shows the T hr map.

  indicated before, MSE and PSNR are not efficient to evaluate the subjective quality. Another way, Mean opinion score (MOS) is a directly subjective test to obtain the human user's view of the quality. It requires the users to evaluate the image and give a perceived score, and then average the score values to generate the final MOS value. This test really gives the subjective results of the image, but it requires a certain number of users to take the test without any distortion. Any change of the users or the scene of the test possibly bring the different MOS. It is not as convenient as the MSE and PSNR. In 2004, Z. Wang et al. proposed a new paradigm for quality assessment, SSIM, which is based on the hypothesis that the HVS is highly adapted for extracting structural information [WBSS04]. They developed the measure of Structural Similarity (SSIM) that compared local patterns of pixel intensities that have been normalized for luminance and contrast. The SSIM metric is calculated in a specific form of the index as Eq. (3.15).

Figure 3 .

 3 Figure3.33 -Adaptive T hr allocation according to quqp = 45 for "bike crop". 3.33a is the original image ; 3.33b illustrates different T hr in blocks, the brighter block represents a larger T hr than the darker one ; 3.33c gives the Quadtree grid with the adaptive T hr allocation scheme ; 3.33d shows the grid without the scheme.

Figure 3 .

 3 Figure3.34 -Adaptive T hr allocation according to quqp = 45 for "woman crop". 3.34a is the original image ; 3.34b illustrates different T hr in blocks, the brighter block represents a larger T hr than the darker one ; 3.34c gives the Quadtree grid with the adaptive T hr allocation scheme ; 3.34d shows the grid without the scheme.

K 2

 2 << 1. L is the dynamic range of the pixel-values (255 for 8-bit gray scale images). In practice, the SSIM index is applied locally rather than globally. Because the image statistical features are usually highly spatially non-stationary. The localized quality measurement can provide a spatially varying quality map of the image, which delivers more information about the quality degradation of the image. The local statistics µ x , σ x and σ xy are computed within a local 8 × 8 square window. The window moves pixel-by-pixel over the entire image. In order to solve the undesirable "blocking" artifacts, Z. Wang et al. used an Gaussian weighting function w = {w i | i = 1, 2, ..., N}, with normalized unit sum N i=1 w i = 1, to modify the local statistics as

Figure 3 .Fig. 3 .

 33 Figure 3.35 -Comparison of different distortions in the same MSE = 200. (a) MSSIM = 0.9934 (43.5534 dB) ; (b) MSSIM = 0.9894 (39.5122 dB) ; (c) MSSIM = 0.8878 (18.9973 dB).

Fig. 3 .

 3 Fig.3.36 and 3.37 show the decoded images with and without the T hr adaptive scheme.

Figure 3 .

 3 Figure 3.36 -Comparison of the decoded images in quqp = 45. (a) MSSIM = 0.9898 (39.8670 dB), bitrate :0.841 bpp ; (b) MSSIM = 0.9875 (38.0621 dB), bitrate :0.836 bpp.

Figure 3 .

 3 Figure 3.38 -Images for tests of the adaptive T hr scheme.

Figure 3 .Figure 3 .Figure 3 .

 333 Figure 3.39 -MSSIM scores of "bike crop". Bike crop

Figure 3 .Figure 3 .

 33 Figure 3.42 -MSSIM scores of "p06".

Figure 3 .Figure 3 .Figure 3 .Figure 3 .

 3333 Figure 3.44 -Part of the image "p06". (a) the reference image ; (b) the improved decoded image, 0.5 bpp ; (c) the unimproved image, 0.5 bpp.

a

  first decorrelation step based on transform and/or prediction techniques, and a final Variable 91 92 LAR-LLC Length Coding (VLC) stage. As the VLC part is always a reversible process, the lossless coding feature is generally only dependent on the first stage. For transform-based approaches, it implies to use only reversible transforms, or to encode the residual errors after the transform. Besides the standards, new methods are also proposed for specific image coding applications. Matsuda et al. designed an image coding scheme including a variable block-size adaptive inter-color prediction technique [MKMI07]. This scheme requires a high computational complexity of encoding due to an iterative optimization procedure. Zhao et al. applied a structure learning and prediction scheme to the lossless image coding [ZH10]. This method is efficient to images with rich high-frequency components, but also demands much computational complexity caused by the expensive structure prediction. Pan et al. developed a low-complexity screen compression scheme for lossy coding [PSL + 13]. This scheme performs well on screen images of texts, but underperforms JPEG2000 for natural images. Park et al. presented a low complexity lossless image compression scheme using the context modeling and got compression results close to that of JPEGLS [PKC + 10].

Framework

  of Coding Scheme 93 limited complexity. Both transform and prediction are performed on the integer calculation only.

Fig. 4 .

 4 1 shows the coder structure. The color image is firstly converted from RGB space to Y Db Dr space [PSB + 09]. As given in the equation (4.1), the Y Db Dr color space is reversible and has a low computation complexity as only shift and addition operations are required. Because the green light contributes the most to the intensity perceived by humans, the luminance Y reserves the half amplitude of the green element G, and quartered of the red and blue. The chrominance Db and Dr represent the difference to G from B and R respectively. After the color transform, the luminance Y and chrominance Db, Dr components are coded in parallel channels. In the pyramid structure, a multi-resolution image representation is built. Starting from

Figure 4 .

 4 Figure 4.1 -Scalable lossless coder

Figure 4 . 2 -

 42 Figure 4.2 -Construction of the upper level.

Figure 4 . 3 -

 43 Figure 4.3 -Hierarchical Diagonal S Transform, M d,l is the evaluation of the average in a block and used for upper level.

Figure 4 . 4 -

 44 Figure 4.4 -A median edge predictor.

Figure 4 . 5 -

 45 Figure 4.5 -Prediction for G 1,l .

Figure 4 . 6 -

 46 Figure 4.6 -Prediction for G 2,l .

  Marpe et al. [MC97] propose a partitioning, aggregation and conditional coding (PACC) based on the discrete wavelet transform. Further, they use an adaptive binary arithmetic coding to reduce the alphabet size of quantized transform coefficients [MSW03]. Instead of the arithmetic coding, LAR-LLC adopts the Huffman coding and focuses on the Entropy Pre-coding and Coding of Prediction Errors 103 arrangement of PD. The details are introduced here.

  .25) where 0 ≤ β ≤ 1. The length 4.25 has the minimum value N(H(A) -1) when α = 0.5. It is noticed that the required code length descends after the classification, and at most 1 bit is saved while N 1 equals to N 2 . The saved 1 bit indicates the reduction of the range of the sub alphabet of A 1 and A 2 compared to the alphabet of A. In order to reduce the alphabet set by the classification, one possible way is to separate errors according to their amplitude and separately encode them. This classification allocates the elements of the error sequence into sub-sequences. The subsequences should have the equal length.

4 4

 44 Coe ad jacent + 1 Coe upper

( 4 .

 4 26) In (4.26), Coe ad jacent is the average of adjacent available errors, Coe upper is the one from upper level. Their positions are shown in Fig. 4.7 . Entropy Pre-coding and Coding of Prediction Errors 105

Figure 4 . 8 -

 48 Figure 4.7 -Estimation for ȇl_apt (2i, 2 j).

Figure 4 . 9 -

 49 Figure 4.9 -Distributions of subsequences and original error sequence of G 1 on image "bike".

Figure 4 .

 4 Figure 4.10 -Test images.

Figure 4 .

 4 Figure 4.11 -Comparison of bitrates of color image codecs.

2 .

 2 By the use of the RDO model, the Mean Square Error (MSE) of the decoded image shows 117 Conclusion and Perspectives a nearly linear relationship with the quqp. Therefore, a linear model is proposed to describe this relationship. With this linear model, users can refrain the overall distortion of the decoded image to a target MSE by a choice of quqp. This part is introduced in Subsection 3.4.1.

Perspectives

  119

Section 4 .

 4 4 introduced a forward classification scheme in order to reduce the entropy of the prediction error stream. It also indicates that if the two subclasses have no intersections, and the same length, the average code length can reach H(A) -1. Therefore, the accuracy of the classification affects the final average code length. The proposed context model, shown in Fig.4.7 and Eq. (4.26), can differ the probability distribution of subclasses as shown in Fig.4.9.

  Glossary p(x) the probability of occurrence of the symbol x H(X) the entropy of the alphabet set X H(X|Y) the conditional entropy, the uncertainty of X when Y has been known DCT the Discrete Cosine Transform DWT the Discrete Wavelet Transform VLC the variable length coding T hr the threshold used for the Quadtree Partition I(x, y) the pixel of an image in the position (x, y) . rounding downward 1M the Image made of the mean value of the first diagonal by S transform 2G the Image made of the gradient value of the first diagonal by S transform 3M the Image made of the mean value of the second diagonal by S transform 3G the Image made of the gradient value of the second diagonal by S i, j) the pixel on the position (i,j) in the level l M 1,l the mean value of the first diagonal in the block of the level l G 1,l the gradient value of the first diagonal in the block of the level l M 2,l the mean value of the second diagonal in the block of the level l G 2,l the gradient value of the second diagonal in the block of the level l M d,l the mean value of the block in the level l G d,l the difference value of M 1,l and M 2,l in the level l Gd,l the predicted value of G d,l G1,l the predicted value of G 1,l G2,l the predicted value of G 2,l

  should guarantee that the decoder is able to identify the outcomes {X n } from the sequence of the codewords c x n . An example of VLC is introduced in the following.Table1.1 shows a alphabet {X} with four symbols {x n , 0 ≤ n ≤ 4} having different probabilities p x n . The entropy of the data formed by these symbols is

	2 0.1 011 001
	x 3 0.25 01	01
	x 4 0.6	1	1
	Table 1.1 -Variable length codes
	choice of codewords

Table 1 .

 1

						1 1
	. . .	. . .	. . .	. . .	. . .	. . .	. . .
	0	h i g k l m

2 -Structure of 16-bit numbers identical to the first m bits of the large file.

Table 1 .

 1 codec for JPEG-AIC Response

	43

4

-Bitrates (bpp) of lossless coding for color images modes. CALIC can save the most bitrates in lossless coding. For color images, JPEG2000 has the best coding efficiency among JPEG series. More results of the comparison between image coding methods will be provided in latter chapters.

1.5 LAR codec for JPEG-AIC Response

In 2008, JPEG Committee announced a Call for Advanced Image Coding (AIC) and evaluation methodologies [Lar08]. This call aims to : (1) Standardize potential technologies going beyond JPEG standards ; (2) Define guidelines for evaluation of coding technologies. The Image group of IETR laboratory proposed the LAR (Locally Adaptive Resolution) codec as a response of the Call of AIC for both natural images [BD09] and medical images [BD10].

The LAR (Locally Adaptive Resolution) method was initially proposed for the lossy image coding initially

[START_REF] Déforges | Color lar codec : A color image representation and compression scheme based on local resolution adjustment and self-extracting region representation[END_REF]

. Besides the image compression, it also provides functions such as resolution/quality scalability, lossy to lossless compression and region of interest (ROI) coding.

The LAR codec is based on the assumption that an image can be represented by a two-layer system : a Flat layer for the basic image information and a Texture layer for the detail information. The Flat layer is implemented by a Flat coder in LAR codec. It encodes the image at a low bitrate cost. The second layer is completed by texture coder which aims at quality improvement at medium/high bitrates. This structure offers a natural quality scalability.

Table 4 .

 4 2 gives the entropy reduction of the prediction error stream G1 of each

	LAR-LLC

Table 4 .

 4 2 shows that H class is less than H original and the reduction ratio is 5.72% in average.

Table 4 .

 4 3 shows the compression results of different codec solutions. The addition data indicates the ratio of bits per pixel (bpp) between codec solutions and JPEG2K used as reference.

	It is calculated in (4.30).
	Addition =	(bitrate of codec) -(bitrate of JPEG2K) bitrate of JPEG2K	(4.30)
	Besides, H sum is the summation of entropies from the luminance and chrominances. It is defined
	as (4.31).
	H sum = H(Y) + H(Db) + H(Dr)	(4.31)

H(Y) is the entropy of Y component introduced as the luminance Y, while H(Db) and H(Dr) are entropies of chrominances Db and Dr. H sum is used to represent the optimal code rate of the image if Y, Db and Dr components are directly coded respectively. According to the Table 4.3, Fig.4.11 gives the comparison of bitrates of coders. Based on the Table 4.3 and Fig.4.11, LAR-LLC keeps quite close to JPEG2K in compression ratio for LAR-LLC

Table 4 .

 4 3 -Bitrates (bits/pixel) of Lossless Color Image (24 bits/pixel) Codecs

		Image	H sum		JPEGXR JPEG2K JPEGLS	LJPEG	LCIC	LARLLC LARLLC
		bike		18.9574	12.7117	11.9620	13.4238 15.2339 11.9717	11.9980	12.6153
		tools		21.6405	17.7141	17.2953	16.8608 18.4419 17.4366	17.1031	17.6948
		boats		17.9918	10.2317	9.5897	9.8568	11.9158	9.1201	9.6360	10.3803
		flowers	19.4811	12.8349	11.0428	10.3861 12.0695 10.8445	11.0215	11.3957
		food		19.3113	8.8038	7.5938	7.3736	8.7659	7.4742	7.5773	7.8830
		woman	18.4163	12.1915	11.5022	13.7202 15.3821 11.5965	11.4827	12.0114
		woman2 20.4784	10.5590	9.9005	12.2876 13.5644	9.5871	9.9011	10.4169
		birthday 18.9132	10.0703	8.8880	10.2907 11.3325	8.9251	8.5474	8.7910
		boy		20.2896	8.4229	6.9459	8.2635	9.5655	6.7187	7.0269	7.2244
		cafe		20.9485	16.0008	15.5082	15.3658 17.9514 15.6295	15.5327	16.2929
		green	20.8334	16.7807	16.5124	16.6452 17.7940 16.6764	16.2514	16.5517
		cabin		20.7533	11.8518	11.3156	12.2742 14.3281 11.0487	11.3700	12.3011
		fall		17.2929	10.8843	9.4066	11.0843 13.0315	9.0087	9.4190	10.0468
		leaves	19.2470	14.4032	13.8618	9.6327	11.4100 14.4082	12.7797	13.0207
		building 18.0781	9.6831	8.4068	12.7103 13.7053	8.0496	8.4108	8.6159
		mount.	17.6862	8.6423	7.1561	9.1210	10.0601	7.2050	7.0910	7.2159
		Average 19.3949	11.9866	11.0555	11.8311 13.4095 10.9813	10.9468	11.4036
		Addition			8.42%	0%	7.02%	21.29%	-0.67%	-0.98%	3.15%
	LARLLC shows the results with the classification step ;
	LARLLC shows results without classification.
		20
		18
	Bitrate (bpp)	12 14 16
				JPEG XR
		10		JPEG 2K JPEG LS
				LJPEG
		8		LAR LLC H sum
				LCIC
		6	bike	tools	boats flowers food woman woman2 birthday	boy	cafe	green	cabin	fall	leaves building mountain
								Image

Rate-distortion-optimization (RDO) model for LAR codec

(a) "woman crop"

Coe ad jacent can be implemented by [Coe ad jacent -(Coe ad jacent >> 2)]. Besides, the binary search step makes the decision 2 times in order to choose the class for each residual error e. By the

Acknowledgments I would like to thank Prof. MOKRAOUI Anissa, Prof. DUFAUX Frédéric, Prof. PUECH William and Prof. LE MEUR Olivier for accepting to be members of the Ph.D. jury and taking time to read and review this manuscript. I would like to express my deep gratitude to my supervisor, Prof. Olivier Déforges, for Acknowledgments

LAR-LLC

The prediction error is coded by the Huffman coder. After coding the top level, the following work aims to recover higher resolution levels inside the pyramid. The transformed gradient coefficients are estimated by three predictors. In a classical "flat" prediction scheme, the already known (decoded) values that can be used are located before the current position. In a multi-layers prediction scheme such as the proposed one, partial decoded information is also available in the current position and following space. The different strategies implemented for the prediction of the three gradients are detailed in following. G denotes the predicted value of G. For image borders, predicted values are set to zero.

Prediction for G d,l

Let G d,l represent the contrast between M 1,l and M 2,l . In most cases, the mean values of the two diagonals are quite close, thus G d,l is generally close to zero. For the prediction to G d,l , available values are the mean value Y l+1 (i, j) of the each block and previously reconstructed G d,l . The prediction Gd,l is defined as (4.9) Gd,l (2i, 2 j) = α 4 G d,l (2i -2, 2 j -2) + G d,l (2i + 2, 2 j -2)

-Y l+1 (i -1, j + 1) -Y l+1 (i + 1, j -1) (4.9)

In one block, M 1,l and M 2,l often have closed values, which leads to a small amplitude of G d,l .

Thus, coefficients are relatively small in order to respect the low amplitude feature of G d,l . After a learning stage over a large set of images, the weights are set with α = 0.3, β = 0.035. Once G d,l decoded, M 1,l and M 2,l are computed by the inverse transform (4.10). Their mean values M 1,l and M 2,l are available. G 1,l (2i, 2 j) is represented by [X l (2i, 2 j) -X l (2i + 1, 2 j + 1)]. To evaluate G 1,l (2i, 2 j), we consider six pairs of pixels with the same direction around G 1,l (2i, 2 j), and assume that they have an equivalent contribution. The difference of the JPEG2K for "bike", "boats", "woman2", "boy", "cabin", "fall" and "building", although LAR-LLC is not as efficient as JPEG2K, it achieves very closed bitrates to those of the standard JPEG2K. For images "birthday" and "green", LAR-LLC has the salient better coding results compared to other solutions. The reason probably relies on the directional texture parts which appear on the shirt in "birthday" and the grass in "green". JPEGLS shows obvious fluctuations for the compression ratio. For example, It obtains a superior coding gain for the image "leaves", whereas suffers more than 3 bpp compared with JPEG2K and LAR-LLC for the image "building". JPEGXR reaches close results to JPEG2K for lossy coding [DSOD + 07], but not exceeds JPEG2K for the lossless coding as shown in Table 4.3.

Besides, Table 4.3 provides the coding bitrates of the LAR-LLC solution without the classification step. This solution is named LAR-LLC in the table. For each image, LAR-LLC costs more bpp than the one of LAR-LLC. Its average bitrate is also higher than that of JPEG2K by 3.15%. Consequently, it is concluded that the classification step is beneficial for the compression efficiency.

Compared with the latest non-standard method LCIC, LAR-LLC also has the equivalent compression efficiency. Indeed, the coding ratio is relevant with the tested images. Such as the image "leaves", JPEGLS and LJPEG perform well on it, but they cost much for the average bitrate. According to the Table 4.3, we can argue that LAR-LLC has an equivalent lossless coding ratio with the one of JPEG2K, is as efficient as the non-standard color coding method, such as the LCIC.

Computation Complexity

Measuring the complexity of coding method is a hard issue. The execution times of their implementations are dependent on the codec language, the execution environment and so on.

Commercial solutions are often implemented by assembly languages and Single Instruction, Multiple Data (SIMD). They are platform dependent and fast. In our tests, the parallel technique is not used. All the executable programs are compiled from the plain C/C++ language and run in the same environment as shown in table 4.5. For the LCIC, the executable software is available, but it needs much more time to complete the encoding and decoding. We notice that the LCIC website also provides a version of the Jasper (JPEG2K reference solution) [KC]. This version of Jasper costs the time which is about 2 times more than the one of the jasper version implemented from [Ada] in our platform. Thus, it is possible that the authors of [START_REF] Kim | Hierarchical prediction and context adaptive coding for lossless color image compression[END_REF] may upload the debug version of LCIC, or release it in a rather different platform from the ours. For the fairness, the LCIC is not put into this test section. However, as described in [START_REF] Kim | Hierarchical prediction and context adaptive coding for lossless color image compression[END_REF], the LCIC requires more coding time than the one of JPEG2K. In order to compare the computation complexity of codecs, the processing speeds are presented in the According to the average data in the Table 4.6, JPEGLS provides the least encoding latency and runs more than 3 times faster than JPEG2K. For JPEGXR, the implementation [ITU] is faster than JPEG2K by 49.38%. This method shows an advantage on the lossless coding of the luminance component in the test in [START_REF] Zhao | Local structure learning and prediction for efficient lossless image compression[END_REF]. However, as noted in [START_REF] Zhao | Local structure learning and prediction for efficient lossless image compression[END_REF], one drawback of this method is its computational complexity. It applies a structure prediction scheme which is quite computational expensive.

In

Abstract

This doctoral research project aims at designing an improved solution of the still image codec called LAR (Locally Adaptive Resolution) for both compression performance and complexity. Several image compression standards have been well proposed and used in the multimedia applications, but the research does not stop the progress for the higher coding quality and/or lower coding consumption. JPEG was standardized twenty years ago, while it is still a widely used compression format today. With a better coding efficiency, the application of the JPEG 2000 is limited by its larger computation cost than the JPEG one. In 2008, the JPEG Committee announced a Call for Advanced Image Coding (AIC). This call aims to standardize potential technologies going beyond existing JPEG standards. The LAR codec was proposed as one response to this call. The LAR framework tends to associate the compression efficiency and the content-based representation. It supports both lossy and lossless coding under the same structure. However, at the beginning of this study, the LAR codec did not implement the ratedistortion-optimization (RDO). This shortage was detrimental for LAR during the AIC evaluation step. Thus, in this work, it is first to characterize the impact of the main parameters of the codec on the compression efficiency, next to construct the RDO models to configure parameters of LAR for achieving optimal or sub-optimal coding efficiencies. Further, based on the RDO models, a "quality constraint" method is introduced to encode the image at a given target MSE/PSNR. The accuracy of the proposed technique, estimated by the ratio between the error variance and the set-point, is about 10%. Besides, the subjective quality measurement is taken into consideration and the RDO models are locally applied in the image rather than globally.

The perceptual quality is improved with a significant gain measured by the objective quality metric SSIM (structural similarity).

Aiming at a low complexity and efficient image codec, a new coding scheme is also proposed in lossless mode under the LAR framework. In this context, all the coding steps are changed for a better final compression ratio. A new classification module is also introduced to decrease the entropy of the prediction errors. Experiments show that this lossless codec achieves the equivalent compression ratio to JPEG 2000, while saving 76% of the time consumption in average in encoding and decoding.

Résumé

Abstract

This doctoral research project aims at designing an improved solution of the still image codec called LAR (Locally Adaptive Resolution) for both compression performance and complexity. Several image compression standards have been well proposed and used in the multimedia applications, but the research does not stop the progress for the higher coding quality and/or lower coding consumption. JPEG was standardized twenty years ago, while it is still a widely used compression format today. With a better coding efficiency, the application of the JPEG 2000 is limited by its larger computation cost than the JPEG one. In 2008, the JPEG Committee announced a Call for Advanced Image Coding (AIC). This call aims to standardize potential technologies going beyond existing JPEG standards. The LAR codec was proposed as one response to this call. The LAR framework tends to associate the compression efficiency and the content-based representation. It supports both lossy and lossless coding under the same structure. However, at the beginning of this study, the LAR codec did not implement the rate-distortion-optimization (RDO). This shortage was detrimental for LAR during the AIC evaluation step. Thus, in this work, it is first to characterize the impact of the main parameters of the codec on the compression efficiency, next to construct the RDO models to configure parameters of LAR for achieving optimal or sub-optimal coding efficiencies. Further, based on the RDO models, a "quality constraint" method is introduced to encode the image at a given target MSE/PSNR. The accuracy of the proposed technique, estimated by the ratio between the error variance and the setpoint, is about 10%. Besides, the subjective quality measurement is taken into consideration and the RDO models are locally applied in the image rather than globally. The perceptual quality is improved with a significant gain measured by the objective quality metric SSIM (structural similarity).

Aiming at a low complexity and efficient image codec, a new coding scheme is also proposed in lossless mode under the LAR framework. In this context, all the coding steps are changed for a better final compression ratio. A new classification module is also introduced to decrease the entropy of the prediction errors. Experiments show that this lossless codec achieves the equivalent compression ratio to JPEG 2000, while saving 76% of the time consumption in average in encoding and decoding.