Kontextadaptive binäre arithmetische Codierung - Context-adaptive binary arithmetic coding

Kontextadaptive binäre arithmetische Codierung ( CABAC ) ist eine Form der Entropiecodierung, die in den Standards H.264/MPEG-4 AVC und High Efficiency Video Coding (HEVC) verwendet wird. Es handelt sich um eine verlustfreie Komprimierungstechnik , obwohl die Videocodierungsstandards, in denen sie verwendet wird, typischerweise für verlustbehaftete Komprimierungsanwendungen bestimmt sind. CABAC zeichnet sich durch eine viel bessere Kompression aus als die meisten anderen Entropie-Kodierungsalgorithmen, die bei der Videokodierung verwendet werden, und es ist eines der Schlüsselelemente, das dem H.264/AVC-Kodierungsschema eine bessere Kompressionsfähigkeit als seine Vorgänger bietet.

In H.264/MPEG-4 AVC wird CABAC nur im Main- und höheren Profil (aber nicht im erweiterten Profil) des Standards unterstützt, da es mehr Verarbeitungsaufwand zum Decodieren erfordert als das einfachere Schema, das als kontextadaptiv bekannt ist Variable-Length-Codierung (CAVLC), die im Baseline-Profil des Standards verwendet wird. CABAC ist auch schwierig zu parallelisieren und zu vektorisieren, so dass andere Formen der Parallelität (wie die Parallelität der räumlichen Region) mit seiner Verwendung gekoppelt werden können. In HEVC wird CABAC in allen Profilen des Standards verwendet.

Algorithmus

CABAC basiert auf arithmetischer Codierung mit einigen Neuerungen und Änderungen, um es an die Anforderungen der Videocodierungsstandards anzupassen:

  • Es codiert binäre Symbole, was die Komplexität gering hält und eine Wahrscheinlichkeitsmodellierung für häufiger verwendete Bits eines beliebigen Symbols ermöglicht.
  • Die Wahrscheinlichkeitsmodelle werden adaptiv basierend auf dem lokalen Kontext ausgewählt, was eine bessere Modellierung von Wahrscheinlichkeiten ermöglicht, da Codierungsmodi normalerweise lokal gut korreliert sind.
  • Es verwendet eine multiplikationsfreie Bereichsteilung durch die Verwendung von quantisierten Wahrscheinlichkeitsbereichen und Wahrscheinlichkeitszuständen.

CABAC hat mehrere Wahrscheinlichkeitsmodi für verschiedene Kontexte. Es konvertiert zuerst alle nicht- binären Symbole in binäre. Dann wählt der Codierer für jedes Bit das zu verwendende Wahrscheinlichkeitsmodell aus und verwendet dann Informationen von nahegelegenen Elementen, um die Wahrscheinlichkeitsschätzung zu optimieren. Schließlich wird eine arithmetische Codierung angewendet, um die Daten zu komprimieren.

CABAC-Methode zur Entropiekodierung, die innerhalb des H264-Videokomprimierungsstandards in Englisch verwendet wird

Die Kontextmodellierung liefert Schätzungen von bedingten Wahrscheinlichkeiten der Codierungssymbole. Unter Verwendung geeigneter Kontextmodelle kann eine gegebene Intersymbolredundanz ausgenutzt werden, indem zwischen verschiedenen Wahrscheinlichkeitsmodellen entsprechend bereits codierten Symbolen in der Nachbarschaft des zu codierenden aktuellen Symbols umgeschaltet wird. Die Kontextmodellierung ist für die meisten der ungefähr 10 % Einsparungen von CABAC bei der Bitrate gegenüber dem CAVLC- Entropiecodierungsverfahren verantwortlich.

Das Codieren eines Datensymbols umfasst die folgenden Schritte.

  • Binarisierung: CABAC verwendet binäre arithmetische Codierung, was bedeutet, dass nur binäre Entscheidungen (1 oder 0) codiert werden. Ein nicht-binärwertiges Symbol (zB ein Transformationskoeffizient oder ein Bewegungsvektor) wird vor der arithmetischen Codierung "binarisiert" oder in einen Binärcode umgewandelt. Dieser Vorgang ist dem Vorgang der Umwandlung eines Datensymbols in einen Code variabler Länge ähnlich, jedoch wird der Binärcode vor der Übertragung (durch den arithmetischen Codierer) weiter codiert.
  • Stufen werden für jedes Bit (oder "Bin") des binärisierten Symbols wiederholt.
  • Kontextmodellauswahl: Ein "Kontextmodell" ist ein Wahrscheinlichkeitsmodell für einen oder mehrere Bins des binarisierten Symbols. Dieses Modell kann aus einer Auswahl verfügbarer Modelle in Abhängigkeit von der Statistik der kürzlich codierten Datensymbole ausgewählt werden. Das Kontextmodell speichert die Wahrscheinlichkeit, dass jedes Bin "1" oder "0" ist.
  • Arithmetische Codierung: Ein arithmetischer Codierer codiert jeden Bin gemäß dem ausgewählten Wahrscheinlichkeitsmodell. Beachten Sie, dass es für jedes Bin nur zwei Unterbereiche gibt (entsprechend "0" und "1").
  • Wahrscheinlichkeitsaktualisierung: Das ausgewählte Kontextmodell wird basierend auf dem tatsächlich codierten Wert aktualisiert (z. B. wenn der Bin-Wert "1" war, wird die Häufigkeitszählung von "1" erhöht).

Beispiel

1. Binarisieren Sie den Wert MVDx, die Bewegungsvektordifferenz in x- Richtung.

