BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC NHA TRANG
KHOA CÔNG NGHỆ THÔNG TIN

HUỲNH MINH TRÍ

TÌM HIỂU VÀ NÂNG CAO HIỆU QUẢ
NHẬN DẠNG CHỮ VIẾT TAY RỜI RẠC
DỰA TRÊN CÁC KỸ THUẬT LẤY ĐẶC TRƯNG
VÀ PHÁT TRIỂN ỨNG DỤNG

ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC
Ngành Công nghệ thông tin
CÁN BỘ HƯỚNG DẪN:
ThS. Nguyễn Đình Cường
Nha Trang – 2014
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN
CHƯƠNG 2. CÁC KỸ THUẬT RÚT TRÍCH ĐẶC TRƯNG TRONG BÀI TOÁN
NHẬN DẠNG CHỮ VIẾT TAY 33
2.1. Ảnh hưởng giai đoạn rút trích đặc trưng đối với hiệu quả bài toán 33
2.2. Một số kỹ thuật rút trích đặc trưng đang được sử dụng 33
2.2.1. Kỹ thuật Zoning 33
2.2.2. Kỹ thuật Coutour profile 34
2.2.3. Kỹ thuật Projection 35
2.2.4. Kỹ thuật wavelet Haar 35
2.2.5. Kỹ thuật Diagonal based 37
2.2.6. Kỹ thuật Twelve Direction 40
2.2.7. Kỹ thuật tiếp cận cấu trúc 41
2.2.8. Kỹ thuật Hotspot 43
2.2.9. Kỹ thuật 40-Point 45
2.2.10. Kỹ thuật Background Directional Distribution 47
2

2.2.11. Kỹ thuật Shadow 48
2.2.12. Kỹ thuật Chain code histogram 50
2.2.13. Kỹ thuật Intersection 51
2.2.14. Kỹ thuật Straight line fitting 52
2.3. Giới thiệu kỹ thuật rút trích đặc trưng mới 53
2.4. Vấn đề cải tiến giai đoạn rút trích đặc trưng 57
2.4.1. Xu hướng cải tiến giai đoạn rút trích đặc trưng 57
2.4.2. Những cải tiến của một số kỹ thuật đã nêu 58
CHƯƠNG 3. MÔ HÌNH SVM (SUPPORT VECTOR MACHINE) 60
3.1. Giới thiệu mô hình SVM 60
3.2. Cơ sở toán học của mô hình SVM 62
3.2.1. Bài toán phân lớp nhị phân hoàn toàn 62
3.2.2. Bài toán phân lớp nhị phân không hoàn toàn 66
3.2.3. Vấn đề phân lớp đa lớp sử dụng mô hình SVM 68

6.2. Hướng phát triển của đề tài 136
TÀI LIỆU THAM KHẢO 138 4

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

Từ viết tắt

Giải thích
SVM Support Vector Machine

5

DANH MỤC CÁC BẢNG

Bảng 2.1. Cách phân giá trị gradient vào các bin 41
Bảng 4.1. So sánh ưu nhược điểm của một số kỹ thuật rút trích đặc trưng 113
Bảng 5.1. Mô tả vật lý của lược đồ quan hệ Subject 121
Bảng 5.2. Mô tả vật lý của lược đồ quan hệ Record 121
Bảng 5.3. Mô tả vật lý của lược đồ quan hệ Student 121
Bảng 5.4. Mô tả vật lý của lược đồ quan hệ RecordDetail 122
Bảng 5.5. Kết quả chạy ứng dụng trên một số bảng điểm 132

6

DANH MỤC CÁC HÌNH

Hình 1.1. Cách xét góc nghiêng của ký tự 23

Hình 5.3. Minh họa một ô điểm đã được cắt ra 127
Hình 5.4. Giao diện màn hình sử dụng 130
Hình 5.5. Giao diện màn hình cập nhật cơ sở dữ liệu 131
Hình 5.6. Giao diện xem bảng điểm đã có trong cơ sở dữ liệu 132
Hình 5.7. Điểm số ghi lọt ra ngoài khung điểm 133
Hình 5.8. Điểm được chỉnh sửa ngay trên bảng điểm 134 8

DANH MỤC CÁC SƠ ĐỒ, BIỂU ĐỒ

