1

Com

pressione di Imm

agini

Michelangelo D

iligentiD

ipartimento di Ingegneria dell’Inform

azioneU

niversità di SienaEm

ail: diligmic@

dii.unisi.ithttp://w

ww

.dii.unisi.it/~diligmic/B

DM

2009

2

Imm

agini

M

aggior parte dell'informazione sul W

eb è m

emorizzata in im

magini

U

n imm

agine è una matrice di pixel

–Im

magini a Colori: ogni pixel è una terna che

rappresenta i valori dei 3 colori fondamentali. U

n colore è rappresentato da un valore tra 0 ed N•

N può essere 2

8, 216 o 2

32

–Bianco e nero: ogni pixel ha due possibili valori

–Scale di grigio: ogni pixel contiene un valore che tra 0 ed N

N

spesso è pari a 28 o 2

16

3

Imm

agini

La risoluzione di un'im

magine determ

ina il num

ero di pixel per unità di superfice–

Imm

agini con alta qualità hanno risoluzione alta•

Ma dipende dal contesto, da un certo punto in

poi non c'è alcuna differenza all'occhio umano

all'aumentare della risoluzione

–Alta risoluzione im

plica maggior spazio per

mem

orizzare l'imm

agine

4

Imm

agini in bianco e nero

Standard CCITT

(Comitato consultativo Internazionale

per la Telefonia e Telegrafia)–

Parte di ITU (International Telecom

munication U

nion)–

Nasce negli anni 1970 com

e standard per l'invio di fax

–N

el 1980 si arriva alla versione 3 che permette

trasmissioni più veloci delle precedenti

–Ancor oggi uno degli standard più diffusi, ogni fax lo supporta

–U

sa algoritmi di com

pressione per migliorare la

velocità di trasmissione

5

CC

ITT

e compressione1728 bits/line

1188 lines/page

U

sa foglio A4–

Risoluzione (200x100) dpi (dots per inch)–

Modalità high resolution (200x200) dpi

Im

magni sono 1728x1188 pixels

–Assum

endo 1bit/pixel → 2M

bit

Velocità di trasmissione 4.8Kbit/s

–O

ggi si raggiungono velocità di 14.4-33.6Kbit/s

–Pertanto senza com

pressione circa 428 secondi per invio di una pagina

–Con CCITT si arriva a 60 secondi

6

Codifica R

un-length

O

gni linea è una sequenza di blocchi di pixels dello stesso colore (run)

Si contano i pixel in ogni run–

Esempio

•3w

4b 9w 2b 2w

6b 5w 2b 5w

7

Codifica in C

CIT

T - G

3 1D

Le lunghezze dei run sono codificate usando una codifica di H

uffman statica (predefinita)

–L'albero di H

uffman è stato definito sulla base delle

lunghezze tipiche dei run misurate in un insiem

e di docum

enti di test

Per mantenere la sincronizzazione ogni linea

inizia sempre con una sequenza di pixel bianchi

–La sequenza può avere lunghezza zero

U

na parola EOL term

ina ogni linea: 00000000001–

Sarebbe inutile dato che la larghezza del docum

ento è data, ma evita che gli errori si

propaghino alle linee successive

8

Codifica con G

3 1D

1000 011 10100 11 0111 0010 ...

9

Coerenza 2D

- G3 2D

•G

3 1D non sfrutta che le im

magini sono regolari

verticalmente oltre che orizzontalm

ente–

Detta coerenza verticale, pixel vicini in verticale

hanno alta probabilità di essere uguali

•La linea precedente viene presa com

e riferimento:

reference line–

La codifica della linea corrente è fatta riportando i cam

biamenti rispetto a quelli sulla reference line

10

G3 2D

•Funzionam

ento G32D

ha diversi “stati”–

Se un run è sia sulla linea corrente che sulla reference (entro 3 posizioni)

vertical mode

•Si codifica la differenza tra la posizione del run attuale ed il precedente (usando H

uffman)

