Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu kỹ thuật dán nhãn cho đối tượng 2D

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:62

Thêm vào BST

Báo xấu

20
lượt xem 3
download

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

Mục đích nghiên cứu của đề tài là tìm hiểu về bài toán dán nhãn cho đối tượng, thực tiễn ứng dụng của nó trong các lĩnh vực, tìm hiểu một số vấn đề về đồ họa 2D, các thuật toán liên quan từ đó đặt nền tảng nghiên cứu sâu hơn về vấn đề này từ đó thiết kế chương trình thử nghiệm dán nhãn cho một số đối tượng 2D. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu kỹ thuật dán nhãn cho đối tượng 2D

i ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG VŨ VĂN ANH NGHIÊN CỨU KỸ THUẬT DÁN NHÃN ĐỐI TƢỢNG 2D LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
ii LỜI CAM ĐOAN Luận văn là sự nghiên cứu các kiến thức mà học viên đã thu thập, tìm hiểu đƣợc trong quá trình học tập tại Trƣờng Đại học Công nghệ thông tin và truyền thông- Đại học Thái Nguyên, dƣới sự hƣớng dẫn, giúp đỡ của các thầy cô và bạn bè. Đặc biệt là sự hƣớng dẫn của thầy giáo hƣớng dẫn TS. Nguyễn Văn Huân Học viên xin cam đoan nội dung bản luận văn này không phải là sản phẩm sao chép của bất kỳ tài liệu khoa học nào. Thái Nguyên, ngày 12 tháng 5 năm 2015 Học viên Vũ Văn Anh Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
iii LỜI CẢM ƠN Luận văn sẽ không thể hoàn thành nếu không có sự động viên, hỗ trợ hết mình của rất nhiều ngƣời. Trƣớc hết tôi xin gửi lời cảm ơn sâu sắc đến TS Nguyễn Văn Huân ngƣời thầy đã chỉ bảo, giúp đỡ tận tình trong cả quá trình học tập, nghiên cứu và hoàn thiện luận văn. Xin gửi lời cảm ơn đến các thầy cô giáo tại trƣờng Đại học Công nghệ thông tin và truyền thông – Đại học Thái Nguyên, những ngƣời đã trang bị các kiến thức cơ sở, nền tảng cho việc nghiên cứu, tiếp thu những tri thức mới, mà từ đó tôi có thể hoàn thành tốt luận văn của mình. Quá trình thực hiện đề tài không tránh khỏi những thiếu sót. Tôi hi vọng sẽ đƣợc sự góp ý chân thành từ phía các thầy, cô giáo, bạn bè, đồng nghiệp để đề tài nghiên cứu đƣợc hoàn thiện hơn Xin chân trọng cảm ơn! Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
iv MỤC LỤC LỜI CAM ĐOAN .............................................................................................. i LỜI CẢM ƠN .................................................................................................. iii MỤC LỤC ........................................................................................................ iv DANH MỤC HÌNH VẼ TRONG LUẬN VĂN .............................................. vi DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ CÁI VIẾT TẮT......................... viii MỞ ĐẦU ........................................................................................................... 1 Chƣơng I. TỔNG QUAN VỀ BÀI TOÁN DÁN NHÃN ................................. 4 1.1. Giới thiệu bài toán .................................................................................. 4 1.2. Định nghĩa bài toán ................................................................................. 5 1.3. Tƣ tƣởng chung giải quyết bài toán dán nhãn ........................................ 7 Chƣơng 2. MỘT SỐ THUẬT TOÁN DÁN NHÃN ĐỐI TƢỢNG ................. 9 2.1. Thuật toán dán nhãn điểm GFPL ............................................................ 9 2.2. Kỹ Thuật toán ELP ............................................................................... 15 2.2.1. Thuật toán ELP............................................................................... 15 2.2.2. Thuật toán Fast ELP: ...................................................................... 17 2.3. Giới thiệu kỹ thuật NLP (Node Label Placement) ............................... 23 2.4. Kỹ thuật MLP (Multiple Label Placement) .......................................... 24 2.4.1. Giới thiệu kỹ thuật MLP ................................................................ 24 2.4.2.Thuật toán Iterative ......................................................................... 29 2.4.3. Thuật toán Flow-based ................................................................... 32 2.5. Kỹ thuật dán nhãn dựa vào hiệu chỉnh đối tƣợng................................. 36 2.6. Thuật toán dán nhãn đƣờng biên .......................................................... 37 2.6.1. Giới thiệu chung ............................................................................. 37 2.6.2. Thuật toán ....................................................................................... 39 Chƣơng 3. CHƢƠNG TRÌNH CÀI ĐẶT ỨNG DỤNGError! Bookmark not defined.6 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
v 3.1. Đánh giá thuật toán ......................................................................... 466 3.2. Yêu cầu bài toán dán nhãn .................................................................... 49 3.3. Chƣơng trình: ........................................................................................ 49 3.4. Kết quả thử nghiệm .............................................................................. 50 KẾT LUẬN ..................................................................................................... 51 TÀI LIỆU THAM KHẢO ............................................................................... 53 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
vi DANH MỤC HÌNH VẼ TRONG LUẬN VĂN Hình 1.1. (a) Dán nhãn điểm, (b) Dán nhãn cạnh, (c) Dán nhãn vùng ............. 6 Hình 2.1. Bản vẽ hƣớng nơi nhãn đƣợc định vị bằng các kỹ thuật phù hợp cho kỹ thuật GFLP. Các nhãn đƣợc đặt song song với trục ngang. Hộp màu xám là nút nhãn và hộp trắng cạnh nhãn................................................................. 12 Hình 2.2. Đồ thị với các vị trí nhãn đƣợc dán cho mỗi cạnh .......................... 13 Hình 2.3. Vị trí nhãn có thể cho một điểm...................................................... 13 Hình 2.4. Xác định các vị trí nhãn cho cạnh ................................................... 18 Hình 2.5. (a) Một bản vẽ đơn giản với các vị trí nhãn cho mỗi cạnh (b) Các đồ thị phù hợp tƣơng ứng. .................................................................................... 19 Hình 2.6. Một kết quả dán nhãn của thuật toán Fast ELP .............................. 21 Hình 2.7. Kết quả dán nhãn cạnh cho một bản vẽ trực giao có nhiều cạnh nằm ngang, áp dụng Fast ELP. ............................................................................... 22 Hình 2.8. Bản vẽ hình tròn với các nhãn cạnh, nơi nhãn đƣợc phép chồng lên các đối tƣợng hình khác, đƣợc xây dựng bằng kỹ thuật ELP ......................... 23 Hình 2.9. (a) Phân nhãn thích hợp hơn. (b) Đặt nhãn gây hiểu nhầm. (c) Ràng buộc khoảng cách chặt chẽ. (d) Xác định ràng buộc tự do. ............................ 27 Hình 2.10. (a) Gán nhãn thích hợp hơn. (b) Việc gán nhãn chấp nhận đƣợc. (c) Việc gán nhãn gây hiểu nhầm.................................................................... 29 Hình 2.11. Một bản vẽ trực giao với vị trí hai nhãn mỗi cạnh sự dụng thuật toán Iterative .................................................................................................... 31 Hình 2.12. Một bản vẽ phân cấp với vị trí hai nhãn mỗi cạnh sự dụng thuật toán Iterative .................................................................................................... 32 Hình 2.13. Đồ thị Flowbased .......................................................................... 33 Hình 2.14. Bản vẽ với vị trí hai nhãn mỗi cạnh bởi thuật toán Flow-based ... 34 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
vii Hình 2.15. Một bản vẽ vòng tròn với ba nhãn cho mỗi cạnh và nút đƣợc định vị bằng thuật toán Flow-based trên. Các ô màu trắng là các nhãn cạnh và các hộp đen là nút nhãn ......................................................................................... 35 Hình 2.16. Bốn bƣớc chính trong kĩ thuật lần, đánh nhãn thành phần ........... 40 Hình 2.17. P là điểm đầu của đƣờng biên ngoài,1 là điểm đen chƣa đƣợc đánh nhãn ................................................................................................................. 41 Hình 2.18. (A) P là điểm khởi đầu của đƣờng biên trong, cũng nằm trên đƣờng biên ngoài. (B) P là điểm khởi đầu của đƣờng biên trong nhƣng không nằm trên đƣờng biên ngoài. 1: điểm đen chƣa đƣợc đánh nhãn, ∆: điểm đen đã đƣợc đánh nhãn. .............................................................................................. 41 Hình 2.19. P là điểm chƣa đƣợc đánh nhãn, điểm lân cận trái N đã đƣợc đánh nhãn 42 Hình 2.20. Các điểm trắng bao quanh đối tƣợng đƣợc đánh dấu bởi số âm... 43 Hình 2.21. Các điểm trắng quanh đối tƣợng đƣợc đánh dấu âm khi đƣờng biên đã đƣợc lần ...................................................................................................... 43 Hình 2.22. Lần đƣờng biên của một đối tƣợng ............................................... 44 Hình 2.23. (A) đánh số thứ tự các điểm lân cận của P từ 0 tới 7; (B) Nếu điểm biên trƣớc P nằm ở 3 thì bắt đầu tìm kiếm từ 5 .............................................. 44 Hình 2.24. Lần đƣờng biên trong, ngoài đồng thời đánh dấu các điểm trắng bao quanh ........................................................................................................ 45 Hình 2.25. Ví dụ 1 điểm biên P nằm trên 4 đƣờng biên ................................. 46 Hình 2.26. (A) Nếu P nằm trên đƣờng biên trong ∂, điểm lân cận trái Q là điểm trắng thì ∂ phải có điểm U trên Q và P. (B) Ngoài ra, nếu đƣờng kẻ dọc L qua Q không giao với phi trên Q thì Q là điểm nằm ngoài thành phần (đối tƣợng đang xét) và P là điểm thuộc đƣờng biên ngoài. .................................. 48 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
viii DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ CÁI VIẾT TẮT GFLP Graphical Feature Label Placement ELP Edge Label Placement MLP Multiple Label Placement NLP Node Label Placement Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
1 MỞ ĐẦU 1. Lí do chọn đề tài: Công nghệ thông tin đã ở một bƣớc phát triển cao đó là số hóa tất cả các dữ liệu thông tin, luân chuyển mạnh mẽ và kết nối tất cả chúng ta lại với nhau. Mọi loại thông tin, số liệu âm thanh, hình ảnh có thể đƣợc đƣa về dạng kỹ thuật số để bất kỳ máy tính nào cũng có thể lƣu trữ, xử lý và chuyển tiếp cho nhiều ngƣời. Những công cụ và sự kết nối của thời đại kỹ thuật số cho phép chúng ta dễ dàng thu thập, chia sẻ thông tin và hành động trên cơ sở những thông tin này theo phƣơng thức hoàn toàn mới, kéo theo hàng loạt sự thay đổi về các quan niệm, các tập tục, các thói quen truyền thống, và thậm chí cả cách nhìn các giá trị trong cuộc sống. Công nghệ thông tin đã mang lại cho con ngƣời những thành tựu to lớn trong nhiều lĩnh vực đời sống nhƣ xây dựng kiến trúc, y tế, giáo dục, quảng cáo... Đặc biệt trong lĩnh vực khoa học, nhiều ngành cần có sự hỗ trợ của công nghệ thông tin . Một trong những ứng dụng quan trọng trong nghành công nghệ thông tin, đặc biệt trong các đối tƣợng đò họa 2D nhƣ bản đồ địa lí, hình ảnh... là việc dán nhãn cho các đối tƣợng đó. Tự động đặt vị trí nhãn là một lĩnh vực trong trực quan hóa thông tin. Nhãn là các đoạn văn bản nhằm truyền đạt thông tin, làm rõ ý nghĩa của các cấu trúc phức tạp đƣợc biểu diễn ở dạng đồ họa. Bài toán tự động dán nhãn đƣợc xác định là một lĩnh vực nghiên cứu quan trọng. Bài toán này có ứng dụng trong nhiều lĩnh vực bao gồm vẽ bản đồ, hệ thống thông tin địa lý và vẽ đồ thị... Hiện trên thế giới đã có nhiều công trình nghiên cứu về bài toán dán nhãn tự động. Tuy nhiên ở Việt Nam, bài toán này còn đƣợc đề cập đến một cách hạn chế. Từ sự định hƣớng của cán bộ hƣớng dẫn, căn cứ vào sự phát triển và những ứng dụng của bài toán này, tôi đã quyết định lựa chọn đề tài: “ Nghiên Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
2 cứu kỹ thuật dán nhãn cho đối tƣợng 2D ”, bởi đây là một đề tài có mang tính thực tiễn cao và đồng thời mở ra nhiều hƣớng phát triển nghiên cứu. 2.Lịch sử nghiên cứu Những tài liệu đầu tiên đƣợc công bố liên quan đến bài toán dán nhãn là những bài toán dán nhãn cho bản đồ địa lí, do bài toán khi đặc tả bản đồ có hai yếu tố cần phải đặc tả là yếu tố hình và chữ viết. Một trong những công bố đầu tiên liên quan đến bài toán dán nhãn là của Eduard Imhof[7] vào năm 1962, sau này bài toán dán nhãn tự động đƣợc xây dựng bởi một số nhà khoa học nhƣ Pinhas Yoeli[5]…Vào những thập niên 80 lƣợng nghiên cứu đến bài toán dán nhãn tự động có tăng thể hiện qua nhiều bài báo đƣợc công bố, nhiều nhà khoa học trong trong lĩnh vực khác nhau cũng quan tâm đến chủ đề này và nó thuộc lớp bài toán tối ƣu tổ hợp có độ phức tạp tính toán cao. 3.Mục đích đối tƣợng và phạm vi nghiên cứu Bài toán dán nhãn tự động cho một đối tƣợng cụ thể nhƣ bản đồ, đối tƣợng 2D, đối tƣợng 3D… đã đƣợc nghiên cứu và công bố trên thế giới. Tuy nhiên ở Việt Nam chƣa quan tâm đến bài toán này một cách đúng mức. Vì vậy đề tài đƣợc xây dựng với các mục đích: Tìm hiểu về bài toán dán nhãn cho đối tƣợng, thực tiễn ứng dụng của nó trong các lĩnh vực, tìm hiểu một số vấn đề về đồ họa 2D, các thuật toán liên quan từ đó đặt nền tảng nghiên cứu sâu hơn về vấn đề này từ đó thiết kế chƣơng trình thử nghiệm dán nhãn cho một số đối tƣợng 2D. Đối tƣợng và phạm vi nghiên cứu của đề tài là tập chung vào đối tƣợng 2D và các thuật toán dán nhãn tự động. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
3 4. Phƣơng pháp nghiên cứu. Trong luận văn này học viên sử dụng một số phƣơng pháp sau. - Phƣơng pháp lý thuyết - Phƣơng pháp quan sát và tìm hiểu thực tế - Phƣơng pháp phân tích, tổng hợp Với mục đích nghiên cứu, phạm vi và đối tƣợng nghiên cứu đề ra trong luận văn này tôi trình bày một số nội dung nhƣ sau: Với những mục đích nghiên cứu, phạm vi và đối tƣợng nghiên cứu đề ra, trong luận văn này tôi trình bày một số các nội dung đƣợc trình bày và phân bố trong các chƣơng nhƣ sau: Chƣơng 1: Giới thiệu tổng quan về bài toán dán nhãn, tƣ tƣởng chung để giải quyết bài toán trong ba trƣờng hợp: áp dụng cho dán nhãn riêng cho cạnh, riêng cho điểm, cho cả cạnh và điểm. Chƣơng 2: Trình bày một số thuật toán gán nhãn cho bài toán dán nhãn tổng hợp hay bài toán vị trí nhãn các đối tƣợng đồ họa (GFLP: Graphical Feature Label Placement), một tập hợp các điểm (NLP: Node Label Placement), gán nhãn cho một tập hợp các đƣờng hoặc cạnh (ELP: Edge Label Placement), nhiều nhãn trên mỗi đối tƣợng (MLP: Multiple Label Placement), kỹ thuật gán nhãn dựa vào hiệu chỉnh đối tƣợng và kỹ thuật dán nhãn đối tƣợng cách lần theo đƣờng biên; đánh nhãn cho mỗi thành phần; sau đó đánh giá tính đúng đắn và hiệu quả của thuật toán. Chƣơng 3: Chƣơng trình Ở đây, tôi sẽ cài đặt theo thuật toán đƣợc trình bày trong chƣơng 2 là thuật toán lần theo đƣờng biên và đánh nhãn cho các đối tƣợng trong một bức ảnh, chạy minh họa trên ảnh chữ scan hay ảnh tự vẽ, ở dạng đuôi *.pcx. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
4 Chƣơng I. TỔNG QUAN VỀ BÀI TOÁN DÁN NHÃN 1.1.Giới thiệu bài toán Đây là bài toán có ứng dụng trong nhiều lĩnh vực bao gồm đồ họa 2D, vẽ bản đồ, hệ thống thông tin địa lý và vẽ đồ thị. Do quá trình dán nhãn là nhiệm vụ đơn điệu nhƣng lại rất cần thiết nên rất thích hợp cho tự động hóa. Rất khó để định lƣợng tất cả các đặc tính của một vị trí tốt để dán nhãn do những vị trí này còn phụ thuộc vào cảm nhận của con ngƣời nhƣ trực giác và kinh nghiệm..., đặc biệt là khi những cảm giác, kinh nghiệm này đƣợc hoàn thiện qua nhiều thế kỷ bởi những nhà vẽ bản đồ và đƣợc họ nâng lên thành một nghệ thuật. Vì vậy các vị trí nhãn do các hệ thống máy tính cung cấp khó có thể có chất lƣợng tƣơng đƣơng so với làm thủ công bởi những ngƣời làm bản đồ có kinh nghiệm. Tuy vậy vẫn có nhiều lĩnh vực không có nhiều đòi hỏi cao, nghiêm ngặt về tính thẩm mĩ, các kỹ thuật tự động dán nhãn có thể đƣợc áp dụng trong những trƣờng hợp này. Ví dụ có thể áp dụng để dán nhãn tức thời cho những hệ thống thông tin địa lý trực tuyến, tìm kiếm bản đồ trên internet hay một số bản đồ với mục đích đặc biệt khác nhƣ hiển thị điều tra dân số, thăm dò dầu khí, điều tra đất. Hiện tại, các hệ thống tƣơng tác bán tự động có thể là hƣớng tiếp cận phổ biến nhất cho nghiên cứu dán nhãn tự động. Các hệ thống có thể cung cấp các vị trí nhãn, những vị trí này sau đó đƣợc chỉnh sửa thủ công để đạt đƣợc kết quả nhƣ mong muốn. Hơn nữa toàn bộ khái niệm của dán nhãn cho đối tƣợng 2D tự động có thể thay đổi phụ thuộc vào khả năng của máy tính. Đối tƣợng 2D có thể đƣợc thể hiện dƣới dạng điện tử, cho phép tƣơng tác với ngƣời dùng để hiển thị những thông tin theo yêu cầu thay vì hiển thị toàn bộ mọi thông tin. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
5 1.2. Định nghĩa bài toán  là một hình vẽ, F là một tập các đối tƣợng của hình  . Một giải pháp cho bài toán dán nhãn là một cách dán nhãn (ở dạng text hay ký tự) cho mỗi một thành phần f trong F sao cho các thông tin liên quan đƣợc biểu thị ở mức tốt nhất có thể bằng cách xác định những vị trí tốt nhất cho các nhãn. Mỗi một f có thể có rất nhiều vị trí để dán nhãn, cần phải dán nhãn vào vị trí rõ ràng nhất trong số đó. Vị trí dán nhãn tốt có thể hỗ trợ rất nhiều trong việc truyền đạt thông tin và tăng cƣờng tính thẩm mỹ của bức vẽ ban đầu. Rất khó để xác định đƣợc những đặc tính của một vị trí tốt cho nhãn vì chúng phụ thuộc nhiều vào nhận thức trực giác của con ngƣời. Việc dán nhãn sẽ dễ dàng trong trƣờng hợp các đối tƣợng của bức vẽ có vị trí độc lập. Khó khăn xảy ra khi vị trí có thể dán nhãn bị hạn chế bởi sự hiện diện của các đối tƣợng khác gần đó. Thông thƣờng ta không phải chỉ quan tâm tới đặt vị trí của một nhãn cho thích hợp với đối tƣợng của nó mà còn cần chú ý đến cả các nhãn và đối tƣợng khác trong khoảng không gian xung quanh đó. Với một cách dán nhãn chấp nhận đƣợc, các nhãn phải đƣợc đặt ở vị trí sao cho dễ hiểu và thỏa mãn một số yêu cầu thẩm mĩ cơ bản. Theo một số ngƣời vẽ bản đồ chuyên nghiệp nhƣ Imhof [7], vị trí tốt nhất dành cho nhãn phải thỏa mãn một số luật sau: nhãn dễ đọc, có thể xác định vị trí nhanh chóng, nhãn và đối tƣợng của nó dễ đƣợc nhận diện, nhãn phải đặt rất gần với đối tƣợng của nó, nhãn không đƣợc che vào nhãn hay các đối tƣợng khác, nhãn phải đƣợc đặt vào vị trí tốt nhất trong số những vị trí thỏa mãn. Tổng quát lại, ta đánh giá chất lƣợng ghi nhãn theo ba luật cơ bản sau đây: - Không có sự chồng chéo giữa các nhãn, các đối tƣợng trong hình vẽ. - Mỗi nhãn có thể dễ dàng đƣợc xác định là của đối tƣợng nào trong hình vẽ. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
6 - Mỗi nhãn phải đƣợc đặt ở vị trí ƣu tiên nhất trong số những vị trí có thể (thứ tự ƣu tiên của những vị trí này có thể đa dạng, tùy thuộc vào từng ứng dụng). Thứ tự ƣu tiên cho các vị trí nhãn có thể đặt tùy thuộc vào ứng dụng cụ thể. Trong vẽ bản đồ địa lí, vị trí của nhãn thông thƣờng đƣợc ƣu tiên ở ngay phía trên, bên phải của đối tƣợng. Hình 1.1. (a) Dán nhãn điểm, (b) Dán nhãn cạnh, (c) Dán nhãn vùng Ví dụ, hình 1.1.a, mỗi vị trí có thể dán nhãn đƣợc đánh số theo thứ tự ƣu tiên. Nhãn có thể chạm nhƣng không đƣợc chồng lên đối tƣợng của nó hay bất cứ đối tƣợng nào khác. Trong trƣờng hợp dán nhãn cho cạnh, nhãn đƣợc phép chạm vào cạnh nhƣng không đƣợc chồng lên đối tƣợng khác. Hình 1.1.b, đối tƣợng cần dán nhãn là một cạnh, nhãn A, B, D là chấp nhận đƣợc. Nhãn C chồng lên cạnh mà nó chú thích cũng có thể chấp nhận đƣợc (với một “giá” thích hợp). Một cách dán nhãn cho một khu vực, nhãn có thể trải rộng trên khu toàn vực đó, tƣơng ứng với hình dạng của khu vực (hình 1.1.c). Thông thƣờng, với bản hình vẽ 2D, một tập luật khác sẽ chi phối vị trí nhãn. Những luật này phụ thuộc vào từng ứng dụng cụ thể và phải theo sự miêu tả của ngƣời dùng. Ngƣời dùng cần có khả năng hiệu chỉnh các luật của chất lƣợng nhãn để đạt đƣợc yêu cầu mong đợi. Ví dụ, nếu cần dán nhãn cho một cạnh, nhãn có liên quan tới đỉnh nguồn thì phải đƣợc đặt gần đỉnh nguồn tránh gây hiểu nhầm. Mọi thuật toán dán nhãn thành công đều phải tính đến sở thích của ngƣời dùng. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
7 Định nghĩa bài toán dán nhãn Kí hiệu: Cho một tập F những đối tƣợng của một bản đồ hay bức vẽ cần đƣợc dán nhãn. Ta định nghĩa một số ký hiệu sau:  f : tập tất cả các vị trí nhãn của đối tƣợng f trong F.  : tập các vị trí nhãn của mọi đối tƣợng cần đƣợc dán nhãn.  : F   : là hàm gán vị trí nhãn trong  cho đối tƣợng đồ thị f trong F. Bài toán dãn nhãn có thể đƣợc nhìn dƣới dạng bài toán tối ƣu với nhiệm vụ là tìm cách dán nhãn sao cho tổng chi phí là nhỏ nhất (trong đó mỗi đối tƣợng đều có một vị trí nhãn gắn cho nó). Mỗi vị trí nhãn  f đƣợc chọn trong kết quả cuối đƣợc gán cho một giá trị chi phí. COST:   N là hàm gán cho  f giá trị chi phí tƣơng ứng với chất lƣợng của nó. Định nghĩa: Instance: F là một tập các đối tƣợng cần đƣợc dán nhãn. Question: Tìm một phép dán nhãn cho hàm sau là nhỏ nhất:   COST( (i))P(i,j) iF ji 1, neáu  (i )  j Với: P(i, j )   0, tröôøng hôïp coøn laïi và   P(i, j) | F | , trong đó  P(i, j)  1, i  F iF ji ji 1.3. Tƣ tƣởng chung giải quyết bài toán dán nhãn Hầu hết nghiên cứu về bài toán dán nhãn gần đây tập trung vào dán nhãn cho đối tƣợng của bản đồ vật lý và bản đồ kỹ thuật. Bài toán vị trí nhãn thƣờng chia làm ba loại: (a) dán nhãn điểm (VD : các thành phố,...), (b) dán nhãn cạnh/đoạn thẳng (đƣờng, sông,...), (c) dán nhãn khu vực (hồ, đại dƣơng...). Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
8 Đã có nhiều nghiên cứu phát triển bài toán dán nhãn cho điểm (NLP: Node Label Placement)[5]. Đồng thời, bài toán dán nhãn cạnh (ELP: Edge Label Placement) cũng đƣợc đề cập đến trong nhiều nghiên cứu [8]. Bài toán dán nhãn tổng quát (dán nhãn cho điểm, cạnh, khu vực; GFLP: Graphical Feature Label Placement) đƣợc đề cập tới chủ yếu trong lĩnh vực vẽ bản đồ, tuy nhiên cũng có ứng dụng trực tiếp trong lĩnh vực vẽ đồ thị. Trong nhiều ứng dụng thực tế, mỗi đối tƣợng có thể có nhiều nhãn. Chẳng hạn khi đối tƣợng có thể rất lớn, dài hay có nhiều thuộc tính. Đây là bài toán dán nhiều nhãn cho một đối tƣợng (MLP: Multiple Label Placement). Với bản đồ địa lí hay bản đồ kĩ thuật, các vị trí, chi tiết là cố định, không cho phép thay đổi. Tuy nhiên với bản vẽ đồ thị, thuật toán có thể đƣợc phép thay đổi cách bố trí để lấy không gian cho nhãn. Cả hai bài toán NLP và ELP đều có độ phức tạp là NP hard, cần dựa vào các giải thuật heuristic để tìm lời giải cho các bài toán thực tế. Nhiều loại giải thuật đã đƣợc sử dụng để giải bài toán dán nhãn trong đó ngƣời ta thƣờng dựa vào một số nguyên lý cơ sở nhƣ sau: Nguyên lý vét cạn thông minh, nguyên lý tham lam, nguyên lý thứ tự... Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
9 Chƣơng 2. MỘT SỐ THUẬT TOÁN DÁN NHÃN ĐỐI TƢỢNG 2.1. Thuật toán dán nhãn điểm GFPL Giới thiệu Các nghiên cứu giải quyết các bài toán dán nhãn đã đƣợc tập trung vào việc dán nhãn nhãn cho đối tƣợng 2D trong tập thành phần các đối tƣợng 2D.Thành phần kết nối dán nhãn quét một hình ảnh và các nhóm điểm ảnh của nó thành các thành phần dựa trên kết nối pixel, tức là tất cả các điểm ảnh trong một thành phần chia sẻ kết nối tƣơng tự nhƣ giá trị cƣờng độ pixel và trong một số cách kết nối với nhau. Một khi tất cả các nhóm đã đƣợc xác định, mỗi điểm ảnh đƣợc dán nhãn với một màu ghi nhãn theo các thành phần đƣợc phân công. Khi nghiên cứu để giải quyết bài toán dán nhãn cho một tập hợp các điểm hoặc các nút, bài toán vị trí nút nhãn. Bài toán ghi nhãn tổng hợp, bài toán vị trí nhãn với các tính năng đồ họa (GFLP:Graphical Feature Label Placement) nơi một đặc điểm đồ họa có thể là một điểm, đƣờng, hoặc khu vực. Quá trình dán nhãn không đƣợc phép sửa đổi các hình học cơ bản của của đối tƣợng 2D vì đó là cố định. Và cũng khó có thể sửa đƣợc mô hình dựng sẵn trong 2D. Hầu hết các giải thuật dán nhãn của GFLP sử dụng thuật toán tìm kiếm vét cạn. Các thuật toán này hoạt động tốt cho các bài toán số liệu nhỏ. Những phƣơng pháp này sử dụng kỹ thuật không tối ở một số khía canh và đƣợc xác minh trong một số bài toán. Trên thực tế, những phƣơng pháp này sử dụng phƣơng pháp tiếp cận dựa trên nguyên tắc để đánh giá tốt vị trí nhãn và biến thể của tìm kiếm theo chiều sâu để khám phá các cấu hình ghi nhãn khác nhau. Cách tiếp cận dùng để mô phỏng, để tìm giải pháp cho bài toán gán nhãn chung, và nó tách biệt các kiến thức về 2D, nó cần thiết để nhận biết các vị trí Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
10 nhãn tốt nhất từ các quy trình tối ƣu hóa cần thiết để tìm thấy chúng. Tất cả các kỹ thuật ở trên cho bài toán dán nhãn tổng hợp đầu tiên tạo ra một nhãn ban đầu mà trong đó cuộc xung đột giữa các nhãn đƣợc phép. Sau đó chúng đƣợc giải quyết bằng định vị lại dán nhãn cho đến khi tất cả các cuộc xung đột đƣợc giải quyết, hoặc không cải thiện hơn nữa có thể đạt đƣợc. Hơn nữa chúng bắt đầu với một thiết lập ban đầu khá nhỏ của của các vị trí nhãn, vị trí tiềm năng mà từ đó họ lấy để dán nhãn cuối cùng. Việc thực hiện các kỹ thuật giảm khi số lƣợng các vị trí các nhãn có khả năng. Đôi khi bài toán dán nhãn đƣợc chuyển thành bài toán kết hợp (Matching problem)[7]. Nền chung của kỹ thuật này khá linh hoạt, có thể đƣợc hiệu chỉnh theo các yêu cầu dán nhãn cụ thể. Khái quát thuật toán Kỹ thuật dán nhãn đƣợc chuyển thành một bài toán tổng hợp. Nội dung của kỹ thuật này là có thể linh hoạt tùy chỉnh cho yêu cầu dán nhãn cụ thể. Trong phần tiếp theo kỹ thuật này đƣợc trình bày chi tiết hơn. *Thuật toán gán nhãn cơ bản GFLP Thuật toán dán nhãn cơ bản: Input: Một bức vẽ  , tập F các đối tƣợng cần dán nhãn. Output: Một phép dán nhãn không bị chồng chéo. 1. Chọn lọc một tập các vị trí có thể đặt dán nhãn (vị trí tiềm năng) cho từng đối tƣợng trong F. 2. Tập này đƣợc loại bớt bằng cách loại bỏ những nhãn bị chồng chéo nhiều. Những nhãn còn lại đƣợc phân nhóm sao cho nếu hai nhãn chồng chéo nhau thì đƣợc cho vào một nhóm. 3. Chọn vị trí cho nhãn bằng cách giải quyết biến thể của bài toán kết hợp, trong đó nhiều nhất chỉ một vị trí nhãn trong mỗi nhóm đƣợc lựa chọn. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
11 Ba bƣớc cơ bản của các thuật toán dán nhãn đƣợc trình bày chi tiết: + Kết hợp nhãn vào các đối tƣợng đồ họa Định nghĩa đồ thị kết hợp nhƣ sau: Cho hình  , một tập F các đối tƣợng cần dán nhãn, một tập  các vị trí nhãn của F, đồ thị kết hợp Gm (V f ,Vc , Em ) đƣợc định nghĩa nhƣ sau: - Mỗi điểm trong Vf tƣơng ứng với một đối tƣợng trong F. - Mỗi điểm trong Vc tƣơng ứng với một nhóm các nhãn trùng nhau. - Mỗi cạnh (i,j) trong Em nối đỉnh i trong Vf với đỉnh j trong Vc nếu và chỉ nếu đối tƣợng tƣợng cần dán nhãn i có vị trí nhãn nằm trong j (j tƣơng ứng với một nhóm các vị trí nhãn trùng nhau). Chú ý rằng Gm là đồ thị lƣỡng phân, giá của việc dán nhãn l cho đối tƣợng f là trọng số của cạnh (f,l) trong đồ thị Gm. Vậy lời giải tối ƣu cho bài toán là một đồ thị con của Gm sao cho hai cạnh bất kì không chung đỉnh đầu, cuối, tổng số cạnh là nhiều nhất và tổng trọng số là nhỏ nhất (maximum cardinality minimum weight matching). Có thể đánh giá đƣợc độ khó của bài toán dán nhãn thông qua biểu diễn bài toán bằng một đồ thị lƣỡng phân. Bài toán dán nhãn rất gần với bài toán tìm tập con độc lập. Xét trƣờng hợp đơn giản, nếu mỗi đối tƣợng chỉ có một vị trí có thể dán nhãn, bài toán trở thành tìm tập con độc lập lớn nhất. Khi đã thiết lập đƣợc các nhóm, việc xây dựng đồ thị kết hợp là hoàn toàn có thể. Việc tìm phép dán nhãn cuối cùng là tìm đồ thị con của Gm sao cho hai cạnh bất kì không chung đỉnh đầu, cuối, tổng số cạnh là nhiều nhất và tổng trọng số là nhỏ nhất. Đã có một số giải thuật hiệu quả cho bài toán này. Độ lớn của đồ thị kết hợp phụ thuộc vào cỡ của hình đầu vào, cỡ tập  của các nhãn và mật độ chồng chéo. Nhiều nhất chỉ một vị trí nhãn trong mỗi nhóm đƣợc lựa chọn vào lời giải vì vậy một phép kết hợp của đồ thị Gm sẽ là một cách dán nhãn không có chồng chéo, giá của mỗi vị trí nhãn sẽ chỉ phụ Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
12 thuộc vào hạng của nhãn. Có nghĩa là có thể xác định giá của vị trí nhãn qua một bƣớc tiền xử lý. + Chọn vị trí nhãn Để tìm một tập hợp các vị trí nhãn riêng biệt cho từng đặc điểm đối tƣợng đồ họa, ta phải có một số tính toán phù hợp. Cho điểm thì một số vị trí nhãn nhãn chạm vào điểm tƣơng ứng phải đƣợc xác định. Trong các thuật toán đƣợc nêu ra thì một tập các vị trí nhãn phải có tiềm năng liên kết với mỗi điểm. Hình 2.1. Bản vẽ hướng nơi nhãn được định vị bằng các kỹ thuật phù hợp cho kỹ thuật GFLP. Các nhãn được đặt song song với trục ngang. Hộp màu xám là nút nhãn và hộp trắng cạnh nhãn Nhƣ hình. 2.1 nó minh họa cho một số điểm cách đều nhau trên mỗi cạnh cho trƣớc  i đã đƣợc xác định. Mỗi nhãn đƣợc dán vị trí  i có liên quan đến chính xác với một trong các điểm i, vì vậy mà một trong các góc của nhãn  i trùng với điểm i. Hơn nữa, nhãn  i không chồng chéo lên đặc điểm đồ họa tƣơng ứng của nó hoặc bất kỳ tính năng đồ họa khác (ngoại trừ các vị trí nhãn khác). Có thể ta sẽ có phƣơng pháp tiếp cận cho việc tìm kiếm một thiết lập ban đầu của trị trí nhãn cho ngang cạnh. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn