Compressione di immagini - DCT e standard JPEG

Un'immagine a colori occupa 24 bit per pixel (12 in 4:2:0, Audio, immagini e video digitali non compressi e spazi di coloreIl parlato (banda 200-3400 Hz) si digitalizza con $F_c=8$ kHz e 8 bit per campione: 64 kbit/s (PCM, pacchetti di 20 ms = 160 campioni = 160 byte). La musica (banda fino a 20 kHz) con $F_c=44{,}1$ kHz, 16 bit, 2 canali: 1,411 Mbit/s. Un'immagine a colori RGB ha 3 canali da 8 bit (24 bit per pixel); nello spazio YCbCr, ottenuto con una rotazione dello spazio colore, l'occhio è molto meno sensibile alla crominanza e si scartano 3 campioni su 4 di Cb e Cr (4:2:0), dimezzando i dati: $1{,}5\cdot H\cdot W$ campioni per immagine. Un video non compresso costa $H,W,1{,}5,b,f$ bit/s (1080p a 50 Hz: 1,244 Gbit/s, 4K: 5,3 Gbit/s): serve la compressione.Audio, immagini e video digitali non compressi e spazi di colore →). La codifica lossless (Codifica lossless - entropia, Huffman e codifiche a dizionarioLa codifica lossless rappresenta i simboli di una sorgente con parole di codice a lunghezza variabile in modo invertibile; si usano codici a prefisso (istantanei). L'entropia $H(X)=\sum p_i\log_2\frac1{p_i}$ è il limite: $H(X)\le\mathcal L^*<H(X)+1$ (Shannon), con uguaglianza se le probabilità sono potenze di 1/2. Il codice di Huffman è ottimo ma lascia fino a 1 bit di overhead per simbolo; raggruppando $K$ simboli (codifica a blocchi) si tende al tasso entropico $\mathcal H(X)\le H(X)$, ma la complessità cresce come $M^K$; la codifica aritmetica ($\mathcal L<H+2$ per messaggio) ha complessità lineare. Altre tecniche: dizionario (LZ, DEFLATE di ZIP e PNG, ANS in Zstandard), Exp-Golomb e categoria/ampiezza (usati in JPEG e nei codec video) per interi con probabilità decrescente col modulo, codifica predittiva (si codifica l'errore di predizione, che ha entropia molto più bassa).Codifica lossless - entropia, Huffman e codifiche a dizionario →) sulle immagini non riduce molto la dimensione: i livelli di grigio sono quasi equiprobabili. Per ridurre di un fattore 10 o più bisogna accettare una perdita: questa nota spiega come lo fa lo standard JPEG, il formato di immagini più diffuso, passando per le trasformate lineari e la DCT. L'esercizio svolto sul blocco $8\times8$ delle demo è in Esercizio - Trasformata DCT e quantizzazione di un blocco JPEG (demo del corso) e quello sulla codifica dei coefficienti in Esercizio - Zig-zag, run-length e flusso di bit di un blocco JPEG (domande ed esercizi del corso).

1. Compressione con perdita: principi

Nella codifica con perdita si accetta una degradazione del segnale per ottenere una compressione più spinta. I dati in ingresso sono segnali già digitalizzati (la perdita dell'ADC è trascurabile per costruzione). I numeri da ridurre: 8 bit per pixel per un'immagine in grigi, 24 per RGB, 12 per YCbCr 4:2:0; parlato 64 kbit/s; musica stereo 1,41 Mbit/s; video HD 1080p a 50 Hz 1,244 Gbit/s.

Oltre al tasso (bit/s o bit per pixel, bpp) e alla qualità (qui il PSNR, versione logaritmica dell'MSE, Digitalizzazione dei segnali multimediali - campionamento, quantizzazione e binarizzazioneLa conversione analogico-digitale (ADC) ha tre passi: campionamento $s_c(n)=s(nT_c)$, quantizzazione su $L=2^m$ livelli, binarizzazione dell'indice in $m$ bit; il bit-rate vale $R=F_c\log_2L$. Per il teorema di Shannon un segnale a banda limitata $f_M$ si ricostruisce senza errore se $F_c\ge2f_M$ (criterio di Nyquist), altrimenti c'è aliasing; per questo prima del campionatore c'è un filtro passa-basso. La quantizzazione uniforme di passo $\Delta=\frac{2A}{L}$ è irreversibile, con errore massimo $\frac\Delta2$ e $\mathrm{MSE}=\frac{\Delta^2}{12}$; la qualità si misura con MSE e $\mathrm{PSNR}=10\log_{10}\frac{(2^b-1)^2}{\mathrm{MSE}}$. In ricezione il bit mapper ricostruisce i valori e l'interpolazione con un nucleo $h$ (sample and hold, lineare, cubica, sinc troncato) riporta il segnale al tempo continuo.Digitalizzazione dei segnali multimediali - campionamento, quantizzazione e binarizzazione →) contano altri parametri di un sistema di compressione:

• complessità: memoria e numero di operazioni;
• ritardo: occorre "accumulare" dati prima di poter iniziare a codificare?
• robustezza: quanto si degrada il segnale se ci sono errori nel bitstream.

Sono parametri in conflitto: migliorarne uno peggiora quasi sempre uno o più degli altri.

2. Perché una trasformata lineare

L'unico strumento per ridurre il bit-rate con perdita è la quantizzazione. Ma i campioni sono già stati quantizzati nell'ADC: quantizzarli ancora (e direttamente) fa degradare la qualità molto in fretta. Il motivo è che nel dominio originale i segnali multimediali non sono sparsi: tutti i campioni (pixel, valori di pressione acustica) sono importanti. Per un dataset di immagini in grigi la distribuzione dei livelli di luminosità di un pixel copre tutti i livelli; invece la distribuzione congiunta di due pixel adiacenti è molto concentrata (vicino alla diagonale: pixel vicini si somigliano), segno di forte dipendenza.

L'idea: trovare una rappresentazione sparsa, in cui alcuni coefficienti "non sono importanti" e quantizzarli grossolanamente introduce un degrado impercettibile. Un modo è applicare una trasformata lineare ortogonale (una rotazione degli assi) al vettore di $N$ campioni $\mathbf x=[s(n+1),\dots,s(n+N)]^T$: $$\mathbf y=A\mathbf x,\qquad \tilde{\mathbf y}=\bigl[Q(y_1,\Delta_1),\dots,Q(y_N,\Delta_N)\bigr],\qquad\tilde{\mathbf x}=A^{-1}\tilde{\mathbf y}=A^T\tilde{\mathbf y}.$$ Ogni componente della trasformata ha il proprio passo $\Delta_i$. Se la trasformata è "sparsificante" molti $y_i$ sono piccoli, e approssimarli a zero costa poco errore.

Perché ortogonale. Per una matrice ortogonale $A^{-1}=A^T$ (e quindi si inverte a basso costo), e soprattutto la trasformata conserva le distanze. L'errore di ricostruzione è $$\mathrm{MSE}=\frac1N\|\mathbf x-\tilde{\mathbf x}\|^2=\frac1N(A^T\mathbf y-A^T\tilde{\mathbf y})^T(A^T\mathbf y-A^T\tilde{\mathbf y})=\frac1N(\mathbf y-\tilde{\mathbf y})^TAA^T(\mathbf y-\tilde{\mathbf y})=\frac1N\|\mathbf y-\tilde{\mathbf y}\|^2.$$ Quindi un piccolo errore sui coefficienti dà un piccolo errore sui pixel, e si può ottimizzare la quantizzazione direttamente sulla trasformata.

Esempio di segnale sparso. Il tono puro $x(n)=\cos(2\pi f_0n)$ ha tutti i campioni "importanti" (nessuno è trascurabile); trasformato con una matrice che fa l'analisi di frequenza dà un solo coefficiente grande e $N-1$ trascurabili.

3. Dalla trasformata 1D alla 2D

Una trasformata 1D si estende alle immagini applicandola alle colonne e poi alle righe. Per un'immagine $N\times N$, $X=[\mathbf x_1\ \dots\ \mathbf x_N]$ (colonne):

• trasformata sulle colonne: $\tilde Y=AX=[A\mathbf x_1\ \dots\ A\mathbf x_N]$;
• trasformata sulle righe di $\tilde Y$: si moltiplica a destra per $A^T$ (perché le righe di $\tilde Y$ trasformate con $A$ sono le colonne di $A\tilde Y^T$): $Y=\tilde YA^T$.

Alla fine $$\boxed{Y=A\,X\,A^T},\qquad X=A^T\,Y\,A.$$ Per una trasformata di Fourier discreta (Trasformata di Fourier discreta (DFT) e FFTUn segnale discreto periodico di periodo $NT$ ha una trasformata discreta e periodica, la DFT: $S(kF)=\sum_{n=0}^{N-1}T,s(nT)e^{-i2\pi kn/N}$, con $F=1/(NT)$, e $s(nT)=\sum_{k=0}^{N-1}F,S(kF)e^{i2\pi kn/N}$. Dipende da soli $N$ numeri, si calcola senza approssimazioni e con la FFT costa $N\log_2N$ invece di $N^2$. I coefficienti di Fourier del segnale periodico sono $S_k=F,S(kF)$. La DFT dà anche campioni della trasformata di un segnale discreto o continuo a durata limitata (con zero-padding), ma la scalatura $T$ e l'asse delle frequenze vanno gestiti con cura.Trasformata di Fourier discreta (DFT) e FFT →) i coefficienti rappresentano le frequenze spaziali: velocità di variazione in orizzontale e in verticale. Le immagini naturali sono segnali passa-basso: l'energia sta nelle basse frequenze (le alte frequenze sono bordi e dettagli fini); l'istogramma dei coefficienti mostra la sparsità.

4. La DCT

La DCT (discrete cosine transform) è una variante della DFT: produce valori reali, usa solo frequenze positive e sparsifica meglio (concentra ancora più energia nei coefficienti iniziali; il motivo è che la DCT equivale a una DFT di un segnale esteso per simmetria, quindi non ha le discontinuità di bordo che la DFT di un blocco produce). Per un blocco $N\times N$ (qui $N=8$): $$Y(u,v)=\frac2N\,c(u)\,c(v)\sum_{m=0}^{N-1}\sum_{n=0}^{N-1}x(m,n)\cos\frac{(2m+1)u\pi}{2N}\cos\frac{(2n+1)v\pi}{2N},\quad c(0)=\tfrac1{\sqrt2},\ c(k)=1\ (k>0).$$ In forma matriciale è $Y=AXA^T$ con $A_{um}=\sqrt{\tfrac2N}c(u)\cos\frac{(2m+1)u\pi}{2N}$, ortogonale. L'indice $u$ è la frequenza verticale (la riga), $v$ quella orizzontale (la colonna). Le basi della DCT sono coseni a frequenza crescente: ogni coefficiente $Y(u,v)$ è il prodotto scalare del blocco con l'immagine base $B_{u,v}(m,n)=\cos\frac{(2m+1)u\pi}{2N}\cos\frac{(2n+1)v\pi}{2N}$ (a meno di normalizzazione); i coefficienti indicano direzionalità e rapidità delle variazioni. Le basse frequenze stanno in alto a sinistra (il coefficiente $(0,0)$ è proporzionale al valor medio, detto DC; gli altri sono i coefficienti AC).

Esempio 1D (rampa). Il vettore $\mathbf x=[10,12,14,16,18,20,22,24]$ (una rampa) ha energia $\sum x_i^2=2480$. La sua DCT ortonormale è $[48{,}08,\ -12{,}88,\ 0,\ -1{,}35,\ 0,\ -0{,}40,\ 0,\ -0{,}10]$: tutta l'energia (la somma dei quadrati dà ancora $2480$, per l'ortogonalità) sta nei primi due coefficienti ($48{,}08^2+12{,}88^2=2478$), gli altri sono quasi nulli. Quantizzando con un passo grande i coefficienti piccoli diventano 0 e si trasmettono solo 2-3 valori su 8.

DCT a blocchi. Si divide l'immagine in blocchi e si calcola la DCT su ciascuno: così si analizzano le caratteristiche locali (il segnale è più sparso dove non ci sono dettagli o bordi; un blocco di cielo ha quasi solo il DC). JPEG usa blocchi $8\times8$, adeguati alle risoluzioni dell'epoca (1991-92); di contro non si sfruttano dipendenze tra pixel lontani (tranne il valor medio dei blocchi, vedi la codifica del DC).

5. JPEG baseline

Lo standard JPEG (definito nel 1991, adottato nel 1992) rappresenta immagini a colori (3 canali) o in grigi (1 canale). Ogni canale è trattato allo stesso modo: si descrive un solo canale. Lo standard definisce il decodificatore e lascia libertà ai codificatori (diverse implementazioni sono concorrenti ma interoperabili): per questo è più facile descriverlo partendo dal codificatore.

Schema. Un canale (matrice di valori tra 0 e 255):

1. si centra: si sottrae 128 (valori tra $-128$ e $127$);
2. si divide in blocchi $8\times8$;
3. ogni blocco subisce DCT, quantizzazione, codifica lossless;
4. si aggiungono altri elementi sintattici (intestazioni, tabelle).

5.1 Quantizzazione

La quantizzazione uniforme trasforma il reale $x$ nell'indice di quantizzazione $x_{\text{ind}}=\mathrm{round}(x/\Delta)$; in decodifica il valore ricostruito è $\tilde x=\Delta\,x_{\text{ind}}$, il multiplo di $\Delta$ più vicino; l'errore massimo è $\Delta/2$. Passo grande: quantizzazione forte e tasso basso; passo piccolo: qualità migliore e tasso maggiore.

JPEG permette un passo diverso per ogni frequenza spaziale: una tabella di quantizzazione $q(i,j)\in\{1,\dots,256\}$ e $\mathrm{DCT}_{\text{ind}}(i,j)=\mathrm{round}\!\left(\frac{\mathrm{DCT}(i,j)}{q(i,j)}\right)$. Lo standard non definisce la tabella: la sceglie il codificatore e la inserisce nel file (64 byte per tabella), perché al decodificatore serve per ricostruire i valori. Perché non fissarla? Così ogni implementazione può scegliere la strategia di quantizzazione migliore.

La tabella usata di fatto (standard de facto) per la luminanza, ricavata da test soggettivi di qualità percepita (massima qualità a parità di tasso) è:

$$q^*=\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}$$

Per la crominanza si usa un'altra tabella. Valori piccoli in alto a sinistra, grandi in basso a destra, per due motivi: (1) la DCT concentra l'informazione alle basse frequenze (quindi lì servono passi fini, e quasi nessun bit alle alte); (2) l'occhio è più sensibile alle frequenze basse e medio-basse, quindi i passi piccoli stanno dove l'errore si vede di più.

Fattore di qualità. Una tabella sola non basta (se si vuole comprimere di più o avere più qualità): si moltiplica per un fattore di scala. Si definisce un parametro $Q\in[1,100]$ e $$\mathrm{SF}=\begin{cases}5000/Q&Q\le50\\200-2Q&50<Q\le99\\1&Q=100\end{cases},\qquad q(i,j)=\min\!\left(256,\ \left\lceil\frac{\mathrm{SF}}{100}\,q^*(i,j)\right\rceil\right).$$ Con $Q=50$ la tabella non cambia; con $Q<50$ si moltiplica per un numero maggiore di 1 (qualità peggiore); con $Q=1$ si moltiplica per 50; con $Q=100$ i valori sono tutti 1. Si arrotonda per eccesso (devono essere interi positivi) e si tronca a 256 per stare in un byte.

5.2 Esempio completo: un blocco $8\times8$

Blocco centrato di luminanza (valori già diminuiti di 128): $$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}$$ La sua DCT $Y=AXA^T$ ha i seguenti coefficienti (in alto a sinistra il DC):

$$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}$$ Qualità $Q=30$: $\mathrm{SF}=5000/30\approx166{,}7$, fattore $1{,}667$; la tabella diventa $q=\lceil1{,}667\,q^*\rceil$, per esempio $q(0,0)=\lceil26{,}7\rceil=27$, $q(0,1)=\lceil18{,}3\rceil=19$: $$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 di quantizzazione $\mathrm{round}(Y/q)$ (per esempio $\mathrm{round}(-58{,}7/17)=\mathrm{round}(-3{,}45)=-3$; $\mathrm{round}(59{,}1/27)=2$; il DC $\mathrm{round}(8{,}5/27)=0$): $$\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 9 indici su 64 sono non nulli: "rimangono pochi valori da codificare in lossless".

