2-D DISCRETE FOURIER TRANSFORM

DEFINITION
– j 2π  ------- + -----
M –1N –1 mk nl
1  M N
F ( k, l ) = ---------
MN ∑ ∑ f ( m, n ) ⋅ e forward DFT
m = 0n = 0
+ j2π  ------- + -----
M – 1N – 1 mk nl
 M N
f ( m, n ) = ∑ ∑ F ( k, l ) ⋅ e inverse DFT
k=0l=0
• The DFT is a transform of a discrete, complex 2-D array of size M x
N into another discrete, complex 2-D array of size M x N
Approximates the Continuous Fourier Transform (CFT) under certain conditions
Both f(m,n) and F(k,l) are 2-D periodic
Alternate definitions:
1 1
• --------- in inverse definition instead, or -------------- in forward and inverse definitions (“unitary”)
MN MN
• doesn’t matter as long as consistent
ECE/OPTI533 Digital Image Processing class notes 188 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
RELATION OF THE DFT TO THE CFT
• One view of the DFT is as an approximation to the CFT
• “ recipe” to convert CFT to DFT:
1. sample f(x,y)
1
f ( x, y ) ⋅ -------comb ( x ⁄ X , y ⁄ Y )
XY
2. truncate to MX x NY
1
f ( x, y ) ⋅ -------comb ( x ⁄ X , y ⁄ Y ) ⋅ rect ( x ⁄ MX , y ⁄ N Y )
XY
3. make periodic
1
f ( x, y ) ⋅ -------comb ( x ⁄ X , y ⁄ Y ) ⋅ rect ( x ⁄ MX , y ⁄ NY )
XY
= f p ( m, n )
1
❉ ❉ ---------------------- comb ( x ⁄ MX , y ⁄ NY )
MX ⋅ NY
, i.e. the periodic extension of a 2-D array f(m,n) with sample intervals X=Y=1
ECE/OPTI533 Digital Image Processing class notes 189 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
4. take CFT
replicate (aliasing smooth (leakage
occurs here) occurs here) sample
[ F ( u, v ) ❉ ❉ comb ( uX , vY ) ❉ ❉ MX ⋅ NY sinc ( uMX , vNY ) ] ⋅ comb ( uMX , vNY )
= F p ( k, l )
, i.e. the periodic extension of a 2-D array F(k,l) with sample intervals 1/X=1/Y=1
• The arrays f and F are both discrete and periodic in space and
spatial frequency, respectively
ECE/OPTI533 Digital Image Processing class notes 190 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
CALCULATION OF DFT
• Both arrays f(m,n) and F(k,l) are
periodic (period = M x N) and
sampled (X x Y in space, 1/MX x 1/NY in frequency)
• In the CFT, if one function has compact support (i.e. it is space- or
frequency-limited), the other must have ∞ support
• Therefore, aliasing will occur with the DFT, either in space or
frequency. If we want the DFT to closely approximate the CFT,
aliasing must be minimized in both domains
• The Fast Fourier Transform (FFT) is an efficient algorithm to
calculate the DFT that takes advantage of the periodicities in the
complex exponential
Can use 1-D FFT for 2-D DFT (later)
ECE/OPTI533 Digital Image Processing class notes 191 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
ARRAY COORDINATES
• The DC term (u=v=0) is at (0,0) in the raw output of the DFT (e.g.
the Matlab function “fft2”)
raw output of DFT reordered output of DFT
DC
Quad I II III IV
DC
IV III II I
• Reordering puts the spectrum into a “physical” order (the same
as seen in optical Fourier transforms) (e.g. the Matlab function
“fftshift”)
• N and M are commonly powers of 2 for the FFT. Therefore, the DC
term is at (M/2,N/2) in the reordered format for (0,0) indexing
and at (M/2+1,N/2+1) for (1,1) indexing
ECE/OPTI533 Digital Image Processing class notes 192 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
SAMPLE INTERVALS
• Constraints
product of physical sample intervals in x and u, y and v: XU = 1/M, YV = 1/N
sampling (replication) frequency in u and v: us = 1/X, v: vs = 1/Y
folding frequency in u and v: uf = 1/2X, vf = 1/2Y
• For images, a convenient, normalized set of units is
X = Y = 1 pixel
• Therefore,
U = 1/M cycles/pixel, us = 1 cycle/pixel, uf = 1/2 cycle/pixel
V = 1/N cycles/pixel, vs = 1 cycle/pixel, vf = 1/2 cycle/pixel
• Note, in reodered DFT format, uf and vf are along the first row
and columns of the array
ECE/OPTI533 Digital Image Processing class notes 193 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM 1
Reordering the 2-D DFT 0.8
0.6
0.4
f(m,n)
• “origin-centered” display 0.2
0
40
30 40
20 30
20
10
10
l 0 0
25
20
4 3 15
10 |F(k,l)|
5
2 1 2 0
40
30 40
20 30
k 10
20
3 4
10
25 0 0
20
15
origin-centered
10
5
|F(k,l)|
0
40
30 40
20 30
20
10
10
0 0
ECE/OPTI533 Digital Image Processing class notes 194 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
Aliasing in the frequency domain
• DFT of discrete approximation to a rect(x/W,y/W) function
1 3x3 f(m,n) 10
|F(k,l)| |F(k,l)| - |F(u,v)|
0.14
0.8 8 0.12
0.1
0.6 6
0.08
0.4 4 0.06
0.04
0.2 2
0.02
0 0 0
40 40 40
30 40 30 40 30 40
20 30 20 30 20 30
20 20 20
10 10 10
10 10 10
0 0 0 0 0 0
5x5
1 25
0.14
0.8 20 0.12
0.1
0.6 15
0.08
0.4 10 0.06
0.04
0.2 5
0.02
0 0 0
40 40 40
30 40 30 40 30 40
20 30 20 30 20 30
20 20 20
10 10 10
10 10 10
0 0 0 0 0 0
9x9
1 100
0.14
0.8 80 0.12
0.1
0.6 60
0.08
0.4 40 0.06
0.04
0.2 20
0.02
0 0 0
40 40 40
30 40 30 40 30 40
20 30 20 30 20 30
20 20 20
10 10 10
10 10 10
0 0 0 0 0 0
ECE/OPTI533 Digital Image Processing class notes 195 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
Digital image power spectrum (squared amplitude of F) coordinates
(0,0)
(u,v)=(-0.5,-0.5)
cycles/pixel
(M/2,N)
(u,v) = (+0.5-1/N,0)
cycles/pixel
(M,N)
(u,v)=(+0.5-1/N,
+0.5-1/M)
(M,N/2), (u,v) = (0,+0.5-1/M) cycles/pixel cycles/pixel
ECE/OPTI533 Digital Image Processing class notes 196 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
EXAMPLES OF IMAGE POWER SPECTRA
desert streets
fields railroad
ECE/OPTI533 Digital Image Processing class notes 197 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
DISPLAY OF POWER SPECTRA
• Large dynamic range
amplitude at zero-frequency dominates
Power Spectra Display
• Mask zero-frequency term to zero
• Contrast stretch with square-root transform
• Repeat constrast stretch as needed
ECE/OPTI533 Digital Image Processing class notes 198 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
Example
m=0
n=0 n=N-1
m=M-1 power spectrum DC masked due to
periodic
border
at m=0
and M-1
due to
periodic
border
at n=0
and N-1
2 2 4 2 8 2
ECE/OPTI533 Digital Image Processing class notes 199 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
MATRIX REPRESENTATION
This section is from lecture notes by my late friend and colleague, Professor Steve
Park, of the College of William and Mary, Virginia
• Compact notation
• Generalizable to other transforms
– j 2π  ------- + -----
M –1N –1 mk nl
1  M N
• DFT definition F ( k, l ) = ---------
MN ∑ ∑ f ( m, n ) ⋅ e
m = 0n = 0
– j 2π  -------
mk
 M
