COMPRESSION - analyse du projet JPEG

La compression du format JPEG

La compression du format JPEG est intéressante à étudier puisque elle est en fait composée de plusieurs types de compression utilisés pour certains par d'autres formats d'images numériques et de fichiers en général. On distingue huit grandes étapes pour aboutir à une image compressée de format JPEG :

Le format BMP

Le format BMP est un des formats les plus simples développé conjointement par Microsoft et IBM, ce qui explique qu'il soit particulièrement répandu sur les plates formes Windows et OS/2. Un fichier BMP est un fichier bitmap, c'est-à-dire un fichier d'image graphique stockant les pixels sous forme de tableau de points et gérant les couleurs soit en couleur vraie soit grâce à une palette indexée.

  • La structure d'un fichier bitmap est la suivante :
  • Entête du fichier (en anglais file header)
  • Entête du bitmap (en anglais bitmap information header)
  • Palette (optionnellement)
  • Corps de l’image.

 

Le découpage de l'image

La première étape est le découpage de l'image de la matrice en bloc de 8 par 8 pixels. La compression JPEG n'a lieu que dans ces matrices. Si la taille de l'image fait qu'il reste certains pixels au bord ne pouvant pas former une matrice, ces pixels seront compressés autrement.

Le passage de RVB à YCbCr

Chaque pixel d’une l'image en couleur est caractérisé par trois valeurs : sa composante de rouge, sa composante de vert et sa composante de bleu, entre 0 et 255. Le mélange de ces trois couleurs permet d'obtenir la couleur RVB du pixel. La couleur peut aussi être déterminée par sa luminance et sa chrominance. On a toujours 3 valeurs qui caractérise la couleur du pixel : une valeur de luminance (Y) et deux valeurs de chrominance (Cb = Saturation, Cr = Teinte). On peut facilement passer du mode RVB au mode YCbCr en utilisant les formules suivantes :

Y = 0.299R + 0.587V + 0.114B

Cb = -0.1687R - 0.3313V + 0.5B + 128

Cr = 0.5R - 0.41874V - 0.0813B + 128

On peut revenir au mode RVB avec ces formules :

R = Y + 1.402 ´ (Cr - 128)

V = Y - 0.34414 ´ (Cb - 128) - 0.71414 ´ (Cr - 128)

B = Y + 1.777 ´ (Cb - 128)

Les valeurs permettant de passer d'un mode à l'autre ont été déterminées par des expériences de physique ; Les mesures ont été effectuées par des récepteurs photoélectriques. Ces coefficients ont été normalisés en supposant que le valeur maximal 255 est la luminance du blanc. Les deux valeurs de chrominance sont elles aussi comprises entre 0 et 255. L'intérêt de ce changement est mis en valeur lors de l'étape suivante.

On applique les procédés qui suivent à chacun des trois plans Y, Cb et Cr. Dans le cas d’une image en niveaux de gris, il n’y a qu’un plan de valeurs Y.

Nous ilustrons chacune des étapes par un exemple simple. Prenons l’exemple d’une image BMP de taille 8x8, échelle true color ou RVB.

Cette image ne possèdent que trois couleur dont les valeur RVB sont les suivantes :

Première couleur : R=15 V=15 B=15

Deuxième couleur : R=150 V=150 B=150

Troisième couleur : R=200 V=200 B=200

Nous pouvons donc calculer les valeurs Y, Cb, Cr :

Première couleur : Y=15, Cb=128, Cr=128.

Deuxième couleur : Y=150, Cb=128, Cr=128.

Troisième couleur : Y=200, Cr=128, Cr=128.


Le lissage

Durant cette étape, la matrice 8x8 est redécoupée en matrices 2x2. Dans chacun des blocs de quatre pixels ainsi formés, la valeur de chrominance (Cb et Cr) est remplacée par la valeur moyenne de la chrominance des quatre pixels. La valeur de départ du pixel est alors perdue. Toutefois la perte n'est pas très importante. En effet, l'œil est très sensible a la luminance, mais très peu a la chrominance. Ainsi malgré le changement de valeur, l'œil n'en perçoit rien ou quasiment rien. Par contre le changement est très intéressant pour l'étape suivante : la DCT. En effet, dans le bloc de quatre pixels, au lieu d'effectuer quatre calculs pour chaque valeur de chrominance, il suffit d'en faire un seul et d'utiliser ce résultat pour les quatre pixels.

Matrice originelle 8*8: Les valeurs correspondent a une valeur de chrominance

102

153

76

121

Matrice redécoupé 8*8: (102 + 153 + 76 + 121) / 4 = 113 Les valeurs sont remplacées par la moyenne.

113

113

113

113

 

La DCT

La DCT (= Discret Cosinus Transform = Transformée en Cosinus Discrète) est une dérivée des transformées de Fourier. Elle transforme la matrice 8x8 en une autre matrice 8x8, dont les valeurs sont rangées selon leur fréquence. La valeur de coordonnées (0 ; 0) correspond à la valeur moyenne des points. Les autres valeurs de la matrice correspondent à l'éloignement du point par rapport a la moyenne. Les valeurs sont rangées dans la matrice (grâce à la DCT) d'après leur fréquence : les basses fréquences sont situés en haut a gauche et les basses fréquences en bas a droite. Les basses fréquences sont les plus importantes pour l'image, tandis que les hautes fréquences sont moins importantes. Cette étape a pour but de préparer la matrice a l'étape suivante : la quantification, durant laquelle l'image subira le plus de perte. La DCT est l'étape caractéristique du format JPEG, elle est propre à ce format et c'est autour de cette étape que tourne tout le fonctionnement de la compression au format JPEG.


La quantification

La quantification est la seconde phase non conservatrice du processus de compression, c'est à dire que c'est ici que l'on va principalement perdre en qualité pour gagner en compression. Sa tâche est donc de réduire la mémoire nécessaire au stockage. Pour cela, on réduit chaque valeur de la matrice DCT en la divisant par un nombre (appelé quantum) fixé par une table de quantification (qui est en fait une matrice 8x8). Cette table est variable, selon le pas de quantification.

Matrice de quantification avec pas de 2

3

5

7

9

11

13

15

17

5

7

9

11

13

15

17

19

7

9

11

13

15

17

19

21

9

11

13

15

17

19

21

23

11

13

15

17

19

21

23

25

13

15

17

19

21

23

25

27

15

17

19

21

23

25

27

29

17

19

21

23

25

27

29

31

Matrice de quantification avec pas de 5

6

11

16

21

26

31

36

41

11

16

21

26

31

36

41

46

16

21

26

31

36

41

46

51

21

26

31

36

41

46

51

56

26

31

36

41

46

51

56

61

31

36

41

46

51

56

61

66

36

41

46

51

56

61

66

71

41

46

51

56

61

66

71

76

Généralement, les logiciels de dessin proposant une compression JPEG offrent la possibilité de choisir le pas de quantification (alias facteur de compression). Ce pas est compris entre 1 et 100.


La linéarisation

La linéarisation consiste à lire la matrice quantifiée en zigzag pour créer une suite de valeurs proches car le quantum est le même pour chaque case d'une diagonale de la matrice. On aura donc le plus de chance d'obtenir des suites de nombres identiques, ce qui sera très facilement compressible à l'étape suivante avec une compression RLE.