[Francesco Bucciantini] Utilizzo Delle Trasformate Nella Codifica Delle Immagini Fisse, In Movimento...

8/18/2019 [Francesco Bucciantini] Utilizzo Delle Trasformate Nella Codifica Delle Immagini Fisse, In Movimento Ed Audio

1/179

Facoltà di Ingegneria Informatica

Utilizzo delle Trasformatenella codifica delle immagini fisse, in movimento ed audio

Studente: Professore:

Francesco Bucciantini Giovanni Murari

Si ringrazia

il Dott. Ingegner Tiziano Squarcia

!!" ##D$MI#" %&'()%&'*


2/179

– Indice:

– Introduzione

– 0) Cenni storici ed importanza della compressione video

–

1) Basi della codifica tramite trasformata– 1.1) Trasformate unitarie

– 1.2) Trasformate ad una dimensione (monodimensionali)

– 1.3) Trasformate a due dimensioni (bidimensionali)

– 1.4) Trasformate a tre dimensioni (tridimensionali)

– 1.5) Trasformate direzionali

– 1.6) Analisi del funzionamento di alcune trasformate prese in esame– Trasformata di Karhunen-Loève

– Trasformata Discreta di Fourier

– Trasformata Discreta del Coseno

– Trasformata di Walsh adamard

– Trasformata Discreta di Wavelet

– 2) Utilizzo delle trasformate nei codec di codifica delle immagini

–2.1) Lo standard J!"

– 2.2) Lo standard J!"2###

– 2.3) Lo standard "$%

– 2.4) Lo standard &"

– 3.0) Basi della codifica video– 3.#.1) 'cene ideo naturali

– 3) Utilizzo delle trasformate nei codec di codifica video– "eneralizzazione su encoder e decoder

– 3.1) .261

– 3.2) *ideo 'tandard+ ,!"-1

– 3.3) *ideo 'tandard+ ,!"-2

–3.4) *ideo 'tandard+ .263

– 3.5.#) *ideo 'tandard+ ,!"-4

– 3.5.1) *ideo 'tandard+ ,!"-4 *isual (,!"-4 art 2)

– 3.5.2) *ideo 'tandard+ ,!"-4 (art 1#)+ A* .264

– 3.6.#) $ntroduzione all/!* 0 .265

– 3.6.1) na trasformata adattia per la codifica ideo miliorata basata sull/.264

– 3.6.2) Arcitettura

– 3.6.3) ettali della trasformata adattia

– 3.6.4) *alutazione delle prestazioni

– 3.) !* 0 .265

– 3..1) !* s .264

– 4) Utilizzo delle trasformate nei codec di codifica audio

–4.1) ,!"-1 Laer 1 (.mp1)

– 4.2) ,!"-1 Laer 2 (.mp2)

– 4.3) ,!"-1 Laer 3 (.mp3)

– 4.4) Adanced Audio odin (AA)

– 4.5) A3 0 Audio odin 3

– 4.6) *orbis (.o)

– 4.) 7pus (.opus)

– 4.8) $ codec audio lossless9 %LA e :A* a confronto

– !alutazioni finali della tesi

– "i#lio$rafia


3/179

Introduzione:

+a tesi si asa sull-analisi delle tecnologie di codifica in un articolare metodo di comressione/la codifica mediante trasformata.Tale metodo di codifica 0 asato sul rimuovere la ridondanza saziale resente in una dataimmagine 1c2e sia singola o arte di un video 3 frame 3 4 trasformandola dal dominio saziale aquello delle frequenze.Il metodo di codifica reso in esame trae vantaggio dal fatto c2e l-occ2io umano erceisce in modominore le alte frequenze risetto alle asse frequenze in modo da oter tagliare dettagli menosignificativi a livello di ercezione visiva.d oggi, quasi tutti i i5 conosciuti ed utilizzati metodi di codifica utilizzano la D#T 1Discrete#osine Trasformate4 ovvero la Trasformata Discreta del #oseno, tuttavia 0 in fase di sviluo unnuovo metodo di codifica c2e unta a trarre vantaggio da un diverso metodo di codifica tramitetrasformata/ l-6$7#.+o scoo della tesi 0 di analizzare nel dettaglio la nuova codifica video 6$7#, la codifica audio edi vari metodi di trasformata utilizzaili, nonc28 comarare i risultati dei recedenti metodi di

codifica, in articolar modo con l-M9$G): 9art '& 17#, 6.%*:4 c2e verrà analizzato in modocomleto e dettagliato.#ome introduzione alle codific2e video, inoltre, verranno eslicati i vari metodi di codifica delleimmagini fisse, con articolare imortanza rivolta allo standard lossless 9!G ed, infine, verrannoanalizzati anc2e i codec audio.

0) Cenni storici ed importanza della compressione video

+a velocità delle connessioni internet 0 in continuo aumento, cos; come i itrate dei netra


4/179

al costo erA di erdere arte delle informazioni difatti l-immagine ricostruita dal decoder non saràmai identica a quella originale.+-oiettivo dei codec di codifica video 0 dunque quello di ottenere il massimo eneficio in terminidi comressione, con la minima distorsione introdotta dal rocesso di comressione.Gli algoritmi di comressione video rimuovono la ridondanza temorale, saziale eCo i domini difrequenza.

#ome rima introduzione, si guardi ora l-immagine sottostante c2e raresenta un esemio di unsingolo frame video.

ll-interno delle regioni evidenziate 1rettangolo di sinistra e destra4 0 resente una lieve variazione

nel contenuto dell-immagine e, quindi, c-0 una ridondanza saziale significativa.Si renda ora in analisi la seconda immagine riortata di seguito.

uesta seconda immagine mostra lo stesso identico frame doo essere stato rocessato da un filtro

assa)asso in modo da rimuovere alcuni dei contenuti ad alta frequenza.


5/179

+-occ2io umano 0 i5 sensiile alle asse frequenze e l-immagine 0 ancora riconosciile, seene arte delle informazioni sono andate erdute 1si ensi ai lineamenti del muro sullo sfondo4.Si renda ora in esame questa terza immagine c2e mostra il frame successivo della sequenza video.

+a sequenza originale era stata catturata da una videocamera a %( fs, quindi c-0 un iccolocamiamento tra i due frame e c-0 una c2iara ridondanza temorale 1la maggior arte dell-immaginerimane identica tra i frame successivi4.Eimuovendo i diversi tii di ridondanza 1saziale, delle frequenze eCo temorale4, 0 ossiilecomrimere i dati al costo di una erdita di informazioni 1distorsione4.Un-ulteriore comressione uA essere raggiunta encodando i dati rocessati utilizzando una codifica

entroica come quella di 6uffman.+a comressione video e delle immagini raresenta da anni un rolifero camo di ricerca e sonostati sviluati numerosi sistemi ed algoritmi di comressione e decomressione e sono stati definitinumerosi standard.Doo questa reve introduzione, assiamo adesso ad analizzare le fondamenta sulle quali si asa lacodifica mediante trasformata er oi introdurre i rimi standard di codifica delle immagini fisse.

1) Basi della Codifica Tramite Trasformata

+a codifica tramite trasformata 0 uno degli strumenti fondamentali della codifica audio e video c2e

utilizziamo oggi giorno in quasi ogni settore.Il suo funzionamento 0 da ricondurre al rocesso di riduzione di ridondanza saziale raresentandoi iel nel dominio delle frequenze er oi oter effettuare una riduzione della quantità di dati inuscita tramite comressione e quantizzazione.9er oter essere comresso, un segnale deve essere decorellato tramite una trasformata aosita,ridistriuendo la sua energia ad un iccolo numero di coefficienti,collocati nella regione delle asse frequenze.uesti coefficienti ossono essere quantizzati in modo da oter eliminare una iccola quantità diinformazioni meno rilevanti senza intaccare la qualità finale dell-immagine una volta ricostruita.Seene il rocesso di trasformata non comorti una erdita di dati 1cio0 0 >lossless?4, il rocessodi quantizzazione la comorta e viene dunque detto >loss@? ) cio0 >con erdita? si 2a cos; quello

c2e viene c2iamato un >errore di quantizzazione? in quanto non 0 i5 ossiile accedere ai dati


6/179

originali una volta quantizzati.d ogni modo, non 0 del tutto corretto dire c2e il rocesso di trasformata 0 rivo di erdita, oic28,seene lo sia da teoria, in ratica uA comortare una limitazione in quanto la suaimlementazione uA avere dei limiti numerici dovuti al suo stesso imiego, quali, ad esemio,arrotondamenti e troncamenti.Il segnale viene segmentato in locc2i ari, tiicamente da .

"gni locco 0 oi trasformato individualmente mediante l-oerazione di >transformazione deimacrolocc2i?.Grazie a questo rocesso asato sui locc2i, 0 ossiile ridurre la comlessità totale dei calcoli ditrasformata in quanto risulta molto i5 facile eseguire i locc2i individualmente risetto c2e a

rocessare tale oerazione sull-intera immagine.Trasformare ogni locco singolarmente uA inoltre catturare le informazioni in modo migliore,sfruttando la correlazione tra di essi in modo migliore, anc2e se, in realtà, tale correlazione non 0mai veramente sfruttata a dovere e sesso questo uA risultare in errori di riroduzione dovuti allaricostruzione finale dell-intera immagine.Un esemio 0 dato da un-immagine fortemente quantizzata nella quale 0 ossiile notare artefattidovuti a >loc=ing?, ovvero 0 ossiile notare con facilità i ordi dei vari locc2i.

In altre arole/ maggiore 0 la comressione, i5 facile sarà vedere tali artefatti.Dal unto di vista teorico, una trasformata 0 tenuta a soddisfare alcuni unti fondamentali in mododa rendere la sua adozione utile al fine ratico.Il rimo dei requisiti fondamentali 0 la >reversiilità?, ovvero il fatto c2e il segnale di ingresso

ossa essere ricostruito senza errori dal segnale di uscita al quale 0 stato alicato il calcolo ditrasformata.uesto 0 forse il i5 imortante dei requisiti ) almeno er quanto riguarda la codifica video ) inquanto er oter visualizzare un-immagine 0 necessario oter ricreare il segnale di artenza.Un altro elemento riguarda la riduzione della quantità di dati, ovvero il fatto c2e la trasformatadea concentrare il segnale in entrata nel minor numero ossiile di coefficienti.Imortante 0 anc2e il fatto c2e la stessa informazione non deve essere rietuta in coefficientidiversi, o, se ciA accade, la rietizione deve essere ridotta al minimo in modo da assicurareun-efficiente decorrelazione.Idealmente, ossiamo dire c2e, oltre alle cose soraelencate, una trasformata dea essere anc2e ilmeno comlessa ossiile 1arlando in termini di oerazioni da eseguire4 in quanto 0 logico ensarec2e meno calcoli vengono eseguiti, maggiore sarà la sua efficienza a livello di calcolocomutazionale.

1.1) Trasformate Unitarie:

Una trasformata unitaria di un dato vettore in ingresso 0 definita da/

