
Nhận dạng là bài toán xuất hiện cách đây khá lâu và vẫn luôn thu
hút được nhiều sự quan tâm, nghiên cứu. Đặc biệt là trong vài thập niên gần
đây, do sự thúc đẩy của quá trình tin học hoá trong mọi lĩnh vực, bài toán nhận
dạng không còn dừng lại ở mức độ nghiên cứu nữa mà nó trở thành một lĩnh
vực để áp dụng vào thực tế. Các bài toán nhận dạng đang được ứng dụng
trong thực tế hiện nay tập trung vào nhận dạng mẫu, nhận dạng tiếng nói và
nhận dạng chữ. Trong số này, nhận dạng chữ là bài toán được quan tâm rất
nhiều và cũng đã đạt được nhiều thành tựu rực rỡ. Các ứng dụng có ý nghĩa
thực tế lớn có thể kể đến như: nhận dạng chữ in dùng trong quá trình sao lưu
sách báo trong thư viện, nhận dạng chữ viết tay dùng trong việc phân loại thư
ở bưu điện, thanh toán tiền trong nhà băng và lập thư viện sách cho người mù
(ứng dụng này có nghĩa: scan sách bình thường, sau đó cho máy tính nhận dạng
và trả về dạng tài liệu mà người mù có thể đọc được).
Xuất phát từ yêu cầu thực tế, đang rất cần có nhưng nghiên cứu về vấn đề
này. Chính vì vậy tôi đã chọn đề tài nhận dạng ký tự viết tay làm đồ án tốt
nghiệp với mong muốn phần nào áp dụng vào bài toán thực tế.
Bài toán đã đặt ra phải giải quyết được những yêu cầu sau:
 Nhận dạng được các ký tự từ ảnh đầu vào
 Trích chọn được các đặc trưng của ảnh
 Tiến hành nhận dạng với thuật toán Markov ẩn
Với nhưng yêu cầu đã đặt ra ở trên, cấu trúc của khóa luận sẽ bao gồm
những nội dung sau đây:
  
Giới thiệu về bài toán nhận dạng chữ viết tay, tình hình
nghiên cứu trong và ngoài nước, quy trình chung để giải quyết bài
toán và các phương pháp điển hình trong việc huấn luyện nhận
dạng, phạm vi của đề tài.
  !"#$%&''(
)'%
Trình bày lý thuyết về lọc nhiễu, nhị phân hóa, chuẩn hóa

EWW^'OV\_^%U
 OV\`abbcadbe
- Nhận dạng chữ được biết đến từ năm 1900, khi nhà khoa học người
Nga Tyuring phát triển một phương tiện trợ giúp cho những người mù.
- Các sản phẩm nhận dạng chữ thương mại có từ những năm1950, khi
máy tính lần đầu tiên được giới thiệu tính năng mới về nhập và lưu trữ
dữ liệu hai chiều bằng cây bút viết trên một tấm bảng cảm ứng .Công
nghệ mới này cho phép các nhà nghiên cứu làm việc trên các bài toán
nhận dạng chữ viết tay on-line.
- Mô hình nhận dạng chữ viết được đề xuất từ năm 1951 do phát minh
của M. Sheppard được gọi là GISMO, một robot đọc-viết.
- Năm 1954, máy nhận dạng chữ đầu tiên đã được phát triển bởi J.
Rainbow dùng để đọc chữ in hoa nhưng rất chậm.
- Năm 1967 ,Công ty IBM đã thương mại hóa hệ thống nhận dạng chữ.
 OV\`adbcaabe
- Với sự phát triển của các thiết bị phần cứng máy tính và các thiết bị thu
thu nhận dữ liệu, các phương pháp luận nhận dạng đã được phát triển
trong giai đoạn trước đã có được môi trường lý tưởng để triển khai các
ứng dụng nhận dạng chữ.
- Các hướng tiếp cận theo cấu trúc và đối sánh được áp dụng trong nhiều
hệ thống nhận dạng chữ.
- Trong giai đoạn này, các hướng nghiên cứu chỉ tập trung vào các kỹ
thuật nhận dạng hình dáng chứ chưa áp dụng cho thông tin ngữ nghĩa.
Điều này dẫn đến sự hạn chế về hiệu suất nhận dạng, không hiệu quả
3
trong nhiều ứng dụng thực tế.
 OV\*`/faabOe
