Kontextově adaptivní binární aritmetické kódování - Context-adaptive binary arithmetic coding

Kontextově adaptivní binární aritmetické kódování (CABAC) je forma kódování entropie použitý v H.264 / MPEG-4 AVC[1][2] a Vysoce efektivní kódování videa (HEVC). Je to bezztrátová komprese technika, ačkoli standardy pro kódování videa, ve kterých se používá, jsou obvykle pro ztrátová komprese aplikace. CABAC je pozoruhodný tím, že poskytuje mnohem lépe komprese než většina ostatních algoritmů kódování entropie používaných při kódování videa a je to jeden z klíčových prvků, které poskytují kódovací schéma H.264 / AVC s lepší schopností komprese než jeho předchůdci.

v H.264 / MPEG-4 AVC, CABAC je podporován pouze v hlavní a vyšší profily (ale ne rozšířený profil) standardu, protože k dekódování vyžaduje větší množství zpracování než jednodušší schéma známé jako kontextově adaptivní kódování s proměnnou délkou (CAVLC), který se používá v základním profilu standardu. CABAC je také obtížné paralelizovat a vektorizovat, takže s jeho použitím lze spojit i jiné formy paralelismu (například paralelismus prostorové oblasti). V HEVC se CABAC používá ve všech profilech standardu.

Algoritmus

CABAC je založen na aritmetické kódování, s několika inovacemi a změnami, které jej přizpůsobí potřebám standardů kódování videa:[3]

  • Kóduje binární symboly, což udržuje nízkou složitost a umožňuje modelování pravděpodobnosti pro častěji používané bity libovolného symbolu.
  • Pravděpodobnostní modely jsou vybírány adaptivně na základě místního kontextu, což umožňuje lepší modelování pravděpodobností, protože režimy kódování jsou obvykle lokálně dobře korelované.
  • Používá dělení rozsahu bez násobení pomocí kvantováno rozsahy pravděpodobnosti a stavy pravděpodobnosti.

CABAC má několik pravděpodobnost režimy pro různé kontexty. Nejprve převede všechnybinární symboly na binární. Potom pro každý bit kodér vybere, který model pravděpodobnosti se má použít, a poté použije informace z blízkých prvků k optimalizaci odhadu pravděpodobnosti. Aritmetické kódování se nakonec použije ke kompresi dat.

Metoda kódování entropie CABAC použitá v normě komprese videa H264 v angličtině

Kontextové modelování poskytuje odhady podmíněných pravděpodobností kódovacích symbolů. Použitím vhodných kontextových modelů lze danou mezisymbolovou redundanci využít přepínáním mezi různými modely pravděpodobnosti podle již kódovaných symbolů v sousedství aktuálního symbolu pro kódování. Kontextové modelování je zodpovědné za většinu zhruba 10% úspor CABAC v přenosová rychlost přes CAVLC metoda kódování entropie.

Kódování datového symbolu zahrnuje následující fáze.

  • Binarizace: CABAC používá binární aritmetické kódování, což znamená, že jsou kódována pouze binární rozhodnutí (1 nebo 0). Symbol bez binární hodnoty (např. Transformační koeficient nebo pohybový vektor) je „binarizován“ nebo převeden na binární kód před aritmetickým kódováním. Tento proces je podobný procesu převodu datového symbolu na kód s proměnnou délkou, ale binární kód je před přenosem dále kódován (aritmetickým kodérem).
  • Fáze se opakují pro každý bit (nebo „bin“) binarizovaného symbolu.
  • Výběr kontextového modelu: „Kontextový model“ je model pravděpodobnosti pro jeden nebo více košů binarizovaného symbolu. Tento model může být vybrán z výběru dostupných modelů v závislosti na statistice nedávno kódovaných datových symbolů. Kontextový model ukládá pravděpodobnost, že každý koš bude „1“ nebo „0“.
  • Aritmetické kódování: Aritmetický kodér kóduje každou přihrádku podle vybraného modelu pravděpodobnosti. Pamatujte, že pro každý zásobník existují pouze dva dílčí rozsahy (odpovídající „0“ a „1“).
  • Aktualizace pravděpodobnosti: Vybraný kontextový model se aktualizuje na základě skutečné kódované hodnoty (např. Pokud byla hodnota bin „1“, zvýší se počet frekvencí „1“ s).

Příklad

1. Binarizujte hodnotu MVDx, rozdíl vektoru pohybu v X směr.

MVDXBinarizace
00
110
2110
31110
411110
5111110
61111110
711111110
8111111110

První bit binarizovaného kódového slova je bin 1; druhý bit je bin 2; a tak dále.

2. Vyberte kontextový model pro každou přihrádku. Jeden ze 3 modelů je vybrán pro zásobník 1 na základě předchozích kódovaných hodnot MVD. Norma L1 dvou dříve kódovaných hodnot, napřk, se počítá:

EkKontextový model pro zásobník 1
0 ≤ ek < 3Model 0
3 ≤ ek < 33Model 1
33 ≤ ekModel 2

Pokud ek je malý, pak je vysoká pravděpodobnost, že aktuální MVD bude mít malou velikost; naopak, pokud ek je velká, je pravděpodobnější, že aktuální MVD bude mít velkou velikost. Podle toho vybereme pravděpodobnostní tabulku (kontextový model). Zbývající koše jsou kódovány pomocí jednoho ze 4 dalších kontextových modelů:

ZásobníkKontextový model
10, 1 nebo 2 v závislosti na ek
23
34
45
5 a vyšší6

3. Zakódujte každý zásobník. Vybraný kontextový model poskytuje dva odhady pravděpodobnosti: pravděpodobnost, že přihrádka obsahuje „1“ a pravděpodobnost, že přihrádka obsahuje „0“. Tyto odhady určují dva dílčí rozsahy, které aritmetický kodér používá ke kódování zásobníku.

4. Aktualizujte kontextové modely. Například pokud byl vybrán kontextový model 2 pro zásobník 1 a hodnota zásobníku 1 byla „0“, zvýší se počet frekvencí „0“ s. To znamená, že při příštím výběru tohoto modelu bude pravděpodobnost „0“ o něco vyšší. Když celkový počet výskytů modelu překročí prahovou hodnotu, počet frekvencí pro „0“ a „1“ se zmenší, což ve skutečnosti dává vyšší prioritu nedávným pozorováním.

Aritmetický dekódovací modul

Aritmetický dekodér je podrobně popsán ve standardu. Má tři odlišné vlastnosti:

  1. Odhad pravděpodobnosti se provádí procesem přechodu mezi 64 samostatnými stavy pravděpodobnosti pro „nejméně pravděpodobný symbol“ (LPS, nejméně pravděpodobný ze dvou binárních rozhodnutí „0“ nebo „1“).
  2. Rozsah R představující aktuální stav aritmetického kodéru je kvantifikován na malý rozsah přednastavených hodnot před výpočtem nového rozsahu v každém kroku, což umožňuje vypočítat nový rozsah pomocí vyhledávací tabulky (tj. bez násobení).
  3. Pro datové symboly je definován zjednodušený proces kódování a dekódování s téměř rovnoměrným rozdělením pravděpodobnosti.

Definice procesu dekódování je navržena tak, aby usnadňovala implementace aritmetického kódování a dekódování s nízkou složitostí. Celkově CABAC poskytuje lepší účinnost kódování ve srovnání s kódováním založeným na CAVLC, na úkor větší výpočetní složitosti.

Dějiny

V roce 1986 IBM vědci Kottappuram M. A. Mohiuddin a Jorma Johannen Rissanen podali a patent pro algoritmus binárního aritmetického kódování bez násobení.[4][5] V roce 1988 provedl výzkumný tým IBM včetně R.B.Aps, T.K. Truong, D.J. Lu, W. B. Pennebaker, L. Mitchell a G. G. Langdon představili algoritmus adaptivního binárního aritmetického kódování (ABAC) nazvaný Q-Coder.[6][7]