Dove B 0 una matrice unitaria ari ed 0 il vettore con i coefficienti di trasformata.Una matrice ari 0 unitaria se il suo inverso 0 uguale al suo trasosto coniugato.Se una matrice unitaria 2a solo valori reali, allora la sua inversa sarà uguale al suo coniugatoe viene definita >matrice ortogonale?.Eicordo c2e i vettori colonna ed i vettori riga di una matrice unitaria sono ortogonali1erendicolari tra loro4 e normalizzati e ossono essere definiti come segue/


7/179

dove ! di " 0 la " #esima colonna della matrice unitaria B.I vettori ! di " costituiscono un gruo di vettori ase ortonomali.I vettori ase sono un gruo di vettori c2e ossono essere cominati linearmente er raresentareogni vettore in un dato sazio vettoriale. sua volta, le funzioni ase sono un gruo di funzioni c2e ossono essere cominate linearmente

er raresentare ogni funzione in un dato sazio di funzione.In questo caso, la matrice unitaria B raresenta la trasformata unitaria di funzione ase.+e trasformate unitarie comrendono le caratteristic2e soraelencate tra cui, in rimis,la reversiilità in questo caso aiamo c2e/

Un-altra rorietà di quelle soraelencate c2e viene risettata 0 quella della riduzione della quantitàdi dati tramite i coefficienti ed il fatto di reservare l-energia dell-onda mediante gli stessi/

+e trasformate unitarie, solitamente, sono le i5 utilizzate negli standard di comressione video.

1.$) Trasformate ad Una %imensione &monodimensionali):

#onsiderando x(n) un locco di N camioni in entrata 1dominio saziale4 ed y(k) un gruo di N coefficienti di trasformata 1dominio delle frequenze4, una trasformata monodimensionale 0 data da/

dove a(k,n) sono le funzioni di trasformata ase.+a trasformata inversa usata er ricomorre il segnale originale 0 invece definita da/

dove b(k,n) sono le funzioni di trasformata ase inversa.Tenendo conto c2e il rimo vettore ase tiicamente corrisondente alla frequenza di comonentezero, corrisonde alla funzione costante, allora y(0) 0 c2iamato coefficiente DC , c2e raresenta il

rinciale indicatore della forma d-onda sotto trasformata.H rorio questo il coefficiente di trasformata i5 imortante dato c2e 0 associato alla frequenza i5

assa erceiile.Tutti gli altri coefficienti, invece, sono c2iamati coefficienti AC .


8/179

1.') Trasformate a %ue %imensioni &!idimensionali):

#onsiderando ora x(m,n) come locco di camioni NxN a due dimensioni e y(k,l) un gruo di NxN coefficienti di trasformata, la trasformata idimensionale 0 data da/

+a trasformata idimensionale inversa 0 invece data da/

a(k,l,m,n) e b(k,l,m,n) sono risettivamente le funzioni di trasformata idimensionale e trasformata idimensionale inversa.#i sono due classi fondamentali di trasformate idimensionali/ le trasformate separabili e letrasformate non separabili.+e trasformate non searaili sono calcolate utilizzando semlicemente le ! colonne in ingresso daun cao all-altro er formare una singola colonna di vettori di lung2ezza !% e solo doo vieneeffettuato il calcolo di trasformata.+e trasformate searaili sfruttano sia le correlazioni orizzontali c2e quelle verticali del segnale iningresso e, tiicamente, ric2iedono un-oerazione aritmetica !:.In una trasformata searaile idimensionale, entrame le funzioni di trasformata di ase sonosearate in oerazioni distinte 1orizzontale e verticale4/

#on queste due oerazioni, una trasformata searaile idimensionale uA essere elaorata in duefasi indiendenti, eseguite una doo l-altra.+a rima fase utilizza la funzione ase orizzontale ah (l,n),sfruttando la correlazione orizzontale dei dati.+a seconda fase utilizza invece la funzione di ase verticale av (k,m),sfruttando la correlazione verticale dei dati.+e trasformate idimensionali searaili sono imlementate come due trasformatemonodimensionali consecutive e sono date da/

In notazione di matrice aiamo/

+e funzioni di ase simmetric2e sono funzioni c2e 2anno comonenti orizzontali e verticalisimmetric2e Av = Ah = A. In questo caso, aiamo/


9/179

+a moltilicazione di due matrici NxN ric2iede un-oerazione matematica di N^.

Di conseguenza, una trasformata searaile idimensionale, c2e 2a due moltilicazioni di matrice,ric2iede un-oerazione !N^ 1ricordo c2e la trasformata non searaile ric2iede N^"4.uindi, nel caso in cui si aia ! J %, 0 referiile utilizzare una trasformata idimensionale.

1.() Trasformate a Tre %imensioni &tridimensionali):

#onsideriamo adesso x(m,n,p) come un locco di camioni NxNxN tridimensionale in ingresso.Tale segnale d-ingresso 2a due comonenti saziali ed una comonente temorale.#onsiderando @1=,l,q4 i coefficienti di trasformata, la trasformata tridimensionale 0 data da/

+a trasformata tridimensionale inversa 0 invece data da/

a(k,l,#,m,n,p) e b(k,l,#,m,n,p) sono risettivamente le funzioni di trasformata tridimensionale etrasformata tridimensionale inversa.#on una trasformata tridimensionale 0 ossiile sfruttare la correlazione tra i dati in tre dimensioni/due nello sazio ed uno nel temo.In articolare, nella codifica video, 0 ossiile rimuovere non solo la ridondanza saziale,ma anc2e la ridondanza temoraleK"vviamente, utilizzando questo tio di trasformata, la durata di codifica suirà un significativorallentamento, sorattutto su video con un elevato numero di frame.

1.) Trasformate %irezionali

Una trasformata direzionale 0 una trasformata c2e utilizza le informazioni dei ordi resenti inalcuni dati in entrata er oter sfruttare meglio la correlazione dei grui di dati.+o scoo di questa trasformata 0 di aumentare la comressiilità rilevando e rimuovendo laridondanza saziale in modo migliore risetto alle trasformate non direzionali,aumentando cos; il raorto di comressione risetto alle stesse.+e trasformate idimensionali 3 come 2o detto rima 3 sono rocessate individualmente calcolandodue trasformate monodimensionali 1una verticale ed una orizzontale4.Tale aroccio uA risultare molto utile in alcuni casi, ma non 0 semre ossiile alicarloottenendo il risultato serato in tutte le situazioni.


10/179

#onsideriamo il seguente locco c2e 2a la eculiarità di avere una linea diagonale c2e divide dueregioni.

In questo caso, una trasformata idimensionale searaile genereree un numero i5 elevato dicoefficienti non nulli, deteriorando cos; l-efficienza di comressione della trasformata stessa.H rorio in questo caso c2e ci vengono in aiuto le trasformate direzionali.+e trasformate direzionali sono varie e ossono avere arocci e risultati diversi l-una dall-altra acausa del loro modus oerandi.#i sono le trasformate direzionali $ipen$enti $al mo$o c2e ossono utilizzare diverse funzioni ase,ognuna er un ordo secifico.Doo aver analizzato la direzione dei ordi, selezionano quale funzione ase utilizzare ed effettuano

una trasformata idimensionale.#i sono le trasformate direzionali a sin%ola $imensione ripet&ta.

!ella rima fase, viene eseguita una trasformata monodimensionale sulla direzione del ordo. !ella seconda fase, viene effettuata una trasformata monodimensionale orizzontale.#i sono infine le trasformate direzionali $i or$inamento e bi$imensionali.In questo caso, i grui di dati in ingresso vengono riordinati a seconda del ordo direzionale.Doodic28, viene eseguita una trasformata monodimensionale er le rig2e e er le colonne,similmente a quanto accade in un rocesso di trasformata idimensionale.

1.*) +nalisi del funzionamento di alcune trasformate prese in esame

Doo una reve introduzione sui tii di trasformata, rocedo ora col rendere in esame letrasformate i5 imortanti utilizzate er la codifica video.

– Trasformata di ,ar-unen/ove

+a Trasformata di 'arh&neno*ve 1L+T4 0 una trasformata unitaria ortogonale non searaile,la cui trasformata monodimensionale e la sua inversa monodimensionale er un vettore x sonodefinite da/

+a matrice % raresenta la funzione di trasformata di Lar2unen)+o0ve di ase.uesta trasformata non 2a un insieme di funzioni ase redefinite oic28 le sue funzioni ase sonodiendenti dal dato di origine e sono determinate nel seguente modo/

Convarian+a la convarianza della matrice & 0 definita come


11/179

dove

0 il valore dell-i)esimo dato in ingresso nel vettore .

A&tovettori e$ A&tovalori $ella convarian+a comp&ta+ionale $ella matrice comutazione dellamatrice degli autovettori della matrice di convarianza N

dove O 0 la matrice diagonale di autovalori della matrice di convarianza N

dove Pm 0 l-m)esimo autovalore della matrice di convarianza N. +e colonne della matrice corrisondono agli autovettori della matrice di convarianza N, raresentata nelle funzioni di asedella trasformata di Lar2unen)+o0ve.uesta trasformata 0 la miglior trasformata ossiile in termini di comressione in quanto riesce acodificare il segnale utilizzando il minor numero di coefficienti ossiile.

d ogni modo, la trasformata di Lar2unen)+o0ve utilizza delle funzioni di ase diendenti dal datodi ingresso, il c2e comorta la continua comutazione della matrice di convarianza del segnale iningresso, cos; come la sua memorizzazione e trasmissione.

!on solo, rorio er ottenere una codifica tanto efficiente, la trasformata di Lar2unen)+o0veric2iede una grande quantità di calcoli er oter determinare le funzioni di ase,il c2e ne aumenta la comlessità.9rorio a causa della grande quantità di calcoli ric2iesti, il suo utilizzo nell-amito della codificavideo 0 limitato, anc2e se una sua versione modificata 0 rorio alla ase del nuovo codec 6$7#.

– Trasformata %iscreta di ourier

+a Trasformata Discreta di Fourier 1DFT4 0 una trasformata unitaria ed ortogonale c2e 0 utilizzata er scomorre il dato originale nelle sue comonenti di seno e coseno.H una trasformata unitaria idimensionale e la sua trasformata ed inversa 1er un locco di dati

NxN 4 sono definite da/

+e funzioni ase della trasformata discreta di Fourier corrisondono alle onde di seno e coseno confrequenze in aumento.Il rimo coefficiente @1&,&4 raresenta i comonenti D#. differenza di quella di Lar2unen)+o0ve, quella di Fourier 0 una trasformata searaile e le suefunzioni di ase ossono essere raresentate come rodotti di due trasformate unitarie date da/


12/179

9er un vettore di lung2ezza N, comutare una trasformata di fourier monodimensionale ric2iede !% oerazioni aritmetic2e.9er ridurre la comlessità di questa trasformata, sesso viene utilizzata un-imlementazione secialec2iamata >-rasformata Discreta $i o&rier /eloce? 1FFT4.Utilizzando la FFT al osto della DFT normale, 0 ossiile ridurre le oerazioni aritmetic2e er latrasformata monodimensionale ad un semlice Nlo%N.

