Bildformate und Bildkompression

Eine Einführung in verschiedene Methoden der Codierung und Komprimierung von Bilddaten (v.a. Rasterbilder)

Ausarbeitung zum Vortrag vom 17. Mai 1999

Ausarbeitung: Horst Rechner (4. Semester)
Seminarleiter: Stanislav Stoev

Wilhelm - Schickard Institut für Informatik
Universität Tübingen

Inhaltsverzeichniß

1. Das Problem
2. Allgemein

2.1 Was ist ein Bildformat ?
2.2 Was ist Kompression ?

3. Verschiedene Repräsentationen von Bilddaten

3.1 Vektordaten
3.2 Rasterdaten

4. Kompressionsmethoden

4.1 Verlustfreie Kompression (oder lossless compression)
4.2 Verlustbehaftete Kompression (oder lossy compression)
4.3 Vergleich lossless und lossy compression

5. Kompressionsphasen

5.1 Vorverarbeitung

5.1.1 Reduktion der Farbtiefe
5.1.2 Konvertierung in den YUV Farbraum und Subsampling

5.2 Transformation mit DCT
5.3 Quantisierung
5.4 Codierung

5.4.1 Run Length Encoding (RLE) (oder Variable Length Coding VLC)
5.4.2 Difference Codierung
5.4.3 Huffman Codierung
5.4.4 Arithmetische Codieriung
5.4.5 LZW Codierung

5.5 Abtastung von Pixelgrafiken

6. Bildaufbau

7. Vergleich verschiedener Bildformate

8. Ausblick

9. Literaturliste

1. Das Problem

Die Problematik der Datencodierung und Kompression ist so alt wie die Geschichte des Computers. Seit es möglich ist, mit hochauflösenden Ausgabegeräten, wie CRTs (Cathode Ray Tubes / Kathodenstrahlröhren) und Druckern, Grafiken darzustellen sucht man auch nach Möglichkeiten, diese Grafiken effizient und platzsparend zu organisieren, zu speichern und zu übermitteln.
Diese Suche hat mit dem Aufkommen von Netzwerken, seien es nun LANs (Local Area Network) oder dem Internet eine neue Dimension erhalten. Nun soll möglichst viel Information über zum Teil schmalbandige Netzwerkverbindungen übermittelt werden.
Gerade das Internet lebt von bunten Bildern und ansprechenden Illustrationen, die die Menschen auf bestimmte Websites locken sollen, und so war es auch dieses Medium, das die Entwicklung von neuen Bildformaten vorangetrieben hat.

Diese Arbeit soll eine Einführung in verschiedene Codierungs- und Kompressiontechniken sein, wobei ein besonderer Augenmerk auf Pixelformate gelegt wird.

2. Allgemein

2.1 Was ist ein Bildformat ?

Ein Bildformat ist eine Struktur oder das Erscheinungsbild einer Ansammlung von Daten, die ein Bild repräsentieren. Dabei ist vor allem auf effiziente Organisation der Daten zu achten.

2.2 Was ist Kompression ?

Kompression ist die gedrängte, kurze Darstellung von Daten, die nur das Wesentliche enthält, und möglichst jegliche Redundanz entfernt. Man sieht sofort, daß es eine Grenze gibt, die der Kompression gesetzt ist, nämlich:

Komprimierte Daten = Unkomprimierte Daten - Redundanz

Redundanz kann man als "unnötige" Daten bezeichnen, also Daten, die für die eigentliche Information nicht wichtig sind, da sie entweder nicht durch das menschliche Auge erkannt werden, oder komprimiert werden können. Z.B. sich wiederholende Muster oder Farbflächen mit einer Farbe.

Das bedeutet, daß Daten, die keine Redundanz enthalten, oder Redundanz enthalten, die nicht durch den verwendeten Algorithmus erkannt wird, nicht komprimiert werden können.

Satz des Informationstheoretikers Shannon (Ref.: xxi)
Es ist nicht möglich, einen Algorithmus zu finden, der jedes Datenmuster ohne Informationsverlust in ein kürzeres komprimiert.

3. Verschiedene Repräsentationen von Bilddaten

3.1 Vektordaten

Der Gedanke, der hinter Bildern im Vektor-Format steckt, ist, daß jedes Bildelement durch seine Paramter gespeichert wird. Zum Beispiel wird ein Kreis durch Mittelpunkt und Radius abgelegt. Diese Vektor-Bilder sind frei skalierbar, und werden nicht "stufig", wenn man sie vergrößert.

Die Postscript Sprache ist eine solche Beschreibungssprache, wobei es in dieser Sprache möglich ist, ein Bild durch eine Kombination von Vektor- und Pixel- Daten in einer Datei zu speichern.
Hier eine Plain-Text Postscript Datei, die folgendes Graustufenbild erzeugt:

circle.ps


%!PS
% "C" takes the following arguments:
% linewidth linegray fillgray X Y r ang1 ang2
/C { %def
  gsave
    newpath 0 360 arc
    gsave setgray fill grestore
    setgray setlinewidth stroke
  grestore
} bind def
3 .5 .9 300 500 200 C
showpage