–Se ci sono cam

biamenti di run nella linea corrente

ma non sulla reference

horizontal mode

•Si codifica com

e in G3 1D

–Se la reference line ha run che non vi è sulla linea attuale si em

ette un codice speciale detto pass code

11

Esem

pio di G3 2D

Linea corrente

reference line

Codice

generato

vertical mode

-10

horizontal m

odepass code

Da tabella di H

uffman,

con codici rappresentanti i delta -3, -2, -1, 0, +

1, +2, +

3

<codice del m

odo, lunghezza del run bianco, lunghezza del run nero>

0001

vertical mode ...

+2

-2

12

Problem

i del G3 2D

•M

igliore compressione del G

3 1D•

Ma gli errori creano disturbi m

aggiori–

In G3 1D

un errore disturba solo la linea corrente, ma

appena si trova l'EOL la propagazione dell'errore si ferm

a–

Qui un errore sulla linea di riferim

ento si propaga alla successiva e cosi via

–Per questa ragione si forza una linea ogni K ad essere codificate con G

3 1D. Tali linee saranno le reference

•Risoluzione standard

K=2

•Alta risoluzione

K=4

13

Confronto tra G

3 1D e 2D

•Risoluzione standard (~

200x100 dpi)–

G3 1D

0.13 bits/pixel 57 secondi per A4 a 4.8 Kbps

–G

3 2D (K=

2) 0.11 bits/pixel 47 secondi per A4 a 4.8 Kbps

•Alta risoluzione (~

200x200 dpi)–

G3 2D

(K=4)

0.09 bits/pixel 74 secondi per A4 a 4.8 Kbps

•Com

pressione è buona per documenti da ufficio

•Lunghezza m

edia dei run è alta•

Compressione sarebbe pessim

a per imm

agini naturali da m

acchine fotografiche

14

Imm

agini naturali

•Com

pressione di imm

agini generiche–

Spesso si tratta di imm

agini naturali da macchine

fotografiche–

Le imm

agini hanno un numero elevato di livelli di

grigio o colori (tipicamente tra 2

8 e 232)

•La com

pressione di imm

agini generiche si divide in due categorie principali

–C

on perdita o lossy: i dati compressi non possono

esattamente ricostruire l'im

magine iniziale

–Senza perdita o lossless: i dati una volta decom

pressi ricostruiscono esattamente l'im

magine

priginale

15

Com

pressione senza perdita

•Analogo delle varie tecniche studiate per il testo, dove perdite non sono am

messibili

•G

li standard più comuni sul W

eb sono–

GIF

–PN

G–

JPEG-LS

•N

uovo standard

16

Introduzione al formato G

IF

•Creato da Com

puterServe•

Il formato più usato fino al 1995, m

a ancora comune

•8-bit per pixel

•Im

magini a 256 colori m

a è possibile aggiunge m

appe di colori per aumentare la gam

ma

17

Il formato G

IF

•La m

appa di colori è opzionale–

Se specificata viene inserita nella testata (header) del file dell'im

magine in form

a non compressa

–La m

appa dei colori contiene 256 24-bit entries, che specifican 256 colori RG

B

•L'im

magine è poi codificata usando LZW

–I sim

boli iniziali dell'alfabeto sono i 256 colori nella mappa,

oltre che un codice speciale che indica il pixel vuoto e un sim

bolo che indica la fine dell'informazione (EO

F)

18

Il formato G

IF

•N

el 1995 Unisys annunciò che avrebbe chiesto il

pagamento di royalies sulle im

plementazioni del G

IF–

Per via di un brevetto sull'algoritmo LZW

•Q

uesto fece nascere lo sviluppo di un nuovo formato

lossless–

Il formato sarebbe dovuto essere aperto e

gratuito per tutti gli utilizzatori–

Avrebbe utilizzato gli ultimi sviluppi in term

ini di algoritm

