ĐẠI HỌC CÔNG NGHỆ
ĐẠI HỌC QUỐC GIA HÀ NỘI

Nguyễn Đức Nam
Nghiên cứu, phát triển các công cụ xử lý tiếng Việt
trên UIMA
KHÓA LUẬN TỐT NGHIỆP HỆ CHÍNH QUY
Ngành: Công Nghệ Thông Tin
Hà Nội – 2010
i
ĐẠI HỌC CÔNG NGHỆ
ĐẠI HỌC QUỐC GIA HÀ NỘI

Tạ Việt Cường
Nghiên cứu phương pháp nhận dạng chữ viết tay trực
tuyến liền nét
KHÓA LUẬN TỐT NGHIỆP HỆ CHÍNH QUY
Ngành: Công Nghệ Thông Tin
Hà Nội – 2010
ĐẠI HỌC CÔNG NGHỆ
ĐẠI HỌC QUỐC GIA HÀ NỘI

Nguyễn Đức Nam
Nghiên cứu, phát triển các công cụ xử lý tiếng Việt
trên UIMA
KHÓA LUẬN TỐT NGHIỆP HỆ CHÍNH QUY
Ngành: Công Nghệ Thông Tin
GV hướng dẫn: TS. Phạm Bảo Sơn
Hà Nội – 2010
i
ĐẠI HỌC CÔNG NGHỆ

