MỞ ĐẦU 1. Lí do chọn đề tài 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, bản đồ (đƣờng đi, dầu mỏ. Đặ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 nhƣ nghiên cứu địa lí, sinh, hóa học,. Một trong những ứng dụng quan trọng, đặc biệt trong địa lí, là việc gán nhãn cho các loại bản đồ, hay chú thích các loại sơ đồ, đồ thị.
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 gán nhãn đƣợc xác định là một lĩnh vực nghiên cứu quan trọng của ACM Computational Geometry Task Force (Đội tính toán hình học ACM): “Gán nhãn là nguồn của nhiều bài toán tối ưu hóa hình học. Ngay cả khi nhãn được đặt vào vị trí cố định tương ứng với một điểm, đây vẫn là bài toán NP-hard.
Các bản đồ cần được gán nhãn, vậy cần có các giải thuật hiệu quả, giải thuật heuristics để xác định những ràng buộc, vị trí có thể.”1 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 gá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, học viên đã quyết định lựa chọn đề tài: 1 “Label placement is a source of many geometric optimization problems.
Even when labels are to be placed in fixed positions relative to point features these are typically NP-hard. Since maps do need labels, heuristics and efficient algorithms for identifying constraints and possible positions are needed.” – Application Challenges to Computational Geometry, CG Impact Task Force Report, pp. Số hóa bởi Trung tâm Học liệu http://www.vn/ 2 “MỘT SỐ KỸ THUẬT GÁN NHÃN ĐỐI TƢỢNG TRONG ẢNH VÀ ỨNG DỤNG”, 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 Tài liệu đầu tiên có liên quan tới bài toán gán nhãn có thể là một bản đồ địa lí, do bản đồ luôn bao gồm hai yếu tố hình vẽ và chữ viết.
Bằng chứng đầu 1 tiên là một tấm bản đồ ƣớc chừng khoảng 2300 năm trƣớc, với tỉ lệ xích 500 của vùng ngày nay là miền nam thị trấn Heibei ở Trung Quốc. Bài báo đầu tiên về bài toán gán nhãn đƣợc công bố năm 1962 bởi Eduard Imhof [4], ngƣời đã đặt ra các nguyên tắc cho chất lƣợng của bản đồ. Trƣớc đó, những ngƣời vẽ bản đồ đánh giá chất lƣợng một tấm bản đồ đƣợc gán nhãn tốt hay không tốt hoàn toàn chỉ dựa vào kinh nghiệm. Mƣời năm sau, Pinhas Yoeli lần đầu tiên thử xây dựng một hệ thống gán nhãn tự động [11].
Trong khoảng gần hai thập kỉ sau đó, có rất ít nghiên cứu về bài toán gán nhãn tự động. Tuy nhiên vào đầu những thập niên 80, lƣợng nghiên cứu về lĩnh vực gán nhãn tự động tăng đáng kể, thể hiện qua số lƣợng các bài báo đã đƣợc công bố. Nhiều nhà khoa học trong các lĩnh vực khác nhƣ tính toán hình học hay vẽ đồ thị cũng quan tâm tới chủ đề này. Độ phức tạp của bài toán gán nhãn thuộc lớp NP-Hard nên đã có nhiều hƣớng tiếp cận đƣợc đề cập nhƣ trong [10].
Mục đích, đối tƣợng và phạm vi nghiên cứu Bài toán gán nhãn đã đƣợc đề cập, nghiên cứu nhiều trên thế giới. Tuy nhiên ở Việt Nam dƣờng nhƣ còn chƣa chú trọng nhiều tới bài toán này. Vì vậy, đề tài này đƣợc xây dựng với các mục đích: Tìm hiểu về bài toán gán nhãn, ứng dụng của nó trong các lĩnh vực; Tìm hiểu một số vấn đề, các thuật Số hóa bởi Trung tâm Học liệu http://www.vn/ 3 toán liên quan; Đặt nền tảng cho cá nhân nghiên cứu, tìm hiểu sâu hơn về vấn đề này. Từ đó thiết kế một chƣơng trình thử nghiệm gán nhãn cho một hình vẽ cụ thể.
Đối tƣợng và phạm vi nghiên cứu của đề tài tập chung vào các loại bản đồ địa lí, đồ thị. Phƣơng pháp nghiên cứu Trong Luận văn này tôi sử dụng một số các phƣơng pháp sau: - Phƣơng pháp quan sát, tìm hiểu thực tế. - Phƣơng pháp lý thuyết. - Phƣơng pháp phân tích tổng hợp.
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 khái quát xử lý ảnh, một số vấn đề cơ bản. Trình bày tổng quan về bài toán gán nhãn cho đối tƣợng trong ảnh. Chƣơng 2: Trình bày một số thuật toán gán nhãn cho bài toán ghi 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) và kỹ thuật gán nhãn dựa vào hiệu chỉnh đối tƣợng. Chƣơng 3: Chƣơng trình Số hóa bởi Trung tâm Học liệu http://www.vn/ 4 Ở đây, tôi sẽ cài đặt theo thuật toán đƣợc trình bày trong chƣơng 2 tìm vị trí thích hợp nhất khi phóng to và thu nhỏ ảnh để hiển thị nhãn tối đa cho các đối tƣợng trong một bức ảnh.
Số hóa bởi Trung tâm Học liệu http://www.vn/ 5 Chƣơng 1 KHÁI QUÁT VỀ XỬ LÝ ẢNH VÀ BÀI TOÁN GÁN NHÃN ĐỐI TƢỢNG Trong ngành khoa học máy tính, xử lý ảnh là một dạng của xử lý tín hiệu cho đầu vào là một ảnh hoặc các frame của phim ảnh. Đầu ra có thể là một hình ảnh, hoặc tập hợp các ký tự hoặc các tham số liên quan tới hình ảnh. Thƣờng thì kỹ thuật xử lý ảnh có liên quan tới xử lý tín hiệu hai chiều và đƣợc áp dụng bằng một chuẩn riêng về kỹ thuật xử lý ảnh cho nó. Các khái niệm cơ bản để xử lý tín hiệu nhƣ, khái niệm về tích chập, các biến đổi Fourier, biến đổi Laplace, các bộ lọc hữu hạn,… Ngoài ra còn cần tới các công cụ toán học nhƣ đại số tuyến tính, thống kê.
Và một số kiến thức cần thiết nhƣ trí tuệ nhân tao, mạng nơron nhân tạo cũng đƣợc đề cập trong quá trình phân tích và xử lý ảnh. Khái quát về xử lý ảnh Cũng nhƣ xử lý dữ liệu bằng đồ hoạ, xử lý ảnh là một lĩnh vực của tin học ứng dụng. Xử lý dữ liệu bằng đồ họa đề cập đến những ảnh nhân tạo, các ảnh này đƣợc xem xét nhƣ là một cấu trúc dữ liệu và đƣợc tạo ra bởi các chƣơng trình. Xử lý ảnh bao gồm các phƣơng pháp và kỹ thuật để biến đổi, để truyền tải hoặc mã hóa các ảnh tự nhiên.
Mục đích của xử lý ảnh gồm: Thứ nhất: biến đổi ảnh và làm đẹp ảnh. Thứ hai: tự động nhận dạng ảnh hay đoán nhận ảnh và đánh giá các nội dung của ảnh. Nhận dạng ảnh là quá trình liên quan đến các mô tả đối tƣợng mà ngƣời ta muốn đặc tả nó. Quá trình nhận dạng thƣờng đi sau quá trình trích chọn các đặc tính chủ yếu của đối tƣợng.
Có hai kiểu mô tả đối tƣợng: - 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). Số hóa bởi Trung tâm Học liệu http://www.vn/ 6 Nhận biết và đánh giá các nội dung của ảnh là sự phân tích một hình ảnh thành những phần có nghĩa để phân biệt đối tƣợng này với đối tƣợng khác. Dựa vào đó ta có thể mô tả cấu trúc của hình ảnh ban đầu.
Có thể liệt kê một số phƣơng pháp nhận dạng cơ bản nhƣ nhận dạng biên của một đối tƣợng trên ảnh, tách cạnh, phân đoạn hình ảnh,. Kỹ thuật này đƣợc sử dụng nhiều trong y học (xử lý tế bào, nhiễm sắc thể). Trong thực tế ngƣời ta đã áp dụng kỹ thuật nhận dạng khá thành công với nhiều đối tƣợ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). Nhận dạng chữ in hoặc đánh máy trong văn bản phục vụ cho việc tự động hoá quá trình đọc tài liệu, tăng nhanh tốc độ và chất lƣợng thu nhận thông tin từ máy tính, nhận dạng chữ viết tay (với mức độ ràng buộc khác nhau về cách viết, kiểu chữ,.
Xử lý ảnh là gì? Con ngƣời thu nhận thông tin qua các giác quan, trong đó thị giác đóng vai trò quan trọng nhất. Những năm trở lại đây với sự phát triển của phần cứng máy tính, xử lý ảnh và đồ hoạ đó phát triển một cách mạnh mẽ và có nhiều ứng dụng trong cuộc sống. Xử lý ảnh và đồ hoạ đóng một vai trò quan trọng trong tƣơng tác ngƣời máy. Xử lý ảnh đƣợc xem nhƣ là quá trình thao tác ảnh đầu vào nhằm cho ra kết quả mong muốn.
Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh “tốt hơn” hoặc một kết luận. Ảnh “Tốt hơn” Ảnh đầu vào XỬ LÝ ẢNH Kết luận Hình 1. Quá trình xử lý ảnh 1. Các giai đoạn chính trong xử lý ảnh Giai đoạn xử lý ảnh đƣợc mô tả bằng sơ đồ sau: Số hóa bởi Trung tâm Học liệu http://www.vn/ 7 Biểu diễn và Phân đoạn mô tả ảnh Tiền xử lý ảnh CƠ SỞ TRI THỨC Nhận dạng Thu nhận và giải thích Hình 1.
Quá trình xử lý ảnh Thu nhận ảnh: Đây là công đoạn đầu tiên mang tính quyết định đối với quá trình xử lý ảnh. Ảnh đầu vào sẽ đƣợc thu nhận qua các thiết bị nhƣ camera, sensor, máy quét, vv… và sau đó các tín hiệu này sẽ đƣợc số hóa. Các thông số quan trọng ở bƣớc này là độ phân giải, chất lƣợng màu, dung lƣợng bộ nhớ và tốc độ thu nhận ảnh của các thiết bị. Tiền xử lý: Ở bƣớc này ảnh sẽ đƣợc cải thiện về độ tƣơng phản, khử nhiễu, khử bóng, khử độ lệch, vv… với mục đích làm cho chất lƣợng ảnh trở nên tốt hơn và thƣờng đƣợc thực hiện bởi các bộ lọc.
Phân đoạn ảnh: Phân đoạn ảnh là bƣớc then chốt trong xử lý ảnh, giai đoạn này nhằm phân tích ảnh thành những thành phần có cùng tính chất nào đó, dựa theo biên hay các vùng liên thông.
