1

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

BÙI PHƢƠNG THẢO PHƢƠNG PHÁP PHÂN TÍCH TRANG VĂN
BẢN DỰA TRÊN TAB-STOP Chuyên ngành : Khoa học máy tính
Mã số : 60.48.01
Luận văn thạc sĩ khoa học máy tính
Ngƣời hƣớng dẫn khoa học:
TS. Nguyễn Đức Dũng

Một giải pháp được đưa ra đó là xây dựng các hệ thống nhận dạng chữ trong
các tấm ảnh chứa cả chữ và đối tượng đồ họa, sau đó chuyển thành dạng trang văn
bản và có thể mở, soạn thảo được trên các trình soạn thảo văn bản. Một cách tổng
quát thì cách thức hoạt động của một hệ thống nhận dạng chữ đó như sau [5]:
1. Chụp ảnh hoặc scan các trang tài liệu và lưu lại trên máy tính dưới dạng hình
ảnh.
3

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

2. Phân tích hình ảnh sau khi quét, đọc được ký tự trên hình ảnh và ghi lại vào máy
tính theo cách mà máy tính quản lý được thông tin dữ liệu đó.
- Bước 1: phân tích cấu trúc của ảnh tài liệu, từ đó xác định đâu là phần chứa ký
tự, đâu là phần chứa cả ảnh lẫn ký tự và đâu chỉ chứa hình ảnh. Bước này thực
sự quan trọng cho bước nhận dạng. Bởi nó định vị chính xác cho việc áp dụng
các thuật toán nhận dạng lên vùng đã xác định tính chất, nếu bước này chính xác
trước tiên nó hạn chế thời gian cho việc nhận dạng, sau là tăng ngữ nghĩa bổ
sung cho việc nhận dạng.
- Bước 2: nhận dạng ký tự dựa vào các tính chất của ký tự, ví dụ như sắp xếp theo
dòng, khoảng cách giữa 2 từ lớn hơn khoảng cách giữa 2 ký tự, dùng trí tuệ nhân
tạo để dự đoán các ký tự kề nhau phải như thế nào, các từ trong câu phải như thế
nào để câu có nghĩa. Từ đó có nội dung đúng để lưu trữ, quản lý….
Trong thực tế không phải quá trình nhận dạng nào cũng chỉ trải qua hai bước
như trên, bởi vì có rất nhiều tham số ảnh hưởng đến kết quả của các chương trình
nhận dạng như nhiễu, Font chữ, kích thước chữ, kiểu chữ nghiêng, đậm, gạch dưới.
Ngoài ra các dòng chữ cũng có thể trộn lẫn với các đối tượng đồ họa, vì thế trước
khi nhận dạng chữ, một số thao tác tiền xử lý sẽ được tác động lên ảnh như, lọc
nhiễu, chỉnh góc nghiêng và đặc biệt quan trọng là phân tích trang tài liệu để xác
định cấu trúc của trang văn bản đồng thời tách biệt hai thành phần là chữ và các đối
tượng đồ họa.

2.4. Phƣơng pháp nghiên cứu
 Tìm kiếm, tham khảo, tổng hợp tài liệu từ các nguồn khác nhau để xây dựng
phần lý thuyết cho luận văn.
 Sử dụng các kỹ thuật được áp dụng phân tích trang tài liệu để làm rõ bản chất
của các vấn đề được đưa ra trong phần lý thuyết.
 Xây dựng chương trình Demo.
2.5. Phạm vi nghiên cứu
Bài toán phân tích trang tài liệu đã được phát triển với nhiều thành tựu trong
thực tế, có rất nhiều thuật toán tối ưu đã được các nhà khoa học đề nghị. Tuy nhiên
có thể nói chưa có một chương trình nào có thể “đọc” một ảnh văn bản như con
người, vì thực tế có rất nhiều kiểu trang văn bản khác nhau, khác nhau về cấu trúc
5

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

trình bày, ngôn ngữ, kiểu font, chữ viết tay,… Đây thực sự là một bài toán lớn,
chính vì thế trong phạm vi của luận văn chỉ tìm hiểu một số kỹ thuật phân tích trang
văn bản tiêu biểu với mục đích để so sánh với một thuật toán mới chưa được đưa ra
ở các đề tài trước. Cuối cùng, dựa vào đó để xây dựng Demo cho một ứng dụng.
Các kết quả nghiên cứu dự kiến cần đạt được:
 Tìm hiểu tài liệu liên quan đến lĩnh vực quan tâm để nắm bắt được bản chất
vấn đề đặt ra.
 Báo cáo lý thuyết
 Chương trình Demo.
3. Bố cục của luận văn
Nội dung của luận văn được trình bày trong ba chương với nội dung chính sau:
Chƣơng 1: Trình bày nội dung trang văn bản và các phương pháp tiền xử
lý trang văn bản, cấu trúc trang tài liệu và quá trình phân tích trang tài liệu
Chƣơng 2: Trình bày một số phương pháp phân tích trang tài liệu, từ đó
đánh giá ưu nhược điểm để lựa chọn kỹ thuật Tab-Stop cho chương trình thử

Hình 1: Sơ đồ tổng quan quá trình tạo ảnh tài liệu

Tài liệu
Thiết bị thu nhận ảnh
Ảnh số tài liệu
7

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 2: Ví dụ ảnh tài liệu
1.1.2. Nhận dạng tài liệu và vai trò của phân tích ảnh tài liệu
Ngày nay, máy tính đang phát triển mạnh mẽ, tốc độ xử lý không ngừng
được nâng lên. Cùng với nó là sự ra đời của các phần mềm thông minh đã khiến
máy tính ngày một gần gũi với con người hơn. Một trong các khả năng tuyệt vời
của con người mà các nhà khoa học máy tính muốn đạt được đó là khả năng nhận
dạng và lĩnh vực nhận dạng thu được nhiều thành công nhất là nhận dạng ký tự
quang OCR–Optical Character Recognition. OCR có thể được hiểu là quá trình
chuyển đổi tài liệu dưới dạng file ảnh số hoá (là dạng chỉ có người đọc được) thành
tài liệu dưới dạng file văn bản (là tài liệu mà cả người và máy đều có thể đọc được).
OCR có rất nhiều ứng dụng hữu ích trong cuộc sống như:
- Sắp xếp thư tín, dựa vào việc nhận dạng mã bưu chính (Zipcode) hay địa chỉ
gửi tới.
- Tự động thu thập dữ liệu từ các mẫu đơn/báo biểu hay từ các hồ sơ lao động.
- Hệ thống tự động kiểm tra trong ngân hàng (tự động xác nhận chữ ký)
- Tự động xử lý các hóa đơn hay các yêu cầu thanh toán
- Hệ thống tự động đọc và kiểm tra passport
- Tự động phục hồi và copy tài liệu từ các ảnh quét.
- Máy đọc cho những người khiếm thính
- Các ứng dụng Datamining

(hay bố cục vật lý) và cấu trúc logic mô tả mối quan hệ logic giữa các vùng đối
tượng trong tài liệu.
1.2.1. Cấu trúc vật lý
Bố cục vật lý của một tài liệu mô tả vị trí và các đường danh giới giữa các
vùng có nội dung khác nhau trong một trang tài liệu[6]. Quá trình phân tích bố cục
tài liệu là thực hiện việc tách từ một trang tài liệu ban đầu thành các vùng có nội
dung cơ sở như hình ảnh nền, vùng văn bản,…
Để mô tả bố cục vật lý của tài liệu người ta sử dụng một cấu trúc hình học
với mỗi đối tượng trong cấu trúc là một phần tử chỉ chứa nội dung đồng nhất. Các
kiểu đối tượng hình học được định nghĩa như sau[4]:
 Block là đối tượng cơ sở tương ứng với một vùng hình chữ nhật chứa một phần
nội dụng của tài liệu.
 Frame một đối tượng hỗn hợp tương ứng với một hình chữ nhật bao gồm một
hoặc nhiều block hoặc bao gồm các frame.
 Page là đối tượng hình học hoặc hỗn hợp các thành phần cơ sở tương ứng với
một vùng hình chữ nhật, nếu là đối tượng hỗn hợp nó chứa một hoặc nhiều
block, một hoặc nhiều frame.
 Page set (tập trang) là một tập của một hoặc nhiều page.
 Điểm gốc của cấu trúc (hay nút gốc) là một đối tượng ở mức cao nhất trong sơ
đồ phân cấp của cấu trúc hình học tài liệu. Hình 4(b) cho ví dụ một cấu trúc hình
học mô tả bố cục vật lý của trang tài liệu tương ứng.
Các thuật toán phân tích bố cục tài liệu có thể được chia làm ba loại chính
dựa theo phương pháp thực hiện của nó.
- Bottom-up: Ý tưởng chính của các thuật toán loại này là bắt đầu từ những
phần tử nhỏ nhất (như từ các pixel hay các phần tử liên thông) sau đó liên
tục nhóm chúng lại thành các vùng lớn hơn.
- Top-down: Thuật toán này bắt đầu từ vùng lớn nhất chứa cả trang tài liệu
sau đó liên tục phân chia thành các vùng nhỏ hơn.
10


chính xác. Hình 4(c,d) mô tả một ví dụ cấu trúc logic của tài liệu.

11

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

1.3. Quá trình phân tích tài liệu
Ảnh tài liệu chứa rất nhiều loại vùng thông tin khác nhau như các block,
lines, words, figures, tables và background. Ta có thể gọi các vùng này theo chức
năng của nó trong tài liệu hoặc gán cho nó các nhãn logic như sentences, titles,
captions, address,… Quá trình phân tích tài liệu là thực hiện việc tách một tài liệu
thành các vùng theo một tiêu chuẩn hay mối quan hệ lẫn nhau nào đấy. Công việc
này được thực hiện qua nhiều bước như tiền xử lý, tách vùng, lặp cấu trúc tài
liệu,…
Một số loại tài liệu như báo, tạp chí, sách quảng cáo, chúng có cấu trúc và bố
cục rất phức tạp và không có một form chung nào cả (Hình 5). Với con người để có
thể đọc hiểu được một trang tài liệu còn cần thêm nhiều kiến thức bổ sung như ngôn
ngữ, hoàn cảnh, các luật ngầm định, vì thế việc tự động phân tích các trang tài liệu
một cách tổng quát là một việc rất khó khăn thậm chí là không khả thi ngay cả với
các hệ thống phân tích tài liệu tiên tiến nhất[6].

Hình 5: Ví dụ loại tài liệu có bố cục phức tap

12

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên


- Dựa theo độ đo xác suất xuất hiện của mỗi điểm ảnh mà phân lớp nó vào
nền hay phần nổi
- Dựa vào các pixel liên thông kết hợp với mạng noron để phân tách.

Hình 7: a - Ảnh gốc b - Ảnh sau khi tách nền
 Xác định góc nghiêng:
Do quá trình thu nhận ảnh (như đặt lệch tài liệu khi scan,…) ảnh tài liệu thu
được rất có thể bị nghiêng, tức trục của các dòng văn bản không song song với trục
ngang (Hình 8). Việc xác định được góc nghiêng và xoay lại tài liệu là một khâu rất
quan trọng ảnh hưởng đến hiệu quả trong một số thuật toán phân tích. Ví dụ như các
thuật toán dựa theo biểu đồ sau phép chiếu nghiêng để tiến hành phân tích thì sẽ
hoàn toàn thất bại nếu văn bản bị nghiêng. Tuy nhiên việc có thể tự động ước lượng
được chính xác góc nghiêng của ảnh tài liệu là một bài toán khó.
Có nhiều kỹ thuật để có thể xác định được góc nghiêng của tài liệu, điểm
chung trong hầu hết các thuật toán là xác định góc nghiêng bằng việc xác định
hướng của các dòng văn bản dựa vào vị trí một số ký tự trong tài liệu.
1.3.2. Phân tích cấu trúc vật lý
Phân tích tài liệu được định nghĩa là quá trình xác định cấu trúc vật lý của
14

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

một tài liệu. Trong khâu này thì từ một ảnh tài liệu đầu vào sẽ được chia thành một
số khối (block) chứa các nội dung thành phần của tài liệu như các dòng văn bản,
tiêu đề, đồ họa, cùng với có hoặc không các tri thức biết trước về định dạng của
nó[6].
Có một số phương pháp phân tích và được phân ra làm hai loại như sau:
 Các phương thức có thứ bậc: Trong quá trình chia tài liệu thành các
block chúng ta quan tâm đến mối quan hệ về mặt hình học giữa các
block. Có ba phương pháp thuộc loại này là:

