Nén Ảnh part 3

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

Thêm vào BST

Báo xấu

69
lượt xem 14
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 3', 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 3

ind=1; while(ind) { ch=getc(fptr); for(k=0;kact_len){ind=0; break;} aux1=(ch&mask); ch
Nót gèc 1 0 Nót l¸ 1 0 0 0 1 0 2 1 4 3 1 0 0 C¸c nót gèc 1 5 6 8 7 H×nh 13.3 C©y nhÞ ph©n gi¶i m· Huffman h×nh 13.2. Bµi tËp 13.3 1. ¸p dông ch¬ng tr×nh 13.3 cho viÖc gi¶i m· ¶nh ®· m· ho¸ ë bµi tËp 13.2. 2. M· ho¸ Huffman cã thÓ ®¹t ®îc kÕt qu¶ h¬n nhê sö dông c©y nhÞ ph©n. C©y nhÞ ph©n trong h×nh 13.3 biÓu diÔn m· Huffman ë h×nh 13.2. a. ViÕt ch¬ng tr×nh C sö dông m· Huffman ®Æt trong phÇn header cña file ¶nh ®· m· ho¸ ®Ó t¹o mét c©y nhÞ ph©n. b. Më réng cho ch¬ng tr×nh gi¶i m· dïng c©y nhÞ ph©n. Ch¬ng tr×nh ph¶i ®¹t ®îc mét vµi yªu cÇu quan träng nhanh h¬n ph¬ng ph¸p ®· m« t¶ trong phÇn nµy. gi¶i thÝch t¹i sao. 13.3 M· chiÒu dµi thay ®æi M· chiÒu dµi thay ®æi (RLC) lµ mét ph¬ng ph¸p nÐn ¶nh dùa trªn sù c¾t bít c¸c d thõa kh«ng gian. Cho m· ho¸ chiÒu dµi thay ®æi mét chiÒu, mét m· chiÒu dµi thay ®æi ®îc ®Þnh nghÜa lµ mét sè c¸c phÇn tö ®iÓm ¶nh liªn tôc cã chung mét gi¸ trÞ. Mét ¶nh cã thÓ m· ho¸ dïng mét cÆp (m· chiÒu dµi thay ®æi, m· møc x¸m). Mét ch¬ng tr×nh nh vËy sÏ kh«ng thÓ lµm gi¶m kÝch thíc cña ¶nh nÕu ¶nh kh«ng chøa c¸c ®iÓm cã cïng c¸c gi¸ trÞ møc x¸m. §iÒu kiÖn nµy xuÊt hiÖn trong mét ¶nh nhiÒu chi tiÕt. Dï cã thÕ ®i ch¨ng n÷a th× ®Þnh nghÜa cña RLC cã thÓ lµ mét ph¬ng ph¸p tèt ®Ó m· ho¸ mµ cã thÓ kh¾c phôc c¸c vÊn ®Ò xuÊt hiÖn dùa theo c¸c ®iÒu kiÖn sau: 334
1. Mét m· chiÒu dµi thay ®æi ®îc x¸c ®Þnh b»ng ba bÝt cuèi cïng cã ý nghÜa cña nã ®îc x¸c lËp b»ng 1. Cßn 5 bÝt thÊp cña nã cung cÊp mét bé ®Õm tõ 1 ®Õn 31 cho byte ®i theo nã. 2. NÕu gi¸ trÞ mét ®iÓm cã m· chiÒu dµi thay ®æi b»ng kh«ng, th× nã ®îc m· ho¸ nh sau: a.NÕu 3 bit cuèi cña nã ®Òu x¸c lËp lªn 1, ch©öng h¹n,  224, th× nã ®îc m· ho¸ thµnh (11100000, gi¸ trÞ ®iÓm), cô thÓ, m· chiÒu dµi thay ®æi b»ng kh«ng theo sau b»ng gi¸ trÞ ®iÓm. b. Cho c¸c trêng hîp cßn l¹i, nã ®îc m· ho¸ nh gi¸ trÞ ®iÓm. C¸c bíc trªn gi¶ thiÕt r»ng trong mét ¶nh b×nh thêng, m· chiÒu dµi thay ®æi lín h¬n 31 Ýt xuÊt hiÖn, vµ c¸c ®iÓm cã gi¸ trÞ lín h¬n 224 còng Ýt xuÊt hiÖn. Ch¬ng tr×nh C sau sÏ thùc hiÖn c¸c bíc trªn. Ch¬ng tr×nh 13.4 "RLC.C". Ch¬ng tr×nh cho gi¶i thuËt RLC. /*Program 13.4 "RLC.C". Program for RLC.*/ /* Run length code. */ /* This program can be used for either coding images in RLC or decoding them. */ #include #include #include #include #define MASK 224 /* MASK=11100000 */ void main() { int buff[256],p; int N,i,k; FILE *fptr,*fptro; char file_name[14],ch; int NMASK=(~MASK); clrscr(); printf("This program can be used for both coding"); printf("\nand decoding images using 1-D RLC."); printf("\n\n Enter choice:"); printf("\n 1.Coding."); printf("\n 2.Decoding --- >" ); while(((ch=getch())!='1')&&(ch!='2')); 335
putch(ch); printf("\n\nEnter input file name-->"); scanf("%s",file_name); fptr=fopen(file_name,"rb"); if(fptr==NULL) { printf("\n file %s does not exist.\n"); exit(1); } switch(ch) { case '1': printf("Enter output file name-->"); scanf("%s",file_name); fptro=fopen(file_name,"wb"); /* Read first line.*/ N=0; while((buff[N]=getc(fptr))!=EOF) { N++; if(N==256) break; } while(N!=0) { i=0; while(i
} i++; while(p==buff[i]) { i++; k++; if((k==31)||(i==N)) break; } if(k==0) { if((p&MASK)==MASK) { k=MASK; putc(k,fptro); putc(p,fptro); } else putc(p,fptro); } else { k|=MASK; putc(k,fptro); putc(p,fptro); } } N=0; while((buff[N]=getc(fptr))!=EOF) { N++; if(N==256) break; } } fcloseall(); printf("\nDone coding"); break; case '2': /* Decoding procedure.*/ printf("\nEnter file name for storing decoded image-->"); scanf("%s",file_name); 337
fptro=fopen(file_name,"wb"); while(1) { k=getc(fptr); if(k==EOF) break; if((k&MASK)==MASK) { p=getc(fptr); if(p==EOF) { putc(k,fptro); break; } k=k&(NMASK); for(i=0;i
Cã thÓ chuyÓn m· 1-D RLC sang m· 2-D RLC b»ng c¸ch kiÓm tra c¸c dßng tríc, hoÆc kiÓm tra bèn híng kh¸c nhau (trªn, díi, tr¸i, ph¶i). C¸c 2-D RLC nµy cã thÓ nÐn ¶nh ë møc ®é cao h¬n. 13.4 M· chuyÓn ®æi Nh¾c l¹i lµ biÕn ®æi Fourier cho mét ¶nh th× cã phÇn lín c¸c gi¸ trÞ lín nhÊt n»m ë miÒn tÇn sè thÊp. MËt ®é c¸c gi¸ trÞ nµy gi¶m xuèng nhanh chãng khi tÇn sè t¨ng lªn. TÝnh chÊt nµy, tÝnh chÊt mµ chóng ta ¸p dông ®Ó läc ¶nh, còng ®îc ¸p dông trong khi nÐn ¶nh. Cã mét sè phÐp biÕn ®æi thuËn tiÖn h¬n phÐp biÕn ®æi Fourier. PhÐp biÕn ®æi tèi u nhÊt lµ phÐp biÕn ®æi ®îc ®Ò xuÊt bëi Karhunen-Loeve (KL). Tuy nhiªn, phÐp biÕn ®æi nµy tù nã kh«ng thÓ ®a ra c¸c bíc tÝnh to¸n nhanh hoÆc hiÖu qu¶ h¬n. Mét phÐp biÕn ®æi xem cã vÎ gièng nh biÕn ®æi KL nhng cã thÓ tÝnh to¸n nh biÕn ®æi Fourier rêi r¹c lµ phÐp biÕn ®æi cosin rêi r¹c. BiÕn ®æi cosin cã mét sù thay ®æi nhá tèi u ho¸ trong miÒn tËp trung n¨ng lîng so víi biÕn ®æi KL; nhng do u ®iÓm cña kü thuËt tÝnh to¸n nªn nã ®îc ¸p dông nh mét tiªu chuÈn trong kü thuËt nÐn ¶nh. PhÐp biÕn ®æi ®îc ¸p dông trªn toµn bé ¶nh nhng th«ng thêng ngêi ta hay ¸p dông trªn c¸c khèi nhá h¬n cã kÝch thíc 8  8 hoÆc 16  16. Lý do lµ: 1. BiÕn ®æi cña c¸c khèi nhá th× dÔ tÝnh h¬n lµ biÕn ®æi cho toµn bé ¶nh. 2. Quan hÖ gi÷a c¸c ®iÓm ¶nh Ýt thay ®æi gi÷a c¸c ®iÓm ¶nh gÇn nhau. Chóng t«i sÏ tr×nh bµy díi ®©y phÐp biÕn ®æi cosin vµ c¸c kü thuËt tÝnh to¸n hoµn thiÖn cña nã. Mét sè phÐp biÕn ®æi kh¸c nh Hadamard, Walsh, ..., kh«ng ®îc nghiªn cøu trong cuèn s¸ch nµy, bëi v× chóng kh«ng tèi u b»ng phÐp biÕn ®æi Fourier vµ chóng cã nhiÒu giíi h¹n trong lÜnh vùc nµy. 13.4.1 BiÕn ®æi cosin BiÕn ®æi mét chiÒu cosin rêi r¹c (DCT-Discrete Cosin Transform) cho bëi N 1 2 k   ( 2n  1)k  (13.4)  x(n) cos X (k )   N 2N   n 0 ë ®©y 1 k=0 víi k  2 339
=1 víi c¸c trêng hîp cßn l¹i. k = 0,1,2, ..., N. vµ Mét sè ph¬ng ph¸p biÕn ®æi nhanh cosin (FCT-Fast Cosine Transform) ®· ®îc ph¸t triÓn. Mét trong sè ®ã lµ biÕn ®æi cña Chan vµ Ho. ThuËt to¸n nµy t¬ng tù nh thuËt to¸n FFT, ngo¹i trõ mét sè biÕn ®æi ë ®Çu vµo d÷ liÖu. PhÐp biÕn ®æi nµy coi r»ng N lµ béi sè cña 2. D÷ liÖu ®Çu vµo x(n) ®îc s¾p xÕp l¹i theo thø tù: ~  x  x ( 2n)   n = 0,1,2,...,N/2 - 1 (13.5) ~ x( N  n  1)  x(2n  1)  Thay vµo biÓu thøc (13.4) chóng ta ®îc ( N / 2 1)  (4n  1) k ( N / 21)  (4n  3) k    x (2n  1) cos X (k)  x (2n) cos 2N 2N n 0 n 0 Sau khi nh©n ta ®îc: N 1  (4n  1)k X (k )   ~ (n) cos (13.6) x 2N n 0 Còng gièng nh ph¬ng ph¸p hÖ thËp ph©n trong miÒn tÇn sè cïng trong FFT, chóng ta còng chia X(k) thµnh c¸c gi¸ trÞ ch½n vµ lÎ theo c¸c bíc sau: C¸c môc chØ sè ch½n: N 1  (4n  1)2k X (2k )   ~ (n) cos x 2N n 0 cã thÓ biÓu diÔn thµnh: N 1  (4 n  1)k N X (2 k )   [ ~ (n )  ~ (n  )] cos (13.7) x x N 2 n 0 2  2 C¸c môc chØ sè lÎ: N 1  (4n  1)(2k  1) X (2 k  1)   ~ (n ) cos x 2N n 0 biÓu thøc nµy sau khi nh©n mét vµi phÐp nh©n, cã thÓ biÓu diÔn thµnh: ( N / 2 1) N    (4n  1) ~  ~   x (n)  x (n  2 ) cos 2 N (2k  1)  (13.8) X (2k  1)     n 0 340
Nhng cos[(2k + 1)] = 2coscos(2k) - cos[(2k - 1) ]. V× vËy,    (4n  1)  ( N / 2 1) N  2 ~(n)  ~ (n  ) cos   X (2k  1)  x x k N 2  2  n 02    2  ( N / 2 )1 N   (4n  1) ~  ~  (13.9)  x (n)  x (n  2 ) cos  2 N (2k  1) -    n 02 BiÓu thøc thø hai trong (13.9) lµ X(2k - 1). Bëi vËy, nªn (13.9) rót gän thµnh   ( N / 2 1)   (4n  1)   (4 n  1) N ~ {2  x (n )  ~ (n  ) cos  X (2 k  1)  x k } cos N 2N 2  2  n  02 2       (4n  1)  (2k  1)  X (2k  1)  cos (13.10) N 2   2  N x00 (n )  ~ (n)  ~ (n  ) §Æt x x 2 (13.11)   (4n  1)  N  x01   ~ (n)  ~ (n  ) 2 cos vµ (13.12) x x   2N  2  V× vËy: N / 2 1  (4n  1)  (13.13) X (2 k )  x 00 (n ) cos N n0 2( ) 2 Vµ N / 2 1  (4n  1)k  (13.14) X (2 k  1)  x01 (n) cos( )  X (2k  1) N n0 2( ) 2 BiÓu thøc (3.13) vµ (3.14) dÉn chóng ta ®Õn s¬ ®å h×nh 13.4 cho DCT 8 ®iÓm. Chó ý r»ng X(1) = X(-1). BiÓu thøc (13.11) vµ (13.12) lµ biÓu thøc cho c¸c phÐp to¸n bím: 341
§Æt Y00 (k )  X (2k ) (13.15) Y01 ( k )  X (2 k  1)  X (2 k  1) ~ (0) x(0) x ~ (1) x(2) x DCT ~ (2 ) x(4) x ~ (3) 4 ®iÓm. x(6) x 2C16 ~ (0) 2x(1) x -1 2C16 ~ (1) x(3)+x(1) x -1 2C 9 DCT ~ (2 ) x(5)+x(3) x 16 -1 ~ (3) 4 ®iÓm. x(7)+x(5) x -1 13 2C16 i C ij  cos j H×nh 13.4 Lu ®å cho biÓu thøc (13.13) vµ (13.14). N / 2 1  (4n  1)k  V× thÕ: Y00 (k )  x00 (n) cos N n 0 2  2 (13.16) N / 2 1  (4n  1)k  Y01 (k )  x01 (n) cos( ) N n 0 2( ) 2 (13.17) Chia Y00(k) vµ Y01(k) thµnh hai d·y chØ sè ch½n vµ lÎ nh trªn chóng ta ®îc:    N    (4n  1)     ( N / 4 ) 1     x00 (n)  x00 (n  ) cos  Y00 (2k )  (13.18) 4   2( N )    n 0    2     342
     (4 n  1)    ( N / 4 ) 1 N    x00 (n)  x00 (n  ) 2 cos  Y00 (2 k  1)   2( N )   4  n 0    2         ( 4n  1) k    Y00 ( 2k  1) s (13.19)  cos  2( N )    4        (4n  1)    ( N / 4 ) 1 N    x01 (n)  x01 (n  ) 2 cos  Y01 (2 k )  (13.20)  2( N )  4  n 0    2          (4n  1)    ( N / 4 ) 1 N  Y01 (2 k  1)    x01 (n )  x01 (n  ) 2 cos   2( N )  4 n 0     2     (13.21)     (4 n  1)k   cos   Y01 (2k  1)  2( N )    4   N §Æt (13.22) x10 ( n)  x00 ( n )  x00 ( n  ) 4 N ))C N4 n1) ( (13.23) x11 ( n)  ( x00 ( n)  x00 ( n  4 N (13.24) x12 (n )  x01 ( n)  x01 ( n  ) 4 N ))C N4 n 1) ( (13.25) x13 ( n)  ( x 01 ( n)  x01 ( n  4  i  C ij  cos  ë ®©y  j  (13.26) 343
X10(0 X00 (0 Y00 (0 ) X10(1 DCT ) ) X00 (1 Y00 (2 ) ) ) 2C8X11(0 X00 (2 2Y00(1) -1 2) 5 X ( C 8 11 ) DCT Y00 (3)+Y00(1 X00 (3 1) ) -1 ) X12(0 X01 (0 Y01 (0 ) X12(1 DCT ) ) X01 (1 Y01 (2 ) ) ) 2C8X13(0 X01 (2 2Y01(1) -1 ) 5 2C 8X13( DCT ) Y01 (3)+Y01(1 X01 (3 -1 1) ) ) H×nh 13.5 Bíc thø hai cña thuËt to¸n biÕn ®æi cosin. BiÓu thøc (13.22) ®Õn (13.25) biÓu diÔn cho to¸n tö bím. Thay c¸c biÓu thøc nµy vµo c¸c biÓu thøc tõ (13.18) ®Õn (13.21) chóng ta cã: N / 4 1  (4 n  1)k  (13.27) Y00 (2k )  x10 (n) cos N n 0 2  4 N / 41  (4n  1)k (13.28)  Y00 (2k  1)  Y00 (2k  1)  x11 (n ) cos N 2( ) n 0 4 N / 4 1  (4n  1)k  (13.29) Y01 (2 k )  x12 ( n) cos N n 0 2  4 N / 4 1  (4n  1)k (13.30)  Y01 (2 k  1)  Y01 (2k  1)  x13 (n) cos N n 0 2( ) 4 344