1

L Caponetti

Trasformata di Fourier

Filtri lineari

L Caponetti

Filtri lineari

Gli operatori locali che operano su una immaginemediante la convoluzione con maschere di pesipossono essere descritti mediante la teoria deisegnali ed in particolare dei sistemi lineari:

Trasformata di FourierProdotto di convoluzioneSistemi lineari

2

L Caponetti

Immagine digitaleUna immagine digitale è una funzione digitale del tipo:

f : D [0,255]

dove D è un dominio discreto, costituito da coppie di coordinate x,y. D è chiamato griglia di campionamento

L Caponetti

Funzione immagine

Una immagine è una funzione digitale in due dimensioni: i valori rappresentano il livello di grigio di un determinato pixel di coordinate (x,y)

x

y

O

3

L Caponetti

Immagine come segnale

Segnale: variazione di una grandezza fisica rispetto al tempo e/o allo spazio cioè

Valore della grandezza ad ogni istante di tempo (spazio)

Un segnale è una funzione dipendente da una o più variabili Le immagini stazionarie dipendono dalle coordinate spaziali: siparla di studio nel dominio dello spazio La funzione immagine considerata un segnale bidimensionale può essere studiata anche nel dominio delle frequenze –tramite la trasformata di Fourier

L Caponetti

Dominio delle frequenze

Ampiezza della trasformata di Fourier nel dominio delle frequenze (u,v) con origine nel centro

u

v

O

4

L Caponetti

Trasformata di Fourier

FondamentiSerie di Fourier: una funzione periodica può essererappresentata come somma di funzioni seno e coseno di differenti frequenze, moltiplicate per differenti coefficientiTrasformata di Fourier: le funzioni non periodichepossono essere rappresentate come integrale difunzioni seno/coseno moltiplicate per deicoefficienti

L Caponetti

1D Discrete Fourier Transform -DFT

Trasformata discreta di Fourier- DFT : un segnale digitale di estensione finita può essere rappresentato mediante la trasformata discreta di Fourier -

Sia f(x) -- {f (0), f (1), … , f (N - 1) } un segnalemonodimensionale di lunghezza N

Ssi definiscono la trasformata diretta e quella inversaDFT diretta

∑−

=

−=1

