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