DFT Domain Image Filtering - New York University

DFT Domain Image Filtering

Yao Wang

Polytechnic Institute of NYU, Brooklyn, NY 11201

With contribution from Zhu Liu, Onur Guleryuz, and

Gonzalez/Woods, Digital Image Processing, 2ed

Lecture Outline

?

?

?

?

?

?

1D discrete Fourier transform (DFT)

2D discrete Fo

Fourier

rier transform (DFT)

Fast Fourier transform (FFT)

DFT domain filtering

1D unitary transform

2D unitary transform

Yao Wang, NYU-Poly

EL5123: DFT and unitary transform

2

Discrete Fourier Transform (DFT):

DTFT for Finite Duration Signals

If the signal is only defined for n ? 0,1,..., N ? 1 :

Fourier transform becomes :

N ?1

F ' (f) ? ? f (n) exp(? j 2?fn),

f ? (0,1)

n ?0

Sampling F ' (f) at f ? k/N, k ? 0 ,1,...,N-1, and rescaling yields :

Forward transform (DFT) :

1 N ?1

k

k

F (k ) ? F ' (

)?

f

(

n

)

exp(

?

j

2

?

n), k ? 0,1,..., N ? 1

?

N

N

N n ?0

Inverse transform

f

(

(IDFT)

):

1

f(n) ?

N

Yao Wang, NYU-Poly

N ?1

k

F (k ) exp( j 2? n), n ? 0,1,..., N ? 1

?

N

k ?0

EL5123: DFT and unitary transform

3

Property of DFT (1)

? Periodicity F (k ) ? F (((k )) N ), k ? 0 or k ? N .

where ((k )) N

represents

p

modulo N .

N ?1

(k ? mN )

Proof F (k ? mN ) ? 1

f (n) exp(? j 2?

n)

?

N

N n ?0

1 N ?1

k

?

f

(

n

)

exp(

?

j

2

?

n ? j 2?mn) ? F (k )

?

N

N n ?0

F(k)

A

A

A

G

G

G

B

B

B

C

F

C

F

C

F

D

D

D

E

E

E

0

low

N-1 N

high

low

Note: Highest frequency is at k=[N/2]. k=0,1, N-1 represent low frequency.

Yao Wang, NYU-Poly

EL5123: DFT and unitary transform

4

Property of DFT (2)

? Translation

f (((n ? no )) N ) ? F (k ) exp{{? j 2? (kn

k o / N )}

f (n) exp{ j 2?k0 n / N } ? F (((k ? k0 )) N ).

¨C Special

p

case

? N is even, k0 = N/2.

f (n) exp{ j?n} ? f (n)(?1)

?

n

N

F (((k ? )) N ).

)

2

Shifting

g the frequency

q

y up

p by

y N/2

Yao Wang, NYU-Poly

EL5123: DFT and unitary transform

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download