Codificación aritmética binaria adaptable al contexto

La codificación aritmética binaria adaptativa al contexto ( CABAC ) es una forma de codificación de entropía utilizada en los estándares H.264 / MPEG-4 AVC ^{[1] [2]} y Codificación de video de alta eficiencia (HEVC). Es una técnica de compresión sin pérdidas , aunque los estándares de codificación de vídeo en los que se utiliza suelen ser para aplicaciones de compresión con pérdidas . CABAC se destaca por proporcionar una compresión mucho mejor que la mayoría de los otros algoritmos de codificación de entropía utilizados en la codificación de video, y es uno de los elementos clave que proporciona al esquema de codificación H.264 / AVC una mejor capacidad de compresión que sus predecesores. ^[3]

En H.264 / MPEG-4 AVC , CABAC solo se admite en los perfiles principal y superior (pero no en el perfil extendido) del estándar, ya que requiere una mayor cantidad de procesamiento para decodificar que el esquema más simple conocido como adaptable al contexto codificación de longitud variable (CAVLC) que se utiliza en el perfil de línea de base del estándar. CABAC también es difícil de paralelizar y vectorizar, por lo que otras formas de paralelismo (como el paralelismo de la región espacial) pueden combinarse con su uso. En HEVC, CABAC se utiliza en todos los perfiles del estándar.

Algoritmo

CABAC se basa en la codificación aritmética , con algunas innovaciones y cambios para adaptarla a las necesidades de los estándares de codificación de video: ^[4]

• Codifica símbolos binarios, lo que mantiene baja la complejidad y permite el modelado de probabilidad para los bits de cualquier símbolo que se utilizan con más frecuencia.
• Los modelos de probabilidad se seleccionan de forma adaptativa en función del contexto local, lo que permite un mejor modelado de probabilidades, porque los modos de codificación suelen estar bien correlacionados localmente.
• Utiliza una división de rango libre de multiplicación mediante el uso de rangos de probabilidad cuantificados y estados de probabilidad.

CABAC tiene múltiples modos de probabilidad para diferentes contextos. Primero convierte todos los símbolos no binarios en binarios. Luego, para cada bit, el codificador selecciona qué modelo de probabilidad usar, luego usa información de elementos cercanos para optimizar la estimación de probabilidad. Finalmente se aplica la codificación aritmética para comprimir los datos.

Método CABAC de codificación de entropía utilizado dentro del estándar de compresión de video H264 en inglés

El modelado de contexto proporciona estimaciones de probabilidades condicionales de los símbolos de codificación. Utilizando modelos de contexto adecuados, se puede explotar una redundancia entre símbolos dada cambiando entre diferentes modelos de probabilidad de acuerdo con los símbolos ya codificados en la vecindad del símbolo actual para codificar. El modelado de contexto es responsable de la mayor parte de los ahorros de aproximadamente un 10% de CABAC en la tasa de bits sobre el método de codificación de entropía CAVLC .

La codificación de un símbolo de datos implica las siguientes etapas.

• Binarización: CABAC utiliza codificación aritmética binaria, lo que significa que solo se codifican las decisiones binarias (1 o 0). Un símbolo de valor no binario (por ejemplo, un coeficiente de transformación o un vector de movimiento) se "binariza" o se convierte en un código binario antes de la codificación aritmética. Este proceso es similar al proceso de convertir un símbolo de datos en un código de longitud variable, pero el código binario se codifica adicionalmente (mediante el codificador aritmético) antes de la transmisión.
• Las etapas se repiten para cada bit (o "bin") del símbolo binarizado.
• Selección del modelo de contexto: un "modelo de contexto" es un modelo de probabilidad para uno o más contenedores del símbolo binarizado. Este modelo puede elegirse entre una selección de modelos disponibles según las estadísticas de los símbolos de datos codificados recientemente. El modelo de contexto almacena la probabilidad de que cada contenedor sea "1" o "0".
• Codificación aritmética: un codificador aritmético codifica cada bin según el modelo de probabilidad seleccionado. Tenga en cuenta que solo hay dos subrangos para cada contenedor (correspondientes a "0" y "1").
• Actualización de probabilidad: el modelo de contexto seleccionado se actualiza en función del valor codificado real (p. Ej., Si el valor del intervalo era "1", se incrementa el recuento de frecuencia de "1" s).