Sơ đồ 1.1. Cấu trúc chung của một hệ thống nhận dạng 16
Sơ đồ 1.2. Vị trí của giai đoạn huấn luyện 31
Sơ đồ 2.1. Thuật toán Diagonal based 39
Sơ đồ 2.2. Thuật toán Hotspot 44
Sơ đồ 4.1. Quá trình biên dịch bộ công cụ CSharp-2.6 77
Sơ đồ 5.1. Cấu trúc hệ thống nhận dạng bảng điểm sinh viên 116
Sơ đồ 5.2. Mô hình quan niệm dữ liệu của hệ thống 120
Sơ đồ 5.3. Cấu trúc bộ xử lý bảng điểm 125
Biểu đồ 4.1. Kết quả trên MyCharacter của Diagonal based 84
Biểu đồ 4.2. Kết quả trên MNIST của Diagonal based 85
Biểu đồ 4.3. Thí nghiệm Twelve Direction trên MyCharacter và MNIST 87
Biểu đồ 4.4. Tìm xương ký tự đối với Twelve Direction 88
Biểu đồ 4.5. Kích thước ma trận chuẩn hóa đối với Twelve Direction 90
Biểu đồ 4.6. Việc lấy trung bình đối với Twelve Direction 91
Biểu đồ 4.7. Kết quả trên MyCharacter và MNIST của Hotspot 93
Biểu đồ 4.8. Việc tìm xương ký tự đối với Hotspot 94
Biểu đồ 4.9. Kết quả trên MyCharacter và MNIST của 40-Point 96
Biểu đồ 4.10. Việc tìm xương ký tự đối với 40-Point 97

mới. Bên cạnh đó, đồ án cũng trình bày và nắm bắt nội dung của mô hình SVM
(Support Vector Machine) – một trong những mô hình nhận dạng đang được sử
dụng phổ biến hiện nay. Sau đó, sử dụng kết quả của việc cải tiến để cài đặt ứng
dụng đọc bảng điểm sinh viên trường Đại học Nha Trang, đây là một ứng dụng có
tính chất bước đệm nhằm giúp đơn giản hóa công tác quản lý đào tạo của phòng
Đào tạo, trường Đại học Nha Trang.
Em cũng xin gửi lời biết ơn chân thành và sâu sắc nhất đến Thầy Nguyễn
Đình Cường, giảng viên bộ môn Kỹ thuật phần mềm, đã tận tình hướng dẫn và giúp
đỡ em trong suốt quá trình hoàn thành đồ án tốt nghiệp này.
11

CHƯƠNG 1
TỔNG QUAN VỀ BÀI TOÁN NHẬN DẠNG CHỮ VIẾT TAY
1.1. Giới thiệu về bài toán nhận dạng chữ viết tay
Kể từ khi chiếc máy tính đầu tiên ENIAC được phát minh vào năm 1946 cho
đến nay, lịch sử phát triển của ngành Công nghệ thông tin đã có nhiều bước tiến
nhảy vọt cả về mặt lý thuyết lẫn mặt ứng dụng. Đi cùng với sự phát triển với tốc độ
bùng nổ của khối lượng thông tin kinh tế - xã hội thì số lượng nhà nghiên cứu cũng
như lĩnh vực chuyên sâu hẹp của tin học tăng lên mạnh mẽ. Song song với vấn đề
đó thì yêu cầu mới trong quá trình lưu trữ dữ liệu và giao tiếp liên tục được phát
sinh, thể hiện mức độ tương tác liên tục giữa người dùng với máy tính. Một trong
những yêu cầu được đặt ra là làm thế nào để có được các sản phẩm phần mềm có
khả năng nhận dạng được các ký tự viết tay của một ngôn ngữ nào đó. Hai mục tiêu
chính yếu của các loại phần mềm ứng dụng kiểu này là: Một là, phục vụ cho quá
trình số hóa dữ liệu (nhất là các bản thảo chép tay có giá trị), phục vụ mục đích xử
lý thông tin tự động sau quá trình số hóa; Hai là, phục vụ cho nhu cầu tương tác cho
người dùng trên các thiết bị khác nhau, đặc biệt là cho người phi bản ngữ có thiết bị
di động (chẳng hạn người không biết tiếng Nhật có thể nhập các ký tự tiếng Nhật
khi tra cứu nhanh trên Internet).
Tuy gần đây mới ra đời các sản phẩm loại trên, nhưng nguồn gốc về nhận

