Quantificació vectorial

Pla amb sis zones representades pels seus sis vectors centroides.

La quantificació vectorial és una tècnica de codificació de font emprada per a representar d'una manera compacta un conjunt de valors i té les seves bases en la Teoria de la Informació. Aquesta demostra que sempre que la informació mútua entre les diferents components sigui no nul·la, l'ús de quantificació vectorial conjunta aconseguirà una representació més compacta que la quantificació escalar de cada component per separat. No va anar fins a la dècada dels anys 80, quan la seva realització pràctica es va fer possible a través del treball de Linde, Buzo i Gray (algorisme LBG) . Aquest mètode sorgeix com generalització de l'algorisme de Lloyd.

Un vector pot ser usat per a descriure gairebé qualsevol tipus de patró, com podrà ser un segment d'un senyal de veu o d'una imatge, simplement formant un vector de mostres de la forma d'ona o de la imatge. Però també podrà formar-se un vector amb un conjunt de paràmetres usats per a representar, per exemple, l'envolupant espectral d'un senyal de veu. La quantificació vectorial pot veure's com una forma de reconeixement de patrons on un patró és apariat amb un patró seleccionat d'un conjunt emmagatzemat de llibre de codis.

Per aquest motiu la quantificació vectorial és molt més que una generalització formal de la quantificació escalar. En els últims anys s'ha convertit en una important tècnica en reconeixement de veu i firmes manuscrites com, també en compressió d'àudio i vídeo, i la seva importància i les seves aplicacions van en augment.

Comparança quantificació vectorial i quantificació escalar

La quantificació vectorial pot veure's com una generalització de la quantificació d'un escalar a la quantificació d'un vector. Existeixen interessants paral·lels entre la quantificació escalar i la vectorial i moltes de les tècniques d'anàlisis i de disseny són generalitzacions naturals per al cas escalar.

Una diferència important entre la quantificació escalar i la vectorial és la següent: mentre que la quantificació escalar és usada principalment per a la conversió A/D, la quantificació vectorial és usada al costat d'un processament digital de senyals sofisticat on en general el senyal d'entrada ja té algun tipus de representació digital i la sortida desitjada és una versió comprimida del senyal original.

Llibre de codis

L'objectiu de l'algorisme de generació del llibre de codis és seleccionar els vectors prototip per a representar la distribució d'una gran mostra de vectors d'entrenament, i minimitzar la distorsió total de cada vector d'entrenament pel que fa al vector prototip al que més se sembli. Degut al fet que trobar una solució òptima global és computacionalment prohibitiu, generalment s'obté una solució optima local per mitjà d'un algorisme iteratiu de refinament progressiu. S'han proposat diversos mètodes de generació del llibre de codis, que es podrien dividir en els basats en agrupació (clustering) i els d'aprenentatge aleatori. En els mètodes d'aprenentatge aleatori se seleccionen aleatòriament vectors a partir de les dades d'entrenament i s'emmagatzemen com vectors prototip.

Aquest mètode s'utilitza quan la quantitat de dades d'entrenament és comparable a la grandària del llibre de codis. Per altra banda, els mètodes basats en agrupament es basen normalment en l'algorisme de Lloyd (algorisme de les k-mitges). En aquest cas les dades d'entrenament se separen en grups disjunts, i es calculen els centroides per a cada grup de manera que es minimitzi la distorsió mitjana. Encara que amb aquest mètode no es garanteix l'optimització global, és possible decrementar monòtonament la distorsió mitjana per mitjà de la renovació iterativa del llibre de codis, de manera que s'obtingui una solució òptima local.

Diversos investigadors han demostrat que no es perd gens o gairebé gens de precisió a l'aplicar la quantificació vectorial quan la grandària del llibre de codis és prou gran. Les grandàries del llibre de codis usats generalment en sistemes reconeixedors varia entre 32 i 256 vectors prototip. Normalment no s'usen més de 256 vectors prototip perquè s'ha demostrat que a partir de 128 vectors prototip, l'augment de la grandària del llibre de codis no proporciona una disminució significativa de la distorsió mitjana.

Centroide

Un vector centroide ha de complir la característica de tenir la menor distorció respecte la resta de possibles vectors.

És un vector prototip del llibre de codis triat específicament per minimitzar la distorsió mitjana de la regió que representa.

Formulació

La formulació tècnica de la quantificació vectorial és la següent: sigui x un vector k-dimensional els components de la qual són variables aleatòries de valor real, i sigui $I=\ {y_{i}}$ (amb $1\leq i\leq K$) un conjunt de K vectors prototip denominat llibre de codis, es defineix l'operació quantificar que assigna al vector x l'índex i del vector prototip yi al que més se sembla. Es diu llavors que x es quantifica com i, i s'escriu com $i=\ q(x)$. La grandària del llibre de codis, K, es denomina nombre de nivells. Per a dissenyar aquest llibre de codis, l'espai k-dimensional del vector x es divideix en K regions ${C_{i}}$ on($1\leq i\leq K$), amb un vector yi associat a cada regió $C_{i}$. Llavors el quantificador assigna el vector prototip yi a x si aquest està contingut en la regió $C_{i}$. Això es representa com $q(x)=\ y_{i}$.

Condicions d'optimització

Es diu que un quantificador és òptim si la distorsió total està minimitzada sobre tots els K-nivells de quantificació. Són necessàries dues condicions perquè el quantificador sigui òptim: La primera és que el quantificador es dissenyi utilitzant una regla de selecció de distància mínima. És a dir, $d(x)=\ y_{i}$ si i només si $d(x,y_{i})\leq d(x,y_{j}),j\neq i,1\leq j\leq K$

La segona condició és que cada vector prototip yi sigui triat per a minimitzar la distorsió mitjana en la regió Ci, és a dir, aquest sigui el centreoide de la regió Ci. El càlcul del centroide d'una regió depèn de la definició de la mesura de distorsió.

Bibliografia

• Allen Gersho, Robert M. Gray, Vector quantization and signal compression, Ed. Springer 1992 (en anglès)