0

)2exp()()(N

x NuxjxfuF π u=0,1,…,N-1

DFT inversa

∑−

=

=1

0

)2exp()(1)(N

u NuxjuF

Nxf π x=0,1,…,N-1

5

L Caponetti

Nucleo della trasformata di Fourier

Formula di Eulero φφφ sincos je j +=

Nucleo o base della trasformata diretta - kernel

)2sin()2cos()2exp(2

Nuxj

Nux

Nuxje N

uxjπππ

π−=−=

−

Nucleo della trasformata inversa

Nuxj

eπ2 u=0,1,…,N-1

x=0,1,…,N-1

L Caponetti

2D Discrete Fourier Transform -DFT

Trasformata discreta di Fourier- 2-D DFT : un segnale digitale bidimensionale di estensione finita può essere rappresentato mediante la trasformata discreta di Fourier 2-D

Sia f(x,y) x= 0,1,…, M -1 , y= 0,1,…, N- 1una immagine di M x N pixel; si definiscono la trasformatadiretta e quella inversa bidimensionali

6

L Caponetti

2D Discrete Fourier TransformSia f(x,y) una immagine digitale, si definisce Trasformata discreta di Fourier:

( ) ( )

( ) ( )

1,...,2,1,0 e 1,...,2,1,0per

,,

1,...,2,1,0 e 1,...,2,1,0per

,1,

1

0

1

0

2

1

0

1

0

2

−=−=

=

−=−=

=

∑∑

∑∑

−

=

−

=

+

−

=

−

=

+−

NyMx

evuFyxf

NvMu

eyxfMN

vuF

M

u

N

v

Nvy

Muxj

M

x

N

y

Nvy

Muxj

π

π

DFT diretta 2-D

DFT indiretta -2D

L Caponetti

Considerazioni

Ogni termine della trasformata di Fourier F(u,v) èottenuto come combinazione lineare di tutti i valori della funzione f(x,y)I valori f(x,y) sono moltiplicati per le funzioni base seno e coseno di frequenze diverseIl dominio (u,v) è noto come dominio delle frequenze

I coefficienti F(u,v) sono detti componenti in frequenza della trasformata o coefficienti di Fourier

7

L Caponetti

Esponenziale complesso

)2sin()2cos()2exp(2

Nuxj

Nux

Nuxje N

uxjπππ

π−=−=

−

Parte reale Parte immaginaria

F(u,v) è una funzione complessa; si può quindi esprimere in coordinate polari

( ) ( ) ),(,, vujevuFvuF φ=

L Caponetti

Trasformata in 2Df(x,y)–funzione reale. La trasformata –complessa- si può esprimere in termini di ampiezza e fase:

Spettro o ampiezza

Angolo di fase

spettro di potenza

Le variabili u e v vengono chiamate variabili di frequenza

( ) ( ) ( )

( ) ( )( )

( ) ( ) 2

22

,,

,,,

,,,

vuFvuP

vuRvuIarctgvu

vuIvuRvuF

=

=

+=

ϕ

( ) ( ) φjevuFvuF ,, =

8

L Caponetti

L Caponetti

Visualizzazione della trasformata di Fourier

La trasformata di Fourier non può essere visualizzata essendo una funzione complessaSi visualizzano separatamente l’ampiezza o la fase. Per l’ampiezza si utilizza la funzione logaritmica

( ) ( )( )u,vF1logu,vD +=

Infatti l’ampiezza decresce piuttosto rapidamente all’aumentare della frequenzaLe componenti di alta frequenza tenderebbero ad essere scure se visualizzate direttamenteLa funzione log è non negativa e preserva il valore 0

9

L Caponetti

Trasformata di Fourier direttaI coefficienti F(u,v) di Fourier sono in relazione con alcune caratteristiche della immagine

F(0,0) è proporzionale al valore di brillanza medio della immagine f(x,y)

I coefficienti F(u,v) in corrispondenza di valori elevati di u,v–alte frequenze spaziali- sono in relazione alle brusche variazioni di livello di grigio – edge pixel

I coefficienti F(u,v) in corrispondenza di valori bassi di u,v, vicino all’origine –basse frequenze spaziali- sono in relazione a regioni abbastanza uniformi

L Caponetti

Esempio

inputfft

output

Smoothing filter

10

L Caponetti

ghepardo

L Caponetti

Ampiezza della trasformata del ghepardo

11

L Caponetti

Fase della trasformata del ghepardo

L Caponetti

Zebra

12

L Caponetti

Ampiezza della trasformata della zebra

L Caponetti

Fase della trasformata della zebra

13

L Caponetti

Curiosità sulla FT di immagini

Le ampiezze della FT delle immagini naturali sonoabbastanza simili tra loro

L’informazione è elevata vicino alle bassefrequenze, si va attenuando verso le altefrequenze

La maggior parte della informazione è nella fase e non nell’ampiezza

Non è molto chiaro perchè sia quasi sempre così

L Caponetti

Ricostruzionecon la fase dellazebra e l’ampiezza del ghepardo

14

L Caponetti

Ricostruzopne con la fase del ghepardo e l’ampiezza dellazebra

L Caponetti

Proprietà fondamentali

La trasformata di Fourier gode delle seguenti proprietà:

separabilità

traslazione

periodicità

simmetria

linearità

convoluzione

correlazione

15

L Caponetti

TraslazioneUna traslazione effettuata sulla funzione originale comporta una modifica della fase per la trasformata, e viceversa:

( ) ( )

( ) ( ) Nvyuxj

Nyvxuj

evuFyyxxf

eyxfvvuuF

00

00

200

200

,,

,,

+−

+

⇔−−

⇔−−

π

π

L Caponetti

Traslazione

f(x,y)exp[j2π(u0x+v0y)/N] ⇔ F(u-u0, v-v0)

Il prodotto di f(x,y) per un termine esponenziale produce nella trasformata F(u,v) una traslazione di (u0,vo). Si ha cioè che l’origine del piano (u,v) trasla nel punto (u0, v0)

In particolare se u0= v0 = N /2, si ha che l’origine (0,0) trasla al centro del piano

exp[j2π(u0x+v0y)/N] = e jπ(x+y) = (-1)x+y

f(x,y)(-1) x+y ⇔ F(u-N/2, v-N/2)

16

L Caponetti

Traslazione

E’ possibile traslare l’origine della trasformata di Fourier di f(x,y) nel centro del piano (u,v) moltiplicando f(x,y) per (-1)x+y ed effettuando quindi la trasformata di FourierÈ da notare che questa traslazione non influenza il modulo della trasformata:

( )[ ] ( )vuFNvyuxjvuF ,/2exp),( 00 =+− π

se u0= v0 = N /2

L Caponetti

SeparabilitàPotendo esprimere la funzione esponenziale complesso come prodotto lungo le due direzioni:

è possibile separare la Trasformata di Fourier lungo le due direzioni:

( ) ( )∑ ∑−

=

−

=

−−

⋅=1

0

1

0

22

,,N

x

N

y

Nvyj

Nuxj

eyxfevuFππ

( )vxF ,

Nvyj

Nuxj

Nvyuxj

eeeπππ 2.2)(2 −−+−

=

Vantaggio: la trasformata può essere calcolata mediante due successive applicazioni della trasformata monodimensionale

17

L Caponetti

[ ]∑−

=−=

1N

0xj2π2πuxF(x,v)exp

N1 F(u,v)

[ ]

−= ∑

−

=

1N

0yj2π2πvyf(x,v)exp

N1N F(x,v)

dove

y

(N-1)

(0, 0)

x

f(x,y)

N-1 v

(N-1)

(0, 0)

x

N-1

F(x,v)(N-1)

v(0, 0)

u

N-1

F(u,v)Trasf. 1D lungo colonne

Trasf. 1D lungo righe; * N

F(u,v) o f(x,y) possono essere valutate in 2 passi mediante l’applicazione ripetuta della trasformata monodimensionale o della sua inversa

L Caponetti

Rotazione

Se f(x,y) è ruotata di un angolo θ anche F(u,v) èruotata dello stesso angolo θIn maniera analoga una rotazione della trasformata F(u,v) causa una rotazione della funzione f(x,y) dello stesso angolo

18

L Caponetti

Periodicità

La trasformata di Fourier è periodica.

( ) ( )( ) ( )NvNuFNvuF

vNuFvuF++=+=

=+=,,

,,

La traformata discreta di fourier è periodica con periodo N

L Caponetti

Simmetria coniugata

Sia f(x,y) una funzione reale. La trasformata equivale alla trasformata complessa coniugata

( ) ( )vuFvuF −−= ,, *

( ) ( )vuFvuF , di coniugata complessa ,con *

L’ampiezza della trasformata è simmetrica rispetto all’origine

( ) ( )vuFvuF −−= ,,

19

L Caponetti

LinearitàLa Trasformata di Fourier è lineare:

( ) ( )

( ) ( )vuFbvuFa

yxfbyxfa

,,

,,

21

21

⋅+⋅

⋅+⋅

c

L’operatore TF che genera la trasformata di Fourier èlineare: ( ) ( ) ( )2121 fbTfaTbfafT FFF +=+

L Caponetti

Sistemi lineari e filtraggio lineare

Un processo che accetta una immagine I ( segnale ) in input e la trasforma mediante una convoluzione è dettosistema lineare

Filtro digitalecaratterizzato dallarisposta impulsiva H

Immagine IOutput -Image J = I*H

Goals del filtraggio lineare è di migliorare la qualità della immagine, enfatizzando oppure attenuando alcune caratteristiche

20

L Caponetti

Obiettivi

Smoothing – rimuove il rumore dovuto allatrasmissione, acquisizione..

Enhancement – migliora la qualità delle immagini o enfatizza feature significative, come gli edge

Deblurring – migliora la nitidezza ( sharpness) delleimmagini sfocate (blurred)

L Caponetti

Sistemi lineari

Un sistema lineare può essere caratterizzato in unodei 2 modi equivalenti mediante

Risposta impulsiva: risposta del sistemaall’impulso unitario

Risposta in frequenza: descrive come il sistemaelabora ogni componente in frequenza in unaimmagine

Le componenti in frequenza sono amplificate oppureattenuate

21

L Caponetti

)],([),( nmfTnmg =

Immagine filtrata Transformation Immagine iniziale

La trasformazione T è lineare nel caso dei sistemi lineari

Spatial Filtering

Il filtraggio nel dominio spaziale può essererappresentato come:

L Caponetti

Linear Shift-Invariance

Una trasformazione T{} is Lineare se: T(a g(x,y)+b h(x,y)) = a T{g(x,y)} + b T(h(x,y))

Shift invariant se:Nella ipotesi T(f(x,y)) = g(x,y)

Risulta T{f(x-x0, y- y0)} = g(x-x0, y-y0)

22

L Caponetti

∑ ∑

∑ ∑∞

−∞=

∞

−∞=

∞

−∞=

∞

−∞=

−−=

−−=

∗=

l k

l k

lkhlnkmf

lkflnkmh

nmfnmhnmg

),(),(

),(),(

),(),(),(

h( m , n ) =0 for (m,n) ∉ ∆

Come specificare TSe l’operatore T è lineare e invariante per traslazione (LSI), caratterizzato dalla risposta impulsiva h(m, n), la risposta g(m,n) può essere ottenuta dal prodotto di convoluzione:

In pratica h( n, m ) è di “estensione finita:”

Dove ∆ è il più piccolo insieme (detto intorno) in cui h è diversa da 0. ∆ è anche detto il supporto di h

La maschera h(m,n) èinvertita rispetto agli assi x,y

L Caponetti

∑ ∑−= −=

++=

∗=a

al

b

bklmkmfnmh

nmfnmhnmg

),(),(

),(),(),(

Correlazione

L’equazione è detta correlazione della maschera h e dellaimmagine f

Quando h(m,n) è simmetrica l’operazione di correlazione èuguale a quella di convoluzione

23

L Caponetti

Teorema di convoluzione

Nel dominio delle frequenze il prodotto di convoluzione può essererappresentato come:

G(u, v ) = H (u, v) . F (u, v )

Dove H (u, v) and F (u, v ) sono trasformate di Fourier ottenutedopo operazioni di zero-padding – cornice di zeri

L’operatore . indica la moltiplicazione punto a punto delle 2 matrici

Molte operazioni LSI possono essere interpretate nel dominio dellefrequenze come operazioni di filtraggio: ad esempio lasciarepassare di certe componenti di frequenza e non lasciare passarealtre componenti

L Caponetti

Lowpass filter

Filtro che attenua le frequenze, meno quelle più basse

Utile per un processo di smoothing cioèattenuare il rumore o sfocare i dettagli di una immagine, in modo da conservare le caratteristiche più evidenti

24

L Caponetti

Highpass filter

Filtro che attenua le frequenze, meno quelle più alte

Utile per un processo di enhancement cioèevidenziare i dettagli di una immagine ed ilcontrastorimuovere lo sfocamento

L Caponetti

Bandpass filter

Filtro che attenua le frequenze e fa passare le frequenze in una paricolare intervallo di frequenze(banda di frequenze)

25

L Caponetti

w(i,j) è una maschera 3 x 3 w1 w3w2

w4 w6w5

w7 w9w8

h =

)1,1(),1()1,1()1,(),()1,(

)1,1(),1()1,1(),(

987

654

321

+++++−+++++−+

+−+−+−−=

yxfwyxfwyxfwyxfwyxfwyxfw

yxfwyxfwyxfwyxg

(x,y)y

xf(x+1,y+1)f(x+1,y)f(x+1,y-1)

f(x,y+1)f(x,y)f(x,y-1)

f(x-1,y+1)f(x-1,y)f(x-1,y-1)Finestra immagine didimensione 3 x 3

Il valore del pixel centrale è calcolato come somma pesata di f secondo i coefficienti wi:

Operatori locali

L Caponetti

Come si calcola il prodotto di convoluzione

L’output g(m, n) è calcolato facendo scorrere la maschera su ogni pixel della immagine f(m, n) Attenzione particolare richiedono i pixel del bordodella immagine f(m, n)1. La maschera è troncata al bordo (free boundary)

e l’immagine è estesa con degli zeri. In unadimensione si ha:

=0

)()(~ xf

xfNx <≤0

01)2/( <≤+− xL 1)2/( −+<≤ LNxN

26

L Caponetti

Prodotto di convoluzione

2. L’immagine è estesa aggiungendo ai bordi righe e colonne extra – cornice. L’estensione è fattaripetendo la prima/ultima riga/colonna oppuremediante valori costanti (fixed boundary). In unadimensione si ha:

−=

)1()()0(

)(~

Nfxf

fxf

1)2/( −+<≤ LNxN

01)2/( <≤+− xL

Nx <≤0

L Caponetti

Prodotto di convoluzione

3. L’immagine è estesa in modo periodico (periodic boundary). In una dimensione si ha:

+

=)mod(

)()mod)((

)(~

Nxfxf

NNxfxf

1)2/( −+<≤ LNxN

01)2/( <≤+− xL

Nx <≤0

27

L Caponetti

Prodotto di convoluzione

In ogni caso l’output finale g(m, n) è ristretto al supporto dell’immagine originale f(m, n)

L Caponetti

Low-pass, Band-pass, High-pass filters

low-pass:

band-pass:

28

L Caponetti

2D convolution theorem example

*

f(x,y)

h(x,y)

g(x,y)

|F(sx,sy)|

|H(sx,sy)|

|G(sx,sy)|

Slide by Steve Seitz