1

Lecture 5
Fourier Transforms of 2D signals

Instructor: Dr. Yaser Esmaeili

Email: [email protected]

Department of Computer Science and Software Engineering

Concordia University

Slides modified from materials provided by Drs. Yiming Xiao & Tien Bui
 Frequency domain representation
High frequency
• The frequency domain analysis
refers to the analysis of signals wrt.
their frequency components.

• The purpose of the Fourier

transform is to represent a signal
as a linear combination of
sinusoidal signals of various Low frequency
frequencies.

• Mathematically easier to analyze

the effects of signal properties (e.g.,
noise)

2
 Frequency domain representation

s(x)

S(f)

Just 6 scalars! 3
https://en.wikipedia.org/wiki/Fourier_series
Examples of Fourier Transform

4
Give this try yourself

http://www.falstad.com/fourier/ Jean-Baptiste Joseph Fourier (1768 ‐ 1830)

French mathematician and physicist
5
 Continuous Fourier Transform
1-D and continuous Freq in rad or Hz?

Fourier transform

Inverse Fourier transform

(a>0) scaling

http://www.cs.cornell.edu/courses/cs5540/2010sp/lectures/Lec5.Transforms.pdf
6
Fourier transform: magnitude & phase

F(u) can be expressed in polar coordinates:

R(u): the real part of F(u)

I(u): the imaginary part of F(u)

Power spectrum:

7
Example: Fourier transform of a simple continuous function
 Review: Linear Systems [Lecture#02]
System Characterization (Con’t)

The convolution of f and h

The Fourier transform of the expression is

The term inside the inner brackets is the Fourier transform of the term h(x - a ).
But,
 Review: Linear Systems [Lecture#02]
System Characterization (Con’t)

so,

We have succeeded in proving the important result that the Fourier

transform of the convolution of two functions is the product of
their Fourier transforms.
 Review: Linear Systems [Lecture#02]
System Characterization (Con’t)

Following a similar development, it is not difficult to show that the

inverse Fourier transform of the convolution of H(u) and F(u) [i.e.,
H(u)*F(u)] is the product f(x)g(x). This result is known as the
convolution theorem, typically written as

and

where "  " is used to indicate that the quantity on the right is obtained by
taking the Fourier transform of the quantity on the left, and, conversely, the
quantity on the left is obtained by taking the inverse Fourier transform of the
quantity on the right.
Sampling Theorem

overlapping now
13
 Sampling Theorem - Nyquist Theorem

The period is ; sufficient separation is guaranteed if

i.e. a continuous, band-limited function can be recovered completely from
sampling if the samples are at the rate exceeding twice the highest frequency
content of the func. (Sampling Theorem)

Or: the max frequency can be captured by sampling at the rate of:

14
 Aliasing
What happens if a band-limited function is sampled at a rate less than
twice the highest frequency?

This is under-sampled. The inverse transform would yield a corrupted func.

This effect of under-sampling is called frequency aliasing, This is because
the high frequencies overlap with lower frequencies (hence the name aliasing
= false identity)

15
 Discrete Fourier Transform (1-D)
Let us define a set of orthonormal basis vectors

Inverse Fourier transform

Discrete Fourier
Fourier transform
Transform pair
16
 Discrete Fourier Transform (1-D)

only discrete in time domain

DFT

17
Example: Discrete Fourier Transform (1-D)

[Right] A continuous function sampled T units apart.

[Left] Samples in the x-domain.
Note: Variable t is continuous, while x is discrete

Q. Find DFT of f(t)?

Then, find the inverse Fourier transform of F(w)?
 Differences Between 1D and Multi-Dimensional
Signal Processing

• Much more data for M-D signal processing

1) 1-D signal: speech 10K samples/sec
2) 3-D signal: videos 500x500 pixels/frame, 30 frames/sec,
hence 7.5 Mega samples/sec.

Again, this is why we need to do frequency domain analysis

• Mathematics for M-D is not as complete as 1-D

1) 1-D systems are described by ODEs vs. M-D by PDEs.
2) Fundamental results of algebra do not hold in M-D, e.g. factorization
of polynomials in 1-D is known but not in M-D.
3) This effects filter design, filter stability, reconstruction, etc…

19
 Signals, Systems and Transforms

Digital Signal Processing Digital Image Processing

An image is a signal in 2-D or m-D (e.g., colors)
Signal carries physical information like speech, music, images
• continuous x(t)
• discrete x[n]

System
x[n] T y[n]

Input Output
Transform

20
 Signals, Systems and Transforms

• Linear system T(ax1[n] + bx2[n]) = T(ax1[n])+T(bx2[n]) = ay1[n] + by2[n]

• Time (shift) invariant system if T(x[n]) = y[n] then T(x[n-n0]) = y[n-n0]

• Linear Time Invariant system (LTI):

Impulse response can entirely characterize an LTI system.

• Impulse response and convolution (e.g.,Filters)

• Separable LTI system: computational efficiency

• Transforms: Bounded input bounded output (BIBO) stability

• Finite impulse response (FIR): always stable (e.g, averaging)
• Infinite impulse response (IIR): not always stable (e.g., feedback loop)
21
 Special signal: Impulse

[n] LTI f[n]

Impulse response

