Xử lý ảnh số - Biểu diễn và miêu tả part 9

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

Thêm vào BST

Báo xấu

86
lượt xem 20
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ố - biểu diễn và miêu tả part 9', văn hoá - nghệ thuật, điêu khắc - hội họa 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ố - Biểu diễn và miêu tả part 9

Phu.o.ng tr`nh Ph´p to´n e a ı Ch´ th´ u ıch ´ ´ e˙ ’ ˙ ’ ˙ ’ Ph´p tıa X4 l` kˆt qua khi tıa A. Sˆ ae o X1 = A ⊗ {B } lˆn thu.c hiˆn trong phu.o.ng ` a e . . X2 = ∪8=1 (X1 Bk) k ınh d e’ c´ X1 th´. nhˆ t ˙ ´ tr` ¯ˆ o u a X3 = (X2 ⊕ H ) ∩ A cˆn cho tru.´.c. C´c phˆn tu. ` ` a˙ ’ a o a X4 = X1 ∪ X3 cˆ u tr´c (V) d u.o.c su. dung ´ ¯. ˙ . ’ a u trong hai phu.o.ng tr`nh d` u ı ¯ˆ a .o.ng tr`nh th´. ba tiˆn. Phu e ı u su. dung phˆn tu. cˆ u tr´c ` ’´ ˙. ’ ˙a a u (I). Bang 8.2: Bang tˆ’ng kˆt c´c kˆt qua, t´ chˆ t cua c´c ph´p to´n h` th´i hoc. ˙ ´ ´ ´’ ˙ ’ ˙ ’ ˙ ınh a ˙ a ’ o eae e a ınh a . Mo. rˆng d ˆi v´.i c´c a nh gi´ tri x´m ´ ˙o ’. ¯o o a ˙ ’ 8.4.5 a.a Trong phˆn n`y ch´ng ta mo. rˆng c´c ph´p to´n d˜n, ph´p co, ph´p mo. v` ph´p d ´ng `a ˙o ’. ˙ a e ¯o ’ a u a e aa e e .a trˆn co. so. d o, ch´ng ta tr` b`y c´c thuˆt to´n h`nh a˙ ’ ˙ ¯´ ’ cho c´c anh gi´ tri x´m. Du a .a e u ınh a a a aı . . th´i hoc cho c´c anh gi´ tri x´m. Nhu. trong Phˆn 8.4.4, du.a v`o h`nh th´i hoc anh ` a˙ ’ a.˙ ’ a. a .a a aı . .ng cua c´c th`nh phˆn x´m ch´ng ta s˜ tˆp trung v`o viˆc biˆ’u diˆn v` tr´ch d ac tru ˙ ˜ a ı ¯ˇ ` ˙a ’ a u ea a e e e a a . . . -a ˙ ’ quan tˆm trong anh. Dˇc biˆt ch´ng ta s˜ tr`nh b`y c´c thuˆt to´n t´ch biˆn thˆng a e u eı aa a aa e o . . . . h`nh th´i hoc gradient, v` phˆn hoach v`ng du.a v`o kˆt cˆ u (texture) ´´ a˙ ’ qua to´n tu ı a. aa u aea . . cua d oi tu.o.ng. Ch´ng ta c˜ng d` cˆp d e n c´c thuˆt to´n d e’ l`m tro.n v` nˆng cao ˙ ´ ´ ˙ ¯ˆ ’ u u ¯ˆ a ¯ˆ a e. a a ¯ˆ a aa . . .o.ng anh. ´ ˙ ’ chˆ t lu . a Gia su. f (x, y ) l` anh v`o v` b(x, y ) l` phˆn tu. cˆ u tr´c (xem nhu. mˆt anh con). a` ’´ ˙˙ ’’ a˙’ a ˙a o˙ .’ aa u . c´c h`m n`y r`.i rac theo ngh˜ d .o.c d` cˆp trong Phˆn 2.2.1. T´.c l` nˆu k´ ` ´ ˙˙ ’’ Gia su a a ao. ıa ¯u . ¯ˆ a e. a u ae y hiˆu Z l` tˆp c´c sˆ nguyˆn th` v´.i mˆi toa d o (x, y ) ∈ Z × Z ta g´n c´c m´.c x´m ˜ ´ e aa a o e ıo o . ¯ˆ aa ua . . . .c trong R. f (x, y ) v` b(x, y ) l` c´c gi´ tri thu a aa a.. 271
.................................................... ........................................................... . . . . .. . . . . ... . . . . . . . .. . .................................................... . ... . . . . . . .................. . . ... . . . . . .. ... . . . .. . .............. ..................... ...... ..................... . ................................................................ . ..................... . . . . . . . .. . . . . . . ................................................................ ..................... .. .... ... ... ... .... ... ... .... ... . . .. .... ... . . . . . ................................................................ .... .... ....... . . . . ................................................................ . . . ..................... . . . ... ... ..... ... ... .... ... ... ... .. . ..................... . . . . . ................................................................ ..................... ................................................................ . . . . ................................................................ . . . . . .. ............... .. . . .. ............. .... .............................. . . . ........... ...................................... .. ..... ........................................... .... ........ .... ..... ........ ..... ......... . .. . . .. . . . .. . . .. . .. . . .. . . . . . . . . . .. .... .... .. . . . . . . . . . ... ... .... ... ... ... .. .. ... ... ... . ................................................................ ............................................................... ................................................................ .... .... ... ... .... ... ... .... ... .. . . . ... ... ..... ... ... .... ... ... ... .. . ... ... .... ... ... ... .. .. ... ... ... . ................................................................ ............................................................... . . .. .... ... ... ... .... ... ... .... ... . .... .... ... ... .... ... ... .... ... .. . . . . . . . ................................................................ ............................................................... . . ................................................................ ............................................................... . . . . . . ... ... .... ... ... .... ... ... ... .. . ... ... .... ... ... ... .. .. ... ... ... . ................................................................ ............................................................... . . . . . . . ................................................................ ............................................................... ............. ......... ...... ......... ...... ...... .... ................... ............. ....... . . . ... . . . .. . ... ... .... .. ... . . . .. .. .. ........ ... .. .. ..... ... .. .. ..... .... B B . . . . . . . .. . . . .. . .. . . . .. . .. . . ................................................................ . . . ........... ...................................... .. . ... . ... . . . . . . ................................................................ ............. ......... ...... ......... ...... ...... ..................... . . ... ... .... ... ... .... ... ... ... .. . . . . . . ..................... . . . ..................... . . ................................................................ . . . ................................................................ . ..................... . . .. .... ... ... ... .... ... ... .... ... . . . ..................... . . ... ... .... ... ... .... ... ... ... .. . . . . ................................................................ . ..................... . .. .... ... ... ... .... ... ... .... ... . . . . ..................... . . . . . ................................................................ . .. . . . . .. . . . . . . . . . .. . ..................... . . . ................................................................ . ... . . . . . . ................ . . ... . . . . ..................................................... .. .. ............ .. ........ ...... ........ .... . . . . . . . . . .. . . . . . .. . . . . .. . . . . .. .. I II .................................................... ....................... . . . . . .... . . . . . . . .. ..................... . . . . . .. . . .................................................... . ... . . . . . . . ... . . . . .. . . ... . . . . . . . . .............. . . . . . . . . . . . . .. ........ ... . . . . . . . . . . . . . . . ... ... .... . . . . . . ...................... . × × . . . . . . . . . . . . . ...................... ...................... . . . . . . . . . . . . . . . . ...................... . . . . . . ...................... . . . . . . . ....... ......................................... . ................................................... . . ...................... . .. .... ... ... . . . . . . ... . . . . . . . ... . . . . . . . . ... . . . . . . .......... .... . ... . . . .. . . ... ... .... .. . . ... .. .. ....... . . . . . . . . . . ...................... . . ..................... . . . . . ...................... . ..................... . . . . . . . . . ... ... .... ...................... . ..................... . . . . . . . ..................... × × × . . . . . . ...................... ...................... . . . . ..................... . . . . .. .... ... ... . ..................... . . . . . . . . ...................... ..................... . . . . . . . . ...................... . .................... ...................... .................................................. . . . .. . . B i, i = 1, 2, 3, 4 B i , i = 1, 2, . . . , 8 ..................................................... . . . . . . . . . . . . . .. ............................................................... . ... . . .. . . ....................... . . . . . .... . .. . . . . . . . .. . . .. . . . .. . . ............. .... . . ..... ... ...... ........................... .... . . . . .............................................................. . . . ... .... ..... . .... ........................ .. .. .... ........ .... .... .... ....... ... ... .... ... .. .. .... ... ... . . . ...................... . . . . . . . . . . .. . . . . . . × × . . ... ... .... ...................... ............................................................... . . . . ... ... ... .... ... ... .. .. ... ... ... . . . . ...................... ............................................................... .... .... .... .. .... ... ... .... ... .. ...................... . . .............................................................. . . .. .... ... ... (quay 900 ) (quay 450 ) . . . . . . . ... ... ... .... ... ... .. .. ... ... ... . . . . . . . . . . . . ... ... .... ...................... ............................................................... . . . . ......... . .... . . . . . . .... . . . . . . . .. . . . . . . . .. . . . . . . .. .. .. .. . .. . ..... ... . ...... . ... . ...... . .... ...... . ..................................................... ..................................................... . .. . . . . . . . . . . III IV .................................................... . . . . . . ... . . . . . . . .... . . . . . . . .. . . . . .................................................... ................. .. ... . . . . .. . . ... . . . . . .. .. . . . . . . . . ..................... . . . . .... .... ...... .... .... .... . . . . . . . . . . . . . . . . . . . . . . . . . . ..................... . . . . . ... ... ... . . . × . . . . . . . . . . . ..................... . . . . ..................... . . . . . . . . . . . . . .... .... .... . . . . . . . . ..................... . ... ... ... . . . . ..................... . . . . . . ... ..... ........................................ . . . . . . . . .. . . . . . .. . . .. ..... ....... . . ... . . . . . . . .................................................. . ............ .... ... ...... .... . . . . . . . .. . . .... . ..... ...... . .......... . ... .. . . ....... ....... .. . . . . . ........................................... . . . . .. ..... ..... . .. ....... ....... ... .... .... . . . ..................... . . . ... ... .... ... ... ... . . . .. .... ... ... ... .... .... . . . . . ..................... . . ... ... .... ... ... ... . . . ..................... . ........................................... . . . . . . . . . . . ..................... . . . ........................................... ..................... . . . ........................................... . .. .... ... ... ... .... .... . ........................................... . . . . ..................... . . . ..................... . . . . ... .... . ... . . . . . . . . .. . . .. .. . . B i, i = 1, 2, 3, 4 B i, i = 5, 6, 7, 8 .................................................... .................. . . ... . . . . ........................................... . . . . . . . . . .. . . ....................................................... . . . . . . ... . . . . . . . .... . .. . . .. .. . . ... . . . . . . .. .. .. . . .. . . ... .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . × . . . . . . . . . . . . . . . . . . (quay 900 ) (quay 900 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ................................... . . . . . . . . .. ................................... . . . ... . . . . . ... . . . . . . . . . . . . ... . ................... . . . . . .... . ................... ... . . . . .. . . . . . . . . . ←−−−−−− V −−−−−−− −−−−−−− −−−−−−→ H` 8.17: Nˇm cˆ u tr´c co. ban thu.`.ng d u.o.c su. dung trong phˆn n`y. Tˆm cua c´c ´ ` ˙ ’ ¯. ˙ .’ ˙a ’ ınh a a u o aa a phˆn tu. cˆ u tr´c d .o.c d ˇt tai vi tr´ trung tˆm v` dˆ u × chı ra c´c gi´ tri “khˆng ` ’´ ´ a ˙a ˙ ’ u ¯u . ¯a . . ı a aa a a. o . quan tˆm”. a Ph´p d˜n e a Ph´p d˜n anh gi´ tri x´m f bo.i phˆn tu. cˆ u tr´c b x´c d .nh bo.i ` ’´ e a˙ ’ ˙ ’ a ˙a ˙ ’ a .a u a ¯i (f ⊕ b)(s, t) := max{f (s − x, t − y ) + b(x, y ) | (s − x, t − y ) ∈ Df , (x, y ) ∈ Db }, (8.15) trong d ´ Df , Db l` c´c miˆn x´c d inh cua f v` b tu.o.ng u.ng. Nhu. trˆn, b l` phˆn tu. ` a` ˙ ’ a˙ ’ ¯o aa e a ¯. a ´ e . l´ h` th´i hoc nhu.ng ch´ y rˇ ng trong tru.`.ng ho.p n`y b l` mˆt ` ´ ˙ ’ cˆ u tr´c trong xu y ınh a . a u u´ a o a ao . . .p. a˙ ’ h`m anh thay v` mˆt tˆp ho ıoa .. . Diˆu kiˆn (s − x, t − y ) ch´.a trong miˆn x´c d inh cua f tu.o.ng tu. v´.i d ` u kiˆn -` ` ˙ ’ e e u e a ¯. . o ¯iˆ e e . . .i anh nhi phˆn, trong d ´ hai tˆp cˆn ch´.a ´t ´ a` trong d inh ngh˜ cua ph´p d˜n d oi v´ ˙ ıa ˙ ’ e a ¯ˆ o ’ ¯. .a ¯o .a uı . chung. Ch´ y rˇ ng Phu.o.ng tr`nh (8.15) c´ dang cˆng th´.c t´ ` ´ ` ˙ ’ nhˆ t mˆt phˆn tu a o a u´ a ı o. o u ıch . . max thay cho ph´p to´n cˆng v` ph´p cˆng thay cho ph´p nhˆn trong a˙ ’ chˆp: to´n tu a e ao aeo e a . . . .c t´ch chˆp. cˆng th´ ı o u a . 272
Dˆ’ d o.n gian ch´ng ta s˜ minh hoa kh´i niˆm v` co. chˆ thu.c hiˆn cua ph´p to´n -e ¯ ˙ ´ ˙ ’ e˙ ’ u e ae a e. e a . . . .`.ng ho.p mˆt chiˆu. Trong tru.`.ng ho.p n`y, Phu.o.ng tr`nh (8.15) c´ dang ` trong tru o o e o a ı o. . . . (f ⊕ b)(s) := max{f (s − x) + b(x) | s − x ∈ Df , x ∈ Db }. Ch´ y rˇ ng d` thi h`m f (−x) d ˆi x´.ng v´.i f (x) qua truc y. Tu.o.ng tu. trong tru.`.ng ` ´ u´ a ¯ˆ . a o ¯o u o o . . ho.p t´ chˆp, h`m f (s − x) di chuyˆ’n sang phai khi s du.o.ng v` sang tr´i khi s ˆm. ˙ ˙ ’ . ıch a a e a a a . .o.ng u.ng chı ra rˇ ng ` C´c d ` u kiˆn (s − x) v` x thuˆc miˆn x´c d .nh cua f v` cua b tu ` a ¯i ˙ ’ a˙ ’ ˙ ’ a ¯iˆ e e a o e ´ a . . f v` b phu mˆt phˆn lˆn nhau. C´c d ` u kiˆn n`y tu.o.ng tu. nh˜.ng yˆu cˆu trong d .nh `e e` ˙o ’. a a a ¯iˆ e ea u a ¯i . . .a ´t nhˆ t mˆt phˆn tu. chung. Cuˆi a` ´o ` ´ ıa e a ˙ ˙ ’’ a˙ ’ ngh˜ ph´p d˜n cua anh nhi phˆn: hai tˆp cˆn ch´ ı .a .a u a o . c`ng, kh´c v´.i tru.`.ng ho.p anh nhi phˆn, f d u.o.c dich chuyˆ’n thay v` b. Bˇ ng c´ch ˙ ` .˙’ u ao o .a ¯. e ı a a . .o.ng tr` (8.15) c´ thˆ’ viˆt lai trong d o b dich chuyˆ’n thay v` f. Tuy d ˆ’i biˆn, Phu ˙e ˙´ ˙ ´ ¯o ınh oee. ¯´ e ı . nhiˆn, nˆu Db nho ho.n Df (mˆt d iˆu kiˆn thu.`.ng xay ra trong thu.c tˆ) th` dang d a ´ o ¯` ´ ˙ ’ ˙ ’ e e e e o .e ı. ¯˜ . . .o.ng tr`nh (8.15) s˜ d .n gian ho.n trong viˆc d anh chı sˆ. Vˆ quan niˆm ˙o ` ’´ e ˙ ’ cho trong Phu ı e ¯o e ¯´ e . . .o.t qua f khˆng kh´c v´.i viˆc f tru.o.t qua b. th` viˆc b tru . ıe o aoe . . . Ph´p d˜n c´ t´ giao ho´n. Do d ´ thay v` t´ b ⊕ f ta c´ thˆ’ t´nh f ⊕ b. Tuy ˙ e a o ınh a ¯o ı ınh o eı ` e` ı.` nhiˆn cˆn ch´ y rˇ ng ph´p co khˆng c´ t´nh giao ho´n. H` 8.18 cho v´ du vˆ ph´p a u´ a e o oı a ınh ee d˜n. a Do ph´p d˜n chon gi´ tri l´.n nhˆ t cua f + b trong lˆn cˆn x´c d .nh bo.i h` ´’ a˙ ˙ ınh ’ ea a .o a a a ¯i . . . cˆ u tr´c nˆn anh hu.o.ng chung cua ph´p to´n n`y trˆn anh gi´ tri ` a ˙´ ˙ ’ ’ u e˙ ’ ˙ ’ ˙ ’ e˙ ’ dang cua phˆn tu a e aa a. . . cˆ u tr´c du.o.ng th` anh ra s˜ s´ng ho.n ´´’ ` a ˙´ e a ˙a a.˙ ’ ’ ı˙’ x´m l`: (1) nˆu tˆ t ca c´c gi´ tri cua phˆn tu a aa u ea . bo phu thuˆc v`o c´c gi´ tri v` ´´ anh v`o; v` (2) c´c chi tiˆt tˆi s˜ giam hoˇc bi khu ˙ ˙ ’ eoe˙ ’ ˙’ ’ a a a a. oaa a.a . . . .i phˆn tu. cˆ u tr´c d u.o.c su. dung trong ph´p d˜n. ´ ` ’´ ˙ ’ a ˙a u¯. ˙ . ’ h`nh dang cua ch´ng d ˆi v´ ı u ¯o o ea . Ph´p co e Ph´p co anh gi´ tri x´m f bo.i phˆn tu. cˆ u tr´c b x´c d .nh bo.i ` ’´ ˙ ’ ˙ ’ a ˙a ˙ ’ e a.a u a ¯i (f b)(s, t) := min{f (s + x, t + y ) − b(x, y ) | (s + x, t + y ) ∈ Df , (x, y ) ∈ Db }, (8.16) trong d ´ Df , Db l` c´c miˆn x´c d .nh cua f v` b tu.o.ng u.ng. Diˆu kiˆn (s + x, t + y ) -` ` ˙ ’ ¯o aa e a ¯i a ´ e e . .a trong miˆn x´c d nh cua f tu.o.ng tu. v´.i d ` u kiˆn trong d nh ngh˜ cua ph´p ` ˙ ’ ıa ˙’ ch´ u e a ¯i o ¯iˆe e ¯i e . . . . co d ˆi v´.i anh nhi phˆn, trong d ´ phˆn tu. cˆ u tr´c cˆn ch´.a trong tˆp cˆn d .o.c co. ´ ¯o ` ’´ u` a ` ¯u . ¯o o ˙ ’ a ˙a .a a u .a .o.ng tr` (8.16) c´ dang cˆng th´.c tu.o.ng quan: to´n tu. min thay cho u´ ` a˙ ’ Ch´ y rˇ ng Phu a ınh o. o u ph´p to´n cˆng v` ph´p tr`. thay cho ph´p nhˆn trong cˆng th´.c tu.o.ng quan. e ao ae u e a o u . Ch´ng ta minh hoa co. chˆ hoat d ˆng cua ph´p co (Phu.o.ng tr`nh (8.16)) trong ´ ˙ ’ u e . ¯o e ı . . 273
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . f . . . . . . . . . . .. . .. . . . .. .. . . .. .. . . . .. . .. . . . .. . .. . . . . . . .. .. . . . .. . .. . . . . . . . . . . . . . . . .. . . . . . . . .. . . . .. . . . . . . . . . .. . . . . . . .. .. . . . . . . . . b .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. .. . . . . . . . . . . ... . . . . . . ....... . . . . . .... . . .. . . ... . ..... . . . . . . . . . . . .. . . .. . . .. .. .. . . . . . . . . .. . .. . . .. . . . . . . . . . . .. . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . ..... . . . . . . . . . ... . . . . . . . . ...... . . . . . ... . . x x . . . . . . . ... . . . . . . . .. . . . . .. ... . . . . . . . . . . . . . . . . ... . . .............................................................................................................................. .............................................................................................. . .. . . . (a) (b) f (s ) + b(s − x) . . . . 2 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . f (s ) + b(s − x) . . . . . . . . . 1 1 ... . . .. . . . . . . .. . . . . . . . . . . . . . . . ............ .... ...... . . . . . . .. . . . .. .. . .. . . .. . . . . ....... .. ..... . . .. . . .. ... ... ... ... . . . . . .. . . .. . . . ... . . .. . . . . .. . . . .. . . . .. . . . .. . . . . . . ... . .... ..... .... ...... .... ..... .... ..... .... ..... .... .. f (s2 ) . . . . . . . . .. .. .. . . . . . . .. . .. . . .. . .. .. . .. .. . . . .. . .... ... . . . . . . . ... . . . . ... .. .. . .. .. .. .. ... . .. . . . .. . .. .. .. . .. . . . . . .. . .. . . . . . . . .. . . .. . .. . . . . . .. . . . ... . .. . .. . . .. . ........... . . . . . . . . .. . .. . .. . . .. . . .. . .. . . .. .... ...... . . . ... . .. .. .. .. . .. . .. . .. .. . . .. .. . .. .. .. .. . . .. .. .. . . .. .. .. . . .. . .. .. . . . . . .. . .. ... . . . . . . . .. . .. . . ... . . . .. .. . .. . .. . . . .. . ... .. ... . . . .. . . . .. ... . . .. . ..... .... ..... ...... . f (s1 ) f ⊕b . .. . .. .. . . . . .. . .. . . .. . . . . . .. .. .. ... . . . . . . .. .. .. .. . .. . . . . . . . .. . .. .. .. . .. . . . . ... . . . . .. .. . . . .. . .. .. .. . . . .. . .. . .. . . . .. . . . .. . . . .. . . . . . . . .. . . . . . . ... . . . . .. .. . . .. .. . . .. . . ... . . .. . . ... . . .. . .. . . .. . . . . .. . . . . . . .. . . .. . . . . .. . . .. . . .. .. . . .. . .. . . .. . .. .. . . . . .. . . .. . . . . .. . . .. . . . . .. . . . . . . .. . . . ... . . . . ... . . ... . .. . . . .. .... . . . . . . . ..... . . . .. . . . . .. .. . . . .. . . . .... .. . . . . .. .... . . . . . . ... ... . . . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . . . . . . . ... . . ... .. . . .. . . . . . . . . ................................................................................................................................ . . .......................................................................................................................... s s . . . . . . .. .. . . . .. s1 s2 (c) (d) H` 8.18: Ph´p d˜n nhˆn d .o.c bˇ ng c´ch tru.o.t b qua f. a ¯u . ` ınh ea a a . . 274
. . . . . . . . . . . . . . . . . . . . f b . . . . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . . . . .. . . . . .. .. . . .. . . . . . . . .. . .. . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . .. . .. .. . . . . . .. . . . . . .. . . . .. .. . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .. .. .. . . .. . .. .. . . . . . .. . . . . .. .. . . .. . . . . . . . .. . . . . . . . . . .. ... . . . ..... . ... . . . . ... . . . ... ... . . . . ... ... . . . . . . ... . ... . ... . . . . . . ... . . . . . . . . . . . . ...................................................................................................................................................... . . . .. . .. .. . . . .. . . .. . . . . . .. .. .. . ... .... . ... ..... . . . .... ... . . . . . . . . . . . . . . . . . . . . . . H` 8.19: Ph´p co cua h`m d u.o.c cho trong H` 8.18(a) bo.i phˆn tu. cˆ u tr´c trong ` ’´ ˙ a ¯. ’ ˙ ’ a ˙a ınh e ınh u H` 8.18(b). ınh tru.`.ng ho.p mˆt chiˆu. Khi d ´ biˆ’u th´.c cua ph´p co c´ dang ˙ ` u˙ ’ o o e ¯o e e o. . . (f b)(s) := min{f (s + x) − b(x) | s + x ∈ Df , x ∈ Db }. Tu.o.ng tu. trong ph´p t´nh tu.o.ng quan, h`m f (s + x) di chuyˆ’n sang tr´i khi s du.o.ng ˙ eı a e a . -` ` ` ˙ ’ ˙’ v` sang phai khi s ˆm. Diˆu kiˆn (s + x) ∈ Df v` x ∈ Db chı ra rˇ ng v`ng b nˇ m a a e e a a u a . ho`n to`n trong v`ng f dich chuyˆ’n. Nhu. d a n´i trˆn, c´c d ` u kiˆn n`y tu.o.ng tu. ˙ a a u e ¯˜ o e a ¯iˆe ea . . . . trong tru.`.ng ho.p t´c d ˆng trˆn anh nhi phˆn: phˆn tu. cˆ u tr´c cˆn ch´.a ho`n ` ’´ u` e˙ ’ a ˙a nhu o . a ¯o .a a u a . .o.c co. to`n trong tˆp d . a a ¯u . Cuˆi c`ng, kh´c v´.i d .nh ngh˜a ph´p co trˆn anh nhi phˆn, f d u.o.c dich chuyˆ’n ˙ ´ e˙ ’ ou a o ¯i ı e .a ¯. . e thay v` b. Phu.o.ng tr`nh (8.16) c´ thˆ’ viˆt lai dang b d u.o.c dich chuyˆ’n nhu.ng khi d o ˙´ ˙ ı ı oee.. ¯. . e ¯´ viˆc d ´nh chı sˆ s˜ ph´.c tap ho.n. Do viˆc tru.o.t f qua b c˜ng giˆng nhu. tru.o.t b qua f ’´ ´ ˙oe u . e ¯a e u o . . . . .o.ng tu. nhu. ph´p d˜n o. phˆn trˆn, ch´ng ta s˜ su. dung dang cua Phu.o.ng tr` e a˙ `’ e˙ . ’ ˙ ’ nˆn tu e a e u ınh . . ` ´ ` ˙˙ ’’ (8.16). H` 8.19 minh hoa kˆt qua cua ph´p co h`m f trong H` 8.18(a) bˇ ng phˆn ınh .e e a ınh a a . cˆ u tr´c trong H` 8.18(b). ˙´ ’ tu a u ınh T`. Phu.o.ng tr` (8.16) ta suy ra ph´p co chon gi´ tri nho nhˆ t (f − b) trong lˆn ´ a. ˙ a ’ u ınh e a . .i h` dang cua phˆn tu. cˆ u tr´c. Anh hu.o.ng chung cua ph´p to´n ˙ ’ ` ’´ ˙ ’ ˙’ a ˙a ˙ ’ ˙ ’ cˆn x´c d inh bo ınh . a a ¯. u e a . n`y trˆn anh gi´ tri x´m l`: (1) nˆu tˆ t ca c´c gi´ tri cua phˆn tu. cˆ u tr´c du.o.ng ´´’ ` ’´ e˙ ’ e a ˙a a.˙ ’ a ˙a a a .a a u .n anh v`o; v` (2) c´c chi tiˆt s´ng trong anh v`o nho ho.n “v`ng” ´ ´ th` anh ra s˜ tˆi ho ˙ ı˙’ ’ ˙ ’ ˙ ’ eo a a a ea a u phˆn tu. cˆ u tr´c s˜ giam v´.i m´.c d ˆ thu nho d u.o.c x´c d .nh bo.i c´c gi´ tri x´m xung ` ’´ a ˙a ue˙ ’ ˙ ¯ . a ¯i ’ ˙ a a .a ’ o u ¯o . .i h`nh danh v` c´c gi´ tri biˆn d o cua ch´ phˆn tu. cˆ u ´ ınh ` ’´ a˙ ’ a . e ¯ˆ ˙ .’ a ˙a quanh c´c chi tiˆt s´ng v` bo ı a ea aa . tr´c. u Nhu. trˆn, c´c ph´p to´n d˜n v` co l` d ˆi ngˆu cua nhau tu.o.ng u.ng v´.i h`m ˜ ´ ˙ ’ e a e a aa a ¯o a ´ oa 275