TRƯỜNG ………………….
KHOA……………………….
[\[\
Đồ án tốt nghiệp
Đề tài:
Hệ thống quản lý đào tạo
và cấp giấy phép lái xe 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
LỜI NÓI ĐẦU
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.
Giáo viên nhận xét
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-
WRITE, WORD-SCAN, Ở Việt Nam cũng có một số hệ như WORC của 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 4
ty 3C, VIET-IN của công ty SEATIC, VNDOCR của Viện Công Nghệ Thông Tin,
Image Scon của Trung Tâm Tự Động Hóa Thiết Kế, hệ WINGIS của công ty
DolfSoft
Nhìn chung, các sản phẩm phần mềm nhận dạng văn bản Tiếng Việt chữ in
của nước ta đã thu được kết quả khả quan, đặc biệt phần mềm VNDOCR đã được
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
1
2
2
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
0
22
1
1
1
1
1/10
1
1
1
1
4
1
1
1
1
1/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 6
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
j
, j=0 L-1 cực tiểu hố MSE tuân theo quan hệ sau:
(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:
Như vậy đủ để biến đổi v
1
từ v
0
đến v
2
. MSE được tính bằng cách thay r
0
1
0
2
1
2
1
2
0
2
v
v
v
v
dvvprvdvvprveE
1
0
1
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à Biểu thức có thể đơn giản thành :
2
1111
2
1010
*
1
maxarg
TT
vvpvvpv
max2
1
1
1
0
1
0
1
1
v
v
v
v
dvvvpv
dvvpv
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:
Để gán nhãn cho thành phần liên thông ta có thể duyệt theo từng đường
chạy. Kỹ thuật này gán cho mỗi thành phần liên thông của ảnh nhị phân một nhãn
riêng biệt. Nhãn thường là các số tự nhiên bắt đầu từ một đến tổng số các thành
phần liên thông trong ảnh input.
Giải thuật phát biểu như sau:
Quét ảnh từ trái sang phải và từ trên xuống dưới. Trong dòng thứ nhất chứa
pixel đen, một nhãn duy nhất được gán cho mỗi đường chạy liên tục của pixel đen.
Với mỗi pixel đen của dòng tiếp theo, các pixel lân cận dòng trước và pixel bên
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. Hình a Hình b
Chuyển gớc toạ độ về trọng tâm ảnh như hình b
Góc nghiêng của kí tự được qui ước tính là góc từ trục tung, hướng về bên
trái có giá trị dương, hướng về bên phải có giá trị âm.
1
1
1
1
. .
2
2
2
. . . .
. .
*
*
*
. .
*
*
*
*
. . . . .
1
*
. . . .
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
1
.
2
2
2
2
2
. . . .
1
1
1
1
.
1
1
1
1
1
1
1
.
3
. . . . . .
1
1
1
1
1
1
.
2
. . .
4
4
. . . . . . . .
3
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)
(trong hệ toạ độ mới ) sẽ có toạ độ mới là p(x’
,y’) (trong hệ toạ độ mới ) với :
Để tính góc nghiêng tổng thể ta phải tính được hướng của các điểm ảnh đối
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
x
(x,y) là giá trị điểm ảnh kết quả ứng với giá trị toạ độ (x, y).
Chú ý:
-
1
0
0
01
2
1
S
y
yy
ytgxx
'
'
22
yx
GGf
x
y
G
G
yx
1
tan,
yxs
sysxfyxf ,,
, đượ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 AB, được định nghĩa: Tập B thường được gọi là thành phần cấu trúc.
3. Phép co:
Giả sử A, B là hai tập thuộc Z
2
, phép co của A đối với B, ký hiệu AB
được định nghĩa:
AxxA
C
BxAxxBA ,
ABxBA
x
*
ABxBA
x
BBABA
Ngược lại “sang phải” đến khi “gặp pixel 1”
Minh hoạ dò biên
0
1
0
1
1
0
0
0
1
1
1
0
1
0 1
2
12
3
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à
hai điểm liên tiếp có hiệu số hướng bằng 1.
Theo mã hướng Freeman, hiệu số hướng của 2 điểm liên tiếp nhau trên
đường biên được định nghĩa :
Goi c
i
là mã hướng tại điểm biên đang xét p
i
, c
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
chẵn , c
i+1
chẵn
i+1
lẻ
e. dabs=3, c
i
lẻ, c
i+1
chẵn Nhận dạng kí tự viết tay và phát triển ứng dụng
SVTH : NguyễnĐình Cường Trang 15
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ề mn điểm ảnh, ảnh
được chia nhỏ thành các ô vuông nhỏ kích thước 88 điểm ảnh như hình: Hình minh hoạ cách chia ô kí tự.
Gom 4 ô kích thước 8x8 thành ô kích thước 16x16, và các ô kích thước
16x16 này được phủ lên nhau một nữa theo hai hướng ngang và dọc. Trên mỗi ô
kích thước 16x16 sẽ rút đặc trưng theo 4 hướng (0
0
, 45
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
loại đặc trưng, x
j
được tính cho một ô kích thước 16x16 như sau:
III. Đặc trưng hướng của đường biên:
Aûnh để rút đặc trưng này là ảnh chỉ chứa đường biên. Với mỗi ô kích
PHẦN II
CÁC MÔ HÌNH NHẬN DẠNG
x
j
=4x
j
(A)
+3x
j
(B)
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
pháp giải quyết vấn đề khác nhau.
Lý thuyết thống kê về nhận dạng là một nhánh phát triển từ thống kê tốn
học, sử dụng các phương pháp cơ bản của thống kê tốn để nghiên cứu vấn đề nhận
dạng có yếu tố ngẫu nhiên và lượng thông tin đủ lớn. Công trình đầu tiên ở
phương Tây theo hướng này là của Sebestyen, mới đây hai nhà tốn học Liên Xô
là Vapnhic và Trecvonenkix đã cho ra một tài liệu khá đầy đủ về vấn đề này.
Lý thuyết cấu trúc về nhận dạng cho tới nay vẫn chưa được xây dựng hồn
chỉnh. Các nghiên cứu theo hướng này tập trung vào nghiên cứu các đối tượng mà
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
,,
p
,,
21
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
j
, M là số lớp cần phân biệt và tổng
được xác định từ các vectơ này, cách xác định lớp của một vectơ mẫu x chưa biết
là chỉ định nó cho lớp đơn điệu gần nhất. Dùng khoảng cách Euclid để xác định
độ gần sẽ giảm được tính tốn. Trong đó a =(a
Mjx
N
m
j
x
j
j
,2,1
1
MjmxxD
jj
,2,1;
Mjmmmxxd
j
T
jj
T
j
,2,1
2
1
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
) :
Nhận xét:
Nếu chọn là hàm khoảng cách Euclid thì giải thuật hàm thế này gần giống
với cách xếp lớp theo khoảng cách cực tiểu.
3. Phương pháp LDA (Linear Discriminant Analysis):
Phương pháp LDA cho trường hợp phân biệt 2 lớp, LDA sẽ tìm một
phương chiếu mà phân biệt tốt nhất các mẫu thuộc hai lớp khác nhau trong tập
1
và
C
2
.
'
21
'
,'
,.
1
,
,
'
SSCC
SS
eSS
ss
j
K
S,
neáu
j
KS
t
KS
t
j
j
SSS
m
KS
jt
.,
1
,
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:
Phương pháp LDA sẽ tìm giá trị w để cực đại hố hàm tiêu chuẩn sau đây:
m
~
i
T
Xx
T
i
Yy
i
i
mwxw
n
y
n
m
ii
11
~
2
~~
2
1
))((
i Xx
T
iiW
i
mxmxS
T
B
mmmmS ))((
2121
2
i
s
=
i
Xx
i
TT
mwxw
2
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
~
i
ta được một độ đo khoảng cách từ x đến các cụm ứng với mỗi
lớp.
i=1 2
B
w.
J(w) =
wSw
wSw
W
T
B
T
.
S
B
w =
S
W
w)(
21
1
mmSw
W
1
( )
i
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.
Copyright: Tài liệu đại học ©