i di compressione

–N

asce il formato PN

G

19

Il formato P

NG

•PN

G: Portable N

etwork G

raphics (pronunciato “ping”)•

Usa la com

pressione gzip•

Migliorie rispetto al G

IF–

Compressione tipicam

ente tra il 10-30% m

igliore–

Non più solo 256 colori m

a usa fino a 16 bit per pixel per im

magini in scale di grigio e fino a 48 bit per pixel

per imm

agini a colori–

GIF ha un solo sim

bolo per i pixel trasparenti, PNG

ha 256 valori di trasparenza, per im

magini che

gradualmente sfum

ano nel background•

PNG

sta diventando lo standard dominante sul W

eb per la com

pressione senza perdita

20

Com

pressione lossy

•La com

pressione con perdita o lossy–

L'imm

agine compressa non può esattam

ente ricostruire l'im

magine iniziale

–Tuttavia l'approssim

azione è buona e l'occhio um

ano può non percepire alcuna differenza–

Alto grado di compressione, superiore agli

analoghi standard senza perdita

21

Com

pressione lossy

•Particolarm

ente adatta per imm

agini che devono essere trasm

esse oltre che mem

orizzate–

Importante m

inimizzare il tem

po di trasmissione

–Im

magini sul W

eb sono scaricate dagli utenti, im

portante minim

izzare i tempi di dow

nload•

Non adatta per alcune categorie di im

magini com

e–

Imm

agini mediche

–Im

magini legali

–D

ocumenti storici

22

Standard per com

pressione lossy

•JPEG

, il più comune

–File con estensione .jpg

•JPEG

2000–

Nuovo standard che usa tecniche w

avelet–

File con estensione .jp2–

Con alti gradi di compressione la qualità

percepita dell'imm

agine con JPEG2 è

molto m

igliore di JPEG

23

Il formato JP

EG

•D

efinito dal Joint Photographic Experts Group nel 1992

•H

a una modalità senza perdite m

a non è usata spesso–

Oggi si usa invece lo standard JPEG

-LS•

Si comprim

e ad 1 bit/pixel con ottima qualità

•Im

plementazione dello standard è relativam

ente sem

plice•

Permette la trasm

issione progressiva (preferibile per il W

WW

) oltre che raster•

Amm

ette imm

gini a colori ed in scale di grigio–

Per imm

agini a colori, ogni canale RGB è trattato

separatamente

24

Codifica JP

EG

•La codifica JPEG

effettua i seguenti passi–

L'imm

agine viene divisa in quadrati 8x8–

Preprocessing per passare dalla rappresentazione RG

B a quella YUV

–Si applica la Trasform

ata Coseno Discreta

(Discrete Cosine Transform

o DCT) su ogni

quadrato–

I coefficienti sono normalizzati, quantizzati e

codificati–

La sequenza dei coefficienti forma l'im

magine

compressa

25

Codifica JP

EG

26

Preprocessing

•D

a RGB a YU

V–

Y rappresenta l'intensità (brightness) del pixel–

U e V reppresentano il colore (la sua arm

onica prim

aria) e la sua saturazione•

Equivalente alla rappresentazione RGB

•Si trasform

a perché occhio umano è più

sensibile alla Y che alla U o V

•Si vuole com

primere le U

e V modo più

aggressivo•

In RGB i 3 colori sono ugualm

ente importanti

27

Discrete C

osine Transform

•La discrete cosine transform

(DCT)

è una trasformata di Fourier

–Sim

ile alle Discrete Fourier Transform

(DFT), m

a con il doppio dei coefficienti–

Usa solo num

eri reali–

Mi scom

pone l'imm

agine nel dominio

della frequenza–

Usata in JPEG

perché veloce e facile da calcolare

28

Discrete C

osine Transform

dove –Blocco ha dim

ensioni (N1 ,N

2 ), in JPEG N

1 =N

2 =8

– Si considera una com

