Đồ án tốt nghiệp:
" Tìm hiểu bài toán nhận dạng kí tự viết
tay và phát triển ứng dụng”


Nhận dạng kí tự viết tay và phát triển ứng dụng
SVTH : NguyễnĐình Cường Trang 1

Nhận dạng kí tự viết tay và phát triển ứng dụng
SVTH : NguyễnĐình Cường Trang 2

NHẬN XÉT CỦA GIÁO VIÊN. CHƯƠNG I
TỔNG QUAN

I. Giới thiệu bài tốn:
Nhận dạng kí tự, đặc biệt kí tự viết tay là bài tốn có nhiều ứng dụng thực tế.
Máy tính xử lí, nhận dạng các biểu mẫu, phiếu điều tra tự động, bằng cách này ta
có thể tiết kiệm được nhiều chi phí về thời gian, công sức cũng như các chi phí
khác cho việc nhập dữ liệu.
Ngày nay cùng với sự phát triển về mặt lý thuyết, công nghệ, có rất nhiều
hướng đi cho việc giải quyết bài tốn này như: nhận dạng kí tự dựa trên cấu trúc
hay cách tiếp cận khác như dùng: logic mờ, giải thuật di truyền, mô hình xác suất
thống kê, mô hình mạng nơ ron. Đặc biệt trong những năm gần đây mô hình mạng
nơron được quan tâm nhiều do khả năng tổng hợp của mô hình và sự phát triển về
tốc độ xử lí của máy tính.
Trên thế giới hiện nay có nhiều chương trình nhận dạng chữ viết (chữ in và
viết tay) bằng các thứ tiếng Anh, Nga, v.v như các hệ OMNIPAGE, READ-

Chương 1: Giới thiệu một số kĩ thuật phân lớp: đối sánh, sử dụng
hàm thế, phương pháp LDA.
Chương 2: Giới thiệu mô hình mạng nơ ron cho bài tốn nhận dạng.
Phần III: Giới thiệu một số ứng dụng và đánh giá kết luận gồm 4
chương .
Chương 1: Giới thiệu ứng dụng kĩ thuật tách liên thông cho việc
tách liên thông kí tự trong văn bản.
Chương 2: Xây dựng, đánh giá chương trình nhận dạng kí tự viết
tay.
Chương 3: Đưa kết quả vào ứng dụng xây dựng chương trình xử lí
phiếu đăng kí môn học cho sinh viên ở trường Đại học Thuỷ Sản Nha
Trang.
Chương 4: Đánh giá kết luận và nêu hướng phát triển của đề tài.
Phần IV : Phụ lục giới thiệu giao diện chương trình. Nhận dạng kí tự viết tay và phát triển ứng dụng
SVTH : NguyễnĐình Cường Trang 5

 
 
 
dvvpvveE
j
j
j





Lọc mịn ảnh có tác dụng hạn chế ảnh nhiễu muối tiêu.
II. Nhị phân ảnh:
Nhị phân ảnh mức xám là tìm giá trị ngưỡng sao cho các điểm ảnh có giá
trị lớn hơn ngưỡng được gọi là trắng(nền) và các điểm ảnh có giá trị nhỏ hơn
ngưỡng được gọi là đen (đối tượng).
Tiêu chuẩn xác định ngưỡng thường sử dụng nhất là sử dụng sai số bình
phương trung bình giữa giá trị mẫu v và mức tái thiết r(v). (ký hiệu MSE)
Ta có:

Trong đó p(v) là hàm mật độ xác suất của biến ngẫu nhiên v, có thể coi xấp
xỉ bằng histogram của ảnh. Với một số cho trước L các mức xám MSE được biểu
diễn bởi: E


2
e =
 
 
 
 
 
 
dvvpvrvvrvE



1

2

1

1

1

1

1/10

1

1

1

1

4

1

1

1

rr
v
j
j
j
j
v
v
v
v
j
jj
j
Do r(v)=r
j
là hằng số trong đoạn [v
j ,
v
j+1
].
Với p(v) cho trước và số mức tái thiết L cố định, các mức quyết định v
j
,
j= 1…L-1 và các mức tái thiết r