Vektordaten werden normalerweise nur verlustfrei Komprimiert, da sie normalerweise keine Daten enthalten, die weggelassen werden können (wie z.B. Rauschen).

3.2 Rasterdaten

Eine andere Möglichkeit ist es, ein Bild als Matrix zu repräsentieren, wobei man das Bild erst in Zeilen und Spalten zerlegt, und dann jedem Bildelement (Pixel), das man durch diese Zerlegung erhalten hat einen Farbwert zuweist, der in dieser Matrix abgelegt wird.

ps_circle.bmp


FFFFFFFF FFFFFFFF FFFFFFFF

FFFFFFFF FFFFFFFF FFFFFFFF

FFFFFFFF 7D7D7D7D 7D7D7D7D

Dies ist ein Ausschnitt aus der Bitmap-Datei des Kreises in Hexadezimal Ansicht. Es sind fast alle Werte mit FF belegt. Dies bedeutet, daß in diesem Bereich die Pixel Weiß sind, und dann nach Grau übergehen (7D7D7D).

Eine solche Repäsentation ergibt eine viel größere Datenmenge als ein Vektorbild. Z.B. hat der Kreis oben im PNG-Format (Rasterformat) eine Größe von 6 KB, und als Postscript-Datei eine Größe von 1 KB.
Um die Datenmenge eines Rasterbildes, die auch redundante Information enthalten kann zu verkleinern, benützt man sowohl verlustfreie, wie auch verlustbehaftete Kompression.

Um zu veranschaulichen, wie groß die Datenmengen sind, die bei Rasterbildern auftreten können, hier ein paar Berechnungen:
Die Größe eines Bildes (oder einer Serie von Bildern) berechnet sich durch:
Breite x Höhe x Farbtiefe (x Bilder pro Sekunde)
Die Farbtiefe gibt die mögliche Anzahl von Farbnuancen an. Bei 24 Bit sind dies ca. 16 Millionen.
z.B. braucht man für ein Bild der Größe 1024 x 768 Pixel mit 24 Bit Farbtiefe 2,3 Megabyte Speicher.

Das Argument, das Speichermedien eine immer größere Datenmenge zu immer niedrigeren Kosten aufnehmen können ist zwar angebracht, doch sind bei bewegten Bildern die Datenmengen so groß, daß hier eine Kompression stattfinden muß, um die Daten auf eine akzeptable Größe zu reduzieren.

Z.B. tritt bei einem Film mit 320 x 200 Pixel und 24 Bit Farbtiefe bei einer Bildrate von 25 bps ein Datenvolumen von 4,6 MB pro Sekunde, oder 16,1 Gigabyte pro Stunde auf. Das würde bedeuten, daß man 100 CDs brauchen würde, um "Vom Winde verweht" in dieser Auflösung zu speichern. Man sieht, daß hier Datenkompression unumgänglich ist, um sowohl die Übertragungszeit über Netzwerke, als auch das Datenvolumen zu minimieren.

4. Kompressionsmethoden

Unterschiedliche Bilddaten verlangen nach unterschiedlichen Kompressionsmethoden. Im Groben kann man zwei Kompressionsarten unterscheiden:

4.1 Verlustfreie Kompression (oder lossless compression)

"Qualität vor Geschwindigkeit"

Verlustfreie Kompression wird vor allem dort eingesetzt, wo mit teueren, schwer zu beschaffenden oder aufwendig zu berechnenden Bilddaten gearbeitet wird. Hier ist jede Bildinformation wichtig. Es findet also keine Reduktion der Daten statt.
Einsatzgebiete sind z.B. Satellitenbilder, medizinische oder künstliche Bilder.
Bei künstlich erzeugten Bildern kommt noch hinzu, daß diese meist keine Redundanz im Sinne von Rauschen oder ähnlichem enthalten, sodaß hier eine verlustbehaftete Kompression sicherlich nur wichtige Bildinformation zerstören würde. Das selbe gilt für Schwarz-Weiß Zeichnungen und ähnlichen Bildern.

Formate die lossless compression unterstützen sind z.B.:
BMP, GIF, PNG, JPEG, TIF

4.2 Verlustbehaftete Kompression (oder lossy compression)

"Geschwindigkeit vor Qualität"

Diese Kompressionsart wird verwendet, wenn Bildinformation übertragen werden muß, bei der Details nicht den Informationsgehalt des Bildes bestimmen. Hier findet eine Reduktion der Bilddaten statt, sodaß das Urprungsbild nicht 1:1 wiederherstellbar ist. Die Fehler, die bei zu starker Datenreduktion sichtbar werden, nennt man Artefakte.
Einsatzgebiete sind z.B. digitales Fernsehen, Telekonferenzen, Bilder im Internet.
Bei Netzwerken wie dem Internet kommt noch hinzu, daß die Übertragungsgeschwindigkeiten meist sehr niedrig sind, und da lossy compression vor allem bei True-Color Bildern eine viel höheren Kompressionsfaktor erreicht als lossless compression, wählt man hier diese Kompressionsart.

Formate die lossy compression unterstützen sind z.B.:
GIF, JPEG, Wavelet

