Bài Giảng Công Nghệ Xử Liý Ảnh Số - Mai Cường Thọ phần 9

Chia sẻ: Dqwdqweferg Vgergerghegh | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

63
lượt xem 4
download

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

Kết xuất đồ họa là một trong các chủ đề con chính của đồ họa máy tính ba chiều (3D computer graphics). Trong thực tiễn, nó luôn luôn có quan hệ chặt chẽ với các chủ đề khác.

Chủ đề:

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

Lưu

Nội dung Text: Bài Giảng Công Nghệ Xử Liý Ảnh Số - Mai Cường Thọ phần 9

57 Bài gi ng X lý nh Quá trình dò biên theo n n vùng là: tìm 1 dãy các i m (n0, v0), (n1, v1)…(nk, vk) sao cho n0, n1, ….nk : chu tuy n n n v0, v1, ….vk : chu tuy n vùng C p (ni+1, vi+1) 8 láng gi ng 00000000000000 00001111111000 00011111111100 00011111111100 00011111111000 00011111110000 00001111100000 00000000000000 3. X p x b i o n th ng N i i m xu t phát R v i i m ang xét Pc b i m t o n th ng. Sau ó tính to c a Pi, m t i m n m gi a R và Pc sao cho kho ng cách t Pi n o n th ng là c c i. G i kho ng cách này là di. N u di l n hơn m t ngư ng cho trư c ( chính xác c a x p x ) ngư i ta phân o n RPc thành 2 o n RPi và PiPc và ti p t c th c hi n l y m u v i t ng o n cho t i khi o n th ng tìm ư c là “r t g n” v i ư ng bao. • Pi • • • • • • • • di • Pc • • Pi • R • di • • • • • • • • Pc • • P2 R • P1 • • • • • • • • • Pc • • ư ng biên b ng ư ng g p khúc R Hình x p x GV. Mai Cư ng Th
58 Bài gi ng X lý nh III. CÁC PHƯƠNG PHÁP PHÂN VÙNG NH phân tích các i tư ng trong nh, chúng ta c n ph i phân bi t ư c các i tư ng c n quan tâm v i ph n còn l i c a nh. Nh ng i tư ng này có th tìm ra ư c nh các k thu t phân o n nh, theo nghĩa tách ph n ti n c nh ra kh i h u c nh trong nh. Chúng ta c n ph i hi u ư c là: Không có k thu t phân o n nào là v n năng, theo nghĩa có th áp d ng cho - m i lo i nh. Không có k thu t phân o n nào là hoàn h o. - Có th hi u phân vùng là ti n trình chia nh thành nhi u vùng, m i vùng ch a m t i tư ng hay nhóm i tư ng cùng ki u. Ch ng h n, m t i tư ng có th là m t kí t trên m t trang văn b n ho c m t o n th ng trong m t b n v k thu t ho c m t nhóm các i tư ng có th bi u di n m t t hay hay o n th ng ti p xúc nhau. Ta có m t s phương pháp phân vùng nh như sau: 1. Thu t toán gán nhãn thành ph n liên thông K thu t này gán cho m i thành ph n liên thông c a nh nh phân m t nhãn riêng bi t. Nhãn thư ng là các s t nhiên b t u t m t n t ng s các thành ph n liên thông có trong nh. Gi i thu t quét nh t trái sang ph i và t trên xu ng dư i. Trong dòng th nh t c a các pixel en, m t nhãn duy nh t ư c gán cho m i ư ng ch y liên t c c a pixel en. V i m i pixel en c a các dòng ti p theo, các pixel lân c n trên dòng trư c và pixel bên trái ư c xem xét. N u b t kì pixel lân c n nào ư c gán nhãn, nhãn tương t ư c gán cho pixel en hi n th i; ngư c l i nhãn ti p theo chưa ư c s d ng ư c ch n. Th t c này ư c ti p t c cho t i dòng cu i c a nh. Lúc k t thúc ti n trình này, m t thành ph n liên thông có th ch a các pixel có các nhãn khác nhau vì khi chúng ta xem xét lân c n c a pixel en, ch ng h n pixel “?” trong hình v . Pixel i v i lân c n trái và nh ng lân c n trong dòng trư c có th ư c gán nhãn m t cách riêng bi t. M t tình hu ng như v y ph i ư c xác nh và ghi l i. Sau ti n trình quét nh, vi c gán nhãn ư c hoàn t t b ng cách th ng nh t các mâu thu n các nhãn và gán l i các nhãn chưa s d ng. GV. Mai Cư ng Th
59 Bài gi ng X lý nh minh ho ta có hình bi u di n sau : . . . . . . . . . …….. ....PPPP.... ....L?....... . . . . . . . .. . . . . .. P: lân c n trư c, L lân cân trái . ..... ...... . . ...... ...... . . . ** * * . . * ** . . . . . 1 11 1 . . 2 22 . . . . . .* * * . . * ** * . . . ..111. .2 2 22 . . . . ** * * . * * ** * . . . . 1 1 11 . 2 2 2 22 . . . . . . * ** **.... . . . . . 1 1? **.... . . ⇒ . . . * ** * * * .* . . . . . .* ** * * * .* . . . ** . . . . ....** . . **.... ....** . . .* * . . . ....** . . .**... ....** . . .* * . . . ...... . . .**... ...... . . Hình b . nh ban u Hình c . Ti n trình gán nhãn . ..... ...... . . ...... ...... . . . 11 1 . . 2 22 . . . . . 11 1 . . 1 11 . . . . 1 1 . . 11 1 . . 2 22 2 . . . ..111. .1 1 11 . . . . 1 11 1 . 22 22 2 . . . .1 1 11 . 1 1 1 11 . . . . . . 1 11 .... . . ...111 11.... . . 11 ⇒ . . . 1 11 1 .3 . . . . . .1 1 1 1 1 1 .2 . . . 11 44 . . . . ....33 . . 33.... . . . .2 2 . . .4 4 . . . ....33 . . .33... . . . .2 2 . . .4 4 . . . ...... . . .33... ...... . . Hình d . Sau khi quét y Hình e .K t qu sau cùng Vd : m t phương pháp s a nhãn ∃(p,q) là liên thông 8 mà label(p)label(q) -> s a nhãn cho gi ng nhau. 2. Phân vùng b ng tách cây t phân V nguyên t c, phương pháp này ki m tra tính h p th c c a tiêu chu n m t cách t ng th trên mi n l n c a nh. N u tiêu chu n ư c th a, vi c phân o n coi như k t thúc. Trong trư ng h p ngư c l i, ta chia mi n ang xét thành 4 mi n nh hơn. V i m i mi n nh , ta áp d ng m t cách quy phương pháp trên cho n khi t t c các mi n u th a. Thu t toán này t o nên m t cây mà m i nút cha có 4 nút con m i m c tr m c ngoài cùng. Vì th cây này có tên là cây t phân. Cây này cho ta hình n rõ nét v c u trúc phân c p c a các vùng tương ng v i tiêu chu n. GV. Mai Cư ng Th
60 Bài gi ng X lý nh M t vùng th a chu n s t o nên m t nút lá, n u không nó s t o nên m t nút trong và có 4 nút con tương ng v i vi c chia làm 4 vùng. Ta c ti p t c như v y cho n khi phân xong. Các nút c a cây bi u di n s vùng ã phân. Tiêu chu n phân vùng ây là màu s c. N u m i i m c a vùng u là màu tr ng thì s t o nên nút lá tr ng và tương t như v y v i nút lá en. Nút màu ghi vùng không thu n nh t và ph i ti p t c chia. V i ngư ng θ cho trư c, vùng thu n nh t ph i th a i u ki n l ch chu n σ < θ • Ho c Max − Min < θ v i Max, Min l n lư t là giá tr l n nh t và nh nh t c a • m c xám trong vùng c n chia. • Giá tr i m nh trong vùng b ng cách l y trung bình giá tr c a vùng ó Vùng 2 Vùng 1 Vùng 3 Vùng 4 nh g c Phân o n m c1 Ví d : Cho nh S(m, n) , hãy phân vùng theo tiêu chí: ngư ng θ= 2 và Max − Min < θ Vùng 1 2 2 4 4 6 6 8 8 22446688 2 2 4 4 6 6 8 8 2 2 4 4 6 6 8 8 2 3 5 5 6 7 8 9 2 3 5 5 6 7 8 9 8 7 5 5 3 3 2 1 8 7 5 5 3 3 2 1 S (m, n) = k t qu S (m, n) = 7 7 5 5 3 3 2 2 7 7 5 5 3 3 2 2 7 7 5 5 3 3 2 2 7 7 5 5 3 3 2 2 2 2 4 4 6 6 8 9 2 2 4 4 6 6 8 9 2 2 4 4 6 6 8 9 2 2 4 4 6 6 8 9 GV. Mai Cư ng Th
61 Bài gi ng X lý nh Ta có cây t phân như sau 4 3 2 1 21 22 23 24 (9) (5) (5) (7) (2) (4) (2) (3) (6) (4) (2) (3) (2) (8) (7) 11 14 12 (8) 13 (6) (9) (8) (2) (1) (3) (7) (6) (3) 3. Phân vùng b i h p Ý tư ng c a phương pháp này là xem xét nh t các mi n nh nh t r i h p ư c m t mi n ng nh t l n hơn. Ta l i ti p t c chúng l i n u th a tiêu chu n v i mi n thu ư c cho t i khi không th h p ư c n a. S mi n còn l i cho ta k t qu phân o n. Như v y mi n nh nh t c a bư c xu t phát là i m nh. Phương pháp h p vùng ư c th c hi n như sau: Gi s có 2 vùng ω và ω’ • nh c p các i m 4 láng gi ng (p, q) sao cho p ∈ω và q ∈ω’ • Ta xác 1 if I ( p ) − I (q) ≤ θ 1 nh T ( p , q ) =   • Xác 0 otherwise Trong ó I(p), I(q) là giá tr m c xám c a i m p và q, θ1 là giá tr ngư ng cho trư c. i b(ω) và b(ω’) là s i m biên c a 2 vùng ω và ω’ •G GV. Mai Cư ng Th
62 Bài gi ng X lý nh ∑ T ( p, q) hàm kh năng h p 2 vùng : KNG (ϖ , ϖ ' ) = • Xét Min(b(ϖ ), b(ϖ ' )) u KNG (ϖ , ϖ ' ) ≥ θ 2 thì có th h p 2 vùng ω và ω’ thành 1 vùng. •N Ví d : Xét kh năng h p các vùng c a nh sau, θ1 =3, θ 2 =0.6 11666666 11166666 11168886 S ( m, n ) = 2 1 6 6 6 8 8 8 21226688 22244688 22224444 G i A, B, C, D, E l n lư t là các vùng ch a m c xám 1, 2, 4, 6, 8 ∑ T ( p, q) Ta có b ng 1, ms i m biên các vùng và tính toán các ω’ B(ω) A B C D E ω A - 5 0 0 0 10 B 5 - 4 0 0 11 C 0 4 - 3 0 6 D 0 0 3 - 11 19 E 0 0 0 11 - 10 Xác nh h p vùng B ng 2 KNG(ω,ω’) A B C D E A - 5/10 0 0 0 B 5/10 - 4/6 0 0 C 0 4/6 - 3/6 0 D 0 0 3/6 - 11/10 K t lu n : Có th h p ư c 2 vùng D và E vì 11/10 >θ2 Có th h p ư c 2 vùng B và C vì 4/6 >θ2 GV. Mai Cư ng Th
63 Bài gi ng X lý nh IV. Phân vùng nh d a theo ngư ng biên - K thu t l y ngư ng K thu t này d a trên m t ý tư ng h t s c ơn gi n. M t tham s θ, g i là ngư ng ư c ch n sáng, s áp d ng cho m t nh a[m,n] theo cách sau: N u a[m, n] ≥ θ thì a[m, n] = object = 1 a[m, n ] = background = 0 Ngư c l i i tư ng sáng Thu t toán trên gi nh r ng chúng ta ang quan tâm n các (object) hay n n nh (background) b ng các giá tr “1” ho c “0”. Câu h i trung tâm trong k thu t l y ngư ng khi ó s là: Chúng ta nên ch n ngư ng θ như th nào? M c dù không có thu t toán ch n ngư ng v n năng nào có th áp d ng cho m i lo i nh. Chúng ta cũng có nhi u phương pháp ưa ra dư i ây: 1. Ngư ng c nh Phương pháp u tiên là ch n m t ngư ng c l p v i d li u nh. N u chúng ta bi t trư c là chương trình ng d ng s làm vi c v i nh ng nh có tương ph n i tu ng quan tâm r t t i còn n n g n như r t cao, trong ó các ng nh t và r t sáng, thì giá tr ngư ng không i 128 trên thang sáng t 0 n 255 s là m t giá ây nên ư c hi u theo nghĩa là s lư ng các tr ch n khá chính xác. Chính xác i m nh b phân l p sai là c c ti u. 2. Ngư ng d a trên lư c Trong h u h t các trư ng h p, ngư ng ư c ch n t lư c sáng c a vùng hay nh c n ư c phân o n. Hình dư i ây cho chúng ta m t ví d v nh và lư c sáng liên k t v i nó. GV. Mai Cư ng Th