1
, và v
1
. Tham số v
1
gọi là
ngưỡng nhị phân hố. Hơn nữa r
0
(v
1
) và r
1
(v
1
) cực tiểu MSE, với một giá trị cho
trước của v
j
, đơn giản là những giá trị trung bình trong đoạn tương ứng:

1
). Nếu 
W
2
(v
1
) được bổ sung vào phương sai lớp giữa  
       
 

1
0
2
1
2
1
2
0
2
v
v
v
v
dvvprvdvvprveE 

v
v
dvvp
dvvvp
vr
Nhận dạng kí tự viết tay và phát triển ứng dụng
SVTH : NguyễnĐình Cường Trang 7

B
2
(v
1
), ta được tồn bộ biến đổi 
T
2
( độc lập v
1
). Như vậy, thay vì cực tiểu MSE,
giải thuật của Otsu cực đại phương sai giữa lớp:
Trong đó:
Và















2
1111
2
1010
*
1
maxarg
TT
vvpvvpv






   









   
   




1
0
1
0
1
1
v
v
v
v
dvvvpv
dvvpv






Nhận dạng kí tự viết tay và phát triển ứng dụng
SVTH : NguyễnĐình Cường Trang 8
Đã_xét[x, y] :=True ;
For i :=x-1 to x+1 do
For j:= y-1 to y+1 do
If ( i <>x) or (j<>y) then Chonvao((i, j),t);
End;
End ;
// Ta có thủ tục tách liên thông đệ quy như sau :
Procedure TáchLiênThôngĐQ(VAR LT: Danh_Sách_Liên_Thông)
Begin
T:=<danh sách rỗng>
t:=<liên thông rỗng>
For j:=1 to Height do
For i:=1 to Width do đã_xét[i, j]:=False;
For j:=1 to Height do
For i:=1 to Width do
If (Điểm(x, y)=1) AND( NOT Đã_xét[i, j]) then
Begin
Chonvao( (i, j ),t);
Thêm _liên_thông_vào_Danh_Sách(T, t) ;
t :=<liên thông rỗng> ;
End ;
End;
Nhận xét:
Thuật tốn này chỉ có ý nghĩa minh hoạ bản chất của tách liên thông. Ta
không chọn thuật tốn này cài đặt vì chi phí đệ quy quá cao, chưa kể tốc độ thực
hiện.
2. Giải thuật cải tiến:
Hình a. lân cận của “?” P= dòng trước; L=lân cận trái IV. Chỉnh nghiêng:
Chỉnh nghiêng ảnh là một phép biến đổi tuyến tính của toạ độ điểm ảnh.
Trước hết ta phải xác định góc nghiêng tổng thể của đối tượng, và ta dịch chuyển
điểm ảnh đối tượng theo phương ngang tuỳ theo giá trị góc nghiêng tổng thể này
và giá trị y của điểm này.
*
. .
*

*

*
. . . . .
1

1

1

1
. .
2

2

2
. . . .
. .
*

*

*
. .
*

*

*

*

*

*
. . . .
1

1

1

1
.
2

2

2

2

2
. . .
. . .
*

*
. . .  . . .
*

*

*

*

*

*
.
*
. . .
*

*
. . . . . . . .
*

*
. .
*

*
. . . . . . . .
*



. . . . . . . . . . . . . . . . .
. . . . . . . . . . .

.
1

1

1

1
. .
2

2

2
. . . . .
1

1

1

1
. .


1

1
. . .
.
1

1

1

1
.
2

2

2

2

2
. . . .
1

1

1



1
. . . . . .
. . .
1

1

1

1

1

1
.
3
. . .  . . .
1

1

1

1

1

1
.

. . . . . . .
2

2
. .
.
4

4
. . . . . . . . . . . .
3

3
. . . . . . . . . . .

Hình d . Sau khi quét đầy đủ Hình e .Kết quả sau cùng
Nhận dạng kí tự viết tay và phát triển ứng dụng
SVTH : NguyễnĐình Cường Trang 10
Góc nghiêng tổng thể kí tự là hướng trung bình của các điểm ảnh đối tượng
có giá trị góc khoảng –45
0
đến 45
0
theo quy ước tính góc trên . Các điểm ảnh đối
tượng có hướng ngồi khoảng –45
0
đến 45
0
không tính.
Giả sử gọi  là góc nghiêng tổng thể của kí tự , điểm ảnh đối tượng p(x,y)

