Xử lý ảnh số - Nén dữ liệu ảnh part 7

Chia sẻ: Adfgajdshd Asjdaksdak | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

91
lượt xem 11
download

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

Tham khảo tài liệu 'xử lý ảnh số - nén dữ liệu ảnh part 7', 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: Xử lý ảnh số - Nén dữ liệu ảnh part 7

yˆu l` g´n x´c suˆ t d ˆi v´.i k´ hiˆu shift tru.´.c khi m˜ ho´ Huﬀman khˆi tham chiˆu. ´ ´´ ´ ´ e aa a a ¯o o y e o aa o e . .`.ng ph´p g´n thu.c hiˆn bˇ ng c´ch lˆ y tˆ’ng x´c suˆ t cua tˆ t ca c´c k´ hiˆu ´˙ .` ´’´’ a ˙ a ˙a y e Thˆng thu o o ea ea a ao a . . .c l` d nh ngh˜a k´ hiˆu tiˆn tˆ nhu. trong m˜ Huﬀman chˇt ´ ´u ıye`o e´ ngo`i khˆi tham chiˆu; t´ a ¯i a o e a a . . . .`.ng ho.p n`y, tˆ’ng lˆ y t`. a dˆn a v` do d ´ bˇ ng 0.39. Do d o k´ hiˆu ˙ ` ´ u 8 ¯e 21 a ´ cut. Trong tru o ao a ¯o a ¯´ y e . . . .n nhˆ t v` d u.o.c g´n mˆt t`. m˜ Huﬀman l` 00. ´ ´eo ´ shift c´ x´c suˆ t xuˆ t hiˆn l´ oa a a a a¯ . a oua a . . ´ M˜ ho´ sˆ hoc a ao . Kh´c v´.i c´c m˜ c´ d ˆ d`i thay d ˆ’i d .o.c d` cˆp trˆn, m˜ ho´ sˆ hoc sinh ra c´c t`. ˙ ´ aoa a o ¯o a ¯o ¯u . ¯ˆ a e. e a ao . au . .o.ng u.ng mˆt mˆt gi˜.a c´c k´ hiˆu nguˆn ˜ ` ˙a ’ m˜ khˆng phai l` chuˆi c´c bit. Khˆng c´ tu ao oa o o ´ o ouaye o . . . v` c´c t`. m˜. Thay v`o d ´, mˆt d˜y c´c k´ hiˆu nguˆn (hay thˆng b´o) d .o.c g´n ` aa u a a ¯o oaaye o o a ¯u . a . . . m˜. T`. m˜ n`y l` mˆt sˆ thu.c thuˆc khoang [0, 1). Khi sˆ c´c k´ hiˆu ` .´ ´ ˙ ’ bˇ ng mˆt t` a u a a a o o . a ou o oa y e . . . ` n trong thˆng b´o tˇng th` khoang biˆ’u diˆn n´ s˜ nho d i v` sˆ c´c d .n vi thˆng ˙ ˜ oe ´ ˙ ’ ˙ ¯ a o a ¯o . o ’ nguˆ o o aa ı e e tin (chˇng han, bit) biˆ’u diˆn khoang n`y s˜ nhiˆu ho.n. Mˆi k´ hiˆu cua thˆng b´o ˙ ˙’ ˜ ˜ ` ˙ ’ ˙ ’ a e e ae e oye o a . . s˜ thu gon k´ch thu.´.c cua khoang tu.o.ng u.ng v´.i x´c suˆ t xuˆ t hiˆn cua n´. Kh´c v´.i ´ ´e˙o o˙ ’ ˙ ’ ’ e .ı ´ oa a a ao . .o.ng ph´p m˜ ho´ Huﬀman, k˜ thuˆt n`y khˆng d oi hoi mˆi k´ hiˆu nguˆn tu.o.ng ˜ ` o ¯` ˙ ’oye phu a aa y aa o . . u.ng mˆt sˆ nguyˆn m˜ ho´ k´ hiˆu (t´.c l` c´c k´ hiˆu d .o.c m˜ ho´ riˆng biˆt) nˆn vˆ .´ e` ´ oo e a ay e u a a y e ¯u . a ae e e . . . .´.i d .o.c thiˆt lˆp bo.i d nh l´ m˜ ho´ khˆng nhiˆu (xem ˜ ´ ´. ˙ ¯i ’. mˇt l´ thuyˆt n´ d at cˆn du o ¯u . ay e o ¯. a ea yaao e . . ` Phˆn 6.3.3). a D˜y m˜ ho´ a aa ..................................... . . . . .. . . . . . . . . .. . . .. . a1 a2 a3 a4 a5 ....................................................................................................................................................................................................................................................................................................................................................................... . . . . . . . . ... . . . . . . . . ... . . . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . 1−........ 0.2 −........ 0.08 −........ 0.072 −........ ... 0.0688 − . . ... .................. .. . .. . .. ... .... ... . . .. . .. .. . ... .. . ... .. .. . .. ... .. . .. ... .. . a4 .................. . a4 ............... a4 a4 . a4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .. . . . . . . . .. .. . .. − −..... − −.... . . . . . 0.06752 −.......... ............................... − − . . . . . . . . . . . . . . . . . . .. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .. . .. . . . . a3 a3 a3 a3 a3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . − −− − −........ − −....... − . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . a2 a2 a2 ......... a2 ....... a2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. . . . . .. . . . . . . −− − −................ − − − . . . . . . . . . . . . . . .. . . . . . . .. . . . . . . . . . . . . . . . .. . . . .. . . . . . .. a1 a1 a1 a1 a1 . . . . . . ... ... . . . . . .. . . . . . .. . . . ... . . . . . . ... . . . . . . . .. . . .... . ... . . . . . .. ... . . . . . .. . . . . . .. ... .... ... . . . .. . . .. . .... 0− ................................................................. 0− 0.04 − 0.056 − 0.0624 − . . . . . . . . . . . ´ H` 6.10: Thuˆt to´n m˜ ho´ sˆ hoc. ınh a a a ao . . ´ ´ ` H` 6.10 minh hoa tiˆn tr`nh m˜ ho´ sˆ hoc. X´t d˜y (thˆng b´o) gˆm nˇm ınh e ı a ao . ea o a o a . . mˆt nguˆn gˆm bˆn k´ hiˆu. Kho.i tao, thˆng b´o chiˆm `` ´ ´ ˙. ’ k´ hiˆu m := a1a2 a3a3a4 t` o ye u. oo oye o a e . . . chı ra trong Bang 6.4, khoang n`y d .o.c phˆn chia to`n bˆ khoang J1 := [0, 1). Nhu ˙ ˙ ’ ’ ˙ ’ ˙ ’ ao a ¯u . a . 177
Khoang kho.i tao ` ´ ˙ ’ ˙. ’ Ky hiˆu nguˆn ´e o X´c suˆ t a a . a1 0.2 [0.0, 0.2) a2 0.2 [0.2, 0.4) a3 0.4 [0.4, 0.8) a4 0.2 [0.8, 1.0) ´ ˙ ’ Bang 6.4: V´ du m˜ ho´ sˆ hoc. ı . a ao . th`nh bˆn v`ng con du.a trˆn x´c suˆ t xuˆ t hiˆn cua mˆi k´ hiˆu nguˆn. Chˇng han, ˜ ˙ ’ ´ ´ ´e˙ ` ’ a ou ea a a oye o a . . . . .o.ng u.ng khoang con [0, 0.2). V` d ay l` k´ hiˆu d` u tiˆn cua thˆng b´o ˙ ’ ˙ ’ k´ hiˆu a1 tu ye ´ ı ¯ˆ a y e ¯ˆ a e o a . . ˙ ’ ˙ ’ m nˆn khoang [0, 1) s˜ thu hep th`nh J2 := [0, 0.2). Do d ´ trong H` 6.10 khoang J2 e e a ¯o ınh . .o.c k´o d˜n ra v´.i d o cao bˇ ng 1 v` c´c d e’m d a u cuˆi cua n´ d .o.c g´n c´c gi´ ˙ ` ´ ´ ’ o ¯u . a a o˙ du . e a ¯ o ¯ˆ a a a ¯iˆ ¯ˆ a . tri cua khoang hep ho.n n`y. Kˆ tiˆp khoang J2 d u.o.c chia th`nh nh˜.ng khoang con ´´ .˙ ’ ˙ ’ ˙ ’ ˙ ’ a ee ¯. a u . .o.ng u.ng v´.i x´c suˆ t xuˆ t hiˆn cua t`.ng k´ hiˆu nguˆn v` qu´ tr` lai tiˆp tuc ´ ´ ` ´ ˙u ’ tu ´ oa a a e ye o a a ınh . e . . . v´.i k´ hiˆu tiˆp theo trong thˆng b´o m. Ta c´ k´ hiˆu a2 thu hep khoang J2 th`nh ´ ˙ ’ oye e o a oy e a . . . ˙ ’ ˙ ’ khoang J3 := [0.04, 0.08); k´ hiˆu a3 thu hep khoang J3 th`nh J4 := [0.056, 0.072) v` ye a a . . ` ´ sau d ´ th`nh J5 := [0.0624, 0.0688). K´ hiˆu nguˆn cuˆi c`ng trong thˆng b´o (l` a4) ¯o a ye o ou o aa . . k´ hiˆu d ac biˆt d ´nh dˆ u kˆt th´c thˆng b´o s˜ thu hep khoang J th`nh ´´ ˙ ’ xem nhu y e ¯ˇ e ¯a ae u o ae a . . . . 5 J6 := [0.06752, 0.0688). D˜ nhiˆn c´ thˆ’ d`ng mˆt sˆ bˆ t k` thuˆc khoang J6 (chˇng ˙ ˙ ’ . ´´ ˙ ’ ı e o eu ooa y o a . han, 0.068) d e’ biˆ’u diˆn cho thˆng b´o m. ˙˙ ˜ ¯ˆ e e o a . Theo c´ch m˜ ho´ sˆ hoc tr` b`y trˆn, ch´ng ta cˆn ba ch˜. sˆ thˆp phˆn dˆ’ ˙ ´ ` ´. a a ao . ınh a e u a uo a a ¯e m˜ ho´ thˆng b´o gˆm nˇm k´ hiˆu. T´.c l` su. dung 3/5 hay 0.6 ch˜. sˆ thˆ p phˆn a` ´´ u a˙ .’ aao o a ye uo a a . dˆ’ biˆ’u diˆn mˆt k´ hiˆu. Ch´ y rˇ ng entropy cua nguˆn l` 0.58. Khi d o d`i cua d˜y ˙˙ ˜ u´ ` `a ˙ ’ ¯ˆ a ˙ a ’ ¯e e e oye a o . . . . sˆ thˆp phˆn d e’ biˆu diˆn mˆt k´ hiˆu s˜ tiˆn d e n ˙e a ¯ˆ ˜ ˜ ` ıo u´ . ´ ´´ cˆn m˜ ho´ tˇng lˆn th` sˆ ch˜ o a a a aa e e o y e e e ¯ˆ . . cˆn du.´.i d .o.c thiˆt lˆp bo.i d .nh l´ m˜ ho´ khˆng nhiˆu. Trong thu.c tˆ, hai nhˆn tˆ ˜ ´. ´ ´ ˙ ¯i ’ a o ¯u . ea yaao e .e ao . .o.c cˆn du.´.i n`y l`: (1) thˆm dˆ u hiˆu kˆt th´c thˆng b´o dˆ’ ˙ ´ ´ ´ khiˆn cho khˆng d at d u . a e o ¯. ¯ oaa e a ee u o a ¯e . . t´ch c´c thˆng b´o; v` (2) su. dung sˆ v´.i d o ch´ x´c h˜.u han. Dˆ’ giai quyˆt vˆ n -e ˙ ˙’ ´ ´´ ˙. ’ a a o a a o o ¯ˆ ınh a u ea . . .c hiˆn bu.´.c co gi˜n v` bu.´.c l`m tr`n. Ph´p co gi˜n nhˇ m d` sau ch´ng ta c´ thˆ’ thu ˙ ` ¯ˆe u oe. e o aa oa o e a a . chuˆ’n ho´ mˆi khoang con th`nh khoang [0, 1) tru.´.c khi phˆn chia n´ th`nh nh˜.ng ˙ ˜ ˙’ ˙ ’ a ao a o a oa u .o.ng u.ng x´c suˆ t xuˆ t hiˆn cua k´ hiˆu. Giai d oan l`m tr`n bao d ˙ m ´ ´e ˙ ’ ˙ye ’ ˙ ¯a ’ ’ khoang con tu ´ a a a ¯. a o . . c´c ph´p l`m tr`n sˆ cho sˆ v´.i d o ch´ x´c h˜.u han khˆng l`m mˆ t t´nh ch´nh x´c ´ ´ ´ a ea oo o o ¯ˆ ınh a u o a aı ı a . . ˙ ’ ˙ ’ cua qu´ tr`nh m˜ ho´ c´c khoang con. aı a aa 178
˙ ’ 6.4.2 M˜ ho´ mˇt phˇ ng bit a aa a . Ch´ng ta d a tr` b`y nh˜.ng phu.o.ng ph´p ch´nh dˆ’ giam du. th`.a trong m˜ ho´. ˙’ ¯e ˙ u ¯˜ ınh a u a ı u aa Phˆn kˆ tiˆp s˜ d` cˆp d e n mˆt sˆ phu.o.ng ph´p n´n bao to`n thˆng tin giam du. th`.a ` e e e ¯ˆ a ¯ˆ a ´´ ´ .´ ae˙ ’ ˙ ’ e. oo a o u .a c´c pixel. Tru.´.c hˆt, k˜ thuˆt m˜ ho´ mˇt phˇng bit du.a trˆn ˙ ’ ´ trong quan hˆ gi˜ a eu oe y a aaa a e . . . . kh´i niˆm phˆn r˜ mˆt anh nhiˆu m´.c x´m (d .n sˇc hay m`u) th`nh mˆt d˜y c´c ´ ` a a o˙ .’ ae e ua ¯o a a a oaa . . .o.ng ph´p n´n anh nhi ´ ˙ nh nhi phˆn v` n´n c´c anh nhi phˆn thˆng qua mˆt sˆ phu ’ ˙ ’ a e˙ ’ a . a ae a .a o oo . . ` ´ o˙a a ’ phˆn quen thuˆc. Phˆn n`y mˆ ta c´c c´ch phˆn r˜ quen thuˆc nhˆ t v` nh` lai mˆt a o aa aa o a a ın . o . . . .o.ng ph´p n´n thu.`.ng d`ng. v`i phu a ae o u ˙ ’ Phˆn r˜ mˇt phˇ ng bit aaa a . Ta biˆ’u diˆn c´c m´.c r cua anh x´m m-bit theo hˆ nhi phˆn ˙ ˜a ˙˙ ’’ e e u a e.a . r = am−1 2m−1 + am−2 2m−2 + · · · + a121 + a020 . T`. d ´ ta c´ thˆ’ phˆn r˜ anh th`nh c´c anh nhi phˆn bˇ ng c´ch t´ch m hˆ sˆ ai th`nh ˙ ` .´ o e a a˙ ’ a˙ ’ u ¯o a .aa a a eo a m mˇt phˇng bit; mˆi mˇt phˇng biˆ’u diˆn mˆt bit. Nhu. d ˜ d` cˆp trong Chu.o.ng 4, ˙ ˙ ’ ˜ ˙ ’ ˜ a a oa a e e o ¯a ¯ˆ a e. . . . mˇt phˇng bit d` u tiˆn (bˆc khˆng) gˆm c´c bit a0; mˇt phˇng bit bˆc (m − 1) ch´.a ˙ ’ ˙’ ` a a ¯ˆ a e a o o a a a a u . . . . c´c bit am−1 . N´i chung, mˆi mˇt phˇng bit d .o.c d anh sˆ th´. tu. t`. 0 dˆn m − 1 v` ˜ ˙ ’ ´ ´ a o oa a ¯u . ¯´ o u . u ¯e a . .o.c xˆy du.ng bˇ ng c´ch d ˇt c´c pixel cua n´ bˇ ng c´c gi´ tri bit (hay hˆ sˆ) th´ch ` ` .´ ˙ oa ’ du . a ¯ a a ¯a a a a. eo ı . . ho.p t`. mˆi pixel trong anh gˆc. Nhu.o.c d iˆ’m cua c´ch tiˆp cˆn n`y l` mˆt thay d ˆ’i ˙ ˙ ˜ ´ ´. ˙ ’ ˙a ’ .uo o . ¯e eaaao ¯o . nho vˆ gi´ tri x´m dˆn d e n anh hu.o.ng rˆ t l´.n vˆ d ˆ ph´.c tap cua c´c mˇt phˇng bit. ˜ ˙ ’ ˙` a .a ´’ a o ` ¯o u . ´ ’e a ¯ˆ ˙ ˙ ’ ˙a ’ e. a a . Chˇng han, nˆu pixel c´ gi´ tri 127 (0111111) kˆ v´.i pixel c´ cu.`.ng d ˆ 128 (1000000) ˙’ ´ `o a e oa. e oo ¯o . . .a liˆn tiˆp 0 1 (hoˇc 1 0). V´ du, v` c´c bit quan trong ˜ ˙’ ´ th` mˆi mˇt phˇng bit s˜ ch´ ıoa a eue e a ı. ıa . . . ´t cua hai t`. m˜ nhi phˆn 127 v` 128 kh´c nhau nˆn mˇt phˇng bit 7 s˜ ch´.a mˆt ˙ ’ nhˆ ˙ a’ ua.a a a e a a eu o . . pixel gi´ tri 0 kˆ tiˆp mˆt pixel gi´ tri 1 v` s˜ l`m chuyˆ’n trang th´i 1 sang 0 (hoˇc 0 ˙ ´´ a. ee o a. aea e a a . . . sang 1) tai pixel n`y. a . Dˆ’ giam anh hu.o.ng thay d ˆ’i nho gi˜.a c´c gi´ tri x´m ta c´ thˆ’ biˆ’u diˆn anh -e ˙ ˙ ˙’’ ˙ ˙˙ ˜˙ ˙ ’ ˙ua ’ e’ ¯o a.a oee dang m˜ Gray m-bit. M˜ n`y s˜ biˆ’u diˆn gi´ tri r th`nh d˜y nhi phˆn gm−1 gm−2 . . . g0 ˙ ˜ a aa e e e a. a a .a . .i v´ o gi = ai ⊕ ai+1 , i = 0, 1, . . . , m − 2, gm−1 = am−1 , trong d o ⊕ k´ hiˆu ph´p to´n OR. M˜ Gray c´ t´nh chˆ t giai m˜ duy nhˆ t v` hai t`. ´ ´ ˙ ’a ¯´ ye e a a oı a aa u . m˜ liˆn tiˆp chı kh´c nhau dung mˆt vi tr´ bit. Do d o khi c´ thay d o’i nho trong c´c ˙ ´ ˙a ’ ˙’ ae e ¯´ o.ı ¯´ o ¯ˆ a . 179
mu.c x´m n´ ´ anh hu.o.ng d e n tˆ t ca m mˇt phˇng bit. Chˇng han khi c´c pixel c´ ˙ ’ ˙ ’ ´´’ o ıt ˙ ’ ˙ ’ ¯ˆ a ˙ ´a a a a a o . . . 7 xay ra trang th´i chuyˆ’n t`. ˙ ˙ ’ ` ı ˙o a ’ ˙ ’ gi´ tri 127 v` 128 kˆ nhau th` chı c´ mˇt phˇng bit th´ a. a e a u a eu . . 0 sang 1 do c´c t`. m˜ Gray cua 127 v` 128 tu.o.ng u.ng l` 11000000 v` 01000000. ˙ ’ aua a ´ a a ` ´ M˜ ho´ v`ng thuˆn nhˆt a au a a Dˆ’ n´n c´c anh nhi phˆn ta c´ thˆ’ su. dung c´c t`. m˜ d ac biˆt dˆ’ x´c d .nh c´c v`ng -e e a ˙ ˙ ˙’ ˙ ’ o e˙ . .a a u a ¯ˇ e ¯e a ¯i au . . liˆn thˆng c´ gi´ tri x´m 1 hoˇc 0. Ch´ng ta chia anh th`nh c´c khˆi c´ k´ch thu.´.c ´ ˙ ’ e o o a .a a u a a ooı o . ´ ´y ´’ a ˙a m × n pixel v` phˆn loai khˆi tu` theo tˆ t ca c´c gi´ tri trong v`ng l` trˇng, d hay aa o a. u aa ¯en . .p. V´.i nh˜.ng khˆi thu.`.ng xuyˆn xuˆ t hiˆn ta g´n t`. m˜ l` 0 v` hai khˆi c`n ˜ ´ ´e ´ hˆn ho o o u o o e a a u aa a oo . . lai g´n c´c t`. m˜ 10 v` 11. Khi d o v´.i nh˜.ng v`ng thuˆn nhˆ t (gi´ tri x´m khˆng ` ´ .aaua a ¯´ o u u a a a.a o .o.c thay bˇ ng mˆt t`. m˜ 1-bit hoˇc t`. m˜ 2-bit. D˜ nhiˆn t`. m˜ u.ng v´.i d ˆ’i) s˜ d . ˙ ` ¯o e ¯u a oua aua ı e u a´ o . . c´c khˆi hˆn ho.p d .o.c xem nhu. l` tiˆn tˆ m` sau d o l` mˆt mˆu mn-bit biˆ’u diˆn ˙ ´˜ ˜ ˜ a` o a e´ a oo . ¯u . ¯´ a o a e e . ´ cho khˆi. o Tru.`.ng ho.p nh˜.ng anh ch´.a t`i liˆu l` vˇn ban (k´ tu. d en trˆn nˆn trˇng), ta ´ e` ˙ ’ ˙ ’ o u u a e aa y .¯ e a . . c´ thˆ’ cai biˆn bˇ ng c´ch m˜ ho´ c´c khˆi d ac trˇng l` 0 v` tˆ t ca c´c khˆi kh´c (kˆ’ ˙’ e a ˙ ` ´ ´. ´’ ´ o e˙ aa ˙a a a aa o ¯ˇ a a o a e ca c´c khˆi d ac m`u d en) l` 1 theo sau d ´ l` mˆu bit cua khˆi. Phu.o.ng ph´p n`y (c´ ˜ ´. ´ ˙a ’ ˙ ’ o ¯ˇ a¯ a ¯o a a o aa o ´´ ´ e .a˙ ’ ˙e e o ’. tˆn goi l` bo qua khˆi trˇng v` k´ hiˆu WBS-White Block Skipping) cho tı lˆ n´n tˆt oa ay e . v´.i nh˜.ng anh biˆt tru.´.c vˆ cˆ u tr´c Mˆt cai biˆn d ac biˆt hiˆu qua cua thu tuc n`y ´ o `a e´ ˙ ’ o˙ . ’ e ¯ˇ ˙˙ ’’ ˙. a ’ o u e u e e . . . .i c´c khˆi k´ch thu.´.c 1 × n) l` m˜ ho´ c´c d`ng trˇng d ac l` 0 v` tˆ t ca c´c d`ng ´ ¯ˇ a ´ ´’ aa ˙a o (v´ a o oı o a a aa o a . kh´c l` 1 theo sau d˜y t`. m˜ WBS. Ch´ng ta c˜ng c´ thˆ’ su. dung phu.o.ng ph´p lˇp: ˙’ o e˙ . aa aua u u aa . .ng v`ng con cho d e n khi thoa yˆu cˆu. V´.i c´c ´ ˙e` ˙’ ’ phˆn chia anh nhi phˆn th`nh nh˜ a .a a u u ¯ˆ a oa khˆi 2-D ta m˜ ho´ anh trˇng d ac l` 0 v` tˆ t ca c´c anh kh´c d .o.c chia th`nh c´c ´ ´ ´’ a a˙ ’ aa ˙a˙ ’ o a ¯ˇ a a ¯u . a a . .o.c g´n tiˆn tˆ l` 1 v` sau d o d .o.c m˜ ho´ tu.o.ng tu.. ˜ khˆi con, mˆi khˆi con n`y d . a ` o a ´ ´ e´ o o o a ¯u a ¯´ ¯u . aa . .c l` nˆu mˆt khˆi con c´ tˆ t ca c´c pixel trˇng th` n´ d u.o.c m˜ ho´ l` 10: tiˆn tˆ 1 ´ ´ ´ ´’ `o e´ oa ˙a T´ a e u o o a ı o¯ . a aa . ´ chı ra d o l` khˆi con trong ph´p lˇp d` u tiˆn v` sˆ 0 chı ra d o l` khˆi d ac trˇng. Nˆu ´ ´ ´. ´ ˙ ’ ¯´ a o ˙’ ¯´ a o ¯ˇ e a ¯ˆ a e ao a e . khˆi con khˆng phai d ac trˇng th` ta tiˆp tuc phˆn chia cho d e n khi k´ thu.´.c cua ´ ´ ´ ´ ˙ ¯ˇ ’. ˙ ’ o o a ı e. a ¯ˆ ıch o .˜.ng n`o d ´ v` d .o.c m˜ ho´ th`nh 0 (nˆu tˆ t ca l` trˇng) hoˇc ´ ´ ´ ´´’ e a ˙a a khˆi con d at dˆn ngu o o ¯ . ¯e a ¯o a ¯u . aaa a. ˜ ´ ˙ ’ l` 1 theo sau d ´ l` mˆu bit cua khˆi. a ¯o a a o ` M˜ ho´ run length mˆt chiˆu a a o e . Thuˆt to´n run length rˆ t d .n gian v` hiˆu qua khi su. dung m˜ ho´ c´c tˆp tin d` ´ ˙ ’ae ˙ ’ ˙. ’ a a a ¯o a aa a ¯ˆ o . . . ´ co. ban l` ph´t hiˆn su. lˇp lai c´c pixel trˆn mˆi h`ng cua anh v` xuˆ t ˜ ´ ˙aa ’ ˙˙ ’’ hoa bitmap. Y e .a . a e oa aa . . . .ng gi´ o` a a o ´a . ´ ra hai gi´ tri: mˆt cho sˆ lˆn lˇp v` mˆt cho gi´ tri pixel lˇp thay v` xuˆ t t` a. o a. a ıau a . . . 180
tri pixel mˆt. M˜ ho´ run length khˆng hiˆu qua d ˆi v´.i c´c mˆu chˆ m d e’m hoˇc ˙ ˜ ’´ ´ ˙ ¯o o a o aa o e a a ¯iˆ a . . . . .o.c qu´t bo.i scan (thu.`.ng khˆng c´ su. lˇp lai). Ngu.o.c lai, run length l`m a˙ ’ ˙’ c´c anh d .¯u e o o o.a . a . .. .i c´c kiˆ’u d˜. liˆu kh´c v` d u.o.c d`ng d e’ n´n c´c tˆp tin dang BMP, ˙ ˙ .´´´ viˆc rˆ t tˆt d oi v´ a e a o ¯ˆ o e ue a a ¯ . u ¯ˆ e a a . . . PCX, TIFF, Apple MacPaint... ` M˜ ho´ run length mˆt chiˆu (RLC) a a o e . Khi qu´ tr`nh m˜ ho´ diˆn ra, tˆ t ca c´c d˜. liˆu d .o.c qu´t theo t`.ng h`ng v` d .o.c aa˜ ´’ a ˙ a u e ¯u . aı e e u a a ¯u . . .c x´m g . d ˆ’i th`nh d˜y c´c cˇp (lk , gk ) trong d o lk l` sˆ c´c pixel kˆ nhau c´ c`ng m´ a ˙a ´ ` ¯o aaa ¯´ aoa e ou u . k . nhiˆn) ˜ ´ eo` ´ Nˆu mˆi d`ng qu´t c´ chiˆu d`i N th` 1 ≤ lk ≤ N, do d ´ (nˆu d`ng m˜ ho´ tu e oo ea ı ¯o e u a a. e .n nhiˆu cˆn log2 N bit dˆ’ m˜ ho´ c´c gi´ tri lˇp lk . Nˆu hˆu hˆt c´c gi´ tri lˇp nho ho ˙ ` e` ´aea ´ ` ˙ ’ a ¯e a a a a .a a .a e . . so v´.i N th` c´ch m˜ ho´ tu. nhiˆn khˆng hiˆu qua. V` vˆy vˆ n d` tiˆp theo l` chon ´e´ ˙ ’ o ıa a a. e o e ı a a ¯ˆ e a. . . .o.ng ph´p m˜ ho´ c´c gi´ tri lˇp v` gi´ tri x´m sao cho tˆi u.u. Diˆu n`y ho`n to`n -` ´ phu a a a a a .a a a . a o ea a a . phu thuˆc v`o d˜. liˆu ban d` u. o a ue ¯ˆa . . . ` ˙ ’ M˜ ho´ run length hai chiˆu (PDQ v` DDC) cho anh nhi phˆn a a e a a . Phu.o.ng ph´p lu.o.ng tu. ho´ sai phˆn du. b´o, k´ hiˆu PDQ, biˆn d o’i mang c´c gi´ ˙ ´ ˙ ’ ˙ ’ a a a .a ye e ¯ˆ a a . . tri x´m hai m´.c th`nh d˜y c´c cˇp sˆ nguyˆn (∆ , ∆ ), trong d o ∆ := xs − xs l` ´ .a u a aaao e ¯´ 1a . 2 .a c´c ho`nh d ˆ d iˆ’m kho.i d` u cua c´c d`ng qu´t trˆn hai d`ng liˆn tiˆp, v` ˙ ´ ˙ ¯ˆ ’a ˙ao ’ hiˆu gi˜ a e u a ¯o ¯ e ee o e e a . . ∆ := l2 − l1 l` hiˆu gi˜.a c´c gi´ tri lˇp trˆn hai d`ng liˆn tiˆp. Ngo`i ra ch´ng ta ´ ae ua a .a e o e e a u . . . dung thˆm c´c dˆ u hiˆu “new start” v` “merge” d e’ k´ hiˆu d`ng bˇt d` u v` d`ng ˙ ´a ´ ˙ ’ su . e aa e a ¯ˆ y e o a ¯ˆ a o . . kˆt th´c cua mˆi v`ng d oi tu.o.ng. Kˆ tiˆp ta c´ thˆ’ d`ng m˜ B1 dˆ’ m˜ ho´ c´c d ai ˙ ˙ ˜ ´ ´ ´´ u˙ ’ e ou ¯ˆ ee o eu a ¯e a a a ¯ . . lu.o.ng ∆ , ∆ , new start v` merge. a . Ch´ng ta c˜ng c´ thˆ’ m˜ ho´ delta k´p (DDC) bˇ ng c´ch su. dung ∆ v` ∆ ˙ ` ˙. ’ u u oeaa e a a a .a c´c ho`nh d o d iˆ’m kˆt th´c ˙ e e ´ thay cho ∆ v` ∆ , trong d ´ ∆ := x2 − x1 l` hiˆu gi˜ a a ¯o ae u a ¯ˆ ¯ e e u . . ´ ˙ao ’ cua c´c d`ng qu´t trˆn hai d`ng liˆn tiˆp. ee o e e Nhˆn x´t rˇ ng, v´.i nh˜.ng d oi tu.o.ng d l´.n, c´ch m˜ ho´ run length hai chiˆu ae` ´ ` a o u ¯ˆ ¯en o a aa e . . .n; ngu.o.c lai, nˆu c´ nhiˆu v`ng d nho th` m˜ ho´ run length mˆt chiˆu ´ ` ` ˙ ’ ˙ıaa ’ hiˆu qua ho e eo e u ¯en o e . .. . .n. ˙ ’ hiˆu qua ho e . 181
6.4.3 M˜ ho´ sai phˆn a a a Phu.o.ng ph´p n`y thu.`.ng su. dung trong tru.`.ng ho.p anh sˆ c´ c´c gi´ tri x´m tu.o.ng ´ ˙. ’ .˙ ’ aa o o ooa a.a tu.; n´i c´ch kh´c, biˆ’u d` cˆt cua anh tˆp trung v`o mˆt v`ng. ˙ o. ’’ e ¯ˆ o ˙ ˙ .oa a a a ou . . -ˆ e D` u tiˆn ta biˆn d ˆ’i tˆp c´c gi´ tri x´m z0 , z1, . . . , zN −1 th`nh d˜y d0 , d1 , . . . , dN −1 ˙. ´ a e ¯o a a a . a a a x´c d .nh bo.i ˙ ’ a ¯i d0 = z0, di = zi − zi−1 , i ≥ 1. Bu.´.c kˆ tiˆp su. dung mˆt trong c´c bˆ m˜ Huﬀman, m˜ Shift... d e’ m˜ ho´ d˜y ˙ ´´ ˙. ’ o ee o aoa a ¯ˆ a a a . . di , i = 0, 1, . . . , N − 1. Chˇng han, nˆu d˜y di thay d o’i trong pham vi [−127, 127] v` ˙ ˙ ’ ´ a ea ¯ˆ a . . thu.`.ng tˆp trung v`o khoang (−8, 8) ta c´ thˆ’ xˆy du.ng bˆ m˜ tu. nhiˆn gˆm 16 t`. m˜ ˙ e` ˙ ’ o a a o ea . o a. o ua . . . m˜ c , c , . . . , c tu.o.ng u.ng 14 gi´ tri −7, −6, . . . , −1, 0, 1, . . . , 6; c0 , c1, . . . , c15 : trong d o 14 t` a 1 2 ¯´ u ´ a. 14 hai t`. m˜ c`n lai, c0 su. dung d e’ d ´nh dˆ u gi´ tri di < −7 v` c15 d anh dˆ u di ≥ 7. ˙ ´ ´ ˙. ’ u ao . ¯ˆ ¯a a a. a ¯´ a Nguyˆn tˇc m˜ ho´ (nhu. m˜ Shift) nhu. sau: ´ ea aa a 1. nˆu di ∈ [−7, 6] ta su. dung t`. m˜ tu.o.ng u.ng gi´ tri n`y. Chˇng han, −7 d .o.c ˙ ’ ´ ˙. ’ e ua ´ a .a a ¯u . . m˜ ho´ l` c1, −6 l` c2 v` vˆn vˆn. a aa a aa a 2. nˆu di > 6, ta chuyˆ’n dich theo hu.´.ng lˆn. Chˇng han, 10 d u.o.c m˜ ho´ l` c15 c4, ˙ ˙ ’ ´ e e. o e a ¯. a aa . 25 l` c15 c15c5 . a 3. tu.o.ng tu. d ˆi v´.i c´c gi´ tri nho ho.n −7 ta chuyˆ’n dich theo hu.´.ng xuˆng. ˙. ´ ´ ˙ ’ . ¯o o a a. e o o Chˇng han, −8 d .o.c m˜ ho´ l` c0 c1 , −9 l` c0 c2 , −23 l` c0 c0 c13. ˙ ’ a ¯u . a aa a a . ´ 6.4.4 M˜ ho´ chu tuyˆn a a e Thuˆt to´n m˜ ho´ chu tuyˆn trong phˆn n`y giam k´ch thu.´.c anh bˇ ng c´ch lu.u mˆt ` ´ ` ˙ ’ o˙ ’ a a aa e aa ı a a o . . .o.c x´c d nh duy nhˆ t bo.i: ˜ ´ ´ ´’ a˙ danh s´ch c´c chu tuyˆn. Mˆi chu tuyˆn d . a ¯i a a e o e ¯u . 1. m´.c x´m cua chu tuyˆn; ´ ˙ ’ ua e 2. vi tr´ (h`ng v` cˆt) cua mˆt pixel trˆn biˆn cua n´, goi l` d iˆ’m kho.i tao (IP-initial ˙ ˙ ’ e ˙ o . a¯e ’ ˙. ’ .ıa ao o e . . point); v`a 3. mˆt d˜y c´c hu.´.ng cho ph´p ch´ng ta xˆy du.ng lai chu tuyˆn. ´ oaa o e u a e . . . a` ˙. ’ Thuˆt to´n gˆm hai thu tuc con: a o . 182