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

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

Thêm vào BST

Báo xấu

71
lượt xem 12
download

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

Lưu ý rằng khi chúng ta để màn trập mở mở lâu thì việc máy bị rung cũng tạo thêm mờ nhòe. Cách tốt nhất để tránh hiện tượng này là sử dụng chân ba. Nếu không có chân ba thì kiếm một mặt phẳng vững và để chế độ chụp hẹn giờ. Kĩ thuật này cũng phù hợp với chụp cảnh đường phố vào ban đêm. Đặt máy lên giá đỡ và chỉnh tốc độ màn trập dài, (thử bắt đầu với thời gian 1 giây và khẩu độ khoảng f/5.6), luồng phương tiện đang chuyển động sẽ giống như...

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 8

1. thuˆt to´n IP x´c d .nh vi tr´ d iˆ’m kho.i tao m´.i (tu.o.ng u.ng trˆn chu tuyˆn m´.i); ˙ ´ ˙. ’ a a a ¯i . ı¯e o ´ e e o . v` a 2. thuˆt to´n T (tracing) t`m chu tuyˆn xuˆ t ph´t t`. d iˆ’m kho.i tao m´.i. ˙ ´ ´ ˙. ’ a a ı e a a u ¯e o . Hai thu tuc d .o.c thu.c hiˆn mˆt c´ch tuˆn tu.. Thuˆt to´n IP d .o.c su. dung dˆ’ ˙ ` ˙ . ¯u . ’ ¯u . ˙ .’ e oa a. a a ¯e . . . . x´c d inh d iˆ’m kho.i tao th´. nhˆ t trˆn chu tuyˆn th´. nhˆ t v` sau d ´ thuˆt to´n T ˙ ´e ´ ´ ˙. ’ a ¯. ¯e u a e u aa ¯o a a . d u.o.c su. dung d e’ ph´t hiˆn n´; tiˆp theo, thuˆt to´n IP d u.o.c su. dung d e’ x´c d inh ˙ ˙ ´ ¯. ˙ . ’ ¯. ˙ . ’ ¯ˆ a eoe a a ¯ˆ a ¯. . . d iˆ’m kho.i tao th´. hai trˆn chu tuyˆn th´. hai v` sau d o thuˆt to´n T d u.o.c su. dung ˙ ´ ˙. ’ ¯. ˙ . ’ ¯e u e e u a ¯´ a a . dˆ’ ph´t hiˆn n´; v` tiˆp tuc. Thuˆt to´n IP x´c d .nh tˆ t ca c´c chu tuyˆn; khˆng chu ˙ ´ ´’ ´ a ˙a ¯e a e oae . a a a ¯i e o . . .o.c x´c d nh hai lˆn. Thuˆt to´n T ph´t hiˆn biˆn cua tˆp liˆn thˆng l´.n ´ ` e˙ae’. tuyˆn n`o d u . a ¯i e a¯ a a a a e o o . . . nhˆ t gˆm c´c phˆn tu. c´ c`ng gi´ tri x´m nhu. d iˆ’m kho.i tao; n´ luˆn luˆn kˆt th´c ˙ a` ´o ` ´ a ˙ou’ ˙. ’ a a .a ¯e oo oe u .i tao. V´.i mˆi chu tuyˆn, thuˆt to´n cho ta gi´ tri x´m, vi tr´ cua d e’m tai d e’m kho . ˙ ˙ ˜ ´ ˙ ’ . ı ˙ ¯iˆ ’ . ¯iˆ o o e a a a .a . kho.i tao v` hu.´.ng di chuyˆ’n xung quanh biˆn. Tˆ t ca c´c phˆn tu. d u.o.c bao bo.i chu ˙ ´’ ` ˙.ao ’ a ˙a a ˙¯ . ’ ˙ ’ e e . chu tuyˆn d .o.c bo qua. ´ ´ ˙ ’ tuyˆn c´ c`ng gi´ tri nhu e ou a. e ¯u . Thuˆt to´n T a a . Thuˆt to´n T ´p dung nguyˆn tˇc t` d .`.ng d trong mˆ d . o (mazealways). Nhu. ´ a a a e a ım ¯u o ¯i e ¯a . . minh hoa trong H` 6.11, viˆc ph´t hiˆn chu tuyˆn cho ta hu.´.ng di chuyˆ’n gi˜.a hai ˙ ´ ınh e a e e o e u . . . . ngo`i chu tuyˆn v` kˆ v´.i n´ c´ c`ng gi´ ` ` e a` o oou ´ a˙ ’ pixel kˆ nhau sao cho khˆng c´ hai phˆn tu e o o a e a tri nhu. c´c phˆn tu. trˆn chu tuyˆn. Viˆc quyˆt d .nh hu.´.ng ra cua mˆi phˆn tu. l` ˜ ` ´ ´ ` a˙e ’ ˙ ’ a ˙a’ a e e e ¯i o o . . .o.ng d ˆi v´.i hu.´.ng v`o cua phˆn tu. n`y bo.i nguyˆn tˇc t`m bˆn tr´i nhˆ t (LML-left ´ ´ ` ´ a˙ ’ a ˙a ˙’ ’ tu ¯o o o eaı e a a most looking). Nguyˆn tˇc LML. T` phˆn tu. bˆn tr´i (d oi v´.i hu.´.ng v`o cua phˆn tu.); nˆu phˆn ´ ım ` ˙ e ´ `˙ ´ ` a’ a˙ ’ a’ ea a ¯ˆ o o e a tu. n`y c´ c`ng gi´ tri, di chuyˆ’n dˆn n´; nˆu khˆng, t`m phˆn tu. ph´a trˆn; nˆu phˆn ˙´ ´ ` ´ ` ˙ a ou ’ a˙ ’ a. e ¯e o e o ı ı e e a . n`y c´ c`ng gi´ tri, di chuyˆ’n d e n n´; nˆu khˆng, t` phˆn tu. ph´a bˆn phai; nˆu ˙´ ´ ım ` ´ ˙’ a˙ ’ ˙ ’e tu a o u a. e ¯ˆ o e o ıe phˆn tu. n`y c´ c`ng gi´ tri, di chuyˆ’n d e n n´; nˆu khˆng, quay tro. lai; nˆu khˆng, ˙´ ` ´ ´ a ˙ a ou ’ ˙. ’ a. e ¯ˆ o e o e o . kˆ c´ c`ng gi´ tri, do d o chu tuyˆn chı gˆm mˆt phˆn tu.. khˆng c´ phˆn tu ` o u o` ´ ˙` ` a ˙e’ ’o a˙ ’ o a. ¯´ e o. Thuˆt to´n T g´n mˆt trong bˆn dˆ u hiˆu d oi v´.i mˆi phˆn tu. cua mang hai ˜ ´a ´ ´ `a˙˙’’ ˙ ’ a a a o o e ¯ˆ o o . . . .o.c su. dung trong thuˆt to´n IP. Ch´ng ta k´ hiˆu bˆn dˆ u ` ´ ´´ chiˆu. C´c dˆ u hiˆu n`y d u . ˙ . ’ e aa e a¯ a a u yeoa . . . hiˆu bo.i R, D, A v` I. Kho.i tao, mˆi phˆn tu. d u.o.c g´n dˆ u hiˆu I. Khi thuˆt to´n ˜ ` ´ ˙ ’ ˙. ’ a ˙¯. a a ’ e a o e a a . . . .c hiˆn, n´ c˜ng cˆp nhˆt dˆ u hiˆu mˆi phˆn tu. trˆn chu tuyˆn theo nguyˆn tˇc ˜ ´ .´ ` ´ a˙e ’ T thu e ou a aa e o e ea . . . . ´ g´n dˆ u hiˆu (IA-indicator assignment). aa e . Nguyˆn tˇc IA. Dˆ u hiˆu d .o.c g´n d ˆi v´.i mˆi phˆn tu. trˆn chu tuyˆn phu thuˆc ´ ˜ ´ ´ ` ´ a˙e ’ ea a e ¯u . a ¯o o o e o . . . 183
IP 1 • −→ • −→ • −→ • −→ • −→ • −→ • −→ • ◦ ↑ ↓ • • ◦ • • • + + ↑ ↓ • • ◦ • • • + + ↑ ↓ • • • • ◦ ◦ ◦ • ↑ ↓ •←− •←− •←− • ◦ ◦ ◦ • ↓↑ ↑ ↓ •←− •←− •←− •←− • • H` 6.11: Chu tuyˆn th´. nhˆ t cua anh c´ bˆn m´.c x´m. ´ ´ ’’ ´ u a ˙˙ ınh e oo ua IP 1 • −→ • −→ • −→ • −→ • −→ • −→ • −→ • ◦ IP 2 IP 3 ↑ ↓ +−→+ • • ◦ • • • ↓ ↑ ↓↑ ↑ ↓ +←−+ • • ◦ • • • ↓↑ ↑ ↓ ◦ −→ ◦ −→ ◦ • • • • • ↑ ↓ ↑ ↓ •←− •←− •←− • ◦ ←− ◦ ←− ◦ • ↓↑ ↑ ↓ −→ •←− •←− •←− •←− • • ←− IP 4 H` 6.12: Bˆn IP v` c´c chu tuyˆn tu.o.ng u.ng. ´ ´ ınh o aa e ´ v`o hu.´.ng di chuyˆ’n v`o v` ra cua phˆn tu. n`y nhu. trong H` 6.13. Mˆt sˆ phˆn ˙ ` oo` .´a ˙ ’ a ˙a ’ a o eaa ınh tu. d u.o.c viˆng thˇm hai lˆn. Khi d i qua phˆn tu. lˆn th´. hai (d ` u n`y d u.o.c x´c d .nh ´ ` ` a ˙` ˙¯. ’ ’a e a a ¯ u ¯iˆ a ¯ . a ¯i e bˇ ng c´ch kiˆ’m tra dˆ u hiˆu cua n´-nˆu khˆng l` I ngh˜ l` n´ d .o.c viˆng thˇm lˆn ˙ ` ´ ´ ´ a` e ˙ oe ’ a a e a o a ıa a o ¯u . e a . th´. hai) d` u tiˆn ch´ng ta x´c d inh dˆ u hiˆu cua n´ theo H` 6.13, nhu.ng sau d ´ ´ ˙o ’ u ¯ˆ a e u a ¯. a e ınh ¯o . cˆp nhˆt lai theo H`nh 6.14. a a. ı . . Khˆng c´ phˆn tu. n`o d u.o.c viˆng thˇm ho.n hai lˆn, ngoai tr`. phˆn tu. IP luˆn o` ´ ` .u` a ˙ a¯. ’ a˙ ’ o e a a o ´ luˆn c´ dˆ u hiˆu I. o oa e . Chˇng han c´c dˆ u hiˆu d u.o.c g´n khi thu.c hiˆn thuˆt to´n T x´c d .nh chu tuyˆn ˙ ’ ´ ´ a .aa e¯. a e a a a ¯i e . . . . . nhˆ t trˆn H`nh 6.11 nhu. trong H` 6.15. ´e th´ ua ı ınh 184
....................................................................................................................................................................................................................................................................................................................... . . . . . ... . . . . . . . . ... . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . .... . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . ... . . . . . . . . ... . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hu.´.ng ra cua phˆn tu. . . . . . . ` . ˙ ’ a˙ ’ . . o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .............................................................................................................................................................. . . . . . . . . . . . . . . . . . . ... . . . . . . . . . . . . . ... . . . . . . . . . . . . ... . . . . . . . . . . . . ... . . . . . . . . . . . . ... . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ↑ hoˇc −→ a ↓ hoˇc ←− a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..................................................................................................................................................................................................................................................................................................................... . . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . ... . . . .... . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . ... . . . .... . . ... . . . . . . . . ... . . . . . . . ... . . . . . . . . ... . . . .. . . . ... . . . . . . . . ... . . . . . . . ... . . . . . . . . ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hu.´.ng v`o . . . . . . . . . . . . . . . . ↑ hoˇc −→ a o a . . . . . A R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . ... . . . . . . . . . ... . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . .. . . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . ... . . . . . . . . . ........................................................................................................................................................................................................................................... . . . . . . . . . . . . . . . . . cua phˆn tu. . . . . . . . . . . . . . . . ` ˙ ’ a˙ ’ ↓ hoˇc ←− a . . . . . R D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . ... . . . .... . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . ... . . . .... . . ... . . . . . . . . ... . . . . . . . ... . . . . . . . . ... . . . .. . . . ... . . . . . . . . ... . . . . . . . ... . . . . . . . . ... . . . . . . . . ..................................................................................................................................................................................................................................................................................................................... . . H` 6.13: C´c dˆ u hiˆu d ˆi v´.i tˆ t ca c´c kha nˇng c´ thˆ’ c´ cua c´c hu.´.ng di chuyˆ’n ˙ ˙ ´ ´ ´’ e ¯o o a ˙ a ˙a ’ o eo˙ a ’ ınh aa o e . ´ ˙ ’ dˆn v` ra cua mˆt pixel. ¯e a o . ................................................................................................................................................................................................................................................................................................................................... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (D, A) (D, D) (A, A) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dˆ u hiˆu d .o.c g´n . . . . . . . . . . . ´ . . . . a e ¯u . a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (A, D) (R, D) (R, A) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (lˆn d` u, lˆn hai) ` ¯ˆ ` . aaa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (R, R) (D, R) (A, R) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ................................................................................................................................................................................................................................................................................................................................... . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dˆ u hiˆu d .o.c g´n cuˆi c`ng . . . . . . . . . . . . . . . ´ ´ . a e ¯u . a ou . . . . . R D A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ................................................................................................................................................................................................................................................................................................................................... . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . ... . . . . . . . . . ... . . . . . . . . . . . . H` 6.14: C´c ph´p g´n cuˆi c`ng d oi v´.i mˆi cˇp dˆ u hiˆu d .o.c x´c d .nh trˆn lˆn ˜. ´ ´ ´ e` ınh a ea o u ¯ˆ o oa a e ¯u . a ¯i a . . nhˆ t v` th´. hai. ´ duyˆt th´ e uaau . Thuˆt to´n IP a a . Thuˆt to´n IP ´p dung thu tuc t`m kiˆm c´ hˆ thˆng dˆ’ x´c d .nh c´c d iˆ’m kho.i tao. ˙ ˙ ´ o e o ¯e a ¯i .´ ˙. ı ’ ˙. ’ a a a e a ¯e . . . phˆn tu. tai (0, 0) v` tiˆp tuc sang bˆn phai doc theo Viˆc t`m kiˆm n`y xuˆ t ph´t t` ` ´ ´ ´ au a ˙. ’ ˙. ’ eı e a a ae . e . v` cho dˆn hˆt h`ng th´. nhˆ t. Sau d o h`ng th´. hai, th´. ba... d .o.c duyˆt t`. tr´i ´ea ´ ´ a ¯e u a ¯´ a u u ¯u . eua . .o.c x´c d nh v` thuˆt to´n d`.ng. Do sang phai. Kˆt th´c ta c´ tˆ t ca c´c d e’m IP d . a ¯i ˙ ´ ´’ ˙ ’ o a ˙ a ¯iˆ e u ¯u a a au . . . trong mang hai chiˆu d .o.c kiˆ’m tra dˆ’ x´c d nh n´ c´ phai l` phˆn ˙ ˙ a ¯i ˜ ` ` ¯u . ˙a ` a˙ ’ ˙ ’ ’ d ´, mˆi phˆn tu ¯o o e e ¯e oo a . . IP hay khˆng. Khi di chuyˆ’n theo c´c phˆn tu. doc theo mˆi h`ng d e’ t`m c´c IP, ˙ ˙ ˜ ` ˙ ’ a˙. ’ tu o e a oa ¯ˆ ı a ch´ng ta cˆn d` ng th`.i biˆn dich mˆt danh s´ch d iˆ’m so s´nh (CPL-comparision point ˙ ` ¯ˆ u ao oe. o a ¯e a . list). Nguyˆn tˇc xˆy du.ng CPL. Kho.i d` u di chuyˆ’n theo mˆi h`ng, danh s´ch l` rˆng. ˙ ´ ˜ ˜ ˙ ¯ˆ ’a eaa e oa a ao . . bˇt gˇp. Khi di chuyˆ’n doc theo h`ng ch´ng ta kiˆ’m tra dˆ u hiˆu cua mˆi phˆn tu a a ˙. ˙ ˜ a ˙´. ´ ` ˙ ’ ’ e a u e a e o . 185
I R R R R R R • −→ • −→ • −→ • −→ • −→ • −→ • −→ • D ◦ ↑ ↓ A• • ◦ • • •D + + ↑ ↓ • • ◦ • • •D + + A ↑ ↓ • • • • ◦ ◦ ◦ •D A ↑ ↓ R R R •←− •←− •←− • ◦ ◦ ◦ •D A ↓↑ ↑ ↓ •←− •←− •←− •←− • D • R A R R R ı.`a a ´ H` 6.15: V´ du vˆ g´n dˆ u hiˆu. ınh e e . Nˆu dˆ u hiˆu l` A (add) ch´ng ta ch`n gi´ tri cua phˆn tu. n`y (m´.c x´m cua n´) v`o ´´ ` a.˙ ’ a ˙a ’ ˙oa ’ ea ea u e ua . cuˆi danh s´ch; nˆu dˆ u hiˆu l` D (drop) ch´ng ta xo´ phˆn tu. cuˆi c`ng trong danh ´ ´´ a` ´ a ˙ ou ’ o a ea ea u . s´ch; nˆu dˆ u hiˆu l` I hoˇc R (retain) danh s´ch khˆng thay d o’i. ˙ ´´ a ea ea a a o ¯ˆ . . Cuˆi cua mˆi h`ng danh s´ch d e’m so s´nh CPL l` rˆng v` d oi v´.i mˆi h`ng sˆ ˙ ˜ ˜ ˜ ´’ ´ ´ o˙ oa a ¯iˆ a ao ı ¯ˆ o oa o c´c phˆn tu. bi xo´ bˇ ng sˆ c´c phˆn tu. ch`n. a ˙. a` ` ´ ` ’ a˙e ’ a a oa Nguyˆn tˇc IP. Phˆn tu. d u.o.c kiˆ’m tra l` mˆt IP nˆu hai d ` u kiˆn sau d .o.c thoa ˙ ´ ` ´ a ˙¯.’ ˙ ’ ea e ao e ¯iˆ e e ¯u . . . m˜n: a ´ e ˙ oa ’ 1. dˆ u hiˆu cua n´ l` I ; v` a a . 2. gi´ tri x´m cua n´ kh´c gi´ tri cua phˆn tu. cuˆi trong danh s´ch CPL. ` ´ ˙oa ’ a.˙ ’ a˙o ’ a .a a M˜ ho´ a a Thuˆt to´n bˇt d` u t`. phˆn tu. trˆn h`ng v` cˆt d` u tiˆn. Phˆn tu. n`y luˆn luˆn l` ´a a a ¯ˆ u ` ` a˙ea ’ a ˙a ’ a a o ¯ˆ .a e o oa . ´ dung thuˆt to´n T dˆ’ t`m chu tuyˆn d` u tiˆn v` d` ng th`.i ˙ ´a IP, ta n´i IP l` # 1. Ap . o a a a ¯e ı e ¯ˆ e a ¯ˆ o o . cˆp nhˆt c´c dˆ u hiˆu. Sau khi tro. vˆ IP # 1 ch´ng ta goi thu tuc IP dˆ’ t`m IP m´.i. ˙ ´ ˙` ’e ˙. ’ a aaa e u ¯e ı o . . . . .i, g´n #2, ta lai goi thuˆt to´n T d e’ t`m chu tuyˆn th´. hai v` ˙ ´ ´ Khi t` thˆ y IP m´ ım a o a a a ¯ˆ ı e u a .. . d` ng th`.i cˆp nhˆt c´c dˆ u hiˆu. Tiˆp tuc su. dung thuˆt to´n IP d e’ t`m IP #3, v` ˙ ´ ´ e.˙. ’ ¯ˆ o oa aaa e a a ¯ˆ ı a . . . . .c hiˆn t` c´c chu tuyˆn ta d .o.c ´ ´ ˙˙ ’’ vˆn vˆn. Kˆt qua cua viˆc thu aa e e e ım a e ¯u . . . . 1. m´.c x´m cua n´; ˙o ’ ua 186
2. vi tr´ cua phˆn tu. IP; v` ` .ı˙ ’ a˙ ’ a 3. d˜y c´c hu.´.ng di chuyˆ’n. ˙ aa o e Ta c´ thˆ’ m˜ ho´ c´c chu tuyˆn bˇ ng c´ch su. dung m˜ tu. nhiˆn d ˆi v´.i c´c m´.c ˙ ´` ´ ˙. ’ o e a aa ea a a. e ¯o o a u x´m v` vi tr´ cua d iˆ’m kho.i tao, v` m˜ x´ch Freeman d ˆi v´.i c´c hu.´.ng. M˜ x´ n`y ˙ ´ a . ı ˙ ¯e ’ ˙. ’ a a aı ¯o o a o a ıch a . dung t`. m˜: ˙ ’ su . ua  00 d oi v´.i hu.´.ng lˆn,  ´ ¯ˆ o o e     01 d oi v´.i hu.´.ng phai, ´ ˙’ ¯ˆ o o d := 10 d oi v´.i hu.´.ng xuˆng,  ´ ´ ¯ˆ o o o     11 d oi v´.i hu.´.ng tr´i. ´ ¯ˆ o o a Mˆt vˆ n d` quan trong cua ngu.`.i giai m˜ l` l`m sao x´c d .nh d e’m kˆt th´c cua mˆt ˙ .´e ´ ˙ ’ ˙ aaa ’ u˙ ’ o a ¯ˆ o a ¯i ¯iˆ e o . . .´.ng v` mˆt chu tuyˆn m´.i bˇt d` u. Diˆu n`y c´ thˆ’ biˆt du.a trˆn nhˆn x´t o a ¯ˆ - ` ˙´ ´a ´ tˆp c´c hu o aa ao e eaoee. e ae . . . .´.ng) cˆn kˆt th´c tro. lai d e’m d` u tiˆn. Ch´ng ta ˙ ¯ˆ ´’ ´ `e a´ aa ˙a ˙ . ¯iˆ ’ l` tˆ t ca c´c chu tuyˆn (d˜y c´c hu o e aa u a e u .´.ng phai−tr´i v` hiˆu sˆ c´c hu.´.ng lˆn−xuˆng. Khi ˙` .´ .´ ´ ’a ˙ ’ chı cˆn theo d˜i hiˆu sˆ c´c hu o o e oa a a e oa o e o ch´ng d` ng th`.i bˇ ng 0, ngh˜ l` ta tro. vˆ vi tr´ xuˆ t ph´t v` d˜. liˆu kˆ tiˆp tu.o.ng ` ˙`.ı a ´ ´´ ’e u ¯ˆ o oa ıa a a aue ee . .ng v´.i chu tuyˆn m´.i. Phu.o.ng ph´p n`y thu.c hiˆn ch´ x´c d oi v´.i tˆ t ca c´c chu ´ ´ ´’ ınh a ¯ˆ o a ˙ a u ´ o e o aa e . . tuyˆn c´ d ˆ d`i l´.n ho.n hoˇc bˇ ng 2. V´.i chu tuyˆn d ˆ d`i 1 (c´c d e’m cˆ lˆp) ch´ng ˙ oa a` ´ ´. e o ¯o a o .a o e ¯o a a ¯iˆ u . . . dung cˇp nhi phˆn 11; d ay l` mˆt hu.´.ng d` u tiˆn khˆng thˆ’ c´ v` pixel khˆng ˙ ˙ ’ ta su . a .a ¯ˆ a o o ¯ˆ a e o eoı o . . l` IP nˆu n´ c´ c`ng m´.c x´m v´.i pixel bˆn tr´i cua n´. ´ a˙o’ a e oou ua o e Nhˆn x´t 6.4.1 (i) Do d˜y c´c m´.c x´m liˆn tiˆp thu.`.ng c´ liˆn hˆ mˆt thiˆt, entropy ´ ´ a e aaua ee o oe e a e .. . .c x´m thu.`.ng ´t y ngh˜a ho.n entropy c´c m´.c x´m; v` v` vˆy c´ .´ ˙’ cua hiˆu sˆ c´c m´ a e oa u o ı´ ı a ua aıa o . . dung m˜ ho´ sai phˆn (sau d ´ l` Huﬀman) dˆ’ m˜ ho´ c´c m´.c x´m. Tu.o.ng thˆ’ su . ˙’ ˙ e˙ aa a ¯o a ¯e a a a ua . d ˆi v´.i c´c h`ng v` c´c cˆt cua nh˜.ng d e’m kho.i tao c´c chu tuyˆn. ˙ .´ ´ aa o ˙ .’ ˙.a ’ tu ¯o o a a u ¯iˆ e (ii) Nhu. d u.o.c d` cˆp o. trˆn, phu.o.ng ph´p m˜ ho´ c´c hu.´.ng su. dung m˜ x´ch Freeman. ¯ . ¯ˆ a ˙ e e. ’ ˙. ’ a a aa o aı (iii) Sˆ c´c bit d `i hoi d e’ m˜ ho´ mˆt anh khˆng chı phu thuˆc v`o tˆp c´c m˜ d .o.c ’˙ ´ ¯o ˙ ¯ˆ a a o ˙ .’ ˙ ’. oa o oaaa a ¯u . . . . dung m` c`n phu thuˆc v`o sˆ c´c chu tuyˆn, t´.c l` phu thuˆc v`o sˆ lu.o.ng c´c ´ ´ua ´ ˙ ’ su . ao o a oa e oao. a . . . . .c x´m trong anh. N´i c´ch kh´c, phu.o.ng ph´p khˆng hiˆu qua ´ ´ ˙ ’ ˙ ’ chi tiˆt v` sˆ c´c m´ a e aoa u oa a a o e . d ˆi v´.i c´c anh c´ sˆ lu.o.ng l´.n c´c chu tuyˆn nho. ´ ´ ´ ¯o o a ˙ ’ ˙ ’ oo . oa e ˙ ’ Giai m˜ a Viˆc xˆy du.ng lai anh t`. m˜ chu tuyˆn cua n´ l` dˆ d`ng. Thuˆt to´n giai m˜ xˆy ´ ˙ oa ˜ a .˙ ’ ’ ˙ ’ ea ua e e a a aa . . . .ng lai mˆi phˆn tu. trong mang d˜. liˆu bˇt d` u t`. phˆn tu. trˆn h`ng v` cˆt d` u ˜ ´a ` u e a ¯ˆ u ` a˙ ’ ˙ ’ a˙ea ’ du o a o ¯ˆ .a . . . 187
tiˆn. V` phˆn tu. n`y l` IP # 1 nˆn gi´ tri x´m cua n´ l` x´c d .nh. Ho.n n˜.a, c´c phˆn ı` ` a ˙aa ’ ˙ o a a ¯i ’ e e a .a u a a . trong mang d˜. liˆu tu.o.ng u.ng v´.i chu tuyˆn #1 c´ thˆ’ xˆy du.ng lai c`ng v´.i c´c ˙ ´ ˙ ’ ˙ ’ tu ue ´ o e o ea .u oa . . . dung hˆ thˆng xuˆ t v` nguyˆn tˇc IA. Sau khi xˆy du.ng lai chu ´ ´ .´ ´ ˙ o˙ ’ ’ dˆ u hiˆu cua n´ su . a e eo aa ea a . . . . vˆ d iˆ’m IP # 1, ch´ng ta di chuyˆ’n t`.ng pixel doc theo h`ng dˆu ˙e ˙ ˙u ´n n`y v` tro ` ¯ e ` ’ tuyˆ a a e u e a a . . hai... e`a tiˆn, rˆi h`ng th´ o u Khi di chuyˆ’n doc theo mˆi h`ng, ch´ng ta c˜ng biˆn dich danh s´ch CPL theo ˙. ˜ e oa u u e. a . bˇt gˇp hoˇc l` IP tu.o.ng u.ng phˆn tu. trˆn mˆt chu ´ ˜ a ˙´. ` ` ’ a˙e ’ nguyˆn tˇc CPL. Mˆi phˆn tu a a ea o aa ´ o . . .c su. d u.o.c xˆy du.ng tru.´.c d o, hoˇc l` mˆt phˆn tu. khˆng thuˆc chu ´n d ˜ thu . ¯ . ` ˙ ’ tuyˆ ¯a e a o ¯´ aao a o o . . . . . ´ tuyˆn. e Nguyˆn tˇc xˆy du.ng lai l`: ´ eaa .a . 1. Nˆu phˆn tu. l` IP, xˆy du.ng chu tuyˆn v` d at c´c dˆ u hiˆu. ´ ` ´ ´ a ˙a ’ e a e a ¯ˇ a a e . . . 2. Nˆu dˆ u hiˆu khˆng l` I, n´ d a thu.c su. d u.o.c xˆy du.ng lai. Do d ´ chuyˆ’n d e n ˙´ ´´ ea e o a o ¯˜ . . ¯ . a ¯o e ¯ˆ . . . phˆn tu. kˆ tiˆp. ` ’´´ a ˙ee 3. Nˆu phˆn tu. khˆng l` IP v` dˆ u hiˆu cua n´ l` I, gi´ tri cua n´ l` phˆn tu. cuˆi ´ ` ´ a . ˙ oa ` ´ a˙ ’ e ˙ oa ’ ’ a˙o ’ e o a aa . trong danh s´ch CPL. a ˙ ’ 6.5 N´n khˆng bao to`n thˆng tin e o a o Kh´c v´.i c´c phu.o.ng ph´p n´n bao to`n thˆng tin d` cˆp phˆn tru.´.c, n´n mˆ t m´t ` ´a ˙ ’ aoa ae a o ¯ˆ a e. a o e a .a trˆn thoa hiˆp: giam t´nh ch´nh x´c trong anh d u.o.c xˆy du.ng lai d e’ ˙ ˙e ’. ˙ ’ ˙ ’ thˆng tin du o e ı ı a ¯. a . ¯ˆ . . tˇng tı lˆ n´n. Nˆu cho ph´p mˆ t thˆng tin (m` c´ thˆ’ hoˇc khˆng anh hu.o.ng d e n ˙. ´ ´ ´ ˙e e ’. ˙ ’ ˙ ’ a e e a o ao e a o ¯ˆ ´ ` ˙ e e a o´ ’. qu´ tr`nh quan s´t) th` viˆc tˇng tı lˆ n´n rˆ t c´ y ngh˜ Thˆt vˆy, nhiˆu k˜ thuˆt aı a ıea ıa. aa ey a . .. . .n sˇc t`. d˜. liˆu d .o.c n´n v´.i ´ ´ . `.a˙ ˙a ’ ’ n´n mˆ t thˆng tin c´ kha nˇng phuc hˆi lai c´c anh d e a o o o ¯o a u u e ¯u . e o . tı lˆ 30 : 1 v` c´c anh n`y kh´ c´ thˆ’ phˆn biˆt bˇ ng mˇt v´.i nh˜.ng anh d .o.c n´n ˙ e` ´ ˙e ’. aa˙ ’ ˙ ’ a oo e a a ao u ¯u . e . v´.i tı lˆ t`. 10 : 1 dˆn 20 : 1. Cˆn d e’ y rˇ ng, tı lˆ n´n bao to`n thˆng tin d ˆi v´.i c´c ˙ ` ¯ˆ ´ ` ´ ´ o ˙eu ’. ˙e e ’. ˙ ’ ¯e a a a o ¯o o a .n sˇc hiˆm khi d at d u.o.c kˆt qua 3 : 1. Nhu. d ˜ tr`nh b`y, kh´c nhau co. ban ´ ´ ´ ˙ ’ ˙ ’ ˙ ’ anh d ¯o a e ¯. ¯ . e ¯a ı a a gi˜.a hai c´ch tiˆp cˆn n`y l` c´ hay khˆng c´ khˆi lu.o.ng tu. ho´ trong H` 6.3. ´. ´ ˙ ’a u a e a a ao o oo ınh . Trong nhiˆu u.ng dung, anh xˆy du.ng lai c´ thˆ’ sai kh´c v´.i anh ban d` u nhu.ng ˙ `´ ˙ ’ a o˙ ’ e a .oe ¯ˆ a . . chˆ p nhˆn d .o.c. Phˆn n`y tr`nh b`y mˆt v`i phu.o.ng ph´p m˜ ho´ mˆ t m´t thˆng ´ ` ´ a a ¯u . aa ı a oa a aaa a o . . tin. 188