Codificación aritmética binaria adaptativa 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 de codificación de vídeo 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 destaca por proporcionar una compresión mucho mejor que la mayoría de los demás algoritmos de codificación de 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 mayor capacidad de compresión que sus predecesores. ^{[ 3 ]}

En H.264/MPEG-4 AVC , CABAC solo es compatible con los perfiles Main y superiores (pero no con el perfil extendido) del estándar, ya que requiere un procesamiento mayor para su decodificación que el esquema más simple conocido como codificación de longitud variable adaptativa al contexto (CAVLC), que se utiliza en el perfil Baseline del estándar. CABAC también es difícil de paralelizar y vectorizar, por lo que otras formas de paralelismo (como el paralelismo de regiones espaciales) pueden combinarse 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 modelar la probabilidad de los bits más utilizados 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, ya que los modos de codificación suelen estar bien correlacionados localmente.
• Utiliza una división de rango sin multiplicación mediante el uso de rangos de probabilidad cuantificados y estados de probabilidad.

CABAC cuenta con 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 el modelo de probabilidad a utilizar y, posteriormente, emplea 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 las probabilidades condicionales de los símbolos de codificación. Mediante modelos de contexto adecuados, se puede aprovechar una redundancia entre símbolos determinada alternando entre diferentes modelos de probabilidad según los símbolos ya codificados en la vecindad del símbolo que se está codificando. El modelado de contexto es responsable de la mayor parte del ahorro de aproximadamente un 10 % en la tasa de bits que ofrece CABAC en comparación con 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 decisiones binarias (1 o 0). Un símbolo con 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 de convertir un símbolo de datos en un código de longitud variable, pero el código binario se codifica adicionalmente (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 intervalos del símbolo binarizado. Este modelo puede elegirse de 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 intervalo sea "1" o "0".
• Codificación aritmética: Un codificador aritmético codifica cada intervalo según el modelo de probabilidad seleccionado. Cabe destacar que cada intervalo tiene solo dos subrangos (correspondientes 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 intervalo 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 clave binarizada es el bin 1; el segundo bit es el bin 2; y así sucesivamente.

2. Elija un modelo de contexto para cada intervalo. Se selecciona uno de los 3 modelos para el intervalo 1, basándose en 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 intervalos restantes se codifican utilizando uno de los 4 modelos de contexto adicionales:

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 contenga "0". Estas estimaciones determinan los dos subrangos que el codificador aritmético utiliza para codificar el contenedor.

4. Actualizar los modelos de contexto. Por ejemplo, si se seleccionó el modelo de contexto 2 para el bin 1 y el valor de este bin era "0", se incrementa el conteo de frecuencia de "0". Esto significa que la próxima vez que se seleccione este modelo, la probabilidad de obtener un "0" será ligeramente mayor. Cuando el número total de ocurrencias de un modelo supera un valor umbral, los conteos de frecuencia de "0" y "1" se reducen, lo que en la práctica da mayor prioridad a las observaciones recientes.

El decodificador aritmético se describe con cierto detalle en el estándar. 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 permite calcular el nuevo rango utilizando una tabla de búsqueda (es decir, sin multiplicaciones).
3. Se define un proceso simplificado de codificación y decodificación 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 ofrece una mayor eficiencia de codificación en comparación con la codificación basada en CAVLC, a costa de una mayor complejidad computacional.

En 1986, los investigadores de IBM Kottappuram MA Mohiuddin y Jorma Johannes 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 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 se debió originalmente a preocupaciones sobre 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 vídeo en movimiento fue en una propuesta de investigadores de IBM al grupo MPEG en 1989. ^{[ 11 ] [ 12 ]} Esta propuesta extendió el uso de la codificación aritmética de JPEG intraframe a la codificación de vídeo interframe.

En 1999, Youngjun Yoo ( Texas Instruments ), Young Gap Kwon y Antonio Ortega ( Universidad del Sur de California ) presentaron una forma de codificación aritmética binaria adaptativa al contexto. ^{[ 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érdidas
• Codificación de longitud variable adaptativa al contexto (CAVLC)