- Các hệ thống nhận dạng thời gian thực được chú trọng trong giai đoạn
này.
- Các kỹ thuật nhận dạng kết hợp với các phương pháp luận trong lĩnh

EW^'_'Z"iTV^
Nhận dạng chữ viết tay thường bao gồm năm giai đoạn: tiền xử lý
(preprocessing), tách chữ (segmentation), trích chọn đặc trưng(representation),
huấn luyện và nhận dạng (training and recognition), hậu xử lý (postprocessing).
- Tiền xử lý: giảm nhiễu cho các lỗi trong quá trình quét ảnh, hoạt động
viết của con người, chuẩn hóa dữ liệu và nén dữ liệu.
- Tách chữ: chia nhỏ văn bản thành những thành phần nhỏ hơn ,tách các
từ trong câu hay các kí tự trong từ.
- Biểu diễn, rút trích đặc điểm: giai đoạn đóng vai trò quan trọng nhất
trong nhận dạng chữ viết tay. Để tránh những phức tạp của chữ viết tay
cũng như tăng cường độ chính xác, ta cần phải biểu diễn thông tin chữ
viết dưới những dạng đặc biệt hơn và cô đọng hơn, rút trích các đặc
điểm riêng nhằm phân biệt các ký tự khác nhau.
- Huấn luyện và nhận dạng: phương pháp điển hình so trùng mẫu, dùng
thống kê, mạng nơ-ron ,PjQPO%#Vk ,trí tuệ nhân tạo hay dùng
phương pháp kết hợp các phương pháp trên.
5
- Hậu xử lý: sử dụng các thông tin về ngữ cảnh để giúp tăng cường độ
chính xác, dùng từ điển dữ liệu.
- Mô tả quá trình trong hệ thống nhận dạng .Sơ đồ gồm hai phần chính:
đường màu đỏ mô tả các bước để huấn luyện cho máy học, đường màu
xanh mô tả các bước trong quá trình nhận dạng:
Ban đầu các hình ảnh này đi qua giai đoạn chuyển ảnh về dạng ảnh nhị
phân (giai đoạn tiền xử lý). Ảnh sẽ được lưu trữ dưới dạng ma trận điểm, vị trí
pixel có nét vẽ sẽ mang giá trị 1, ngược lại có giá trị 0. Sau đó, ảnh được cắt
xén để ký tự nằm trọn trong một khung chữ nhật, các vùng không gian không
có nét vẽ được loại bỏ đi. Giải thuật cắt xén hiện thực đơn giản dựa trên ảnh nhị
phân và thu giảm ảnh đã được cắt xén về một ảnh có kích thước chung đã được
quy định trước.
Tiếp theo, ảnh đã được cắt xén và thu nhỏ được làm mỏng. Quá trình làm

