BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC LẠC HỒNG
*** NGUYỄN MINH TRIẾT
NGHIÊN CỨU NHẬN DẠNG CHỮ VIẾT
TAY MÔ HÌNH MARKOV ẨN
Chuyên ngành : CÔNG NGHỆ THÔNG TIN
Mã số: 60.48.02.01 Luận văn thạc sĩ Công nghệ thông tin NGƢỜI HƢỚNG DẪN KHOA HỌC
TS. VŨ ĐỨC LUNG
Đồng Nai – Năm 2013
Học viên Nguyễn Minh Triết
MỤC LỤC CHƢƠNG I : GIỚI THIỆU ĐỀ TÀI 3
1.1 Giới thiệu về nhận dạng chữ viết tay 3
1.1.1 Các giai đoạn phát triển 3
1.1.2 Tình hình nghiên cứu trong nƣớc 4
1.1.3 Tình hình nghiên cứu ở nƣớc ngoài 5
1.2 Cách tiếp cận giải quyết bài toán 5
1.3 Tổng quan về các phƣơng pháp huấn luyện 6
1.3.1 Mô hình Markov ẩn 6
1.3.2 Máy vector hỗ trợ 8
1.3.3 Mạng Neural 11
1 4 Phạm vi đề tài 11
CHƢƠNG II : CƠ SỞ LÝ THUYẾT VỀ TIỀN XỬ LÝ ẢNH
VÀ TRÍCH CHỌN ĐẶC TRƢNG 13
2.1 Tổng quan về tiền xử lý ảnh 13
2.2 Các công đoạn tiền xử lý 13
2 2.1 Chuyển xám ảnh. 14
2 2.2 Phân ngƣỡng ảnh (Nhị phân ảnh) 15
2 2.3 Nhiễu ảnh 17
2 2.4 Một số phƣơng pháp lọc nhiễu 17
2 2.4.1 Bộ lọc Mean 18
2.2.4.2 Bộ lọc Gauss 19
3.5.1.2 Thiết kế codebook 58
3.5.2 Phân nhóm 60
3.5.2.1 Thuật toán –Kmeans 61
3.5.2.2 Thuật toán ISODATA 62
3.5.3 Kết luận 65
CHƢƠNG IV : ỨNG DỤNG MÔ HÌNH MARKOV ẨN
TRONG NHẬN DẠNG CHỮ VIẾT TAY 67
4.1 Cấu trúc một hệ nhận dạng chữ viết khi dùng mô hình Markov ẩn 67
4.2 Ứng dụng mô hình Markov ẩn vào nhận dạng chữ viết tay 67
4.3 Các vấn đề khó khăn và hƣớng giải quyết đối với
bài toán nhận dạng chữ viết tay tiếng Việt 70
4.3.1 Khó khăn về dấu trong tiếng Việt 70
4.3.2 Khó khăn về sự biến dạng chữ 71
4.4 Mô hình nhận dạng và huấn luyện 73
CHƢƠNG V : CÀI ĐẶT CHƢƠNG TRÌNH
VÀ ĐÁNH GIÁ KẾT QUẢ 75
5.1 Môi trƣờng thực nghiệm 75
5.2 Tạo cơ sở dữ liệu mẫu 75
5.2.1 Tạo CSDL mẫu cho nhận dạng online 76
5.2.2 Tạo CSDL mẫu cho nhận dạng offline 77
Kết luận 78
Tài liệu kham khảo
DANH MỤC HÌNH ẢNH
Hình 1.1 Mô hình tiếp cận giải quyết bài toán 5
Hình 3.1 Mô hình Markov 3 trạng thái .36
Hình 3.2 Tiến trình Markov 38
Hình 3.3 Biểu đồ trạng thái 38
Hình 3.4 Ví dụ về hình vuông và hình tròn 40
Hình 3.5 Chuỗi Q tối ưu cục bộ. 43
Hình 3.6. Sơ đồ lưới cho 3 trạng thái kết nối đầy đủ 48
Hình 3.7. Thao tác cơ bản của tính toán tiến 48
Hình 3.8. Sơ đồ lưới cho 3 trạng thái 53
Hình 3.9 Thao tác cơ bản của tính toán Viterbi 53
Hình 3.10. Biểu đồ minh họa giải thuật Level Building 55
Hình 3.11 Phép lượng hóa một độ đo một chiều 56
Hình 3.12. Phép lượng hóa không gian hai chiều 67
Hình 3.13 Cây nhị phân tìm kiếm VQ 60
Hình 3.14 Ba nhóm cluster trong mặt phẳng hai chiều 61
Hình 4.1 Mô hình ứng dụng Markov ẩn 68
Hình 4.2 Minh họa chia vùng ảnh 69
Hình 4.3 Dãy các trạng thái. 70
Bảng 4.4 Cấu trúc ký tự tiếng Việt 70
Hình 4.7. Mẫu ký
t
ự chữ A v
i
ế
t t
ay 71
Hình 4.8. Mẫu ký
t
ự chữ G v
i
ế
LỜI MỞ ĐẦU 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ữ viết tay 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:
Chƣơng 1: Giới thiệu đề tài
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.
98%).
Nhận dạng chữ viết tay: vẫn còn là vấn đề thách thức lớn đối với các nhà nghiên
cứu. Bài toàn này chƣa thể giải quyết trọn vẹn đƣợc vì nó hoàn toàn phụ thuộc vào
ngƣời viết và sự biến đổi quá đa dạng trong cách viết và trạng thái sức
khỏe, tinh thần của từng ngƣời viết.
1.1.1 Các giai đoạn phát triển
Giai đoạn 1: (1900 – 1980)
- 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ữ.
Giai đoạn 2: (1980 – 1990)
- 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
4 đã 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ả trong nhiều ứng dụng thực tế.
Các phƣơng pháp này tỏ ra không hữu hiệu hoặc xử lý chậm. Do đó ngƣời ta cần
nghiên cứu phƣơng pháp nghiên cứu phƣơng pháp nhận dạng chữ viết tay trên các máy
Palm Pilot hay các máy TABLET PC.
1.2 Cách tiếp cận giải quyết bài toán
Hình 1.1 Mô hình tiếp cận giải quyết bài toán
Nhận dạng chữ viết tay thƣờng bao gồm năm giai đoạn: tiền xử lý
(preprocessing), 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.
- 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 ,mô hình markov ẩn ,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.
- 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.
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ẽ
6 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 mỏng
Hình 1.2 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.
)(/)|()|( XPXYPXYP Hình 1. 3 Đồ 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ữ liệu
quan sát đƣợc tại thời điểm thứ t=n trong chuỗi X. Do trạng thái hiện tại chỉ phụ thuộc
vào trạng thái ngay trƣớc đó với giả thiết rằng dữ liệu quan sát đƣợc tại thời điểm t chỉ
phụ thuộc và trạng thái t. Ta có thể tính:
…
…
…
X
n
8 gặp phải là việc sử dụng xác suất đồng thời P(Y, X) đôi khi không chính xác vì với một
số bài toán thì việc sử dụng xác suất điều kiện P(Y | X) cho kết quả tốt hơn rất nhiều.
1.3.2 Máy vector hỗ trợ
Có thể mô tả 1 cách đơn giản về bộ phân lớp SVM (Support Vector Machine) nhƣ
sau: Cho trƣớc 2 tập dữ liệu học, mỗi tập thuộc về 1 lớp cho trƣớc, bộ phân lớp SVM sẽ
xây dựng mô hình phân lớp dựa trên 2 tập dữ liệu này. Khi có một mẫu mới đƣợc đƣa
vào, bộ phân lớp sẽ đƣa ra dự đoán xem mẫu này thuộc lớp nào trong 2 lớp đã định.
Phƣơng pháp này đƣợc Vapnik và cộng sự đề xuất năm 1992, lấy nền tảng từ lý thuyết
học thống kê của Vapnik & Chervonenkis vào năm 1960.
Đặ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.
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
Việc huấn luyện SVM là việc giải bài toán quy hoạch toàn phƣơng với các ràng
buộc bằng và không bằng. Việc xử lý sau cùng là xử lý các tham số dƣơng α và rút ra
một tập con của tập huấn luyện tƣơng ứng với các tham số. Việc huấn luyện một tập dữ
liệu nhỏ (nhỏ hơn 1000 mẫu) có thể đƣợc xử lý một cách nhanh chóng trên một máy tính
có cấu hình thích hợp. Đối với những tập dữ liệu lớn hơn, việc giải bài toán quy hoạch
toàn phƣơng đòi hỏi một máy tính có năng lực lớn và bộ nhớ lớn để lƣu trữ ma trận hạt
nhân trong suốt quá trình tính toán. Bộ nhớ yêu cầu lên đến bình phƣơng kích thƣớc của
tập huấn luyện.
Có nhiều phƣơng pháp huấn luyện SVM đƣợc phát triển để tận dụng bộ nhớ, cải
thiện tốc độ huấn luyện và tìm một mô hình tốt nhất bằng cách dùng một nhân và các
siêu tham số thích hợp (Burges, 1988). Lƣu ý rằng, SVM cơ bản dùng cho hai lớp, để có
thể dùng cho nhiều lớp thì ta phải kết hợp nhiều bộ phân loại hai lớp hoặc xây dựng
SVM cho nhiều lớp.
1.3.3 Mạng Neural
Quá trình huấn luyện là quá trình học các tập mẫu để điều chỉnh trọng số liên kết.
Giải thuật huấn luyện thƣờng đƣợc dùng nhất là giải thuật lan truyền ngƣợc sai số Back
Progration.
Hình 1.9 Sơ đồ một mạng neural nhận dạng ký tự
Phƣơng pháp sử dụng mạng Neural có 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.
1.4 Phạm vi đề tài
Đề tài nghiên cứu các thuật toán tiền xử lý ảnh và các phƣơng pháp huấn luyện
và nhận dạng từ đó đánh giá ƣu và nhƣợc điểm mô hình Markov ẩn ứng dụng vào nhận
dạng chữ viết tay cũng nhƣ mức độ chính xác trong quá trình nhận dạng .
12 Đề tài tập trung vào nghiên cứu nhận dạng các ký tự tiếng Việt đơn lẽ và đó là
tiền đề cho việc phát triển nhận dạng từ và cả văn bảng viết tay.
Đồ á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#.
13 CHƢƠNG II
CƠ SỞ LÝ THUYẾT VỀ TIỀN XỬ LÝ ẢNH
VÀ TRÍCH CHỌN ĐẶC TRƢNG
Chuyển xám
Phân ngƣỡng
Lọc nhiễu
Chỉnh nghiên
Phát hiện và tách biên.
2.2.1 Chuyển xám ảnh.
Đơn vị tế bào của ảnh số là pixel. Tùy theo mỗi định dạng là ảnh màu hay ảnh
xám mà từng pixel có thông số khác nhau. Đối với ảnh màu từng pixel sẽ 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, các giá trị α, β, Ω là các hệ số cƣờng độ sáng của 3 màu.
TyxSourceif
TyxSourceif
yxDest
),(__0
),(__1
),(
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.
Giá trị cụ thể của ngƣỡng phụ thuộc vào từng ảnh, vùng ảnh đầu vào đang xét và
không thể lấy cố định, nhƣ trên hình 2.2.2
+ Hình a là ảnh ban đầu
+ Hình e thể hiện biểu đồ histogram (biểu đồ tần suất)
+ Hình b,c,d thể hiện ảnh đã đƣợc nhị phân hóa với cùng ngƣỡng thấp, trung bình
và ngƣỡng cao. Chúng ta có thể thấy là giá trị ngƣỡng trong hình d là thích hợp hơn
cả. a) ảnh gốc ban đầu b) Ngƣỡng thấp (90)
16
Hình 2.2 - Phương pháp lấy ngưỡng
Copyright: Tài liệu đại học ©