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 :
x
1
,

x
2
,

x
3

1
0
2
)()(
N
k
nk
N
j
ekTfnF


Công thức này có thể viết lại dới dạng





1
0
Ư)()(
N
n
nk
N
WkfnF

ở đây f(k) = f(kT) và W
N
= e

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
f
1
(n) và f
2
(n), và cả hai dãy này tuần hoàn với chu kỳ N, đợc dùng
để tính
f
3
(k) = af
1
(k) + bf
2
(k)
là kết quả của biến đổi DFT f
3

eekf
WkfnNF


















2
1
0
2
1
0
2
1
0
)(

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 f
1
(k) và f
2
(k) là hai dãy tuần hoàn có chu kỳ N, với biến đổi
Fourier rời rạc là F
1
(n) và F
2
(n). Xem xét tích F(n
1
).F(n
2
)
khi
)()(
1
0
1111
1
11



= n

Đặt f
3
(k) = IDFT của F
1
(n).F
2
(n)
hay

nk
N
n
WnFnF
N
kf




1
0
213
)().(
1
)(

vì vậy
W =

N
n
N
k
kn
N
N
k
kn
N
Wkfkf
WkfWkfnFnF



















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

0
1
1
1
0
)(
21
N
n
kkkn
W
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ú ý

= e
-j2

/N
Và biến đổi ngợc:






1
0
1, ,1,0,
1
N
k
kn
N
NnWkv
N
nu

Trong xử lý ảnh ngời ta hay dùng phép biến đổi DFT đơn vị:
cho k = k
1
+ k

NnWkv
N
nu
N
k
kn
N

Ma trận DFT thuần nhất NxN đợc đa ra với:
1,0
1








NnkW
N
F
kn
NDFT 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ị:


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
k
uku




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
)(
**
kvWnunkNWnukNv
N
n
kn
N
N
n
nkN
N







),

m,n
= h(m-n) = h[(m-n) modulo N], 0 m,n N-1
Vectơ cơ sở của DFT thuần nhất là các cột của F
*T
= F
*
, đó là:
1, ,0,10,
1









NkNnW
N
T
kn
Nk

Xét biểu thức:




kn

