Ir al contenido

Context-Adaptive Variable Length Coding

De Wikipedia, la enciclopedia libre
Esta es una versión antigua de esta página, editada a las 19:41 30 nov 2008 por New.limit (discusión · contribs.). La dirección URL es un enlace permanente a esta versión, que puede ser diferente de la versión actual.

Resumen

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.

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 aquél 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 VLC.

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

Características de la información a codificar

Un bloque de luminancia puede considerarse una subdivisión de una imagen en escala de grises. En este caso consideraremos, de manera muy simplificada, que la imagen se ha dividido muchos en bloques de tamaño 4x4 píxeles, con lo cual cada uno de los bloques que componen la imagen estará formado por 16 píxeles. Cada uno de estos píxeles tendrá asignado un valor comprendido entre 0 y 255 de forma que el color negro se corresponde al valor 0, el color blanco al valor 255 y el resto de valores se corresponderán a los distintos tonos de gris.

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:

Escaneo de coeficientes del bloque 4x4
Secuencia resultante: 120,64,12,24,110,8,43,10,0,11,33,98,55,12,21,0

Esta codificación resulta muy poco conveniente para ser transmitida, porque no presenta redundancia alguna y a causa de ello nos veríamos forzados a transmitir los 16 valores. Es aquí donde entra en juego la transformación: el objetivo de la misma es tratar de representar la información contenida en el bloque 4x4 de una forma que nos permita no tener que transmitir todos los valores del bloque. Si la aplicamos, los valores del bloque de tamaño 4x4 anterior tendrán este aspecto:

Bloque sin transformar
Bloque transformado

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.

Si ahora quisiéramos transmitir estos valores, podríamos hacerlo enviando únicamente los valores que son distintos de cero, asumiendo que los píxeles que no enviamos valdrán cero. Esta es la esencia del CAVLC.

El orden en el que se transmiten los valores es el que indican las flechas de color rojo. Esta forma tan peculiar de ordenar los bits va a permitir que en la secuencia resultante se agrupen por un lado los píxeles de valor distinto de cero y por otro los píxeles de valor cero. Así pues, la secuencia que deberíamos transmitir sería la siguiente:

Escaneo de coeficientes del bloque 4x4
Secuencia resultante: 7,6,-2,0,-1,0,0,1,0,0,0,0,0,0,0,0

Elementos de la CAVLC

La codificación CAVLC se puede dividir en dos conceptos:

  • La codificación en sí de los valores obtenidos tras la transformación
  • Parámetros auxiliares

Debe tenerse en cuenta que CAVLC no no hace uso en ningún momento de los píxeles de valor cero que quedan agrupados al final de la secuencia. Es por este motivo que puede considerarse que la secuencia que se va a transmitir será en realidad:

Secuencia que considerará el codificador:
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 valores. En general, los parámetros auxiliares están diseñados para intentar transmitir todavía menos valores. Las características que van a intentar explotar son los píxeles de valor cero que han quedado entre otros píxeles de valor distinto de cero y los píxeles de valor 1 y -1.

Número de coeficientes no nulos (N) y número de píxeles con valor 1 en la cola de la secuencia (T1).

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

Información de signo

Para los píxeles 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 píxeles con valor cero hay antes de cada píxel de valor distinto de cero. Esto se hace a través de los parámetros siguientes:

Número total de ceros

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

Run before

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 píxel 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 píxeles. Los valores Run Before se codifican mediante codificación VLC.

Codificación del valor de los coeficientes

Finalmente, los valores distintos de cero y de uno 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 la estadística que presentan los valores de los píxeles. Puesto que los píxeles de tipo T1 sólo pueden valer 1 ó -1 tansolo se codifica su signo. Así pues, el primer valor que se codificará será el -2 e irá después de la codificación de +, - que representarán a los píxeles de valor 1 y -1 respectivamente.

Véase también

Referencias

  • 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ágina 571 y 572, 2003.