Dokumente und Algorithmen, Komprimierung

5 Komprimierung

Aufgaben:

Starten Sie das zu Windows gehörende Programm "Paint" und erzeugen Sie ein neues Bitmap-Bild mit 360 Zeilen zu je 420 Pixel. Lassen Sie Ihrer Kreativität freien Lauf und gestalten Sie innerhalb von 3 Minuten eine schön(e) bunte Graphik. Speichern Sie dann dieses Kunstwerk in dem von Paint angebotenen Standardformat (24-Bit-BMP) unter dem Namen "Kunst.bmp" auf Ihrem privaten Laufwerk ab.

Starten Sie das Programm "I_View", laden Sie Datei "Kunst.bmp" und speichern Sie sie als "Kunst.png" im PNG-Format ebenfalls auf Ihrem privaten Laufwerk ab.
Laden Sie dann in "I_View" die Datei "Kunst.png" und parallel dazu in "Paint" die Datei "Kunst.bmp". Überzeugen Sie sich davon, dass beide Dateien wirklich dasselbe Bild enthalten.

Schließen Sie dann die beiden Graphik-Programme, und schauen Sie sich die beiden "Kunst"-Dateien im Datei-Explorer an. Was fällt auf?

Das in Windows häufig verwendete Graphikformat "BMP" scheint recht verschwenderisch mit dem Festplattenplatz des Benutzers umzugehen. Eine Datei, die dasselbe Bild im "PNG"-Format enthält, ist in der Regel sehr viel kleiner als die entsprechende "BMP"-Datei. Offenbar ist es möglich, dieselbe Bildinformation auch in einer viel kürzeren Byte-Folge zu kodieren. Dies erreicht man durch Komprimierung.

Die allgemeine Grundidee der Komprimierung ist es, beim Kodieren die Wiederholung gleicher Bytefolgen im Datenstrom zu vermeiden. Taucht eine bestimmte Bytefolge das zweite Mal auf, dann wird statt der eigentlichen Bilddaten nur ein Vermerk in den Datenstrom geschrieben, wo genau in den bisher schon geschriebenen Daten die jetzt eigentlich hier her gehörende Bytefolge steht. Beim Dekodieren kann dann diese Bytefolge den schon restaurierten Daten entnommen und an der aktuellen Stelle nochmals eingefügt werden. Obwohl das Grundprinzip also recht einfach ist, sind die Details der verschiedenen Komprimierungsmethoden meist recht kompliziert.

Wir wollen uns daher hier nur 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). Auch 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, die die Anzahl der nun folgenden Pixel dieser Farbe angibt.

Aufgaben:

Entwerfen Sie ein Format zur Kodierung von Schwarz-Weiß-Graphiken, das eine RLE-Kodierung verwendet. Verfassen Sie auf einem DIN-A4-Blatt eine so genaue Dekodierungs-Beschreibung für Ihr Format, dass Ihr Nachbar nur mit Hilfe dieser Beschreibung aus von Ihnen hergestellten Daten das zugehörige Bild rekonstruieren kann. Prüfen Sie dabei u.a., ob Ihre Beschreibung die folgenden Fragen klärt:
- Wie lang kann ein "Lauf" sein? Dies wird z.B. auch durch das verwendete Zahl-Format beeinflußt!
- Wie soll reagiert werden, wenn mehr gleiche Pixel auf einander folgen als in einen "Lauf" passen?
- Werden die Pixelzeilen/-spalten separat kodiert, oder kann ein "Lauf" auch zeilen-/spalten-übergreifend auftreten?
Bemühen Sie sich auf jedem Fall um ein möglichst einfaches Format.

Erstellen Sie mit "ImagEdit" eine Schwarz-Weiß-Graphik beliebiger (aber noch bewältigbarer!) Größe, und speichern Sie sie auf Ihrem privaten Laufwerk unter "gr_rle.bmp" ab. Kodieren Sie dann dieses Bild mit Ihrem in der vorigen Aufgabe entwickelten Verfahren in eine Byte-Folge, die Sie auf ein neues "Daten"-Blatt schreiben.
(Zur Erleichterung dürfen Sie die Bytes dezimal schreiben. Beachten Sie aber, dass ein Byte höchstens den Wert 255 enthalten kann!)

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

Im Falle der Schwarz-Weiß-Graphik 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äßt 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:

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.
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äßt 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 2 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.

Aufgaben:

Die folgende Hex-Byte-Folge enthält ein Bild, das nach dem oben beschriebenen RLE-Verfahren kodiert wurde. Starten Sie "ImageEdit" und rekonstruieren Sie 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

