Luận văn Thạc sĩ Khoa học máy tính: Tìm hiểu phương pháp đánh giá độ chính xác của các hệ thống nhận dạng chữ Việt

Trang - i- ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG -----------------------------------

NGÔ MINH HIẾU TÌM HIỂU PHƯƠNG PHÁP ĐÁNH GIÁ ĐỘ CHÍNH XÁC

CỦA CÁC HỆ THỐNG NHẬN DẠNG CHỮ VIỆT

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên 2015

Trang - ii- ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG =================== NGÔ MINH HIẾU TÌM HIỂU PHƯƠNG PHÁP ĐÁNH GIÁ ĐỘ CHÍNH XÁC

CỦA CÁC HỆ THỐNG NHẬN DẠNG CHỮ VIỆT

Chuyên ngành: Khoa học máy tính Mã số:60 48 01 01

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

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 THỊ THANH TÂN Thái Nguyên 2015

Trang - 1-

LỜI CAM ĐOAN

Tôi xin cam đoan rằng bản luận văn này là tự thân nghiên cứu và hoàn

thành dưới sự hướng dẫn khoa học của TS. Nguyễn Thị Thanh Tân. Nếu có gì

vi phạm tôi xin hoàn toàn chịu trách nhiệm.

Thái Nguyên, ngày tháng năm 2015

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Ngô Minh Hiếu

Trang - 2-

LỜI CẢM ƠN

Lời đầu tiên tôi xin gửi lời cảm ơn chân thành và lòng biết ơn sâu sắc tới

TS Nguyễn Thị Thanh Tân, người đã chỉ bảo và hướng dẫn tận tình cho tôi và

đóng góp ý kiến quý báu trong suốt quá trình học tập, nghiên cứu và thực hiện

luận văn này.

Tôi xin trân trọng cảm ơn Ban giám hiệu Trường Đại học Công nghệ

Thông tin và Truyền thông, Đại học Thái Nguyên, khoa CNTT đã giúp đỡ và

tạo các điều kiện cho chúng tôi được học tập và làm khóa luận một cách thuận

lợi.

Và cuối cùng tôi xin gửi lời cảm ơn đến gia đình, người thân và bạn bè,

những người luôn bên tôi và là chỗ dựa giúp cho tôi vượt qua những khó khăn

nhất. Họ luôn động viên tôi khuyến khích và giúp đỡ tôi trong cuộc sống và

công việc cho tôi quyết tâm hoàn thành luận văn này.

Tuy nhiên do thời gian có hạn, mặc dù đã nỗ lực cố gắng hết mình nhưng

chắc rằng luận văn khó tránh khỏi những thiếu sót. Rất mong được sự chỉ bảo,

góp ý tận tình của quý Thầy Cô và các bạn.

Tôi xin chân thành cảm ơn! Thái Nguyên, ngày tháng năm 2015

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Ngô Minh Hiếu

Trang - 3-

MỤC LỤC

LỜI CAM ĐOAN ......................................................................................... 1 LỜI CẢM ƠN ............................................................................................... 2 MỤC LỤC .................................................................................................... 3 HÌNH VẼ ...................................................................................................... 5 BẢNG ............................................................................................................ 6 DANH MỤC CÁC TỪ VIÊT TẮT .............................................................. 7 MỞ ĐẦU ....................................................................................................... 8 CHƯƠNG 1 - TỔNG QUAN VỀ NHẬN DẠNG CHỮ ............................ 12 1.1.Qui trình chung của một hệ nhận dạng chữ .................................... 12 1.1.1.Phân lớp mẫu ............................................................................... 12 1.1.2.Nhận dạng văn bản ....................................................................... 13 1.2.Tìm hiểu một số phần mềm nhận dạng chữ .................................... 16 1.2.1.VnDOCR .................................................................................. 16 1.2.2.FineReader ................................................................................... 18 1.2.3.OmniPage ..................................................................................... 20 1.2.4. VietOCR ..................................................................................... 20 1.3. Những vấn đề ảnh hưởng tới chất lượng của một phần mềm nhận dạng ......................................................................................................... 22 1.3.1.Chữ bị dính, nhòe ......................................................................... 23 1.3.2.Văn bản bị đứt hoặc mất nét ......................................................... 24 1.3.3.Văn bản bị nhiễu .......................................................................... 25 1.3.4.Văn bản được in với các kiểu font chữ đặc biệt ............................ 26 1.3.5.Cỡ chữ quá lớn hoặc quá nhỏ ....................................................... 26 1.4.Kết luận ............................................................................................. 27 CHƯƠNG 2 - PHƯƠNG PHÁP ĐÁNH GIÁ HIỆU QUẢ CỦA CÁC

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

THUẬT TOÁN NHẬN DẠNG CHỮ VIỆT .............................................. 28 2.1. Một số khái niệm ............................................................................... 28 2.2. Bài toán hiệu chỉnh chuỗi ký tự (string editing) ................................. 29 2.3. Thuật toán Ukkonen........................................................................... 34

Trang - 4-

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

2.4. Đánh giá độ chính xác mức ký tự ....................................................... 40 2.5. Đánh giá độ chính xác mức ký tự theo lớp mẫu ................................. 44 2.6. Hiệu quả của các ký tự đánh dấu ........................................................ 44 2.7. Độ chính xác mức từ .......................................................................... 46 CHƯƠNG 3 :THỰC NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ ................... 51 3.1.Phân tích, cài đặt chương trình ........................................................ 51 3.1.1.Quy trình thực hiện ...................................................................... 51 3.1.2.Các cấu trúc dữ liệu ...................................................................... 52 3.1.3.Danh sách các từ dừng trong tiếng Việt ........................................ 54 3.1.4 Danh sách các ký tự đặc biệt ........................................................ 55 3.1.5.Module đánh giá độ chính xác mức ký tự ..................................... 56 3.1.6.Module đánh giá độ chính xác mức từ .......................................... 58 3.2.Đánh giá thực nghiệm ....................................................................... 65 3.2.1Dữ liệu thực nghiệm ...................................................................... 65 3.2.2 Kết quả thực nghiệm .................................................................... 68 3.3.Kết luận chương 3 ............................................................................. 70 KẾT LUẬN ................................................................................................. 71 DANH MỤC TÀI LIỆU THAM KHẢO ................................................... 72

Trang - 5-

HÌNH VẼ

Hình 1.1: Qui trình chung của một hệ thống nhận dạng chữ ......................... 15

Hình 1.2. Màn hình làm việc của VnDOCR ................................................. 17

Hình 1.3. Màn hình kết quả phân tích và nhận dạng ảnh hình 1.7 ................. 18

Hình 1.4 Màn hình làm việc của OmniPage ................................................. 20

Hình 1.5 Màn hình làm việc của VietOCR ................................................... 21

Hình 1.6 Trường hợp văn bản in đậm ........................................................... 23

Hình 1.7: Một số hình ảnh bị biến dạng của các ký tự .................................. 23

Hình 1.8 Hình ảnh các ký tự tiếng Việt bị nhập nhằng phần dấu .................. 24

Hình 1.9 Trường hợp văn bản bị đứt và mất nét ........................................... 24

Hình 1.10 Hình ảnh của ký tự bị biến dạng do lỗi đứt nét ............................. 24

Hình 1.11 Một số dạng nhiễu thường gặp trên văn bản................................. 25

Hình 1.12 Văn bản bị các nhiễu đánh dấu .................................................... 25

Hình 1.13 Văn bản bị nhiễu do bị chồng chữ ký/con dấu ............................. 26

Hình 1.14 Văn bản được in với kiểu font chữ đặc biệt .................................. 26

Hình 2.1: Đồ thị G(A,B), với A = zxy và B = xyxz ...................................... 32

Hình 2.2: Các đường đi trên đồ thị G(A, B) .................................................. 33

Hình 2.3: Sự tương ứng giữa chuỗi văn bản nhận dạng và văn bản mẫu ....... 42

Hình 2.4: Độ chính xác mức từ..................................................................... 48

Hình 3.1 Quy trình thực hiện của chương trình ............................................ 52

Hình 3.2: Kết quả đánh giá độ chính xác mức ký tự trên một văn bản tiếng Anh

..................................................................................................................... 61

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Hình 3.3: Đánh giá độ chính xác mức từ trên 1 file văn bản tiếng Anh ......... 65

Trang - 6-

BẢNG Bảng 2.1: Giải thuật cho bài toán chỉnh sửa chuỗi ........................................ 33

Bảng 2.2: Độ chính xác mức ký tự ............................................................... 43

Bảng 3.1 Bảng danh sách các từ dùng trong tiếng Việt ................................. 55

Bảng 3.2 Thông tin các thao tác hiệu chỉnh .................................................. 57

Bảng 3.3 Thông tin về đánh giá độ chính xác mức ký tự .............................. 57

Bảng 3.4: Các tập dữ liệu tiếng Anh ............................................................. 66

Bảng 3.5: Các tập dữ liệu Tiếng Việt............................................................ 67

Bảng 3.6: Độ chính xác mức ký tự trên tập dữ liệu tiếng Anh ...................... 68

Bảng 3.7: Độ chính xác mức ký tự trên các tập dữ liệu tiếng Việt ................ 69

Bảng 3.8: Độ chính xác mức từ trêntập dữ liệu tiếng Anh ............................ 69

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Bảng 3.9: Độ chính xác mức từ tập dữ liệu tiếng Việt .................................. 69

Trang - 7-

DANH MỤC CÁC TỪ VIÊT TẮT

STT Từ viết tắt Ý nghĩa Nội dung

1 NLP

2 LCS Xử lý ngôn ngữ tự nhiên Dãy chung dài nhất

3 OCR

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Natural Language Processing Longest common subsequence Optical Character Recognition Nhận dạng ký tự quang học

Trang - 8-

MỞ ĐẦU

1. Tính cấp thiết của luận văn

Nhận dạngmẫu là một ngành khoa học mà vai trò của nó là phân lớp các

đối tượng thành một số loại hoặc một số lớp riêng biệt.Tuỳ thuộc vào lĩnh vực

ứng dụng, các đối tượng có thể ở dạng ảnh, dạng tín hiệu sóng hoặc một kiểu

dữ liệu bất kỳ nào đó mà cần phải phân lớp. Những đối tượng này được gọi

bằng một thuật ngữ chung đó là “mẫu” (pattern). Nhận dạng mẫu đã được biết

đến từ rất lâu, nhưng trước những năm 1960 nó hầu như chỉ là kết quả nghiên

cứu về mặt lý thuyết trong lĩnh vực thống kê. Tuy nhiên, với sự phát triển không

ngừng của khoa học kỹ thuật về phần cứng cũng như phần mềm, các yêu cầu

về mặt ứng dụng thực tế của lĩnh vực nhận dạng mẫu ngày càng tăng lên và

hiện nay nhận dạng mẫu đã được sử dụng trong rất nhiều lĩnh vực như y học,

tự động hoá một số qui trình sản xuất công nghiệp, dự báo thời tiết, dự báo cháy

rừng,v.v. Ngoài ra nhận dạng mẫu còn là thành phần quan trọng trong hầu hết

các hệ thống máy tính thông minh được xây dựng để thực hiện việc ra quyết

định.

Cùng với sự phát triển của nhận dạng mẫu, nhận dạng chữ đã và đang ngày

càng trở thành một ứng dụng không thể thiếu được trong đời sống xã hội của

con người.Nhận dạng chữ là quá trình chuyển đổi từ dạng hình ảnh của một

hay nhiều trang ảnh chứa các thông tin văn bảnthành tệp văn bản thực sự có thể

soạn thảo được trên máy tính. Ngoài ứng dụng số hóa các trang văn bản, tài

liệu, hiện tại nhận dạng chữ còn được ứng dụng rộng rãi trong các hoạt động

giao dịch hàng ngày và qui trình tự động hóa các công việc văn phòng, chẳng

hạn như nhập liệu tự động phiếu chấm thi trắc nghiệm, phiếu điều tra, nhận

dạng các dòng địa chỉ trên phong bì thư, nhận dạng nhãn sản phẩm, nhận dạng

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

thông tin cá nhân trên chứng minh nhân, hộ chiếu, card visit,v.v.

Trang - 9-

Trên thế giới, bài toán nhận dạng chữ đã được đầu tư nghiên cứu từ những

năm 50 của thế kỷ trước. Những sản phẩm nhận dạng chữ hiện đã được thương

mại hóa rộng rãi trên thị trường, điển hình như ABBYY FineReader 11 (có khả

năng nhận dạng được 189 ngôn ngữ khác nhau, kể cả tiếng Việt).Bên cạnh đó,

còn có các dòng sản phẩm được tích hợp với phần cứng của máy tính như

OmniPage, Omniform, Scanshell, v.v.. Với lợi thế có một cộng đồng nghiên

cứu rộng lớn, từ những năm 1996, Viện nghiên cứu khoa học thông tin (The

Information Science Research Institute – ISRI), thuộc trường Đại học Nevada,

Las Vegas đã kết hợp với các nhóm nghiên cứu tại Mỹ và Anh để xây dựng

một một bộ công cụ đánh giá hiệu quả của các engine nhận dạng (OCRtk) và

một cơ sở dữ liệu văn bản mẫu lớn (gồm trên 2229 trang văn bản), đa dạng về

chủng loại (sách , báo, tạp chí, fax, thư tín, báo cáo tài chính của các doanh

nghiệp, tài liệu khoa học kỹ thuật, văn bản luật, v.v.) và chất lượng. Mỗi trang

văn bản được quét với lần lượt với 3 ngưỡng độ phân giải 200, 300 và 400 dpi

với các mức độ đậm, nhạt khác nhau. Ngoài ra, để đánh giá hiệu quả của các

thuật toán nhận dạng chữ viết tay còn có các bộ dữ liệu chuẩn như đối với nhận

dạng chữ viết tay còn có các bộ dữ liệu chuẩn như MNIST, USPS, v.v.

Cùng với xu thế phát triển của thế giới, bài toán nhận dạng chữ Việt cũng

đã thu được những kết quả ứng dụng đáng kể, với các sản phẩm thương mại

hóa điển hình như sản phẩm VnDOCR (đã được ứng dụng tại hầu hết các cơ

quan, đơn vị trên toàn quốc), sản phẩm FineReader 11 (đã được ứng dụng để

số hóa tài liệu trong các dự án chính phủ điện tử). Tuy nhiên, do mới chỉ thực

sự được đầu tư nghiên cứu trong khoảng hơn chục năm trở lại đây nên các sản

phẩm nhận dạng chữ Việt chưa thể đáp ứng được hết các yêu cầu của người sử

dụng, chẳng hạn như độ chính xác nhận dạng không cao đối với chữ viết tay và

các văn bản đầu vào kém chất lượng, chỉ làm việc với ảnh đa cấp xám hoặc ảnh

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

nhị phân có nền đồng nhất,...[1]. Vì những lý do nêu trên, việc đầu tư nghiên

Trang - 10-

cứu để tiếp tục nâng cao độ chính xác của các thuật toán nhận dạng chữ Việt là

một vấn đề thực sự cần thiết, có cả ý nghĩa khoa học lẫn thực tiễn. Vấn đề lớn

nhất mà hiện nay các nhóm nghiên cứu về nhận dạng chữ Việt đang phải đối

mặt là chưa có được một bộ công cụ cũng như cơ sở dữ liệu mẫu chuẩn, phục

vụ cho việc thử nghiệm và đánh giá các thuật toán nhận dạng.

2. Mục tiêu của luận văn

Nội dung nghiên cứu của luận văn hướng tới 2 mục tiêu chính:

 Xây dựng bộ công cụ đánh giá độ chính xác của các phần mềm nhận

dạng chữ Việt.

 Xây dựng cơ sở dữ liệu mẫu chuẩn, phục vụ cho việc nghiên cứu,

đánh giá và thử nghiệm các thuật toán nhằm nâng cao chất lượng nhận

dạng.

Phần thực nghiệm, luận văn sẽ tiến hành đánh giá độ chính xác của một

sốphần mềm nhận dạng chữ hiện đang được thương mại hóa hoặc công

bố rộng rãi trên thị trường như VnDOCR,FineReader, Omnipage,

VietOCR...

3. Bố cục của luận văn

Các nội dung trình bày trong luận văn được chia thành 3 chương:

Chương I: Tổng quan về nhận dạng chữ

Chương này trình bày tổng quan về bài toán nhận dạng chữ, những yếu tố

ảnh hưởng tới độ chính xác của các phần mềm nhận dạng chữ.

Chương II: Phương pháp đánh giá hiệu quả của các phần mềm nhận dạng

chữ Việt

Chương này trình bày cơ sở lý thuyết của các độ đo và phương phápđánh

giá chất lượng (độ chính xác) của các hệ thống nhận dạng được đề xuất trên cơ

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

sở bài toán đối sánh hai chuỗi ký tự dựa trên ý tưởng quy hoạch động với họ

Trang - 11-

các hàmmục tiêu được xây dựng từ các chi phí của các bước hiệu chỉnh để biến

văn bản được nhận dạng thành văn bản mẫu.

Chương III: Thực nghiệm và đánh giá kết quả

Trong chương III, luận văn sẽ mô tả chi tiết quá trình cài đặt chương trình

thử nghiệm tự động đánh giá chất lượng (độ chính xác) của các phần mềm

(thuật toán) nhận dạng chữ. Chương trình được kiểm thử với các phần mềm

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

VnDOCR, FineReader, Omnipage, VietOCR, v.v.

Trang - 12-

CHƯƠNG1 - TỔNG QUAN VỀ NHẬN DẠNG CHỮ

Nhận dạng chữ là lĩnh vực được nhiều nhà nghiên cứu quan tâm và cho

đến nay lĩnh vực này cũng đã đạt được nhiều thành tựu cả về mặt lý thuyết lẫn

ứng dụng thực tế.Chương này sẽ trình bày các khía cạnh tổng quan về bài toán

nhận dạng chữ. Trong đó, phần đầu tiên của chương sẽ đề cập đến các thao tác

xử lý cơ bản trong qui trình chung của bài toán nhận dạng chữ. Phần tiếp theo

là những tìm hiểu, khảo sát về các phần mềm nhận dạng chữ đang được công

bố và thương mại hóa trên thị trường như phần mềm FineReader, VnDOCR,

Omnipage, VietOCR. Phần cuối cùng trình bày và hệ thống lại những vấn đề

thường gặp trong bài toán nhận dạng cũng như các yếu tố ảnh hưởng đến chất

lượng của một hệ thống nhận dạng.

1.1. Qui trình chung của một hệ nhận dạng chữ

Qui trình chung của một hệ thống nhận dạng chữ thường gồm hai giai đoạn

là: Phân lớp mẫu và nhận dạng văn bản.

1.1.1. Phân lớp mẫu

Phân lớp (sắp lớp) mẫu là giai đoạn quyết định trong quá trình nhận dạng.

Hai kiểu phân lớp điển hình thường được sử dụng là: phân lớp có giám sát(học

có giám sát) và phân lớp không giám sát (học không giám sát). Các vấn đề

thường được đặt ra trong bước phân lớp là:

 Độ chính xác: Độ tin tưởng của một luật phân lớp được thể hiện bởi tỷ

lệ phân lớp đúng. Nhìn chung, độ chính xác được đo bởi tập dữ liệu học

và độ chính xác được đo bởi tập dữ liệu thử nghiệm là khác nhau. Đây

không phải là một điều bất thường, đặc biệt trong các ứng dụng học máy,

đối với tập dữ liệu học thì có thể đúng hoàn toàn, nhưng trên tập dữ liệu

thử nghiệm có khi kết quả lại rất tồi tệ. Khi nói đến độ chính xác của một

thuật toán phân lớp thì thường là nói đến độ chính xác trên tập dữ liệu

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

thử nghiệm. Kinh nghiệm thực tế cho thấy, độ chính xác của một thuật

Trang - 13-

toán phân lớp phụ thuộc khá nhiều vào tập dữ liệu học (cả về mặt số

lượng lẫn chất lượng) nói một cách khác là việc trích chọn đặc trưng của

các mẫu có ảnh hưởng lớn tới độ chính xác của quá trình phân lớp.

 Tốc độ phân lớp:Đây là yếu tố đặc biệt quan trọng đối với các hệ thống

có tính thời gian thực, chẳng hạn như nhận dạng chữ viết tay trực tuyến

(online), ...

 Tính dễ hiểu:Thuật toán phân lớp đơn giản, dễ cài đặt và hiệu quả.

 Thời gian học: Nhất là trong một môi trường thường xuyên thay đổi,

cần phải học một luật phân lớp một cách nhanh chóng hoặc hiệu chỉnh

một luật đã có trong thời gian thực. Để học nhanh, nhiều khi ta chỉ cần

sử dụng một số lượng nhỏ các mẫu huấn luyện để thiết lập các luật phân

lớp.

1.1.2. Nhận dạng văn bản

Các bước cần thực hiện trong giai đoạn này được thể hiện cụ thể trênHình

1.1[1]bao gồm:

1. Thu nhận và lưu trữ ảnh: Đây là công đoạn đầu tiên trong một quá trình

nhận dạng ảnh. Trong một hệ thống nhận dạng, ảnh thường được thu nhận

qua scanner, sau đó được lưu trữ dưới các định dạng file (.pcx, .bmp,

.jpg, .tif, .gif, .png, ...). Nhìn chung việc lựa chọn định dạng file lưu

trữ sẽ tuỳ thuộc vào các văn bản đầu vào cần nhận dạng và các yêu cầu cụ

thể của từng hệ thống.

2. Tiền xử lý ảnh: Đây là công đoạn sử dụng các kỹ thuật xử lý ảnh để nâng

cao chất lượng ảnh đầu vào. Nhìn chung, chất lượng của ảnh đầu vào sẽ

ảnh hưởng nhiều đến chất lượng nhận dạng. Vì vậy, tiền xử lý ảnh là một

bước không thể thiếu được trong một hệ thống nhận dạng hay xử lý ảnh.

Các kỹ thuật thường được sử dụng trong quá trình tiền xử lý là: Phân

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

ngưỡng, căn chỉnh độ lệch trang văn bản, lọc nhiễu, nối nét đứt trên ảnh,...

Trang - 14-

3. Phân đoạn ảnh:Đây là một trong những công đoạn quan trọng nhất trọng

nhất của quá trình nhận dạng và có ảnh hưởng lớn đến kết quả nhận dạng.

Hai cách tiếp cận phổ biến được đề xuất trong quá trình phân đoạn ảnh là:

 Cách tiếp cận trên xuống (top-down): Toàn bộ ảnh văn bản cần phân

đoạn được coi là một khối lớn, sau đó khối này được phân thành các khối

nhỏ hơn, các khối nhỏ này lại tiếp tục được phân thành các khối nhỏ hơn

nữa cho đến khi thu được các ký tự hoặc không thể phân nhỏ hơn được

nữa. Nhìn chung, với cách tiếp cận này, phương pháp thường dùng để

phân đoạn ảnh là sử dụng các biểu đồ tần suất ngang và dọc. Tuy nhiên,

do biểu đồ tần suất bị ảnh hưởng nhiều bởi độ nghiêng trang văn bản nên

trước khi xử lý phân đoạn, ta thường phải căn chỉnh độ lệch của trang

văn bản.

 Cách tiếp cận dưới lên (bottom-up): Quá trình phân đoạn bắt đầu bằng

việc xác định những thành phần nhỏ nhất, sau đó gộp chúng lại thành

những thành phần lớn hơn, cho đến khi thu được tất cả các khối trong

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

trang văn bản.

Trang - 15-

Thu nhận ảnh

Tiền xử lý

Phân trang văn bản

Cơ sở tri thức

Nhận dạng

Cập nhật tri thức (thông qua huấn luyện mẫu mới)

Hậu xử lý

Lưu văn bản

Hình 1.1: Qui trình chung của một hệ thống nhận dạng chữ

4. Nhận dạng:Đây chính là thao tác gán nhãn cho đối tượng dựa trên những

tri thức đã học được, nói cách khác đâylà thao tác tìm kiếm một lớp mẫu

phù hợp nhất với đối tượng đầu vào.

5. Học mẫu mới:Do tập mẫu huấn luyện không thể bao quát được toàn bộ

các mẫu trong thực tế nên trong quá trình nhận dạng có thể sẽ gặp những

mẫu mới mới mà hệ thống không thể nhận dạng chính xác được. Khi đó việc

học thêm những mẫu này sẽ góp phần làm tăng chất lượng của hệ thống

nhận dạng.

6. Hậu xử lý: Đây là một trong những công đoạn cuối cùng của quá trình

nhận dạng. Trong nhận dạng chữ, có thể hiểu hậu xử lý là bước ghép nối các

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

ký tự đã nhận dạng được thành các từ, các câu, các đoạn văn nhằm tái hiện

Trang - 16-

lại văn bản đồng thời phát hiện ra các lỗi nhận dạng 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âu, đoạn vă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 kết quả nhận dạng. Đặc biệt đối với các ảnh văn bản đầu vào

không tốt (chẳng hạn: Bản in bị mờ, bị đứt nét do photo nhiều lần,...) hoặc

các văn bản in chứa nhiều thông tin hỗn hợp (chẳng hạn: Trong văn bản có

cả số lẫn chữ và các ký hiệu), điều này rất dễ gây nhầm lẫn trong nhận dạng.

Thậm chí có những trường hợp nhập nhằng chỉ có thể giải quyết được bằng

ngữ cảnh bằng cách phân tích ngữ cảnh của câu, chẳng hạn như trường hợp

nhập nhằng giữa từ “lO” với số “10”.

7. Lưu văn bản: Sau khi văn bản cần nhận dạng đã được tái tạo về dạng

nguyên bản sẽ được lưu lại ở các định dạng file được hệ thống hỗ trợ, chẳng

hạn như file dạng (.doc, .rtf, .xls, ...).

1.2.Tìm hiểu một số phần mềm nhận dạng chữ

1.2.1.VnDOCR

Phần mềm nhận dạng tiếng Việt VnDOCR là một sản phẩm của Viện

Công nghệ Thông tin. VnDOCR có khả năng nhận dạng ký tự tiếng Việt từ

máy scan hoặc file ảnh và chuyển đổi về dạng file văn bản như: *.doc.*.txt,

*.xls, *.rtf,...[18]và có thể đọc và sửa trên các phần mềm soạn thảo văn bản

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

thông dụng như Office, Wordpad, Notepad...

Trang - 17-

Hình 1.2: Màn hình làm việc của VnDOCR

Môi trường

+ PC với hệ điều hành Windows 9x, Windows ME, Windows 2000, Windows

XP hoặc Windows NT

Tiện ích: Bộ gõ chữ Việt và bộ phông 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. 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ó thể là các dạng tệp tin của Microsoft Word (.doc), tệp ký tự ASCII (.txt),

Rich Text Format (.rtf), *.xls (đối với bảng biểu).

Theo công bố, độ chính xác của phần mềm có thể đạt tới 99 % trong trường

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

hợp các file ảnh cần nhận dạng có chất lượng tốt.

Trang - 18-

Các tính năng chính:

- Tiền xử lý: Căn chỉnh độ nghiêng, tăng cường chất ảnh (xóa nhiễu, làm

dày nét chữ nhằm nối nét đứt, làm mỏng nét chữ,… ).

- Phân tích cấu trúc trang văn bản nhằm xác định các vùng thông tin khác

nhau (chẳng hạn vùng ảnh, vùng văn bản, vùng bảng, các dạng tiêu

đề…).

- Nhận dạng văn bản: Nhận dạng các khối văn bản đã được xác định ở

bước phân trang.

- Hậu xử lý: Định dạng lại trang văn bản ban đầu, chỉnh lỗi chính tả,…

Một số hạn chế của phần mềm (Tính đến phiên bản 4.0)

- VnDOCR chỉ làm việc với ảnh đen trắng.

- Với ảnh có cấu trúc vật lí phức tạp thì hiệu quả phân tích trang và độ

chính xác nhận dạng còn chưa cao.

1.2.2.FineReader

FineReader là một sản phẩm của hãng ABBYY, có khả năng nhận dạng đa

ngôn ngữ (198 ngôn ngữ) bao gồm cả ngôn ngữ tiếng Việt.[19]

Hình 1.3:Màn hình làm việc của FineReader

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 19-

Môi trường làm việc:

PC với hệ điều hành: Windows XP, 2003, Vista, 2008, Windows 7,

Windows 8, Windows 8.1.

Các tính năng cơ bản của phần mềm:

 Tiền xử lý: Căn chỉnh độ nghiêng, tăng cường chất ảnh (xóa nhiễu, làm

dày nét chữ nhằm nối nét đứt, làm mỏng nét chữ,… )

 Phân tích cấu trúc trang văn bản nhằm xác định các vùng thông tin

khác nhau (chẳng hạn vùng ảnh, vùng văn bản, vùng bảng, các dạng

tiêu đề…).

 Nhận dạng:

 Nhận dạng các khối văn bản

 Nhận dạng công thức toán.

 Nhận dạng mã vạch.

 Văn bản: Nhận dạng các khối văn bản đã được xác định ở bước

phân trang.

 Hậu xử lý: Định dạng lại trang văn bản ban đầu, chỉnh lỗi chính tả,…

 Ngoài ra còn có các tính năng mở rộng như:

 Xuất ra XML và tích hợp với Microsoft Office Word

 Hỗ trợ các fiel ảnh đầu vào có định dạng file PDF.

 Kết quả nhận dạng có thể được xuất ra nhiều định dạng file như:

DOC, DOCX, XLS, XLSX, PPTX, RTF, PDF,PDF/A, HTML,

CSV, TXT, ODT, EPUB, FB2, DjVu...

 Chức năng tìm kiếm với Morphology Support

 Các tùy chọn lưu ảnh cao cấp

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

 Các ứng dụng thêm cho việc hoàn thành và in ấn các Form.

Trang - 20-

