Luận án Tiến sĩ Toán học: Phân tích cấu trúc hình học trang ảnh tài liệu dựa trên phương pháp ngưỡng thích nghi

Chia sẻ: Lê Thị Hồng Nhung | Ngày: | Loại File: PDF | Số trang:111

Thêm vào BST

Báo xấu

24
lượt xem 2
download

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

Luận án nhằm nghiên cứu các thuật toán phân tích trang giảm, bài toán phân tích trang, những lỗi cơ bản nhất của các thuật toán phân tích trang. Hướng tiếp cận dựa trên nền trang ảnh trong phân tích trang ảnh tài liệu, thuật toán phân tích trang WhiteSpace, thuật toán phát hiện nền trang ảnh nhanh. Thuật toán phân tách trang ảnh tài liệu HP2S và AOSM. Mời các bạn cùng tham khảo luận án để nắm rõ chi tiết nội dung nghiên cứu.

Chủ đề:

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

Lưu

Nội dung Text: Luận án Tiến sĩ Toán học: Phân tích cấu trúc hình học trang ảnh tài liệu dựa trên phương pháp ngưỡng thích nghi

VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ PHÂN TÍCH CẤU TRÚC HÌNH HỌC TRANG ẢNH TÀI LIỆU DỰA TRÊN PHƯƠNG PHÁP NGƯỠNG THÍCH NGHI LUẬN ÁN TIẾN SỸ TOÁN HỌC Hà Nội - 08/02/2018
Lời cam đoan Tôi xin cam đoan luận án tiến sĩ "Phân tích cấu trúc hình học trang ảnh tài liệu dựa trên phương pháp ngưỡng thích nghi" là một công trình nghiên cứu của riêng tôi. Các số liệu và tài liệu trong luận án là trung thực và chưa được công bố trong bất kì công trình nghiên cứu nào. Tất cả các tài liệu tham khảo đều được trích dẫn và tham chiếu đầy đủ. Hà Nội, ngày 08 tháng 02 năm 2018 Tác giả luận án i
Lời cảm ơn Luận án Tiến sĩ được hoàn thiện bằng sự nỗ lực và nghiêm túc của tôi trong quá trình nghiên cứu, quá trình luôn được sự hỗ trợ, giúp đỡ tận tình của Thầy giáo hướng dẫn khoa học, Ban lãnh đạo Học viện Khoa học và Công nghệ, Ban lãnh đạo Trường THPT Chuyên Hạ Long - Quảng Ninh, các đồng nghiệp, các chuyên gia và các nhà khoa học, bạn bè và những người thân trong gia đình tôi. Trước tiên, xin trân trọng cảm ơn Thầy giáo hướng dẫn khoa học đã luôn dành sự nhiệt tình, ân cần, chỉ bảo và định hướng cho tôi trên con đường nghiên cứu khoa học từ ngày đầu học tập và quá trình nghiên cứu trong những năm qua. Chân thành cảm ơn Học viện Khoa học và Công nghệ - Viện Hàn Lâm Khoa học và Công Nghệ Việt Nam đã ủng hộ, giúp đỡ tôi trong quá trình học tập và nghiên cứu. Đặc biệt, tôi xin dành tặng tình cảm và sự biết ơn cao quý đến bạn bè và các thành viên trong gia đình: Bố, mẹ, anh chị, vợ và hai con yêu quý đã chấp nhận nhiều hy sinh vất vả, luôn sát cánh cùng tôi trong cuộc sống, quá trình học tập nghiên cứu để tôi có được thành công này. ii
Mục lục Lời cam đoan i Lời cảm ơn ii Danh mục các hình vẽ vi Lời mở đầu xi Chương 1. Tổng quan về phân tích cấu trúc hình học trang ảnh tài liệu 1 1.1 Các thành phần chính của hệ thống nhận dạng văn bản . . . . . . . . . . 1 1.1.1 Tiền xử lý . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1.1 Nhị phân hóa . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1.2 Phát hiện và phân loại các thành phần liên thông . . . . 3 1.1.1.3 Lọc nhiễu . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1.4 Căn chỉnh độ nghiêng . . . . . . . . . . . . . . . . . . . 4 1.1.2 Phân tích trang ảnh tài liệu . . . . . . . . . . . . . . . . . . . . . 5 1.1.3 Nhận dạng kí tự quang học . . . . . . . . . . . . . . . . . . . . . 7 1.1.4 Hậu xử lý . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 Các thuật toán phân tích cấu trúc hình học (phân tách) trang ảnh tài liệu tiêu biểu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Hướng tiếp cận từ trên xuống . . . . . . . . . . . . . . . . . . . . 9 1.2.2 Hướng tiếp cận từ dưới lên . . . . . . . . . . . . . . . . . . . . . . 9 1.2.3 Hướng tiếp cận lai ghép . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.4 Các thuật toán tiêu biểu . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Các phương pháp và các tập dữ liệu đánh giá các thuật toán phân tách trang ảnh tài liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3.1 Độ đo F-Measure . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.2 Độ đo PSET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3.3 Độ đo PRImA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3.4 Dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.4 Vấn đề nghiên cứu, hướng tiếp cận và những đóng góp của luận án . . . 26 1.5 Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 iii
Chương 2. Thuật toán nhanh phát hiện nền trang ảnh tài liệu 28 2.1 Phân tách trang ảnh tài liệu dựa trên nền trang ảnh . . . . . . . . . . . 28 2.2 Bài toán phát hiện nền trang ảnh . . . . . . . . . . . . . . . . . . . . . . 29 2.2.1 Định nghĩa vùng trắng lớn nhất . . . . . . . . . . . . . . . . . . . 29 2.2.2 Thuật toán tìm vùng trắng lớn nhất . . . . . . . . . . . . . . . . 32 2.2.3 Thuật toán phát hiện nền trang ảnh . . . . . . . . . . . . . . . . 34 2.3 Tăng tốc thuật toán phát hiện nền trang ảnh . . . . . . . . . . . . . . . 34 2.4 Thuật toán WhiteSpace và Fast-WhiteSpace . . . . . . . . . . . . . . . . 36 2.4.1 Thuật toán WhiteSpace . . . . . . . . . . . . . . . . . . . . . . . 36 2.4.2 Thuật toán Fast-WhiteSpace . . . . . . . . . . . . . . . . . . . . . 37 2.5 Thực nghiệm và thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.6 Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Chương 3. Thuật toán phân tách trang ảnh tài liệu HP2S và AOSM 42 3.1 Mô hình phân tách trang của hai thuật toán HP2S và AOSM . . . . . . 42 3.2 Thuật toán HP2S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.2.1 Phát hiện các đường phân tách . . . . . . . . . . . . . . . . . . . 44 3.2.2 Xác định các dòng chữ . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2.3 Gom cụm các dòng chữ thành các vùng chữ . . . . . . . . . . . . 50 3.3 Thuật toán AOSM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.3.1 Xác định các vùng chữ ứng cử viên . . . . . . . . . . . . . . . . . 52 3.3.1.1 Phát hiện các đối tượng phân tách . . . . . . . . . . . . 52 3.3.1.2 Xác định biên của mỗi vùng chữ ứng cử viên . . . . . . 56 3.3.1.3 Gom các kí tự thành các dòng chữ ứng cử viên . . . . . 58 3.3.2 Gom cụm các vùng chữ bị "tách quá" . . . . . . . . . . . . . . . . 59 3.3.2.1 Hạn chế của các phương pháp truyền thống . . . . . . . 60 3.3.2.2 Phương pháp ngưỡng thích nghi . . . . . . . . . . . . . . 63 3.4 Thuật toán Fast-AOSM . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.5 Xác định các đoạn văn bản . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.5.1 Định nghĩa các dòng chữ phân tách . . . . . . . . . . . . . . . . . 67 3.5.2 Tách các vùng chữ thuần nhất thành các đoạn văn bản . . . . . . 68 3.6 Thực nghiệm và thảo luận . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.6.1 Các thuật toán, tập dữ liệu và độ đo . . . . . . . . . . . . . . . . 70 3.6.2 Các kết quả thực nghiệm và thảo luận . . . . . . . . . . . . . . . 72 3.7 Kết luận chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Kết luận và hướng phát triển 85 Danh mục các công trình đã công bố của tác giả 88 iv
Danh mục chữ viết tắt Từ viết tắt Từ gốc Giải thích nghĩa AOSM An adaptive over-split and Thuật toán phân tích trang tách merge algorithm for page quá và gom cụm bằng phương segmentation pháp ngưỡng thích nghi HP2S A hybrid paragraph-level Một thuật toán lai ghép phân tích page segmentation trang ảnh tài liệu ở cấp độ đoạn văn bản "tách quá" over segmentation Lỗi phân tích một vùng dữ liệu chuẩn (được chuẩn bị sắn) thành các vùng nhỏ hơn "gộp" under segmentation Lỗi gộp các vùng ảnh lại với nhau tab-stop tab-stop Kí tự ở đầu hoặc cuối mỗi dòng chữ FRE FineReader Sản phẩm thương mại nhận dạng văn bản của hãng ABBYY TO Tesseract Open Source Bộ mã nguồn mở được phát triển OCR Engine bởi tập đoàn công nghệ thông tin HP ground-truth ground-truth các dòng chữ (vùng chữ) được chuẩn bị sắn v
Danh sách hình vẽ 1 Trang chủ của cuộc thi phân tích trang quốc tế các năm 2009, 2015 và 2017. xii 1.1 Các bước xử lý cơ bản của một hệ thống nhận dạng văn bản. . . . . . . . 2 1.2 Hệ thống nhận dạng VnDOCR.4.0. . . . . . . . . . . . . . . . . . . . . . 2 1.3 Một ví dụ xác định hình bao các thành phần liên thông. . . . . . . . . . 3 1.4 Minh họa trang ảnh tài liệu với nhiễu là những chấm nhỏ, những vệt dài đen ở lề trang ảnh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 Một ví dụ minh họa ảnh đầu vào bị nghiêng so với các trục tọa độ. . . . 5 1.6 Minh họa kết quả của quá trình phân tích trang. . . . . . . . . . . . . . 6 1.7 Minh họa các kết quả phân tích trang đúng và phân tích trang sai trên cùng một trang ảnh đầu vào. Kết quả phân tích ở hình a), b) được xem là phân tích đúng. Kết quả phân tích ở hình c) có hai lỗi: lỗi gộp hai cột văn bản và lỗi gộp vùng chữ với vùng ảnh. . . . . . . . . . . . . . . . . . 6 1.8 Kết quả nhận dạng sai do phân tích trang sai. a) kết quả phân tích trang sai, b) kết quả nhận dạng sai do vùng ảnh được xem như chữ. . . . . . . 7 1.9 Kết quả nhận dạng sai do phân tích trang sai. a) kết quả phân tích trang sai. b) kết quả của quá trình nhận dạng đã trộn vùng chữ ở hai cột lại với nhau. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.10 Minh họa một trường hợp phân tích lỗi của thuật toán WhiteSpace. Do thuật toán không xử lý được những vùng ảnh có cấu trúc không phải hình chữ nhật nên mắc lỗi "tách quá". . . . . . . . . . . . . . . . . . . . . . . 10 1.11 Minh họa một trường hợp phân tích lỗi của thuật toán Docstrum. Thuật toán mắc lỗi "gộp" và lỗi "tách quá" do các ngưỡng khoảng cách không được đánh giá đúng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.12 Minh họa một trường hợp phân tích lỗi của thuật toán Tab-Stop. Thuật toán Tab-Stop mắc lỗi "gộp" do xác định thiêu đối tượng phân tách giữa các cột văn bản. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.13 a) Các thành phần liên thông được xác định từ thuật toán PAL. b) Các vùng trắng xen kẽ giữa các thành phần liên thông được xác định. c), d) Các vùng trắng đã được lọc. . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.14 Kết quả lọc các vùng trắng và dây chuyền các vùng trắng tạo thành các phân tách giữa các cột văn bản, các dòng chữ được tạo thành. . . . . . . 15 1.15 Các kiểu lỗi trong phân tách trang ảnh tài liệu được định nghĩa trong PSET. 17 1.16 Công cụ đánh giá các thuật toán phân tách trang của thư viên PRImA (phiên bản 1.51). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.17 Lỗi "gộp" vùng theo phương ngang và lỗi "gộp" vùng theo phương dọc, a) các kiểu lỗi, b) các vùng ảnh chuẩn của ảnh tương ứng. . . . . . . . . 19 vi
1.18 Lỗi "tách" vùng theo phương ngang và lỗi "tách" vùng theo phương dọc, a) các kiểu lỗi, b) các vùng ảnh chuẩn của ảnh tương ứng. . . . . . . . . 20 1.19 Lỗi "quên/quên một phần" vùng ảnh, a) các kiểu lỗi, b) các vùng ảnh chuẩn của ảnh tương ứng. . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.20 Lỗi "phân loại sai" vùng ảnh, a) kiểu lỗi, b) các vùng ảnh chuẩn của ảnh tương ứng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.21 Sự phụ thuộc của các kiểu lỗi vào các trọng số, a) 6 kiểu lỗi cơ bản của một cấu hình đánh giá, b) mỗi kiểu lỗi lại phụ thuộc vào một tập các trọng số. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.22 Một số ảnh minh họa của tập dữ liệu UWIII. . . . . . . . . . . . . . . . 24 1.23 Một số ảnh minh họa của tập dữ liệu PRImA. . . . . . . . . . . . . . . . 25 1.24 Một số ảnh minh họa của tập dữ liệu UNLV. . . . . . . . . . . . . . . . . 26 2.1 Một trang ảnh có cấu trúc trang và cấu trúc nền đơn giản. . . . . . . . . 30 2.2 Minh họa trường hợp các vùng chữ của trang ảnh được phân tách hoàn toàn dựa trên các vùng trắng nền trang ảnh. a) các hình chữ nhật thể hiện cho các vùng trắng nền của trang ảnh, b) kết quả phân tách trang. . 30 2.3 Thời gian thực thi trung bình của các thuật toán tiêu biểu [TPAMI2008][62]. 31 2.4 Hình chữ nhật có đường bao màu xanh thể hiển cho vùng trắng lớn nhất tìm được. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.5 Sơ đồ thuật toán tìm các vùng trắng lớn nhất. . . . . . . . . . . . . . . . 33 2.6 Mô tả bước chia trang ảnh thành bốn miền con của thuật toán tìm vùng trắng lớn nhất, (a) hình bao và các hình chữ nhật, (b) điểm chốt tìm được, (c, d) các miền con trái/phải và trên/dưới. . . . . . . . . . . . . . . . . . 34 2.7 Sơ đồ thuật toán tìm các vùng trắng bao phủ nền trang ảnh. . . . . . . . 35 2.8 Hạn chế dẫn đến làm giảm tốc độ thực thi của thuật toán WhiteSpace- Detection. Miền ZCTR , ZCRT và các miền con của chúng sẽ được xét lại nhiều lần. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.9 Minh họa một trường hợp sinh các miền con của thuật toán WhiteS- paceDetection và thuật toán Fast-WhiteSpaceDetection. a) thuật toán WhiteSpaceDetection. b) thuật toán Fast-WhiteSpaceDetection. . . . . . 37 2.10 Sơ đồ thuật toán WhiteSpace. . . . . . . . . . . . . . . . . . . . . . . . . 38 2.11 Minh họa các bước của thuật toán WhiteSpace. Hình a) thể hiện ảnh gốc đầu vào, b) thể hiện hình bao của các thành phần liên thông (CCs), c) các hình chữ nhật là các vùng trắng bao phủ nền của trang ảnh, d) các hình chữ nhật là các đối tượng phân tách ngang và dọc được sử dụng để phân đoạn trang ảnh thành các vùng, e) thể hiện kết quả của quá trình phân tách. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.12 Biểu đồ thể hiện thời gian thực thi trung bình của thuật toán WhiteSpace và Fast-WhiteSpace. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.13 Biểu đồ so sánh độ chính xác của thuật toán Fast-Whitespace với thuật toán WhiteSpace và các thuật toán phân tách trang tiên tiến hiện nay: Tab-stop và RAST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.1 Mô hình chung của hai thuật toán HP2S và AOSM. . . . . . . . . . . . . 43 3.2 Các bước chính của quá trình xác định các vùng chữ của thuật toán HP2S. 44 vii
3.3 Các hình chữ nhật kề trái, phải, trên và dưới của các kí tự a), b) và e). a) và b) kí tự được xét đến là một tab−stop ứng cử viên ; c) và d) kí tự được xét đến không phải là một tab−stop ứng cử viên. . . . . . . . . . . 45 3.4 Minh họa những bước xác định các đường phân tách: a) ảnh đầu vào với hình bao của các kí tự, b) tab−stop ứng cử viên, c) tab−stop, d) tab−stop mở rộng, e) tab−line. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.5 Minh họa các dòng chữ ở phần tiêu đề bị phân mảnh và các dòng chữ giữa các cột bị gộp lại với nhau. . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.6 Minh họa các bước chính của quá trình xác định các dòng chữ của thuật toán HP2S. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.7 Các đường phân tách được sử dụng trong quá trình xác định các dòng chữ. a) minh họa các dòng chữ ứng cử viên. Các kí tự nằm ở các phía khác nhau của một đường phân tách sẽ thuộc các dòng chữ khác nhau. b) Các dòng chữ là kết quả được xác định bởi thuật toán. . . . . . . . . . . . . . 49 3.8 a) các dòng chữ ứng cử viên, b) trường hợp không tồn tại đường phân tách, dw được sử dụng để tách các kí tự thành các dòng chữ. . . . . . . . 49 3.9 Lỗi quên gộp các kí tự gần kề vào dòng chữ. a) các đường phân tách, b) các chỉ số bị tách ra khỏi các dòng chữ bởi các đường phân tách. . . . . . 49 3.10 a) minh họa các kí tự được gán nhãn m− tabs, b) minh họa các dòng chữ được phục hồi lại. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.11 a) Ảnh gốc, b) các đường phân tách, c) các vùng chữ được xác định. . . 51 3.12 Minh họa khoảng cách theo phương ngang giữa hai dòng chữ linei và linej . 51 3.13 Các bước chính của quá trình xác định các vùng chữ của thuật toán AOSM. 52 3.14 Hình minh họa các phân tách vật lý, các tab−stop và cả các vùng trắng phân cách giữa các cột văn bản. . . . . . . . . . . . . . . . . . . . . . . . 53 3.15 Lỗi "gộp" bị gây ra do tham số "ngưỡng" khoảng cách không phù hợp cho các vùng khác nhau trên cùng một trang ảnh. . . . . . . . . . . . . . . . 54 3.16 Lỗi "gộp" bị gây ra do thuật toán theo hướng tiếp cận từ trên xuống không xử lý được những vùng ảnh có cấu trúc "không phải hình chữ nhật". 55 3.17 Hình a) minh họa lỗi "gộp" bị gây ra bởi thuật toán RAST (thuật toán lai ghép) do xác định thiếu đường phân tách. Hình b) minh họa lỗi "tách quá" bị gây ra bởi thuật toán PAL (thuật toán lai ghép) do xác định sai các đường phân tách. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.18 Các bước của giai đoạn 1: a) ảnh gốc đầu vào ; b) các hình chữ nhật thể hiện các vùng trắng nền tìm được ; c) kết quả của quá trình "đổ mực" ; d) các vùng chữ ứng cử viên. . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.19 Minh họa các điểm được xem là điểm biên, điểm góc. a) minh họa một điểm với 8 lân cận của điểm đó. Một điểm là điểm biên, nếu nó là điểm trắng và 8 lân cận của nó có ít nhất một điểm đen b), c), d). Một điểm là điểm góc nếu nó là điểm trắng và 8 lân cận của nó có 1 hoặc 5 điểm đen c), d). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.20 Hình minh họa thuật toán Ray-Casting xác định điểm trong hoặc ngoài đa giác. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.21 Các bước chính của quá trình gom cụm các kí tự thành các dòng chữ. . . 60 viii
3.22 Minh họa kết quả phân tách của giai đoạn 1: a) các vùng ảnh được "đổ mực" thể hiện cho các vùng chữ ; b) các vùng chữ được xem là bị "tách quá". . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 3.23 Kết quả phân tách của thuật toán RLSA trên ảnh UWIII-A005BIN, RSLA quên không xác định các dòng chữ dính vào các thành nhiễu. . . . . . . . 62 3.24 Kết quả phân tách của thuật toán Docstrum và Voronoi trên ảnh UWIII- A005BIN, cả hai thuật toán Docstrum và Voronoi đều mắc lỗi "tách quá" vùng chữ phần tiêu đề. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.25 Chiều cao x −height được ước lượng trên một dòng chữ. . . . . . . . . . . 64 3.26 Minh họa một trường hợp các dòng chữ được nhóm lại với nhau bằng phương pháp ngưỡng thích nghi. . . . . . . . . . . . . . . . . . . . . . . . 65 3.27 Kết quả của quá trình nhóm các dòng chữ bị "tách quá": a) các dòng chữ bị "tách quá" ; b) kết quả sau khi gom cụm. . . . . . . . . . . . . . . . . 65 3.28 Minh họa một trường hợp phân tách tốt của thuật toán Fast-AOSM chỉ với bước xác định và loại bỏ các vùng trắng. a) các hình chữ nhật thể hiện cho các vùng trắng được phát hiện, b) kết quả phân tách. . . . . . . . . . 66 3.29 Dòng chữ liền trước (pre− line) và liền sau (next− line) của một dòng chữ (current− line). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.30 Hình chữ nhật "nét đứt" thể hiện dòng chữ bắt đầu của một đoạn văn bản. 67 3.31 Các chữ nhật "nét đứt" thể hiện các dòng chữ nằm phía trên a) và nằm phía dưới b) của các cột văn bản. . . . . . . . . . . . . . . . . . . . . . . 68 3.32 Dòng chữ bắt đầu của một đoạn với "symbol" a), dòng chữ bắt đầu của một tài liệu tham khảo b). . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.33 Các khối văn bản rất gần nhau. Dòng chữ có hình bao là nét đứt nằm bắc ngang qua hai cột văn bản có khoảng cách rất gần với các dòng chữ ở hai cột bên dưới nó. Các thuật toán truyền thống hầu hết thất bại trong tình huống này và gây ra lỗi "gộp". . . . . . . . . . . . . . . . . . . . . . . . . 69 3.34 Tách các vùng chữ thuần nhất thành các đoạn văn bản: a) ảnh gốc, b) kết quả phân tách không sử dụng các dòng chữ phân tách, c) các dòng chữ "tô đậm" là các dòng chữ phân tách, d) các vùng chữ được tách ra do áp dụng các dòng chữ phân tách, e) kết quả phân tách cuối cùng. . . . . . . 71 3.35 Độ chính xác của các thuật toán với độ đo PSET, tập dữ liệu UW-III and ICDAR2009. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.36 Độ chính xác của các thuật toán với độ đo F-Measure và tập dữ liệu ICDAR2009. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.37 Độ chính xác của thuật toán HP2S và AOSM so với các kết quả tốp đầu đã được công bố tại cuộc thi ICDAR2009 [4] với độ đo PRImA và tập dữ liệu ICDAR2009. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.38 Độ chính xác của thuật toán Fast-AOSM và các kết quả tốp đầu đã được công bố tại cuộc thi ICDAR2015 [9] với độ đo PRImA và tập dữ liệu của cuộc thi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.39 Độ chính xác của thuật toán HP2S, Fast-AOSM, các hệ thống tốp đầu tại cuộc thi phân tích trang năm 2015 (ICDAR2015), bộ mã nguồn mở Tesseract-3.03 và Fine Reader 12 được thực nghiệm trên tập UNLV với bốn ngữ cảnh khác nhau của độ đo PRImA. . . . . . . . . . . . . . . . . 75 ix
3.40 Độ chính xác của thuật toán Fast-AOSM và các kết quả tốp đầu tại cuộc thi ICDAR2017 với độ đo PRImA và tập dữ liệu của cuộc thi. . . . . . . 76 3.41 So sánh các kiểu lỗi khác nhau khi thực hiện trên tập dữ liệu ICDAR2009 dataset với độ đo PSET. . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.42 So sánh các kiểu lỗi của thuật toán Fast-AOSM với các thuật toán tốp đầu tại cuộc thi năm 2015 khi thực hiện trên tập dữ liệu ICDAR2015 dataset với ngữ cảnh OCR của độ đo PRImA. . . . . . . . . . . . . . . . . . . . 77 3.43 Kết quả thực hiện của thuật toán HP2S trên độ đo PSET-measure, tập dữ liệu ICDAR2009 với các giá trị khác nhau của θ. . . . . . . . . . . . . 78 3.44 Kết quả thực hiện của thuật toán AOSM trên độ đo PSET-measure, tập dữ liệu ICDAR2009 với các giá trị khác nhau của θ. . . . . . . . . . . . . 79 3.45 Thời gian thực thi trung bình của mỗi thuật toán khi thực hiện trên mỗi trang ảnh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.46 Kết quả phân tách trên cùng ảnh PRImA-00000197. . . . . . . . . . . . . 80 3.47 Kết quả phân tách trên cùng ảnh PRImA-00000781. . . . . . . . . . . . . 81 3.48 Kết quả phân tách trên cùng ảnh PRImA-00000769. . . . . . . . . . . . . 82 3.49 Kết quả phân tách trên cùng ảnh UWIII-A005. . . . . . . . . . . . . . . 83 3.50 Minh họa một kết quả phân tích của cả hai thuật toán HP2S và Fast - AOSM trên cùng trang ảnh PRImA-00000801, a) kết quả phân tích của thuật toán HP2S, b) kết quả phân tích của thuật toán Fast - AOSM. . . 84 x
Lời mở đầu Tính cấp thiết của đề tài Ngày nay với sự phát triển của công nghệ thông tin và nhu cầu ngày càng tăng đối với truyền thông, nhu cầu giao tiếp, trao đổi, lưu trữ thông tin ở dưới dạng các tệp văn bản điện tử. Hầu hết tài liệu của người dùng bây giờ đều đã được số hóa và được lưu trữ trên máy tính. Việc số hóa đảm bảo tính an toàn và thuận tiện hơn hẳn so với sử dụng tài liệu giấy. Mặc dù vậy, yêu cầu về các văn bản giấy vẫn không thay đổi. Đã có nhiều cài tiến trong việc sử dụng các văn bản giấy và hầu hết mọi người vẫn thích đọc văn bản giấy hơn đọc các văn bản điện tử, đặc biệt là khi đọc các văn bản khoa học, công văn, ... Tuy nhiên, việc sử dụng văn bản giấy thường mang đến những hạn chế như ; việc lưu trữ chúng sẽ rất rườm rà và tốn nhiều thời gian, đặc biệt là khi muốn sửa chữa hay chỉ dùng lại một phần văn bản. Vì vậy nhu cầu cấp thiết của con người là tạo ra các máy trí tuệ nhận tạo có thể làm tốt những vấn đề này thay con người. Vấn đề này sẽ có thể được giải quyết nếu các văn bản giấy có thể được chuyển đổi một cách tự động thành các văn bản điện tử sao cho các máy có thể đọc và hiểu được thông tin. Tuy nhiên, nó không phải là một nhiệm vụ đơn gian để tự động chuyển đổi các văn bản giấy thành các văn bản điện từ giữ nguyên định dạng. Nhận dạng văn bản đã ra đời nhằm mục tiêu chuyển đổi tự động các văn bản ở dạng ảnh sang dạng tệp tin có thể dễ dàng lưu trữ và chỉnh sửa. Quá trình nhận dạng văn bản được thực hiện qua các bước chính như sau: trang ảnh đầu vào sẽ qua bước tiền xử lý, sau đó là bước phân tích trang, đầu ra của phân tích trang sẽ là đầu vào của bước nhận dạng, cuối cùng là bước hậu xử lý. Kết quả của một hệ thống nhận dạng phụ thuộc chính vào hai bước: phân tích trang và nhận dạng. Đến thời điểm này, bài toán nhận dạng trên các văn bản chữ in đã được giải quyết gần như trọn vẹn (sản phẩm thương mại FineReader 12.0 của hãng ABBYY có thể nhận dạng chữ in trên nhiều ngôn ngữ khác nhau, phần mềm nhận dạng chữ Việt in VnDOCR 4.0 của Viện Công nghệ Thông Tin Hà Nội có thể nhận dạng với độ chính xác trên 98%). Tuy nhiên trên thế giới cũng như ở Việt Nam, bài toán phân tích trang vẫn còn là một thách thức lớn đối với các nhà nghiên cứu. Cho đến nay phân tích trang vẫn đang nhận được sự quan tâm của nhiều nhà nghiên cứu. Cứ hai năm một lần trên thế giới lại có cuộc thi phân tích trang quốc tế nhằm thúc đẩy sự phát triển các thuật toán phân tích trang 1. Chính những điều này đã là động lực thúc đẩy luận án cố gắng nghiên cứu để đề xuất các giải pháp hữu hiệu cho bài toán phân tích trang. xi
(ICDAR2009) (ICDAR2015) (ICDAR2017) Hình 1 – Trang chủ của cuộc thi phân tích trang quốc tế các năm 2009, 2015 và 2017. xii
Mục tiêu của luận án Trong những năm gần đây đã có rất nhiều các thuật toán phân tích trang được phát triển, đặc biệt là các thuật toán phát triển theo hướng tiếp cận lai ghép. Các thuật toán được đề xuất đều thể hiện những điểm mạnh, điểm yếu khác nhau, nhưng nhìn chung hầu hết vẫn mắc phải hai lỗi cơ bản là: lỗi phân tách một vùng chữ đúng ra thành các vùng chữ nhỏ hơn từ đó làm sai hoặc mất thông tin của các dòng chữ hay đoạn văn bản (sau đây gọi là lỗi "tách quá"), lỗi gộp các vùng chữ ở các cột văn bản hay các đoạn văn bản lại với nhau (sau đây gọi là lỗi "gộp"). Vì vậy mục tiêu của luận án là nghiên cứu phát triển các thuật toán phân tích trang giảm đồng thời cả hai kiểu lỗi: "tách quá", "gộp". Phạm vi nghiên cứu Bài toán phân tích trang vẫn chưa đạt được nhiều kết quả khả quan bởi những thách thức sau: 1. Cấu trúc của các dạng văn bản rất đa dạng và phức tạp như : sách, báo, tạp chí, báo cáo, ... Trên các trang ảnh có các vùng chữ bao quanh những bức ảnh, biểu đồ, đồ thị. 2. Sự thay đổi đa dạng của kích cỡ và kiểu phông chữ. 3. Sự xuất hiện của các vùng bảng với cấu trúc rất đa dạng và phức tạp, có những vùng bảng không được giới hạn bởi các đường kẻ, hoặc có những vùng bảng với các đường kẻ đứt nét,... 4. Sự có mặt của các vùng ảnh không phải là vùng chữ như: ảnh, biểu đồ, logo, đường kẻ, ... Tạo ra rất nhiều khó khăn cho việc phân loại là chữ hay không phải là chữ. 5. Mỗi ngôn ngữ lại có thứ tự đọc, cách viết, cách giãn dòng và cấu trúc khác nhau. Vì vậy, các thuật toán phân tích trang hiện nay vẫn bị giới hạn bởi ngôn ngữ. Luận án giới hạn phạm vi nghiên cứu trong khuôn khổ các trang ảnh tài liệu được soạn thảo bằng ngôn ngữ Latin cụ thể là Tiếng Anh và tập trung vào phân tích các vùng chữ, chưa đề xuất đến vấn đề phát hiện và phân tích cấu trúc bảng. Bài toán đặt ra là xây dựng một mô hình hiệu quả cho việc phân tích các vùng chữ. xiii
Những đóng góp mới của luận án 1. Đánh giá ưu nhược điểm của các hướng tiếp cận của các thuật toán phân tích trang. 2. Đề xuất một giải pháp làm tăng tốc thuật toán phát hiện nền trang ảnh. 3. Đề xuất phương pháp tham số thích nghi làm giảm sự ảnh hưởng của kích cỡ và kiểu phông chữ đến kết quả phân tích trang. 4. Đề xuất một giải pháp mới cho vấn đề phát hiện và sử dụng các đối tượng phân tách trong các thuật toán phân tích trang. 5. Đề xuất một giải pháp mới tách các vùng chữ thành các đoạn văn bản dựa trên phân tích ngữ cảnh. Bố cục của luận án Luận án được phân thành ba chương với cấu trúc như sau : Chương 1: Tổng quan về phân tích trang ảnh tài liệu. Chương này trình bày tổng quan về hệ thống nhận dạng văn bản và bài toán phân tích trang ảnh tài liệu, những thuật toán phân tích trang tiêu biểu, các phương pháp và các tập dữ liệu để đánh giá các thuật toán phân tích trang. Chương 2: Thuật toán nhanh phát hiện nền trang ảnh tài liệu. Chương này trình bày vai trò quan trọng của nền trang ảnh trong phân tích trang, thuật toán phát hiện nền hiệu quả WhiteSpace, thuật toán phát hiện nền nhanh dựa trên việc cải tiến của thuật toán WhiteSpace. Chương 3: Thuật toán phân tích trang ảnh HP2S và AOSM. Chương này trình bày hai thuật toán phân tách trang ảnh tài liệu theo hướng tiếp cận lai ghép HP2S và AOSM. Các thuật toán được phát triển dựa trên sự kết hợp giữa phương pháp xác định các đối tượng phân tách và phương pháp tham số thích nghi. Những kết quả thực nghiệm được trình bày trong chương này đã chứng tỏ hai thuật toán HP2S và AOSM có độ chính xác cao so với những thuật toán và các sản phẩm thương mại hàng đầu trong thời điểm hiện tại. Cuối cùng là kết luận và hướng phát triển của luận án. xiv
Chương 1 Tổng quan về phân tích cấu trúc hình học trang ảnh tài liệu Trong chương này, luận án trình bày tổng quan hệ thống nhận dạng văn bản, bài toán phân tích trang, các thuật toán phân tích trang tiêu biểu, những lỗi cơ bản nhất của các thuật toán phân tích trang. Từ đó dẫn đến mục tiêu nghiên cứu và những kết quả đạt được của luận án. 1.1 Các thành phần chính của hệ thống nhận dạng văn bản Về cơ bản, một hệ thống nhận dạng văn bản thường được thực hiện qua các bước cơ bản như được mô tả ở hình 1.1. Những thông tin ở dạng văn bản như sách, báo, tạp chí, ... sau quá trình quét ảnh sẽ cho ta kết quả là các trang ảnh tài liệu. Những file ảnh này sẽ là đầu vào của một hệ thống nhận dạng, kết quả đầu ra của hệ thống nhận dạng là những file văn bản có thể dễ dàng chính sửa và lưu trữ, ví dụ như: file *.doc, *.docx, *.excel, *.pdf, ... xem Hình 1.2. Luận án chỉ tập trung vào nghiên cứu bước phân tích trang, trong đó trọng tâm là phân tích cấu trúc hình học của trang ảnh. 1.1.1 Tiền xử lý Nhiệm vụ của quá trình tiền xử lý trang ảnh thông thường là nhị phân hóa, xác định các thành phần liên thông ảnh, lọc nhiễu, căn chỉnh độ nghiêng. Kết quả đầu ra 1
Chương 1. Tổng quan về phân tích cấu trúc hình học trang ảnh tài liệu 2 Hình 1.1 – Các bước xử lý cơ bản của một hệ thống nhận dạng văn bản. Hình 1.2 – Hệ thống nhận dạng VnDOCR.4.0. của bước tiền xử lý sẽ là đầu vào của quá trình phân tích trang. Do đó, kết quả của quá trình tiền xử lý cũng sẽ có những ảnh hưởng đáng kể đến kết quả phân tích trang. 1.1.1.1 Nhị phân hóa Ảnh đầu vào của các thuật toán phân tích trang là những bức ảnh có được từ quá trình quét ảnh, những bức ảnh này có thể là ảnh màu hay ảnh nhị phân. Kết quả đầu ra của hệ thống là những vùng ảnh đã được phân tích (thường được gán nhãn với định dạng XML), quá trình nhận dạng có thể xác định các vùng này để đọc và hiểu các thông tin trên đó. Bởi vì, thuật toán được trình bày trong luận án thực hiện trên ảnh nhị phân (đen và trắng), vì vậy những bức ảnh màu đầu vào trước tiên sẽ được chuyển đổi thành ảnh nhị phân bằng cách sử dụng thuật toán Sauvola [57], [63]. Trong luận án này quy
Chương 1. Tổng quan về phân tích cấu trúc hình học trang ảnh tài liệu 3 định những điểm ảnh thuộc vùng nền có giá trị là 0, những điểm ảnh thuộc phần nội dung của ảnh có giá trị là 1. 1.1.1.2 Phát hiện và phân loại các thành phần liên thông Các thành phần liên thông là các vùng gồm các điểm ảnh liên tục có cùng giá trị. Chúng ta nói rằng hai điểm ảnh [r , c], [r 0 , c 0 ] trong một ảnh nhị phân B là liên tục nếu tồn tại một dãy các điểm ảnh [r0 , c0 ], [r1 , c1 ], ..., [rn , cn ], sao cho: [r , c] = [r0 , c0 ], [r 0 , c 0 ] = [rn , cn ], B [ri , ci ] = 1 và [ri , ci ] là lân cận của [ri−1 , ci−1 ] với mọi i = 1, ..., n. Để xác định các thành phần liên thông, thuật toán dò biên của Heckbert đã được áp dụng, thuật toán được cài đặt trong bộ mã nguồn mở của thư viện xử lý ảnh Leptonica [2], xem Hình 1.3. Ảnh gốc Hình bao các thành phần liên thông Hình 1.3 – Một ví dụ xác định hình bao các thành phần liên thông. Các thành phần liên thông là nội dung quan trọng nhất của các thuật toán phân tích trang. Vì vậy, việc phân loại các thành phần liên thông là rất cần thiết, nó sẽ giúp tăng độ chính xác của các thuật toán phân tích trang ảnh tài liệu. Bởi vì các thành phần non-text nếu không được xem xét trước khi nhóm các thành phần text thì các thuật toán sẽ thất bại trên những trang ảnh có nhiễu hoặc có các thành phần khác như ảnh, biểu đồ, bảng biểu..., có thể sẽ gộp cả những thành phần này vào các đoạn văn bản và làm cho quá trình ước lượng những thuộc tính kích cỡ của phông chữ sẽ bị sai. Điều này dẫn đến kết quả phân tích trang sẽ thiếu chính xác. Các thuật toán được trình bày trong luận án này sử dụng phép biến đổi hình thái để lọc các ảnh bán sắc, các đường kẻ ngang, kẻ dọc. Sau đó, xây dựng biểu đồ tần số của chiều rộng và chiều cao của các thành phần liên thông. Từ đó suy ra được kích cỡ
Chương 1. Tổng quan về phân tích cấu trúc hình học trang ảnh tài liệu 4 trung bình của các phông chữ, dựa trên các kích cỡ trung bình này các thành phần liên thông của trang ảnh được chia làm ba loại như sau: nhóm các thành phần nhỏ (được xem như là nhiễu), loại các thành phần liên thông lớn (xem như vùng ảnh), phần còn lại được xem là phần chữ. Cũng đã có rất nhiều các thuật toán giải quyết bài toán này theo hướng xem xét chi tiết trong nhiều trường hợp riêng, ví dụ như [18], [69] 1.1.1.3 Lọc nhiễu Những trang ảnh thu được sau quá trình quét ảnh, chụp ảnh, có thể xuất hiện những thành phần không mong muốn được gọi là nhiễu, những kiểu nhiễu thường gặp là những chấm nhỏ trên trang ảnh, những vệt đen dài thường xuất hiện ở lề trang ảnh,... xem Hình 1.4. Lọc nhiễu là một vấn đề căn bản, kết quả của quá trình lọc nhiễu sẽ có ảnh hướng đáng kể đến độ chính xác của hệ thống nhận dạng. Đã có nhiều phương pháp mạnh lọc nhiễu được đề xuất ví dụ như [54], [59], [60], [61]. Hình 1.4 – Minh họa trang ảnh tài liệu với nhiễu là những chấm nhỏ, những vệt dài đen ở lề trang ảnh. 1.1.1.4 Căn chỉnh độ nghiêng Góc nghiêng của trang ảnh tài liệu là một vấn đề phổ biến ở hầu hết các trang ảnh tài liệu, nó là kết quả của quá trình quét dữ liệu từ dạng giấy thành các file ảnh hoặc cũng có thể là do đặc trưng của cấu trúc dữ liệu các trang ảnh, xem Hình 1.5 . Trong
Chương 1. Tổng quan về phân tích cấu trúc hình học trang ảnh tài liệu 5 hầu hết các trường hợp, ngay cả khi góc nghiêng của trang ảnh là nhỏ cũng có những ảnh hưởng bất lợi rất rõ ràng đến độ chính xác của bước phân tích cấu trúc hình học và phân tích cấu trúc logic của trang ảnh. Điều này là vì hầu hết các thuật toán phân tích trang ảnh đều yêu cầu dữ liệu đầu vào là những trang ảnh đã được căn chỉnh độ nghiêng, có một số ít các thuật toán phân tích không yêu cầu việc căn chỉnh độ nghiêng ở bước trước đó [33], [49]. Tuy nhiên, hầu hết các thuật toán phân tích đều yêu cầu các trang ảnh đầu vào đã được xử lý góc nghiêng ở bước trước đó. Đã có nhiều thuật toán phát hiện góc nghiêng trang ảnh được đề xuất, ví dụ như [27], [51], [52]. Các thuật toán được đề xuất trong luận án này cũng được thực hiện trên những trang ảnh đã được căn chỉnh độ nghiêng. Hình 1.5 – Một ví dụ minh họa ảnh đầu vào bị nghiêng so với các trục tọa độ. 1.1.2 Phân tích trang ảnh tài liệu Phân tích cấu trúc trang ảnh tài liệu (document layout analysis - sau đây gọi tắt là "phân tích trang") là một trong những thành phần chính của các hệ thống nhận dạng văn bản (OCR - System). Ngoài ra nó còn được ứng dụng rộng rãi trong các lĩnh vực khác của tin học ví dụ như: số hóa tài liệu, nhập liệu tự động, thị giác máy tính,... Nhiệm vụ của phân tích trang bao gồm việc tự động phát hiện những vùng ảnh có trên một trang ảnh tài liệu (cấu trúc hình học) [12], [48] và phân loại chúng thành những vùng dữ liệu khác nhau như vùng chữ, vùng ảnh, vùng bảng biểu, vùng đồ thị, . . . (cấu trúc logic) [30], [32], [39], [40], [50], [51], [73] xem Hình 1.6. Kết quả phân tích trang được sử dụng như một thông tin đầu vào cho quá trình nhận dạng và nhập liệu tự động của các hệ thống xử lý ảnh tài liệu.