Salta al contenuto
Note per Studenti Esercizio - Trasformata DCT e quantizzazione di un blocco JPEG (demo del corso)

Esercizio - Trasformata DCT e quantizzazione di un blocco JPEG (demo del corso)

In questa pagina 3

Teoria: Compressione di immagini - DCT e standard JPEGPer comprimere con perdita non basta quantizzare i pixel (non sono sparsi): si applica una trasformata lineare ortogonale che concentra l'energia in pochi coefficienti, si quantizzano i coefficienti e si codificano senza perdita. Le trasformate ortogonali conservano l'MSE ($\frac1N|\mathbf x-\tilde{\mathbf x}|^2=\frac1N|\mathbf y-\tilde{\mathbf y}|^2$). JPEG baseline: si sottrae 128, si divide in blocchi $8\times8$, DCT 2D ($Y=AXA^T$), quantizzazione uniforme con tabella (passi piccoli a bassa frequenza, scalata da un fattore di qualità $Q$), zig-zag scan, DC codificato in modo differenziale con categoria/ampiezza, AC con coppie (run, categoria) e simbolo EOB, codici di Huffman non standardizzati scritti nel file. Esempio completo: un blocco da 512 bit diventa 49 bit (0,766 bit/pixel).Compressione di immagini - DCT e standard JPEG → (DCT, quantizzazione con tabella e fattore di qualità, ricostruzione). Fonte: slide e demo jpeg del corso di Reti di Calcolatori, Ing. Informatica UniPD 2025-26 (blocco numerico delle slide); i conti sono verificati in Python (DCT ortonormale). La codifica lossless degli stessi indici è in Esercizio - Zig-zag, run-length e flusso di bit di un blocco JPEG (domande ed esercizi del corso).

Testo

Un blocco 8×88\times8 di luminanza, già centrato (sottratto 128), è

X=[−192−5−2−1217−14−145−4−321636−34−52−3−362231−4970−4−2112910−42140−622033−11−3312−7−792421−11−263−1101627−8−6−52−1072027−2833]X=\begin{bmatrix}-19&2&-5&-2&-1&2&17&-14\\-14&5&-4&-3&2&16&36&-34\\-5&2&-3&-3&6&22&31&-49\\7&0&-4&-2&11&29&10&-42\\14&0&-6&2&20&33&-11&-33\\12&-7&-7&9&24&21&-11&-26\\3&-11&0&16&27&-8&-6&-5\\2&-10&7&20&27&-28&3&3\end{bmatrix}

(a) Calcolare il coefficiente DC e verificare la conservazione dell'energia. (b) Quantizzare la DCT con la tabella standard per luminanza scalata a qualità Q=30Q=30. (c) Ricostruire il blocco e calcolare MSE e PSNR. (d) Come cambia il risultato con altri valori di QQ? La DCT del blocco è (valori arrotondati)

Y≈[8,58,3−58,759,1−20,319,5−21,413,2−11,1−15,07,617,3−61,612,8−15,7−9,7−3,6−18,413,1−52,219,62,0−20,815,2−2,61,6−0,64,513,0−16,115,6−13,4−0,53,65,1−7,98,8−7,05,7−1,1−4,2−1,20,5−5,14,8−0,61,50,7−2,32,6−1,52,0−0,32,0−0,30,4−0,70,9−0,8−2,01,7−2,60,70,1]Y\approx\begin{bmatrix}8{,}5&8{,}3&-58{,}7&59{,}1&-20{,}3&19{,}5&-21{,}4&13{,}2\\-11{,}1&-15{,}0&7{,}6&17{,}3&-61{,}6&12{,}8&-15{,}7&-9{,}7\\-3{,}6&-18{,}4&13{,}1&-52{,}2&19{,}6&2{,}0&-20{,}8&15{,}2\\-2{,}6&1{,}6&-0{,}6&4{,}5&13{,}0&-16{,}1&15{,}6&-13{,}4\\-0{,}5&3{,}6&5{,}1&-7{,}9&8{,}8&-7{,}0&5{,}7&-1{,}1\\-4{,}2&-1{,}2&0{,}5&-5{,}1&4{,}8&-0{,}6&1{,}5&0{,}7\\-2{,}3&2{,}6&-1{,}5&2{,}0&-0{,}3&2{,}0&-0{,}3&0{,}4\\-0{,}7&0{,}9&-0{,}8&-2{,}0&1{,}7&-2{,}6&0{,}7&0{,}1\end{bmatrix}

Soluzione

(a) DC ed energia

