JPEG baseline · blocchi 8×8 · DCT

Algoritmo JPEG passo per passo

Una demo interattiva per seguire un singolo blocco: luminanza, spostamento di livello, DCT, quantizzazione, scansione zig-zag, run-length coding e codifica Huffman.

Blocco
x 0, y 0
Qualità
50
Coefficienti non nulli
0 / 64
Bit entropici
0

Passo 1

Da RGB a luminanza e spostamento di livello

JPEG baseline lavora di solito nello spazio YCbCr. Qui seguiamo il canale di luminanza \(Y\), perché è il più importante per la percezione dei dettagli. Prima della DCT i valori vengono centrati intorno allo zero.

\[ Y(x,y)=0.299R(x,y)+0.587G(x,y)+0.114B(x,y), \qquad f(x,y)=Y(x,y)-128 \]
\(Y\) arrotondato
\(f=Y-128\)

Passo 2

Discrete Cosine Transform 2D

La DCT riscrive il blocco come somma di 64 pattern cosinusoidali. Il coefficiente \((0,0)\) è la componente DC, cioè il livello medio; gli altri coefficienti descrivono frequenze spaziali via via più alte.

\[ F(u,v)=\frac{1}{4}\alpha(u)\alpha(v) \sum_{x=0}^{7}\sum_{y=0}^{7} f(x,y)\cos\frac{(2x+1)u\pi}{16} \cos\frac{(2y+1)v\pi}{16} \] \[ \alpha(k)= \begin{cases} 1/\sqrt{2} & k=0\\ 1 & k>0 \end{cases} \]
Coefficienti DCT \(F(u,v)\)

Passo 3

Quantizzazione: il punto in cui JPEG perde informazione

Ogni coefficiente DCT viene diviso per un passo di quantizzazione e poi arrotondato. I passi sono più grandi alle alte frequenze, dove l'occhio umano è meno sensibile.

\[ \widehat{F}(u,v)= \operatorname{round}\left(\frac{F(u,v)}{Q_q(u,v)}\right) \] \[ Q_q(u,v)= \operatorname{clip}_{[1,255]} \left( \left\lfloor\frac{s(q)Q_{50}(u,v)+50}{100}\right\rfloor \right), \quad s(q)= \begin{cases} 5000/q & q<50\\ 200-2q & q\ge 50 \end{cases} \]
Tabella \(Q_q\)
Coefficienti quantizzati \(\widehat{F}\)
- -

Passo 4

Scansione zig-zag

Dopo la quantizzazione molti coefficienti ad alta frequenza diventano zero. L'ordine zig-zag mette prima le frequenze basse e tende a raggruppare gli zeri in fondo alla sequenza.

\[ z_k=\widehat{F}(u_k,v_k), \qquad (u_k,v_k)\in\text{ordine zig-zag}, \quad k=0,\dots,63 \]
Ordine di visita
Sequenza \(z_k\)

Passo 5

Run-length coding

Il coefficiente DC viene codificato come differenza dal blocco precedente in ordine raster. Gli AC vengono rappresentati con triple \((\text{RUN},\text{SIZE},\text{AMPLITUDE})\): RUN conta quanti zeri precedono il valore non nullo, SIZE è il numero di bit necessari per scrivere l'ampiezza.

\[ \Delta DC=\widehat{F}_{0,0}^{(i)} -\widehat{F}_{0,0}^{(i-1)}, \qquad \text{SIZE}(a)= \begin{cases} 0 & a=0\\ \lfloor\log_2|a|\rfloor+1 & a\ne0 \end{cases} \]
Tipo Run Size Valore Evento Bit ampiezza

Passo 6

Codifica Huffman entropica

JPEG baseline associa un codice Huffman al simbolo DC o AC e concatena i bit di ampiezza. La demo usa le tabelle standard di luminanza JPEG: nel file reale questi bit verrebbero poi impaccati in byte e inseriti nello stream insieme ai marker.

Lo zig-zag fissa l'ordine delle frequenze, ma lo stream non contiene tutti i 64 coefficienti uno per uno. Dopo la RLE contiene eventi a lunghezza variabile: differenza DC, coppie \((RUN,SIZE)\), simboli ZRL ed EOB. Il simbolo Huffman serve a dire al decoder quale evento sta arrivando e quanti bit di ampiezza deve leggere subito dopo.

\[ \text{codice} = H_{\text{tabella}}(\text{simbolo}) \parallel \operatorname{VLI}(\text{ampiezza}) \]
# Evento Huffman Bit ampiezza Totale
Bitstream del blocco 0 bit