Quantificació (processament d'imatge)

La Quantificació, involucrada en el processament d'imatge, és una tècnica de compressió amb pèrdua que consisteix a comprimir un rang de valors a un únic valor. Quan el nombre de símbols discrets en un flux donat es redueix, el flux es torna més comprensible. La quantificació es pot utilitzar en diferents etapes del processament digital:

• En el procés de digitalització: un cop mostrejada la imatge les mostres han de ser quantificades, és a dir, discretitzades en amplitud.
• En imatges digitals, per reduir el nombre de bits amb què es codifiquen els píxels de la imatge.
• En compressió d'imatge, per representar les intensitats o coeficients transformats amb un nombre finit de bits. (quantificació de dades DTC en JPEG i DWT en JPEG 2000).

La quantificació és un procés irreversible, i sempre introdueix distorsió (error o soroll de quantificació)

Nivells de reconstrucció i decisió

Figura 1: Quantificador amb els nivells de reconstrucció i decisió

Un quantificador és una funció “Q” que transforma una variable contínua “u” en una variable discreta que pren valors en un conjunt finit {r1, ..., rL}. Aquests “L” valors s'anomenen nivells de reconstrucció.

Es defineix un conjunt de “L+1” nivells de decisió creixents en la variable contínua,” {tk, k = 1, ..., L +1} “on “t1” i “tL +1” són els valors màxim i mínim que pren la variable contínua “u”.

Si el valor d'”u” pertany a l'interval “[tk, tk +1)” llavors “Q(u) = rk”, és a dir, s'assigna au el nivell de reconstrucció “rk”.

Tipus de Quantificadors (imatges en gris)

Quantificador uniforme

Quantificació d'una imatge de 8 a 2 bits/pixel

El quantificador més senzill és el quantificador uniforme, on els nivells de reconstrucció i de decisió estan equiespaiats, dividint el rang de valors de “u” en “L” intervals iguals. Quedant així també el pas de quantificació “q” (diferencia entre nivells) constant.

• Pas de quantificació: $q=(tL+1-t1)/L$
• Nivells de decisió: $tk=t1+q*(K-1)$
• Nivells de reconstrucció: $rk=tk+q/2$

Funciona exclusivament bé quan la distribució de l'entrada és uniforme, encara sempre dona una SNR molt baixa.

Max Lloyd

El quantificador Max Lloyd minimitza el MSE (mínim error quadràtic mitjà) per a un nombre donat de nivells de reconstrucció. Això el fa un dels quantificadors mes optims. Sigui u una variable aleatòria amb funció de densitat de probabilitat p (u).
Busquem els nivells de decisió i de reconstrucció que minimitzin l'error quadràtic mitjà:

$\varepsilon =E\left[(u-Q(u))^{2}\right]=\int \limits _{t_{1}}^{t_{L+1}}(u-Q(u))^{2}p_{u}(u)du=\sum _{i=1}^{L}\int \limits _{t_{i}}^{t_{i+1}}(u-r_{i})^{2}p_{u}(u)du$

Per minimitzar aquesta expressió, es calculen les seves derivades respecte tk i rk, i s'igualen a zero. Aïllant després tk i rk s'obtenen les següents fórmules:

$t_{k}={\frac {r_{k}+r_{k+1}}{2}}\qquad r_{k}={\frac {\int _{t_{k}}^{t_{k+1}}up_{u}(u)du}{\int _{t_{k}}^{t_{k+1}}p_{u}(u)du}}$re

Els nivells de reconstrucció són els centroides de les àrees sota p (u), sobre els intervals de decisió especificats. Els nivells de decisió es troben en el punt mitjà entre els nivells de reconstrucció.

En general, és difícil trobar una solució tancada a aquestes equacions per a una p (u) no trivial, de manera que aquests valors es calculen i tabulen utilitzant mètodes numèrics.

Falsos Contorns

Imatge amb fals contorns per una quantificació amb pocs nivells.

Quan el nombre de nivells de reconstrucció no és suficient apareix un fenomen visual: falsos contorns.
En general, per a imatges monocromàtiques "naturals", una quantificació uniforme amb 256 nivells és suficient per obtenir una imatge de bona qualitat(encara que l'ull humà només pugui distingir 16 nivells de gris diferents). Els falsos contorns comencen a aparèixer en utilitzar menys de 6 bits per píxel. Visualment un fals contorn és quan dos objectes que es solapen en l'espai i de nivells de gris propers passen a ser visualment un sol objecte d'un mateix nivell de gris a causa de la quantificació.
Aquests falsos contorns ens donarien problemes en diferents apartats del processament de la imatge, no només en el camp visual, ja sigui a l'hora de detectar contorns amb mascares de convolució, detecció de regions, ens la selecció o eliminació de camps amb càlculs morfològics amb elements estructurants de 4 veïns, i molts altres càlculs basics per processar imatges.
Utilitzant un quantificador d'error quadràtic mínim és possible quantificar els nivells amb 5 o 6 bits per píxel sense que es produeixin falsos contorns.

Tipus de Quantificadors (imatges en color)

La quantificació del color redueix el nombre de colors usats en una imatge, això és important per visualitzar imatges en dispositius que suporten un nombre limitat de colors i per eficiència de compressió de certs tipus d'imatges. La majoria dels editors d'imatge i molts sistemes operatius suporten de forma nativa la quantificació del color.

Quantificador Color uniforme

Imatge de color quantificada uniformement

Cada component es tracta de manera independent representant l'espai color com un cub on cada eix es divideix en segments d'igual grandària. Els plans perpendiculars als eixos que passen pels punts de divisió determinen regions en l'espai color. El nombre de regions obtingudes depèn de com es divideixi cada eix.
Exemple: Dividir eix vermell i verd en 8 segments (3 bits per component) i l'eix blau en 4 segments (2 bits). El cub és dividit en 256 parts o regions.
Per a cada color, el color representatiu (que s'agrega a la paleta de colors) és la mitjana dels colors de la regió. A cada color C a la imatge original, s'assigna el color representatiu de la regió a la qual pertany C.
Característiques: Algoritme ràpid i fàcil d'implementar, però no dona bons resultats, ja que les divisions no tenen en compte el contingut de la imatge.

Median cut

Divisió del cub RGB per a una quantificacio de Median cut

Es considera que cada entrada a la paleta representi el mateix nombre de píxels en la imatge original. L'espai color es divideix segons la distribució dels colors a la imatge.
Algorisme: Trobar la menor regió rectangular que conté tots els colors de la imatge i ordenar els colors al llarg de l'eix més llarg de la regió rectangular. Dividir la regió en dues parts, segons el valor de la mitjana de la llista ordenada. Repetir el procés fins a tenir 256 regions (en cada pas es divideixen totes les regions obtingudes fins ara). Els colors representatius s'obtenen mitjana dels colors de cada regió.
Característiques: En utilitzar informació de la imatge per dividir l'espai, els resultats solen ser millors que els algoritmes de quantificació uniforme. El cost computacional i de memòria no és més gran que el dels algoritmes de popularitat.

Quantificador no uniforme (popularitat)

El quantificador ideal no uniforme seria agrupar punts en l'espai color 3D, on els punts representen colors que apareixen a la imatge original definit grups (clústers) de colors similars, i buscant un color representatiu per a cada clúster.
Es pot implementar de moltes maneres, una d'elles és mitjanant l'algoritme de popularitat:
Realitza inicialment una quantificació uniforme, dividint l'espai en moltes regions, i tria les regions més utilitzades. El pas de quantificació és 4 a cada eix: 64x64x64 = 262144 regions. Per a cada regió, es calcula el seu color representatiu com la mitjana de colors de la regió. S'assigna cada píxel a la regió corresponent i es calcula l'histograma de les assignacions. La paleta de colors es crea amb les 256 assignacions més freqüents (del total de 262144 colors). Els colors restants (no elegits) s'assignen al color de la paleta més proper (segons distància Euclidiana) .
Característiques: Algorisme fàcil d'implementar. Dona millor resultat que la quantificació uniforme bàsica, tot i que en algunes imatges pot no donar bon resultat (la quantificació inicial no té en compte el contingut de la imatge).

Altres quantificadors

Pairwise Clustering, Local K-means, Variance-based, Octree.

Quantificació de la freqüència per compressió d'imatge

L'ull humà és bastant bo percebent les petites diferències en el brillantor sobre una àrea relativament extensa, però no és tan bo distingint la mateixa intensitat de variació de brillantor d'alta freqüència. Aquest fet permet reduir la quantitat d'informació requerida ignorant els components d'alta freqüència. Això es realitza dividint cada component en la matriu de freqüències entre una constant per a aquest component, i després arrodonir al valor sencer més proper. Aquesta és l'operació en què més informació es perd de tot el procés. Com a resultat, és habitual que la majoria dels components d'alta freqüència siguin arrodonits a zero i molts dels components restants arribin a un valor positiu petit o negatiu.

Com la visió humana és també més sensible a la luminància que a la crominància, es pot obtenir més compressió treballant sobre un espai de colors no-RGB separant ambdós canals (pe YCbCr) i quantificant.

Matrius de quantificació

Un còdec de vídeo típic funciona separant la imatge en blocs discrets (8 × 8 píxels en el cas de MPEG). Aquests blocs poden ser sotmesos a la transformada de cosinus discreta (DCT) per separar els components de baixa i alta freqüències tant en la direcció horitzontal com en la vertical. El bloc resultant (de la mateixa mida que el bloc original) es divideix per la matriu de quantificació, i cada entrada és arrodonida. Els coeficients de la matriu de quantificació es dissenyen sovint per mantenir certes freqüències en la font per evitar pèrdues en la qualitat de la imatge. Molts codificadors de vídeo (com ara DivX, Xvid, i 3ivx) i algoritmes de compressió estàndard (com ara MPEG-2 i H.264/AVC) permeten utilitzar matrius personalitzades. Alternativament, l'abast de la reducció pot variar multiplicant la matriu de quantificació per un factor d'escalat, el codi d'escalat quantificador, abans de realitzar la divisió. Aquest és un exemple de matriu de coeficients DCT: <! - NOTA: aquesta matriu ha estat generada utilitzant nombres aleatoris, i les altres dues matrius. Pot no funcionar bé amb un iDCT. ->

${\begin{bmatrix}-415&-33&-58&35&58&-51&-15&-12\\5&-34&49&18&27&1&-5&3\\-46&14&80&-35&-50&19&7&-18\\-53&21&34&-20&2&34&36&12\\9&-2&9&-5&-32&-15&45&37\\-8&15&-16&7&-8&11&4&7\\19&-28&-2&-26&-2&7&-44&-21\\18&25&-12&-44&35&48&-37&-3\end{bmatrix}}$

Una matriu de quantificació comú és:

${\begin{bmatrix}16&11&10&16&24&40&51&61\\12&12&14&19&26&58&60&55\\14&13&16&24&40&57&69&56\\14&17&22&29&51&87&80&62\\18&22&37&56&68&109&103&77\\24&35&55&64&81&104&113&92\\49&64&78&87&103&121&120&101\\72&92&95&98&112&100&103&99\end{bmatrix}}$

Dividint els elements de la matriu de coeficients DCT amb aquesta matriu de quantificació, i arrodonint a sencers resulta en:

${\begin{bmatrix}-26&-3&-6&2&2&-1&0&0\\0&-3&4&1&1&0&0&0\\-3&1&5&-1&-1&0&0&0\\-4&1&2&-1&0&0&0&0\\1&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&0&0\end{bmatrix}}$

Per exemple, usant -415 (el coeficient DC) i arrodonint al sencer més proper:

$\mathrm {round} \left({\frac {-415}{16}}\right)=\mathrm {round} \left(-25.9375\right)=-26$

Normalment, aquest procés donarà com a resultat matrius amb valors principalment a la cantonada superior esquerra (baixa freqüència). Utilitzant un ordenament ziga-zaga per agrupar les entrades majors de zero i Run-length encoding, la matriu quantificada pot ser emmagatzemada de forma molt més eficient que la versió no quantificada.