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

Chia sẻ: Asg Ahsva | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

70
lượt xem 5
download

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

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ả

Chủ đề:

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

Lưu

Nội dung Text: 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 trung gian. 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 0 NÕ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 0 ví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  0 ví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Õt qu¶ 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ña m¶ng 2-D FFT, cã thÓ dïng trùc tiÕp díi d¹ng Êy mµ kh«ng ®ßi hái mét phÐ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 theo hµ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, 116
yª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 ®Õn tõng hµng mét trong FFT cña kÕt qu¶ trung gian, ®ßi hái nhiÒu h¬n N lÇn truy 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 trong trê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¶i quyÕ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Ðt ma 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íc lÆ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Þch chuyÓ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 truy nhËp ®Üa cã thÓ gi¶m xuèng bëi ®äc, vÝ dô, bèn hµng hoÆc t¸m hµng mét lóc. ThuËt to¸n trong trêng hîp tæng qu¸t cã thÓ coi nh lµ sù ph¸t triÓn cña gi¶i thuËt FFT. B¹n cÇn ph¸t triÓn hai lu ®å, mét ®Ó lùa chän hµng cã thÓ ®· ®îc thªm d÷ liÖu vµo vµ mét ®Ó ph¸t hiÖn ra phÇn tö ®· thay ®æi. Nh÷ng thuËt to¸n nµy coi nh lµ mét bµi tËp. M· cña ch¬ng tr×nh nguån cho tÊt c¶ c¸c thuËt to¸n nµy cho ë ch¬ng tr×nh 6.5. Ch¬ng tr×nh 6.5 TRANSPOS.C ch¬ng tr×nh cho dÞch chuyÓn mét ma trËn. /****************************** * Program developed by: * * M.A.Sid-Ahmed. * * ver. 1.0 1992. * * @ 1994 * ******************************/ /*This program is for obtaining the transpose of a large binary file stored on secondary memory. We assume that the file is large to the point that it would not fit in active memory, and the data type in the 117
file is character.*/ #include #include #include #include #include #include void transpose(FILE *, int, int); void main() { int N,n; char file_name[11]; FILE *fptr; float nsq; clrscr(); printf("Enter file-name to be transposed -->"); scanf("%s",file_name); fptr=fopen(file_name,"rb+"); if(fptr==NULL) { printf("%s does not exist. "); exit(1); } nsq=filelength(fileno(fptr)); N=sqrt((double)nsq); n=(int)(log10((double)(N))/log10((double)(2.0))); clrscr(); transpose(fptr,N,n); fclose(fptr); } void transpose(FILE *fptr, int N, int n) /* Algorithm */ { int N1,inc; 118
int iter,i,k; int k1,inc1; int k2,j,k3,k4; char *buff1,*buff2,tmp; long loc; buff1=(char *)malloc(N*sizeof(char)); buff2=(char *)malloc(N*sizeof(char)); N1=N/2; inc=1; inc1=2; 10 04 24 34 00 20 30 14 00 01 02 03 04 05 06 07 11 05 25 35 01 21 31 15 10 12 16 11 13 14 15 17 12 06 16 26 36 02 22 32 21 23 25 27 20 22 24 26 13 07 17 27 37 03 23 33 30 31 32 33 34 35 36 37 44 54 64 74 40 50 60 70 41 43 45 47 40 42 44 46 45 55 65 75 41 51 61 71 50 52 51 53 55 57 54 56 46 66 61 63 65 67 56 76 42 52 62 72 60 62 64 66 47 67 57 77 43 53 63 73 70 74 76 71 72 73 75 77 bíc 0 bíc 2 10 40 60 00 20 30 50 70 02 06 10 12 16 04 14 00 11 41 61 01 21 31 51 71 03 07 11 13 17 05 15 01 12 42 62 02 22 32 52 72 20 30 22 32 24 34 26 36 13 43 63 03 23 33 53 73 21 31 23 33 25 35 27 37 40 44 54 04 14 24 34 44 54 64 74 42 46 50 52 56 53 57 41 43 47 45 55 05 15 25 35 45 55 65 75 51 60 62 66 64 74 70 72 76 16 46 66 06 26 36 56 76 61 63 67 65 75 71 73 77 17 47 67 07 27 37 57 77 bíc 1 Ma trËn chuyÓn vÞ 119
H×nh 6.10 ThuËt to¸n cña Eklundh cho dÞch chuyÓn mét ma trËn. for(iter=0;iter
for(k2=0;k2
k1+=inc1 ; } inc*=2; inc1*=2; N1/=2; } §Ó kiÓm tra ch¬ng tr×nh 6.5 chóng ta sÏ ¸p dông thuËt to¸n nµy lªn ¶nh cho trong h×nh 6.11. ¶nh nµy chøa trªn ®Üa ®i kÌm theo cuèn s¸ch nµy díi file cã tªn lµ “MOHSEN.IMG”. Ch¬ng tr×nh 6.6 FFT2D.C 2-D FFT /****************************** * Program developed by: * * M.A.Sid-Ahmed. * * ver. 1.0 1992. * * @ 1994 * ******************************/ /* 2D-FFT - Using Decimation-in-time routine.*/ #define pi 3.141592654 #include #include #include #include #include #include void bit_reversal(unsigned int *, int , int); void WTS(float *, float *, int, int); void FFT(float *xr, float *xi, float *, float *, int, int ) ; void transpose(FILE *, int, int); void FFT2D(FILE *, FILE *, float *, float*, unsigned int *,int,int,int); 122
H×nh 6.11 ¶nh ®· ®îc dÞch chuyÓn, "MOHSEN.IMG". void main() { int N,n2,m,k,i; unsigned int *L; float *wr , *wi; char file_name[14]; FILE *fptr,*fptro; double nsq; clrscr(); printf(" Enter name of input file-> "); scanf("%s",file_name); if((fptr=fopen(file_name,"rb"))==NULL) { printf("file %s does not exist.\n"); exit(1); } nsq=(double)filelength(fileno(fptr)); N=sqrt(nsq); m=(int)(log10((double)N)/log10((double)2.0)); 123
k=1 ; for(i=0;i1)-1; 124