Tesi di laurea magistrale
Metodi numerici per il restauro di video clips
Candidato:
Paolo Burdo
Relatore:
Introduzione
Modelli per il restauro di immagini digitali sono stati ampiamente analizzati in letteratura. Diversi gruppi di ricerca hanno condotto studi approfonditi in questo campo e sono tuttora attivi. Generalmente l'interesse è rivolto al restauro di una singola immagine, problema per il quale esiste una letteratura molto ampia.
Recentemente è stato rivolto interesse speci co al restauro di video clips. In particolare, uno dei problemi considerato dal gruppo di Hong Kong coordinato da Raymond Chan riguarda la elaborazione di video clips a bassa risoluzione per ricavare immagini più dettagliate e in alta risoluzione di particolari parti di scena.
In questa tesi siamo partiti dal recente lavoro di Raymond Chan [1], in cui un modello di restauro di video clips viene introdotto e analizzato dal punto di vista modellistico e algoritmico, per fare una analisi dettagliata delle problematiche teoriche e computazionali che intervengono in questo campo.
Il modello matematico e gli approcci algoritmici sono molto articolati, coin-volgono strumenti di varia natura, e presentano aspetti numerici di particolare interesse e di coltà.
Informalmente il modello è organizzato nel modo seguente. Fissato il frame da ricostruire in super-risoluzione (frame di riferimento), si seleziona un insieme di frame a bassa risoluzione che compongono il video in modo che tutti i frame considerati contengano la stessa sezione dell'immagine del frame di riferimento. Si applica quindi un algoritmo di usso ottico per determinare gli spostamenti e i cambiamenti di luminosità tra il frame di riferimento e i restanti frame, così da allineare le sezioni comuni tra i frame e poter poi applicare un modello di rango basso.
L'idea del modello di rango basso è la seguente:
tutti i frame a bassa risoluzione che sono stati riallineati con la procedura di usso ottico, vengono visti come delle immagini in alta risoluzione che sono state sfocate. Idealmente queste immagini da ricostruire devono essere tutte uguali, quindi riorganizzando queste immagini in vettori ne segue che la ma-trice che ha questi vettori per colonne deve avere rango 1. Il rumore e gli errori causati dall'algoritmo di usso ottico e il rumore delle immagini creano perturbazioni che possono aumentare il rango di questa matrice.
La tesi tratta le metodologie numeriche per calcolare da una parte il usso ottico e dall'altra per minimizzare il funzionale associato al modello.
Il lavoro è organizzato come segue.
Nel capitolo 1 vengono presentate le de nizioni e le notazioni di base degli oggetti matematici usati, lo standard di codi ca delle immagini, il modello di sfocatura basato sul concetto di point spread function (PSF). Si riassumono poi gli elementi di base della teoria dei segnali che mettono in relazione le PSF e i ltri digitali e che saranno utili nelle parti successive della tesi.
Nei capitoli successivi si entra nel merito delle metodologie algoritmiche. In particolare nel capitolo 2 viene presentato l'algoritmo di usso ottico Local All-Pass (LAP), introdotto in [5], che viene utilizzato nel modello di norma nucleare per determinare lo spostamento e i cambi di luminosità.
Nel capitolo 3 viene presentato il metodo delle direzioni alternate dei mol-tiplicatori, introdotto in [6], che verrà poi utilizzato per ottenere le approssi-mazioni di rango basso che minimizzano un opportuno funzionale.
In ne nel capitolo 4 viene presentato il modello nucleare per il restauro di video clips.
Indice
Introduzione 3
1 Notazioni e De nizioni preliminari 7
1.1 Codi ca di immagini . . . 11
1.2 La Point-Spread-Function . . . 11
1.3 Matrici associate alla sfocatura . . . 14
1.4 Matrici circolanti e FFT . . . 18
1.5 Prodotto matrice di Toeplitz-vettore . . . 21
1.6 Prodotto per matrici a blocchi . . . 23
1.7 Richiami di teoria dei segnali . . . 23
1.7.1 Segnali . . . 23
1.7.2 Segnali periodici a tempo continuo . . . 24
1.7.3 Segnali aperiodici a tempo continuo . . . 26
1.7.4 Segnali a tempo discreto . . . 28
1.7.5 Sistemi monodimensionali . . . 29
1.7.6 Generalità sui ltri e ltri ideali . . . 31
1.7.7 Caratterizzazione e proprietà dei sistemi monodimensio-nali a tempo discreto . . . 34
1.7.8 Sistemi lineari e stazionari a tempo discreto . . . 34
1.7.9 Risposta in frequenza di un SLS . . . 35
1.7.10 Filtri a tempo discreto . . . 35
1.7.11 Cambiamento della frequenza di campionamento . . . . 36
1.7.12 Cenni alla trasformata Z di una sequenza . . . 36
1.7.13 Sistemi a tempo discreto regolati da equazioni alle die-renze . . . 38
1.7.14 La funzione di trasferimento . . . 39
1.7.15 Sistemi a risposta impulsiva nita e in nita . . . 40
1.8 Osservazioni su PSF e ltri . . . 41
1.9 De nizioni per il modello nucleare . . . 42
2 Algoritmo Local All-Pass (LAP) per la stima del Flusso Ottico 43 2.1 Introduzione . . . 43
2.2.1 Lo spostamento è un ltraggio all-pass . . . 45
2.2.2 Approssimazione di un ltro all-pass Una rappresenta-zione di base . . . 45
2.2.3 Ricerca di una base di ltri migliore . . . 46
2.2.4 Estrazione del vettore spostamento . . . 47
2.2.5 Esempio . . . 47
2.3 Algoritmo Local All-Pass . . . 47
3 Metodo delle direzioni alternate dei moltiplicatori 49 3.1 Precursori . . . 49
3.1.1 Ascesa duale . . . 49
3.1.2 Decomposizione duale . . . 51
3.1.3 Lagrangiana aumentata e metodo dei moltiplicatori . . . 51
3.2 Metodo delle direzioni alternate dei moltiplicatori . . . 52
3.3 Convergenza . . . 54
3.3.1 Convergenza teorica . . . 55
3.3.2 Convergenza nella pratica . . . 59
3.4 Condizioni di ottimalità . . . 59
3.5 Criteri di arresto . . . 60
3.6 Estensioni e varianti . . . 61
3.6.1 Parametro di penalizzazione variabile . . . 61
3.6.2 Termini aumentati più generali . . . 62
3.6.3 Sovra-rilassamento . . . 62
3.6.4 Minimizzazione inesatta . . . 62
3.6.5 Ordini di aggiornamento . . . 62
4 Modello nuleare 63 4.1 Modello di bassa risoluzione con spostamenti . . . 63
4.2 Il Modello Nucleare . . . 65
4.2.1 Scomposizione della matrice di deformazione. . . 65
4.2.2 Algoritmo per risolvere il modello nucleare . . . 67 4.2.3 Registrazione dell'immagine e selezione del parametro . 68
Notazioni e De nizioni
preliminari
Introduciamo delle notazioni e de nizioni che ci serviranno in tutta la pre-sentazione. Questo capitolo è principalmente basato su [4], tranne che per la sezione 1.7 per cui si rimanda a [10] e la sezione 1.9 per cui vedere [1].
De nizione 1.1. Si de nisce matrice di Toeplitz una matrice n × n con dia-gonali costanti, ossia se A = {ai,j}è matrice n × n allora ai,j = ai−1,j−1,
∀ i, j = 2, . . . , n.
Esempio 1.2. Ad esempio, è matrice di Toeplitz una matrice della forma: a b c d e a b c f e a b g f e a
Osservazione 1.3. Siano ci ∈ R per i = −n + 1, . . . , n − 1, allora la matrice
A di dimensione n × n di elementi ai,j = cj−i è di Toeplitz.
De nizione 1.4. Una matrice di Toeplitz n × n si dice circolante se per ogni riga i suoi elementi sono permutati ciclicamente di un posto verso destra rispetto alla riga precedente.
Esempio 1.5. Un esempio di matrice di Toeplitz circolante è: a b c d d a b c c d a b b c d a
Osservazione 1.6. Siano ci ∈ R per i = 0, . . . , n − 1, allora la matrice A di
dimensione n × n di elementi ai,j = cj−i mod n è circolante.
Proposizione 1.7. Sia C la matrice circolante la cui prima riga è data dal vettore reale [c0, . . . , cn−1], sia ωn= exp(2πin )e W = √1n{ωnij}i,j=0,n−1. Allora
valgono le seguenti proprietà:
1. la matrice W è unitaria, cioè W∗W = I, inoltre W∗CW =diag(d 0, . . . , dn−1), dove dj = n−1 X k=0 ckwjn−k per j= 0, ..., n − 1
sono gli autovalori di C e diag(d0, . . . , dn−1)denota la matrice diagonale
con elementi diagonali di;
2. Come conseguenza immediata della formula per gli autovalori data nel punto precedente, il determinante della matrice circolante è calcolato co-me det(C) = n−1 Y j=0 λj = n−1 Y j=0 n−1 X k=0 ckwn−kj
e siccome prendere la trasposta non cambia gli autovalori di una matrice otteniamo det(C) = n−1 Y j=0 n−1 X k=0 ckwjk= n−1 Y j=0 f(wj).
3. Il rango di C è n − d dove d è il grado di gcd(f(x), xn− 1).
4. Posto P matrice di permutazione ciclica
P = 0 · · · 1 1 ... ... ... ... ... ... ... 0 · · · 1 0
allora una matrice circolante può essere scritta come un polinomio C =
n−1
X
i=0
Introduciamo adesso una operazione tra matrici che risulta particolarmente utile per trattare problemi bidimensionali in modo adeguato.
De nizione 1.8. Sia A ∈ Rm×n matrice m × n e B ∈ Rp×q matrice p × q,
allora il loro prodotto di Kronecker A ⊗ B è una matrice mp × nq de nita a blocchi nel modo seguente:
A ⊗ B= a1,1B · · · a1,nB ... ... ... am,1B · · · am,nB
dove A = {ai,j}m,ni=1,j=1 e il prodotto tra ogni ai,j e B è il prodotto costante per
matrice.
Il prodotto di Kronecker gode di alcune interessanti proprietà. La seguente proposizione ne descrive alcune di particolare rilievo.
Proposizione 1.9. Siano A, B, C e D tre matrici allora valgono:
1. A ⊗ (B + C) = A ⊗ B + A ⊗ C, supponendo che B e C abbiano le stesse dimensioni in modo che abbia senso la somma.
2. (A + B) ⊗ C = A ⊗ C + B ⊗ C, supponendo che A e B abbiano le stesse dimensioni in modo che abbia senso la somma.
3. Sia k ∈ R, allora (kA) ⊗ B = A ⊗ (kB) = k(A ⊗ B). 4. (A ⊗ B) ⊗ C = A ⊗ (B ⊗ C).
5. Questo prodotto non è commutativo, ma A ⊗ B e B ⊗ A sono equivalenti per permutazioni, cioè esistono delle matrici di permutazione P e Q tali che A ⊗ B = P (B ⊗ A)Q. Se A e B sono quadrate allora A ⊗ B e B ⊗ A sono simili per permutazioni, ossia P = QT.
6. (A ⊗ B) · (C ⊗ D) = (A · C) ⊗ (B · D), supponendo si possa eseguire il prodotto matriciale tra le matrici A e C e tra B e D.
7. Immediata conseguenza è che A ⊗ B è invertibile se e solo se lo sono A e B e l'inversa è (A ⊗ B)−1 = A−1⊗ B−1.
8. Siano A e B quadrate di ordine n e q rispettivamente e siano λ1, ..., λn
gli autovalori di A, µ1, ..., µq quelli di B. Allora gli autovalori di A ⊗ B
sono λiµj, per i = 1, ..., n e j = 1, ..., q. Come conseguenza si ha che
la traccia è tr(A ⊗ B) = tr(A)tr(B) e il determinante è det(A ⊗ B) = (det(A))q(det(B))n.
Introduciamo adesso un operatore che risulta particolarmente utile usato in combinazione con il prodotto di Kronecker.
De nizione 1.10. L'applicazione vec : Rm×n −→ Rmn è un operatore che
permette la "vettorizzazione" di una matrice, cioè se A = {ai,j}m,ni=1,j=1∈ Rm×n
è una matrice m × n, allora si indica con vec(A) il vettore mn × 1 tale che vec(A) = [a1,1, ..., am,1, a1,2, ..., am,2, ..., a1,n, ..., am,n]T.
Proposizione 1.11. Consideriamo tre matrici A, B e C allora valgono: 1. L'operatore vec può essere usato insieme al prodotto di Kronecker per
esprimere il prodotto tra matrici come trasformazione lineare, cioè: vec(ABC) = (CT ⊗ A)vec(B)
dove ad esempio A ∈ Rm×n, B ∈ Rn×p e C ∈ Rp×q.
2. Altre due formulazioni che possono essere utili sono:
vec(ABC) = (Iq⊗ AB)vec(C) = (CTBT ⊗ Im)vec(A),
vec(AB) = (Ip⊗ A)vec(B) = (BT ⊗ Im)vec(A).
Introduciamo ora una norma matriciale che verrà utilizzata in seguito nel modello matematico.
Teorema 1.12. Sia A ∈ Rm×n e supponiamo senza perdita di generalità che
m ≥ n(infatti il caso opposto può essere trattato allo stesso modo usando AT) allora esistono due matrici unitarie U ∈ Rm×m e V ∈ Rn×n tali che
UTAV = ˜ Σ 0 = Σ, dove ˜Σ = diag(σ1, ..., σn) e σ1 ≥ σ2 ≥ ... ≥ σn≥ 0.
De nizione 1.13. Considerata la matrice A di dimensioni m × n si de nisce decomposizione ai valori singolari (SVD) di A la fattorizzazione A = UΣVT,
dove U e V sono matrici unitarie di dimensioni m × m e n × n rispettivamente, mentre Σ è una matrice m × n diagonale; i valori sulla diagonale di Σ sono detti valori singolari.
Osservazione 1.14. Si noti che non ci sono ipotesi sulla matrice A del Teo-rema 1.12, quindi la SVD esiste per ogni matrice.
Proposizione 1.15. La somma dei valori singolari della matrice A de nisce una norma matriciale.
De nizione 1.16. Si de nisce norma nucleare di una matrice A di dimensioni m × n e si denota con kAk∗ la quantità
kAk∗=
min{m,n}
X
i=1
σi,
1.1 Codi ca di immagini
La tecnica raw consiste in un particolare metodo di memorizzazione dei dati che descrivono un'immagine. Viene usata per non avere perdite di qualità nella registrazione su un qualsiasi supporto di memoria, rispetto ai segnali cat-turati dal sensore e successivamente composti per interpolazione dal processore d'immagine della fotocamera.
Una foto digitale in bianco/nero, nel formato raw, consisterà di una matrice m × ndi numeri interi A = {ai,j}in cui ai,j rappresenta la luminosità
dell'im-magine nel punto di posizione (i, j). Questi punti dell'imdell'im-magine sono detti pixel, termine ottenuto dalla contrazione dei termini picture-element, ossia ele-mento dell'immagine. In genere se si usa una convenzione discreta i valori di ai,j sono interi, con il valore 0 si rappresenta il nero e con il valore massimo
consentito si rappresenta il bianco, generalmente si usa 255. Se si assume una convenzione nella quale i valori possono essere reali si ha ancora 0 per il nero, mentre il bianco corrisponde al valore 1. Nella modalità raw ogni pixel, di una immagine in bianco e nero, è memorizzato in un singolo byte, quindi le dimensioni del le sono uguali al numero di pixel dell'immagine catturata .
Una foto a colori, nella sua rappresentazione RGB viene registrata come una matrice A di dimensioni m × n × 3 dove le tre matrici A(:, :, 1), A(:, :, 2) e A(:, :, 3)di dimensione m × n ognuna, esprimono l'intensità di luminosità del rosso (Red), verde (Green) e blu (Blue), rispettivamente, da cui si può capire il perché del nome RGB. Infatti un punto in posizione (i, j) di una immagine digitale a colori è visto come la somma di una componente di rosso, una di verde e una di blu. Inoltre unendo questi tre colori alla massima intensità si ottiene il colore bianco. Anche in questo caso il valore 0 corrisponde a una intensità nulla del colore, mentre il valore massimo corrisponde all'intensità massima. I valori numerici relativi alla componente rossa di ogni pixel dell'immagine, prende il nome di "Canale del rosso"; così i valori numerici della componente verde di ogni pixel dell'immagine prendono il nome di "Canale del verde" e lo stesso si dice per tutti valori numerici relativi alla componente blu dei pixel che vengono chiamati "Canale del blu".
1.2 La Point-Spread-Function
Supponiamo di avere una immagine formata da un solo punto luminoso di intensità 1, o se usiamo la convenzione discreta 255, come nella Fig.1.1. Con l'obiettivo regolato male si otterrà qualcosa tipo l'immagine in Fig.1.2, dove l'eetto della sfocatura è volutamente esagerato. Questa nuova immagine sarà de nita da dei pixel fi,j, dove per comodità facciamo scorrere gli indici i e j
da −k a k e dove 2k + 1 è l'ampiezza del supporto dell'immagine del puntolino sfocato. Una scena, che vogliamo ad esempio fotografare la possiamo pensare
Figura 1.1: Immagine di un punto luminoso
Figura 1.2: Immagine di un punto luminoso fotografato con l'obiettivo non a fuoco
svolgersi nel piano Z×Z e allora chiameremo supporto dell'immagine l'insieme dei valori degli indici dei pixel dell'immagine che stiamo considerando.
La matrice di numeri fi,j, per i, j = −k, ..., k, descrive quindi il tipo di
sfocatura ed è chiamata in gergo Point-Spread Function, o più semplicemente PSF. Essa descrive il modo in cui il punto luminoso si espande in una mac-chiolina più grande, come in Fig.1.2. I valori fi,j sono non negativi e devono
sommarsi ad 1 poiché la quantità di luminosità presente nell'immagine sfo-cata deve essere uguale a quella presente nell'immagine originale. Allora, se A = {ai,j} per i, j ∈ Z, sono i pixel dell'immagine originale A costituita da
in niti pixel collocati sul piano Z × Z, possiamo identi care una fotogra a di A come una matrice B = {bi,j} che cattura una parte rettangolare di A,
pre-cisamente quella i cui indici sono i = 1, ..., m, j = 1, ..., n, cioè bi,j = ai,j per
i= 1, ..., m, j = 1, ..., n.
Ora supponiamo che tutti i pixel di A siano nulli tranne ap,q= g 6= 0, cioè
l'immagine è costituita da un unico punto luminoso di intensità g posto nella posizione (p, q). Se la foto viene scattata senza mettere a fuoco, l'immagine sfocata bi,j avrà i pixel uguali a
bi,j =
gfi−p,j−q, se |i − p| e |j − q| < k
In questo modello il tipo di sfocatura (di PSF) è invariante spazialmente, cioè non dipende dalla posizione del punto (p, q) ed è de nito dalla stessa matrice di numeri {fi,j}i,j=−k,...,k qualunque sia il punto (p, q).
Il modello fornisce una approssimazione della situazione reale. Infatti, nella realtà il comportamento di un obiettivo fotogra co è diverso a seconda che si consideri il centro o il bordo dell'immagine.
Un'altra considerazione riguarda il supporto delle immagini, infatti per A è Z×Z. In realtà, però, i pixel dell'immagine sfocata sono in uenzati dai pixel ai,j di A con i = −k +1, ..., m+k, j = −k +1, ..., n+k, cioè l'immagine sfocata
nasce non solo dai pixel che hanno indici 1 ≤ p ≤ m, 1 ≤ j ≤ n, ma anche dai pixel che sono fuori da questo supporto e che sono in una cornice di ampiezza k. Infatti, se il pixel luminoso di coordinate (r, s) si trova a distanza al più k (detta semiampiezza del supporto della PSF ) dal supporto [1 : m] × [1 : n], allora l'in uenza della sfocatura di questo punto si ritrova anche dentro il supporto di B.
In questo modello l'immagine sfocata di una generica immagine costituita da più pixel non nulli sarà la somma delle immagini che si ottengono sfocando i singoli pixel. Vale cioè
bi,j =
X
p,q
fi−p,j−qap,q i= 1, ..., m, j = 1, ..., n (1.1)
dove la somma è fatta per p = 1 − k, ..., m + k, q = 1 − k, ..., n + k, su tutti gli indici per cui i − p e j − q sono compresi tra −k e k. Ponendo r = i − p e s= j − q, la (1.1) può essere riscritta come
bi,j = k
X
r,s=−k
fr,sai−r,j−s i= 1, ..., m, j = 1, ..., n. (1.2)
Si riportano alcuni esempi di PSF:
• PSF uniforme: in questo caso la matrice F di dimensioni (2k+1)×(2k+1) ha tutti elementi uguali tra di loro che valgono fi,j =
1
(2k + 1)2. Un
punto viene quindi trasformato in un rettangolo di (2k + 1) × (2k + 1) pixel. Maggiore è k e maggiore sarà l'eetto di sfocatura.
• PSF esponenziale: i valori della PSF sono dati da fi,j = θe−α(i2+j2)
, per i, j = −k, ..., k, dove θ è un parametro di normalizzazione scelto in modo che la somma degli fi,j faccia 1, e α > 0 determina l'ampiezza
dell'eetto di sfocatura. In questo caso il punto centrale della PSF, quello corrispondente agli indici i = j = 0, è quello di luminosità massima,
inoltre la luminosità decade esponenzialmente a zero man mano che ci si allontana dal punto centrale. Il decadimento dipende dalla grandezza di α. Per α = 0 si ottiene la PSF uniforme.
• PSF sinc: i valori della PSF di tipo sinc sono dati da fi,j = θ(σ +
sinc(α(i2 + j2)1/2)) dove la funzione sinc è data da sinc(x) = sin(x)
x . Questo tipo di PSF è quello più vicino alla situazione reale delle macchine fotogra che digitali. Il parametro α determina l'intensità della sfocatura: più piccolo è α e maggiore è la sfocatura. Il parametro σ è scelto in modo da avere valori non negativi della PSF, il valore θ viene scelto in modo che gli elementi della PSF si sommino a 1.
L'applicazione che trasforma una immagine A in una immagine B sfocata può essere vista come un ltro FIR dove la PSF non è altro che la Finite Impulse Response, cioè l'immagine sfocata di una sorgente luminosa puntiforme di valore unitario.
Dal punto di vista computazionale per sfocare una immagine in bianco e nero basta calcolare una doppia sommatoria: data A = {ai,j} e F = {fi,j},
si calcola B = {bi,j} mediante la (1.1) o la (1.2). Per rimettere a fuoco una
immagine basta "risolvere" un sistema lineare di mn equazioni in (m + 2k) × (n + 2k)incognite: data l'immagine sfocata B e la PSF F si calcola l'immagine originale A risolvendo il sistema (1.2). Per immagini a colori la manipolazione va compiuta sui tre canali del rosso, verde e blu. Per una foto scattata con una macchina fotogra ca da 5 megapixel si devono risolvere tre sistemi di circa 5 milioni di equazioni e di incognite per poter rimettere a fuoco la foto. I sistemi che si ottengono in questo modo sono sottodeterminati, hanno cioè meno equazioni che incognite, dovuto alla in uenza nella sfocatura dei punti in una cornice di ampiezza k al di fuori del supporto dell'immagine, come detto sopra. La risoluzione di questi sistemi va allora intesa in termini di "risoluzione ai minimi quadrati".
1.3 Matrici associate alla sfocatura
Il sistema (1.2) può essere scritto in forma matriciale come Ha = b dove a e bsono i vettori ottenuti applicando l'operatore vec ad A e B, cioè a = vec(A) e b=vec(B), mentre H è la matrice del sistema lineare che si ottiene con questa organizzazione in vettori.
Vediamo di descrivere la struttura della matrice H del sistema Ha = b che lega l'immagine originale A e l'immagine sfocata B. Per vedere come è fatta la matrice del sistema che dobbiamo risolvere, esaminiamo prima il caso più elementare in cui n = 1, cioè le immagini A, B e la PSF F sono costituite da una sola colonna, cioè A = (a1−k, ..., am+k)T, B = (b1, ..., bm)T,
F = (f−k, ..., fk)T. In questo caso il sistema (1.2) prende la forma bi = k X r=−k frai−r, i= 1, ..., m.
Si può osservare che in ciascuna equazione di questo sistema compaiono 2k+ 1incognite consecutive, ad esempio nella i-esima equazione sono ai−k, ..., ai+k
e che i coe cienti di queste incognite in ciascuna equazione sono sempre gli stessi, cioè gli elementi della PSF. Questo porta a una matrice del sistema che ha una struttura a banda di ampiezza 2k + 1 e che gli elementi della matrice sulla banda sono uguali lungo le diagonali. Cioè, in notazione matriciale, il sistema Ha = b ha la forma b1 b2 ... bm = fk fk−1 · · · f−k+1 f−k fk fk−1 ... f−k+1 f−k ... ... ... ... ... fk fk−1 · · · f−k+1 f−k a1−k ... a0 a1 ... ... am am+1 ... am+k . (1.3)
Osserviamo che questa matrice è una matrice di Toeplitz. Nel caso generale in cui m, n > 1, se scriviamo le matrici A e B rispettivamente come vettori a e b usando vec, la matrice del sistema H prende la forma di matrice n × (n + 2k) a blocchi con blocchi di dimensione m × (m + 2k)
H= Fk Fk−1 · · · F−k+1 F−k Fk Fk−1 ... F−k+1 F−k ... ... ... ... ... Fk Fk−1 · · · F−k+1 F−k (1.4) dove Fr = fr,k fr,k−1 · · · fr,−k+1 fr,−k fr,k fr,k−1 ... fr,−k+1 fr,−k ... ... ... ... ... fr,k fr,k−1 · · · fr,−k+1 fr,−k
Cioè la matrice del sistema ha due livelli di struttura: in termini di blocchi e in termini di elementi dei blocchi. Infatti, la matrice è di Toeplitz a blocchi con blocchi di Toeplitz; è inoltre a banda a blocchi con blocchi a banda. Queste matrici sono dette matrici di Toeplitz bi-livello.
Come già notato alla ne della sezione precedente, il sistema da risolve-re (1.3) è un sistema sottodeterminato, cioè ha più incognite che equazioni. Per ovviare a questo imponiamo delle condizioni al bordo che possono essere principalmente di tre tipi, vedere [12]:
1. condizioni al bordo nulle: queste consistono nell'imporre i valori dell'inco-gnita che sono fuori dal supporto dell'immagine uguali a zero. Si osserva che nel sistema rettangolare sottodeterminato da risolvere, si ottiene una matrice di Toeplitz (di Toeplitz a blocchi con blocchi di Toeplitz nel caso bidimensionale), vedere [13].
2. condizioni al bordo periodiche: i valori dell'incognita che sono fuori dal supporto dell'immagine sono uguali ai valori dell'incognita all'estremo opposto, cioè si impone che l'immagine abbia i valori fuori dal supporto a sinistra uguali ai valori fuori dal supporto a destra e analogamente per i valori in alto e in basso sempre fuori dal supporto. In questo caso quindi si sta supponendo che l'immagine si trovi su un toro, si osserva che i valori rientrano in modo ciclico e la matrice del nuovo sistema che si ottiene è circolante (a blocchi con blocchi circolanti nel caso bidimensionale), vedere [14].
3. condizioni al bordo ri essive: se i valori fuori dal supporto, ad esem-pio sul lato sinistro, sono uguali ai primi valori all'interno del supporto dell'immagine sempre sul lato sinistro, allora si ottiene una matrice che è somma di una Toeplitz e di una Hankel che è diagonalizzata da una trasformata dei coseni, vedere [12] .
Nel seguito useremo l'approccio di R. Chan, che usa le condizioni al bordo periodiche, cioè i singoli fotogrammi vengono considerati a supporto su un toro.
È interessante ora fare una manipolazione formale per ridurre l'espressione sopra ad un prodotto di polinomi. Precisamente, considerando il caso in cui n = 1, nella matrice H in (1.3) aggiungiamo 2k righe in testa e 2k righe in coda rispettando la struttura Toeplitz. Abbiamo allora
b−2k+1 .. . b0 b1 b2 .. . bm bm+1 .. . bm+2k = f−k f−k+1 f−k .. . ... ... fk−1 ... f−k+1 f−k fk fk−1 · · · f−k+1 f−k fk fk−1 ... f−k+1 f−k ... ... ... ... ... fk fk−1 · · · f−k+1 f−k fk fk−1 ... f−k+1 fk ... ... ... fk−1 fk a1−k .. . a0 a1 .. . .. . am am+1 .. . am+k (1.5)
dove ora la matrice ha dimensioni (m + 4k) × (m + 2k).
L'espressione che si è ottenuta in questo modo esprime la relazione tra i coe cienti dei polinomi b(x) = Pm+4k−1
i=0 bi−2k+1xi, f(x) = P2k−1i=0 fi−k+1xi e
a(x) =Pm+2k−1
i=0 ai−k+1xi, tali che
b(x) = f (x) a(x).
Questa proprietà è dimostrabile facilmente. Infatti basta moltiplicare a sinistra entrambi i membri della (1.5) per il vettore [1, x, x2, ..., xm+4k−1]. A sinistra si
ottiene b(x), a destra si ha [f(x), xf(x), ..., xm+2k−1f(x)][a
1−k, ..., am+k]T =
= f (x)[1, x, ..., xm+2k−1][a
1−k, ..., am+k]T = f (x)a(x). Quindi è possibile
rica-vare il vettore [b1, ..., bm]dai coe cienti centrali del polinomio b(x) = f(x)a(x).
Notiamo poi che la trasposta della matrice H in (1.3) è data da
HT = fk fk−1 fk ... ... ... f−k+1 ... ... ... f−k ... ... ... fk ... ... ... fk−1 ... ... ... f−k f−k+1 f−k
per cui il prodotto u = HTv equivale a calcolare i coe cienti del polinomio
vettore v. Quindi osserviamo che per calcolare i coe cienti di u(x) usiamo la convoluzione.
De nizione 1.17. Si dice convoluzione la trasformazione che associa ai vettori a e b dei coe cienti di due polinomi a(x), b(x) il vettore c dei coe cienti del polinomio prodotto c(x) = a(x)b(x).
Osservazione 1.18. Siano f(x) = P2k
i=0fi−kxi, ˜f(x) =
P2k
i=0fi+kxi, b(x) =
= Pm+4k
i=0 bi−kxi, a(x) = Pm+2ki=0 ai−kxi. Allora il vettore [b1, ..., bm] soddisfa
(1.3) se e solo se b(x) = f(x)a(x). Inoltre se u e v sono i vettori rispettivamente di m + 2k e m + 4k e u(x), v(x) i polinomi associati, vale u = HTv se e solo
se u(x) = ˜f(x)a(x).
In modo analogo, anche nel caso di matrici di Toeplitz bi-livello possiamo scrivere il prodotto tra H ed un vettore a così come il prodotto tra HT e un
vettore v mediante il prodotto di due polinomi. I polinomi però sono bivariati in questo caso, cioè sono polinomi di due variabili x e y.
1.4 Matrici circolanti e FFT
In questa sezione esaminiamo come sia possibile calcolare il prodotto tra una matrice di Toeplitz circolante n×n e un vettore con O(n log(n)) operazioni aritmetiche.
Si consideri il polinomio monico a(x) = xn−Pn−1
i=0 aixi e si de nisce la
matrice companion (di Frobenius) associata
C(a) = 0 1 ... ... 0 1 a0 a1 · · · an−1 .
È immediato veri care che se ξi è uno zero di a(x), cioè se a(ξi) = 0, allora
vi= (ξij)i,j=0,...,n−1 veri ca la relazione
C(a)vi = ξi ξi2 ... ξin = ξivi.
Per cui, se a(x) ha n zeri distinti ξ1, ..., ξn allora la matrice di Vandermonde
V = {ξj−1i } è tale che
Si consideri il polinomio a(x) = xn− 1e la matrice companion associata C = 0 1 ... ... 0 1 1 0 · · · 0 .
Il polinomio a(x) ha per zeri le radici n-esime dell'unità, ξi = wi−1n , i= 1, ..., n,
dove wn = cos(
2π
n ) + i sin( 2π
n), dove i è l'unità immaginaria. Per cui, posto Ω = (w(i−1)(j−1)n ), e V = 1 √ nΩ, valgono VHV = I, VHCV =diag(1, wn, w2n..., wn−1n ), V CVH =diag(1, wn, w2n..., wn−1n ),
dove VH indica la matrice trasposta coniugata di V e w
nil complesso coniugato
di wn. Si osservi tra l'altro che, essendo wndi modulo 1, vale wn= w−1n .
Si ricorda che Ω è la matrice che de nisce la trasformata discreta di Fourier. Infatti, per de nizione, l'applicazione y = 1
nΩ
Hx è la trasformata discreta
di Fourier (DFT), mentre l'applicazione x = Ωy è la trasformata discreta inversa di Fourier (IDFT). Si ricorda che, se n è una potenza intera di 2, esistono algoritmi per calcolare la DFT e la IDFT in circa 3
2nlog2noperazioni aritmetiche. Se n è un intero positivo qualsiasi esistono comunque metodi per il calcolo della DFT e della IDFT che richiedono O(n log n) operazioni aritmetiche. Tali algoritmi sono noti come algoritmi FFT, acronimo di Fast Fourier Transform. Esistono diverse implementazioni degli algoritmi FFT. Nel seguito denotiamo rispettivamente con y = DF T (x) e x = IDF T (y) la trasformata discreta di Fourier e la sua inversa.
Si osservi che C è una matrice di permutazione associata alla permutazione ciclica πi = i + 1 mod nche agisce su {0, 1, ..., n − 1}. Cioè il generico vettore
x = (xi)i=0,1,...,n−1 viene trasformato da C in Cx = (x1, x2, ..., xn−1, x0)T.
Per cui anche le matrici Ck, k = 0, 1, ..., n − 1 sono matrici di permutazione
associate alla permutazione π ◦ π ◦ ... ◦ π (k-volte). In particolare risulta che Ck è la matrice che ha elementi uguali a 1 in posizione (i, j) se j − i = k
mod n, ed elementi nulli altrove. Di conseguenza la matrice C(a) = Pn−1i=0 aiCi
avrà elementi C(a) = {aj−i mod n}. Quindi possiamo aermare che C(a) è una
matrice di Toeplitz circolante, matrici che avevano in eetti questa proprietà come visto nella Proposizione 1.7.
Si osservi che, posto V = (1/√n)Ω, dalla relazione VHCV =diag(1, w n, wn2,
..., wn−1
n )e dal fatto che C(a) è esprimibile come polinomio segue
V C(a)VH =
n−1
X
i=0
e quindi
C(a) = VHDV = 1 nΩ
HDΩ; D =diag(d), d = Ω(a
0, ..., an−1)T.
Siccome la prima riga di C(a) si ottiene invertendo l'ordine degli elementi della prima colonna di C(a), si ha che d = ΩC(a)e1, dove e1 = (1, 0, ..., 0)T.
Per cui possiamo scrivere C(a) = 1
nΩ
HDΩ, D =diag(d), d = ΩC(a)e 1
cosi che il prodotto y = C(a)x può essere scritto y= 1
nΩ
HhΩC(a)e 1,Ωxi ,
dove h·, ·i indica il prodotto componente a componente di due vettori, cioè il prodotto scalare. In questo modo il prodotto y = C(a)x, dati x ed a, può essere calcolato in modo e ciente dal seguente algoritmo
• z = IDF T (x);
• w = IDF T (a0, an−1, ..., a1);
• u = hw, zi; • y = DF T (u);
che richiede il calcolo di due trasformate inverse discrete di Fourier e di una tra-sformata diretta. Se n è potenza intera di 2 il costo computazionale complessi-vo è di circa (9/2)n log2noperazioni aritmetiche. Praticamente si ha, a meno
di costanti dato che u = F F T (x) = ΩHx = nDF T
n(x) e v = IF F T (x) = (1/n)Ωx = (1/n)IDF Tn(x), • z = F F T (x); • w = F F T (a); • u = hw, zi; • y = IF F T (u);
Quindi il prodotto tra matrice circolante e vettore y = C(a)x lo otteniamo attraverso l'uso della FFT.
1.5 Prodotto matrice di Toeplitz-vettore
Il prodotto tra una matrice di Toeplitz e un vettore può essere ricondotto al calcolo del prodotto matrice circolante−vettore procedendo nel seguente modo. Data una matrice di Toeplitz T = {tj−i} di dimensione n × n si consideri la
matrice circolante A di dimensione p × p con p ≥ 2n la cui prima riga è (t0, t1, ..., tn−1,0, ..., 0, t−n+1, ..., t−2, t−1)
e si osservi che la sottomatrice principale di testa di A di ordine n coincide con T. Si veda ad esempio il caso
A= a0 a1 a2 0 a−2 a−1 a−1 a0 a1 a2 0 a−2 a−2 a−1 a0 a1 a2 0 0 a−2 a−1 a0 a1 a2 a2 0 a−2 a−1 a0 a1 a1 a2 0 a−2 a−1 a0
in cui la sottomatrice principale di testa 3×3 è una generica matrice di Toeplitz. Per calcolare il prodotto y = T x si considera il vettore ˆx di dimensione p ottenuto estendendo con zeri il vettore x, cioè ˆxT = (xT,0, ..., 0). Per il vettore
ˆ
y= Aˆxvale allora
ˆ y= y
y0
dove y0 è un opportuno vettore.
In questo modo il calcolo di y = Ax è ricondotto al calcolo di un prodotto matrice circolante−vettore per un costo di O(n log n). Inoltre, poichè la di-mensione p della matrice circolante in cui si immerge la matrice di Toeplitz è arbitraria purché almeno 2n, possiamo sceglierla pari a una potenza intera di 2 in modo che le trasformate discrete di Fourier possano essere calcolate in modo più e ciente.
Esaminiamo ora il caso in cui la matrice A è rettangolare di dimensioni m × n con PSF di semiampiezza k. Per semplicità descriviamo il caso in cui m= 11, n = 7 e k = 2 per cui A= a−2 a−1 a−2 a0 a−1 a−2 a1 a0 a−1 a−2 a2 a1 a0 a−1 a−2 a2 a1 a0 a−1 a−2 a2 a1 a0 a−1 a−2 a2 a1 a0 a−1 a2 a1 a0 a2 a1 a2
L'immersione in una circolante per calcolare il prodotto y = Ax la svolgiamo nel seguente modo
y = a−2 a2 a1 a0 a−1 a−1 a−2 a2 a1 a0 a0 a−1 a−2 a2 a1 a1 a0 a−1 a−2 a2 a2 a1 a0 a−1 a−2 a2 a1 a0 a−1 a−2 a2 a1 a0 a−1 a−2 a2 a1 a0 a−1 a−2 a2 a1 a0 a−1 a−2 a2 a1 a0 a−1 a−2 a2 a1 a0 a−1 a−2 x1 x2 x3 x4 x5 x6 x7 0 0 0 0
Quindi la matrice circolante si ottiene aggiungendo 2k colonne opportune ad A, o più semplicemente la circolante è de nita dalla sua prima colonna che coincide con la prima colonna di A. Il vettore x viene completato con 2k zeri nelle ultime componenti. In questo caso si ha
y= DF T (IDF T (Ae1) ∗ IDF T (˜x)), x˜= (x, 0, ..., 0)T.
In modo analogo, per calcolare il prodotto z = ATwragioniamo allo stesso
modo considerando semplicemente che ora lavoriamo con la matrice A tra-sposta e quindi anche la matrice circolante di immersione lo sarà. Inoltre si sottolinea il fatto che in questo caso sarà z ad avere degli elementi in più, men-tre w rimane lo stesso, a dierenza del sistema y = Ax in cui si aggiungevano ad x degli zeri. In altri termini è su ciente costruire la matrice circolante la cui prima riga coincide con la trasposta della prima colonna di A. Si può osservare ancora che la prima riga rT
1 e la prima colonna c1 di una matrice
circolante sono legate dalla seguente relazione
r1 = Πc1, Π = 1 0 1 0 .·· 1 . Inoltre la IDFT di rT
1 e di c1 sono l'una la complessa coniugata dell'altra.
Infatti se C è una matrice circolante per cui C = F DFH, vale CH = F DHFH,
per cui, se F è reale vale CT = CH = F DHFH. Cioè la diagonale di DH, che
è la IDFT della prima colonna di CT, coincide con la coniugata della diagonale
1.6 Prodotto per matrici a blocchi
Nel caso di matrici Toeplitz n×n a blocchi con blocchi di Toeplitz m×m è possibile condurre una analisi analoga ed arrivare ad un algoritmo per il calcolo del prodotto matrice−vettore con un costo computazionale di O(mn log(mn)) operazioni aritmetiche. Per ottenere questo è utile introdurre la classe delle matrici circolanti a blocchi con blocchi circolanti
C = m−1 X i=0 n−1 X j=0 ai,jCmi ⊗ Cnj,
dove Cm e Cn sono le matrici companion associate rispettivamente ai polinomi
xm − 1 e xn − 1 e ⊗ indica il prodotto di Kronecker. Tutte le matrici di
questa classe sono diagonalizzate dalla trasformazione per similitudine de nita dalla matrice Vm⊗ Vn, dove Vm =
1 mΩm, Vn = 1 nΩn e Ωm = {w (i−1)(j−1) m },
Ωn= {w(i−1)(j−1)n }. Vale infatti
(Vm⊗ Vn)(C)(Vm−1⊗ V −1 n ) = m−1 X i=0 n−1 X j=0 ai,jDmi ⊗ Djn,
la quale è una matrice diagonale essendo Dm =diag(1, wm, ..., wm−1m ), Dn =
diag(1, wn, ..., wn−1n ).
Questa espressione permette di calcolare il prodotto di una matrice circo-lante a blocchi con blocchi circolanti con un numero di operazioni dell'ordine di O(mn log(mn)).
Analogamente al caso delle matrici di Toeplitz trattato in precedenza, è possibile veri care che una matrice di Toeplitz a blocchi con blocchi di Toeplitz può essere vista come una sottomatrice principale di una matrice circolante a blocchi con blocchi circolanti. In questo modo il prodotto tra una matrice di Toeplitz a blocchi con blocchi di Toeplitz e un vettore può essere calcolato in O(mn log(mn)) operazioni aritmetiche. Lasciamo i dettagli al lettore.
1.7 Richiami di teoria dei segnali
Per un approfondimento dei concetti e risultati ottenuti in questa sezione si rimanda a [10].
1.7.1 Segnali
Cosa è un segnale? Esempi familiari nella vita quotidiana sono il segna-le acustico prodotto da uno strumento musicasegna-le, il segnasegna-le misurato da un
elettrocardiografo, il segnale radio e così via. Un segnale esiste poiché è porta-tore di una informazione, che può essere di varia natura: di carattere estetico, nel caso del brano musicale, medico, nel caso dell'elettrocardiogramma, e così via. Dunque possiamo dire che un segnale è una qualunque grandezza sica variabile a cui è associata una informazione.
Il modo più conveniente per caratterizzare, studiare ed elaborare un segna-le è di schematizzarlo come una funzione matematica di una o più variabili. Possiamo, ad esempio, vedere una immagine in bianco e nero come un segnale che viene schematizzato da una funzione i due variabili, che sono le coordinate del pixel, inoltre il valore assunto dalla funzione indica l'intensità luminosa. Quindi avremmo I(x, y) : R2 −→ R ∀ (x, y) appartenente al supporto
dell'im-magine. Per le immagini a colori si avrà lo stesso ragionamento ma per ognuno dei tre colori dell'RGB.
I segnali possono essere di due tipi:
1. segnali a tempo continuo: per i quali il dominio della funzione ha la cardinalità dell'insieme dei numeri reali. La variabile indipendente può assumere con continuità tutti i valori compresi entro un certo intervallo, eventualmente illimitato.
2. segnali a tempo discreto: per i quali il dominio della funzione ha la cardinalità dell'insieme dei numeri interi.
Una classi cazione analoga può essere condotta sulla base dei valori assunti dai segnali (cioè sulla base del codominio della funzione che li rappresenta):
1. segnali ad ampiezza continua, che possono assumere con continuità tutti i valori reali di un intervallo (eventualmente illimitato), come nel caso di un segnale acustico;
2. segnali ad ampiezza discreta, aventi come codominio un insieme numera-bile, eventualmente illimitato. Ad esempio il segnale luminoso prodotto da una lampadina di un semaforo può assumere solo due valori (acceso o spento)
I segnali a tempo continuo e ad ampiezza continua si dicono analogici, mentre quelli a tempo e ampiezza discreti si dicono numerici e sono quelli ti-picamente trattati dai calcolatori elettronici. Anche i segnali a tempo discreto e ampiezza continua (cioè successioni a valori reali) hanno una grande impor-tanza perché costituiscono l'oggetto delle tecniche di elaborazione numerica dei segnali (DSP, Digital Signal Processing). I segnali ad ampiezze discrete e tempo continuo sono detti quantizzati.
1.7.2 Segnali periodici a tempo continuo
Supponiamo di avere il segnale
dove a è l'ampiezza della oscillazione, f0 = 1/T0 è la frequenza, T0 rappresenta
il periodo del segnale e θ è la fase iniziale.
Un segnale x(t) è periodico se soddisfa la seguente relazione: x(t) = x(t+T0)
per ogni valore della variabile t.
L'analisi di Fourier, che costituisce la base della moderna teoria dei segnali permette, sotto opportune ipotesi,di esprimere un segnale reale periodico qua-lunque come somma di oscillazioni sinusoidali di ampiezza, frequenza e fase opportune, cioè in forma
x(t) = A0+ A1cos(2πf1t+ θ1) + A2cos(2πf2t+ θ2) + . . . (1.6)
Questa rappresentazione del segnale prende il nome di sviluppo in serie di Fourier. Si hanno tre forme per lo sviluppo in serie di Fourier:
• le frequenze di oscillazione includono in generale la "frequenza zero" relativa al termine costante A0, e sono multiple intere della frequenza
fondamentale f0 cosicché la (1.6) diventa
x(t) = A0+ 2 ∞
X
k=1
Akcos(2πkf0t+ θk), (1.7)
detta espressione in forma polare dello sviluppo in serie di Fourier. Essa permette dunque di rappresentare un segnale reale x(t) come somma di una costante A0 e di una serie il cui k-esimo termine, detto k-esima
oscillazione armonica, ha ampiezza Ak > 0, frequenza kf0 (la k-esima
frequenza armonica) e fase iniziale θk.
• usando le formule di Eulero delle funzioni trigonometriche si ottiene x(t) = X0+ ∞ X k=1 Xkei2πkf0t+ −1 X k=−∞ Xkei2πkf0t= ∞ X k=−∞ Xkei2πkf0t, (1.8) dove Xk= Akeθk per k = 1, ..., ∞ e Xk= A−ke−θ−k per k = −1, ..., −∞.
Questa rappresenta l'espressione in forma complessa della serie di Fou-rier, e che risulta la più conveniente dal punto di vista del calcolo. • x(t) = a0+ 2 ∞ X k=1 [akcos(2πkf0t) − bksin(2πkf0t)], (1.9)
la quale è detta espressione in forma rettangolare.
Si può provare che un modo per ottenere i coe cienti Xkè dato dalla seguente
formula, supponendo che la serie in (1.8) sia convergente uniformemente: Xk= 1 T0 Z T0/2 −T0/2 x(t)e−i2πkf0tdt (1.10)
che coincide con l'espressione del valor medio del segnale.
Un insieme di condizioni su cienti che garantiscono la possibilità di svi-luppare un segnale in serie di Fourier è il cosiddetto criterio di Dirichlet che può essere enunciato come segue:
• se x(t) è assolutamente integrabile sul periodo T0 (cioè se veri ca la
condizione RT0/2
−T0/2|x(t)| dt < ∞);
• se x(t) è continua o presenta in un periodo un numero nito di disconti-nuità di prima specie;
• se x(t) è derivabile rispetto al tempo nel periodo, escluso al più un numero nito di punti nei quali esistono nite la derivata destra e sinistra, allora la serie di Fourier converge al valore assunto dalla funzione x(t) nei punti in cui questa è continua, e alla semisomma dei limiti destro e sinistro nei punti in cui x(t) presenta le eventuali discontinuità di prima specie.
La (1.10) è una equazione di analisi che permette di stabilire qual è il con-tenuto in termini di oscillazioni armoniche del segnale (in una parola, di ana-lizzare il segnale). La (1.8), viceversa, è una equazione di sintesi che permette di pensare il segnale come "scomposto" in una sovrapposizione di oscillazioni sinusoidali (le armoniche) a frequenza multipla della frequenza fondamentale f0 = 1/T0. L'equazione di sintesi prevede l'uso di in nite armoniche per
rico-struire il segnale, ma condizione necessaria alla convergenza della serie è che l'ampiezza delle armoniche |Xk| −→ 0 quando k −→ ∞. Questo comporta che
le armoniche più "importanti" ai ni della sintesi del segnale siano in numero limitato.
Le equazioni di analisi e sintesi permettono dunque di stabilire una corri-spondenza tra il segnale x(t) e la sequenza Xk costituita dai coe cienti della
serie coe cienti di Fourier. La conoscenza della successione completa dei coef- cienti di Fourier, che in generale sono complessi, è di fatto equivalente alla conoscenza dell'andamento del segnale nel tempo.
In pratica,la sintesi di un segnale periodico viene eettuata con un numero di armoniche nito. Questo comporta un certo errore nella ricostruzione del segnale, tanto minore quanto maggiore è il numero di armoniche considerate, ma tanto maggiore quanto più la velocità di variazione del segnale è grande: il caso più sfavorevole è quello di un segnale con discontinuità di prima specie, come l'onda quadra.
1.7.3 Segnali aperiodici a tempo continuo
L'analisi di Fourier è applicabile anche ai segnali aperiodici. Immaginando infatti di ottenere un segnale aperiodico come il limite di un segnale periodico
quando il periodo di ripetizione T0 tende a in nito, si riesce a estendere
l'e-spansione in serie di Fourier, valida per il segnale periodico, anche ai segnali non periodici, ottenendo così l'integrale di Fourier
x(t) = Z ∞
−∞
X(f )ei2πf tdf. (1.11)
In questa equazione di sintesi,il ruolo che nella serie giocavano i coe cienti Xk
viene riservato alla trasformata continua di Fourier X(f) del segnale aperiodico x(t)
X(f ) = Z ∞
−∞
x(t)ei2πf tdt (1.12)
che è una funzione complessa della variabile continua f, che mantiene il signi- cato di frequenza.
La (1.11), detta anche antitrasformata di Fourier (o trasformata inversa di Fourier), permette ancora di rappresentare il segnale aperiodico x(t) come la sovrapposizione di componenti sinusoidali, ma stavolta di ampiezza in nitesi-ma X(f)df e di frequenza f variabile con continuità su tutto l'asse reale. In altre parole, il segnale aperiodico è visto come un segnale periodico "di periodo illimitato" e quindi con frequenza fondamentale "in nitamente piccola".
Un criterio di esistenza è il criterio di Dirichlet che può essere enunciato come segue (si confronti con il criterio per la serie di Fourier):
• se il segnale x(t) è assolutamente sommabile, ovvero R−∞∞ |x(t)| dt < +∞; • se in qualunque intervallo nito t1 ≤ t ≤ t2 l segnale x(t) ha un numero
nito di discontinuità di prima specie;
• se in qualunque intervallo nito t1 ≤ t ≤ t2 il segnale x(t) ha un numero
nito di massimi e minimi;
allora il segnale è rappresentabile come integrale di Fourier (cioè antitrasfor-mata della sua propria trasforantitrasfor-mata di Fourier X(f) secondo le (1.11)-(1.12), e nei punti di discontinuità l'integrale di Fourier converge alla semisomma dei limiti destro e sinistro del segnale.
Alcune proprietà importanti sono: Considerati x1(t) e x2(t) due
segna-li, X1(f ) e X2(f ) le rispettive trasformate, a, b, t0 ∈ R, alcune proprietà
importanti sono
• Teorema di linearità: x(t) = ax1(t) + bx2(t) allora X(f) = aX1(f ) +
bX2(f ).
• Teorema del ritardo: la trasformata di un segnale traslato sull'asse del tempo risulta essere X(f)e−i2πf t0, cioè x(t − t
0) ⇔ X(f )e−i2πf t0 dove il
⇔ va letta come corrispondenza biunivoca.
• Teorema del cambiamento di scala: x(αt) ⇔ 1 |α|X f α ove α ∈ R e si ha una compressione della scala dei tempi se |α| > 1, una dilatazione se <1 e una inversione se α < 0.
• Teorema della modulazione: x(t) cos(2πf0t) ⇔
X(f − f0) + X(f + f0)
2 .
• Teoremi di derivazione e integrazione: dx(t)
dt ⇔ i2πf X(f ) e Rt
−∞x(α)dα ⇔
X(f ) i2πf .
• Teorema del prodotto: x1(t)x2(t) ⇔ X(f ) ∗ Y (f )dove ∗ indica la
con-voluzione.
• Teorema della convoluzione: x(t) ∗ y(t) ⇔ X(f)Y (f).
1.7.4 Segnali a tempo discreto
Sappiamo che un segnale a tempo discreto è una successione xno sequenza
x[n] di numeri, ed è quindi rappresentabile con una successione avente valori reali o complessi. Nel seguito useremo la notazione x[n] per sempli care la notazione ed evitare l'uso di doppi indici. Un caso tipico nell'elaborazione dei segnali è quello in cui il segnale a tempo discreto viene ottenuto da un segna-le a tempo continuo attraverso la cosiddetta operazione di campionamento. Campionare un segnale x(t) signi ca "estrarre" dal segnale stesso i valori che esso assume a istanti temporali equispaziati, cioè multipli di un intervallo T detto periodo di campionamento. Con questa operazione viene a crearsi una sequenza il cui valore n-esimo x[n] è il valore assunto dal segnale a tempo con-tinuo all'istante nT . La cadenza con cui il segnale viene campionato, è pari a fc= 1/T, prende il nome di frequenza di campionamento.
La rappresentazione di una sequenza aperiodica x[n] in campo frequenziale analoga alla trasformata continua di Fourier di un segnale analogico aperiodico è la trasformata di Fourier della sequenza x[n] de nita da
¯ X(f ) = ∞ X −∞ x[n]e−i2πnf T = F[x[n]]. (1.13) La funzione ¯X(f ) è periodica in ambito frequenziale di un periodo pari al-la frequenza di campionamento fc = 1/T. La sequenza x[n] viene
espres-sa attraverso un integrale di Fourier (o antitrasformata di Fourier di una sequenza) x[n] = T Z 1/2T −1/2T ¯ X(f )e−i2πnf Tdf. (1.14)
Elenchiamo alcune proprietà fondamentali della trasformata di Fourier di una sequenza, spesso analoghe, ma in qualche caso signi cativamente dierenti da quelle per i segnali a tempo continuo. Considerati x1[n] e x2[n] due segnali,
¯
X1(f )e ¯X2(f )le rispettive trasformate, a, b ∈ R, alcune proprietà importanti
sono
• Teorema di linearità: x(t) = ax1[n] + bx2[n] allora ¯X(f ) = a ¯X1(f ) +
b ¯X2(f ).
• Teorema del ritardo: x[n − k] ⇔ ¯X(f )e−i2πkf T. • Teorema della modulazione: x[n]ei2πnf0T ⇔ ¯X(f − f
0).
• Teorema della somma di convoluzione: de nita la somma di convoluzione come z[n] = x[n] ∗ y[n] = P∞
k=−∞x[k]y[n − k] =
P∞
k=−∞y[k]x[n − k], si
ha z[n] = x[n] ∗ y[n] ⇔ ¯X(f ) ¯Y(f ) = ¯Z(f ).
• Teorema del prodotto: p[n] = x[n] · y[n] ⇔ ¯P(f ) = T R1/2T
−1/2T X(v) ¯¯ Y(f −
v)dv.
• Teorema dell'incremento: de nito ∆x[n] = x[n] − x[n − 1] e approssi-mando la derivata di un segnale continuo con ∆x[n]/T allora abbiamo ∆x[n] ⇔ ¯X(f ) − ¯X(f )e−i2πf T.
• Teorema della sequenza somma: considerata la sequenza somma y[n] = Pn
k=−∞x[k] si dimostra che la relativa trasformata è ¯Y(f ) =
= X(f )¯ 1 − e−i2πf T.
1.7.5 Sistemi monodimensionali
In senso lato, possiamo chiamare sistema monodimensionale (altrimenti detto a un ingresso e una uscita) un qualunque dispositivo, o interconnessione di dispositivi, o apparato, che produce un segnale di uscita (chiamato anche risposta o eetto) in corrispondenza a un segnale di ingresso (detto anche sol-lecitazione, eccitazione o causa). Dal punto di vista matematico la de nizione di sistema è assai meno vaga. In questo contesto, un sistema è una trasforma-zione (o, con la nomenclatura dell'analisi funzionale, un funzionale) che a un segnale di ingresso x(t) fa corrispondere un ben determinato e unico segnale d'uscita y(t). La trasformazione del segnale x(t) nel segnale y(t) si denota nel modo seguente:
y(t) = T [x(t)]. (1.15)
A prescindere dalla struttura interna del sistema, fortemente dipendente dal contesto e dall'applicazione, è possibile acquisire alcune informazioni prelimi-nari sul comportamento del sistema stesso e individuarne così alcune proprietà, compiendo osservazioni esclusivamente sui segnali di ingresso/uscita.
• Stazionarietà: se le caratteristiche del sistema non variano nel tempo, il sistema è stazionario, cioè se y(t) = T [x(t)] allora T [x(t−t0)] = y(t−t0).
Cioè in pratica la risposta corrispondente al segnale in ingresso traslato nel tempo x(t − t0) ha lo stesso andamento della risposta al segnale
originario x(t) non traslato, purché la si trasli della stessa medesima quantità t0, in altre parole il sistema è tempo-invariante.
• Causalità: un sistema è causale quando il valore dell'uscita all'istante arbitrario generico t dipende soltanto dai valori assunti dall'ingresso agli istanti precedenti (o al limite coincidenti con) t stesso.
• Memoria: un caso particolare di sistema causale è il cosiddetto sistema istantaneo in cui l'uscita all'istante t dipende solamente dal valore del-l'ingresso al medesimo istante; in questo caso si usa anche la dizione di sistema senza memoria.
Se invece il calcolo del valore dell'uscita all'istante t presuppone la co-noscenza dell'andamento del segnale d'ingresso in tutto l'intervallo [t − T, t]: il sistema mantiene una certa memoria dell'andamento del segnale d'ingresso x(t) ed sistema con memoria.
• Stabilità: Diremo che un sistema è stabile se, sollecitato da un segnale con andamento arbitrario ma di ampiezza limitata, produce a sua volta in uscita un segnale di ampiezza limitata: |x(t)| ≤ M ⇒ |y(t)| ≤ K con M e K niti. Questa de nizione di stabilità si indica con l'acronimo BIBO (Bounded-Input Bounded-Output) che signi ca "uscita limitata per ogni ingresso limitato", ed è solo una tra le molte de nizioni di stabilità. • Invertibilità: se esiste un sistema inverso T−1[·] tale che: T−1[y(t)] =
x(t)qualunque sia il segnale di ingresso x(t).
• Linearità: un sistema è lineare se a esso è applicabile il principio di sovrapposizione degli eetti, cioè se x(t) = a x1(t) + b x2(t) allora in
uscita si ha y(t) = T [x(t)] = a y1(t) + b y2(t) dove y1(t) = T [x1(t)] e
y2(t) = T [x2(t)].
Restringiamo adesso la nostra attenzione al caso estremamente importan-te di sisimportan-temi lineari e stazionari (SLS) (o invarianti nel importan-tempo). Per un SLS dato è possibile misurare (o calcolare se si dispone di uno schema di proget-to) la cosiddetta risposta impulsiva, cioè l'uscita del sistema in corrispondenza all'eccitazione impulsiva x(t) = δ(t), dove δ(t) è la delta di Dirac. Convenzio-nalmente, tale segnale viene indicato con: h(t) = T [δ(t)]. L'importanza della risposta impulsiva di un SLS risiede nel fatto che la sua conoscenza permette di determinare la risposta del sistema a un segnale di ingresso di andamento arbitrario. Infatti si vede che se y(t) = T [x(t)] e vogliamo calcolare il segnale di uscita si ha che
La conoscenza della risposta impulsiva, oltre a permettere di ricavare il segna-le di uscita dato quello di ingresso, consente anche di veri care segna-le proprietà possedute dal sistema e quindi caratterizza completamente il comportamento del sistema stesso.
In molti casi però non è possibile e/o conveniente applicare al sistema una sollecitazione impulsiva, cambiamo dunque tipo di eccitazione, e forniamo al si-stema un segnale di ingresso sinusoidale o meglio, per semplicità di calcolo,una oscillazione sinusoidale complessa alla frequenza f, x(t) = ei2πf t. L'uscita
corrispondente è espressa da y(t) = ei2πf t
Z ∞
−∞
h(α)e−i2πf αdα.
Se il sistema è stabile, la risposta a un'oscillazione di frequenza f assegnata è a sua volta un'oscillazione alla stessa frequenza f, ma modi cata in ampiezza e fase rispetto all'ingresso di un fattore a valori complessi che chiamiamo risposta in frequenza (talvolta risposta armonica) del sistema
H(f ) = y(t) x(t) x(t)=ei2πf t = Z ∞ −∞ h(α)e−i2πf αdα. (1.17) Allora è chiaro che la risposta in frequenza è anche ricavabile come trasformata di Fourier della risposta impulsiva: H(f) = F[h(t)] Le due de nizioni sono chiaramente equivalenti.
Se in ne indichiamo con X(f) e Y (f) le trasformate di Fourier rispettiva-mente del segnale di ingresso e di quello di uscita, possiamo trovare una terza maniera di de nire o ricavare la risposta in frequenza H(f). Trasformando entrambi i membri della relazione costitutiva del SLS (1.16) abbiamo
y(t) = x(t) ∗ h(t) ⇔ Y (f ) = X(f )H(f ).
1.7.6 Generalità sui ltri e ltri ideali
Un caso tipico che si presenta nell'elaborazione dei segnali è quello in cui il segnale osservato x(t) è costituito dalla sovrapposizione, cioè dalla somma, di due segnali: x(t) = x1(t) + x2(t)dei quali il primo è un segnale utile, cioè
portatore di informazione, mentre il secondo rappresenta solo un disturbo ine-liminabile alla fonte. Consideriamo però i segnali in ambito frequenziale, in cui lo spettro del segnale "utile" e quello del "disturbo" possono insistere su intervalli frequenziali disgiunti. Si intuisce allora che è possibile separare il segnale utile dal disturbo utilizzando un SLS con risposta in frequenza oppor-tuna. Se, come di consueto, indichiamo con X1(f ) e X2(f )le trasformate di
Fourier rispettivamente di x1(t) e x2(t), la trasformata di Fourier del segnale
Se vogliamo reiettare (cioè cancellare) il disturbo x2(t), possiamo elaborare
il segnale tramite un SLS con caratteristiche di selettività nei confronti delle varie componenti frequenziali che compongono il segnale. De nita la funzione rect come rect(α) = 1 |α| < 1/2 1/2 |α| = 1/2 0 altrimenti
in particolare, il segnale x1(t) viene preservato e il disturbo viene reiettato se
il sistema ha una risposta in frequenza pari a HLP(f ) =rect f 2B ,
dove B è la banda del primo segnale, ossia è la dierenza tra la frequenza massima fH e la frequenza minima fL (in questo caso fL = 0)
dell'inter-vallo, sull'asse positivo, delle frequenze assunte dalle componenti del segnale x1(t). Il segnale d'uscita y(t) del ltro, avendo infatti trasformata di Fourier
Y(f ) = X(f )H(f ), sarà privo del disturbo x2(t). Un sistema con risposta in
frequenza di questo tipo viene chiamato ltro passa-basso ideale. Esso infatti possiede caratteristiche di selettività, nel senso che le componenti frequenziali all'interno di un certo intervallo vicino alla frequenza nulla (quindi basse fre-quenze) vengono lasciate inalterate. In questa zona infatti, chiamata banda passante, si ha H(f) = 1. Viceversa, all'esterno della banda passante, e cioè nella cosiddetta banda oscura, le componenti frequenziali vengono completa-mente cancellate perché H(f) = 0. La frequenza B rappresenta il cosiddetto limite di banda, in questo caso, poichè coincide con fH dato che fL= 0.
Questa funzione di selettività giusti ca il nome di " ltro" dato a questo SLS, nel senso che le componenti nello spettro del segnale aventi frequenza maggiore del limite di banda vengono "trattenute", mentre le altre compo-nenti vengono "lasciate passare". Nella pratica, si tende ad identi care il limite di banda B con l'ampiezza della banda passante (o banda tout-court). Per convenzione, infatti, la banda del ltro è l'ampiezza della banda passante considerata sul solo semiasse positivo delle frequenze.
La risposta impulsiva del ltro passa-basso (low-pass) ideale si ricava anti-trasformando l'espressione della risposta in frequenza
hLP(t) = 2Bsinc(2Bt).
Si nota immediatamente che hLP(t)è diversa da zero anche per valori di t < 0,
per cui il ltro passa-basso ideale è un sistema non causale e quindi sicamente non realizzabile.
Se invece desiderassimo sopprimere la componente x1(t) nel segnale x(t)
per isolare x2(t), potremmo utilizzare un SLS che permette l'eliminazione delle
dalle risposte in frequenza e impulsiva seguenti: HLP(f ) = 1 −rect f 2B ⇔ hLP(t) = δ(t) − 2Bsinc(2Bt).
È chiaro che stavolta la banda passante del ltro passa alto (high-pass) è quella che sta al di là del limite di banda B, nella quale le componenti frequenziali del segnale di ingresso non vengono alterate. Colloquialmente, diremo ancora (in modo improprio) che la banda del ltro passa-alto è B, alludendo in realtà al limite di banda. È immediato veri care che anche il ltro passa-alto ideale è un sistema non causale.
Supponiamo invece di osservare il segnale x(t) = x1(t) + x2(t) + x3(t)
somma di tre componenti, con trasformate tali che 0 ≤ X1(f ) < fL< X2(f ) <
fH < X3(f )e di voler estrarre da esso il segnale x2(t). I vari segnali hanno
infatti spettri non sovrapposti in ambito frequenziale e posti a cavallo delle cosiddette frequenze portanti. È necessario disporre di un sistema con risposta in frequenza HBP(f ) non nulla solo nella banda occupata dal segnale x2(t).
Tale sistema prende il nome di ltro passa-banda ideale. La banda passante del ltro (de nita per convenzione sul solo semiasse delle frequenze positive) si estende tra il limite di banda inferiore fL e il limite di banda superiore fH.
Alternativamente ai limiti di banda, il ltro passa-banda (band-pass) viene più comunemente caratterizzato attraverso i due parametri equivalenti frequenza centrale (o di centro-banda) f0 = (fL+ fH)/2, e ampiezza della banda passante
B = fH−fL. Calcoliamo ora la risposta impulsiva del ltro passa-banda ideale
ricordandoci il teorema della modulazione: HBP(f ) =rect f − f0 B +rect f + f0 B , hBP(t) = 2Bsinc(Bt) cos(2πf0t).
Consideriamo di nuovo il segnale x(t) = x1(t) + x2(t) + x3(t)e supponiamo di
voler eliminare da esso il segnale x2(t). Il ltro che permette di eettuare tale
operazione viene detto ltro elimina-banda ideale. La sua risposta in frequenza HBR(f )è ancora caratterizzata da una frequenza centrale f0e da un'ampiezza
di banda B (o dai limiti di banda fLed fH), entrambe però relative alla banda
oscura. È immediato stabilire la seguente relazione tra la risposta in frequenza del ltro elimina-banda (band-reject) ideale e quella del ltro passa banda ideale:
HBR(f ) = 1 − HBP(f )
per cui
hBR(t) = δ(t) − 2Bsinc(Bt) cos(2πf0t).
Un ltro elimina-banda può essere molto selettivo, e al limite può essere utiliz-zato per reiettare la componente spettrale a una sola particolare frequenza. In tal caso il ltro elimina-banda viene più comunemente chiamato ltro notch.
Un altro tipo di ltro è il ltro passa-tutto (all-pass) che non interviene sulle ampiezze delle frequenze, ma modi ca la soltanto la fase.
1.7.7 Caratterizzazione e proprietà dei sistemi monodimensio-nali a tempo discreto
La maggior parte delle considerazioni che sono già state fatte a proposito dei sistemi a tempo continuo possono essere ripetute per i sistemi a tempo discreto. Un sistema monodimensionale a tempo discreto è un dispositivo, un apparato, un programma per calcolatore che elabora una sequenza d'ingresso x[n] e genera una sequenza di uscita y[n]. L'unica dierenza notevole dal punto di vista concettuale che abbiamo introdotto è la menzione esplicita di un programma per calcolatore. Infatti i segnali a tempo discreto possono essere elaborati da circuiti elettronici digitali programmabili (microprocessori) il cui funzionamento è regolato da un programma.
Stanti le forti analogie tra lo studio dei sistemi a tempo continuo e quello dei sistemi a tempo discreto, vedremo nelle prossime sezioni brevemente quelle de nizioni e proprietà che sono già state discusse in maniera dettagliata per i sistemi a tempo continuo, limitandoci a sottolineare le (molte) similitudini e le (poche) diversità.
Identi chiamo dunque un sistema a tempo discreto con la trasformazione che viene eseguita sull'eccitazione x[n] per fornire la risposta y[n]:
y[n] = T [x[n]].
Un generico sistema monodimensionale a tempo discreto ha le stesse proprietà già citate per i sistemi monodimensionali a tempo continuo, cioè linearità, causalità, ecc. con de nizioni da modi care considerando le notazioni per i tempi discreti.
1.7.8 Sistemi lineari e stazionari a tempo discreto
Rivolgiamo adesso la nostra attenzione alla classe dei sistemi lineari e sta-zionari (SLS) a tempo discreto. Come già dimostrato per i sistemi analogici, un SLS a tempo discreto è caratterizzato completamente dalla conoscenza del-la risposta impulsiva h[n] de nita daldel-la redel-lazione h[n] = T [δ[n]]. Infatti, nota h[n], la sequenza di uscita y[n] del sistema avente in ingresso la sequenza x[n] è
y[n] = x[n] ∗ h[n] (1.18)
e cioè la sequenza di uscita di un SLS è la somma di convoluzione fra la sequenza di ingresso e la risposta impulsiva del sistema stesso.
È possibile dimostrare che condizione necessaria e su ciente per la stabilità in senso BIBO di un SLS è la assoluta sommabilità della sua risposta impulsiva:
∞
X
k=−∞
|x[k]| < ∞
e che inoltre un SLS è causale se e solo se la sua risposta impulsiva è una sequenza causale: h[n] = h[n]u[n] cioè h[n] = 0 se n < 0.
1.7.9 Risposta in frequenza di un SLS
La de nizione di risposta in frequenza di un SLS a tempo discreto stabile non dierisce apprezzabilmente da quella già introdotta. Dunque diremo che: 1. la risposta in frequenza di un SLS a tempo discreto è la trasformata di
Fourier della risposta impulsiva h[n] del sistema stesso: ¯ H(f ) = ∞ X n=−∞ h[n]e−i2πnf T;
2. la risposta in frequenza ¯H(f )è il rapporto fra le trasformate ¯Y(f )e ¯X(f ) rispettivamente della sequenza di uscita y[n] e di quella d'ingresso x[n]; 3. la risposta in frequenza ¯H(f )è data dal rapporto fra la sequenza di uscita
y[n] e quella di ingresso x[n] quando x[n] è una oscillazione complessa alla frequenza f: ¯ H(f ) = y[n] x[n] x[n]=ei2πnf T .
Si può provare che le tre espressioni sono equivalenti.
1.7.10 Filtri a tempo discreto
Il concetto di SLS selettivo in frequenza, o ltro, viene esteso direttamente al caso dei sistemi a tempo discreto, con identica nomenclatura. Naturalmen-te, le caratteristiche di selettività di un ltro a tempo discreto con risposta in frequenza ¯H(f )(che è una funzione periodica di periodo 1/T ) sono determi-nate dall'andamento della sua risposta in ampiezza ¯H(f )
in un solo periodo della funzione, ad esempio nell'intervallo [−1/2T, 1/2T ). Limitando l'analisi di ¯H(f )
a questo intervallo di frequenze occorre tener conto del fatto che le "basse frequenze" continuano a essere quelle prossime alla frequenza nulla, mentre le "alte frequenze" sono quelle prossime al limite superiore dell'inter-vallo, cioè 1/2T . Queste considerazioni giusti cano la classi cazione dei ltri ideali, per la quale si possono ripetere le stesse osservazioni esposte nella clas-si cazione dei sistemi analogici della sottosezione precedente, in particolare quelle riguardo la causalità, cioè si nota che i ltri ideali non sono causali.
1.7.11 Cambiamento della frequenza di campionamento
Molto spesso, nella pratica dell'elaborazione numerica dei segnali è oppor-tuno cambiare in tempo reale la cadenza con cui i campioni di una sequenza vengono elaborati. È conveniente allora introdurre un opportuno sistema per cambiare la cadenza di campionamento della sequenza z[n] in uscita dal ltro. Le operazioni principali di cambiamento della frequenza di campionamen-to fc possono essere ricondotte a una combinazione di due funzioni base, il
sovracampionamento e il sottocampionamento. Tali funzioni, opportunamente combinate, consentono di modi care fcsecondo un fattore razionale arbitrario,
in modo da generare una nuova sequenza con cadenza f0
c = (p/q) · fc, p e q
interi.
1.7.12 Cenni alla trasformata Z di una sequenza
De nizione di trasformata Z e zone di convergenza Si introduce la sequenza ˜ x[n] = x[n] 1 r n , r >0 (1.19)
che, contrariamente alla sequenza originaria, tende rapidamente a zero quando n −→ ∞. In questo modo ci si assicura che la trasformata di Fourier per questa nuova sequenza esiste, essendo la relativa serie convergente assolutamente.
Infatti calcolando la trasformata della nuova sequenza "smorzata" ˜x[n]: ¯ ˜ X(f ) = ∞ X n=−∞ x[n](re−i2πf T)−n. (1.20) Possiamo de nire un'unica variabile complessa espressa in forma polare come segue: z = rei2πf T, r = |z| ≥ 0, −π < ∠z ≤ π =⇒ − 1
2T ≤ f < 1 2T e interpretare poi la trasformata di Fourier della sequenza "modi cata" ˜x[n] come una diversa trasformata del segnale originario x[n] dipendente appunto dalla variabile complessa z = rei2πf T:
X(z) = Z[x[n]] =
∞
X
n=−∞
x[n]z−n. (1.21)
Questa relazione de nisce la trasformata Z bilatera della sequenza x[n]. La dierenza principale rispetto alla trasformata di Fourier sta evidentemente nel fatto che questa trasformata esiste in senso ordinario anche in molti casi in cui la trasformata di Fourier della sequenza originaria non esiste. È chiaro dalla breve discussione sul ruolo del "parametro di smorzamento" r = |z| che tale risultato deve intendersi valido solo per particolari valori di r.