MVD x Binarisierung
0 0
1 10
2 110
3 1110
4 11110
5 111110
6 1111110
7 11111110
8 111111110

Das erste Bit des binärisierten Codeworts ist Bin 1; das zweite Bit ist Bin 2; usw.

2. Wählen Sie für jede Bin ein Kontextmodell aus. Eines von 3 Modellen wird für Bin 1 ausgewählt, basierend auf zuvor codierten MVD-Werten. Die L1-Norm von zwei zuvor codierten Werten, e k , wird berechnet:

e k Kontextmodell für Bin 1
0 ≤ ek < 3 Modell 0
3 ≤ ek < 33 Modell 1
33 e k Modell 2

Wenn e k klein ist, besteht eine hohe Wahrscheinlichkeit, dass die aktuelle MVD eine kleine Größe hat; umgekehrt, wenn e k groß ist, ist es wahrscheinlicher, dass die aktuelle MVD eine große Größe hat. Entsprechend wählen wir eine Wahrscheinlichkeitstabelle (Kontextmodell) aus. Die restlichen Bins werden mit einem von 4 weiteren Kontextmodellen kodiert:

Behälter Kontextmodell
1 0, 1 oder 2 je nach e k
2 3
3 4
4 5
5 und höher 6

3. Codieren Sie jeden Behälter. Das ausgewählte Kontextmodell liefert zwei Wahrscheinlichkeitsschätzungen: die Wahrscheinlichkeit, dass der Bin „1“ enthält, und die Wahrscheinlichkeit, dass der Bin „0“ enthält. Diese Schätzungen bestimmen die zwei Unterbereiche, die der arithmetische Codierer verwendet, um den Bin zu codieren.

4. Aktualisieren Sie die Kontextmodelle. Wenn beispielsweise das Kontextmodell 2 für Bin 1 ausgewählt wurde und der Wert von Bin 1 „0“ war, wird der Häufigkeitszähler von „0“ inkrementiert. Das bedeutet, dass bei der nächsten Auswahl dieses Modells die Wahrscheinlichkeit einer „0“ etwas höher ist. Wenn die Gesamtzahl der Vorkommen eines Modells einen Schwellenwert überschreitet, werden die Häufigkeitszählungen für „0“ und „1“ herunterskaliert, was in der Tat den jüngsten Beobachtungen eine höhere Priorität einräumt.

Die arithmetische Dekodierungs-Engine

Der arithmetische Decoder ist im Standard ausführlich beschrieben. Es hat drei verschiedene Eigenschaften:

  1. Die Wahrscheinlichkeitsschätzung wird durch einen Übergangsprozess zwischen 64 separaten Wahrscheinlichkeitszuständen für "Least Probable Symbol" (LPS, die am wenigsten wahrscheinliche der beiden binären Entscheidungen "0" oder "1") durchgeführt.
  2. Der Bereich R, der den aktuellen Zustand des arithmetischen Codierers darstellt, wird in einen kleinen Bereich voreingestellter Werte quantisiert, bevor der neue Bereich bei jedem Schritt berechnet wird, wodurch es möglich ist, den neuen Bereich unter Verwendung einer Nachschlagetabelle zu berechnen (dh multiplikationsfrei ).
  3. Für Datensymbole mit einer nahezu gleichförmigen Wahrscheinlichkeitsverteilung ist ein vereinfachter Codierungs- und Decodierungsprozess definiert.

Die Definition des Decodierungsprozesses soll Implementierungen von arithmetischer Codierung und Decodierung mit geringer Komplexität erleichtern. Insgesamt bietet CABAC eine verbesserte Codierungseffizienz im Vergleich zu CAVLC-basierter Codierung auf Kosten einer größeren Rechenkomplexität.

Geschichte

1986 meldeten die IBM- Forscher Kottappuram MA Mohiuddin und Jorma Johannen Rissanen ein Patent für einen multiplikationsfreien binären arithmetischen Codierungsalgorithmus an. 1988 präsentierte ein IBM-Forschungsteam mit RB Arps, TK Truong, DJ Lu, WB Pennebaker, L. Mitchell und GG Langdon einen adaptiven binären arithmetischen Codierungs-(ABAC)-Algorithmus namens Q-Coder.

Die oben genannten Patente und Forschungsarbeiten wurden zusammen mit mehreren anderen von IBM und Mitsubishi Electric später von der CCITT und der Joint Photographic Experts Group als Grundlage für den adaptiven binären arithmetischen Codierungsalgorithmus des JPEG -Bildkompressionsformats im Jahr 1992 zitiert Das JPEG-Dateiformat, das Optionen sowohl für die Huffman-Codierung als auch für die arithmetische Codierung bietet, unterstützt normalerweise nur die Huffman-Codierungsoption, die ursprünglich aus Patentgründen bestand, obwohl die Patente für die arithmetische Codierung von JPEG inzwischen aufgrund des Alters des JPEG-Standards abgelaufen sind.

1999 stellten Youngjun Yoo ( Texas Instruments ), Young Gap Kwon und Antonio Ortega ( University of Southern California ) eine kontextadaptive Form der binären arithmetischen Codierung vor. Der moderne kontextadaptive binäre arithmetische Codierungsalgorithmus (CABAC) wurde 2003 mit dem H.264/MPEG-4 AVC- Format kommerziell eingeführt . Die Mehrheit der Patente für das AVC-Format werden von Panasonic , Godo Kaisha IP Bridge und LG Electronics gehalten .

Siehe auch

Verweise