Nhận dạng chữ

DANH MỤC CÁC KÝ HIỆU, CỤM TỪ VIẾT TẮT
Ký hiệu Thuật ngữ
HMM Hidden Markov Model (Mô hình Markov ẩn)
kernel hàm nhân
KKT Karush-Kuhn-Tucker
k-NN k – láng giềng gần nhất
L
P
Hàm Lagrange của bài toán gốc (primal)
L
D
Hàm Lagrange của bài toán đối ngẫu (dual)
L
2
Không gian các hàm khả vi liên tục cấp 2
MD Marginal Difference
MMD Maximum Marginal Difference
MNIST bộ mẫu chữ số viết tay NIST - Viện Công nghệ và Tiêu chuẩn
Quốc gia Hoa Kỳ (National Institute of Standard and Technology
of the United States)
NN Neuron Network (Mạng nơ ron)
OCR Optical Character Recognition (nhận dạng chữ quang học)
OVO One – versus – One
OVR One – versus – Rest
off-line ngoại tuyến
on-line trực tuyến
QP Quadratic Programing (quy hoạch toàn phương)
RBF Radial Basic Function

5
SOM Self Origanizing Map
SMO Sequential Minimal Optimization
SV Support vector (véc tơ tựa)
SVM Support Vector Machines (Máy véc tơ tựa)
TSMN two-stage multinetwork (máy phân lớp đa mạng hai giai đoạn)
USPS United States Postal service
VC Vapnik – Chervonenkis
working set tập làm việc
||w||
2
Chuẩn Euclide của siêu phẳng


6
DANH MỤC CÁC BIỂU BẢNG

Bảng 2.1. Kết quả thực nghiệm trên tập USPS 57
Bảng 2.2. Kết quả thực nghiệm trên tập MNIST 57
Bảng 2.3. Kết quả thực nghiệm với các hàm nhân khác nhau trên tập USPS 58
Bảng 2.4. Kết quả huấn luyện với hàm nhân Gausse. 58
Bảng 2.5. Kết quả huấn luyện với kích thước cache khác nhau. 59
Bảng 2.6. So sánh kết quả nhận dạng của SVM với các mô hình mạng nơ ron. 59
Bảng 2.7. So sánh một số phương pháp phân lớp trên bộ dữ liệu MNIST 60
Bảng 3.1. Kết quả nhận dạng theo các loại đặc trưng khác nhau. 67
Bảng 3.2. Kết quả nhận dạng trên các tập dữ liệu tiếng Việt viết tay rời rạc 74
Bảng 3.3. Kết quả nhận dạng trên tập dữ liệu TestData5. 82


7

DANH MỤC CÁC HÌNH VẼ
Hình 1.1. Sơ đồ tổng quát của một hệ thống nhận dạng chữ viết tay. 12
Hình 1.2. Nhị phân hóa ảnh. 13
Hình 1.3. Nhiễu đốm và nhiễu vệt. 14
Hình 1.4. Chuẩn hóa kích thước ảnh các ký tự “A” và “P” 14
Hình 1.5. (a) Ảnh gốc, (b) Ảnh sau khi được làm trơn biên 15
Hình 1.6. Làm mãnh chữ 15
Hình 1.7. Hiệu chỉnh độ nghiêng của văn bản 16
Hình 1.8. Tách dòng chữ dựa trên histogram theo chiều ngang của khối chữ. 16
Hình 1.9. Xác định khoảng cách giữa hai kí tự và giữa hai từ 17
Hình 2.1. Siêu phẳng tách tuyến tính. 34
Hình 2.2. So sánh hiệu quả phân lớp giữa máy tuyến tính thông thường với SVM 34
Hình 2.3. Siêu phẳng tách hai lớp ‘o’ và ‘+’. 35
Hình 2.4. Phân lớp mềm 36
Hình 2.5. Ánh xạ dữ liệu vào không gian đặc trưng. 42
Hình 2.6. Độ tin cậy VC tăng theo h 47
Hình 2.7. Họ hàm được chia làm các tập con theo chiều VC tăng dần. 47
Hình 2.8. Không phải 3 điểm nào cũng tách được bởi đường thẳng 48
Hình 2.9. Với 3 điểm không thẳng hàng trong R
2
thì luôn tách được 49
Hình 2.10. Mô hình nhận dạng chữ viết tay rời rạc. 55
Hình 2.11. Chọn đặc trưng ma trận nhị phân 56
Hình 2.12. Các mẫu chữ viết tay trích từ tập các tập dữ liệu USPS và MNIST 57

8
Hình 3.1. Trích chọn đặc trưng trọng số vùng 62
Hình 3.2.Trích chọn các biểu đồ chiếu ngang, dọc và 2 đường chéo 63
Hình 3.3. Trích chọn các khối bên ngoài của chữ 63
Hình 3.4. Quá trình trích chọn đặc trưng 64
Hình 3.5. Dãy đặc trưng wavelet Haar 66
Hình 3.6. Kiến trúc của hệ nhận dạng chữ viết tay tiếng Việt 69
Hình 3.7. Một số nhiễu thường gặp khi quét ảnh 69
Hình 3.8. Chuẩn hóa ảnh. 70
Hình 3.9. Chuẩn hóa các vùng liên thông. 70
Hình 3.10. Các mẫu trích từ tập ký tự viết tay tiếng Việt 73
Hình 3.11. Độ sai lệch lề giữa siêu phẳng gốc và siêu phẳng đơn giản hóa 81



9

PHẦN MỞ ĐẦU

Tính cấp thiết của đề tài
Nhận dạng chữ là một lĩnh vực đã được quan tâm nghiên cứu và ứng dụng từ
nhiều năm nay theo hai hướng chính:
Nhận dạng chữ in: phục vụ cho công việc tự động hóa đọc tài liệu, tăng tốc
độ và hiệu quả nhập thông tin vào máy tính trực tiếp từ các nguồn tài liệu.
•
Nhận dạng chữ viết tay: với những mức độ ràng buộc khác nhau về cách
viết, kiểu chữ phục vụ cho các ứng dụng đọc và xử lý chứng từ, hóa đơn,
phiếu ghi, bản thảo viết tay Nhận dạng chữ viết tay được tách thành hai
hướng phát triển: nhận dạng chữ viết tay trực tuyến (on-line) và nhận dạng
chữ viết tay ngoại tuyến (off-line).
•
Đến thời điểm này, bài toán nhận dạng chữ in đã được giải quyết gần như trọn
vẹn (sản phẩm FineReader 9.0 của hãng ABBYY có thể nhận dạng chữ in theo 20
ngôn ngữ khác nhau, phần mềm nhận dạng chữ Việt in VnDOCR 4.0 của Viện
Công nghệ Thông tin Hà Nội có thể nhận dạng được các tài liệu chứa hình ảnh,
bảng và văn bản tiếng Việt với độ chính xác trên 98%, ). Tuy nhiên trên thế giới
cũng như ở Việt Nam, bài toán 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 vì nó phụ
thuộc quá nhiều 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 tinh thần của từng người viết. Đặc biệt đối với việc nghiên cứu nhận dạng chữ
viết tay tiếng Việt lại càng gặp nhiều khó khăn hơn do bộ ký tự tiếng Việt có thêm
phần dấu, rất dễ nhầm lẫm với các nhiễu. Vì vậy, đến thời điểm này có rất ít công
trình công bố chính thức về các kết quả nghiên cứu nhận dạng chữ viết tay tiếng
Việt. Điều này chính là động lực thúc đẩy luận án cố gắng nghiên cứu để đề xuất
các giải pháp hữu hiệu cho bài toán nhận dạng chữ viết tay tiếng Việt.