Ejemplo

1. Binarice el valor MVDx, la diferencia del vector de movimiento en la dirección x .

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

El primer bit de la palabra de código binarizada es bin 1; el segundo bit es el bin 2; y así.

2. Elija un modelo de contexto para cada contenedor. Se selecciona uno de los 3 modelos para el contenedor 1, según los valores MVD codificados anteriormente. Se calcula la norma L1 de dos valores previamente codificados, e _k :

e k	Modelo de contexto para el contenedor 1
0 ≤ e k <3	Modelo 0
3 ≤ e k <33	Modelo 1
33 ≤ e k	Modelo 2

Si e _k es pequeño, entonces existe una alta probabilidad de que el MVD actual tenga una magnitud pequeña; a la inversa, si e _k es grande, es más probable que el MVD actual tenga una gran magnitud. Seleccionamos una tabla de probabilidad (modelo de contexto) en consecuencia. Los contenedores restantes se codifican utilizando uno de los 4 modelos de contexto adicionales:

Compartimiento	Modelo de contexto
1	0, 1 o 2 dependiendo de e k
2	3
3	4
4	5
5 y superior	6

3. Codifique cada contenedor. El modelo de contexto seleccionado proporciona dos estimaciones de probabilidad: la probabilidad de que el contenedor contenga "1" y la probabilidad de que el contenedor contenga "0". Estas estimaciones determinan los dos subrangos que utiliza el codificador aritmético para codificar el contenedor.

4. Actualice los modelos de contexto. Por ejemplo, si se seleccionó el modelo de contexto 2 para el contenedor 1 y el valor del contenedor 1 era "0", se incrementa el recuento de frecuencia de "0". Esto significa que la próxima vez que se seleccione este modelo, la probabilidad de un "0" será ligeramente mayor. Cuando el número total de ocurrencias de un modelo excede un valor de umbral, los recuentos de frecuencia para "0" y "1" se reducirán, lo que en efecto da mayor prioridad a las observaciones recientes.

El motor de decodificación aritmética

El decodificador aritmético se describe con cierto detalle en la Norma. Tiene tres propiedades distintas:

1. La estimación de probabilidad se realiza mediante un proceso de transición entre 64 estados de probabilidad separados para el "Símbolo menos probable" (LPS, la menos probable de las dos decisiones binarias "0" o "1").
2. El rango R que representa el estado actual del codificador aritmético se cuantifica en un pequeño rango de valores preestablecidos antes de calcular el nuevo rango en cada paso, lo que permite calcular el nuevo rango utilizando una tabla de búsqueda (es decir, sin multiplicaciones ).
3. Se define un proceso de codificación y decodificación simplificado para símbolos de datos con una distribución de probabilidad casi uniforme.

La definición del proceso de decodificación está diseñada para facilitar implementaciones de baja complejidad de codificación y decodificación aritmética. En general, CABAC proporciona una eficiencia de codificación mejorada en comparación con la codificación basada en CAVLC, a expensas de una mayor complejidad computacional.

Historia

En 1986, los investigadores de IBM Kottappuram MA Mohiuddin y Jorma Johannen Rissanen presentaron una patente para un algoritmo de codificación aritmética binaria sin multiplicación. ^{[5] [6]} En 1988, un equipo de investigación de IBM que incluía a RB Arps, TK Truong, DJ Lu, WB Pennebaker, L. Mitchell y GG Langdon presentaron un algoritmo de codificación aritmética binaria adaptativa (ABAC) llamado Q-Coder. ^{[7] [8]}

