1
Tham khảo bài giảng ĐH Vanderbilt
BỘ MÔN KHOA HỌC MÁY TÍNH
NHẬP MÔN XỬ LÝ ẢNH
Chương 6: Biến đổi Fourier
Biên soạn: Dr Ngo Huu Phuc
Nội dung
1. Biến đổi Fourier 1D.
2. Biến đổi Fourier nhanh.
3. Biến đổi Fourier 2D.
4. Biến đổi Fourier 2D nhanh.
5. Hiển thị FFT.
6. Ứng dụng FFT.
2
Tham khảo bài giảng ĐH Vanderbilt
Giới thiệu
Đáp ứng tần số của hệ thống của hệ thống tuyến
tính 2D được cho bởi:
Nếu h(k1,k2) có k1 ≥ 0, k2 ≥ 0 và xác định trong
miền hữu hạn N × N thì:
3
Tham khảo bài giảng ĐH
Vanderbilt
)1.6(),(),(
1 2
2211
)(
2121
∑ ∑
∞
−∞=

ekkhH
ωω
ωω
Giới thiệu (tiếp)
Công thức (6.2) là tuần hoàn, với chu kỳ tuần hoàn là
2π.
Nếu chúng ta lấy mẫu dưới dạng ω1, ω2, và miền xác
định là (0 ≤ ω1 ≤ 2π) và (0 ≤ ω2 ≤ 2π), N × N mẫu,
chúng ta có thể viết
khi đó:
Công thức 6.4 là biến đổi Fourier rời rạc DFT.
Tham khảo bài giảng ĐH
Vanderbilt
4
ω
π
1 1
2
=
N
n
)3.6(
2
22
n
N
π
ω
=
( )

công thức:
Công thức này có thể viết lại dưới dạng
trong đó f(k) = f(kT) và WN = e- j2 /N . WN được gọi là hạt nhân của
phép biến đổi
Tổng quát: , với A(n),
φ
(n) gọi là phổ khuyếch đại
và phổ pha của F(n).
Tham khảo bài giảng ĐH
Vanderbilt
5
)5.6()()(
1
0
2
∑
−
=
⋅−
=
N
k
nk
N
j
ekTfnF
π
)6.6(¦)()(
1
0

∑
−
=
=
N
n
nk
N
j
enF
N
kf
π
)8.6()()( nFkf
⇔
Một vài tính chất của DFT
Tuyến tính. Nếu ta có hai dãy tuần hoàn cùng f1(n) và
f2(n), và cả hai dãy này tuần hoàn với chu kỳ N, được
dùng để tính
f3(k) = af1(k) + bf2(k) (6.9)
là kết quả của biến đổi DFT f3(n) cho bởi
F3(n) = aF1(n) + bF2(n) (6.10)
ở đây a, b là hằng số và
F1(n) = DFT của f1(k)
F2(n) = DFT của f2(k)
Tham khảo bài giảng ĐH
Vanderbilt
7
Một vài tính chất của DFT
Tính đối xứng.

−
=
−−
∑
∑
∑
=
=
=−
π
ππ
2
1
0
2
1
0
2
1
0
)(
)(
)(
)()(
∗
∗
−
=
−
=

Tham khảo bài giảng ĐH
Vanderbilt
9
∑
−
=
−
=
1
0
1111
1
11
)()(
N
k
kn
N
WkfnF
∑
−
=
−
=
1
0
2222
2
22
)()(

−−=
∑
−
=
2. Biến đổi FFT
Tính trực tiếp giá trị của DFT bao gồm N phép nhân phức
và N - 1 phép cộng phức cho mỗi giá trị của F(n).
Khi N giá trị được tính toán thì N2 phép nhân và N(N - 1)
phép cộng được tính toán.
Cũng như vậy, cho N có giá trị rất lớn, tính trực tiếp giá trị
của DFT sẽ đòi hỏi một số phép tính lớn đến mức không
thể chấp nhận được.
để giảm việc tính toán, có thể sử dụng thuật toán phân
chia thời gian và phân chia tần số, ta có FFT
Tham khảo bài giảng ĐH
Vanderbilt
10