Einleitung
kap1: wahrnehmung
kap2: das digitale bild
kap3: die digitale aufnahme
kap4: das jpeg-verfahren
kap5: farbraumveränderung
kap6: dct
kap7: quantisierung
kap8: codierung
kap9: de-codierung
kap10: dateitypen
kap11: jpeg2000
resümee
quellen
autoren


< Kapitel 7 Kapitel 9 >

8 Codierung


Nach der Quantisierung der 8*8 Blöcke werden nun alle Werte codiert, um weiteren Speicherplatz zu sparen. Dieses geschieht üblicherweise mit der sogenannten Huffman-Codierung, die die Werte in Binärcode umwandelt und es sich dabei zu Nutzen macht, dass bestimmte Werte häufiger vorkommen als andere. Warum es für das Komprimieren förderlich ist, wie es funktioniert und wie man die 8*8-Blöcke vorher vorbereiten muss, sehen wir im Laufe dieses Kapitels.


8.1 Zick-Zack-Umsortierung

Durch das Quantisieren sind viele Null-Werte entstanden, was ja auch unsere Absicht war, um Redundanzen zusammenfassen zu können. Aus Kapitel 2.4 wissen wir, dass Werte gruppiert werden können, wenn sie hintereinander stehen. Damit das in unseren 8*8-Matrizen der Fall ist, muss man sie im Zick-Zack Kurs ablesen, denn dann stehen möglichst viele der beim Quantisieren entstandenen Nullen hintereinander.



Man liest die Werte einer 8*8-Matrix im dargestellten Zick-Zack-Verfahren ab, um so die häufig auftretenden Nullen am Ende der Matrix zu gruppieren.

Nun haben wir die Werte hintereinander aufgeschrieben, die 8*8-Matrix also in einen 1x64-Vektor umgewandelt. Grundlage für die Erstellung eines so genannten Huffman-Codes ist nun eine stochastische Verarbeitung der Werte, die die Matrix enthält, denn es ist wesentlich zweckmäßiger, häufig auftretenden Werten einen kurzen Code und seltener vorkommenden Werten einen langen zu geben, als jeden einzelnen Wert ungeachtet, wie oft er auftritt, mit der gleichen Codelänge zu verschlüsseln.


8.2 Huffman-Codierung: Stochastische Auswertung

Bevor wir den Huffman-Code auf unseren Vektor anwenden, demonstrieren wir das System der stochastischen Auswertung, indem wir folgendermaßen statt 64 verschiedenen Zahlenwerten ein herkömmliches Wort codieren, bestehend aus bestimmten der 26 Buchstaben des Alphabets, was etwas anschaulicher sein dürfte. Als Beispiel sei hier die beliebte Begrüßung unserer ehemaligen Mathematiklehrerin willkommen, die da heißt: "MOORJEEEN". Wir wollen für dieses Wort nun einen einzigartigen Code finden, der ohne Zweifel decodierbar ist. Dies ist eine wichtige Voraussetzung, denn wir wollen auf Trennzeichen zwischen den Codes verzichten (um nicht unnötig Speicher zu belegen) und automatisch erkennen, wo ein Buchstabe anfängt und aufhört.

Zunächst bestimmen wir die relativen Häufigkeiten der einzelnen Buchstaben:

Dann ordnen wir die Paare nach Wahrscheinlichkeiten (von der größten zur kleinsten):

Nun fassen wir die beiden Buchstaben mit den kleinsten Wahrscheinlichkeiten zusammen und geben dem einen den Code 0, dem anderen den Code 1:

Im nächsten Schritt werden wieder die beiden Elemente mit den kleinsten Wahrscheinlichkeiten zusammengefasst, denen dann wieder die Ziffern 0, bzw. 1 zugeordnet werden. Die Buchstaben G und N erhalten jeweils einen neuen Code, indem dem alten einfach 1 vorangestellt wird.

So verfahren wir nun, bis alle Buchstaben diesen Prozess durchlaufen haben:

Das Verfahren ist hiermit zu Ende geführt und zeigt nun für jeden Buchstaben einen Huffman-Code an, dargestellt durch Binärzahlen. Unser Ausgangswort MOORJEEEN erhält jetzt also folgenden Code: 1000101101110000000111
Oft wird in der Praxis auch von einem Huffman-Baum gesprochen, da man den Vorgang, die jeweils seltensten Werte zusammenzufassen und ihnen 0 oder 1 zuzuordnen, auch in Form eines (aus der Schulstochastik bekannten) Wahrscheinlichkeits-Baumes darstellen kann, nur dass hier die Pfade einen Code für jedes Element der Ergebnismenge angeben:



Den Code für ein bestimmtes Symbol liest man ab, indem man die einzelnen Pfade des Huffman-Baumes entlangliest; für "J" ergibt sich so der Code 110. Die "leeren" Knoten sind keine Panne oder ein unschöner Nebeneffekt, sondern notwendig: Sie sorgen dafür, dass die einzelnen Codes einzigartig sind und dass kein Code Präfix eines anderen ist (das wird später noch genau erläutert).

Der Code 1000101101110000000111 ist eindeutig identifizierbar mit dem Ausgangswort MOORJEEEN, ohne dass Trennzeichen nötig sind, was genau die Stärke der Huffman-Codierung ist: mit möglichst wenig Platz (es entfällt Speicherplatz für Trennzeichen) kann eine lange Information gespeichert werden. Wir sehen auch, dass die Buchstaben, die im Beispielwort oft auftauchen, kurze Codes erhalten haben. Das führt ebenfalls zur Minimierung des Speicherplatzes. Wäre das Ausgangswort MOORJEEEN normal in Binärcode umgewandelt worden, hätte man statt der 22 Stellen des Huffman-Codes (1000101101110000000111) 42 benötigt (jedem Buchstaben wird seine Platzzahl im Alphabet in Binärform zugeordnet, außerdem kommen 8 Trennzeichen hinzu, da die Codes nicht eindeutig sind). Das Funktionsprinzip des Huffman-Codes können Sie sich hier anhand eines kleinen Huffman-Programmes veranschaulichen.

Neben diesem Verfahren des Codierens gibt es auch die arithmetische Codierung - sie unterscheidet sich wenig von der Huffman-Codierung, da sie die Wahrscheinlichkeiten als Dezimalzahlen angibt, und nicht als Brüche. Allerdings ist sie Patent-geschützt, was viele Benutzer zurückschrecken lässt und wieder auf die Huffman-Codierung verweist.


8.3 Huffman-Codierung: Hintergründe

Im Folgenden wollen wir kurz darstellen, warum der Huffman-Code so ideal ist, weshalb er kurz ist und warum er keine Trennzeichen benötigt. Dazu müssen wir etwas weiter ausholen: Die Huffman-Codierung gehört in das große Feld der Informationstheorie. Eingeführt sei an dieser Stelle der Begriff der Entropie:

Betrachtet man ein Zufallsexperiment mit n möglichen Ausgängen, was durch den endlichen Wahrscheinlichkeitsraum mit beschrieben wird, so herrscht Unsicherheit über den Ausgang dieses Experiments. Die Unsicherheit über den Ausgang des Experiments messen wir mit der Zahl H(p), der Entropie des Experiments. Das Maß der Unbestimmtheit muss nun auch anschaulich verständlich gemacht werden: Wir stellen uns ein Experiment vor, in dem es n verschiedene Versuchsausgänge gibt. Die Person A weiß schon, wie der Versuch ausgegangen ist, Person B soll dies mit Hilfe von Fragen herausfinden. Die mittlere Anzahl von Fragen, die B benötigt, um die Antwort herauszufinden ist nun die wahre Entropie.

Wir gelangen so zur Definition: Für ein Zufallsexperiment ist die wahre Entropie definiert als der Erwartungswert der Anzahl benötigter Fragen bei optimaler Fragestrategie.

Die Formel der so genannten ideellen Entropie, mit der wir rechnen, nennen wir an dieser Stelle noch einmal (uns ist sie bereits in Kapitel 2.3 begegnet):

Falls es Sie interessiert, geben wir Ihnen hier eine interessante Herleitung an, warum jeder Huffman-Code optimal ist. Wer dem nicht ganz akribisch nachgehen möchte, dem liefern wir im Folgenden zwei Beispiele zur Verdeutlichung:

  1. Das Experiment, bei dem schon vor Ausführung gesagt werden kann, wie es ausgeht, hat die wahre Entropie 0. Im Allgemeinen gilt dann auch H(p) > 0.
  2. Beim Münzwurf, also bei , fragt man nach dem Versuchsausgang etwa: "Ist es ?" Das ist offensichtlich optimal. Somit ist , denn es ist nur eine Frage nötig, um herauszufinden, welches Ereignis eingetreten ist.

Wir ersetzen jetzt die Worte "ja" und "nein" durch die Zeichen 0 und 1. Die Fragestrategie kann nun anhand eines Codes ausgedrückt werden. Ein Wort sei eine endliche Folge von Nullen und Einsen. Ist ein Wort, so bezeichnen wir mit die Länge des Wortes, zum Beispiel hat die Länge . Die leere Folge von Zeichen nennen wir das leere Wort, es hat die Länge 0.