GIF und JPEG unterstützen sowohl lossless als auch lossy compression, da bei diesen Formaten der Benutzer manuell den Kompressionsfaktor regulieren kann, und diesen auch auf Null herabsetzen kann. Was bei dieser Regulierung im JPEG-Format passiert wird im folgenden noch erklärt.

4.3 Vergleich lossless und lossy compression

a) earth_lossless.png (42 KB)	b) earth_lowlossy.jpg (19 KB)
lossless	lossy / niedrige Kompression
c) earth_highlossy.jpg (4 KB)	d) earth_lossydetail.jpg
lossy / hohe Kompression	Detail aus c)

Das gleiche Bild wurde in verschiedenen Formaten abgespeichert. Bild a) wurde in einem verlustfreien Format abgespeichert. Bild b) wurde im lossy JPEG-Format gespeichert. Man sieht, daß bei einer Erhöhung des Kompressionsfaktors, und damit einhergehend einer drastischen Verkleinerung der Dateigröße kaum Artefakte auftauchen (Bild b) nach c) ). Um Fehler sichtbar zu machen, wurde ein Detail aus Bild c) vergrößert. Bei Erhöhung der Helligkeit und des Kontrasts erkennt man klar Fehler, die sich als Aura um die hellen Gebiete des Bildes manifestieren. Bei noch höherer Kompression sind diese Fehler auch im unvergrößerten Bild sichtbar. Die Erhöhung des Kompressionsgrads im JPEG-Format führt auch dazu, daß das Bild an Schärfe und Kontrast verliert.

5. Kompressionsphasen

Die Kompression von Pixeldaten vor der Speicherung in das endgültige Bildformat läuft immer in 4 Schritten ab, wobei nicht alle dieser Schritte bei allen Formaten vorkommen müssen. Bei verlustfreien Verfahren wird nur Codierung angewendet.

5.1 Vorverarbeitung

Die Vorverarbeitung ist ein verlustbehafteter Schritt des Kompressionsvorgangs.

5.1.1 Reduktion der Farbtiefe

Eine Form der Vorberarbeitung ist die Reduktion der Farbtiefe von 32 nach 24 Bit.
Dabei tritt keine sichtbare Verschlechterung des Bildes auf, da das menschliche Auge nur ca. 100.000 Farbstufen (2¹⁷ Farben) unterscheiden kann. Da dies aber 2 Byte und einem Bit Farbinformation entspricht, wählt man die nächstgrößere Anzahl von ganzen Bytes. Also 3 Byte = 24 Bit. Somit erhält man 2²⁴ Farben. Also wird jedem Punkt 3 Byte Farbinformation zugeordnet, was etwa 16 Millionen möglichen Farben entspricht.

5.1.2 Konvertierung in den YUV Farbraum und Subsampling

Die Farbinformation von 3 Byte teilen sich in jeweils 1 Byte für jeden Farbkanal auf. Man erhält 256 mögliche Farbnuancen für Rot, Grün und Blau.
Dies entspricht dem additiven RGB Modell. In diesem Farbmodell steckt die Helligkeitsinformation in jeder Farbkomponente, was sich für das chrominance subsampling als nachteilig erweist. Deshalb führt man eine Konvertierung vom RGB in den YUV Farbraum durch. Im YUV Farbraum steckt die Helligkeitsinformation nur in der Y-Komponente (U ist die Rot-Grün Balance und V die Gelb-Blau Balance).
Das menschliche Auge hat verschiedene Auflösungsvermögen, was Helligkeits- und Farbnuancen betrifft. Auf der Retina befinden sich ca. 120 Millionen Stäbchen, die auf Helligkeit ansprechen, und 6 Millionen Zapfen, die auf die unterschiedlichen Farben ansprechen. Deshalb ist es möglich diese Informationen verschieden zu gewichten. Dieser Schritt wird als chrominance subsampling bezeichnet. Hier wird die Y-Komponente, also die Helligkeit mit voller Auflösung abgetastet, und die anderen beiden Komponenten U und V mit halber Auflösung. Es werden also zwei Pixel zu einem interpoliert.
Die Gewichtung kann entweder 4:2:2 erfolgen, also 100% Y-Auflösung, und 50% Farbauflösung, oder 4:1:1. Man bekommt also 3 Bilder verschiedener Größe: dasY-Layer hat volle Größe und die U- und V-Layer sind jeweils halb oder ein viertel so groß wie das Y-Layer.
Hinzu kommt, daß in einem Bild Regionen mit gleicher Helligkeit häufiger vorkommmen, als Regionen mit gleichen RGB werten. Somit wird hier noch zusätzlich eine stärkere Kompression der Y-Komponente begünstigt.

Ausgangsbild	RGB-Layer	YUV-Layer	YUV-Layer
			Nachbearbeitet

In der Bildtabelle erkennt man, wie die Helligkeit von der Farbigkeit im YUV-Modell getrennt wird. Die nachbearbeiteten YUV-Layer sollen verdeutlichen, daß bei diesem Beispielbild im YUV Farbraum eine viel stärkere Kompression angewendet werden kann, als beim Bild im RGB-Farbraum, da ein Layer fast vollständig Schwarz ist. Dieses Layer kann danach z.B. mit einer RLE-Codierung auf einen Bruchteil der ursprünglichen Größe komprimiert werden.

