Comprendre le code RLE

De l'image au message binaire

En informatique, on peut représenter une image par une grille de petits carrés colorés appelés pixels.

Dans le cas d'une image en noir et blanc, chaque pixel peut être représenté par une valeur binaire (0 ou 1) appélée bit. Par exemple, on peut coder le pixel blanc par le bit 0 et le pixel noir par le bit 1. On peut alors parler d'encodage binaire brut.

Si l'on connaît la largeur \(L\) et la hauteur \(H\) de la grille, alors une image peut être représentée par une suite de \(L \times H\) bits. Les \(L\) premiers bits correspondent à la première ligne, les \(L\) suivants à la deuxième, etc.

Remarque : on découpe souvent les messages binaires par blocs de 8 bits, appelés octets. Il y a \(2^8 = 256\) octets différents, on peut donc les représenter par un entier entre 0 et 255 en notation décimale, ou par 00 et ff en notation hexadécimale. Par exemple, la séquence 00011011 correspond à l'octet "décimal" 27 (c'est sa décomposition en base 2), ou encore à l'octet "hexadécimal" 1b.

Un encodage pas toujours efficace

Les images que nous manipulons quotidiennement sont de taille grandissante. Par exemple, les appareils photo modernes ont une résolution de plus de 10 mégapixels, autrement dit plus de 10 millions de pixels. Pour diminuer les coûts de stockage et de transmission, on peut essayer de compresser l'image, c'est-à-dire d'en trouver un encodage qui utilise moins de bits.

L'encodage brut, présenté ci-dessus, nécessite autant de bits que l'image contient de pixels. Dans le cas d'une image complètement blanche de taille \(1000 \times 1000\), c'est un peu du gâchis : on utilise un million de bits, alors qu'on pourrait simplement écrire " un million de 0".

On cherche donc à utiliser des méthodes d'encodage plus efficaces, qui prennent en compte des suites de pixels identiques qui se repètent, qu'on appelle des plages.

Du message binaire au code RLE : l'exemple de la feuille blanche

L'idée de l'encodage par plages (RLE, pour run-length encoding en anglais) est d'enregistrer les tailles des suites de bits consécutifs identiques du message binaire. Ces tailles sont appelées longueurs de plages.

Pour créer le code RLE, on commence par écrire le nombre de 0 (donc, de pixels blancs) que l'on trouve consécutivement dans le message binaire. Puis, le bit suivant est nécessairement un 1, donc on peut écrire le nombre de 1 consécutifs qui le suivent. Ensuite, on recommence avec les 0, puis les 1, etc. jusqu'à arriver à la fin du message.

Remarque : si l'image commence par un pixel noir, alors le premier nombre à enregistrer est un 0. C'est d'ailleurs le seul endroit où le nombre zéro peut apparaître dans un code RLE !

Dans l'exemple de la grille blanche ci-contre, on enregistre donc simplement le nombre 144 : c'est le code RLE de l'image blanche. C'est beaucoup plus court à écrire que la série d'octets 00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:00 !