Tài liệu Kỹ thuật định vị các vùng trong nhập điểm tự động

H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic TR GIÁO D C VÀ ÀO T O NG I H C S PH M HÀ N I 2 NGUY N H I B NG NGUY N H I B NG CHUYÊN NGÀNH KHOA H C MÁY TÍNH THU T NH V CÁC VÙNG TRONG NH P MT NG LU N V N TH C S MÁY TÍNH KHÓA 15 HÀ N I, 2013 .d o o .c m C m w o .d o w w w w w C lic k to 1 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic TR GIÁO D C VÀ ÀO T O NG I H C S PH M HÀ N I 2 NGUY N H I B NG THU T NH V CÁC VÙNG TRONG NH P MT NG Chuyên ngành: Khoa h c máy tính Mã s : 60 48 01 01 LU N V N TH C S MÁY TÍNH Ng ih ng d n khoa h c: PGS.TS HÀ N I, 2013 N ng Toàn .d o o .c m C m w o .d o w w w w w C lic k to 2 c u-tr a c k .c H F-XC A N GE H F-XC A N GE c u-tr a c k N y bu to k lic IC M N Trong quá trình th c hi n lu n v n này, em luôn nh n n, ch b o t n tình c a PGS. TS. cs h ng N ng Toàn hi n công tác t i Vi n Công ngh Thông tin thu c Vi n Khoa h c và Công ngh Vi t Nam là cán b tr c ti p h ng d n khoa h c cho em. Em xin chân thành c m n s giúp quý báu ó. Em xin chân thành c m n các Th y, Cô giáo trong khoa Công ngh thông tin, các th y cô công tác t i Vi n Công ngh Thông tin thu c Vi n Khoa h c và Công ngh Vi t Nam, các cán b , chuyên viên phòng Sau i h c, tr ng i h c s ph m Hà N i 2 cùng các anh ch trong c quan ã t o nh ng i tr ng ào t o ng nghi p u ki n thu n l i cho tôi h c t p và nghiên c u i h c S Ph m Hà N i 2. Xin chân thành c m n các anh, các ch và các b n h c viên l p Cao c K15KHMT- tr ng i h c s ph m Hà N i 2 ã luôn ng viên, giúp và nhi t tình chia s v i tôi nh ng kinh nghi m h c t p, công tác trong su t khoá h c. Cu i cùng, tôi mu n g i l i c m vô h n t i gia ình và b n bè, nh ng ng i thân yêu luôn bên c nh và ng viên tôi trong su t quá trình th c hi n lu n v n t t nghi p. c dù r t c g ng, song lu n v n này không th tránh kh i nh ng thi u sót, kính mong c s ch d n c a các quý th y cô và các b n. nh Phúc, ngày 1 tháng 7 n m 2013 Tác gi Nguy n H i B ng .d o o .c m C m w o .d o w w w w w C lic k to bu y N O W ! PD O W ! PD c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic I CAM OAN Tôi xin cam oan r ng s li u và k t qu nghiên c u trong lu n v n này là trung th c và không trùng l p v i các ng m i s giúp tài khác. Tôi c ng xin cam oan cho vi c th c hi n lu n v n này ã thông tin trích d n trong lu n v n ã c c m n và các c ch rõ ngu n g c. nh Phúc, ngày 1 tháng 7 n m 2013 Tác gi Nguy n H i B ng .d o o .c m C m w o .d o w w w w w C lic k to 2 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic CL C C L C ............................................................................................................. 1 U ............................................................................................................... 4 Ch ng 1: KHÁI QUÁT V X LÝ NH VÀ BÀI TOÁN NH V VÙNG ....... 6 1.1. Khái quát v x lý nh ....................................................................... 6 1.1.1. lý nh, s 1.1.2. Các v n 1.1.2.1. t ng quát c a m t h th ng x lý nh................ 6 c b n trong x lý nh ............................................... 7 t s khái ni m ................................................................... 7 1.1.2.2. Bi u di n nh ......................................................................... 9 1.1.2.3. ng c ng nh –khôi ph c nh ........................................... 9 1.1.2.4. Nh n d ng nh ....................................................................... 9 1.1.3. Thu nh n nh ............................................................................. 10 1.1.3.1. Thi t b thu nh n nh ........................................................... 10 1.1.3.2. Bi u di n màu ...................................................................... 11 1.1.3.3. t a màu...................................................................... 12 1.1.4. Các k thu t x lý nh c b n .................................................... 13 1.1.4.1. Nh phân hóa........................................................................ 13 1.1.4.2. Kh nhi u ............................................................................ 14 1.1.4.3. Làm tr n biên, l p 1.2. Bài toán y ch tr ng ......................................... 14 nh v vùng trong nh p mt ng................................ 15 1.2.1. Mô t bài toán ............................................................................ 15 1.2.2. Ch t s cách ti p c n .................................................................. 16 ng 2: M T S K 2.1. THU T nh v vùng theo ph NH V VÙNG ....................................... 17 ng pháp hình thái h c .................................. 17 2.1.1. Các phép toán hình thái c b n .................................................. 17 2.1.1.1. ts nh ngh a ................................................................ 17 .d o o .c m C m w o .d o w w w w w C lic k to 1 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic 2.1.1.2. t s tính ch t c a phép toán hình thái .............................. 18 2.1.2. Phát hi n biên d a vào các phép toán hình thái .......................... 24 2.1.2.1. p x trên và x p x d i it ng nh ............................. 24 2.1.2.2. Thu t toán phát hi n biên d a vào phép toán hình thái......... 25 2.1.3. 2.2. nh v vùng s d ng ph nh v vùng s d ng ph ng pháp hình thái h c ........................ 27 ng pháp phân lo i Heuristic ................... 28 2.2.1. Thu t gi i Heuristic.................................................................... 28 2.2.2. Bài toán hành trình ng n nh t – ng d ng nguyên lý Greedy ..... 29 2.2.3. Bài toán phân vi c – ng d ng c a nguyên lý th t .................. 31 2.2.4. Các ph 2.2.4.1. ng pháp tìm ki m Heuristic ......................................... 34 u trúc chung c a bài toán tìm ki m .................................. 34 2.2.4.2. Tìm ki m chi u sâu và tìm ki m chi u r ng......................... 35 2.2.5. 2.3. nh v vùng s d ng ph ng pháp phân lo i Heuristic .............. 39 nh v vùng s d ng phép bi n i Hough ..................................... 41 2.3.1. Bi n i Hough cho ng th ng............................................... 41 2.3.2. Bi n i Hough cho ng th ng trong t a 2.3.3. Bi n i Hough và phát hi n góc nghiêng v n b n..................... 44 2.3.3.1. Áp d ng bi n c c .................... 43 i Hough trong phát hi n góc nghiêng v n b n ... 44 2.3.3.2. Thu t toán phát hi n và hi u ch nh góc nghiêng v n b n ..... 45 2.3.4. 2.4. Ch nh v vùng s d ng phép bi n nh v vùng b ng ph ng 3: CH i Hough ................................. 49 ng pháp k t h p hình thái h c v i Heuristic ........ 50 NG TRÌNH TH NGHI M ................................................ 51 3.1. Bài toán............................................................................................ 51 3.2. Phân tích bài toán ............................................................................. 52 3.3. Ch ng trình th nghi m ................................................................. 55 3.3.1. Thi t k ch 3.3.2. ng trình ................................................................. 55 t s k t qu ch ng trình ...................................................... 58 .d o o .c m C m w o .d o w w w w w C lic k to 2 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic Hình 3.2. Hình nh b ng m ch a xác Hình 3.3. Hình nh b ng m ã xác nh nh c vùng ch a c vùng ch a m .............. 58 m .................. 58 PH N K T LU N ............................................................................................. 60 TÀI LI U THAM KH O .................................................................................. 62 .d o o .c m C m w o .d o w w w w w C lic k to 3 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic U 1. Lý do ch n tài lý nh là m t khoa h c còn t ng i m i m so v i nhi u ngành khoa h c khác, nh t là trên quy mô công nghi p, song trong x lý nh ã b t u xu t hi n nh ng máy tính chuyên d ng. Nh n d ng là m t trong nh ng b ph n quan tr ng c a x lý nh và ã c ng d ng r t hi u qu trong nhi u nh v c khác nhau nh y t , giáo d c, qu c phòng, nghiên c u v tr . Trong quá trình công tác, tôi nh n th y r ng: Vi c x lý k t qu thi c a sinh viên hi n nay h u h t t qu thi sau khi vào máy tính các tr ng c th c hi n m t cách th công. c gi ng viên ghi vào biên b n ch m thi s l u tr và x lý. Vi c nh p m th công nh v y t n khá nhi u công s c và kh n ng nh m l n cao. N u công vi c nh p n ch m thi vào máy tính ct m t biên ng hóa thì hi u qu h n r t nhi u. giúp cho vi c ó òi h i chúng ta ph i xây d ng c các công c u hi u trong vi c nh n d ng các vùng ch a d li u trên b ng ng c nh p c các ch s vi t tay. Trong ph m vi m t m, nh n tài lu n v n th c s , tôi i sâu vào tìm hi u k thu t nh n d ng các vùng ch a d li u trên b ng m. Do ó tôi ch n tài: “ thu t nh v các vùng trong nh p m ng”. 2. M c ích nghiên c u - Làm gi m công s c cho giáo viên trong vi c nh p m t biên b n ch m thi vào máy tính - T ng tính chính xác, gi m thi u t i a các sai sót trong quá trình nh p m vào máy tính. .d o o .c m C m w o .d o w w w w w C lic k to 4 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic 3. Nhi m v nghiên c u - Nghiên c u các k thu t x lý và nh n d ng nh c b n - Nghiên c u c u trúc m t b ng i giúp cho vi c nh n d ng t 4. it mt ó xu t m u phi u ng c chính xác. m ng và ph m vi nghiên c u a. it ng nghiên c u - Phi u m (biên b n ch m thi) c a m t s tr ng h c. - Các k thu t x lý và nh n d ng nh - Xây d ng ph n m m mô ph ng nh n d ng vùng ch a d li u b. Ph m vi nghiên c u: M t s k thu t h tr xác li u m nh vùng ch a d m. 5. D ki n óng góp m i: tài khi hoàn thành s gi i quy t m t ph n quan tr ng c a bài toán nh p mt ng: Xác nh vùng ch a d li u phát tri n ng d ng áp d ng trong th c t 6. Ph m. t t c các tr ây là c s có th ng h c hi n nay. ng pháp nghiên c u - Nghiên c u tài li u, tìm hi u các thông tin trên Internet v các k thu t liên quan. - d ng th nghi m công c có s n xây d ng ch ng trình demo . hi u rõ b n ch t v n , sau ó .d o o .c m C m w o .d o w w w w w C lic k to 5 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic Ch ng 1: KHÁI QUÁT V X TOÁN 1.1. LÝ NH VÀ BÀI NH V VÙNG Khái quát v x lý nh 1.1.1. lý nh, s t ng quát c a m t h th ng x lý nh có th hình dung c u hình m t h th ng x lý nh chuyên d ng hay t h th ng x lý nh dùng trong nghiên c u, ào t o, tr xem xét các b c h t chúng ta s c c n thi t trong x lý nh. u tr Scanner Thu nh nh n Phân nh hóa tích Nh n d ng Camera quy t u tr nh Hình 1.1. Các giai Tr Thông th n chính trong x lý nh c h t là quá trình thu nh n nh. nh có th thu nh n qua camera. ng nh thu nh n qua camera là tín hi u t ki u CCIR), nh ng c ng có th là tín hi u s ng t (lo i camera ng hóa (lo i CCD – Charge Coupled Devide). nh c ng có th thu nh n t v tinh qua các b c m ng (sensor), hay nh, tranh c quét trên scanner. Chi ti t v quá trình thu nh n nh s c mô t trong m c 1.1.3. Ti p theo là quá trình s hóa (Digitalizer) bi n tín hi u t ng hóa, tr ng t sang tín hi u r i r c (l y m u) và s hóa b ng l c khi chuy n sang giai n x lý, phân tích hay l u tr l i. i .d o o .c m C m w o .d o w w w w w C lic k to 6 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic Quá trình phân tích nh th c ch t bao g m nhi u công t là công vi c t ng c ng nh nâng cao ch t l nguyên nhân khác nhau: có th do ch t l n nh . Tr ng nh. Do nh ng ng thi t b thu nh n nh, do ngu n sáng hay do nhi u, nh có th b suy bi n. Do v y c n ph i t ng c khôi ph c l i nh làm n i b t m t s n ti p theo là phát hi n các ch n các ng và c tính chính c a nh, hay làm cho nh g n gi ng nh t v i tr ng thái g c –tr ng thái tr Giai c c khi nh b bi n d ng. c tính nh biên, phân vùng nh, trích c tính, v.v… Cu i cùng, tùy theo m c ích c a ng d ng, s là giai phân l p hay các quy t nh khác. Các giai n nh n d ng, n chính c a các quá trình x lý nh có th mô t nh hình 1.1. 1.1.2. Các v n Nh ã khái quát các v n c b n trong x lý nh c p trong ph n gi i thi u, chúng ta ã th y chính trong x lý nh. xem xét hai khái ni m (thu t ng ) th (ph n t 1.1.2.1. § c m t cách hi u chi ti t h n, tr c tiên ta ng dùng trong x lý nh, ó là Pixel nh) và Grey level (m c xám), ti p theo là tóm t t các v n chính. t s khái ni m Pixel (Picture Element): ph n t nh nh trong th c t là m t nh liên t c v không gian và v giá tr sáng. có th x lý nh b ng máy tính c n thi t ph i ti n hành s hóa nh. Trong quá trình s hóa, ng i ta bi n i tín hi u liên t c sang tín hi u r i r c thông qua quá trình l y m u (r i r c hóa v không gian) và l ph n giá tr mà v nguyên t c b ng m t th m k nhau. Trong quá trình này, ng ng hóa thành ng không phân bi t c hai i ta s d ng khái ni m Picture element mà ta quen g i hay vi t là Pixel – ph n t nh. Nh v y, m t nh là t t p h p các pixel. ây c ng c n phân bi t khái ni m pixel hay c p .d o o .c m C m w o .d o w w w w w C lic k to 7 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic n trong các h th ng h a máy tính. tránh nh m l n ta t m g i khái ni m pixel này là pixel thi t b . Khái ni m pixel thi t b có th xem xét nh sau: khi ta quan sát màn hình (trong ch mà g m nhi u h a), màn hình không liên t c m nh , g i là pixel. M i pixel g m m t c p t a (x, y) và giá tr màu. a. nh v i phân gi i 72 dpi b. nh v i Hình 1.2. Bi u di n nh v i pt a (x, y) t o nên tính có nhi u lo i v i phân gi i 36 dpi phân gi i khác nhau phân gi i (resolution). Nh màn hình máy phân gi i khác nhau: màn hình CGA có phân gi i là 320 x 320; màn hình VGA là 640 x 350,… Nh v y, m t nh là m t t p h p các th ng m nh. Khi c s hóa, nó c bi u di n b i b ng hai chi u I(n, p): n dòng và p c t. Ta nói nh m n x p pixels. Ng i ta th ng ký hi u I(x, y) cho ta th y vi c bi u di n m t nh v i ch m t pixel. Hình 1.2 phân gi i khác nhau. M t pixel có th l u tr trên 1, 4, 8 hay 24 bit. § Gray level: M c xám c xám là k t qu s mã hóa t ng ng m t c m nh v i m t giá tr s - k t qu c a quá trình l kinh n th ng sáng c a m i ng hóa. Cách mã hóa ng dùng 16, 32 hay 64 m c. Mã hóa 256 m c là ph d ng nh t .d o o .c m C m w o .d o w w w w w C lic k to 8 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic do lý do k thu t. Vì 2^8 = 256 (0, 1, … , 255), nên v i 256 m c, m i pixel s c mã hóa b i 8 bit. 1.1.2.2. Bi u di n nh Trong bi u di n nh, ng i ta th ng dùng các ph n t c tr ng c a nh là pixel. Nhìn chung có th xem m t hàm hai bi n ch a các thông tin nh bi u di n c a m t nh. Các mô hình bi u di n nh cho ta m t mô t logic hay nh l ng các tính ch t c a hàm này. Trong bi u di n nh c n chú ý tính trung th c c a nh ho c các tiêu chu n “thông minh” o ch t l ng nh ho c tính hi u qu c a các k thu t x lý. Vi c x lý nh s yêu c u nh ph i c m u hóa và l ng t hóa. Thí m t nh ma tr n 512 dòng g m kho ng 512 x 512 pixel. Vi c l nh là chuy n i tín hi u t ng t hóa ng t sang tín hi u s (Analog Digital Convert) a m t nh ã l y m u sang m t s h u h n các m c xám. t s mô hình th ng c dùng trong bi u di n nh: mô hình toán, mô hình th ng kê. Trong mô hình toán, nh hai chi u c bi u di n nh các hàm hai bi n tr c giao g i là các hàm c s . V i mô hình th ng kê, m t nh c coi nh m t ph n t c a m t t p h p v ng toán h c, hi p bi n, ph 1.1.2.3. ng c ng c c tr ng b i các il ng nh : ng sai, moment. ng nh –khôi ph c nh ng nh là b c quan tr ng, t o ti n t lo t các k thu t nh : l c t cho x lý nh. Nó g m ng ph n, kh nhi u, n i màu, v.v… 1.1.2.4.Nh n d ng nh Nh n d ng nh là quá trình liên quan ta mu n c t nó. Quá trình nh n d ng th c tính ch y u c a it n các mô t it ng mà ng i ng i sau quá trình trích ch n các ng. Có hai ki u mô t it ng: .d o o .c m C m w o .d o w w w w w C lic k to 9 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic - Mô t tham s (nh n d ng theo tham s ). - Mô t theo c u trúc (nh n d ng theo c u trúc). Trên th c t , ng i nhi u it i ta ã áp d ng k thu t nh n d ng khá thành công ng khác nhau nh : nh n d ng nh vân tay, nh n d ng ch (ch cái, ch s , ch có d u). Ngoài ra, hi n nay m t k thu t nh n d ng m i d a vào k thu t m ng ron ang c áp d ng và cho k t qu kh quan. 1.1.3. Thu nh n nh 1.1.3.1.Thi t b thu nh n nh Các thi t b thu nh n nh có th cho nh tr ng en B/W (Black & White) v i m t t 400 n 1600 dpi (dot per inch) ho c nh màu 600 dpi. i nh B/W m c màu là 0 ho c 1. V i nh a c p xám, m c xám bi n thiên 0 n 255. nh màu, m i m nh l u tr trong 3 bytes và do ó ta có 2 8 x 3 màu (c 16,7 tri u màu). Khi dùng scanner, m t dòng photodiot s quét ngang nh (quét theo hàng) và cho nh v i phân gi i ngang khá t t. ma tr n s mà ta quen g i là b n t o nh vect có h u ra c a scanner là nh nh ( nh Bitmap), b s hóa (digitalizer) ng. Trong x lý nh b ng máy tính, ta không th không nói monitor (màn hình) hi n nh. Monitor có nhi u lo i khác nhau: § CGA: 640 x 320 x 16 màu, § EGA: 640 x 350 x 16 màu, § VGA: 640 x 480 x 16 màu, § SVGA: 1024 x 768 x 256 màu. n thi t b .d o o .c m C m w o .d o w w w w w C lic k to 10 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic i nh màu, có nhi u cách t h p màu khác nhau. Theo lý thuy t màu do Thomas a ra t n m 1802, m i màu u có th t h p t 3 màu c b n: Red ( ), Green (l c) và Blue (l ). Thi t b ra nh có th là máy en tr ng, máy in màu hay máy v (ploter). Máy v c ng có nhi u lo i: lo i dùng bút, lo i phun m c. Nhìn chung, các h th ng thu nh n nh th c hi n hai quá trình: - m bi n: bi n ng - i n ng l ng quang h c (ánh sáng) thành n ng n. ng h p n ng l ng n thành nh. 1.1.3.2.Bi u di n màu Ánh sáng màu là t h p c a ánh sáng m nh n n s c. M t ng c vài ch c màu, song l i có th phân bi t i ch có th c hàng ngàn màu. Có 3 thu c tính ch y u trong c m nh n màu: - Brighness: s c màu, còn g i là - Hue: s c l chói. ng, còn g i là s c thái màu. - Saturation: bão hòa. Hình 1.3. H t a i ngu n sáng hòa thay n s c, i nhanh n u ta thêm l quan gi a nh ng các il hue t ng ng v i b màu RGB c sóng λ. bão ng ánh sáng tr ng. Hình 1.3 mô t m i liên ng trên và 3 màu ch y u R, G và B. .d o o .c m C m w o .d o w w w w w C lic k to 11 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic i ph màu m W* c nh, các ký hi u G, R, B ch v trí t ng i c a các , l c và l . Do s tán s c ánh sáng mà ta nhìn rõ màu. Theo Maxwell, trong võng c có 3 lo i t bào hình nón c m th 3 màu c b n ng v i 3 ph h p th S1( λ ), S2( λ ) và S3( λ ); λ min = 380 nm; λ max = 780 nm. - t màu b t k s là m t m trên vòng tròn. - u White và Black là nh nhau thì ng tròn là l n nh t và R là m bão hòa. - S thay i theo bán kính - H thay i theo góc θ . - W* là s c màu. 1.1.3.3. t a màu ch c y t d’Eclairage) ây ch màu c b n). Nh a x-y-z) chu n hóa màu CIE (Commision Internationalé a ra m t s các chu n chu n riêng. t t l nào v c p bi u di n màu. Các h này có các n chu n m u CIE-RGB (h t a dùng 3 ã nêu trên, m t màu là t h p c a các màu c b n theo y. Ng i ta dùng h t a bi u di n màu nh sau: ba màu R-G-B (t ng ng v i h .d o o .c m C m w o .d o w w w w w C lic k to 12 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic Hình 1.4. H t a R-G-B Trong cách bi u di n này ta có công th c: + l c + l = 1. Công th c này g i là công th c Maxwell. Ta c ng có th chuy n t h t a t a 3 màu v x-y-z. 1.1.4. Các k thu t x lý nh c b n Trên ây ã nói các khái ni m c b n trong x lý nh, chúng ta s tìm hi u m t s k thu t x lý nh. 1.1.4.1.Nh phân hóa Nh phân hóa là th c hi n phép bi n i nh t nh a c p xám v nh phân (có 2 c p xám). Do các k thu t nh n d ng ch c n nh nh nh phân nên b Ph ng pháp 0 : f (u) =  1 : c này c n th c hi n khi nh u<θ u vào là u vào là nh a c p xám. n gi n là dùng m t hàm c t v i giá tr ng u≥θ nh ng θ. .d o o .c m C m w o .d o w w w w w C lic k to 13 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic Trong ó u là m c xám c a m t ng θ có th Ng cách tính toán các il m nh. c ch n tr c ho c th c hi n ch n t ng th ng kê trên l c ng b ng t n xu t histogram c a nh, a vùng nh. 1.1.4.2.Kh nhi u Kh nhi u c ti n hành b ng cách s d ng các b l c tuy n tính (l c trung bình) ho c phi tuy n (l c trung v ). Kh nhi u b ng các b l c tuy n tính ph bi n là các b l c sau: 1 1 1 1 2 1  1 1   1 1 1 2 4 2  9 16  1 1 1 1 2 1  Các b l c trên 1 2 1  4 100  2 1 2 4 2 1 4 8 4 2  8 16 8 4  4 8 4 2 2 4 2 1  c k t h p v i nh b ng phép nhân ch p (phép cu n) và cho ra nh k t qu có nhi u nh h n nh ban 1.1.4.3.Làm tr n biên, l p u. y ch tr ng Trên th c t , sau khi kh nhi u, nh ban u mà hình thành các hành l p y ch tr ng, xóa i các ng biên ch không c tr n tru ng cong có r ng c a. Khi ó ta ph i ti n m gi trên biên ch . Hai k thu t hay c s d ng là Unger và Dineen. thu t Dineen dùng m t m t n n x n di chuy n trên t t c các v trí trong nh. M t nh m i c t o ra trên ó m i ph n t t i tâm c a s c tính l i theo các ph n t lân c n. N u t ng các ph n t trong c a s l n h n t ng ng θ nào ó thì v trí t 0. Kích th c c a s th ng ng trong nh m i s là 1, ng ng ch n là 3 x 3 ho c 4 x 4. c l i là .d o o .c m C m w o .d o w w w w w C lic k to 14 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic thu t Unger dùng m t t p lu t m ang xét, ta có các l p y ch tr ng. Gi s P là m lân c n c a P nh sau: P3 P2 P9 P4 P P8 P5 P6 P7 m P trên nh m i là en khi và ch khi th a mãn 1 trong 2 u ki n sau: 1. P là m en 2. Có ít nh t 3 trong 4 láng gi ng P 2 , P 3 , P 6 , P 8 là en lo i b các m cô l p sau khi l p y ch tr ng, Unger l i dùng t t p lu t khác: 1. Có ít nh t 1 trong 3 láng gi ng P 2 , P 3 , P 4 là en 2. Có ít nh t 1 trong 3 láng gi ng P 6 , P 7 , P 8 là en Ho c: 1. Có ít nh t 1 trong 3 láng gi ng P 4 , P 5 , P 6 là en 2. Có ít nh t 1 trong 3 láng gi ng P 2 , P 8 , P 9 là en 1.2. Bài toán nh v vùng trong nh p mt ng 1.2.1. Mô t bài toán Hi n nay, a ph n các tr qu n lý ng h c m. Vi c này, giúp vi c qu n lý u s d ng ph n m m tin h c c chính xác, tra c u nhanh chóng. Tuy nhiên, theo tìm hi u c a tác gi thì các ph n m m này cho phép in biên b n ch m trách các giáo viên ch m thi nh p m ph i có trách nhi m nh p u cho ch m r i ng i ph m b ng tay. M c dù các ph n m m .d o o .c m C m w o .d o w w w w w C lic k to 15 c u-tr a c k .c H F-XC A N GE H F-XC A N GE N y bu bu y N O W ! PD O W ! PD c u-tr a c k to k lic hi n nay u có ch c n ng in ki m dò, nh ng công vi c này v n hoàn toàn th công d n t i có nhi u sai sót. Bài toán nh p n mà tác gi mt ã nêu ng n u trên. Vi c nh p th p nh biên b n ch m thi (thông th a ra c b ng c gi i quy t s kh c ph c mt c các ng s là quá trình thu ng qua máy Scanner) sau ó s x lý m chính xác d i d ng s trên máy tính. Trong bài toán này, có hai bài toán nh c n gi i quy t ó là: Xác nh vùng ch a d li u m và nh n d ng ch s vi t tay. Trong ph m vi nghiên c u c a lu n v n, tác gi s 1.2.2. i t p trung nghiên c u vào vi c xác m. t s cách ti p c n Có nhi u ph ng pháp xác tính ch t c a các ph ph nh vùng ch a d li u nh vùng trong nh p ng pháp xác mt nh vùng d li u ng. D a vào m, có th ch ra hai ng pháp ti p c n chính: ng ti p c n d a trên tri th c: Mã hóa các hi u bi t c a con ng i v các vùng trong m t b ng m. Trên th c t thì m c dù b ng m s có th trình bày b ng b t k ngôn ng nào chúng ta v n có th nh n c âu là vùng d li u ch a ng cá nhân. M t ví d m t ó xác n hình là trên b t k b ng nh c oán mc a m h s 10 nào thì m bao gi c ng g m hai ph n: ph n nguyên và ph n th p ph n cách nhau i d u “.” ho c d u “,”. ng ti p c n d a trên so kh p m u: N u chúng ta có s n các m u phi u m thì hoàn toàn có th s d ng ph nh n d ng m t b ng m kh p v i các m u. Xác nh ta ã xác trúc riêng). nh xác ng pháp này. Khi c n nh vùng ch a d li u c b ng c vùng ch a d li u m, ta s i so m thu c m u nào thì rõ ràng chúng m (các m u c l u tr u có c u .d o o .c m C m w o .d o w w w w w C lic k to 16 c u-tr a c k .c