Salta al contenuto
Note per Studenti Esercizio - Zig-zag, run-length e flusso di bit di un blocco JPEG (domande ed esercizi del corso)

Esercizio - Zig-zag, run-length e flusso di bit di un blocco JPEG (domande ed esercizi del corso)

In questa pagina 4

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 → (zig-zag, codifica del DC e degli AC, categorie, run-length) e 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 →. Fonte: domande a risposta multipla ed esempi di preparazione, slide e demo jpeg del corso di Reti di Calcolatori, Ing. Informatica UniPD 2025-26. Conti verificati in Python. Il blocco di indici è quello ottenuto in Esercizio - Trasformata DCT e quantizzazione di un blocco JPEG (demo del corso).

Ordine dello zig-zag in un blocco N×NN\times N (indici riga, colonna): (0,0),(0,1),(1,0),(2,0),(1,1),(0,2),(0,3),(1,2),(2,1),(3,0),(4,0),(3,1),…(0,0),(0,1),(1,0),(2,0),(1,1),(0,2),(0,3),(1,2),(2,1),(3,0),(4,0),(3,1),\dots: si percorrono le diagonali i+j=costantei+j=\text{costante} a partire dall'angolo in alto a sinistra, alternando il verso (sulle diagonali con i+ji+j pari si sale, sulle dispari si scende).

1. Zig-zag e run-length

Domanda 1. Dopo DCT e quantizzazione, un blocco 8×88\times8 ha i coefficienti 205000000123000000900000009000000080000000000000000000000000000000\begin{matrix}20&5&0&0&0&0&0&0\\12&3&0&0&0&0&0&0\\9&0&0&0&0&0&0&0\\9&0&0&0&0&0&0&0\\8&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{matrix} (le ultime tre righe sono nulle). Quale affermazione è esatta? (a) dopo lo zig-zag scan e il run-length coding la sequenza è: 2020; (0,5)(0,5); (0,12)(0,12); (0,9)(0,9); (0,3)(0,3); (4,9)(4,9); (0,8)(0,8); EOB; (b) il blocco contiene soprattutto variazioni orizzontali; (c) il blocco contiene soprattutto alte frequenze; (d) dopo lo zig-zag e il run-length la sequenza è 20;5;12;9;3;0;0;0;0;9;820;5;12;9;3;0;0;0;0;9;8; EOB.

Soluzione. Lo zig-zag percorre: (0,0)=20(0,0)=20 (DC); (0,1)=5(0,1)=5; (1,0)=12(1,0)=12; (2,0)=9(2,0)=9; (1,1)=3(1,1)=3; (0,2)=0(0,2)=0; (0,3)=0(0,3)=0; (1,2)=0(1,2)=0; (2,1)=0(2,1)=0; (3,0)=9(3,0)=9; (4,0)=8(4,0)=8; poi solo zeri. Sequenza: 20,5,12,9,3,0,0,0,0,9,8,0,…20,5,12,9,3,0,0,0,0,9,8,0,\dots.

  • Il DC (20) si codifica a parte. Per gli AC il run-length sostituisce ogni gruppo di zeri con un conteggio: prima di 55 nessuno zero →(0,5)\to(0,5); prima di 1212 nessuno →(0,12)\to(0,12); (0,9)(0,9); (0,3)(0,3); poi 44 zeri e 9→(4,9)9\to(4,9); nessuno zero e 8→(0,8)8\to(0,8); infine solo zeri fino alla fine del blocco: EOB.
  • (a) è esatta. (d) riporta la sequenza dello zig-zag con gli zeri scritti esplicitamente: manca il run-length (gli zeri non sono stati sostituiti da conteggi).
  • (b) è falsa: i coefficienti non nulli stanno nella prima colonna, che contiene le variazioni verticali (l'indice di riga è la frequenza verticale; le variazioni orizzontali sono nella prima riga, dove c'è solo il 5).
  • (c) è falsa: i coefficienti grandi (20, 12, 9, 9, 8) sono a frequenze basse, vicino all'angolo in alto a sinistra; le alte frequenze sono in basso a destra e valgono 0.

