Lauflängenkodierung

Lauflängenkodierung

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. Liegt eine Wiederholung vor, wird die Anzahl der Wiederholungen sowie der wiederholte Wert gespeichert.

Um den Beginn einer Wiederholung zu kennzeichnen, werden sogenannte Marker-Bytes eingesetzt. Das sind Bytes, die nicht im Datenstrom vorkommen. Der Offset ist die Mindestwiederholrate, ab der kodiert wird. Bei einem Offset von 4 wird ab einer Wiederholung von 4 lauflängenkodiert. Dabei ergibt sich der Wert folgendermaßen: AnzahlderWiederholungenOffset = Wert. FF FF FF FF FF wird also zu AA 1 FF.

Beispiel

Als Beispiel sei ein Schwarz-Weiß-Bildschirm angenommen, auf dem sich schwarzer Text auf weißem Hintergrund befindet. Hier sind lange Folgen von weißen Punkten bzw. Pixeln nur selten durch einzelne schwarze Punkte unterbrochen. Bezeichnet man weiße Punkte mit "W" und schwarze mit "S", so ergibt sich z.B. in einer einzelnen Bildzeile die folgende Information:

WWWWWWWWWWSWWWWWWWWWWSSS

Nach Anwendung der Lauflängenkodierung erhält man:

10W1S10W3S

Dieses Beispiel dient lediglich der Veranschaulichung der Arbeitsweise des Algorithmus. In der Realität arbeitet man aber nicht mit Zeichen, sondern mit Bytes. Diese können durch zweistellige Hexadezimalzahlen beschrieben werden.
Wählt man für Weiß 00 und für Schwarz FF, so ergibt sich folgendes Bitmuster:

00000000000000000000FF00000000000000000000FFFFFF

Dies muss interpretiert werden als eine Folge von zehn weißen, einem schwarzen, gefolgt von weiteren zehn weißen und drei schwarzen Punkten. Die ursprünglich verwendeten 24 Buchstaben wurden somit in acht Buchstaben komprimiert, was einer Kompression auf ca. 33% der ursprünglichen Größe entspricht.

Als Marker-Byte kann man das nicht im Datenstrom enthaltene Byte AA verwenden. Lauflängenkodiert und mit einem Offset von 4, sieht er dann folgendermaßen aus:

AA600FFAA600FFFFFF

Bei einer ungünstigen Verteilung der Werte kann allerdings auch eine Vergrößerung der Datenmenge vorkommen. Dies ist bspw. bei folgenden Zahlenwerten der Fall:

5656

Da man hier nicht mehr zwischen den ursprünglichen Daten und dem Multiplikator unterscheiden kann, muss man selbst einzeln vorkommende Werte kodieren. Ansonsten würde der Algorithmus 56 zu 66666 expandieren. Die Kodierung der obigen Folge wird also wie folgt vorgenommen:

15161516

Vor jede ursprüngliche Zahl wird die Anzahl *1* ergänzt. Der längenkodierte Wert ist somit doppelt so lang wie der ursprüngliche.

Dieses Problem lässt sich vermeiden, indem bei Multiplikatoren größer 3 ein Kontrollzeichen eingefügt wird:

WSWSWWWWWWWWWSSSSSSWSWWW
WSWSX9WX6SWSWWW

Hier kommt es aber zum Konflikt, wenn im Datensatz das Kontrollzeichen als Inhalt auftaucht. Lösen kann man das, wenn man ein einzelnes X als XX komprimiert. Das Kontrollzeichen-X ist hervorgehoben.

WSSSSSWWWWWWXWWSWSSSSSSSSSXXXXXWSSW
WX5SX6WXXWWSWX9SX5XWSSW

Es gibt weitere Möglichkeiten, ein solches Aufblähen der Daten zu verringern, ganz vermeiden lässt sich dieser Effekt jedoch nicht.

Praktische Anwendung

Die unterschiedlichen Kompressionsprogramme speichern die komprimierte Datenfolge im Gegensatz zum obigen Beispiel in binärer Form ab, die teilweise sehr unterschiedlich sein kann. Einige Anwendungen speichern auch zusätzlich Folgen von mehreren Datenwerten, machen also aus -ABC-ABC-ABC-ABC- die gekürzte Darstellung 4[-ABC]-.

Geeignet ist die Lauflängenkodierung also da, wo es lange Folgen des gleichen Wertes gibt. Dies ist sehr häufig bei computergenerierten Bildern, Grafiken und Clip-Art-Bildern der Fall, die meist nur mit wenigen Farben gezeichnet sind, ebenso wie ältere Icons.

Bei natürlichen Bildern von Kameraufnahmen wird die Lauflängenkodierung nicht direkt auf den Bildpixelwerten angewandt, weil die Pixelwerte meist nicht regelmäßig genug sind. Allerdings ist die Lauflängenkodierung nach Anwendung einer Transformation wie der bei JPEG verwendeten DCT sehr effektiv. Insbesondere nach der Quantisierung entstehen in der Regel viele gleiche Werte oder Nullen, die sich effektiv mit einer Lauflängenkodierung komprimieren lassen. Häufig wird auch die noch effektivere Huffman-Kodierung verwendet.

Bekannte Dateiformate, die die Lauflängenkodierung anwenden, sind einige ältere Grafikformate wie beispielsweise Windows Bitmap, GEM Image, Targa oder PCX.

Unter Microsoft Windows wird die Dateiendung *.rle üblicherweise für RLE-komprimierte BMP-Bilder verwendet, die Dateiendung *.bmp/*.dib meist für unkomprimierte Bilder.

Lauflängenkodierung kommt außerdem bei der Fax-Übertragung zum Einsatz.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Bilddateiformat — Ein Grafikformat ist ein Dateiformat, das den Aufbau einer Bilddatei beschreibt. Es gibt zahlreiche Grafikformate, von denen sich nur wenige im großen Maßstab durchsetzen konnten. Viele Grafikformate werden nur von wenigen Anwendungen unterstützt …   Deutsch Wikipedia

  • Truevision Targa file format — Das Targa Image File Format (kurz: TGA, übliche Dateiendung: .tga) ist ein Dateiformat zur Speicherung von Bildern. Targa steht für „Truevision Advanced Raster Graphics Array“. Vorlage:Infobox Dateiformat/Wartung/magic fehltVorlage:Infobox… …   Deutsch Wikipedia

  • Targa Image File — Das Targa Image File Format (kurz: TGA, übliche Dateiendung: .tga) ist ein Dateiformat zur Speicherung von Bildern. Targa steht für „Truevision Advanced Raster Graphics Array“. Vorlage:Infobox Dateiformat/Wartung/MagischeZahl fehltVorlage:Infobox …   Deutsch Wikipedia

  • Intervalllängencodierung — 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

  • Lauflaengenkodierung — 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

  • Lauflängencodierung — 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

  • RLE — 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

  • Rle — 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-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 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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”