Đặt vấn đề Cuộc sống ngày càng phát triển, con người ngày càng xây dựng nhiều công trình phức tạp, sản xuất máy móc linh kiện đòi hỏi độ chính xác cao. Để làm được những điều này đòi hỏi cần có nhiều các bản vẽ đồ họa mô tả chính xác từ những chi tiết nhỏ nhất. Bản vẽ kĩ thuật (gọi tắt là bản vẽ) trình bày thông tin kĩ thuật của sản phẩm dưới dạng các hình vẽ và các kí hiệu theo các quy tắc thống nhất và thường vẽ theo tỉ lệ. Mỗi lĩnh vực kĩ thuật có loại bản vẽ riêng, trong đó có một số loại được sử dụng rất nhiều như bản vẽ xây dựng, bản vẽ cơ khí vv.1 là một ví dụ về bản vẽ mô tả thiết kế hệ thống mạch điện bao gồm nhiều thông tin như tụ điện, điện trở, bóng bán dẫn.2 ví dụ về bản vẽ mô tả thiết kế kiến trúc gồm nhiều biểu tượng như cửa, cửa sổ, ghế, bàn vv.1: Ví dụ về dữ liệu ảnh đồ họa bản vẽ kĩ thuật điện Ban đầu, quá trình xây dựng, phác thảo lên các bản vẽ này được thực hiện thủ công bởi các kỹ sư.
Theo thời gian cùng với sự phát triển của công nghệ thì các kỹ sư sử dụng những phần mềm hiện đại như AutoCad để thiết kế bản và lưu trữ các bản vẽ. Tuy nhiên vẫn còn rất nhiều các tài liệu về bản vẽ cũ cần được lưu trữ và sắp xếp phân loại lại để phục vụ cho các mục đích tra cứu, xử lý phân tách phần đồ họa và văn bản trên ảnh đồ họa. Để làm được việc này thì đa phần hiện nay người ta chỉ có thể làm thủ công thu thập và sắp xếp bằng tay. Ngoài ra, tất cả các bản vẽ hiện tại vẫn chỉ để giúp các kĩ sư đọc hiểu và dự toán một cách thủ công, cần có một công cụ giúp tự động hóa quy trình dự toán này một cách chính xác và nhanh chóng giúp tiết kiệm thời gian, công sức và mang lại hiệu quả kinh tế cao hơn.2: Ví dụ về dữ liệu ảnh đồ họa bản vẽ kiến trúc Luận văn tập trung tìm hiểu và đề xuất phương pháp giải quyết về bài toán nhận dạng ký hiệu trên dữ liệu ảnh đồ họa kiến trúc.
Cụ thể là với mỗi ảnh tài liệu và một biểu tượng đầu vào sẽ cho ra kết quả là danh sách các vùng ứng viên giống biểu tượng ở trong ảnh nhất. Việc thực hiện xử lý nhận dạng nhằm trích xuất các thông tin trên bản vẽ kĩ thuật xây dựng với mong muốn tăng tự động hóa để tăng năng suất và giảm bớt thời gian cho việc dự toán công trình cũng như lưu trữ để việc tra cứu tài liệu được thuận tiện hơn.2 Các hướng tiếp cận trong nhận dạng biểu tượng Nhận dạng biểu tượng là một vấn đề phức tạp, ngày càng được cộng đồng nghiên cứu về nhận dạng đồ họa quan tâm. Về cơ bản có năm hướng nghiên cứu chính đang được nhiều nhóm nghiên cứu theo đuổi được liệt kê như trong bảng 1. 3 STT Hướng tiếp cận Ưu điểm Nhược điểm 1 Mô hình Markov ẩn Có khả năng xử lý trong Cần phải huấn luyện cho mô [1, 2, 3] trường hợp ảnh bị nhiễu khá hình tốt 2 Đặc trưng điểm ảnh Có khả năng biểu diễn tốt các Cần phân đoạn trước các biểu [4] ký hiệu và tốc độ tính toán tượng đặc biệt nhanh 3 Dựa trên đồ thị Phân đoạn và nhận dạng ký Khối lượng tính toán lớn [5, 6] hiệu đồng thời 4 Chữ kí biểu tượng Mô tả biểu tượng đơn giản, Khả năng xử lý nhiễu chưa tốt [7] khả năng tính toán nhanh Giảm hiệu năng nếu ký tự không được phân đoạn tốt 5 Biểu diễn kí hiệu Tránh việc so sánh tuyến tính Cấu trúc phân cấp Dendo- theo cấu trúc phân bằng cách sử dụng kĩ thuật gram phụ thuộc nhiều vào cấp đánh chỉ số tiêu chí hợp nhất [8] Bảng 1.1: Bảng thống kê các phương pháp phát hiện đối tượng Dưới đây là phân tích cụ thể hơn về cách thức vận hành cũng như ưu nhược điểm của từng nhóm phương pháp được đề xuất.1 Mô hình Markov ẩn Nhóm các mô hình Markov ẩn (HMM) là hướng tiếp cận biểu diễn các mô hình động có sự thay đổi về không gian và thời gian[1].Ưu điểm chính của mô hình này là phân loại chuỗi không gian, là kết quả từ khả năng căn chỉnh một mẫu dọc theo các trạng thái của chúng bằng cách sử dụng mật độ xác suất (pdf) cho mỗi trạng thái, ước tính 4 xác suất của một phần nhất định của mẫu thuộc về trạng thái.
HMM đã được áp dụng thành công để nhận dạng chữ viết tay [2], trong đó các ký tự biểu diễn các mẫu thay đổi trong không gian khi di chuyển từ trái sang phải. Ngoài ra, HMM đã được áp dụng cho các bài toán phân loại hình ảnh và nhận dạng hình thể [3]. Muller và Rigoll [9] đề xuất HMM 2-D để mô hình hóa sự sắp xếp hai chiều của các đối tượng tượng trưng. Đây là một trong những cách tiếp cận đầu tiên có thể xác định đối với ký hiệu đánh dấu, trong đó tài liệu được phân vùng bằng một lưới có kích thước cố định,trong đó mỗi ô nhỏ được nhập vào một mô hình HMM 2D để xác định các vị trí có thể tìm thấy các ký hiệu từ cơ sở dữ liệu mô hình.
HMM 2D không cần phân đoạn trước và có thể sử dụng trong các điều kiện nhiễu.2 Các phương pháp đặc trưng điểm ảnh Đặc trưng điểm ảnh là tập hợp các phương pháp sử dụng các tính chất của điểm ảnh để phát hiện các ký hiệu [4]. Để giảm độ phức tạp tính toán, người ta thường trích chọn và xây dựng bộ mô tả các đặc trưng trên một số vùng của tài liệu. Những vùng này có thể được xây dựng dựa trên của sổ trượt hoặc các công cụ xác định các điểm đặc trưng cần chú trọng trong không gian ảnh. Các đặc trưng này sẽ lại đại diện thể hiện cho vùng quan tâm.
Để phân loại được chính xác cần một quá trình phân đoạn trên ảnh đồ họa ban đầu để trích xuất các vùng không gian có đối tượng cụ thể. Các bộ mô tả các đối tượng dựa trên các pixel cơ bản sẽ được tính toán tại mỗi vị trí tuần tự và so sánh với các ký hiệu. Nhờ việc trích trọn đặc trưng này khiến cho tốc độ tính toán của phương pháp là rất nhanh. Tuy nhiên so khớp một-một là hạn chế của phương pháp, bước phân đoạn dựa trên các điểm đặc trưng cũng chỉ cho phép nó hoạt động với một tập giới hạn các ký hiệu.3 Dựa trên đồ thị Hướng tiếp cận dựa trên đồ thị là nhóm các phương pháp dựa trên biểu diễn cấu trúc của các đối tượng đồ họa và sử dụng kỹ thuật xây dựng bản đồ để phát hiện các ký hiệu trong tài liệu.
Đối sánh đồ thị có thể được giải quyết bằng cách tiếp cận đối sánh cấu trúc trong miền đồ thị hoặc được giải quyết bằng bộ phân loại thống kê trong không gian vectơ nhúng của đồ thị. Trong cả hai trường hợp, các kỹ thuật này bao gồm một mô hình lỗi cho phép đối sánh đồ thị không chính xác để chịu được nhiễu cấu trúc trong tài liệu. Có rất nhiều phương pháp dựa trên đồ thị [5, 6] vv. Nói chung, các thuộc tính cấu trúc của các thực thể đồ họa được mã hóa dưới dạng đồ thị và sau đó một thuật toán xác định đồ thị con được áp dụng để tìm kiếm hoặc nhận dạng ký hiệu trong tài liệu.
Các thuật toán so khớp đồ thị kết hợp một số mô hình nhiễu để thể hiện sự biến dạng của hình ảnh. Vì so khớp đồ thị là một bài toán khó để tính toán được kết quả tuyệt đối( NP hard) [10], các thuật toán này thường có thời gian tính toán rất lớn. Trong số các phương pháp đã nghiên cứu, Messmer và Bunke trong [?] đã biểu diễn các ký hiệu đồ họa và bản vẽ đường bằng đồ thị quan hệ thuộc tính (AGR). Sau đó, quá trình nhận dạng các bản vẽ được thực hiện dưới dạng các đồng dạng biểu đồ con có khả năng chịu lỗi từ biểu đồ ký hiệu truy vấn đến biểu đồ vẽ.
Llados và cộng sự [6] đề xuất đồ thị tiếp cận vùng (RAG) cho các ký hiệu nhận dạng trong biểu đồ vẽ tay. Chúng đại diện cho các vùng trong biểu đồ bằng các đường đa tuyến trong đó tập hợp các thao tác chỉnh sửa được xác định để đo mức độ giống nhau giữa các chuỗi theo chu kỳ tương ứng với các đường đa tuyến.4 Chữ kí biểu tượng Tương tự như hướng tiếp cận sử dụng đặc trưng của điểm ảnh thì nhóm các phương pháp chữ kí biểu tượng cũng hoạt động với cơ chế phân đoạn đặc biệt. Tuy nhiên, thay vì phân đoạn các vùng không gian ảnh dựa trên các điểm đặc trưng thì ý tưởng là sử dụng tính toán các vector [7]. Các vector được sử dụng thường là sự kết hợp của các 6 đặc trưng cơ bản của ảnh như các nút trên đồ thị, quan hệ giữa các điểm đặc trưng hoặc độ dài của các cạnh vv.
Do đó các vector thể hiện tốt hơn đặc tính cấu trúc của đối tượng và được coi là "chữ ký" thể hiện bản chất riêng của các đối tượng. Các phương pháp này được xây dựng dựa trên giả định rằng các ký hiệu luôn nằm trong vùng quan tâm và tính toán các ký hiệu vectơ bên trong các vùng đó. Vì "chữ ký" biểu tượng bị ảnh hưởng nhiều bởi nhiễu hình ảnh, các phương pháp này không hoạt động tốt trong các ứng dụng trong thế giới thực.5 Biểu diễn kí hiệu phân cấp Biểu diễn kí hiệu phân cấp [8] là nhóm các phương pháp dựa trên định nghĩa thứ bậc của các ký hiệu, trong đó chúng phân tách các ký hiệu một cách phân cấp và tổ chức các phần của ký hiệu trong một mạng hoặc cấu trúc biểu đồ. Về cơ bản, các ký hiệu được phân tách tại các điểm giao nhau và mỗi phần trong số các phần con được mô tả sử dụng một bộ mô tả hình dạng riêng.
Các phần con một lần nữa được hợp nhất bằng thước đo mật độ, xây dựng cấu trúc dạng biểu đồ. Sau đó sử dụng các cấu trúc mạng để tìm các vùng quan tâm của các đường đa tuyến nơi biểu tượng truy vấn có khả năng xuất hiện.3 Một số phương pháp trích chọn đặc trưng của ảnh 1.1 Đặc trưng của ảnh Một vector biểu diễn thông tin nào đó thì được gọi là một đặc trưng của ảnh, một ảnh thường có nhiều vector đặc trưng tương ứng với các thông tin về đặc điểm của ảnh.