Domanda 2 (blocco 4×44\times4). Un blocco 4×44\times4 dopo DCT e quantizzazione è 15400700030000000\begin{matrix}15&4&0&0\\7&0&0&0\\3&0&0&0\\0&0&0&0\end{matrix} Qual è la sequenza corretta in formato run-length? (a) 15;(0,4);(0,7);(0,3)15;(0,4);(0,7);(0,3); EOB, (b) 15;4;7;315;4;7;3; EOB, (c) 15;(1,4);(1,7);(1,3)15;(1,4);(1,7);(1,3), (d) 15;(0,4);(1,7);(2,3)15;(0,4);(1,7);(2,3).

Zig-zag 4×44\times4: (0,0)=15, (0,1)=4, (1,0)=7, (2,0)=3(0,0)=15,\ (0,1)=4,\ (1,0)=7,\ (2,0)=3, poi tutti zeri: 15,4,7,3,EOB15,4,7,3,\text{EOB}. Dopo ogni coefficiente non nullo il successivo è immediatamente adiacente nell'ordine, quindi tutti i run sono 00: (a). (b) è la sequenza dello zig-zag senza la notazione (R,C)(R,C); (c) e (d) attribuiscono run diversi da zero, ma tra 44, 77, 33 non c'è alcuno zero.

2. Codifica completa di un blocco (demo del corso)

Il blocco di indici dopo la quantizzazione con Q=30Q=30 è [00−32−1000−1−101−10000−10−100000000000000000000000000000000000000000000].\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}. Il DC del blocco precedente è 1.

Zig-zag. (0,0)=0(0,0)=0 (DC); (0,1)=0(0,1)=0; (1,0)=−1(1,0)=-1; (2,0)=0(2,0)=0; (1,1)=−1(1,1)=-1; (0,2)=−3(0,2)=-3; (0,3)=2(0,3)=2; (1,2)=0(1,2)=0; (2,1)=−1(2,1)=-1; (3,0)=0(3,0)=0; (4,0)=0(4,0)=0; (3,1)=0(3,1)=0; (2,2)=0(2,2)=0; (1,3)=1(1,3)=1; (0,4)=−1(0,4)=-1; (0,5)=0(0,5)=0; (1,4)=−1(1,4)=-1; (2,3)=−1(2,3)=-1; poi zeri. La sequenza è 0  0  -1  0  -1  -3  2  0  -1  0  0  0  0  1  -1  0  -1  -1  EOB0\ \ 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} (il primo 00 è il DC; gli altri sono gli AC).

DC. Predittore: DC del blocco precedente =1=1. Errore e=0−1=−1e=0-1=-1. Categoria k=⌈log⁡2(1+1)⌉=1k=\lceil\log_2(1+1)\rceil=1 (codice 010010); ampiezza: ∣e∣=1|e|=1 su 1 bit =1=1, negativo →\to complemento 00. Bit del DC: 010 0010\,0.

AC: simboli (R,C)(R,C). Dopo il DC: 0,−1→(1,−1)0,-1\to(1,-1); 0,−1→(1,−1)0,-1\to(1,-1); −3→(0,−3)-3\to(0,-3); 2→(0,2)2\to(0,2); 0,−1→(1,−1)0,-1\to(1,-1); 0,0,0,0,1→(4,1)0,0,0,0,1\to(4,1); −1→(0,−1)-1\to(0,-1); 0,−1→(1,−1)0,-1\to(1,-1); −1→(0,−1)-1\to(0,-1); EOB =(0,0)=(0,0).

Bit. Con il codice di categoria del DC {0:00, 1:010, 2:011, 3:100}\{0{:}00,\ 1{:}010,\ 2{:}011,\ 3{:}100\} e il codice dei simboli (R,k)(R,k): (0,0)=1010(0,0)=1010 (EOB), (0,1)=00(0,1)=00, (0,2)=01(0,2)=01, (0,3)=100(0,3)=100, (1,1)=1100(1,1)=1100, (4,1)=111011(4,1)=111011:

Simbolo (R,k)(R,k) codice valore (kk bit, complemento se negativo) bit
DC e=−1e=-1 cat. 1 010010 −1→0-1\to0 01000100
(1,−1)(1,-1) (1,1)(1,1) 11001100 00 1100011000
(1,−1)(1,-1) (1,1)(1,1) 11001100 00 1100011000
(0,−3)(0,-3) (0,2)(0,2) 0101 3=11→003=11\to00 01000100
(0,2)(0,2) (0,2)(0,2) 0101 1010 01100110
(1,−1)(1,-1) (1,1)(1,1) 11001100 00 1100011000
(4,1)(4,1) (4,1)(4,1) 111011111011 11 11101111110111
(0,−1)(0,-1) (0,1)(0,1) 0000 00 000000
(1,−1)(1,-1) (1,1)(1,1) 11001100 00 1100011000
(0,−1)(0,-1) (0,1)(0,1) 0000 00 000000
EOB (0,0)(0,0) 10101010 10101010

Flusso: 0100 11000 11000 0100 0110 11000 1110111 000 11000 000 1010 == 0100110001100001000110110001110111000110000001010, lunghezza 4+5+5+4+4+5+7+3+5+3+4=494+5+5+4+4+5+7+3+5+3+4=49 bit. Bit per pixel: 4964=0,766\frac{49}{64}=0{,}766; rispetto agli 8 bpp del blocco non compresso il rapporto è 51249≈10,4\frac{512}{49}\approx10{,}4.

Decodifica (esercizio). Riportare il flusso ai simboli. Si legge un prefisso alla volta con le tabelle:

  • 010010: categoria 1; il bit successivo 00 è un valore negativo (primo bit 0): si complementa 0→10\to1, valore −1-1; DC =1+(−1)=0=1+(-1)=0.
  • 1100→(1,1)1100\to(1,1), valore 0→−10\to-1 (1 bit, negativo): 1 zero poi −1-1.
  • 1100→(1,1)1100\to(1,1), valore 00: 1 zero poi −1-1.
  • 01→(0,2)01\to(0,2), valore 00→00\to negativo, complemento 11=3→−311=3\to-3.
  • 01→(0,2)01\to(0,2), valore 10→10\to positivo =2=2.
  • 1100, 0→1100,\,0\to 1 zero, −1-1.
  • 111011→(4,1)111011\to(4,1), valore 1→+11\to+1: 4 zeri, +1+1.
  • 00→(0,1)00\to(0,1), valore 0→−10\to-1.
  • 1100, 0→1100,\,0\to 1 zero, −1-1.
  • 00, 0→−100,\,0\to-1.
  • 1010→1010\to EOB. Il primo bit del valore decide il segno: 11 positivo, 00 negativo (dopo aver complementato per ottenere il modulo). Riscrivendo gli AC in ordine di zig-zag si ritrova la sequenza di partenza: 0,−1,0,−1,−3,2,0,−1,0,0,0,0,1,−1,0,−1,−10,-1,0,-1,-3,2,0,-1,0,0,0,0,1,-1,0,-1,-1.

3. Un run lungo: il simbolo ZRL (costruito sul modello del corso)

Un blocco ha DC predetto con errore +3+3; poi i coefficienti AC sono 55, poi 20 zeri, poi −2-2, poi solo zeri. Codifica.

  • DC: e=3e=3, categoria ⌈log⁡24⌉=2\lceil\log_24\rceil=2 (codice 011011), 3=1123=11_2: bit 011 11011\,11.
  • AC: primo simbolo (0,5)(0,5): categoria di 55 (5=10125=101_2): k=3k=3; coppia (0,3)(0,3) codice 100100; valore 101101: bit 100 101100\,101.
  • Run di 20 zeri: un run non può superare 15, quindi si emette il simbolo speciale ZRL (15,0)(15,0) che vale 16 zeri consecutivi (codice 1111111100111111111001), e il run restante è 20−16=420-16=4: simbolo (4,−2)(4,-2), categoria 2: coppia (4,2)(4,2), codice 11111110001111111000; valore −2-2: 2=102→2=10_2\to complemento 0101: bit 1111111000 011111111000\,01.
  • EOB: 10101010. Flusso: 01111 100101 11111111001 111111100001 1010 == 01111100101111111110011111111000011010, 38 bit (verificato con le tabelle del demo).