5.2 Transformation mit DCT

Unter Transformation versteht man die Konvertierung der einzelnen Farbwerte der Pixel einer Zeile, welche eine Kurve mit diskreten Werten beschreiben in einen anderen Raum. Bei Bildformaten wird vor allem die diskrete Cosinus-Transformation angewendet, die die Farbwerte dann als eine Überlagerung von Cosinus-Wellen darstellt. Diese Abbildung ist bijektiv. Man kann also aus den DCT-Koeffizienten die ursprünglichen Pixelfarbwerte ohne Verlust zurückrechnen.

In dieser Arbeit wird das JPEG-Format nicht explizit herausgegriffen, da es sich im wesentlichen durch die Schritte Transformation mit DCT und Quantisierung auszeichnet, die aber auch in anderen Bildformaten vorkommen können. Die DCT-Transformation ist der zentrale Teil des JPEG-Verfahrens.

Zur Transformation wird das Ausgangsbild zuerst in 8x8 Blöcke zerlegt, auf die dann die DCT angewendet wird. Dies wird deshalb gemacht, da der 1D-DCT Algorithmus in O(n*log n) liegt, und sich daher die Anwendung auf größere Blöcke negativ in der Rechenzeit auswirken würde. Außerdem wird bei dieser Zerlegung gewährleistet, das sich die Farb-, und Helligkeitswerte in den Blöcken in einer normalen Photographie nicht sehr unterscheiden (außer bei Kanten), und dadurch eine gute Kompression erreicht wird. Es existieren also nun 3 Layer (Y, U und V), die jeweils in 8x8 Blöcke zerlegt sind.
Die Transformation im Zweidimensionalen wird durch folgende Formel, die 2D-DCT, erreicht, deren Laufzeit auch durch eine Zerlegung des Bildes in Blöcke begünstigt wird:

hierbei sind i und j die jeweiligen Positionen der Helligkeitswerte f(i,j) (im Y-Layer. Entsprechend der Farbwerte in den anderen beiden Layern) der Pixel im Ausgangsblock, und u, v die Position der Amplituden F(u,v) in der Zielbitmap. Die Zielbitmap enthält jetzt natürlich keine Farbinformation mehr, sondern eben die Amplituden der jewiligen Cosinus-Frequenzen. Die Frequenzen steigen mit dem Betrag von u und v. Im Zielblock stehen nun die Frequenzamplituden
Da u und v in jedem 8x8 Block immer nur von 0 bis 7 laufen können erhält man also eine mögliche Überlagerung von 64 Grundfunktionen, die jeweils verschieden stark gewichtet werden.

Diese Grafik stellt alle 64 Grundfunktionen dar. Wobei jede einzelne der Funktionen bei der Zurückrechnung in ein Bild natürlich einen ganzen 8x8 Block überdeckt..Wie man sieht enthält das Kästchen (0,0) den niederfrequentesten Anteil, sozusagen den Gleichstromanteil oder direct current coefficient (DC). Je weiter man fortschreitet, desto höher wird die Frequenz. In x-Richtung steigt die Frequenz der horizontal überlagerten Cosinus-Welle, und in y-Richtung entsprechend die Frequenz der vertikal überlagerten Cosinus-Welle. Die Koeffizienten der Felder ungleich (0,0) werden als der Wechselstromanteil, oder alternating current coefficient (AC) bezeichnet.
Zerlegt man einen Pixel-Block in sein Cosinus-Spektrum, so wird der Mittelwert der Helligkeitswerte im DC-Koeffizienten abgelegt, und Schwankungen in der Helligkeit in den AC-Koeffizienten verteilen. Hat man also einen Block mit gleicher Helligkeit, so sind alle AC-Koeffizienten gleich 0. Genau dies ist auch Sinn der DCT: Die Konzentration der Daten auf wenige Koeffizienten.

Wie schon angesprochen ist diese Abbildung, wenn man von der Rechenungenauigkeit bei Matrizenmultiplikation einmal absieht, bijektiv (also lossless), da man durch die Überlagerung der Grundfunktionen praktisch jeden möglichen Pixelwert im ursprünglichen 8x8 Block erreichen kann. Der eigentlich verlustbehaftete Schritt ist die Quantisierung.

5.3 Quantisierung

Bei der Quantisierung werden wieder die 8x8 Blöcke betrachtet, die jetzt mit den Cosinus-Amplituden gefüllt sind.
Man teilt jeden Koeffizienten durch einen gemeinsamen Faktor. Die Größe dieses Faktors wird durch den Benutzer im Grafikprogramm festgelegt. Je größer dieser Faktor ist, desto gröber wird das Bild. Dieser Faktor wird gemeinsam mit dem 8x8 Block in den Enddaten gespeichert.

