Capitolo 2 Trasformata di Wavelet

Trasformata di Wavelet

Un considerevole interesse si ` e sviluppato nell’ultimo decennio per un particolare tipo di trasformata, che va sotto il nome di wavelet transform, che si ` e rivela- ta molto efficaci per risolvere problemi sia di compressione delle immagini che di pattern recognition (rivelazione di bordi o di oggetti particolari nelle immagini o, in generale, di transienti in segnali di qualsiasi dimensionalit` a).

Il successo di queste trasformate ` e anche legato al fatto che tutti i segnali che cor- rispondono a rapide transizioni (p.es. un eco su un segnale da un radar rotante, oppure i bordi di un oggetto o una linea di costa in una immagine) sono mal rappresentati dalla trasformata di Fourier e da ogni altra trasformazione che usi una base costituita da funzioni a supporto non compatto (cio` e funzioni che si estendono da −∞ a +∞). Queste sono infatti inadeguate a descrivere (e quindi rivelare) efficientemente i segnali transienti molto localizzati come, per esempio, l’accendersi di una lampada in una scena.

In linea di principio la trasformata di Fourier ` e in grado di rappresentare qual- siasi funzione analitica, e quindi anche un transiente, usando una base di seni e coseni. Il prezzo che si paga ` e di generare un gran numero di sinusoidi non nulle, sfasate in modo tale da annullarsi a vicenda in quasi tutto lo spazio ad eccezione della regione in cui si presenta il segnale transiente. Una situazione del genere, vista dal lato dello spettro di Fourier, appare molto confusa perch` e la potenza del segnale si distribuir` a su moltissime frequenze rendendo difficile la ricostruzione del segnale di partenza a partire dal campionamento.

Per evitare inconvenienti di questo tipo ` e importante scegliere funzioni di base che abbiano un supporto compatto e che possano variare sia in posizione che

35

in frequenza. Si tratta cio` e di funzioni di estensione limitata (nello spazio o nel tempo a seconda del tipo di segnale analizzato) dette wavelets ¹ .

La Fig 2.1 mostra la differenza tra onda sinusoidale ed una wavelet alla stessa frequenza. Sia con funzioni seno e coseno che con funzioni di wavelet si possono realizzare basi ortogonali su cui proiettare segnali. La differenza sta nel fatto che le funzioni seno e coseno, usate nella trasformata di Fourier, si estendono su un intervallo infinito mentre le wavelet sono diverse da zero solo su una regione finita, caratteristica quest’ultima che apre interessanti possibilit` a nell’analisi dei segnali.

Figura 2.1: Confronto tra una sinusoide ed una wavelet di pari frequenza. Tutte e due le funzioni sono utilizzabili per valutare il contenuto in frequenza di un segnale, ma la wavelet ` e localizzata mentre la sinusoide si estende all’infinito.

2.1 Il Piano Tempo-Frequenza

L’analisi di Fourier ci permette di indagare il contenuto in frequenza di un seg- nale, ma non d` a alcuna informazione sulla loro collocazione temporale o spaziale.

Questo aspetto ` e particolarmente rilevante avendo a che fare con segnali non stazionari come illustrato in Figura 2.2 che mostra due segnali che, pur essendo chiaramente diversi (grafici a sinistra) appaiono all’analisi di Fourier come prati- camente sovrapponibili (grafici a destra). Lo spettro di frequenza ottenuto nei due casi mostra correttamente che il contenuto in frequenza e’ simile, ma non d` a alcuna informazione sull’istante in cui si presentano le diverse frequenze.Questo tipo di problema riguarda quindi tutti i segnali che contengano delle componenti transitorie che per loro natura sono irregolari e localizzate.

1

una traduzione italiana potrebbe essere “piccole onde, ondine” ma ` e ormai uso comune

lasciare il termine invariato.

Per questo tipo di segnali possiamo intuitivamente immaginare un piano tempo- frequenza in cui ognuna di queste componenti occupa una diversa posizione come

` e mostrato in Figura 2.3 in cui un segnale monodimensionale (in funzione del tempo) contiene due impulsi transitori di diversa frequenza. Nella stessa figura

` e mostrato come questi impulsi possano essere rappresentati su un piano tempo- frequenza in modo da mantenere l’informazione sia sulle frequenze che sulla loro localizzazione nel tempo.

Figura 2.2: Segnali costituiti da sinusoidi non localizzate (sopra) e localizzate (sotto). Lo spettro di Fourier (a destra) individua correttamente le frequenze presenti ma non d` a alcuna informazione sulla loro localizzazione.

Figura 2.3: Un segnale contenente due frequenze localizzate nel tempo (sopra) ` e rappresentato nel piano tempo-frequenza (sotto) come due picchi centrati ai tempi e frequenze corrispondenti.

Un esempio di questo approccio ` e mostrato dallo schema usato in musica (Fig. 2.4)

che, introducendo il pentagramma, orienta il tempo lungo l’asse x e le frequenze

(le note che nel nostro linguaggio sono i transienti) lungo l’asse y. La durata dei

transienti ` e poi indicata dal carattere della nota invece che dalla sua estensione temporale, ma ` e solo una differenza di notazione.

Figura 2.4: Un esempio di diagramma tempo-frequenza: il pentagramma.

Analogamente nel caso di segnali 2-D come le immagini potremo rappresentare due diversi oggetti dell’immagine analizzando spazio-frequenza lungo le due di- mensioni dell’immagine rappresentando quindi i transienti presenti in una terza dimensione che rappresenti la frequenza. Si immagini quindi una rappresen- tazione grafica del tipo mostrato in Figura 2.5. Gli oggetti appaiono gi` a separati spazialmente, ma per evidenziare il loro diverso contenuto in frequenza filtriamo l’immagine f(x,y) con filtri a frequenza variabile in modo tale da realizzare una pila di immagini h <sub>1</sub> (x, y), h <sub>2</sub> (x, y), ... filtrate a diverse frequenze. La separazione in frequenza pu` o cos`ı avvenire lungo la pila delle immagini filtrate.

Figura 2.5: Le frequenze contenute in un’immagine sono rappresentabili come un un set di piani allineati all’immagine, ognuno contenente le ampiezze ad una data frequenza nella corrispondente regione dell’immagine.

2.1.1 Trasformate

Abbiamo visto che vi sono tre diversi, ma imparentati, approcci che utilizzano la

trasformata di Fourier: la trasformata integrale, l’espansione in serie, la trasfor-

mata discreta.

La trasformata integrale, insieme alla sua trasformata inversa, associa due funzioni continue (il segnale ed il suo spettro) ed in una dimensione ` e data da

F (s) = Z +∞

−∞

f (x)e ^−j2πxs dx

f (s) = Z +∞

−∞

F (s)e ^j2πxs ds

L’espansione in serie di Fourier rappresenta, attraverso una serie di coeffi- cienti, una funzione periodica. Si ottiene rendendo la frequenza s = n∆s una variabile discreta, cos`ı che dalla precedente abbiamo:

F _n = F (n∆s) = Z L

0

f (x)e ^{−j2πn∆s x} dx

f (s) = ∆s

∞

X

n=0

F n e ^{j2πn∆s x} dove L rappresenta il periodo e ∆s = 1/L.

La trasformata discreta infine mette in relazione una funzione campionata con il suo spettro di Fourier, anch’esso campionato, con il numero di campi- oni indipendenti (detti anche gradi di libert` a) uguale nei corrispondenti domini.

Questa trasformata ` e ottenuta rendendo discreto lo spazio: x = i∆x. Allora, se g(x) ` e band-limited (cio` e contiene solo un intervallo di frequenze limitato) ed il campionamento spaziale soddisfa il teorema di sampling allora g _i = g(i∆x) e avremo:

G _k = 1

√ N

N −1

X

i=0

g _i e ^−j2πk

g _i = 1

√ N

N −1

X

k=0

G _k e ^j2πk

In tutte e tre queste trasformazioni:

- la base ortonormale ` e formata da seni e coseni di differenti frequenze - ciascun coefficiente delle trasformazioni ` e determinato dal prodotto interno

(ovvero la proiezione) della funzione da trasformare con una delle funzioni

che formano la base.

- la trasformata inversa corrisponde a sommare le funzioni della base, ognuna pesata dai coefficienti della trasformazione. Queste somme diventano un integrale nel caso della trasformata continua.

Questo tipo di architettura ` e comune a tutte le trasformate, indipendentemente dalla base usata, per cui le tecniche di calcolo ed i conceti sottostanti sono molto simili in tutte le trasformazioni. Inoltre, nei casi incui la base ` e costituita da funzioni reali la trasformata inversa ` e identica a quella diretta.

Wavelets

Le stesse operazioni si possono definire per la trasformata con wavelet e cio` e: una trasformata continua, un’espansione in serie, una trasformata discreta. Tuttavia una differenza sostanziale esiste perch` e le basi della trasformata con wavelets possono anche non essere ortonormali. In altre parole questo significa che un’es- pansione in serie di wavelets non ortonormali potrebbe richiedere una serie di termini (o coefficienti) molto pi` u lunga (e quindi, in generale, non ottimale) per rappresentare una funzione band-limited. Se la sequenza di termini viene tronca- ta ad un numero finito di termini allora la funzione originale sar` a rappresentata con un certo grado di approssimazione.

Per introdurre i concetti consideriamo il caso di segnali unidimensionali e di funzioni a quadrato integrabile sull’asse reale. L’insieme di queste funzioni viene comunemente indicato con L ² (R) e quindi dire che f (x) ∈ L ² (R) significher` a che

Z +∞

−∞

|f (x)| ² dx < ∞ (2.1)

La tecnica usata nell’analisi con le wavelet per generare una base ` e di scegliere una funzione prototipo ψ(x) per poi dilatarla e traslarla per generare gli elementi della base. Questa funzione generatrice ` e di solito una funzione oscillante, solitamente centrata sull’origine, che tende rapidamente a zero per |x| → ∞. Questa scelta fa si che gli integrali siano finiti e quindi che ψ(x) ∈ L ² (R) .

2.1.2 Wavelets e trasformata continua

Se ψ(x) ` e una funzione reale con spettro di Fourier dato da Ψ(s), allora potr` a

essere una generatrice di wavelet se soddisfa al seguente criterio, detto di ammis-

sibilit` a:

C _ψ = Z +∞

−∞

|Ψ(s)| ²

|s| ds < ∞ (2.2)

Si noti che, a causa della presenza di s al denominatore, per evitare la divergenza nell’origine dovr` a anche essere:

Ψ(0) = 0 che a sua volta implica → Z +∞

−∞

ψ(x)dx = 0 (2.3) Questa affermazione deriva dal fatto che l’ampiezza dello spettro di Fourier a frequenza zero ` e pari al valor medio della funzione, da cui segue la (2.3).

Inoltre, poich` e dovr` a anche essere Ψ(∞) = 0 ci rendiamo conto che una wavelet ammissibile non potr` a contenere alte frequenze e quindi il suo spettro sar` a abbas- tanza simile a quello di un filtro passa banda. In questo senso potremmo anche dire che ogni filtro passa banda a media zero pu` o generare una base di wavelet.

In pratica, il set di wavelet che costituiscono una base ` e generato traslando e dilatando una certa funzione generatrice ψ(x) come in:

ψ _a,b = 1

√ a ψ  x − b a



(2.4) dove a, b sono numeri reali con a > 0. Per le relazioni che intercorrono tra queste funzioni la ψ viene detta mother wavelet e le ψ _a,b sono le daughter wavelets ² . Il ruolo di a ` e di dilatare o comprimere la scala, mentre quello di b ` e di produrre una traslazione della funzione, in questo caso lungo l’asse x. Il fattore di scala 1/ √

a assicura che la norma delle funzioni di base (le wavelet) sia sempre la stessa, indipendentemente dalla scala, poich` e:

ψ  x − b a



=

Z +∞

−∞

ψ  x − b a

   

2

dx

! 1/2

= √

a kψ(x)k (2.5)

dove l’integrale ` e risolto dalla sostituzione (x − b)/a = dy. Questo mette in evidenza un’altra propriet` a della base che, essendo generata da una funzione a media nulla, sar` a costitutita da elementi tutti a media zero. Questa caratteristica implica che l’informazione sulla media del segnale f (x) dovr` a essere considerata separatamente non potendo essere codificata con funzioni di base a media nulla ³ .

2

dette anche baby wavelets

3

Al contrario, nel caso di Fourier la media del segnale ` e codificata nella componente a

frequenza zero della trasformata.

La figura 2.6 mostra alcuni esempi tra le wavelet pi` u usate, la cui espressione analitica ` e data da:

ψ(x) = 1 (0 ≤ x < 1); −1 (1 ≤ x ≤ 2); 0 (altrove) Haar

ψ(x) = 2

3 ^1/2 π ^1/4 (1 − x ² )e ^−x

^/2 M exicanHat

ψ(x) = e ^−x

^/2 cos(5 x) M orlet

Si noti come tutte siano a media zero e quindi le loro trasformate di Fourier, mostrate in sulla destra di Figura 2.6, saranno nulle a frequenza zero.

Figura 2.6: Esempi di wavelets di uso comune. A sinistra, dall’alto verso il basso: (a) Haar, (b) Mexican Hat, (c) Morlet wavelet. A destra sono mostrate le corrispondenti rappresentazioni nelle spazio di Fourier. Si noti che le wavelets sono tutte a media zero e pertanto nello spazio di Fourier valgono zero a frequenza nulla. Nel caso Morlet la trasformata di Fourier ` e mostrata per pi` u valori del parametro di scala che regola la frequenza di indagine della wavelet.

Formalmente, per esprimere la trasformata continua di una funzione f (x) rispetto ad una wavelet ψ(x), scriviamo:

W f (a, b) =< f, ψ a,b >=

Z +∞

−∞

f (x)ψ a,b (x)dx (2.6)

Come si vede i coefficienti delle trasformazione sono dati dal prodotto interno

<> ⁴ della funzione da trasformare con ciascuna delle funzioni della base.

Si pu` o mostrare <sup>5</sup> che la trasformazione inversa ` e data da:

f (x) = 1 C _ψ

Z +∞

0

Z +∞

−∞

W _f (a, b)ψ _a,b (x)db da

a ² (2.7)

con ψ _a,b (x) data dalla (2.4).

Il caso continuo in 2D

Abbiamo visto che la trasformata di wavelet di una funzione f (x) 1D ` e una fun- zione W (a, b) di due variabili, a (scala) e b (shift), al variare delle quali ` e possibile indagare il contenuto di un segnale sia in tempo (o spazio) che in frequenza. In conseguenza, per rappresentare la trasformata di wavelet di un segnale 1D abbi- amo bisogno di uno spazio 2D. Analogamente per una immagine, che ` e un segnale bidimensionale, l’operazione di trasformazione aumenta la dimensionalit` a di uno:

W f (a, b x , b y ) = Z +∞

−∞

Z +∞

−∞

f (x, y)ψ a,b

,b

(x, y)db x db y (2.8) con b _x , b _y che specificano le traslazioni nelle due dimensioni. Si noti che qui il parametro di scala ` e stato assunto uguale nelle due dimensioni.

La corrispondente trasformazione inversa ` e data da:

f (x, y) = Z +∞

0

Z +∞

−∞

Z +∞

−∞

W _f (a, b _x , b _y )ψ _a,b

_,b

(x, y)db _x db _y da

a ³ (2.9) Nelle precedenti:

ψ a,b

,b

(x, y) = 1

|a| ψ  x − b _x

a , y − b _y a



(2.10) con ψ(x, y) wavelet generatrice della base bidimensionale.

Interpretazione in termini di “filter bank”

Un possibile modo di interpretare la trasformata di wavelet continua ` e di im- maginarla come una serie di filtri che vengono applicati al segnale da analizzare.

4

questo prodotto corrisponde alla proiezione di un elemento dello spazio (una funzione o un segnale) su un elemento della base (una wavelet)

5

Grossman & Morlet, Decomposition of Hardy Function into Square Integrable Wavelets,

J.Appl.Math. 15, 723 (1984)

Questa possibilit` a nasce dal fatto che le wavelet, essendo funzioni a media zero, nello spazio di Fourier appaiono come filtri “passa-banda”, che possono essere sintonizzati su frequenze particolari al variare della scala della wavelet. Questo aspetto ` e evidente in Figura 2.6 che nei riquadri in basso mostra come la Morlet wavelet cambia la risposta in frequenza al variare della scala.

Per questo torniamo a considerare la trasformata di Fourier del nostro segnale ed immaginiamo di poter suddividere lo spettro delle frequenze in parti, ciascuna corrispondente ad un certo intervallo di frequenze.

Come abbiamo visto, se con ψ indichiamo la funzione “mother”, possiamo gener- are una base esprimendone gli elementi attraverso la relazione (vedi l’eq. 2.4 con b=0)

ψ _a (x) = 1

√ a ψ(x/a). (2.11)

Si tratta di una operazione di scaling (rispetto alla scala rappresentata da a) e di normalizzazione (ottenuta moltiplicando per 1/ √

a allo scopo di ottenere la stessa norma alle varie scale). Per come sono state definite, le wavelets cos`ı generate avranno larghezza tanto pi` u grande quanto pi` u a sar` a grande, mantenendo sempre valor medio nullo e norma costante (come richiesto dalle eq. 2.3, 2.4, 2.5).

Per evidenziare l’equivalenza tra la trasformata di wavelet e l’operazione di con- voluzione, definiamo la complessa-coniugata-riflessa di una wavelet come:

ψ ˜ _a (x) = ψ ^∗ (−x) = 1

√ a ψ ^∗ (−x/a) (2.12)

che permette di riscrivere la trasformata continua rendendo evidente il legame con la convoluzione (qui indicata dall’asterisco ∗):

W _f (a, b) = Z +∞

−∞

f (x) ˜ ψ _a (b − x)dx = f ∗ ˜ ψ _a (2.13)

Quindi, per ottenere la trasformata di wavelet ad una data scala a possiamo usare

la convoluzione della funzione f (x) con la coniugata riflessa della wavelet alla

scala scelta. Ripetere questa operazione per pi` u valori della scala corrisponde in

definitiva a filtrare il segnale f (x) con filtri a diversa frequenza, e quindi scegliendo

opportunamente le scale da indagare (e quindi le frequenze coinvolte) saremo in

grado di coprire l’intero spettro delle frequenze. Questo approccio ` e illustrato

nella Figura 2.7 che mostra una copertura dello spettro di frequenza ottenuta con

una successione di bande passanti adiacenti le une alle altre, ognuna generata dal

corrispondente livello della suddivisione in wavelets (qui diadiche).

Figura 2.7: Dall’alto verso il basso: una mother wavelet, al livello 0, che genera due livelli successivi di daughter wavelets. Nel corrispondente spazio di Fourier, mostrato in basso, sono rappresentate le regioni corrispondenti alle frequenze indagate. H

corrisponde alla banda di frequenza maggiore indagata dalla wavelet di livello 0 (mother), H

ed H

sono le bande relative alle daughter wavelets dei due livelli successivi. La rappresentazione qui ` e diadica ed i valori sovrapposti alle bande rappresentano i fattori di normalizzazione ai vari livelli.

La trasformazione inversa, che ricostruisce il segnale, sar` a data da f (x) = 1

C _V Z +∞

0

Z +∞

−∞

[f ∗ ˜ ψ](b)ψ _a (b − x)db da a ² = 1

C _V Z +∞

0

[f ∗ ˜ ψ ∗ ψ _a ] da

a ² (2.14) Inoltre, in analogia alla propriet` a di similarit` a che vale per la trasformata di Fourier ⁶ :

F {f (ax)} = 1

a F (s/a) (2.15)

si pu` o ricavare per la trasformata di wavelet la relazione:

Ψ _a (s) = F {ψ _a (x)} = √

aΨ(as) (2.16)

che mostra come un aumento della scala a corrisponda ad indagare una frequenza pi` u bassa (Figura 2.7).

Questa propriet` a introduce naturalmente l’idea che, dato un segnale, la sua con- voluzione con una wavelet di estensione fissata equivale ad estrarre, dallo stesso

6

ad una contrazione in un dominio corrisponde una espansione nell’altro

segnale, le sole frequenze corrispondenti alla scala di wavelet usata. In questo senso possiamo quindi intendere l’analisi in wavelet come una scomposizione del segnale nelle sue diverse frequenze, associate alle diverse scale indagate dal set di wavelet scelto. ` E come usare una serie di filtri in frequenza che costituiscono il cosiddetto “filter bank” rappresentato nella parte bassa della Figura 2.7 .

2.1.3 Wavelets discrete

La trasformata continua ` e utile per intuire le similitudini con l’approccio di Fouri- er ma presenta una serie di inconvenienti che suggeriscono come pi` u efficiente una analisi “discreta”. In breve:

- la base ` e ridondante: si pu` o infatti notare che nella (2.6) la wavelet viene traslata e scalata in modo continuo implicando quindi che inevitabilmente le funzioni (e quindi le frequenze passanti) andranno a sovrapporsi con continuit` a le une alle altre e non possono quindi costituire una base or- togonale <sup>7</sup> . A meno che non vengano traslate e scalate di quantit` a discrete opportunanmente scelte per non sovrapporsi le una alle altre, consentendo quindi di costruire una base ortogonale su cui “proiettare” i segnali. In altri termini si p` o dire che usare wavelet continue per trasformare un seg- nale ` e un’operazione inefficiente in quanto si dovranno calcolare un gran numero di coefficienti che, essendo ridondanti, conterranno informazioni gi` a parzialmente presenti nei coefficienti adiacenti. Dal lato delle frequenze sarebbe come costruire un “filter bank” in cui le regioni esplorate dai filtri, invece di essere complementari, si sovrappongono a quelle dei filtri adiacenti replicando quindi pi` u volte la stessa informazione;

- il numero di wavelets necessarie ad indagare il segnale ` e virtualmente in- finito;

- la maggior parte delle funzioni di wavelet usate non permettono soluzioni analitiche per le proiezioni e richiedono quindi metodi numerici per il cal- colo.

Diventa quindi pi` u conveniente usare un approccio discreto, che viene detto dis- crete wavelet transform o DWT, che utilizza forme appropriate di wavelet,

7

Nel caso di Fourier la funzioni continue sin e cos costituiscono una base perch` e il loro

prodotto integrato su tutto il dominio ` e nullo. Qui invece le funzioni sono finite ed il loro

prodotto si annulla solo in particolari condizioni che vengono soddisfatte con una opportuna

scelta delle wavelet discretizzate.

alcune delle quali mostrate in Fig. 2.6. Queste hanno le propriet` a matematiche giuste per poter formare basi ortogonali quando usate secondo uno schema discre- to, consentendo quindi una decomposizione efficiente del segnale cos`ı come una sua fedele ricostruzione.

Essenzialmente possiamo dire che la decomposizione in wavelet ` e un modo di analizzare il contenuto di un segnale utilizzando due forme particolari di coeffi- cienti (che poi saranno delle funzioni da calcolare) che rappresentano specifiche componenti (additive) dello stesso segnale. Il senso che avranno queste compo- nenti sar` a quello di rappresentare rispettivamente la scala ed il dettaglio del segnale che sono le informazioni che emergono dal filtrare il segnale con

- un filtro passa alto, che mette in evidenza le componenti ad alta frequenza (dettagli);

- un filtro passa basso che corrisponde ai coefficienti di scala (scaling).

Reiterando questo approccio su tutte le scale che si vogliono/possono indagare si ottengono una serie di segnali filtrati utili per una successiva analisi che potr` a individuare non solo la presenza di una data frequenza ma anche il tempo nel quale questa si presenta (vedi anche Figura 2.3).

La tabella 2.1 che segue vuole essere un aiuto a superare le difficolt` a che possono insorgere per l’uso di una terminologia non sempre chiarissima che si ritrova nell’ampia e varia letteratura in questo campo. In tabella sono riassunti i termini pi` u frequentemente incontrati in letteratura per indicare propriet` a e senso fisico di queste due componenti:

Discretizzazione diadica

In generale una famiglia di wavelet viene descritta a partire dalla mother wavelet rappresentata dalla ψ(x) che soddisfa a queste condizioni:

Z

kψ(x)k ² dx = 1 normalizzazione Z

|ψ(x)| dx < ∞ finitezza Z

ψ(x)dx = 0 media zero

Nelle applicazioni la “mother” wavelet viene replicata in una forma scalata e

traslata generando cos`ı le daughter wavelets, anch’esse normalizzate, che vanno

Caratteristica φ(t) ψ(t) Comments tipo di funzione scaling function wavelet function

nome attribuito father wavelet mother wavelet corrispondenza con scale coefficient detail function componente investigata deterministic stochastic azione prodotta scaling ψ halves bandpass filter dalla dicretizzazione the bandwidth of φ scaled and shifted filtro equivalente low pass scaling high pass details

Tabella 2.1: Caratteri e nomenclatura corrispondente usata per descrivere l’azione delle wavelets.

ad analizzare il segnale e che sono ricavate dalla mother wavelet secondo la (2.4).

Una scelta molto adottata ` e di porre a = 2 ^−j e b = 2 ^−j k, con j e k interi, in modo che, sostituendo nella (2.4), le wavelet che si ottengono sono della forma:

ψ(x) = 2 ^j/2 ψ(2 ^j x − k) (2.17)

Con questa particolare scelta, che permette di rappresentare il segnale senza ri- dondanza e anche di coprire lo spazio delle frequenze con completezza, cambiare j di una unit` a corrisponde a cambiare la scala a di un fattore 2, mentre cam- biare k di una unit` a corrisponde a cambiare lo shift b di una quantit` a pari ad 1/2 <sup>j</sup> . In pratica il segnale analizzato verr` a scansionato da wavelet successive, la cui es- tensione cambia secondo un fattore 1/2 ^j e che vengono traslate a passi di 1/2 ^j (al variare di k). In questo caso le wavelet vengono dette diadiche ⁸ a causa dell’uso del 2 alla base della scelta di a e b. Nel gergo comune si dice che il valore di j determina il livello di scaling indagato che ` e rappresentato in Figura 2.7.

Un esempio di suddivisione diadica semplice da illustrare ` e dato in Figura 2.8 che mostra il caso della wavelet di Haar.

8

si dice anche che l’analisi ` e fatta per “ottave”, in riferimento al fatto che un’ottava superiore

(inferiore) corrisponde al raddoppio (dimezzamento) della frequenza

Figura 2.8: Stadi successivi per le wavelet di Haar. In colonna (i) lo spazio del segnale viene coperto alle diverse scale (livelli) della wavelet. Nelle colonne (ii) ed (iii) ` e mostrato lo schema di suddivisione diadica con cui sono realizzati i tre livelli: ad ogni salto di scala l’estensione della wavelet raddoppia, dimezzando il numero di coefficienti da calcolare per realizzare la convoluzione.

Dalla propriet` a delle wavelet di avere media nulla si intuisce facilmente come la convoluzione con un segnale costante darebbe invariabilmente zero a tutte le scale e su tutti i punti. Lo stesso risutato si avrebbe se le eventuali variazioni del segnale indagato fossero presenti solo a scale maggiori (quindi a frequenze pi` u basse) della wavelet piu ampia usata ! Nasce quindi l’esigenza di completare l’analisi compensando la mancanza di informazione alle frequenze al disotto di quella pi` u bassa indagata. A questo scopo viene introdotta la father wavelet che, rappresentata dalla φ(x), svolge il ruolo di un filtro passa-basso e soddisfa alle seguenti propriet` a:

Z

kφ(x)k ² dx = 1 normalizzazione Z

φ(x)dx = 1 area unitaria

Z

φ(x)φ(x − n)dx = δ(n) ortogonalit` a

dove n rappresenta un dato livello di scaling. L’ultima relazione dice che due filtri

passa-basso corrispondenti a due diversi livelli di scaling (e quindi di risoluzione)

non sono sovrapposti (il loro prodotto ` e nullo). In pratica, dopo aver esplorato

lo spazio delle frequenze con le daughter wavelets fino alla frequenza pi` u bassa,

rimarr` a sempre inesplorata un’ultima porzione di frequenze ancora pi` u basse, fino

alla frequenza zero. Lo scopo della father wavelet ` e proprio quello di salvaguardare

questa informazione attraverso il fatto che il suo spettro di frequenza ` e proprio

di tipo passa-basso e quindi in grado di codificare le approssimazioni a pi` u bassa frequenza del segnale.

Multirisoluzione

Supponiamo di aver scelto una campionamento diadico per analizzare il nos- tro segnale e di procedere al calcolo dei coefficienti, di scaling(low-pass) e di wavelet(band-pass), corrispondenti alle traslazioni necessarie a coprire tutta l’esten- sione del segnale. Il segnale potr` a quindi essere rappresentato in termini dei coefficieni ottenuti come:

f (x) = X

c _{J k} φ _{J k} +

J

X

j=1

X

k

d _jk ψ _jk (x) (2.18)

Nella precedente j rappresenta il livello dell’analisi, J l’ultimo livello analizzato, k tutte le traslazioni necessarie a coprire il segnale per ogni livello j della wavelet.

Quindi: c J k sono i coefficienti di scaling (ricavati dalla father wavelet) corrispon- denti all’ultima scala J indagata, e d _jk sono i coefficienti di wavelet (daughter wavelets) ottenuti alle varie scale j per tutte le traslazioni k. Come si vede il pri- mo termine a destra dell’equazione contiene una somma sulle traslazioni k riferita alla sola ultima scala (J ) indagata: questo corrisponde ad una approssimazione del segnale alla pi` u bassa risoluzione. Il secondo termine invece contiene infor- mazione sui dettagli a partire da quelli a pi` u alta frequenza, estratti dal segnale originale, fino a quelli a frequenze via via minori risultanti man mano che si pro- cede verso all’ultimo livello di risoluzione J .

Questo modo di procedere ` e rappresentato schematicamente nella Figura 2.9 e prende il nome di “multirisoluzione”. Si tratta di applicare iterativamente i filtri passa-basso (in figura: h ₀ ) e passa-banda (h ₁ ) al segnale originale (livello 0) e, successivamente, in cascata alle parti dello spettro di bassa frequenza risultanti dall’applicazione dei filtri al livello precedente.

Si noti che nella figura, per ogni livello di indagine, la linea a tratto continuo in- dica le regioni dello spettro di frequenze che sono interessate dal calcolo, mentre la linea tratteggiata mostra le regioni gi` a indagate ai livelli precedenti.

Adottando uno scaling diadico, l’ampiezza delle regioni di frequenza indagate si

dimezza ogni volta che il processo passa al livello successivo perch` e la scala di

wavelet si raddoppia ad ogni passaggio di livello (vedi anche Fig. 2.8). Si noti

che l’uso di uno scaling diadico ha una giustificazione nel teorema del campiona-

Figura 2.9: Il segnale X viene filtrato al primo livello 0 con un filtro passa-alto (h

, wavelet) ed uno passa-basso (h

, scaling). Lo spettro di frequenza corrispondente ` e mostrato in basso con linea continua. L’analisi prosegue al livello 1 con il segnale di bassa frequenza, risultante dal livello 0, filtrato dai nuovi h

ed h

che lo suddividono in due ulteriori componenti a bassa ed alta frequenza del livello 1. Iterando il processo si pu` o quindi indagare fino ad un livello finale J scelto per terminare l’analisi.

mento ⁹ , gi` a incontrato nella sezione 1.4.1 che, in breve, stabilisce che una data frequenza potr` a essere rivelata solo se il campionamento del segnale avviene ad una frequenza almeno doppia. Diventa quindi naturale che il livello 0 della analisi debba partire da una ampiezza di wavelet di almeno 2 campionamenti: p.es. se un segnale ` e campionato ogni secondo, il dettaglio pi` u fine che possiamo estrarre saranno fluttuazioni con periodo di almeno 2 secondi e quindi di frequenza minore o uguale a 1/2 s ⁻¹ .

Supponiamo allora di analizzare il nostro segnale con una wavelet di Haar che meglio si presta ad esemplificare. Per estrarre la frequenza pi` u alta sar` a necessario usare al livello 0 una wavelet che si estende su 2 campionamenti adiacenti e viene shiftata (convoluta) col segnale a salti di 2 campionamenti. Questa operazione produrr` a quindi un numero di coefficienti pari ai passi necessari per esplorare tutto il segnale con la wavelet di ampiezza data.

La Figura 2.8 aiuta a visualizzare questi passaggi: un segnale formato da N cam- pioni al livello 0 sara’ coperto da una successione di N/2 wavelets, ognuna che si estende su due punti, ottenendo quindi N/2 coefficienti. Passando al livello successivo la wavelet raddoppia la scala (diadica) e si estende ora su 4 punti

9

detto di Nyquist o di Shannon a seconda che ci si riferisca al dominio del segnale o a quello

delle frequenze

cosicch` e il segnale sar` a coperto da un numero di passi pari ad 1/4 dei punti del segnale. Iterando la procedura, ad ogni livello rimarr` a comunque una parte dello spettro alle basse frequenze non indagata che viene per` o recuperata dalla “scaling function” (anche detta “father wavelet”) che ha proprio lo scopo di raccogliere l’informazione a tutte le frequenze minori dell’ultima frequenza analizzata con le wavelet usate. Per questo lo spettro in frequenza di una father wavelet cor- risponde ad un filtro passa-basso (come si vede in Fig. 2.9).

Adottando la wavelet di Haar per esemplificare i vari livelli dell’analisi abbiamo lo schema seguente che ha il suo riferimento nelle Figure 2.8 e 2.9:

liv.0 cominciamo con la scala pi` u piccola che corrisponde alla frequenza pi` u al- ta. Per il teorema del campionamento la scala pi` u piccola deve coinvolgere almeno 2 punti ed i coefficienti di approssimazione e dettaglio saranno cal- colati da father and doughter wavelet traslate con una successione di 2 punti fino a coprire il segnale. Si otterranno quindi N/2 coefficienti sia per l’approssimazione (father, basse frequenze);

liv.1 la scala si raddoppia e la wavelet si estende ora su 4 punti, dimezzando l’intervallo di frequenze indagato. Con wavelet su 4 punti saranno neces- sarie N/4 traslazioni per coprire tutto il segnale cosicch` e si otterranno N/4 coefficienti sia per l’approssimazione che per il dettaglio;

liv.2 iterando il processo ad ogni ulteriore passo si dimezzano i coefficienti nec- essari a codificare le nuove frequenze (sempre pi` u basse) indagate.

Questo ` e l’essenza dell’approccio detto a multirisoluzione che comunque vale per qualsiasi altra forma di wavelet.

Il caso delle immagini

Un procedimento come quello appena descritto, sviluppato per un segnale ad

una dimensione, ` e estensibile alle immagini e permette quindi di separare l’infor-

mazione in frequenza alle varie scale spaziali. Per questo intoduciamo funzioni

di wavelet ψ _a (x, y) che ora dipendono da due variabili. Con queste si possono

estrarre versioni filtrate alle varie frequenze attraverso la convoluzione dell’im-

magine di partenza, sempre usando le propriet` a di scaling e traslazione delle

wavelets, e quindi estendendo il concetto del “filter bank” al caso delle 2 dimen-

sioni.

Per gli stessi motivi visti nel caso 1D, ` e conveniente usare una suddivisione diad- ica delle scale di wavelet cos`ı da dimezzare il numero di coefficienti che, ad ogni cambio di scala, vengono calcolati per ognuna delle 2 dimensioni. La wavelet di Haar ` e rappresentata nei due casi 1D e 2D in Figura 2.10, dove notiamo facil- mente che il prodotto tra mother e father wavelets rimane sempre nullo, rendendo questa wavelet adatta a costituire una base ortonormale anche nel caso 2D.

Figura 2.10: La wavelet di Haar nella sua forma 1D (a sinistra) e 2D (a destra). Le funzioni φ e ψ indicano father e mother wavelets Le altezze delle varie funzioni sono scalate in modo da rispettare le prescrizioni su media (=0) e norma (=1).

Infatti, se applichiamo la convoluzione diadica ad un’immagine con dimensioni

NxN otterremo N ² /4 coefficienti in corrispondenza degli N/2 passi di 2 pixel nec-

essari per indagare lungo un’intera riga e degli altri N/2 passi di 2 pixel necessari

per passare da una coppia di righe alla successiva. Un meccanismo di questo tipo

produrr` a un numero di valori pari ad 1/4 dei pixel di partenza ogni volta che

procediamo al livello successivo nell’analisi di una immagine. Una volta ottenuti

gli N ² /4 valori filtrati alle varie frequenze indagate dalle wavelet al livello 0, ` e

naturale rappresentarli in forma di una nuova immagine costituita dallo stesso

numero di pixel, ma questa volta suddivisa in 4 quadranti, ognuno dei quali cor-

rispondente ad una delle wavelet con cui ` e stata filtrata l’immagine.

Un modo per illustrare questo approccio ` e di usare una immagine standard, nota come immagine di Lena e mostrata in Figura 2.11, per rappresentare visivamente come avviene la suddivisione delle frequenze.

Figura 2.11: Immagine di Lena, un’immagine di test largamente usata come riferimento per illustrare e confrontare gli effetti delle diverse tecniche di analisi sviluppate.

Questo procedimento porta quindi a separare le varie frequenze che compongono un’immagine utilizzando una rappresentazione che riorganizza l’informazione sud- dividendola in una serie di sottoimmagini costruite attraverso una sequenza or- dinata di passi.

Cominciando l’analisi dalle frequenze pi` u alte e assumendo per semplicit` a che l’immagine sia quadrata (N pixel x N pixel) fissiamo a 2 x 2 le dimensioni del- la wavelet che analizza le frequenze pi` u alte nell’immagine. Tenendo conto che adottiamo le wavelets di Haar (Figura 2.10) verranno calcolate separatamente le frequenze lungo le righe, le colonne, e lungo la diagonale della Figura 2.11.

Si otterranno quindi sia i coefficienti a bassa frequenza (anche detti “approssi-

mazione”) dell’immagine, sia quelli ad alta frequenza (detti “dettagli”) lungo

righe, colonne, diagonale. Notiamo che la scelta di usare wavelet di dimensione

2x2 pixel, alla fine della procedura ci far` a calcolare per ogni wavelet N/2 x N/2

valori su tutta l’immagine in modo tale che, per ogni wavelet, basteranno 1/4

dei pixel originali per rappresentare i coefficienti. In questo modo vengono gen-

erate tutte le sottoimmagini che in Figura 2.12 vengono indicate con due lettere

il cui significato ` e riferito a righe e colonne indicando che: LL sono rappresen-

tati i coefficienti alle basse frequenze calcolati dalla φ (father wavelet), LH ed

HL mostrano le alte frequenze emergenti dalla scansione rispettivamente lun-

go le colonne e lungo le righe, HH infine sono le componenti ad alta frequenza

estratte dall’ultima wavelet 2D in Figura 2.10. La Figura 2.12 mostra come le

Figura 2.12: Decomposizione a diversi livelli di risoluzione di un’immagine. Il primo passo ` e illustrato in alto a sinistra con la coppia di lettere LL (Low-Low) per indicare che sia le righe che le colonne contengono l’informazione a bassa frequenza al livello 0. Si noti che, per effetto dello scaling diadico, il numero di punti in cui la componente di bassa frequenza ` e stata valutata

` e dimezzato sia in X che in Y e quindi per rappresentare la bassa frequenza baster` a usare 1/4 dell’area dell’immagine di partenza. Lo stesso vale per le altre 3 parti che rappresentano i coefficienti delle alte frequenza ottenuti analizzando le sole righe (HL), le sole colonne (LH), sia righe che colonne (HH). Lo schema di suddivisione ` e poi replicato sul livello 1 (in alto a destra) e 2 (in basso a destra). L’ultimo riquadro in basso a sinistra mostra il risultato finale sull’immagine 2.11.

varie componenti dell’immagine si possono organizzare a formare un’immagine di uguale dimensione ma che mostra ben separate le varie componenti in frequenza.

E intuitivo che una volta ottenuta questa scomposizione si potr` ` a lavorare su una

specifica componente alla ricerca di particolari dettagli interessanti ai fini della

specifica tematica affrontata.