: Hình . Các nhân của bộ lọc Sobel
Chú ý: góc tính theo gradient tại mỗi điểm ảnh đối tượng là góc so với trục
x và chỉ xét những điểm có hướng của vectơ gradient thoả trong khoảng [45
0
,135
0
]
hay [-135
0
,-45
0
].
V. Chuẩn kích thước:
Chuẩn kích thước ảnh kí tự về một kích thước cố định và phóng sát bốn
biên của ảnh.
Phóng ảnh là thực hiện phép biến đổi sau: Với (x, y) là toạ độ điểm ảnh sau khi phóng và s
x
,s
y
là tỷ lệ phóng theo trục
x và y tương ứng, f

-
2

-
10

0

01

2

1

S
y

yy
ytgxx



x
f
G
G
f
y
x

22
yx
GGf 
 










x
y
G
G
yx
1
tan,


trạng này, ta thực hiện một số xử lý bằng phép đóng morphology:
VI. Lấp khoảng trống ảnh bằng phép đóng morphology:
1. Một số định nghĩa:
Giả sử A và B là hai tập trong không gian Z
2
, aЄ A thì a=(a1, a2)
Phép dịch chuyển của tập A đối với x=(x1, x2) ký hiệu(A)
x
, được định
nghĩa. Phép phản chiếu của tập B, ký hiệu B
*
, được định nghĩa: Phép bù của một tập A, ký hiệu A
c
, được định nghĩa:

Hiệu của hai tập hợp A và B, ký hiệu A-B, được định nghĩa: 2. Phép giãn:
Giả sử A, B là hai tập thuộc Z
2
,  là tập hợp rỗng, phép giãn của A đối với
B, ký hiệu AB, được định nghĩa:


A a vôùi  ,xaccA
x



B bôùi  vbxxB ,
*



AxxA
C




BxAxxBA  ,





 ABxBA
x
*






2. Dò biên và mã hố đường biên:
Ta có giải thuật dò tìm biên như sau:
Bước 1: Quét ảnh đến khi gặp điểm ảnh đen. Gọi nó là pixel 1
Bước 2: Lặp
Nếu ” điểm ảnh hiện thời là đen “ thì “dò ngược”
Ngược lại “sang phải” đến khi “gặp pixel 1”
Minh hoạ dò biên

0

1

0

1

0

1

0

1

1

1

0

1

0 1

2

12


Nhận dạng kí tự viết tay và phát triển ứng dụng
SVTH : NguyễnĐình Cường Trang 13
3. Xác định hướng của điểm biên (Freeman code):
Các hướng được quy ước như sau:

Với hướng quy ước trên, đường biên được mã hố như sau: 4. Làm trơn đường biên:
Làm trơn đường biên là duyệt theo đường biên, nếu hai điểm liên tiếp trên
đường biên có hiệu số hướng lớn hơn 1 thì có thể hiệu chỉnh để có đường biên mà

và thay hướng p
i
như sau: 0

1

2

3

4

5

6

7

Nhận dạng kí tự viết tay và phát triển ứng dụng
SVTH : NguyễnĐình Cường Trang 14


Dabs=2 và c
i
lẻ, c
i+1
lẻ
d. dabs=3 , c
i
chẵn, c
i+1
lẻ

e. dabs=3, c
i
lẻ, c
i+1
chẵn
CHƯƠNG III
RÚT ĐẶC TRƯNG

I. Giới thiệu đặc trưng hướng:
Hướng các điểm trên đường biên của kí tự mô tả khá đầy đủ về kí tự. Đặc
trưng của ảnh được xác định là hướng của các điểm ảnh trên biên. 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à

Nhận dạng kí tự viết tay và phát triển ứng dụng
SVTH : NguyễnĐình Cường Trang 16
đặc trưng được rút trong các ô đó, việc chọn các ô phủ lấp lên nhau cũng không
ngồi mục đích trên.
II.Chia ô:
Aûnh kí tự sau khi tiền xử lý kích thước được chuẩn về mn điểm ảnh, ảnh
được chia nhỏ thành các ô vuông nhỏ kích thước 88 điểm ảnh như hình:
D