1.2. Sơ lược về một số nghiên cứu trước đây
Trong suốt những năm qua, công tác nghiên cứu lý thuyết và ứng dụng trên
bài toán nhận dạng chữ viết tay nói riêng và chữ viết nói chung đã và đang phát
triển rất mạnh. Hàng loạt các bài báo, các đồ án tốt nghiệp trong lĩnh vực này được
giới thiệu. Dưới đây là một vài nghiên cứu trong số đó.
Phạm Anh Phương, trong nghiên cứu ở [3] đã giới thiệu một số kỹ thuật lấy
đặc trưng đơn giản nhưng hiệu quả cho bài toán nhận dạng chữ viết tay. Các kỹ
thuật được giới thiệu gồm kỹ thuật Zoning (trọng số vùng), Projection (hình chiếu),
Contour profile (trích chọn chu tuyến) và wavelet Haar, được thực hiện trên bộ dữ
13

liệu MNIST. Kết quả nghiên cứu cho thấy kỹ thuật Zoning và wavelet Haar cho độ
chính xác cao hơn. Hai kỹ thuật còn lại độ chính xác thấp hơn đôi chút song do số
chiều của vector đặc trưng ít hơn nên tốc độ xử lý được cải thiện đáng kể.
Himavathi S. và các đồng nghiệp đã đưa ra một kỹ thuật mới trong việc rút
trích đặc trưng ký tự trong nghiên cứu [18], đó là kỹ thuật Diagonal based. Kỹ thuật
này được tiến hành trên bộ dữ liệu chữ viết tiếng Anh gồm 26 ký tự. Kỹ thuật của
Himavathi S. và các đồng nghiệp dựa trên đặc tính về lượng của điểm ảnh và số
lượng phân bố của chúng trên các đường chéo trong mỗi vùng. Ngoài ra, các tác giả
còn nâng cao hiệu quả bằng việc lấy thêm giá trị trung bình vừa tìm được giữa các
vùng trong từng dòng và từng cột. Thí nghiệm được thực hiện trên bộ nhận dạng
bằng mạng nơ ron nhân tạo đa lớp lan truyền ngược. Hiệu quả thu được là rất khả
quan với độ chính xác 97.8% cho tập vector đặc trưng có 54 chiều và 98.5% cho tập
vector đặc trưng có 69 chiều.
Das S.K. và cộng sự thì giới thiệu một kỹ thuật khác, trong đó, số lượng
điểm ảnh màu đen trong một vùng cũng được sử dụng để lấy đặc trưng [11], gọi là
kỹ thuật 40-Point. Kỹ thuật 40-Point cũng được tiến hành trên bộ dữ liệu chữ viết
tay tiếng Anh (780 mẫu huấn luyện và 260 mẫu kiểm tra), dùng mạng nơ ron nhân
tạo đa lớp lan truyền ngược. Độ chính xác trong nghiên cứu đạt được là 83.84%.
Trong nghiên cứu ở [23], Schomaker L. và cộng sự đã đề xuất kỹ thuật

dụng mạng nơ ron để phân lớp mà dùng độ tương tự (similarity) giữa mẫu cần phân
lớp với các khuôn mẫu thu được từ giá trị trung bình các vector trong cùng lớp. Dữ
liệu được sử dụng bao gồm 500 mẫu huấn luyện và 200 mẫu kiểm tra, độ chính xác
đạt được là 88.29%.
Cũng lấy giá trị đặc trưng từ gradient của điểm ảnh, nhưng nghiên cứu [13]
của Dubey P. và Sinthupinyo W. lại chia ma trận điểm ảnh ra thành 16 vùng và lấy
histogram giá trị bin của gradient. Trước đó, tất cả các giá trị gradient đã được phân
15

vào 6 bin trải rộng từ 0 đến 2π, mỗi khoảng tương ứng với
3