10
Mục tiêu của luận án
Trong những năm gần đây, máy véc tơ tựa (SVM – Support Vector Machines)
được biết đến như một hướng tiếp cận phân lớp hiệu quả và đã được áp dụng thành
công trong nhiều ứng dụng thực tiễn. Vì vậy, mục tiêu của luận án là nghiên cứu
phương pháp máy véc tơ tựa để ứng dụng vào bài toán nhận dạng chữ viết tay rời
rạc (isolated handwritten character recognition). Từ nay về sau, trong luận án này
sẽ sử dụng cụm từ viết tắt SVM thay cho thuật ngữ máy véc tơ tựa.
Phạm vi nghiên cứu
Bài toán nhận dạng chữ viết tay hiện nay vẫn chưa đạt được nhiều kết quả khả
quan bởi những thách thức sau:
Với mỗi người viết khác nhau, chữ viết có độ nghiêng khác nhau (nhiều/ít,
trái/phải ).
•
Khoảng cách giữa các kí tự và các dấu trong cùng một văn bản thường
khác nhau nên rất khó tách được các ký tự, các dấu.
•
Cùng một kí tự trong văn bản do một người viết nhiều khi cũng có độ rộng,
hẹp, cao, thấp khác nhau
•
Luận án giới hạn phạm vi nghiên cứu trong khuôn khổ chữ Việt viết tay rời rạc.
Chữ viết tay rời rạc ở đây được hiểu là các ký tự viết tay tách biệt, giữa phần dấu
và phần chữ phải tách rời. Bài toán đặt ra là xây dựng một mô hình hiệu quả cho
việc nhận dạng chữ Việt viết tay rời rạc.
Những đóng góp mới của luận án
Đề xuất mô hình hiệu quả cho bài toán nhận dạng chữ Việt viết tay rời rạc

dựa trên cơ sở phân lớp SVM
.

Đề xuất một giải pháp để tăng tốc độ nhận dạng chữ Việt viết tay rời rạc trên cơ
sở rút gọn số chiều của các véc tơ đặc trưng đầu vào và áp dụng phương pháp
tập thu gọn để giảm thiểu số véc tơ tựa nhằm tăng tốc độ phân lớp của SVM.



11
Đề xuất một phương pháp trích chọn đặc trưng hiệu quả cho bài toán nhận dạng
chữ viết tay rời rạc theo ý tưởng của phép biến đổi wavelet Haar và chứng minh
được tính bất biến của đặc trưng theo phép biến đổi wavelet đối với ảnh ký tự
đầu vào.


Bố cục của luận án
Luận án được phân thành ba chương với cấu trúc như sau:
Chương 1: Tổng quan về nhận dạng chữ viết tay.
Chương này giới thiệu tổng quan về tình hình nghiên cứu trong lĩnh vực nhận
dạng chữ viết tay, mô hình tổng quát của một hệ nhận dạng chữ viết tay và một số
phương pháp nhận dạng có thể áp dụng vào bài toán nhận dạng chữ viết tay.
Chương 2: Máy véc tơ tựa (Support Vector Machines – SVM).
Chương này nghiên cứu sâu về lý thuyết SVM bao gồm: SVM tuyến tính, SVM
phi tuyến, không gian đặc trưng và hàm nhân, lý thuyết chiều Vapnik –
Chervonenkis (VC), các thuật toán huấn luyện SVM và áp dụng SVM vào bài toán
nhận dạng chữ viết tay rời rạc với một số kết quả thực nghiệm trên các tập dữ liệu
chữ số viết tay như USPS, MNIST.
Chương 3: Áp dụng máy véc tơ tựa vào bài toán nhận dạng chữ Việt viết tay rời
rạc.
Chương này trình bày
một số phương pháp trích chọn đặc trưng hiệu quả đối với
chữ viết tay,
đề xuất một mô hình hiệu quả cho bài toán nhận dạng chữ Việt viết tay
rời rạc và đề xuất phương án cải tiến tốc độ nhận dạng bằng cách
thu gọn số chiều
của véc tơ đặc trưng đầu vào và thu gọn số véc tơ tựa nhằm tăng tốc độ phân lớp của
các SVM.

Cuối cùng là phần kết luận và hướng nghiên cứu của luận án.



12

CHƯƠNG 1: TỔNG QUAN VỀ NHẬN DẠNG CHỮ VIẾT TAY

