Trasformata wavelet discreta (DWT)

| ˆψ(ζ)|2 |ζ| ^{dζ (4.40)}

si chiama costante di ammissibilit`a e ˆψ `e la trasformata di Fourier di ψ. Per ottenere con successo la trasformata inversa, la costante di ammissibilit`a deve soddisfare la condizione:

0 < C_ψ < +∞

Si pu`o anche mostrare che ˆψ(0) = 0, cio`e che tale wavelet si pu`o integrare in 0. La funzione ψ serve come prototipo per le wavelets figlie, che infatti sono delle copie traslate e scalate della mother wavelet:

ψs,τ(t) = ¹ p|s|^ψ(

t − τ

s ^{) (4.41)}

Alcune applicazioni della CWT

• Determinazione della dimensione frattale:

Guardando agli estremi della CWT, in base alle traslazioni, si pu`o quantificare la dimensione frattale di una funzione.

• Analisi tempo-frequenza:

Guardando agli estremi della CWT, in base al fattore di scala, si pu`o decomporre un segnale in termini sia temporali sia di frequenza si-multaneamente. Tale analisi tempo-frequenza basata sulla CWT ha alcuni vantaggi rispetto ad altri metodi di analisi tempo-frequenza. Inoltre ha molte applicazioni in materie quali la fisica, la chimica, la biologia, l’ingegneria e la finanza.

4.4.4 Trasformata wavelet discreta (DWT)

La trasformata wavelet discreta (DWT) `e una trasformata wavelet in cui le wavelets sono campionate e discretizzate. La prima DWT fu inventata dal matematico ungherese Alfred Haar. Per una sequenza d’ingresso di 2<sup>n</sup> numeri, la trasformata wavelet di Haar pu`o essere considerata un campiona-mento dei valori d’ingresso, il quale memorizza la differenza e itera la somma. Questo processo viene ripetuto ricorsivamente, accoppiando le somme per ottenere la prossima scala. Infine si ottengono 2ⁿ−1 differenze e una somma. Questa semplice DWT illustra le propriet`a che si desiderano dalle wavelets in generale. Per prima cosa, pu`o essere calcolata in un numero di operazioni pari a O(n); inoltre, non analizza soltanto le informazioni in frequenza del-l’ingresso esaminandole a diverse scale, ma anche le informazioni temporali, ad esempio quante volte si presentano le informazioni in frequenza. Queste propriet`a combinate stanno alla base della Fast Wavelet Transform (FWT),

un alternativa alla classica Fast Fourier Transform. L’insieme di DWT pi`u utilizzato fu formulato dalla matematica belga Ingrid Daubechies nel 1988. Questa formulazione si basa sull’uso delle relazioni di ricorrenza per gener-are progressivamente campioni discreti dettagliati di una funzione mother wavelet implicita, in cui ogni risoluzione `e il doppio della scala precedente. Nel suo trattato, Daubechies ricav`o una famiglia di wavelets, la prima delle quali fu la wavelet di Haar. L’interesse in questo campo esplose da allora, e furono sviluppate molte alternative alle wavelets originarie di Daubechies. Definizione

La DWT di un segnale viene calcolata facendolo passare attraverso una serie di filtri. Per prima cosa, i campioni x(n) vengono passati ad un filtro passa-basso con risposta impulsiva g(n), per cui ottengo come risultato la convoluzione: y(n) = (x ∗ g)(n) = +∞ X k=−∞ x(k)g(n − k)

Il segnale viene simultaneamente decomposto utilizzando un filtro passa-alto con risposta impulsiva h(n). Le uscite danno rispettivamente i coefficienti di dettaglio (dal filtro passa-alto) e i coefficienti di approssimazione (dal filtro passa-basso). `E importante che i due filtri siano connessi uno all’altro, e tali filtri prendono il nome di filtri quadrature mirror. Tuttavia, siccome met`a delle frequenze del segnale sono state rimosse, met`a dei campioni pu`o essere scartata. Le uscite dei filtri poi vengono sottocampionate di un fattore 2:

y_low(n) = +∞ X k=−∞ x(k)g(2n − k) (4.42) y_high(n) = +∞ X k=−∞ x(k)h(2n − k) (4.43)

Questa decomposizione ha dimezzato la risoluzione temporale dato che solo met`a delle uscite dei filtri caratterizzano il segnale d’ingresso. Per`o, ogni uscita viene rappresentata solo su met`a della banda di frequenza del segnale d’ingresso, per cui la risoluzione in frequenza viene raddoppiata. Definendo

l’operatore di sottocampionamento ↓:

(y ↓ k)(n) = y(kn) (4.44) Si possono scrivere in tale maniera le relazioni (5.42) e (5.43):

ylow = (x ∗ g) ↓ 2 (4.45) y_high = (x ∗ h) ↓ 2 (4.46) Tuttavia, calcolare la convoluzione x ∗ g con un sottocampionamento suc-cessivo sprecherebbe molto tempo. Esistono a tal proposito delle ottimiz-zazioni, ad esempio il Lifting Scheme [13], dove tali calcoli vengono eseguiti contemporaneamente.

Banchi di filtri in cascata

Questa decomposizione viene ripetuta per incrementare la risoluzione in fre-quenza e i coefficienti di approssimazione decomposti con filtri passa-alto e passa-basso e quindi sottocampionati. Questo procedimento si rappresenta con un albero binario che rappresenta un sottospazio con una localizzazione tempo-frequenza diversa. Tale albero si chiama banco di filtri [12]. Ad esem-pio si consideri un banco di filtri a 3 livelli: Ad ogni livello il segnale viene

Figura 4.5: Un banco di filtri a 3 livelli

decomposto in basse e alte frequenze. Il segnale d’ingresso deve avere un numero di campioni multiplo di 2ⁿdove n `e il numero di livelli. Ad esempio, con un segnale con 32 campioni, intervallo di frequenza [0, fn] e 3 livelli di decomposizione, vengono prodotte 4 uscite:

Livelli Frequenze Campioni

3 [0,^fn 8 ] 4 3 [^fn 8,^fn 4 ] 4 2 [^fn 4,^fn 2 ] 8 1 [^fn 2 , f_n] 16

Figura 4.6: Rappresentazione nel dominio della frequenza della DWT

Un esempio in codice Java

Viene qui riportato un esempio in codice Java della DWT utilizzando la wavelet di Haar:

public static int[ ] invoke(int[ ] input){

//Si assume che la lunghezza input.length sia una potenza di 2

int[ ] output = new int[input.length];

for(int length = input.length >> 1; ; length >>= 1){ //length=2ⁿ, con n decrescente

for(int i = 0; i < length; i + +) { int sum = input[i*2]+input[i*2+1]; int difference = input[i*2]-input[i*2+1]; output[i] = sum;

output[length+i] = difference; }

if (length == 1) return output;

//Scambia gli array per eseguire la prossima iterazione System.arraycopy(output, 0, input, 0, length<<1); }

}

Alcune applicazioni della DWT

La DWT ha un vasto numero di applicazioni nella scienza, nell’ingegneria e nella matematica. `E anche utilizzata nella codifica dei segnali, per rap-presentare un segnale discreto in una forma pi`u ridondante, spesso come precondizione per la compressione dei dati. Ovviamente tali applicazioni sono strettamente legate alla disponibilit`a di algoritmi efficienti che imple-mentino fedelmente la DWT. Tali algoritmi prendono il nome di FWT (Fast Wavelet Transform).