Per la DCT ortonormale 8×88\times8 il coefficiente (0,0)(0,0) vale Y(0,0)=28c(0)2∑m,nx(m,n)=14⋅12∑x=18∑xY(0,0)=\frac28c(0)^2\sum_{m,n}x(m,n)=\frac14\cdot\frac12\sum x=\frac18\sum x. La somma di tutti i 64 valori del blocco è 6868, quindi Y(0,0)=688=8,5Y(0,0)=\frac{68}8=8{,}5 ✓. (Il DC è 64=8\sqrt{64}=8 volte la media del blocco, che vale 6864=1,06\frac{68}{64}=1{,}06.)

Ancora un controllo con la formula generale, per (u,v)=(0,1)(u,v)=(0,1): Y(0,1)=28⋅12∑x(m,n)cos⁡(2n+1)π16≈8,31Y(0,1)=\frac28\cdot\frac1{\sqrt2}\sum x(m,n)\cos\frac{(2n+1)\pi}{16}\approx8{,}31 ✓.

Conservazione dell'energia (la DCT è ortogonale): ∑x2=19 062\sum x^2=19\,062 e ∑Y2=19 062\sum Y^2=19\,062. Perciò l'errore che si fa quantizzando i coefficienti è lo stesso errore che si ritrova sui pixel (vedi (c)).

(b) Quantizzazione con Q=30Q=30

SF=500030=166,7\mathrm{SF}=\frac{5000}{30}=166{,}7, quindi q=min⁡ ⁣(256,⌈1,667 q∗⌉)q=\min\!\left(256,\lceil1{,}667\,q^*\rceil\right) con q∗q^* la tabella standard (valori 16,11,10,16,24,…16,11,10,16,24,\dots). Alcuni passi: q(0,0)=⌈1,667⋅16⌉=⌈26,7⌉=27q(0,0)=\lceil1{,}667\cdot16\rceil=\lceil26{,}7\rceil=27; q(0,1)=⌈18,3⌉=19q(0,1)=\lceil18{,}3\rceil=19; q(0,2)=⌈16,7⌉=17q(0,2)=\lceil16{,}7\rceil=17; q(0,3)=27q(0,3)=27; q(7,7)=⌈1,667⋅99⌉=165q(7,7)=\lceil1{,}667\cdot99\rceil=165. Tabella:

q=[27191727406785102202024324497100922422274067951159424293749851451341043037629411418217212940599210713517418915482107130145172202200169120154159164187167172165]q=\begin{bmatrix}27&19&17&27&40&67&85&102\\20&20&24&32&44&97&100&92\\24&22&27&40&67&95&115&94\\24&29&37&49&85&145&134&104\\30&37&62&94&114&182&172&129\\40&59&92&107&135&174&189&154\\82&107&130&145&172&202&200&169\\120&154&159&164&187&167&172&165\end{bmatrix}

Indici round(Y/q)\mathrm{round}(Y/q), elemento per elemento. Esempi: Y(0,0)/27=0,31→0Y(0,0)/27=0{,}31\to0; Y(0,2)/17=−58,7/17=−3,45→−3Y(0,2)/17=-58{,}7/17=-3{,}45\to-3; Y(0,3)/27=59,1/27=2,19→2Y(0,3)/27=59{,}1/27=2{,}19\to2; Y(0,4)/40=−0,51→−1Y(0,4)/40=-0{,}51\to-1; Y(1,0)/20=−0,56→−1Y(1,0)/20=-0{,}56\to-1; Y(1,4)/44=−61,6/44=−1,40→−1Y(1,4)/44=-61{,}6/44=-1{,}40\to-1; Y(2,3)/40=−52,2/40=−1,31→−1Y(2,3)/40=-52{,}2/40=-1{,}31\to-1; Y(3,4)/85=0,15→0Y(3,4)/85=0{,}15\to0. Risultato:

idx=[00−32−1000−1−101−10000−10−100000000000000000000000000000000000000000000]\mathrm{idx}=\begin{bmatrix}0&0&-3&2&-1&0&0&0\\-1&-1&0&1&-1&0&0&0\\0&-1&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&0&0&0&0&0\\0&0&0&0&0&0&0&0\end{bmatrix}

Solo 99 indici su 6464 sono diversi da zero ("molti degli indici di quantizzazione sono nulli, rimangono pochi valori da codificare in lossless"): è il motivo per cui il blocco si comprime bene. Si noti che il DC è diventato 0: la media del blocco (8,5 su una scala che nel blocco centrato va da −128-128 a 127127) è piccola rispetto al passo 27.