Errori tipici

  • Percorrere il blocco a righe invece che a zig-zag, o girare nel verso sbagliato sulle diagonali.
  • Contare l'EOB tra i coefficienti, oppure mettere un EOB se l'ultimo coefficiente è non nullo e in posizione 63 (in quel caso non serve).
  • Includere il DC nelle coppie (R,C)(R,C): il DC si codifica a parte, in differenza rispetto al blocco precedente.
  • Dimenticare di complementare il valore per i negativi, o di usare la categoria ⌈log⁡2(∣n∣+1)⌉\lceil\log_2(|n|+1)\rceil per il numero di bit del valore.
  • Scrivere (R,C)(R,C) con la categoria al posto del valore nel simbolo (la coppia codificata è (R,k)(R,k); il valore si aggiunge dopo).

Versione ripasso

Zig-zag: (0,0),(0,1),(1,0),(2,0),(1,1),(0,2),(0,3),(1,2),(2,1),(3,0),(4,0),(3,1),…(0,0),(0,1),(1,0),(2,0),(1,1),(0,2),(0,3),(1,2),(2,1),(3,0),(4,0),(3,1),\dots (diagonali i+ji+j costante, verso alternato). Il DC si codifica a parte (in differenza); gli AC con (R,C)(R,C): RR zeri precedenti, CC il valore; EOB =(0,0)=(0,0) quando restano solo zeri; ZRL =(15,0)=16=(15,0)=16 zeri.

Domanda 1. Prima colonna 20,12,9,9,820,12,9,9,8, prima riga 20,520,5, (1,1)=3(1,1)=3: zig-zag 20,5,12,9,3,0,0,0,0,9,820,5,12,9,3,0,0,0,0,9,8; run-length 20;(0,5);(0,12);(0,9);(0,3);(4,9);(0,8)20;(0,5);(0,12);(0,9);(0,3);(4,9);(0,8); EOB. (d) ha gli zeri espliciti (niente run-length); (b) falsa: non nulli nella prima colonna ⇒\Rightarrow variazioni verticali; (c) falsa: coefficienti grandi a frequenze basse.

Domanda 2. Blocco 4×44\times4 con 15,4,7,315,4,7,3 (colonna 0 e posizione (0,1)(0,1)): zig-zag 15,4,7,315,4,7,3, tutti run 0: 15;(0,4);(0,7);(0,3)15;(0,4);(0,7);(0,3); EOB. (b) senza coppie; (c), (d) run non nulli sbagliati.

Blocco della demo, Q=30Q=30. Zig-zag: 0 0 −1 0 −1 −3 2 0 −1 0 0 0 0 1 −1 0 −1 −10\,0\,{-1}\,0\,{-1}\,{-3}\,2\,0\,{-1}\,0\,0\,0\,0\,1\,{-1}\,0\,{-1}\,{-1} EOB. DC: predittore 1, e=−1e=-1, cat. 1 (codice 010010), valore 00: 01000100. AC: (1,−1)(1,−1)(0,−3)(0,2)(1,−1)(4,1)(0,−1)(1,−1)(0,−1)(1,-1)(1,-1)(0,-3)(0,2)(1,-1)(4,1)(0,-1)(1,-1)(0,-1) EOB. Codici: (0,1)=00(0,1)=00, (0,2)=01(0,2)=01, (0,3)=100(0,3)=100, (1,1)=1100(1,1)=1100, (4,1)=111011(4,1)=111011, EOB =1010=1010. Valore su kk bit, complementato se negativo (−3→00-3\to00, 2→102\to10, ±1→0/1\pm1\to0/1).

  • Flusso: 0100 11000 11000 0100 0110 11000 1110111 000 11000 000 1010, 49 bit =0,766=0{,}766 bit/pixel, rapporto 51249≈10,4\frac{512}{49}\approx10{,}4.
  • Decodifica: prefisso →(R,k)\to(R,k), poi kk bit di valore (primo bit 1: positivo; 0: negativo, complementare per il modulo); DC == precedente +e+e.

ZRL. DC e=+3e=+3 (011 11011\,11), AC 55 ((0,3)(0,3): 100 101100\,101), 20 zeri == ZRL (1111111100111111111001, 16 zeri) ++ run 4 con −2-2: (4,2)=1111111000(4,2)=1111111000, valore 0101; EOB 10101010. Totale 38 bit: 01111100101111111110011111111000011010.

Errori tipici: scorrere a righe o nel verso sbagliato; contare l'EOB come coefficiente; includere il DC nelle coppie (R,C)(R,C); non complementare i negativi; confondere (R,C)(R,C) e (R,k)(R,k).

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