document(page)
article(page)
article(page)
sub-title
paragraphs
abstract
sub-title
paragraphs
sub-title
paragraphs

16

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

thảo văn bản thông dụng như Office, Wordpad,… (Hình 10)
Môi trƣờng
 PC với hệ điều hành Windows 9x, ME, 2000, XP, NT,… Tiện ích: Bộ gõ chữ
Việt, bộ font ABC, VNI, Unicode,
Thông tin đƣa vào
 Quét trực tiếp các loại sách báo, văn bản qua máy quét (Scanner).
 Đọc và xử lý hơn 30 dạng tệp tin ảnh phổ dụng nhất như PCX, BMP, TIF, GIF,
JPG,
 Có thể nhận dạng trực tiếp tài liệu quét qua Scanner không cần lưu trữ dưới dạng
tệp ảnh trung gian. Các trang tài liệu có thể được quét và lưu trữ dưới dạng tệp
tin nhiều trang.
Các chức năng chính:
- Phân tích cấu trúc vật lý của tài liệu và đưa ra cấu trúc phân vùng
- Phân tích và nhận dạng chữ đầu ra là text có thể copy hay lưu trữ và soạn
thảo lại được.

19

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Kết quả phân tích bởi VnDOCR bỏ sót một vùng văn bản và gộp nhầm 2
vùng ảnh vào vùng văn bản số 1 (Hình 14).

Hình 14: Kết quả phân tích với ảnh 13
1.4.2. OminiPage
OmniPage là phần mềm nhận dạng văn bản của NUANCE. Nó có thể chuyển
đổi các file ảnh tài liệu hay file PDF sang dạng file văn bản có thể đọc được bởi các
phần mềm soạn thảo như Office, với khả năng nhận dạng các ký tự la tinh chính xác
tới 99%.
Một số đặc tính chính:
- Nhận dạng chính xác tới 99% trên 119 ngôn ngữ khác nhau
- Nhận dạng cả các file vào là PDF
- Nhận dạng được các trang có nhiều loại font, kiểu font hoặc có nền là ảnh
mầu
20

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

- Một số hạn chế chính:
Chưa hiệu quả với các ảnh tài liệu có cấu trúc phức tạp.
Thí nghiệm 1:
Với ảnh đầu vào Hình-11 có kết quả như sau: Omnipage đoán nhận tất các
ảnh đều là vùng văn bản (Hình-15)
Thí nghiệm 2: Với ảnh đầu vào 13, tương tự như VnDOCR OmniPage vẫn phân
vùng sai (Hình 16)


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Hình 18 Với ảnh I-15 hiệu quả đạt 100%

Hình 19: Với mẫu phức tạp hơn Finereader cho kết quả 95%

Hạn chế chính của Finereader là tốc độ làm việc chậm so với 2 phần mềm kể trên.
I.5. Kết luận
Từ những kết quả ở trên phạm vi đề tài ở đây sẽ chỉ tập trung vào việc phân
tích cấu trúc vậy lý của một trang tài liệu (trình bày chi tiết ở chương 2). Để cải tiến
hơn, đối tượng của đề tài sẽ là ảnh màu có độ phức tạp cao.

24

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG 2. MỘT SỐ KỸ THUẬT XỬ LÝ TRANG VĂN BẢN
Với phạm vi đặt ra ở chương một và phần mở đầu là đề tài sẽ tập trung vào
giải pháp phân tích cấu trúc vật lý của trang tài liệu, chương 2 sẽ giới thiệu một số
phương pháp phân tích hiện nay, từ đó đưa ra và đánh giá được ưu nhược điểm của
mỗi phương pháp đó. Sau đó sẽ tập trung phân tích kỹ một phương pháp mới chưa
được trình bày ở các đề tài trước đó là Fractal Signature với những ưu điểm vượt
trội của nó là hiệu quả cao với tài liệu phức tạp, không phân biệt góc nghiêng. Đồng
thời thiết kế hệ thống demo với giải pháp mới này.
2.1. Các phƣơng pháp phân tích định dạng trang tài liệu
2.1.1. Top-down
a) Tổng quan
Ý tưởng chính của thuật toán là phân tách liên tiếp từ một trang ban đầu
thành các vùng cơ sở nhỏ hơn. Các khối cơ sở ở đây là các khối như đoạn văn, tiêu