Výše uvedené patenty a výzkumné práce spolu s několika dalšími od společností IBM a Mitsubishi Electric, byly později citovány CCITT a Společná skupina fotografických odborníků jako základ pro JPEG komprese obrazu adaptivního binárního aritmetického kódovacího algoritmu formátu v roce 1992.[4] Kodéry a dekodéry však formát souboru JPEG, který má možnosti pro oba Huffmanovo kódování a aritmetické kódování obvykle podporují pouze možnost Huffmanova kódování, což bylo původně kvůli patentovým obavám, ačkoli aritmetické kódovací patenty JPEG[8] od té doby vypršela platnost kvůli věku standardu JPEG.[9]

V roce 1999 Youngjun Yoo (Texas Instruments ), Young Gap Kwon a Antonio Ortega (University of Southern California ) představil kontextově adaptivní formu binárního aritmetického kódování.[10] Algoritmus moderního kontextově adaptivního binárního aritmetického kódování (CABAC) byl komerčně představen s H.264 / MPEG-4 AVC formátu v roce 2003.[11] Většinu patentů na formát AVC vlastní Panasonic, Godo Kaisha IP Bridge a LG Electronics.[12]

Viz také

Reference

  1. ^ Richardson, Iain E. G., Bílá kniha H.264 / MPEG-4 část 10, 17. října 2002.
  2. ^ Richardson, Iain E. G. (2003). Video komprese H.264 a MPEG-4: Kódování videa pro multimédia nové generace. Chichester: John Wiley & Sons Ltd.
  3. ^ Marpe, D., Schwarz, H. a Wiegand, T., Kontextové adaptivní binární aritmetické kódování ve standardu komprese videa H.264 / AVC, IEEE Trans. Obvody a systémy pro videotechniku, Sv. 13, č. 7, s. 620–636, červenec 2003.
  4. ^ A b „T.81 - DIGITÁLNÍ STLAČENÍ A KÓDOVÁNÍ STÁLÝCH OBRAZŮ S NEPŘETRŽITÝMI TÓNY - POŽADAVKY A POKYNY“ (PDF). CCITT. Září 1992. Citováno 12. července 2019.
  5. ^ US patent 4 652 856
  6. ^ Arps, R. B .; Truong, T. K.; Lu, D. J .; Pasco, R. C .; Friedman, T. D. (listopad 1988). "Víceúčelový čip VLSI pro adaptivní kompresi dat dvouúrovňových obrazů". IBM Journal of Research and Development. 32 (6): 775–795. doi:10.1147 / rd.326.0775. ISSN  0018-8646.
  7. ^ Pennebaker, W. B .; Mitchell, J. L .; Langdon, G. G .; Arps, R. B. (listopad 1988). "Přehled základních principů adaptivního binárního aritmetického kodéru Q-Coder". IBM Journal of Research and Development. 32 (6): 717–726. doi:10.1147 / rd.326.0717. ISSN  0018-8646.
  8. ^ „Doporučení T.81 (1992) Oprava 1 (1. 4.)“. Doporučení T.81 (1992). Mezinárodní telekomunikační unie. 9. listopadu 2004. Citováno 3. února 2011.
  9. ^ Standard komprese statických obrázků JPEG, W. B. Pennebaker a J. L. Mitchell, Kluwer Academic Press, 1992. ISBN  0-442-01272-1
  10. ^ Ortega, A. (říjen 1999). Msgstr "Komprese vloženého obrazu a domény pomocí kontextových modelů". Proceedings 1999 International Conference on Image Processing (Cat. 99CH36348). 1: 477–481 vol.1. doi:10.1109 / ICIP.1999.821655.
  11. ^ „Kontextové adaptivní binární aritmetické kódování (CABAC)“. Institut Fraunhofera Heinricha Hertze. Citováno 13. července 2019.
  12. ^ „AVC / H.264 - Seznam patentů“ (PDF). MPEG LA. Citováno 6. července 2019.