T.I.P.E : La compression JPEG

FLIEDEL Romain

10 mars 2005

La norme J.P.E.G. (Joint Photographic Experts Groups) permet de compresser des images au formatRGB en images de taille beaucoup moins importante mais dont la qualite n’est que peu affectee. Ceci estparticulierement important en ce qui concerne la transmission d’images par Internet et dans le stockagedes donnees. Cette compression est donc essentielle afin de reduite les couts et les ressources de stockage.Ainsi grace au sacrifice de certaines informations (partie destructive de la compression) et en introduisantvolontairement des ”erreurs” dans l’image, on peut transmettre et stocker d’avantage d’information.

Nous nous interesseront dans un premier temps a une presentation de la methode de compression puisdans le theme erreur et progres nous etudierons l’iteration du procede de compression - decompressionen nous limitant aux etapes destructives du procede.

1

1 Presentation du procede de compression

1.1 L’algorithme JPEG

Le procede JPEG va donc chercher a minimiser le volume de donnees en supprimant certaines infor-mations de l’image. Cette compression s’effectue selon le procede decrit ci-dessous :

Fig. 1 – Principales etapes de l’algorithme de compression JPEG (Les etapes destructives sont representees sur fond gris)

La decompression s’effectue alors selon les etapes suivantes :

Fig. 2 – Principales etapes de l’algorithme de decompression JPEG

1.2 Le passage des composantes RGB en composantes Y,Cb, Cr

Les images sont des ensembles de points elementaires (pixels) colores. Pour les images en 16 millionsde couleurs on peut definir la couleur par un triplet (r,g,b) de composantes Rouge, Vert, Bleu chaquecomposante variant de 0 a 255 (cf : Figure 1). C’est ce type de codage de couleur qui est utilise dans leformat BMP (Bitmap). Pour chaque point de l’image on stocke un triplet definissant la couleur du pixelce qui produit un volume de donnee tres important mais une definition optimale de l’image.

Fig. 3 – Couleurs pour r=125 et g,b variant de 0 a 255

2

Exemple de codage d’une image en RGB :

Fig. 4 – Image de depart

Fig. 5 – Composante Rouge Fig. 6 – Composante Verte Fig. 7 – Composante Bleue

Un autre type de codage est utilise dans l’algorithme JPEG, c’est le codage de couleur Y CbCr.Les trois composantes alors utilisees sont respectivement la luminance (Y), et deux composantes dechrominance : Bleu (Cb) et Rouge (Cr).

Fig. 8 – Couleurs pour Y=128 et Cb,Cr variantde -227 a 227

Fig. 9 – Variation de la luminance pour Cb,Cr

nuls

Exemple de codage d’une image en Y CbCr :

3

Fig. 10 – Image de depart

Fig. 11 – Composante de Lu-minance

Fig. 12 – Composante de Chro-minance Bleue

Fig. 13 – Composante de Chro-minance Rouge

On voit bien sur ces exemples que l’oeil humain est beaucoup plus sensible a la luminance qu’ala chrominance. C’est pourquoi on va convertir l’image BMP, encodee dans le systeme RGB, en uneimage au format Y CbCr. On traitera alors separement la luminance des composantes de chrominance.La conversion du systeme RGB vers Y CbCr se fait selon les formules suivantes.

YCb

Cr

=

0.2220 0.7067 0.0713−0.1195 −0.3810 0.5

0.5 −0.4542 −0.0458

RGB

Cette transformation des composantes RGB en composantes Y,Cb, Cr est bijective et il est tres simplede repasser en RGB en inversant la matrice de conversion :

RGB

=

1 0 1.55601 −0.1866 −0.488861 1.8580 0.0001

YCb

Cr

Cette etape n’engendre donc pas de pertes en theorie, mais nous verrons dans la partie programmationqu’en realite il y a quand meme des pertes dues au calcul sur les entiers.

1.3 Le downsample (sous echantillonnage)

Comme on a vu que les informations de chrominance etaient moins importantes que celles de lu-minance on va reduire par 4 le volume d’informations de chrominance. Pour cela on va decouper lescomposantes de luminance en blocs de 16*16 puis les reduire a des blocs de 8*8 selon le procede suivant :Pour chaque sous bloc de 2*2 on fait la moyenne des valeurs et on ne garde que la moyenne.Ex (on a reduit l’exemple a une matrice 8*8 transformee en 4*4 pour des raisons de lisibilite) :