ponente alla volta–

A(i,j) è il valore del pixel (i,j) nel blocco.

–B(k

1 ,k2 ) coefficiente D

CT in posizione (k1 ,k

2 )

–Valori bassi per k

1 rappresentano le basse frequenze verticali, i valori bassi di k

2 corrispondono alle basse frequenze orizzontali

–Le alte frequenze assum

ono tendenzialmente valori più bassi

29

Discrete C

osine Transform

•O

gni quadrato 8x8 corrisponde a 64 coefficienti

30

Discrete C

osine Transform

•I 64 coefficienti D

CT permettono di ricostruire

esattamente i pixels del quadrato

•Tuttavia se li m

emorizzassi tutti ed con precisione

infinita non avrei compresso nulla, anzi!

•Approssim

azioni–

Precisione è finita–

I coefficienti sono quantizzati–

I coefficienti di alta frequenza non sono spesso mem

orizzati o trasm

essi poiché•

L'occhio umano è poco sensibile ad essi e spesso

essi assumono valori m

olto bassi•

Per quadrati senza variazioni brusche essi sono nulli

31

Quantizzazione

•Si ottiene una m

atrice dei DCT per ogni com

ponente–

Ogni valore sulla m

atrice è rinormalizzato in base

ad un fattore che misura quanto l'occhio um

ano è sensibile a quel coefficiente

–D

iversi gradi di compressione per le diverse

frequenze–

Valori sono quindi approssimati all'interno più vicino

–In genere le alte frequenze hanno valori finali nulli

–È possibile decidere quali coefficienti tagliare a seconda della qualità dell'im

magine risultante

•La precisione nella ricostruzione è controllata dal un Q

uality Factor

32

Quantizzazione

•La m

atrice di normalizzazione per i coefficienti di un

blocco in genere usa i seguenti fattori–

Si noti come i fattori di norm

alizzazione sono più alti andando verso in basso a destra

33

Quality factor

•Alto quality factor

–Vengono tenute più com

ponenti•

Basso quality factor–

Vengono tagliate più componenti

–M

aggiore compressione

–In genere dim

inuendo il quality factor inizialmente

non ho una diminuzione della qualità percepita

–Se si continua a dim

inuirlo l'imm

agine inizia a degradare sensibilm

ente

34

JPE

G e quality factor

35

JPE

G e quality factor

Orig

inal

Qu

ality fa

ctor 7

5

Qu

ality fa

ctor 2

0Q

uality fa

ctor 3

36

Ordine dei coefficienti

•O

rdine di m

emorizzazione dei

coefficienti del blocco segue Zig-zag scan

•Coefficienti in bassa frequenza sono m

emorizzati/trasm

essi prim

a•

Permette la

visualizzazione progressiva del blocco

37

Raster vs. progressiva

•Trasm

issione Raster–

I coeficienti DCT sono inviati in ordine dal

blocco in alto a sinistra ad in basso a destra

•Trasm

issione Progressiva (meglio per il

WW

W)

–Prim

a si inviano tutti i coefficienti (0,0), poi gli (0,1) e cosi via seguendo lo zig-zag scan di ogni blocco

38

JPE

G e trasm

issione progressiva

39

Codifica binaria

•D

CT(0,0) ha di solito una variazione lenta tra i blocchi contigui–

Si codifica la differenza tra i valori dei blocchi vicini

•Il bit stream

è codifcato con Huffm

an–

Lo standard prevede anche l'utilizzo della codifica aritmetica

a scapito di una minor velocità di decom

pressione

•I codici di H

uffman sono predefiniti

–Lo standard prevede la possibilità di calcolare dei codici ottim

ali per l'imm

agine ed aggiungerli allo stream

40

Decodifica del JP

EG

Alcuni valori sono persi

Decodifica

Decodifica

Inversa DC

TInversa D

CT

Dequantizzazione

Dequantizzazione

Imm

ag

ine

Rico

struita