W M ( m, k ) = e
let , where WM is M x M, WN is N x N
– j 2π  -----
nl
 N
W N ( n, l ) = e
M–1 N–1
1 1
then F ( k, l ) = ---------
MN ∑ W M ( m, k ) ∑ f ( m, n )W N ( n, l ) = ---------W M f W N ,
MN
m=0 n=0
which is the forward transform
ECE/OPTI533 Digital Image Processing class notes 200 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
• Note that
* *
W M W M = W M W M = M I M (M x M identity matrix)
* *
W N W N = W N W N = N I N (N x N identity matrix)
then,
* * 1 * *
W M FW N = --------- ( W M W M ) f ( W N W N )
MN
1 , which is the inverse transform
= --------- ( M I M ) f ( N I N )
MN
= f
ECE/OPTI533 Digital Image Processing class notes 201 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
Matrix Dimensionality Diagram (M > N)
1
F = --------- WM f WN
MN
NxN
MxN MxM MxN
1
F = ---------W M f W N
MN
• Diagram for inverse transform is similar, except no 1/MN factor
• Note, this representation is possible because the 2-D DFT kernel is
– j 2π  ------- + ----- – j2π  ------- – j2π  -----
mk nl mk nl
 M N  M  N
separable, i.e. e = e e
ECE/OPTI533 Digital Image Processing class notes 202 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
CALCULATING THE 2-D DFT
1
F = ---------W M f W N
MN
• Step 1
write image as f = [ f 1 f 2 . . . f N] where f1, f2, . . . fN are the image columns of
length M
then,
1 1 1 1
F = ---- ----- W M f 1 ----- W M f 2 . . . ----- W M f N W N
N M M M
1
= ---- [ F 1 F 2 . . . F N ]W N
N
where each column is a 1-D DFT of length M of the image columns
ECE/OPTI533 Digital Image Processing class notes 203 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
• Step 2
t
F1
t 1 t F 2t t
form matrix transpose F = ---- W note, W is symmetric WN = WN
N N
…
t
FN
• Step 3
partition image matrix by columns
t
F1
t
F2
= [ g1 g2 . . . g M ] , where each column is an array of length N
…
t
FN
ECE/OPTI533 Digital Image Processing class notes 204 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
t 1 1 1
then F = ---- W N g 1 ---- W N g 2 . . . ---- W N g N
N N N
where each column is a 1-D DFT of length N
t
therefore F = [ G1 G2 . . . G M ]
• Step 4
transpose Ft to get F
ECE/OPTI533 Digital Image Processing class notes 205 Dr. Robert A. Schowengerdt 2003
 2-D DISCRETE FOURIER TRANSFORM
Calculating the 2-D DFT - Summary
1-D DFT 1-D DFT
applied to matrix applied to matrix
f each transpose each transpose F
column column
N 1-D DFTs of length M M 1-D DFTs of length N
N(Mlog2M) operations M(Nlog2N) operations
• N(Mlog2M) + M(Nlog2N) = MNlog2(MN) total operations
assumes 1-D FFT is used and M,N are powers of 2
• Compares to M2N2 total operations for “brute force” 2-D DFT
ECE/OPTI533 Digital Image Processing class notes 206 Dr. Robert A. Schowengerdt 2003