BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC DUY TÂN
 NGUYỄN MINH ĐỨC

NGHIÊN CỨU PHƯƠNG PHÁP MÁY VÉCTƠ
TỰA TRONG NHẬN DẠNG CHỮ VIẾT TAY
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH ĐÀ NẴNG, 2012



ii

LỜI CẢM ƠN
Tôi xin được gửi lời cám ơn sâu sắc tới TS. Phạm Anh Phương về những chỉ
dẫn khoa học và tận tình hướng dẫn, định hướng cho tôi trong suốt quá trình thực
hiện Luận văn.
Tôi xin chân thành cám ơn các Thầy, Cô trong Khoa Sau đại học, những người
đã quan tâm tổ chức, chỉ đạo và trực tiếp giảng dạy trong suốt quá trình học tập của
chúng tôi.
Tôi xin chân thành cám ơn bạn bè, đồng nghiệp đã có nhiều ý kiến quan trọng
giúp tôi hoàn thiện tốt hơn luận văn của mình.
Tôi xin gửi lời cảm ơn tới gia đình, anh chị em và những người thân đã quan
tâm, giúp đỡ và động viên để tôi yên tâm và hoàn thành được luận văn.
Đà Nẵng, tháng 6 năm 2012 Nguyễn Minh Đức iii

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu và
kết quả nghiên cứu trong luận văn này là trung thực và không trùng lặp với các đề
tài khác.
Học viên thực hiện luận văn
1.3.3. Sử dụng phương pháp máy véc tơ tựa 13
1.4. Mô hình tổng quát của một hệ nhận dạng 14
1.4.1. Mô hình tổng quát 14
1.4.2. Tiền xử lý 15
1.4.2.1. Nhị phân hóa ảnh 16
1.4.2.2. Hiệu chỉnh kích thước ảnh 16
1.4.2.3. Khử nhiễu 17
1.4.2.4. Làm trơn biên chữ 18
1.4.2.5. Làm dày chữ 19
1.4.2.6. Làm mảnh chữ 20
1.4.2.7. Xoay văn bản 20
1.4.3. Tách chữ 20
1.4.4. Trích chọn đặc trưng 21
1.4.4.1. Đặc trưng thống kê 22
1.4.4.2. Đặc trưng hình học và hình thái 24
1.4.4.3. Biến đổi toàn cục và triển khai chuỗi 24
1.4.5. Huấn luyện và nhận dạng 25 v

1.4.6. Hậu xử lý 25
CHƯƠNG 2. PHƯƠNG PHÁP MÁY VÉCTƠ TỰA 27
2.1. Cơ sở lý thuyết 27
2.1.1. Giới thiệu bài toán phân lớp nhị phân 27
2.1.2. Máy SVM tuyến tính 28
2.1.2.1. SVM trong trường hợp tập mẫu phân hoạch tuyến tính được 28
2.1.2.2. SVM tuyến tính trong trường hợp tập mẫu không phân hoạch tuyến
tính được 30
2.1.3. Máy SVM phi tuyến 35

Tài liệu tiếng Anh 57
viDANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT

Ký hiệu Thuật ngữ
SVM
Support Vector Machine – (Máy Vectơ tựa)
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ỳ
SMO
Sequential Minimal Optimization – (Thuật toán cực tiểu tuần tự)
OVO
One – versus – One – (Một chống một)
OVR
One – versus – Rest – (Một chống phần còn lại)
USPS
United States Postal service
ANN
Artificial Neural Network (Mạng nơron nhân tạo)
HMM
Hiden Markov Models – (Mô hình Markov ẩn)
MLP
MultiLayer Perceptron
kNN

Hình 1-5 Nhị phân hóa ảnh 16
Hình 1-6 Chuẩn hóa kích thước ảnh các ký tự “A” và “D” 17
Hình 1-7 Nhiễu đốm và nhiễu vệt đen dài 17
Hình 1-8 Làm trơn biên chữ bằng kỹ thuật Dineen và Unger 19
Hình 1-9 Xác định khoảng phân cách giữa hai ký tự và hai từ 21
Hình 1-10 Phân vùng ký tự A 23
Hình 1-11 Trích chọn theo phép chiếu theo hai chiều trên ký tự a 23
Hình 1-12 Trích chọn theo chu tuyến của ký tự a 24
Hình 2-1 Các siêu phẳng H1, H2 phân cách giữa hai lớp 27
Hình 2-2 Siêu phẳng tách tuyến tính 28
Hình 2-3 Không thể phân hoạch tập mẫu trên bằng một siêu phẳng 30
Hình 2-4 Một mặt phân chia phi tuyến có thể trở thành một siêu phẳng trong không
gian lớn hơn. 35
Hình 3-1 Sơ đồ bỏ phiếu cho bài toán phân 5 lớp 43
Hình 3-2 Bài toán phân bốn lớp theo chiến lược OVR 44
Hình 3-3 Mô hình nhận dạng chữ viết tay rời rạc 45
Hình 3-4 Chuẩn hóa kích thước ảnh 46
Hình 3-5 Trích chọn đặc trưng nhị phân 47
Hình 3-6 Trích chọn đặc trưng ma trận trọng số vùng 48
Hình 3-7 Các mẫu chữ số viết tay trích từ tập dữ liệu MNIST 51
Hình 3-8 Các mẫu chữ số viết tay trích từ tập dữ liệu USPS 52 1
MỞ ĐẦU

