YOMEDIA
ADSENSE
Biến đổi fourier rời rạc part 5
69
lượt xem 5
download
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ả
AMBIENT/
Chủ đề:
Bình luận(0) Đăng nhập để gửi bình luận!
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
ADSENSE
CÓ THỂ BẠN MUỐN DOWNLOAD
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
AANETWORK
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn