Frequency Domain

Lecture 4
Sankalp Kallakuri
elsanky@gmail.com
 Frequency Domain

1D Fourier transform
F (u )  

f ( x)e  j 2uxdx


f ( x)   F (u )e  juxdu
1D Inverse Fourier transform

 2D Fourier Transform
2D Continuous Forward Transform
 
F (u, v)  

f ( x, y )e  j 2 (uxvy ) dxdy
2D Continuous Inverse Transform
 

 
j 2 ( ux vy )
f ( x, y )  F (u , v ) e dudv

2D Discrete Forward Transform
M 1 N 1
1
F (u, v) 
MN
 f (i ,
i 0 j 0
j ) e  j 2 ( uk / M  vl / N )

for u,v = 0,1,2….M-1

2D Discrete Inverse Transform
M 1 N 1
f (i, j )   F (u, v)e j 2 (uk / M vl / N )
u 0 v 0 for k,l = 0,1,2….M-1
 Fourier Transforms are Complex

FT can be expressed as F (u) | F (u) | e j (u )

Magnitude Spectrum | F (u) | [ R 2 (u)  I 2 (u)]1/ 2

 I (u ) 
Phase Spectrum  (u )  tan 
1

 R (u ) 

Power Spectral Density

P(u) | F (u) |2
 R 2 (u)  I 2 (u)
 2D Fourier Transform

2D fourier transform

DC level

Shifted 2D fourier transform

 Properties of Fourier Transforms
Relation between the frequency and space domain sampling rates
1
u 
Mx
Centering the Fourier Transform

 [ f ( x, y)(1) x y ]  F (u  M / 2, v  N / 2)
Mean at center
M 1 N 1
1
F (0,0) 
MN
 f ( x, y)
x 0 y 0

FT is conjugate symmetric

F (u, v)  F * (u,v)
 Convolution Theorem
Convolution of two images f(x,y) and h(x,y)

M 1 N 1
1
f ( x, y ) * h( x, y ) 
MN
 f (m, n)h( x  m, y  n)
m 0 n 0
(1)

Convolution in space and frequency domain

f ( x, y)h( x, y)  F (u, v) * H (u, v) (2)

f ( x, y) * h( x, y)  F (u, v) H (u, v) (3)

Impulse Function of strength a located at ( Xo,Yo)

M 1 N 1

 s( x, y) A ( x  x , y  y )  As ( x , y )
x 0 y 0
0 0 0 0 (4)
 Convolution Theorem
Let f(x,y) be  (x,y)
M 1 N 1
1
f ( x, y) * h( x, y ) 
MN
 (m, n)h( x  m, y  n)
m 0 n 0

1
MN
h ( x, y ) (5)

FT of unit impulse at the origin

M 1 N 1 1
1 
F (u, v) 
MN
 ( x, y)e
x 0 y 0
 j 2 ( ux / M  vy / N )
MN
(6)

To show the correspondence between spatial and frequency filters

f ( x, y) * h( x, y)  F (u, v) H (u, v)
 ( x, y) * h( x, y)   [ ( x, y)]H (u, v) (7)

h( x, y)  H (u, v)
 Spatial vs Frequency Domain Filtering

• Spatial Domain small masks allow lower computation

loads.

• Frequency domain more intuitive.

• IFT on frequency domain filters can give us

corresponding spatial domain filters and vice versa.

• Usually the essence of the filter is captured in a small

spatial domain mask.

• Sometimes it may be more efficient to transform to

frequency domain filter and the transform back.
 FT Properties: Translation

Translation in frequency domain is equivalent to :-

f ( x, y)e j 2 (u0 x / M v0 y / N )  F (u  u0 , v  v0 )

Translation in space domain is equivalent to :-

f ( x  x0 , y  y0 )  F (u, v)e j 2 (ux0 / M vy0 / N )

Centering the transform

f ( x, y)(1) x y  F (u  M / 2, v  N / 2)

Centering the image

f ( x  M / 2, y  N / 2)  F (u, v)(1) x y
 FT Properties: Distributivity and Scaling

Additive distribution property

 [ f1 ( x, y)  f 2 ( x, y)]   [ f1 ( x, y)]   [ f 2 ( x, y)]