Quelle: Anwendung eines Applet von Markus Schumacher, Christian Herzog and Olav Gröhn, TH-Darmstadt (http://www.fh-jena.de/contrib/fb/et/personal/ansorg/dct/dct/applet.html)

In diesem Bild sieht man klar die Auswirkungen einer zu starken Quantisierung sehen. Nach dieser Quantisierung bleibt nur noch der DC-Koeffizient übrig. Somit haben wir für jeden der 8x8 Blöcke einen Helligkeits- und Farbwert, was sich direkt im Bild niederschlägt.

An die Quantisierung wird normalerweise noch eine Codierung der Daten angeschlossen.
Da in jedem 8x8 Block nach der Quantisierung viele der hochfrequenten AC-Koeffizienten Null werden, steckt somit die Hauptinformation dieses Blocks in den DC-Koeffizienten und den niederfrequenten AC-Koeffizienten. Wenn man diese 64 Koeffizienten noch günstig anordnet, so ist danach eine noch stärkere Kompression z.B. mit RLE möglich.

Als Methode zur Umordnung der Koeffitienten wird die Matrix im Zick-Zack Kurs abgetastet. Somit erhält man aus dem 8x8 Block einen 1x64 Vektor, in dem die niederfrequenten Amplitudes oben, und die hochfrequenten (die ja meist Null sind) unten stehen,
Außer der besserern Kompression ist es jetzt auch möglich einen progessiven Aufbau (umgesetzt in Progessive JPEG-Format) des Bildes zu realisieren, indem man erst einmal die DC-Koeffizienten liest, diese Umrechnet, und als Bitmap auf dem Bildschirm darstellt. Dann werden sukzessive die weiteren AC-Koeffizienten umgerechnet. Somit erhält man schon nach kurzer Übertragungszeit einen ungefähren Eindruck des Bildes.

5.4 Codierung

Codierung kommt in fast allen Bildformaten vor, da sie zu keinem Datenverlust führt. Hierbei wird die Ausgangsdatenmenge über eine bijektive Abbildung in eine möglichst kleinere oder gleich große Datenmenge überführt. Die im folgenden beschriebenen Codieralgorithmen kommen auch in anderen Bereichen der Informatik vor, da sie auf beliebige Datenstrukturen angewendet werden können, und nicht auf Bilddaten beschränkt sind.

Als Ausgangswort wird immer die Zeichenfolge "HAAAALLO" codiert. Gleichwohl kann eine Bitmap Repräsentation eines Bildes als Ausgangswort angenommen werden.

5.4.1 Run Length Encoding (RLE) (oder Variable Length Coding VLC)

Bei diesem Verfahren wird das wiederholte Auftreten von Symbolen durch die Angabe der Häufigkeit ersetzt.

Wie man sieht, wird das 2 Mal auftretende L nicht codiert, sondern nur übernommen. Das liegt daran, daß man durch die Codierung keinen Speichergewinn erhalten würde.

Beispiel:

Das Windows BMP-Format bietet RLEncoding an:

a) 12 KB	b) 2 KB

Diese zwei Muster wurden mit RLE Komprimiert. Die Variante des RLEs im BMP-Formats arbeitet zeilenweise, was zu keiner Kompression beim ersten Muster führt. Zur Anzeige wurden die Bilder in das PNG-Format konvertiert. Die Originaldateien sind unter rle_horizontal.bmp und rle_vertikal.bmp zu finden.
Um eine bessere Kompression bei beliebigen Bildern zu erreichen, wäre es möglich die Abtastung nicht nur in einer Richtung zu betreiben, sondern z.B. als Peano Kurve. Diese Variation der Abtastung bietet sich auch für andere Codierungsverfahren an, und wird später noch einmal angesprochen.

5.4.2 Difference Codierung

Wie schon im Namen angedeutet wird hier eine Differenz gebildet. In der einfachsten Veriante werden die Farbwerte von zwei Zeilen voneinander abgezogen, und die Differenz abgelegt.

In diesem Beispiel wurden die ASCII Werte der Buchstaben voneinander abgezogen. Bei gleichen Symblen taucht also der Wert 0 auf. Hier werden vor allem geringe Abweichungen in vertikaler Richtung sehr gut berücksichtigt. Wenn man also Bild 5.4.1.a) difference Coden würde, würde man folgenden Code erhalten:

Bei nachfolgender Anwendung von RLE kann man diese Daten auf einen Bruchteil der Ursprungsdaten komprimieren.

5.4.3 Huffman Codierung

Das Prinzip beim Huffman Coding ist eine stochasitsche Auswertung des Codes vor der Codierung. Danach wird ein Algorithmus eingesetzt, der häufig vorkommenden Symbolen einen kurzen, und selten vorkommenden Symbolen einen langen Code zuordnet.

An dem Beispiel von "HAAAALLO":
Zuerst wird eine Tabelle mit der relativen Warscheinlichkeit für das Auftreten von Symbolen angelegt:

Danach werden die 2 Symbole mit der kleinsten Warscheinlichkeit zusammengefaßt und die Warscheinlichkeiten addiert. Diesen Symbolen wird jeweils die Ziffer 0 und 1 zugeordnet indem sie an den bestehenden Code vorangestellt werden. Dieser Prozess wird wiederholt, bis alle Symbole zusammengefaßt sind, und wir wieder die Gesamtwarscheinlichkeit 1 erhalten.