Sifting property of an impulse function:

(generalization) (discrete cases)

Given a LTI system T, we can easily obtain output signal for all possible input signals x[n]
from the Impulse response!

22
Computation of Correlation and Convolution (1-D)

23
 Examples of convolution operations between function f and g

f*g
Square functions

Gaussian functions

24
Examples of convolution operations between function f and g

25
Convolution Theorem - revisit

Theorem: The FT of the convolution of two functions is equal to the

product of the FTs of the two functions.

26
Reverse: The inverse FT of gives the convolution of
the two functions in spatial domain.

In General:

Discrete Fourier Transform (1-D)

27
2-D D.F.T

28
 Computation of 2D-DFT
• Fourier transform matrix:
1 1 1 · · · 1
2 N-1
1 W W · · · W N
N N

· · · ·
· · · ·
· · · · 2
N-1 2(N-1) (N-1)
1 WN WN · · · W N

where
 Computation of 2D-DFT
• Inverse Fourier transform matrix:

where

1 1 1 · · · 1

-1 -2 1-N
1 W W · · · W N
N N

· · · ·
· · · ·
· · · ·
2
1-N 2(1-N) - (N-1)
1 W W · · · W N
N N
 Computation of 2D-DFT
• Example. N = 4:

● Matlab function: dftmtx

 Computation of 2D-DFT
• 1D-DFT (of 1D signal x):

• Inverse 1D-DFT:

• 2D-DFT (of 2D image X):

• Inverse 2D-DFT:
 How to compute 2D D.F.T ?

1. Direct Method
2. Row/Column Decomposition
3. Fast Fourier Transform (FFT)

Factors effecting speed:

1. Number of arithmetic operations (addition & multiplication)
2. Complexity of program: memory usage
3. Language and platform

35
 How to compute 2D D.F.T ?

Direct Method
N2

N1

Assuming N1 = N2 = N,
For each (k1,k2), we need N2 multiplications and N2 adds
For all pairs of (k1,k2), we will need N4 multiplications and N4 adds

36
 How to compute 2D D.F.T ?
Row/column decomposition
N2

N1
1-D DFT

• By varying n2 from 0 to N-1, we compute a set of 1-D DFTs for all rows of f(n1,n2)
• The 2D-DFT is just the 1-D transforms of columns of f(k1,n2)

So 2-D DFT of f can be obtained by computing the 1-D

transform of each row of f and then compute the 1-D
transform along each column of the result

we will need 2N3 multiplications and 2N3 adds

37
 How to compute 2D D.F.T ?
n2 n2
x(n1,n2) f(k1,n2)
(N2-1) (N2-1)

1-D
N1-point DFT
….. …..

n1 k1
0 (N1-1) 0 (N1-1)

n2 k2
f(k1,n2) x(k1,k2)

(N2-1) (N2-1)

1-D
N2-point DFT
….. …..

k1 k1
0 (N1-1) 38
0 (N1-1)
After J.S.Lim: 2-D Signal and Image Processing
 How to compute 2D D.F.T ?
Fast Fourier Transform (FFT) N2

• Divides original vector into 2

• Calculates FFT of each half recursively N1

For 1 DFT operation,
• Merges results FFT requires [successive
doubling FFT algorithm ]

(N/2)log2N multiplications
N log2N additions

N=2048
92 million mult for FFT
1 trillion for direct method

Using FFT in row/column decomposition,

we will need N2 log2N multiplications 39
Example: Eklundh’s matrix transpose algorithm
 2-D Fourier Transform

Deriving Fourier transforms of box functions

43
 Aliasing in 2-D

moiré-like patterns

44
Newspaper printing (75dpi)
 Systems and Transforms (2-D)
• Transform (Operator): input into output
• Linear System (Operator)

• Time Invariant System

• Impulse Response

(2-D convolution)

• LTI system can be completely characterized by its response to the

impulse and its shift. 45
Computation of Correlation and Convolution (2-D)

Correlation

Convolution
Phase vs. Magnitude

50
Properties of 2D Fourier Transform

51
Intuitive experience with 2D FT

52
 Change in magnitude

translation

rotation

53
Change in phase maps

54
DFT

DFT

DFT

55
 DFT

Gaussian
DFT

Dot grid

Think about other patterns,

what their FT look like?
56
Summary

• 1-D Fourier transform -> 2D Fourier Transform

• Aliasing: reasons and impacts

• Discrete Fourier Transform (DFT) and its computation

(FT matrix, direct method, row/column decomposition,
FFT, computational complexity)

• Convolution and properties

• Properties of FT: phase & magnitude

• Intuitive understanding of images vs. FT

58
Reading materials

• Textbook Chapter 4

Page 204-240, 249-261

240-248 [good to read, Table 4.1]

59
Questions

• What is the Nyquist theorem? what is the type of signal fitted?

• Image reconstruction with inverse Fourier transform: phase vs. magnitude
• Moire-like patterns in old news-paper printing: what is the cause?
• What are the benefits of Fourier analysis?
• Is Fourier transform a linear operation?
• What is the “sifting property” of the delta/impulse function?
• How would the magnitude and phase maps change if spatial
transformations are applied to the image?
• Images vs. frequency representation
• Correlation vs. convolution

60