1
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
2
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
3
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.
4
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).
5
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 độ
