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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.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.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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
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 *. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 Chƣơng I. TỔNG QUAN VỀ BÀI TOÁN DÁN NHÃN 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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Đị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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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ể.