Tóm tắt 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:26

Thêm vào BST

Báo xấu

25
lượt xem 3
download

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

Mục tiêu của luận án là nghiên cứu và phát triển các thuật toán vi phân. Lỗi tách một vùng văn bản chính xác làm cho các vùng văn bản nhỏ hơn làm sai lệch hoặc mất thông tin của văn bản hoặc văn bản (phân đoạn quá mức), lỗi bao gồm các vùng văn bản trong các cột văn bản hoặc các đoạn văn bản (phân đoạn dưới).

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt 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

BỘ GIÁO DỤC VÀ ĐÀO TẠO 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Ệ ……..….***………… HÀ ĐẠI TÔN 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 Chuyên ngành: Cớ sở Toán học cho Tin học Mã số: 62 46 01 10 LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2018 1
Công trình được hoàn thành tại: 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ười hướng dẫn khoa học: TS. Nguyễn Đức Dũng Phản biện 1: … Phản biện 2: … Phản biện 3: …. Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại 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 vào hồi … giờ ..’, ngày … tháng … năm 201…. Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam 2
MỞ ĐẦU Nhận dạng văn bản là một lĩnh vực đã được quan tâm nghiên cứu và ứng dụng trong nhiều năm nay. 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, kết quả đầ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 này 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. 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.ThuậtTrong 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 lại ghép (hybrid). 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 làm sai hoặc mất thông tin của các dòng chữ hay đoạn văn bản (over-segmentation), 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 (under-segmentation). 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: over-segmentation, under-segmentation. Các vấn đề trong phân tích trang là rất rộng vì vậy luận án giới hạn phạm vi nghiên cứu trong khuôn khổ các trang ảnh văn bản đượ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ữ. Luận án chưa đề xuất đến vấn đề phát hiện và phân tích cấu trúc của các vùng bảng, phát hiện các vùng ảnh và phân tích cấu trúc logic. Với những mục tiêu đặt ra luận án đã đạt được một số kết quả sau: 1. Đề 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. 2. Đề 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. 3. Đề 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. 4. Đề 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. 3
CHƯƠNG 1. TỔNG QUAN VỀ PHÂN TÍCH TRANG ẢNH TÀI LIỆU Trong chương này, tôi 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 này. 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. Những thông tin ở dạng văn bản như sách, báo, tạp chí, ... sau quá trình scan sẽ cho ta kết quả là các file ảnh văn bản. 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, ... Luận án chỉ tập trung vào nghiên cứu bước phân tích trang, trong đó trọng tập là phân tích cấu trúc hình học của trang ảnh. Hình 1: Minh họa các bước xử lý cở bản của một hệ thống nhận dạng văn bản. 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 trình độ nghiêng. Kết quả đầu ra 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.2. Phân tích trang ảnh tài liệu Phân tích trang ảnh tài liệu (document layout analysis) 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 vật lý) và phân loại chúng thành những vùng dữ liệu khác nhau như vùng chữ, ảnh, bảng biểu, header, footer... (cấu trúc logic). 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 (document imaging). 1.1.3. Nhận dạng kí tự quang học Đây là giái đoạn quan trọng nhất, giái đoạn này quyết định độ chính xác của hệ thống nhận dạng. Có nhiều phương pháp phân lớp khác nhau được áp dụng cho các hệ thống nhận dạng chữ, ví dụ như: phương pháp đối sánh, phương pháp tiếp cận trực tiếp, phương pháp ngữ pháp, phương pháp đồ thị, mạng nơ ron, phương pháp thống kê, máy véc tơ tựa (SVM). 1.1.4. Hậu xử lý Đây là công đoạn cuối cùng của quá trình nhận dạng. Có thể hậu xử lý là bước ghép nối các kí tự đã nhận dạng thành các từ, các câu, các đoạn văn bản nhằm tái hiện lại văn bản đồng thời phát hiện ra các lỗi nhận dạng sai bằng cách kiểm tra chính tả dựa trên cấu trúc và ngữ nghĩa của các từ, các câu hoặc các đoạn văn bản. Việc phát hiện ra các lỗi, các sai sót trong nhận dạng ở bước này góp phần đáng kể vào việc nâng cao chất lượng nhận dạng. 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 tiêu biểu Qua hàng chục năm phát triển cho đến nay đã có rất nhiều các thuật toán phân tích trang đã được công bố. Dựa trên thứ tự thực hiện của các thuật toán, các thuật toán phân tách trang ảnh tài liệu có thể được chia thành ba hướng tiếp cận khác nhau: từ trên xuống (top-down), từ dưới lên (bottom-up) và các phương pháp lai ghép (hybrid). 4
1.2.1 Hướng tiếp cận từ trên xuống (top-down) Các thuật toán top-down tiêu biểu như: X-Y Cut, WhiteSpace,... Các thuật toán theo hướng tiếp cận này thực hiện phân tích trang bằng cách chia đệ quy trang ảnh văn bản theo các phương ngang hoặc phương thẳng đứng dọc theo các khoảng trắng trong trang. Những khoảng trằng này thường là dọc theo biên của các cột văn bản (column) hoặc biên của các đoạn ảnh văn bản (paragraph). Điểm mạnh của các thuật toán này là độ phức tạp tính toán thấp, cho kết quả phân tách tốt trên những trang ảnh có cấu trúc hình chữ nhật (rectangle) tức là các trang ảnh mà các vùng ảnh có thể được bao quanh bởi các hình chữ nhật không giáo nhao. Tuy nhiên, chúng không thể xử lý được những trang vùng ảnh không phải là hình chữ nhật (non-rectangular). 1.2.2. Hướng tiếp cận từ dưới lên (bottom-up) Các thuật toán bottom-up tiêu biểu như: Smearing, Docstrum, Voronoi,... Các thuật toán theo hướng tiếp cận này bắt đầu với các vùng nhỏ của ảnh (các pixel điểm ảnh hoặc các kí tự) và lần lượt nhóm các vùng nhỏ có cùng kiểu lại với nhau để hình thành nên các vùng ảnh. Điểm mạnh của hướng tiếp cận này là các thuật toán có thể xử lý tốt những trang ảnh với cấu trúc bất kì (rectangle hoặc non-rectangle). Điểm yếu của các thuật toán bottom-up là tốn bộ nhớ, chậm, do các vùng nhỏ được gộp lại với nhau dựa trên những tham số khoảng cách mà thông thường các tham số này được ước lượng trên toàn trang ảnh nên các thuật toán này thường quá nhạy cảm với giá trị tham số và mắc lỗi chia quá nhỏ (over-segmentation) các vùng ảnh văn bản, đặc biệt là các vùng chữ có sự khác biệt về kích cỡ và kiểu phông. 1.2.3. Hướng tiếp cận lai ghép (hybrid) Từ những phân tích trên cho thấy ưu điểm của hướng tiếp cận bottom-up là nhược điểm của hướng tiếp cận Top-down và ngược lại. Do đó, trong những năm gần đầy đã có nhiều các thuật toán phát triển theo hướng lai ghép giữa top-down và bottom-up, một trong các thuật toán tiêu biểu như: RAST , Tab-Stop , PAL ,... Các thuật toán phát triển theo hướng này thường dựa trên các đối tượng phân tách ví dụ như, các vùng trắng hình chữ nhật, các tab-stop, ... để suy ra cấu trúc các cột văn bản. Từ đó các vùng ảnh được xác định bằng phương pháp bottom-up. Các kết quả đánh giá đã cho thấy các thuật toán lai ghép đã khắc phục được phần nào hạn chế của các thuật toán top-down và bottom-up, đó là có thể thực hiện trên những trang ảnh với cấu trúc bất kì và ít hạn chế hơn vào các tham số khoảng cách. Tuy nhiên, việc xác định các đối tượng phân tách lại là một bài toán gặp phải rất nhiều khó khắn bởi nhiều lý do, ví dụ như có những vùng chữ ở quá gần nhau, các vùng chữ được căn lề, trái phải không thẳng hàng hoặc khoảng cách giữa các thành phần liên thông là quá lớn,... điều này đã làm cho các thuật toán hiện tại thường mắc phải các lỗi quên hoặc xác định nhầm các đường phần tách dẫn đến kết quả phân tách lỗi. 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 1.3.1. Độ đo Đánh giá các thuật toán phân tích trang ảnh tài liệu luôn là một vấn đề phức tạp vì nó phụ thuộc nhiều vào tập dữ liệu, ground-truth và phương pháp đánh giá. Vấn đề đánh giá chất lượng của các thuật toán phân tích trang đã nhận được nhiều sự quan tâm. Trong luận án này sử dụng ba đô đo: F-Measure, PSET-Measure và PRImA- Measure cho tất các đánh giá thực nghiệm. Độ đo PRImA-Measure đã được sử dụng thành công tại các cuộc thi phân tích trang quốc tế ở các năm 2009, 2011, 2013, 2015 và 2017. 1.3.2. Dữ liệu Trong luận án này, tôi sử dụng ba tập dữ liệu UW-III, tập dữ liệu PRImA và tập dữ liệu UNLV để đánh giá thực nghiệm và so sánh các thuật toán phân tích trang ảnh tài liệu. Tập UW- III có 1600 ảnh, tập PRImA có 305 ảnh và tập UNLV có 2000 ảnh. Các tập dữ liệu này đều có ground-truth ở cấp độ đoạn văn bản và cấp độ dòng chữ, được biểu diễn bởi các đa giác không giáo nhau. Các trang ảnh đều được quét với độ phân giải 300 DPI và đã được căn trỉnh lại độ 5
nghiêng. Nó chứa nhiều trang ảnh đa dạng về các kiểu trang ảnh, phản ảnh nhiều thách thức trong phân tích trang. Cấu trúc của trang ảnh chứa đựng một sự pha trộn từ đơn giản đến phức tạp, gồm nhiều bức ảnh có phần chữ bao quanh các trang ảnh, có sự thay đổi lớn về kích cỡ kiểu phông chữ. Do đó, đây là những tập dữ liệu rất tốt để thực hiện đánh giá so sánh các thuật toán phân tích trang. 1.4. Kết luận chương Chương này đã giới thiệu một cách tổng quan về lĩnh vực nhận dạng văn bản, trong đó phân tích trang là một khâu quan trọng. Cho đến nay bài toán phân tích trang vẫn là một vấn đề được nhiều nghiên cứu trong và ngoài nước quan tâm. Đã có nhiều thuật toán phân tích trang được đề xuất, đặc biệt là tại các cuộc thi phân tích trang quốc tế (ICDAR). Tuy nhiên các thuật toán vẫn mắc phải hai lỗi cơ bản: over-segmentation và under-segmentation. Vì vậy, luận án sẽ tập trung nghiên cứu các giải pháp cho bài toán phân tích trang ảnh tài liệu. Có ba hướng tiếp cận chính cho bài toán phân tích trang ảnh tài liệu: top-down, bottom-up và hybrid. Trong đó, hybrid là hướng tiếp cận được phát triển mạnh trong giái đoạn gần đây do nó khắc phục được nhược điểm của hai hướng tiếp cận top-down và bottom-up. Bởi vì lý đó đó, luận án sẽ phân tích trọng tâm hơn vào các thuật toán hybrid, đặc biệt là các kĩ thuật phát hiện và sử dụng các đối tượng phân tách của các thuật toán hybrid. Chương tiếp theo của luận án trình bày về một kĩ thuật phát hiện nền trang ảnh nhanh, kĩ thuật này sẽ được sử dụng như một module trong thuật toán được đề xuất ở Chương 3. 6
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 ưu, nhược điểm của 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 và cuối cùng là các kết quả thực nghiệm. 2.1. Ưu nhược điểm của 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 Về mặt trực quan, trong rất nhiều trường hợp có thể thấy phát hiện nền trang ảnh là dễ dàng hơn, đồng thời dựa trên nền trang ảnh có thể dễ dàng tách được trang ảnh thành các vùng ảnh khác nhau. Do vậy, từ rất sớm đã có nhiều thuật toán phân tích trang dựa trên nền trang ảnh được phát triển, ví dụ điển hình như, X-Y Cut, WhiteSpace-Analysis, WhiteSpace-Cuts, ...và gần đây cũng có nhiều thuật toán mạnh dựa trên trang ảnh được phát triển, ví dụ như, Fraunhofer (chiến thắng tại IC- DAR2009), Jouve (chiến thắng tại ICDAR2011), PAL (chiến thắng tại ICDAR2013),... Không chỉ trong phân tích trang, hướng tiếp cận dựa trên nền trang ảnh còn được ứng dụng rộng rãi trong bài toán phát hiện bảng, phân tích cấu trúc bảng, phân tích cấu trúc logic. Qua các ví dụ trên có thể thấy được hướng tiếp cận dựa trên nền trang ảnh có nhiều ưu điểm. Đã có nhiều thuật toán khác nhau được phát triển để phát hiện nền trang ảnh, ví dụ như X-Y Cuts, WhiteSpace-Analysis, WhiteSpace-Cuts (sau đây gọi tắt là WhiteSpace), ...Trong đó, WhiteSpace được biết đến như một thuật toán hình học rất nổi tiếng trong việc phát hiện nền trang ảnh, thuật toán có trong bộ mã nguồn mở OCROpus vì vậy nó được sử dụng rộng rãi như một bước cơ bản để phát triển thuật toán. Tuy nhiên, thuật toán WhiteSpace có hạn chế là thời gián thực thi khá chậm, xem Hình 2. Do đó, việc tăng tốc thuật toán WhiteSpace có nhiều ý nghĩa thực tiến. Hình 2: Minh họa thời gián thực thi trung bình của mỗi thuật toán. 2.2. Thuật toán phát hiện nền trang ảnh (WhiteSpace) cho bài toán phân tích trang 2.2.1. Định nghĩa Vùng trắng lớn nhất trong một trang ảnh được định nghĩa là hình chữ nhất lớn nhất nằm trong hình bao của trang ảnh và không chữ một kí tự nào, xem Hình 3. Hình 3: Hình chữ nhật màu xanh thể hiển cho vùng trắng lớn nhất tìm được. 7
2.2.2. Thuật toán tìm vùng trắng lớn nhất Thuật toán tìm vùng trắng lớn nhất (sau đây được gọi MaxWhitespace) có thể áp dụng cho các đối tượng là các điểm hoặc các hình chữ nhật. Ý tưởng mẫu chốt của thuật toán là phương pháp nhánh cận và thuật toán Quicksort. Hình 5 a) và 4 minh họa giả code của thuật toán và bước chia hình chữ nhật thành các hình chữ nhật con. Trong khuôn khổ của luận án này, đầu vào của thuật toán là một tập các hình chữ nhật rectangles (hình bao của các kí tự), hình chữ nhật bound (hình bao của cả trang ảnh) và hàm quality(rectangle) trả về diện tích của mỗi hình chữ nhật, xem Hình 4.a). Thuật toán định nghĩa một trang thái (state) bao gồm một hình chữ nhật r, tập các hình chữ nhật obstacles (hình bao của các kí tự) nằm trong hình chữ nhật r và diện tích của hình chữ nhật r (q = quality(r)). Trạng thái 𝑠𝑡𝑎𝑡𝑒𝑖 được định nghĩa là lớn hơn trạng thái 𝑠𝑡𝑎𝑡𝑒𝑗 nếu 𝑞𝑢𝑎𝑙𝑖𝑡𝑦(𝑟𝑖 ) > 𝑞𝑢𝑎𝑙𝑖𝑡𝑦(𝑟𝑗 ). Hàng đợi ưu tiên queue được sử dụng để lưu trữ các trạng thái. Mỗi vòng lặp thuật toán sẽ lấy ra trạng thái state = (q, r, obstacles) là đầu của hàng đợi ưu tiên, đây là trạng thái mà hình chữ nhật r có diện tích lớn nhất. Nếu không có hình chữ nhật obstacles nào chứa trong r thì r là vùng trắng hình chữ nhật lớn nhất tìm được và thuật toán kết thúc. Ngược lại, thuật toán sẽ chọn một trong các hình chữ nhật obstacles làm chốt (pivot), cách chọn tốt nhất là càng gần tâm của hình chữ nhật r càng tốt, xem Hình 4.b). Chúng ta biết rằng vùng trắng lớn nhất sẽ không chứa bất kì một hình chữ nhật obstacles nào vì vậy nó cũng sẽ không chứa pivot. Do đó, có bốn khả năng có thể xảy ra của vùng trắng lớn nhất: là bên trái và bên phải của pivot, xem Hình 4.c), hoặc bên trên và bên dưới của pivot, xem Hình 4.d). Tiếp theo, thuật toán sẽ xác định các hình chữ nhật obstacles giáo với mỗi hình chữ nhật con này, có bốn hình chữ nhật con 𝑟0 , 𝑟1 , 𝑟2 , 𝑟3 được sinh ra từ hình chữ nhật 𝑟, xem Hình 5 và tính toán chặn trên của vùng trắng lớn nhất có thể có trong mỗi hình chữ nhật con mới được tạo ra, chặn trên được lựa chọn chính là diện tích của mỗi hình chữ nhật con. Các hình chữ nhật con cùng với các obstacles nằm trong nó và chặn trên tương ứng với nó được đẩy vào hàng đợi ưu tiên và các bước trên được lặp lại cho đến khi xuất hiện trạng thái với hình chữ nhật r không chữ bất kì một obstacles nào. Hình chữ nhật này là nghiệm toàn cục của bài toán tìm vùng trắng lớn nhất. a) b) c) d) Hình 4: 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. 8
a) b) Hình 5: a) minh họa giả code của thuật toán tìm các vùng trắng lớn nhất. b) minh họa thuật toán tìm các vùng trắng bao phủ nền trang ảnh 2.2.3. Thuật toán phát hiện nền trang ảnh Để phát hiện nền trang ảnh thuật toán được đề xuất như một mô đun của thuật toán WhiteSpace áp dụng thuật toán MaxWhitespace Để tìm m — Whitespace vùng trắng (với m — Whitespace khoảng 300 là đủ Để mô tả tốt nền trang ảnh), sau đây thuật toán phát hiện nền được gọi là WhiteSpaceDetection. Sơ đồ của thuật toán được the hiện ở Hình 5 b). 2.3. Tăng tốc thuật toán phát hiện nền trang ảnh Để tìm các vùng trắng bao phủ nền của trang ảnh, thuật toán tìm vùng trắng chia đệ quy trang ảnh thành các vùng con sao cho vùng con tìm được không chứa một kí tự nào. Tại mỗi lần lặp thuật toán sẽ chia mỗi vùng con của trang ảnh thành bốn miền con khác nhau, xem Hình 6. Quá trình này sẽ tạo thành một cây tứ phân do vậy nếu vòng lặp lớn thì số lượng các miền còn cần được xem xét đến sẽ là rất lớn. Chính vì vậy thời gián thực thi của thuật toán thường rất chậm. Do đó, để tăng tốc thuật toán phát hiện nền trang ảnh cần phải làm giảm tối đa số các vùng con cần phải xét đến, bằng cách hạn chế sinh ra các nhanh con không cần thiết của cây tứ phân. Hình 6 cho thấy miền Z G (Vùng ông bà) được chia làm bốn miền con: miền con trên Z P T , miền con dưới Z P B , miền con trái Z P L và miền con phải Z P R . Tiếp tục chia miền Z P T , thì miền con phải Z C T R sẽ nằm trọn trong miền Z P R , nên khi xét đến miền Z P R thì cũng xem xét luôn miền Z C T R , hay miền Z C T R được xem xét lại. Ví dụ minh họa ở Hình 6 cho thấy miền con trên Z C R T của miền Z P R đã xét lại miền Z C T R . Quá trình phân chia này sẽ tạo thành một cây tứ phân và càng xuống sâu thì sẽ càng có nhiều các vùng con bị xem xét lại nhiều lần. Trong chương này, luận án đề xuất một giải pháp làm giảm tối đa số các miền con bị xét lại. Thuật toán được đề xuất (sau đây gọi là Fast-WhiteSpaceDetection) sẽ không sinh ra các miền con mà nó nằm trọn vẹn trong các miền con trước đó, bằng cách dựa vào vị trí tương đối giữa Pivot của miền đang xét với Pivot của miền cha. Như ví dụ ở Hình 6, miền con Z C T R sẽ không được sinh ra vì nó nằm trong miền (Z P R ). Tuy nhiên, chỉ xem xét loại bỏ các miền con theo từng cặp, hoặc miền con trái/phải hoặc miền con trên/dưới, trong tất cả các miền xem xét. Có nghĩa là, nếu xem xét loại bỏ các miền con trái/phải thì không được xem xét loại bỏ các miền con trên/dưới nữa, và ngược lại vì nếu xem xét loại bỏ ở tất cả bốn miền con thì sẽ có vùng không bao giờ được xét đến, dẫn đến sẽ bỏ sót một số vùng trắng. Ví dụ trong Hình 6, nếu xét loại bỏ ở 9
cả bốn miền con thì miền Z C T R và Z C R T sẽ bị loại bỏ nên một phần trong vùng giáo giữa hai miền này sẽ không được xét đến bao giờ. Do đó, thuật toán Fast-WhiteSpaceDetection cải tiến bước sinh ra các miên con như sau (Hình 7):  Sinh miền con trên.  Sinh miền con dưới.  Sinh miền con trái nếu tọa độ trái của Pivot của nó lớn hơn tọa độ trái của Pivot của miền cha và hai Pivot không chồng lên nhau theo chiều dọc.  Sinh miền con phải nếu tọa độ phải của Pivot của nó nhỏ hơn tọa độ phải của Pivot của miền cha và hai Pivot chồng lên nhau theo chiều dọc. 2.4. Thuật toán WhiteSpace và thuật toán Fast-WhiteSpace 2.4.1. Thuật toán WhiteSpaceThuật Hình 6: Minh họa mặt hạn chế dẫn đến làm giảm tốc độ của bước tìm các vùng trắng của thuật toán WhiteSpaceDetection. Miền Z C T R , ZC RT và các miền con của chúng sẽ được xét lại nhiều lần. a) b) Hình 7: Minh họa một trường hợp sinh các miền con của thuật toán WhiteSpaceDe- tection và thuật toán Fast-WhiteSpaceDetection. Hình a) minh họa kết quả sinh bốn miền con của thuật toán WhiteSpaceDetection. Hình b) minh họa kết quả sinh các miền con của thuật toán Fast-WhiteSpaceDetection. Phân tích cấu trúc nền của trang ảnh là một hướng tiếp cận được phát triển bởi nhiều tác giả. Tuy nhiên các hướng tiếp cận này đều khó cài đặt thực nghiệm, yêu cầu một số lượng lớn cấu trúc dữ liệu hình học và chi tiết với nhiều trường hợp đặc biệt. Bởi vậy những phương pháp này đã không được áp dụng rộng rãi. Thuật toán WhiteSpace được đề xuất bởi Breuel được phát biểu và cài đặt đơn giản, không phải xem xét đến các trường hợp đặc biệt. Các bước chính của thuật toán bao gồm: Bước 1 (Hình 8 b): Tìm và phân loại các thành phần liên thông thành ba nhóm dựa vào kích 10
thước: nhóm lớn là các đối tượng hình ảnh, đường kẻ,.. . nhóm vừa là các ký tự (CCs), nhóm nhỏ là các đối tượng nhiễu. Bước 2 (Hình 8 c): Tìm các vùng trắng hình chữ nhật. Bước 3: Từ các vùng trắng tìm được, lọc lấy các vùng trắng hình chữ nhật dọc (vspace) phân tách các cột và các vùng chữ nhật ngang (hspace) phân tách các đoạn dựa trên một số tiêu chí: kích thước và sự chồng gối lên nhau của các vùng trắng và mật độ kí tự liền kề với vùng trắng. Bước 4 (Hình 8 d): Tìm các vùng chữ bằng cách áp dụng thuật toán tìm các vùng trắng ở bước 2. Lúc này, các CCs được thay thế bằng các vspace và hspace. a) b) c) d) Hình 8: Minh họa các bước của thuật toán WhiteSpace. Hình a) thể hiện hình bao của các thành phân liên thông (CCs), b) các hình chữ nhật là các vùng trắng bao phủ nền của trang ảnh, c) 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, d) thể hiện kết quả của quá trình phân tách. 2.4.2. Thuật toán Fast-WhiteSpace Để tiến hành thực nghiệm cho thấy sự hiệu quả (tăng tốc độ nhưng không ảnh hưởng đến kết quả của quá trình phát hiện nền trang ảnh) của bước tìm nhanh nền trang ảnh. Luận án đã ứng dụng mô đun tìm nhanh nền để phát triển thuật toán Fast-WhiteSpace và thuật toán AOSM (AOSM sẽ được trình bày ở chương 3). Fast- WhiteSpace là sự kết hợp của thuật toán WhiteSpace với mô đun tìm nhanh nền trang ảnh. 2.5. Thực nghiệm và thảo luận Trong phần này chúng tôi trình bày các kết quả so sánh tốc độ và độ chính xác của Thuật toán Fast-WhiteSpace với thuật toán WhiteSpace trên tập dữ liệu UW-III. Hình 9 a) trình bày thời gián thực thi trung bình trên mỗi bức ảnh của thuật toán WhiteSpace và Fast-WhiteSpace. Cả hai thuật toán được thực nghiệm đồng thời trên máy tính PC, bộ xử lý Intel Pentium 4 CPU 3.4 GHz, bộ nhớ RAM 2 GB, hệ điều hành Windows 7 Ultimate Service Pack 1. Kết quả thực nghiệm đã cho thấy thuật toán Fast-WhiteSpace đạt tốc độ thực thi nhanh vượt trội so với thuật toán WhiteSpace gốc. Hình 9 b) trình bày kết quả đánh giá độ chính xác của các thuật toán trên tập dữ liệu UW- III với độ đo PSET. Độ chính xác của thuật toán Fast-WhiteSpace thay đổi không đáng kể so với thuật toán gốc và có kết quả tương đối tốt so với các thuật toán tiên tiến hiện nay, 91.87%của thuật toán AdWhiteSpace so với 93.84% của Tab-Stop và 79.45% của thuật toán RAST. 2.6. Kết luận chương 11
Trong chương này, luận án đã trình bày những lợi thế có được từ hướng tiếp cận dựa trên nền trang ảnh và cụ thể hóa bằng những dẫn chứng về những thuật toán mạnh dựa trên nền trang ảnh được phát triển. Luận án đã trình bày thuật toán phát hiện nền WhiteSpaceDetection và thuật toán phát hiện nền trang ảnh nhanh Fast- WhiteSpaceDetection. Các kết quả thực nghiệm đã chứng tỏ thuật toán WhiteSpace cải tiến (sử dụng Fast-WhiteSpaceDetection làm một mô đun) đạt tốc độ thực thi nhanh vượt trội, đồng thời độ chính xác hầu như không thay đổi so với thuật toán gốc. a) b) Hình 9: Minh họa thời gián thực thi và độ chính xác của thuật toán Fast-WhiteSpace so thuật toán WhiteSpace và các thuật toán tiêu biểu: a) thời gián thực thi, b) độ chính xác. 12
CHƯƠNG 3. THUẬT TOÁN PHÂN TÁCH TRANG ẢNH TÀI LIỆU 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: thuật toán lai ghép phân tích trang ở cấp độ đoạn văn bản (A hybrid paragraph-level page segmentation - sau đây gọi tắt là thuật toán HP2S), thuật toán phân tích trang tách quá và gộp lại bằng phương pháp tham số thích nghi (Adaptive over-split and merge for page segmentation - sau đây gọi tắt là thuật toán AOSM). Phần một trình bày mô hình phân tích trang của cả hai thuật toán HP2S và AOSM. Phần hai trình bày giái đoạn gom cụm từ các thành phân liên thông thành các vùng văn bản của thuật toán HP2S. Phần ba trình bày hai giái đoạn của thuật toán AOSM: giái đoạn 1 tách trang ảnh thành các vùng chữ ứng cử viên, giái đoạn 2 gộp các vùng chữ bị phân tách quá nhỏ thành các vùng chữ. Giái đoạn tách các vùng chữ thành các đoạn văn bản được trình bày trong phần bốn. Cuối cùng là các kết quả thực nghiệm trên các tập dữ liệu của các cuộc thi phân tích trang các năm 2009, 2015, 2017, tập dữ liệu UWIII và tập dữ liệu UNLV. 3.1. Mô hình phân tích trang của hai thuật toán HP2S và AOSM Các thuật toán phân tích trang theo hướng tiếp cận lai ghép (hybrid) là sự kết hợp của hai hướng tiếp cận từ trên xuống và từ dưới. Trong những năm gần đây đã có nhiều thuật toán mạnh phát triển theo hướng tiếp cận lai ghép. Ý tưởng chung của hướng tiếp cận lai ghép là sử dụng các thông tin ở cấp độ thấp (thông thường là các thành phần liên thông) để xác định các đối tượng phân tách từ đó suy ra cấu trúc cột của trang ảnh. Tức là có thể suy ra được trang ảnh có bao nhiêu cột văn bản và các cột văn bản sẽ nằm về các phía khác nhau của các đối tượng phân tách. Sau đó, áp dụng phương pháp gom cụm để nhóm các thành phần ở cấp độ thấp thành các vùng chữ. Cuối cùng tách các vùng chữ thành các đoạn văn bản. Trong phần này luận án trình bày mô hình phân tích trang của cả hai thuật toán HP2S và AOSM, xem Hình 10. Từ mô hình 10 có thể thấy HP2S và AOSM áp dụng chung phương pháp tách các vùng chữ thành các đoạn văn bản. Tuy nhiên, để xác định các vùng chữ hai thuật toán sử dụng hai cách tiếp cận khác nhau, xem Hình 11. HP2S sử dụng hướng tiếp cận từ dưới lên để gom cụm các thành phân liên thông thành các vùng chữ. Trong khi đó, AOSM sử dụng hướng tiếp cận từ trên xuống để chia trang ảnh thành các vùng chữ ứng cử viên, sau đó áp dụng phương pháp tham số thích nghi để nhóm các vùng chữ bị tách quá nhỏ lại với nhau. Hình 10: Mô hình chung của hai thuật toán HP2S và AOSM. 13
a) b) Hình 11: Sơ đồ thuật toán của cả hai thuật toán HP2S và AOSM: a) thuật toán HP2S, b) thuật toán AOSM. 3.2. Thuật toán HP2S Trong phần này, luận án trình bày các bước chính xác định vùng chữ của thuật toán HP2S. Quá trình này gồm ba bước chính như minh họa ở Hình 12. Bước đầu tiên, thuật toán sẽ phát hiện các đường phân tách (sau đây được gọi là các tab — line) giữa các cột văn bản. Bước 2, thuật toán sử dụng phép biến đổi Hough cùng với các tab — line để xác định các dòng chữ. Cuối cùng, các dòng chữ được nhóm lại thành các vùng chữ. Chi tiết của các bước này sẽ được trình bày tại các mục , , . 3.2.1. Phát hiên các đường phân tách Hình 12: 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. Thuật toán Tab-Stop đã trình bày vấn đề phát hiện các đường phân tách (tab-line) là dãy các kí tự ở đầu hoặc cuối mỗi dòng chữ (tab-stop) và thẳng hàng theo phương dọc. Các đường phần tách này có thể được sử dụng để thay thế cho các phân tách vật lý hay các khoảng trắng hình chữ nhật trong việc phát hiện cấu trúc cột của trang ảnh tài liệu. Trong phần này, tôi trình bày một phương pháp đơn giản để phát hiện các tab-lines. Thuật toán HP2S đã đề một phương pháp xác định các tab - line được thực hiện ít bước hơn, đơn giản hơn và dễ dàng cài đặt thực nghiệm. 3.2.2. Xác Định các dòng chữ Trước tiên, phép biến đổi Hough được thực hiện trên tập hợp các trung điểm của các cạnh đáy của các kí tự để từ đó tìm ra dãy các kí tự thẳng hàng theo phương ngang. Mỗi dãy các kí tự thẳng hàng theo phương ngang sẽ là các ứng cử viên tốt nhất để tạo thành các dòng chữ. Mỗi dãy các kí tự này được gọi là các dòng chữ ứng cử viên, xem Hình 13 và 14. Đối với mỗi dòng chữ ứng cử viên, thuật toán ước lượng khoảng cách theo phương ngang của các kí tự và các từ kề nhau theo phương ngang, khoảng cách giữa các từ được kí hiệu là dw. Khoảng cách d w sẽ được 14
sử dụng cùng với các đường phân tách để tách các dòng chữ ứng cử viên thành các dòng chữ như sau: hai kí tự kề nhau theo phương ngang là thuộc cùng một dòng chữ nếu chúng không nằm về hai phía của một đường phân tách nào đó đồng thời khoảng cách theo phương ngang của chúng không vượt quá hai lần dw. Sự kết hợp giữa các đường phân tách với phương pháp truyền thống từ dưới lên để xác định các dòng chữ đã giúp thuật toán tách được các dòng chữ ở các cột văn bản ở rất gần nhau. Trong một số trường hợp khoảng cách giữa hai cột gần như là tương đương với khoảng cách giữa các từ trên các dòng chữ ứng cử viên (13a). Tuy nhiên, sự tồn tại của các đường phân tách theo phương đứng đã giúp thuật toán tách các dòng chữ ứng cử viên thành các dòng chữ khác nhau năm về các cột khác nhau, xem Hình 13b). Khi các cột văn bản không được căn lề thẳng hàng thì sẽ không tồn tại các đường phân và khí đó tham số dw sẽ là hữu ích trong quá trình xác định các dòng chữ. Hầu hết trong các trường hợp này, khoảng cách giữa các dòng chữ d là lớn hơn khoảng cách giữa các từ dw (Hình 14). Khác với các thuật toán bottom-up truyền thống, thuật toán của chúng tôi không sử dụng một tham số dw cho tất cả các dòng chữ ứng cử viên. Tham số dw được ước lượng trên mỗi tập các kí tự có kích cỡ phông chữ tương tự nhau và thuộc cùng một dòng chữ ứng cử viên. Do đó, điều này đã giúp thuật toán giảm đáng kề lỗi phân mảnh dòng chữ, đặc biệt là các dòng chữ ở phần tiêu đề (Hình 13b). a) b) Hình 13: Minh họa 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. a) b) Hình 14: 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, d w được sử dụng để tách các kí tự thành các dòng chữ. Trong một số trường hợp, ví dụ như các vùng chữ phần tại liệu tham khảo hoặc các đoạn văn bản bắt đầu với các kí tự đặc biệt, các vùng chữ thường được căn lề thẳng hàng và thụt vào so với các chỉ số và kí tự đặc biệt. Do đó, các đường phần tách sẽ tách các chỉ số hay các kí tự đặc biệt ra khỏi các dòng chữ. Để khắc phục kiểu lỗi này, trước tiên chúng tôi tìm thêm các tab-stop ứng cử viên bằng các áp dụng phương pháp tìm các tab-stop tương tự như mục với chiều rộng của hình chữ nhật kề phải chỉ bằng một của chiều rộng của kí tự đang xét. Sau đó, các tab-stop ứng cử viên mới tìm được mà giáo với các tab-stop ứng cử viên trái được xác định từ mục thì cập nhật là tab-stop phần tài liệu tham khảo hay đó là các kí tự đặc biệt và kí hiệu là m - tabs. Các m - tabs là các kí tự đã bị tách ra khỏi dòng chữ do sự xuất hiện của các đường phân tách. Cuối cùng, thuật toán sẽ kết hợp các m - tabs với các dòng chữ kề phải và gán nhán là các dòng chữ phân tách. Các dòng chữ phân tách này sẽ được sử dụng lại ở mục để xác định các đoạn văn bản. 15
3.2.3. Gom cụm các dòng chữ thành các vùng chữ Trong phần này, trình bày quá trình gom cụm các dòng chữ thành các vùng chữ. Hướng tiếp cận bottom-up được sử dụng để nhóm các dòng chữ gần kề để hình thành các vùng chữ với hình bao bất kì. Tập các dòng chữ được xác định từ phần trước được sắp xếp lại theo thứ tự từ trái qua phải, từ trên xuống dưới. Một cặp các dòng chữ (𝑙𝑖𝑛𝑒𝑖 , 𝑙𝑖𝑛𝑒𝑗 ) thỏa mãn đồng thời các điều kiện dưới đây sẽ được nhóm vào cùng một vùng chữ. a) b) c) Hình 15: a) Ảnh gốc, b) các đường phân tách, c) các vùng chữ được xác định. Trong các điều kiện trên, DisHoriz(.,.) là khoảng cách theo phương ngang giữa các dòng chữ. AvgHoriz là khoảng cách trung bình theo phương ngang của các dòng chữ, 𝑦𝑖 và 𝑦𝑗 lần lượt là tung độ của tâm của các dòng chữ line i và 𝑙𝑖𝑛𝑒𝑗 . 𝑥 − ℎ𝑒𝑖𝑔ℎ𝑡𝑖𝑗 là giá trị nhỏ nhất của 𝑥 − ℎ𝑒𝑖𝑔ℎ𝑡𝑖 và 𝑥 − ℎ𝑒𝑖𝑔ℎ𝑡𝑗 . CheckTabline (., .) trả về giá trị true nếu hai dòng chữ nằm về hai phía các dòng của một đường phân tách bất kì, ngoài ra trả về giá trị false. CheckRulling (., .) trả về giá trị true nếu hai dòng chữ nằm về hai phía khác nhau của một được kẻ ngang, ngoài ra trả về giá trị false. Các điều kiện (i) và (ii) đảm bảo tách các dòng chữ thành các cột khác nhau. Điều này được thực hiện bằng cách sử dụng sự kết hợp của các đường phân tách và điều kiện gom cụm chặt chẽ. Điều kiện (iv) cho phép chỉ nhóm các dòng chữ có kích cỡ phông chữ tương tự nhau và chồng lên nhau theo chiều dọc. Điều đáng giá là điều kiện (iv) ủng hộ các dòng chữ có kích cỡ phông chữ tương tự nhau và trở nên nghiêm ngặt khi kích cỡ phông chữ khác nhau. Trong một khía cạnh khác, khoảng cách giữa các tâm của hai dòng chữ ở phía bên trái của (iv) tính cả kích cỡ phông chữ lớn trong khi bên trái của (iv) tính kích cỡ phông nhỏ. Kết quả thực nghiệm được chỉ ra ở Hình 26 cho thấy HP2S ít nhạy cảm với các giá trị của thám số 𝜃. Các giá trị 𝜃 phù hợp nhất là trong phạm vị giữa 1.4 đến 1.6. Do đó, thuật toán sử dụng giá trị mặc định là 1.5 cho tất cả các thực nghiệm. 3.3. Thuật toán AOSM Trong phần này, luận án trình bày quá trình xác định các vùng chữ của thuật toán AOSM. Quá trình này gồm hai giái đoạn chính như sau (Hình 16): Giái đoạn 1: Tách quá trang ảnh thành các vùng chữ ứng cử viên. Giái đoạn 2: Gộp các vùng chữ ứng cử viên bị tách quá lại thành các vùng chữ. 16
Hình 16: 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. 3.3.1. Xác định các vùng chữ ứng cử viên Các phân tách phổ biến nhất được áp dụng bởi một trong các thuật toán Hybrid hàng đầu hiện nay là các vùng trắng hình chư nhật, ví dụ như thuật toán RAST, Fraunhofer hay dây chuyên các vùng trắng, ví dụ như PAL hay dây chuyên các kí tự ở đầu hoặc cuối dòng, ví dụ như Tab- Stop, ETIPA. Các phương pháp dựa trên các phân tách này đều phụ thuộc vào hai bước:  Bước 1: trích rút các phân tách ứng cử viên,  Bước 2: lựa chọn và nhóm các phân tách ứng cử viên thành các đường phân tách tốt nhất. Do đó, các thuật toán hybird thường nhạy cảm vào kết quả của quá trình phát hiện các đối tượng phân tách, nếu xác định thiếu thì sẽ dẫn đến lỗi under-segmentation, nếu xác định sai thì sẽ dẫn đến lỗi over-segmentation. Để khắc phục được nhược điểm của bước xác định các phân tách chúng tôi một giải pháp đơn giản và hiệu quả sau:  Bước 1: để trích rút các phân tách ứng cử viên (vùng trắng) chúng tôi sử dụng thuật toán WhiteSpace, là một thuật toán phát hiện đơn gián và hiệu quả đặc biệt thuật toán đã có mã nguồn mở.  Bước 2: tập các vùng trắng ứng cử viên tìm được ở bước 1 đều được sử dụng làm các phân tách để từ đó chia trang ảnh thành các vùng chư ứng cử viên. Với cách tiếp cận này thuật toán AOSM có thể khắc phục được hạn chế nhược điểm của cácphương pháp phát hiện phân tách mạnh nhất hiện nay. Một điều khá thú vị là các vùng chữ ứng cử viên được xác định một cách rất dễ dàng bằng cách loại bỏ đi các đối tượng phân tách, xem Hình 17 c) và 17 d). Đồng thời kết quả của việc phân tích khi sử dụng toàn bộ các vùng trắng sẽ khắc phục hầu như hoàn toàn lỗi under-segmentation bị gây ra do cấu trúc trang hay các vùng trang ảnh ở quá gần nhau. Tuy nhiên, có thể có những vùng chữ sẽ bị phân tích quá nhỏ (over-segmentation), xem Hình 17. Các vùng chữ bị tách quá nhỏ này có thể kiểm soát được và sẽ được khắc phục ở giai đoạn 2 của thuật toán AOSM. 17
Hình 17: Minh họa các bước kết quả của giải đ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. 3.3.2. Gom cụm các vùng chữ bị over-segmentation Những vùng mà có số dòng chữ đủ nhỏ sẽ được xem là mắc lỗi over-segmentation. Tất cả các dòng chữ thuộc các vùng chữ này sẽ được nhóm lại với nhau bằng phương pháp tham số thích nghi được phát biểu như sau: Hai dòng chữ 𝑙𝑖𝑛𝑒𝑖 và 𝑙𝑖𝑛𝑒𝑗 (thuộc hai vùng chữ lân cận) được xem xét để nhóm vào một vùng nếu thỏa mãn các điều kiện dưới đây (xem Hình 18) ở đây, 𝑦𝑖 và 𝑦𝑗 lần lượt là tung độ của tâm các dòng chữ 𝑙𝑖𝑛𝑒𝑖 và 𝑙𝑖𝑛𝑒𝑗 , x — height là chiều cao của các kí tự xuất hiện nhiều nhất trong một dòng chữ, 𝑥 − ℎ𝑒𝑖𝑔ℎ𝑡𝑖𝑗 là chiều cao 𝑥— ℎ𝑒𝑖𝑔ℎ𝑡 nhỏ nhất của hai dòng chữ. Tham số 𝜃 được sử dụng để xác định khoảng cách lân cận theo phương thẳng đứng giữa hai dòng chữ trong cùng một vùng ảnh. Những điều kiện này có nghĩa là hai dòng chữ sẽ được nhóm vào cùng một vùng nếu chúng đủ gần nhau theo phương ngang (i) hoặc đủ gần nhau theo phương dọc (ii). Một vấn đề rất đáng giá đó là điều kiện (ii) cho phép thuật toán không chỉ có thể đánh giá được khoảng cách theo phương dọc giữa các dòng chữ mà còn có thể đánh giá được sự chênh lệch về kích cỡ phông chữ giữa các dòng chữ. Điều kiện (ii) ủng hộ việc nhóm hai dòng chữ có kích cỡ phông tương tự nhau và nghiêm khắc hơn với những dòng chữ có kích cỡ phông khác nhau nhiều. Các kết quả thực nghiệm đã cho thấy thuật toán AOSM ít nhạy cảm với tham số 𝜃 (Hình 26) và các giá trị phù hợp của 𝜃 là trong khoảng 1.4 và 1.6. Do đó, giá trị mặc định 1.5 được lựa chọn trong tất cả các thực nghiệm. Giá trị 1.5 tương ứng với giãn dòng 1.5 chiều cao dòng chữ của nhiều định dạng văn bản. Hình 18: Minh họa cho phương pháp tham số thích nghi. Hai dòng chữ 𝑙𝑖𝑛𝑒𝑖 , 𝑙𝑖𝑛𝑒𝑗 có khoảng cách theo phương dọc lớn hơn khoảng cách theo phương dọc giữa hai dòng chữ 𝑙𝑖𝑛𝑒𝑖 , 𝑙𝑖𝑛𝑒𝑘 . Tuy nhiên, hai dòng chữ 𝑙𝑖𝑛𝑒𝑖 , 𝑙𝑖𝑛𝑒𝑗 được xem xét là cùng một nhóm vì |𝑦𝑖 − 𝑦𝑗 | < (1 + 𝜃) ∗ 𝑥 − ℎ𝑒𝑖𝑔ℎ𝑡𝑖𝑗 , còn hai dòng chữ 𝑙𝑖𝑛𝑒𝑖 , 𝑙𝑖𝑛𝑒𝑘 lại không cùng thuộc một nhóm vì |𝑦𝑘 − 𝑦𝑗 | < (1 + 𝜃) ∗ 𝑥 − ℎ𝑒𝑖𝑔ℎ𝑡𝑗𝑘 . 18
Hình 19 chỉ ra một ví dụ nhóm các dòng chữ bị phân tách quá nhỏ thành vùng chữ. Các dòng chữ vùng tiêu đề thường bị phân tách quá nhỏ vì khoảng cách giữa các dòng chữ lớn. Thuật toán AOSM sẽ gộp các dòng chữ này vào cùng một vùng chữ dựa trên sự tương tự của chiều cao và mỗi liên hệ khoảng cách giữa chúng. Các dòng chữ vùng tiêu đề và các dòng chữ phần nội dung không bị nhóm lại với nhau do khoảng cách tương quan giữa tâm của các dòng chữ lớn. a) b) Hình 19: Minh họa kết quả của quá trình nhóm các dòng chữ bị over-segmentation: a) các dòng chữ bị over- segmentation; b) kết quả sau khi gom cụm. 3.4. Xác định các đoạn văn bản 3.4.1. Định nghĩa các dòng chữ phân tách Để tách các vùng chữ thành các đoạn văn bản thuật toán HP2S và AOSM sử dụng năm kieu dòng chữ phân tách được minh họa như Hình 20. a) b) c) d) e) Hình 20: Các hình chữ nhật "nét đứt” the hiện cho các dòng chữ phân tách được định nghĩa. Tách các vùng chữ thuần nhất thành các đoạn văn bản. Những khó trong phân tích trang văn bản không chỉ là cấu trúc trang ảnh văn bản phức tạp hay sự thay đổi kiểu hay kích cỡ phông chữ mà còn vấn đề khoảng cách giữa các vùng chữ ở quá gần nhau. Khoảng giữa các dòng chữ, vùng chữ đôi khi còn nhỏ hơn cả khoảng cách giữa các từ trên cùng một dòng chữ. Đây là một thách thức mà hầu hết các thuật toán phân tích trang dựa trên các đối tương phân tách và việc phân tích các thành phần liên thông đều thất bài. Để vượt qua khó khăn này, thuật toán HP2S và AOSM sử dụng một tập các dòng chữ phân tách để chia nhỏ những vùng chữ các đoạn văn bản. Quá trình xác định các đoạn văn bản được thực hiện như sau: thuật toán duyệt từ trên xuống dưới và từ dưới lên trên của mỗi vùng chữ để không cắt qua các dòng chữ phân tách (Hình 20.b) hay 20.c), và rồi chia tiếp mỗi vùng thành các vùng con (Bước 1 ở Hình 21.d). Và sau đó, các dòng chữ trong những vùng con này được sắp xếp lại theo thứ tự dọc và ngang, (bước 2 ở Hình 21.d). Cuối cùng, các đoạn văn bản được xác định bằng cách sử dụng các dòng chữ phân tách ở Hình 20.a), 20.d) hoặc 20.e) (bước 3 ở Hình 21.d). 19
Như đã được minh họa ở Hình 21, các dòng chữ phân tách đã cho thấy sự hiểu quả trong việc phân tách các vùng chữ có kích cơ phông tương tự nhau, ở rất gần nhau và có cấu trúc rất phức tạp. Những thuật toán top-down và bottom-up truyền thống hầu như thất bại trong trường hợp này. a) b) c) d) Hình 21: Tách các vùng chữ thuần nhất thành các đoạn văn bản: a) kết quả phân tách không sử dụng các dòng chữ phân tách, b) 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 sử dụng các dòng chữ phân tách, e) kết quả phân tách cuối cùng. 3.5. Thực nghiệm và thảo luận 3.5.1. Các thuật toán, tập dữ liệu và đô đo Trong phần này, luận án trình bày các kết quả đánh giá thực nghiệm thuật toán HP2S, AOSM và Fast-AOSM (Fast-AOSM là thuật toán AOSM sử dụng mô đun tìm nhanh các vùng trắng được trình bày ở Chương 2) với các thuật toán tiêu biểu cho các hướng tiếp cận của các thuật toán phân tích trang, các hệ thống phân tích trang tốp đầu trong các cuộc thi phân tích trang quốc tế ICDAR2009, ICDAR2015 và ICDAR2015, các sản phẩm thương mại và các hệ thống mã nguồn mở nổi tiếng.  Các thuật toán tiêu biểu cho các hướng tiếp cận to-down, bottom –up và hybrid bao gồm các thuật toán: Docstrum, Voronoi, WhiteSpace, Tab-Stop.  Các hệ thống tốp đầu trong các cuộc thi phân tích trang quốc tế ICDAR2009, ICDAR2015 và ICDAR2017.  Các sản phẩm thương mại nổi tiếng: Fine Reader 8.1, 10, 11 và 12 sau đây lần lượt được kí hiệu là: FRE 8.1, FRE 10, FRE 11, FRE 12.  Các hệ thống mã nguồn mở nổi tiếng: OCRopus 0.3.1, Tesseract 3.02, Tesseract 3.03, Tesseract 3.04. Các kết quả thực nghiệm được thực hiện trên các tập dữ liệu nổi tiếng là UWIII, UNLV, ICDAR2009 dataset, ICDAR2015 dataset và ICDAR2017 dataset. Các độ đo mà chúng tôi sử dụng bao gồm F-Measure, PSET và độ đo PRImA với các ngữ cảnh đánh giá khác nhau đã được sử dụng để đánh giá thành công các thuật toán phân tích trang tại các cuộc thi ICDA2009, ICDAR2011, ICDAR2013 và ICDAR2015. 20