Biến đổi fourier rời rạc part 5

Tham khảo tài liệu biến đổi fourier rời rạc part 5, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Biến đổi fourier rời rạc part 5 BiÓu thøc (6.62) cã thÓ më réng ra thµnh N 1  h(0, k 2 )e  j.2 / N .n k G (0, n 2 )  22 k2 0 N 1  h(1, k 2 )e  j.2 / N .n k G (1, n2 )  22 k 2 0 . . . ...v.v...Mçi biÓu thøc trªn biÓu diÔn DFT cña mét hµng trong ¶nh. BiÓu thøc (6.63) còng cã thÓ më réng ra thµnh: N 1  G (k1 ,0)e  j.2 / N .n k H (n1 ,0)  22 k1 0 N 1  G(k1 ,1)e  j.2 / N .n k H (n1 ,1)  22 k1 0 . . . ...v.v... C¸c biÓu thøc nµy dÉn ta ®Õn gi¶i thuËt sau ®©y tÝnh FFT hai chiÒu: 1. TÝnh 1-D FFT cho tÊt c¶ c¸c hµng, vµ chøa kÕt qu¶ vµo m¶ng trunggian. 2. DÞch chuyÓn m¶ng trung gian. 3. Rót ra 1-D FFT cho tÊt c¶ c¸c hµng cña m¶ng dÞch chuyÓn trung gian.KÕt qu¶ lµ dÞch chuyÓn cña m¶ng 2-D FFT. Chóng ta cã thÓ viÕt biÓu thøc (6.61) cã d¹ng 115 N 1 N 1  [  h(k1 , k 2 )e  j.2 / N .n k ]e  j .2 / N .n2k21 (6.64) H (n1 , n2 )  1 12 k 2 0 k1 0NÕu chóng ta ®Æt N 1  h(k1 , k 2 )e  j.2 / N .n k (6.65) G (n1 , k 2 )  11 k1 0víi k2 = 0,1,2,..., (N-1) th× N 1  j.2 / N .n2 k21  G (n1 , k1 )e (6.66) H (n1 , n2 )  k1  0víi n1 = 0,1,2,..., (N-1). C¸c biÓu thøc nµy dÉn chóng ta ®Õn thuËt to¸n tÝnh 2-D FFT sau 1. DÞch chuyÓn file ¶nh. 2. TÝnh FFT theo tõng hµng mét cña ¶nh ®· ®îc ®äc. 3.DÞch chuyÓn kÕt qu¶ trung gian. 4. Rót ra mét hµng kÒ hµng FFT cña dÞch chuyÓn kÕt qu¶ trung gian. KÕtqu¶ ta sÏ ®îc 2-D FFT. Trong c¶ hai ph¬ng ph¸p dïng ®Ó rót ra 2-D FFT, kÕt qu¶ trung gian ®Òu®· ph¶i dÞch chuyÓn. Ph¬ng ph¸p ®Çu tiªn thêng hay ®îc sö dông h¬n v×nã chØ yªu cÇu mét phÐp to¸n dÞch chuyÓn. KÕt qu¶ lµ mét dÞch chuyÓn cñam¶ng 2-D FFT, cã thÓ dïng trùc tiÕp díi d¹ng Êy mµ kh«ng ®ßi hái métphÐp dÞch chuyÓn thø hai. Ch¾c b¹n sÏ cã mét c©u hái r»ng t¹i sao chóng ta cÇn ph¶i dÞch chuyÓn.Lý do cña sù dÞch chuyÓn nµy lµ hÖ thèng cña b¹n cã thÓ kh«ng cã ®ñ bénhí kÝch ho¹t (RAM) ®Ó lu tr÷ kÕt qu¶ trung gian hoÆc lµ FFT cña ¶nh.NÕu b¹n cã ®ñ bé nhí RAM th× viÖc dÞch chuyÓn nµy lµ kh«ng cÇn thiÕt, vµb¹n cã thÓ ®äc th¼ng tõng cét tõ bé nhí kÝch ho¹t. Dï sao ®i ch¨ng n÷a th×sù lùa chän vÉn lµ ®äc th¼ng tõng cét vµ cã kÕt qu¶ trung gian chøa theohµng. NÕu lµ nh vËy, chóng ta sÏ cÇn N  N d÷ liÖu thªm vµo tõ ®Üa cøng, 116yªu cÇu thêi gian nhiÒu h¬n. Nãi mét c¸ch kh¸c, dÞch chuyÓn file dÉn ®Õntõng hµng mét trong FFT cña kÕt qu¶ trung gian, ®ßi hái nhiÒu h¬n N lÇntruy nhËp ®Üa. C©u hái b©y giê lµ lµm thÕ nµo chóng ta cã thÓ dÞch chuyÓn mét file trongtrêng hîp kh«ng thÓ chuyÓn tÊt c¶ d÷ liÖu mét lÇn vµo bé nhí kÝch ho¹t.Trong phÇn tiÕp theo chóng ta sÏ ®Ò cËp ®Õn ph¬ng ph¸p Eklundh ®Ó gi¶iquyÕt vÊn ®Ò nµy.6.5.1 Ma trËn dÞch chuyÓn tõ bé nhí ngoµi ThuËt to¸n ®îc gi¶i thÝch râ rµng nhÊt b»ng mét vÝ dô ®Æc biÖt. Xem xÐtma trËn cã kÝch thíc 7  7 ë h×nh 6.10. C¸c bíc cña thuËt to¸n thÓ hiÖn rârµng trªn h×nh 6.10. B¹n cÇn chó ý r»ng ch¬ng tr×nh ®ßi hái ba lÇn lÆp l¹i 23  23. Trong tÊt c¶ c¸c lÇn®Ó dÞch chuyÓn mét ma trËn cã kÝch thíclÆp l¹i b¹n cÇn ph¶i gi÷ l¹i trong bé nhí kÝch ho¹t t¹i hai hµng cuèi cïng,cho phÐp lÆp, tÊt c¶ lµ yªu cÇu yªu cÇu N lÇn truy nhËp ®Üa cho xö lý mét¶nh cã kÝch thíc N  N. NÕu N = 2r th× r  N sè lÇn truy nhËp ®Üa ®Ó dÞchchuyÓn mét ¶nh, Ýt h¬n nhiÒu so víi N  N lÇn truy nhËp trong c¸ch xö lý®äc mét ¶nh c¬ b¶n tõng khèi mét. Sè lÇn tru ...