Post-Traitements

Codage RLE

Le codage RLE (run-length encoding) consiste à remplacer la répétition d'un même code par une balise et le nombre d'occurences de ce code :
Pour le JPEG, le codage RLE ne sera appliqué que pour les séquences de 0. Exemple :
la séquence : 150000000008
Séquence RLE : 15#98

On se rend compte du gain considérable que l'on peut réaliser en codant chaque bloc 8x8 passé en DCT, puis quantifié.

Principe du Codage de Huffman

Le codage de Huffman (statique) est un codage classique en algorithmique. Il demande cependant plusieurs étapes avant de pouvoir réellement compresser le code. Le principe consiste à remplacer en intégralité tous les coefficients que l'on rencontre dans l'image par des codes de Huffman. Plus un coefficient apparaitra souvent, moins le code correspondant comportera de bits.

Mise en Oeuvre

Tout d'abord, il faut créer une table comportant l'ensemble des coefficients de l'image, en faisant correspondre le nombre d'occurences de ces coefficients.

Ensuite, on classe cette table par ordre croissant d'occurences. A partir de cette table classée, on construit un arbre, en partant des feuilles.

1. On prend les deux coefficients ayant un nombre d'occurences le moins élevé, et on les enlève de la table.
2. On crée un arbre avec pour fils gauche le coefficient ayant la plus faible occurence. La racine est un nouveau coefficient dont l'occurence est la somme des occurences de ses deux fils. On insère (de manière a garder la croissance des occurences) ce nouveau coefficient dans la table, et on recommence l'étape 1. On s'arrête lorsque la table ne contient plus qu'un seul coefficient.

Ainsi on obtient un arbre complet dont les feuilles sont les coefficients de l'image. Le code de Huffman est connu en partant de la racine de l'arbre et en concaténant 0 si on suit le fils gauche, et 1 si on suit le fils droit.

Avec une table de correspondance Coefficient - Code de Huffman, on transforme les séquences trouvées à la suite du codage RLE, en convertissant les coefficients par les codes correspondants.

Cette transformation est sans perte, et entièrement réversible. Il faut simplement se souvenir de la table de correspondance.

Exemple :

$${ \left( \begin{array}{c} Coefficient\\ Occurences\\ \end{... ...3 & 2 & \char93 \\ 2 & 2 & 4 & 7 & 11 \\ \end{array}\right)$$

Figure: Arbre de Huffman.

$${ \left( \begin{array}{c} Coefficient\\ Code Binaire\\ \en... ...\char93 \\ 1100 & 1101 & 111 & 10 & 0 \\ \end{array}\right)$$