S húa bi Trung tõm Hc liu http://www.lrc-tnu.edu.vn/

Đạ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 S húa bi Trung tõm Hc liu http://www.lrc-tnu.edu.vn/


i

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/

LỜI CÁM ƠN

Để đạt đƣợc những kết quả trong quá trình nghiên cứu luận văn, học viên
xin chân thành cảm ơn thầy PGS. TS Ngô Quốc Tạo luôn tận tình chỉ bảo,
hƣớng dẫn và giúp đỡ em trong suốt quá trình làm luận văn.
Học viên xin cảm ơn các thầy cô giáo trƣờng Đại học Công nghệ thông tin
và Truyền thông đã hƣớng dẫn và tạo điều kiện cho em trong suốt thời gian học
tập tại trƣờng.
Học viên xin chân thành cảm ơn các thầy giáo trong Hội đồng xét duyệt
luận văn tốt nghiệp lớp cao học CK11A năm 2014 - Đợt 1 đã nhận xét và góp ý
để bài luận văn của em đƣợc hoàn thiện hơn.
ii

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ LỜI CAM ĐOAN

Tôi xin cam đoan luận văn “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)” là do tôi tự nghiên
cứu và hoàn thành dƣới sự hƣớng dẫn của PGS-TS. Ngô Quốc Tạo.
Các kết quả đạt đƣợc trong quá trình nghiên cứu là hoàn toàn trung thực và

Hàm nhân
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)
QP
Quadratic Programing (quy hoạch toàn phƣơng)
USPS
United States Postal service
VC
Vapnik – Chervonenkis

iv

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ DANH MỤC CÁC HÌNH
Hình 1.1. Các giai đoạn trong quá trình xử lý và nhận dạng ảnh 7
Hình 1.2. Nhị phân hóa ảnh 8
Hình 1.3. Nhiễu đốm và nhiễu vệt 8
Hình 1.4. Chuẩn hóa kích thƣớc ảnh các ký tự “A” và “P” 8
Hình 1.5. (a) Ảnh gốc, (b) Ảnh sau khi đƣợc làm trơn biên 9
Hình 1.6. Làm mảnh chữ 9
Hình 1.7. Hiệu chỉnh độ nghiêng của văn bản 10
Hình 1.8. Tách dòng chữ dựa trên histogram theo chiều ngang của khối chữ 10

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
1

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ MỞ ĐẦU
Biết sử dụng các phƣơng pháp nhận dạng đóng vai trò hết sức quan trọng

việc nhận dạng chữ viết tay hạn chế.
MỤC LỤC
LỜI CÁM ƠN i
LỜI CAM ĐOAN ii
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT iii
DANH MỤC CÁC HÌNH iv
MỞ ĐẦU 1
MỤC LỤC 2
Chƣơng 1. GIỚI THIỆU VỀ CHỮ VIẾT VÀ NHẬN DẠNG CHỮ VIẾT 5
1.1. Trình bày về lịch sử của nhận dạng chữ viết tay 5
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 5
1.2.1. Nhận dạng chữ in 5
1.2.2. Nhận dạng chữ viết tay 6
1.3. Tiền xử lý 7
1.3.1. Nhị phân hóa ảnh 7
1.3.2. Lọc nhiễu 8
1.3.3. Chuẩn hóa kích thƣớc ảnh 8
1.3.4. Làm trơn biên chữ 9
1.3.5. Làm đầy chữ 9
1.3.6. Làm mảnh chữ 9
1.3.7. Điều chỉnh độ nghiêng của văn bản 9
1.4. Khối tách chữ 10
1.4.1. Tách chữ theo chiều nằm ngang và thẳng đứng 10
1.4.2. Tách chữ dùng lƣợc đồ sáng 11
1.5. Trích chọn đặc trƣng 11
1.5.1. Biến đổi toàn cục và khai triển chuỗi 12
1.5.2. Đặc trƣng thống kê 13
1.5.3. Đặc trƣng hình học và hình thái 14
3


