Nén dữ liệu ảnh và chuẩn JPEG

Chia sẻ: _ _ | Ngày: | Loại File: DOC | Số trang:39

Thêm vào BST

Báo xấu

797
lượt xem 193
download

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

Rõ ràng, việc truyền và lưu giữ các ảnh sẽ có nhiều vấn đề. Có rất nhiều ví dụ khác mà sẽ dễ dàng làm sáng tỏ vai trò của nén ảnh, và rất có nhiều nghiên cứu tập trung vào lĩnh vực này. Fax, một tài liệu đồ hoạ được truyền qua đường dây điện thoại, nén dữ liệu ảnh y học, truyền hình là một vài trong số nhiều ứng dụng tiềm tàng của nén ảnh. Sự phát triển của kỹ thuật vi điện tử và sự phát triển của rất nhiều ứng dụng thương mại dẫn dắt......

Chủ đề:

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

Lưu

Nội dung Text: Nén dữ liệu ảnh và chuẩn JPEG

Môc lôc: I. Tæng quan vÒ nÐn d÷ liÖu ¶nh vµ chuÈn JPEG: 1.1.Tæng quan vÒ nÐn d÷ liÖu ¶nh: 1.1.1. Sù cÇn thiÕt ph¶i nÐn d÷ liÖu ¶nh: 1.1.2. Mét sè kh¸i niÖm: 1.1.3. Ph©n lo¹i ph¬ng ph¸p nÐn ¶nh 1.1.3.1.NÐn kh«ng mÊt m¸t th«ng tin 1.1.3.2.NÐn ¶nh tÜnh dùa trªn phÐp biÕn ®æi ¶nh 1.2.KÜ thuËt nÐn ¶nh JPEG: 1.2.1.Kh«ng gian mµu: 1.2.2.ChuÈn JPEG 1.2.2.1. BiÕn ®æi Cosin rêi r¹c: 1.2.2.2.S¾p xÕp Zigzag: 1.2.2.3.Lîng tö ho¸. 1.2.2.4.M· ho¸ d÷ liÖu ¶nh. 1.2.3. CÊu tróc ¶nh JPEG: II.NÐn ¶nh theo chuÈn JPEG: 2.1. BiÕn ®æi Cosin rêi r¹c: 4.1. 4.2. 2.2. S¾p xÕp Zigzag: 5.2 2.3.Lîng tö ho¸ 6.1 6.1 2.4.M· ho¸ ¶nh 7.1 7.2 III.Phô lôc: 3.1.C¸c tµi liÖu tham kh¶o vµ ch¬ng tr×nh 3.2.C¸c thuËt ng÷. 1
I. Tæng quan vÒ nÐn d÷ liÖu ¶nh vµ chuÈn JPEG: 1.1.Tæng quan vÒ nÐn d÷ liÖu ¶nh: 1.1.1 Sù cÇn thiÕt ph¶i nÐn d÷ liÖu ¶nh: NÐn ¶nh lµ mét kü thuËt m· ho¸ hiÖu suÊt cao ¶nh sè nh»m lµm gi¶m sè bit cÇn cho biÓu diÔn ¶nh. Chøc n¨ng cña kü thuËt nµy lµ gi¶m ®é lín d÷ liÖu ph¶i lu tr÷ cïng víi thêi gian truyÒn trong khi vÉn gi÷ nguyªn chÊt lîng cña ¶nh. §Ó ®¸nh gi¸ sù cÇn thiÕt cña nÐn ¶nh, chóng ta xem xÐt vÒ yªu cÇu bé nhí vµ thêi gian truyÒn khi dïng mét modem 9600 baud (bit/s) cho c¸c ¶nh sau ®©y: ■ Mét ¶nh 512 × 512 ®iÓm, 8 bit cho mét ®iÓm, ¶nh møc x¸m yªu cÇu 2,097,152 bit cho lu gi÷ vµ mÊt 3.64 phót ®Ó truyÒn. ■ Mét ¶nh mµu RGB cã cïng c¸c bíc xö lý nh trêng hîp trªn yªu cÇu xÊp xØ 6 triÖu bÝt cho lu tr÷ vµ mÊt gÇn 11 phót ®Ó truyÒn. ■ Mét phim ©m b¶n cã kÝch thíc 24 × 36 mm (35 mm) chia b»ng c¸c kho¶ng c¸ch nhau 12 µm, vµo kho¶ng 3000 × 2000 ®iÓm, 8 bit cho mét ®iÓm, yªu cÇu 48 triÖu bit cho lu gi÷ ¶nh vµ 83 phót ®Ó truyÒn. Mét phim ©m b¶n mµu sÏ yªu cÇu mét sè lín gÊp ba lÇn cho lu gi÷ vµ truyÒn. Râ rµng, viÖc truyÒn vµ lu gi÷ c¸c ¶nh sÏ cã nhiÒu vÊn ®Ò. Cã rÊt nhiÒu vÝ dô kh¸c mµ sÏ dÔ dµng lµm s¸ng tá vai trß cña nÐn ¶nh, vµ rÊt cã nhiÒu nghiªn cøu tËp trung vµo lÜnh vùc nµy. Fax, mét tµi liÖu ®å ho¹ ®îc truyÒn qua ®êng d©y ®iÖn tho¹i, nÐn d÷ liÖu ¶nh y häc, truyÒn h×nh lµ mét vµi trong sè nhiÒu øng dông tiÒm tµng cña nÐn ¶nh. Sù ph¸t triÓn cña kü thuËt vi ®iÖn tö vµ sù ph¸t triÓn cña rÊt nhiÒu øng dông th¬ng m¹i dÉn d¾t sù ph¸t triÓn cho c¸c tiªu chuÈn vµ phÇn cøng cña bé nÐn ¶nh theo thêi gian thùc. 1.1.2.Mét sè kh¸i niÖm: *NÐn d÷ liÖu ¶nh: 2
-BiÕn ®æi dßng th«ng tin ¶nh thµnh tõ m· nh»m gi¶m ®é d thõa th«ng tin. *C¸c ®é d thõa th«ng tin: -D thõa th«ng tin vÒ kh«ng gian, vÒ thêi gian, ®« d thõa phæ vµ d thõa do ®é c¶m thô. *¶nh tÜnh : *¶nh ®éng: C¸c tham sè chÊt lîng nÐn ¶nh *Tû sè nÐn : -Tû sè: CR= -Tû sè bÝt: -Tèc ®é dßng bÝt(®èi víi ¶nh ®éng):bit/s *ChÊt lîng nÐn: -NÐn cã mÊt m¸t th«ng tin(lossless). -NÐn kh«ng mÊt m¸t th«ng tin(lossy). *§é phøc t¹p: -VÒ thêi giannÐn: NÐn thêi gian thùc/ kh«ng thêi gian thùc. -VÒ kh«ng gian bé nhí. 1.1.3. Ph©n lo¹i ph¬ng ph¸p nÐn ¶nh: 1.1.3.1.NÐn kh«ng mÊt m¸t th«ng tin: -M· lo¹t dµi (RLE):Dïng sè ®Õm ®Ó thay thÕ c¸c ®iÓm gièng nhau lÆp l¹i. -M· Shannon-Fano:Dïng côm bÝt cã ®é dµi thay ®æi ®Ó m· ho¸ . -M· Hufman:Sö dông ®Æc ®iÓm m· ho¸ cña Shannon-Fano víi ý t- ëng:kÝ hiÖu cã x¸c su©t xuÊt hiÖn nhiÒu th× ®îc m· ho¸ víi tõ m· ng¾n. -M· Lemple-Ziv:Dùa trªn viÖc x©y dùng vµ tra tõ ®iÓn. -M· dù ®o¸n (prediction): Dùa trªn qu¸ tr×nh t¹o ®iÓm tuÇn tù vµ luËt dù ®o¸n. 1.3.2.NÐn ¶nh tÜnh dùa trªn phÐp biÕn ®æi ¶nh -PhÐp biÕn ®æi Cosin rêi r¹c (DCT):biÓu diÔn c¸c gi¸ trÞ ®iÓm ¶nh trªn miÒn tÇn sè, tËp trung n¨ng lîng vµo mét sè hÖ sè, DCT cho phÐp ¸p dông trong c¸c chuÈn JPEG va MPEG. -PhÐp biÕn ®æi Wavelet rêi r¹c (DWT):Sö dông c¸c bé läc th«ng gi¶i xö lý ®a ph©n gi¶i trong phÐp DWt. - PhÐp biÕn ®æi dùa trªn h×nh häc Fractal (PhÐp biÕn ®æi Fractal): Sö dông c¸c phÐp biÕn ®æi h×nh häc. 3
1.3.KÜ thuËt nÐn ¶nh JPEG: 1.3.1.ChuÈn JPEG: Trong chuÈn JPEG ¶nh ®îc nÐn nh sau: 1. Khèi ®iÓm kÝch thíc 8 × 8 cña DCT trªn ¶nh nguyªn gèc ®îc tÝnh. 2. HÖ sè chuyÓn ®æi ®îc tiªu chuÈn ho¸ b»ng c¸ch ¸p dông mét m¶ng do ngêi sö dông ®Þnh nghÜa nã ®îc ®Þnh tríc cho tÊt c¶ c¸c khèi. 3. HÖ sè DC ®îc m· hãa víi lîc ®å DPCM. 4. Mçi khèi ®îc s¾p xÕp l¹i sö dông m· zigzag (xem h×nh 13.21). §iÒu nµy lµ theo RLC vµ lîc ®å m· Huffman. §Ó nÐn mét ¶nh mµu, JPEG ®Ò xuÊt r»ng mçi thµnh phÇn ®îc m· ho¸ mét c¸ch ®éc lËp víi nhau. 1.2.1.1. BiÕn ®æi Cosin rêi r¹c: 1.2.1.2.S¾p xÕp Zigzag: 1.2.1.3.Lîng tö ho¸. 1.2.1.4.M· ho¸ d÷ liÖu ¶nh. 1.3.2.CÊu tróc ¶nh JPEG: C¸c byte ®¸nh dÊu Gi¶I thÝch FF D8 B¾t ®Çu File FF FE Chó gi¶I-cã thÓ kh«ng cã FF E0 Byte ®¸nh dÊu d÷ liÖu øng dông ( th«ng thêng kh«ng dïng) FF DB §Þnh nghÜa b¶ng lîng tö FF C0 B¾t ®Çu cña Baseline DCT FF C4 §Þnh nghÜa b¶ng Huffman FF DA B¾t ®Çu d÷ liÖu ¶nh XX XX KÕt thóc d÷ liÖu ¶nh FF D9 KÕt thóc File ¶nh VÝ dô: ff d8 ff e0 00 10 4a 46 49 46 00 01 01 00 00 01 00 01 00 00 ff fe 00 46 76 77 78 79 7a 83 84 85 86 b5 b6 b7 b8 b9 ba c2 03 00 04 ff db 00 43 00 08 06 06 07 06 05 08 07 07 07 09 09 08 0a 0c 14 0d 0c 0b 0b 0c 19 12 13 0f 14 1d 1a 1f 1e 1d 1a 1c 1c 20 24 2e 27 20 22 2c 23 1c 1c 28 37 29 2c 30 31 34 34 34 1f 27 39 3d 38 32 3c 2e 33 34 32 ff c0 00 0b 08 01 00 4
01 00 01 01 11 00 ff c4 00 1f 00 00 01 05 01 01 01 01 01 01 00 00 00 00 00 00 00 00 01 02 03 04 05 06 07 08 09 0a 0b ff c4 00 b5 10 00 02 01 03 03 02 04 03 05 05 04 04 00 00 01 7d 01 02 03 00 04 11 05 12 21 31 41 06 13 51 61 07 22 71 14 32 81 91 a1 08 23 42 b1 c1 15 52 d1 f0 24 33 62 72 82 09 0a 16 17 18 19 1a 25 26 27 28 29 2a 34 35 36 37 38 39 3a 43 44 45 46 47 48 49 4a 53 54 55 56 57 58 59 5a 63 64 65 66 67 68 69 6a 73 74 75 76 77 78 79 7a 83 84 85 86 87 88 89 8a 92 93 94 95 96 97 98 99 9a a2 a3 a4 a5 a6 a7 a8 a9 aa b2 b3 b4 b5 b6 b7 b8 b9 ba c2 c3 c4 c5 c6 c7 c8 c9 ca d2 d3 d4 d5 d6 d7 d8 d9 da e1 e2 e3 e4 e5 e6 e7 e8 e9 ea f1 f2 f3 f4 f5 f6 f7 f8 f9 fa ff da 00 08 01 01 00 00 3f 00 xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx ff d9 II.NÐn ¶nh theo chuÈn JPEG: 2.1. BiÕn ®æi Cosin rêi r¹c: 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  X (k ) = N ∑ x(n) cos  2N   (13.4) n =0 ë ®©y (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. 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 5
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. DÞch chuyÓn bit. H×nh 13.10 BiÓu ®å chuyÓn ®æi cosin nhanh. BiÕn ®æi ngîc DCT ®îc cho bái X(0) N −1 1  πk (2n + 1) C4 x(n) = ∑ X (k )ε k cos  2 (13.48) X(1) k =0  2 N-1  1 2 ë ®©y X(2) -1 5 2C8 C4 1 -1 2  1 X(3)  cho k = 0 -1 -1 εk =  2 2C16 X(4) -1 15 cho k = 1,2, ..., N - 1  2C16 C4 -1 X(5) Thay v× lËp l¹i-12C16 -1 c¶ 9mét ch¬ng tr×nh ®Ó tÝnh biÕn-1 2C8 ®æi ngîc FCT, chóng ta sÏ dïng lu ®å cña-1 X(6) FCT tiÕn (forward). §Ó rót ra FCT ngîc, tÊt c¶ c¸c viÖc mµ 13 2C16 -1 5 2C8 C4 -1 -1 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 X(7) -1 -1 -1 cña thuËt to¸n biÕn ®æi ngîc cña phÐp biÕn ®æi ngîc cña mét bím. KÕt qu¶ 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 A C C D X B B D -1 -1 A=C+D C=0.5A+B/(2CX) B=(C-D)CX 6 D=0.5A-B/(2CX)
1/2CX H×nh 13.11 PhÐp ®æi ngîc cña mét bím. DÞch chuyÓn bit. X(0 0. 0. 0. ~(0) x 1 5 5 5 ) X(1 2C 4 0. 0. ~(1) x -1 51 5 ) 0. 4C 0. ~(2) X(2 1 1 8 x 5 -1 5 ) 2C 4 4C 5 0. ~(3) X(3 + 8 1 x -1 -1 5 ) 0. 0. C ~(4) X(4 1 16 x 5 5 1 -1 ) 2C 0. 5 ~(5) X(5 H×nh 13.12 BiÓu ®å ®¶o ngîc C thuËt FCT. 4 1 gi¶i 16 x + -1 5 1 -1 ) 0. 4C 9 C ~(6) x 8 X(6 1 16 + 5 1 -1 1 -1 ) theo t«i sÏ giíi 2C4 TiÕp thiÖu mét ch¬ng tr×nh mµ sÏ hiÓn thÞ c¸c khèi 8 × 8 4C 13 C ~(7) X(7 8 16 x + + -1 -1 -1 ) cña kÕt qu¶ ®· chuyÓn ®æi trªn mµn h×nh v¨n b¶n. Chó ý r»ng gi¸ trÞ sÏ gi¶m xuèng mét c¸ch nhanh chãng kÓ tõ gãc tr¸i cña mµn h×nh, hay lµ ®iÓm tÇn sè (0,0). §Ó tho¸t khái ch¬ng tr×nh nµy, bÊm ESC. Ch¬ng tr×nh 13.7 "DISPFCT.C". Ch¬ng tr×nh hiÓn thÞ khèi 2-D FCT. Mét mÉu cña 2-D FCT tõ mét khèi rót ra tõ ¶nh IKRAM.IMG giíi thiÖu trong h×nh 13.13. C¸c thµnh phÇn mét chiÒu (c¸c khèi cã tÇn sè 0,0) cã gi¸ trÞ lín nhÊt. Thµnh phÇn nµy biÓu diÔn gi¸ trÞ trung b×nh cña khèi. C¸c thµnh phÇn kh¸c (®îc hiÓu lµ c¸c thµnh phÇn xoay chiÒu) ph¶i cã c¸c gi¸ trÞ nhá h¬n. 7
2.2. S¾p xÕp Zigzag: 5.2 2.3.Lîng tö ho¸ 6.1 6.1 Lîng tö ho¸ Trong toµn bé cuèn s¸ch nµy chóng ta lµm viÖc víi c¸c ¶nh ®· lîng tö ho¸. Chóng ta coi r»ng c¸c ¶nh ®îc chia lµm c¸c møc x¸m dïng 8 bit víi c¸c gi¸ trÞ tõ 0 ®Õn 255. Tuy vËy, chóng ta kh«ng bao giê ®Ó ý ®Õn c¸c gi¸ trÞ nµy. Lý do lµ c¸c gi¸ trÞ nµy b¶n th©n nã kh«ng cã ý nghÜa g× c¶. C¸i mµ chóng ta thËt sù quan t©m lµ biÓu diÔn díi d¹ng nhÞ ph©n cña gi¸ trÞ cêng ®é s¸ng tÝn hiÖu lÊy mÉu. TÊt c¶ c¸c bÝt biÓu diÔn kho¶ng cña tÝn hiÖu chãi. NÕu tÝn hiÖu chãi cã gi¸ trÞ trong kho¶ng tõ gi¸ trÞ nhá nhÊt yL cho ®Õn gi¸ trÞ lín nhÊt yu, th× hµm lîng tö ho¸ sÏ chia tÝn hiÖu ra thµnh N miÒn vµ g¸n cho mçi miÒn mét gi¸ trÞ nhÞ ph©n nh trong h×nh 13.14. Sù biÓu diÔn nµy kh«ng cã ý nghÜa g× vÒ mÆt vËt lý, vµ chøc n¨ng cña sù biÓu diÔn nµy, nh chóng ta muèn, chØ dïng trong lÜnh vùc xö lý tÝn hiÖu sè. TÊt c¶ c¸c tÝn hiÖu sè nµy gäi lµ ®iÒu m· xung (Pulse Code Modulated - PCM). §Ó cã thÓ thùc sù thÊy gi¸ trÞ c¸c møc x¸m chóng ta cÇn lîng tö ho¸ ngîc. Trong bíc nµy, c¸c gi¸ trÞ nhÞ ph©n biÓu diÔn mét ®é chãi cô thÓ. C¸c bíc thùc sù cña qu¸ tr×nh nµy biÓu diÔn trong h×nh 13.15. Trong lÜnh vùc t¬ng tù vµ lÜnh vùc sè qu¸ tr×nh nµy gäi lµ chuyÓn ®æi tõ t¬ng tù sang sè (A/D) vµ chuyÓn ®æi D¹ng nhÞ tõ sè sang t¬ng tù (D/A). D¹ng thËp ph©n. Trong c¸c YU dông nh trêngph©n. øng hîp N-1 ®æi cosin 2-D th× cã mét chót kh¸c biÕn Kho¶ng tÝn hiÖu. dN 11111111 N-2 hîp nµy lµ biÕn ®æi tõ mét tËp hîp biÖt. C¸i mµ chóng ta cÇn lµm trong trêng dN-1 . 11111110 c¸c dÊu phÈy ®éng sang mét tËp hîp c¸c bÝt nhÞ ph©n vµ ngîc l¹i. BiÓu v× . . . biÕn ®æi ngîc cña lîng tö ho¸ lµ biÕn ®æi tõ nhiÒu vµo mét, nªn qu¸ tr×nh . . . nµy kh«ng thÓ tiÕn hµnh mét c¸ch th«ng thêng ®îc. May m¾n thay, cã mét . . sè ph¬ng ph¸p ®Ó lîng tö ho¸ vµ lîng. tö ho¸ ngîc. Chóng ta sÏ nghiªn cøu c¸c . ph¬ng ph¸p nµy ë phÇn díi ®©y. . . . . . . . . . . . . . . . . 4 . d5 00000100 8 d4 3 00000011 2 00000010 YL d3 1 00000001 d2 00000000 0 di { i= 0,...,1} lµ c¸c møc chia.
H×nh 13.14 Lîng tö ho¸. Lîng tö ho¸ ®ång ®Òu §©y lµ d¹ng ®¬n gi¶n nhÊt cña lîng tö ho¸. Trong d¹ng lîng tö ho¸ nµy, kho¶ng (yu - yL) ®îc chia thµnh N kho¶ng c¸ch ®Òu nhau (xem trong h×nh 13.14). C¸c gi¸ trÞ tõ d0 ®Õn dN ®îc gäi lµ c¸c møc chia. C¸c møc lîng tö biÓu diÔn gi¸ trÞ thùc cña c¸c møc chia trong kho¶ng tõ di ®Õn di+1 díi d¹ng sè nhÞ ph©n b»ng i. V× vËy, nÕu nh di+1 < y ≤ di th× gi¸ trÞ cña lîng tö ®Çu ra = i. Møc lîng tö ®Çu ra cã thÓ biÓu diÔn theo c«ng thøc:  y − yL  i= (N − 1)  yv − y L  ë ®©y dÊu   cã nghÜa lµ lµm trßn thµnh sè nguyªn gÇn nhÊt. Lîng tö ho¸ ngîc dïng mét b¶ng biÕn ®æi ngîc gi÷a gi¸ trÞ lîng tö i vµ biÕn ®æi ngîc cña nã ri d i + d i +1 ri = 2 9
Tuy nhiªn lîng tö ho¸ ®ång ®Òu kh«ng quan t©m ®Õn kh¶ n¨ng x¶y ra cña sù kiÖn víi c¸c gi¸ trÞ ®îc ®a ra. Tæng qu¸t, qu¸ tr×nh lîng tö ho¸ nµy ¸p dông cho trêng hîp tÊt c¶ c¸c møc cã kh¶ n¨ng xuÊt hiÖn b»ng nhau. §iÒu nµy, trong hÇu hÕt c¸c trêng hîp lµ kh«ng ®óng. DÔ nhËn thÊy lµ c¸c møc lîng tö ho¸ tËp trung nhiÒu nhÊt vµo miÒn mµ kh¶ n¨ng xuÊt hiÖn cña c¸c møc x¸m nhiÒu nhÊt. §iÒu nµy dÉn chóng ta ®Õn ph¬ng ph¸p thiÕt kÕ lîng tö ho¸ díi ®©y. L-îng TÝn hiÖu Møc ®- d¹ng nhÞ tö ho¸ TÝn îc t¸i TÝn ph©n. ng-îc hiÖu t- thiÕt. hiÖu ¸nh hay Bé läc ¬ng tù. biÕn s¸ng. th«ng ®æi sè thÊp. sang t- t t H×nh 13.15 Lîng tö ho¸ ngîc. Lîng tö ho¸ kh«ng ®ång ®Òu Trong phÇn nµy chóng ta sÏ xem xÐt ph¬ng ph¸p lîng tö ho¸ kh«ng ®ång ®Òu tèi u nhÊt trong hÖ thèng PCM. C¸c nghiªn cøu cho ph¬ng ph¸p nµy ®· ®îc Panter vµ Dite ®a ra trong mét cuèn s¸ch xuÊt b¶n vµo n¨m 1949. Trong cuèn s¸ch nµy hä ®· ®a gi¶i thuËt cho lîng tö ho¸ kh«ng ®ång ®Òu. Hä ®a ra mét ph¬ng ph¸p xÊp xØ tèi u cho lîng tö ho¸ kh«ng ®ång ®Òu. Gi¶i thuËt nµy sÏ kh«ng ®óng cho c¸c trêng hîp qu¸ tr×nh lîng tö ho¸ cã qu¸ Ýt møc chia. Tuy nhiªn c¸c gi¶i thuËt nµy ®îc ph¸t triÓn mét c¸c trän vÑn trong mét b¸o c¸o cha ®îc xuÊt b¶n cña Lloyd vµo n¨m 1957 vµ ®îc Max kiÓm nghiÖm vµo n¨m 1960. Mét ph¬ng ph¸p lîng tö ho¸ kÕt hîp c¶ hai ph¬ng ph¸p cña Lloyd vµ Max thêng ®îc gäi lµ ph¬ng ph¸p lîng tö ho¸ Lloyd-Max. Trong phÇn b¸o c¸o xuÊt b¶n sau ®ã cña Lloyd xuÊt b¶n vµo n¨m 1982 ®· cho thÊy cã rÊt nhiÒu øng dông rÊt thó vÞ cña ph¬ng ph¸p nµy. B¶n b¸o c¸o nµy cã hai ph¬ng ph¸p thiÕt kÕ, mét ph¬ng ph¸p trong ®ã gièng ph¬ng ph¸p cña Max. Ph¬ng ph¸p nµy gäi lµ ph¬ng ph¸p II. Ph¬ng ph¸p I tá ra cã nhiÒu øng dông vµ dÔ tÝnh to¸n h¬n ph¬ng ph¸p II. C¶ hai ph¬ng ph¸p thiÕt kÕ nµy ®Òu ®îc tr×nh bµy ë phÇn díi ®©y. 10
NÕu chóng ta coi r»ng c¸c møc lîng tö ho¸ ®îc cho bëi di , i = 0 ... N (xem h×nh 13.16) vµ c¸c møc kh«i phôc cho bëi ri , i = 0 ... N vµ gi¸ trÞ ®o cña tÊt c¶ c¸c møc nµy cho bëi: N d k +1 E= ∑ ∫ ( y − rk ) 2 p( y)dy (13.49) k =0 d k ë ®©y y lµ tÝn hiÖu ®Çu vµo cßn p(y) lµ kh¶ n¨ng xuÊt hiÖn cña y. H×nh 13.16 C¸c møc lÊy mÉu vµ kh«i phôc. y(t) ri C¸c møc chia. mÉu i L-îng tö ho¸ L-îng tö ho¸. ng-îc. MÉu y yu dN N-1 i ri dN-1 r0 d5 3 . . d4 2 d3 . . 1 yL d2 0 . . d1 LUT cho l-îng tö ho¸ ng-îc. 11
H×nh 13.17 C¸c xö lý lÊy mÉu vµ kh«i phôc. H×nh 13.17 cung cÊp s¬ ®å khèi cña qu¸ tr×nh lîng tö ho¸ vµ lîng tö ho¸ ngîc. TÝn hiÖu vµo y(t) ph¶i ®îc coi lµ ®· biÕt kh¶ n¨ng xuÊt hiÖn. VÊn ®Ò ®Æt ra lµ ph¶i x¸c ®Þnh c¸c møc lÊy mÉu vµ c¸c møc kh«i phôc sao cho mÐo tÝn hiÖu lµ nhá nhÊt. ViÕt l¹i biÓu thøc (13.49 ): d1 di E = ∫ ( y − r0 ) p ( y )dy + ... + 2 ∫ ( y − ri−1 ) 2 p ( y )dy + d0 di −1 d i +1 d n +1 ∫(y − r ) p ( y )dy + ... + ∫(y − r 2 i N ) 2 p( y )dy (13.50) di dN Vi ph©n (13.50) theo dI vµ cho biÓu thøc nµy b»ng kh«ng chóng ta ®îc ri + ri −1 di = (13.51) 2 i = 1,2,3, ... ,N LÊy vi ph©n (13.50) theo ri chóng ta ®îc. d ∂E i +1 = −2 ∫ ( y − ri ) p ( y )dy ∂ri d i d i +1 di ∫ yp( y)dy ri = d i +1 (13.52) ∫ p( y)dy di i = 0, 1, ... , N - 1. 12
H×nh 13.18 Ph¬ng ph¸p Newton-Raphson cho tÝnh c¸c biÓu thøc trong ngoÆc. BiÓu thøc (13.50) vµ biÓu thøc (13.51) ®a ra ph¬ng ph¸p x¸c ®Þnh c¸c møc lÊy mÉu vµ c¸c møc kh«i phôc dïng cho c¶ ph¬ng ph¸p cña Lloyd-Max hoÆc lµ ph¬ng ph¸p Lloyd. Ph¬ng ph¸p Lloyd-Max Lloyd vµ Max ®· ph¸t triÓn ®éc lËp thuËt to¸n ®Ó gi¶i quyÕt biÓu thøc (13.50) vµ (13.51). C¸c chi tiÕt cña thuËt to¸n nµy vÉn cha ®îc cung cÊp. Trong phÇn nµy t«i sÏ cung cÊp cho b¹n mét thuËt to¸n dùa trªn thuËt to¸n Lloyd-Max nhng cã c¸c chi tiÕt cô thÓ h¬n. T«i còng sÏ cung cÊp cho b¹n phÇn mÒm thiÕt kÕ N møc lÊy mÉu vµ kh«i phôc. ThuËt to¸n nµy gåm c¸c bíc sau: 1. Chän mét gi¸ trÞ cho r0. d0 vµ dN ®îc coi lµ ®· biÕt. 2. Cho i = 1,2,...,N - 1. a. TÝnh di tõ di ∫ yp( y)dy di −1i ri −1 = di ∫ p( y)dy d i −1 b. TÝnh ri tõ ri = 2d i − ri −1 3. TÝnh 13
dN ∫ yp( y)dy d N −1 r/ = dN ∫ p( y)dy d N −1 4. NÕu rN-1 ≠ r/, thay ®æi l¹i r0 vµ lÆp l¹i c¸c bíc tõ bíc 2 cho ®Õn bíc 4. B©y giê t«i sÏ cung cÊp cho b¹n c¸c chi tiÕt cÇn thiÕt ®Ó t¹o ra thuËt to¸n trªn. Chi tiÕt cho viÖc tÝnh di trong bíc 2a cña thuËt to¸n Lloyd-Max. di cã thÓ tÝnh theo hµm sau ®©y: di ∫ yp( y)dy d i −1 f (d i ) = ri −1 − di (13.53) ∫ p( y)dy di −1 Cã thÓ rót ra biÓu thøc gèc theo c«ng thøc lÆp Newton-Raphon ®îc cho bëi: f (d il ) d il +1 = d il − (13.54) f / (d il ) ë ®©y l lµ sè lÇn lÆp vµ f/(di) lµ ®¹o hµm cña f(di) theo di cho theo c«ng thøc:  di   ∫ yp( y )dy  / p (d i )  di −1  f (d i ) = − d d i − d  (13.50) i  i  ∫ p( y )dy  ∫ p ( y )dy  di −1   d i −1   d0i lµ gi¸ trÞ ban ®Çu. PhÐp lÆp diÔn ra cho ®Õn khi f (di ) < ε Gi¸ trÞ ban ®Çu cho d1 lµ d0 + ∆, cho d2 lµ d1 + ∆, ..., ë ®©y ∆ lµ mét gi¸ trÞ nhá. Gi¸ trÞ gèc cña f(di) cã thÓ tÝnh theo dïng ph¬ng ph¸p nöa lÆp (bisection). ¦u ®iÓm cña ph¬ng ph¸p Newton-Raphson lµ kh¶ n¨ng héi tô nhanh. Nhîc ®iÓm lµ ®¹o hµm cña mét hµm thêng cã gi¸ trÞ rÊt nhá vµ dÔ dÉn ®Õn gi¸ trÞ zero g©y nªn sù kh«ng æn ®Þnh cña c¸c sè. 14
C¸c chi tiÕt cho viÖc thay ®æi r0. Gi¸ trÞ r0 cã thÓ thay ®æi l¹i nÕu chóng ta nhËn thÊy r»ng gi¸ trÞ gèc cña hµm: g (r0 ) = rN −1 − r / (13.56) Gi¸ trÞ gèc nµy cã thÓ rót ra dïng c¸c gi¶ thiÕt cña Newton-Raphson theo: l +1 g ( r0l ) r0 =r − / l 0 l (13.57) g (r0 ) §¹o hµm cña g(r0) cã thÓ rÊt khã kh¨n cho viÖc ph©n tÝch. Trong trêng hîp nµy cÇn cã mét c«ng cô tÝnh to¸n kh¸c. Chóng ta cã thÓ thay thÕ ®¹o hµm b»ng mét gi¸ trÞ h»ng sè cã cïng dÊu nh biÓu thøc trong dÊu ngoÆc (xem h×nh 13.8). Trong trêng hîp nµy th× tÝch ph©n l©u héi tô h¬n. TiÕp theo lµ mét ch¬ng tr×nh cho tÝnh c¸c møc lîng tö ho¸ theo ph¬ng ph¸p Lloyd-Max. TÝch ph©n ®îc ®a ra dïng ph¬ng ph¸p tÝch ph©n Romberg bëi v× nã chÝnh x¸c h¬n ph¬ng ph¸p tÝch ph©n Simpson. Ch¬ng tr×nh cho phÐp b¹n thiÕt kÕ lîng tö ho¸ ®ång ®Òu, Gauss hoÆc lµ Laplace. 1 2 / 2σ 2 ) Gauss p( y) = e −( y 2πσ 2 α −α y Laplace p( y ) = e 2 2 α= σ 1 | y |
®ång ®Òu thêng cho kÕt qu¶ tÝnh to¸n rÊt tèt. Cßn cho ph©n bè Laplace, khi dïng t¨ng gi¸ trÞ cña biÓu thøc trong ngoÆc sÏ kh«ng gÆp mét khã kh¨n nµo viÖc t¹o m· 6 bit. Ch¬ng tr×nh 13.9 “MAXQ1.C” Ch¬ng tr×nh cho tÝnh c¸c møc lîng tö Lloyd-Max. Ph¬ng ph¸p Lloyd Lloyd còng ®a ra mét ph¬ng ph¸p thø hai cho phÐp x¸c ®Þnh c¸c møc lîng tö mµ «ng gäi lµ ph¬ng ph¸p Lloyd I. Ph¬ng ph¸p nµy cã nhiÒu u ®iÓm h¬n ph¬ng ph¸p II (gi¶i thuËt Lloyd-Max), v× nã dÔ dµng cho tÝnh to¸n vµ c¸c vector lîng tö ho¸ cã thÓ më réng. Chó ý lµ vÊn ®Ò mµ chóng ta quan t©m ë ®©y lµ kho¶ng c¸ch lîng tö ho¸, lîng tö ho¸ cña hµm mét biÕn ®· biÕt ®îc ph©n t¸n. Vector lîng tö ho¸ lµ mét vector cña nhiÒu biÕn mµ víi c¸c biÕn nµy ta ®· biÕt ®îc ph©n t¸n. ThuËt to¸n Lloyd theo c¸c bíc sau: 1. Rót ra íc lîng cho ph¹m vi cña c¸c biÕn di {i = 0, 1, 2, ..., N} (Mét íc lîng cã thÓ rót ra b»ng c¸ch dïng c¸c gi¸ trÞ tõ lîng tö ho¸ ®ång ®Òu hoÆc tõ c¸c møc lîng tö tríc mµ ta cÇn mét kÕt qu¶ tèt h¬n). 2. §Æt mét biÕn D1= 0. D1 dïng ®Ó lu l¹i t×nh tr¹ng kh«ng chÝnh x¸c lóc tr- íc. 3. TÝnh d i +1 ri = ∫ di yp( y )dy d i +1 ∫ di p ( y )dy i = 0, 1, ..., N - 1. 4. TÝnh ri + ri −1 di = 2 i = 0, 1, ..., N - 1 5. TÝnh t×nh tr¹ng kh«ng chÝnh x¸c N −1d k +1 D2 = ∑ ∫ ( y − rk ) 2 p( y)dy k =0 d k 16
Cã thÓ dÔ dµng më réng biÓu thøc tr¹ng th¸i kh«ng chÝnh x¸c theo N −1 ∑ ∫d p ( y )dy  d k +1 d k +1 d k +1 D= y 2 p ( y ) − 2rk ∫ yp( y )dy + rk2 ∫ (13.58)   k dk dk   k =0 6. NÕu D2 − D1 ≤ε D1 th× mét gi¶i ph¸p ®· ®îc t×m ra. Lu l¹i kÕt qu¶ vµ tho¸t khái ch¬ng tr×nh. 7. §Æt D1 = D2 8. Quay l¹i bíc 3. Mét ch¬ng tr×nh C cho gi¶i thuËt trªn ®îc ®Ò cËp ®Õn ë díi ®©y. Tõ biÓu thøc (13.52) vµ (13.58) chóng ta cã thÓ ph¸t triÓn mét ch¬ng tr×nh cho t×nh tr¹ng mÐo tèi thiÓu: N −1 ∑ ∫d p ( y )dy  d k +1 d k +1 Dmin = y 2 p ( y )dy − rk2 ∫ (13.59)   k dk   k =0 Lîng tö ho¸ c¸c hÖ sè cña FCT Trong phÇn 13.4 chóng ta ®· b¾t ®Çu vÊn ®Ò cña biÕn ®æi cho m· ho¸. Ph¬ng ph¸p chóng ta ¸p dông lµ chia ¶nh thµnh c¸c khèi h×nh vu«ng; mçi khèi cã kÝch thíc 8 × 8 vµ 16 × 16. BiÕn ®æi cosin nhanh cho mçi khèi nµy ®· ®îc rót ra. Chóng ta nhËn thÊy r»ng hÇu hÕt c¸c hÖ sè nµy cã biªn ®é rÊt nhá so víi c¸c gi¸ trÞ xung quanh khèi (mét chiÒu) DC. C©u hái ®Æt ra lóc nµy lµ c¸c hÖ sè nµo chóng ta cÇn lu gi÷ vµ b»ng ph¬ng ph¸p nµo chóng ta cã thÓ lu gi÷ tèt nhÊt c¸c gi¸ trÞ nµy? C©u tr¶ lêi cho vÊn ®Ò nµy cã thÓ t×m thÊy trong phÇn lîng tö ho¸ mµ chóng ta ®· nghiªn cøu ë trªn. Chó ý lµ c¸c hÖ sè cña FCT x¸c ®Þnh mét d¹ng biÕn d¹ng. Cho vÝ dô, mét ¶nh cã 256 × 256 ®iÓm vµ kÝch thíc cña c¸c khèi lµ 8 × 8 ®iÓm, cã tÊt c¶ 64 hÖ sè cho mçi khèi vµ 32 × 32 khèi. Mçi hÖ sè cã 1024 gi¸ trÞ khi chóng ta xem xÐt tÊt c¶ c¸c khèi, vµ t¹o nªn mét biÕn d¹ng riªng. §¸nh gi¸ biÕn d¹ng cho hÖ sè thø j cã thÓ cho bëi 17
d N J −1 k +1 j Dj = ∑ ∫(y − r k =0 d k k, j ) p j ( y )dy (13.60) j j = 0, 1, 2, ..., L - 1. ë ®©y L lµ sè c¸c hÖ sè cho mét khèi vµ Nj sè c¸c møc lîng tö cho hÖ sè j. Tæng sè c¸c biÕn d¹ng sÏ lµ L −1 D = ∑ Dj (13.61) j =0 Lµm theo c¸c bíc trong phÇn 13.5 chóng ta ®îc d k +1 j ∫dk j yp j ( y )dy rk , j = d k +1, j (13.62) ∫ d kj p j ( y )dy rk , j + rk +1, j vµ dk, j = (13.63) 2 NÕu chóng ta coi r»ng bÊt kú hÖ sè nµo cã thÓ x¸c ®Þnh b»ng cïng mét hµm kh¶ n¨ng xuÊt hiÖn ®é s¸ng, th× thay thÕ gi¸ trÞ c¸c hÖ sè nµy (mµ ®îc biÓu diÔn trong biÓu thøc trªn lµ y) b»ng y − µj (13.64) σj Chóng ta sÏ cho tÊt c¶ c¸c hÖ sè víi c¸c ph©n bè xuÊt hiÖn gièng nhau, víi gi¸ trÞ trung b×nh vµ chuÈn cña ®é lÖch cho bëi µ = 0 vµ σ = 1. KÕt qu¶ sau khi tÝnh to¸n cho ta c¸c møc chia vµ c¸c møc kh«i phôc cho tÊt c¶ hÖ sè “chia”. §iÒu nµy tÊt nhiªn chØ ¸p dông víi ®iÒu kiÖn lµ c¸c hÖ sè cã cïng mét sè c¸c bit. Tríc khi ®a ra c¸c møc lîng tö chóng ta cã thÓ bá bít mét sè hÖ sè. NÕu hÖ sè (0, 0) hay cßn gäi lµ thµnh phÇn mét chiÒu DC biÓu diÔn cho gi¸ trÞ trung b×nh cña ®é s¸ng cña mét khèi, chóng ta kh«ng thÓ bá ®iÓm nµy ®i ®îc. C¸c hÖ sè kh¸c trong mét khèi (cßn gäi lµ c¸c hÖ sè xoay chiÒu AC) mang c¸c th«ng tin vÒ c¸c chi tiÕt cña ¶nh. Cã thÓ nhËn thÊy lµ c¸c chi tiÕt cã ®é lÖch lín h¬n ®é lÖch chuÈn th× mang nhiÒu tin tøc h¬n c¸c chi tiÕt cã ®é lÖch Ýt h¬n ®é lÖch chuÈn. V× vËy mµ chóng ta b¾t ®Çu lîc bá c¸c hÖ sè b¾t ®Çu tõ vïng cã tr¶i réng Ýt nhÊt. VËy bao nhiªu hÖ sè sÏ ®îc chóng ta gi÷ l¹i? §iÒu nµy phô thuéc vµo møc ®é mµ chóng ta muèn nÐn ¶nh vµ phô 18
thuéc vµo bao nhiªu c¸c chi tiÕt bÞ mÊt trªn ¶nh mµ chóng ta cã thÓ chÊp nhËn ®îc. Dùa trªn c¸c gi¶ thiÕt trªn chóng ta cã thÓ ph¸t triÓn mét thuËt to¸n cho nÐn ¶nh vµ lîng tö ho¸. C¸c bíc sau m« t¶ cho c¶ viÖc lîng tö ho¸ c¸c hÖ sè FCT. 1. TÝnh µ vµ σ cho tÊt c¶ c¸c hÖ sè FCT. (Chó ý lµ ®é lÖch chuÈn vµ trung b×nh cã thÓ tÝnh trong mét d¶i th«ng cña ¶nh dïng biÓu thøc sau cho σ: n∑ xi2 − ( ∑ xi ) 2 σ = 2 n(n − 1) ë ®©y xi biÓu diÔn c¸c gi¸ trÞ cho mét trong c¸c hÖ sè). µ ®îc tÝnh tõ tæng cña xi. 2. ¸p dông c¸c hÖ sè cho c¸c chi tiÕt ®îc gi÷ l¹i cô thÓ lµ 0.25 , 0.5. 3. Gi÷ l¹i c¸c hÖ sè ®· nh©n thªm ph©n sè chia cã sai lÖch cao h¬n sai lÖch chuÈn. 4. §Þnh d¹ng mét ma trËn T cã d¹ng 1 nÕu hÖsè (i, j) kh«ng mÊt Tij =  0 c¸c tr-êng hîp cßn l¹i 5. Chia kho¶ng c¸ch c¸c hÖ sè cij (cô thÓ mét cho c¸c gi¸ trÞ mµ Tij = 1) trong tÊt c¶ c¸c khèi, ngo¹i trõ c¸c gi¸ trÞ mét chiÒu cho mçi khèi, nh sau: cij − µ ij (13.65) σ ij 6. TÝnh ph©n bè cña c¸c gi¸ trÞ AC “chia” cho m¶ng FCT. 7. TÝnh σs cña ph©n bè rót ra tõ c¸c bíc tríc. 8. Dïng lîng tö ho¸ Lloyd-Max møc N, vµ söa l¹i c¸c møc chia vµ kh«i phôc c¸c møc theo: di ⇐ di × σ s (13.66) 19
i = 0, 1, 2, ..., N - 1. chó ý dN = -d0 Hµm ph©n bè Laplace cung cÊp mét xÊp xØ tèt h¬n cho ph©n bè cña c¸c hÖ sè chia nh chóng ta thÊy ë phÇn díi ®©y. Sù lùa chän cña N còng nh c¸c hÖ sè chia cña c¸c hÖ sè phô thuéc møc ®é nÐn. 9. Lîng tö c¸c hÖ sè AC “ chia” dïng lîng tö ho¸ cña bíc 8. 10. Chia mçi gi¸ trÞ mét chiÒu víi 2. §iÒu nµy ®¶m b¶o r»ng c¸c gi¸ trÞ mét chiÒu kh«ng vît qu¸ 255 (mét biÓu diÔn 8 bit). 11. §Þnh d¹ng mét phÇn ®Çu file chøa ®Çy ®ñ th«ng tin ®Ó kh«i phôc l¹i ¶nh bÞ nÐn. PhÇn nµy chøa th«ng tin vÒ c¸c møc chia vµ c¸c møc mét chiÒu bÞ c¾t bít vµ tËp hîp c¸c gi¸ trÞ AC cho c¸c hÖ sè gi÷ l¹i. 12. ¸p dông mµ m· ho¸ Huffman cho file chøa c¸c gi¸ trÞ AC. Ma trËn T thêng gäi lµ ma trËn khu vùc, vµ cÇn cung cÊp c¸c hÖ sè cho chøc n¨ng kh«i phôc. PhÇn ®Çu file dïng bèn th«ng tin theo thø tù sau. ChiÒu réng cña khèi (ta coi khèi lµ mét h×nh vu«ng): 1byte. Sè c¸c møc lîng tö: 1 byte. ChiÒu réng cña ¶nh: 2 byte. Ma trËn T: 1 bit cho mét phÇn tö. §é lÖch chuÈn, trung b×nh: 4 byte trong biÓu diÔn sè thùc × sè c¸c hÖ sè. C¸c møc kh«i phôc: 4 byte trong biÓu diÔn sè thùc/ møc. Ch¬ng tr×nh 13.11 ®a ra lîng tö cña c¸c hÖ sè biÕn ®æi cosin dïng c¸c bíc trªn. KÕt qu¶ cña ch¬ng tr×nh lµ 3 file cã cïng tªn do ngêi dïng x¸c ®Þnh, nh- ng cã phÇn më réng kh¸c nhau. NÕu ngêi dïng cho tªn ‘image1q’ khi tr¶ lêi cho th«ng b¸o “Enter file name to store quantized image ...” xuÊt hiÖn khi ch¹y ch¬ng tr×nh, ba file sau ®©y ®îc t¹o ra: 20