Kontekstowe binarne kodowanie arytmetyczne — Context-adaptive binary arithmetic coding

Kontekstowe kodowanie binarne arytmetyczne ( CABAC ) jest formą kodowania entropijnego stosowaną w standardach H.264/MPEG-4 AVC i High Efficiency Video Coding (HEVC). Jest to technika kompresji bezstratnej , chociaż standardy kodowania wideo, w których jest używana, są zwykle stosowane w aplikacjach z kompresją stratną . CABAC wyróżnia się zapewnianiem znacznie lepszej kompresji niż większość innych algorytmów kodowania entropii używanych w kodowaniu wideo i jest jednym z kluczowych elementów, który zapewnia schematowi kodowania H.264/AVC lepsze możliwości kompresji niż jego poprzednicy.

W H.264/MPEG-4 AVC CABAC jest obsługiwany tylko w głównym i wyższym profilu (ale nie w rozszerzonym profilu) standardu, ponieważ wymaga większej ilości przetwarzania do dekodowania niż prostszy schemat znany jako adaptacja kontekstu kodowanie o zmiennej długości (CAVLC), które jest używane w profilu podstawowym normy. CABAC jest również trudny do zrównoleglenia i wektoryzacji, więc inne formy paralelizmu (takie jak paralelizm przestrzenny) mogą być połączone z jego użyciem. W HEVC CABAC jest stosowany we wszystkich profilach normy.

Algorytm

CABAC opiera się na kodowaniu arytmetycznym , z kilkoma innowacjami i zmianami w celu dostosowania go do potrzeb standardów kodowania wideo:

  • Koduje symbole binarne, co utrzymuje niską złożoność i umożliwia modelowanie prawdopodobieństwa dla częściej używanych bitów dowolnego symbolu.
  • Modele prawdopodobieństwa są wybierane adaptacyjnie w oparciu o kontekst lokalny, co pozwala na lepsze modelowanie prawdopodobieństw, ponieważ tryby kodowania są zwykle lokalnie dobrze skorelowane.
  • Wykorzystuje dzielenie zakresu bez mnożenia przy użyciu skwantowanych zakresów prawdopodobieństwa i stanów prawdopodobieństwa.

CABAC ma wiele trybów prawdopodobieństwa dla różnych kontekstów. Najpierw konwertuje wszystkie niebinarne symbole na binarne. Następnie dla każdego bitu koder wybiera, który model prawdopodobieństwa zastosować, a następnie wykorzystuje informacje z pobliskich elementów, aby zoptymalizować oszacowanie prawdopodobieństwa. Kodowanie arytmetyczne jest ostatecznie stosowane do kompresji danych.

Metoda kodowania entropii CABAC stosowana w standardzie kompresji wideo H264 w języku angielskim

Modelowanie kontekstu zapewnia oszacowanie prawdopodobieństw warunkowych symboli kodowania. Wykorzystując odpowiednie modele kontekstowe, daną redundancję międzysymbolową można wykorzystać przez przełączanie między różnymi modelami prawdopodobieństwa zgodnie z już zakodowanymi symbolami w sąsiedztwie bieżącego symbolu do zakodowania. Modelowanie kontekstu jest odpowiedzialne za większość około 10% oszczędności CABAC w zakresie przepływności w porównaniu z metodą kodowania entropijnego CAVLC .

Kodowanie symbolu danych obejmuje następujące etapy.

  • Binaryzacja: CABAC wykorzystuje kodowanie arytmetyczne binarne, co oznacza, że ​​kodowane są tylko decyzje binarne (1 lub 0). Symbol o wartości niebinarnej (np. współczynnik transformacji lub wektor ruchu) jest „binaryzowany” lub konwertowany na kod binarny przed kodowaniem arytmetycznym. Proces ten jest podobny do procesu konwersji symbolu danych na kod o zmiennej długości, ale kod binarny jest dalej kodowany (przez koder arytmetyczny) przed transmisją.
  • Etapy są powtarzane dla każdego bitu (lub „bin”) zbinaryzowanego symbolu.
  • Wybór modelu kontekstowego: „Model kontekstowy” to model prawdopodobieństwa dla jednego lub więcej przedziałów zbinaryzowanego symbolu. Model ten może być wybrany z szeregu dostępnych modeli w zależności od statystyk ostatnio zakodowanych symboli danych. Model kontekstowy przechowuje prawdopodobieństwo, że każdy pojemnik ma wartość „1” lub „0”.
  • Kodowanie arytmetyczne: koder arytmetyczny koduje każdy bin zgodnie z wybranym modelem prawdopodobieństwa. Zauważ, że istnieją tylko dwa podzakresy dla każdego przedziału (odpowiadające „0” i „1”).
  • Aktualizacja prawdopodobieństwa: Wybrany model kontekstu jest aktualizowany na podstawie rzeczywistej zakodowanej wartości (np. jeśli wartość przedziału wynosiła „1”, liczba częstotliwości „1” jest zwiększana).

Przykład

1. Binaryzacja wartości MVDx, różnicy wektora ruchu w kierunku x .

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