+a trasformata Discreta di Fourier 7eloce 0 dunque in grado di ridurre significativamente lacomlessità della Trasformata Discreta di Fourier normale ed il fatto di oter contare su unaversione >veloce? della stessa 0 senza duio un grande vantaggio risetto alla trasformata diLar2unen)+o0ve.d ogni modo, la FFT 2a un grande difetto c2e 0 quello di rodurre nella codifica dei coefficienticomlessi 1cio0 con arti reali ed immaginarie4 e quindi difficili da gestire, salvare e maniolare.7iene in aiuto, in questo caso, la D#T cio0 la Trasformata Discreta del #oseno 1della quale arlerAdi seguito4 c2e utilizza valori reali e non numeri comlessi.

– Trasformata %iscreta del Coseno

+a Trasformata Discreta del #oseno 1D#T4 0 una trasformata unitaria ortogonale concettualmentesimile a quella di Fourier 1DFT4 ma con il vantaggio di utilizzare solamente numeri reali 1e noncomlessi come quella di Fourier4.+a trasformata idimensionale er un locco !! 0 definita da/

e la sua inversa 0 data da/

con

#ome er la trasformata Discreta di Fourier, la trasformata Discreta del #oseno uA essereraresentata come rodotto di due trasformate monodimensionali, visto c2e 0 anc2-essa unatrasformata searaile.

2 %T e %CT a confronto

In questo grafico rendo come modello una funzione ase da sia er la Trasformata Discreta di

Fourier c2e er la Trasformata Discreta del #oseno, onde evidenziarne il differente funzionamento/


13/179

Trasformata Discreta di Fourier 1DFT4 Trasformata Discreta del #oseno 1D#T4

Dato c2e la funzione coseno 0 reale e ari cos(x) = cos(x) ed il segnale in ingresso 0 anc2-essoreale, la trasformata Discreta del #oseno inversa genera una funzione ari eriodica in !N,

considerando N la lung2ezza della sequenza del segnale originale.+a trasformata Discreta di Fourier inversa, invece, roduce un segnale ricostruito c2e 0 eriodico in N.

+a trasformata Discreta del #oseno, inoltre, introduce delle discontinuità molto i5 lievi di quella diFourier e gli errori di ricostruzione ai ordi dei locc2i sono i5 iccoli, di conseguenza gli artefattida comressione 1loc=ing4 sono meno esanti di quelli della trasformata Discreta di Fourier.

Dall-illustrazione 0 facile notare come la DFT sia eriodica in N e la D#T sia eriodica in !N.Il c2e significa c2e, nella DFT, ci sono delle discontinuità tra N ed N nei unti di ordo c2e sonoinvece evitate nella D#T.9er quanto concerne i segnali altamente correlati, la D#T 2a dei risultati di codifica molto similialla trasformata di Lar2unen)+o0ve.d ogni modo, a differenza di quest-ultima, le funzioni di ase della D#T non sono diendenti daidati in ingresso, favorendone cos;, ancora una volta, l-utilizzo.


14/179

+a D#T, inoltre, cos; come la DFT, 2a una versione >veloce? c2iamata -rasformata Discreta $elCoseno /eloce1.

+a versione >veloce? riduce i calcoli aritmetici er una trasformata monodimensionale er unvettore di lung2ezza N a solo Nlo%N , esattamente come er la trasformata Discreta $i o&rier/eloce.

Grazie a tutte queste eculiarità, la Trasformata Discreta del #oseno 0 diventata la trasformata di

riferimento er codific2e come il Q9$G, l-6.%*: e l-M9$G)% nel quale la D#T idimensionale vieneeffettuata su locc2i da ed in seguito viene effettuata una quantizzazione dei suoi coefficienti.9er quanto riguarda l-6.%*: 7#, erA, questi non si serve solamente della D#T, ens; esegue una>seconda assata? er mezzo di un-altra trasformata/ la trasformata di Rals2)6adamard,c2e illustrerA di seguito.

– Trasformata di 3als-4adamard

+a trasformata di 2alsh3a$amar$ 0 una trasformata unitaria ed ortogonale.H una trasformata searaile e la sua trasformata ed inversa monodimensionali er un vettore x

di lung2ezza !^m sono definite da/

dove la matrice 3m raresenta la funzione di ase della R6T.+a matrice 6m 0 una matrice di 6adamard da !^m x !^m, ovvero una matrice quadrata i cui valoridi ingresso ossono essere sia 45 c2e 5 e le cui rig2e sono recirocamente ortogonali ed 0 data da/

in cui ' su radice di due 0 il fattore normalizzante.+a trasformata di Rals2)6adamard, cos; come le recedenti due, ossiede una sua versione>veloce?, c2iamata >Trasformata di Rals2)6adamard 7eloce?.#os; come er le altre soraelencate, la versione >veloce? di questa trasformata uA ridurre ilnumero di oerazioni aritmetic2e er una trasformata monodimensionale da N^! a Nlo%N.+a trasformata di Rals2)6adamard lavora con matrici uramente reali, contenendo valori di ' e)' cos; facendo, le oerazioni c2e deve comiere sono limitate a calcoli molto semlici e,sorattutto er la sua versione >veloce?, 0 la trasformata col i5 asso livello di comlessità.d ogni modo, rorio er la semlicità dei calcoli c2e effettua, la sua caacità di comressione 0altrettanto modesta, er questo il suo utilizzo autonomo 0 ressoc28 nullo nel camo della codificavideo, ma 3 come 2o detto rima 3 0 molto imortante in quanto viene associata alla D#T er oterottenere una miglior comressione nel codec 6.%*: 7#.

– Trasformata %iscreta di 3avelet

+a trasformata Discreta di Ravelet 0 una trasformata unitaria, ortogonale e searaile c2e di solito 0alicata all-intero dato in ingresso e non a dei iccoli locc2i come invece accadeva er letrasformate viste in recedenza.+a DRT di un segnale in ingresso 0 eseguita assandolo attraverso vari filtri.9er rima cosa, il segnale in entrata 0 decomosto usando un filtro assa asso, ovvero un filtro c2e

assa le asse frequenze ed attenua le alte frequenze, doodic28 viene rocessato da un filtro assaalto c2e assa le alte frequenze ed attenua le asse frequenze.Tale oerazione 0 effettuata utilizzando/


15/179

dove lo6 and hi%h sono risettivamente i coefficienti di anda assa asso e assa alto.I filtri g ed 2 devono essere in stretto raorto tra loro er oter dividere il segnale in ingresso indue ande, formando cos; un filtro di quadratura a secc2io/

dove f 0 la frequenza.Tale rorietà assicura c2e non ci sia alcuna erdita di informazioni durante il rocesso didecomosizione.#on l-oerazione di filtraggio assa asso e assa alto, metà delle frequenze del segnale sonorimosse in entrame le ande.In questo modo, 0 ossiile utilizzare il teorema di camionamento/

se una funzione x(f) contiene frequenze c2e sono i5 iccole di 7 hert+, allora 0 determinata dandole sue ordinate ad una serie di unti distanziati 58(!7) secondi.Metà dei camioni ossono essere tagliati e l-outut dei due filtri 1g ed 24 uA esseresotto)camionato er due. Tale oerazione 0 data da/

Doo questo rocesso, la maggior arte dell-energia 0 generalmente concentrata nella anda assa asso.

9er oter aumentare la frequenza di risoluzione in questa anda, ossono essere eseguite i5decomosizioni, rietendo l-oerazione di sora.9er un segnale in ingresso monodimensionale, le alicazioni successive dei filtri sull-outut assa

asso risultano in una scomosizione dinamica, ovvero il numero di coefficienti er ogni nuova anda assa 0 metà del numero della scomosizione recedente.9er un segnale in ingresso idimensionale, il numero dei coefficienti di ogni nuova anda assa 0un quarto del numero della scomosizione recedente.+a trasformata Discreta di Ravelet 2a la eculiarità di ossedere coefficienti in grado di ricostruirevarie risoluzioni saziali.#os; come er le altre trasformate soraelencate, la trasformata Discreta di Ravelet 2a la suaversione >veloce? c2iamata -rasformata Discreta $i 2avelet /eloce1 e uA eseguire unatrasformata monodimensionale er un vettore di lung2ezza N in sole N oerazioni aritmetic2e.Tra i regi della Trasformata Discreta di Ravelet ci sono l-assenza di loc=ing come artefatto dacomressione 1questo erc28 viene alicata all-intera immagine e non a locc2i4, sfrutta lacorrelazione di tutti i locc2i vicini 1visto c2e viene alicata a tutta l-immagine4 consentendo altilivelli di comressione ed 2a una decomosizione dinamica ed 0 quindi ossiile aumentare odiminuire la risoluzione saziale dei dati recuerati semlicemente aumentando o diminuendo ilnumero dei coefficienti decodificati.+-unico rolema 0 c2e rocessare l-intera immagine assieme invece di dividerla in locc2i ric2iedeun alto carico comutazionale dal unto di vista dei calcoli.+a trasformata Discreta di Ravelet 0 utilizzata nello Standard Q9$G %&&& di cui arlerA di seguito.


16/179

$) Utilizzo delle Trasformate nei codec di codifica immagini

l fine di eslicare l-utilizzo dei metodi di codifica all-interno dei codec video, 0 referiileaffrontare rima il loro imiego nei codec di codifica di immagini static2e in quanto i5 semlici.Inoltre, in questo caitolo viene raresentato asso er asso l-utilizzo dei metodi di trasformata

visti sora in un contesto reale e di utilizzo ratico.

$.1) /o Standard 5P67

+o standard Q9$G utilizza due tii di codifica/ loss@ 1con erdita4 e lossless 1rivo di erdita4 nelsecondo caso, inoltre, non viene effettuata una codifica tramite trasformata.H doveroso dire, comunque, c2e la codifica lossless 0 molto meno efficiente in termini dicomressione risetto a quella loss@ c2e, erA, comorta la erdita di una arte di informazione.

!on solo, non 0 semre detto c2e il metodo di comressione lossless riesca semre a ridurre ladimensione finale del file e otreero esserci casi in cui questo risulta essere addirittura i5 grandedel file di artenzaK

In tale caso, quindi, 0 referiile otare er lasciare il file originale invariato al osto di tenerequello rocessato dalla codifica lossless.Generalmente, il metodo i5 utilizzato 0 quello loss@ ed 0 rorio questo a cui darA i5 imortanza.+a trasformata utilizzata dal Q9$G nella codifica loss@ 0 la trasformata discreta del coseno

idimensionale, unitaria, ortogonale e searaile ed 0 data da/

dove y(k,l) 0 il coefficiente alle coordinate (k,l) e x(m,n) 0 il valore di ingresso 1di c2roma 3comonente del colore 3 e luma 3 immagine in ianco e nero in s8 er s84 alle coordinate (m,n).

Il Q9$G utilizza dunque la Trasformata Discreta del #oseno er la sua imlementazione e rocedenella codifica nel seguente modo/

'4 +-immagine originale viene divisa in locc2i da .%4 "gni locco da viene trasformato utilizzando un-oerazione di trasformata Discreta del

#oseno idimensionale 1cio0, raresentandolo in un-oortuna ase dello saziovettoriale4 il risultato 0 dato da coefficienti 1quindi *:4 creati dalla D#T stessa.

4 Tutti i *: coefficienti creati dalla D#T sono oi quantizzati utilizzando una secifica matricedi quantizzazione.


17/179

:4 I coefficienti D#T quantizzati vengono organizzati in una sequenza monodimensionale a>zig zag?.Grazie a questa articolare sequenza, l-encoder incontrerà tutti i coefficienti D#T non nullidel locco il i5 velocemente ossiile.

