Transcription
Algoritmi di compressioneper le immagini Abbiamo visto nella lezione precedenteche le immagini possono esserecompresse in vari modi, per ridurnel'occupazione di memoria (su disco orete)–compressione lossless – non si perdonodati–compressione lossy – si perdono i dati“meno importanti”
Algoritmo RLE L'RLE (run lenght encoding, codificadella lunghezza delle sequenza) è unalgoritmo lossless particolarmentesempliceIdea di base: quando trovo una serie dipixel dello stesso colore, codifico solola lunghezza della serie e il colorePer immagini di tipo “fumetto” ogeometriche, funziona molto bene!
Algoritmo RLE Esempio: 8x8x24 1536 bit RRRRBBB3B 2R 3BB2B 1R 2VB1B 1R 4VB1B 1R 1VRLEB1B 1R 1VB1B 1R 4VB2B 1R 2VB3B 2R 3B1R1R2R2R1R1R2B1B1V 1R 1B1V 1R 1B1B2B40x(4 24) 1120 bitSe l'immagine ha ampie aree di coloreuguale, si ottengono grossi risparmiSe viceversa ogni punto ha un colorediverso, si può anche peggiorare!
Un teorema importantesulla compressione Teorema:– non esiste un algoritmo di compressione che“funzioni” sempre (cioè, che riduca ladimensione dell'input in tutti i casi)Dimostrazione (per assurdo, approssimata):–supponiamo che un tale algoritmo esista (chiamiamolo A), e indichiamocon # la lunghezza di un dato–dato un input i, A(i) deve essere più piccolo di i, ovvero #A(i) #i–ma A(i) è a sua volta un dato, quindi #A(A(i)) #A(i) #i .–se #i k, dopo al più k passi sono arrivato a 0: come posso da una datolungo 0 ricostruire l'input originale i?
Algoritmi Huffmann e LZW Si tratta di due algoritmi lossless usatiin molte applicazioni–non sono specializzati per le immagini–in entrambi i casi, il grado di compressionenon è direttamente legato al contenutodell'immagine–essendo lossless, non c'è mai perdita diqualità: quando il formato li supporta, èsempre* meglio usarli* ma si ricordi il teorema precedente.
Algoritmo JPEG JPEG è un algoritmo lossy specializzatoper le immaginiFunziona particolarmente su immaginicon molti sfumati (fotografie, incarnati,paesaggi)Quando l'immagine ha un fortecontrasto o passaggi bruschi di colore,si possono notare dei difetti (dettiartefatti)
Algoritmo JPEG Il processo prevede 4 passi–lo scopo è togliere informazione checomunque l'occhio non noterebbe
Algoritmo JPEGtrasformazione colori L'immagine viene dapprima trasportatain un altro spazio colore–si cambia il modello colore da RGB (o altro)a YUV, che codifica Crominanza (colore,2 valori) Luminanza (luminosità, 1valore)–l'occhio umano è infatti più sensibile allaluminosità che al particolare colore, quindinei passi successivi si può “perdere” incrominanza senza danni, mentre le perditadi luminanza è sensibile
Algoritmo JPEGtrasformazione colori inanza
Algoritmo JPEGriduzione componenti La componente luminanza viene lasciatainvariataLe componenti di crominanza possonoessere “tagliate”, sostituendo blocchi di2x1 o 2x2 pixel (o più) con un solo valore,dato dalla media dei componenti eliminatiQuesta operazione, da sola, riduce già del50%-60% la dimensione!–Lo specifico taglio è indicato con codici come4-1-1, 4-2-1, 4-2-2, ecc.
Algoritmo JPEGseparazione in blocchi Il passo successivo consiste neldividere l'immagine in blocchi di 8x8pixelUn'immagine di tipo televisivo(640x512 pixel) richiede 80x64 blocchiA volte la “scalettatura” causata daiblocchi è ben visibile!–quasi sempre dovuto ad altifattori di compressione
Algoritmo JPEGtrasformata DCT Ciascun blocco viene trasformatousando la DCT (trasformata discreta delcoseno)–è una variante della Trasformata di Fourier–trasforma l'immagine dallo spazio delleampiezze a quello delle frequenze–le frequenze alte corrispondono a dettaglifini, che l'occhio non riuscirebbe comunquea scorgere – si possono tagliare!
Algoritmo JPEGtrasformata DCT Il valore dellatrasformata DCT diun'immagine di NxMpixel è datadall'equazione:originaletrasformatadove La funzione inversa trasforma F(u,v) in f(i,j) erestituisce l'immagine originale
Algoritmo JPEGtrasformata DCT L'applicazione della DCT aiblocchi 8x8 trasformal'immagineOgni blocchetto trasformatorappresenta uno spettro difrequenzaL'energia è maggiore ( c'èpiù bianco) dove più alto è ilcontrasto
Algoritmo JPEGtrasformata DCT I coefficienti cheesprimono lo spettro diciascun blocchettovengonoapprossimatiQuesto equivale arappresentare unblocchetto 8x8 comecombinazione di unpiccolo numero diblocchetti predefiniti
Algoritmo JPEGriordinamento dei punti I singoli punti di unblocchetto vengonovisitati a zig-zagQuando li si mette insequenza inquest'ordine, è piùfacile che si trovinopunti consecutivi similiLa compressionefunziona meglio!
Algoritmo JPEGcompressione lossless finale I passi visti fin qui scartano informazione:–si riduce la risoluzione della crominanza–si approssimano i colori–si eliminano i dettagli troppo fini per esserevisti dall'occhioSui dati rimanenti, si applica infine unacompressione lossless (Huffman)Il risultato finale è la codifica JPEGdell'immagine originale–fattore di compressione: da 10 a 50 volte!
Algoritmo JPEGaltri usi notevoli L'algoritmo JPEG è usato (ovviamente)nei file .jpg o .jpeg – che costituisconol'80%-90% delle immagini sul WebÈ un formato anche molto usato inambito medico (raggi X, TAC, ecc.)Una variante più sofisticata è usata neiformati per i film (MPEG, AVI, WMV;anche DVD, satellite e digitale terrestre)Grande vantaggio: qualità buona,compressione alta
Algoritmo JPEGJPEG2000 e il futuro JPEG2000 è (sarà) la nuova versione dellostandard JPEG Lavoro iniziato nel 2001, tuttora in corso Usa la compressione wavelet –20% di compressione in più–qualità significativamente più alta–la definizione matematica è molto complicataPochissimo supporto nelle applicazioni
Algoritmo JPEGJPEG2000 e il futuroOriginale te comunque il rapporto 1:150!
Un teorema importante sulla compressione Teorema: - non esiste un algoritmo di compressione che "funzioni" sempre (cioè, che riduca la dimensione dell'input in tutti i casi) Dimostrazione (per assurdo, approssimata): - supponiamo che un tale algoritmo esista (chiamiamolo A), e indichiamo con # la lunghezza di un dato - dato un input i, A(i) deve essere più piccolo di i, ovvero #A(i) #i
