Frequency Domain
Lecture 4
Sankalp Kallakuri
[email protected]
Frequency Domain
1D Fourier transform
F (u )
f ( x)e j 2uxdx
f ( x) F (u )e juxdu
1D Inverse Fourier transform
2D Fourier Transform
2D Continuous Forward Transform
F (u, v)
f ( x, y )e j 2 (uxvy ) 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
Mx
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 2ux / M
N y 0
f ( x, y ) e j 2vy / N
M 1
1
M
F (
x 0
x, v )e j 2ux / M
where
N 1
1
F ( x, v )
N
f ( x, y)e
y 0
j 2vy / 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