0
1
1
)()()(
1
N
ml
kl
N
N
l mNl
kl
N
kl
N
km
N
m
k
WlhlWlhWlhW
N
H

Với W
N
-l
= W
N
N-1
(khi W

kl
Nk
Wlh

0 k N 1
Đó là DFT đơn giản của cột đầu tiên của H
Dựa trên các thuộc tính trớc của DFT, các thuộc tính thêm vào sau đây
có thể đợc chứng minh
Thuyết chập vòng : DFT chập vòng của 2 chuỗi tuần tự cân bằng
với sản phẩm DFT của nó. Nghĩa là:
Nếu
10,)()(
1
0
12




Nnkxknhx
N
k
c

Thì DFT

NN
N
nxDFTnhDFTnx
)(,)()(

)(
1
nx
, 0 n M 1 là một chuỗi mở
rộng tơng ứng với từng cặp
)(
nh
và
)(
1
nx

Bớc 3: Cho

M
nxDFTky )()(
11

xác định
)()(
12
kyky
k


k=0,.,M 1 .
Bớc 4: Lấy DFT ngợc của
)(
2
ky

1
c
2
= c
2
c
1
, tính chất giao hoán.
C
-1
là một ma trận vòng và có thể tính toán với độ phức tạp tính toán
là O(Nlog N)
C
T
, C
1
+

C
2
và f(C) là các ma trận vòng, f(C) là một hàm tuỳ ý của C.

III. DFT hai chiều :
1. Định nghĩa:
DFT hai chiều của một ảnh NxN {u(m,n)} là một phép biến đổi tách
đợc và đợc định nghĩa nh sau:





2
),(
1
),(
N
k
N
l
N
km
N
WWlkv
N
nmu
0 k,l N 1
Cặp biến đổi DFT đơn vị đợc định nghĩa là:






1
0
ln
1
0
),(
1
),(

N
km
N
WWlkv
N
nmu
0 k,l N 1
Dạng rút gọn:
V =FUF
U=F
*
VF
*

Nếu U và V đợc ánh xạ vào các vectơ sắp xếp theo hàng u,v thì:
vFuFuv
*
,


FFF


F là một ma trận kích thớc N
2
x N
2
và là một biểu diễn của DFT đơn vị hai
chiều.
2. Tính chất của DFT hai chiều :


),(),(
2
,
2
~
lkvnmuDFT
N
l
N
k
U









Với
),(
~
21
wwU
là biến đổi nhanh Fourier của
),(
~
nmU

N
vl
N
k
N
v

2
,
22
,
2
*
0 k,l N/2 - 1
hay

lNkNvlNkNv

,,
*

0 k,l N -1
Tính chất 6 : ảnh cơ sở
ảnh cơ sở đợc cho bởi định nghĩa

ln)(*
,
1



0'
2
)''()','(),(
N
m
N
n
c
nmUnnmmhnmU
0 m,n N-1
với h(m,n)
c
= h(m module N, n module N)
Chập vòng chính là khai triển theo chu kì của h(m,n) chồng
lên miền NxN của u
1
(m,n) DFT hai chiều của h(m m, n n)
c
đối
với hai giá trị cố định m, n là








),()','(
)''()()''(
'1
'
'1
'
)()''(
1
0
1
0
)(

Theo tính chất biến đổi nhanh (P142) ta có chập vòng NxN
có thể tính toán đợc với độ phức tạp tính toán là:O(N
2
log
2
N)
Ta có thể tính chập vòng nh sau:






1
0'
1
0'



nm
Mnm
,
1,0






0
),(
),(
~
1
1
nmx
nmu



nm
Mnm
,
1,0

Ký hiệu DFT{x(m,n)}
N

tính N F trong cột đầu tiên của K là các thành phần h(m,n) đợc ánh xạ
vào theo thứ tự từ điển.
IV. Biến đổi nhanh Fourier (FFT)
1. Giới thiệu :
Phép biến đổi DFT có thể áp dụng với bất kỳ chuỗi giá trị phức nào nhng
với các chuỗi số lớn nó có thể chiếm lợng thời gian quá lớn (thời gian tỷ lệ với
bình phơng số điểm trong chuỗi)
Một thuật toán nhanh hơn đã đợc phát triển bởi Cooley và Tuky trong
những năm 1965 gọi là FFT ( phép biến đổi Fourier nhanh) yêu cầu duy nhất với
các thuật toán là số điểm của chuỗi phải bằng 2
n
. Thời gian tính toán tỷ lệ với
ví dụ: biến đổi dùng 1024 điểm với DFT lâu hơn 10 phút so với dùng FFT, FFT
làm tăng tốc độ đáng kể.
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ì N
2
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. Để ví dụ, cho N = 1024 = 2
10
ta sẽ phải tính 2
20
= 1,048,576
phép nhân số phức và một số gần bằng nh vậy các phép cộng.
2. Phép biến đổi nhanh Fourier 2 chiều :
2.1 2-D FFT
Một DFT hai chiều của tín hiệu lấy mẫu hai chiều h(k
1

(6.41)
ở đây n
1
= 0,1,2 , , N-1
n
2
= 0,1,2, , N-1
Biểu thức
)(/2
2211
knknNj
e

trong hai dấu tổng gọi là hạt nhân của phép biến
đổi. H(n
1
,n
2
), trong trờng hợp tổng quát, đầy đủ có thể biểu diễn theo:

)n,(nj
2121
21
e )n,A(n )n,H(n



Trong không gian ba chiều, A(n
1
,n





1
0
1
0
).(/2
21
2
21
1 2
2211
),(
1
),(
N
n
N
n
knknNj
ennH
N
kkh

(6.42)
2.3 Một số tính chất của 2-D DFT
Chuyển đổi. Từ định nghĩa của 2-D DFT và IDFT cho thấy
),(),(

)1)(,())(,(),(
21
)
21
)(
21
kkkk
j
kkj
kkhekkhekkh





Hay là

)
2
,
2
()1)(,(
2121
21
N
n
N
nHkkh
kk


21
),(),(
bnanNj
ennAnnH




ở đây A(n
1
,n
2
) là phổ biên độ. Nếu một ảnh với phổ tần số cho bởi
I(n
1
,n
2
) đợc lọc qua bộ lọc có đặc tuyến pha tuyến tính cho bởi biểu thức
ở trên, kết quả sẽ là

a)-na,-(n
)],(),([),(]),([|
21
).(/2
212121
).(/2
21
2121
f
bnanNjbnanNj

N)n,H(n )nN,H(n )n,(n
21
212121


H
(6.48) và N)kN,h(k
N)k,h(k )kN,h(k )k,h(k
21
212121


(6.49)
Biến đổi DFT đối xứng liên hợp khi

)n- ,(-n*H )n,H(n
2121

(6.50)
hoặc
)n- ,H(-n )n,H(n
2121

(6.51)
Quay. Nếu chúng ta đặt k
1
và k

1
2



hoặc
)
(r,H )n,H(n
21




từ định nghĩa của DFT chúng ta có thể có

h r H
( , ) ( , )

0 0
(6.52)
Điều đó có nghĩa là nếu ảnh bị quay đi một góc
0
thì phổ của nó cũng bị quay đi
một góc nh vậy.

Phân phối và chia độ. Từ biểu thức (6.1) chúng ta dễ thấy

)n,(nbH)n,(naH )k,(kh b )k,(kh a
212211212211





1
2 1 2
0
1
0
1
11
( , )

hoặc
h H

( , )0 0

Điều này có nghĩa là H(0,0) biểu diễn mức sáng của ảnh.
2.5 Tích chập và sự tơng quan
Tích chập của tín hiệu 2-D h
1
(k
1
,k
2
) và h
2
(k
1
,k

k A k B
1 1
0 1 0 1

, ,

và nếu h
2
(k
1
,k
2
) đợc xác định trên miền

k C k D
1 1
0 1 0 1


k
N
( , ) ( , ) ( , )
1 2 1 1 2 2 1 1 2 2
0
1
0
1
21







Biểu thức này đợc viết dới dạng ký hiệu
g n n h k k h k k
( , ) ( , ) ( , )
1 2 1 1 2 2 1 2Tơng quan chéo thờng đợc gọi là lọc kết hợp và dùng để phát
hiện ra phần đầu dấu hiệu các vết sắc nổi trên ảnh. Nó có thể cho thấy
rằng

h k k h k k H n n H n n
1 1 2 2 1 2 1 1 2 2 1 2
( , ) ( , ) ( , ). ( , )


2
N phép cộng phức để thu đợc 2-D FFT,
N
2
phép nhân phức trong miền tần số giữa FFT của điểm ảnh và các đáp ứng
tần số cuả bộ lọc, 2 . (N
2
/2) . log
2
N phép nhân phức cho IFFT. Mặt khác, một
bộ lọc 2-D FIR có kích thớc (2m + 1) (2m + 1) đòi hỏi (2m + 1)
2
N
2
phép
nhân để thu đợc ảnh trực tiếp trong miền không gian. Xem xét một ảnh có
kích thớc 512 512 điểm. FFT yêu cầu:
4 4 2 4 4 512 2 9 1
2
2
2 2
( ( / ) log ) ( )
N N N


20 triệu phép nhân.
Để đa ra tính toán này chúng ta coi rằng một phép nhân phức thì bằng 4
phép nhân thông thờng, và bộ lọc có pha zero. Phơng pháp không gian áp
dụng cho một bộ lọc có kích thớc 7 7 yêu cầu 7 7 512
2

c n n
/
1
2
2
2

. Cần nhắc lại là cả đáp ứng tấn số và đáp ứng xung đợc xem xét khi
làm việc với DFT.
Thuộc tính là h(n
1
, n
2
) tăng lên một cách nhanh chóng đợc xem xét khi
lựa chọn phơng án lọc. Không phụ thuộc vào kích thớc của ảnh, đa ra phép
nhân giứa đáp ứng tần số của ảnh và đáp ứng tần số của bộ lọc, và chúng ta chú
ý rằng lỗi wrapapound chỉ xuất hiện ở miền nhỏ nằm ở đờng bao của ảnh và
trong phần lớn trờng hợp lỗi này có thể bỏ qua.

Phơng pháp tần số có thể thực hiện qua các bớc sau:

1. Rút ra 2-D FFT của một ảnh 21
)1)(,(),(
2121
nn
nniFFTkkI




Dùng
)
2
(
2
11
N
k
N




)
2
(
2
22
N
k
N


Đáp ứng tần số của ảnh lọc có thể rút ra từ


ở đây có nghĩa là phần thực của phần nằm trong hai dấu ngoặc.