Index

5. Komprimierung von Daten (2)

RLE-Verfahren


Übung  

Wir wollen uns mit einer einfachen Sonderform beschäftigen, die sich speziell für die effektive Übermittlung von Schwarz-Weiß-Bilddaten eignet, nämlich der "Lauflängen-Kodierung". In der Informatik-Fachsprache redet man von "RLE-Daten" ("r"un "l"ength "e"ncoded data).

Das RLE-Verfahren versucht, möglichst ohne Wiederholungen auszukommen, beschränkt sich aber darauf, direkt aufeinanderfolgender Wiederholungen desselben Datenwertes zu vermeiden. Enthält also z.B. der Datenstrom eines Bildes n aufeinanderfolgende Pixel gleicher Farbe (also einen "Lauf" oder "run" der Länge n), dann wird nicht n-mal diese Pixelfarbe in die Daten übernommen (wie wir das bisher getan haben), sondern man fügt nur 1-mal die Pixelfarbe ein, gefolgt von einer Zahl, welche die Anzahl der nun folgenden Pixel dieser Farbe angibt.

Aufgaben:

  1. Entwirf ein Format zur Kodierung von Schwarz-Weiß-Graphiken, das eine RLE-Kodierung verwendet. Verfasse auf einem DIN-A4-Blatt eine so genaue Dekodierungs-Beschreibung für dein Format, dass dein Nachbar nur mit Hilfe dieser Beschreibung aus von dir hergestellten Daten das zugehörige Bild rekonstruieren kann. Prüfe dabei u.a., ob deine Beschreibung die folgenden Fragen klärt:
    Bemühe dich auf jeden Fall um ein möglichst einfaches Format.


  2. Erstelle mit "Image-Edit" eine Schwarz-Weiß-Grafik beliebiger (aber noch bewältigbarer!) Größe, und speichere sie im Homeverzeichnis unter "gr_rle.bmp" ab. Kodiere dann dieses Bild mit deinem in der vorigen Aufgabe entwickelten Verfahren in eine Byte-Folge, die du auf ein neues "Daten"-Blatt schreibst.
    (Zur Erleichterung darfst du die Bytes dezimal schreiben. Beachte aber, dass ein Byte höchstens den Wert 255 enthalten kann!)


  3. Tausche dann mit dem Nachbarn (wie bei der entsprechenden Aufgabe aus dem vorigen Kapitel) Format-Beschreibung und Daten aus, und rekonstruiere das Bild des Nachbarn als "gr_rle2.bmp" auf deinem Rechner.
    Auch diesmal gilt: Es darf keine zusätzliche mündliche Information fließen!

Im Falle der Schwarz-Weiß-Grafik kann das RLE-Verfahren noch weiter vereinfacht werden:
Da auf einen Lauf aus schwarzen Pixeln in der Regel einer aus weißen Pixeln folgt, ist die explizite Nennung der Pixelfarbe überflüssig: man muss einfach nach jedem Lauf die Farbe umschalten. Der Krisenfall, dass mehr Pixel derselben Farbe hintereinander kommen, als in einen Lauf passen, also zwei gleichfarbige Läufe direkt hintereinander kommen müssen, lässt sich leicht durch das Einfügen eines Laufes der anderen Farbe mit der Länge 0 entschärfen. Damit erhält man z.B. die folgende Format-Beschreibung:

  1. Die ersten 4 Byte enthalten Angaben zu den Abmessungen des Bildes:
    1. Die ersten 2 Byte enthalten die Anzahl n der Pixel in jeder Zeile, und zwar als 4-stellige Hex-Zahl.
    2. Die nächsten 2 Byte enthalten die Anzahl m der Zeilen des Bildes, ebenfalls als 4-stellige Hex-Zahl.

  2. Dann folgen die Bilddaten:
    1. Das Bild wird bzw. ist zeilenweise kodiert, und zwar von oben nach unten, also mit der obersten Zeile beginnend.
    2. Jede Zeile wird bzw. ist von links nach rechts kodiert, also beginnend mit dem links außen stehenden Pixel.
    3. Kodierung:
      Wir denken uns alle Pixel des Bildes in der unter 2a) und 2b) beschriebenen Reihenfolge in einer "Pixelschlange" aufgereiht.
      Setze die "aktive Farbe" auf "schwarz".
      Wiederhole nun die folgenden Schritte....
      {
      1. Bestimme die Anzahl n der am Anfang der Schlange aufeinander folgenden Pixel, die die aktive Farbe haben. Dabei darf n höchstens 255 werden. Gibt es mehr als 255 "aktiv"-farbige Pixel hintereinander, dann halte beim 255. Pixel an.
      2. Schreibe das Byte n in die Daten.
      3. Streiche die schon gezählten Pixel ab, d.h.: die Schlange beginnt nun mit dem ersten noch nicht gezählten Pixel.
      4. Wenn die aktive Farbe "schwarz" ist, dann:
             schalte sie auf "weiß" um,
        andernfalls:
             schalte sie auf "schwarz" um.
      }
      ....solange, bis keine Pixel mehr in der "Schlange" sind.

      Dekodierung:
      Wir fügen alle im Datenstrom vermerkten Pixel des Bildes in eine "Pixelschlange" ein, die zunächst noch leer ist:
      Setze die "aktive Farbe" auf "schwarz".
      Wiederhole nun die folgenden Schritte....
      {
      1. Lies das nächste Byte n aus den Daten. Füge so viele Pixel mit der aktiven Farbe an die Schlange an, wie n angibt.
      2. Gehe zum nächsten Byte im Datenstrom.
      3. Wenn die aktive Farbe "schwarz" ist, dann:
             schalte sie auf "weiß" um,
        andernfalls:
             schalte sie auf "schwarz" um.
      }
      ....solange, bis keine Zahlen mehr im Datenstrom enthalten sind.
      Nun werden alle in der Schlange vermerkten Pixel in der unter 2a) und 2b) beschriebenen Reihenfolge in das Bild eingefügt.

Im Gegensatz zu unserem BitMap-Format aus dem letzten Kapitel werden nun hier für das RLE-Format getrennte "Rezepte" für Kodierung und Dekodierung benötigt. Es scheint einen wesentlichen Unterschied zwischen diesen beiden Formaten zu geben, der sich auch in den Datenströmen wiederspiegelt:
Wenn wir die Abmessungen eines zu rekonstruierenden Bildes kennen, dann lässt sich aus der Position eines Zeichens in einem BitMap-Datenstrom eindeutig auf das zugehörige Pixel im Bild schließen, ohne dass wir erst die Nachbarpixel analysieren müssen; beim RLE-kodierten Datenstrom hängt die Bedeutung eines Byte von allen vorangehenden Byte-Werten ab!

Man kann den Unterschied auch anders verdeutlichen:
Während im BitMap-Datenstrom stets Pixel-Farb-Werte aufgezeichnet werden, enthält der RLE-Datenstrom Informationen über die Orte von Pixel-Farbwert-Änderungen. Um nun aber von den Änderungen wieder zurückschließen zu können auf den Farb-Wert eines bestimmten Pixels, ist es eben nötig, dass man die Farb-Werte aller zuvor aufgelisteten Pixel berücksichtigt.

Wann ist nun RLE-Kodierung sinnvoll? Sicher nur dann, wenn die Wahrscheinlichkeit groß ist, dass benachbarte Pixel dieselbe Farbe haben. Damit ist klar, dass sich vor allem Bilder mit möglichst wenig Farben gut komprimieren lassen werden. Nimmt die Zahl der Farben in einem Bild zu, dann nimmt die Kompressibilität der Bilddaten ab. Im schlimmsten Fall ("Keine zwei benachbarten Pixel haben dieselbe Farbe!") wird der Datenstrom durch die Kompressionsversuche verlängert statt verkürzt! Der klassische Einsatzfall für das RLE-Verfahrens ist das gute, alte Schwarz-Weiß-Fax-Gerät.

Seitenanfang


Übungen:

  1. Die folgende Hex-Byte-Folge enthält ein Bild, das nach dem oben beschriebenen RLE-Verfahren kodiert wurde. Starte "Image-Edit" und rekonstruiere das Bild aus diesen Daten!
        00 09 00 1C 00 0A 01 05 01 02 07 02 01 05 01 0E
        02 06 04 04 05 03 05 05 05 05 04 06 02 0D 01 05
        01 02 07 02 01 05 01 0B 05 07 01 09 01 08 01 04
        04 11 01 05 06 06 01 02 01 08 01 0A
    

  2. Welche Folge für das Bild hätte es, wenn im Datenstrom aus Aufgabe 1 das dritte 00h-Byte fehlen würde?
    Wie würde es sich auswirken, wenn aufgrund eines Übertragunsfehlers statt des Byte 0Dh der Wert 0Ch übermittelt werden würde?
    Könnte man diese Fehler beim Dekodieren "erkennen"?
    Denke dir ein Prüfsummen-Verfahren aus, mit dem man einen so kodierten RLE-Datenstrom daraufhin testen kann, ob beim Übertragen ein Fehler aufgetreten ist, ohne dass dazu das Datenformat erweitert werden muss!
    Kläre, wie "sicher" dieser Test ist!

  3. Einem aufmerksamen Beobachter könnte auffallen, dass in dem Datenstrom aus Aufgabe 1 gelegentlich eine schon zuvor aufgetauchte Bytefolge wiederholt wird, was nach den obigen Ausführungen für eine weitere Kompression genutzt werden könnte. Kannst du solche Wiederholungen finden? Suche dabei nach möglichst langen Bytefolgen!

Andere Grafik-Formate:

Neben dem nicht komprimierenden BMP-Format gibt es eine ganze Reihe komprimierender Formate wie z.B. PNG ("Portable Network Grafic") oder TIFF ("Tag Image File Format"), die alle ein verlustlos komprimiertes Bild transportieren.

Noch stärkere Kompression ist (bisher) nur mit Informationsverlusten zu erreichen. Bei den Grafikformaten GIF ("Grafics Interchange Format") und JPEG ("Joint Photografic Expert Group) kann man beim Abspeichern das Ausmaß der Kompression (und damit den Qualitätsverlust) einstellen.

(Das GIF-Format hat allerdings einen gravierenden Nachteil: seit 1994 bemüht sich die US-amerikanische Firma Unisys darum, Lizenzgebühren von den Benutzern dieses Formats zu erhalten. Die Rechtsposition von Unisys ist unstrittig, lediglich das Geld-Einsammel-Verfahren ist mühsam....{Quelle: c't 3/95})

Seitenanfang


1. Einführung   3. Huffman-Verfahren   4. LZW-Verfahren  

[Index]


Autor: Roland Mechling
Überarbeitet: Jürgen Dehmer
Letzte Änderung: 09.10.2004