Verlauf
|
Alle Kapitel anzeigen
RLE steht für Runlength-Encoding und ist eines der einfachsten Datenkompressionsverfahren, es wurde schon sehr früh eingesetzt und existiert in verschiedenen Ausführungen. Beispielsweise wird es von folgenden Formaten verwendet:
- BMP
- TIFF
- PCX
- TGA
RLE eignet sich besonders zur Kompression von einfachen Grafiken mit vielen gleichfarbigen Flächen, nicht jedoch für Farbbilder, in denen jeder Pixel einen anderen Wert hat.
Dieses Modul beschreibt vor allem das Grundprinzip von RLE, aber auch einige verschiedene Versionen dieses Kompressionsverfahrens.
Die Grundidee der Lauflängenkodierung ist die, anstelle der unkodierten Daten so genannte Runs zu speichern. Ein Run ist eine Abfolge von identischen Zeichen, die Länge der jeweiligen Sequenz wird in einem Run Counter gespeichert. Den Inhalt der Abfolge bezeichnet man auch als Run Value. Aus den Originaldaten aaaabbaaaccccccggggggff wird dann beispielsweise 4a2b3a6c6g2f, wobei 4, 2, 3, 6, 6, 2 die Run Counter sind und a, b, a, c, g, f die Run Values. Idealerweise lässt sich mit dieser einfachen Form der Lauflängenkodierung eine 256 Zeichen lange Abfolge mit 2 Zeichen darstellen, wenn man von einem 1-Byte-Counter ausgeht. Allerdings kann sich im ungünstigsten Fall mit diesem Verfahren das Datenvolumen auch verdoppeln. Dies passiert beispielsweise bei folgender Datensequenz: abghdfgs - daraus wird nach der Kodierung 1a1b1g1h1d1f1g1s.
Heute existieren neben der Urform der RLE verschiedene Varianten, denen allen die selbe Idee zu Grunde liegt, mit Hilfe derer aber eine, im Gegensatz zur prinzipiellen Form, höhere Wahrscheinlichkeit der tatsächlichen Datenreduktion gegeben ist. Man unterscheidet allgemein zwischen primitiven Versionen und solchen mit Steuerzeichen, auf die im Kapitel Varianten näher eingegangen wird.
Die Kodierung ist abhängig von der jeweils benutzen RLE- Variante, das Grundprinzip beruht jedoch auf dem einfachen Zusammenfassen von aufeinander folgenden identischen Zeichen.
Aus aaaabbbcccc wird dann 4a3b4c. Es werden jedoch nur gute Kompressionsraten erzielt, wenn häufig entsprechende Runs auftreten (was in der Praxis z.B. bei großen, gleichfarbigen Flächen der Fall ist).
Bei sehr selten vorkommenden Runs gleicher Zeichen ist die Datei nach der Kodierung größer als zuvor - im schlechtesten Fall genau doppelt so groß. Dies ist beispielsweise bei folgender Zeichenkette der Fall: aus abghjkl wird 1a1b1g1h1j1k1l.
Bei der nun folgenden Animation wird eine Zeichenkette kodiert.
Die Dekodierung macht aus den zusammengefassten Runs wieder die ursprüngliche Zeichenkette.
Aus dem kodierten String 4a3b4c wird wieder aaaabbbcccc.
Allgemein- 8-Bit-RLE
Allgemeine RLE- Verfahren orientieren sich an der gängigen Basisgröße Byte, da diese in den üblichen Rechnersystemen Standard ist. Aus diesem Grund ist hier sowohl die Anzahl der Zeichen als auch die Größe des Counters auf 256 beschränkt. Das Schema sieht dann also folgendermaßen aus:
| Run1 | Run2 | |||
| Counter | Value | Counter | Value | |
| Wertebereich | 0 - 255 | 0 - 255 | 0 - 255 | 0 - 255 |
Hier tritt das oben bereits angesprochene Problem auf, dass sich die Datenmenge verdoppelt wenn es keine Runs identischer Zeichen gibt.
Allgemein - unkodierte Originaldaten
Dieses RLE-Verfahren verbessert das Kodierergebnis bei Reihen ohne Wiederholungen. Alternativ zu der Anzahl der hintereinander auftretenden identischen Zeichen eines Runs kann der Zähler die Anzahl der folgenden unkodierten Daten anzeigen. Kodiert wird also nur wenn auch wirklich Wiederholungen auftreten. Allerdings benötigt man dazu ein zusätzliches Flag das angibt ob der nächste Run Wiederholungen oder unkodierte Zeichen sind. Das Schema bei Wiederholungen sieht folgendermaßen aus:
| Counter | Value | Counter | Value | |||
| Wertebereich | 0 (*) | 0 - 127 | 0 - 255 | 0 | 0 - 127 | 0 - 255 |
Das Schema bei unkodierten Passagen sieht folgendermaßen aus:
| Counter | Value | Value | Value | Value | ||
| Wertebereich | 1 (*) | 0 - 127 | 0 - 255 | 0 - 255 | 0 - 255 | 0 - 255 |
(*) diese Zahl ist das Flag das bestimmt, woraus der nächste Run besteht. 0 bedeutet Wiederholungen, 1 bedeutet unkodierte Originaldaten.
Mit diesem Verfahren bleibt die Zunahme des Datenvolumens gering, falls keine Wiederholungen auftreten, da nur alle 128 Zeichen ein zusätzlicher Zähler eingefügt werden muss.
Mit Steuerzeichen
Auch hier geht es darum, nur zu kodieren, wenn tatsächlich Wiederholungen auftreten. Es wird allerdings, anstatt einem zusätzlichen Zähler ein Steuerzeichen eingesetzt, das innerhalb der unkodierten Daten auf eine Wiederholung hinweist. Da die minimale sinnvolle Sequenzlänge bei 4 liegt (diese Zahl ergibt sich daraus, dass bei diesem Kodierschema jede Wiederholung eines Zeichens einen Kodierungsaufwand von 3 Byte benötigt: Steuerzeichen+Counter+Value), wird die Anzahl der identischen Zeichen minus dem Offset von 4 kodiert. Das könnte folgendermaßen aussehen:
| Unkodierte Daten | Kodierte Daten |
| ahdlwbbbbbhzewkdl | ahdlw#1bhzewkdl |
Nähere Informationen zu den wichtigeren Grafikdateiformaten findet man unter folgenden Links:
Nähere Informationen zu TIFF
Nähere Informationen zu TGA
RLE ist zwar vollkommen verlustfrei und erzielt gute Kompressionsraten bei dafür geeigneten Bildern (viele gleichfarbige Flächen, Skizzen, Diagramme), ist aber zur Kompression komplexer Farbbilder ungeeignet- auch wenn das Verfahren weiterentwickelt wurde und dadurch die Zunahme des Datenvolumens bei Reihen ohne Wiederholungen kein Problem mehr darstellt, so sind die Kompressionsraten bei solchen Bildern doch denkbar schlecht. Der sinnvolle Einsatz von RLE beschränkt sich daher auf bestimmte Grafiktypen.