Die am seltendsten austretenen Symbole "H" und "O" erhalten den längsten Code, und "A" den kürzesten.

Aus dieser Codierungstabelle läßt sich auf folgender Baum generieren: der Huffman-Baum. Folgt man den Ästen, so erhält man den dem jeweiligen Symbol zugehörigem Code.

Dieser Code ist eine Bijektion mit Präfixabgeschlossenheit, was bedeutet, daß man durch Hinzufügen einer Binärzahl zu einer gegebenen Repräsentation eines Zeichens kein anderes erhält.
Z.B. ergibt "001" (für "O") durch hinzufügen von "0" oder "1" keinen gültigen Code. "1001" oder "0001" ist nicht in der Tabelle enthalten.

5.4.4 Arithmetische Codieriung

Die Arithmetische Codierung ist eine Übertragung des Huffman-Prinzips in die reellen Zahlen. Hierzu wird jedem Symbol wieder seine relative Häufigkeit zugeordnet.

Entsprechend seiner Häufigkeit wird in Spalte 3 der Tabelle jedem Symbol ein halboffenes Intervall im Bereich zwischen [0 - 1) zugeordnet. In unserem Beispiel wird "H" das Intervall [0 - 0,125) zugewiesen.

Bei der Codierung des Eingabewortes geht man dann folgendermaßen vor:
Man betrachtet das erste Symbol, und schränkt das Gesamtintervall [0,1) auf das Symbolintervall ein (siehe unten). Danach wird dieses Intervall, also hier [0 - 0,125), als Gesamtintervall für die weitere Codierung betrachtet. Entsprechend der Codierungstabelle berechnet man für dieses Intervall wieder eine Einengung für das nächste Symbol, usw. bis das letzte Symbol abgearbeitet ist.

Die neuen Intervalle berechnen sich mittels der Formel:
[US + UZ (OS - US), US + OZ (OS - US))
wobei US die untere Schranke des vorhergehenden Intervalls ist, und OS entsprechend die obere. UZ und OZ sind die Grenzen des zu codierenden Zeichens.

Im folgenden werden die jeweils betrachteten Symbole mit den zugehörenden Intervallen für das Beispielwort aufgezeigt:

Nach abarbeiten des letzten Symbols erhalten wir also [0,03582763671875 - 0,035888671875) als Teilintervall, das die Zeichenkette "HAAAALLO" eindeutig identifiziert.
Wie man sieht, wäre hier der zu übermittelnde Code viel länger als die ursprünglich zu übermittelnde Zeichenkette. Aber da eine beliebige reelle Zahl aus diesem Intervall die Zeichenkette eindeutig identifiziert greift man sich natürlich eine Zahl heraus, die nach möglichst wenig Nachkommastellen abbricht. In diesem Beispiel also die 0,03588 die man zusammen mit der Warscheinlichkeitstabelle übermittelt.

Die Decodierung geht entsprechend rückwärts. Man betrachtet die Ausgangszahl R, also hier 0,03588, die in einem Symbolintervall liegt, und bildet diese Zahl mittels der Formel:
R = (R - UZ) / (OZ - UZ)
auf eine neue Zahl R ab, die jetzt wiederum in einem anderen Symbolintervall liegt. Man decodiert von hinten, wobei hier wichtig ist, die Länge des Ausgangswortes zu kennen (diese wird mitübermittelt), da man nach dem eigentlich letzten Decodierungsschritt weiter machen könnte, und so Symbole erhalten würde, die gar nicht mehr zum Ausgangswort gehören.

5.4.5 LZW Codierung

In diesem Abschnitt wird die einfachste Variante (LZ78) des von Lempel, Ziv und Welch erfundenen Algorithmus vorgestellt. Eine andere Variante dieses Algorithmus wird auch in PKZIP oder GZIP zur Kompression benutzt.

Das Prinzip des Algorithmus ist ein Wörterbuch, das aus einem statischen und aus einem dynamischen Teil besteht. Der dynamische Teil, muß im Gegensatz zum statischen Teil nicht mit dem Code übermittelt werden, da er sowohl beim Codieren als auch beim Decodieren aufgebaut werden kann.
Das statische Wörterbuch besteht aus allen Einzelsymbolen, denen nach der Reihenfolge des Auftretens Zahlen zugeordnet werden. Diese Zuordnung wird als Ausgangsschlüssel bezeichnet. Also in unserem Beispiel:

Um das dynamische Wörterbuch aufzubauen, wird die aktuell längste im Wörterbuch vorkommende Zeichenkette betrachtet, also hier "H", und dann mittels der existieren Schlüssel codiert. Dann wird zu dieser Zeichenkette ein weiteres Symbol aus dem Eingabestrom hinzuaddiert, und dieses Wort ("HA") bildet nun einen neuen Schlüssel. So wird das dynamische Wörterbuch aufgebaut. Dieses neu aufgenommene Wort kann jetzt zur Codierung der weiteren Eingabe genutzt werden. Dies wird fortgesetzt, bis der Eingabestrom komplett codiert ist.