2.12. Áp dụng SVM vào nhận dạng chữ Việt viết tay rời rạc 49
2.12.1. Tiền xử lý 49
4

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 2.12.2. Phân nhóm sơ bộ 52
2.12.3. Trích chọn đặc trƣng. 52
2.12.4. Xây dựng các máy phân lớp SVM 55
Chƣơng 3 – CHƢƠNG TRÌNH THỬ NGHIỆM 56
3.1. Giới thiệu về hệ nhận dạng dùng LIBSVM 56
3.2. Các chức năng chính của hệ nhận dạng 57
3.3. Sử dụng libsvm-3.18 57
3.4. Kết quả chạy thử nghiệm trên tập dữ liệu libsvm 60
3.4.1. Kết quả thực nghiệm đƣợc tiến hành trên tập dữ liệu mnist 61
3.4.2. Kết quả thực nghiệm đƣợc tiến hành trên tập dữ liệu usps 62
3.5. Chƣơng trình nhận dạng. 64
3.5.1. Chức năng chƣơng trình 64
- Tiền xử lý (Convert Color Image to Black & white): Chuyển đổi ảnh từ ảnh màu
sang ảnh nhị phân và chuẩn hóa kích thƣớc ảnh với kích cỡ 16x16. 64
3.5.2. Chức năng Tiền xử lý: 64
3.5.3. Chức năng trích chọn đặc trƣng 65
3.5.4. Huấn luyện 65
3.5.4. Nhận dạng 66
KẾT LUẬN VÀ ĐỀ NGHỊ 68
TÀI LIỆU THAM KHẢO 69

5


bảng và văn bản với độ chính xác trên 98%).
6

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1.2.2. 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ý các chứng từ, hóa đơn, phiếu ghi, văn bản viết tay,… Nhận
dạng chữ viết tay đƣợc tách ra hai hƣớng phát triển: nhận dạng chữ viết tay trực tuyến
(online) và chữ viết tay ngoại tuyến (offline). Trong đó nhận dạng chữ viết tay trực
tuyến là khi viết lên màn hình thì máy tính sẽ chuyển những hình ảnh viết tay thành
dạng text. Khác với chữ offline, chữ online có thêm thông tin về thứ tự các điểm, các
nét đƣợc viết. Hiện nay việc nhận dạng chữ viết tay tiếng Anh online hầu nhƣ đã giải
quyết xong và đã đƣợc tích hợp vào máy tính cầm tay thậm chí là máy để bàn và điện
thoại di động. Nhƣng đối với tiếng Việt thì chƣa có một phần mềm nào tƣơng tự. Còn
trong nhận dạng chữ viết tay offline chúng ta nghiên cứu về nhận dạng chữ viết tay tự
nhiên và nhận dạng chữ viết tay hạn chế. Nhận dạng chữ viết tay tự nhiên là dùng để
xử lý các văn bản viết tay thông thƣờng, công việc này cực kỳ khó khăn nếu không nói
là không thể.
Nhận dạng chữ viết tay hạn chế là dạng các form điều tra xã hội, có các thông tin
về chữ số, tên ngƣời, địa chỉ, điện thoại,… Những ngƣời đƣợc điều tra sẽ điền các
thông tin bằng chữ viết tay vào form. Để nhập thông tin hàng trăm nghìn các phiếu
điều tra vào máy tính sẽ mất rất nhiều thời gian khi làm thủ công bằng tay. Nếu ta
dùng một chƣơng trình để nhận dạng các chữ viết tay trên các phiếu điều tra đó thì
công việc sẽ đơn giản hơn. Các chữ trong phiếu điều tra thƣờng là các chữ viết tay hạn
chế: viết rõ ràng, rời nhau, hoặc không dính liền nhau nhiều, thậm chí là viết hoa. Hiện
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

