Run-length encoding


Run-length encoding

Le run-length encoding, appelé en français le codage par plages, est un algorithme de compression de données en informatique.

Le système s'applique essentiellement à des documents scannés en noir et blanc : au lieu de coder un bit par point, on dispose d'un compteur — en général sur un octet — indiquant combien de points blancs ou noirs se suivent. Comme il est rare de ne pas avoir au moins 8 pixels noirs ou 8 pixels blancs qui se suivent, et que 256 ne sont pas rares sur les endroits vierges ou les à-plats noirs, le système a bien pour effet une compression. S'il y a plus de 256 bits de la même couleur, on peut placer ensuite un octet spécifiant 0 bit de la couleur opposée, puis coder le nombre de bits qui restent...

Par exemple, considérons un écran de texte noir sur fond blanc. Il sera constitué de longues séquences de pixels blancs pour le fond, et de courtes séquences de pixels noirs pour le texte. Représentons une ligne d'un tel écran, avec B pour les pixels noirs et W pour les pixels blancs :

WWWWWWWWWWWWBWWWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWW 

Un encodage RLE consiste alors à indiquer pour chaque suite de pixels d'une même couleur, le nombre de pixels de cette séquence. Le résultat comporte en général moins de caractères, bien que ce ne soit pas une obligation. On obtient par exemple pour la ligne précédente :

12W1B14W3B23W1B11W

Tandis que :

WBWBWBWBWB

donnerait :

1W1B1W1B1W1B1W1B1W1B

Ce qui est deux fois plus long.

Applications

Les formats d'images utilisent cette compression en considérant que toutes les lignes de pixels sont jointes pour former une unique séquence de couleur.

  • Le format BMP de Windows et OS/2 permet d'utiliser la compression RLE pour les images en 1, 4 et 8 bits/pixel (respectivement noir & blanc, 16 couleurs et 256 couleurs).
  • Le format PCX utilise également le principe de la compression RLE pour les images en 8 et 24 bits/pixel. Dans le cas des images en 24 bits/pixel, l'image est en fait découpée en trois plans de couleur (rouge, vert et bleu) où chaque plan est encodé comme une image en 8 bits/pixel.

RLE est aussi utilisé pour les fax Groupe 3 et Groupe 4 (Recommendations ITU-T T.4 et T.6), son usage le plus fréquent hors informatique. Les lignes, ici des succcessions de points blancs ou noirs, sont codées par leur longueur en pixel de chaque couleur. Mais les longueurs sont codées en fonction de leur fréquence d'apparition. Et ce codage fait partie de la spécification. Il s'agit d'une sorte de compression Huffman prédéfinie. Chaque segment est forcément de la couleur opposée et cette couleur ne doit donc pas être transmise, augmentant la compression. Dans l'exemple le W et B ne sont pas transmis. Par contre, cela implique que chaque ligne commence par une couleur connue. Et quand la longueur dépasse celle possible, on intercale l'autre couleur mais de longueur nulle.

La même compression peut être utilisée en niveaux de gris mais elle est alors peu efficace, de là la faible vitesse de transmission des fax pour de telles images.

Articles connexes



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Run-length encoding de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Run-length encoding — (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. This is …   Wikipedia

  • Run-length encoding — Saltar a navegación, búsqueda La compresión RLE o Run length encoding es una forma muy simple de compresión de datos en la que secuencias de datos con el mismo valor consecutivas son almacenadas como un único valor más su recuento. Esto es más… …   Wikipedia Español

  • Run-length encoding — Die Lauflängenkodierung (engl. Run length encoding, kurz RLE) ist ein sehr einfacher verlustfreier Kompressionsalgorithmus für digitale Daten. Sie ist besonders gut geeignet, Wiederholungen oder Sequenzen von gleichen Werten verkürzt darzustellen …   Deutsch Wikipedia

  • Run-length encoding — La compresión RLE o Run lenght enconding es una forma muy simple de compresión de datos en la que secuencias de datos con el mismo valor son almacenadas como un único valor más su recuento. Esto es más útil en datos que contienen muchas de estas… …   Enciclopedia Universal

  • run-length encoding — noun A simple data compression scheme in which sequences of the same item are replaced by one such item and a count (so for example the text BBBBB is stored as a single B with count of 5) …   Wiktionary

  • Run-length encoding —   Refer instead to Data compression …   International financial encyclopaedia

  • Run length limited — or RLL coding is a technique that is used to store data on recordable media. Specifically, RLL prevents long stretches of repeated bits from causing the signal recorded on media to not change for an excessive period, by modulating the data. RLL… …   Wikipedia

  • Run-length-kodierung — Die Lauflängenkodierung (engl. Run length encoding, kurz RLE) ist ein sehr einfacher verlustfreier Kompressionsalgorithmus für digitale Daten. Sie ist besonders gut geeignet, Wiederholungen oder Sequenzen von gleichen Werten verkürzt darzustellen …   Deutsch Wikipedia

  • Run Length Encoded — Die Lauflängenkodierung (engl. Run length encoding, kurz RLE) ist ein sehr einfacher verlustfreier Kompressionsalgorithmus für digitale Daten. Sie ist besonders gut geeignet, Wiederholungen oder Sequenzen von gleichen Werten verkürzt darzustellen …   Deutsch Wikipedia

  • advanced run-length limited encoding —    Abbreviated ARLL. A technique used to store information on a hard disk that increases the capacity of runlength limited (RLL) storage by more than 25 percent and increases the data transfer rate to 9Mbps.    See also RLL encoding …   Dictionary of networking