!on solo, dato c2e tale ordine corrisonde 1molto arossimativamente4 ad una lista

ordinata dei coefficienti di ercezione visiva, il suo imiego fa s; c2e i coefficienti i5imortanti dal unto di vista visivo siano semre trasmessi rima di quelli meno imortanti.Doodic28, il Q9$G crea una coia 1run, level4 er ogni coefficiente.Il >run? 0 la quantità di coefficienti D#T nulli c2e recedono i veri coefficienti c2e vengonocodificati nella sequenza a >zig zag?.Il >level? 0 la grandezza quantizzata dei coefficienti er essere codificati.Il >run? ed il numero di it utilizzati er codificare il >level? sono oi codificati utilizzandola codifica di 6uffman ed il >level? 0 codificato utilizzando il 7+I 17ariale +engt2 Integer4.9er sfruttare meglio la correlazione saziale, i coefficienti D# di ogni locco sono codificaticome la differenza dei locc2i D# recedente e successivo.

Il rocesso di decodifica altro non 0 c2e l-inverso di quello di codifica/ il decoder entroicodecodifica la sequenza a >zig zag? dei coefficienti D#T quantizzati e, doo averli de)quantizzati,vengono ri)trasformati in locc2i da .+e matrici di quantizzazione non sono standardizzate, ens; il Q9$G suggerisce una matrice diquantizzazione utilizzando i valori corrisondenti alle minime differenze ercettive di ognicoefficiente D#T.uesta matrice di quantizzazione di ase uA essere utilizzata er generare matrici diquantizzazione di qualità i5 assa semlicemente moltilicando la matrice di artenza con un certocoefficiente di quantizzazione intero.I rocessi di quantizzazione sono revalentemente assi er le asse frequenzeed alti er le alte frequenze.In questo modo, il noise di quantizzazione 0 concentrato nelle frequenze di ercezione visivaminore ed 0 molto imortante in quanto sfrutta l-irrilevanza di segnale, ovvero evita di trasmettereinformazioni di immagine c2e non 2anno imortanza a livello ercettivo.Infine, la matrice di quantizzazione 1se utilizzata4 deve essere trasmessa.#2iaramente, i5 la quantizzazione 0 marcata, i5 il raorto di comressione aumenterà e i5 laqualità dell-immagine finale ricostruita sarà affetta.

H facilmente ossiile erceire come l-immagine di sinistra, rocessata con una fortequantizzazione Q9$G, al costo di avere una codifica maggiore 1e quindi occuare meno sazio4

introduca anc2e dei vistosi artefatti da comressione quali ad esemio il loc=ing, il lur 1sfocatura4


18/179

ed il anding 1ande di colore nel cielo invece di un gradiente uniforme di sfumatura4.#ome detto recedentemente, i locc2i vengono rocessati dal quantizzatore c2e effettua un>taglio? di arte dell-informazione nella codifica loss@.$ene, il quantizzatore rimuoverà er rime le alte frequenze oic28 sono meno imortanti dal

unto di vista ercettivo risetto alle asse frequenze.H inoltre doveroso aggiungere c2e, er quanto riguarda il Q9$G 1ma tanti altri standard utilizzano lo

stesso aroccio4 al momento del rocesso di D#T, l-immagine viene considerata nelle sue duecomonenti fondamentali, quali il >luma? ed il >c2roma?.Il luma 0 definito come la comosizione dell-immagine in scala di grigi, mentre il c2roma 0 la suacomonente di colore.

sinistra 0 raresentata l-immagine originale, mentre a destra sono raresentate le suecomonenti di luma e c2roma.In altre arole, l-immagine e la sua comonente di colore vengono searate, rocessatesearatamente mediante il rocesso soraelencato relativo ai locc2i da e oi ri)assemlate

er oter ricreare l-immagine finale.+-occ2io umano erceisce meglio il luma del c2roma 1cio0 l-immagine risetto al colore4, dunque,in fase di quantizzazione, verrà data i5 imortanza al luma e minore al c2roma in altre arole,verranno tagliate maggiormente le frequenze relative al c2roma risetto a quelle relative al luma.uesto erc28 l-occ2io umano 0 comosto da coni e astoncelli e la nostra vista 0 affetta da tre tii

di visione/ fotoica, mesoica e scotoica.


19/179

!ella visione fotoica 1molta luce4, solo i coni 1c2e sono in grado di erceire luma e c2roma4 sonoin funzione 1immagine in alto4.

!ella visione mesoica 1media luce4, i soli coni non sono sufficienti ad offrire una corretta visioneed entrano in gioco i astoncelli c2e, erA, sono in grado di erceire solamente il luma, ma non ilc2roma 1immagine media4.

!ella visione scotoica 1scarsa luce4, solo i astoncelli sono attivi e la visione 0 rincialmente in

ianco e nero con oc2issima sensiilità alle variazioni di colore 1immagine in asso4.In questo caso, aiamo dunque una differenza della variazione di colore del fiore raresentatosora durante la giornata, quindi aiamo una variazione della sua ercezione nel camo delc2roma, ma non in quello del luma c2e resta invariato.

$.$) /o Standard 5P67 $000

Il Q9$G %&&& venne creato attorno al %&&& con l-oiettivo di ottenere una miglior comressione a arità di qualità risetto allo standard recedente."gni immagine uA essere codificata er intero oure divisa in tile1 ovvero aree rettangolari nonsovraoste c2e sono comresse indiendentemente e, talvolta, una >tile? uA corrisondere ad

un-intera immagine.9er rima cosa, ogni tile 1o l-intera immagine, a seconda dei casi4 0 trasformata utilizzando laTrasformata Discreta di Ravelet idimensionale.Grazie a questo rocesso, le immagini, dalle loro due comonenti 1luma e c2roma4,sono scomoste in differenti livelli di risoluzione.Tali livelli sono effettuati su sotto ande oolate dai coefficienti della Trasformata di Ravelet c2edescrivono le caratteristic2e di frequenza delle aree locali di ogni comonente dell-immagine.H lecito ricordare c2e la Trasformata Discreta di Ravelet uA essere irreversiile 1metodo didefault4 o reversiile.

d ogni modo, doo il rocesso di trasformata, i coefficienti sono sottoosti ad una quantizzazionescalare uniforme, sfruttando una zona morta refissata attorno all-origine.+a dimensione del asso di quantizzazione 0 consentita er sotto)ande, ad ogni modo,il Q9$G %&&& non definisce alcun metodo articolare er il asso di quantizzazione,quindi 0 ossiile utilizzare svariati metodi a rorio iacimento.uesto fatto uA tornare molto comodo in quanto 0 ossiile aggiustarlo in ase all-imortanzavisiva dei coefficienti di sotto)anda in altre arole 0 ossiile utilizzare un asso di quantizzazione

i5 grande er i coefficienti meno imortanti dal uro unto di vista di qualità visiva

ed un asso i5 iccolo er quelli i5 imortanti.


20/179

Doo la quantizzazione, ogni sotto)anda della scomosizione di trasformata 0 divisa in un loccorettangolare non sovraosto c2iamato >locco di codifica? e la codifica entroica 0 effettuataindiendentemente su ognuno di essi, itlane er itlane.

I itlane sono arra@ inari raresentanti un locco di codifica dal suo it i5 significativoa quello meno significativo."gni itlane 0 codificato con una codifica adattiva inaria asata sul contesto in modo da ottenereun it)stream molto comlesso er ogni locco."gni it)stream viene oi organizzato in acc2etti."gni acc2etto uA essere interretato come un incremento di qualità er un livello di risoluzione in

una locazione saziale.uesti acc2etti vengono oi raggruati in strati dove ogni strato uA essere interretato come unincremento di qualità er l-intera immagine a risoluzione comleta.

I vantaggi del Q9$G %&&& risetto al Q9$G si ossono notare maggiormente a itrate molto assi

oic28 il Q9$G %&&& non soffre del loc=ing.


21/179

uesto erc28, dato c2e il Q9$G utilizza la D#T c2e calcola ogni locco di iel indiendentemente1e uA quindi esserci loc=ing4, la Trasformata di Ravelet 1er il rocedimento visto sora4 analizzal-intera immagine 1o una tile4.Di seguito, sono riortati alcuni esemi di codifica Q9$G contro il Q9$G %&&& a assi itrate.H ossiile notare la qualità visiva sensiilmente maggiore in quest-ultimo standard.