1.2.3.OmniPage

OmniPage là phần mềm nhận dạng văn bản của Nuance, có khả năng nhận

dạng trên 120 ngôn ngữ, độ chính xác có thể đạt tới 99% trên các file ảnh đầu

vào chất lượng tốt.[20]

Hình 1.4: Màn hình làm việc của OmniPage

Các tính năng cơ bản của phần mềm:

 Hỗ trợ nhiều định dạng file ảnh, bao gồm cả file pdf.

 Nhận dạng chính xác tới 99% trên hơn 120 ngôn ngữ khác nhau

 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.

Hạn chế của phần mềm:

OminiPage chưa hiệu quả với các ảnh có cấu trúc phức tạp.

1.2.4. VietOCR

Phần mềm VietOCR được xây dựng từ engine nhận dạng mã nguồn mở

Tesseract của Google. VietOCR có thể hoạt động trên nhiều hệ điều hành khác

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

nhau như: Windows, Linux,…

Trang - 21-

Hình 1.5: Màn hình làm việc của VietOCR

Các tính năng cơ bản của phần mềm:

 Tính năng nhận dạng:

- OCR nhận dạng tốt nhất ảnh ở độ phân giải từ 200 DPI trở lên

tới 400 trong trắng đen hoặc grayscale

- Chế độ Screenshot Mode cung cấp độ nhận dạng tốt hơn cho

những hình ảnh có độ phân giải thấp

- Ngoài ra VietOCR cho phép nhận dạng trên các vùng khoanh

chọn để cho ra kết quả chính xác hơn.

- Tính năng hậu xử lý: Định dạng lại trang văn bản ban đầu, chỉnh lỗi

chính tả,…

Hạn chế của phần mềm: Độ chính xác nhận dạng không cao, các module

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

phân trang văn bản chưa tốt.

Trang - 22-

1.3.Những vấn đề ảnh hưởng tới chất lượng của một phần mềm nhận

dạng

Chất lượng của ảnh đầu vào là yếu tố quyết định tới độ chính xác của một

hệ thống nhận dạng.Hầu hết các hệ thống nhận dạng chữ hiện đang được thương

mại hóa trên thị trường đều cho độ chính xác cao trên những ảnh đầu vào có

chất lượng tốt.Tuy nhiên, độ chính xác này thường không được đảm bảo trong

trường hợp ngược lại. Ngay cả khi văn bản được in thông thường, dễ dàng nhận

dạng mặt chữ và định dạng, vẫn có rất nhiều lỗi sinh ra do ảnh đầu vào có chất

lượng thấp hay nói một cách khác là do những lỗi về mặt hình ảnh (imaging

defect). Những lỗi này thường bao gồm các ký tự bị dính, bị nhiễu, in quá đậm,

các ký tự bị mờ, đứt hoặc mất nét. Ngoài ra các nhiễu vệt và các đường baseline

cong cũng là những nguyên nhân gây ảnh hưởng đến chất lượng nhận dạng.

Các lỗi hình ảnh thường sinh ra trong quá trình in ấn (printing process) hoặc

quá trình thu nhận hình ảnh (scanning process). Các băng mực máy in quá đậm

có thể tạo ra các ký tự bị nhòe hoặc có vết bẩn, trong khi các băng mực bị mòn

sẽ sinh ra các bản in mờ nhạt. Việc sao chụp (photocopy) các văn bản nhiều lần

sẽ làm mất dần các thông tin làm cho các ký tự trên đó bị đứt, gẫy và mất nét.Ở

bước thu nhận hình ảnh, các phần mềm điều khiển thiết bị quét thường cho

phép người dùng hiệu chỉnh ngưỡng độ sáng thông qua chức năng điều khiển

độ sáng (brightness control). Việc lựa chọn giá trị ngưỡng này ảnh hưởng trực

tiếp tới độ chính xác của hệ thống OCR bởi vì nếu chọn ngưỡng thấp sẽ làm

cho các ký tự bị đứt, mất nét (broken characters), nếu chọn ngưỡng cao sẽ làm

cho các ký tự bị dính (touching characters). Giá trị ngưỡng này đôi khi cũng

bất thường do các nhiễu nhiệt hoặc nhiễu điện, bản thân độ nhạy cảm

(sensitivity) cũng có thể rất khác nhau giữa các phần tử cảm ứng của máy quét

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

do sự không hoàn hảo của qui trình sản xuất. Do đó, các ký tự giống hệt nhau

Trang - 23-

trên các phần khác nhau trên trang văn bản có thể có hình ảnh nhị phân khác

nhau[1].

1.3.1.Chữ bị dính, nhòe

Tách ký tự (character segmentation) là quá trình xác định vị trí của các ký

tự riêng biệt trong một từ. Khi các ký tự bị dính nhau hoặc bị nhòe do chữ được

quá đậm, các hệ thống OCR cần phải áp dụng những kỹ thuật đặc biệt để phân

tách chúng (xem Hình 1.6)

Hình 1.6: Trường hợp văn bản in đậm

Thậm chí đối với những ký tự có thể phân tách một cách dễ dàng, việc in

quá đậm cũng có thể làm biến dạng hình ảnh của chúng, làm cho việc nhận

dạng chúng rất khó khăn.Với kiểu in đậm, hình dạng của các ký tự hoa thường

có xu hướng tương tự nhau và giống như các hình khối.Điều này gây khó khăn

cho việc phân tách và nhận dạng chúng (xem Hình 1.7)

Hình 1.7: Một số hình ảnh bị biến dạng của các ký tự

Ngoài ra, đối với các văn bản kém chất lượng, đã qua nhiều bước tiền xử

lý, hình ảnh của các ký tự tiếng Việt có thể bịbiến dạng do phần dấu bị nhòe,

bị dính vào các thành phần khác của chữ và rất khó để phân biệt (xem Hình

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

1.8)

Trang - 24-

Hình 1.8: Hình ảnh các ký tự tiếng Việt bị nhập nhằng phần dấu

1.3.2.Văn bản bị đứt hoặc mất nét

Thực tế cho thấy là các ký tự bị đứt/mất nét gây ra nhiều lỗi hơn các ký tự

in đậm hoặc mờ. Đây có thể là hệ quả của một thực tế là thông thường sẽ có

nhiều điểm trắng hơn điểm đen cho dù là trong trong các vùng văn bản của

trang ảnh. Như vậy, việc chuyển từ một điểm đen sang điểm trắng sẽ mất nhiều

thông tin hơn là trường hợp ngược lại. Các nguyên nhân điển hình gây ra sự

đứt/mất nét ký tự thường là do băng mực máy in bị mòn, các văn bản cần nhận

dạng đã qua sao chụp nhiều lần hoặc ảnh được quét với độ phân giải thấp(xem

Hình 1.9).

Hình 1.9: Trường hợp văn bản bị đứt và mất nét

Hình ảnh của các ký tự thu được từ các văn bản này có thể bịthiếu hoặc

mất đi những đặc trưng quan trọng giúp nhận biết được ký tự (xem Hình 1.10).

Hình 1.10: Hình ảnh của ký tự bị biến dạng do lỗi đứt nét

Nhìn chung, thách thức đối với một thuật toán phân lớp ký tự hiện vẫn là

trường hợp chỉ còn lại một vài điểm ảnh của một ký tự, thậm chí không đủ để

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

con người nhận biết ký tự đó một cách riêng biệt.Khi có quá nhiều ký tự bị đứt

Trang - 25-

nét có thể làm hỏng cả đoạn văn bản. Các hệ thống nhận dạng rất khó xử lý

những trường hợp như vậy, và có thể sinh ra những kết quả sai lệch hoàn

toàn.Trong những trường hợp đứt nét phức tạp, việc xác định mảnh nào thuộc

vào ký tự nào là một công việc rất khó đối với một hệ thống OCR.

1.3.3.Văn bản bị nhiễu

Các dạng nhiễu đặc biệt là nhiễu dạng vệt rất dễ gây nhầm lẫn cho các hệ

thống OCR. Nhiễu thường sinh ra do chất lượng in thấp hoặc do giấy in không

tốt (chẳng hạn giấy báo). Mặc dù nhiễu thường bắt nguồn từ các trang văn bản

cần nhận dạng, nhưng chúng cũng có thể được sinh ra bởi các đốm bụi trên trục

lăn của máy quét, bởi các vết hằn từ mặt kia của trang văn bản (xemHình 1.11).

Hình 1.11: Một số dạng nhiễu thường gặp trên văn bản

Bên cạnh những nhiễu liên quan đến chất lượng in ấn và chất lượng máy

quét, còn có rất nhiều dạng nhiễu có thể xuất hiện trên văn bản gốc cần nhận

dạng. Chẳng hạn như các dạng nhiễu do người đọc cố tình khoanh tròn hoặc

gạch chân vào các vùng văn bản (xemHình 1.12).

Hình 1.12: Văn bản bị các nhiễu đánh dấu

Đặc biệt với các văn bản ở dạng công văn, biên bản hoặc quyết định,

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

thường xuất hiện các loại nhiễu do con dấu hoặc chữ kí bị chờm lên các vùng

Trang - 26-

văn bản cần nhận dạng (xemHình 1.13).Những nhiễu dạng này hiện vẫn là vấn

đề khó đối với bài toán nhận dạng.

Hình 1.13: Văn bản bị nhiễu do bị chồng chữ ký/con dấu

1.3.4.Văn bản được in với các kiểu font chữ đặc biệt

Các hệ thống nhận dạng thường được huấn luyện để nhận dạng các ký tự

của các kiểu font chữ thông thường chẳng hạn đối với tiếng Việt có các font

chữ Unicode thường dùng như Arial, Courier, Tahoma, Times New Roman và

Verdana. Do các ký tự của font chữ .VnTime không khác biệt nhiều so với các

ký tự của font chữ Times, một hệ thống OCR có khả năng nhận dạng các ký tự

của font chữ .VnTime một cách dễ dàng mà không cần phải được huấn luyện

với font chữ này.

Tuy nhiên khi văn bản được in với font chữ đặc biệt chẳng hạn như

.VnGothic (xem Hình 1.14). Đây là font chữ khác hẳn với các loại font chữ

trên, hệ thống nhận dạng có thể sẽ bị thất bại hoàn toàn nếu nó không được

huấn luyện trước với kiểu font chữ này.

Hình 1.14:Văn bản được in với kiểu font chữ đặc biệt

1.3.5.Cỡ chữ quá lớn hoặc quá nhỏ

Cỡ chữ quá lớn về bản chất là không khó để nhận dạng.Tuy nhiên các hệ

thống OCR thường được tối ưu cho các cỡ chữ thông thường. Để đối phó với

các các ký tự có kích cỡ quá lớn, các hệ thống OCR có thể chuẩn hóa chúng,

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

tức là giảm kích thước của chúng tới kích thước chuẩn trước khi nhận dạng

Trang - 27-

chúng. Tuy nhiên, quá trình xử lý này có thể làm biến dạng hình ảnh của ký

tự.Điều này có thể gây ra các lỗi nhập nhằng cho thuật toán phân lớp ký tự.

Ngược lại, đối với những văn bản được in với cỡ chữ quá bé, rất nhiều chi

tiết quan trọng của ký tự có thể bị mất đi khi được quét với độ phân giải 30

DPI. Trong trường hợp này, việc quét văn bản với độ phân giải cao hơn có thể

khắc phục được vấn đề trên. Tuy nhiên, điều này lại có thể gây ra hiện tượng

nhòe và dính nét ký tự gây khó khăn cho các hệ thống nhận dạng trong việc

phân tách các ký tự

1.4.Kết luận

Trong chương này, luận văn đã đề cập đến các bước cơ bản của một quá

trình nhận dạng chữ với 6 bước cơ bản, bao gồm thu nhận ảnh, tiền xử lý, phân

trang văn bản, nhận dạng, hậu xử lý, lưu văn bản. Bên cạnh đó, luận văn đã tập

trung khảo sát một số phần mềm nhận dạng chữ hiện đang được công bố và

thương mại hóa trên thị trường như phần mềm VnDOCR của Viện Công nghệ

Thông tin, viện Hàn Lâm Khoa Học và Công Nghệ Việt Nam, phần mềm

FineReader của hãng ABBYY, phần mềm OmniPage của hãng Nuance và phần

mềm VietOCR, được xây dựng từ thư viện mã nguồn mở Tesseract của Google.

Ngoài ra, phần cuối của chương cũng đã tìm hiểu và hệ thống lại những vấn đề

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

ảnh hưởng tới chất lượng của một hệ thống nhận dạng.

Trang - 28-

CHƯƠNG 2 - PHƯƠNG PHÁP ĐÁNH GIÁ HIỆU QUẢ CỦA

CÁC PHẦN MỀM NHẬN DẠNG CHỮ VIỆT

Một hệ thống nhận dạng chữ có thể được định nghĩa một cách hình thức

là một hệ thống máy tính có khả năng chuyển đổi có khả năng chuyển đổi các

văn bản in trên giấy thành các văn bản điện tử có khả năng soạn thảo, hiệu

chỉnh và tìm kiếm,v.v.

Trong chương này, luận văn trình bày cơ sở lý thuyết của các độ đo và

phương pháp đánh giá chất lượng (độ chính xác) của các hệ thống nhận dạng

dựa trên ý tưởng tìm kiếm một ánh xạ (sự tương ứng) giữa các ký tự trong file

văn bản được nhận dạng với các ký tự trong file văn bản mẫu.

Các kết quả khảo sát từ thực tế cho thấy các lỗi chính tả trên các file văn

bản được nhận dạng thường sinh ra do bị mất (không nhận dạng được) hoặc

thừa ký tự (do việc phân tách ký tự bị sai). Do vậy, chúng ta không thể giả

thuyết ký tự thứ i trong file văn bản được nhận dạng tương ứng với ký tự thứ i

trong file văn bản mẫu. Trong thực tế, có thể tìm kiếm ánh xạ giữa hai chuỗi

ký tự bằng cách xác định một chuỗi các thao tác hiệu chỉnh để biến chuỗi ký tự

này thành chuỗi ký tự kia với chi phí tối thiểu. Việc tìm kiếm sự tương ứng tối

ưu này được biết đến như bài toán hiệu chỉnh chuỗi ký tự.

2.1.Một số khái niệm

 Tỷ lệ nhận dạng (recognition rate): Tỷ lệ phần trăm của các ký tự được

phân lớp một cách chính xác.

 Tỷ lệ loại bỏ (rejection rate): Tỷ lệ phần trăm của các ký tự mà hệ thống

không có khả năng nhận dạng. Trong quá trình xử lý, một hệ thống nhận

dạng dạng có thể đánh dấu lại các ký tự bị loại bỏ và không cần xét đến

ở các bước hiệu chỉnh sau đó.

 Tỷ lệ lỗi (error rate): Tỷ lệ phần trăm của các ký tự bị phân lớp sai. Các

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

ký tự bị phân lớp sai không được phát hiện bởi hệ thống, việc kiểm tra

Trang - 29-

lại văn bản đã nhận dạng là cần thiết để phát hiện và hiệu chỉnh những

