Context-adaptive variable-length coding

Aquest article o secció no cita les fonts o necessita més referències per a la seva verificabilitat.

Les sigles CAVLC corresponen a les inicials de Context-Adaptive Variable Length Coding, que traduït de l'anglès significa codificació adaptativa segons el context de longitud variable. L'objectiu d'aquesta codificació és processar la informació que es vol transmetre o emmagatzemar en un dispositiu de forma que ocupi el mínim espai possible. D'aquesta manera, amb l'ús de la CAVLC serà possible transmetre una imatge en menys temps o fer que ocupi menys espai en el dispositiu d'emmagatzematge. Una característica important d'aquesta codificació és que no té pèrdues i, per tant, es podrà recuperar la informació original a l'aplicar el procés invers.

La codificació CAVLC s'utilitza en l'estàndard de codificació de vídeo MPEG-4 (part 10), per codificar i comprimir la informació que resulta de l'aplicació de la transformació i quantificació d'un bloc de luminància de mida 4x4 píxels.

CAVLC és un mètode de codificació de font, que pertany a la família dels codificadors entròpics. Un codi entròpic és aquell que substitueix les paraules codi d'una font d'informació per altres amb una longitud proporcional a la freqüència de dita paraula. L'objectiu dels codis font és tractar d'eliminar tota la informació que sigui redundant per reduir al màxim la quantitat de dades a transmetre. Un exemple d'aquest tipus de codis seria l'UVLC.

Abans de descriure el funcionament del CAVLC resulta interessant fer un petit estudi de les característiques de la informació que es va a codificar. La descripció d'aquest tipus de mètode de codificació es basarà en l'àmbit de codificació de vídeo segons l'estàndard MPEG-4, part 10.

La unitat elemental és un bloc de píxels d'una mida determinada. Així doncs, de forma simplificada, el pas previ a la codificació és la divisió del quadre o camp que omple en bloc. Per simplificar l'explicació considerarem que codificarem una imatge en escala de grisos, és a dir, sense color. En l'estàndard MPEG-4 s'especifica que la mida d'aquests blocs siguin de 4x4 píxels, amb això es formaran blocs de 16 píxels. Cadascun d'aquest píxels tindran assignats un valor comprés entre 0 i 255 de forma que:

• si el píxel és de color negre s'assignarà el valor 0
• si és de color blanc s'assignarà el valor 255
• si el color del píxel és un to de gris, se li assignarà un valor comprés entre 1 (gris més obscur) i 254 (gris més clar).

Si fóssim a transmetre aquest valors tal qual, podríem enviar, per exemple, un darrere l'altre llegint el bloc per files. La seqüència de bits resultants sería la següent:

Seqüència resultant: 120,63,12,24,110,8,43,10,0,11,33,98,55,12,21,0

Aquesta codificació és molt simple però resulta molt poc convenient per ser transmesa, perquè ens veuríem forçats a transmetre els 16 valors que constitueixen el bloc. Volem que al transmetre ocupi el mínim espai possible, així que haurem d'aplicar una transformació: l'objectiu d'aquesta és representar la informació del bloc d'una forma que ens permetrien transmetre els 16 valors que el componen. Si apliquem aquesta transformació, els valors del bloc de mida 4x4 anterior tindran aquest aspecte:

La diferència més clara entre els dos és l'aparició d'un elevat nombre de píxels en què el valor ara és 0 i a més els valors que no són nuls han quedat agrupat en la cantonada superior esquerra. A partir d'ara utilitzarem la paraula coeficient per referir-nos a cadascun dels valors un cop s'hagi aplicat la transformació. La transformació és reversible, és a dir, que podrem recuperar els valors originals de cada píxel.

Si ara volguéssim transmetre aquests coeficients, podríem fer-ho enviant únicament els que són diferents de 0, assumint que aquests que no s'envien seran 0. Aquesta és la idea bàsica del CAVLC.

La CAVLC utilitza els coeficients obtinguts mitjançant la transformació citada en l'apartat anterior. Això implica que abans de poder aplicar la CAVLC s'haurà de fer la transformació. L'ordre en el que es llegeixen els coeficients del bloc és el que indiquen les fletxes de color vermell. Aquesta forma tan peculiar d'ordenar els valors permetrà agrupar l'inici de la seqüència els coeficients diferents de 0 i al final de la mateixa els coeficients que valen 0. La seqüència que tractarà de comprimir la CAVLC és la següent, per l'exemple proposat:

Seqüència resultant: 7,6,-2,0,-1,0,0,1,0,0,0,0,0,0,0,0

En la codificació CAVLC es poden distingir dos parts diferenciades:

• Paràmetres auxiliars que permetran reduir encara més la quantitat de dades que anem a transmetre.
• La codificació en si dels valors obtinguts després de la transformació.

S'han de tenir en compte que CAVLC no fa ús en cap moment dels coeficients de valor 0 que queden agrupats al final de la seqüència. És per aquest motiu que a partir d'aquest moment poden ignorar-se tots els zeros que queden agrupats al final de la seqüència:

En aquest exemple ens estalviem haver de transmetre la meitat dels coeficients. En general, els paràmetres auxiliars estan dissenyats per intentar transmetre encara menys coeficients. Les característiques que intentaran explotar són els coeficients de valor 0 que han quedat entre altres coeficients de valor diferent de 0 i els coeficients de valor 1 i -1.

Amb aquests paràmetres es tracta d'indicar quants coeficients tenen valors diferents de 0 i quants tenen valor absolut -ja que els valors dels coeficients després de la transformació poden ser tant positius com negatius- igual a un al final de la seqüència. Per el cas de l'exemple N=5 i T1=2.

Pels coeficients que tinguin valor absolut igual a 1, es codifica el seu signe amb un sol bit, mentre que el signe del reste de coeficients diferents de 0 queda integrat en la codificació que s'utilitzi.

Ara només queda especificar quants coeficients de valor 0 hi ha abans de cada coeficient de valor diferent de 0. Això es fa a través dels paràmetres Nombre total de zeros i Run before:

Amb aquest paràmetre s'especifica el nombre de coeficients de valor 0 que han quedat compresos entre valors no nuls. En l'exemple, el nombre total de zeros és 3.

A través d'aquest paràmetre es defineix com es distribueix el nombre total de zeros abans indicat. Així, en l'exemple s'estableix que abans de l'últim coeficient de la seqüència hi ha 2 zeros i abans del penúltim hi ha 1 zero. Els valors del Run before es codifiquen utilitzant la tècnica VLC.

Finalment, els valors diferents de 0 és codifican en ordre invers utilitzant la codificació VLC. El motiu de seguir l'ordre invers de codificació és degut a l'estadística que presenten els valors dels coeficients. Com els coeficients de tipus T1 només poden valer 1 o -1 només es codificarà el seu signe.

Les dades a transmetre seran: els coeficients -2, 6 i 7; els dos T1 representats respectivament per '+' i '--'; els dos valors del Run before que seran 2 i 1 i els paràmetres N i T1 que tindran els valors 5 i 2 respectivament. Sabent que el nombre total de coeficients és 16, serà possible reconstruir el bloc per complet utilitzant els paràmetres que s'acaben de definir.

Mitjançant la utilització de la codificació CAVLC s'aconsegueix explotar la redundància existent en els coeficients transformats reduint la quantitat de dades que han de ser transmeses, disminuint així el temps necessari per la seva transmissió o reduint l'espai d'emmagatzematge necessari sense que hagi pèrdua alguna d'informació.

• UVLC
• CABAC
• Algorisme de Huffman