d ogni modo, rorio er la differenza delle due trasformate utilizzate, il vantaggio del Q9$G %&&&diventa ressoc28 nullo ad alti itrate/ er immagini di &.%( il eso di quella in Q9$G %&&& 0 del

( minore, mentre er immagini a '.&& 0 i5 iccolo solo del '.


22/179

H ossiile dunque notare come, in immagini con un itrate relativamente alto, la differenza ercettiva sia molto minore. !on solo, la decodifica del Q9$G %&&& comorta anc2e una maggiore comlessità risetto a quelladel Q9$G.

$.') /o standard 7I

nalizzando i due standard recedenti 0 stato introdotto il termine >lossless? 1rivo di erdita4senza erA restare articolare attenzione a questo metodo di codifica.nalizzando lo standard GIF 3 asato su una codifica lossless 3 0 ossiile andare a vedere neldettaglio tale tio di codifica ed analizzare i regi ed i difetti comarandola ai due tii di codificaloss@ 1con erdita4 introdotti con gli standard Q9$G e Q9$G %&&&.9rima di cominciare, erA, 0 doveroso ricordare c2e lo standard GIF 2a suito due aggiornamenti diversione, ovvero il GIFVa ed il GIFWa 1utilizzato er lo i5 er le animazioni4 e la versioneutilizzata 0 ricavaile dai caratteri S#II dei rimi * @te del file codificato.Seur lo standard GIF utilizzi una codifica lossless asata su un algoritmo di comressionelossless universale ideato da +emel, Xiv e Relc2 e c2e rende il nome da tali 1+XR4, durante il

rocesso di conversione di un-immagine in GIF ci uA essere una sostanziale erdita di qualitàe di informazioni.uesto erc28 la codifica GIF associa ad ogni iel un numero di it c2e va da ' ad ed associa,tramite questi, un massimo di %(* diversi ossiili colori ed ogni iel otrà assumere uno traquesti %(* ossiili colori.

– +lgoritmo di 4uffman e 8uello di /empel 9iv 3elc-

#ome 0 stato elencato sora, lo standard di codifica GIF utilizza l-algoritmo +XR, tuttavia, 0necessario analizzare anc2e l-algoritmo di 6uffman in quanto quello di +XR diende da esso.Suoniamo c2e la fonte in ingresso mandi una sequenza di simoli di un alfaeto.

Tale alfaeto uA essere un testo oure una sequenza di it corrisondente ad un-immagine digitaleod anc2e un video.Di ase, un codice 0 maato in simoli e arole di codice.Il motivo er cui 0 maato 0 c2e 0 referiile adattare il messaggio in una forma c2e uA esseremaniolata 1rocessata4, salvata e trasmessa tramite i canali di comunicazione e le arole di codicefatte di it 1zero ed uno4 sono un modo efficiente er farlo.d esemio, se volessimo comunicare delle lettere dell-alfaeto quali , B, #, D er indicare ilivelli di efficienza energetica di una determinata marca di frigoriferi, utilizzeremmo ' er , &' erB, &&& er # e &&' er D.Se volessimo oi mandare una sequenza di lettere tio D#B#B ossiamo mandare un unicomessaggio c2e sarà &&'&&&'''&'&&&&' e sarà il ricevitore a decodificarlo er oter ottenere tali

lettere.


23/179

!el rocesso di decodifica, dunque, il decodificatore andrà a cercare le aroriate sotto)string2econtigue non sovraoste del messaggio ricevuto nel codice condiviso e nella source.Una rorietà molto utile c2e un codice dovree ossedere 0 c2e un simolo corrisondente aduna arola di codice ricevuta uA essere decodificato aena la arola di codice corrisondente 0ricevuta in tal caso si arla di codice istantaneo.+-esemio c2e 2o riortato rima 0 rorio un codice istantaneo.

Il motivo 0 c2e se il ricevitore 2a già decodificato la sequenza e, successivamente,riceve nuovamente ', sa già c2e il simolo corrisondente sarà er forza .Se riceve uno &, allora asetterà il it successivo e, se questo 0 un ', allora sa c2e il simolo 0 B,mentre se 0 un altro &, sarà ancora incaace di saere quale simolo 0 ed asetterà ancora una voltaquello successivo ed allora sarà er certo quale lettera sarà/ & darà # mentre ' darà D.9er quanto riguarda invece i codici non istantanei, questi sono i5 difficili da decodificare.d esemio, rendiamo la solita lista , B, #, D ed assegniamo & ad , &' a B, &'' a # ed ''' a D.In questo modo, aiamo un codice non istantaneo e, se riceviamo una stringa del tio &'''''&',non siamo in grado di decodificare il rimo simolo come semlicemente ricevendo il rimo &.Difatti, non ossiamo essere sicuri c2e il rimo simolo sia oic28 otree anc2e essere B.Di conseguenza, si deve asettare la fine della trasmissione della sequenza er cominciare a

decodificare ed, in questo caso, la sequenza decodificata 0 BDB.uesto codice reso in esemio 0 unicamente decodificaile, ma non 0 semre cos; con i codici nonistantanei, cosa c2e invece non accade nei codici istantanei c2e sono tutti unicamente decodificaili.Un esemio di un codice non istantaneo non unicamente decodificaile uA essere il seguente/ con &, B con ', # con &' e D con ''.#on questo codice ossono esistere diverse sequenze di it c2e non maano un unico simoload esemio, &' otree essere B oure solo #.d ogni modo, dato c2e la maggior arte delle codific2e lossless fanno utilizzo di codici istantanei,mi limiterA ad analizzare quest-ultimi.Un modo conveniente er visualizzare i codici 0 il metodo dell-alero di codice.

!ell-esemio, riorto l-alero di codice er la sequenza con '&, B con &, # con ''& e D con '''.

In generale, un alero di codice 0 un alero inario con tre simoli ai nodi e le cui estremità sono& o ' a significare l-encoding.9er trovare l-encoding di un simolo, il ricevitore deve semlicemente ercorrere il ercorso c2e vadall-inizio dell-alero fino alla lettera desiderata.d esemio, artiremo dall-alto e ci sosteremo a sinistra, trovando B 1&4."ure, artiremo dall-alto, scenderemo di una osizione e troveremo ', oi ci sosteremo a sinistrae troveremo &, quindi '& ovvero e cos; via.H necessario aggiungere un-altra definizione rima di andare a arlare dell-algoritmo di 6uffman ed0 quella della lung2ezza di codice asettata.Dati N simoli, con simoli i c2e si resentano con roailità p con i , se aiamo un codice il cuisimolo i 2a lung2ezza l con i , nell-alero di codice 1ovvero la arola di codice lunga l con i it4 la

lung2ezza di codice asettata sarà/


24/179

In generale, i codici con una iccola lung2ezza di codice asettata sono utili erc28 consentonodi comrimere i messaggi, consegnandoli senza alcuna erdita di informazione 1lossless4,ma consumando comunque meno it.Diremo quindi c2e la lung2ezza + dea essere i5 corta ossiile, in quanto i5 0 ossiile

comrimere tali dati senza erdita, meglio 0.+-alero di codice corrisondente ci dà la maatura ottimale tra i simoli e le arole di codice e,solitamente, non 0 unico.H stato dimostrato inoltre c2e la lung2ezza di codice asettata di ogni codice decodificaile non uAessere i5 iccola dell-entroia, 6, della sottostante roailità di distriuzione tra i simoli.H stato inoltre dimostrata l-esistenza di codici c2e raggiungono l-entroia asintoticamente come lalung2ezza di codice dei messaggi si arossima all-infinito.Inoltre, un codice ottimale deve avere una lung2ezza di codice asettata c2e concordi con l-entroia

er i lung2i messaggi.Tenendo conto di tutto quello eslicato sora, 0 ora ossiile andare ad introdurre due metodi dicodifica/ il rimo metodo, quello di 6uffman, 0 ottimale er codici istantanei quando le roailità

dei vari simoli sono note, i simoli sono indiendenti ed identicamente distriuiti con tali roailità e la maatura 0 ristretta ad un >simolo er simolo?.Il secondo, l-algoritmo +XR, adotta l-attuale distriuzione di simoli nel messaggio,non rifacendosi ad alcuna conoscenza della roailità dei simoli.

– a Co$ifica $i 3&ffman

+a codifica di 6uffman effettua un encoding efficiente er una lista di simoli c2e devono esseretrasmessi quando saiamo la roailità di un dato messaggio.Tornando ad analizzare l-alero di codici analizzato sora, 0 ossiile notare come i simoli i5

roaili 1ad esemio B4 siano i5 vicini all-inizio dell-alero e quindi 2anno una codifica i5 corta,

mentre quelli meno roaili 1tio # o D4 sono i5 distanti ed 2anno una codifica i5 lunga.David 6uffman utilizzA questa osservazione er realizzare un algoritmo di decodifica ad alero

er un codice di lung2ezza variaile ottimale.uello c2e 6uffman voleva fare era creare un alero di decodifica dal asso verso l-altoc2e cominciasse con i simoli meno roaili.In entrata all-algoritmo aiamo dunque un set di simoli e le loro risettive roailità dioccorrenza.In uscita, aiamo un alero di codifica dal quale 0 ossiile leggere la arola c2iavecorrisondente ad ogni simolo.

'4 Ingresso/ un set di S tule. "gni tula consiste in un simolo di messaggio e la sua roailità associata.

$semio/ S←{(0.333, A), (0.5, B), (0.083,C), (0.083, D)}%4 7engono oi rimosse da S le due tule con la roailità i5 assa. 9oi, i due simoli delle

tule rimosse vengono cominati er formare una nuova tula 1c2e raresenta un nodointerno dell-alero di codici4. 7iene oi comutata la roailità di questa nuova tulaaggiungendo le due roailità dalle tule.uesta nuova tula viene in seguito aggiunta ad S.9er far c2iarezza, diciamo c2e se S 2a ! tule all-inizio, ora ne 2a ! 3 ' oic28 due tuleerano state rimosse e ne 0 stata aggiunta nuovamente una sola4.

$semio/ S←{(0.333, A), (0.5, B), (0.167,C ∧ D)}4 7iene oi rietuta la fase due finc28 S contiene una sola tula.


25/179

$semio/ S←{(0.5, B), (0.5, A ∧ (C ∧ D))}

S←{(1.0, B ∧ (A ∧ (C ∧ D)))}

Il risultato 0 dunque un alero di codice c2e raresenta un codice di lung2ezza variaile er i datisimoli e roailità.+a codifica di 6uffman dà risultati migliori quando alcuni simoli sono sostanzialmente i5

roaili di altri.Se tutti i simoli sono equiroaili, allora tutte le arole di codice saranno arossimativamentedella stessa lung2ezza.9er quanto concerne le rorietà della codifica di 6uffman, mi limiterA ad elencarne alcune,senza erA dimostrarle formalmente.

Non unicità: Banalmente, dato c2e &C' arti di ogni coia di rami in un alero di codice ossonoessere invertiti, ci sono diversi encoding c2e 2anno la stessa lung2ezza asettata. Difatti, otreero

esserci diversi codici ottimali er un dato set di roailità di simoli e, a seconda di quanti legamisono sezzati, la codifica di 6uffman uA rodurre diversi aleri di codice non isomorfi, ovveroaleri di codice c2e semrano strutturalmente diversi.d esemio, se rendiamo sei simoli le cui roailità sono Y, Y, 'C, 'C, 'C, otterremo iseguenti aleri di codice 1entrami validi4/

Ottimizzazione: +a codifica di 6uffman 0 ottimizzata nel senso c2e non ci sono codici con unalung2ezza asettata minore quando ristretti a dei codici istantanei ed i messaggi occorrono in unaforma ideale in una roailità di distriuzione conosciuta.

9n o%ni albero $i co$ice ottimale per &n co$ice sen+a prefisso, o%ni no$o p&: avere $&e fi%li o non

averne.

9er dimostrarlo, suoniamo c2e un alero di codice ottimale aia un nodo con un figlio.Se rendiamo quel nodo e lo muoviamo in su di un livello al suo adre, avremo ridotto la lung2ezzadi codice asettata, lasciando il codice ancora decodificaile.In questo caso, allora, significa c2e l-alero di codice di artenza non era un alero di codiceottimale.

Nell;albero $i co$ice $i &na co$ifica $i 3&ffman, ness&n no$o ha esattamente &n fi%lio.


26/179

nc2e questa roosizione 0 ovvia, in quanto, come detto sora nei unti della codifica di6uffman, aiamo semre cominato i due nodi con la roailità i5 assa in un singolo nodo,il c2e significa c2e nell-alero di codifica, ogni nodo interno deriva da due nodi cominati assieme.


27/179

Codifica di Huffman con simboli raggruppati: Suoniamo c2e la codifica di 6uffman er dei datisimoli roduca un codice con una lung2ezza asettata di un certo tot.+a domanda c2e 0 lecito orsi 0/ ossiamo utilizzare la codifica di 6uffman er avvicinarciall-entroia[Un aroccio otree essere quello di raggruare i simoli in dei >meta)simoli? i5 grandied encodare quest-ultimi.

#onsideriamo allora di encodare coie di simoli, trile di simoli, quadrule di simoli e cos; via.H ossiile quindi avvicinarsi all-entroia aumentando il numero di simoli encodati er volta,ma al costo di aumentare anc2e la comlessità di codifica e decodifica.Tale aroccio 2a comunque due rolemi di ase/ il rimo 0 c2e isogna saere la roailitàdi ogni simolo, il secondo 0 c2e isogna resuone c2e la roailità di ogni simolo siaindiendente ed equamente distriuita.d ogni modo, nella realtà delle cose, la roailità dei simoli camia messaggio er messaggio o,alcune volte, addirittura nel mezzo di uno stesso messaggio.Dunque, saree oortuno creare un encoding a lung2ezza variaile adattivoc2e tiene in considerazione il contenuto di ogni messaggio, ma la cosa ella 0 c2e tale encodingesiste già ed 0 rorio l-algoritmo +XR c2e analizzerA di seguitoK

9er oter eslicare meglio il rolema, andiamo ad analizzare il rolema di raresentaredigitalmente e trasmettere i caratteri di un liro 1er esemio4.+-aroccio i5 semlice saree quello di analizzare tale liro e di fare una stima della roailitàdella ricorrenza di diverse lettere dell-alfaeto, doodic28 trattare ogni lettera come simolo edalicare la codifica di 6uffman er comrimere il tutto.uesto metodo 0 assolutamente legittimo e funzionante,tuttavia ermette di avere solo un leggero guadagno in termini di comressione.uesto erc28 la roailità con cui una lettera comare non 0 semre la stessa.d esemio, ossiamo fare una stima dell-utilizzo delle vocali e dare loro i5 imortanza

er oi andare a fare un elenco della ricorrenza delle consonanti, ma uA caitare c2e,in una determinata frase, alcuni consonanti catalogate come >meno imortanti?

ossano comarire i5 volte.Inoltre, tornando all-inizio del nostro aroccio, aiamo detto di aver voluto scegliere come>simoli? le lettere, tuttavia, a seconda del contesto analizzato,avremmo addirittura otuto scegliere le arole.Dunque, un metodo c2e si adatti al materiale c2e deve essere comresso

uA ortare vantaggi significativi.Un aroccio di codifica adattiva 0 quello di utilizzare la doia assata/ nel rimo asso si effettuail conteggio del numero di volte in cui ogni simolo comare, doodic28 viene utilizzatotale conteggio er sviluare una codifica di 6uffman adatta a quel tio di file.

"vviamente, 0 ossiile analizzare anc2e coie di simoli o trile di simoli od anc2e quadruledi simoli 1e cos; via4 a seconda del livello di raggruamento scelto.9er quanto concerne la seconda assata, viene effettuato l-encoding vero e rorio utilizzandola codifica di 6uffman ersonalizzata.d ogni modo, anc2e cos; facendo non si raggiunge ancora la massima efficienza.Il fatto 0 c2e, a rescindere dal livello di raggruamento scelto, non ci sarà mai una codificaottimale er i grui di grandezza diversa 1siano questi i5 grandi o i5 iccoli4.Inoltre, se le roailità di un simolo camia radicalmente in un certo unto del file,una codifica di 6uffman fatta in questo modo risulterà comunque non essere ottimale.Un altro aroccio di codifica adattiva 0 rorio quello utilizzato dalla +XR.ena il messaggio da codificare 0 rocessato, l-algoritmo di codifica +XR crea una taella di

string2e 1aritrariamente lunga4 c2e maa le sequenze di simoli in un inde di !)it.


28/179

+a taella di string2e 2a %! voci in entrata ed il codice trasmesso uA essere utilizzato dal decodercome inde della taella di string2e er oter ricostruire la sequenza di simoli originale.+-algoritmo 0 sviluato in modo c2e la taella di string2e ossa essere ricostruita dal decoder in

ase alle informazioni nello stream encodato in altre arole, la taella di string2e non 0 maitrasmessa ed 0 rorio questo il rinciale vantaggio della codifica +XR.uando si encoda un @te stream 1ovvero una stringa contigua di it4, le rime % 1%(*4 voci in

entrata alla taella di string2e 1numerate da & a %((4 sono inizializzate a conteneretutte le ossiili sequenze ad un @te.+e altre voci in entrata saranno comilate aena il @te stream sarà rocessato.Il rocedimento di codifica 0 semlice e si divide in varie fasi.9er rima cosa, vengono accumulati @te di messaggio finc28 le sequenze accumulate comaiono inqualc2e voce in ingresso della taella di string2e.d un certo unto, l-aending tra il @te successivo 1c2iamiamolo b4 con la sequenza accumulata1c2iamiamola S 4 creerà una sequenza S+b c2e non 0 i5 nella taella di string2e.+-encoder oi rocederà trasmettendo il codice di !)it er la sequenza S , aggiungerà una nuovavoce in ingresso nella taella di string2e er S+b 1se la taella 0 iena al momento dell-aggiuntadella nuova voce in ingresso, rima di aggiungerla4 ed infine resetta S

er oter contenere solo il @te b.uesto rocesso viene rietuto finc28 non vengono consumati tutti i @tea quel unto l-encoder esegue la trasmissione finale del codice di !)it er la sequenza S corrente.

!otiamo dunque come, er ogni trasmissione fatta dall-encoder,questi crea una nuova voce di ingresso nella taella di string2e.Il decoder, dunque, 0 in grado di caire quali siano le nuove voci in ingressonon aena riceve il risettivo codice di !)it.#on una tavola di string2e dulicata costruita dal decoder man mano c2e l-algoritmo rocede,0 ossiile risalire al messaggio d-origine/ asta usare il codice di !)it ricevuto come inde nellatavola di string2e del decoder.

$.() /o standard P7

#ome ultimo standard della codifica delle immagini, rocederA ad analizzare nel dettaglio il 9!Gin quanto uno degli standard i5 diffusi er la codifica delle immagini fisse in modo lossless.+o standard 9!G venne ideato rorio come sostituto del GIF e ne conserva alcune funzionalitàquali le immagini indeate con un massimo di %(* colori, la ossiilità di leggere e scrivere file inmaniera seriale, la ossiilità di elaorare le immagini in maniera immediata aena ricevute 1comequando si clicca un lin=4 er oi rocedere ad un successivo incremento della qualità, la ossiilitàdi marcare arti di immagini come trasarenti, la ossiilità di salvare all-interno del file diimmagine stesso dei commenti ed ovviamente, come già detto, il fatto di essere lossless.

"ltre a queste recedenti ossiilità, il 9!G introduce anc2e alcune imortanti innovazioni qualiimmagini con c2roma fino a : it er iel, mentre le immagini con solo luma sono ossiili finoa '* it er iel un al2a c2annel comleto er una gestione migliore della trasarenza,informazioni sulla gamma dell-immagine 1c2e suorta la corretta riroduzione dell-immagine conluminosità e contrasto rirodotti correttamente a rescindere dalla macc2ina utilizzata errirodurre l-immagine4, un affidaile autocontrollo er individuare file corrottied una raresentazione iniziale i5 veloce nei disla@ rogressivi.

– ;appresentazione dei dati

Tutti gli interi c2e ric2iedono i5 di un @te devono essere ordinati con quelli i5 significativi rima

e quelli meno significativi doo in discendente ordine di imortanza.


29/179

Il it i5 alto 1di valore '%4 di un @te 0 numerato it V, mentre il it i5 asso 1di valore '40 numerato it &.I valori sono unsigned a meno c2e non sia eslicitato diversamentein caso di valori signed, questi sono raresentati in notazione comlemento a due.In caso di valori unsigned, interi da : @te sono limitati al range da & a %' )' er comatiilità,mentre er quelli signed, gli interi da : @te sono limitati al range da )1%' 3 '4 a %' 3 ' er

comatiilità.

–


30/179

uando i iel 2anno meno di it e la larg2ezza delle linee di scansione non 0 divisiile er ilnumero di iel er @te, i it di ordine minore nell-ultimo @te di ogni linea di scansione vengono

uttati ed il loro contenuto non 0 secificato.Un @te >filter)t@e? aggiuntivo 0 aggiunto all-inizio di ogni linea di scansione e questo non vieneconsiderato arte dei dati dell-immagine, ma 0 incluso nello stream di dati inviato in fase dicomressione.

– Il canale alp-a

Il canale al2a raresenta le informazioni di trasarenza er iel e uA essere incluso sia nellamodalità in ianco e nero, sia in quella turecolor, come già detto sora.Il valore zero dell-al2a raresenta una trasarenza comleta, mentre un valore di 2^bitdepth − 1raresenta un iel comletamente oaco.7alori intermedi, dunque, indicano iel arzialmente trasarenti c2e ossono essere cominati conun-immagine di sfondo er comorre oi l-immagine finale.Il canale al2a uA essere incluso con immagini c2e 2anno sia c2e '* it er dato,ma non con immagini c2e ne 2anno meno di .

I dati del canale al2a sono raresentati con la stessa rofondità di it utilizzata er i datidelle immagini ed i dati del canale al2a er ogni iel sono salvati immediatamente doo i datidei iel in ianco e nero o in EGB.I valori di colore er ogni iel non sono intaccati dal valore al2a assegnato allo stessoe questa regola viene c2iamata >non associatività?.d ogni modo, il controllo della trasarenza 0 comunque ossiile anc2e senza un canale al2acomleto/ in un-immagine a colori indeati, il valore al2a uA essere definito er ogni tavolozza inentrata, mentre er le immagini in ianco e nero e er quelle in truecolor, il valore di un singolo

iel uA essere identificato come >trasarente?.Tutto questo 0 gestito dal canale al2a o dai tE!S ausiliari, tuttavia, se nessuno dei due 0 resente,i iel vengono trattati come comletamente oac2i.

– iltraggio

+o standard 9!G consente di filtrare l-immagine rima di comrimerla in modo da aumentarne lacomressiilità senza erA erdere informazioni 1visto c2e, aunto, rieto, il 9!G 0 lossless4.+o standard 9!G 2a definito vari e diversi algoritmi er il filtraggio, inclusa la modalità >none?c2e indica >nessuno? e quindi non filtra l-immagine.+-algoritmo di filtraggio 0 secificato er ogni linea di scansione da un @te filter)t@e c2e recedela linea di scansione filtrata nel datastream re)comresso.+-encoder uA assare da un filtro ad un altro ed il metodo secondo il quale vengono scelti

0 lasciato all-encoder stesso.

– =rdinamento dei dati interlacciati

Un-immagine salvata con lo standard 9!G uA essere salvata sia rogressiva c2e interlacciata ed idecoder sono in grado di leggere quest-ultima in ogni occasione,indiendentemente dalla tiologia del disla@ di riferimento.#on il metodo di interlacciamento di tio &, i iel sono salvati in sequenza da sinistra verso destrae le linee di scansione sono in sequenza dall-alto verso il asso.#on il metodo di interlacciamento di tio ', conosciuto come metodo di dam M. #ostello 1nomedell-autore4, si 2anno sette diverse assi sull-immagine/ ogni asso trasmette un suset dei iel

nell-immagine.


31/179

Il asso in cui ogni iel 0 trasmesso viene definito relicando il seguente attern er ,cominciando da in alto a sinistra.

In ogni asso, i iel selezionati sono trasmessi da sinistra verso destra in una linea di scansionee le scansioni sono selezionate sequenzialmente dall-alto verso il asso.d esemio, il secondo asso contiene i iel :, '%, %& e cos; via delle linee di scansione &, , '*1contando da &,& in alto a sinistra4 l-ultimo asso contiene invece ', , ( ecc.I dati di ogni asso sono disosti come se fossero un-immagine comleta delle dimensioniaroriate ad esemio, se un-immagine comleta 0 di '* er '* iel, allora il terzo asso conterràdue linee di scansione, ognuna contenente quattro iel.

