Codificación aritmética binaria adaptativa al contexto

La codificación aritmética binaria adaptativa al contexto ( CABAC ) es una forma de codificación por entropía utilizada en los estándares H.264/MPEG-4 AVC ^{[1] [2]} y High Efficiency Video Coding (HEVC). Es una técnica de compresión sin pérdida , aunque los estándares de codificación de vídeo en los que se utiliza suelen ser para aplicaciones de compresión con pérdida . CABAC se destaca por proporcionar una compresión mucho mejor que la mayoría de los demás algoritmos de codificación por entropía utilizados en la codificación de vídeo, 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 superiores (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 codificación de longitud variable adaptativa al contexto (CAVLC) que se utiliza en el perfil base del estándar. CABAC también es difícil de paralelizar y vectorizar, por lo que se pueden combinar otras formas de paralelismo (como el paralelismo de región espacial) con su uso. En HEVC, CABAC se utiliza en todos los perfiles del estándar.

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

• Codifica símbolos binarios, lo que mantiene la complejidad baja y permite el modelado de probabilidad para los bits utilizados con mayor frecuencia de cualquier símbolo.
• Los modelos de probabilidad se seleccionan de forma adaptativa en función del contexto local, lo que permite una mejor modelización de las 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 a binarios. Luego, para cada bit, el codificador selecciona qué modelo de probabilidad utilizar y luego utiliza información de elementos cercanos para optimizar la estimación de probabilidad. Finalmente, se aplica la codificación aritmética para comprimir los datos.

El modelado de contexto proporciona estimaciones de probabilidades condicionales de los símbolos de codificación. Utilizando modelos de contexto adecuados, se puede aprovechar una redundancia entre símbolos dada alternando entre diferentes modelos de probabilidad según los símbolos ya codificados en la vecindad del símbolo actual a codificar. El modelado de contexto es responsable de la mayor parte del ahorro de aproximadamente el 10 % de CABAC en la tasa de bits en comparación con el método de codificación por 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 que no tenga un valor 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 aún más (por 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 de 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 intervalo según el modelo de probabilidad seleccionado. Tenga en cuenta que solo hay dos subrangos para cada intervalo (que corresponden a "0" y "1").
• Actualización de probabilidad: el modelo de contexto seleccionado se actualiza en función del valor codificado real (por ejemplo, si el valor del bin era "1", se incrementa el recuento de frecuencia de "1").

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

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

2. Elija un modelo de contexto para cada bin. Se selecciona uno de los 3 modelos para el bin 1, en función de los valores MVD codificados previamente. Se calcula la norma L1 de dos valores codificados previamente, e _k :

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

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

4. Actualice los modelos de contexto. Por ejemplo, si se seleccionó el modelo de contexto 2 para el bin 1 y el valor del bin 1 fue "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 umbral, se reducirán los recuentos de frecuencia de "0" y "1", lo que, en efecto, otorga mayor prioridad a las observaciones recientes.

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, el 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 a un pequeño rango de valores preestablecidos antes de calcular el nuevo rango en cada paso, lo que hace posible calcular el nuevo rango utilizando una tabla de consulta (es decir, sin multiplicación).
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.

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 presentó 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 decodificadores del formato de archivo JPEG, que tiene opciones tanto para la codificación Huffman como para la codificación aritmética, normalmente solo admiten la opción de codificación Huffman, lo 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] El primer uso informado de la codificación aritmética binaria adaptativa en la compresión de video en movimiento fue en una propuesta de los investigadores de IBM al grupo MPEG en 1989. ^{[11] [12]} Esta propuesta extendió el uso de la codificación aritmética de JPEG intracuadro a la codificación de video entre cuadros.

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

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