Chapitre 2 :INTRODUCTION A LA COMPRESSION:

La compression sans perte :

      La compression sans perte signifie que lorsque des données sont compressées et ensuite décompressées, l'information originale contenue dans les données a été préservée. Aucune donnée n'a été perdue ou oubliée. Les données n'ont pas été modifiées.

Les méthodes de compression d’images sans perte sont utiles lorsqu’on veut garder une grande précision, tel que pour des balayages médicaux, ou des numérisations d'images destinées à l'archivage.

Nous allons nous intéresser aux deux algorithmes RLE (basé sur les répétitions) et le codage Huffman (basé sur les statistiques). Ces deux algorithmes sont utilisés lors de la compression JPEG.

RLE (Run Length encoding):

Le run-length encoding, aussi appelé codage par plages, est un algorithme de compression de données en informatique basé sur les répétitions. Ainsi, le RLE s'emploie à réduire la taille physique d'une répétition de chaîne de caractère.

Principe: Compter le nombre d’occurrences d’une chaîne répétée appelée passage (run) à l’aide d’un compteur de passages (run count) et associer ce nombre à chaque séquence, soit à la valeur du caractère répété dans le passage qu’on appelle la valeur de passage (run value). Chacune de ces deux opérations est codée sur un octet, on obtient donc une chaîne de deux octets après codage. Cette représentation est nommée un paquet RLE (RLE packet) dont on génère un nouveau à chaque fois que le caractère change ou chaque fois que le nombre de caractères dans le passage excède la valeur maximum que peut prendre le compteur. 

Exemple: « aaaabccdddd aaaabccdddd» cette suite de caractères contient 23 caractères, en suivant la méthode RLE on obtient: 2(4a1b2c4d) qui fait 11 caractères.
Cet exemple montre que l’encodage RLE est très efficace si le nombre de redondances est élevé, prenons l’exemple suivant : « abcdefg » 7 caractères RLE >> « 1a1b1c1d1e1f1g » 14 caractères !
La méthode RLE n’est donc pas efficace quand il n’y a pas de redondances !!!

Puisqu’on s’intéresse à la compression d’images numériques, étudions l’application de l’encodage RLE sur un bloc de pixels  (Prenons ce bloc de pixels 10x10 ):

exemple RLE

Cette image étant codée sur 24 bits en mode RVB, ce qui donne 1 octet pour chaque couleur élémentaire (1 octet pour le rouge, 1 octet pour le vert et 1 octet pour le bleu).
La taille de cette image sans compression est donc de 3x10x10 = 300 octets. On extrait les matrices de pixels, c'est-à-dire les matrices comportant les valeurs de chaque couleur élémentaire pour chaque pixel :

Rouge
251 166 214 255 255 255 255 255 251 251
194 120 129 255 255 255 255 255 255 181
123 123 208 255 255 255 255 255 255 242
220 255 255 255 246 209 213 249 255 255
255 255 255 223 159 143 125 214 250 255
235 253 255 224 144 218 235 247 255 244
188 248 247 183 126 242 255 255 255 227
240 255 252 240 135 236 255 255 255 248
254 255 244 240 245 251 253 250 255 217
255 255 147 136 201 183 245 223 202 127

 

Vert
251 166 214 255 255 255 255 255 251 251
194 120 129 255 255 255 255 255 255 181
123 123 208 255 255 255 255 255 255 242
220 255 255 255 246 209 213 249 255 255
255 255 255 223 159 143 125 214 250 255
235 253 255 224 144 218 235 247 255 244
188 248 247 183 126 242 255 255 255 227
240 255 252 240 135 236 255 255 255 248
254 255 244 240 245 251 253 250 255 217
255 255 147 136 201 183 245 223 202 127





Bleu
251 166 214 255 255 255 255 255 251 251
194 120 129 255 255 255 255 255 255 181
123 123 208 255 255 255 255 255 255 242
220 255 255 255 246 209 213 249 255 255
255 255 255 223 159 143 125 214 250 255
235 253 255 224 144 218 235 247 255 244
188 248 247 183 126 242 255 255 255 227
240 255 252 240 135 236 255 255 255 248
254 255 244 240 245 251 253 250 255 217
255 255 147 136 201 183 245 223 202 127

Ce qui donne :
3x 251 (premier pixel avec R =251 , V=251 , B=251) + 3x166 + 3x214 + 15x255 + 6x251 + 3x194 + 3x120 +3x129 + 18x255 + 3x181 + 6x123 + 3x208 + 6x255 + 3x242 + 3x220 + 9x255 + 3x246 + 3x209 + 3x213 + 3x249 + 15x255 + 3x223 + 3x159 + 3x143 + 3x125 + 3x214 + 3x250 + 3x255 + 3x188 + 3x 248 + 3x247 + 3x183 + 3x126 + 3x242 + 9x255 + 3x248 + 3x254 + 3x255 + 3x244 + 3x240 + 3x245 + 3x251 + 3x250 + 3x255 + 3x217 + 6x255 + 3x147+ 4x136 + 3x201 + 3x183 + 3x245 + 3x223 + 3x202 + 3x127.

Taille de l’image compressée est de 108 octets !!!!
(Le fichier compressé codé en binaire va être de la forme suivante : 00000011 11111011  00000011 10100110 …)

Huffman (Méthode statistique) :

Méthode inventée par D.A. Huffman en 1952. Cet algorithme est capable de faire une analyse statistique de données et ainsi associer aux séquences qui se répètent un code plus court qu’aux séquences plus rares (code à longueur variable).

Cet algorithme utilise un dictionnaire de codes où sont stockées les données issues de l’analyse statistique. Ce dictionnaire doit être conservé entre la compression et la décompression.

Principe : L’algorithme effectue tout d’abord une analyse pour trouver la fréquence (nombre d’occurrences) de chaque séquence (caractère pour un texte, code de couleur pour un pixel,...) dont on reporte le résultat dans une table de fréquence. Ensuite on crée un arbre binaire à partir de ces informations ; chaque séquence constitue une de feuilles de l’arbre à laquelle on associe un poids valant sa fréquence. A chaque deux nœuds de poids faible on associe un père de poids équivalent à la somme des poids de ses fils jusqu’à ce qu’on arrive à la racine. Ensuite le code 0 est associé à la branche droite et le code 1 à la branche gauche ou vice-versa.
Pour obtenir le code binaire il suffit de remonter l’arbre à partir de la racine jusqu’aux feuilles en rajoutant à chaque fois le code adéquat (0 ou 1) selon la branche suivie.

Exemple: Codage de l’expression suivante : « Compression d’une image numérique »

Selon le code ASCII et le codage de Huffman:


On peut classifier les méthodes de compressions en deux types : avec perte et sans perte.