Nén Ảnh part 4

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

Thêm vào BST

Báo xấu

71
lượt xem 13
download

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

Tham khảo tài liệu 'nén ảnh part 4', công nghệ thông tin, đồ họa - thiết kế - flash 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: Nén Ảnh part 4

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 (13.31) Y10 (k )  Y00 (2k ) (13.32) Y11 ( k )  Y00 ( 2k  1)  Y00 ( 2k  1) V× vËy (13.33) Y12 (k )  Y01 (2k ) (13.34) Y12 ( k )  Y00 ( 2k  1)  Y01 ( 2k  1) N / 4 1  (4n  1)k  (13.35) Y10 (k )  x10 (n ) cos N n 0 2( ) 4 N / 4 1  (4n  1)k (13.36)  Y11 (k )  x11 (n ) cos N n 0 2( ) 4 N / 4 1  (4n  1)k (13.37)  Y12 (k )  x12 (n ) cos N n 0 2( ) 4 N / 4 1  (4n  1)k (13.38)  Y12 (k )  x12 (n ) cos N n 0 2( ) 4 NÕu N = 8, c¸c biÓu thøc trªn cã d¹ng: k  5k (13.39) Y10 ( k )  x10 (0) cos  x10 (1) cos 4 4 k  5k (13.40) Y11 ( k )  x11 ( 0) cos  x11 (1) cos 4 4 k  5k (13.41) Y12 (k )  x12 (0) cos  x12 (1) cos 4 4 k  5k (13.42) Y13 ( k )  x13 (0) cos  x13 (1) cos 4 4 ë ®©y k = 0,1. C¸c biÓu thøc cuèi cã thÓ biÓu diÔn thµnh Y10(0) = x10 (0) + x10(1) 345
Y10 = (x10(0) - x10(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: (13.43) Y10 (k)  X(4k) 1 x10(0) Y10(0) C4 x10(1) Y10(1) -1 1 x11(0) Y11(0) C4 x11(1) Y11(1) -1 1 x12(0) Y12(0) C4 x12(1) Y12(1) -1 1 x13(0) Y13(0) C4 x13(1) Y13(1) -1 1 x14(0) Y14(0) C4 x14(1) Y14(1) -1 H×nh 13.6 Bím cuèi cïng trong FCT. §Çu ra BitdÞch chuyÓn 000 0 X(0) 000 0 001 1 X(4) 100 4 cïng cña c¸c thao t¸c 010 2 2X(2) 010 2 346 Þch chuyÓn bit 011 3 X(6)+X(2) 110 6 bím. 100 4 2X(1) 001 1
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. X(0) 0 2X(1) 1 2X(2) 2 DÞch chuyÓn bit 2(X(3)+X(1)) 3 X(4) 4 X(5)+X(3) 5 X(6)+X(2) 6 X(7)+X(5)+X(3)+X(1) 7 H×nh 13.8 TÝn hiÖu ra sau dÞch chuyÓn bÝt. X(0) 1 2 X(1) 1 2 X(2) 1 DÞch chuyÓn bit -1 2 X(3) 347 X(4) -1 X(5)
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: Y11 (k)  X(4k  2)  X(4k - 2) (13.44) (13.45) Y12 (k)  X(4k  1)  X(4k - 1) (13.46) Y13 (k)  X(4k  3)  X(4k  1)  X(4k - 1)  X(4k - 3) 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. 348
2-D FCT cña mét d·y 2-D thùc ®îc cho bëi N1 1 N 2 1 4 k 1 k 2   (2n1  1)k1    (2n 2  1)k 2    x(n , n ) cos  cos  X (k 1 , k 2 )     1 2 2 2 N1 2N 2 N    n1  0 n2  0 (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 #include #include #include #include #include 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; 349
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
/* ------------------ 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>m); /* ------------------------------------ 2-D FCT using the row-column approach. ----------------------------------- */ for(i=0;i
for(k2=0;k2>1; T=x[2]; x[2]=x[1]; x[1]=T; k1=2; k2=4; for(i=1;i
{ T=x[k2]; for(j=0;j1);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>=1; } /*Bit reversal. */ for(i=0; i
{ if(i2); NK2=(N>>1); kk=1; for(iter=1;iter
{ A=(k&MASK)>>i; A
1 cho k = 0  k   2 1 cho k = 1,2, ..., N - 1  Thay v× lËp l¹i c¶ mét ch¬ng tr×nh ®Ó tÝnh biÕn ®æi ngîc FCT, chóng ta sÏ dïng lu ®å cña FCT tiÕn (forward). §Ó rót ra FCT ngîc, tÊt c¶ c¸c viÖc mµ chóng ta cÇn lµm lµ ®¶o ngîc biÓu ®å ë h×nh 13.10. H×nh 13.11 giíi thiÖu phÐp biÕn ®æi ngîc cña mét bím. KÕt qu¶ cña thuËt to¸n biÕn ®æi ngîc cña lu ®å FCT cho trong h×nh 13.12. Tõ lu ®å cña h×nh 13.11 biÕn ®æi ngîc cña FCT cã thÓ ph¸t triÓn b×nh thêng tõ FCT tiÕn. Ch¬ng tr×nh tÝnh 2-D FCT ngîc cho trong ch¬ng tr×nh 13.6. Gi¸ trÞ cña khèi ¶nh gèc ph¶i ®îc cho tríc bëi ngêi dïng. 0.5 C A C A C D B B D X -1 -1 A=C+D 1/2CX C=0.5A+B/(2CX) B=(C-D)CX D=0.5A-B/(2CX) H×nh 13.11 PhÐp ®æi ngîc cña mét bím. 0. 0. 0. ~(0) X(0 x 1 5 5 5 ) ~(1) 0. 0. 2C x 4 X(1 -1 5 5 1 DÞch chuyÓn bit. ) 0. 0. ~(2) 4C8 X(2 x -1 5 1 5 1 ) 0. 2C ~(3) 5 4C8 4 X(3 x + -1 -1 51 ) 0. 0. ~ C16 X(4 -1 x(4) 1 5 5 1 ) 0. 2C ~(5) 5 C16 4 X(5 x + -1 -1 51 1 ) 0. 9 ~(6) 4C8 C16 X(6 x + 1 -1 -1 5 1 1 ) 2C 13 ~(7) C16 4C8 4 X(7 x + + -1 -1 -1 ) H×nh 13.12 BiÓu ®å ®¶o ngîc gi¶i thuËt FCT. 356