Context-Adaptive Variable Length Coding

Las siglas CAVLC corresponden a las iniciales de Context-Adaptive Variable Length Coding, que traducido del inglés significa codificación adaptativa según el contexto de longitud variable. El objetivo de esta codificación es procesar la información que se quiere transmitir o almacenar en un dispositivo de forma que ocupe el mínimo espacio posible. De esta manera, con el uso de la CAVLC será posible transmitir una imagen en menos tiempo o hacer que ocupe menos espacio en el dispositivo de almacenamiento. Una característica importante de esta codificación es que no tiene pérdidas y que por lo tanto se podrá recuperar la información original al aplicar el proceso inverso.

La codificación CAVLC se emplea en el estándar de codificación de vídeo MPEG-4 (parte 10), para codificar y comprimir la información que resulta de la aplicación de la transformación y cuantificación de un bloque de luminancia de tamaño 4x4 píxels.

CAVLC es un método de codificación de fuente, que pertenece a la familia de los codificadores entrópicos. Un código entrópico es aquel que sustituye las palabras código de una fuente de información por otras cuya longitud es proporcional a la frecuencia con la que aparece dicha palabra. El objetivo de los códigos de fuente es tratar de eliminar toda aquella información que sea redundante para reducir al máximo la cantidad de datos a transmitir. Un ejemplo de este tipo de códigos es la Codificación Huffman o la Codificación Variable Length Coding (VLC).

Antes de describir el funcionamiento de la CAVLC resulta interesante hacer un pequeño estudio de las características de la información que se va a codificar. De esta manera la comprensión de la CAVLC resultará más sencilla y se pondrá en relevancia la utilidad de la misma. La descripción de este método de codificación se contextualizará en el ámbito de codificación de vídeo según el estándar MPEG-4, parte 10.

La unidad elemental que maneja la CAVLC es un bloque de píxeles de un tamaño determinado. Así pues, de forma simplificada, el paso previo a la codificación es la división del cuadro o campo completo en bloques. Para simplificar la explicación consideraremos que vamos a codificar una imagen en escala de grises, es decir, sin color. En el estándar MPEG-4 se especifica que el tamaño de estos bloques sea de 4x4 píxeles, con lo cual cada uno de ellos estará formado por 16 píxeles. Cada uno de estos píxeles tendrá asignado un valor comprendido entre 0 y 255 de forma que:

• si el píxel es de color negro se le asignará el valor 0
• si es de color blanco se le asignará el valor 255
• si el color del píxel es un tono de gris, se le asignará un valor comprendido entre 1 (gris más oscuro) y 254 (gris más claro).

Si fuéramos a transmitir estos valores tal cual, podríamos enviarlos, por ejemplo, uno detrás de otro leyendo el bloque por filas. La secuencia de bits resultante sería la siguiente:

Secuencia resultante: 120,63,12,24,110,8,43,10,0,11,33,98,55,12,21,0

Esta codificación es muy simple pero resulta muy poco conveniente para ser transmitida, porque nos veríamos forzados a transmitir los 16 valores que constituyen el bloque. Puesto que queremos que la información a transmitir ocupe el mínimo espacio posible, tendremos que aplicar una transformación: el objetivo de la misma es representar la información contenida en el bloque de una forma que nos permita no tener que transmitir los 16 valores que lo componen. Si aplicamos esta transformación, los valores del bloque de tamaño 4x4 anterior tendrán este aspecto:

La diferencia más clara entre ambos es la aparición de un elevado número de píxels cuyo valor ahora es cero y que además los valores que no son nulos han quedado agrupados en la esquina superior izquierda. A partir de ahora emplearemos la palabra coeficiente para referirnos a cada uno de los valores una vez se les ha aplicado la transformación. Cabe destacar que esta transformación es reversible, es decir, que podremos recuperar los valores originales de cada píxel.

Si ahora quisiéramos transmitir estos coeficientes, podríamos hacerlo enviando únicamente los que son distintos de cero, asumiendo que aquellos que no enviamos valdrán cero. Esta es la idea básica del CAVLC.

La CAVLC utiliza los coeficientes obtenidos mediante la transformación citada en el apartado anterior. Esto implica que antes de poder aplicar la CAVLC habrá que llevar a cabo la transformación. El orden en el que se leen los coeficientes del bloque es el que indican las flechas de color rojo. Esta forma tan peculiar de ordenarlos va a permitir agrupar al inicio de la secuencia los coeficientes distintos de cero y al final de la misma los coeficientes que valen cero. Así pues, la secuencia que va a tratar de comprimir la CAVLC es la siguiente, para el ejemplo propuesto:

Secuencia resultante: 7,6,-2,0,-1,0,0,1,0,0,0,0,0,0,0,0

En la codificación CAVLC se pueden distinguir dos partes diferenciadas:

• Parámetros auxiliares que permitirán reducir aún más la cantidad de datos que vamos a transmitir.
• La codificación en sí de los valores obtenidos tras la transformación.

Debe tenerse en cuenta que CAVLC no hace uso en ningún momento de los coeficientes de valor cero que quedan agrupados al final de la secuencia. Es por este motivo que a partir de este momento pueden ignorarse todos los ceros que quedan agrupados al final de la secuencia:

Secuencia resultante de la transformación	Secuencia que realmente considerará el codificador CAVLC
7,6,-2,0,-1,0,0,1,0,0,0,0,0,0,0,0	7,6,-2,0,-1,0,0,1

Nótese que, en este ejemplo, de entrada nos ahorramos tener que transmitir la mitad de los coeficientes. En general, los parámetros auxiliares están diseñados para intentar transmitir todavía menos coeficientes. Las características que van a intentar explotar son los coeficientes de valor cero que han quedado entre otros coeficientes de valor distinto de cero y los coeficientes de valor 1 y -1.

Con estos parámetros se trata de indicar cuántos coeficientes tienen valores distintos de cero y cuántos tienen valor absoluto -ya que los valores adoptados por los coeficientes tras la transformación pueden ser tanto positivos como negativos- igual a uno al final de la secuencia. Este segundo parámetro tiene interés en tanto que es bastante frecuente que tras los coeficientes iniciales haya cierto número de coeficientes cuyos valores se alternan entre 1, -1 y 0. Para el caso del ejemplo N=5 y T1=2.

Para los coeficientes que tengan valor absoluto igual a uno, se codifica su signo con un solo bit, mientras que el signo del resto de coeficientes distintos de cero queda integrado en la codificación que se emplee.

Ahora sólo queda especificar cuántos coeficientes de valor cero hay antes de cada coeficiente de valor distinto de cero. Esto se hace a través de los parámetros Número total de ceros y Run before:

Con este parámetro se especifica el número de coeficientes de valor cero que han quedado comprendidos entre valores no nulos. En el ejemplo, el número total de ceros es 3.

A través de este parámetro se define cómo se distribuye el número total de ceros antes indicado. Así pues, en el ejemplo se establece que antes del último coeficiente de la secuencia hay 2 ceros y antes del penúltimo hay 1 cero. Puesto que especificando estos dos valores ya se ha alcanzado el número total de ceros, ya no es necesario indicar nada más para el resto de coeficientes. Los valores Run before se codifican empleando la técnica VLC.

Finalmente, los valores distintos de cero se codifican en orden inverso empleando una codificación VLC. El motivo de seguir el orden inverso de codificación al que se muestra en la figura se debe a que es el más adecuado a la estadística que presentan los valores de los coeficientes. Puesto que los coeficientes de tipo T1 solamente pueden valer 1 o −1, solamente se codifica su signo.

Así pues, los datos que se transmiten serán: los coeficientes −2, 6 y 7; los dos T1 representados respectivamente por '+' y '–'; los dos valores del Run before que serán 2 y 1 y los parámetros N y T1 que tendrán los valores 5 y 2 respectivamente. Sabiendo que el número total de coeficientes es 16, será posible reconstruir el bloque por completo empleando los parámetros que se acaban de definir.

Mediante el empleo de la codificación CAVLC se logra explotar la redundancia existente en los coeficientes transformados reduciendo en gran medida la cantidad de datos que deben ser transmitidos, disminuyendo así el tiempo necesario para su transmisión o reduciendo el espacio de almacenamiento necesario sin que haya pérdida alguna de información.

Codificación Huffman

Codificación Video Coding Layer

• Wiegand, T; Sullivan, G; Bjøntegaard, G; Luthra, A: "Overview of the H.264/AVC Video Coding Standard", IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL 13., NO. 7, páginas 571 y 572, 2003.