uando i iel 2anno meno di it, ogni linea di scansione 0 ortata a raggiungere un interonumero di @te.Il filtraggio 0 fatto sull-immagine ridotta nel solito modo e viene trasmesso un @te filter)t@ead ogni linea di scansione.Da notare, comunque, c2e l-ordine di trasmissione 0 definito in modo c2e tutte le linee di scansionetrasmesse in un asso aiano lo stesso numero di iel,necessario er il corretto utilizzo di alcuni filtri.Se erA un-immagine contiene meno di cinque rig2e o meno di cinque colonne,alcuni assi saranno comletamente vuoti.Gli encoder ed i decoder devono essere in grado di gestire anc2e questa articolare occasione e,nello secifico, i @te filter)t@e sono associati solo con le linee di scansione non vuote, er cui,in un asso vuoto, non ci sarà alcun @te filter)t@e.

– Correzione della 7amma

+e immagini codificate secondo lo standard 9!G ossono secificare, mediante il gM,le informazioni relative alla raresentazione in outut.I rogrammi er la riroduzione sono fortemente incoraggiati ad utilizzare queste informazioni inmodo da consentire una corretta riroduzione all-utente c2e sta guardando l-immagine, tuttavia,la correzione di gamma non 0 alicata al canale al2a.9er alicazioni di alto livello, l-esatta c2romaticità dei dati EGB uA essere secificata tramite il

c6EM, consentendo una riroduzione i5 accurata risetto a quella offerta dalla sola correzione digamma normale.

– String-e di testo

Un file 9!G 0 in grado di salvare orzioni di testo associate all-immagine, quali, ad esemio,la descrizione delle immagini o informazioni relative al [email protected] set di caratteri consigliato 0 l-IS"CI$# (W)' 1+atin)'4 e, in caso le informazioni vengano scrittein un set di caratteri diverso, c-0 il risc2io c2e i diversi decoder 1nelle diverse iattaforme4le interretino in vario modo e otreero non essere in grado di rirodurle.


32/179

– irma

+o standard di codifica 9!G include una firma c2e viene semre riortata dai rimi otto @te diogni file di immagine quali/ 'V & V V' ' '& %* '& ed indica c2e il file 0 un-immagine9!G e consiste in una serie di dati c2e cominciano con un dato I6DE e finiscono con un datoI$!D.

– /aout dei dati

"gni dato consiste in quattro arti quali/

'4 l&n%he++a/ in intero di : @te unsigned c2e indica il numero di @te nel camo dati del dato.+a lung2ezza conta solo il camo dati e non se stessa, il dato stesso er intero od il #E# e>zero? 0 considerato un valore accettaile. d ogni modo, anc2e se molti decoder trattano la

lung2ezza come unsigned, il suo valore non deve eccedere 2^31 −1 @te.

%4 -ipo $i $ati/ 0 un codice di : @te. 9er convenienza nella descrizione e nell-esaminazione deifile 9!G, i tii di codice sono ristretti er consentire maiuscole e minuscole in lettere S#II1)X, a)z, oure *()W&, WV)'%% decimali4. d ogni modo, encoder e decoder devonotrattare i codici come valori inari fissati e non come string2e di caratteri.

4 Dati $el tipo $i $ato/ sono @te riferiti al tio di dato, se ci sono. !el caso non ci siano,questo camo uA tranquillamente assumere lung2ezza zero.

:4 C?C / il #@clic Eedunanc@ #2ec= 1#ontrollo di Eidondanza #iclico4 0 fatto da : @te ed 0calcolato nei @te recedenti, incluso il codice del tio di dati ed i dati del tio di dato,ma senza includere il camo della lung2ezza ed 0 semre resente, anc2e er i dati vuoti.

– Convenzione di nomenclatura dei dati

I dati del tio di dati sono assegnati in modo c2e il decoder ossa determinare alcune rorietà ditali dati anc2e senza riconoscere il tio.ueste regole sono state introdotte er questione di sicurezza e flessiilità del formato 9!G,consentendo ai decoder di decidere il da farsi quando incontrano un dato a loro sconosciutoad ogni modo, le regole di nomenclatura di solito non sono contemlate quando il decoderriconosce il tio di dato.9er trasmettere le rorietà dei dati, sono utilizzati quattro it del codice del tio,ovvero ( it 1di valore %4 di ogni @te.

uesta scelta significa c2e un umano 0 in grado di leggere le rorietà assegnate a seconda del casoin cui ogni lettera del codice del tio sia maiuscola 1il quinto it 0 &4 o minuscola 1il quinto it 0 '4.d ogni modo, i decoder dovreero testare le rorietà di un dato sconosciuto testandonumericamente i it secificati testare se un carattere 0 maiuscolo o minuscolo 0 del tuttoinefficiente e ersino incorretto in alcuni casi.H del tutto insignificante saere c2e i it di rorietà sono arte integrante del nome dei dati e c2esono sistemati er ogni tio di dato.Dunque, B+"B e +" sareero tii di dato non relazionati e non lo stesso datocon rorietà differenti.I decoder devono riconoscere i codici del tio di dato eseguendo semlicemente un confronto a :

@te.


33/179

9er quanto riguarda la semantica dei it di rorietà, si dividono in/

5) 7it a&siliari cin#&e bit $el primo byte.

0 (mai&scolo) ovvero critico, 5 (min&scolo) ovvero a&siliario.

I dati c2e non sono strettamente necessari a rirodurre significativamente il contenuto delfile, sono considerati dati >ausiliari?. Un decoder c2e incontra un dato sconosciuto nel quale

il it ausiliario 0 ', uA tranquillamente ignorarlo e rocedere alla riroduzionedell-immagine. Un esemio di dato critico 0 l-2eader 1I6DE4.

!) 7it privati cin#&e bit $el secon$o byte.

0 (mai&scolo) ovvero p&bblico, 5 (min&scolo) ovvero privato.

Un dato ulico 0 arte delle secific2e 9!G oure 0 registrato nella lista dei tii di dato ulici seciali. +e alicazioni ossono anc2e definire dati rivati 1non registrati4 er i rori scoi. I nomi dei dati rivati devono avere la seconda lettera minuscola, mentre aquelli ulici saranno semre assegnati nomi con la seconda lettera maiuscola. Da notarec2e i decoder non 2anno isogno di testare i it di rorietà dei dati rivati, visto c2e non2anno un significato funzionale 0 una semlice convenzione assicurarsi c2e i nomi dei dati

ulici e rivati siano corretti.

) 7it $i riserva cin#&e bit $el ter+o byte.

0 (mai&scolo) in conformit> con la corrente versione @N.

I it di riserva ossono essere utilizzati nel caso in cui la terza lettera del nome del dato siariservata er una ossiile esansione futura e tutti i nomi devono avere una terza letteramaiuscola.

") 7it sic&ri $a copiare cin#&e bit $el #&arto byte

0 (mai&scolo) ovvero non sic&ro $a copiare, 5 (min&scolo) ovvero sic&ro $a copiare.

uesto it di rorietà non 0 imortante al uro scoo della decodifica, ma 0 necessario ergli editor dei 9!G 1cio0 rogrammi c2e modificano i 9!G4 in quanto definisce la correttagestione dei dati non riconosciuti in un file c2e 0 stato modificato.Se 0 >sicuro da coiare? 1'4, il dato otree essere coiato nel file 9!G modificato sia c2eil softinsicuro da coiare? 1&4, significa c2e il dato 0 diendente dai dati dell-immagine. Se il

rogramma 2a fatto qualc2e camiamento ad alcuni dati critici, allora i dati >insicuri dacoiare? non devono essere coiati nel 9!G di outut.+-editor dei 9!G 0 semre autorizzato a coiare tutti i dati non riconosciuti se 2a solamenteaggiunto, rimosso, modificato o riordinato i dati ausiliari.Se invece l-editor non 0 in grado di riconoscere un dato critico, dovree riortare un errore

ed interromere la modifica del file 9!G.– /#algoritmo C;C

I dati #E# sono calcolati utilizzando un metodo #E# standard ed il olinomiale utilizzato 0/

x^32 + x^26 +x^23 +x^22 +x^16 +x^12 +x^11 +x^10 + x^8 +x^7 +x^5 + x^4 + x^2 +x+1Il registro #E# a %it 0 inizializzato a tutti ' e oi ogni dato da ogni @te viene rocessatodall-ultimo it significativo 1'4 a quello i5 significativo 1'%4.uando tutti i dati sono rocessati, il registro #E# 0 invertito 1viene reso il suo stessocomlemento4 e tale valore viene oi trasmesso.9er oterlo searare in @te ed ordinare, l-ultimo it significativo del #E# a %it 0 definito er

essere il coefficiente dell- 'esima termine.


34/179

– 4eader dell#immagine I4%;

9arlando della semantica dei it di rorietà 1in articolare dei it ausiliari critici4 2o utilizzato comeesemio l-2eader senza erA secificare cosa fosse nel dettaglio.+-I6DE deve aarire er rimo e contiene : @te er la larg2ezza, : @te er l-altezza, ' @te er la rofondità di it, ' @te er il tio di colore, ' @te er il metodo di comressione, ' @te er il metodo difiltraggio ed ' @te er il metodo di interlacciamento.+arg2ezza ed altezza indicano le dimensioni dell-immagine in iel e sono date da interi di : @te zero viene

considerato un valore non valido ed il massimo 0 di 2^31 − 1 in modo da evitare rolemi con le linguec2e 2anno difficoltà a gestire i valori di : @te unsigned.+a rofondità di it 0 data da un intero di un @te ed indica il numero dei it er inde di tavolozza1e non er iel4 e uA assumere i valori ', %, :, e '*, anc2e se non tutti sono consentiti er tutti itii di colore.Il tio di colore 0 dato da un intero di ' @te e descrive l-interretazione del dato dell-immagine.I codici del tio di colore raresentano somme dei seguenti valori/ ' 1tavolozza utilizzata4, %1colore utilizzato4, : 1canale al2a utilizzato4 e uA assumere valori &, %, , : e *.

+e restrizioni della rofondità di colore er ogni tio di colore sono imoste er semlificarel-imlementazione e er roiire cominazioni c2e non sono en comrimiili.I decoder devono suortare tutte le cominazioni valide di rofondità di it e tio di colore ovvero/tio di colore &, rofondità di it consentite 1', %, :, , '*4 3 ogni iel 0 in ianco e nerotio di colore %, rofondità di it consentite 1, '*4 3 ogni iel 0 una trila EGBtio di colore , rofondità di it consentite 1', %, :, 4 3 ogni iel 0 un indice della tavolozza ecomaiono i dati 9+T$tio di colore :, rofondità di it consentite 1, '*4 3 ogni iel 0 in ianco e nero, seguito dalcanale al2atio di colore *, rofondità di it consentite 1, '*4 3 ogni iel 0 una trila EGB, seguito dal canaleal2a.

I dati di rofondità sono gli stessi di quelli della rofondità di it, eccetto nel caso del tio di colore, in cui i dati della rofondità sono semre it.Il metodo di comressione 0 un intero di un @te c2e indica il metodo utilizzato er comrimere idati dell-immagine.ttualmente, solo il metodo di comressione & 0 definito.Tutte le immagini comresse con lo standard 9!G devono seguire questo sc2ema.Il camo del metodo di comressione 0 fornito er cami futuri dello stesso standard ed i decoderdevono controllare questo @te e riortare un errore se 2a un codice non riconosciuto.9roseguendo al camo successivo, il metodo di filtraggio 0 dato da un intero di ' @te c2e indica ilmetodo di re)rocessing alicato al dato dell-immagine rima della comressione.ttualmente, solo il metodo & 1filtraggio adattivo con cinque tii di filtri ase4 0 definito.9er quanto riguarda il camo del metodo di comressione, i decoder devono controllare questo @tee riortare un errore se 2a un codice non riconosciuto.Il metodo di interlacciamento, infine, 0 indicato da un intero di ' @te c2e riferisce l-ordine dei datidell-immagine attualmente sono definiti due valori/ & 1non interlacciato4 oure ' 1interlacciamentodamV4.d ogni modo, arlerA dell-ordine dei dati interlacciati i5 avanti.