Nhị phân hóa ảnh là một kỹ thuật chuyển ảnh đa cấp xám sang ảnh nhị phân.
Trong bất kỳ bài toán phân tích hoặc nâng cao chất lƣợng ảnh nào, nó cũng cần thiết
để xác định các đối tƣợng quan trọng. Nhị phân hóa ảnh phân chia ảnh thành 2 phần:
phần nền và phần chữ. Hầu hết các phƣơng pháp nhị phân hóa ảnh hiện nay đều lựa
chọn một ngƣỡng thích hợp theo cƣờng độ sáng của ảnh và sau đó chuyển tất cả các
giá trị độ sáng lớn hơn ngƣỡng đó thành một giá trị độ sáng (“trắng”) và tất cả các giá
trị bé hơn ngƣỡng thành một giá trị độ sáng khác (“đen”).
Ảnh văn bản
quét vào
Tiền xử lý
Trích chọn đặc trƣng
Hậu xử lý
Huấn luyện và
nhận dạng
Tách chữ
Văn bản đƣợc
nhận dạng
8

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
Hình 1.2. Nhị phân hóa ảnh
1.3.2. Lọc nhiễu
Nhiễu là một tập các điểm sáng thừa trên ảnh. Khử nhiễu là một vấn đề thƣờng
gặp trong nhận dạng, nhiễu có nhiều loại (nhiễu đốm, nhiễu vệt, nhiễu đứt nét, ).

Hình 1.3. Nhiễu đốm và nhiễu vệt.
Để khử các nhiễu đốm (các nhiễu với kích thƣớc nhỏ), có thể sử dụng các

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.

Hình 1.6. Làm mảnh chữ
1.3.7. Điều chỉnh độ nghiêng của văn bản
Do trang tài liệu quét vào không cẩn thận hoặc do sự cố in ấn, các hàng chữ bị
lệch so với lề chuẩn một góc α, điều này gây khó khăn cho công đoạn tách chữ, đôi khi
10

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ không thể tách đƣợc. Trong những trƣờng hợp nhƣ vậy, phải tính lại tọa độ điểm ảnh
của các chữ bị sai lệch.
Có nhiều kỹ thuật để điều chỉnh độ nghiêng, kỹ thuật phổ biến nhất dựa trên cơ
sở biểu đồ chiếu (projection profile) của ảnh tài liệu; một số kỹ thuật dựa trên cơ sở
các phép biến đổi Hough và Fourier.

Hình 1.7. Hiệu chỉnh độ nghiêng của văn bản
1.4. Khối tách chữ
Khối này có nhiệm vụ tách từng ký tự ra khỏi văn bản. Chỉ khi nào văn bản đƣợc
tách và cô lập đúng từng ký tự đơn ra khỏi tổng thể văn bản thì hệ thống mới có thể
nhận dạng đúng ký tự đó. Sau đây là một số phƣơng pháp tách chữ thông dụng.
1.4.1. Tách chữ theo chiều nằm ngang và thẳng đứng
Phƣơng pháp này thƣờng áp dụng cho chữ in. Khác với chữ viết tay, kích thƣớc
và kiểu chữ cố định, phải tuân theo một số quy định in ấn, các chữ phải nằm gọn trong
một khung nên việc cô lập một ký tự đơn có thể đồng nhất với việc tìm ra khung bao
của chữ đó tại vị trí của nó trong văn bản. Tách chữ theo chiều nằm ngang và thẳng
đứng là tìm một hình chữ nhật có cạnh thẳng đứng và nằm ngang chứa trọn một ký tự
ở bên trong.

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ữ:
- Biến đổi Fourier: Một trong những tính chất nổi bật nhất của phép biến đổi
Fourier là khả năng nhận dạng các ký tự có sự thay đổi về các tƣ thế khác nhau, các
phép biến đổi này đã đƣợc áp dụng để nhận dạng ký tự theo nhiều cách khác nhau.
- Biến đổi Wavelet: Phép biến đổi này là một dãy các kỹ thuật khai triển cho
phép mô tả đặc trƣng của ảnh ở các mức độ khác nhau. Các công đoạn tách chữ thành
các ký tự hoặc từ đƣợc mô tả bằng các hệ số Wavelet theo các mức độ khác nhau đối
với từng giải pháp. Sau đó các hệ số Wavelet đƣợc chuyển qua một máy phân lớp để
phục vụ cho việc nhận dạng.
- Phƣơng pháp mô men: Theo phƣơng pháp này, ảnh gốc sẽ đƣợc thay thế bằng
một tập các đặc trƣng vừa đủ để nhận dạng các đối tƣợng bất biến đối với các phép
thay đổi tỷ lệ, tịnh tiến hoặc quay. Các mô men đƣợc xét nhƣ các dãy khai triển đặc
trƣng vì ảnh gốc có thể xây dựng lại một cách đầy đủ từ các hệ số mô men.
- Khai triển Karhunent - Loeve: Việc khai triển này nhằm phân tích các véc tơ
riêng để rút gọn số chiều của tập đặc trƣng bằng cách tạo ra các đặc trƣng mới là tổ
hợp tuyến tính của các đặc trƣng gốc. Đây chỉ là một phép biến đổi tối ƣu trong một số
13

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/