Distributive over addition but not multiplication

 [ f1 ( x, y). f 2 ( x, y)]   [ f1 ( x, y)]. [ f 2 ( x, y)]

Scaling in the amplitude of the function

af ( x, y)  aF (u, v)
Scaling in the sampling rate
1
f (ax, by )  F (u / a, v / b)
ab
 FT Properties: Rotation
The FT and IFT pairs can be expressed in polar coordinates

x  r cos  y  r sin  u  w cos  v  w sin 

Rotation of f( r ,  ) by 0 would mean rotation of F(  ,  ) by  0

f (r ,  0 )  F (,   0 )
FT Properties: Periodicity and Conjugate Symmetry

The DFT is periodic with the dimensions of the image

F (u, v)  F (u  M , v)  F (u, v  N )  F (u  M , v  N )

So is the IDFT
f ( x, y)  f ( x  M , y)  f ( x, y  N )  f ( x  M , y  N )

Conjugate Symmetry
F (u, v)  F * (u,v)

The absolute value of the two is equal

F (u, v)  F * (u,v)
 FT Properties: Separability
The DFT is separable along the 2 dimensions
M 1
1 1 N 1
F (u, v) 
M
e
x 0
 j 2ux / M

N y 0
f ( x, y ) e  j 2vy / N

M 1
1

M
 F (
x 0
x, v )e  j 2ux / M

where
N 1
1
F ( x, v ) 
N
 f ( x, y)e
y 0
 j 2vy / N

f(x,y) F(x,v) F(u,v)

 Need for Padding

The filtering of images without padding may result in incorrect results.

1D example of convolutions without need and with need for padding

 2D padding
B

A C

A+C-1 *
D

B+D-1
 Correlation Theorem
The discrete correlation of two images is given by
M 1 N 1
1
f ( x, y)  h( x, y) 
MN
 f  (m, n)h( x  m, y  n)
m 0 n 0

The correlation of two images is an FT pair with the multiplication of the

Complex conjugate of FT of one image with the FT of the second image.

f ( x, y)  h( x, y)  F  (u, v) H (u, v)
f  ( x, y)h( x, y)  F (u, v)  H (u, v)
Correlation used for template matching
Auto- correlation
f ( x, y)  f ( x, y)  F (u, v)
2

f ( x, y)  F (u, v)  F (u, v)
2
 Fast Fourier Transform
For an M point transform:
Traditional 1D Discrete Fourier Transform takes M 2 multiply add operations
1D Fast Fourier Transform takes Mlog2 M multiply add operations

The1D DFT can be expressed as

M 1
1
F (u ) 
M
 f
x 0
( x )WM
ux

where
WM  e  j 2 / M
M  2N
M  2K

M should be a power of 2, hence obviously divisible by 2

 Fast Fourier Transform
2 K 1
1
F (u ) 
2K
 f ( x)W
x 0
ux
2K

1  1 K 1 1 K 1 u ( 2 x 1) 
   f (2 x)W2 K   f (2 x  1)W2 k
u(2 x)

2  K x 0 K x 0 
1  1 K 1 1 K 1 u 
   f (2 x)W2 K   f (2 x  1)W2 k W2 K 
ux ux

2  K x 0 K x 0 

1 K 1 1 K 1
Feven (u )   f (2 x)W2uxK
K x 0
Fodd (u ) 
K
 f
x 0
( 2 x  1)W ux
2K

for u  0,1,2,3...., K  1
 Fast Fourier Transform
1

F (u )  Feven (u )  Fodd (u )W2uK
2

We know
WMu  M  WMu & WMu  M  W2uM

1

F (u  K )  Feven (u )  Fodd (u )W2uk
2


Two K point transforms can be used to obtain a 2K point transform

http://www.relisoft.com/Science/Physics/fft.html
 Butterfly diagrams

2 point fft

2 mul 1 add
4point fft

http://www.relisoft.com/Science/Physics/fft.html
 Computational Advantage

M2 DFT
C (M ) 
M log 2 M FFT

M
=
log 2 M

becauseM  2n
2n
C ( n) 
n
 HW-3
• NON GRADED DO NOT HAVE TO
SUBMIT
• Study fourier transforms
• Do q4.4 in text book