Biến đổi Fourier rời rạc (DFT)

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 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:        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 )(** kvWnunkNWnukNv N n kn N N n nkN N         ), 2 () 2 ( * kNvkNv  k=0, …. N/2 –1  ) 2 () 2 ( kNvkNv  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ù l­u 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µ: 1,....,0,10,1          NkNnW N T kn Nk XÐt biÓu thøc:     knNmk WnmhNH )( 1 ViÕt m-n =l vµ s¾p xÕp l¹i c¸c môc chóng ta cã thÓ viÕt:                  1 1 1 0 1 1 )()()(1 N ml kl N N l mNl kl N kl N km Nmk WlhlWlhWlhWN H Víi WN-l = WNN-1 (khi WNN-1)  gi¸ trÞ riªng nguån:   )(mH kkmk   hoÆc kkkH   k c¸c gi¸ trÞ riªng cña H ®­îc ®Þnh nghÜa lµ:      1 0 )( N l 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      NNN nxDFTnhDFTnx )(,)()(2  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 N2 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 )(nh vµ )(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  MnxDFTky )()( 11  x¸c ®Þnh )()( 12 kyky k k=0,….,M –1 . B­íc 4: LÊy DFT ng­îc cña )(2 ky ®Ó thu ®­îc )(2 nx sau ®ã tÝnh )()( 22 nxnx  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. ë ®ã  10,  NkDiagA k 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:       1 0 ln 1 0 ),(),( N n N km N N m WWnmulkv 0  k,l  N – 1 Vµ biÕn ®æi ng­îc cña nã lµ:        1 0 1 0 ln 2 ),( 1),( N k N l N km N WWlkvN 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 n N km N N m WWnmu N lkv 0  k,l  N – 1        1 0 1 0 ln),(1),( N k N l N km N WWlkvN 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 N2 x N2 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 :  TÝnh chÊt 1: ®èi xøng, ®¬n vÞ: FF T  ***1 FFFF   TÝnh chÊt 2 : TÝnh tuÇn hoµn ),()),( lkvNlNkv   k,l ),(),( nmuNnNmu   m,n  TÝnh chÊt 3 : LÊy mÉu phæ fourier NÕu ),(),(~ nmunmu  0  m,n  N-1 vµ 0),(~ nmu th×:   ),(),(2,2~ lkvnmuDFT N l N kU       Víi ),(~ 21 wwU lµ biÕn ®æi nhanh Fourier cña ),( ~ nmU  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(N2 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           lNkNvlNkNv  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  kmNTlklk WNA 1,0 1,0   Nlk Nnm  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µ:       1 0' 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 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 lnkm N nlmk N lnkm N mN mi nN nj jlik Nc lnkm N N m N n nlmk Nc nmhDFTWWnmhW WjihWWnnmmh ),(),( ),()','( )''()()''( '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(N2 log2 N) Ta cã thÓ tÝnh chËp vßng nh­ sau:        1 0' 1 0' 123 )','()','(),( N m N n nmxnnmmxnmx 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     0 ),( ),(~ 2 nmx nmh   nm Mnm , 1,0     0 ),( ),(~ 11 nmx nmu   nm Mnm , 1,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ã: )()( FFDHFF  Víi H lµ ma trËn vßng hai lÇn vµ D lµ ma trËn ®­êng chÐo cã c¸c thµnh phÇn cho bëi :    NlklkNlkN nmhDFTdD ),(,,    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 nh­ng 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 = 210 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 )},({ ),(),( 21 1 0 1 0 ).(/2 2121 1 2 2211 kkhDFT ekkhnnH N k N k knknNj           (6.41) ë ®©y n1 = 0,1,2 , ..., N-1 n2 = 0,1,2,..., N-1 BiÓu thøc )(/2 2211 knknNje   trong hai dÊu tæng gäi lµ h¹t nh©n cña phÐp biÕn ®æi. H(n1,n2), trong tr­êng hîp tæng qu¸t, ®Çy ®ñ cã thÓ biÓu diÔn theo: )n,(nj2121 21e )n,A(n )n,H(n  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        1 0 1 0 ).(/2 21221 1 2 2211),(1),( N n N n knknNjennH 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 ),(),( 21 )(2 21 21 bnanHekkh bkakN j   )(2 2121 21),(),( bnanN j ennHbkakh   §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. 212121 )1)(,())(,(),( 21 ) 21 )( 21 kkkkjkkj kkhekkhekkh    Hay lµ ) 2 , 2 ()1)(,( 2121 21 NnNnHkkh kk   Nãi c¸ch kh¸c, b»ng c¸ch nh©n vµo mçi ®iÓm (-1) 21 kk  tr­íc khi lÊy 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 ®é. )()( 21).(/221 21 nnHennH bnanNj    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 ).(/22121 21),(),( bnanNjennAnnH   ë ®©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)-na,-(n )],(),([),(]),([| 21 ).(/2 212121 ).(/2 21 2121 f bnanNjbnanNj i ennAnnInnIennA     ë ®©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 ))n,n f( - n ),n,(n f - (n i 212211f ë ®©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µ : N)nN,H(n 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 k1 vµ k2 d­íi d¹ng cos r k2  sinr k1  th× )(r,h)rcos,rsin h( )k,h(k 21   Vµ t­¬ng tù cho n1, n2   sinn cosn 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  (6.53) ë ®©y a,b lµ nh÷ng ®é chia. Còng nh­ vËy ),(1),( 2121 b n a nH ab bkakh  (6.54) 2.4 Gi¸ trÞ trung b×nh Møc c­êng ®é s¸ng trung b×nh trong mét ¶nh cho bëi : h N h k k k N k N      12 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 h1(k1,k2) vµ h2(k1,k2) cho bëi g n n h k k h n k n k k N k N ( , ) ( , ) ( , )1 2 1 1 2 2 1 1 2 2 0 1 0 1 21         NÕu h1(k1,k2) ®­îc x¸c ®Þnh trªn miÒn        k A k B1 10 1 0 1    , , vµ nÕu h2(k1,k2) ®­îc x¸c ®Þnh trªn miÒn        k C k D1 10 1 0 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: )k,(kh* )k,(kh 212211 Cã thÓ thÊy r»ng )n,(n)Hn,(nH )k,(kh* )k,(kh 212211212211  §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 g n n h k k h n k n k k N 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 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 h k k h k k H n n H n n1 1 2 2 1 2 1 1 2 2 1 2( , ) ( , ) ( , ). ( , )  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 2 4 4 512 2 9 12 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  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 222 2 N 1) (2m 1) N (2log 4N  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 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(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  21)1)(,(),( 2121 nnnniFFTkkI  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 0 2 2 2 1 2 2 2 1 21 )12( ),( D H       Dïng ) 2 (2 11 Nk N   ) 2 (2 22 Nk N   §¸p øng tÇn sè cña ¶nh läc cã thÓ rót ra tõ )) 2 (2), 2 (2()()( 212121 Nk N Nk N HkkIkkG  3. ¶nh ®· läc cã thÓ rót ra tõ : 21)1()},({{),( 2121 nnf kkGIFFTnni  ë ®©y  cã nghÜa lµ phÇn thùc cña phÇn n»m trong hai dÊu ngoÆc.