1. Lý do chọn đề tài
Đã từ lâu chiếc máy tính trở thành công cụ không thể thiếu trong hầu hết các
lĩnh vực đời sống xã hội, máy tính hỗ trợ từng cá nhân cũng như cơ quan doanh
nghiệp phát triển. Con người không ngừng nghiên cứu để tăng cường sức mạnh của

2. Mục đích nghiên cứu
- Nghiên cứu về phương pháp phân lớp SVM áp dụng cho bài toán nhận dạng
chữ viết tay.
- Cài đặt demo dạng chữ viết tay rời rạc với độ chính xác chấp nhận được.
3. Đối tượng và phạm vi nghiên cứu của đề tài
Đối tượng nghiên cứu của đề tài:
- Quy trình nhận dạng chữ viết tay ngoại tuyến.
- Phương pháp phân lớp máy Véctơ tựa.
Phạm vi nghiên cứu của đề tài:
- Nhận dạng chữ viết tay rời rạc trên các tập dữ liệu chữ số viết tay MNIST và
USPS.
- Trong phương pháp SVM chọn thuật toán huấn luyện cực tiểu tuần tự -SMO.
- Đối với SVM đa lớp, nghiên cứu hai chiến lược OVO (One-vs-One) và OVR
(One-vs-Rest).
4. Phương pháp nghiên cứu
- Tìm kiếm, đọc hiểu các tài liệu, các thông tin liên quan đến đề tài.
- Sử dụng thư viện mã nguồn mở LIBSVM để xây dựng ứng dụng.
- Sử dụng các tập dữ liệu chữ số viết tay điển hình như USPS va MNIST cho
việc kiểm thử bộ nhận dạng và dựa vào kết quả thực nghiệm để đánh giá chất
lượng bộ nhận dạng.
3
5. Kết cấu của luận văn
Nội dung của cuốn luận văn được trình bày trong ba chương.
Chương 1. Tổng quan về nhận dạng chữ viết: Giới thiệu về chữ in và chữ
viết tay, trong đó tập trung vào bài toán đặt nhận dạng chữ viết tay ngoại tuyến và
lựa chọn phương pháp nhận dạng. Đồng thời giới thiệu tổng quan về một hệ nhận
dạng với tất cả các khâu từ tiền xử lý, trích chọn đặc trưng cho tới khâu huấn luyện,

quyết bài toán toán nhận dạng chữ viết tay vẫn tiếp tục là một đề tài thách thức với
các nhà nghiên cứu.
Có hai loại nhận dạng chữ viết tay:
- Thứ nhất là nhận dạng chữ viết tay ngoại tuyến (off-line handwriting
recognition): chương trình sẽ thông dịch các kí tự, các chữ hay các đoạn văn được
viết trên các mẫu giấy hoặc các các bề mặt khác mà chúng ta có thể thu thập thông
tin về chúng thông qua hình ảnh thu được từ các bề mặt bằng cách chụp lại hình
ảnh. 5
- Thứ hai là nhận dạng chữ viết tay trực tuyến (online handwriting
recognition): nhận dạng ký tự hoặc chữ viết dựa trên thông tin thu được trong thời
gian thực ngay lúc người dùng thực hiện hành động viết, những thông tin đó là tốc
độ viết, áp lực khi viết và hướng viết.
Đối với phương pháp nhận dạng, hiện nay có khá nhiều phương pháp, cổ
điển nhất là nhận dạng dựa vào đặc trưng cấu trúc chữ, phương pháp đối sánh mẫu,
K láng giềng gần nhất, hay một số phương pháp tiên tiến như sử dụng mạng Nơron,
mô hình Markov ẩn, hay sử dụng máy vector tựa…
1.2. Các phương pháp nhận dạng cổ điển
1.2.1. Nhận dạng dựa vào đặc trưng cấu trúc chữ
Cách tiếp cận của phương pháp này dựa vào việc mô tả đối tượng nhờ một số
khái niệm biểu thị đối tượng cơ sở trong ngôn ngữ tự nhiên. Để mô tả đối tượng
người ta dùng một số dạng nguyên thuỷ như đoạn thẳng, cung,… Mỗi đối tượng
được mô tả như một sự kết hợp của các dạng nguyên thuỷ. Chẳng hạn một hình chữ
nhật được định nghĩa gồm bốn đoạn thẳng vuông góc với nhau từng đôi một. Các
ký tự chữ viết thường bao gồm các đoạn thẳng và các dường cong. Tất cả các đoạn
thẳng hoặc đường cong đều có thể mở rộng theo một hướng nhất định. Một đường
cong có thể tạo thành một vòng lặp. Do đó một ký tự chữ viết tay đều có thể mô tả
bằng việc sử dụng các loại nguyên thủy khác nhau của đường thẳn, đường cong

