Retour au siteretour à la liste des cours

L’algorithme JPEG

Cet article a pour but de présenter le fonctionnement de l'algorithme JPEG, qui est un algorithme de compression : il transforme une image de manière à lui faire prendre moins de place, quitte à perdre en qualité. Les logiciels de retouche classiques l’exécutent quand vous lui demandez d'enregistrer une image au format JPEG. Voici un exemple d'image compressée avec cet algorithme :

chat chat

Représentation des couleurs

Bien que l'on ne le remarque pas en regardant une image (de bonne qualité), une image est composée de milliers de petits carrés, les pixels. On peut les observer en zoomant sur l'oeil du chat :

oeil chat zoom

Tous ces petits carrés possèdent soit une couleur uniforme soit un dégradé entre deux couleurs. Pour décrire une image, il suffit donc de donner la couleur de chacun de ces pixels : en coloriant chaque carré de la bonne couleur, on retrouve l'image de départ.

Mais encore faut-il se mettre d'accord sur la façon de représenter les couleurs. Il existe différentes façons de le faire, mais la plupart utilisent 3 (ou 4) nombres compris entre 0 et 255.

RGB

Ici, on décrit une couleur par la proportion de rouge (R), de vert (G) et de bleu (B) qu'elle contient. Ce système repose sur le fonctionnement de l’œil : sur la rétine, différents types de cellules nerveuses (les cônes) s'activent lorsqu'elles sont frappées par un rayon lumineux d'une certaine couleur (rouge, vert, bleu).
Mais que ce passe-t-il lorsqu'une de ces cellules est frappée par un rayon jaune ? Puisque les cellules sont sensibles à une couleur précise, nous ne devrions pas être capables de voir autre chose que les 3 couleurs primaires !
Heureusement, les cônes ne sont pas activés par une unique couleur (c'est-à-dire une unique longueur d'onde), mais par toute une plage. Ainsi quand l’œil reçoit un rayon jaune, les 3 cônes s'activent plus ou moins, et le cerveau interprète ceci comme du jaune.
Là où ça devient intéressant, c'est que le cerveau aurait réagit de la même manière si on avait envoyé un peu de rouge et un peu de vert sur l’œil (ce que n'a rien à voir avec un rayon jaune pur).
Ainsi, pour l’œil humain, jaune = rouge + vert.

De manière générale, toute les couleurs perçues par l’œil peuvent être décrites comme ceci. On en déduit les 3 nombres (R,G,B) : le rouge est (255,0,0) car il ne contient que du rouge, le noir est (0,0,0), le jaune est (255,255,0), le blanc est (255,255,255) car il contient « toutes les couleurs ».

Ce système est utilisé dans les images BMP (bitmap). On mémorise la couleur correspondant à un pixel en écrivant successivement les 3 nombres dans le modèle RGB.

YCbCr

images en ycbcrMais l’œil ne contient pas que des bâtonnets. On y trouve aussi des cônes, qui sont plus sensibles à la luminosité du rayon lumineux, et moins à sa couleur. Il se trouve que les cônes, bien que moins nombreux, sont plus sensibles que les bâtonnets. L’œil remarque donc plus facilement les variations de luminosité que les variations de couleur.
Il est donc judicieux de séparer l'information de luminosité et l'information de couleur. C'est ce qui est fait dans le modèle YcbCr : le Y correspond à l'image en niveaux de gris, et les deux autres nombres Cb et Cr (chrominance bleue et chrominance rouge) permettent de reconstituer la couleur.

Ci-contre, la décomposition d'une image en 3 composantes (source wikipédia).

Ce type de modèle a été mis au point au moment du passage à la télé couleur : les anciens écrans se contentaient de la première valeur (Y) pour afficher l'image en noir et blanc alors que les nouveaux utilisaient les 3 composantes.

C'est celui qui est utilisé dans l'algorithme JPEG, on va voir pourquoi dans la suite.

Sous-échantillonnage de la chrominance

On va donc représenter une image en utilisant 3 tableaux, un par composante, par exemple :

Y
141 150 143 147
142 150 147 144
140 139 143 145
138 145 150 148
Cb
170 172 174 179
169 170 168 179
169 171 173 175
171 172 170 170
Cr
85 84 79 83
84 80 82 86
82 89 85 84
82 87 86 83

Mais comme l’œil est moins sensible aux variations de chrominance, il ne sert à rien de garder autant de valeurs sur les deux derniers tableaux !