Las patentes y los artículos de investigación anteriores, junto con varios otros de IBM y Mitsubishi Electric , fueron citados posteriormente por el CCITT y el Joint Photographic Experts Group como base para el algoritmo de codificación aritmética binaria adaptativa del formato de compresión de imágenes JPEG en 1992. ^[5] Sin embargo, los codificadores y los decodificadores del formato de archivo JPEG, que tiene opciones para la codificación de Huffman y la codificación aritmética, generalmente solo admiten la opción de codificación de Huffman, que originalmente se debió a problemas de patentes, aunque las patentes de codificación aritmética de JPEG ^[9] han expirado desde entonces debido a la antigüedad del estándar JPEG. ^[10]

En 1999, Youngjun Yoo ( Texas Instruments ), Young Gap Kwon y Antonio Ortega ( Universidad del Sur de California ) presentaron una forma adaptable al contexto de codificación aritmética binaria. ^[11] El moderno algoritmo de codificación aritmética binaria adaptativa al contexto (CABAC) se introdujo comercialmente con el formato H.264 / MPEG-4 AVC en 2003. ^[12] La mayoría de las patentes para el formato AVC pertenecen a Panasonic , Godo Kaisha Puente IP y LG Electronics . ^[13]

Ver también

• Codificación aritmética
• Compresión de datos
• Compresión sin perdidas
• Codificación de longitud variable adaptativa al contexto (CAVLC)

Referencias

1. Richardson, Iain EG, Libro blanco de H.264 / MPEG-4 Parte 10 , 17 de octubre de 2002.
2. Richardson, Iain EG (2003). Compresión de video H.264 y MPEG-4: Codificación de video para multimedia de próxima generación . Chichester: John Wiley & Sons Ltd.
3. Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 de abril de 2014). Fundamentos de Multimedia . Springer Science & Business Media. ISBN 978-3-319-05290-8.
4. Marpe, D., Schwarz, H. y Wiegand, T., Codificación aritmética binaria adaptativa basada en el contexto en el estándar de compresión de video H.264 / AVC , IEEE Trans. Circuitos y sistemas para tecnología de video , vol. 13, núm. 7, págs. 620–636, julio de 2003.
5. "T.81 - COMPRESIÓN DIGITAL Y CODIFICACIÓN DE FOTOGRAFÍAS EN TONO CONTINUO - REQUISITOS Y DIRECTRICES" (PDF) . CCITT . Septiembre de 1992 . Consultado el 12 de julio de 2019 .
6. Patente de Estados Unidos 4.652.856
7. Arps, RB; Truong, TK; Lu, DJ; Pasco, RC; Friedman, TD (noviembre de 1988). "Un chip VLSI de usos múltiples para la compresión de datos adaptativa de imágenes binivel". IBM Journal of Research and Development . 32 (6): 775–795. doi : 10.1147 / rd.326.0775 . ISSN 0018-8646 . 
8. Pennebaker, WB; Mitchell, JL; Langdon, GG; Arps, RB (noviembre de 1988). "Una descripción general de los principios básicos del codificador aritmético binario adaptativo Q-Coder". IBM Journal of Research and Development . 32 (6): 717–726. doi : 10.1147 / rd.326.0717 . ISSN 0018-8646 . 
9. "Recomendación T.81 (1992) Corrigendum 1 (04/01)" . Recomendación T.81 (1992) . Unión Internacional de Telecomunicaciones. 9 de noviembre de 2004 . Consultado el 3 de febrero de 2011 .
10. Estándar de compresión de datos de imagen JPEG , WB Pennebaker y JL Mitchell , Kluwer Academic Press, 1992. ISBN 0-442-01272-1 
11. Ortega, A. (octubre de 1999). "Compresión de dominio de imagen incrustado utilizando modelos de contexto". Proceedings 1999 International Conference on Image Processing (Cat. 99CH36348) . 1 : 477–481 vol. 1. doi : 10.1109 / ICIP.1999.821655 .
12. "Codificación aritmética binaria adaptativa basada en contexto (CABAC)" . Instituto Fraunhofer Heinrich Hertz . Consultado el 13 de julio de 2019 .
13. "AVC / H.264 - Lista de patentes" (PDF) . MPEG LA . Consultado el 6 de julio de 2019 .