. Kỹ thuật này thực
hiện trên 50750 mẫu ký tự tiếng Thái và tiếng Anh, sử dụng thuật toán phân cụm K-
Mean và đạt được độ chính xác trung bình là 95%.
Cavalcanti G.D.C và các đồng nghiệp đã kết hợp các kỹ thuật lấy đặc trưng
khác nhau để tăng tỉ lệ nhận dạng lên [10]. Sáu kỹ thuật được kết hợp bao gồm kỹ
thuật đặc tính cấu trúc (structural characteristics), kỹ thuật bản đồ cạnh (modified
edge maps), kỹ thuật hình chiếu (image projections), kỹ thuật đa vùng (multi
zoning), kỹ thuật đo độ lõm (concavities measurement) và kỹ thuật gradient định
hướng (MAT-based gradient directional features). Nghiên cứu sử dụng mạng nơ ron
lan truyền ngược và đã đạt được độ chính xác cao nhất, tính đến thời điểm hiện tại
trên bộ dữ liệu MNIST, là 99.68%.
Arora S. và các cộng sự cũng nâng cao hiệu quả của hệ thống nhận dạng theo
hướng kết hợp các kỹ thuật lấy đặc trưng khác nhau [6]. Bằng việc sử dụng bốn kỹ
thuật là Shadow (hình chiếu), Chain code histogram (histogram chuỗi mã định
hướng), Intersection (giao điểm) và Straight line fitting (đường thẳng xấp xỉ) và lần
lượt cho các tập vector đặc trưng riêng đi qua từng mạng nơ ron lan truyền ngược
riêng biệt, nghiên cứu đã đạt được độ chính xác cuối cùng là 92.8% trên bộ dữ liệu
chữ viết tay Devnagari. Bộ dữ liệu này gồm có 3332 mẫu huấn luyện và 1568 mẫu

huấn luyện
Cơ sở dữ liệu
nhận dạng
Tập dữ liệu
nhận dạng
Kết quả
nhận dạng
Tiền xử lý Trích chọn
đặc trưng
Huấn luyện
Nhận dạng


















17

 Kết quả nhận dạng: thu nhận kết quả có được từ bộ Nhận dạng và đưa vào
lưu trữ ở dạng văn bản, hiển thị lên màn hình,…
1.3.2. Các giai đoạn thực hiện
Bởi vì hiện nay, bài toán nhận dạng ký tự đã và đang phát triển thành nhiều
bài toán nhỏ khác nhau dẫn đến sử dụng một loạt các thuật toán khác nhau trong
mỗi giai đoạn tiến hành, do vậy ở đây chỉ tập trung đến những nội dung liên quan
đến nhận dạng chữ viết tay rời rạc, tức là mỗi ký tự viết tay được xử lý riêng biệt.
a. Giai đoạn tiền xử lý
Tiền xử lý là một giai đoạn cực kỳ quan trọng trong quá trình nhận dạng một
ký tự, kể cả đó là nhận dạng ký tự in máy hay chữ viết tay. Mục tiêu chính của giai
đoạn tiền xử lý là:
 Giảm đi các yếu tố có thể ảnh hưởng đến đường nét của các ký tự trong
ảnh như các điểm muối tiêu, các vệt mờ/đậm không liên quan đến ký tự, xuất hiện
trong quá trình thu thập ảnh do tình trạng vật lý hiện tại của thiết bị (khả năng quét
không tốt, bề mặt máy quét không tốt, có vết trầy xước), do thao tác của người quét
thủ công (không để bản giấy phẳng, để nếp nhăn,…),…
 Giảm đi sự phức tạp cho quá trình nhận dạng thông qua việc nhị phân ảnh.
 Đưa ảnh ký tự về kích thước quy chuẩn để phục vụ cho quá trình trích
chọn đặc trưng.
Bên dưới đây là một số công đoạn chính của giai đoạn tiền xử lý ảnh ký tự.

Lọc mịn ảnh
Đối với một ảnh bất kỳ, không riêng ảnh ký tự, khi lọc người ta thường sử
dụng hai bộ lọc rất quan trọng là lọc thông thấp (Low – pass filter) [20] và lọc thông
cao (High – pass filter) [19]. Trong đấy:
 Lọc thông thấp (Low-pass filter, còn gọi là Blurring filter hay Smoothing
filter) là bộ lọc có khả năng làm cho các phần tử ảnh trở nên trơn hơn, tạo cho mắt
19

ta có cảm giác các điểm ảnh li ti có khả năng “tan đều” trong không gian ảnh, đặc

9
1
9
1
9
1
9
1
9
1
9
1
9
1
1
L
(1.1)
Song nếu chúng ta không muốn bộ lọc khiến các điểm ảnh bị “tan ra” quá, ta
có thể sử dụng bộ lọc sau đây:












trung bình thì tốt hơn.

Nhị phân ảnh
Mặc dù tính đến thời điểm hiện tại việc xử lý ảnh màu hoặc ảnh xám ký tự
đang được quan tâm nghiên cứu do bảo toàn được nhiều tính chất của ảnh, nhất là
20