(c) Ricostruzione, MSE e PSNR

Il decodificatore moltiplica gli indici per qq (dequantizzazione, "quantizzazione inversa" con abuso di termine): Y~=idx⋅q=[00−5154−40000−20−20032−440000−220−4000000000000000000000000000000000000000000000]\tilde Y=\mathrm{idx}\cdot q=\begin{bmatrix}0&0&-51&54&-40&0&0&0\\-20&-20&0&32&-44&0&0&0\\0&-22&0&-40&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&0&0&0&0&0\\0&0&0&0&0&0&0&0\end{bmatrix} (per esempio −3⋅17=−51-3\cdot17=-51, 2⋅27=542\cdot27=54, −1⋅40=−40-1\cdot40=-40), applica la DCT inversa e risomma 128, arrotondando:

X^+128=[101124127114127154144107109125124114130156141101123128121115135157136941331301201191401551319213713012212514214912797133130128134142140125109125128135142140131124123119127140147138125124132]\hat X+128=\begin{bmatrix}101&124&127&114&127&154&144&107\\109&125&124&114&130&156&141&101\\123&128&121&115&135&157&136&94\\133&130&120&119&140&155&131&92\\137&130&122&125&142&149&127&97\\133&130&128&134&142&140&125&109\\125&128&135&142&140&131&124&123\\119&127&140&147&138&125&124&132\end{bmatrix}

