IMAGE PROCESSING

FILTERING IN THE FREQUENCY

DOMAIN

NGUYôN HÉI TRIóU1

1 BÎ môn Kˇ thu™t ph¶n m∑m,
Khoa Công nghª thông tin, Tr˜Ìng H Nha Trang

NhaTrang, December 2023

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 1 / 63

 C£i thiªn £nh trong mi∑n t¶n sË

1 C£i thiªn £nh trong mi∑n t¶n sË

2 Preliminary Concepts
3 THE 2-D DISCRETE FOURIER TRANSFORM
Bi∏n Íi Fourier rÌi r§c
Bi∏n Íi DFT ng˜Òc
Fourier spectrum and phase angle
4 LÂc £nh trong mi∑n t¶n sË
5 The Fast Fourier Transform (FFT)
Separability of the 2D-DFT
6 LÂc £nh trong mi∑n t¶n sË
Lowpass Frequency domain Filters
Highpass Frequency domain Filters

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 2 / 63

 C£i thiªn £nh trong mi∑n t¶n sË

Fourier Transform (FT)

Inverse Fourier Transform

(IFT)

Hình 1: S˚ dˆng Fourier Transform chuy∫n Íi £nh t¯ mi∑n không gian

sang mi∑n t¶n sË và ng˜Òc l§i

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 3 / 63

 C£i thiªn £nh trong mi∑n t¶n sË

TÍng quan
Trong ch˜Ïng này s≥ trình bày v∑ c£i thiªn £nh trong mi∑n t¶n sË
Khái niªm v∑ chuÈi Fourier - Bi∏n Íi Fourier
Kˇ thu™t lÂc m‡n £nh (Lowpass filter)
I Ideal (l˛ t˜ng)
I Gaussian
I Butterworth
Kˇ thu™t lÂc s≠c nét £nh (Highpass filter)
I Ideal (l˛ t˜ng)
I Gaussian
I Butterworth

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 4 / 63

 C£i thiªn £nh trong mi∑n t¶n sË

T§i sao c¶n ph£i chuy∫n sang mi∑n t¶n sË ∫ lÂc?

Spatial filtering takes on the order of M N mn operations
(multiplications and additions) to filter an M ⇥ N image with a
kernel of size m ⇥ n elements.

Computational advantages of filtering in the frequency

Frequency filtering takes on the order of 2M N log2 (M N )
operations to perform the equivalent filtering process in the
frequency domain, where the 2 in front arises from the fact that
we have to compute a forward and an inverse FFT-Fast Fourier
Transform.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 5 / 63

 C£i thiªn £nh trong mi∑n t¶n sË

LÒi ích cıa viªc tính toán trong mi∑n t¶n sË

Xem ví dˆ Hình 4.2 trang 206 tài liªu [1]

If filtering a bank of images of size 2048 ⇥ 2048 takes 1 minute
with the FFT, it would take on the order of 17 hours to filter
the same set of images with a nonseparable kernel of size
201 ⇥ 201 elements (˛ nghæa t˜Ïng t¸ nh˜ viªc s˚ dˆng bÎ lÂc Sobel
có kích th˜Óc 201 ⇥ 201 trong mi∑n không gian s≥ ph£i mßt ∏n 17
giÌ ∫ lÂc xong cùng mÎt b˘c £nh).

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 6 / 63

 C£i thiªn £nh trong mi∑n t¶n sË

Ti∫u s˚ Fourier

Jean Baptiste Joseph Fourier

The French mathematician Jean Baptiste Joseph Fourier was
born in 1768 in the town of Auxerre.
Basically, Fourier’s contribution in this field states that any
periodic function can be expressed as the sum of sines
and/or cosines of different frequencies, each multiplied
by a different coefficient (we now call this sum a Fourier
series)
Fourier transform: functions that are not periodic (but
whose area under the curve is finite) can be expressed as
the integral of sines and/or cosines multiplied by a
weighting function.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 7 / 63

 C£i thiªn £nh trong mi∑n t¶n sË

Hình 2: ChuÈi Fourier: mÎt hàm tu¶n hoàn bßt k˝ l∞p l§i có th∫ bi∫u
diπn d˜Ói d§ng tÍng các hàm sine và cosine  các t¶n sË khác nhau.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 8 / 63

 Preliminary Concepts

1 C£i thiªn £nh trong mi∑n t¶n sË

2 Preliminary Concepts
3 THE 2-D DISCRETE FOURIER TRANSFORM
Bi∏n Íi Fourier rÌi r§c
Bi∏n Íi DFT ng˜Òc
Fourier spectrum and phase angle
4 LÂc £nh trong mi∑n t¶n sË
5 The Fast Fourier Transform (FFT)
Separability of the 2D-DFT
6 LÂc £nh trong mi∑n t¶n sË
Lowpass Frequency domain Filters
Highpass Frequency domain Filters

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 9 / 63

 Preliminary Concepts Complex numbers

‡nh nghæa sË Ph˘c

A complex number, C, is defined as

C = R + jI,

where R (real part) and I (imaginary part) are real numbers

and j 2 = 1. The conjugate of a complex number C, denoted C ⇤ ,
is defined as
C ⇤ = R jI

V∑ m∞t hình hÂc, sË ph˘c có th∫ ˜Òc xem nh˜ là các i∫m trên
mÎt m∞t phØng (gÂi là m∞t phØng ph˘c), trˆc hoành Î giá tr‡
th¸c (các giá tr‡ cıa R) và trˆc tung có giá tr‡ £o (các giá tr‡ cıa
I)

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 10 / 63

 Preliminary Concepts Complex numbers

complex numbers in polar coordinates

Sometimes it is useful to represent complex numbers in polar
coordinates,
C = |C|(cos ✓ + j sin ✓)
p
where |C| = R2 + I 2 ( Î dài cıa vector t¯ gËc ∏n i∫m (R,I)
trên m∞t phØng ph˘c), ✓ = arctan(I/R) (góc gi˙a vector vÓi trˆc
th¸c
⇥ (R)). The
⇤ arctan function returns angles in the range
⇡/2, ⇡/2 .

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 11 / 63

 Preliminary Concepts Complex numbers

Euler’s formula,
Using Euler’s formula,

ej✓ = cos ✓ + j sin ✓

where e = 2.71828..., gives the following familiar representation of

complex numbers in polar coordinates,

C = |C|ej✓

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 12 / 63

 Preliminary Concepts Fourier series

Fourier series
A function f (t) of a continuous variable, t (we interpret t as
time), that is periodic with a period, T , can be expressed as the
sum of sines and cosines multiplied by appropriate coefficients.
This sum, known as a Fourier series, has the form
1
X 2⇡n
f (t) = cn e j T
t
(1)
n= 1

where Z T /2
1 j 2⇡n t
cn = f (t)e T dt,
T T /2

for n = 0, ±1, ±2, . . .

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 13 / 63

 Preliminary Concepts Impulses and their Sifting properties

