Đại học Thái Nguyên
trờng đại học công nghệ thông tin và truyền thông

nguyễn quang huy

nghiên cứu phơng pháp nhận dạng chữ viết
tay hạn chế bằng mô hình svm
(support vector machines)

LUN VN THC S KHOA HC MY TNH

Thỏi Nguyờn - 2014


Đại học Thái Nguyên
trờng đại học công nghệ thông tin và truyền thông

nguyễn quang huy

nghiên cứu phơng pháp nhận dạng chữ viết tay
hạn chế bằng mô hình svm
(support vector machines)
Chuyên ngành: KHOA HC MY TNH
Mã số: 60 48 01

LUN VN THC S KHOA HC MY TNH
Ngời hớng dẫn khoa học: PGS-TS. NGễ QUC TO

Thỏi Nguyờn - 2014




DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Thuật ngữ,
chữ viết tắt
SVM
MMH
HMM
Kernel

Giải thích
Support Vector Machine (Máy véc tơ hỗ trợ)
Maximum Marginal Hyperplane (Siêu phẳng có biên độ lớn nhất)
Markov Model (Mô hình Markov ẩn)
Hàm nhân
Bộ mẫu chữ số viết tay NIST - Viện Công nghệ và Tiêu chuẩn Quốc

MNIST

gia Hoa Kỳ (National Institute of Standard and Technology of the

NN
OCR
QP
USPS
VC

United States)
Neuron Network (Mạng nơ ron)
Optical Character Recognition (nhận dạng chữ quang học)
Quadratic Programing (quy hoạch toàn phương)

Hình 2.6. Đường biểu diễn H1 và H2. Đường màu đỏ là khoảng cách Euclidean của
hai điểm 1 và 2, đường màu xanh là khoảng cách Euclidean nhỏ nhất...........................30
Hình 2.7. Các support vector trong SVM.........................................................................31
Hình 2.8. Trường hợp trên không gian 2 chiều không thể vẽ một đường thẳng phân
chia 2 lớp...........................................................................................................................35
Hình 2.9. Bước 1- Học để xây dựng mô hình phân lớp...................................................37


7

Hình 2.10. Bước 2 - Kiểm tra và đánh giá........................................................................38
Hình 2.11. Mô hình nhận dạng chữ viết tay rời rạc..........................................................45
Hình 2.12. Trích chọn đặc trưng trọng số vùng................................................................45
Hình 2.13. Kiến trúc của hệ nhận dạng chữ viết tay tiếng Việt.......................................48
Hình 2.14. Chuẩn hóa ảnh: (a) Ảnh gốc, (b) Xác định các vùng liên thông và đánh thứ
tự các vùng liên thông.......................................................................................................49
Hình 2.15. Chuẩn hóa các vùng liên thông.......................................................................49
Hình 2.16. Quá trình trích chọn đặc trưng........................................................................51
Hình 3.1. Các bước cơ bản của quá trình nhận dạng văn bản bằng mô hình SVM.........55
Hình 3.2. Các mẫu chữ số viết tay trích từ tập các tập dữ liệu USPS và MNIST...........59
Hình 3.3. Giao diện chương trình.....................................................................................61
Hình 3.4. Hộp thoại tiền xử lý..........................................................................................61
Hình 3.5. Hộp thoại trích chọn đặc trưng.........................................................................62
Hình 3.6. Hộp thoại lưu file mô hình huấn luyện.............................................................62
Hình 3.7. Hộp thoại chọn file ảnh cần nhận dạng............................................................63
Hình 3.8. Hộp thoại thông báo kết quả nhận dạng...........................................................63


8


9

MỤC LỤC


10