Confronto con l'originale (X+128X+128, per esempio 109109 in alto a sinistra): l'errore massimo è 2525 (riga 7, colonna 5: −28+128=100-28+128=100 contro 125125), l'errore quadratico totale è 54775477, quindi MSE=547764=85,58\mathrm{MSE}=\frac{5477}{64}=85{,}58 e PSNR=10log⁡10255285,58=48,13−19,32=28,8 dB.\mathrm{PSNR}=10\log_{10}\frac{255^2}{85{,}58}=48{,}13-19{,}32=28{,}8\ \text{dB}. Controllo sul dominio della trasformata: l'errore sui coefficienti 164∑(Y−Y~)2=85,55≈85,58\frac1{64}\sum(Y-\tilde Y)^2=85{,}55\approx85{,}58 (la differenza, 0,03, è dovuta solo all'arrotondamento a interi dei pixel): la trasformata ortogonale conserva le distanze, quindi si può ragionare sull'errore direttamente sui coefficienti. 28,8 dB è sotto i 30 dB: qualità "scadente" nella scala empirica; ricordare che è un blocco con molto dettaglio e Q=30Q=30 è una qualità bassa.

(d) Effetto della qualità

Stesso blocco con diversi QQ (tabella q∗q^* scalata con SF=5000/Q\mathrm{SF}=5000/Q per Q≤50Q\le50, 200−2Q200-2Q per 50<Q≤9950<Q\le99, 1 per Q=100Q=100):

QQ SF\mathrm{SF} indici non nulli MSE PSNR
10 500 2 197,6 25,2 dB
30 166,7 9 85,6 28,8 dB
50 100 13 64,9 30,0 dB
70 60 16 44,9 31,6 dB
90 20 34 5,5 40,8 dB
100 1 58 0,14 56,7 dB

Più alta è la qualità, più indici non nulli (più bit) e meno errore: è il compromesso tasso-distorsione. A Q=100Q=100 la tabella è tutta di 1: quasi nessuna quantizzazione (l'errore residuo viene solo dall'arrotondamento a interi); a Q=10Q=10 rimangono 2 indici e si perde quasi tutto il dettaglio.

Errori tipici

  • Dimenticare il centraggio (−128-128) prima della DCT e la risomma di 128 dopo l'IDCT.
  • Quantizzare con ⌊⋅⌋\lfloor\cdot\rfloor invece di round\mathrm{round}.
  • Confondere indici e valori ricostruiti: al decoder si moltiplica per la stessa tabella qq.
  • Usare per Q=30Q=30 il fattore 5000Q\frac{5000}{Q} senza dividere per 100 (la tabella va scalata per SF100=1,667\frac{\mathrm{SF}}{100}=1{,}667).
  • Calcolare il PSNR con 255 al posto di 2b−12^b-1 in segnali a bit diversi (qui 8 bit: 255 è corretto).

Versione ripasso

Blocco XX centrato (−128-128) 8×88\times8, ∑x=68\sum x=68, ∑x2=19 062\sum x^2=19\,062. DC =18∑x=688=8,5=\frac18\sum x=\frac{68}8=8{,}5 (DCT ortonormale: 2Nc(0)2∑x\frac{2}{N}c(0)^2\sum x). Parseval: ∑Y2=∑x2=19 062\sum Y^2=\sum x^2=19\,062: la trasformata ortogonale conserva le distanze, l'errore sui coefficienti è l'errore sui pixel.

Quantizzazione. SF=5000Q\mathrm{SF}=\frac{5000}{Q} (Q≤50Q\le50), 200−2Q200-2Q (50<Q≤9950<Q\le99), 11 (Q=100Q=100); q=min⁡(256,⌈SF100q∗⌉)q=\min(256,\lceil\frac{\mathrm{SF}}{100}q^*\rceil). Q=30Q=30: SF=166,7\mathrm{SF}=166{,}7, fattore 1,6671{,}667: q(0,0)=27q(0,0)=27, q(0,1)=19q(0,1)=19, q(0,2)=17q(0,2)=17, q(0,3)=27q(0,3)=27, q(7,7)=165q(7,7)=165. Indici round(Y/q)\mathrm{round}(Y/q): Y(0,2)=−58,7Y(0,2)=-58{,}7, q=17→−3q=17\to-3; Y(0,3)=59,1Y(0,3)=59{,}1, q=27→2q=27\to2; Y(1,4)=−61,6Y(1,4)=-61{,}6, q=44→−1q=44\to-1; Y(2,3)=−52,2Y(2,3)=-52{,}2, q=40→−1q=40\to-1; DC 0,31→00{,}31\to0. Indici: righe [0,0,−3,2,−1][0,0,-3,2,-1], [−1,−1,0,1,−1][-1,-1,0,1,-1], [0,−1,0,−1][0,-1,0,-1], resto 0: 9 indici non nulli su 64.

Ricostruzione. Y~=idx⋅q\tilde Y=\mathrm{idx}\cdot q (−3⋅17=−51-3\cdot17=-51, 2⋅27=542\cdot27=54, −1⋅40=−40-1\cdot40=-40, −1⋅20=−20-1\cdot20=-20, −1⋅22=−22-1\cdot22=-22, −1⋅44=−44-1\cdot44=-44, 1⋅32=321\cdot32=32), IDCT, +128+128, arrotondamento. Primo elemento: 109→101109\to101; errore massimo 2525. Errore quadratico totale 54775477: MSE=547764=85,58\mathrm{MSE}=\frac{5477}{64}=85{,}58; PSNR=48,13−19,32=28,8\mathrm{PSNR}=48{,}13-19{,}32=28{,}8 dB. Sul dominio dei coefficienti 164∑(Y−Y~)2=85,55\frac1{64}\sum(Y-\tilde Y)^2=85{,}55 (stesso valore a meno degli arrotondamenti).

Effetto di QQ.

QQ non nulli MSE PSNR
10 2 197,6 25,2 dB
30 9 85,6 28,8 dB
50 13 64,9 30,0 dB
70 16 44,9 31,6 dB
90 34 5,5 40,8 dB
100 58 0,14 56,7 dB

Più qualità: più indici non nulli (più bit), meno errore.

Errori tipici: niente centraggio ±128\pm128; ⌊⋅⌋\lfloor\cdot\rfloor invece di round\mathrm{round}; non moltiplicare gli indici per qq al decoder; usare 5000Q\frac{5000}{Q} senza dividere per 100; leggere 28,8 dB come "buono" (è sotto 30).

Teoria: Compressione di immagini - DCT e standard JPEGPer comprimere con perdita non basta quantizzare i pixel (non sono sparsi): si applica una trasformata lineare ortogonale che concentra l'energia in pochi coefficienti, si quantizzano i coefficienti e si codificano senza perdita. Le trasformate ortogonali conservano l'MSE ($\frac1N|\mathbf x-\tilde{\mathbf x}|^2=\frac1N|\mathbf y-\tilde{\mathbf y}|^2$). JPEG baseline: si sottrae 128, si divide in blocchi $8\times8$, DCT 2D ($Y=AXA^T$), quantizzazione uniforme con tabella (passi piccoli a bassa frequenza, scalata da un fattore di qualità $Q$), zig-zag scan, DC codificato in modo differenziale con categoria/ampiezza, AC con coppie (run, categoria) e simbolo EOB, codici di Huffman non standardizzati scritti nel file. Esempio completo: un blocco da 512 bit diventa 49 bit (0,766 bit/pixel).Compressione di immagini - DCT e standard JPEG →.

Esercizi su questo argomento

Teoria collegata