Chương này giới thiệu khái quát về lĩnh vực nhận chữ viết, sơ đồ tổng quát của
một hệ nhận dạng chữ viết tay và cuối cùng là phần tổng hợp các phương pháp
nhận dạng được áp dụng trong lĩnh vực nhận dạng chữ viết tay.
1.1. GIỚI THIỆU
Nhận dạng chữ là lĩnh vực được nhiều nhà nghiên cứu quan tâm và cho đến nay
lĩnh vực này cũng đã đạt được nhiều thành tựu lớn lao cả về mặt lý thuyết lẫn ứng
dụng thực tế. Lĩnh vực nhận dạng chữ được chia làm hai loại: Nhận dạng chữ in và
nhận dạng chữ viết tay.
Đến thời điểm này, nhận dạng chữ in đã được giải quyết gần như trọn vẹn. Tuy
nhiên, nhận dạng chữ viết tay vẫn đang là vấn đề thách thức lớn đối với các nhà
nghiên cứu. Nhận dạng chữ viết tay được phân ra làm hai loại: nhận dạng chữ viết
tay on-line (trực tuyến) và nhận dạng chữ viết tay off-line (ngoại tuyến).
Nhận dạng chữ viết tay on-line được thực hiện trên cơ sở lưu lại các thông tin
về nét chữ như thứ tự nét viết, hướng và tốc độ của nét viết trong quá trình nó đang
viết. Đây chính là cơ sở để máy tính nhận diện được các chữ cái, do đó việc nhận
dạng không gặp quá nhiều khó khăn. Một trong những sản phẩm nhận dạng chữ
viết tay trực tuyến tiêu biểu nhất là hệ thống nhận dạng chữ viết tay rời rạc trực
tuyến trên một trạm làm việc của IBM do H.S.M.Beigi, C.C.Tapert, M.Ukeison và
C.G.Wolf ở phòng thực hành Watson IBM cài đặt [6]. Ngược lại, đối với nhận
dạng chữ viết tay off-line, dữ liệu đầu vào là ảnh văn bản được quét vào nên việc
nhận dạng có độ khó cao hơn nhiều so với nhận dạng chữ viết tay on-line. Do dữ
liệu đầu vào là ảnh văn bản nên nhận dạng chữ viết tay off-line và nhận dạng chữ in
còn được gọi chung là nhận dạng chữ quang học (OCR - Optical Character
Recognition). Cho đến nay, việc giải bài toán nhận dạng chữ viết tay off-line vẫn

13
Khó khăn lớn nhất khi nghiên cứu bài toán nhận dạng chữ viết tay là sự biến
thiên quá đa dạng trong cách viết của từng người. Cùng một người viết nhưng
đôi khi cũng có nhiều sự khác biệt trong cách viết tuỳ thuộc vào từng ngữ cảnh,
kiểu viết của một người cũng có thể thay đổi theo thời gian hoặc theo thói
quen Điều này gây ra nhiều trở ngại trong việc trích chọn đặc trưng cũng như
lựa chọn mô hình nhận dạng.
Các kiến thức cần thiết để nghiên cứu về lĩnh vực nhận dạng chữ viết tay tương
đối rộng, có liên quan đến nhiều lĩnh vực khác nhau. Sau đây là một số lĩnh vực và
mối liên hệ của chúng đối với nhận dạng chữ viết tay:
Xử lý ảnh (Image Processing): Các kỹ thuật xử lý ảnh được sử dụng trong
các giai đoạn tiền xử lý, tách chữ và trích chọn đặc trưng. Chẳng hạn như
các thuật toán khử nhiễu, tìm xương, phát hiện biên, phân vùng ảnh

Học máy (Machine Learning): được sử dụng trong giai đoạn huấn luyện và
nhận dạng, chẳng hạn như các mạng nơ ron nhân tạo, SVM,

Lý thuyết nhận dạng (Pattern Recognition): sử dụng các phương pháp luận
phân lớp sử dụng trong công đoạn huấn luyện và nhận dạng.

Xác suất thống kê và toán ứng dụng: lý thuyết xác suất đóng vai trò rất quan
trọng trong các phương pháp phân lớp thống kê như mô hình Markov ẩn,
phương pháp Bayes, k-láng giềng gần nhất, còn đối với phương pháp phân
lớp SVM thì kết hợp cả lý thuyết thống kê lẫn toán tối ưu, đặc biệt là bài
toán quy hoạch toàn phương.

Ngôn ngữ học và ngôn ngữ học tính toán (Linguistic and Computational
Linguistic): Các kiến thức về ngữ pháp đóng vai trò quan trọng trong công
đoạn hậu xử lý, nâng cao độ chính xác cho các hệ thống nhận dạng chữ viết.

Hiện nay, trên thế giới cũng như ở Việt Nam, các kết quả thu được từ việc
nghiên cứu nhận dạng chữ viết tay vẫn còn hạn chế hoặc chỉ ứng dụng được trong

14

Xem chi tiết: Nhận dạng chữ