đặc điểm về việc biến thiên mức năng lượng, song các thuật toán nhận dạng hiện
nay hầu như đều xử lý trên ảnh nhị phân (ảnh chỉ có hai loại điểm ảnh là hoàn toàn
đen hoặc hoàn toàn trắng). Hai lý do có thể kể đến cho vấn đề này là:
 Việc nghiên cứu các thuật toán áp dụng trên ảnh màu bao giờ cũng tốn
nhiều chi phí (thời gian, độ phức tạp) hơn so với ảnh nhị phân. Để đơn giản nhất ta
xét ví dụ về ảnh màu dùng hệ màu RGB thì phải tiến hành trên ít nhất ba ma trận
điểm ảnh tương ứng với ba gam màu red – green – blue.
 Một vài thuật toán chỉ có thể áp dụng trên ảnh nhị phân, đặc biệt là các
thuật toán tính đến thời điểm hiện tại.
Cách thức để nhị phân ảnh phổ biến nhất là dựa trên dữ liệu hiện thời của ảnh
(đặc biệt là dữ liệu về Histogram) để đưa ra một ngưỡng nhị phân, sau đó xét trên
toàn bộ các điểm ảnh, điểm ảnh nào có giá trị nhỏ hơn ngưỡng nhị phân thì quy về
pixel 0, điểm ảnh nào có giá trị lớn hơn ngưỡng nhị phân thì quy về pixel 1.
Sau đây là một số kỹ thuật nhị phân đang được sử dụng, tham khảo từ [16]:
 Kỹ thuật ngưỡng toàn cục giản đơn (Global fixed threshold): đây là kỹ
thuật nhị phân đơn giản nhất, theo đó b
i
= 1 nếu x
i
>= 0.5 và b
i
= 0 nếu x
i

Lk


1
) để xem k có phải là mức xám tốt
nhất để phân ngưỡng hay không. Nhiệm vụ của chúng ta là phân các điểm ảnh ra
thành hai lớp là lớp C
0
(điểm ảnh 0) và lớp C
1
(điểm ảnh 1). Ta có:
21 
 
)7.1(
)(1
)(
)|(
)6.1(
)(
)(
)|(
)5.1()(1)(
)4.1()()(
1
1
1
1

i
k
i
L
ki
i
k
i
i
k
k
ip
Ciyprobabiliti
k
k
ip
Ciyprobabiliti
kpCyprobabilit
kpCyprobabilit












i
iT
ipL


Nên theo kết quả của Nobuyuki Otsu [22] thì mức xám tốt nhất k
optimal
để
phân ngưỡng là mức xám thỏa mãn biểu thức:


 
)11.1(
)(1)(
)()(
max)(max)(
2
1
2
1
2










lặp lại lần lượt từ bước số 2 đến bước số 4 cho các ô có kích thước lớn hơn
(
hh 44

,
hh 88

,
hh 1616

,…).
Bước 5: Mỗi ô
hh 22

sẽ được nhị phân bởi ngưỡng Otsu cuối cùng tìm
được qua quá trình trên.
Bước 6: Ngưỡng t
i
cho mỗi điểm ảnh sẽ được chuẩn hóa bởi nội suy song
tuyến tính từ các ngưỡng có được trong bước 5.
Bước 7: Mỗi điểm ảnh x
i
của ảnh gốc sẽ được so sánh với ngưỡng tương ứng
t
i
để từ đó chuẩn hóa thành điểm ảnh nhị phân b
i
.
 Kỹ thuật Sauvola – Niblack: trong kỹ thuật này ta cũng chia toàn bộ ảnh ra
thành các ô có kích thước




(1.12), trong
đó
5.0

k
và
255
128
R .
Để giảm công sức tính toán thì ta chỉ tính
i

của điểm ảnh trung tâm ô, với
các điểm ảnh khác cũng thuộc ô đó ta sẽ tính
i

từ phép nội suy song tuyến.
23


Chỉnh nghiêng
Đối với một ảnh ký tự, sự nghiêng của một ký tự trong ảnh có thể ảnh hưởng
rất lớn đến kết quả của toàn bộ quá trình nhận dạng, do đó một trong những bài toán
con của bài toán nhận dạng chữ viết tay là bài toán phát hiện và chỉnh nghiêng cho
các ký tự trong ảnh – một bài toán mà đến nay vẫn còn đang được nghiên cứu rất
mạnh mẽ.
Nguyên nhân chính của việc ký tự bị nghiêng có thể do khi đưa ảnh vào máy