35/179

– Tavolozze P/T6

I dati 9+T$ contengono da ' a %(* tavolozze in entrata, ognuna delle quali 2a una serie di tre @teEGB/ Eed 1' @te & equivale a nero, %(( a rosso4, Green 1' @te & equivale a nero, %(( a verde4,Blue 1' @te & equivale a nero, %(( a lu4, come già detto rima.

Il numero di valori in entrata 0 determinato dalla lung2ezza dei dati e questa risulta in errore se non0 divisiile er .uesto tio di dato deve comarire nel tio di colore e uA aarire er i tii % e *, ma non devecomarire er i tii & e :.Se questo dato comare, deve recedere il rimo dato IDT e non uA esserci i5 di un dato 9+T$.9er il tio di colore 1colori indeati4, 0 ric2iesto il 9+T$.Il rimo valore in entrata nel 9+T$ 0 riferito dal valore del iel &, il secondo dal valore del iel 'e cos; via.Il numero di tavolozze in entrata non deve eccedere il range raresentaile dalla rofondità di itdell-immagine, ma 0 ossiile averne meno.9er i tii di colore % 1truecolor4 e * 1truecolor con il canale al2a4, i dati 9+T$ sono ozionali.

Se resenti, dic2iarano un set di colori suggerito da ' a %(* col quale l-immagine truecolor uAessere quantizzata se l-utente non 0 in grado di rirodurre l-immagine truecolor direttamente.Se non sono resenti n8 il 9+T$, n8 l-s9+T, l-utente dovrà scegliere i colori da solo,ma 0 referiile c2e tale scelta venga fatta dall-encoder.H doveroso ricordare c2e la tavolozza utilizza it 1' @te4 a rescindere dalla rofondità di itdell-immagine.

– %ati dell#immagine I%+T

I dati IDT vengono creati a artire dalle linee di scansione dell-immagine raresentate comedescritto recedentemente e la dimensione finale di questi dati 0 determinata dai cami dell-I6DE.Doodic28, i dati dell-immagine vengono filtrati secondo il metodo di filtraggio secificato semredall-I6DE.Infine, i dati dell-immagine sottoosta a filtraggio vengono comressi utilizzando il metodo dicomressione secificato, ancora, dall-I6DE.I dati IDT contengono lo stream di dati di outut e l-algoritmo di comressione.9er leggere i dati dell-immagine, il rocesso 0 l-inverso.9ossono esserci i5 dati IDT e, in quel caso, aaiono consecutivamente e lo stream di daticomresso sarà la concatenazione di tutti i dati IDT.Gli encoder ossono dividere lo stream di dati comresso in dati IDT a iacimento/ sonoconsentiti i5 dati IDT in modo c2e gli encoder ossano lavorare in una certa quantità di memoria

e, generalmente, la dimensione dei dati corrisonde al uffer size dell-encoder.H doveroso ricordare c2e i ordi dei dati IDT non 2anno imortanza a livello semantico e ossonocollocarsi in qualsiasi unto dello steam di dati comresso.Un file 9!G nel quale ogni dato IDT contiene solo un @te di dati 0 valido, seur raresenti unincrediile sreco di sazio allo stesso modo, anc2e i dati IDT di lung2ezza zero sono validi,seur raresentino uno sreco ancora i5 grandeK

– Il dato I6%

+-I$!D deve aarire er ultimo in quanto indica la fine dello stream di dati del file 9!G ed i suoicami sono vuoti.


36/179

– %ati ausiliari

Tutti i dati ausiliari sono ozionali, nel senso c2e gli encoder non 2anno l-oligo di scriverli ed idecoder ossono tranquillamente ignorarli.d ogni modo, gli encoder sono invitati a scrivere dei dati ausiliari standard quando 0 ossiile

ed i decoder sono invitati ad interretare questi dati quando 0 ossiile.9arlerA dei vari dati ausiliari ossiili di seguito, ad ogni modo, l-ordine in cui ne arlonon 0 necessariamente l-ordine in cui comaiono in uno stream di dati 9!G.

– Informazioni ausiliarie di trasparenza

uesto dato contiene le informazioni nello stream di dati c2e non include un canale al2a comleto.

– t;S

Il tE!S secifica c2e l-immagine utilizza una trasarenza semlice/ i valori al2a associati alletavolozze in entrata 1er le immagini a colori indeati4 o i colori trasarenti singoli 1er le immaginiin ianco e nero e quelle truecolor4.nc2e se una trasarenza semlice non 0 efficiente come un canale al2a comleto,questa ric2iede meno sazio ed in molti casi 0 sufficiente.9er il tio di colore 1colori indeati4, il tE!S contiene una serie di valori al2a di un @tecorrisondenti ai valori in entrata del 9+T$."gni entrata indica c2e iel dell-indice di tavolozza corrisondente devono essere trattati come seavessero il valore al2a secifico ed i valori al2a sono come quelli in un canale al2a comleto ad it/ & 0 comletamente trasarente, %(( 0 comletamente oaco,a rescindere dalla rofondità di it dell-immagine.

Il tE!S non deve contenere i5 valori al2a dei dati di tavolozze in entrata, tuttavia ne uAcontenere di meno in quest-ultimo caso, tutti i valori rimanenti vengono considerati %((.9er il tio di colore & 1ianco e nero4, il tE!S contiene un solo valore di livello di grigio, del tio/

Gray: 2 bytes, range 0. . . 2^proo!dit" di bit − 1

Se la rofondità di it 0 minore di '*, vengono utilizzati gli ultimi it significativi e gli altri sono &.9iel del livello di grigio secificato sono trattati come trasarenti 1cio0 come valore al2a &4,

mentre tutti gli altri iel sono trattati come comletamente oac2i 1valore al2a 2^proo!dit" di bit −1#.Il tE!S 0 roiito er i tii di colore : e *, visto c2e 0 resente un canale al2a comleto.uando si 2a a c2e fare con ianc2i e neri o dati truecolor da '*it, 0 imortante comarare

entrami i @te dei valori dei camioni 1samle4 er determinare se un iel 0 trasarente.Ultimo aunto 0 c2e il tE!S, quando resente, deve recedere il rimo dato IDT e seguire il9+T$, se resente.

– Informazioni dello spazio di colore

uesti dati sono relativi alla riroduzione dei camioni 1samle4 dell-immagine.

– 7amma dell#immagine g+>+

I dati gM secificano la relazione tra i camioni 1samle4 dell-immagine e l-intensità di

riroduzione in outut desiderata/ $a%p&e ' &i(ht o)t^(a%%a


37/179

>samle? e >lig2t\out? sono normalizzati nel range &.& 1intensità minima4, '.& 1intensità massima4.Dunque/

Il valore 0 encodato come un intero unsigned di : @te.Il valore di gamma non 2a effetto sugli al2a samle,c2e sono semre una frazione lineare dell-oacità comleta.Se l-encoder non sa il valore di gamma dell-immagine, dovree evitare di scrivere il dato gM.Tecnicamente, >l-intensità di riroduzione in outut desiderata? 0 ancora troo >vago? come dato.In altre arole, si devono secificare le condizioni di riroduzione in cui 0 desiderato.9er il gM ci sono condizioni di riroduzione di referenza delle secific2e sEGB.ggiustare er le diverse condizioni di riroduzione 0 un rocedimento comlessoe di solito 0 gestito dal #MS 1#olor Management [email protected] non viene fatto alcun aggiustamento, l-errore, di solito, 0 comunque iccolo.+e alicazioni c2e ric2iedono un-alta fedeltà di colore otreero voler utilizzare un dato sEGB

o un dato i##9 ed analizzerA entrami i5 avanti.Se il gM 0 resente, deve recedere il rimo dato IDT e deve anc2e recedere il 9+T$,se resente.Se sono resenti l-sEGB o l-i##9, il dato gM viene sovrascritto.

– Cromaticit? primarie c4;>

+e alicazioni c2e ric2iedono una secifica di colore indiendente dal device in un file 9!G ossono utilizzare i dati c6EM er secificare le 'W' cromaticità #I$ , @ di rosso, verde e lu rimarie utilizzate nell-immagine ed i unti ianc2i di riferimento e contiene/

"gni valore 0 encodato come intero unsigned di : @te.Il c6EM 0 consentito in tutti i file 9!G, seene sia di oca imortanza

er le immagini in ianco e nero.Se l-encoder non conosce i valori di cromaticità, dovree evitare di scrivere il c6EM

e l-assenza di tale dato indica c2e i colori rimari dell-immagine sono diendenti dal device.Se resente, il c6EM deve recedere il rimo IDT ed il 9+T$, se resente.Se resenti e riconosciuti, i dati sEGB e i##9 sovrascrivono il dato c6EM.

– s;7B@ Spazio di colore standard per l#;7B

Se l-sEGB 0 resente, i samle dell-immagine sono conformi allo sazio di colore sEGBe dovreero essere rirodotti utilizzando un rendering secifico.+-sEGB contiene un dato di rendering c2e definisce : valori/ ercettivo, relativo alla colorimetrica,della saturazione e colorimetrico assoluto.uello ercettivo 0 er le immagini er le quali 0 referiile un uon adattamento della gamma eril device di outut al costo di un accuratezza colorimetrica, come nelle fotografie.


38/179

uello relativo alla colorimetrica 0 er le immagini c2e ric2iedono c2e l-aarenza dei colori siafedele, tio i log2i.uello della saturazione 0 er le immagini er le quali 0 referiile reservare la saturazione alcosto di un accuratezza in 2ue e luminosità, come nei grafici.uello colorimetrico assoluto 0 er le immagini er le quali 0 necessario reservareuna colorimetrica assoluta.

Un-alicazione c2e scrive un dato sEGB dovree anc2e scriverne uno gM 1e, magari, anc2eun c6EM4 er comatiilità con le alicazioni c2e non sono in grado di utilizzare l-sEGB stesso.Se resente, le alicazioni c2e riconoscono l-sEGB e sono caaci della gestione del colore,ignorano i dati relativi a gM e c6EM.Tale dato deve recedere il rimo dato IDT ed il 9+T$, se resente.Eicordo infine c2e l-sEGB e l-i##9 non dovreero comarire insieme.

– iCCP@ profilo ICC integrato

Se il dato i##9 0 resente, i samle dell-immagine sono conformi allo sazio di colore e vengonoraresentate dal rofilo I## integrato.

[Francesco Bucciantini] Utilizzo Delle Trasformate Nella Codifica Delle Immagini Fisse, In Movimento...

Documents

Transcript of [Francesco Bucciantini] Utilizzo Delle Trasformate Nella Codifica Delle Immagini Fisse, In Movimento...