Luận văn Phương pháp phân tích trang văn bản dựa trên Tab-Stop

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 
Thái Nguyên, 2012 
2 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
MỞ ĐẦU 
1. Đặt vấn đề 
Hiện nay, hầu hết tài liệu của con người đề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. Tuy nhiên việc sử dụng giấy để lưu trữ tài liệu trong một số mục 
đích là không thể thay thế hoàn toàn được (như sách, báo, tạp chí, công văn,). 
Hơn nữa, lượng tài liệu được tạo ra từ nhiều năm trước vẫn còn rất nhiều mà không 
thể bỏ đi được vì tính quan trọng của chúng. 
Việc chuyển đổi tài liệu điện tử sang tài liệu giấy có thể thực hiện được dễ 
dàng bằng cách in hay fax, nhưng công việc ngược lại là chuyển từ tài liệu giấy 
sang tài liệu điện tử lại là một vấn đề không hề đơn giản. Chúng ta mong muốn có 
thể số hóa tất cả các tài liệu, sách, báo đó và lưu trữ chúng trên máy tính, việc tổ 
chức và sử dụng chúng sẽ thuận tiện hơn rất nhiều. Vậy nhưng giải pháp sẽ là gì? 
Công nghệ đang phát triển một cách chóng mặt, các máy scan với tốc độ 
hàng nghìn trang một giờ, các máy tính với công nghệ xử lí nhanh chóng và chính 
xác một cách siêu việt. Vậy tại sao chúng ta không quét các trang tài liệu vào và xử 
lý, chuyển chúng thành các văn bản một cách tự động? Nhưng vấn đề là khi quét 
chúng ta chỉ thu được các trang tài liệu đó dưới dạng ảnh nên không thể thao tác, 
sửa chữa, tìm kiếm như trên các bản Office được, khi đó máy tính không phân biệt 
được đâu là điểm ảnh của chữ và đâu là điểm ảnh của đối tượng đồ họa. 
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. Nội dung nghiên cứu 
2.1.Mục tiêu nghiên cứu chính của đề tài 
 Tìm hiểu cấu trúc trang tài liệu (cấu trúc vật lý, logic) 
 Tìm hiểu một số kỹ thuật phân tích trang tài liệu (phân vùng, phân đoạn, top-
down hay bottom-up, ) 
 Trình bày kỹ thuật phân tích trang văn bản Tab-Stop 
 Cài đặt thử nghiệm một giải pháp phân tích trang văn bản trên kỹ thuật Tab-
Stop. 
4 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
 Từ kết quả nghiên cứu có một sự chuẩn bị kiến thức đẩy đủ cho bước nghiên 
cứu tiếp theo là nhận dạng ký tự quang. 
2.2.Ý nghĩa khoa học của đề tài 
 Giải quyết được vấn đề về học thuật: đề tài sẽ mang ý nghĩa cung cấp về mặt 
lý thuyết để làm rõ về các phương pháp phân tích trang tài liệu. 
 Đáp ứng được yêu cầu của thực tiễn: từ các lý thuyết đã được nghiên cứu, từ 
đó liên hệ và gắn vào thực tiễn để có thể áp dụng vào các lĩnh vực như: Số hóa 
tài liệu, lưu trữ thư viện, điện tử hóa văn phòng, nhận dạng và xử lý ảnh,  
2.3.Nhiệm vụ nghiên cứu 
Mục đích của luận văn đề cập được đến hai phần: 
 Phần lý thuyết: Nắm rõ và trình bày những cơ sở lý thuyết liên quan đến cấu 
trúc trang tài liệu, một số kỹ thuật phân tích trang tài liệu, từ đó có để có thể 
xác định tính quan trọng của bước này trong nhận dạng ký tự, đồng thời hiểu 
các công việc kế tiếp cần làm trong bước nhận dạng ký tự. 
 Phần phát triển ứng dụng: Áp dụng các thuật toán đã trình bày ở phần lý thuyết 
từ đó lựa chọn một giải pháp tối ưu và cài đặt thử nghiệm chương trình phân 
tích trang tài liệu. 
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ử 
nghiệm. 
Chƣơng 3: Cài đặt chương trình Demo và đánh giá kết quả chương trình 
6 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
CHƢƠNG 1. NỘI DUNG TRANG VĂN BẢN VÀ CÁC PHƢƠNG PHÁP TIỀN XỬ 
LÝ 
Chương này đưa ra các khái niệm về đối tượng làm việc của đề tài là ảnh tài 
liệu, khái niệm về cấu trúc vật lý và cấu trúc logic. Giới thiệu các khâu trong một hệ 
thống nhận dạng chữ viết hoàn chỉnh. Đồng thời đưa ra một số phần mềm nhận 
dạng của Việt Nam và Thế giới cùng với các mẫu kết quả phân tích của nó nhằm 
mục đích so sánh và xác định phạm vi cho đề tài. 
1.1. Ảnh tài liệu và nhận dạng ảnh tài liệu 
1.1.1. Tổng quan về ảnh tài liệu 
Trang ảnh tài liệu được đề cập ở đây là các file ảnh số hoá thu được bằng 
cách quét các trang tài liệu dùng máy scanner, hoặc chụp từ các máy ảnh số, hay 
nhận từ một máy fax (Hình 1), file ảnh này được lưu giữ trong máy tính. Ảnh tài 
liệu có nhiều loại: ảnh đen trắng, ảnh đa cấp xám, ảnh đa cấp xám với các phần mở 
rộng như TIF, BMP, PCX, (Hình 2) và ảnh tài liệu được đưa ra trong luận văn 
này là ảnh đa cấp xám. 
 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 
-  
8 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
Sơ đồ một hệ thống OCR cơ bản ở Hình 3. 
Trong đó: 
- Scanner: Thiết bị quét ảnh 
- OCR hardware/software: 
o Document analysis: Phân tích tài liệu 
o Character recognition: Nhận dạng ký tự 
o Contexttual processor: Xử lý văn cảnh 
- Output interface: Đầu ra 
 Như vậy vai trò chính của khâu phân tích ảnh tài liệu là việc phân đoạn trang, 
tách vùng văn bản ra khỏi nền và đồ họa tạo mẫu chuẩn cho khâu nhận dạng. Rõ 
ràng là kết quả của khâu phân tích này ảnh hưởng rất lớn đến hiệu qủa của khâu 
nhận dạng nếu sử dụng mẫu hay các chuỗi văn bản đầu ra của nó. 
Hình 3: Sơ đồ OCR cơ bản 
1.2. Cấu trúc của ảnh tài liệu 
Một khái niệm mấu chốt trong xử lý tài liệu đó là cấu trúc của tài liệu. Cấu 
trúc tài liệu thu được từ việc liên tiếp chia nhỏ nội dung của tài liệu thành các phần 
nhỏ đơn vị (tức không thể phân chia được nữa) và chúng được gọi là các đối tượng cơ 
sở (basic objects). Còn tất cả các đối tượng khác được gọi là các đối tượng hỗn hợp. 
Có hai loại cấu trúc của tài liệu được quan tâm ở đây đó là cấu trúc vật lý 
9 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
(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 ... ....................................................................................... 2 
2. Nội dung nghiên cứu ........................................................................................... 3 
2.1.Mục tiêu nghiên cứu chính của đề tài ............................................................ 3 
2.2.Ý nghĩa khoa học của đề tài ........................................................................... 4 
2.3.Nhiệm vụ nghiên cứu ..................................................................................... 4 
2.4. Phương pháp nghiên cứu .............................................................................. 4 
2.5. Phạm vi nghiên cứu ...................................................................................... 4 
3. Bố cục của luận văn ............................................................................................. 5 
CHƢƠNG 1. NỘI DUNG TRANG VĂN BẢN VÀ CÁC PHƢƠNG PHÁP TIỀN XỬ LÝ
 ............................................................................................................................................................ 6 
1.1. Ảnh tài liệu và nhận dạng ảnh tài liệu .............................................................. 6 
1.1.1. Tổng quan về ảnh tài liệu ........................................................................... 6 
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............................. 7 
1.2. Cấu trúc của ảnh tài liệu ................................................................................... 8 
1.2.1. Cấu trúc vật lý ............................................................................................ 9 
1.2.2. Cấu trúc logic ........................................................................................... 10 
1.3. Quá trình phân tích tài liệu ............................................................................. 11 
1.3.1. Tiền xử lý (preprocessing): ...................................................................... 12 
1.3.2. Phân tích cấu trúc vật lý ........................................................................... 13 
1.3.3. Phân tích cấu trúc logic ............................................................................ 15 
1.4. Một số hệ thống phân tích tài liệu hiện nay ................................................... 15 
1.4.1. VnDOCR ................................................................................................. 15 
1.4.2. OminiPage ............................................................................................... 19 
2.4.3. Finereader ................................................................................................ 21 
iii 
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 ....................................... 24 
2.1. Các phương pháp phân tích định dạng trang tài liệu ...................................... 24 
2.1.1. Top-down ................................................................................................. 24 
2.1.2. Bottom-up ................................................................................................ 29 
2.1.3. Phương pháp Tách và Nối thích nghi (Adaptive Split – and – Merge) ... 31 
2.1.4 Phương pháp phân tích trang văn bản dựa trên Tab-Stop ........................ 33 
2.2. Lựa chọn giải pháp ......................................................................................... 47 
CHƢƠNG 3. CÀI ĐẶT THỬ NGHIỆM, ĐÁNH GIÁ KẾT QUẢ ..................................... 48 
3.1. Yêu cầu hệ thống ............................................................................................ 48 
3.2 Một số anh debug của chương trình ................................................................ 49 
3.3 Đánh giá thực nghiệm...................................................................................... 58 
KẾT LUẬN .................................................................................................................................... 62 
TÀI LIỆU THAM KHẢO ........................................................................................................... 63 
iv 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
DANH MỤC CÁC HÌNH ẢNH 
Hình 1: Sơ đồ tổng quan quá trình tạo ảnh tài liệu ..................................................................... 6 
Hình 2: Ví dụ ảnh tài liệu ................................................................................................................ 7 
Hình 3: Sơ đồ OCR cơ bản ............................................................................................................. 8 
Hình 4: b-Cấu trúc vật lý: c,d-Cấu trúc logic của một tài liệu[4] ............................................ 10 
Hình 5: Ví dụ loại tài liệu có bố cục phức tap ............................................................................ 11 
Hình 6: Sơ đồ nguyên lý hệ thống xử lý tài liệu[6] .................................................................... 12 
Hình 7: a - Ảnh gốc b - Ảnh sau khi tách nền ............................................................................. 13 
Hình 8: Ví dụ một ảnh tài liệu bị nghiêng một góc 5 độ ............................................................ 14 
Hình 9: Ví dụ một cây mô tả cấu trúc logic của một trang tài liệu[5] ..................................... 15 
Hình 10: VnDOCR và một ví dụ nhận dạng ............................................................................... 16 
Hình 11: Ảnh mẫu có cấu trúc vật lý phức tạp ........................................................................... 17 
Hình 12: Kết quả ra hai vùng ảnh với ảnh mẫu 11 .................................................................... 17 
Hình 13: Mẫu ảnh có cấu trúc vật lý phức tạp, nhưng các khối bao bởi hình chữ nhật ........ 18 
Hình 14: Kết quả phân tích với ảnh 13 ....................................................................................... 19 
Hình 15: Đầu ra phân vùng chỉ có 1 vùng văn bản ................................................................... 20 
Hình 16: Đầu ra có vùng chứa cả ảnh và text ............................................................................ 21 
Hình 17: Với ảnh 13 đạt hiệu quả 90% ....................................................................................... 22 
Hình 18 Với ảnh I-15 hiệu quả đạt 100% ................................................................................... 23 
Hình 19: Với mẫu phức tạp hơn Finereader cho kết quả 95% ................................................ 23 
Hình 20: Kết quả chiếu nghiêng theo phương ngang và phương thẳng đứng của một trang 
tài liệu4 ............................................................................................................................................ 25 
Hình 21: Phân tách cột dựa vào phép chiếu nghiêng theo phương ngang5 ........................... 26 
Hình 22: Phép chiếu nghiêng theo phương ngang để phân đoạn ký tự hoặc từ ..................... 26 
Hình 23: Lược đồ chiếu ngang của một dòng chữ nghiêng - rất khó phân đoạn ký tự ......... 27 
Hình 24: Lược đồ chiếu đứng của trang tài liệu bị nghiêng ..................................................... 28 
Hình 25: Lược đồ chiếu đứng của một bài báo .......................................................................... 28 
Hình 26: Phương pháp Dostrum cho phân tích định dạng trang từ dưới lên. (a) Một phần 
v 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  
của nội dung văn bản gốc. (b) Các thành phần lân cận gần nhất được xác định. (c) Các hình 
chữ nhật tối thiểu tạo nên nhóm láng giềng gần nhất từ đó xác định được dòng văn bản. ... 30 
Hình 27: Mô tả thuật toán Tách và Nối thích nghi .................................................................... 32 
Hình 28: ảnh đầu vào .................................................................................................................... 34 
Hình 29. (a) Đường dọc, (b) Các thành phần hình. ................................................................... 36 
Hình 30: filtered CCs .................................................................................................................... 37 
Hình 31. (a) Các thành phần tab-stop phù hợp (b) Dòng tab hợp lý và những kết nối dấu vết
 .......................................................................................................................................................... 38 
Hình 32: cho thấy các phân đoạn dòng tab cuối. ....................................................................... 39 
Hình 33: Cột chính(cps) ................................................................................................................ 41 
Hình 34: làm sạch các tab-stop .................................................................................................... 43 
Hình 35: Typed partition chains .................................................................................................. 44 
Hình 36: Các khối cuối cùng ........................................................................................................ 46 
Hình 37:. Kết quả trên một số bộ tiêu chí đánh giá đối tượng ICDAR2007. .......................... 49 
Hình 38: ảnh 002.LeaderNeighbours .......................................................................................... 49 
Hình 39: ảnh 003.FindTabBoxes: Các thành phần tab-stop ứng cử (candidate tab-stop CCs)
 .......................................................................................................................................................... 50 
Hình 40: ảnh 004.FindAllTabVectors_Finding ......................................................................... 52 
Hình 41: ảnh 017.ImproveColumnCandidates2_column ......................................................... 52 
Hình 42: ảnh 020.MovePartitionsToGrid................................................................................... 53 
Hình 43: ảnh 024.InitialPartitions ............................................................................................... 54 
Hình 44: ảnh 025.ColumnPartitionsAndNeighbors .................................................................. 55 
Hình 45: ảnh 036.FindPartitionPartners ................................................................................... 56 
Hình 46: ảnh 038.RefinePartitionPartners ................................................................................. 57 
Hình 47: ảnh 040.Blocks ............................................................................................................... 58 
Hình 48: ảnh đầu vào .................................................................................................................... 59 
Hình 49: ảnh kết quả ..................................................................................................................... 60