Chương 1. GIỚI THIỆU VỀ CHỮ VIẾT VÀ NHẬN DẠNG CHỮ VIẾT
1.1. Trình bày về lịch sử của nhận dạng chữ viết tay
Ngày nay khoa học công nghệ phát triển mạnh cũng không ngoài mục đích khác
là để đáp ứng nhu cầu ngày càng cao của con người. Mỗi quốc gia đều phải có ít nhất
một ngôn ngữ, chữ viết để giao tiếp, từ năm 1922 khái niệm nhận dạng chữ đã được
hình thành cho đến năm 1950, 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 [4].
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 online. 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ữ. Từ năm
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
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
đã 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ữ.
Từ 1990 đến nay, các kỹ thuật nhận dạng kết hợp với các phương pháp luận trong lĩnh
vực học máy (Machine Learning) được áp dụng rất hiệu quả, một số công cụ học máy
hiệu quả như mạng Nơ ron, mô hình Markov ẩn và SVM (Support Vector Machines)
…
1.2. Giới thiệu các hướng tiếp cận trong việc nhận dạng chữ viết tay
1.2.1. 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à chất lượng nhập

nay, phần mềm MarkRead cũng đã có tích hợp đặc trưng nhận dạng chữ viết tay hạn
chế, nhưng kết quả mới chỉ dừng lại ở phòng thí nghiệm. 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.
Việc xây dựng hệ thống có thể được mô tả trực quan bằng sơ đồ hình 1.1. Trong
hệ thống này phần chúng ta cần tập trung quan tâm nhất là phần hệ huấn luyện và nhận
dạng. Chúng ta sẽ sử dụng mô hình SVM trong việc huấn luyện và nhận dạng đó.


12

Ảnh văn bản quét vào

Tiền xử lý

Tách chữ

Văn bản được nhận dạng
Hậu xử lý

Trích chọn đặc trưng

Huấn luyện và nhận dạng

Hình 1.1. Các giai đoạn trong quá trình xử lý và nhận dạng ảnh
Vì vậy muốn xây dựng được hệ thống có khả thi thì chúng ta cần phải tìm hiểu
về SVM nói chung và ứng dụng của SVM nói riêng trong việc nhận dạng chữ viết.
1.3. Tiền xử lý
Giai đoạn này góp phần làm tăng độ chính xác phân lớp của hệ thống nhận dạng,


Hình 1.4. Chuẩn hóa kích thước ảnh các ký tự “A” và “P”.
Việc chuẩn hóa kích thước ảnh dựa trên việc xác định trọng tâm ảnh, sau đó xác
định khoảng cách lớn nhất từ tâm ảnh đến các cạnh trên, dưới, trái, phải của hình chữ
nhật bao quanh ảnh. Thông qua khoảng cách lớn nhất đó, có thể xác định được một tỷ
lệ co, giãn của ảnh gốc so với kích thước đã xác định, từ đó hiệu chỉnh kích thước ảnh
theo tỷ lệ co, giãn này. Như vậy, thuật toán chuẩn hóa kích thước ảnh luôn luôn đảm
bảo được tính cân bằng khi co giãn ảnh, ảnh sẽ không bị biến dạng hoặc bị lệch.


14

1.3.4. Làm trơn biên chữ
Đôi khi do chất lượng quét ảnh quá xấu, các đường biên của chữ không còn giữ
được dáng điệu trơn tru ban đầu mà hình thành các đường răng cưa giả tạo. Trong các
trường hợp này, phải dùng các thuật toán làm trơn biên để khắc phục [12].

(a)

(b)

Hình 1.5. (a) Ảnh gốc, (b) Ảnh sau khi được làm trơn biên.
1.3.5. Làm đầy chữ
Chức năng này được áp dụng với các ký tự bị đứt nét một cách ngẫu nhiên. Ảnh
đứt nét gây khó khăn cho việc tách chữ, dễ bị nhầm hai phần liên thông của ký tự
thành hai ký tự riêng biệt, tạo nên sai lầm trong quá trình nhận dạng.
1.3.6. Làm mảnh chữ
Đây là một bước quan trọng nhằm phát hiện khung xương của ký tự bằng cách
loại bỏ dần các điểm biên ngoài của các nét. Tuy nhiên, quá trình làm mảnh chữ rất
nhạy cảm với việc khử nhiễu.

