Biến đổi ROURIER rời rạc

Chia sẻ: KTMT08 KTMT08 | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST

Báo xấu

92
lượt xem 20
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phép biến đổi Rourier rời rạc là phép biến đổi Fourier được áp dụng để rời rạc hóa một chuỗi giá trị phức. Phép biến đổi Fourier rời rạc được áp 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ỹ thuaatjj tính toán

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Biến đổi ROURIER rời rạc

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 : N 1  j 2  nk F ( n)   f ( kT )e N k 0 C«ng thøc nµy cã thÓ viÕt l¹i díi d¹ng N 1  f (k ) ¦ WN nk  F ( n)  n 0 ë ®©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 F (n)  A(n)e j ( n ) 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 2 N 1 j nk 1  F ( n)e N f (k )  N n 0 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 f ( k )  F ( n) 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 b iÕ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. N 1 F ( N  n)   f (k )WN k ( N  n ) k 0 2 2 N 1 j N j nk   f ( k )e N N e k 0 2 N 1 j n k   f ( k )e e N k 0  2  N 1  j .nk  F ( N  n)    f ( k )e N   F ( n)  NÕu f(k) lµ thùc th×  k 0    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) N 1  f1 (k1 )W N n k  khi 11 F1 ( n1 )  k1 0 N 1  f 2 (k 2 )W N n k  22 F2 ( n2 )  k 2 0 vµ t¹i c¸c vÞ trÝ n1 = n2 = n N 1 N 1 F1 ( n1 ).F1 ( n1 ) =  f 1 ( k1 )W N n1k1 .  f 2 ( k1 )W N n2 k 2 k1  0 k2 0 N 1 N 1 =   f 1 ( k1 ) f 2 ( k 2 )W N n1k1 WNn 2 k 2 - k1  0 n1  0 §Æt f3(k) = IDFT cña F1(n).F2(n) N 1 1  F1(n).F2 (n)W nk hay f3 (k )  N n 0 v× vËy
N 1 N 1 N 1  1    f1 ( k1 ) f 2 ( k 2 )W N n ( k1  k2 ) W N  nk  f 3 (k)  N  n 0  k1 0k2 0  N 1 N 1  1 N 1     f1 ( k1 )  f 2 ( k 2 )   W N n ( k1  k2 k )   N n 0    k1 0 k 2 0 cho k = k1 + k2 + lN N 1 1 1 W  n(k1  k2  k )  0 Chó ý lµ : c¸c trêng hîp cßn l¹i. N  n 0 ë ®©y l lµ sè nguyªn. V× vËy mµ N 1  f1 (k1 ) f 2 (k  k1  lN ) f 3 (k )  k10 ë ®©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 ph¶i 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: N 1 v k    u n W kn víi k=0,1,2,…,N -1 N n0 víi WN = e-j2/N Vµ biÕn ®æi ngîc: N 1 1 u n    vk W  kn , n  0,1,....., N  1 N N k 0 Trong xö lý ¶nh ngêi ta hay dïng phÐp biÕn ®æi DFT ®¬n vÞ:
N 1 1 vk    u n W kn k  0,1,...., N  1 , N N n0 N 1 1 u n    vk W  kn n  0,1,...., N  1 , N N k 0 Ma trËn DFT thuÇn nhÊt NxN ®îc ®a ra víi: 1  W Nkn  F  0  k, n  N 1 N  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:  un 0  n  N 1 ~ u n n0 0 khi ®ã phÐp biÕn ®æi Fourier lµ:  N 1 ~ ~ u w   u nexp( jwn)   u(n).exp( jwn) n n 0 ~ 2 k ) So s¸nh ®iÒu nµy víi c«ng thøc trªn ta ®îc : u ( k )  u ( N Khi ®ã biÕn ®æi DFT ®¬n vÞ trë thµnh: u ( ) 2k ~ N N 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µ:   N log 2 N  . ë ®ã 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µ   N log 2 N  , 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. N 1 N 1 ( N k ) n * * kn v ( N  k )  u (n)WN ( N  k )n  u(n)WN  v(k ) n0 n0 N N k=0, …. N/2 –1  k)  v*(  v(  k ), 2 2 N N  v(  k )  v(  k) 2 2 Cã thÓ nãi r»ng DFT hoÆc DFT ®¬n vÞ cña chuçi tuÇn tù thùc Nx1 cã N møc vµ thø tù lu tr÷ ph¶i gièng thø tù chuçi u(n). C¸c vect¬ c¬ së cña DFT ®¬n vÞ lµ vect¬ trùc giao cña bÊt kú ma trËn tuÇn hoµn nµo. C¸c gi¸ trÞ riªng cña ma trËn tuÇn hoµn ®îc cho bëi DFT cña cét ®Çu tiªn cña nã. Cho H lµ mét ma trËn (circulant).  nã tho¶ m·n: [H]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µ: T 1  W N kn ,0  n  N  1 , k  0 ,...., N  1 k   N  1 XÐt biÓu thøc:  H  k m   kn  h ( m  n )W N N ViÕt m-n =l vµ s¾p xÕp l¹ i c¸c môc chóng ta cã thÓ viÕt:  N 1 1 N 1 1  H k m W N km   h (l )W Nkl   h (l )W Nkl l   h (l )W Nkl   N  l 0  l   N  m 1 l  m 1 Víi WN-l = WNN-1 (khi WNN-1)  gi¸ trÞ riªng nguån: H  k m   k  k ( m ) hoÆc H  k   k  k c¸c gi¸ trÞ riªng cña H ®îc ®Þnh nghÜa lµ: k  N 1 kl 0  k  N –1  h ( l )W k  N l0 §ã 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 1 NÕu x 2   h(n  k ) x1 ( k ),0  n  N  1 c k 0 Th× DFT x 2 ( n )N  DFT h ( n )N DFT x , ( n )N
DFT {x(n)}N chØ râ DFT cña chuçi tuÇn tù x(n) kÝch thíc N. §iÒu ®ã cã nghÜa lµ ®Ó tÝnh chËp vßng, tríc tiªn chóng ta tÝnh DFT cña x2(n), sau ®ã tÝnh DFT ngîc cña nã. Sö dông DFT sÏ ®¹t ®îc ® é phøc t¹p tÝnh to¸n lµ:O (Nlog2N) so víi íc lîng trùc tiÕp N 2 phÐp tÝnh. ChËp tuyÕn tÝnh cña 2 chuçi tuÇn tù cã thÓ ®¹t ®îc trong FFT b»ng viÖc nhóng nã vµo 1 ChËp vßng. Tæng qu¸t, chËp tuyÕn tÝnh cña 2 chuçi tuÇn tù {h(n),n=0,….,N -1} vµ {x1(n),n=0,…,N-1} lµ mét chuçi tuÇn tù: {x2(n),0  n  N’ +N – 2} vµ cã thÓ thu ®îc b»ng thuËt to¸n sau: Bíc 1: cho M  N’ + N –1 lµ mét sè nguyªn Bíc 2: X¸c ®Þnh h (n) vµ x1 (n) , 0  n  M – 1 lµ mét chuçi më réng t¬ng øng víi tõng cÆp h (n) vµ x1 (n) Bíc 3: Cho y1 (k )  DFT x1 (n)M x¸c ®Þnh y 2 ( k )   k y1 ( k ) k=0,….,M –1 . Bíc 4: LÊy DFT ngîc cña y 2 (k ) ®Ó thu ®îc x 2 (n) sau ®ã tÝnh x 2 ( n)  x 2 ( n) víi 0  n  N+N’ – 2. BÊt kú ma trËn nµo còng cã thÓ ®îc chÐo ho¸ bëi DFT/DFT ®¬n vÞ: FHF* = A. ë ®ã A  Diag  k ,0  k  N  1 vµ k ®îc cho bëi ( c,c1,c2 lµ c¸c ma trËn vßng víi c¸c tÝnh chÊt: c1c2 = c2c1, 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) CT, C1 + C2 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: N 1 N 1 km ln 0  k,l  N – 1  v(k , l)  u ( m , n )W W N N m 0 n0 Vµ biÕn ®æi ngîc cña nã lµ: N 1 N 1 1  km W N ln 0  k,l  N – 1   v ( k , l )W u (m , n)  N N2 k 0 l0 CÆp biÕn ®æi DFT ®¬n vÞ ®îc ®Þnh nghÜa lµ: N 1 N 1 1 km ln 0  k,l  N – 1  v(k , l)  u ( m , n )W W N N N m 0 n0
N 1 N 1 1  km W N ln 0  k,l  N – 1   v ( k , l )W u (m , n)  N N k 0 l0 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×: * v  Fu , u  F v FFF F lµ mét ma trËn kÝch thíc N x N2 vµ lµ mét biÓu diÔn cña DFT ®¬n vÞ hai 2 chiÒu. 2. TÝnh chÊt cña DFT hai chiÒu :  TÝnh chÊt 1: ®èi xøng, ®¬n vÞ: F 1  F *  F *  F * FT  F  TÝnh chÊt 2 : TÝnh tuÇn hoµn v(k  N ), l  N )  v(k , l )  k,l u (m  N , n  N )  u (m, n)  m,n  TÝnh chÊt 3 : LÊy mÉu phæ fourier ~ ~ NÕu u (m, n)  u (m, n) 0  m,n  N-1 vµ u (m, n)  0 th×: ~  2k 2l    DFT u ( m, n)  v( k , l ) U , N N ~ ~ Víi U ( w1 , w2 ) lµ biÕn ®æi nhanh Fourier cña U (m, n)  TÝnh chÊt 4 : BiÕn ®æi nhanh V× DFT hai chiÒu lµ t¸ch ®îc, biÕn ®æi t¬ng ®¬ng víi 2N phÐp DFT mét chiÒu víi ®é phøc t¹p tÝnh to¸n O(N log2 N) theo c¸ch tÝnh FFT. Do vËy ®é phøc t¹p tÝnh to¸n tæng lµ: O(N 2 log2 N).  TÝnh chÊt 5 : §èi xøng kÕt hîp BiÕn ®æi DFT vµ DFT ®¬n vÞ cña ¶nh thùc cã tÝnh ®èi xøng kÕt hîp N N N N   v  k ,  l   v *   k ,  l  0  k,l  N/2 - 1 2 2 2 2   hay vN  k , N  l   v * N  k , N  l  0  k,l  N -1  TÝnh chÊt 6 : ¶nh c¬ së ¶nh c¬ së ®îc cho bëi ®Þnh nghÜa 1 0  m, n  N  1  Ak ,l   k  T  * W N ( km  ln) l N 0  k,l  N 1  TÝnh chÊt 7: §Þnh lý chËp vßng hai chiÒu:
DFT cña chËp vßng hai chiÒu cña hai m¶ng lµ tÝch c¸c DFT cña chóng. ChËp vßng hai chiÒu cña hai m¶ng NxN U(m,n) x U1(m,n) ®îc ®Þnh nghÜa lµ: N 1 N 1 0  m,n  N-1   h(m  m ' , n  n' ) U 2 (m, n)  U ( m ' n ' ) c m ' 0 n ' 0 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 u1(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µ N 1 N 1 N 1 m ' N 1 n ' W N( mk  nl )  W N( m 'k  n 'l ) W N( ik  jl )   h(m  m' , n  n' )   h (i , j ) c c m 0 n0 im' jn'  W N( m 'k  n 'l )   h ( m , n )W N( mk  nl )  W N( m 'k  n 'l ) DFT h ( m , n )N 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 log2 N) Ta cã thÓ tÝnh chËp vßng nh sau: N 1 N 1  x3 (m , n )  x 2 ( m  m ' , n  n ' ) x1 ( m ' , n ' ) m ' 0 n ' 0 Víi x1(m,n) & x2(m,n) ®îc gi¶ thiÕt =  Víi m,n  [0,M – 1] miÒn x¸c ®Þnh x3(m,n) lµ {0  m,n  2M –2} §Æt N  2M –1 & ®Þnh nghÜa m¶ng NxN   x (m , n) 0  m, n  M  1 ~ h (m , n)   2 m, n  0    x (m, n) 0  m, n  M  1 ~ u1 (m , n )   1 m, n  0  Ký hiÖu DFT{x(m,n)}N lµ DFT hai chiÒu cña m¶ng NxN x(m,n) 0  m,n  2M –1  TÝnh chÊt 8 : Chia theo c¶ hai chiÒu theo N & sö dông ®Þnh nghÜa tÝnh knoncker ta cã: ( F  F ) H  D( F  F ) Víi H lµ ma trËn vßng hai lÇn vµ D lµ ma trËn ®êng chÐo cã  D kN  l ,kN  l  d k ,l  DFT h ( m , n )N c¸c thµnh phÇn cho bëi : 0 k,l  N-1 Tõ c¸c tÝnh chÊt cña phÐp biÕn ®æi nhanh ta cã thÓ rót ra: Mét ma trËn vßng khèi hai lÇn cã thÓ ®îc chÐo ho¸ b»ng O( N2 log2 N) phÐp to¸n.TrÞ riªng cña K cho bëi DFT hai chiÒu cña h(m,n) gièng nh phÐp
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 2n. 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× 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. §Ó vÝ dô, cho N = 1024 = 2 10 ta sÏ ph¶i tÝnh 220 = 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(k1,k2) cho bëi N 1 N 1   h(k1 , k 2 )e  j 2 / N .(n k n k ) H ( n1 , n2 )  11 22 (6.41) k1 0k2 0  DFT {h( k1 , k 2 )} ë ®©y n1 = 0,1,2 , ..., N-1 n2 = 0,1,2,..., N-1 BiÓu thøc e  j 2 / N ( n k  n k ) trong hai dÊu tæng gäi lµ h¹t nh©n cña phÐp biÕn 11 22 ®æi. H(n1,n2), trong trêng hîp tæng qu¸t, ®Çy ®ñ cã thÓ biÓu diÔn theo: H(n1 , n2 )  A(n1 , n2 ) e j (n1 ,n2 ) Trong kh«ng gian ba chiÒu, A(n1,n2) vµ (n1,n2) n»m t¹i vÞ trÝ cña n1 vµ n2 vµ gäi lµ phæ tÇn sè vµ phæ pha cña H(n1,n2).
2.2 BiÕn ®æi ngîc 2-D DFT Hµm h(k1,k2) lµ biÕn ®æi ngîc cña 2 -D DFT (IFFT) cña H(n1,n2) vµ ®îc cho bëi biÓu thøc N 1 N 1 1   H (n1 , n2 )e j 2 / N .(n k n k ) (6.42) h( k1 , k 2 )  11 22 2 N n1 0n2 0 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 j 2 ( ak1  bk 2 ) N h( k 1 , k 2 ) e  H (n1  a, n 2  b) j 2 ( n1a  n2 b ) N h(k1  a, k 2  b)  H (n1 , n 2 )e §iÒu ®ã cã nghÜa lµ mét dÞch chuyÓn pha tuyÕn tÝnh trong mét miÒn biÓu diÔn b»ng mét dÞch chuyÓn h»ng sè trong mét miÒn kh¸c. Xem xÐt biÓu thøc (6.43), trêng hîp ®Æc biÖt khi a = b = N/2 . h(k1 , k 2 )e j ( k1  k2 )  h(k1 , k 2 )(e j ) k1  k2 )  h(k1 , k 2 )(1) k1  k2 Hay lµ N N h( k1 , k 2 )( 1) k1  k2  H ( n1  , n2  ) 2 2 Nãi c¸ch kh¸c, b»ng c¸ch nh©n vµo mçi ®iÓm (-1) k  k tríc khi lÊy 1 2 DFT, chóng ta sÏ rót ra ®îc mét phæ tÇn sè mµ ®iÓm tÇn sè (0,0) cña nã sÏ n»m gi÷a m¶ng 2-D. BiÓu thøc nµy rÊt h÷u dông trong hiÓn thÞ phæ tÇn sè, phæ biªn ®é vµ läc dïng DFT. Chóng ta rót ra kÕt luËn tõ c«ng thøc trªn r»ng dÞch chuyÓn mét h»ng sè trong ¶nh sÏ kh«ng t¸c ®éng ®Õn phæ biªn ®é. H ( n1  n2 )e  j 2 / N .( n1a  n2b )  H ( n1  n2 ) BiÓu thøc ®ã còng quan hÖ ®Õn bé läc 2 -D. Xem xÐt ®Æc tÝnh cña bé läc 2-D cho bëi H (n1 , n2 )  A(n1 , n2 )e  j 2 / N .( n1a  n2b ) ë ®©y A(n1,n2) lµ phæ biªn ®é. NÕu mét ¶nh víi phæ tÇn sè cho bëi I(n1,n2) ®î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( n1 , n2 )e  j 2 / N .( n1a  n2b ) ]I ( n1 , n2 )  [ I ( n1 , n2 ) A( n1 , n2 )]e  j 2 / N .( n1a  n2b )  i f (n 1 - a, n 2 - a)
ë ®©y if (n1-a, n2-b) ký hiÖu cho ¶nh ®· ®îc läc. Mét bé läc víi ®Æc tuyÕn pha tuyÕn tÝnh cã nghÜa lµ kh«ng dÞch chuyÓn biªn ®é. Trong khi ®ã nÕu bé läc cã ®Æc tuyÕn pha kh«ng tuyÕn tÝnh th× pha cña ¶nh còng bÞ biÕn d¹ng. Lý do cña sù biÕn d¹ng nµy lµ tÊt c¶ c¸c ®iÓm ®Òu ph¶i chÞu mét sù dÞch chuyÓn vÞ trÝ kh¸c nhau tuú theo vÞ trÝ cña ¶nh. Tæng qu¸t, ¶nh ®· ®îc läc cã thÓ cho bëi i f (n1 - f (n1 , n2 ), n2 - f( n1 , n2 )) ë ®©y f lµ hµm dÞch chuyÓn vÞ trÝ. Chó ý r»ng mét ¶nh biÕn d¹ng pha sÏ xuÊt hiÖn trªn mµn h×nh nh mét ¶nh mê .  TÝnh ®èi xøng liªn hîp vµ tuÇn hoµn. BiÕn ®æi2-D DFT vµ IDFT tuÇn hoµn víi chu kú N cã nghÜa lµ : H(n1 , n2 )  H(n1  N, n2 )  H(n1 , n2  N) (6.48) vµ  H(n1  N, n2  N) h(k 1 , k 2 )  h(k 1  N, k 2 )  h(k 1 , k 2  N) (6.49)  h(k 1  N, k 2  N) BiÕn ®æi DFT ®èi xøng liªn hîp khi H(n1 , n2 )  H * (-n1 , - n2 ) (6.50) hoÆc (6.51) H(n1 , n2 )  H(-n1 , - n2 )  Quay. NÕu chóng ta ®Æt k1 vµ k2 díi d¹ng k 2  r cos k 1  r sin th× h(k 1 , k 2 )  h( rsin , rcos )  h (r, ) Vµ t¬ng tù cho n1, n2 n2   cos n1   sin hoÆc H(n1 , n2 )  H (r, ) tõ ®Þnh nghÜa cña DFT chóng ta cã thÓ cã (6.52) h(r ,   0 )  H ( ,   0 ) §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 (6.53) a h1 (k 1 , k 2 )  b h2 (k 1 , k 2 )  aH 1 (n1 , n2 )  bH 2 (n1 , n2 )
ë ®©y a,b lµ nh÷ng ®é chia. Còng nh vËy nn 1 H( 1 , 2 ) (6.54) h(ak1 , bk 2 )  ab ab 2.4 Gi¸ trÞ trung b×nh Møc cêng ®é s¸ng trung b×nh trong mét ¶nh cho bëi : N 1 N 1 1   h( k , k h ) N2 1 2 k1  0 k1  0 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 h1(k1,k2) vµ h2(k1,k2) cho bëi N 1 N 1   h (k , k g ( n1 , n2 )  ) h2 ( n1  k 1 , n2  k 2 ) 1 1 2 k1  0 k 2  0 NÕu h1(k1,k2) ®îc x¸c ®Þnh trªn miÒn  k    0, A  1  k1 0, B  1 1 vµ nÕu h2(k1,k2) ®îc x¸c ®Þnh trªn miÒn k   0, C  1   k 1 0, D  1 1 th× chóng ta cã thÓ thÊy r»ng nÕu hai tÝn hiÖu cã gi¸ trÞ zero ngoµi miÒn x¸c ®Þnh cña chóng th× M = A + C - 1 vµ N = B + D - 1. TÝch chËp cña hai tÝn hiÖu 2-D ®îc viÕt trong d¹ng ký hiÖu nh sau: h1 (k 1 , k 2 )* h2 (k 1 , k 2 ) Cã thÓ thÊy r»ng h1 (k 1 , k 2 )* h2 (k 1 , k 2 )  H 1 (n1 , n2 )H 2 (n1 , n2 ) §iÒu nµy cã nghÜa lµ, tÝch chËp trong miÒn kh«ng gian biÕn thµnh phÐp nh©n b×nh thêng trong miÒn tÇn sè. TÝnh chÊt nµy cã thÓ dïng cho läc 2-D qua DFT. Chóng ta cÇn nhí l¹i r»ng b¹n ®· dïng kü thuËt läc FIR trong c¸c ch¬ng tríc cho chøc n¨ng nµy. Khi ¸p dông c¸c läc bé läc FIR cho chøc n¨ng läc b¹n cÇn lÊy tÝn hiÖu kho¶ng c¸ch 2-D ®· ®îc biÕn thµnh tÝn hiÖu cã chu kú tríc khi tiÕn hµnh lÊy DFT. Sù kh«ng ®ång bé cña chu kú trong biÕn ®æi nµy còng g©y ra lçi nh trong biÕn ®æi 1-D. V× vËy, ®Ó tr¸nh trêng hîp nµy ta cÇn thªm c¸c sè 0 vµo c¶ hai c¸c hµm kh«ng gian ®Ó cho chóng cã kÝch thíc M  N víi M  A + C - 1 vµ N  B + D - 1. T¬ng quan hoÆc t¬ng quan chÐo cña tÝn hiÖu 2 -D ®Þnh nghÜa bëi
N 1 N 1   h (k , k g ( n1 , n2 )  ) h2 ( n1  k 1 , n2  k 2 ) 1 1 2 k1  0 k 2  0 BiÓu thøc nµy ®îc viÕt díi d¹ng ký hiÖu g (n1 , n2 )  h1 ( k 1 , k 2 ) h2 ( k 1 , k 2 ) T¬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 h1 ( k 1 , k 2 ) h2 ( k 1 , k 2 )  H1 (n1 , n2 ). H 2 (n1 , n2 ) 3. HiÓn thÞ FFT 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 ph¶i 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Þ: D(u,v) = log10(1+|H(u,v)|) BiÓu thøc nµy cho ta gi¸ trÞ zero khi D(u,v) = 0 hay |H(u,v)| = 0 vµ nh vËy D(u,v) lu«n lu«n cã gi¸ trÞ d¬ng. §iÓm tÇn sè (0,0) n»m ë trung t©m mµn h×nh. Chó ý phæ ¶nh gi¶m xuèng rÊt nhanh chãng khi tÇn sè t¨ng lªn. 4. Bé läc hai chiÒu dïng FFT NÕu dïng tÝch chËp ®Ó chuyÓn hµng lo¹t c¸c phÇn tö tõ miÒn kh«ng gian sang miÒn tÇn sè ta nªn ¸p dông FFT. PhÐp biÕn ®æi nµy yªu cÇu 2. (N2/2). log2N phÐp nh©n phøc vµ 2. N2. log2N phÐp céng phøc ®Ó thu ®îc 2-D FFT, N2 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 . (N2/2) . log2N 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 N2 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( N 2 / 2) log 2 N )  4 N 2  4  512 2  ( 2  9  1)  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  5122  13 triÖu phÐp nh©n. NÕu kÝch thíc bé läc t¨ng lªn th× ph¬ng ph¸p ph©n chia miÒn tÇn sè cã thÓ ¸p dông. Mét bé läc cã kÝch thíc 11  11 yªu cÇu kho¶ng 30 triÖu phÐp nh©n sÏ chØ cÇn kho¶ng 19 triÖu phÐp nh©n khi ¸p dông ph¬ng ph¸p ph©n chia miÒn tÇn sè. Hai ph¬ng ph¸p nµy sÏ cã cïng mét sè phÐp nh©n nÕu 4N 2 (2log 2 N  1)  (2m  1)2 N 2 Cho mét ¶nh cã kÝch thíc 512  512 (2m + 1)  9, dÔ chøng minh lµ nÕu kÝch thíc bé läc nhá h¬n 9 th× ta cã thÓ ph¬ng ph¸p ph©n chia kh«ng gian. Tuy nhiªn, cÇn chó ý ph¬ng ph¸p ph©n chia tÇn sè còng yªu cÇu Ýt thêi gian xö lý h¬n do sè lÇn truy nhËp ®Üa gi¶m xuèng. ¦u ®iÓm nµy ®îc t¨ng lªn khi kÝch thíc cña bé läc lín h¬n 9  9. ¦u ®iÓm nµy sÏ kh«ng cßn n÷a khi xÐt ®Õn lçi wraparound. §Ó tr¸nh lçi nµy ta ph¶i t¨ng gÊp bèn lÇn kÝch thíc cña ¶nh. Cho mét ¶nh cã kÝch thíc 512  512 ta cÇn ph¶i t¨ng lªn 1024  1024. §Ó tr¸nh c¸c phÐp tÝnh to¸n qu¸ lín khi chó ý r»ng h(n1, n2) cña mét bé läc khi rót ra IFFT sÏ t¨ng lªn rÊt nhanh khi n1, n2 t¨ng lªn. TÝnh chÊt nµy cµng næi bËt khi më réng Fourier chØ chÌn c¸c gi¸ trÞ zero vµo c¸c gi¸ trÞ cuèi cña bé läc tõ c / n12  n2 . CÇn nh¾c l¹i lµ c¶ ®¸p øng tÊn sè vµ ®¸p øng xung ®îc xem xÐt khi 2 lµm viÖc víi DFT. Thuéc tÝnh lµ h(n1, n2) 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   I (k1 , k 2 )  FFT i(n1 , n2 )(1) n1  n2 2. Nh©n I(k1, k2) víi ®Æc tuyÕn cña bé läc, chó ý lµ ®¸p øng tÇn sè cã gèc to¹ ®é n»m t¹i (N/2, N/2). Cho vÝ dô mét bé läc th«ng cao Butterworth cã ®Æc tuyÕn nh sau: 2 2 1   2 H (1 ,  2 )  2 2 2 1   2  ( 2  1) D0 N N 2 2 Dïng (k1  ) (k 2  ) 1  2  N N 2 2 §¸p øng tÇn sè cña ¶nh läc cã thÓ rót ra tõ
N2 N 2 G ( k1  k 2 )  I ( k1  k 2 )  H ( ( k1  ), ( k 2  )) N 2N 2 3. ¶nh ®· läc cã thÓ rót ra tõ : i f ( n1 , n2 )  {IFFT {G ( k1 , k 2 )}  ( 1) n1  n2 ë ®©y  cã nghÜa lµ phÇn thùc cña phÇn n»m trong hai dÊu ngoÆc.