Im folgenden wird unser Beispielwort codiert. Die fett gedruckten Zeichen markieren die Zeichenkette, die neu in das dynamische Wörterbuch aufgenommen wird.

Man muß hier nur das statische Wörterbuch und den Ausgabecode übermitteln.

Die Decodierung geht entsprechend. Wobei man hier nicht wie bei der Codierung "vorausschauend" das dynamische Wörterbuch aufbaut, sondern "zurückblickend".
In unserem Beispiel: (die fett gedruckten Symbole, sind die aktuell zu decodierenden Symbole.

5.5 Abtastung von Pixelgrafiken

Wie bereits in Abschnitt 5.4.1 gesehen variiert die Effizienz vom Codieralgorithmen sehr stark mit den Datenmustern auf denen sie arbeiten. Bei RLE ist diese Varianz sehr gut nachzuvollziehen.
In der einfachsten Variante von Bildformaten werden Codieralgorithmen zeilenweise Spalte für Spalte angewendet. Somit wird nur unter Umständen eine gute Kompression erreicht. Dieses Problem kann man durch verschiedene Methoden lösen.
Entweder kennt man die Strukturen auf denen die Algorithmen arbeiten müssen (z.B. gleichartige Bilder mit minimalen Variationen) und kann die Abtastrichtung manuell anpassen, oder man geht von einer Tatsache aus, die sich auch das JPEG-Bildformat zu nutzen macht. Denn oft enthalten eng beieinander liegende Punkte gleiche Farb- oder Helligkeitswerte, sodaß man die Abtastung z.B. als Kurve (Peano) implementieren kann.

6. Bildaufbau

Viele Bildformate folgen einem bestimmten Aufbau, der in folgender Tabelle zusammengefaßt ist. Es ist klar, das nicht alle Teile in einem Bild vorkommen müssen. Z.B. existiert in einem JPEG Bild kein Control Block, oder in einem GIF-Bild keine Quantisierungstabelle.

Bezeichnung	Repräsentanten	Kommentar / Beispiele
Header	Erkennungssequenz, Versionsnummer, Breite & Höhe & Farbtiefe, Quantisierungstabelle, Huffman Tabelle, Sonstiges (z.B. Kommentare vom Ersteller)	GIF89a.......3.3.f.......,.. ........(..................H .....:`....L.......[..; Der Code eines kompletten GIF-Bildes, der Version 89a.
Control Block	Zeitliche Verzögerung, Transparenzfarbe
Palette		In diesem Block wird jedem vorkommenden RGB-Wert im Bild eine Nummer von 1 bis n zugeordnet. Mit diesen Schlüsseln wird dann der Bilddatenblock des Bildes gefüllt (siehe unten). In diesem Beispiel hat der Eintrag 1 den RGB-Wert (0,0,0). Dieses Verfahren wird nur bei 8-Bit (oder weniger Bit) Bildern angewendet, da bei 24-Bit Bildern, bei denen theoretisch das ganze RGB-Spektrum vorkommen könnte, keine Datenreduktion durch Palettenbildung stattfinden würde.
Bilddaten (Bitmap)	Entweder sind hier Verweise in die Palette, oder der RGB Code eines Pixels, oder die AC und DC Werte bei JPEG Bildern eingetragen.	Mit Palette: 5,7,4,10,14,40,...
		Ohne Palette: (124,243,222), (222,123,3)

Control Block, Palette und Bilddaten treten bei Bildern, die Bildsequenzen in sich tragen, also z.B. Animated GIFs, mehrmals hintereinander auf. Hier muß entweder im Header oder im ersten Control Block noch gesagt werden, wieviele Bilder sich in dieser Datei befinden, und wie oft sie wiederholt werden sollen.

7. Vergleich verschiedener Bildformate

In diesem Kapitel soll nur ein grober Vergleich der gängigen Bildformate gemacht werden. Zu vielen dieser Formate ist die Spezifikation frei erhältlich.

Die Vor- und Nachteile der einzelnen Formate lassen schon schließen, daß die Suche mach dem besten Bildformat keine Pauschalantwort zuläßt. Man muß immer vom Anwendungsgebiet ausgehen. Sowohl lossless- also auch lossy-Verfahren haben ihre Daseinsberechtigung.

8. Ausblick

Aus der Tabelle kann man entnehmen, daß man mit lossy-Verfahren bei Photographien sehr viel höhrere Kompressionsraten als mit lossless Verfahren erreicht. Ein vorgestelltes lossy-Verfahren wurde im JPEG-Format umgesetzt. Doch ist dies keineswegs das Ende der Fahnenstange.
Bei JPEG wird mit der DCT-Transformation, also mit sich überlagernden Cosinus-Wellen gearbeitet. Es wäre doch erstrebenswert durch die Überlagerung beliebiger Funktionen, die auf das Bild hin optimiert sind, einen noch höheren Kompressionsgrad zu erreichen. Genau dieses wird mit der Wavelet-Transformation ereicht. Hier werden unterschiedliche Funktionen überlagert, die zwar nicht auf jedes einzelne Bild angepaßt werden, aber trotzdem einen noch höheren Kompressionsfaktor erreichen.
In dieser Ausarbeitung wurden Wavelet-Transformation und Fraktale Kompression nicht behandelt, da sie den Rahmen einer Einführung in Bildformate sprengen würden.
In der folgenden Grafik werden 3 Transformationen im Hinblick auf ihren mittleren Fehler verglichen.
Auf der x-Achse sind die Kompressionsfaktoren 1:10, 1:15, 1:25, 1:35, 1:50 und 1:100 abgetragen, und auf der y-Achse der mittlere Fehler in Prozent (Root Mean Square in Prozent) der einzelnen Pixel im komprimierten Bild im Vergleich zum Ausgangsbild.
Der Versuch wurde von Dietrich Thie (TU Chemnitz) mit folgendem Graustufenbild durchgeführt, das in voller Auflösung und zusammen mit den Versuchsergebnissen unter http://archiv.tu-chemnitz.de/pub/1998/0010/data/vortrag/dth/pictures.html zu finden ist.

9. Literaturliste

i.) Gunter Dünnbier:
Spezifikation von Pixel-Grafik Formaten
unter http://www.druckerei-duennbier.com/grafik01.htm
ii.) -, Fernhill Press Incorporated.:
Spezifikation von Pixel-Grafik Formaten
unter http://www.fernhillpress.com/gformats.htm
iii.) Ralf Pichler, Uni Siegen:
Bild- und Videokompression allgemein
unter http://www.student-online.de/Hausarbeiten/Informatik/Bild-_und_Videokompression_1/
iv.) Klaus Eppele, Conware Netzpartner GmbH:
Bildkompression mit JPEG
unter http://www.conware.de/Artikel/cihv3.html
v.) W.B. Pennebaker, J.L. Mitchell:
The JPEG Still Image Data Compression Standard, Van Nostrand Reinhold, 1993,
unter http://www.cs.sfu.ca/cs/CC/365/li/material/notes/Chap4/Chap4.2/Chap4.2.html
vi.) Seán Keating, Dublin City University:
Project Report Towards Hardware Implementation of the 2D-DCT Image Processing Algorithm
unter http://homepages.iol.ie/~skeating/dct/2ddct.htm
vii.) Lee Daniel Crocker:
The PNG Image Format
unter http://216.121.56.215/works/png.html
viii.) Dietrich Thie, TU Chemnitz:
Vergleichende Betrachtung von Verfahren zur Bildkompression
unter http://archiv.tu-chemnitz.de/pub/1998/0010/data/vortrag/dth/pictures.html
ix.) Jörgen Hedlund, University of Karlskrona/Ronneby:
Run-Length Encoding (RLE)
unter http://trinity.rsn.hk-r.se/joik/Compression/rle.html
x.) Stephan Frings, Forschungszentrum Jülich:
Struktur von Netzhaut und Photorezeptoren
unter http://www.fz-juelich.de/ibi/ibi-1/stefring/photor/phore01.htm
xi.) Frank Gadegast, Technische Universität Berlin:
Pixel-Grafik Formate allgemein
unter http://www.gadegast.de/diplom/kap232.htm
xii.) Prof. Dr.-Ing. Jürgen Ansorg, Fachhochschule Jena:
WWW-Grafikformate
unter http://www.fh-jena.de/contrib/fb/et/personal/ansorg/ftp/png/formate.htm
xiii.) -, Data Compression Reference Center:
The LZW Algorithm
unter http://www.cs.usyd.edu.au/~loki/cs2csys/gif-info/lzw.html
xiv.) -:
Theory of Arithmetic Coding
unter http://www.brunel.ac.uk/~dc96ppd/pa1.htm
xv.) Dr. Andreas Uhl, Department of Computer Science - Universität Salzburg:
Computergrafik allgemein
unter http://www.cosy.sbg.ac.at/~azunzer/Lossless/skogler/lossless.html
xvi.) Prof. Alan McDonald / Brunel University, London:
Image and Video Compression - Skript zur Vorlesung: Coding for Compression and Data Security
xvii.) J. Encarnacao, W.Straßer und R. Klein:
Graphische Datenverarbeitung, Band II, Oldenburg 1997, Seite 269ff
xviii.) Ralf Hüsing, Universität Frankfurt am Main:
Psycho-physiologische Bildkodierung
unter http://www.informatik.uni-frankfurt.de/~brause/SemSS96/psyphys.ps.zip
xix.) Carsten Rocks, Universität Frankfurt am Main:
Fehlerfreie Bildkompression
unter http://www.informatik.uni-frankfurt.de/~brause/SemSS96/lossless.ps.zip
xx.) Silvio Levy:
The Peano Curve and Fractal Curves
unter http://freeabel.geom.umn.edu/docs/reference/CRC-formulas/node36.html
xxi.) PD Dr. Rüdiger Brause, Carl von Ossietzky Universität Oldenburg:
Skript zum Seminar: Bildkomkression und semantische Bildkodierung
von Carsten Rocks