trong văn bản thường rất khó khăn. Trong trường hợp này, không thể tìm đường phân
cách theo nghĩa thông thường mà phải hiểu là đường phân cách với số điểm cắt hai
dòng là ít nhất. Khi đó phải xây dựng lược đồ sáng của các dòng chữ, từ đó các đoạn
thấp nhất trên lược đồ chính là đường phân cách cần tìm (hình 1.8 và 1.9).


16

Hình 1.9. Xác định khoảng cách giữa hai kí tự và giữa hai từ dựa trên histogram
theo chiều thẳng đứng của dòng chữ.
1.5. Trích chọn đặc trưng
Trích chọn đặc trưng đóng vai trò cực kỳ quan trọng trong một hệ thống nhận
dạng. Trong trường hợp đơn giản nhất, ảnh đa cấp xám hoặc ảnh nhị phân được sử
dụng cho việc nhận dạng. Tuy nhiên, trong hầu hết các hệ nhận dạng, để giảm độ phức
tạp và tăng độ chính xác của các thuật toán phân lớp thì đòi hỏi các đặc trưng được
trích chọn phải rút gọn lại càng nhỏ càng tốt nhưng vẫn phải đảm bảo được thông tin
của ký tự. Với mục tiêu này, một tập các đặc trưng được trích chọn cho mỗi lớp sao
cho có thể phân biệt được với các lớp khác. Có hàng trăm phương pháp trích chọn đặc
trưng cho ảnh văn bản, nhưng chung quy lại, các phương pháp này được gom lại thành
ba nhóm chính sau.
1.5.1. Biến đổi toàn cục và khai triển chuỗi
Một tín hiệu liên tục thường chứa nhiều thông tin và chúng có thể sử dụng làm
các đặc trưng cho mục đích phân lớp. Các đặc trưng được trích chọn cũng có thể đúng
đối với việc xấp xỉ các tín hiệu liên tục thành các tín hiệu rời rạc. Một cách để biểu
diễn một tín hiệu là sử dụng một tổ hợp tuyến tính của một dãy các hàm đơn giản hơn.
Các hệ số của tổ hợp tuyến tính cung cấp một tri thức giải mã vừa đủ, chẳng hạn như
các phép biến đổi hoặc khai triển chuỗi. Một số biến dạng khác như các phép dịch
chuyển và phép quay là bất biến dưới các phép biến đổi toàn cục và khai triển chuỗi.
Sau đây là một số phương pháp biến đổi và khai triển chuỗi thường được áp dụng
trong lĩnh vực nhận dạng chữ:

nhưng nó được sử dụng để thu nhỏ số chiều của tập đặc trưng nhằm tăng tốc độ và
giảm thiểu độ phức tạp tính toán. Sau đây là một số đặc trưng thống kê thường dùng
để biểu diễn ảnh ký tự:


18

- Phân vùng (zoning): Khung chứa ký tự được chia thành một vài vùng chồng
nhau hoặc không chồng nhau. Mật độ của các điểm ảnh trong các vùng khác nhau
được phân tích và tạo thành các đặc trưng [6].
- Các giao điểm và khoảng cách: Một đặc trưng thống kê phổ biến là số giao
điểm giữa chu tuyến của chữ với một đường thẳng theo một hướng đặc biệt nào đó.
Trong [15], khung chứa ký tự được phân chia thành một tập các vùng theo các hướng
khác nhau và sau đó các dãy đen trong mỗi vùng được mã hóa bởi các số lũy thừa của
2. Tương tự như vậy, khoảng cách từ biên của khung chứa ảnh tới điểm đen đầu tiên
của chu tuyến chữ trên cùng một dòng quét cũng được sử dụng như những đặc trưng
thống kê [6].
- Các phép chiếu: Các ký tự có thể được biểu diễn bằng cách chiếu các giá trị
mức xám của từng điểm lên trên các dòng theo các hướng khác nhau. Các đặc trưng
này tạo ra dãy tín hiệu một chiều từ ảnh hai chiều [6].
- Đặc trưng hướng: Các ký tự bao gồm các nét chữ, các nét này là các đoạn
thẳng có hướng, các cung hoặc các đường cong. Hướng của các nét đóng vai trò quan
trọng trong việc so sánh sự khác nhau giữa các ký tự. Các ký tự được mô tả như các
véc tơ mà các phần tử của nó là các giá trị thống kê về hướng. Để trích chọn các đặc
trưng này, góc định hướng của nét chữ phải được phân chia thành một số vùng cố định
và số các đoạn của nét chữ trong mỗi vùng góc được chọn như một giá trị đặc trưng.
Vì vậy, tập các số lượng của các đoạn định hướng sẽ tạo thành một biểu đồ được gọi là
biểu đồ hướng và các đặc trưng về biểu đồ hướng có thể gọi chung là đặc trưng hướng.
Các ảnh ký tự được phân rã thành các mặt phẳng định hướng và một độ đo khoảng
cách được tính giữa các mặt phẳng đó với mẫu của mỗi lớp. Hướng nét chữ cục bộ của