Welche Folge für das Bild hätte es, wenn im Datenstrom aus Aufgabe 5 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"?
Denken Sie sich 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ären Sie, wie "sicher" dieser Test ist!

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

Andere Graphik-Formate:

Neben dem nicht komprimierenden BMP-Format gibt es eine ganze Reihe komprimierender Formate wie z.B. PNG ("Portable Network Grafic"), GIF ("Grafics Interchange Format") und oder TIF ("Tag Image File Format"), die alle ein verlustlos komprimiertes Bild transportieren.
(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})

Noch stärkere Kompression ist (bisher) nur mit Informationsverlusten zu erreichen. Ein solches Grafikformat ist zum Beispiel JPEG ("Joint Photografic Expert Group"); bei diesem Format kann man beim Abspeichern das Ausmaß der Kompression (und damit den Qualitätsverlust gegenüber dem Original) einstellen.

Ganz anders arbeiten die sogenannten Vektor-Grafik-Formate, wie z.B. WMF ("Windows Meta File"), DXF (AutoCAD Drawing eXchange Format) oder EPS ("Encapsulated PostScript"). Bei diesen Formaten werden keine Bild-Inhalte, sondern Bild-Konstruktionsbeschreibungen abgespeichert. Man geht also nicht vom fertigen Bild aus, sondern protokolliert den Entstehungsprozess des Bildes. Dies muss so genau geschehen, dass die aufgezeichneten Daten später zur exakten Rekonstruktion des Bildes ausreichen.

Vektorgrafik hat den Vorteil, dass sie ohne Qualitätsverlust skalierbar ist, weil sie eben keine feste Pixel-Rasterung vorgeben muss. Allerdings sind nur solche Bilder für diese Formate geeignet, bei deren Entstehung eine Konstruktionsbeschreibung aufgezeichnet werden kann: wer ein eingescanntes Photo in eine Vektorgraphik umwandeln will, wird in den meisten Fällen keine befriedigenden Ergebnisse erzielen können.

Weitere Anwendungen von Algorithmen zur Komprimierung:

Komprimierungs-Algorithmen lassen sich nicht nur auf Grafikdateien anwenden, sondern auch auf beliebige Byte-Folgen, also auf alle Sorten von Dateien. Ein weithin bekanntes Kompressionsformat ist das ZIP-Format, bei dem in einer Datei (dem sogenannten ZIP-Archiv) auch mehrere andere Dateien, ja sogar ganze Verzeichnisbäume, in komprimierter Form zusammengefaßt werden können. Speziell bei der Weitergabe von Daten über das Internet hat sich das "Zusammen-Zippen" von Dateien als sehr sinnvoll erwiesen, weil dadurch dieselbe Information insgesamt in sehr viel weniger Bytes übertragen werden kann, als wenn man alle Dateien im Originalzustand einzeln übertragen würde. Dadurch spart man Übertragungszeit. So sind zum Beispiel auch die Lösungsvorschläge zu den Programmieraufgaben aus dem 2. Teil dieses Skriptums in ZIP-Archive gepackt.

Ein Nachteil ist, dass der Empfänger die übermittelten Dateien vor der Verwendung erst noch aus dem ZIP-Archiv herausholen muss. Ein dazu geeignetes Programm ist z.B. "PowerZip". Dieses Programm kann nicht nur die in einem schon vorhandenen ZIP-Archiv enthaltenen Dateien wiederherstellen ("auspacken"), sondern auch Dateien in ein neues ZIP-Archiv schreiben ("einpacken"). Das Programm ist für die nicht-kommerzielle Verwendung frei.

Ein nicht zu unterschätzender zusätzlicher Nutzen bei der Verwendung von ZIP-Archiven ist der damit automatisch vorhandene Schutz gegen Übertragungsfehler: ZIP-Archive werden bei der Herstellung mit entsprechenden Prüfsummen versehen. Falls auch nur 1 Byte eines ZIP-Archivs fehlerhaft übertragen wurde, dann ist es sehr wahrscheinlich (d.h.: praktisch sicher), dass der Dekompressions-Algorithmus beim Versuch, das Archiv auszupacken, scheitert und das Programm den Vorgang mit einer entsprechenden Fehlermeldung abbricht. Wenn Ihnen also die Dekompression eines ZIP-Archives gelingt, dann können Sie ziemlich sicher sein, dass die extrahierten Dateien exakte Kopien derjenigen Dateien sind, die der Absender "eingepackt" hatte.