- V
t
là bộ ký hiệu kết thúc. V
t
= {line, up, down, loop, dot, ‘{‘, ‘}’, ‘,’, 0, 1, 2,
3, 4, 5, 6, 7}, với 0 đến 7 biểu diễn cho các giá trị hướng trong mã chuỗi
Freeman (Hình 1-1).

Hình 1-1 Mã Freeman
- V
n
là bộ ký hiệu không kết thúc. V
n
= { Character, StrokeSet, Stroke,
PrimitiveSet, Primitive, LineType, Direction}
- P là luật sản xuất.
P = {
Character  { StrokeSet}
StrokeSet  Stroke 7
StrokeSet  Stroke, StrokeSet
Stroke  { PrimitiveSet}
PrimitiveSet  Primitive
PrimitiveSet  Primitive, PrimitiveSet
Primitive  { LineType, Direction}
Primitive  loop
Primitive  dot
LineType  line | up | down

chọn một số điểm chạc sao cho chúng tách chữ thành các nét không cắt nhau. Như
vậy, để lấy nét, ta xuất phát từ điểm chạc này theo chiều kim đồng hồ để đến điểm
chạc kia, đồng thời xoá luôn nét đó ra khỏi ảnh, không xoá điểm chạc (vì nó là điểm
chung), điểm chạc chỉ được xoá khi không còn cạnh nào xuất phát từ nó. Kết quả ta
sẽ có một dãy các nét làm đặc trưng cơ bản của chữ. Để tách các nét của chữ ta thực
hiện các bước như sau: đánh dấu các điểm chạc, xác định điểm xuất phát, xác định
nét xuất phát, tách các nét tiếp theo.
Bước 3: Trích chọn các đặc trưng cấu trúc xương của chữ.
Với một chữ, sau khi qua quá trình làm mảnh và tách nét ta sẽ thu được một
dãy các nét có thứ tự. Mỗi nét đặc trưng bởi cặp chỉ số đầu và cuối tương ứng với
thứ tự của điểm chạc đầu và điểm chạc cuối. Đặc trưng này tương đối ổn định với
một chữ, do đó đặc trưng này được dùng làm đặc trưng “cứng” của chữ. Nghĩa là
hai chữ được gọi là cùng lớp nếu giống nhau về đặc trưng xương. Nhờ tính “cứng” 9
của xương ta có thể phân lớp và thực hiện tìm kiếm một cách hiệu quả. Chỉ số các
điểm chạc được đánh số theo thứ tự duyệt các đỉnh và bắt đầu từ đỉnh xuất phát.
Điều này làm cho cấu trúc xương của các thành phần liên thông là độc lập với nhau.
Nếu khi thêm một thành phần liên thông mới như nhiễu lớn thì không ảnh hưởng
đến cấu trúc của các thành phần liên thông khác. Một điểm chạc 4 có thể phân thành
hai điểm chạc 3 và một nét nhỏ nối giữa chúng. Điều này khiến một cấu trúc chữ có
thể biến đổi thành nhiều cấu trúc khác nhau, do vậy ta phải nhập các điểm chạc gần
nhau thành một điểm (không nhập điểm mút).
Bước 4: Xây dựng cây tìm kiếm.
Dựa vào đặc trưng về cấu trúc xương và cấu trúc biên (chỉ số của các nét
xương và chỉ số của các nét tạo bởi các điểm uốn của biên - các nét này rất ổn định
đối với ký tự), ta sẽ phân tập mẫu học thành các lớp.
Quá trình tìm kiếm để phân lớp được tiến hành qua hai bước:
- Xác định lớp tương ứng với mẫu vào

b
) giữa hai đặc trưng đó.
 Nhận dạng: với mỗi mẫu vào là x chưa biết, ta trích chọn đặc trưng tương