C

B

A

n
m

Nhận dạng kí tự viết tay và phát triển ứng dụng
SVTH : NguyễnĐình Cường Trang 17 Đặc trọng số vùng A, B, C và D tương ứng là 4, 3, 2, và 1 . Gọi x
j
là một

0
).
Như vậy ảnh kí tự sẽ được mô tả dưới dạng : Trong đó n=k*4 , với k là tổng số ô vuông 16x16 xếp chồng lên nhau. PHẦN II

CÁC MÔ HÌNH NHẬN DẠNG
x


CHƯƠNG I
GIỚI THIỆU CÁC MÔ HÌNH PHÂN LỚP, NHẬN DẠNG

I. Khái quát tình hình nghiên cứu, ứng dụng lý thuyết nhận dạng:
Lý thuyết nhận dạng là một lĩnh vực khoa học mới phát triển nhưng đã đạt
được nhiều thành tựu đáng kể về lý luận và ứng dụng trong thực tiễn, chứng tỏ khả
năng của máy tính điện tử, có thể mô hình hố được một số chức năng tương đối
phức tạp của trí tuệ con người.
Cho đến nay cơ sở tốn học của lý thuyết nhận dạng được xây dựng và phát
triển đồng thời theo các hướng chính sau đây:
- Lý thuyết thống kê nhận dạng.
- Lý thuyết cấu trúc về nhận dạng.
- Lý thuyết đại số về nhận dạng.
Mỗi lý thuyết nói trên đều có mục đích, đối tượng nghiên cứu và phương

i
biểu diễn kết quả của một phép đo. Tập hợp các biểu diễn xác định
X được gọi là không gian biểu diễn. Ví dụ không gian vectơ.
Giải thích một biểu diễn nghĩa là cho một kết quả chẳng hạn một cái tên.
Giả sử: ta có tập hợp các tên là: Không gian giải thích là một tập thoả các luật, thao tác nào đấy.
Một định danh là một ánh xạ của không gian biểu diễn vào không gian giải
thích. Mục đích nhận dạng là thực hiện ánh xạ này và tìm thuật tốn để thực hiện
trên tồn X. Một thuật tốn như vậy gọi là tốn tử nhận dạng.
2. Tập mẫu nhận dạng:
Dữ liệu cho bài tốn nhận dạng thường được biểu diễn qua tập mẫu học T
với
T=(xq, ) là tập các cặp (dữ liệu - tên).
3. Độ đồng dạng và dị dạng:
Là hai chỉ số thường dùng để xây dựng trên quan hệ gần thứ tự trên các cặp
đặc biệt khoảng cách giữa hai đối tượng là một chỉ số dị dạng thoả mãn 3 tiên đề:
- (x, y) 0 , (x, x)=0
- (x, y)= (y, x)
- (x, z) (x, y)+ (y, z)
4. Khoảng cách đối tượng:


n
xxxxX 
321

(X, A
i
)  (X, A
j
)
Quan hệ này thường được thiết lập nhờ một khoảng cách đối tượng, ký
hiệu: D(X, A).
Nếu muốn phân lớp hoặc định danh X có thể dùng thông tin này. Giả sử C
i

là lớp phân hoạch tương ứng với khái niệm đại diện A
i
; X được gán vào C
i
nếu
D(X, A
i
) là nhỏ nhất.
III. Một số thuật tốn phân lớp:
Có nhiều giải pháp phân lớp, trong thời gian qua em đã tìm hiểu và thử
nghiệm một số giải pháp sau:
1. Xếp lớp khoảng cách cực tiểu:
Giả thiết là mỗi lớp mẫu được biểu diễn bằng một vectơ đơn (hoặc trung
bình).
Trong đó N
j
là số vectơ mẫu từ lớp 

theo mọi phía. Tại điểm M của không gian ta có thế gây ra bởi q là:
a : hằng số
q: độ lớn điện tích q
r: khoảng cách từ M tới q
Các dạng hàm thế thường dùng trong thuật tốn nhận dạng:
Mjx
N
m
j
x
j
j
,2,1
1







MjmxxD
jj
,2,1; 
 
