Download miễn phí Biến đổi Fourier rời rạc (DFT)
Nếu FFT của một ảnh trong trường hợp tổng quát là một mảng của các số
phức đầy đủ, người ta thường biểu diễn biên độ và pha của tần số củ a ảnh. Hai
yếu tố này biểu diễn tính chất của ảnh. Thông thường biên độ tần số được biểu
diễn riêng lẻ và gọi là phổ biên độ. Mặc dù vậy, như chúng ta đã nghiên cứu, pha
đóng vai trò quan trọng trong xử lý ảnh, và hợp không hợp lý khi chỉ biểu diễn
phổ biên độ của ảnh. Để biểu diễn phổ dưới dạng ảnh, tất cả các việc chúng ta
cần làm là chia biên độ của FFT thành các giá trị từ 0 đến 255 (cho ảnh 8
bit). Dù thế nào đi chăng nữa thì phổ của ảnh cũng bị suy giảm rất nhanh khi tần
số tăng lên. Vì vậy mà vùng tần số cao sẽ trở nên lu mờ khi biểu diễn phổ dưới
dạng ảnh. Để giải quyết vấn đề này chúng ta cần xử lý biên độ phổ một chút
bằng hàm log. Hàm logarit sẽ sửa độ khuếch đại, và thay thế cho hiển thị phổ
|H(u,v)| chúng ta hiển thị
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Biến đổi Fourier rời rạc (DFT)I. Mở đầu :
Phép biển đổi Fourier rời rạc là phép biến đổi Fourier được áp dụng để rời
rạc hoá một chuỗi giá trị phức.
Phép biến đổi Fourier rời rạc (DFT) được áp dụng vào nhiều ứng dụng như
lọc, nén ảnh, phóng đại ảnh. chúng ta sẽ nghiên cứu 2-D DFT và các kỹ thuật
tính toán. Đầu tiên, chúng ta sẽ xem xét DFT một chiều, sau đó mở rộng ra cho
DFT 2 chiều.
Một số khái niệm cơ bản :
DFT đối với tín hiệu tương tự :
Với một hàm liên tục một biến F(t), phép biến đổi Fourier F(f) được
định nghĩa là:
và biến đổi ngược
với j là căn bậc 2 của -1 và e biểu thị số mũ tự nhiên.
DFT đối với tín hiệu rời rạc :
Giả sử một chuỗi phức X(k) với phép lấy mẫu gồm N mẫu :
x1, x2, x3,… xk, … xN-1
Với x là số phức
Phép biến đổi Fourier của chuỗi này được biểu thị X(k) gồm N mẫu
Phép biến đổi thuận được định nghĩa :
Phép biến đổi ngược:
Với chuỗi số thực tương tự với phần ảo = 0.
II. DFT cho tín hiệu một chiều :
1. Định nghĩa :
Biến đổi Fourier 1-D cho tín hiệu thời gian rời rạc f(kT) tính
theo công thức :
1
0
2
)()(
N
k
nkNjekTfnF
Công thức này có thể viết lại dưới dạng
1
0
Ư)()(
N
n
nk
NWkfnF
ở đây 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, F(n) có dạng
)()()( njenAnF
Ký hiệu A(n), (n) gọi là phổ khuyếch đại và phổ pha của F(n).
Biến đổi ngược DFT
Hàm f(k) là biến đổi ngược DFT của F(n) cho bởi theo biểu thức
1
0
2
)(1)(
N
n
nk
N
j
enF
N
kf
Khi f(k) có thể rút ra từ F(n) và ngược lại, chúng gọi là cặp biến đổi.
Cặp biến đổi này có dạng
)()( nFkf
Mặc dù f(k) được xác định trên miền k [0,N], nó vẫn là tín hiệu tuần
hoàn với chu kỳ NT.
2. Một số tính chất của DFT :
Tính chất 1 : 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)
là kết quả của biến đổi DFT f3(n) cho bởi
F3(n) = aF1(n) + bF2(n)
ở đây a, b là hằng số và
F1(n) = DFT của f1(k)
F2(n) = DFT của f2(k)
Tính chất 2 :Tính đối xứng.
Tính đối xứng của DFT rất hay được dùng.
nk
N
jN
k
nk
N
jN
k
N
N
j
N
k
nNk
N
eekf
eekf
WkfnNF
21
0
21
0
2
1
0
)(
)(
)(
)()(
Nếu f(k) là thực thì
)()()(
1
0
.2
nFekfnNF
N
k
nk
N
j
Dấu * có nghĩa là liên hợp phức.
Tính chất 3 : Tích chập tuần hoàn.
Coi f1(k) và f2(k) là hai dãy tuần hoàn có chu kỳ N, với biến đổi
Fourier rời rạc là F1(n) và F2(n). Xem xét tích F(n1).F(n2)
khi )()(
1
0
1111
1
11
N
k
kn
NWkfnF
)()(
1
0
2222
2
22
N
k
kn
NWkfnF
và tại các vị trí n1 = n2 = n
Đặt f3(k) = IDFT của F1(n).F2(n)
hay nk
N
n
WnFnF
N
kf
1
0
213 )().(
1)(
vì vậy
W =
.=
2n-
N
2
1
11
1
2
22
1
11
1
0
2211
1
0
1
0
12
1
0
111111
)()(
)()()().(
k
N
k
kn
N
N
n
N
k
kn
N
N
k
kn
N
Wkfkf
WkfWkfnFnF
1
0
)(
1
0
22
1
0
11
1
0
1
0
1
0
)(
2211
21
21
1 2
21
1)()(
)()(1
N
n
kkkn
N
N
k
N
k
nk
N
N
n
N
k
N
k
kkn
N3
W
N
kfkf
WWkfkf
N
(k)f
Chú ý là :
0
11 1
0
)( 21
N
n
kkknW
N
ở đây l là số nguyên. Vì vậy mà
)()()( 12
1
01
113 lNkkfkfkf
N
k
ở đây k = 0 đến 2N - 1.
Biểu thức trên biểu diễn tích chập của hai tín hiệu tuần hoàn. Chú ý
rằng biêủ thức này chỉ áp dụng cho hai dãy có chung một chu kỳ, và
chiều dài của dãy tính theo biểu thức trên là 2N - 1. Kết quả này chứng
minh rằng trong DFT, tín hiệu có số mẫu lớn hơn N sẽ được biến đổi
thành dãy tuần hoàn có chu kỳ N. Khi dùng DFT cho một tín hiệu
không có chu kỳ, mà kết quả thu được từ tích hai dãy, ta sẽ phạm một
sai lầm gọi là lỗi wraparound. Đó là lý do ta phải làm cho cả hai dãy có
chu kỳ bằng nhau. Để sửa lỗi này, một số số 0 cần thêm vào cả
hai dãy để chiều dài hai dãy bằng nhau. Ví dụ, nếu một dãy có chiều dài
A, một dãy có chiều dài B, kết quả ta phải thêm các số 0 cho cả hai
dãy có chiều dài ít nhất là A + B - 1.
Với tín hiệu một chiều, người ta biểu diễn bởi một chuỗi trực giao
các hàm cơ sở. Với các hàm liên tục, khai triển chuỗi trực giao sẽ cung
cấp chuỗi các hệ số dùng trong nhiều quá trình khác nhau hay trong
phân tích hàm. Khai triển Fourier rời rạc cho DFT cho một dãy {u(n),
n=0,1,…,N-1} định nghĩa bởi:
1
0
N
n
kn
NWnukv với k=0,1,2,…,N-1
với WN = e-j2/N
Và biến đổi ngược:
1
0
1,.....,1,0,1
N
k
kn
N NnWkvN
nu
Trong xử lý ảnh người ta hay dùng phép biến đổi DFT đơn vị:
cho k = k1 + k2 + lN
các trường hợp còn lại.
1,....,1,0,1
1
0
NkWnu
N
kv
N
n
kn
N
1,....,1,0,1
1
0
NnWkv
N
nu
N
k
kn
N
Ma trận DFT thuần nhất NxN được đưa ra với:
1,01
NnkW
N
F knN
DFT là một trong số các phép biến đổi quan trọng nhất trong tín
hiệu số & xử lý ảnh. Nó có vài thuộc tính làm thu hút các ứng dụng xử lý
ảnh.
3. Các thuộc tính của DFT & DFT đơn vị:
u(n) là một chuỗi bất kỳ với n=0,1,2,….,N-1. Dịch trái vòng l mẫu của u(n)
ký hiệu u(n-l)c được định nghĩa là: u[(n-l) modulo N]. Ma trận DFT & DFT đơn vị là
đối xứng. Vì vậy: F-1 = F*
Sự mở rộng là tuần hoàn. Sự mở rộng của DFT & DFT đơn vị của một
chuỗi và phép biến đổi ngược của chúng có tính chất tuần hoàn với chu kỳ N.
DFT là phổ mẫu của chuỗi liên tục xác định u(n) mở rộng với các giá trị 0
bên ng Giới thiệu phép biển đổi Fourier rời rạc là phép biến đổi Fourier được áp
dụng để rời rạc hoá một chuỗi giá trị phức.
Ngoài khoảng [0,N-1]. Với chuỗi mở rộng 0 được định nghĩa:
00
10~
n
Nnnu
nu
khi đó phép biến đổi Fourier là:
n
N
n
jwnnujwnnuwu
1
0
)exp().()exp(~~
So sánh điều này với công thức trên ta được : )
2(~)(
N
kuku
Khi đó biến đổi DFT đơn vị trở thành:
N
u N
k )(~ 2
DFT & DFT đơn vị của chiều N có thể được bổ sung bởi một phép toán
nhanh với độ phức tạp tính toán là: NN 2log . ở đó tồn tại một tập các tính
toán gọi là phép biến đổi Fourier nhanh mà yêu cầu độ phức tạp tính toán của
DFT & DFT đơn vị là NN 2log , các phép tính ở đây là cộng & nhân số thực.
Độ chính xác tính toán phụ thuộc vào N ngay khi các phép lựa chọn đặc biệt của
thuật toán trong lớp đó. Phần lớn các thuật toán FFT nói chung yêu cầu N= 2p,
p là một số nguyên dương.
DFT & DFT đơn vị của một chuỗi liên tục thực { x(n), n=0,…,N-1} là đỗi
xứng liên hợp qua N/2.
)()()()()(
1
0
1
0...