Post on 01-May-2015
RELATORI: Sebastiano Greco, Danilo Meli, Lucio Cantone
anno accademico 2009/10
Dipartimento di Matematica e Informatica
FAST FOURIER TRANSFORM
INDICE DEGLI ARGOMENTI Numeri complessi Onde armoniche Ortogonalità di funzioni Polinomi trigonometrici Serie di Fourier Trasformata di Fourier Fast Fourier Transform (FFT) Applicazioni ed esempi
INTRODUZIONE AI NUMERI COMPLESSI
Girolamo Cardano e Rafael Bombelli introdussero i numeri complessi per descrivere le soluzioni a questo tipo di equazioni che a quei tempi erano considerate impossibili poiché non ammettevano soluzioni nell'insieme dei numeri reali.
Intorno alla metà del XVI secolo, i matematici si chiesero se le equazioni contenenti la radice quadrata di numeri negativi potessero avere soluzione.
?4
L’UNITÀ IMMAGINARIA
12 i
Per la risoluzione di questo problema è stata introdotta un’unità immaginaria tale che
iiiii
iii
iiiii
iiiii
iiiii
iii
iiiii
i
1
111
1
1
1
111
1
1
279
268
67
336
235
224
23
2
Si osservi che le potenze sono “cicliche” (di ciclo 4).
Reali
a
Immaginari
ib
C = R U I
Complessi
a+ib
In questo modo si poteva ampliare l’insieme R con un altro insieme che contenesse i numeri immaginari.
L’INSIEME C
DEFINIZIONE NUMERO COMPLESSO
Definiamo numero complesso una coppia ordinata di numeri reali (a, b).
Da esso deriva la forma algebrica di un numero complesso:
i
L’elemento a si chiama parte reale, l’elemento b si chiama parte immaginaria.
Il numero complesso denotato dalla lettera è formato dalla coppia (0,1).
ibaba ),(
L’INSIEME C
ibaz
ibaz
stabilirepuòsinonidciba
dbecasesoloeseidciba
Valgono in C le seguenti proprietà:
Dato si definisce complesso coniugato di z il numero dato daz
ibaz 22 baz Dato si definisce modulo si z il numero
OPERAZIONI FONDAMENTALI
Dati due numeri complessi si ha:),(),,( dcybax
)()(),(),( dbicadcbayx
)()(),(),( dbicadcbayx
),( bcadbdacyx
22
1
ba
iba
x
022 base
)4,3(),2,1( yx
iyx 64 iyx 64
iyx 105
5
211 i
x
5x
ix 21
Pertanto, se:
ESEMPI
INTERPRETAZIONE GEOMETRICA DEI NUMERI COMPLESSI.
E’ possibile un’altra rappresentazione dei numeri complessi utile per
trovare le radici n-esime di un numero complesso.
Dato un sistema di riferimento cartesiano, indicando con l’asse delle x
l’asse reale e con l’asse delle y l’asse immaginario, essendo il numero
complesso una coppia ordinata di numeri vi è una corrispondenza
biunivoca tra i numeri complessi e i punti del piano.
Sia
e P il punto del piano che lo
rappresenta (con P≠O), indichiamo
con
la misura di , si ha:OP
Cbaz ),(
22 ba
co sa
s inb
s inb
co sa
Il numero è il modulo (indicato anche con ) e argomento di z. z
a
barctan
RAPPRESENTAZIONE GEOMETRICA DEI NUMERI COMPLESSI.
FORMA TRIGONOMETRICA
Possiamo allora ricava la seguente forma trigonometrica di un numero complesso:
E' importante notare che l'argomento delle funzioni seno e coseno può essere incrementato di , ottenendo ancora lo stesso numero complesso.Zk
)sin(cos iz
k2
FORMULA DI DE MOIVRE
Per la potenza n-esima di z si ha la formula di De Moivre :
Tale formula è fondamentale per determinare la radice n-esima di un numero complesso.
Vogliamo trovare quei complessi
se esistono, tali che:
)sin(cos ninz nn
)sin(cos iw
zwn
RADICI N-ESIME (1)
Zk Si ha che esiste un unico e tali che:
n kn 2
Zk zwn
)2
sin2
(cosn
ki
n
kw n
k
Pertanto per , l’equazione ammette delle soluzioni che si calcolano da:
Sembrerebbe che ci siano infinite radici n-esime, in realtà quelle a due a due distinte sono n, date dalla formula precedente con
1,...,2,1,0 nk
ESEMPIO
3
2sin
3
2cos2727 33 k
ik 2,1,0k
312
3
3
4sin
3
4cos3
312
3
3
2sin
3
2cos3
30sin0cos3
ii
ii
i
RADICE N-ESIME (2)
3 1
kr
n
ki
n
krk
2sin
2cos 1,...,2,1,0 nk
Un caso particolare è dato dalle radici n-esime dell’unità. Esse sono indicate con e sono date da:
Esse si dispongono nel piano complesso lungo la circonferenza unitaria, ai vertici di un poligono regolare con n lati che ha un vertice in (1,0).
FORMA ESPONENZIALE DEI NUMERI COMPLESSI
I numeri complessi si possono rappresentare anche in forma esponenziale:
ieiibaz sincos
sincos iei
dove
è detta Formula di Eulero.
Essa ci mostra una profonda relazione fra le funzioni trigonometriche e la funzione esponenziale complessa.
FORMULE DI EULERO
La formula di Eulero permette anche di intepretare le funzioni seno e coseno come semplici varianti della funzione esponenziale.
sincos iei sincos ie i
Sommando o sottraendo le formule di Eulero e risolvendo le equazioni ottenute sia per il seno sia per il coseno.
Ri
ee ii
2sin
2
cos
ii ee
POTENZA COMPLESSA
iyxz ez
)sin(cos yiyee xz
Dato un numero complesso chiameremo potenza di base ed esponente il numero complesso:
2cos
iziz eez
Cz
2cos
iziz eez
Cz
i
eez
iziz
2sin
Questa equazione contiene come caso particolare la Formula di Eulero. Hanno significato le seguenti:
FORMULA DI EULERO
01ie
È da notare che la formula di Eulero dà origine ad un'equazione considerata tra
le più affascinanti della matematica (nota come identità di Eulero), in quanto
mette in relazione tra loro i cinque numeri più importanti ed utilizzati (e, i, π, 1,
0)
APPLICAZIONI
In matematica: – Teoria dei numeri– Integrali impropri– Equazioni differenziali– Frattali.
In fisica: – Dinamica dei fluidi– Meccanica Quantistica– Relatività.
APPLICAZIONI: ANALISI DEI SEGNALI
I numeri complessi vengono utilizzati nell'analisi dei segnali e in tutti i campi dove si trattano segnali che variano sinusoidalmente nel tempo, o anche semplicemente periodici.
Il valore assoluto di |z| è interpretato come la ampiezza del segnale mentre l'argomento di z è interpretato come la fase.
I numeri complessi rendono possibile anche l'analisi di Fourier, che rende possibile scomporre un generico segnale tempo-variante in una somma di infinite sinusoidi: ogni sinusoide è scritta come un singolo numero complesso
dove ω è la pulsazione della sinusoide e z la sua ampiezza.
tizetf
L’IMPORTANZA DELLA TEORIA DI FOURIERLe funzioni di una variabile reale f(t), una volta descritte da una legge matematica (una
formula, un algoritmo) il modo più comune di “memorizzarle” è compilare una tabella
con colonne.
La prima colonna contiene il valore della variabile indipendente t, e la seconda il valore
della variabile dipendente f(t). Questa “filosofia” di rappresentazione della funzione si
chiama “analisi nel dominio del tempo” ma non è l’unica. Se consideriamo i polinomi
essi non sono molto adatti per l’approssimazione. Essi oscillano e vanno all’infinito per
grandi valori assoluti dell’argomento x, ma tra altri insiemi di funzioni che
approssimino ogni funzione continua in un intervallo chiuso vi sono i polinomi
trigonometrici. Tali funzioni si calcolano facilmente, mediante serie rapidamente
convergenti; le loro derivate sono ancora seni e coseni e così anche i loro integrali.
Hanno anche proprietà di ortogonalità e di periodicità che non hanno invece i polinomi.
L’approssimazione mediante polinomi trigonometrici è nota come approssimazione di
Fourier. . Una possibile alternativa è offerta quindi dalla Teoria di Fourier il cui
nocciolo fondamentale sono le funzioni armoniche: seno e coseno.
In oltre l’errore di tale approssimazione è dato in termini della funzione stessa e non
dipende, come nel caso dei polinomi, dalle sue derivate di alto ordine.
ONDE ARMONICHE
)cos(
)(
xA
xAsen
fase
Tpulsazione
ampiezzaA
Dove
)2(
:
xcsenxb
xbsenxa
cos
cos
senc
b
sena
cos
Le frequenze armoniche sono l'insieme delle frequenze multiple della frequenza base di un'onda. Quindi, per esempio, un'onda che non sia perfettamente sinusoidale che abbia la frequenza di 100 Hz sarà composta, di fatto, da una frequenza fondamentale, cioè una sinusoide da 100 Hz, e da numerosissime frequenze armoniche, da 200, 300, 400, 500 Hz, e così via, con ampiezze variabili.
E’ possibile rappresentare delle funzioni o dei segnali come sovrapposizione di onde fondamentali (armoniche).
ONDE ARMONICHE (2)
ONDE ARMONICHE (3)
FUNZIONI COME VETTORII vettori sono oggetti assai familiari che tutti abbiamo conosciuto durante precedenti corsi di studi poiché sono utilissimi per descrivere forze, spostamenti, velocità ecc.
Se la funzione è un vettore quindi gli spazi funzionali (insiemi di funzioni) sono anche spazi vettoriali.
Anche per le funzioni possono essere definite operazioni analoghe a quelle definite per i vettori. Per questo motivo possiamo dire che le funzioni sono assimilabili a dei vettori.
Di particolare importanza in questo contesto è l’operazione di prodotto interno definita per i vettori ordinari.
FUNZIONI A QUADRATO SOMMABILE
b
a
dxxf2
Consideriamo le funzioni reali definite per ogni valore reale che abbiano però la proprietà di essere tali per cui esse stesse elevate al quadrato formino un'area rispetto all'asse delle x che abbia un valore finito. Ricordiamo che tale area è l'integrale del quadrato della funzione:
Se questo integrale converge tali funzioni sono dette a quadrato sommabile e costituiscono uno spazio vettoriale perché su esse sono definibili le solite operazioni (addizione, sottrazione e moltiplicazione per uno scalare).
Mentre i coefficienti di Fourier e si possono definire formalmente per ogni funzione per la quale ha senso considerare gli integrali che forniscono i loro valori, se la serie così definita converga effettivamente alla f(x) dipende dalle proprietà specifiche di tale funzione.La conclusione più semplice si ha quando la f(x) è a quadrato sommabile; in tal caso
cioè si ha la convergenza nella norma dello spazio L2
dove lo spazio L2 è lo spazio infinito-dimensionale delle successioni di numeri reali (o complessi) a quadrato sommabili.
0)(lim2
dxeFxf
N
Nk
ikxk
N
IMPORTANZA DELLE FUNZIONI A QUADRATO SOMMABILE
DEFINIZIONE DI ORTOGONALITÀ
Le funzioni di una famiglia si dicono mutualmente ortogonali rispetto ad un prodotto scalare definito per quello spazio se:
0
0, lk
.,. k
lk
lk
b
a
lk dxxx 0
Un sistema di infinite funzioni definite in [a,b] e ivi generalmente continue e integrabili, si dice ortogonale se per qualsiasi coppia di indici k e l fra loro distinti si ha:
n
L’INSIEME DELLE FUNZIONI TRIGONOMETRICHE
Consideriamo l’insieme B delle seguenti funzioni:
nxx cos nxx sin ......2,1,0n
Per n=0 si ha cos 0x=1 e sin 0x=0.
Una qualunque combinazione lineare di funzioni di B produce una funzione periodica di periodo 2π.
La teoria delle serie di Fourier si occupa sostanzialmente del problema inverso: data una funzione periodica di periodo 2π, ci si chiede se essa può essere espressa come combinazione lineare di funzioni di B.
POLINOMI TRIGONOMETRICI
La loro base è costituita dalla famiglia delle funzioni trigonometriche:
Tali funzioni sono a due a due ortogonali in un intervallo
di ampiezza e pertanto sono linearmente indipendenti, quindi formano una base.
,...3cos,2sin,2cos,sin,cos,1 xxxxx
20 x
POLINOMI TRIGONOMETRICI (RELAZIONI DI ORTOGONALITÀ)
lkdxlxkx
lk
lkse
lkse
lkse
dxlxkx
lk
lkse
lkse
lkse
dxlxkx
,0sincos
,
0,0
0,
,0
sinsin
,
0,2
0,
,0
coscos
2
0
2
0
2
0
POLINOMI TRIGONOMETRICI (2)
x2
xL
,...3
cos,2
sin,2
cos,sin,cos,1 xL
xL
xL
xL
xL
LxL x hx
Analogamente si ha l’ortogonalità in
e, generalmente, su ogni intervallo di ampiezza
Cambiando scala lungo l’asse introducendo il fattore , le funzioni
sono ortogonali su . Inoltre, la sostituzione di con
non inficia l’ortogonalità.
dove abbiamo indicato con ,anziché con a0, il coefficiente di cos(0x)
mentre il coefficiente di sin(0x) non ha interesse perché sin(0x) = 0.
Ci si chiede se le funzioni di B costituiscono una “base” per scrivere una generica funzione periodica di periodo 2π come combinazione lineare, magari infinita (serie) di funzioni appartenenti a B, cioè:
:F
nxbnxaxbxaxbxa nn cos....sincos0sin0cos 1100
1
0 cos2 k
kk kxsenbkxaa
xF
20a
In questo modo, i coefficienti a0, ak, bk (k=1,2,…) sono numeri complessi che dipenderanno da come costruiremo la F(x).
x
SERIE DI FOURIER
1
0 coscoscos2
cosk
kk lxkxsenbkxalxa
lxxF
2
0 1
2
01
2
0
2
0
0 cossincoscoscos2
cosk
kk
k dxlxkxbdxlxkxadxlxa
dxlxxF
Possiamo usare l’ortogonalità nell’espansione formale di F(x). Per far questo, determiniamo tali coefficienti moltiplicando formalmente entrambi i termini della F(x) sia per cos(lx) che per sen(lx).
Integrando ambo i membri ed utilizzando la proprietà distributiva, si ha:
1
0 cos2 k
kk lxsenkxsenbkxalxsena
lxsenxF
2
0 1
2
01
2
0
2
0
0 sinsinsincossin2
cosk
kk
k dxlxkxbdxlxkxadxlxa
dxlxxF
SERIE DI FOURIER (2)
dxlxxFa
2
0
)]cos()([2
10
dxlxxFal
2
0
)]cos()([1
dxlxxFbl
2
0
)]sin()([1
...2,1l
...2,1l
...2,1l
Distinguendo i casi per: k=l≠0 k=l=0 k ≠lriferiti alle relazioni di ortogonalità seno coseno viste precedentemente, si dimostra che i coefficienti di Fourier in forma trigonometrica sono:
SERIE DI FOURIER (3)
Gli al, bl calcolati in tal modo si possono estendere ad un sistema generale di funzioni ortogonali
dove ω(x) e’ una funzione peso su (-1,1), ovvero una funzione non negativa e integrabile in (-1,1).
Se:
allora:
sono ancora i coefficienti di Fourier
b
a
ji dxxxfxf 0)()()(
j
0
ji
ji
)()(0
xfaxFii
i
dxxxfxFab
a
ii
i)()()(
1
SERIE DI FOURIER (4)
Come caso particolare possiamo prendere un sistema di polinomi algebrici di grado k, {pk ,k=0,1,…}, mutualmente ortogonali su (-1,1) rispetto ad ω. Ovvero come prima:
1
1
0)()()( dxxxpxp ji jise
dxxxgxfgf )()()(),(1
1
Poniamo e21),( fff dove ..)(., e sono,
rispettivamente, il prodotto scalare e la norma per lo spazio di funzioni
1
1
222 )()(,)1,1(:)1,1( dxxxfCfLL
Per ogni funzione 2LF la serie
,),(ˆ,ˆ
20
k
kk
k
kk
p
pFfconpfSF
è detta serie di Fourier (generalizzata) di F ed è il coefficiente k-esimo di Fourier.
kf̂
SERIE DI FOURIER (5)
SERIE DI FOURIER (IN FORMA COMPLESSA)
La serie di Fourier è una rappresentazione di una funzione periodica (che in una accezione con caratteristiche di semplicità si chiede abbia periodo 2π) mediante una somma di funzioni periodiche.
inxex
Grazie alla formula di Eulero, la precedente serie può essere espressa equivalentemente mediante funzioni seno e coseno.
in particolar modo se , la serie di Fourier è espressa come:
2
02
0
2
0 )(2
1)(
ˆ
,...2,1,0,)(
)(ˆ)(
dxexF
dxee
dxexF
f
kex
xfxF
ikx
ikxikx
ikx
k
ikxk
k
kk
)2,0(2 LF
SERIE DI FOURIER (IN FORMA COMPLESSA) (2)
dove
e
Se generalizziamo per una funzione di periodo L, possiamo allora scrivere che:
k
kxL
i
kecxF2
)(
dove i coefficienti ck sono dati dalla relazione:
dxexFL
cL
kxL
i
k
0
2
)(1
In cui la condizione di ortogonalità è:
0
00
0
22
kmL
kmdxee
Lkx
L
imx
L
i
SERIE DI FOURIER (IN FORMA COMPLESSA) (3)
LA TRASFORMATA DI FOURIER (TOPICS)
Una funzione periodica puo’ essere espressa come somma di seni e/o coseni di differenti frequenze e ampiezze.
(Serie di Fourier).
Una funzione di durata finita puo’ essere espressa come integrale di seni e/o coseni, moltiplicati per opportune funzioni peso
(Trasformata di Fourier).
Dato che tratteremo funzioni di durata finita (le immagini) , ci interesseremo della Trasformata di Fourier.
TRASFORMATA DI FOURIER (2)
Questa rappresentazione coinvolge le armoniche complesse ovvero le funzioni
con numeri d’onda:
L’insieme di questi numeri d’onda è detto lo spettro dei numeri d’onda che è un insieme discreto cioè consiste di numeri separati ad ognuno dei quali corrisponde un’armonica nell’espansione (1.1) con un’ampiezza complessa data dalla (1.2).
)1.1()(
n
L
nxi
necxf
,...2,1,0
)2.1()(2
1
n
L
L
L
nxi
n dxexfL
c
Sia f (x) definita nell’intervallo - L < x < L. essapuò essere rappresentata dalla sua serie di Fourier in forma complessa:
dove:
xikne
xikne
...,2,1,0 nL
nkn
Allora, per L molto grande lo spettro diviene “denso” e molto piccolo. Al limite, per la somma diventa un integrale e quindi:
dove è la distanza tra due punti vicini rappresentanti i numeri d’onda nello
spettro.
Pertanto la (1.1) può essere scritta come:
Lo spettro discreto diventa continuo per e ovvero ogni
armonica ha ampiezza nulla. Le (2.1) e (2.3) sono le trasformate di Fourier di cui la (2.1) è quella diretta e la (2.3) quella inversa.
)1.2()(2
1)(ˆ dxexfxf ikx
)2.2()(ˆ)(2
1)(
2
1kkf
Ldxexfdxexf
Lc n
xikb
a
xikb
an
nn
Lk
n n
xikn
xikn LxLkekfecxf nn )(ˆ)(
kL
)3.2()(ˆ)(
xdxexfxf ikx
L nc
Per semplicità, sia f (x) nulla al di fuori dell’intervallo [a,b] e introduciamo:
che in realtà si estende ad [a,b]. Se L è sufficientemente grande possiamo riscrivere la (1.2) nella forma:
•Algoritmo ottimizzato per il calcolo della trasformata discreta di Fourier
•E’ importante per una grande varietà di applicazioni, tra cui:•Trattamento dei segnali digitali•Soluzione di equazioni differenziali e derivate parziali•Algoritmi per moltiplicare numeri interi di grandi dimensioni prodotto di due trasformate, nel senso che una trasformata segue l’altra.
•L’anti trasformata di Fourier e’ uguale alle DFT, ma con esponente di segno opposto e 1/N fattore, qualsiasi algoritmo FFT può
essere facilmente invertito.
FFT (FAST FOURIER TRANSFORM)
Data una n-pla di coefficienti di Fourier a0, a1, a2, …. , aM, aM+1
e’ possibile verificare che se li volessimo calcolare tramite un calcolo diretto, tale calcolo implica circa M2 moltiplicazioni ed M2 addizioni, per cui un algoritmo prenderebbe tempo O(M2), date le M2 operazioni.
E’ possibile utilizzare un “bound” più stretto, fino ad arrivare ad una complessità dell’ordine di MlgM,facendo uso della “fattorizzazione”
cioè M può essere fattorizzato come:M = G * H
dove per risultato di tale fattorizzazione avremo circaM (G + H)
operazioni al posto delle M2 operazioni precedenti.Se
M = m1 * m2 * m3 * … * mk
allora il numero di operazioni sarà:M(m1 + m2 + m3 + … + mk)
Nel caso più favorevole, cioè che M sia una potenza di 2
M = 2k
si avranno M(2k) operazioni, dove k = lg2M.
Quindi, se M e’ molto grande, si avrà un grande guadagno perché il numero delle operazioni da M2 si ridurrà a MlgM.
Esempio:Campionamento a 1000 punti 1000 moltiplicazioni che richiedono un tempo piu’ elevato rispetto alle addizioni.Se il tempo di esecuzione per una moltiplicazione e’ ad esempio 10 millesimi di secondo, saranno necessari 100 secondi per svolgere solamente le moltiplicazioni, il che rende impossibile l’analisi di una forma d’onda in tempo reale.
Sia ck il generico coefficiente da calcolare.
Il cuore del metodo e’ scrivere i due indici k e p in modo opportuno.Dividiamo k per G :
k = k1G + k0
e dividiamo p per H: p = p1H + p0
con:k0 < Gk1 < Hp0 < Hp1 < G
Si ha:
dove abbiamo usato il fatto che:
N.B. La doppia somma copre gli stessi numeri della somma originale.
Ci sono H termini in questa somma, uno per ogni p0.
Poniamo:
Quindi:
Un conteggio delle operazioni mostra che sono proporzionali a GH(G + H).
La Trasformata di Fourier mantiene un ruolo cardine nell’ image processing, anche se altre trasformate oggi sono in uso in molte applicazioni.Abbiamo visto che la Trasformata di Fourier di una funzione continua f(x) di variabile reale x e’ definita come:
Con u frequenza (u = 2π/T) e T periodo.Inoltre, dato che:
La F(u) e’ composta dalla somma di infiniti termini sinusoidali e cosinusoidali, ed ogni valore di u determina la frequenza della coppia seno-coseno corrispondente.
LA TRASFORMATA DI FOURIER ALLE IMMAGINI
La “anti trasformata” e’ definita come:
Ovviamente la trasformata e la anti trasformata esistono se f(x) e’ continua ed integrabile e se F(u) e’ integrabile.Estendendo al caso bidimensionale (le immagini), definiamo:
Spettro:
Fase:
Densità spettrale:
La trasformata della sequenza bidimensionale f(x,y) e’:
con: u = 0, …, M-1 e v = 0, …, N-1
Naturalmente u e v sono gli indici assi frequenze discretizzati, mentre M ed N sono le dimensioni, in pixel, della immagine.La anti trasformata invece e:
con:x = 0, …, M-1 e y = 0, …, N-1
Nel caso di immagini campionate in una griglia quadrata (M = N), la trasformata e la anti trasformata saranno:
Inoltre, il campionamento della f(x,y) ha luogo in una griglia bidimensionale con passi Δx e Δy.
Esempio di calcolo della DFT…
Per provare quanto detto finora, consideriamo il caso di una sola variabile x, e consideriamo la f(x) nel seguente modo:
La nostra funzione f(x) e’ campionata a partire da x0=0.25, ed otterremo gli N=5 campioni.
Andando ad applicare la formula:
otterremo i valori degli N=5 campioni della trasformata:
Proseguendo…
Ricapitolando, tutti i valori della funzione f(x) contribuiscono per la costruzione dei vari campioni della trasformata F(x).In modo del tutto analogo, tutti i campioni della trasformata F(x) contribuiscono, in fase di antitrasformazione, a ciascuno dei valori della funzione f(x). I campioni della trasformata F(x) sono generalmente complessi, per cui ognuno ha sia modulo che fase, pertanto dall’esempio con i valori calcolati nelle slides precedenti, avremo:
E cosi via dicendo per i restanti valori degli N=5 campioni.
Nel caso bidimensionale (x,y), un impulso che e’ approssimato da un piccolo cerchio bianco circoscritto da un rettangolo su fondo
nero, in una immagine di 200 x 200 pixel:
I differenti livelli di grigio nella immagine di intensita’ dello spettro evidenziano le ampiezze decrescenti dei diversi lobi.
Esempi
Qui abbiamo la trasformata di una immagine di 200 x 200 pixel e 256 livelli di grigio:
La fase (fig.3) contiene l’informazione relativa al dove le strutture periodiche evidenziate nella DFT sono collocate.L’ampiezza (fig.2) contiene l’informazione relativa al fatto che una certa struttura periodica è presente nell’immagine.
Utilizzo della Trasformata di Fourier
Buona parte delle analisi effettuate sulle immagini vengono effettuate nel dominio spaziale.
Se vogliamo eliminare informazioni legate ad errori periodici e’ necessario operare nel campo delle frequenze, prima di
analizzare l’immagine stessa.
La trasformata di Fourier (FFT) ci permette di convertire l’immagine da analizzare nel campo delle frequenze.
Una immagine puo’ avere un rumore periodico, visibile ad esempio sotto forma di un banding causato da alcuni processi di conversione in formato digitale, o dal sensore CCD.
Nel campo delle frequenze, tale rumore ricorrente si riduce ad un limitato set di alte frequenze spaziali.
E’ possibile impiegare delle tecniche o particolari algoritmi per isolare e rimuovere le frequenze indesiderate dalla immagine.
Una volta eliminate tali frequenze, e convertendo l’immagine FFT verso il dominio spaziale (antitrasformata FFT), otterremo una nuova immagine in cui il rumore pediodico risultera’ ridotto, se non eliminato, salvaguardando le altre informazioni.
ESEMPIO SULL’ UTILIZZO DELLA TRASFORMATA DI FOURIER.
Prendiamo come esempio la seguente immagine:
Nell’area ingrandita possiamo notare la presenza di un effetto “banding” verticale, che maschera in parte l’informazione originaria presente.
Convertendo nel dominio delle frequenze la regione ingrandita
Possiamo notare:•Due bracci verticali ed orizzontali•Una zona piu’ densa al centro
Inoltre, in corrispondenza del braccio orizzontale:•Una zona piu’ scura sul bordo destro e sinistro
Passando ad una rappresentazione 3D della FFT, otteniamo il seguente grafico, possiamo osservare meglio le peculiarita’ della superficie calcolata.
1. Mascheriamo le zone che vogliamo utilizzare (poligoni bianchi) in corrispondenza dei due bracci (verticali ed orizzontali) e delle due zone piu’ esterne.
2. Calcoliamo la trasformata inversa di Fourier.
L’immagine a destra non presenta piu’ l’effetto di “banding” verticale, e le informazioni sono piu’ chiare e leggibili.
Ecco l’effetto ottenuto grazie all’utilizzo della FFT:
Puo’ accadere che si vogliano invece mantenere le informazioni legate al rumore periodico e quantomeno alle informazioni legate alle alte frequenze presenti nell’ immagine.
La procedura e’ la stessa del precedente esempio, solo che al posto di mascherare le informazioni relative alle frequenze periodiche, si utilizzera’ una maschera per nascondere le informazioni presenti nell’ immagine.
Qui e’ possibile vedere come lo spettro di Fourier evidenzia la chiara presenza di un errore periodico rappresentato da una serie di bande semi-orizzontali piu’ chiare.
Mascherando la parte centrale ed effettuando in procedimento inverso otteniamo una immagine in cui sono presenti solo le informazioni legate al rumore periodico.
Nel caso di digitalizzazione di immagini stradali, e’ possibile vedere come le strade siano piu’ visibili nella immagine di destra…
MANIPOLAZIONE DELLO SPETTRO
Le circonferenze (dal centro) racchiudono il 90, 93, 95, 99 e il 99,5% della potenza spettrale totale.
CURIOSITA’…
Motivo della presenza delle due bande verticali ed orizzontali sullo spettro di Fourier di una immagine:
La FFT calcola la trasformata di Fourier di segnali 2D periodici:L’algoritmo periodicizza l’immagine presa in input, replicandola in tutte le
possibili posizioni adiacenti senza sovrapposizione in modo da piastrellare tutto il piano x-y.
La FFT calcola la trasformata di Fourier di questa super immagine periodicizzata che si estende fino ad infinito in tutte le direzioni del piano. Dato che l’immagine iniziale non e’ un segnale periodico, e questa sua replicazione in tutte le posizioni adiacenti genera dei salti di intensita’ molto forti ai bordi, la dove il bordo destro di congiunge al bordo sinistro, ecc.
L’insieme di queste discontinuita’ di salto distribuite su una griglia ortogonale nel dominio della super immagine e’ in parte responsabile di tale effetto “a croce”.
Per eliminare tale effetto bisogna apodizzare l’immagine prima della FFT, esempio moltiplicandola con una funzione a “campana” (gaussiana), che vada a zero in modo continuo sui bordi.
BIBLIOGRAFIA
I numeri complessi – Rosa Maria Pidatella (Dispense)Wikipedia – L’enciclopedia liberaAnalisi I - Carlo MirandaDodero, Baroncini, Manfredi – Elementi di Matematica 3www.schgor.com/ElabNumSegn/ENS12.htmhttp://www.keyobs.be/fr/ebonino/html/fft.html