Fondamenti di Informatica

(1)

Fondamenti di Informatica

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 1

Fondamenti di Informatica - Compressione JPEG

FONDAMENTI DI INFORMATICA

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria Università degli Studi di Udine

Compressione JPEG

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 2 Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio, musica e testo) sono di proprietà dell’autore prof. Pier Luca Montessoro, Università degli Studi di Udine.

Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna autorizzazione.

Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni su supporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte degli autori.

L’informazione contenuta in queste slide è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senza preavviso. L’autore non assume alcuna responsabilità per il contenuto di queste slide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamento dell’informazione).

In ogni caso non può essere dichiarata conformità all’informazione contenuta in queste slide.

In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non devono mai essere rimossi e devono essere riportati anche in utilizzi parziali.

Nota di Copyright

JPEG

• “Joint Photographic Experts Group”

• Gruppo di lavoro per la definizione di uno standard internazionale per la compressione di immagini bitmap

• Diversi modi di funzionamento (anche senza perdita). I più importanti sono con perdita e si basano sulla DCT.

DCT Discrete Cosine Transform

• Deriva dalla trasformata discreta di Fourier (che trasforma segnali dal dominio del tempo al dominio della frequenza)

• La DCT trasforma blocchi di immagine (tipicamente 8x8 pixel) in “frequenze spaziali”

• I valori calcolati dalla DCT rappresentano le variazioni della luminanza (o della crominanza)

DCT Discrete Cosine Transform

• Cosa c’entra con la compressione?

– Nelle immagini la luminosità e il colore dei pixel variano per lo più lentamente rappresentando tali variazioni come frequenze spaziali, si ottengono pochi valori corrispondenti alle frequenze basse e valori trascurabili o nulli alle frequenze più elevate

• Questo consente successivamente di applicare tecniche di compressione senza perdita

DCT Discrete Cosine Transform

f(i,j) F(u,v)

DCT



 

 =

= Λ

+ Λ +

Λ

= ∑

altrimenti per

j i v f j u v i

u v

u F

j i

1 2 0 1 ) (

) , 16 (

) 1 2 cos ( 16

) 1 2 cos ( ) ( ) 4 ( ) 1 , (

,

ξ ξ

π π

NOTA: normalmente i coefficienti

generati presentano delle

variazioni (AC) intorno ad un

valor medio (DC)

(2)

Fondamenti di Informatica

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 2

Quantizzazione

• L’occhio umano è più sensibile alle basse frequenze che alle alte

• La quantizzazione arrotonda i valori ottenuti dalla DCT eliminando le informazioni a cui l’occhio è meno sensibile

• Questo passaggio introduce la “perdita”

ed è irreversibile

Quantizzazione

• Esempio di matrice di quantizzazione:

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 basse

frequenze

alte frequenze

JPEG encoder: schema a blocchi

blocco di 8x8 pixel

DCT

8x8 coefficienti di frequenze spaziali

quantization

quantization table entropy

encoder (Huffman

coding) _zig-zag

scan

DPCM on AC components

RLE on DC components

Y V

U

L’immagine viene separata in luminanza (Y) e due componenti di crominanza (U e V)

JPEG decoder: schema a blocchi

blocco di 8x8 pixel

DCT

^-1

8x8 coefficienti di frequenze spaziali

quantization table entropy

decoder (Huffman

coding) _zig-zag

DPCM on AC components

RLE on DC components

JPEG dequantization

Y V

U

Esempio

8 14 23 37 52 68 73 82

6 14 24 37 46 67 74 81

3 11 28 35 48 62 72 82

4 13 22 28 44 61 69 86

5 11 18 30 40 59 72 86

5 9 16 29 39 58 74 83

-1 8 16 31 38 59 75 80

2 11 18 30 37 57 69 82

Sottraendo il valore costante 128 ...

(3)

Fondamenti di Informatica

Esempio

-327.5 -215.8 16.1 -10.7 -3.7 -1.5 4.2 -6.7 18.1 3.4 -9.9 3.7 0.5 -3.2 3.5 2.2 2.5 1.3 -5.4 2.8 -1.0 2.3 -1.6 -2.6 0.6 -2.5 3.0 5.0 1.8 2.2 -2.6 -1.4 0.3 1.6 3.4 0.0 2.5 -5.1 1.6 -0.7 -0.6 -1.8 -2.4 0.5 -0.4 -1.6 -0.1 2.1 0.9 1.6 -0.6 -0.7 2.1 -0.5 0.9 2.8 0.6 -1.0 -2.9 -1.4 0.2 1.9 -0.6 0.7

Applicando la DCT ...

Esempio

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

Matrice di quantizzazione

F(u,v) quantizzato = round (F(u,v) / Q(u,v))

Esempio

20 -20 2 -1 0 0 0 0 0 2 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Quantizzando ...

Esempio

Fondamenti di Informatica

Fondamenti di Informatica

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 1

FONDAMENTI DI INFORMATICA

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria Università degli Studi di Udine

Compressione JPEG

Nota di Copyright

JPEG

• “Joint Photographic Experts Group”

• Gruppo di lavoro per la definizione di uno standard internazionale per la compressione di immagini bitmap

• Diversi modi di funzionamento (anche senza perdita). I più importanti sono con perdita e si basano sulla DCT.

DCT Discrete Cosine Transform

• Deriva dalla trasformata discreta di Fourier (che trasforma segnali dal dominio del tempo al dominio della frequenza)

• La DCT trasforma blocchi di immagine (tipicamente 8x8 pixel) in “frequenze spaziali”

• I valori calcolati dalla DCT rappresentano le variazioni della luminanza (o della crominanza)

DCT Discrete Cosine Transform

• Cosa c’entra con la compressione?

– Nelle immagini la luminosità e il colore dei pixel variano per lo più lentamente rappresentando tali variazioni come frequenze spaziali, si ottengono pochi valori corrispondenti alle frequenze basse e valori trascurabili o nulli alle frequenze più elevate

• Questo consente successivamente di applicare tecniche di compressione senza perdita

DCT Discrete Cosine Transform

f(i,j) F(u,v)

DCT



 

 =

= Λ

+ Λ +

Λ

= ∑

altrimenti per

j i v f j u v i

u v

u F

1 2 0 1 ) (

) , 16 (

) 1 2 cos ( 16

) 1 2 cos ( ) ( ) 4 ( ) 1 , (

ξ ξ

π π

NOTA: normalmente i coefficienti

generati presentano delle

variazioni (AC) intorno ad un

valor medio (DC)

Fondamenti di Informatica

© 2000 Pier Luca Montessoro (si veda la nota di copyright alla slide n. 2) 2

Quantizzazione

• L’occhio umano è più sensibile alle basse frequenze che alle alte

• La quantizzazione arrotonda i valori ottenuti dalla DCT eliminando le informazioni a cui l’occhio è meno sensibile

• Questo passaggio introduce la “perdita”

ed è irreversibile

Quantizzazione

• Esempio di matrice di quantizzazione:

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 basse

frequenze

alte frequenze

JPEG encoder: schema a blocchi

blocco di 8x8 pixel

DCT

8x8 coefficienti di frequenze spaziali

quantization

quantization table entropy

encoder (Huffman

coding) zig-zag

scan

DPCM on AC components

RLE on DC components

Y V

U

JPEG decoder: schema a blocchi

blocco di 8x8 pixel

DCT

8x8 coefficienti di frequenze spaziali

quantization table entropy

decoder (Huffman

coding) zig-zag

DPCM on AC components

RLE on DC components

JPEG dequantization

Y V

U

coding) _zig-zag

coding) _zig-zag