Ricostruzione (decodificatore). Si moltiplica per $q$ ($\tilde Y=\text{indici}\cdot q$, per esempio $-3\cdot17=-51$), si applica la DCT inversa e si risomma 128; in pratica si ottiene un blocco che "somiglia" all'originale (per esempio il primo elemento $-19+128=109$ diventa $101$). L'errore quadratico medio del blocco è $\mathrm{MSE}\approx85{,}6$, cioè $\mathrm{PSNR}\approx48{,}13-19{,}32\approx28{,}8$ dB (sotto i 30 dB, "scadente" nella scala empirica: è un blocco con molto dettaglio compresso a $Q=30$). A qualità alta l'errore non ha struttura riconoscibile; a qualità intermedia è più grande vicino ai bordi (alte frequenze); a qualità bassa compaiono gli effetti di blocchettizzazione (discontinuità tra blocchi adiacenti).

5.3 Codifica lossless dei coefficienti

La codifica lossless non altera i valori, solo il numero di bit.

Zig-zag scan. I valori non nulli sono concentrati in alto a sinistra: per metterli all'inizio e lasciare in coda una lunga sequenza di zeri si leggono i 64 coefficienti con una scansione a zig-zag (diagonali alternate a partire da $(0,0)$: $(0,0),(0,1),(1,0),(2,0),(1,1),(0,2),(0,3),\dots$). Nell'esempio: $$0\ \ 0\ \ \text{-}1\ \ 0\ \ \text{-}1\ \ \text{-}3\ \ 2\ \ 0\ \ \text{-}1\ \ 0\ \ 0\ \ 0\ \ 0\ \ 1\ \ \text{-}1\ \ 0\ \ \text{-}1\ \ \text{-}1\ \ \text{EOB}$$ Quando non ci sono più coefficienti non nulli si mette il simbolo EOB (end of block). Il primo coefficiente è il DC, gli altri sono gli AC.

