程序代写代做代考 Chapter 4 Transform Domain Filtering

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
􏴍􏵓􏵔 􏴃cos􏵃􏶒􏴽sin􏵃
• 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 􏴍􏴘􏵓􏴩􏵗􏵙􏶏 􏴩 􏶉􏶆(􏳿) 􏴽2􏶖f 􏴘􏶂􏴩
􏶉􏶆 􏳿
􏴃− 1 􏴍􏴘􏵓􏵗􏵙􏶂−􏴍􏵓􏵗􏵙􏶂 W 􏴽2􏶖f
W
􏴃 1 􏴍􏵓􏵗􏵙􏶂−􏴍􏴘􏵓􏵗􏵙􏶂
􏴽2􏶖f 􏳿 􏳿
􏴃􏵽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