Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
UNIVERSITÀ
DEGLI STUDI DI TRIESTE
Corso di Elaborazione Elettronica di Immagini
CODIFICA DI IMMAGINI MEDIANTE DCT
LO STANDARD JPEG
Gabriele Guarnieri
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Sommario
1
Introduzione alla compressione di immagini
2
La Discrete Cosine Transform (DCT)
3
Quantizzazione dei coefficienti
4
Codifica dei coefficienti quantizzati
5
Descrizione dello standard JPEG
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Tipi di compressione
Misure di distorsione
INTRODUZIONE ALLA
COMPRESSIONE DI IMMAGINI
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Tipi di compressione
Misure di distorsione
Motivazione
Un’immagine digitale “grezza” contiene grandi quantità di dati:
Raw → 12 – 14 bit per pixel
RGB → 24 bit per pixel
YCbCr 4:2:0 → 12 bit per pixel
I dati presentano varie forme di ridondanza, che possono essere
sfruttate per una codifica efficiente:
Inter-pixel (correlazione spettrale, spaziale/geometrica,
temporale) → Trasformate, predittori
Psicovisiva (sensibilità dell’occhio a luminanza/frequenza)
→ Correzione gamma, quantizzazione
Codifica (probabilità non uniforme) → Codifica entropica
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Tipi di compressione
Misure di distorsione
Tipi di compressione
Con perdita (lossy) → Rapporto 10 – 100
Fotografie digitali
Video
Senza perdita (lossless) → Rapporto 2 – 10
Documenti legali/commerciali
Immagini satellitari/scientifiche (alto valore)
Immagini medicali (rischio di errori nella diagnosi)
Disegni/grafici (artefatti fastidiosi, buone prestazioni
della compressione lossless)
Necessità di elaborazioni successive
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Tipi di compressione
Misure di distorsione
Misure di distorsione
Misure oggettive
Mean squared error: MSE , E
{︁[︀
]︀2 }︁
^I(x , y ) − I(x , y )
Signal to noise ratio: SNR , E
{︁[︀
]︀2 }︁
I(x , y )
/MSE
2 /MSE
Peak signal to noise ratio: PSNR , Imax
Metodi che tengono conto della distribuzione spaziale
dell’errore. Esempio: “Visible difference predictor” (Daly,
1992), “Structural Similarity Index” (Bovik, 2004).
Misure soggettive
Giudizio dato da osservatori
Variabilità, difficile standardizzazione (esempio: VQEG)
Scarsa corrispondenza con le misure oggettive
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Tipi di compressione
Misure di distorsione
Misure di distorsione
La distorsione tipicamente diminuisce all’aumentare del bit-rate
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione e principi
Definizione
LA DISCRETE COSINE TRANSFORM
(DCT)
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione e principi
Definizione
Motivazione
Un’immagine fotografica contiene tipicamente zone con luminosità
uniforme o lentamente variabile. Le variazioni brusche (bordi)
occupano un’area limitata
Conseguenza: forte correlazione statistica tra pixel vicini
Esempio di stimatori:
Covarianza: {︀
}︀
{︀
}︀
Cov(I1 , I2 ) , E (I1 − Ī1 )(I2 − Ī2 ) = E I1 I2 − Ī1 Ī2
Funzione di autocorrelazione:
{︀
}︀
A(Δx , Δy ) , E I(x , y )I(x + Δx , y + Δy )
Due variabili aleatorie statisticamente indipendenti hanno
covarianza nulla → “non correlate”
f (i1 i2 ) = f1 (i1 )f2 (i2 ) ⇒ E [I1 I2 ] = E [I1 ]E [I2 ]
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione e principi
Definizione
Codifica mediante trasformata
Idea: calcolare opportune combinazioni lineari dei campioni che
producano valori (idealmente) non correlati
La codifica mediante trasformata
(transform coding)
Divide i dati in blocchi
Calcola per ogni blocco una
applicazione lineare invertibile
Trasformata “ottima”:
Karhunen-Loève Transform (KLT)
Formulazione equivalente:
Principal Component Analysis (PCA)
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione e principi
Definizione
Definizione
La KLT, seppure ottima, pone alcuni problemi pratici:
La trasformata dipende dalle proprietà statistiche dei dati
Mancanza di algoritmi di calcolo efficienti (cfr. FFT)
È preferibile usare una trasformata che abbia un’espressione
analitica fissa. Si osserva che le funzioni base della KLT per segnali
“naturali” sono approssimabili con segmenti di coseno
Discrete Cosine Transform (DCT) di una sequenza f con N
campioni:
N−1
∑︁
(2n + 1)k𝜋
F [k] = Ck
f [n] cos
2N
n=0
Gabriele Guarnieri
{︃√︀
Ck ,
√︀
1/N
2/N
Codifica di immagini mediante DCT
se k = 0
se k =
̸ 0
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione e principi
Definizione
Definizione
La DCT è ortogonale, quindi la trasformata inversa (IDCT) ha
un’espressione analoga:
f [n] =
N−1
∑︁
F [k] Ck cos
k=0
(2n + 1)k𝜋
2N
Per sequenza bidimensionali (immagini) di M × N campioni, la
DCT si calcola in modo “separabile”:
F [j, k] = Cj Ck
M−1
∑︁ N−1
∑︁
f [m, n] cos
m=0 n=0
(2m + 1)j𝜋
(2n + 1)k𝜋
cos
2M
2N
La codifica JPEG usa blocchi di 8 × 8 campioni (pixel)
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Metodo di quantizzazione
QUANTIZZAZIONE DEI
COEFFICIENTI
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Metodo di quantizzazione
Motivazione
I coefficienti della DCT sono numeri reali. Per poterli codificare
con pochi bit, è necessario quantizzarli in modo da ottenere numeri
interi. La quantizzazione introduce un errore ⇒ codifica lossy.
L’occhio umano ha una diversa sensibilità alle diverse componenti
di frequenza spaziale
Bassa sensibilità alla componente continua (adattamento
locale)
Bassa sensibilità alle alte frequenze (campionamento dei
fotorecettori)
Maggiore sensibilità alle componenti orizzontali o verticali
rispetto alle diagonali
Dipendenza dalla luminosità, distanza, età, persona, ecc.
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Metodo di quantizzazione
Contrast sensitivity function
La sensibilità dell’occhio alle diverse frequenze spaziali si misura
sperimentalmente con apposite immagini
Contrasto (Michelson):
C,
Lmax − Lmin
Lmax + Lmin
Contrast sensitivity: Reciproco
del contrasto alla soglia di
visibilità
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Metodo di quantizzazione
Metodo di quantizzazione
È ragionevole usare passi di quantizzazione diversi per ciascun
coefficiente, in funzione della sensibilità (tipica) dell’occhio a quella
frequenza spaziale.
Si definisce una tabella di quantizzazione Q[j, k]. Ogni coefficiente
della DCT viene diviso per l’elemento corrispondente della tabella
di quantizzazione e arrotondato all’intero più vicino
F [j, k]
Fq [j, k] , Round
Q[j, k]
(︂
)︂
Alla decodifica, i coefficienti vengono moltiplicati per gli elementi
della tabella:
Fdec [j, k] , Q[j, k] Fq [j, k]
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Metodo di quantizzazione
Tabelle di quantizzazione
Esempio di tabella di quantizzazione per la luma
⎡
16
⎢12
⎢
⎢
⎢14
⎢
⎢14
⎢
⎢18
⎢
⎢
⎢24
⎢
⎣49
72
11
12
13
17
22
35
64
92
10
14
16
22
37
55
78
95
16 24 40
19 26 58
24 40 57
29 51 87
56 68 109
64 81 104
87 103 121
98 112 100
⎤
51 61
60 55 ⎥
⎥
⎥
69 56 ⎥
⎥
80 62 ⎥
⎥
103 77 ⎥
⎥
113 92 ⎥
⎥
⎥
120 101⎦
103 99
Fonte: ITU-T Recommendation T.81, Annex K
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Metodo di quantizzazione
Tabelle di quantizzazione
Esempio di tabella di quantizzazione per la croma
⎡
17
⎢18
⎢
⎢
⎢24
⎢
⎢47
⎢
⎢99
⎢
⎢
⎢99
⎢
⎣99
99
18
21
26
66
99
99
99
99
24
26
56
99
99
99
99
99
47
66
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
99
⎤
99
99⎥
⎥
⎥
99⎥
⎥
99⎥
⎥
99⎥
⎥
99⎥
⎥
⎥
99⎦
99
Fonte: ITU-T Recommendation T.81, Annex K
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Metodo di quantizzazione
Effetto della quantizzazione
Le tabelle di quantizzazione sono arbitrarie, e vengono
memorizzate all’interno del file JPEG
Scalando opportunamente i coefficienti delle tabelle, è possibile
variare la qualità dell’immagine codificata
Artefatto tipico: discontinuità tra i blocchi
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Motivazione
Metodo di quantizzazione
Scalaggio delle tabelle di quantizzazione
Esempio: libreria open-source “libjpeg”, sviluppata
dall’Independent JPEG Group (IJG):
L’utente sceglie un fattore di qualità q tra 1 e 100
q < 50 ⇒ s = 5000/q
q > 50 ⇒ s = 200 − 2q
Ts [j, k] = Round
(︁
s Q[j,k]
100
)︁
Valori limitati tra 1 e (tipicamente) 255
q = 50 lascia le tabelle inalterate.
I software proprietari usano talvolta altri metodi.
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
CODIFICA DEI
COEFFICIENTI QUANTIZZATI
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Introduzione
La trasformata DCT, calcolata (ad esempio) su blocchi di 8 × 8
pixel, produce una tabella di 8 × 8 coefficienti reali:
1 coefficiente DC
63 coefficienti AC
I coefficienti vengono quantizzati utilizzando tabelle di
quantizzazione che tengono conto della sensibilità dell’occhio
umano alle diverse frequenze spaziali, in modo da ottenere numeri
interi e piccoli
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Introduzione
I coefficienti quantizzati vengono codificati opportunamente con
diverse tecniche che tengono conto delle loro proprietà statistiche,
in modo da ottenere sequenze di bit più brevi possibile.
È conveniente codificare in modo diverso e separato le componenti
DC e AC, per due motivi principali
Diverse proprietà statistiche
Possibilità di usare i coefficienti DC per generare anteprime
veloci
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Codifica dei coefficienti DC
Ogni coefficiente DC è proporzionale alla media dei 64 campioni
del blocco. I coefficienti formano quindi una versione ridotta
dell’immagine
Anche i coefficienti DC presentano ridondanze spaziali, che si
possono sfruttare per migliorare ulteriormente la compressione. Lo
standard JPEG utilizza una codifica differenziale
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Codifica dei coefficienti DC
La codifica differenziale raddoppia il range dei dati, ma tende a
produrre valori prossimi allo zero. I numeri più grandi (in valore
assoluto) appaiono con probabilità bassa
Distribuzione di probabilità (approssimativamente) di Laplace
Per codificare questi valori in modo efficiente, si memorizzano
soltanto le cifre binarie significative eliminando gli 0 iniziali (o gli 1
per valori negativi, rappresentati in complemento a 1). Si usa
quindi un numero variabile di bit
È necessario delimitare opportunamente i valori. Lo standard JPEG
inserisce, prima di ogni valore, un simbolo che identifica il numero
di bit → rappresentazione “size + amplitude”
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Difference magnitude categories
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Entropy coding
I simboli indicati con SSSS (“Size”) indicano il numero di bit
necessario per codificare il valore DIFF seguente
Per rappresentare i simboli SSSS sarebbero necessari 4 bit.
Tuttavia, i simboli hanno una distribuzione di probabilità non
uniforme che può essere sfruttata per ridurre il numero di bit
utilizzati in media
Esistono appositi codici a lunghezza variabile, che utilizzano un
numero di bit più basso per rappresentare i simboli che appaiono
con una probabilità maggiore. Lo standard JPEG ne prevede due:
Huffman coding (supportato da tutti i decodificatori)
Arithmetic coding (più efficiente ma poco utilizzato per costo
computazionale e licenze)
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Cenni di teoria dell’informazione
La teoria dell’informazione, fondata da Claude Elwood Shannon nel
1948, fornisce limiti teorici alle prestazioni dei codici a lunghezza
variabile
Consideriamo una sorgente senza memoria che genera sequenze da
un alfabeto di N simboli, con probabilità pi . Vogliamo codificare
ciascun simbolo con una sequenza lunga ni bit
In media, per rappresentare i simboli della sequenza si utilizzerà un
numero di bit pari a
n̄ =
N
∑︁
pi ni
i=1
C. E. Shannon, “A Mathematical Theory of Communication”, Bell System
Technical Journal, Vol. 27, pp. 379–423 & 623–656, July & October, 1948.
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Cenni di teoria dell’informazione
Se i simboli sono equiprobabili (pi = 1/N), un codice a lunghezza
variabile non porterebbe benefici. Per rappresentare i simboli, sono
necessari log2 (N) = log2 (1/p) bit
Se la sorgente emette un solo simbolo (con probabilità 1), la
sequenza è completamente prevedibile e non è necessario
“spendere” bit per rappresentarla: n̄ = 0
L’entropia di una sorgente è definita come
H(p) ,
N
∑︁
i=1
(︂
pi log2
1
pi
)︂
Si dimostra che il numero medio di bit n̄ necessario per codificare i
simboli della sorgente è limitato inferiormente dall’entropia
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Huffman coding
In una sequenza di bit prodotta da codice a lunghezza variabile, è
necessario poter riconoscere dove un simbolo termina ed inizia il
successivo
Questo obiettivo si può ottenere senza costi aggiuntivi se nessun
codice è il prefisso di un altro codice
Il codice “ottimo” è stato ideato nel 1952 da David Albert
Huffman. I codici per ciascun simbolo vengono generati costruendo
un albero binario in base alle loro probabilità pi , e soddisfano
(︂
log2
1
pi
)︂
(︂
≤ ni < log2
1
pi
)︂
+1
D. A. Huffman, “A Method for the Construction of Minimum-Redundancy
Codes”, Proceedings of the I.R.E., September 1952, pp 1098–1102.
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Huffman coding nello standard JPEG
I simboli SSSS vengono codificati in modo efficiente utilizzando un
codice di Huffman
Idealmente, il codificatore dovrebbe generare il codice di Huffman
ottimo misurando la probabilità dei simboli. Il codice viene
memorizzato in una o più Huffman tables all’interno del file JPEG
Questo richiede un procedimento in due passi. Spesso, per
velocizzare la codifica, si utilizzano tabelle predefinite
Esistono software che “ottimizzano” un file JPEG, ricalcolando le
Huffman tables in base all’effettiva probabilità dei simboli
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Codifica dei coefficienti AC
La DCT e la quantizzazione tendono a produrre blocchi di
coefficienti con molti zeri. Esempio, con la tabella di
quantizzazione predefinita:
−56
⎢ −4
⎢ 1
⎢
⎢ 0
→⎢
⎢ 0
⎢
⎢ 0
⎣
0
0
⎡
−7
6
−2
0
0
0
0
0
7
−5
2
0
0
0
0
0
−4
3
−1
0
0
0
0
0
2
−2
0
0
0
0
0
0
−1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
Con una codifica opportuna, è possibile rappresentare in modo
compatto i coefficienti nulli
Gabriele Guarnieri
Codifica di immagini mediante DCT
0
0⎥
0⎥
⎥
0⎥
⎥
0⎥
⎥
0⎥
⎦
0
0
⎤
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Zig-zag order
I coefficienti nulli si trovano prevalentemente per le componenti in
alta frequenza
Nello standard JPEG, i coefficienti vengono riordinati seguendo un
percorso a zig-zag che tende a raggruppare i coefficienti nulli
Risultato sul blocco di coefficienti mostrato prima:
(-56) -7 -4 1 6 7 -4 -5 -2 0 0 0 2 3 2 -1 -2 -1 0 0 0 0 0 0 0 0 1 1 0 0 . . .
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Zig-zag order
Il riordinamento tende a produrre una sequenza con
Coefficienti nulli raggruppati
Coefficienti nulli alla fine
Per codificare la sequenza in modo efficiente, si memorizzano
soltanto i coefficienti non nulli. Prima di ogni coefficiente si
inserisce un simbolo (indicato con RRRR) che indica il numero di
coefficienti nulli eliminati → Esempio di run-length encoding
Gli zeri alla fine della sequenza vengono sostituiti da un simbolo di
end of block (EOB)
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Introduzione
Codifica dei coefficienti DC
Codifica dei coefficienti AC
Codifica
I coefficienti AC hanno solitamente valori prossimi allo zero. I
numeri più grandi (in valore assoluto) appaiono con probabilità
bassa
Per codificare questi valori in modo efficiente, si utilizza un
procedimento analogo a quello utilizzato per i coefficienti DC
differenziali. Ogni coefficiente AC è dunque rappresentato da una
terna di valori: “runlength + size + amplitude”
Le coppie di simboli (RRRR, SSSS) vengono codificate in modo
efficiente utilizzando un codice di Huffman. Un codice apposito è
usato per indicare il simbolo EOB
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Lo standard JPEG
DCT-based process
Progressive DCT-based process
DESCRIZIONE DELLO
STANDARD JPEG
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Lo standard JPEG
DCT-based process
Progressive DCT-based process
Lo standard JPEG
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Lo standard JPEG
DCT-based process
Progressive DCT-based process
Lo standard JPEG
Lo standard prevede 4 diversi modes of operation. Non è richiesto
che i software li implementino tutti
1
Sequential DCT-based
2
Progressive DCT-based
3
Lossless
4
Hierarchical
Il procedimento utilizzato più comunemente, e descritto in
precedenza, è il Sequential DCT-based
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Lo standard JPEG
DCT-based process
Progressive DCT-based process
Il colore nello standard JPEG
Lo standard JPEG consente di rappresentare immagini con più
canali di colore, ma non specifica che cosa significhino.
Normative a parte (es. JFIF, EXIF) definiscono appositi header per
i file JPEG con significato dei canali, risoluzione, profilo colore,
ecc. Tipicamente:
1 canale → Luma
3 canali → YCbCr
Ogni canale può essere sotto-campionato a piacimento e usare
diverse tabelle di quantizzazione e Huffman.
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Lo standard JPEG
DCT-based process
Progressive DCT-based process
DCT-based process
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Lo standard JPEG
DCT-based process
Progressive DCT-based process
Baseline JPEG
Lo standard JPEG è molto ampio, e raramente un decodificatore
ne implementa tutte le funzioni.
È stato definito un sottoinsieme di funzioni che ogni decodificatore
dovrebbe supportare: baseline process
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Lo standard JPEG
DCT-based process
Progressive DCT-based process
Progressive DCT-based process
Nella modalità “sequential”, i blocchi DCT vengono codificati e
trasmessi uno dopo l’altro. Nelle immagini a colori, le diverse
componenti vengono alternate tra di loro (interleaving).
Se il file JPEG viene trasmesso attraverso un canale di
comunicazione lento (esempio: immagini in una pagina web), il
decodificatore può già visualizzare le prime righe dell’immagine
prima che il download sia completato
Gabriele Guarnieri
Codifica di immagini mediante DCT
Introduzione alla compressione di immagini
La Discrete Cosine Transform (DCT)
Quantizzazione dei coefficienti
Codifica dei coefficienti quantizzati
Descrizione dello standard JPEG
Lo standard JPEG
DCT-based process
Progressive DCT-based process
Progressive DCT-based process
In alternativa, è possibile trasmettere prima una porzione dei
coefficienti AC (spectral selection), oppure i bit più significativi
(successive approximation), o combinazioni miste: modalità
“progressive”
Il decodificatore è in grado di visualizzare rapidamente
un’anteprima con qualità ridotta
Gabriele Guarnieri
Codifica di immagini mediante DCT