Coefficiente DC. Due passi: predizione e codifica categoria/valore. La predizione usa come predittore il DC del blocco precedente (i DC di blocchi vicini sono simili: si codifica la differenza, una DPCM). Nell'esempio il blocco precedente aveva DC $=1$, il corrente $0$: errore $e=0-1=-1$. Categoria di $e$: $k=\lceil\log_2(|e|+1)\rceil$, cioè il numero di bit di $|e|$ (31 $\to$ categoria 5 perché $31=11111_2$; $-33\to$ categoria 6 perché $33=100001_2$). Si emette il codice della categoria (un codice a prefisso) e poi $|e|$ su $k$ bit, complementato bit a bit se $e<0$. Per $e=-1$: categoria 1 (codice $010$), valore $1\to$ complementato $0$: $0100$. Altro esempio, $e=-6$: categoria 3 (codice $100$), $6=110_2\to001$: $100001$.

Tabella (standard di fatto) dei codici delle categorie DC: 0: $00$; 1: $010$; 2: $011$; 3: $100$; 4: $101$; 5: $110$; 6: $1110$; 7: $11110$; ... fino a 11: $111111110$.

Coefficienti AC. Due passi: codifica run-length e codifica run-categoria/valore. Il run $R$ è il numero di zeri che precedono il prossimo coefficiente non nullo; si forma il simbolo $(R,C)$ con $C$ il valore del coefficiente. Se $R\ge16$ si usa prima il simbolo speciale $(15,0)$ (ZRL, zero run length: significa 16 zeri consecutivi) e poi si prosegue con il resto del run; se non ci sono più coefficienti non nulli si usa il simbolo $(0,0)$ = EOB. Nell'esempio, a partire dal primo AC: $$(1,-1)\ (1,-1)\ (0,-3)\ (0,2)\ (1,-1)\ (4,1)\ (0,-1)\ (1,-1)\ (0,-1)\ (0,0).$$ Per ciascun simbolo si calcola la categoria $k$ di $C$ e si codifica la coppia $(R,k)$ con un codice a prefisso (non standardizzato come per il DC: le due tabelle di Huffman, DC e AC, si inseriscono nel file); il valore di $C$ si codifica come per il DC (su $k$ bit, complementato se negativo). Con le tabelle di esempio:

(Per $-3$: $3=11_2$, complementato $00$; per $2$: $10$.) Flusso totale del blocco, concatenando: 0100 11000 11000 0100 0110 11000 1110111 000 11000 000 1010 $=$ 0100110001100001000110110001110111000110000001010: 49 bit per 64 pixel, cioè $R=\frac{49}{64}=0{,}766$ bit/pixel. Il blocco originale occupava 8 bit/pixel (512 bit): rapporto di compressione $\frac{512}{49}\approx10{,}4$. (Controllo: i 49 bit sono $4+5+5+4+4+5+7+3+5+3+4$.)

Perché la codifica per categoria/valore rende il codice istantaneo: la categoria dice quanti bit seguono; dopo il codice della categoria si sa esattamente quanti bit leggere. Se il primo bit del valore è 1 il segno è positivo, se è 0 si complementa e si cambia segno.

Immagini a colori. Si trasforma in YCbCr, si decima la crominanza (4:2:0) e si codifica ogni componente separatamente come sopra; per $C_b$ e $C_r$ si usa la tabella di crominanza.

5.4 Sintassi del file e robustezza

Un'immagine è rappresentata in un frame: l'intestazione del frame contiene dimensioni, spazio di colore e sottocampionamento (4:2:0 o altro). L'immagine è divisa in uno o più scan, ciascuno con una componente (Y, Cb, Cr); l'intestazione dello scan identifica la componente e la tabella di quantizzazione. Lo scan è formato da uno o più segmenti (si divide per poter decodificare i segmenti in parallelo); l'intestazione del segmento contiene le tabelle di Huffman; ogni segmento è una successione di blocchi in raster scan.

