Chapter 4 Transform Domain Filtering
Agenda
1. 1D and 2D Fourier Transform – Fourierseries,∈Z
–
Fourier transform Continuous variable
Discrete variable , ∈ R
– –
• •
, ∈ R Discrete Fourier transform , ∈ Z
Convolution Theorem
2. Filtering in Fourier domain
2
4.1 1D Fourier Transform
Complex Number
• A complex number x is of the form: =+,where= −1
a: real part, b: imaginary part • Addition
+ + + = + + +
• Multiplication
+ + = − +(+)
4
Complex Number
Magnitude-phase or vector representation for a complex number = +
•Magnitude:= + • P h a s e : = t a n
• Magnitude-phase notation:
=
5
Complex Number
• Multiplication using magnitude-phase representation
• Properties
= ∗ ∗
=
• Complex conjugate
∗ = −
=− ∗ =
6
Euler’s Formula
cossin
• Related identities: – sin
Leonhard Euler
– cos
7
Fourier Series
• A T-periodic function (i.e.,
∀∈Z)canbeexpressedasthe sum of complex exponentials or sinusoids:
() =
where = 1 () ∀ ∈ Z
8
1D Continuous-Time Fourier Transform
• Anyfunctionthatisnotperiodiccanbeexpressed as the integral of complex exponentials or sinusoids
• TheFouriertransformofacontinuousfunction
• The inverse Fourier transform of :
• and () are Fourier transform pairs
() ↔ ()
9
Example
• The Fourier transform of the box or rectangular function
x(t)
Π
1
− 1 () 2f
− 1 − W 2f
W
1 −
2f
sin=
10
Continuous-Time Impulse Function
is the unit impulse of a continuous variable t located at t=0:
11
Fourier Transform of Impulse Function
• The Fourier transform of unit impulse located at the origin (i.e., ())
===1
• The Fourier transform of unit impulse located at = (i.e., ( − ))
=− =
12
Useful Fourier Transform Theorems
Name
Signal
Transform
↔ ; ↔ ; ↔
Superposition FrequencyTranslation Time Delay
Duality
Convolution Multiplication
+
()+()
−
−
∗ () ()()
(−)
∗ = −
∗ = −
∗ ()
13
Useful Fourier Transform Pairs
1.
Π
()
2. 3. 4. 5. 6.
() ( − )
1
By Time Delay and 2
7. 8.
2
Sine expressed as exponentials and 4
Signal
Transform
1
() −
By Duality and 2
cos(2) sin(2)
1 − −+
Cosine expressed as exponentials and 5
2
Gaussian transformed to a Gaussian
1
2 − + +
By Freq. Translation and 4
14
Fourier Transform of an Impulse Train
• The Fourier transform of the periodic impulse train
1 −Δ ↔Δ −Δ
Δ
1 Δ
t
f
1 Δ
15
•
is a Δ-periodic signal, and thus, can be expressed in a Fourier
Derivation
series:
•
where
• Therefore,
=1
=−Δ
Δ
The Fourier transform of 1
=
= Δ − Δ
=1()=1
Δ
Δx
16
1D Discrete-Time Fourier Transform (DTFT)
• In practice, we deal with functions/images of discrete variables
• For 1D discrete function , ∈ Z, 1D Discrete-Time
Fourier Transform and the inverse are defined as:
=
=
• is a discrete complex exponential with frequency cycles per second
• is unique only in any interval of 1 (e.g., ∈ [− , )) – because () = = .
– Thisimpliesthat = +1
• is1-periodic(i.e., + = ,∀∈Z)
• is a continuous signal.
17
Sampling Theorem (1)
• When a continuous function , which has a Fourier transform , is sampled with an interval , a discrete signal
= Δ is obtained.
• What is the Fourier transform of [],
?
• What is the relationship between and ()?
18
Sampling Theorem (2)
• Consider a continuous signal being sampled by the impulse train. Denote the sampled signal :
() ()
=
= −Δ
• First way of computing the Fourier transform of the impulse-sample function is:
= ()()
=∗
1
= ∗Δ−Δ 1
=(Δ)
=Δ −Δ (S.1)
19
Sampling Theorem (3)
↔
= ↔ 1 , Δ
and its -periodic extension.
↔ ↔
f
20
f
Sampling Theorem (4)
• Second way of computing the Fourier transform of the impulse-sample function is to do it directly:
=
= −Δ = []−Δ
= ( . 2
21
Sampling Theorem (5)
• Recall that our ultimate goal was to evaluate , the Fourier transform of the discrete sample .
• Thatis,
=
• Substitute = into Eq. (S.2)
Δ = =
1− =Δ=Δ Δ
=1 Δ Δ
and its 1-periodic extension
22
Sampling Theorem (6)
↔
f
↔ ↔
f
-2 -1 0 1 2
23
u
Aliasing (1)
• Two functions with different frequencies are indistinguishable after sampling
( )
( )
where ∈ Z
= =
24
Aliasing (2)
• is a bandlimited signalwithFT
• To avoid aliasing: – Δ <
u
– Δ <
-2
-1 − Δ 0 Δ 1
2
– The sampling
frequency = must
-1−Δ0 Δ1
u
belargerthan2: > 2
-2
2
– called Nyquist rate
−
f
-3 -2 -1 0 1 2 3
25
u
1D Discrete Fourier Transform (DFT)
• Practical signals are length-N sequences:
,0≤≤−1
• Need only N samples of () to recover
Nsamplesin .
• =∑
∈{,,⋯,}
represents N linear equations in the N unknowns of .
26
1D Discrete Fourier Transform (DFT)
• Define (forward) discrete Fourier transform (DFT)
==,0≤≤−1
• Inverse DFT
1
= ,0≤≤−1
• Note that the forward DFT is N-periodic: – + =∑ () =[]
• Inverse DFT is also N-periodic:
– + =∑ ()=[]
• Thus, do not need to restrict domain of
and
from 0 to N-1, but need to understand both are N-periodic.
to be
27
Circular Convolution in DFT
• Convolution theorem in FT of discrete signal: – = ∗ ↔ – ↔∗
• Due to the periodicity of forward and inverse DFT, corresponding properties of DFT are:
• where denotes circular convolution.
28
Circular Convolution in DFT
• and represents an N-periodic extension of and , respectively.
29
Linear vs. Circular Convolution
Linear Convolution Circular Convolution
wraparound error
30
Linear Convolution via Circular convolution
• Can adjust the circular convolution results to become the same as that obtained in linear convolution.
• Linear convolution is the same as circular convolution if enough zeros are padded behind the two sequences involved.
See below:
• : Length- sequence, y : Length- sequence
• ∗ [] could be obtained by first padding – −1zerosatthebackof
– −1zerosatthebackof[]
Linear Convolution Circular Convolution with Zero Padding
31
4.2 2D Fourier Transform
32
2D Continuous-Time Fourier Transform
• 2D Continuous-Time Fourier Transform and Inverse
33
2D Discrete-Time Fourier Transform (DTFT)
• 2D Discrete-Time Fourier Transform and
Inverse ,= ,
, = ,
34
Periodicity of
•, is1-periodicintheuandv directions:
•+,+ =, ∀,∈Z
35
DTFT Example
h[, ]
36
2D Discrete Fourier Transform (DFT)
• 2DforwardandinverseDFT:
, =,
1
, =[,]
• TakeMandNsamplesofDTFTinu,vdirections, respectively, within a period with interval 1.
• Convolutiontheoreminvolvescircularconvolution instead of linear convolution as in 1D DFT.
37
Periodicity and Translation
Periodicity
• 2D forward and inverse DFT are M- and N-periodic in the two dimensions:
, =+,+
, =+,+ ∀, ∈Z
Translation
, ↔−,−
−,− ↔,
38
A more natural order of DFT coefficients
• Due to the periodicity of DFT, is
[]
High Freq.
Low Freq.
ordered in a way that lower frequencies are
k
orderedfrom to
− 2
− 1.
• Shifting to the right
by unit would be a
k
more natural way to order DFT coefficients.
2
39
2D DFT implemented in Python
40
Symmetry of DFT
• DFT of a real image is conjugate symmetric ∗
• If [,] is real, then −,− = ,
• So, DFT spectrum is symmetric about the centre.
41
Rotation Property of DFT
• When expressed in polar coordinates:
• Results in the following DFT pairs:
• DFT is rotational-invariant.
42
Example (1)
43
Example (2)
44
DFT Pairs
45
2D Sampling and Aliasing
1 > 2 , 1 > 2 , Δ Δ
46
Aliasing Example
47
Need to know….
• Fouriertransformforcontinuousvariables,
,∈R
• Fourier transform for discrete variables, , ∈ R
– 1-periodic
, ∈ Z
• Discrete Fourier Transform (DFT), – Sampling of and 1-periodic
and their extension to 2D.
• Samplingtheoremandaliasing
– Understand in terms of and – Extension to 2D
• CircularconvolutioninDFT
– Need zero padding to avoid wraparound error
48