duy nhất.
Hình 1.4 Mô hình Markov ẩn
x
i
: Các trạng thái trong mô hình Markov
a
ij
: Các xác suất chuyển tiếp
b
ij
: Các xác suất đầu ra
y
i
: Các dữ liệu quan sát
Mô hình Markov ẩn thêm vào các đầu ra: mỗi trạng thái có xác suất phân
bố trên các biểu hiện đầu ra có thể. Vì vậy, nhìn vào dãy của các biểu hiện được
sinh ra bởi HMM không trực tiếp chỉ ra dãy các trạng thái. Ta có tìm ra được
chuỗi các trạng thái mô tả tốt nhất cho chuỗi dữ liệu quan sát được bằng cách
tính.
7
Y1 Y2 … … … Yn
X1 X2 … … … Xn
)(/)|()|( XPXYPXYP =

Hình 1.5 Đồ thị vô hướng HMM
Ở đó Y
n
là trạng thái tại thời điểm thứ t=n trong chuỗi trạng thái Y, X
n
là dữ

Đặc trưng cơ bản quyết định khả năng phân loại của một bộ phân loại là
hiệu suất tổng quát hóa, hay là khả năng phân loại những dữ liệu mới dựa vào
những tri thức đã tích lũy được trong quá trình huấn luyện. Thuật toán huấn luyện
được đánh giá là tốt nếu sau quá trình huấn luyện, hiệu suất tổng quát hóa của bộ
phân loại nhận được cao. Hiệu suất tổng quát hóa phụ thuộc vào hai tham số là
sai số huấn luyện và năng lực của máy học. Trong đó sai số huấn luyện là tỷ lệ lỗi
phân loại trên tập dữ liệu huấn luyện. Còn năng lực của máy học được xác định
bằng kích thước Vapnik Chervonenkis (kích thước VC). Kích thước VC là một
khái niệm quan trọng đối với một họ hàm phân tách (hay là bộ phân loại). Đại
lượng này được xác định bằng số điểm cực đại mà họ hàm có thể phân tách hoàn
toàn trong không gian đối tượng, Một bộ phân loại tốt là bộ phân loại đơn giản
nhất và đảm bảo sai số huấn luyện nhỏ. Phương pháp SVM được xây dựng dựa
trên ý tưởng này.
jh',4
Công thức SVM đơn giản nhất là trường hợp tuyến tính khi mà một siêu phẳng
quyết định nằm giữa hai tập dữ liệu.Trong trường hợp này, không gian giả định là một
tập các điểm có phương trình là: q` ersW tT. SVM đi tìm một siêu phẳng tối ưu như
một phương án để phân chia hai tập hợp dữ liệu và đồng thời có thể sử dụng cho những
dữ liệu mới.
Có hai phương pháp để tìm siêu phẳng tối ưu. Thứ nhất là tìm siêu phẳng nằm
giữa 2 tập đóng. Thứ hai là cực đại hoá khoảng cách giữa hai mặt phẳng hỗ trợ (cực đại
hoá lề). Cả hai phương pháp đều tìm ra một mặt phẳng quyết định và tập hợp những
điểm hỗ trợ cho quyết định. Chúng được gọi là các vector hỗ trợ.
Siêu phẳng
phân chia
9
0QWd,g_u_v'O&
0QWawgxg_u'yTgx'$'\
0QWb4n'V%o%p
Siêu phẳng có

dụng hàm Sigmoid làm hàm ngưỡng.
0QW*,{PxP\n%OZ[\#$
So với hai phương pháp còn lại, phương pháp sử dụng mạng Neural được lựa chọn là do
những ưu điểm sau đây:
• Tính phi tuyến.
• Mô hình tổng quát cho ánh xạ từ tập vào đến tập ra.
• Có thể yêu cầu sự tiến hóa nhanh của hàm mục tiêu.
• Chấp nhận lỗi ở các ví dụ học.
• Thích ứng với nhiễu dữ liệu.
EW<M\P
• Đồ án “Nghiên cứu phương pháp nhận dạng chữ viết tay và cài đặt
chương trình thử nghiệm” được thực hiện với mục đích giải quyết một lớp con các
bài toàn nhận dạng chữ viết tay, tập trung vào bước nhận dạng ký tự tiếng Việt đơn
lẻ do đây là bước mà mọi hệ nhận dạng chữ viết tiếng Việt cần phải có.
• Từ đó tạo cơ sở để tiếp theo có thể xây dựng và phát triển một sản phẩm
nhận dạng chữ viết tay hoàn chỉnh trên các thiết bị di động, áp dụng vào việc hỗ trợ
việc học tập và sinh hoạt của người khiếm thị.
13
• Đồ án sẽ tập trung vào phân tích 3 thành phần chính của một hệ
nhận dạng: Tiền xử lý, trích chọn đặc trưng và huấn luyện bằng mô hình markov ẩn.
Từ đó cài đặt chương trình mô phỏng trên PC bằng ngôn ngữ C#
0I+;EE
+,-./0123/45/E5;|}.L;0
4G/7~00•;H/7I;
EEW/liO !"
Đầu vào của quá trình xử lý ảnh là các ảnh gốc ban đầu, thu được qua
scanner. ảnh ban đầu thường có chất lượng thấp do ảnh hưởng của nhiễu, bị
nghiêng, bị đứt nét nên chúng ta cần phải có một quá trình tiền xử lý ảnh để
nâng cao chất lượng ảnh đầu vào trước khi đưa vào nhận dạng. Quá trình này
bao gồm công đoạn khôi phục ảnh và tăng cường ảnh .

mang thông tin của ba màu cơ bản tạo ra bản màu khả kiến là Đỏ (R), Xanh lá
(G) và Xanh biển (B) [Thomas 1892]. Trong mỗi pixel của ảnh màu, ba màu cơ
bản R, G và B được bố trí sát nhau và có cường độ sáng khác nhau. Thông
thường, mổi màu cơ bản được biểu diễn bằng tám bit tương ứng 256 mức độ
màu khác nhau. Như vậy mỗi pixel chúng ta sẽ có màu (khoảng 16.78
triệu màu). Đối với ảnh xám, thông thường mỗi pixel mang thông tin của 256
mức xám (tương ứng với tám bit) như vậy ảnh xám hoàn toàn có thể tái hiện
đầy đủ cấu trúc của một ảnh màu tương ứng thông qua tám mặt phẳng bit theo
độ xám.
Trong hầu hết quá trình xử lý ảnh, chúng ta chủ yếu chỉ quan tâm đến cấu
trúc của ảnh và bỏ qua ảnh hưởng của yếu tố màu sắc. Do đó bước chuyển từ
ảnh màu thành ảnh xám là một công đoạn phổ biến trong các quá trình xử lý
ảnh vì nó làm tăng tốc độ xử lý là giảm mức độ phức tạp của các thuật toán trên
ảnh.
Chúng ta có công thức chuyển các thông số giá trị màu của một pixel
thành mức xám tương ứng như sau:
G = ỏ.CR + õ.CG + ọ.CB
Trong đó các giá trị CR, CG và CB lần lượt là các mức độ màu Đỏ, Xanh
lá và Xanh biển của pixel màu.
EEWWMv€"`Nhị phân ảnhe
Phân ngưỡng hay còn gọi là nhị phân hóa. Mục đích của nó là chuyển từ
15
ảnh mầu, ảnh đa cấp xám sang ảnh nhị phân (ảnh 2 cấp xám, ảnh đen trắng).
Thuật toán phân ngưỡng cài đặt ở đây sử dụng hàm phân ngưỡng :
1 if Source(x,y) >= T
Dest(x,y)=
0 if Source(x,y) < T
Trong đó, Source(x,y) là giá trị điểm ảnh ở vị trí (x,y) của ảnh nguồn,
Dest(x,y) là giá trị điểm ảnh tương ứng ở vị trí (x,y) của ảnh đích. T là giá trị
ngưỡng.

việc nhận dạng.
EEWW*;•"
Trong xử lý ảnh các ảnh đầu vào thường được thu thập từ các nguồn ảnh
khác nhau và các ảnh thu thập đươc thường có nhiễu và cần loại bỏ nhiễu hay
ảnh thu được không sắc nét, bị mờ cần làm rõ các chi tiết trước khi đưa vào xử
lý.
Một số loại nhiễu ảnh thường gặp:
 Nhiễu cộng : nhiễu cộng thường phân bố khắp ảnh. Nếu ta gọi
ảnh quan sát( ảnh thu được) là X_qs, ảnh gốc la X_gốc và
nhiễu là #. ảnh thu được có thể biểu diễn bởi:
X_qs = X_gốc + #.
 Nhiễu nhân : Nhiễu nhân thường phân bố khắp ảnh. Nếu ta gọi
ảnh quan sát( ảnh thu được) là X_qs, ảnh gốc la X_gốc và
nhiễu là #. ảnh thu được có thể biểu diễn bởi:
X_qs = X_gốc # #.
 Nhiễu xung : Nhiễu xung thường gây đột biến ở một số điểm
của ảnh. Trong hầu hết các trường hợp thừa nhận nhiễu là tuần
17
hoàn. Các phương pháp lọc đề cập trong báo cáo xét với các
trường hợp ảnh chỉ có sự xuất hiện của nhiễu.
EEWW<x‚__^_('•
EEWW<Wwx('nO
Mạch lọc là một mặt nạ có kích thước NxN, trong đó tất cả các hệ số đều
bằng 1. Đáp ứng là tổng các mức xám của NxN pixels chia cho NxN. Ví dụ mặt nạ
3x3 thì đáp ứng là tổng mức xám của 9 pixels chia cho 9. Ví dụ mặt nạ 1/9x
Nhân chập mặt nạ với tất cả các pixel của ảnh gốc chúng ta sẽ thu được ảnh
kết quả qua bộ lọc Mean theo công thức sau:
Hình 3.2.4.1 ảnh thu được khi qua bộ lọc Mean
Với f[i,j] là giá trị pixel kết quả, s(k,l) là các giá trị pixel ảnh gốc được mặt
nạ chập lên và S là kích thước mặt nạ. Bộ lọc Mean có vai trò làm trơn ảnh có

EEWWFP%"S^'Tg‚p
Sau quá trình lọc nhiễu, các từ, kí tự trên ảnh thu được thường bị đứt nét
do ảnh hưởng của bộ lọc nhiễu. Vì thế cần có một bước để nối lại các nét bị
đứt này.
 Phương pháp Canny Là một phương pháp tách biên ảnh do
Francis Canny tìm ra tại phòng thí nghiệm ảnh thuộc MIT.
19
Quá trình tiến hành thuật toán trải qua một số bước như
sau:
 Làm trơn ảnh bằng bộ lọc Gauss nhằm giảm thiểu
ảnh hưởng của nhiễu và các chi tiết không mong
nuôn trong cấu trúc ảnh.
 Tính gradient của ảnh nhờ một trong các toán
tử:Roberts, Sobel hay Prewitt…
và
Xác định ngưỡng:
Với T được chọn là các phần tử cạnh
Dựa vào hướng của dradient để loại bỏ những điểm không thực sự là biên.
Chúng ta kiểm tra các điểm MT(i,j) nếu có giá trị lớn hơn hai điểm lân cận dọc
theo phương gradient
θ
(i,j) thì giữ nguyên và ngược lại thì gán giá trị bằng 0.
Dùng ngưỡng kép ụ1 và ụ2 (ụ1< ụ2) tạo ra các điểm trung gian nhằm nối
liến các điểm biên đã xác định được từ trước theo phương thức sau:
Những điểm M(i,j) có giá trị gradient lớn hơn ụ2 thì được xem là điểm
biên. Những điểm M(i,j) có giá trị gradient nhỏ hơn ụ1 thì loại bỏ. Với những
điểm có giá trị gradient nằm trong khoảng ụ1 và ụ2 thì kiểm tra thêm nếu nó
liền kề với một điểm có gradient lớn hơn ụ1 thì điểm này được xem là điểm biên.
Kết quả chúng ta sẽ thu được các đường biên tạo từ vô số các điểm biên liền kề
liên tục.

Bước đầu tiên trong thuật toán này là xác định các thành phần liên
thông trên ảnh. Bước tiếp theo, tìm láng giềng gần nhất của mỗi thành phần
liên thông này, đó là miền liên thông có khoảng cách Ơclit ngắn nhất giữa tâm
của hai miền liên thông. Sau đó, thực hiên tính góc của các vector nối tâm của
các thành phần láng giềng gần nhất. Tất cả các vector cùng phương được nối
với nhau và tích lũy thanh biểu đồ histogram về số lượng các vector theo các
phương. Khi đó, trên biểu đồ histogram xuất hiện một vị trí có số lượng
vector nhiều nhất và cũng chính là đỉnh của biểu đồ.Vị trí đó chính là góc
21
nghiêng của trang văn bản.
Chi phí tính toán của phương pháp này đã giảm đi nhiều so với phương
pháp sử dụng biến đổi Hough tuy nhiên vẫn còn rất cao. Độ chính xác của
phương pháp này phụ thuộc rất nhiều vào số thành phần của một kí tự trong
văn bản. Đối với các kí tự có nhiều thành phần ví dụ như chữ ẩ có 3 thành
phần gồm thân, mũ và dấu hỏi. Khi đó, láng giềng gần nhất của mỗi phần sẽ là
một trong hai thành phần còn lại chứ không phải là kí tự liền kề với nó. Điều đó
làm giảm đi độ chính xác của thuật toán, đồng thời khiến cho nó không thích
hợp với chữ tiếng việt.
L’O Gorman đã phát triển thuật toán với ý tưởng là với mỗi thành phần
lấy k láng giềng (k có thể là 4 hoặc 5) thay vì lấy một láng giềng duy nhất. Và
góc thu được được sử dụng như là góc nghiêng ước lượng. Góc nghiêng
ước lượng này được sử dụng để loại bỏ các liên kết mà góc của nó không gần
với góc ước lương. Sau đó, thực hiện xác định lại góc nghiêng theo các liên
kết được giữ lại. ý tưởng này đã cải thiện được độ chính xác của thuật toán
nhưng lại đòi hỏi chi phí tính toán cao hơn. Trên thực tế, phương pháp này
được gọi là phương pháp docstrum – thực hiện cả việc xác định góc nghiêng
và phân tích cấu trúc trang .
Phương pháp sử dụng tia quay (project profile) là phương pháp thường
được sử dụng trong các hệ thống thương mại. Project profile là biểu đồ các
giá trị điểm đen được tích lũy theo các dòng quét song song với một phương

được các nhà nghiên cứu quan tâm.
EEW<Wx‚)'%'T"'…OP†
 )'%‚#g
23
0QW‡Mvz
0QWdp'{Ph' ^P`V%OPe
 )'%Q('Q^là các đặc trưng dựa trên
các yếu tố nguyên thủy (đoạn thẳng, cung) tạo ra các ký tự.
24
m
Các ký tự có thể được phân biệt bằng độ đo của các đại lượng
hình học như tỉ số giữa chiều rộng và chiều cao của khung
chứa ký tự, quan hệ khoảng cách giữa hai điểm, độ dài một nét,
độ dài tương quan giữa hai nét, tỉ lệ giữa các chữ hoa và chữ
thường trong một từ, độ dài từ…Vì thế các ký tự được tổ chức
thành các tập hợp của các yếu tố nguyên thủy, sau đó đưa các
yếu tố nguyên thủy vào các đồ thị liên quan.
 )'%Các ký tự được mô tả như các vector mà
các phần tử của nó là các giá trị thống kê về hướng. Việc chọn
đặc trưng để nâng cao độ chính xác của bài tốn nhận dạng là
hết sức khó khăn, đòi hỏi rất nhiều thời gian và quyết định rất
nhiều đến độ chính xác. Hơn nữa, do biến dạng khá lớn trong
chữ viết tay nên để hạn chế người ta thường chia ô trên ảnh và
đặc trưng được rút trong các ô đó.
0QWa)'%
EEW<Wx‚__^_%&''()'%
Ta có một số phương pháp trích chọn đặc trưng đơn giản nhưng hiệu quả
sau, có thể áp dụng cho các tập chữ viết tay rời rạc.
• /%(‚zẢnh ký tự sau khi tiền xử lý kích thước được chuẩn hoá về m×n
điểm ảnh. Đây là cách được áp dụng trong đồ án.