Poiché i bit sono prodotti da codici a lunghezza variabile, un errore su bit può far perdere il sincronismo della decodifica: un'immagine JPEG è molto più compatta di una non compressa ma anche molto più sensibile agli errori (a differenza di un'immagine non compressa, dove un bit errato cambia un solo pixel).

6. Estensioni e altri formati

Parti di JPEG: baseline (sequenziale, quello visto), progressive, hierarchical, sequenziale lossless, JPEG-LS, Motion JPEG.

• JPEG progressivo: l'immagine compare in versioni a qualità crescente; i 64 coefficienti sono divisi in livelli: spectral selection (prima il DC, poi gli AC in ordine; codifica lossless quasi invariata) e successive approximation (primo livello DC; poi gli AC per bit-plane, dal più significativo, codifica lossless molto diversa).
• JPEG gerarchico: versioni a più risoluzioni, ciascuna codificata (baseline o progressiva) e usata come predizione per la successiva.

Reti neurali per la compressione. Possono rendere le immagini più sparse delle trasformate lineari: modellano strutture non lineari, si adattano ai dati, hanno strutture gerarchiche (bordi, texture, forme) e attivazioni sparse (le ReLU forzano molti coefficienti a zero). Un autoencoder (Autoencoderapprofondimento: non nel programma di Telecomunicazioni. Un autoencoder è una rete non supervisionata che impara a ricostruire il proprio ingresso passando per un collo di bottiglia: encoder $z=e(x)$ (dimensione bassa), decoder $\hat x=d(z)$, loss $|x-d(e(x))|^2$. Con attivazioni lineari equivale alla PCA; con non linearità impara rappresentazioni latenti più ricche (ipotesi del manifold). Varianti: sparse (penalità $\ell_1$ sulle attivazioni), denoising (ingresso corrotto, bersaglio pulito), convolutivi (inpainting). Anomaly detection: si addestra su dati normali e si segnala come anomalo ciò che ha errore di ricostruzione sopra una soglia. VAE: l'encoder produce media e deviazione standard di una gaussiana, il campione si ottiene con il trucco di riparametrizzazione $z=\mu+\sigma\odot\zeta$, $\zeta\sim\mathcal N(0,I)$, e la loss è errore di ricostruzione più KL verso $\mathcal N(0,I)$, con $KL=\frac12\sum(\mu^2+\sigma^2-1-\ln\sigma^2)$; il $\beta$-VAE pesa il KL con $\beta>1$ per rappresentazioni disaccoppiate. Cenno ai GAN.Autoencoder →) ha un encoder (strati convoluzionali, non linearità, riduzione di dimensione) che produce una rappresentazione compatta e quantizzata nello spazio latente (il bottleneck) e un decoder che la riporta alla dimensione originale; l'addestramento impara a ridurre la ridondanza. Prestazioni migliori dei metodi tradizionali ma con grande costo computazionale e difficoltà di implementazione hardware.

Come scegliere oggi: web con AVIF e fallback WebP e JPEG; fotografia da smartphone: iPhone mantiene HEIC, Android JPEG o AVIF; archivio professionale: RAW e consegna in AVIF o JPEG XL (JPEG per la massima compatibilità). Non esiste più un formato "migliore" in assoluto: dipende da compatibilità, efficienza, qualità.

Domande d'esame

1. Perché nella codifica JPEG le matrici di quantizzazione hanno valori piccoli in alto a sinistra e crescenti verso il basso a destra? Traccia: la maggior parte dell'informazione di un'immagine sta alle basse e medie frequenze (e l'occhio vi è più sensibile): serve una quantizzazione fine per i coefficienti DCT a bassa frequenza (alto a sinistra) e più grossolana per quelli ad alta frequenza (basso a destra).

2. Dopo DCT e quantizzazione un blocco ha come prima colonna $20,12,9,9,8$ e come prima riga $20,5$ (il resto zero), più $3$ nella posizione $(1,1)$. Qual è la sequenza dopo zig-zag e run-length? Traccia: ordine zig-zag: $20,5,12,9,3,0,0,0,0,9,8,0\ldots$; $20$ è il DC; poi $(0,5),(0,12),(0,9),(0,3),(4,9),(0,8)$ e EOB. (Il blocco contiene variazioni verticali, i coefficienti sono nella prima colonna; $5$ è l'unico orizzontale.)

3. Elencare i blocchi fondamentali di JPEG baseline. Traccia: DCT su blocchi $8\times8$, quantizzazione, zig-zag scan, run-length coding, codifica "pseudo-Huffman" (codici a prefisso di categoria o coppia run/categoria).