Damit ein Code optimal wird, muss er zwei Eigenschaften erfüllen: er muss die Präfixeigenschaft besitzen und eine injektive Abbildung sein. Die Präfixeigenschaft besagt, dass kein Codewort Präfix eines anderen sein darf. Praktisch gesagt heißt das, dass kein Codewort in den Anfangszeichen eines anderen Codewortes vorkommen darf. Injektive Abbildung heißt, dass jedem Versuchsausgang eindeutig ein Codewort zugeordnet ist. Beide Eigenschaften sind durch das Huffman-Verfahren gegeben, das speziell darauf ausgerichtet wurde, keine Codes zu erzeugen, die Präfix eines anderen sein können.

Wir betrachten als Beispiel fünf Codes , von denen aber nur drei brauchbar sind. Finden Sie heraus, welche aus je einem der oben genannten Gründe nicht benutzt werden können!

Haben Sie herausgefunden, welche beiden Codes nicht brauchbar sind? Hier können Sie nachprüfen, ob Ihre Vermutung richtig war.


8.4 Codierungsmuster und Huffman-Codierung

Wieder zurück zu unserer quantisierten Matrix, bzw. unserem Vektor: Der Wert in der oberen linken Ecke der quantisierten Matrix (bzw. der erste Wert unseres Vektors) ist der DC-Wert - er wird gesondert verschlüsselt. Weil er der mit Abstand der größte Wert ist, wird nämlich nicht sein eigener Wert codiert, sondern die Differenz zum DC-Wert des vorangehenden Blocks:

Der Code besitzt zwei Symbole: das erste gibt an, wie viele Bits benötigt werden, um den codierten Wert zu speichern. Zur Bestimmung dieser Bitzahl gibt es eine Tabelle. Symbol 2 gibt einfach den Wert an.

In unserem Beispiel sei der DC-Wert des vorangehenden Blocks 29. Die Differenz zu unserem Block ist damit 2. Dieser Wert 2 wird nun in "Symbolform" gebracht: Zum Speichern der 2 werden 2 Bits benötigt und das Symbol selbst ist 2. Daraus folgt die Zwischendarstellung in der Form (2)(2).

Für die Codierung der AC-Werte gilt nun ein etwas anderes Muster: Auch hier werden zwei Symbole benutzt, das erste hat aber zwei Komponenten. Die erste Komponente ist die so genannte Lauflänge des Symbols, d.h. die Anzahl der ununterbrochenen Nullen, die dem Symbol vorangehen seit dem letzten Symbol, was ungleich null war. Die zweite Komponente ist wieder die Anzahl der Bits, die benötigt werden, um die Zahl zu speichern. Im zweiten Symbol wird die Zahl selbst festgehalten.

Für unsere erste Zahl ungleich Null in der Zick-Zack Reihe, den DCT-Koeffizienten AC3, bedeutet das:

Der quantisierte DCT-Koeffizient AC70 zum Beispiel hat den Wert -3. Dieser Wert kann mit 2 Bit codiert werden, vor ihm stehen im Zick-Zack-Kurs 11 Nullen. Also lautet seine Tupel-Beschreibung <(11;2),-3>.

Die Nullen, die in der letzten langen Sequenz hintereinander auftauchen, werden mit einem "End-of-block"-Symbol dargestellt: (0;0), d.h. es folgen bis zum Ende des Blocks nur noch Nullen.

Alle Werte des Blocks müssen in diese Art der Zwischendarstellung umgeformt werden, um sie dann zu codieren. Dies geschieht nun mit der oben angedeuteten Huffman-Codierung.

Symbol 1 und Symbol 2 werden getrennt auf der Basis einer stochastischen Auswertung codiert. Diese Auswertung kann man wie im obigen Beispiel beschrieben selbst vornehmen, um dann für jedes Symbol einen einzigartigen Code zu erhalten. Allerdings ist dies bei den 8*8 Blöcken sehr viel Arbeit, die man sich ersparen kann. Es gibt nämlich Tabellen, die auf empirischen Werten beruhen und so ein schnelleres Verfahren ermöglichen (zwar sind diese Tabellen nicht immer optimal, weil sie eben allgemein für alle Matrizen gelten, aber da sie vorgefertigt sind und die herkömmlichen zu verschlüsselnden Werte abdecken, kann zugunsten der gesparten Mühe beim Selbercodieren ein nicht zu 100% optimaler Code hingenommen werden). Wir haben einige solcher Tabellen ausgewählt, die uns die Mühe beim Codieren erleichtern - wer mag, kann gerne selbst eine stochastische Auswertung unseres Vektors vornehmen und sich selbst einen Code basteln, es wird aber viel Arbeit werden. Beispielcodierung für unseren Vektor...


< Kapitel 7 Kapitel 9 >

Die JPEG-Kompression, Kapitel 8 Sebastian Wickenburg, Aeneas Rooch, Johannes Groß 2002