En faisant la moyenne sur chaque bloc de deux pixels de côté, on obtient les nouveaux tableaux (le Y n'est pas modifié) :

Y
141 150 143 147
142 150 147 144
140 139 143 145
138 145 150 148
Cb
170 170 175 175
170 170 175 175
171 171 172 172
171 171 172 172
Cr
83 83 83 83
83 83 83 83
85 85 85 85
85 85 85 85

On ne garde qu'une seule valeur sur les 4 identiques :

Y
141 150 143 147
142 150 147 144
140 139 143 145
138 145 150 148
Cb
170 175
171 172
Cr
83 83
85 85

En effectuant cette opération relativement simple, on a déjà divisé par 4 la taille des données de chrominance à compresser.
Il existe différentes variantes de ce système, car il est possible de ne faire la moyenne que sur des blocs de taille 1x2, 2x1, ou 1x1 (ce qui revient à ne rien faire).

La transformée en cosinus discrète

Tout d'abord n'ayez pas peur de ce nom barbare, je vais tout vous expliquer !

Le principe

un signal creneau

Que se passe-t-il si l'on essaie d'approcher ce signal en utilisant des cosinus ? (pour rappel, un cosinus, c'est ça :

un signal cosinus

Eh bien le cosinus qui s'approche le mieux du signal est celui-ci :

un signal creneau + cosinus

C'est mieux, mais c'est toujours pas terrible. Par contre, si on rajoute encore d'autres cosinus, disons 8, qui oscillent de plus en plus rapidement, le signal carré est bien mieux approché :

un signal creneau + cosinus

Il faudrait en fait sommer une infinité de cosinus pour avoir exactement le signal carré (en dehors des points dits de discontinuité où il y a basculement).
Dans le cas des signaux périodiques comme celui-ci (avec un motif qui se répète), on dit que l'on fait la décomposition en séries de Fourier du signal.
Mais le même type de décomposition existe pour des signaux non périodiques comme celui-ci :

un signal gaussienne

On parle alors de transformée de Fourier.
Mais ce qui nous intéresse ici, c'est le cas des signaux 2D, comme celui-ci :

un signal gaussienne

Pourquoi ? Parce que ce genre de signal représente une image ! Imaginez que l'altitude d'un point sur la surface correspond à la valeur d'un pixel. Par exemple, souvenez-vous de l’image du chat au début : si on zoom, on voit que certains pixels sont des dégradés. Cela correspond à une fonction comme celle là :

un signal d’un seul pixel

Ce type de surface peut également se décomposer en une somme de cosinus et sinus, qui vont devoir osciller dans les deux directions :

un signal gaussienne

Pour réduire le temps de calcul, il vaut mieux travailler sur des petits blocs. Les trois tableaux de valeurs Y, Cb et Cr sont découpés en petits carrés de 8x8 pixels. On écrit ensuite dans un nouveau tableau, lui aussi de taille 8, les amplitudes de chacun des cosinus composant le signal. Ils sont classés en faisant apparaître les hautes fréquences vers le coin inférieur droit du tableau.

un signal gaussienne

Mais nous ne sommes pas au bout de nos peines. Il faut encore s'occuper des valeurs que l'on vient d'obtenir.

Quantification

On va maintenant supprimer les hautes fréquences, en espérant que l’œil ne voie pas trop la différence. Le bloc précédent est organisé de telle sorte que les valeurs correspondant aux hautes fréquences sont toutes regroupées en bas à droite de chaque bloc 8x8. Pour les supprimer, il faut utiliser un autre tableau, que l'on appelle matrice de quantification.

Exemple de matrice de quantification
5 9 13 17 21 25 29 33
9 13 17 21 25 29 33 37
13 17 21 25 29 33 37 41
17 21 25 29 33 37 41 45
21 25 29 33 37 41 45 49
25 29 33 37 41 45 49 53
29 33 37 41 45 49 53 57
33 37 41 45 49 53 57 61

Chaque amplitude est divisée par le nombre correspondant dans le tableau. Par exemple, la valeur moyenne est divisée par 5, et l'amplitude associée à la plus haute fréquence est divisée par 61.

On voit que les amplitudes en bas à droite vont être divisées par des coefficients beaucoup plus grands. En arrondissant à l'entier le plus proche, elles seront probablement ramenées à 0. C'est à ce moment que l'on perd en qualité. En effet, pour retrouver l'amplitude de départ, il suffit de multiplier par le coefficient dans la matrice de quantification (aux arrondis près). Sauf pour 0 ! On aura beau multiplier par ce qu'on veut, on aura toujours 0, donc ces valeurs sont perdues, et l'image affichée lors de la décompression ne sera pas exactement la même.

C'est aussi pour cette raison que des blocs apparaissent sur une image fortement compressée, car lors de la suppression des hautes fréquences les transitions entre les blocs deviennent moins douces.

zoom sur les blocs dans un jpeg

Parcours en zigzag

Les 64 valeurs de chaque bloc sont écrites à la suite, selon un parcours en zigzag :

écriture en zigzag

Les basses fréquences sont donc lues en premier (rappelez-vous, elles sont en haut à gauche du bloc), puis viennent les hautes fréquences. Ce type de parcours se termine par une grande suite de 0 car les valeurs correspondant aux hautes fréquences ont été supprimées. Il ne reste donc que quelques nombres, par exemple (85, -5, 10, 0, 4, -2). Tous les autres sont nuls, on peut les oublier. Ces 6 nombres décrivent presque entièrement un bloc de 64 valeurs !

Dans certains cas, on pourrait obtenir un résultat plus long, comme (85, -5, 10, 0, 4, -2, 0, 0, 0, 0, 0, 0, 6, 2, 1). C'est problématique, puisqu'il faut garder les six 0 du milieu, qui prennent beaucoup trop de place.
Un algorithme permet de raccourcir cette suite de nombres : il remplace (0,0,0,0,0,0) par (six 0).
C'est comme si au lieu d'écrire AAAABBCCC, on écrivait 4A 2B 3C.

Algorithme de Huffman

Pour finir, un dernier algorithme est appliqué aux valeurs précédentes : l'algorithme de Huffman. Il va permettre de donner précisément les bits à écrire pour constituer le fichier final (les 0 et 1). Par exemple, 5 peut devenir '010'. Il n'existe cependant pas de dictionnaire universel : la traduction dépend de la suite de caractères que l'on veut écrire. Dans un autre fichier, 5 pourrait devenir « 1001 ».

Alors comment sont définies les traductions ? En se basant sur la fréquence d'apparition de chacun des caractères.

Prenons un exemple : comment écrire la phrase « LE HOLLANDAIS VOLANT » en utilisant le moins de place possible ?

Certains caractères, comme le L et le A, sont répétés plusieurs fois. Il faut trouver une suite de 0 et de 1 suffisamment courte pour de pas perdre de place inutilement (imaginez que L devienne '01000111100000', on aurait 4 fois ça dans le texte final !)
On a aussi une autre contrainte : il ne faut pas que la traduction d'une lettre soit le début de la traduction d'une autre. Par exemple, si A → « 010 », L → « 01011 », T → « 11 » et que la phrase finale contienne « 01011 », comment savoir si elle veut dire « L » ou « AT » ?

Alors comment faire ?

On commence par classer chacun des caractères selon leur nombre d'apparitions dans la phrase.

Ici, cela donne :

4
3
(espace)  2
2
2
1
1
1
1
1
1
1

Puis, on forme un arbre à partir de ces lettres, en commençant par les deux lettres apparaissant le moins souvent, par exemple E et H. On dit alors que E et H sont les feuilles de l'arbre, et que E+H est un nœud.

arbre eh

Remarquez bien le 0 et le 1 sur les branches, ils nous serviront dans la suite. Comme les deux lettres apparaissaient une fois, on considère ce « couple » comme une lettre apparaissant deux fois. On se retrouve avec les nouvelles lettres :
4
3
(espace)  2
2
2
E+H  2
1
1
1
1
1

On ajoute un nouveau nœud à l'arbre, en prenant deux lettres parmi celles qui apparaissent le moins souvent :

arbre

Puis on recommence avec S et V :

arbre

Il nous reste donc ceci :

L4
A3
(espace)2
O2
N2
E+H2
D+I2
S+V2
T 1

On va maintenant associer le T avec, par exemple, E+H :

arbre

On a donc une nouvelle « lettre », de poids 3, E+H+T.

En continuant de la même manière jusqu'à insérer toutes les lettres, on trouve par exemple cet arbre. Il n'est pas unique, cela dépend des lettres que l'on choisit d'associer.

arbre

Il suffit alors de parcourir l'arbre jusqu'à ses feuilles pour en déduire le code correspondant à chaque lettre !
Pour atteindre le T, on ne passe que sur des branches étiquetées avec un 0, donc T devient '0000'. Pour aller sur le L, on va d'abord vers le bas puis vers le haut : L devient '10', et c'est le code le plus court.

Enfin, la traduction d'une lettre ne peut être le début d'une autre : cela voudrait dire qu'une feuille est en fait un nœud qui permet d'atteindre une autre lettre.

En utilisant ce dictionnaire, la phrase 'LE HOLLANDAIS VOLANT' s'écrit :
10 00010 110 00011 0010 10 10 010 111 00110 010 00111 0110 110 0111 0010 10 010 111 0000 (normalement il n'y a pas d'espaces, ici ils séparent les caractères).

Dans la compression JPEG, cet algorithme est appliqué à des nombres entiers et pas à des lettres, mais le principe est exactement le même. En mettant bout à bout toutes les suites de 0 et de 1 correspondant à chaque bloc, on écrit petit à petit le fichier JPEG.

Pour afficher l'image, il suffit de refaire toutes les étapes dans l'ordre inverse, pour afficher le tableau de pixels du début.

Conclusion

Un petit résumé des différentes étapes s'impose :

Vous avez pu voir que le fonctionnement de l'oeil est au cœur de la compression d'une image par cet algorithme. C'est pourquoi il est adapté à des images naturelles, comme des photographies. Il est par contre peu performant sur d'autres types d'images comme les logos (les contours bavent).

Il permet de diviser la taille d'une image par 5 sans que l'oeil ne voie la différence, ce qui explique sa popularité.


Article rédigé par Clément Masson, pour lehollandaisvolant.net