Mjmmmxxd
j

) là khoảng cách S và S
’

(=0, 1, 2 )

Cách tính thế đối với mỗi lớp:

m
j
:

số mẫu của K
j
S
t
: mẫu thuộc K
j

Ta có luật quyết định: Chú ý :
Việc tính thế đối với mỗi lớp, có thể bổ sung trọng số mẫu (S
t
) :
1
và C
2
. Điều này tương đương với việc giảm
số chiều của vectơ đặc trưng xuống còn 1 chiều.
Ta gọi m
i
, i=1, 2 là trị trung bình của các mẫu tương ứng với 2 lớp C
1
và
C
2
. 



 
 
'
21
'
,'
,.
1
,
,
'

,






K S, max arg


j
K
S,

neáu
j
KS



   
t
KS
t
j
j
SSS
m
KS
jt

||
~
2
~
1
mm 

Và tương ứng là trung bình của các mẫu được chiếu lên phương w:

Trong đó y là hình chiếu của x lên w. Y
i
là tập các hình chiếu của các x 
X
i
lên w.
Ta có thể xem là một độ đo cho tính phân biệt giữa hai tập Y
1

và Y
2
. Tuy nhiên để có được sự phân biệt tốt giữa hai tập khi chiếu lên phương w,
ta cần có độ sai khác giữa hai trị trung bình này khá lớn hơn so với độ lệch chuẩn
nội tại của mỗi tập ( có thể xem như độ rộng của đám mây các mẫu).
Thay vì sử dụng phương sai của mỗi tập ta sẽ sử dụng một độ đo khác, gọi
là độ rải (scatter) cho các hình chiếu của các mẫu thuộc lớp C
i
như sau:

Nên Tương tự ta cũng có:
i
m
~

i
T
Xx
T
i
Yy
i
i
mwxw
n
y
n
m
ii



11
~

mm
wJ



 
 

2
1
))((
i Xx
T
iiW
i
mxmxS

T
B
mmmmS ))((
2121


2
i
s


=


S
W
w

Nhận dạng kí tự viết tay và phát triển ứng dụng
SVTH : NguyễnĐình Cường Trang 23 Do đó:
Để xác định w sao cho J(w) cực đại ta cho đạo hàm riêng J(w) theo w bằng
0 kết quả ta sẽ được: Với  là trị riêng, giải bài tốn tìm trị riêng ta sẽ có: Đây là kết quả tìm được của phương pháp LDA đối với trường hợp chỉ có 2
lớp.
Sau khi đã tìm được w, mỗi vectơ x cần nhận dạng sẽ được xử lý như sau:
lấy x trừ đi trung bình của mẫu học rồi chiếu lên phương w ta được một giá trị vô
hướng, tính khoảng cách từ giá trị vô hướng này trên
i
m
~
của mỗi lớp này chia cho
độ lệch chuẩn
2

1 2
( )
m m

 
= w
T
S
B
w.
J(w) =
wSw
wSw
W
T
B
T
.
S
B
w =

S
W
w)(
21
1
CHƯƠNG II
PHÂN LỚP DỰA TRÊN MẠNG NƠRON LAN TRUYỀN NGƯỢC

Sơ lược về mạng nơron MLP (Multi-Layer Perception ) với thuật tốn lan
truyền ngược:
I. Giới thiệu:
Xét về mặt cấu trúc, MLP có cấu trúc phân lớp. Các cung được nối từ một
nút ở lớp này đến các nút ở lớp kế tiếp. Hai nút trong cùng một lớp thì không kết
nối với nhau. Mỗi nút trong một lớp nhận giá trị từ các nút ở lớp liền trước, tổng
hợp lại theo trọng số của cung kết nối và chuyển giá trị kết xuất của nó cho các
nút ở lớp liền sau. Lớp đầu tiên nhận giá trị từ bên ngồi vào và được gọi là lớp
nhập (input). Các nút trong lớp nhập được gọi là nút nhập. Lớp cuối cùng sẽ xuất
ra kết quả của mạng và được gọi là lớp xuất (output). Các nút trong lớp xuất được
gọi là nút xuất. Các lớp còn lại được gọi là lớp ẩn và các nút tương ứng được gọi
là nút ẩn.