ứng F
x
. Tìm trong cơ sở dữ liệu đặc trưng F
b
L “gần giống” với F
x
nhất
theo nghĩa:
)Fd(F,min)F,d(F
x
LF
xb



Khi đó mẫu x được nhận dạng là mẫu b trong cơ sở dữ liệu.
Nhận xét: Phương pháp đối sánh mẫu có đặc điểm là kích thước cơ sở dữ liệu
lớn và tốc độ nhận dạng không nhanh.
1.3. Sử dụng các phương pháp máy học tiên tiến
1.3.1. Sử dụng mạng Nơron
Mạng Nơron nhân tạo (Artificial Neural Network: ANNs) là sự tái tạo
bằng những chức năng của hệ thần kinh con người với vô số các Nơron được liên
kết truyền thông với nhau qua mạng. Giống như con người, ANNs được học
bởi kinh nghiệm, lưu những kinh nghiệm đó và sử dụng trong những tình huống
phù hợp.
Mạng Nơ ron nhân tạo được nghiên cứu từ những năm 40, với những nghiên
cứu của McCulloch và Pitts. Các ông đã chứng tỏ rằng mạng Nơron có thể dùng để

thẳng và mạng Kohonen thuộc nhóm mạng lang truyền ngược. Mạng Perceptron đa
lớp được đề xuất bởi Rosenblatt được nhiều tác giả sử dụng trong các hệ nhận dạng
chữ.
Trong kỹ thuật nhận dạng ký tự, mạng Nơron tỏ ra ưu thế hơn các phương
pháp truyền thống ở chỗ không tốn thời gian cho thủ tục tiền xử lý, làm mảnh ký tự,
trích trọn đặc trưng… Mặt khác các phương pháp ra quyết định trong nhận 12
dạng truyền thống được cài đặt tĩnh trong chương trình, khi muốn bổ sung thêm
các mẫu học mới phải thiết kế lại chương trình. Trong khi với mạng Nơron, chỉ cần
cung cấp một tập mẫu vào ra của dữ liệu mới cho pha huấn luyện là có thể bổ sung
vào “bộ nhớ mạng” những kiểu dữ liệu mới mà không ảnh hưởng đến cấu trúc
chương trình ban đầu. [3]

Hình 1-3 Mạng perceptron đa lớp
Hạn chế của mạng Nơron là tính chậm và xác xuất không cao, không có quy
tắc tổng quát để xác định cấu trúc mạng và các tham số học tối ưu cho một (lớp) bài
toán nhất định. Tiêu chuẩn thu thập cơ sở dữ liệu huấn luyện còn khắt khe. Do đó,
để hệ thống có thể ứng dụng trong thực tế cần phải nới lỏng hơn nữa các tiêu chuẩn
này.
1.3.2. Sử dụng mô hình Markov ẩn
Từ mấy thập kỉ trước, các mô hình Markov ẩn (HMM - Hiden Markov
Models) được tư duy như một sự mở rộng của các kĩ thuật quy hoạch động, nó trở
thành cách tiếp cận tiêu biểu cho bài toán nhận dạng tiếng nói tự động. HMM là
một kĩ thuật mô hình hóa tham số, trái ngược với giải thuật quy hoạch động không
có tham số.
HMM là một mô hình xác suất hữu hạn trạng thái theo kiểu phát sinh tiến trình
bằng cách định nghĩa xác suất liên kết trên các chuỗi quan sát. Mỗi chuỗi quan sát
được sinh ra bởi một chuỗi các phép chuyển trạng thái, bắt đầu từ trạng thái khởi

Do đó SVM là một thuật toán phân loại nhị phân
( ) 14
Mô hình SVM đầu tiên được thiết kế cho bài toán phân lớp nhị phân. Ý
tưởng chính của mô hình này là tìm một siêu phẳng phân cách để tách hai lớp sao
cho khoảng cách (margin) giữa hai lớp đó đạt cực đại. Khoảng cách này được xác
định bởi các véc tơ hỗ trợ (SV – Support Vector), các SV này được lọc ra từ tập
mẫu huấn luyện bằng cách giải một bài toán tối ưu lồi.
Tuy nhiên, trong nhiều ứng dụng thời gian thực, chẳng hạn như nhận dạng
chữ viết tay thì buộc phải giải một bài toán phân nhiều lớp. Vì vậy các mô hình
SVM đa lớp cũng được nghiên cứu và phát triển để đáp ứng với các dạng bài toán
phân nhiều lớp. Có một số hướng tiếp cận để giải bài toán SVM đa lớp, nhưng hầu
hết đều được phát triển từ bài toán phân lớp nhị phân.[4]
1.4. Mô hình tổng quát của một hệ nhận dạng
1.4.1. Mô hình tổng quát
Về cơ bản, một hệ nhận dạng chữ bao gồm 5 khối công việc chính sau:
 Khối tiền xử lý.
 Khối phân đoạn, tách dòng, tách chữ.
 Khối trích chọn đặc trưng.
 Khối huấn luyện và nhận dạng.
 Khối hậu xử lý. 15

Hình 1-4 Mô hình tổng quát của một hệ nhận dạng chữ viết
1.4.2. Tiền xử lý
Đây là giai đoạn rất quan trọng, ảnh hưởng trực tiếp độ chính xác của các