Datenkompression: Verlustfreie Verfahren: Statistische Verfahren: CABAC

zurück

5 Verlustfreie Verfahren

5.1 Statistische Verfahren

5.1.1 Der Morse Code

5.1.2 Shannon-Fano Codierung

5.1.3 Huffman Codierung

5.1.4 Präfixfreie Codes

5.1.5 MNP - MicroCom Network Protokoll

5.1.6 Arithmetische Codierung

5.1.7 Adaptive Arithmetische Codierung

5.1.8 Quasiarithmetische Codierung

5.1.9 CABAC

5.1.10 Dynamische Markov Codierung

5.1.11 PPM

5.1.12 BWT - Burrows-Wheeler-Transformation

5.1.13 BWCA - Burrows-Wheeler Kompressions Algorithmus

CABAC

5.1.9 CABAC

Die Kontextadaptive binäre arithmetische Codierung (Context Adaptive Binary Arithmetic Coding) stellt im Grunde genommen eine leichte Modifikation eines arithmetischen Codierers dar. Das Verfahren wird derzeit im Standard MPEG-4 / Part 10 verwendet. Man vermutet revolutionäre Dinge, aber das Verfahren ist relativ simpel. Je nach Art der Daten (also kontextabhängig) wird ein anderes Modell zur Codierung des nächsten folgenden Binärzeichens verwendet. Jedes vom arithmetischen Codierer zu codierende Symbol wird zuvor in ein binäres Codewort umgewandelt (ebenfalls kontextabhängig). Es erfolgt eine Markierung, ob es sich um ein 'Syntax-Element' (meist Headerinformation) oder um ein Daten-Element handelt. Jedes umgewandelte Bit eines Symbols wird mit einer Zusatzinformation versehen, mit welchem Codierer die besten Ergebnisse erzielbar sind. Dementsprechend wird eines der entsprechenden Modelle verwendet. Man komprimiert also nicht nur die Daten, sondern auch die Header- und Meta-Daten.

Ein weiterer Vorteil ist, dass die Statistiken der redundanten und der weniger redundanten Informationen voneinander getrennt sind.

Konsequenter Weise kann dieses Codiermodell auf noch mehr verschiedene Informationen ausgeweitet werden. Dazu müssen die Daten nur vom Codierer entsprechend markiert werden und anschließend dem Binären Arithmetischen Codierer zugeführt werden. Adaptiv wird dieses Codiermodell dadurch, dass das korrekte Modell mit dem gerade codierten Zeichen aktualisiert wird, was sich irgendwie von selbst versteht. Das bedeutet, dass das 'Daten-Modell' nur mit Codierinformationen versorgt/aktualisiert wird, wenn ein Datenelement codiert wird. Das gilt selbstverständlich ebenso für den Header und aller anderen Syntax-Elemente.

Man erreicht durch Verwendung dieses Verfahrens eine erhöhte Codiereffizienz auf Kosten einer erhöhten Komplexität des Codierers.

Bspw. werden in einem Video-Codec ganz unterschiedliche Daten codiert. Manchmal sind es Bewegungsvektoren, manchmal sind es Interframes und manchmal weitere eingebettete Meta-Daten. Diese besitzen aufgrund ihrer Verschiedenartigkeit ganz unterschiedliche statistische Bindungen.

1. Bewegungsvektoren
2. Intra-Codierte Bildausschnitte
3. Header-Informationen
4. ...

Meines Wissens nach sind bei MPEG-4 / Part 10 für jedes Syntax-Element eigene Vorschriften zur Binärwandlung vorhanden und jedes besitzt darüber hinaus sein eigenes Kontext-Modell. Denn jede Art, sei es die Quantisierung oder die Datenverarbeitung, sorgt dafür, dass die entstehenden Informationen ganz unterschiedliche statistische Abhängigkeiten aufweisen.

Anschließend kommt ein binärer arithmetischer Codierer zum Zug. Der kennt aufgrund des Kontextmodells die beiden Wahrscheinlichkeiten für den Fall dass eine '1' oder '0' codiert wird. Mittlerweile ist man dazu übergegangen nicht 'Nullen' und 'Einsen' zu codieren, sondern das 'MPS' (most probable symbol) und das LPS (least probable symbol), also das aktuell häufigere Symbol und das weniger häufigere Symbol zu codieren. Damit können auch kleinere Varianzen bei der Codierung berücksichtigt werden.

Das Verfahren:

1. Der Quellencodierer erzeugt ein nicht binäres Symbol und gibt an, welcher Binärwandler zu verwenden ist,
2. Der dazu gehörende Binärwandler konvertiert das nicht binäre Symbol in ein binäres Wort,
3. Das binäre Wort ist abhängig von der Art der Daten bereits für die Binärdarstellung optimiert worden,
4. Anschließend werden die einzelnen Binärstellen des Wortes mit einem weiteren Code markiert der das arithmetische Codiermodell vorgibt. Das bedeutet bspw. dass die ersten Bits mit dem Modell 1 codiert werden, die 3 folgenden Bits mit dem Modell 2 und das folgende Bit mit dem Modell 4 und alle weiteren mit dem Modell 3.
5. Anschließend wird ein arithmetischer Codierer verwendet.