- Đồ thị và cây: đầu tiên, các từ hoặc các ký tự được phân chia thành một tập các
đối tượng nguyên thủy như các nét, các điểm chạc... Sau đó, các thành phần nguyên
thủy được thay thế bằng các thuộc tính hoặc các đồ thị liên quan. Có hai loại đặc trưng
ảnh được mô tả bằng đồ thị. Loại thứ nhất sử dụng các tọa độ của hình dáng ký tự.
Loại thứ hai là một đặc trưng trừu tượng, các nút của đồ thị tương ứng với các nét chữ
và các cạnh của đồ thị tương ứng với các mối quan hệ giữa các nét chữ. Cây cũng có
thể dùng để biểu diễn các từ và các ký tự với một tập các đặc trưng theo một quan hệ
phân cấp.
Trích chọn đặc trưng hầu hết được thực hiện trên ảnh nhị phân. Tuy nhiên, việc
nhị phân hóa ảnh đa cấp xám có thể xóa đi một số thông tin quan trọng của các ký tự.


20

Trong trường hợp này, cũng có một số công trình nghiên cứu để trích chọn các đặc
trưng trực tiếp từ các ảnh đa cấp xám.
Cuối cùng, mục đích chính của việc trích chọn đặc trưng là lựa chọn một tập đặc
trưng phục vụ cho việc phân lớp sao cho hệ thống nhận dạng đạt độ chính xác cao nhất
với số lượng phần tử được trích chọn ít nhất.
1.6. Huấn luyện và nhận dạng
Đây là giai đoạn quan trọng nhất, giai đoạn này quyết định độ chính xác của hệ
thống nhận dạng. Có nhiều phương pháp phân lớp khác nhau được áp dụng cho các hệ
thống nhận dạng chữ viết tay.
1.7. Hậu xử lý
Đây là công đoạn cuối cùng của quá trình nhận dạng. Có thể hiểu hậu xử lý là
bước ghép nối các kí tự đã nhận dạng thành các từ, các câu, các đoạn văn nhằm tái
hiện lại văn bản đồng thời phát hiện ra các lỗi nhận dạng sai bằng cách kiểm tra chính
tả dựa trên cấu trúc và ngữ nghĩa của các từ, các câu hoặc các đoạn văn. Việc phát hiện
ra các lỗi, các sai sót trong nhận dạng ở bước này góp phần đáng kể vào việc nâng cao
chất lượng nhận dạng.

bộ ba = (π , A, B), trong đó π = (π1,...,πN) là vector chứa phân bố xác suất các quan sát
tại mỗi trạng thái ở thời điểm khởi tạo. Ma trận chuyển trạng thái A= (a i,j) 0 < i ≤ N, 0
< j ≤ N bao gồm các xác suất ai,j chuyển từ trạng thái Si sang trạng thái Sj. Thành phần
thứ ba là một ma trận B = (b i (ol)) 1 ≤ i ≤ N, 1 ≤ l ≤ T bao gồm các giá trị xác suất rời
rạc đối với 1 số hữu hạn các quan sát O = (o1, o2,..., oT) hoặc một vector các hàm mật
độ đối với một chuỗi liên tục các quan sát. Mỗi HMM có thể sinh ra một chuỗi các kí
hiệu đầu ra, các kí hiệu này quan sát được, chuỗi trạng thái sinh ra quan sát này là ẩn.
b. Phân lớp dựa trên mô hình mạng nơron
Mạng nơron nhân tạo (Artificial Neural Network) là một mô hình tính toán mô
phỏng theo hoạt động của bộ não và nơron sinh học của con người. Cấu trúc của một
mô hình mạng nơron bao gồm nhiều nút (đơn vị xử lý, nơron) được nối với nhau bởi
các liên kết nơron (hình 1.10).


