Luận Văn Thuật toán nhận dạng bảng

MỞ ĐẦU​ Ngày nay khi máy tính phát triển, cùng với tốc độ và không gian lưu trữ trong máy tính đã được nâng cấp lên rất nhiều. Việc lưu trữ số lượng khổng lồ tài liệu và xử lý những nhiệm vụ phức tạp trên máy tính ngày càng nhiều. Những công việc văn phòng hàng ngày đều liên quan đến tài liệu, một tài liệu không chỉ đơn giản được lưu trữ mà nó cần phải được xử lý để có khả năng thay đổi, soạn thảo, chỉnh sửa và trích chọn các thông tin quan trọng. Vì thế các hệ phân tích tài liệu ra đời, mục đích của chúng là giúp biểu diễn thông tin trong các tài liệu ảnh, tài liệu giấy được đưa vào từ máy quét dưới dạng có cấu trúc.





Một hệ phân tích và nhận dạng tài liệu có mục đích là chuyển đổi tự động những thông tin lưu trữ trong tài liệu giấy thành biểu diễn dưới dạng những cấu trúc mà có thể truy xuất, thay đổi được bằng máy tính. Quy trình xử lý của một hệ phân tích tài liệu bắt đầu bằng việc lấy dữ liệu, các tài liệu từ giấy in sẽ được quét qua máy quét để lưu trữ trong máy tính dưới dạng các tệp dữ liệu ảnh. Rõ ràng rằng khi máy tính ra đời và phát triển đã giải quyết được nhiều vấn đề trong việc lưu trữ thông tin. Theo ước tính trên thế giới, chỉ có một số lượng nhỏ tài liệu từ những thư viện giấy khổng lồ được đưa lên mạng và vì vậy vẫn còn số lượng lớn những nguồn tri thức của nhân loại đang được lưu trữ theo cách thức cổ điển trong những thư viện mà việc bỏ ra chi phí duy trì (chủ yếu trả lương cho nhân viên) cho những nguồn tài liệu này là rất lớn. Thông tin bây giờ không nhất thiết phải lưu trữ bằng giấy, một cách lưu trữ không an toàn, không bền vững theo thời gian, thay vì đó nó được lưu trữ một cách ổn định và an toàn trong máy tính. Do đó bằng cách này hay cách khác tài liệu giấy được quét thành các tệp dữ liệu ảnh và được lưu trữ trong máy tính. Không chỉ đơn giản là vấn đề lưu trữ, các tài liệu từ giấy in được đưa vào máy tính còn cần được xử lý và trích chọn ra những thông tin quan trọng. Một tài liệu giấy in được đưa vào máy tính còn yêu cầu có khả năng soạn thảo, hiệu chỉnh và khôi phục lại. Một tệp dữ liệu cần phải chuyển được sang những định dạng khác để có khả năng soạn thảo, khi đó phải đảm bảo các thông tin được chuyển sang từ tệp dữ liệu phải không bị mất đi, không bị thiếu thông tin và cấu trúc vị trí của dữ liệu vẫn được giữ nguyên. Chẳng hạn vị trí các đoạn văn bản, tiêu đề, các bảng dữ liệu, .v.v phải được chuyển sang đúng theo cấu trúc thể hiện trên tệp dữ liệu. Vì thế ngành nhận dạng hay các hệ phân tích tài liệu ảnh ra đời và phát triển để giải quyết những vấn đề trên.