Danh sách các hình vẽ
6
Tóm tắt nội dung
Hiện nay hầu hết dữ liệu được đưa vào máy vi tính thông qua bàn phím. Nhưng
trong một số trường hợp, sử dụng chữ viết tay vẫn thích hợp hơn chẳng hạn như công
việc ghi chép bài vở trên lớp học. Trong hoàn cảnh đó, bài toán nhận dạng chữ viết tay
được nghiên cứu nhằm làm hoàn thiện thêm cách thức giao tiếp giữa người và máy.
Bài toán nhận dạng chữ viết tay đã được nghiên cứu và phát triển trong 40 năm
qua, và cũng đã đạt được nhiều kết quả đáng kể. Nhưng chỉ trong mấy năm gần đây
chúng ta mới phát triển được những ứng dụng nhận dạng chữ viết tay.
Trong khóa luận này, tôi xin giới thiệu một phương pháp tiếp cận trong bài toán
nhận dạng chữ viết tay dựa trên trích chọn đặc trưng theo biến đổi cosine rời rạc
(Discrete Cosine Transforms - DCT). Sau đó, sẽ xây dựng các mô hình Markov ẩn nhận
dạng các kí tự kết hợp với đặc trưng thu được từ biến đổi DCT. Cuối cùng, dựa trên
xác suất thu được từ mô hình Markov ẩn sẽ được sử dụng kết với phương pháp quy
hoạch động để có thể giải quyết hoàn toàn bài toán nhận dạng chữ viết tay.
7
Chương 1. Giới thiệu chung
1.1. Giới thiệu bài toán
Từ lâu chúng ta đã làm quen với cách sử dụng bàn phím để "nói chuyện" với máy
tính. Lí do không phải vì bàn phím là cách tốt nhất mà là vì bàn phím là cách duy nhất
để máy tính có thể hiểu một cách hiệu quả, bao gồm cả yếu tố chính xác và tốc độ, điều
mà chúng ta muốn nó hiểu được. Những nghiên cứu về nhận dạng chữ viết tay và nhận
dạng tiếng nói lại mở ra một hướng khác trong bài toán giao tiếp người và máy. Hiện
nay, các thuật toán hiệu quả cũng như các ứng dụng trên hai lĩnh vực này đang được
nghiên cứu để có thể thay thế được vai trò của bàn phím trong giao tiếp người máy.
Bài toán nhận dạng chữ viết tay là một trong hai vấn đề lớn của giao tiếp Người
Máy có nhiều ứng dụng thực tế. Một mặt là vì con người thích sử dụng chữ viết do tính
tự nhiên của nó hơn là khó bó trong khuôn khổ của bàn phím. Bên cạnh đó, đối với
những thiết bị cầm tay nhỏ gọn, chẳng hạn thiết bị điện tử cầm tay cá nhân (Personal

học máy được áp dụng. Chương sáu đưa ra một lời giải cho bài toán phân đoạn trong
nhận dạng chữ viết tay. Chương bảy sẽ thống kê các kết quả thực nghiệm trên các bộ
dữ liệu có được. Chương tám trình bày những kết luận chung và đưa ra những hướng
nghiên cứu tiếp theo dựa trên kết quả khóa luận đạt được.
9
Chương 2. Tổng quan về bài toán nhận dạng chữ viết tay
2.1. Giới thiệu
Bài toán nhận dạng chữ viết tay là một bài toán lớn, bao gồm nhiều vấn đề.
Thông thường các nghiên cứu chỉ tập trung giải quyết một hoặc một số mặt của bài
toán. Trong chương này tôi xin đề cập đến các vấn đề cơ bản trong bài toán nhận dạng
chữ viết tay.
2.2. Nhận dạng chữ viết tay trực tuyến và nhận dạng chữ viết tay gián tuyến
Có nhiều hướng tiếp cận nghiên cứu đối với bài toán nhận dạng chữ viết tay phụ
thuộc vào nhiều yếu tố như đã được đề cập đến phần trên. Nhưng ở mức độ chung
nhất, bài toán nhận dạng chữ viết tay có thể được chia thành hai phần chính là: nhận
dạng chữ viết tay trực tuyến và nhận dạng chữ viết tay gián tuyến.
Nhận dạng chữ viết tay gián tuyến được đặt ra để nhận dạng các văn bản viết tay
đã được hoàn thành. Với đặc trưng dữ liệu đầu vào là hình ảnh văn bản viết tay được
quét hoặc chụp lại. Sau đó, các thuật toán sẽ được xây dựng để nhận dạng văn bản dựa
trên các hình ảnh này. Các ứng dụng nhận dạng chữ viết tay gián tuyến thường không
quan tâm đến tối ưu thời gian mà chỉ yêu cầu độ chính xác của kết quả.
Nhận dạng chữ viết tay trực tuyến là bài toán nhận dạng song song với quá trình
chữ viết được thực hiện. Với đặc trưng dữ liệu đầu vào là dãy các điểm thu nhận được
trong quá trình con người thực hiện việc ghi chép dữ liệu. Nói chung, cần phải có các
thiết bị chuyên dụng như bảng điện tử hoặc màn hình cảm ứng để ghi lại quá trình di
chuyển của nét bút như điểm bắt đầu, điềm kết thúc, các điểm trên mặt phẳng mà nét
bút đi qua. Một cách hình thức, rõ ràng là có thể xây dựng được dữ liệu của bài toán
nhận dạng chữ viết tay gián tuyến từ dữ liệu trực tuyến. Nên các phương pháp của
nhận dạng gián tuyến hoàn toàn có thể áp dụng vào bài toán trực tuyến. Tuy nhiên, dữ
liệu trực tuyến còn cung cấp cho chúng ta các thông tin quý giá về nét bút và thứ tự các

thời gian liên tiếp giữa hai nét bút. Trong đa số trường hợp, việc sử dụng những thông
tin này là đủ để phân biệt các dòng với nhau và các từ trên cùng một dòng. Vì thế hầu
hết các hệ thống nhận dạng chữ viết tay trực tuyến đều tập trung vào giải quyết bài
toán nhận dạng từng từ riêng biệt hoặc nhận dạng từng kí tự.
11
Hình 2-1: Các mức độ khó khác nhau của bài toán phân đoạn kí tự trong một từ.
Ở trường hợp đơn giản nhất, mỗi kí tự được viết hoàn toàn trong một ô có kích
thước cho trước. bài toán phân đoạn các kí tự trở nên tầm thường và việc phải làm bây
giờ đơn giản hơn rất nhiều, chúng ta chỉ cần nhận dạng các kí tự trong mỗi ô. Trường
hợp đơn giản tiếp theo là khi giữa các kí tự trong một từ tách rời nhau, trong dữ liệu
trực tuyến có thể xác định bằng khoảng cách giữa các nét bút và thời gian bắt đầu các
nét bút. Hai trường hợp khó nhất của bài toàn phân đoạn các kí tự là khi một nét bút là
một phần hoặc toàn bộ của một hay nhiều kí tự liền nhau (liền nét - cursive
handwriting) và hỗn hợp giữa kiểu chữ viết liền nét và tách rời.
Một trong những vấn đề khác nảy sinh cho bài toàn phân đoạn kí tự viết tay trực
tuyến là các nét trễ. Bình thường, con người thường có thói quen viết từ trái sang phải,
nhưng những nét trễ là những nét không tuân theo quy luật đó, nó được thêm vào để
hoàn thành các kí tự nằm phía trước.
12
Hình 2-2: Minh họa về nét trễ. Ở đây là nét gạch ngang của chữ "t". Được thêm vào sau
khi hoàn thành chữ "h".
2.5. Các kết quả nghiên cứu hiện tại
Hiện nay các nghiên cứu giải bài toán nhận dạng chữ viết tay đã đạt được nhiều
thành công. Trong lĩnh vực nhận dạng kí tự, các thuật toán học máy và trích chọn đặc
trưng cho kết quả khá cao, Li và Yeung[15] với phương pháp Lân cận gần nhất sử
dụng so sánh mẫu (Nearest Neighbor using Elastic Matching) đạt được độ chính xác
87.1% trên tập các chữ tiếng Anh viết thường, Chan và Yeung[8] sử dụng các mô hình
cấu trúc (Mannually Designed Structural Models) đạt được tỉ lệ đúng là 97.4% trên
9300 mẫu . Tuy nhiên, ở bài toán nhận dạng từ kết quả đạt được vẫn hạn chế. Kết quả
tốt nhất đạt được có thể kể đến là Hu [6] với tỉ lệ chính xác là 94.5% trên 3,823 từ,

Phân đoạn
Phân đoạn
Giai đoạn huấn luyện
Giai đoạn nhận dạng
Hình 3:
3.2. Thu thập dữ liệu
Không giống như dữ liệu viết tay gián tuyến, chỉ cần một thao tác đơn giản là
chụp ảnh hoặc quét dữ liệu có thể ghi nhận để đưa vào xử lí. Thu thập dữ liệu của chữ
viết tay trực tuyến phải cần các thiết bị chuyên dụng có khả năng ghi nhận các trạng
thái của bút gồm có: pen down (bắt đầu một nét bút), pen up (kết thúc một nét bút) và
dãy các điểm mà bút di chuyển qua. Vì dữ liệu lưu trữ trong máy tính phải được rời rạc
hóa, nên dãy các điểm sẽ không được lấy liên tục theo thời gian, mà được lấy mẫu sau
những khoảng thời gian xác định và chúng ta có thể xem đường di chuyển của nét bút
là các đoạn thẳng nối hai điểm liên tiếp trên dãy các điểm mẫu lấy được.
Đơn giản nhất có thể dùng các chuyển động của con trỏ chuột của máy tính
nhưng dữ liệu thu được sẽ không chính xác do con người không có thói quen dùng
chuột để viết nên các mẫu dữ liệu thu được sẽ khác nhau rất nhiều, khó có thể sự dụng
cho bài toán huấn luyện và nhận dạng. Cách lấy dữ liệu thông thường là sử dụng một
bảng điện tử và bút chuyên dụng kèm theo có khả năng ghi nhận vị trí các điểm di
chuyển của bút từ 80 đến 200 lần một giây. Số điểm lấy trong một giây càng nhiều thì
đường thể hiện của nét bút càng chi tiết, nhưng cũng đồng thời làm tăng khả năng xuất
hiện nhiễu trong dữ liệu thu được. Các thiết bị khác như PDA thì sử dụng các màn hình
cảm ứng để ghi nhận di chuyển của bút.
Hình 3-4: Thiết bị CrossPad, dùng trong thu nhận dữ liệu viết tay trực tuyến
16
Dữ liệu huấn luyện
Tiền xử lý dữ liệu
Huấn luyện
Trích chọn đặc trưng
Kết quả huấn luyện

xiên lên hay xiên xuống khi viết từ trái sang phải. Nếu bỏ qua những yêu cầu đấy, để
xác định được vị trí các miền trong một mẫu viết tay chúng ta sẽ áp dụng một phương
pháp tương tự trong xử lí gián tuyến.
Ở trong xử lí gián tuyến, để xác định được các miền này, chúng ta sẽ khảo sát sự
phân bố của lượng mực theo chiều của trục y. Miền giữa luôn là miền có lượng phân
bố lớn nhất của cả hàng. Bằng cách chọn ra một ngưỡng thích hợp, chúng ta sẽ xác
định được vị trí phải tìm. Trong xử lí trực tuyến, quá trình này có thể mô phỏng bằng
cách chia trục y thành những đoạn ∆y thích hợp. Với mỗi đoạn ∆y, tính chiều dài của
mẫu thuộc đoạn đấy. Từ đó chúng ta sẽ xác định được miền tập trung nhiều lượng mực
nhất là miền giữa [6].
18
Hình 3-6: Cơ sở để xác định các miền của chữ viết
Sau khi xác định được miền giữa, chiều cao của mẫu chữ viết tay sẽ được thay
đổi theo một tỉ lệ thích hợp sao cho miền giữa có chiều cao cố định. Việc xác định góc
độ xiên lên hoặc xiên xuống của mẫu chữ khi được viết từ trái sang phải có thể được
thực hiện bằng cách sử dụng biến đổi Hough [11].
Một vấn đề khác của chuẩn hóa kích thước là về độ nghiêng của chữ. Đối với hệ
thống nhận dạng chữ viết tay phụ thuộc người viết thì vần đế này không quan trọng
lắm vì độ nghiêng sẽ thay đổi không đáng kể. Nhưng đối với các hệ thống không phụ
thuộc người viết thì độ nghiêng ở các mẫu viết tay sẽ rất khác biệt. Để loại bỏ điều này
chúng ta sẽ tìm góc trung bình của các nét lên xuống và lấy đó làm góc nghiêng của
mẫu chữ viết [7].
3.3.2. Định vị lại mẫu
Sau khi chuẩn hóa về chiều cao của mẫu chữ viết, các điểm sẽ lấy lại theo vị trí
tương đối với một điểm mốc nào đấy. Có nhiều cách định vị lại như lấy theo vị trí
tương đối so với điểm thấp nhất và điểm trái nhất, hoặc là lấy theo vị trí tương đối của
điểm bắt đầu nét bút. Ở đây, chúng ta chọn cách định vị lại mẫu theo trục x là điểm trái
nhất và theo trục y là đường cơ bản.
3.3.3. Lấy lại các điểm của mẫu
Các thiết bị dùng để thu thập dữ liệu đầu vào cho bài toán chữ viết tay sẽ lấy các

nhiều khả năng tìm được phân đoạn đúng nhất. Các phương pháp đã được sử dụng là
sử dụng mô hình Markov ẩn ([10], [6]), hoặc dựa trên thuật toán Quy hoạch động
([16]). Với phương pháp sử dụng mô hình Markov ẩn, thuật toán Viterbi[9] nếu được
xem xét cụ thể thì vẫn là một phương pháp dựa trên quy hoạch động để tính xác suất
tối ưu, hơn nữa khả năng xử lí của thuật toán Viterbi với các nét trễ gặp khá nhiều khó
20
khăn. Vì thế, trong khóa luận sẽ sử dụng thuật toán quy hoạch động phân đoạn tối ưu
theo từng bước để tìm ra cách lời giải tối ưu nhất (được trình bày ở chương 5).
3.5. Trích chọn đặc trưng
Trong bài toán nhận dạng chữ viết tay trực tuyến dữ liệu được thao tác là dãy các
điểm thì cách trích chọn đặc trưng trực quan nhất là dựa trên sự thay đổi về quan hệ
hình học giữa hai điểm hoặc dãy các điểm liên tiếp ([15], [5]) .Các quan hệ này thường
là sự thay đổi theo các chiều tọa độ, hoặc là sự thay đổi về góc tiếp tuyến. Nhưng điểm
yếu của cách trích chọn này nằm ở tính cục bộ của nó, chỉ xét đến quan hệ hạn chế
giữa các điểm, không thể thể hiện được đặc trưng của toàn bộ nét bút. Trong những
cách tiếp cận khác mức cao hơn, đặc trưng được thể hiện bằng hình dạng của các nét
chẳng hạn các nét lên, nét xuống, nét nối thành hình tròn [12].
Ở khóa luận này, tôi sử dụng phương pháp trích trọn đặc trưng dựa trên biến đổi
DCT của dãy tọa độ các điểm mẫu. Biến đổi DCT là biến thể của biến đổi Fourier đưa
dãy tín hiệu rời rạc về dải tầng của phổ của nó. Nó có khả năng tập trung năng lượng
cao vào một số hệ số, và trong phần lớn trường hợp các hệ số này sẽ thể hiện đặc trưng
cơ bản của nét bút [19].
3.6. Phương pháp học máy để nhận dạng kí tự viết tay.
Bước tiếp theo trong bài toán nhận dạng chữ viết tay, là nhận dạng từng kí tự
riêng biệt sau khi được tách ra. Đối với bài toán nhận dạng kí tự có khá nhiều phương
pháp học máy để giải quyết vấn đề này và đạt được nhiều kết quả khác nhau. Tùy vào
từng cách tiếp cận mà chúng ta có các thuật toán trích chọn đặc trưng thích hợp để đạt
được kết quả như mong muốn. Ở đây tôi xin giới thiệu phương pháp sử dụng mô hình
Markov ẩn được sử dụng trong khóa luận.
3.6.1. Phương pháp sử dụng mô hình markov ẩn

22
Chương 4. Trích chọn đặc trưng dựa trên biến đổi cosine rời rạc
4.1. Giới thiệu
Biến đổi cosine rời rạc (Discrete Cosine Transforms - DCT) có thể xem là một
biến thể của biến đổi Fourier rời rạc (Discrete Cosine Transforms - DFT). Trong khi biến
đổi DFT sẽ sử dụng cả hai hàm số sin và cosine với các tần số khác nhau để thể hiện
dãy tín hiệu rời rạc thì biến đổi DCT sẽ chỉ sử dụng các hàm số cosine. Tính chất quan
trọng của biến đổi DCT giúp nó có những ứng dụng quan trọng trong nén mất mát dữ
liệu và nhận dạng là khả năng tập trung năng lượng vào những hệ số nhất định [19]. Cụ
thể là những hệ số ứng với các hàm số consine có tần số thấp. Còn những hệ số của
hàm cosine ở tần số cao hơn có thể được xem như là nhiễu, và sẽ được loại bỏ. Vì vậy,
có thể xem như đặc trưng của mẫu chữ viết, khi trích chọn đặc trưng dựa trên biến đổi
DCT là các hệ số của hàm cosine ứng với tần số thấp.
Có tất cả 8 loại biến đổi DCT cơ bản, trong đó có nhiều ứng dụng nhất là biến
đổi loại II DCT, thường được gọi tắt là DCT. Chúng ta sẽ sử dụng biến đổi II DCT này
cho bài toán trích chọn đặc trưng từ dãy các điểm của mẫu chữ viết tay trực tuyến thu
được sau quá trình tiền xử lí.
Phần tiếp theo sẽ đề cập đến cơ sở toán học của phương pháp sử dụng biến đổi
DCT và cách áp dụng biến đổi DCT vào bài toán trích chọn đặc trưng.
4.2. Cơ sở toán học
Giả sử tín hiện đầu vào có biểu diễn rời rạc là , , . Chúng ta sẽ tìm biễu diễn của một
đường cong xấp xỉ nào đó đi qua các điểm (0, ) (1, ) (N-1, ). Cụ thể, trong biến đổi
DCT đường cong xấp xỉ C này sẽ có dạng là tổng các hàm cosine:
C =
Trong đó = (n + ), k = 0, 1, , N-1
23
Hình 4-7: Xấp xỉ dãy tín hiệu N phần tử bằng biến đổi DCT.
Giá trị sẽ thể hiện độ lớn của tần số consine k, và được tính qua các giá trị , , theo
công thức
Khi k thay đổi từ 0 đến N-1 sẽ khiến cho hệ số góc của hàm cosine cơ bản sẽ tăng, hay