22

Hình 1.10. Mô hình mạng nơron nhân tạo
Mỗi liên kết kèm theo một trọng số nào đó, đặc trưng cho đặc tính kích hoạt/ức
chế các nơron. Có thể xem các trọng số là để lưu giữ thông tin dài hạn trong mạng
nơron và nhiệm vụ của quá trình huấn luyện mạng là cập nhật các trọng số khi có thêm
các thông tin về các mẫu học, hay nói một cách khác là các trọng số được điều chỉnh
sao cho dáng điệu vào ra của nó mô phỏng hoàn toàn phù hợp với môi trường đang
xét.
Về lý thuyết, người ta đã chứng minh được rằng chỉ cần sử dụng mạng nơron hai
lớp truyền thẳng (gồm một lớp ẩn và một lớp ra) là đủ để giải quyết các bài toán phân
lớp trên tập dữ liệu đầu vào không khả tách tuyến tính. Thực tế cho thấy mô hình
mạng nhiều tầng truyền thẳng MLP (Multi Layer Perceptron) 3 lớp là mô hình phổ
biến, được sử dụng nhiều trong các bài toán phân lớp (Hình 1.11). Về nguyên tắc, để
giải quyết bài toán phân lớp tập dữ liệu đầu vào thành K lớp, ta sẽ xây dựng 1 mạng
nơron 3 lớp.

mô tả bởi vector trọng số

được

và một ngưỡng. Đối với một mẫu huấn luyện S n, thuật

toán SVM sẽ tìm một siêu phẳng sao cho khoảng phân cách (soft-margin) (hình 1.13)
là lớn nhất


24

Hình 1.13. a) Các lớp phân tách tuyến tính b)Siêu phẳng tối ưu và biên lề tương ứng,
các vectơ hỗ trợ
Việc tính siêu phẳng này tương đương với việc giải quyết vấn đề tối ưu sau đây:
Cực tiểu hóa:

(2.1)

Với giả thiết:

Điều kiện giả thiết thứ nhất yêu cầu tất cả các mẫu huấn luyện đều phải được
phân vào các lớp

với siêu phẳng thì

một cách đúng đắn. Nếu một mẫu huấn luyện nằm ở vị trí sai so

tương ứng sẽ ≥ 1. Như vậy,



Trong đó, mỗi mẫu huấn luyện

để tính b phải là một support vector

không nằm trên biên. Về bản chất thì SVM là một phương pháp phân lớp tuyến tính
nhưng chúng ta cũng có thể dễ ràng tổng quát hóa thuật toán này cho trường hợp phân
lớp không tuyến tính bằng cách thay thế tích vô hướng

bằng hàm nhân

. Các hàm nhân sẽ ánh xạ các điểm dữ liệu vào một không gian thuộc tính
số chiều lớn hơn (higher dimension feature space) và xác định siêu phẳng phân tách tối
ưu trong không gian đó (hình 1.14). Một số hàm nhân thường được sử dụng như hàm
gaussian, hàm đa thức, hàm sigmoid,v.v.

Hình 1.14. Ánh xạ các điểm dữ liệu không thể phân tách tuyến tính vào không
gian số chiều lớn hơn có thể phân tách được tuyến tính.
Với bài toán phân nhiều lớp, có nhiều phương pháp đã được phát triển bằng cách
kết hợp các SVM hai lớp và dùng các phương pháp loại trừ để có được lớp đúng nhất.
Các phương pháp được sử dụng như one-vs-one (Hình 1.15-a), phân lớp bằng việc so