345 Các biểu thức trên cho kết quả của bớc thứ hai trên sơ đồ hình (13.5) trong trờng hợp N = 8. Đặt )2()( 0010 kYkY (13.31) )12()12()( 000011 kYkYkY (13.32) Vì vậy )2()( 0112 kYkY (13.33) )12()12()( 010012 kYkYkY (13.34) 14/ 0 1010 ) 4 (2 )14( cos)()( N n N kn nxkY (13.35) 14/ 0 1111 ) 4 (2 )14( cos)()( N n N kn nxkY (13.36) 14/ 0 1212 ) 4 (2 )14( cos)()( N n N kn nxkY (13.37) 14/ 0 1212 ) 4 (2 )14( cos)()( N n N kn nxkY (13.38) Nếu N = 8, các biểu thức trên có dạng: 4 5 cos)1( 4 cos)0()( 101010 k x k xkY (13.39) 4 5 cos)1( 4 cos)0()( 111111 k x k xkY (13.40) 4 5 cos)1( 4 cos)0()( 121212 k x k xkY (13.41) 4 5 cos)1( 4 cos)0()( 131313 k x k xkY (13.42) ở đây k = 0,1. Các biểu thức cuối có thể biểu diễn thành Y 10 (0) = x 10 (0) + x 10 (1) 346 Y 10 = (x 10 (0) - x 10 (1))cos(/4) v v Các biểu thức này dẫn chúng ta đến lu đồ bớm cuối cùng trình bày ở hình 13.6. Để rút ra tín hiệu đầu ra của lu đồ FCT chúng ta cần quay trở lại. Cho ví dụ, từ biểu thức (13.21) và (13.15) chúng ta có thể viết: X(4k) (k)Y 10 (13.43) Hình 13.6 Bớm cuối cùng trong FCT. x 11 (0) x 11 (1) Y 11 (0) Y 11 (1) 1 C 4 - 1 x 12 (0) x 12 (1) Y 12 (0) Y 12 (1) 1 C 4 - 1 x 14 (0) x 14 (1) Y 14 (0) Y 14 (1) 1 C 4 - 1 x 13 (0) x 13 (1) Y 13 ( 0) Y 13 (1) 1 C 4 - 1 x 10 (0) x 10 (1) Y 10 (0) Y 10 (1) 1 C 4 - 1 Bớc cuối cùng của các thao tác bớm. Đầu ra Bitdịch chuyển 000 001 010 011 100 101 0 1 2 3 4 5 X(0) X(4) 2X(2) X(6)+X(2) 2X(1) X(5)+X(3) Dịch chuyển bit 000 100 010 110 001 101 0 4 2 6 1 5 347 H×nh 13.7 TÝn hiÖu ra cuèi cïng cña thuËt to¸n bím tÝnh díi d¹ng hÖ sè FCT. H×nh 13.8 TÝn hiÖu ra sau dÞch chuyÓn bÝt. X(0) 2X(1) 2X(2) 2(X(3)+X(1)) X(4) X(5)+X(3) X(6)+X(2) X(7)+X(5)+X(3)+X(1) 0 1 2 3 4 5 6 7 DÞch chuyÓn bit - 1 - 1 - 1 2 1 2 1 2 1 X(0) X(1) X(2) X(3) X(4) X(5) DÞch chuyÓn bit 348 Hình 13.9 Bớc cộng truy hồi. Tơng tự, chúng ta có thể rút ra từ các biểu thức (13.32) đến (13.34) và (13.15) các biểu thức dới đây: 2)-X(4k2)X(4k (k)Y 11 (13.44) 1)-X(4k1)X(4k (k)Y 12 (13.45) 3)-X(4k 1)-X(4k 1)X(4k 3)X(4k (k)Y 13 (13.46) Vì vậy, tín hiệu ra từ các bớc cuối cùng của các thao tác bớm có thể tính dới dạng các hệ số của FCT nh trong hình 13.7. Nếu chúng ta sắp xếp lại vị trí của các giá trị bít dùng dịch chuyển bít, chúng ta rút ra tín hiệu ra nh hình (13.8). Sau đó,các tín hiệu ra này có thể đợc dùng để rut ra FCT nh hình (13.9). Bớc cuối cùng này gọi là bớc cộng truy hồi. Có rất nhiều bớc (các thao tác bớm, dịch chuyển bít, và cộng truy hồi) bây giờ có thể nằm trong một bớc trong hình 13.10. Từ sơ đồ này, chơng trình FCT có thể phát triển. Chơng trình này dùng các thuật toán phát triển cho FFT. Chơng trình dùng một bảng tra cứu để chứa các giá trị cosin, một bảng cho dịch chuyển bit. Chi tiết của chơng trình này để lại cho ngời dùng nh một bài tập. Bài tập13.5 1. Phát triển lu đồ cho DCT 16 và 32 điểm. 2. Sử dụng logic tơng tự đã đợc dùng cho việc phát triển chơng trình FFT, để viết một thuật toán cho FCT. 349 2-D FCT của một dãy 2-D thực đợc cho bởi (13.47) Thuật toán cho 2-D FCT có thể phát triển dùng phơng pháp hàng-cột bình thờng nh thuật toán 2-D FFT. Chơng trình 13.5 rút ra biến đổi FCT của các khối ngời dùng tự xác định kích thớc, thông thờng là 8 8 hoặc là 16 16, bằng các chia nhỏ các khối của ảnh. ảnh đợc giả sử là có chiều dài bằng chiều rộng với cac chiều là bội của 2. Chơng trình sử dụng thuật toán 1-D FCT và tận dụng các bảng tra cứu (LUT) nh các trạng thái trớc. Chơng trình 13.5 FCT2D.C 2-D FCT các khối ảnh (ngời dùng tự xác định kích thớc). /*Program 13.5 "FCT2D.C". 2-D FCT of image blocks (user-pecified).*/ /* This program is for carrying out 2-D Fast Cosine Transform of blocks subdividing a given image. Block size is user specified. */ #define PI 3.14159 #include <stdio.h> #include <math.h> #include <alloc.h> #include <conio.h> #include <io.h> #include <process.h> void FCT(float *, unsigned int *, float *, int , int ); void bit_reversal(unsigned int *, int , int ); void WTS(float *,int , int ); void main() { int m,N,i,j,k1,k2,NB,NS,NT,k; float *x,*C,**w; 1 0 2 22 1 11 21 1 0 2 21 21 2 2 1 1 2 )12( cos 2 )12( cos),( 4 ),( N n N n kk N kn N kn nnx N kkX 350 unsigned int *L; double nsq; FILE *fptri,*fptro; char file_name[14]; float *buffi; unsigned char *buffo; clrscr(); printf("Enter name of input file >"); scanf("%s",file_name); fptri=fopen(file_name,"rb"); if(fptri==NULL) { printf("No such file exists.\n"); exit(1); } nsq=(double)filelength(fileno(fptri)); /* Assume image is square. */ N=(int)sqrt(nsq); m=(int)(log10((double)N)/log10((double)2.0)); k=1 ; for(i=0;i<m;i++) k<<=1; if(k!=N) { printf ("Image must have dimensions which are multiples of 2.\n"); exit(1); } printf("Enter name for output file >"); scanf("%s",file_name); fptro=fopen(file_name,"wb"); printf ("\nEnter block size (e.g. 8x8, 16x 16, etc.) > "); scanf ( "%dx%d", &NB,&NB); m=(int)(log10((double)NB)/log10((double)2.0)); NT=N*NB; /* Blocks of NBxNB will be considered. */ 3 51 /* Assigning memory. */ buffi=(float *)malloc(NT*sizeof(float)); buffo=(unsigned char *)malloc(NT*sizeof(char)); x=(float *)malloc(NB*sizeof(float)); L=(unsigned int *)malloc(NB*sizeof(int)); C=(float *)malloc((NB-1)*sizeof(float)); w=(float **)malloc(NB*sizeof(float *)); for(i=0;i<NB;i++) *(w+i)=(float *)malloc(NB*sizeof(float)); bit_reversal(L,m,NB); WTS(C,m,NB); NS=(N>>m); /* 2-D FCT using the row-column approach. */ for(i=0;i<NS;i++) { fread(buffi,NT,1,fptri); for(j=0;j<NS;j++) { for(k1=0;k1<NB;k1++) for(k2=0;k2<NB;k2++) w[k1][k2]=buffi[k1*N+k2+j*NB]; for(k1=0;k1<NB;k1++) { for(k2=0;k2<NB;k2++) x[k2]=w[k1][k2]; FCT(x,L,C,m,NB); for(k2=0;k2<NB;k2++) w[k1][k2]=x[k2]; } for(k2=0;k2<NB;k2++) { for(k1=0;k1<NB;k1++) x[k1]=w[k1][k2]; FCT(x,L,C,m,NB); for(k1=0;k1<NB;k1++) w[k1][k2]=x[k1]; } for(k1=0;k1<NB;k1++) 352 for(k2=0;k2<NB;k2++) buffo[k1*N+k2+j*NB]=w[k1][k2]; } fwrite(buffo,NT,sizeof(float),fptro); } fcloseall(); } H×nh 13.10 BiÓu ®å chuyÓn ®æi cosin nhanh. void FCT(float *x, unsigned int *L, float *C, int m, int N) { int NK1,NK2,i,j,k,kk,ip,incr,L1,k1,k2,iter; float T; /*Rearranging the order of the input sequence.*/ NK1=N>>1; T=x[2]; x[2]=x[1]; x[1]=T; k1=2; k2=4; for(i=1;i<(NK1-1);i++) 16 2C 2 1 2 1 2 1 - 1 -1 - 1 -1 -1 - 1 - 1 - 1 -1 - 1 - 1 -1 -1 - 1 - 1 - 1 - 1 C 4 C 4 C 4 C 4 DÞch chuyÓn bit. X(0) X(1) X(2) X(7) X(3) X(4) X(5) X(6) )0( ~ x )1( ~ x )2( ~ x )3( ~ x )4( ~ x )5( ~ x )6( ~ x )7( ~ x 8 2C 8 2C 5 8 2C 5 8 2C 5 16 2C 9 16 2C 13 16 2C 353 { T=x[k2]; for(j=0;j<=(k2-k1);j++) { x[k2-j]=x[k2-j-1]; } x[k1]=T; k1++; k2+=2; } NK2=N-1; for(i=0; i<(NK1>>1);i++) { T=x[NK2-i]; x[NK2-i]=x[NK1+i]; x[NK1+i]=T; } /*Forward operation. */ ip=NK1; kk=0; incr=N; for(iter=0;iter<m;iter++) { for(k=0;k<ip;k++) { for(j=k;j<N;j+=incr) { i=j+ip; T=x[j]; x[j]=T+x[i]; x[i]=T-x[i]; x[i]*=C[kk]; } kk++; } ip>>=1; incr>>=1; } /*Bit reversal. */ for(i=0; i<(N-1); i++) 354 { if(i<=L[i]) continue; else { T=x[i]; x[i]=x[L[i]]; x[L[i]]=T; } } /*Recursive subtraction. */ for(i=1;i<NK1;i++) x[i]*=0.5; NK1=(N>>2); NK2=(N>>1); kk=1; for(iter=1;iter<m;iter++) { kk<<=1; L1=kk-1; /*L1=2^iter-1*/ for(k=1;k<=L1;k++) for(i=0;i<NK1;i++) x[NK1+k*NK2+i]=x[NK1+k*NK2+i]-x[NK1+(k-1)*NK2+i]; NK1>>=1; NK2>>=1; } x[0]*=1.414/(float)N; for(i=1;i<N;i++) x[i]*=2.0/(float)N; } void bit_reversal(unsigned int *L, int m, int N) { unsigned int MASK,C,A,j,k,i; for(k=0;k<N;k++) { MASK=1; C=0; for(i=0,j=m-1;i<m;i++,j ) [...]... trị của khối ảnh gốc phải được cho trước bởi người dùng C A D C X -1 A=C+D 0.5 A B C B 1/2CX B=(C-D)CX D -1 C=0.5A+B/(2CX) D=0.5A-B/(2CX) Hình 13.11 Phép đổi ngược của một bướm 0 1 5 2C Dịch chuyển bit X(0 ) X(1 ) X(2 ) X(3 ) X (4 ) X(5 ) X(6 ) X(7 ) + + 0 1 5 2C 4 0 1 5 2C 4 0 1 5 + 2C + 4 + 0 5 0 -1 5 1 4C8 1 5 4C8 -1 0 5 0 1 -1 5 0 5 0 5 0 -1 5 0 1 -1 5 C16 1 5 C16 1 9 C16 4C8 1 -1 4C8 4 -1 1 13 C16... NK1,NK2,i,k,iter; NK1=N>>1; NK2=N=1; } for(i=0;i . )12()12()( 010012 kYkYkY (13. 34) 14/ 0 1010 ) 4 (2 ) 14( cos)()( N n N kn nxkY (13.35) 14/ 0 1111 ) 4 (2 ) 14( cos)()( N n N kn nxkY (13.36) 14/ 0 1212 ) 4 (2 ) 14( cos)()( N n N kn nxkY . các biểu thức dới đây: 2)-X(4k2)X(4k (k)Y 11 (13 .44 ) 1)-X(4k1)X(4k (k)Y 12 (13 .45 ) 3)-X(4k 1)-X(4k 1)X(4k 3)X(4k (k)Y 13 (13 .46 ) Vì vậy, tín hiệu ra từ các bớc cuối cùng của các thao. Y 12 (1) 1 C 4 - 1 x 14 (0) x 14 (1) Y 14 (0) Y 14 (1) 1 C 4 - 1 x 13 (0) x 13 (1) Y 13 ( 0) Y 13 (1) 1 C 4 - 1 x 10 (0) x 10 (1) Y 10 (0) Y 10 (1) 1 C 4 - 1