lỗi này.

 Chuỗi ký tự: Chuỗi ký tự là một dãy các ký tự được kết thúc bằng ký

tự NULL (‘\0’). Ở đây, mỗi văn bản mẫu và mỗi văn bản được nhận

dạng sẽ được coi là một chuỗi ký tự.

 Chuỗi con (subsequence): Nếu một chuỗi A bất kỳ có thể biến đổi

được thành chuỗi ký tự C bởi không hoặc nhiều thao tác xóa thì C được

gọi là chuỗi con (subsequence) của A.

 Chuỗi con chung (common subsequence): Một chuỗi ký tự C được

gọi là chuỗi con chung của 2 chuỗi A và B nếu và chỉ nếu C là chuỗi

con của A và C là chuỗi con của B.

 Chuỗi con chung lớn nhất (longest common subsequence -LCS):

Nếu C là một chuỗi con chung của hai chuỗi A, B và không tồn tại bất

kỳ một chuỗi con nào khác của A, B mà có số ký tự nhiều hơn C thì C

được gọi là chuỗi con chung lớn nhất của A và B, ký hiệu C =

LCS(A,B).

Cụ thể, giả sử LA,B là số lượng ký tự trong LCS(A,B) của A và B.

Nếu A = yxzyyx và B = yyxx, thì:

- Chuỗi yzyx là một chuỗi con của A.

- Chuỗi yxx và yyx là các chuỗi con chung dài nhất của A và B, LA,B =3.

- Chuỗi xx là một chuỗi con chung của A và B.

2.2.Bài toán hiệu chỉnh chuỗi ký tự (string editing)

Cho 𝐴 = 𝑎1𝑎2 … 𝑎𝑚 là chuỗi gồm mký tự và chuỗi 𝐵 = 𝑏1𝑏2 … 𝑏𝑛gồm

n ký tự trong bảng chữ cái ∑. Trong bài toán hiệu chỉnh chuỗi ký tự, 3 thao

tác hiệu chỉnh có thể được áp dụng cho A:

1. Thao tác chèn (Insertion): chèn bất kì ký hiệu nào trong bảng chữ cái ∑

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

vào trước 𝑎1, sau 𝑎𝑚 hoặc giữa 𝑎𝑖 và 𝑎𝑖+1(1 ≤i

Trang - 30-

2. Thao tác xóa (Deletion): một ký tự𝑎𝑖 có thể bị xóa (1 ≤i ≤m);

3. Thao tác thay thế (Substitution): một ký tự ai nào đó có thể bị thay thế

bởi một ký tự x bất kỳ (x≠ai) (1 ≤i ≤m);

Một hàm chi phí γ= (𝛾𝐼,𝛾𝐷 ,𝛾𝑆) xác định chi phí của chèn, xóa và thay

thế, tương ứng, với 𝛾𝐼,𝛾𝐷 ,𝛾𝑆 là các số thực không âm.

Giả sử 𝑑𝐴,𝐵,𝛾là chi phí tối thiểu để biến chuỗi A thành chuỗi B sử dụng

hàm chi phí γ. Khi γ là (1,1,1) hoặc (1,1,2) thì𝑑𝐴,𝐵,𝛾 được gọi là khoảng cách

Levenshtein(Levenshtein distance) giữa A và B. Hàm khoảng cách này còn

được gọi là không gianLevenshtein(Levenshtein metric) bởi vì nó đáp ứng

được các tính chất của một metric:

1. 𝑑𝐴,𝐵,𝛾 >0 nếu A≠ B; 𝑑𝐴,𝐴,𝛾=0;

2. 𝑑𝐴,𝐵,𝛾 = 𝑑𝐵,𝐴,𝛾;

3. 𝑑𝐴,𝐶,𝛾≤ 𝑑𝐴,𝐵,𝛾+ 𝑑𝐵,𝐶,𝛾;

Đối với một hàm chi phí tùy ý γ= (γI,γD,γS), dA,B,γđược gọi là khoảng

cách hiệu chỉnh (edit distance) hoặc khoảng cách Levenshtein có trọng số

(weighted Levenshtein distance) giữa A và B. Hàm khoảng cách

này là một metric khi γI= γD>0 và γS>0.

Từ đây chúng ta có thể đưabài toán hiệu chỉnh chuỗi thành bài toán tìm

đường đi ngắn nhất trên một đồ thị hiệu chỉnh (edit graph) được định

nghĩa cụ thể như sau:

Giả sử𝐴 = 𝑎1𝑎2 … 𝑎𝑚và 𝐵 = 𝑏1𝑏2 … 𝑏𝑛là các chuỗi ký tự, có độ dài

tương ứng m và n (m≥0, n≥0). Đồ thị hiệu chỉnh của A và B, ký hiệu 𝐺𝐴,𝐵 là

một đồ thị có hướng, không có chu trình, có (m+1)(n+1) đỉnh, được ký hiệu

𝑣𝑖,𝑗 với 0≤i≤m và 0≤j≤n. Các cạnh (cung) của đồ thị 𝐺𝐴,𝐵 được chia thành ba

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

nhóm:

Trang - 31-

1. Cạnh ngang (horizontal arcs): các cạnh (𝑣𝑖,𝑗−1, 𝑣𝑖,𝑗 ), với 0≤ i ≤m

và 0

2. Cạnh dọc (vertical arcs): các cạnh (𝑣𝑖−1,𝑗, 𝑣𝑖,𝑗 ), với 0< i ≤m và

0≤j≤n;

3. Cạnh chéo (diagonal arcs): các cạnh (𝑣𝑖−1,𝑗−1, 𝑣𝑖,𝑗 ), với 0< i ≤m

và 0

Nếu ai= bj thì cạnh chéo (𝑣𝑖−1,𝑗−1, 𝑣𝑖,𝑗 ) được gọi là cạnh phù hợp

(matching arc), ngược lại thì được gọi là một cạnh không phù hợp (non-

matching arc).

Một đường hiệu chỉnh (edit path) là một đường đi có hướng bất

kỳ từ đỉnh𝑣0,0 đến 𝑣𝑚,𝑛 trên đồ thị 𝐺𝐴,𝐵. Đường đi này xác định một chuỗi

các thao táchiệu chỉnh để biến chuỗi A thành chuỗi B. Một cạnh ngang

(𝑣𝑖,𝑗−1, 𝑣𝑖,𝑗) trên đường đi xác định rằng ký tự𝑏𝑗 được chèn vào, trong khi đó

một cạnh dọc (𝑣𝑖−1,𝑗 , 𝑣𝑖,𝑗) xác định rằng ký tự 𝑎𝑖 bị xóa. Một cạnh không

phù hợp (𝑣𝑖−1,𝑗−1, 𝑣𝑖,𝑗) xác định rằng 𝑏𝑗 bị thay thế bởi 𝑎𝑖, và một cạnh phù

hợp ngầm định rằng không có thao tác hiệu chỉnh nào được thực hiện. Trong

thực tế, các cạnh phù hợp trên đường đi sẽ xác định một chuỗi con chung của

A và B.

Nếu trọng số của mỗi cung bằng với chi phí của bước hiệu chỉnh mà

nó đang biểu diễn thì một đường hiệu chỉnh có trọng số nhỏ nhất sẽ được coi

là một đường đi tối ưu (đường đi ngắn nhất) trên đồ thị hiệu chỉnh 𝐺𝐴,𝐵 và

tổng trọng số (độ dài) của đường đi đó được gọi là khoảng cách hiệu chỉnh

giữa 2 chuỗi.

Hình 2.1 thể hiện đồ thị hiệu chỉnhcho các chuỗi A = zxy và B = xyxz.

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Mỗi cạnhbiểu diễn một thao tác hiệu chỉnhđã được gán nhãn với I là thao tác

Trang - 32-

chèn, D là thao tác xóa, S là thao tác thay thế. Các cạnh phù hợp không được

gán nhãn.

Hình 2.1: Đồ thị G(A,B), vớiA = zxy và B = xyxz

Hai đường đi trên đồ thị G(A,B) được chỉ ra trên Hình 2.2.Mỗi đường

đi xác định một chuỗi các thao tác để chuyển chuỗi A thành chuỗi B. Trong

đó, đường đi thứ nhất (đường nét đứt) chứa 1 thao tác xóa (D) và 2 thao tác

chèn (I), trong khi đường đi thứ 2 (đường nét chấm) chỉ chứa 1 thao tác chèn

(I) và 2 thao tác thay thế (S).

Nếu sử dụng hàm chi phí (1,1,2) thì đường nét đứt sẽ là đường đi ngắn

nhất trên đồ thị và khoảng cách chỉnh sửa được tính bằng 3. Nếu sử dụng hàm

chi phí (2,1,1) thì đường nét chấm là đường đi ngắn nhất trên đồ thị và khoảng

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

cách chỉnh sửa bằng 4.

Trang - 33-

Hình 2.2: Các đường đi trên đồ thị G(A, B)

Một vài giá trị cận dưới đã được đề xuất đối với độ phức tạp của thuật

toán hiệu chỉnh chuỗi. Trong [15], các tác giả đã chứng minh đối với các

chuỗi có độ dài n bao gồm các ký tự từ một bảng chữ cái vô hạn, độ phức tạp

tính toán được ước lượng là(𝑛2). Tuy nhiên, đối với một bảng chữ cái hữu

hạn, Masek và Paterson[2] đã đề xuất một thuật toán chỉ yêu cầu độ phức tạp

thời gian O(𝑛2/log n) trong trường hợp xấu nhất. Đối với bài toán LCS, một

số độ phức tạp thời gian sau đây đã được chứng minh và công nhận:

1. (ns) đối với một bảng chữ cái kích thước hữu hạn[2].

2.  (nlog n) đối với một bảng chữ cái vô hạn[7].

Rất nhiều thuật toán đã được đề xuất cho bài toán hiệu chỉnh chuỗi.

Bảng 2.1 liệt kê một số thuật toán tiêu biểu cùng với độ phức tạp được ước

lượng tương ứng, trong đó n là độ dài của mỗi chuỗi ký tự, d là khoảng cách

hiệu chỉnh, L là chiều dài của một LCS.

Bảng 2.1: Giải thuật cho bài toán chỉnh sửa chuỗi

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 34-

Hàm Độ phức tạp Thuật toán Thời gian Không gian chi phí

Wagner & Fischer[14] Bất kỳ

(1,1,2) O(𝑛2) O(nL + nlog Hirschberg[7] (1,1,2)

Masek & Paterson[9] Bất kỳ O(𝑛2) O(nL) O(d2 + n) O(dLlogn) n) O(𝑛2/log n) O(𝑛2/log n)

Nakatsu, Kambayashi, & (1,1,2) O(nd) O(nd)

Bất kỳ O(nd) O(nd) Yajima[12] Ukkonen[13] (1,1,1) O(nd) O(𝑑2 + n)

Wu, Manber, Myers, & Miller[16] Apostolico, Browne, & Guerra[3] (1,1,2) (1,1,2) O(nd) O(nd) O(n) O(n)

Thuật toánUkkonen với hàm chi phí (1,1,1) có thể được sử dụng để tính

toán độ chính xác mức ký tự cho một hệ thống nhận dạng chữ (OCR).

2.3. Thuật toán Ukkonen

Trong thực tế, các thuật toán hiệu chỉnh chuỗi ký tự có độ phức tạp

thời gian𝑂(𝑛2) là không khả thi đối với bài toán tìm kiếm sự tương ứng tối

ưu giữa một chuỗi văn bản nhận dạng được với một chuỗi văn bản mẫu do số

lượng ký tự trên các chuỗi này thường khá lớn (vài chục nghìn ký tự). Do các

chuỗi văn bản này thường khá giống nhau và khoảng cách hiệu chỉnh nhỏ. Vì

vậy, một thuật toán yêu cầu độ phức tạp về thời gian và không gian cỡ O(nd)

sẽ khả thi.

Thuật toán Ukkonen[13] với hàm chi phí (1,1,1) là lý tưởng, cần O(nd)

thời gian và O(d2 + n) không gian. Giả sử cho chuỗi đầu vàoA =

a1a2 … amvà B = b1b2 … bn, phần sau đây sẽ mô tả các bước của thuật

toánmột cách cụ thể và chi tiết hơn.

Thuật toán 2.1: Thuật toán Ukkonen

Ukkonen_Algorithm(A, B)

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 35-

Input: Các chuỗivăn bản A = a1a2…am và B = b1b2…bm

Output: d = khoảng cách hiệu chỉnh giữa A và B sử dụng hàm chi phí (1, 1, 1)

row = mảng của các đường đi trên đồ thị

Procedure compute_row(k,d)

begin

i  max row [k-1,d-1], row[k+1,d-1]+1, row [k,d-1]+1};

j i+k;

while i

i  i+1;

j  j+1;

end while;

row [k,d]  i

end procedure;

begin

d -1;

while row [n-m, d] ≠ m do

d  d+1;

r d - min {m, n};

for k  max {-m, -d} to min {-1, -r} do

compute_row(k, d)

end for;

for k max {0, r} to min {n, d} do

compute_row(k, d)

end for

end while

end.

Mảng row là một mảng 2 chiều, thưa. Trong đó, chỉ lưu trữ những phần

tử được định nghĩa (mục đích để giảm độ phức tạp tính toán). Những phần tử

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

không được định nghĩa sẽ được coi là có giá trị bằng -1. Đường chéo k của

Trang - 36-

đồ thị G(A, B) chứa tất cả các đỉnh vi,j sao cho j – i = k. Vì vậy, các đường

chéo của đồ thị sẽ thuộc phạm vi từ -m tới n. Phần tử row[k][d] xác định chỉ

số hàng xa nhất trên đồ thị G(A,B) mà có thể đi đến được bởi một đường đi

có độ dài d từ đỉnh v0,0 tới một đỉnh trên đường chéo k.

Trước tiên, xuất phát từ đỉnh khởi đầu v0,0, đường đi có độ dài 0,thuật

toán chỉ cần xét đường chéo 0. Bước tiếp theo, thuật toán sẽ tiến hành tìm

kiếm các đường xa nhất có độ dài bằng 1 bằng cách xét các đường chéo -1,

0, +1. Sau đó, tiếp tục sử dụng các đường đi này để tìm kiếm các đường đi

xa nhất có độ dài bằng 2 đối với các đường chéo -2, 0, +2, thực hiện tương

tự như vậy cho đến khi gặp được đỉnh đích vm,n. Độ dài của đường đi này

chính là khoảng cách hiệu chỉnh và mảng row sẽ chứa các thông tin cần thiết

để dò lại đường đi ngắn nhất đã được xác định.

Thông thường, row(k,d) được tính với mỗi k trong đoạn [-d, +d]. Tuy

nhiên, một số đường chéo có thể sẽ bị loại bỏ do chúng không nằm trong kết

quả cuối cùng. Vì vậy, thuật toán sử dụng biến r để tránh những đường đi mà

biết chắc chắn là không cần thiết. Ngoài ra, các kết quả trung gian của thuật

toán cũng có thể được sử dụng để loại bỏ thêm các đường chéo không cần

thiết.

Thuật toán dò lại đường đi ngắn nhất từ mảng row được mô tả cụ thể

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

như sau:

Trang - 37-

Thuật toán 2.2: Thuật toán dò lại đường đi ngắn nhất từ mảng row

Shortest_Edit_Paths_Recovering(m, n, d, row)

Input:m, n, d , row

Output: Đường đi ngắn nhất trên đồ thị hiệu chỉnh

begin

i  m;

j  n;

while i>0 or j>0 do

k  j-i;

if I = row[k-1, d-1] then

horizontal-arc(vi,j-1,vi,j) thuộc đường đi ngắn nhất;

j  j-1;

d  d-1;

else if i = row [k+1, d-1] +1 then

vertical-arc (vi-1,j, vi,j) thuộc đường đi ngắn nhất;

i  i-1;

d  d-1;

else if i = row [k, d-1]+1 then

non-matching arc(vi-1,j-1,vi,j) thuộc đường đi ngắn nhất;

i i-1;

j j-1;

d d-1;

else

matching-arc(vi-1,j-1,vi,j) thuộc đường đi ngắn nhất;

i i -1;

j j -1;

end if

end while

end.

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 38-

Giả sử vi1,j1 và vi2,j2 là các đỉnh của đồ thị G(A,B) sao cho 0i1i2 m

và 0  j1 j2 n, D(vi1,j1vi2,j2) là độ dài đường đi ngắn nhất từ đỉnh vi1,j1 đến

đỉnh vi2,j2. Có thể dễ dàng chỉ ra rằng:

(2.1) |(i2- i1)-(j2- j1)| D(vi1,j1vi2,j2)  max{i2- i1, j2- j1}

Chú ý rằng row(k,d) = i có nghĩa là D(v0,0vi,i+k) =d.

Có thể sử dụng kết quả trung gian này để tính giá trị cận trên  cho

khoảng cách hiệu chỉnh giữa A và B, từ công thức (2.1) ta thấy:

D(vi,i+kvm,n)  max{m, n- k} – i

Do vậy:

D(v0,0vm,n)D(v0,0vi,i+k)+D(vi,i+kvm,n) d+max{m, n- k} – i=.

Đối với một đường chéo k bất kỳ, ta có thể suy ra giá trị cận dưới của

độ dài đường đi chứa 1 đỉnh trên đường chéo này như sau:

D(v0,0vi,i+k) + D(vi,i+kvm,n)  |k| + |k - (n - m)|.

Nếu |k| + |k - (n - m)| > thì có thể bỏ qua đường chéo k do nó không

thể chứa đỉnh nằm trên đường đi ngắn nhất. Điều này có nghĩa là tất cả các

đường chéo k mà hoặc sẽ bị bỏ qua.

Từ đó, một phiên bản cải tiến của thuật toán Ukkonen được đề xuất

như sau:

Thuật toán 2.3: Thuật toán Ukkonen cải tiến

Optimized_Ukkonen_Algorithm(A,B)

Input: Các chuỗivăn bản A = a1a2…am và B = b1b2…bm

Output: d = khoảng cách hiệu chỉnh giữa A và B sử dụng hàm chi phí (1, 1, 1)

row = mảng của các đường đi trên đồ thị

Procedure compute_row(k,d)

begin

i max row [k-1, d-1], row [k+1, d-1]+1, row [k, d-1]+1};

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 39-

ji+k;

while i

i  i+1;

j  j+1;

end while;

row [k, d]  i ;

if i = m then

lower  k +1

end if;

if j = n then

upper  k -1

end if;

𝛽  d+ max { m, n-k} - i;

𝑛−𝑚−𝛽

lower  max { lower,⌈

⌉};

2

𝑛−𝑚+𝛽

upper  min { upper,⌈

⌉};

2

end procedure;

begin

lower  -m;

upper  n;

d -1;

while lower ≤ n-m do

d  d+1;

if m ≤ n then

for k  min { n - m, d} downto max { lower, -d} do

compute_row(k,d)

end for;

for k  n – m +1 to min { upper, d} do

compute_row(k,d)

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 40-

end for

else

for k max { n -m, -d} to min { upper, d} do

compute_row (k,d)

end for

for k n – m -1 downto max { lower, -d} do

compute_row (k,d)

end for

end if

end while

end.

Trong thuật toán Ukkonen cải tiến, các biến lower và upper được sử

dụng để giới hạn phạm vi của các đường chéo khi row(k,d) được tính. Khi

một đường đi dài nhất đi tới đỉnh vm,m+k có nghĩa là nó đã đi đến hàngcuối

cùng của đồ thị hiệu chỉnh và chỉ có những đường chéo lớn hơn k mới cần

xét tiếp. Tương tự, khi một đường dài nhất đi tới đỉnh vn-k,n thì nó đã đi được

đến cột cuối cùng của đồ thị hiệu chỉnh và chỉ có những đường chéo nhỏ hơn

k mới cần xét tiếp.

Mặc dù những cải tiến này không cải thiện được tiệm cận thời gian

hoặc độ phức tạp không gian của thuật toán Ukkonen, nhưng các kết quả thực

nghiệm trên các văn bản được nhận dạng và văn bản mẫu đã chỉ ra rằng số

phần tử cần lưu trữ trong mảng row của thuật toán Ukkonen cải tiến đã giảm

đi khoảng 25% so với thuật toán Ukkonen ban đầu.

2.4. Độ chính xác mức ký tự

2.4.1. Đánh giá độ chính xác mức ký tự

Mục tiêu chính của một hệ thống OCR là nhận dạng chính xác các ký

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

tự trên các trang ảnh đầu vào. Có thể nói, độ chính xác là thước đo cơ bản

Trang - 41-

nhất để đánh giá hiệu quả của một hệ thống OCR. Độ chính xác thường được

tính toán dựa trên sự khác biệt của văn bản nhận dạng được so với văn bản

mẫu (ground-truth). Có rất nhiều cách để ước lượng sự khác biệt này, tuy

nhiên hướng tiếp cận dựa trên chi phí của việc hiệu chỉnh văn bản nhận dạng

được thành văn bản gốc hiện nay vẫn là hướng tiếp cận hợp lý và được sử

dụng nhiều nhất. Trong ứng dụng thực tế, các biên tập viên thường phải hiệu

chỉnh các văn bản nhận dạng trước khi chúng được sử dụng, vì vậy chi phí

hiệu chỉnh là quan trọng. Trong quá trình hiệu chỉnh, các biên tập viên thường

thực hiện các thao tác chèn, xóa, thay thế trên văn bản được nhận dạng. Vì

vậy, việc định nghĩa khoảng cách hiệu chỉnh (edit distance) giữa chuỗi văn

bản nhận dạng được và chuỗi văn bản mẫu dựa trên chi phí của các thao tác

hiệu chỉnh (chèn, xóa, thay thế) là hoàn toàn hợp lý.

Cụ thể, giả sử A = a1a2 … am là một chuỗi văn bản được nhận dạng và

B = b1b2 … bnlà chuỗi văn bản mẫu tương ứng của trang ảnh cần nhận dạng.

Số lỗi nhận dạng trên trang này được xác định bằng:

E=𝑑𝐴,𝐵,𝛾, trong đó hàm chi phí γ=(1,1,1)

Như vậy, số lỗi nhận dạng được tính bằng khoảng cách Levenshtein giữa

A và B hay nói một cách khác số lỗi nhận dạng được tính bằng số thao tác hiệu

chỉnh cần thiết tối thiểu để hiệu chỉnh văn bản nhận dạng được.

Trên cơ sở đó, độ chính xác mức ký tự trên trang văn bản nhận dạng

được tính bởi công thức:

𝑛 − 𝐸 𝑛

Nếu không có lỗi thì E=0, độ chính xác mức ký tự là 100%. Nếu có 23

lỗi trên một trang chứa tổng cộng 1000 ký tự thì độ chính xác mức ký tự là

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

97,7%. Nếu A và B không có ký tự chung thì E=max{m,n}.

Trang - 42-

Hình 2.3: Sự tương ứng giữa chuỗi văn bản nhận dạng và văn bản mẫu

Hình 2.3 chỉ ra sự tương ứng tối ưu giữa chuỗi văn bản nhận dạng và

chuỗi văn bản mẫu. Trong đó, các chuỗi được tách thành các chuỗi con phù

hợp (matching) và không phù hợp (non-matching), các chuỗi con phù hợp được

bao trong các hình chữ nhật. Các chuỗi con không phù được tạo ra từ một tập

các ký tự bị nhận dạng nhầm (nhận dạng sai).

Để rõ ràng và trực quan hơn, chúng ta sẽ xây dựng một tập cáclỗi nhầm

lẫn (confusion), trong đó mỗi lỗi nhầm lẫn sẽ liên kết một chuỗi con được nhận

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

dạng, ký hiệu𝑔1𝑔2 … 𝑔𝑝 với một chuỗi mẫu, ký hiệu𝑐1𝑐2 … 𝑐𝑞(xem

Trang - 43-

Bảng 2. 2.1). Một trong 2 chuỗi có thể rỗng, ký hiệu . Như vậy, mỗi lỗi

nhầm lẫn có thể hiệu chỉnh bởi:

q- min{p,q} thao tác chèn (insertions)

p- min{p,q} thao tác xóa (deletions)

min{p,q} thao tác thay thế (substitutions)

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Với tổng số max{p,q}thao tác hiệu chỉnh hoặc lỗi (xem Bảng 2.2).

Trang - 44-

Bảng 2.2: Độ chính xác mức ký tự

Nhầm lẫn

Thao tác chèn

Thao tác xóa

Thao tác thay thế

(confusions)

(insertions)

(deletions)

(substitution)

1

0

2

~ l V A N

0

1

0

-

1

0

1

r n  m

0

0

1

5  s

1

0

0

. 

0

1

1

v  l y

0

0

2

% B  9 8

3

2

7

Tổng số:

n = 48

E = 12

Độ chính xác mức ký tự = 75%

Có thể mở rộng phương pháp đếm lỗi này để cho phép các ký tự đặc

biệt(wildcard) hoặc các ký tự không cần quan tâm trong chuỗi văn bản

mẫu.Một trang văn bản có thể chứa một hoặc nhiều ký hiệu mà các hệ thống

OCR không có khả năng nhận dạng chúng, chẳng hạn các ký hiệu toán học (,

, , , , ,…) hoặc các ký hiệu bullet (•). Những ký hiệu này có thể được

biểu diễn bởi một hoặc nhiều ký tự đặc biệt trong chuỗi văn bản mẫu, trong đó

với mỗi ký hiệu wildcard sẽ cho phép các hệ thống OCR sinh ra một hoặc nhiều

ký tự bất kỳ mà không bị tính là lỗi.

Độ chính xác mức ký tựtrung bình trên một tập các trang văn bảnđược

tính bởi công thức:

∑ 𝑛𝑖 − ∑ 𝐸𝑖 ∑ 𝑛𝑖

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trong đó𝑛𝑖 là số ký tự, 𝐸𝑖 là số lỗi trong trang thứ i.

Trang - 45-

Bằng cách chia tập các trang thành các nhóm theo một số thuộc tính của

trang, độ chính xác mức ký tự trung bình cho mỗi nhóm có thể được xác định

và đối sánh với các nhóm khác để có được các đánh giá mức độ phụ thuộc của

độ chính xác nhận dạng vào thuộc tính của trang ảnh một cách chính xác và

trực quan hơn.

2.4.2. Đánh giá độ chính xác mức ký tự theo lớp mẫu

Trong thực tế, việc đánh giá độ chính xác nhận dạng trên từng lớp ký tự

rất hữu dụng đối với các nhà phát triển phần mềm OCR. Chẳng hạn, chúng ta

cầnbiết bao nhiêu phần trăm của các chữ cái thường, chữ cái hoa hoặc chữ số

được nhận dạng chính xác.

Giả sử ∑ là bảng chữ cái chứa các ký tự trong chuỗi văn bản mẫu. Một

lớp ký tự C làmột tập con bất kỳ của ∑. Gọi A là chuỗi văn bản nhận dạng được

và B là chuỗi văn bản mẫu của trang ảnh đầu vào. Giả sử một sự tương ứng tối

ưu giữa A và B được tính bởi hàm chi phí (1,1,1). Gọi là số ký hiệu trong B

thuộc vào lớp C, là số ký hiệu trong B thuộc vào lớp C và thuộc vào chuỗi

con không phù hợp (non-matching substring). Khi đó, độ chính xác mức ký tự

theo từng được tính bởi công thức:

n′ − E′ n′ và cho độ chính xác nức ký tự trung bình trên một tập các trang đượ tính bởi:

i − ∑ E′i ∑ n′i

∑n′

Trở lại ví dụ trên Hình 2.,độ chính xác mức ký tự trên lớp chữ thường là

82,6% ( =23, =4), trên lớp chữ số là 80% ( = 10, = 2).

2.4.3. Hiệu quả của các ký tự đánh dấu

Việc tìm kiếm và hiệu chỉnh lỗi trên các văn bản nhận dạng thường là

một công việc buồn tẻ và tiêu tốn rất nhiều thời gian và công sức của người

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

dùng. Để hạn chế điều đó, các hệ thống nhận dạng thường cung cấp các cơ chế

Trang - 46-

hỗ trợ người dùng bằng cách đánh dấu (gắn cờ) cho các ký tự không nhận dạng

được hoặc bị nghi ngờ là lỗi, với một số quy ước chung như sau:

- Một ký tự bị loại bỏ (reject character), thường được biểu diễn bằng một

dấu ngã (~) sẽ được đưa ra mỗi khi hệ thống không có khả năng nhận

dạng ký tự.

- Nếu một ký tự được nhận dạng nhưng có độ tin cậy thấp (low confidence),

hệ thống sẽ đánh dấu ký tự đó bị nghi ngờ bằng cách đặt một ký hiệu đặc

biệt, chẳng hạn như dấu mũ (‘^’) ngay trước ký tự đó.

Các ký hiệu bị loại bỏ và các ký hiệu bị nghi ngờ được gọi chung là các ký hiệu

được đánh dấu (marked characters).

Không phải tất cả các lỗi nhận dạng đều được coi như nhau. Một lỗi được

gắn cờ sẽ được gọi là một lỗi được đánh dấu (marked error). Các lỗi dạng này

sẽ có chi phí ít hơn các lỗi không được đánh dấu (unmarked error).

Gọi𝐴 = 𝑎1𝑎2 … 𝑎𝑚 là một là chuỗi văn bản nhận dạng được và 𝐵 =

𝑏1𝑏2 … 𝑏𝑛 là chuỗi văn bản mẫu của trang ảnh cần nhận dạng. Một ký tự nhận

dạng được𝑎𝑖bất kỳ được gọi là một ký tự bị đánh dấu nếu nó là một ký tự loại

bỏ (𝑎𝑖=~) hoặc nó được đánh dấu là ký tự bị nghi ngờ bằng một ký hiệu đặc biệt (ký hiệu này không phải là một trong các kýtự trong A).

Giả sử rằng một sự tương ứng tối ưu giữa A và B đã được xác định bằng

cách sử dụng hàm chi phí (1,1,1). Nếu một ký tự bị đánh dấu thuộc vào chuỗi

con phù hợp (matching substring) thì nó là một đánh dấu sai (false mark).

Ngược lại, nó sẽ thuộc vào chuỗi con không phù hợpvà đặt một cờ xác định lỗi

nhập nhằng (confusion).

Một ký tự bị đánh dấu trong một chuỗi con không phù hợp được coi như

đủ để đánh dấu tất cả các lỗi được liên kết với lỗi nhập nhằng. Chẳng hạn,

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

nếu𝑟^𝑛là kết quả nhận dạng của ký tự m thì cả hai lỗi được coi làđánh dấu mặc

Trang - 47-

dù chỉ có một ký tự dánh dấu được thể hiện. Do vậy,các lỗi không được đánh

dấuchỉ được tính đối với các lỗi nhập nhằng mà không chứa các ký tự đánh dấu.

Xem xét quá trình kiểm tra các ký tự bị đánh dấu và hiệu chỉnh các lỗi

đánh dấu. Nếu U là số lỗi không được đánh đánh dấu thì độ chính xác của văn

bản sau quá trình này, được gọi là độ chính xác mức ký tự sau chỉnh sửa,

được tính bằng:

𝑛 − 𝑈 𝑛

trên một trang, và được tính bằng:

∑ 𝑛𝑖 − ∑ 𝑈𝑖 ∑ 𝑛𝑖 trên một tập trang. Hiệu quả của quá trình này phụ thuộc vào độ chính xác đạt

được so với số lượng công việc có liên quan.Nếu tỷ lệ các ký tự đánh dấu sai

(false mark) là lớn thì cần phải bỏ ra nhiều công sức mà độ chính xác không

cải thiện không đáng kể.

2.5.Độ chính xác mức từ

2.5.1. Đánh giá độ chính xác mức từ Giả sử𝐴 = 𝑎1𝑎2 … 𝑎𝑚 là tập các từ trong chuỗi văn bản nhận dạng được

và 𝐵 = 𝑏1𝑏2 … 𝑏𝑛 là tập các từ trong chuỗi văn bản mẫu của một trang ảnh cần

nhận dạng.Để hiệu chỉnh chuỗi văn bản được nhận dạng, các thao tác chèn

thêm, xóa, và thay thế các từ cần phải được thực hiện.Một thao tác chèn là cần

thiết để chèn vào một từ còn thiếu; một thao tác xóa được sử dụng để loại bỏ

một từ vô nghĩa được tạo ra; thao tác thay thế dùng để thay thế một từ không

chính xác bằng từ đúng.

Trong ứng dụng thực tế, đôi khi không nhất thiết phải phạt lỗi các hệ

thống nhận dạng khi chúng sinh ra các từ vô nghĩa trong trường hợp người dùng

không muốn xóa chúng mà để chúng lạitrong cơ sở dữ liệu văn bản, điều này

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

sẽ không ảnh hưởng nhiều tới hiệu quả truy vấn.Như vậy, hàm chi phí thích

Trang - 48-

hợp được sử dụng để dóng hàng 2 chuỗi A và B là (1,0,1). Khoảng cách hiệu

chỉnh giữa A và B sử dụng hàm chi phí này là số các thao tác hiệu chỉnh cần

thiết (chèn, thay thế) và cũng là số từ không nhận dạng được bởi vì mỗi thao

tác chèn hoặc thay thế sẽ tương ứng với một từ không nhận dạng được

(misrecognized). Giả sử E biểu thị giá trị này, ta có:

𝐸 = 𝑑𝐴,𝐵,𝛾

Trong đó γ =(1,0,1). Độ chính xác mức từ của một trang sẽ là:

𝑛 − 𝐸 𝑛

và là tỷ lệ các từ được nhận dạng chính xác. Gọi LA,B là số ký tự trong LCS của A và B, dễ dàng chỉ ra rằng:

𝐸 = 𝑛 − 𝐿𝐴,𝐵

Vì thế độ chính xác mức từ có thể được tính bằng:

𝐿𝐴,𝐵 𝑛 Thật vậy, một LCS của A và B gồm các từ được nhận dạng chính xác.Do đó,

độ chính xác mức từ đối với một tập các trang ảnh đầu vào, được tính bằng:

hoặc ∑ 𝑛𝑖 − ∑ 𝐸𝑖 ∑ 𝑛𝑖 ∑ 𝐿𝑖 ∑ 𝑛𝑖

Trong đó 𝐿𝑖 là độ dài của một LCS của trang thứ i.

Hình 2.4 thể hiện kết quả của việc dóng hàng giữa chuỗi văn bản nhận

dạng được (Hình 2.4c) với chuỗi văn bản mẫu (Hình 2.4b) của ảnh văn bản đầu

vào (Hình 2.4a). Các chuỗi con chúng lớn nhất của 2 chuỗi văn bản này được

chỉ ra trên Hình 2.4d, các chuỗi này chứa các từ được nhận dạng đúng.

Các từ (words) được so sánh với nhau với giả thiết không phân biệt hoa,

thường. Do các hệ thống tìm kiếm văn bản thường không phân biệt hoa, thường

nênhoàn toàn hợp lý khi chúng ta chấp nhận "yuCCA" là chuỗi nhận dạng đúng

so với chuỗi mẫu "Yucca," và "deriV ED" là chuỗi nhận dạng đúng so với chuỗi

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

mẫu "Derived". Ngoài ra, cũng không tính các lỗi nhận dạng các dấu phẩy thành

Trang - 49-

dấu chấm bởi vì các lỗi này không ảnh hưởng nhiều đến hiệu quả truy vẫn văn

bản. Các chuỗi văn bản nhận dạng được trong ví dụ này được hiệu chỉnh bằng

một thao tác chèn, hai thao tác xóa và năm thao tác thay thế, nhưng E=6 do

a) Ảnh văn bản đầu vào

b) Chuỗi văn bản mẫu

thao tác xóa được bỏ qua.

Head contours in the saturated zone underlying Yucca Mountain, Nevada, and its environs are derived on the basis of alternative

c) Chuỗi văn bản nhận dạng được

Ilead contours in the satur ated zone underlying yucca Mountain. Ncvada. and its env irons are deriVed on the basis ofalternative

d) Dóng hàng 2 chuỗi văn bản

Tập các từ trên chuỗi văn bản mẫu

Tập các từ trên chuỗi văn bản nhận dạng được

Hình 2.4: Độ chính xác mức từ

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 50-

2.5.2. Độ chính xác không kể từ dừng

Trong truy vấnvăn bản (text retrieval), các từ dừng (stopwords) thường

không được đánh chỉ mục bởi chúngmang lại rất ít hoặc không có giá trị truy

vấn. Dưới đây là một số ví dụ về từ dừng trong tiếng Anh và tiếng Việt:

 Trong tiếng Anh: the,of,and,to, a;

 Trong tiếng Việt: là, lại, nên, nếu;

Những từ mà không phải là từ dừng (được gọi là non- stopword)đều được

lập chỉ mục. Thông thường, người dùng sẽ tìm kiếm các tài liệu có chứa một

hoặc nhiều từ không phải từ dừng. Do đó, độ chính xác nhận dạng các từ không

phải từ dừng là hợp lý trong một ứng dụng truy xuất văn bản.

Gọi A là một chuỗi các từ được nhận dạng, B là một chuỗi các từ của văn

bản mẫu tương ứng của trang ảnh cần nhận dạng. Giả sử một LCS của A và B

đã được tính, trong đó chứa các từ của B đã được nhận dạng đúng.GọiS là một

tập các các từ dừng, n’ là số các từ không phải từ dừng của B và E’ là số từ

không phải từ dừng của B mà không nhận dạng được. Độ chính xác mức từ

không kể các từ dừng của trang văn bản được tính bằng:

𝑛′ − 𝐸′ 𝑛′

(là tỷ lệ phần trăm củacác từ không phải từ dừng đã được nhận dạng đúng)

Trên một tập các trang ảnh đầu vào, độ chính xác mức từ trung bình không kể

các từ dừng được tính bằng:

∑ 𝑛′𝑖 − ∑ 𝐸′𝑖 ∑ 𝑛′𝑖

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Chẳng hạn, với ví dụ trên

Trang - 51-

Hình 2.2.4, nếu tập các từ dừng là:

S={a, and, are, in, its, of, on, the, to}

Thì độ chính xác không kể từ dừng là 58.33% (n’=12, E’=5)

2.6. Kết luận chương 2

Trong chương này, luận văn trình bày cơ sở lý thuyết của các độ đo và

phương pháp đánh giá chất lượng (độ chính xác) của các hệ thống nhận dạng

dựa trên ý tưởng tìm kiếm một ánh xạ (sự tương ứng) giữa các ký tự trong file

văn bản được nhận dạng với các ký tự trong file văn bản mẫu.Nội dung đánh

giá mà chương đã đề cập đến là đánh giá độ chính xác mức ký tự và độ chính

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

xác mức từ.

Trang - 52-

CHƯƠNG 3-THỰC NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ

Trong chương này, luận văn tiến hành cài đặt và kiểm thử chương trình

đánh giá tự động độ chính xác của các phần mềm nhận dạng chữ dựa trên cơ

sở lý thuyết đã được đề cập trong chương 2. Bên cạnh đó, luận văn đã tiến hành

thu thập, xây dựng được một bộ cơ sở dữ liệu bao gồm các file ảnh văn bản

tiếng Anh và tiếng Việt, được quét với chế độ đen/trắng (B&W), với 3 ngưỡng

độ phân giải: 200DPI, 300DPI và 400DPI. Mỗi file ảnh văn bản được cung cấp

kèm với một file văn bản mẫu.Luận văn đã tiến hành thử nghiệm đánh giá trên

bốn phần mềm nhận dạng: VnDOCR, FineReader, Omnipage, VietOCR. Trong

đó VnDOCR, FineReader, Omnipage là ba phần mềm dạng được thương mại

hóa trên thị trường, VietOCR là phần mềm mã nguồn mở được xây dựng từ bộ

mã nguồn mở Tesseract, được phát triển bởi Google.

3.1.Phân tích, cài đặt chương trình

3.1.1.Quy trình thực hiện

Chương trình thử nghiệm được cài đặt trong môi trường Microsoft Visual

VnDOCR

Các file văn bản mẫu

Kết quả nhận dạng

FineReader

Kết quả nhận dạng

Bộ công cụ đánh giá hiệu quả của các phần mềm nhận dạng

OmniPage

Kết quả nhận dạng

Độ chính xác mức ký tự

Độ chính xác mức từ

VietOCR

Kết quả nhận dạng

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Studio 2008. Quy trình thực hiện được mô tả cụ thể trênHình 3.1.

Trang - 53-

Hình 3.1: Quy trình thực hiện của chương trình

Từ các ảnh văn bản đầu vào, trước tiên sẽ được nhận dạng bởi lần lượt

từng phần mềm. Kết quả nhận dạng trên mỗi ảnh đầu vào đối với mỗi phần

mềm được lưu vào một file văn bản (*.txt), dạng mã UTF8. Sau đó, bộ công

cụ đánh giá sẽ tiến hành đối sánh các file văn bản mẫu với các file kết quả nhận

dạng để tính ra các độ đo mức độ chính xác của các phần mềm như độ chính

xác mức ký tự, mức từ, mức câu và mức đoạn.

Chương trình thử nghiệm bao gồm các module chính như sau:

 Module đánh giá độ chính xác mức ký tự (character accuracy).

+ Đánh giá độ chính xác trên toàn bộ các lớp ký tự.

+ Đánh giá độ chính xác trên từng lớp ký tự.

+ Đánh giá độ chính xác trong trường hợp có sử dụng các ký tự đặc

biệt, ký tự đánh dấu (marked character).

 Module đánh giá độ chính xác mức từ (word accuracy).

+ Đánh giá độ chính xác trên toàn bộ các từ có trong văn bản.

+ Đánh giá độ chính xác trong trường hợp không kể các từ dừng

(Non-stopword accuracy).

+ Đánh giá độ chính xác mức từ trên đoạn văn bản (phrase

accuracy)

3.1.2. Các cấu trúc dữ liệu

Một số cấu trúc dữ liệu cơ bản sau đây được sử dụng để lưu thông tin trong

quá trình xử lý.

 Cấu trúc Accops: Được sử dụng để lưu số thao tác chèn, xóa, thay

thế các ký tự trong quá trình hiệu chỉnh từ văn bản nhận dạng được

Struct Accops{

long ins;

/* Số thao tác chèn ký tự */

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

thành văn bản mẫu:

Trang - 54-

long subst; /* Số thao tác thay thế ký tự*/

long del;

/* Số thao tác xóa ký tự*/

long errors; /* Tổng số lỗi = ins + subst +

del */

} Accops;

 Cấu trúc Accclass: Được sử dụng trong quá trình tính độ chính xác

Struct Accclass{

long count; /* Số ký tự của một lớp mẫu */

long missed; /*Số ký tự không nhận dạng được*/

};

mức ký tự trên từng lớp :

 Cấu trúc Accdata: Được sử dụng để lưu trữ thông tin trong quá trình

Struct Accdata

Struct Accdata{

long characters;/*Số ký tự trong file mẫu */

long errors; /*Tổng số lỗi*/

long reject_characters; /*Số ký tự bị loại bỏ

*/

long suspect_markers;/*Số ký tự bị nghi ngờ*/

long false_marks; /* Số ký tự đánh dấu sai*/

Accops marked_ops; /* Số các thao tác hiệu

chỉnh đối với các lỗi được đánh dấu */

Accops unmarked_ops;/* Số thao tác hiệu chỉnh

đối

với các lỗi không được đánh

dấu*/

Accops total_ops; /* Tổng số các thao tác hiệu

chỉnh đối với tất cả các lỗi */

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

tính độ chính xác mức ký tự trên từng lớp :

Trang - 55-

Accclass large_class[MAX_CHARCLASSES];

/* Số ký tự trên các lớp*/

Accclass total_class; /* Tổng số lớp ký tự*/

Conftable conftable;/*Bảng ký tự nhậpnhằng*/

};

 Cấu trúc Wac: Được sử dụng để lưu số từ của file văn bản mẫu và số

Struct Wac{

long count;

/* Tổng số từ */

long missed; /* Số từ không nhận dạng được*/

};

từ không nhận dạng được:

 Cấu trúc Wacdata: Được sử dụng để lưu thông tin trong quá trình

struct

{

Wac total; /*Tổng số từ*/

Wac stopword[MAX_WORDLENGTH + 1];/*Các từ

dừng*/

Wac non_stopword[MAX_WORDLENGTH + 1];

/*Mảng các từ không kể từ dừng*/

Wac distinct_non_stopword[MAX_OCCURRENCES + 2];

/*Số từ xuất hiện trên một trang văn bản*/

Wac phrase[MAX_PHRASELENGTH + 1];

/*Mảng các đoạn*/

} Wacdata;

tính độ chính xác mức từ:

3.1.3.Danh sách các từ dừng trong tiếng Việt

Danh sách các từ dừng (stop-word) sau đây được sử dụng trong quá trình

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

đánh giá độ chính xác mức từ:

Trang - 56-

Bảng 3.1: Bảng danh sách các từ dừng trong tiếng Việt

không

những

bị

của

theo

bởi

cùng

là

nơi

thì

cả

cũng

lại

nữa

trên

các

đã

lên

phải

trước

cái

đang

lúc

qua

từ

cần

đây

mà

ra

từng

càng

để

mỗi

rằng

và

chỉ

rất

vẫn

đến_nỗi

một_cách

chiếc

đều

này

rất

vào

cho

điều

nên

rồi

vậy

chứ

do

nếu

sau

vì

chưa

đó

ngay

sẽ

việc

chuyện

được

nhiều

so

với

có

dưới

như

sự

vừa

có_thể

gì

nhưng

tại

cứ

khi

3.1.4.Danh sách các ký tự đặc biệt

Như đã đề cập trong chương 2, hầu hết các phần mềm nhận dạng đang

được thương mại hóa trên thị trường đều có cơ chế sử dụng các ký tự đặc biệt

để đánh dấu các ký tự không nhận dạng được hoặc bị nghi ngờ (độ tin cậy thấp).

Từ việc khảo sát (thử nghiệm) thực tế, luận văn đã đề xuất quy ước sử dụng các

ký tự đặc biệt như sau:

- Dấu ngã (~) là các ký tự bị loại bỏ (reject character). Trong thực tế, ký

hiệu này thường được các phần mềm nhận dạng sinh ra trong trường

hợp không nhận dạng được ký tự (do hình ảnh của ký tự bị biến dạng,

mất mát thông tin hoặc ký tự cần nhận dạng là các ký hiệu toán học

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

đặc biệt, chẳng hạn như độ (o), , , , , , , , … )

Trang - 57-

- Dấu mũ (^) là ký hiệu đánh dấu nghi ngờ: Các ký tự đặt sau dấu (^) là

các ký tự bị nghi ngờ nhận dạng sai.

Chẳng hạn trong câu “Tòa nhà ngh^lêng 18~ ”, ký tự ‘l’ trong từ

“ngh^lêng” là ký tự bị nghi ngờ, dấu ~ sau con số 18 là ký tự bị loại bỏ

(tương ứng với ký hiệu độ o).

- Ký tự xuống dòng “<\n>”: Được sử dụng để đánh dấu kết thúc một

dòng trong văn bản.

3.1.5. Module đánh giá độ chính xác mức ký tự

Độ chính xác mức ký tự được tính toán bởi module CharacterAccuracy.

Module này sẽ tiến hành đối sánh nội dung của văn bản mẫu với văn bản được

sinh ra bởi các phần mềm nhận dạng để tính toán và đưa ra các thông tin đánh

giá, cụ thể như sau:

 Tổng số ký tự (Characters).

 Tổng số lỗi (Errors).

 Độ chính xác (Accuracy).

 Số ký tự bị loại bỏ (Reject Characters).

 Số ký tự đánh dấu (Suspect Markers).

 Số ký tự đánh dấu bị sai (False Marks) .

 Phần trăm các ký tự đánh dấu (Characters Marked).

 Số các thao tác hiệu chỉnh:

Thông tin về các thao tác hiệu chỉnh bao gồm số các thao tác chèn (Ins),

số thao tác thay thế (Subst), số thao tác xóa (Del), tổng số lỗi (Errors). Các

tham số này được thống kê trong cả hai trường hợp có sử dụng các ký tự đánh

dấu (Marked) và không sử dụng các ký tự đánh dấu (Unmarked), cụ thể như

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

sau:

Trang - 58-

Bảng 3.2: Thông tin các thao tác hiệu chỉnh

Marked

Ins

Subst

Del

Errors

Unmarked

Để thuận tiện cho việc thống kê và đánh giá và có khả năng mở rộng cho

nhiều ngôn ngữ khác nhau, module này có thể thông kê các kết quả đánh giá

theo các nhóm ký tự, chẳng hạn như:

- Các ký tự dấu cách (ASCII Spacing Characters).

- Các ký hiệu đặc biệt (ASCII Special Symbols).

- Các chữ số (ASCII Digits).

- Các ký tự in hoa (ASCII Uppercase Letters).

- Các ký tự in thường (ASCII Lowercase Letters).

Thông tin đánh giá độ chính xác mức ký tự trên các nhóm ký tự bao

gồm:Tổng số ký tự trên lớp (Count), số ký tự không nhận dạng được (Missed),

phần trăm ký tự nhận dạng đúng (%Right), cụ thể như sau :

Bảng 3.3: Thông tin về đánh giá độ chính xác mức ký tự

Count

Missed

%Right

ASCII Spacing Characters

ASCII Special Symbols

ASCII Digits

ASCII Uppercase Letters

ASCII Lowercase Letters

Total

 Độ chính xác mức ký tự trên lớp

Theo khảo sát thực tế, các phần mềm nhận dạng chữ Việt đều có khả năng

nhận dạng khoảng trên 200 lớp ký tự bao gồm:

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

- Các chữ số: 0…9 (10 số)

Trang - 59-

- Các chữ cái tiếng Anh: A..Z, a..z (52 ký tự)

- Các chữ cái tiếng Việt: Ă, Â, Đ, Ê, Ô, Ơ, Ư, ă, â, đ, ê, ô, ơ, ư (14 ký tự)

- Các chữ cái tiếng Việt có dấu: à, ả, ã, á, ạ, ằ, ẳ, ẵ, ắ, ặ, ầ, ẩ, ẫ, ấ, ậ, è, ẻ, ẽ, é, ẹ, ề, ể, ễ, ế, ệ, ì, ỉ, ĩ, í, ị, ò, ỏ, õ, ó, ọ, ồ, ổ, ỗ, ố, ộ, ờ, ở, ỡ, ớ, ợ, ù, ủ, ũ, ú, ụ, ừ, ử, ữ, ứ, ự, ỳ, ỷ, ỹ, ý, ỵ), À, Ả, Ã, Á, Ạ, Ằ, Ẳ, Ẵ, Ắ, Ặ, Ầ, Ẩ, Ẫ, Ấ, Ậ, È, Ẻ, Ẽ, É, Ẹ, Ề, Ể, Ễ , Ế, Ệ, Ì, Ỉ, Ĩ, Í, Ị, Ò, Ỏ, Õ, Ó, Ọ, Ồ, Ổ, Ỗ, Ố, Ộ, Ờ, Ở, Ỡ, Ớ, Ợ, Ù, Ủ, Ũ, Ú, Ụ, Ừ, Ử Ữ, Ứ, Ự, Ỳ, Ỷ, Ỹ, Ý, Ỵ (120 ký tự)

- Các ký hiệu thường dùng trong văn bản: {. , - : ; “ ” ‘ ’ ( ) # $ @ ! % ?

/}(trên 22 ký tự)

Các thông số đánh giá độ chính xác mức ký tự theo lớp tương tự như phần

trên (gồm tổng số ký tự trên lớp - Count, số ký tự không nhận dạng được -

Missed, phần trăm ký tự nhận dạng đúng %Right.

Ngoài ra, để giúp cho các nhà phát triển phần mềm có những kết quả phân

tích chính xác và trực quan hơn, chương trình có thể thống kê các lỗi cụ thể gặp

phải trên từng văn bản đầu vào.Ví dụ trên Hình Hình 3.3.2 thể hiện kết quả đánh

756 Characters

39 Errors

94.84% Accuracy

6 Reject Characters

7 Suspect Markers

1 False Marks

1.72% Characters Marked

96.96% Accuracy After Correction

giá độ chính xác mức ký tự trên một văn bản:

Ins Subst Del Errors

0 10 6 16 Marked

2 17 4 23 Unmarked

2 27 10 39 Total

Count Missed %Right

117 0 100.00 ASCII Spacing Characters

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 60-

31 4 87.10 ASCII Special Symbols

6 2 66.67 ASCII Digits

24 1 95.83 ASCII Uppercase Letters

578 22 96.19 ASCII Lowercase Letters

756 29 96.16 Total

Errors Marked Correct-Generated

4 0 {fl}-{n}

3 3 {w}-{~-.}

2 2 {r}-{I.}

2 2 {r}-{l-}

2 2 {sy}-{~v}

2 2 {te}-{~s}

2 2 {w}-{~.}

2 0 {,}-{.}

2 0 {a}-{,r}

2 0 {e}-{c}

2 0 {e}-{tr}

2 0 {g}-{ji}

1 1 {f}-{~}

1 1 {s}-{~}

1 1 {}-{.}

1 0 {/}-{I}

1 0 {2}-{3}

1 0 {8}-{6}

1 0 {I}-{i}

1 0 {]}-{1}

1 0 {e}-{s}

1 0 {f}-{i}

1 0 {t}-{i}

1 0 {}-{-}

Count Missed %Right

20 0 100.00 {<\n>}

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 61-

97 0 100.00 { }

5 0 100.00 {(}

5 0 100.00 {)}

5 2 60.00 {,}

5 0 100.00 {-}

7 0 100.00 {.}

2 1 50.00 {/}

2 0 100.00 {0}

2 1 50.00 {2}

1 0 100.00 {7}

1 1 0.00 {8}

1 0 100.00 {A}

1 0 100.00 {C}

2 0 100.00 {D}

1 0 100.00 {F}

1 0 100.00 {H}

1 1 0.00 {I}

2 0 100.00 {L}

2 0 100.00 {M}

2 0 100.00 {O}

1 0 100.00 {P}

3 0 100.00 {S}

30 100.00 {T}

1 0 100.00 {V}

3 0 100.00 {W}

1 0 100.00 {[}

1 1 0.00 {]}

56 1 98.21 {a}

7 0 100.00 {b}

26 0 100.00 {c}

27 0 100.00 {d}

88 5 94.32 {e}

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 62-

14 4 71.43 {f}

16 1 93.75 {g}

20 0 100.00 {h}

37 0 100.00 {i}

21 2 90.48 {l}

13 0 100.00 {m}

44 0 100.00 {n}

28 0 100.00 {o}

7 0 100.00 {p}

1 0 100.00 {q}

45 2 95.56 {r}

312 93.55 {s}

51 2 96.08 {t}

20 0 100.00 {u}

4 0 100.00 {v}

10 2 80.00 {w}

4 0 100.00 {x}

7 1 85.71 {y}

1 0 100.00 {z}

Hình 3.2: Kết quả đánh giá độ chính xác mức ký tự trên một văn bản

3.1.6. Module đánh giá độ chính xác mức từ

Độ chính xác mức từ được tính toán bởi module WordAccuracy. Module

này sẽ tiến hành đối sánh nội dung của văn bản mẫu với văn bản được sinh ra

bởi các phần mềm nhận dạng để tính toán và đưa ra các thông tin đánh giá, cụ

thể như sau:

 Tổng số từ (Words).

 Tổng số từ không nhận dạng được (Misrecognized).

 Độ chính xác (Accuracy).

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

 Đánh giá độ chính xác trong trường hợp tính cả các từ dừng:

Trang - 63-

Các thông số đánh giá được thống kê theo độ dài của từ, bao gồm số từ

(Count), số từ không nhận dạng được (Missed), tỷ lệ nhận dạng đúng (%Right),

độ dài của từ (length), cụ thể như sau:

Count Missed %Right

Length 1

2

… … … .

… … … .

… … … .

… … … n

… … … Total

 Đánh giá độ chính xác trong trường hợp không kể các từ dừng (Non-

stopwords): Các thông số đánh giá tương tự như trên.

 Đánh giá độ chính xác trên đoạn văn bản: Các thông số đánh giá tương

tự như trên.

Ngoài ra, để hỗ trợ các nhà phát triển phần mềm có được các thông tin

đánh giá chính xác và trực quan hơn, có thể đưa ra các thông số đánh giá chi

43928 Words

2211 Misrecognized

94.97% Accuracy

tiết cho từng từ xuất hiện trong văn bản. Xét tiếp với ví dụ trên:

Stopwords

Count Missed %Right Length

810 46 94.32 1

6069 128 97.89 2

6065 92 98.48 3

2438 61 97.50 4

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 64-

949 27 97.15 5

204 10 95.10 6

232 5 97.84 7

1 0 100.00 9

16768 369 97.80 Total

Non-stopwords

Count Missed %Right Length

2275 250 89.01 1

1050 249 76.29 2

1425 169 88.14 3

3025 160 94.71 4

3705 186 94.98 5

3327 172 94.83 6

3216 139 95.68 7

3132166 94.70 8

2345 125 94.67 9

1560 96 93.85 10

1032 57 94.48 11

599 38 93.66 12

260 17 93.46 13

118 5 95.76 14

58 11 81.03 15

23 2 91.30 16

3 0 100.00 17

5 0 100.00 18

2 0100.00 19

27160 1842 93.22 Total

Distinct Non-stopwords

Count Missed %Right Occurs

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 65-

11889 808 93.201

2437 54 97.782

868 15 98.27 3

431 7 98.38 4

241 1 99.59 5

155 4 97.42 6

107 496.26 7

69 1 98.55 8

621 98.39 9

35 0 100.00 10

112 1 99.11 >10

16406 896 94.54 Total

Phrases

Count Missed %Right Length

43928 2211 94.97 1

43753 3927 91.022

43578 5446 87.50 3

43403 6812 84.31 4

43228 8082 81.30 5

43053 9249 78.52 6

42878 10334 75.90 7

42704 11351 73.42 8

Stopwords

Count Missed %Right

723 32 95.57 a

69 1 98.55 about

32 1 96.88 after

9 1 88.89 again

10 0 100.00 against

...

Non-stopwords

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Trang - 66-

Count Missed %Right

2 2 0.00 ab

3 0 100.00 abbreviations

3 0 100.00 abernethy

6 0 100.00 ability

6 0 100.00 able

Hình 3.4: Đánh giá độ chính xác mức từ trên một file văn bản tiếng Việt

3.2.Đánh giá thực nghiệm

3.2.1. Dữ liệu thực nghiệm

Chương trình được thử nghiệm trên 2 bộ dữ liệu tiếng Anh và tiếng Việt.

Trong đó bộ dữ liệu tiếng Anh là bộ dữ liệu chuẩn, được cung cấp bởi viện

nghiên cứu khoa học thông tin ISRI (Information Science Research Institute)

Hoa Kỳ. Bộ dữ liệunày bao gồm tổng 7844 trang ảnh văn bản, được chia thành

6 tập dữ liệu, cụ thể như sau:

 Tập dữ liệu Business Letter (BUS): Chứa tập các trang văn bản ở dạng thư

tín do các tổ chức, cá nhân và doanh nghiệp tặng cho ISRI.

 Tập dữ liệu Corporate Annual Report (REP): Bao gồm các trang văn bản

được lựa chọn từ các báo cáo thường niên của các doanh nghiệp và các tổ

chức tài chính.

 Tập dữ liệu DOE (Department of Energy): Là tập dữ liệu mẫu lớn nhất trong

số các tập dữ liệu thử nghiệm, được lựa chọn một cách ngẫu nhiên từ tập

các văn bản khoa học và kỹ thuật.

 Tập dữ liệu English Newspaper Sample (NEWS): Chứa các trang báo được

lựa chọn một cách ngẫu nhiên từ 50 tạp chí thịnh hành nhất.

 Tập dữ liệu Legal Document (LEGAL): Chứa các trang được lựa chọn từ tập

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

văn bản luật, được thu thập từ các văn phòng luật và các tòa án địa phương.

Trang - 67-

 Tập dữ liệu Magazine (ZSET): Bao gồm các trang báo được lựa chọn một

cách ngẫu nhiên từ 100 tạp chí có số lượng phát hành lớn nhất.

Thông tin chi tiết hơn về các tập dữ liệu được thể hiện trên

Bảng 3.4: Các tập dữ liệu tiếng Anh

Tập dữ liệu Số trang Số khối Tổng số Số ký tự

từ

Business Letter (BUS) 800 5676 205840 1279024

Corporate Annual Report 1200 6826 12488028 3569064

(REP)

DOE (Department of Energy) 1844 854208 5854048 9120

English Newspaper Sample 800 336104 2460400 3124

(NEWS)

Legal Document (LEGAL) 1200 3388 58699 1488392

Magazine (ZSET) 800 9328 826592 4976684

7844 Tổng số: 37462 14769471 19627612

Mỗi trang văn bản sẽ được số hóa 4 lần bởi máy quét Fujitsu M3096G đế

sinh ra 3 ảnh nhị phân và một ảnh 8-bit grey scale. Các ảnh nhị phân được tạo

ra với các độ phân giải lần lượt là 200, 300 và 400dpi (dots per inch). Ảnh gray

scale được quét ở độ phân giải 300dpi. Mỗi file ảnh đi kèm với một file văn

bản mẫu và một file thông tin (ground truth) xác định tọa độ cũng như thứ tự

đọc các khối văn bản trên mỗi ảnh đầu vào.

Đối với dữ liệu tiếng Việt, hiện tại chưa có cơ sở dữ liệu mẫu chuẩn nào

được công bố để phục vụ cho việc thử nghiệm, đánh giá các thuật toán nhận

dạng. Để đánh giá hiệu quả của thuật toán trong nhận dạng văn bản tiếng Việt,

ở đây luận án đã thu thập và xây dựng ba tập dữ liệu sau đây phục vụ cho việc

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

thử nghiệm.

Trang - 68-

 Tập dữ liệu Vie Official Documen, bao gồm các trang văn bản, công văn,

thư từ, các bản fax bằng tiếng Việt lưu hành trong Viện Công Nghệ Thông

Tin.

 Tập dữ liệu Vie Magazine, bao gồm tập các văn bản được thu thập từ các

báo, tạp chí thịnh hành nhất ở Việt nam: báo Phụ Nữ, báo Thanh Niên, báo

Tiền Phong, báo Công An Nhân Dân, báo Gia Đình và Xã Hội, tạp chí Sinh

Học, tạp chí Bưu Chính Viễn Thông, tạp chí PC Word, tạp chí Sức Khỏe và

Đời Sống, v.v.

 Tập dữ liệu VieTypical Book chứa các trang văn bản có chất lượng rất khác

nhau được lựa chọn ngẫu nhiên từ một số loại sách, truyện, giáo trình, kỷ

yếu hội thảo, v.v.

Thông tin về các tập dữ liệu này được thể hiện cụ thể hơn trên [Bảng 3.5].

Bảng 3.5: Các tập dữ liệu Tiếng Việt

Tập dữ liệu Số trang Số vùng Tổng số từ Số ký tự

Vie Magazine 140 766 114358 419561

VieOfficial Document 265 722 87087 312964

Vie Typical Book 300 678 141609 525599

Tổng số: 705 2166 343054 1258124

Mỗi trang văn bản sẽ được quét 3 lần bằng máy quét HP C7716A ở chế

độ ảnh nhị phân (B & W) với các ngưỡng độ phân giải lần lượt là 200 dpi, 300

dpi và 400 dpi. Mỗi file ảnh sẽ đi kèm với một file văn bản mẫu và một file

ground truth định nghĩa tọa độ của các khối văn bản cần nhận dạng theo một

thứ tự đã được xác định (thông thường là theo thứ tự từ trên xuống dưới, từ trái

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

sang phải).

Trang - 69-

3.2.2.Kết quả thực nghiệm

Từ các tập dữ liệu mẫu đã thu thập được, quá trình thử nghiệm bao gồm 2

công đoạn cơ bản:

- Bước 1: Tiến hành nhận dạng toàn bộ các file ảnh mẫu bằng từng phần

mềm nhận dạng (VnDOCR, FineReader, OmniPage, VietOCR). Kết

quả nhận dạng trên mỗi file ảnh đầu vào sẽ được lưu vào một file văn

bản (*.txt), định dạng font chữ UTF8.

- Bước 2: Từ các file văn bản được nhận dạng và các file văn bản mẫu

tương ứng của mỗi ảnh văn bản đầu vào, chương trình sẽ gọi đến lần

lượt từng module trong số 6 module đã được liệt kê ở trên để đưa ra

các độ đo đánh giá mức độ chính xác của từng phần mềm nhận dạng

trên toàn bộ các tập dữ liệu thử nghiệm.

Phần sau đây sẽ trình bày các kết quả thực nghiệm đánh giá độ chính xác

của các phần mềm nhận dạng trên từng tập dữ liệu thử nghiệm.

 Độ chính xác mức ký tự

Các kết quả đánh giá độ chính xác mức ký tự trung bình trên với các tập

dữ liệu tiếng Anh được tổng kết cụ thể trên Bảng 3.6:

Bảng 3.6: Độ chính xác mức ký tự trên tập dữ liệu tiếng Anh

Các tập dữ liệu thử nghiệm

Phần mềm nhận dạng BUS REP DOE NEWS LEGAL ZSET

VnDOCR 97.15% 94.45% 95.26% 95.46% 97.27% 94.64%

FineReader 98.25% 95.7% 96.89% 97.08% 98.57% 96.37%

Omnipage 97.86% 94.67% 95.78% 96.88% 98.2% 96.05%

VietOCR 85.05% 74.2% 77.32% 77.43% 82.56% 75.52%

Kết quả đánh giá độ chính xác mức ký tự trung bình đối với các tập dữ

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

liệu tiếng Việt được thể hiện cụ thể trênBảng 3.7:

Trang - 70-

Bảng 3.7: Độ chính xác mức ký tự trên các tập dữ liệu tiếng Việt

Các tập dữ liệu thử nghiệm

Phần mềm nhận dạng Vie Magazine VieOfficial Document Vie Typical Book

92.48% 96.23% VnDOCR 94.4%

94.03% 98.16% FineReader 95.72%

- - Omnipage -

46.05% 52.17% 50%

VietOCR  Độ chính xác mức từ

Độ chính xác mức từ trung bình trên toàn bộ tập dữ liệu tiếng Anh trong

trường hợp kể cả từ dừng (STW) và không kể từ dừng (NSTW)được thể hiện

cụ thể trên Bảng 3.8.

Bảng 3.8: Độ chính xác mức từ trêntập dữ liệu tiếng Anh

Các tập dữ liệu thử nghiệm

Phần mềm nhận dạng

DOES TW/ NSTW NEWSST W/ NSTW LEGALST W/ NSTW

VnDOCR

FineReade r

VietOCR

BUS STW/ NSTW 96.25% 96.66% 97.48% 97.83% Omnipage 97.37% 97.56% 83.28% 83.55% REP STW/ NSTW 93.3% 93.52% 94.17% 94.46% 93.63% 93.8% 70.11% 70.26% 93.58% 93.7% 95.02% 95.28% 94.14% 94.38% 70.29% 70.33% 94.52% 94.66% 96.12% 96.32% 95.2% 95.31% 71.26% 71.33% 96.22% 96.38% 98.03% 98.21% 96.42% 96.6% 74.12% 74.32% ZSET STW/ NSTW 94.06% 94.22% 95.49% 95.58% 94.15% 94.29% 72.16% 72.27%

Độ chính xác mức từtrung bình đối với các tập dữ liệu tiếng Việt được thể

hiện cụ thể trênBảng 3.9.

Bảng 3.9: Độ chính xác mức từ tập dữ liệu tiếng Việt

Phần mềm nhận dạng

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Vie Magazine (%) STW/ Các tập dữ liệu thử nghiệm VieOfficial Document (%) STW/ Vie Typical Book (%) STW/

Trang - 71-

NSTW NSTW NSTW

VnDOCR

FineReader

Omnipage VietOCR

92.23% 92.46% 95.07% 95.28% - 48.02% 48.23% 91.12% 91.28% 93.68% 93.89% - 45.29% 45.48% 95.14% 95.27% 97.53% 97.67% - 50.27% 50.38%

3.2. Kết luận chương 3

Trong chương này, luận văn đã mô tả cụ thể quy trình cũng như các bước

xây dựng chương trình thử nghiệm đánh giá độ chính xác của các phần

mềm/thuật toán nhận dạng văn bản.Trong đó, tập trung vào2 độ đo cơ bản: Độ

chính xác mức ký tự (character accuracy) và độ chính xác mức từ (word

accuracy). Trong đó, độ chính xác mức ký tự được đánh giá trong các trường

hợp tổng quát (trên toàn bộ lớp ký tự), trên từng lớp ký tự và trong trường hợp

có sử dụng các ký tự đặc biệt, các ký tự đánh dấu.Độ chính xác mức từ được

đánh giá trong trường hợp xét toàn bộ các từ trong văn bản (kể cả các từ dừng)

và trường hợp không sử dụng từ dừng. Hiệu quả của chương trình đánh giá đã

được kiểm nghiệm trên 2 tập dữ liệu tiếng Anh và tiếng Việt (đủ lớn,đa dạng

về chất lượng).Thực nghiệm cho thấy chương trình đánh giá độ chính xác của

các phần mềm thuật toán nhận dạng có thể mang lại cho các nhà phát triển phần

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

mềm nhận dạng chữ những thông tin đánh giá chi tiết, chính xác và trực quan.

Trang - 72-

KẾT LUẬN

Luận văn đã tìm hiểu về một số các vấn đề trong nhận dạng chữ viết

như sau:

 Xây dựng bộ công cụ đánh giá hiệu quả cho các engine nhận dạng chữ

Việt.

 Xâydựng cơ sở dữ liệu mẫu chuẩn, phục vụ cho việc nghiên cứu, đánh

giá và thử nghiệm các thuật toán nhằm nâng cao chất lượng nhận dạng.

Phần thực nghiệm, luận văn đã tiến hành đánh giá so sánh các phần mềm

nhận dạng chữ Việt hiện có như FineReader,VnDOCR, Omnipage, VietOCR.

Tuy nhiên luận văn còn một số vấn đề chưa giải quyết được đó là:

 Luận văn mới chỉ đánh giá các phần mềm nhận dạng trên 2 tiêu chí là

mức ký tự và mức từ.

 Từ việc đánh giá kết quả nhận dạng chưa cải thiện được chất lượng

nhận dạng cho các phần mềm nhận dạng chữ.

Hướng phát triển của luận văn là xây dựng thêm các công cụ đánh giá

khácvà dựa trên kết quả đánh giá đó góp phần để các nhà sản xuất phần mềm

đánh giá chất lượng sản phẩm phần mềm của mình và từ đó đưa ra hướng phát

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

triển và nâng cấp phần mềm của mình.

Trang - 73-

DANH MỤC TÀI LIỆU THAM KHẢO

Tài liệu tham khảo tiếng Việt

[1] Nguyễn Thị Thanh Tân, (2013), “Nghiên cứu phương pháp nâng cao độ

chính xác nhận dạng chữ in đứt, dính và chữ viết tay hạn chế trong tiếng

Việt”, Luận án tiến sĩ toán học, Viện Công nghệ Thông tin, Viện Hàn lâm

Khoa học và Công nghệ Việt Nam, 2013.

Tài liệu tham khảo tiếng Anh

[2] Aho, A. V., Hirschberg, D. S., & Ullman, J. D. (1976). Bounds on the

complexity of the longest common subsequence problem. Journal of the

ACM, 23(1), 1-12.

[3] Apostolico, A., Browne, S., & Guerra, C. (1992). Fast linear-space

computationsof longest common subsequences. Theoretical

ComputerScience, 92, 3-17.

[4] Eppstein, D., Galil, Z., Giancarlo, R., & Italiano, G. F. (1992). Sparse

dynamic programming I: Linear cost functions. Journal of the

ACM,39(3), 519-545.

[5] Fickett, J. W. (1984). Fast optimal alignment. Nucleic Acids

Research,12(1), 175-179.

[6] Hsu, W. J., & Du, M. W. (1984). New algorithms for the LCS

problem.Journal of Computer and System Sciences, 29, 133-152.

[7] Hirschberg, D. S. (1978). An information-theoretic lower bound for the

longest common subsequence problem. Information Processing Letters,

7(1), 40-41.

[8] Hunt, J. W.,& Szymanski, T. G. (1977). A fast algorithm for computing

longest common subsequences. Communications of the ACM, 20(5), 350-

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

353.

Trang - 74-

[9] Masek, W. J., & Paterson, M. S. (1980). A faster algorithm computing

string edit distances. Journal of Computer and System Sciences, 20(1), 18-

31.

[10] Mukhopadhyay, A. (1980). A fast algorithm for the longest-

commonsubsequence problem. Information Sciences, 20, 69-82.

[11] Myers, E. W. (1986). An O(ND) difference algorithm and its variations.

Algorithmica, 1, 251-266.

[12] Nakatsu, N., Kambayashi, Y., & Yajima, S. (1982). A longest

commonsubsequence algorithm suitable for similar text strings. Acta

Informatica,18, 171-179.

[13] Ukkonen, E. (1985). Algorithms for approximate string matching.

Informationand Control, 64, 100-118.

[14] Wagner, R. A., & Fischer, M. J. (1974). The string-to-string

correctionproblem. Journal of the ACM, 21(1), 168-173.

[15] Wong, C. K., & Chandra, A. K. (1976). Bounds for the string editing

problem. Journal of the ACM, 23(1), 13-16.

[16] Wu, S., Manber, U., Myers, G.,& Miller, W. (1990). An O(NP) sequence

comparison algorithm. Information Processing Letters, 35(6), 317-323.

[17] http://www.expervision.com/testimonial-world-leading-and-champion-

ocr/annual-test-of-ocr-accuracy-by-us-department-of-energy-doe-

university-of-nevada-las-vegas-unlv

[18] http://vndocr.com [19] http://www.abbyy.com/finereader [20] http://www.nuance.com [21] http://vietocr.sourceforge.net

http://www.lrc.tnu.edu.vn

Số hóa bởi Trung tâm Học liệu – ĐHTN

Thái Nguyên, ngày.......tháng......năm 2015