14

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 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
một ký tự có thể đƣợc xác định bằng nhiều cách khác nhau: hƣớng của xƣơng, phân
đoạn nét chữ, mã hóa chu tuyến, hƣớng đạo hàm [12]. Hiện nay, các đặc trƣng mã hóa
chu tuyến và hƣớng đạo hàm đƣợc áp dụng rộng rãi vì chúng dễ cài đặt và xấp xỉ bất
biến với sự biến đổi đa dạng của các nét chữ.
1.5.3. Đặc trƣng hình học và hình thái
Các tính chất cục bộ và toàn cục khác nhau của các ký tự có thể đƣợc biểu diễn
bằng các đặc trƣng hình học và hình thái. Các kiểu đặc trƣng này cũng có thể giải mã
một số tri thức về cấu trúc của đối tƣợng ảnh hoặc có thể cung cấp một số tri thức nhƣ
sắp xếp các thành phần để tạo ra đối tƣợng. Các loại đặc trƣng này có thể phân thành
các nhóm sau:
- Trích chọn và đếm các cấu trúc hình thái: trong nhóm đặc trƣng này, một
cấu trúc đã xác định đƣợc tìm kiếm trong một ký tự hoặc một từ. Số lƣợng vị trí hoặc
quan hệ vị trí của các cấu trúc trong ký tự này tạo thành các đặc trƣng biểu diễn ký tự.
Thông thƣờng, các cấu trúc nguyên thủy (các đoạn thẳng, các cung) là các nét tạo ra
ký tự. Các ký tự và các từ có thể đƣợc mô tả bằng cách trích chọn và đếm nhiều loại
đặc trƣng về hình thái nhƣ các điểm cực đại và cực tiểu, các điểm chóp trên và chóp
dƣới của một ngƣỡng nào đó, mở rộng cho các điểm trái, phải, trên, dƣới và các giao

Đâ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
16

Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 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.
Cách đơn giản nhất để kết nối các thông tin ngữ cảnh là tận dụng một từ điển để
điều chỉnh các lỗi của hệ thống nhận dạng. Ý tƣởng cơ bản này dựa trên cơ sở đánh
vần kiểm tra đầu ra của hệ thống nhận dạng và cung cấp một số khả năng cho các đầu
ra của máy nhận dạng khi các đầu ra này không nằm đúng vị trí trong từ điển. Việc
kiểm tra lỗi chính tả phù hợp với một số ngôn ngữ nhƣ Anh, Pháp, Đức, Việt Nam,
1.8. Một số thuật toán phân lớp nhận dạng chữ viết tay
1.8.1. Giới thiệu
Thuật toán phân lớp là yếu tố có vai trò quyết định đến chất lƣợng của một hệ
thống nhận dạng. Các phƣơng pháp nhận dạng truyền thống nhƣ đối sánh mẫu, nhận
dạng cấu trúc đã đƣợc ứng dụng khá phổ biến trong các hệ thống nhận dạng và cũng
đã thu đƣợc những thành công nhất định. Tuy vậy, với những trƣờng hợp văn bản đầu
vào có chất lƣợng không tốt (nhiễu, đứt nét, dính nét ) thì các thuật toán này tỏ ra
không hiệu quả.
Để khắc phục điều này, trong những năm gần đây nhiều nhóm nghiên cứu đã sử
dụng các thuật toán phân lớp dựa trên mô hình Markov ẩn HMM, mô hình mạng

i,j
chuyển từ trạng thái S
i
sang trạng thái S
j
. Thành
phần thứ ba là một ma trận B = (b
i
(o
l
)) 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). 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