Xung (Impulses)
Xung là các tín hiªu có biên Î rßt cao nh˜ng thÌi gian tÁn t§i rßt
ng≠n. Trong x˚ l˛ tín hiªu sË, ng˜Ìi ta th˜Ìng dùng hàm (t) (t là
mÎt bi∏n liên tˆc) ∫ bi∫u diπn mÎt xung l˛ t˜ng (unit impulse)
(
1, if t = 0,
(t) = (2)
0, if t 6= 0

Hàm này b¨ng 0  mÂi nÏi tr¯ t§i t = 0, tÍng diªn tích d˜Ói
˜Ìng cong cıa nó luôn b¨ng 1, bßt k∫ kho£ng tích phân nh‰ cÔ
nào Z 1
(t)dt = 1 (3)
1

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 14 / 63

 Preliminary Concepts Impulses and their Sifting properties

Tính chßt sàng lÂc (Sifting property)

Sifting simply yields the value of the function f (t) at the location
of the impulse. An impulse located at an arbitrary point, t0 ,
denoted as, (t t0 ), the sifting property is
Z 1
(t t0 )f (t)dt = f (t0 )
1

(hàm delta Dirac “sàng lÂc” hàm f (t) và chø lßy ra giá tr‡ cıa nó
t§i thÌi i∫m t = t0 .)

Gi£ s˚ có mÎt tín hiªu f (t) ch˘a mÎt xung t§i t = 1 giây. Bi∏n Íi
Fourier cıa tín hiªu này cho bi∏t thành ph¶n t¶n sË cıa nó. D¸a
vào tính chßt sàng lÂc, chúng ta có th∫ bi∏t ˜Òc thành ph¶n nào
trong Bi∏n Íi Fourier t˜Ïng ˘ng vÓi xung: nó s≥ là mÎt giá tr‡ vô
cùng t§i t¶n sË f0 .
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 15 / 63
 Preliminary Concepts Impulses and their Sifting properties

Let x represent a discrete variable,

(
1, if x = 0,
(x) = (4)
0, if x 6= 0

Clearly, this definition satisfies the discrete equivalent of Eq.3:

1
X
(x) = 1
x= 1

The sifting property for discrete variables using a discrete impulse

located at x = x0 has the form
1
X
(x x0 )f (x) = f (x0 )
x= 1

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 16 / 63

 Preliminary Concepts The fourier transform of functions of one continuous variable

Fourier transform
The Fourier transform (FT) of a continuous function f (t) of a
continuous variable, t, denoted F (µ), is defined by the equation
Z 1
F (µ) = f (t)e j2⇡µt dt (5)
1

We can obtain f (t) back using the inverse Fourier transform (IFT)
Z 1
f (t) = F (µ)ej2⇡µt dt (6)
1

Using Euler’s formula, we can write Eq.5 as

Z 1
⇥ ⇤
F (µ) = f (t) cos(2⇡µt) j sin(2⇡µt) dt (7)
1

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 17 / 63

 Preliminary Concepts The fourier transform of functions of one continuous variable

Fourier spectrum
In general, the Fourier transform contains complex terms, and it
is customary for display purposes to work with the
magnitude of the transform (a real quantity), which is
called the Fourier spectrum.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 18 / 63

 Preliminary Concepts The fourier transform of functions of one continuous variable

Ví dˆ
Hãy tính Fourier Transform cho hàm f (t) có d§ng nh˜ hình bên
d˜Ói.

Hình 3: (a) A box function, (b) its Fourier transform, and (c) its
spectrum. All functions extend to infinity in both directions. Note the
inverse relationship between the width, W , of the function and the
zeros of the transform.
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 19 / 63
 Preliminary Concepts The fourier transform of functions of one continuous variable

Ví dˆ-Hint
S˚ dˆng công th˘c bi∏n Íi FT  Eq.5, s˚ dˆng Áng nhßt th˘c
sin(✓) = (ej✓ e j✓ )/(2j), sinc(m) = sin(⇡m)
⇡m
where sinc(0) = 1
and sinc(m) = 0, ∫ rút gÂn.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 20 / 63

 Preliminary Concepts The fourier transform of functions of one continuous variable

Ví dˆ-Hint
S˚ dˆng công th˘c bi∏n Íi FT  Eq.5, s˚ dˆng Áng nhßt th˘c
sin(✓) = (ej✓ e j✓ )/(2j), sinc(m) = sin(⇡m)
⇡m
where sinc(0) = 1
and sinc(m) = 0, ∫ rút gÂn.
K∏t qu£ F (µ) = AW sin(⇡µW
(⇡µW )
)

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 20 / 63

 Preliminary Concepts The fourier transform of functions of one continuous variable

The Fourier transform of an impulse located at t = t0 is

Z 1 Z 1
j2⇡µt
F (µ) = (t t0 )e dt = e j2⇡µt (t t0 )dt = e j2⇡µt0
1 1

The term e j2⇡µt0 represents a unit circle centered on the origin of

the complex plane, as you can easily see by using Euler’s formula
to expand the exponential into its sine and cosine components.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 21 / 63

 Preliminary Concepts Convolution

Convolution in frequency domain

In the present discussion, we are interested in the convolution of
two continuous functions, f (t) and h(t) of one continuous variable,
t, so we have to use integration instead of a summation
Z 1
(f h)(t) = f (⌧ )h(t ⌧ )d⌧ (8)
1

where, t is the displacement needed to slide one function past the

other, and ⌧ is a dummy variable that is integrated out.

The Fourier transform of Eq.8

R 1 hR 1 i
j2⇡µt
F{(f h)(t)} = 1 1
f (⌧ )h(t ⌧ )d⌧ e dt
R1 h R1 i
j2⇡µt
= 1 f (⌧ ) 1
h(t ⌧ )e dt d⌧ (9)

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 22 / 63

 Preliminary Concepts Convolution

The Fourier transform of Eq.8

The term inside the brackets of Eq.9 is the Fourier transform of
h(t ⌧ ). F{h(t ⌧ )} = H(µ)e j2⇡µt , where H(µ) is the Fourier
transform of h(t). Using this in the preceding equation gives us
R1
F{(f h)(t)} = H(µ) 1 f (⌧ )e j2⇡µt d⌧
= H(µ)F (µ) = (H • F ) (µ) (10)

where • indicates multiplication.

Bài t™p: Convolution theorem

Ch˘ng minh r¨ng bi∏n Íi Fourier cıa tích ch™p cıa hai hàm
trong mi∑n không gian b¨ng tích cıa các bi∏n Íi Fourier cıa hai
hàm trong mi∑n t¶n sË F{(f h)(t)} = (H • F ) (µ). Trong ó,
H, F l¶n l˜Òt là bi∏n Íi Fourier cıa h(t), f (t).
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 23 / 63
 THE 2-D DISCRETE FOURIER TRANSFORM

1 C£i thiªn £nh trong mi∑n t¶n sË

2 Preliminary Concepts
3 THE 2-D DISCRETE FOURIER TRANSFORM
Bi∏n Íi Fourier rÌi r§c
Bi∏n Íi DFT ng˜Òc
Fourier spectrum and phase angle
4 LÂc £nh trong mi∑n t¶n sË
5 The Fast Fourier Transform (FFT)
Separability of the 2D-DFT
6 LÂc £nh trong mi∑n t¶n sË
Lowpass Frequency domain Filters
Highpass Frequency domain Filters

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 24 / 63

 THE 2-D DISCRETE FOURIER TRANSFORM Bi∏n Íi Fourier rÌi r§c

Discrete Fourier Transform (DFT)

Bi∏n Íi DFT cıa f (x, y), ˜Òc bi∫u diπn bi F (u, v):
M
X1 N
X1
j2⇡(ux/M +vy/N )
F (u, v) = f (x, y)e (11)
x=0 y=0

Where, f (x, y) is a digital image of size M ⇥ N . We use (x, y) for

spatial variables and (u, v) for frequency-domain variables, all of
which are discrete. u = 0, 1, . . . , M 1, v = 0, 1, . . . , N 1.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 25 / 63

 THE 2-D DISCRETE FOURIER TRANSFORM Bi∏n Íi Fourier rÌi r§c

Hình 4: Ví dˆ bi∏n Íi DFT cıa £nh f (x, y), ta thu ˜Òc phÍ Fourier
trong hình bên ph£i.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 26 / 63

 THE 2-D DISCRETE FOURIER TRANSFORM Bi∏n Íi Fourier rÌi r§c

⇥ ⇤1/2
Hình 5: Fourier spectrum: |F (u, v)| = R2 (u, v) + I 2 (u, v)
, where R = Real(F ); I = Imag(F )

Mˆc ích chuy∫n Íi Fourier là ∫ s˚ dˆng bÎ lÂc trên mi∑n t¶n

sË F (u, v) sau ó chuy∫n Íi ng˜Òc v∑ mi∑n không gian ∫ ˜Òc
£nh c£i thiªn.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 27 / 63

 THE 2-D DISCRETE FOURIER TRANSFORM Bi∏n Íi DFT ng˜Òc

Inverse Discrete Fourier Transform (IDFT) of F (u, v)

M 1N 1
1 XX
f (x, y) = F (u, v)ej2⇡(ux/M +vy/N ) (12)
M N u=0 v=0
for x = 0, 1, 2, . . . , M 1 and y = 0, 1, 2, . . . , N 1. Eqs.11 and 12
constitute a 2-D discrete Fourier transform pair,
f (x, y) , F (u, v).

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 28 / 63

 THE 2-D DISCRETE FOURIER TRANSFORM Fourier spectrum and phase angle

Because the 2-D DFT is complex in general, it can be

expressed in polar form:

F (u, v) = R(u, v) + jI(u, v) = |F (u, v)|ej (u,v)

⇥ ⇤1/2
where the magnitude |F (u, v)| = R2 (u, v) + I 2 (u, v) is called
the Fourier (or⇥frequency) spectrum, and
I(u,v) ⇤
(u, v) = arctan R(u,v) is the phase angle or phase spectrum.

L˜u ˛
R(u, v), I(u, v), F (u, v), (u, v) là các ma tr™n M ⇥ N . Trong l™p
trình, ∫ bi∫u diπn DFT trong mi∑n t¶n sË, chúng ta th˜Ìng chø
v≥ ph¶n th¸c.
Các công th˘c liên quan ∏n DFT SV có th∫ xem chi ti∏t 
TABLE 4.3: Summary of DFT definitions and corresponding
expressions tài liªu [1], p.258.
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 29 / 63
 LÂc £nh trong mi∑n t¶n sË

1 C£i thiªn £nh trong mi∑n t¶n sË

2 Preliminary Concepts
3 THE 2-D DISCRETE FOURIER TRANSFORM
Bi∏n Íi Fourier rÌi r§c
Bi∏n Íi DFT ng˜Òc
Fourier spectrum and phase angle
4 LÂc £nh trong mi∑n t¶n sË
5 The Fast Fourier Transform (FFT)
Separability of the 2D-DFT
6 LÂc £nh trong mi∑n t¶n sË
Lowpass Frequency domain Filters
Highpass Frequency domain Filters

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 30 / 63

 LÂc £nh trong mi∑n t¶n sË

Các b˜Óc th¸c hiªn bi∏n Íi DFT và lÂc £nh trong mi∑n
t¶n sË (xem chi ti∏t  ph¶n “SUMMARY OF STEPS
FOR FILTERING IN THE FREQUENCY DOMAIN”
tài liªu [1], p.266 ):
1 Chuy∫n £nh ¶u vào f (x, y) có kích th˜Óc M ⇥ N thành £nh
fp (x, y) có kích th˜Óc P ⇥ Q. VÓi P = 2M và Q = 2N (vùng
không ch˘a £nh cho m˘c xám b¨ng 0 ). B˜Óc này có ˛ nghæa
là m rÎng £nh có kích th˜Óc gßp 4 l¶n £nh ¶u vào.
2 T§o £nh mÓi Fp (x, y) có các thành ph¶n Ëi x˘ng qua tâm
t§i (P/2, Q/2) b¨ng cách nhân £nh fp (x, y) vÓi ( 1)x+y .
3 Tính DFT cıa £nh Fp (x, y) ∫ thu ˜Òc £nh F (u, v).
4 T§o bÎ lÂc H(u, v) có kích th˜Óc P ⇥ Q, các ph¶n t˚ bÎ lÂc
Ëi x˘ng vÓi i∫m trung tâm (P/2, Q/2).

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 31 / 63

 LÂc £nh trong mi∑n t¶n sË

5 Nhân t¯ng c∞p (elementwise multiplication) ph¶n t˚ cıa ma

tr™n F (u, v) vÓi H(u, v) ∫ thu ˜Òc G(u, v). Cˆ th∫:
G(i, k) = H(i, k)F (i, k) vÓi i = 0, 1, 2, ..., P 1 và
k = 0, 1, 2, ..., Q 1.
6 Bi∏n Íi ng˜Òc IDFT Ëi vÓi G(u, v). Ti∏p tˆc nhân ph¶n
th¸c sau khi bi∏n Íi ng˜Òc vÓi ( 1)x+y ∫ t§o £nh gp (x, y)
có kích th˜Óc P ⇥ Q và tâm Ëi x˘ng (P/2, Q/2).
⇥ ⇤
gp (x, y) = R F 1 (G(u, v)) ( 1)x+y

7 Trích vùng £nh M ⇥ N t¯ £nh gp (x, y) (t¯ góc ph¶n t˜ trên

bên trái) ∫ ˜Òc £nh g(x, y). Énh g(x, y) là £nh cuËi cùng
sau khi lÂc.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 32 / 63

 LÂc £nh trong mi∑n t¶n sË

Ảnh gốc M ⇥ N Bước 1: Ảnh fp (x, y), (P ⇥ Q) Bước 2: Fp (x, y) = fp (x, y)( 1)x+y

Bước 3: Phổ tần số F (u, v) Bước 4: Phổ tần số Bộ lọc H(u, v) Bước 5: Phổ tần số F (u, v) H(u, v)

Bước 6.1: IDF T (G(u, v)) Bước 6.2: gp (x, y) = Real[IDF T (G(u, v))]( 1)x+y Bước 7: g(x, y), (M ⇥ N )

Hình 6: Ví dˆ minh ho§ các b˜Óc

1 lÂc £nh trên mi∑n t¶n sË.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 33 / 63

 The Fast Fourier Transform (FFT)

1 C£i thiªn £nh trong mi∑n t¶n sË

2 Preliminary Concepts
3 THE 2-D DISCRETE FOURIER TRANSFORM
Bi∏n Íi Fourier rÌi r§c
Bi∏n Íi DFT ng˜Òc
Fourier spectrum and phase angle
4 LÂc £nh trong mi∑n t¶n sË
5 The Fast Fourier Transform (FFT)
Separability of the 2D-DFT
6 LÂc £nh trong mi∑n t¶n sË
Lowpass Frequency domain Filters
Highpass Frequency domain Filters

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 34 / 63

 The Fast Fourier Transform (FFT) Separability of the 2D-DFT

T¯ công th˘c bi∏n Íi Fourier rÌi r§c (DFT)  Eqs. 11 hay 12:
M
X1 N
X1
j2⇡(ux/M +vy/N )
F (u, v) = f (x, y)e
x=0 y=0

Dπ dàng nh™n thßy vßn ∑ r¨ng:

Î ph˘c t§p tính toán cıa bi∏n Íi DFT/IDFT rßt
lÓn: O(n) = n4
ví dˆ: n∏u mÎt b˘c £nh có kích th˜Óc M ⇥ N = 1024 ⇥ 1024
thì Î ph˘c t§p là là 10244 = 1, 099, 511, 627, 776.
V™y nên chúng ta b≠t buÎc ph£i Ïn gi£n tính toán c£i thiªn kh£
n´ng tính toán.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 35 / 63

 The Fast Fourier Transform (FFT) Separability of the 2D-DFT

Do tính chßt sóng, mÎt hàm trong không gian 2 chi∑u có chu kì có
th∫ bi∫u diπn thành tÍng các hàm 1 chi∑u (sine/cosine). V™y nên,
Công th˘c 2-D DFT  Eqs. 11 có th∫ ˜Òc tách thành các
1-D DFT nh˜ sau:
P1 NP1
M
j2⇡(ux/M +vy/N )
F (u, v) = f (x, y)e
x=0 y=0
P1
M
j2⇡ux/M
NP1
j2⇡vy/N
= e f (x, y)e
x=0 y=0
P1
M
j2⇡ux/M
= F (x, v)e (13)
x=0

where
N
X1
j2⇡vy/N
F (x, v) = f (x, y)e (14)
y=0

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 36 / 63

 The Fast Fourier Transform (FFT) Separability of the 2D-DFT

Ïn gi£n hoá bi∏n Íi DFT/IDFT

For one value of x in Eqs.14, and for v = 0, 1, 2, ..., N 1,
we see that F (x, v) is the 1-D DFT of one row of f (x, y).
The computations in Eq.13 similarly are 1-D transforms
of the columns of F (x, v).
Tóm l§i, bi∏n Íi 2-D DFT cıa hàm f (x, y) có th∫ Ïn gi£n
hoá b¨ng cách tính bi∏n Íi 1-D DFT các hàng cıa f (x, y)
tr˜Óc, sau ó bi∏n Íi 1-D DFT dÂc theo các cÎt cıa k∏t
qu£ 1-D theo hàng. Làm t˜Ïng t¸ cho 2-D IDFT s˚ dˆng
1D-IDFT ? Ngoài ra, chúng ta có th∫ tính IDFT s˚ dˆng “DFT
ALGORITHM” (SV tham kh£o tài liªu [1], p.304)

VÓi viªc tách thành 2 hàm rÌi r§c mÓi là F (x, v), F (u, v), Î ph˘c
t§p cıa bi∏n Íi DFT/IDFT là O(n) = n2 (yêu c¶u sinh viên
ch˘ng minh).
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 37 / 63
 The Fast Fourier Transform (FFT) Separability of the 2D-DFT

S˚ dˆng bi∏n Íi DFT/IDFT Ïn gi£n hoá  các phân tích trên

và lÂc £nh trong mi∑n t¶n sË thông qua các b˜Óc sau:
1 Chuy∫n £nh ¶u vào f (x, y) có kích th˜Óc M ⇥ N thành £nh
fp (x, y) có kích th˜Óc P ⇥ Q. VÓi P = 2M và Q = 2N (vùng
không ch˘a £nh cho m˘c xám b¨ng 0 ). B˜Óc này có ˛ nghæa
là m rÎng £nh có kích th˜Óc gßp 4 l¶n £nh ¶u vào.
2 T§o £nh mÓi Fp (x, y) có các thành ph¶n Ëi x˘ng qua tâm
t§i (P/2, Q/2) b¨ng cách nhân £nh fp (x, y) vÓi ( 1)x+y .
3 Tính DFT cıa £nh Fp (x, y) b¨ng công th˘c Ïn gian hoá 
Eq.13 ∫ thu ˜Òc £nh F (u, v).
4 T§o bÎ lÂc H(u, v) có kích th˜Óc P ⇥ Q, các ph¶n t˚ bÎ lÂc
Ëi x˘ng vÓi i∫m trung tâm (P/2, Q/2).

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 38 / 63

 The Fast Fourier Transform (FFT) Separability of the 2D-DFT

5 Nhân t¯ng c∞p (elementwise multiplication) ph¶n t˚ cıa ma

tr™n F (u, v) vÓi H(u, v) ∫ thu ˜Òc G(u, v). Cˆ th∫:
G(i, k) = H(i, k)F (i, k) vÓi i = 0, 1, 2, ..., P 1 và
k = 0, 1, 2, ..., Q 1.
6 Bi∏n Íi ng˜Òc IDFT d¸a trên Eq.14 Ëi vÓi G(u, v). Ti∏p tˆc
nhân ph¶n th¸c sau khi bi∏n Íi ng˜Òc vÓi ( 1)x+y ∫ t§o
£nh gp (x, y) có kích th˜Óc P ⇥ Q và tâm Ëi x˘ng (P/2, Q/2).
⇥ ⇤
gp (x, y) = R F 1 (G(u, v)) ( 1)x+y

7 Trích vùng £nh M ⇥ N t¯ £nh gp (x, y) (t¯ góc ph¶n t˜ trên

bên trái) ∫ ˜Òc £nh g(x, y). Énh g(x, y) là £nh cuËi cùng
sau khi lÂc.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 39 / 63

 The Fast Fourier Transform (FFT) Separability of the 2D-DFT

Nâng cao

Fast Fourier Transform–FFT

Các kˇ thu™t d¸a trên Fourier tr nên phÍ bi∏n nhÌ s¸ phát
tri∫n cıa Fast Fourier Transform (FFT).
Cho phép bi∏n Íi Fourier th¸c hiªn trong thÌi gian có th∫
chßp nh™n ˜Òc.
Gi£m thÌi gian th¸c hiªn bi∏n Íi Fourier 100 - 600 l¶n vÓi
Î ph˘c t§p M N log2 (M N )

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 40 / 63

 LÂc £nh trong mi∑n t¶n sË

1 C£i thiªn £nh trong mi∑n t¶n sË

2 Preliminary Concepts
3 THE 2-D DISCRETE FOURIER TRANSFORM
Bi∏n Íi Fourier rÌi r§c
Bi∏n Íi DFT ng˜Òc
Fourier spectrum and phase angle
4 LÂc £nh trong mi∑n t¶n sË
5 The Fast Fourier Transform (FFT)
Separability of the 2D-DFT
6 LÂc £nh trong mi∑n t¶n sË
Lowpass Frequency domain Filters
Highpass Frequency domain Filters

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 41 / 63

 LÂc £nh trong mi∑n t¶n sË

S˚ dˆng bi∏n Íi Fourier ∫ lÂc £nh trong mi∑n t¶n sË ˘ng dˆng
trong c£i thiªn £nh.
Lowpass filter (cho qua t¶n sË thßp): làm m‡n £nh.
Highpass filter (cho qua t¶n sË cao): làm s≠c nét £nh.

Hình 7: Top row: Frequency domain filter transfer functions of (a) a

lowpass filter, (b) a highpass filter. Bottom row: Corresponding filtered
images.
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 42 / 63
 LÂc £nh trong mi∑n t¶n sË Lowpass Frequency domain Filters

Ideal lowpass filters - ILPF

C≠t b‰ thành ph¶n t¶n sË cao d¸a trên kho£ng cách D0 .
hàm chuy∫n Íi cıa ILPF
(
1, if D(u, v)  D0
H(u, v) = (15)
0, if D(u, v) > D0

trong ó,
I D0 is a positive constant (cutoff)
I and D(u, v) is the distance between a point (u, v) in he
frequency domain and the center of the P ⇥ Q frequency
rectangle; that is,
⇥ ⇤1/2
D(u, v) = (u P/2)2 + (v Q/2)2 .

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 43 / 63

 LÂc £nh trong mi∑n t¶n sË Lowpass Frequency domain Filters

Hình 8: Bi∫u diπn Á th‡ cıa hàm chuy∫n Íi ILPF  Eq.19. (a) Bi∫u
diπn 3 chi∑u; (b) Bi∫u diπn 2 chi∑u; (c) Bi∫u diπn 2 chi∑u theo D

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 44 / 63

 LÂc £nh trong mi∑n t¶n sË Lowpass Frequency domain Filters

Hình 9: (a) Original image. (b)–(f) Results of filtering using ILPFs

with cutoff frequencies set at radii values D0 10, 30, 60, 160, and 460.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 45 / 63

 LÂc £nh trong mi∑n t¶n sË Lowpass Frequency domain Filters

Butterworth Lowpass Filter-BLPF

The transfer function of a Butterworth lowpass filter (BLPF) of
order n, with cutoff frequency at a distance D0 from the center of
the frequency rectangle, is defined as
1
H(u, v) = ⇥ ⇤2n (16)
1 + D(u, v)/D0

Hình 10: Bi∫u diπn Á th‡ cıa hàm chuy∫n Íi BLPF. (a) Bi∫u diπn 3
chi∑u; (b) Bi∫u diπn 2 chi∑u; (c) Bi∫u diπn 2 chi∑u theo D
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 46 / 63
 LÂc £nh trong mi∑n t¶n sË Lowpass Frequency domain Filters

Hình 11: (a) Original image. (b)–(f) Results of filtering using BLPFs
with cutoff frequencies at the radii shown in Fig.9 and n = 2.25.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 47 / 63

 LÂc £nh trong mi∑n t¶n sË Lowpass Frequency domain Filters

Gaussian Lowpass Filter-GLPF

Gaussian lowpass filter transfer functions have the form
D 2 (u,v)/2 2
H(u, v) = e (17)

where, is a measure of spread about the center. We can set

= D0 .

Hình 12: Bi∫u diπn Á th‡ cıa hàm chuy∫n Íi GLPF. (a) Bi∫u diπn 3
chi∑u; (b) Bi∫u diπn 2 chi∑u; (c) Bi∫u diπn 2 chi∑u theo D
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 48 / 63
 LÂc £nh trong mi∑n t¶n sË Lowpass Frequency domain Filters

Hình 13: (a) Sample text of low resolution (note the broken characters
in the magnified view). (b) Result of filtering with a GLPF, showing
that gaps in the broken characters were joined.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 49 / 63

 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

IMAGE SHARPENING USING HIGHPASS FILTERS

LÂc s≠c nét £nh trong mi∑n t¶n sË:
Các chi ti∏t nét trong £nh th˜Ìng g≠n vÓi các thành ph¶n t¶n
sË cao (high-frequency).
Image sharpening can be achieved in the frequency domain
by highpass filtering, which attenuates low-frequencies
components without disturbing high-frequencies in the
Fourier transform.
Highpass filter: chø cho qua các thành ph¶n t¶n sË cao, lo§i
b‰ thành ph¶n t¶n sË thßp.

Subtracting a lowpass filter transfer function from 1 yields the

corresponding highpass filter transfer function in the frequency
domain:
HHP (u, v) = 1 HLP (u, v) (18)
Highpass filter chính là ngh‡ch £o cıa Lowpass filter.
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 50 / 63
 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

Ideal Highpass Filter-IHPF

Áp dˆng nguyên l˛ ngh‡ch £o Eq.18 vào công th˘c Eq.12 cıa
ILPF, hàm chuy∫n Íi cıa IHPF có d§ng
(
0, if D(u, v)  D0
H(u, v) = (19)
1, if D(u, v) > D0

Hình 14: image, and, radial cross section of an IHPF transfer function.
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 51 / 63
 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

Ảnh gốc MxN Bước 1: Ảnh PxQ Bước 2: nhân -1 mũ x+y

Bước 3: Phổ tần số ảnh sau khi DFT Bước 4: Phổ tần số Bộ lọc Bước 5: Sau khi nhân DFT với ảnh sau khi lọc

Bước 6.1: Thực hiện DFT ngượcBước 6.2: Phần thực sau IDFT nhân -1 mũ (x+y) Bước 7: Ảnh cuối cùng MxN

Hình 15: K∏t qu£ lÂc IHPF

1
cho £nh vÓi D0 = 10.
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 52 / 63
 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

Butterworth Highpass Filter-BHPF

Áp dˆng nguyên l˛ ngh‡ch £o Eq.18 vào công th˘c Eq.16 cıa
BLPF, hàm chuy∫n Íi cıa BHPF có d§ng
1
H(u, v) = ⇥ ⇤2n (20)
1 + D0 /D(u, v)

Hình 16: image, and, radial cross section of an BHPF transfer function.
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 53 / 63
 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

Gaussian Highpass Filter-GHPF

Áp dˆng nguyên l˛ ngh‡ch £o Eq.18 vào công th˘c Eq.17 cıa
GLPF, hàm chuy∫n Íi cıa GHPF có d§ng
D 2 (u,v)/(2D02 )
H(u, v) = 1 e (21)

Hình 17: image, and, radial cross section of an BHPF transfer function.
Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 54 / 63
 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

Ảnh gốc M ⇥ N Bước 1: Ảnh fp (x, y), (P ⇥ Q) Bước 2: Fp (x, y) = fp (x, y)( 1)x+y

Bước 3: Phổ tần số F (u, v) Bước 4: Phổ tần số Bộ lọc H(u, v) Bước 5: Phổ tần số F (u, v) H(u, v)

Bước 6.1: IDF T (G(u, v)) Bước 6.2: gp (x, y) = Real[IDF T (G(u, v))]( 1)x+y Bước 7: g(x, y), (M ⇥ N )

Hình 18: K∏t qu£ lÂc GHPF

1 cho £nh vÓi D0 = 60.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 55 / 63

 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

Ví dˆ code minh ho§ ILPF trong mi∑n t¶n sË.

1 import numpy as np
2 import matplotlib.pyplot as plt
3 import cv2
4
5 class Frequency_LowpassFilter(object):
6 def __init__(self,img) -> None:
7 self.img=img
8 M, N=self.img.shape
9 self.P, self.Q = 2*M, 2*N
10
11 def DFT1D(self,img):
12 ’’’Bi∏n Íi DFT Ïn gi£n hoá theo Eq.14 trong slide’’’
13 U = len(img)
14 outarry = np.zeros(U, dtype=complex)
15 for v in range(U):
16 sum = 0.0
17 for n in range(U):
18 e = np.exp(-1j * 2 * np.pi * v * n / U)
19 sum += img[n] * e
20 outarry[v] = sum
21 return outarry
22

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 56 / 63

 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

23 def IDFT1D(self,img):
24 ’’’
25 Bi∏n Íi ng˜Òc IDFT Ïn gi£n hoá theo Eq.14 trong slide:
26 f(u,y)=\frac{1}{N} \sum_{v=0}^{N-1} F(u,v) e^{j2 \pi vy/N}
27 ’’’
28 U = len(img)
29 outarry = np.zeros(U,dtype=complex)
30 for n in range(U):
31 sum = 0.0
32 for v in range(U):
33 e = np.exp(1j * 2 * np.pi * v * n / U)
34 sum += img[v]*e
35 outarry[n]=sum/U
36 return outarry
37
38 def lowPass_Ideals(self,D0):
39 ’’’ ‡nh nghæa hàm lÂc Ideals’’’
40 # H is our filter
41 H = np.zeros((self.P, self.Q))
42 D = np.zeros((self.P, self.Q))
43 U0 = int(self.P / 2)
44 V0 = int(self.Q / 2)
45 # Tính kho£ng cách t¯ i∫m (u,v) ∏n tâm c
46 for u in range(self.P):

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 57 / 63

 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

47 for v in range(self.Q):
48 duc2 = np.power(u-U0, 2)
49 dvc2 = np.power(v-V0, 2)
50 D[u, v] = np.sqrt( duc2 + dvc2)
51 # Tính bÎ lÂc
52 for u in range(self.P):
53 for v in range(self.Q):
54 if D[u,v] <= D0:
55 H[u, v] = 1
56 else:
57 H[u, v] = 0
58 return H
59
60 def step_1(self):
61 ’’’B˜Óc 1: M rÎng £nh t¯ kích th˜Óc MxN vào £nh PxQ vÓi P=2M và Q=2N’’’
62 M, N=self.img.shape
63 # Chuy∫n £nh PxQ vào m£ng fp
64 f_xy_p = np.zeros((self.P, self.Q))
65 f_xy_p[:M, :N] = self.img
66 return f_xy_p
67
68 def step_2(self,f_xy_p):
69 ’’’B˜Óc 2: T§o £nh F_xy_p: nhân £nh fp(x,y) vÓi (-1)_{x+y} ∫t§o £nh mÓi’’’
70 F_xy_p = np.zeros((self.P, self.Q))

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 58 / 63

 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

71 for x in range(self.P):
72 for y in range(self.Q):
73 F_xy_p[x, y] = f_xy_p[x, y] * np.power(-1, x + y)
74 return F_xy_p
75
76 def step_3(self,F_xy_p):
77 ’’’B˜Óc 3: Tính DFT Ïn gi£n cho £nh F_xy_p trong mi∑n t¶n’’’
78 dft_cot = dft_hang = np.zeros((self.P, self.Q))
79 # DFT cho hàng th˘ i
80 for i in range(self.P):
81 dft_hang[i] = self.DFT1D(F_xy_p[i])
82 # DFT cho cÎt th˘ j
83 for j in range(self.Q):
84 dft_cot[:, j] = self.DFT1D(dft_hang[:, j])
85 return dft_cot
86
87 def step_67(self,G_uv):
88 ’’’Bi∏n Íi ng˜Òc IDFT vÓi £nh lÂc G(u,v)’’’
89 # B˜Óc 6.1 Th¸c hiªn bi∏n Íi ng˜Òc DFT
90 idft_cot = idft_hang = np.zeros((self.P, self.Q))
91 # IDFT cho hàng th˘ u
92 for i in range(self.P):
93 idft_hang[i] = self.IDFT1D(G_uv[i])
94 # IDFT cho cÎt th˘ v

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 59 / 63

 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

95 for j in range(self.Q):
96 idft_cot[:, j] = self.IDFT1D(idft_hang[:, j])
97 # B˜Óc 6.2: Nhân ph¶n th¸c £nh sau khi bi∏n Íi ng˜Òc vÓi -1 mÙ (x+y)
98 g_xy_p=self.step_2(idft_cot.real)
99 # B˜Óc 7: Rút trích £nh kích th˜Óc MxN t¯ £nh PxQ
00 # Và ây £nh cuËi cùng sau khi lÂc
01 g_xy = g_xy_p[:self.img.shape[0], :self.img.shape[1]]
02 return g_xy
03
04 def ILPF(self,D0):
05 ’’’LÂc £nh trong mi∑n t¶n sË, s˚ dˆng ILPF’’’
06 # B˜Óc 4: T§o bÎ lÂc
07 H_uv=self.lowPass_Ideals(D0)
08 # Tính F(u,v) trong mi∑n t¶n sË
09 f_p=self.step_1()
10 F_p=self.step_2(f_p)
11 F_uv=self.step_3(F_p)
12 # B˜Óc 5: Nhân £nh (elementwises) sau khi DFT vÓi bÎ lÂc H ∫thu ˜Òc
G(u,v)
13 G_uv=np.multiply(F_uv,H_uv)
14 # B˜Óc 67: K∏t qu£ lÂc
15 g_p=self.step_67(G_uv)
16 return g_p
17

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 60 / 63

 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

18
19 if __name__ == "__main__":
20 image = cv2.imread("./figures/blown_ic.tif", 0)
21 image = cv2.resize(src=image, dsize=(100, 100))
22 f_lowpass=Frequency_LowpassFilter(image)
23 ideal_img=f_lowpass.ILPF(60)
24 fig=plt.figure(figsize=(9,6))
25 ax1,ax2=fig.subplots(1,2)
26 ax1.imshow(image,cmap="gray")
27 ax2.imshow(ideal_img,cmap="gray")
28 plt.show()

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 61 / 63

 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

Ki∫m tra th¸c hành

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 62 / 63

 LÂc £nh trong mi∑n t¶n sË Highpass Frequency domain Filters

Tài liªu tham kh£o

Rafael C. Gonzalez, Richard E. Woods

Digital Image Processing (2018), Fourth Edition, Global
Edition, Pearson.
Ravishankar Chityala, Sridevi Pudipeddi
Image Processing and Acquisition using Python (2020),
Second Edition, Chapman & Hall/CRC.
Ph§m Nguyπn Minh Nh¸t
X˚ l˛ £nh (2021), Tr˜Ìng §i hÂc Công nghª Thông tin và
Truy∑n thông Viªt - Hàn.

Trieu Hai Nguyen Image Processing BM. KTPM–Khoa CNTT 63 / 63