Pierwszy bit zbinaryzowanego słowa kodowego to bin 1; drugi bit to bin 2; i tak dalej.

2. Wybierz model kontekstowy dla każdego pojemnika. Wybrano jeden z 3 modeli dla pojemnika 1, w oparciu o poprzednio zakodowane wartości MVD. Normę L1 dwóch wcześniej zakodowanych wartości, e k , oblicza się:

e k Model kontekstowy dla pojemnika 1
0 ≤ e k < 3 Model 0
3 ≤ e k < 33 Model 1
33 ≤ e k Model 2

Jeśli e k jest małe, to istnieje duże prawdopodobieństwo, że obecny MVD będzie miał małą wielkość; odwrotnie, jeśli ek jest duże, to jest bardziej prawdopodobne, że obecny MVD będzie miał dużą wielkość. Odpowiednio dobieramy tabelę prawdopodobieństwa (model kontekstowy). Pozostałe pojemniki są kodowane przy użyciu jednego z 4 dalszych modeli kontekstowych:

Kosz Model kontekstowy
1 0, 1 lub 2 w zależności od e k
2 3
3 4
4 5
5 i więcej 6

3. Zakoduj każdy pojemnik. Wybrany model kontekstowy dostarcza dwóch szacunków prawdopodobieństwa: prawdopodobieństwo, że pojemnik zawiera „1” i prawdopodobieństwo, że pojemnik zawiera „0”. Te oszacowania określają dwa podzakresy, które koder arytmetyczny wykorzystuje do kodowania pojemnika.

4. Zaktualizuj modele kontekstowe. Na przykład, jeśli model kontekstowy 2 został wybrany dla przedziału 1, a wartość przedziału 1 wynosiła „0”, liczba częstotliwości „0” jest zwiększana. Oznacza to, że przy następnym wyborze tego modelu prawdopodobieństwo „0” będzie nieco wyższe. Gdy łączna liczba wystąpień modelu przekroczy wartość progową, zliczenia częstotliwości dla „0” i „1” zostaną zmniejszone, co w efekcie daje wyższy priorytet ostatnim obserwacjom.

Silnik dekodowania arytmetycznego

Dekoder arytmetyczny jest szczegółowo opisany w normie. Ma trzy różne właściwości:

  1. Oszacowanie prawdopodobieństwa jest wykonywane przez proces przejścia między 64 oddzielnymi stanami prawdopodobieństwa dla „najmniejszego prawdopodobieństwa symbolu” (LPS, najmniej prawdopodobna z dwóch binarnych decyzji „0” lub „1”).
  2. Zakres R reprezentujący bieżący stan kodera arytmetycznego jest kwantowany do małego zakresu wstępnie ustawionych wartości przed obliczeniem nowego zakresu na każdym kroku, co umożliwia obliczenie nowego zakresu za pomocą tabeli przeglądowej (tj. bez mnożenia ).
  3. Dla symboli danych o prawie jednolitym rozkładzie prawdopodobieństwa zdefiniowano uproszczony proces kodowania i dekodowania.

Definicja procesu dekodowania ma na celu ułatwienie implementacji kodowania i dekodowania arytmetycznego o niskiej złożoności. Ogólnie rzecz biorąc, CABAC zapewnia lepszą wydajność kodowania w porównaniu z kodowaniem opartym na CAVLC, kosztem większej złożoności obliczeniowej.

Historia

W 1986 r. badacze IBM Kottappuram MA Mohiuddin i Jorma Johannen Rissanen złożyli patent na algorytm kodowania arytmetycznego bez mnożenia. W 1988 roku zespół badawczy IBM, w tym RB Arps, TK Truong, DJ Lu, WB Pennebaker, L. Mitchell i GG Langdon, zaprezentował algorytm adaptacyjnego kodowania arytmetycznego (ABAC) o nazwie Q-Coder.

Powyższe patenty i prace naukowe, wraz kilkoma innymi z IBM i Mitsubishi Electric , później zostały przywołane przez CCITT oraz Joint Photographic Experts Group jako podstawa do JPEG Kompresja obrazu Adaptive Binary arytmetycznej algorytmu kodowania format w roku 1992. Jednakże, kodery i dekodery format pliku JPEG, który ma opcje zarówno kodowania Huffmana, jak i kodowania arytmetycznego, zazwyczaj obsługuje tylko opcję kodowania Huffmana, która pierwotnie była spowodowana obawami patentowymi, chociaż patenty na kodowanie arytmetyczne JPEG wygasły ze względu na wiek standardu JPEG.

W 1999 roku Youngjun Yoo ( Texas Instruments ), Young Gap Kwon i Antonio Ortega ( Uniwersytet Południowej Kalifornii ) zaprezentowali dopasowującą się do kontekstu formę binarnego kodowania arytmetycznego. Nowoczesny algorytm kontekstowego adaptacyjnego kodowania arytmetycznego (CABAC) został wprowadzony komercyjnie w formacie H.264/MPEG-4 AVC w 2003 roku. Większość patentów na format AVC posiada Panasonic , Godo Kaisha IP Bridge i LG Electronics .

Zobacz też

Bibliografia