Introduction à la compression de données avec l'algorithme RLE

Je ne vais pas vous l'apprendre, l'objectif d'un algorithme de compression de données est de prendre une donnée (texte, image, audio, vidéo,...) et de lui appliquer un certains nombre d'opérations afin d'en ressortir une donnée plus légère.

Mais il y a plusieurs choses à savoir sur ces algorithmes :

• Certains sont plus adaptés pour compresser des données ayant une typologie spécifique
• Si il n'est pas adapté, un algorithme peut avoir l'effet inverse et faire grossir une donnée
• On les divise en deux grandes familles, avec perte (lossy) ou sans perte (lossless)

Celui que nous allons découvrir aujourd'hui est lossless et particulièrement adapté aux images, cet algorithme s'appelle : RLE.

Comment fonctionne le RLE ?

RLE signifie "Run-Length Encoding" (qu'on traduit en français par "codage par plage") et est souvent l'un des premiers algorithmes de compression de données étudiés car c'est l'un des plus simples à comprendre et à mettre en place.

Lossless

Comme évoqué précédemment, RLE est un algorithme lossless ce qui signifie qu'absolument aucune donnée n'est perdue pendant la compression, vous pouvez compresser trois fois de suite la même donnée, sa qualité en sortie ne bougera pas.

Si cela vous semble contre-intuitif, dites-vous simplement que lors d'une compression lossless, on troque un peu d'espace mémoire contre un peu de puissance de calcul (pour l'encodage et le décodage).

L'algorithme

Le fonctionnement de RLE consiste à parcourir toute une ressource, du début à la fin, et de regrouper les plages de données qui se répètent en indiquant à chaque fois le nombre d'occurence de la donnée.

Par exemple :

HellooooooooWoooooooorld devient 1H1e2l8o1W8o1r1l1d

Ici la donnée d'entrée contenait 24 caractères contre 18 caractères après une compression RLE, ce qui nous donne une réduction de 25% de la taille de la donnée !

Mais vous l'autre compris, sur un texte plus classique, le RLE devient inéfficace, voir contre-productif :

HelloWorld devient 1H1e2l1o1W1o1r1l1d

La donnée en sortie a grossi de 80% par rapport à la donnée d'entrée... Mais alors dans quelle situation peut-être utilisé le RLE ?

Cas d'usage

RLE est efficace sur des données qui se répètent énormément donc moins la variance entre chaque morceau de la donnée peut être élevée, plus la compression pourra être importante.

Les images par exemple ont souvent plus de chance d'avoir des pixels contigus de la même valeur que les lettres dans un texte en langage naturel (un ciel bleu par exemple).

Pour les images en noir et blanc, RLE a plus de chance d'être efficace car la variance d'un pixel à l'autre est au maximum de 255 niveaux de gris contre 255³ pour le RGB d'une photo en couleur.

Prenez l'image ci-dessous par exemple :

Normalement chaque pixel de la première ligne devrait être représenté par 8 bits (en niveau de gris) et être répété 1920 fois, prenant au total 1,8Ko juste pour une ligne complètement noire sans compression.

Avec avec le RLE, cette première ligne pèse seulement 11 bits pour stocker le chiffre (1920), et 8 bit pour la valeur du niveau de gris, ce qui nous donne un total de 19bits, soit 97 fois plus léger que l'original.

Evidemment, c'est très impressionnant pour le aplats de couleurs, mais dès que l'on va arriver au centre de l'image, l'efficacité du RLE sera moins grande, et ce sera le cas avec la plupart des images réelles.

Il est possible d'avoir de très bons résultats sur des illustrations par exemple, car les aplats de couleurs sont plus fréquents.

L'algorithme RLE est assez spécifique, mais il souvent utilisé comme algorithme supplémentaire, par dessus d'autres algorithmes de compressions avec perte, comme dans le JPEG par exemple.

Car lorsque l'on compresse d'abord avec perte, on fait souvent baisser la variance globale des données de l'objet, rendant donc RLE plus efficace après une première compression.

J'espère que cet article aura été utile, et à bientôt sur le blog