4

140 144 147 140 140 155 179 175144 152 140 147 140 148 167 179152 155 136 167 163 162 152 172168 145 156 160 152 155 136 160162 148 156 148 140 136 147 162147 167 140 155 155 140 136 162136 156 123 167 162 144 140 147148 155 136 155 152 147 147 136

⇒145 143 145 175155 154 158 155156 149 142 151148 145 151 142

La difference n’est que peu perceptible compte tenu de la faible taille d’un carre de 2*2 pixels.

1.4 D.C.T (Discrete Cosinus Transformation)

Pour cette etape on a deja obtenu des blocs de 8*8 pour la chrominance, on decoupe alors la matricede luminance en blocs de 8*8 afin de pouvoir appliquer la DCT.

La DCT consiste a faire une decomposition frequentielle de l’image vue en tant que triplets de com-posantes spatiales Y ,Cb,Cr dependant de x,y (enplacement dans l’image). On peut alors decider d’aban-donner un certain nombre de frequences pour ne garder que la composante continue et les principalesharmoniques.

Si A = (aij) represente un bloc de l’image originale, et B = (bij) le bloc correspondant dans l’imagetransformee. On a deux matrices de taille 8x8.

La transformee cosinus discrete s’ecrit alors :

bij =14cicj

∑

0≤l≤7

∑

0≤k≤7

cos(2k + 1)iπ

16cos

(2l + 1)jπ16

akl

avec ci = 1√2

pour i = 0 et ci = 1 pour i 6= 0.On peut aussi considerer cette transformation matriciellement en considerant : B = P−1AP ou

P = (pi,j) est la matrice de passage du domaine spatial au domaine frequentiel avec :

pi,j = ci

√14

cos(2i + 1)jπ

16

De plus P est une matrice orthogonale donc P−1 =t P , ce qui permet de l’inverser rapidement pourobtenir la transformee inverse : l’iDCT (inverse Discret Cosinus Transformation).

L’interet de la D.C.T est principalement d’isoler les informations essentielles a l’image et de pouvoirsupprimer des details qui ne sont que peux perceptibles. Les basses frequences sont situees en haut agauche dans la matrice et les hautes frequences en bas a droite.

Les motifs elementaires correspondants aux differentes frequences sont les suivants :

Fig. 14 – Les motifs de base d’une image

5

1.5 La quantification

Une fois qu’on a applique la DCT on peut negliger les hautes frequences. Afin de controler la pertede qualite de l’image on va definir un facteur de qualite Fq. Avec ce coefficient on va creer une matricede quantification Q = (qi,j) definie par la relation suivante : (qi,j) = 1 + (i + j) ∗ Fq. Une fois cettematrice definie on va proceder a la quantification en elle meme. Cette operation consiste a diviser chaquecoefficient ai,j de la matrice DCT par le coefficient de la matrice de quantification associe qi,j . Lescoefficients de la matrice de quantification ont etes choisis de sorte que le coefficient par lequel on vadiviser le coefficient associe dans la matrice DCT, soit d’autant plus grand que la frequence est elevee.

Exemple :Matrice de quantification pour Fq = 5

6 11 16 21 26 31 36 4111 16 21 26 31 36 41 4616 21 26 31 36 41 46 5121 26 31 36 41 46 51 5626 31 36 41 46 51 56 6131 36 41 46 51 56 61 6636 41 46 51 56 61 66 7141 46 51 56 61 66 71 76

Quantification de la matrice :

1758 54 6 -1 -13 -5 23 -119 -15 -9 -16 27 31 -32 1-8 7 8 -15 -16 3 -67 -40-30 4 44 -36 14 -73 20 -420 2 -23 -10 -16 -16 -8 72 8 -12 17 -16 -21 -40 36

-14 45 -49 -20 -31 29 41 51-1 -66 1 20 -4 -31 -2 -31

⇒

293 4 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 -1 0-1 0 1 -1 0 -1 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 1 -1 0 0 0 0 00 -1 0 0 0 0 0 0