Một vài sản phẩm thương mại đã có chẳng hạn như các hệ nhận dạng quang học OCR để nhận dạng các ký tự in, ký tự viết tay, các bảng biểu tuy nhiên vẫn còn cần nhiều nghiên cứu để cải thiện độ chính xác của các hệ thống này. Một số sản phẩm chẳng hạn như VnDOCR (của Việt Nam) cho phép nhận dạng các chuỗi văn bản, các bảng biểu hay Omnipage, Find Reader .v.v là những sản phẩm nhận dạng nổi tiếng.
Bài toán nhận dạng bảng trong tài liệu ảnh là những bài toán khó và phức tạp. Trước đây các hệ phân tích tài liệu ảnh chỉ tập trung vào nhận dạng các chuỗi ký tự, phân đoạn các khối văn bản. Ngày nay tài liệu không chỉ đơn thuần là văn bản mà nó còn bao gồm hỗn hợp những đối tượng các chuỗi ký tự, ảnh, các hình vẽ, sơ đồ, các bảng biểu .v.v Nhận dạng bảng là bài toán nhận dạng ra cấu trúc bảng có trong trang tài liệu ảnh, bao gồm việc nhận dạng các cột, các dòng và các ô có chứa dữ liệu trong bảng. Đã có rất nhiều phương pháp, thuật toán tách bảng, tách ảnh được công bố trước đây. Tuy nhiên những nghiên cứu trên những vấn đề đó vẫn còn tiếp tục phát triển bởi vì chất lượng, độ chính xác, tính hiệu quả của những phương pháp được công bố trước đây vẫn còn chưa hoàn chỉnh và cần phải cải tiến chúng.
Luận án bao gồm 4 phần chủ yếu tập trung vào trình bày thuật toán nhận dạng bảng.


Chương 1 trình bày ngắn gọn cấu trúc chung của một hệ phân tích tài liệu ảnh, sơ lược về nhận dạng ký tự quang học (OCR).


Chương 2 đưa ra một thuật toán nhận dạng bảng theo phương pháp tiếp cận dưới – lên (bottom – up). Thuật toán được đề xuất bởi Thomas G .Kieninger (1998) được đặt tên là T-Recs. Tuy nhiên để nhận dạng được chính xác các cấu trúc bảng thì thuật toán còn nhiều hạn chế. Luận án sẽ chỉ ra trường hợp thuật toán nhận dạng sai và đề xuất thuật toán cải tiến T-Recs++.


Cuối cùng chương 3 trình bày chương trình thử nghiệm: T-Recs++ dùng để nhận dạng bảng.
Phần kết luận nêu tóm tắt lại các vấn đề được đưa ra trong luận án và đưa ra những vấn đề còn tồn tại để nâng cao tính hiệu quả của những thuật toán. Các hướng giải quyết và nghiên cứu trong tương lai đối với những phương pháp này cũng sẽ được đưa ra.








MỤC LỤC
234197659" MỤC LỤC 1
234197660" MỞ ĐẦU 2
234197661" CHƯƠNG 1 TỔNG QUAN HỆ PHÂN TÍCH TÀI LIỆU 4
234197662" 1.1. Giới thiệu chung một hệ phân tích trang tài liệu. 4
234197663" 1.2. Sơ lược về nhận dạng ký tự quang học (OCR). 7
234197664" 1.3. Kết luận chương. 8
234197665" CHƯƠNG 2 THUẬT TOÁN TÁCH BẢNG T-RECS. 9
234197666" 2.1. Giới thiệu. 9
234197667" 2.2. Thuật toán phân đoạn khởi tạo. 11
234197668" 2.2.1. Trường hợp thuật toán nhận dạng sai cột 12
234197669" 2.2.2. Cải tiến các bước của thuật toán phân đoạn khởi tạo - T-Recs++. 13
234197670" 2.2.3. Những ưu điểm của thuật toán. 15
234197671" 2.2.4. Những mặt hạn chế của thuật toán khởi tạo. 16
234197672" 2.3. Các bước xử lý khối sau khi phân đoạn. 16
234197673" 2.3.1. Trộn các khối phân đoạn sai 17
234197674" 2.3.2. Phân tách các cột bị trộn vào một khối 18
234197675" 2.3.3. Nhóm các từ bị phân tách. 20
234197676" 2.4. Phân tích khối 21
234197677" 2.4.1. Khối loại 2 nằm cùng với khối loại 1. 21
234197678" 2.5. Xác định cấu trúc các cột, hàng. 22
234197679" 2.6. Kết luận chương. 22
234197680" CHƯƠNG 3 THỰC NGHIỆM . 24
234197681" 3.1. T-Recs++ 24
234197682" 3.1.1. Giới thiệu. 24
234197683" 3.1.2. Mô tả chương trình. 24
234197684" 3.1.3. Một số kết quả thử nghiệm 26
234197685" KẾT LUẬN 28
DANH MỤC CÁC TÀI LIỆU THAM KHẢO .30