Cet article est le premier d'une série consacrée aux différentes techniques de compression d'image et de séquences vidéo. Nous avons choisi de ne pas nous intéresser au son, dont le stockage est moins problématique que celui des images.

Rappelons qu'une image sous forme numérique est constituée d'une matrice de pixels contenant des informations sur la couleur de chacun d'entre eux. Cette information peut être codée sur 1 bit (2 couleurs - noir et blanc), 8 bits (1 octet - 256 couleurs), 16 ou 24 bits (respectivement 65536 et plus de 16 millions de couleurs: dans ce dernier cas, chaque octet code l'une des couleurs fondamentales, le rouge, le vert ou le bleu). Il est même possible de rajouter un octet contenant une information de transparence: l'information de couleur peut alors être codée sur 32 bits. La taille en octets de l'image est bien sûr proportionnelle à la précision sur la couleur, et à sa taille en pixels. La taille en octets d'une image 24 bits est vite considérable: une image 300x200 "pèse" environ 176 Ko. D'où l'intérêt des algorithmes de compression pour une transmission via le web. Ceci est encore plus vrai pour une séquence de 25 images (300x200, 24 bits) par seconde d'une durée d'une minute, dont la taille est d'environ 258 Mo! Et encore, la taille de l'image est très très petite.

L'algorithme DCT
Le format JPEG (Joint Photographic Experts Group) permet d'atteindre des taux de compression (sans perte notable de qualité) jusqu'à un facteur 25. La technique sous-jacente repose sur une transformation matricielle appelée DCT, pour Discrete Cosine Transform. L'algorithme DCT s'applique sur des sous-matrices (blocs) de 8x8 pixels. Mathématiquement, la transformation s'écrit, pour une sous-matrice A:

tC.A.C (le . désigne un produit matriciel)

où tC désigne la transformée de C: tC(i,j)=C(j,i). C est une matrice 8x8 de coefficents tels que: C(i,j)=K(j)/2*cos((2*i+1)*j*PI/16 avec K(0)=sqrt(1/2) et K(j)=1 pour j>0.
La transformation DCT est orthogonale: on peut l'inverser. Si B est la matrice résultant de l'opération, on récupère A par C.B.tC.

En théorie, la transformation DCT est donc sans perte. En pratique, les arrondis vont venir la fausser. La transformation inverse ne donnera pas exactement A. Minimiser les arrondis permet d'obtenir un meilleur résultat par conséquent.
En elle-même, la transformation DCT ne compresse pas les données: elle modifie simplement les coefficients de la matrice initiale (RVB). Le but est analogue à celui de la transformée de Fourier d'un signal: traduire l'image dans un "domaine de fréquences" (peser le poids relatif de chaque fréquence). Le bloc 8x8 initial donne par DCT un bloc 8x8 dont les coefficients en haut à gauche sont les coefficients des basses fréquences et les coefficients en bas à droite ceux des hautes fréquences. Que représente ces fréquences? Elles caractérisent des courbes sinusoïdales qui sont elles-mêmes la décomposition du "signal" que représente l'image (en l'occurence le bloc). Ce sont des "fréquences spatiales".

Notons qu'il est préférable, afin d'obtenir ultérieurement une meilleure compression, de convertir au préalable (avant la transformation DCT) l'image RVB en image YUV (luminance - chrominance - saturation ou luminosité - teinte - saturation). Une image 16 bits traduite en luminance - chrominance puis transformée par DCT donnera lieu à une matrice de blocs 8x8 contenant des paires de coefficients DCT exploitables au mieux.

Quantification et encodage
Une fois la transformation DCT effectuée, la première étape de la compression proprement dite est la quantification des coefficients DCT. Chaque coefficient d'un bloc 8x8 est divisé par un quantificateur élément d'une matrice 8x8 de quantification. Ces 64 quantificateurs sont soit calculés en fonction d'un paramètre de compression, soit donnés par des tables standards, optimisées par les concepteurs du format JPEG: il existe une table de quantification pour l'information de luminance, une autre pour l'information de chrominance (données ci-dessous).

Chaque coefficient DCT est divisé par le quantificateur correspondant, puis arrondi à l'entier le plus proche. Ceci a pour effet de diminuer (voire supprimer) le poids relatif des faibles coefficients (en valeur absolue) et d'abaisser le niveau de précision qu'expriment les forts coefficients (en valeur absolue). L'étape de quantification (quantization) est donc l'étape de perte d'information.

L'encodage, dernière étape du processus, est précédé d'une réorganisation de la matrice (ensemble des sous-matrices ou blocs): les coefficients correspondant aux basses fréquences, et en bas à droite les coefficients correspondant aux hautes fréquences (ces derniers ayant beaucoup plus de chances d'être proches de - ou égaux à - zéro). On utilise ensuite généralement l'algorithme de Huffman pour effectuer l'encodage.

Arbres de Huffman
Un tel arbre est construit à partir de la matrice (préparée selon le processus ci-dessus) en construisant une liste des éléments et de leur fréquence (cette le fois le nombre d'occurences de chaque coefficient dans la matrice), par ordre croissant. Ensuite, les deux éléments de plus basse fréquence (occurence) consitueront deux des "feuilles" de l'arbre. Leur "parent" est ensuite construit en lui associant une valeur qui est la somme des fréquences de ses deux fils. Ce noeud parent est ensuite injecté dans la liste des fréquences à la place correspondant à sa valeur, tandis que les deux éléments ayant servis à l'obtenir sont enlevés de la liste. Le processus est ensuite itéré avec les autres éléments (en commençant par les fréquences basses) jusqu'à ce qu'il ne reste plus qu'un seul élément dans la liste: l'élément racine de l'arbre de Huffman.
L'encodage proprement dit est constitué en associant à chaque feuille ou branche de l'arbre un identifiant unique: une feuille ou branche gauche se verra associé un "0", tandis qu'une feuille ou branche droite se verra associée un "1". Une feuille gauche d'une branche droite de la racine aura donc l'identifiant "01" (l'arbre est traversé depuis la feuille désirée), unique. Les valeurs sont placées dans une table qui constituera la plus grande partie du fichier JPEG. Ces données sont compressées par la représentation en arbre de Huffman, et au préalable par l'opération de quantification.

Il existe d'autres techniques de compression d'image, notamment la compression par ondelettes, sur lesquelles nous reviendrons. La compression JPEG reste largement répandue sur le web, même si elle pourrait être supplantée par des algorithmes plus performants dans un futur proche.