On obtient a par cette operation elimine les hautes frequences non primordiales dans l’image d’oul’apparition de nombreux zeros en bas a droite.

1.6 Linearisation des matrices

Une fois qu’on a quantifie la matrice DCT, on va la lineariser en la parcourant en zig-zag afin d’obtenirun maximum de zeros a la fin de la sequence.

Fig. 15 – Les motifs de base d’une image

6

Ex : La linearisation de la matrice suivante donne la sequence :

293 4 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 -1 0-1 0 1 -1 0 -1 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 1 -1 0 0 0 0 00 -1 0 0 0 0 0 0

[293 ; 0 ; 4 ;0 ; 0 ; 0 ; -1 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 1 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; -1 ; 0 ; 0 ; 0 ; 0 ; 1 ; 0 ; 0 ; 0 ;0 ; 0 ; 0 ; 0 ; -1 ; -1 ; 0 ; 0 ; -1 ; -1 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0]

1.7 Le codage R.L.E (Run Length Encoding )

La methode de compression RLE aussi connue sous le nom de RLC (Run Length Coding) est assezfacile mettre en place et permet d’obtenir de bons resultats sans necessiter beaucoup de ressources. Leprincipe de cette methode est de remplacer n repetitions d’un motif par le couple (n,motif). D’aprescette definition on constate que cette methode n’entraıne pas de pertes car on peut reconstituer lefichier original d’apres ces couples. Cette methode ce revele efficace uniquement pour des fichiers dontla probabilite de repetition de chaque motif est elevee. En effet coder un texte grace cette methoden’est pas tres efficace compte tenu du faible taux de repetition. Par contre pour des fichiers binairesou hexadecimaux, le faible nombre de codes utilises pour coder un fichier augmente la probabilite derepetition. Dans le cadre de la compression JPEG cette methode est utilisee apres linearisation desmatrices DCT. Comme la sequence obtenue se termine par un nombre important de zeros on va remplacercette suite de zeros par le nombre de zeros ce qui raccourci considerablement la sequence.

1.8 Le Codage Huffman

Le codage Huffman est une methode de compression statistique. Elle vise a associer chaque ca-ractere d’une image (triplet Y,Cb, Cr ) une sequence binaire de longueur inversement proportionnelle ala frequence d’apparition du caractere. Pour cela on construit recursivement un arbre binaire selon leprocede suivant : On cherche les deux caractere ayant la plus faible frequence d’apparition, on en fait unarbre dont le noeud est etiquete de la frequence obtenue en sommant les deux frequences les plus faibles.On procede de cette maniere jusqu’a ce que l’arbre soit totalement construit avec une racine de frequence1. On attribue a chaque caractere (Feuille de l’arbre) la sequence binaire obtenue en parcourant l’arbreet en ajoutant un 1 a la sequence si on prend la branche dont le noeud a la plus petite etiquette et un0 si on prend la branche dont le noeud a la plus grande etiquette. On obtient avec cette methode dessequences uniques et aucune sequence n’est prefixe d’une autre ce qui leve toute ambiguıte lors de lalecture du fichier compresse.

7

Exemple : pour un ensemble de caractere (A, B,C, D, E, F ) avec les frequences

Caractere A B C D E FFrequence 0,02 0.4 0.02 0.3 0.01 0.25

Fig. 16 – Exemple du codage Huffman (le chemin en bleu est celui donnant la sequence correspondant au C)

On obtient donc sur cet exemple les sequences suivantes :

Caractere A B C D E FSequence Binaire 11011 0 1100 10 11010 111

L’inconvenient majeur de ce codage est la necessite d’une bibliotheque donc, si la compression estsatisfaisante (50% en moyenne) et la decompression rapide, la taille du fichier compresse est parfoisplus grande que celle du fichier initial a cause de la bibliotheque. De plus la perte d’un bit entraıne ladestruction de la sequence et rend donc le fichier inutilisable.

2 Programmation en CamL de l’algorithme de compression JPEG

2.1 Presentations d’elements de code

2.2 Exemples de compressions

3 Etude de l’iteration

3.1 Etude Theorique

3.2 Resultats experimentaux

4 Conclusion

8