HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG
TIỂU LUẬN MÔN HỌC
PHƢƠNG PHÁP LUẬN NGHIÊN CỨU KHOA HỌC
Đề tài:
“ỨNG DỤNG KỸ THUẬT NHẬN DẠNG BẰNG
SVM VÀO XÂY DỰNG PHẦN MỀM NHẬP
ĐIỂM TỰ ĐỘNG TẠI TRƢỜNG ĐẠI HỌC AN
GIANG”

Giáo viên hƣớng dẫn : GV.CC.TS Nguyễn Văn Y
Sinh viên thực hiện : Nguyễn Tấn An
Mã học viên : N13CHIS002
Lớp : M13CQIS01-N

Hồ Chí Minh - 2014

LỚI CẢM ƠN
Đầu tiên, em xin gửi lời cảm ơn sâu sắc đến thầy giáo Tiến sĩ Nguyễn Văn Y ngƣời đã
truyền đạt kiến thức cho em về môn nghiên cứu phƣơng pháp luận khoa học tại Học
Viện Bƣu Chính Viễn Thông. Qua 2 tháng em đã tiếp thu đƣợc rất nhiều điểu bổ ích
về cách làm một bài luận khoa học, từ đó đúc kết đƣợc nhiều kinh nghiệm để thực hiện
bài tiểu luận nghiên cứu khoa học với đề tài “Ứng dụng kỹ thuật nhận dạng bằng SVM
vào xây dựng phần mềm nhập điểm tự động tại trƣờng Đại học An Giang”.
Em cũng xin bày tỏ lời cảm ơn đến tập thể lớp cao học hệ thống thông tin
M13CQIS01-N, những ngƣời bạn đã cùng đồng hành trong suốt quá trình học tập môn
nghiên cứu phƣơng pháp luận khoa học, đã lắng nghe, đóng góp và chia sẽ kinh
nghiệm đã giúp em hoàn thành tốt hơn bài tiểu luận của mình.
Em xin chân thành cảm ơn.

Chƣơng 3: GIẢI PHÁP – MÔ HÌNH – SẢN PHẨM 20
3.1. Mô tả dữ liệu đầu vào và đầu ra 20
3.2. Mô tả sơ lƣợc về phiếu điểm 20
3.3. Giải pháp và các mô hình các quá trình xử lý 22
Kết luận chƣơng 3 28
KẾT LUẬN 29
KHUYẾN NGHỊ 29
TÀI LIỆU THAM KHẢO 30

Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 2

GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An

MỞ ĐẦU
1. Lý do chọn đề tài
Trƣờng Đại học An Giang là một trong những trƣờng đại học lớn ở đồng bằng
sông Cửu Long, với tổng số sinh viên lên đến 10000 sinh viên, việc quản lý thông tin
sinh viên và kết quả học tập của sinh viên ở trƣờng đã đƣợc tin học hóa thông qua
website regis.agu.edu.vn, ở website này sinh viên sẽ biết đƣợc các thông tin về đăng
ký học phần, thời khóa biểu, lịch thi, kết quả học tập của mình. Để cung cấp kết quả
học tập của một số lƣợng lớn sinh viên nhƣ vậy, cứ mỗi kỳ thi cán bộ nhập điểm phải
nhập điểm vào hệ thống cơ sở dữ liệu điểm để đƣa lên website, công việc này mất rất
nhiều thời gian và công sức của ngƣời nhập liệu, đồng thời nếu thời gian thông báo
chậm trễ sẽ làm ảnh hƣởng xấu cho sinh viên trong khâu chuẩn bị cải thiện kết quả học
tập của mình.
Mặt khác, hiện nay khi các lĩnh vực khai thác dữ liệu ngày càng phát triển, trong
đó lĩnh vực nhận dạng ký tự cũng là một trong những đề tài đã đƣợc các nhà nghiên
cứu quan tâm rất nhiều. Bài toán này có 2 dạng, một dạng là bài toán nhận dạng ký tự
in và dạng còn lại là bài toán nhận dạng ký tự viết tay, về nhận dạng ký tự in do ký tự
in có kiểu chữ, kích thƣớc, khoảng cách viết đều có qui định cụ thể nên bài toán này

khuyết điểm của SVM so với các giải thuật nhận dạng khác?
 Ứng dụng bài toán nhận dạng ký tự bằng SVM vào phần mềm nhập điểm tự động
nhƣ thế nào?
4. Phạm vi nghiên cứu
Ứng dụng nhận dạng ký tự bằng giải thuật SVM vào xây dựng phần mềm nhập điểm
tự động cho trƣờng Đại học An Giang.
5. Giải pháp hiện có
Thực hiện thủ công:
Ƣu điểm: Tỷ lệ chính xác tƣơng đối cao, trải qua nhiều khâu xác nhận từ sinh
viên đến giảng viên đến ngƣời nhập điểm nên hạn chế nhiều sai sót về điểm xảy ra.
Nhƣợc điểm: mất nhiều thời gian nhập điểm và vẫn còn sai sót diễn ra, chƣa
phù hợp với sự phát triển của trƣờng Đại học lớn.
6. Đối tƣợng và khách thể nghiên cứu
 Nghiên cứu cấu trúc phiếu điểm của trƣờng Đại học An Giang.
 Nghiên cứu phép toán tiền xử lý ảnh phục vụ bài toán nhận dạng ký tự.
 Nghiên cứu giải thuật SVM nhận dạng ký tự số viết tay và ký tự in thông qua phiếu
điểm của trƣờng Đại học An Giang.
7. Giả thuyết khoa học
 Đề tài phân tích đƣợc mô hình nhận dạng ký tự bằng giải thuật SVM cho phiếu
điểm của trƣờng Đại học An Giang.
Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 4

GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An

 Xây dựng đƣợc một công cụ nhập điểm tự động cho trƣờng Đại học An Giang
mang lại hiệu quả cao về hiệu suất làm việc cũng nhƣ tiết kiệm đƣợc rất nhiều thời
gian so với cách nhập điểm bằng tay thông thông.
 Nghiên cứu phân tích đƣợc bộ nhận dạng chữ viết tay cho nhập điểm sẽ là tiền đề
áp dụng cho nhiều ứng dụng khác.
8. Phƣơng pháp chứng mình giả thuyết

MNIST:
Bảng 1-1: Bảng so sánh độ chính xác các giải thuật nhận dạng chữ viết tay [4]
STT
Phƣơng pháp
Độ chính xác (%)
1
1-layer Neural nets (LeCun et al., 1998)
88.00
2
Nearest-neighbor (Euclidean L2) nets (LeCun et al.,
1998)
95.00
3
Convolution net LeNet-1 (LeCun et al., 1998)
98.30
4
Convolution net LeNet-4* (LeCun et al., 1998)
98.90
5
Convolution net LeNet-5* (LeCun et al., 1998)
99.15
Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 6

GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An

6
Convulution Neural Net (CNN)* (Simard el al.,03)
99.10
7
LIBSVM (RBF,  = 0.05, c = 


GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An Hình 1-1: Phiếu xuất nhập cảnh Singapore đọc đƣợc bằng máy.
1.2. Các khái niệm liên quan đến đề tài
 Giới thiệu SVM
SVM đƣợc nghiên cứu từ những năm của thập niên 1960 với công trình của
Vapnik và Lerner (1963), Vapnik và Chervonenkis (1964). Cơ sở của SVM dựa trên
nền tảng của lý thuyết học thống kê và lý thuyết chiều Vapnik Chervonenkis đã đƣợc
phát triển qua 3 thập kỷ bởi Vapnik và Chervonenkis. Lý thuyết này bắt đầu có những
bƣớc phát triển mạnh mẽ về mặt ứng dụng kể từ những năm cuối của thập niên 1990
(Burges, 1996; Osuma, 1997; Platt, 1998) và từ đó đến nay nó đã trở thành một công
cụ khá mạnh trong nhiều lĩnh vực nhƣ: nhận dạng chữ viết, nhận dạng mặt ngƣời, …
Trong những năm gần đây, SVM đƣợc biết đến nhƣ một hƣớng tiếp cận phân
lớp hiệu quả và đang đƣợc áp dụng rộng rãi trong nhiều ứng dụng thực tế. Ƣu điểm
của SVM là khả năng phân lớp với độ chính xác cao, điều này đƣợc bảo đảm bởi các
tính chất của siêu phẩm tối ƣu và cách sử dụng hàm nhân. Tuy nhiên, tốc độ phân lớp
của SVM bị đánh giá chậm hơn so với các phƣơng pháp phân lớp khác. Trong quá
trình phân lớp, SVM phải duyệt qua tất cả các véc tơ tựa để so sánh với mẫu cần nhận
dạng, khi số véc tơ tựa tăng thì tốc độ phân lớp cũng giảm xuống tƣơng ứng.
Các thuật toán huấn luyện SVM đƣợc thực hiện theo ý tƣởng sau: tìm siêu
phẳng tối ƣu trong không gian đặc trƣng để cực đại khoảng cách giữa 2 lớp mẫu huấn
luyện trong bài toán phân lớp nhị phân. Nhƣ vậy, việc huấn luyện SVM tƣơng đƣơng
Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 8

GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An

với việc giải bài toán tối ƣu với số lƣợng các biến là  và số các tham số là 


Từ ảnh nhị phân kích thƣớc 

 

(hình) quá trình trích chọn đặc trƣng đƣợc
mô tả theo thuật toán sau:
Procedure waveletHaarFeature
Đầu vào: Ma trận vuông (A,n) cấp 


Đầu ra: Tập các đặc trƣng 

 

  




.
Phƣơng thức
Khởi tạo: Queue = ; i = 1;
Tính 

Tổng các điểm đen trong toàn bộ ma trận (A,n);
PUSH((A,n),Queue);
while Queue   Do
{
- POP(Queue,(A,n));
- if(n > 1)


   


 
- i  i+ 3;
Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 10

GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An

}
Nhƣ vậy với việc chọn kích thƣớc chuẩn hóa cho ảnh ký tự là 16x16 thì phƣơng
pháp wavelet Haar sẽ trích chọn ra : 1+ 3+ 4x3 + 4x4x3 + 4x4x4x3 = 256 đặc trƣng.
Phƣơng pháp trích chọn đặc trƣng này sẽ tạo ra một dãy số các đặc trƣng giảm
dần. Với cùng một chữ thì các giá trị lớn ở đầu dãy tƣơng đối ổn định, có thể đại diện
cho hình dạng khái quát của chữ, còn các giá trị cuối dãy nhỏ dần và không ổn định,
thể hiện sự đa dạng trong từng chi tiết nhỏ của chữ.
 Một số khái niệm về xử lý ảnh
 Khái niệm về ảnh số:
Ảnh số là hình ảnh đƣợc lƣu trong các thiết bị số nhƣ máy ảnh kỹ thuật số, máy
tính hoặc các thiết bị số khác. Ảnh số là một mảng hai chiều gồm các điểm ảnh (pixel),
mỗi điểm ảnh đƣợc xác định bởi tọa độ (x,y) và đƣợc biểu diễn bởi n bytes dƣới các hệ
màu khác nhau, theo hệ màu thƣờng có 3 loại ảnh chính:
- Ảnh màu (color image): mỗi điểm ảnh có giá trị gồm 3 màu đỏ (red) cộng xanh
lục (green) cộng xanh dƣơng (blue). Mỗi màu có giá trị từ 0 đến 255, nghĩa là
mỗi điểm ảnh cần 24bits hay 3bytes để biểu diễn.
- Ảnh xám (gray image): giá trị mỗi điểm ảnh nằm trong giải giá trị từ 0 đến 255,
nghĩa là cần 8 bits hay 1 byte để biểu diễn mỗi điểm ảnh này.
Ảnh nhị phân (binary image): giá trị mỗi điểm ảnh là 0 hoặc 1, nghĩa là trắng
hoặc đen. Khi xử lý trên máy tính thì ngƣời ta dùng ảnh xám để biểu diễn ảnh nhị phân


   
Phép giãn nhị phân của tập hợp A bởi phần tử cấu trúc B là tập hợp của tất cả các
điểm z (z là tâm điểm của phần tử cấu trúc B trên tập hợp A) sao cho phản xạ của 


giao với tập A tại ít nhất một điểm. Hay nói cách khác, phép giãn nhị phân là sự chồng
chéo ít nhất một phần tử từ phản xạ của phần tử cấu trúc B với tập hợp A. Đồng thời
các phần tử này phải là tập con của tập hợp A.
Dilation phục vụ nhiều mục đích khác nhau nhƣ mở rộng (phình to) các thành
liên thông trong ảnh nhƣ việc nối kết các vết đứt trong kí tự lại với nhau, lọc biên ,…
- Phép co nhị phân (Erotion)
Phép co nhị phân của tập hợp A bởi phần tử cấu trúc B đƣợc kí hiệu    và
viết dƣới dạng công thức nhƣ sau:
   







 


Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 12

GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An

Với 


GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An

Lấy lƣợc đồ chiếu dọc bằng cách duyệt chúng theo chiều dọc, ứng với mỗi cột ta
sẽ cộng dồn số pixel đen. Trên lƣợc đồ trục Oy sẽ là số pixel đen trên một mỗi cột và
trục Ox là chiều rộng của ảnh. Thông qua lƣợc đồ này ta có thể nhận thấy đƣợc sự
phân cách giữa các khối văn bản giữa các dòng với nhau.

Hình 1-6: Lƣợc đồ chiếu dọc
1.3. Hƣớng tiếp cận của đề tài
Tiếp cận đề tài từ mô hình chung ứng dụng SVM vào bài toán nhận dạng chữ viết
tay rời rạc để xây dựng ứng dụng nhập điểm tự động.

Hình 1-7: Mô hình nhận dạng ký tự viết tay rời rạc bằng SVM. [2]
- Bƣớc 1: Xây dựng mô hình huấn luyện.
Tập dữ liệu huấn luyện sau khi qua các khâu tiền xử lý và trích chọn đặc trƣng sẽ đƣợc
đƣa vào máy huấn luyện phân lớp SVM. Sau khi kết thúc quá trình huấn luyện, hệ
thống sẽ lƣu lại giá trị các tham số của hàm quyết định phân lớp để phục vụ cho việc
nhận dạng sau này. Quá trình huấn luyện tiêu tốn khá nhiều thời gian, tốc độ huấn
Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 14

GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An

luyện nhanh hay chậm tùy thuộc vào từng thuật toán huấn luyện, chiến lƣợc phân lớp
SVM cũng nhƣ số lƣợng mẫu tham gia huấn luyện.
- Bƣớc 2: Phân lớp nhận dạng.
Dựa vào giá trị các tham số của hàm quyết định thu đƣợc ở Bƣớc 1, một mẫu mới x
sau khi đã qua các khâu tiền xử lý và trích chọn đặc trƣng sẽ đƣợc đƣa vào tính toán
thông qua hàm quyết định để xác định lớp của mẫu x.
Ngoài ra hƣớng tiếp cận khác của đề tài là tiếp cận theo mô hình tƣơng tác với

tài nhƣ SVM, các thuật toán xử lý ảnh nhƣ nhị phân hóa ảnh, phép toán hình thái, lƣợc
đồ chiếu, …. Chƣơng 1 cũng nêu lên các mô hình tiếp cận về đề tài, mô hình tổng quát
về một bài toán nhận dạng ký tự bằng SVM từ đó giúp ta tiếp cận với vấn đề nghiên
cứu của đề tài tốt hơn.
Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 16

GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An

Chƣơng 2: CƠ SỞ THỰC TIỄN
2.1. Giới thiệu
Trƣờng Đại học An Giang đƣợc thành lập theo Quyết định số 241/1999/QĐ-TTg,
ngày 30 tháng 12 năm 1999 của Thủ tƣớng Chính phủ và khai giảng năm học đầu tiên
ngày 09 tháng 9 năm 2000. Năm học 2009 – 2010, đánh dấu một bƣớc phát triển mới
của Trƣờng Đại học An Giang sau 10 năm thành lập. Đây là năm học đầu tiên chuyển
đổi toàn bộ hệ đào tạo chính quy từ niên chế sang học chế tín chỉ. Đến nay, cơ sở hạ
tầng tại các cơ sở tƣơng đối hoàn chỉnh, thƣ viện mới đƣợc hình thành theo tiêu chí thƣ
viện điện tử với 1.200 máy tính nối mạng, thực hiện xã hội hóa khu liên hợp thể dục,
thể thao tại khu trƣờng mới, bổ sung máy móc thiết bị khu thí nghiệm, tiếp tục bổ sung
trang thiết bị dạy học tiên tiến, đẩy mạnh ứng dụng công nghệ thông tin … Trƣờng Đại
học An Giang có 10,695 sinh viên và 738 cán bộ giảng viên và công nhân viên.
Trƣờng có 6 khoa: Khoa sƣ phạm, Khoa Nông nghiệp và Tài nguyên Thiên nhiên,
Khoa Kỹ thuật – Công nghệ - Môi trƣờng, Khoa Kinh tế - Quản trị Kinh doanh, Khoa
Văn hóa nghệ thuật và khoa Lý luận chính trị.
Trên cơ sở lƣu lƣợng sinh viên nhiều nhƣ vậy thì công việc kiểm soát điểm thi
các loại theo quy trình thủ công hiện tại sẽ mất nhiều thời gian, từ đó dẫn đến sai sót
khi phải kiểm tra theo dõi một lƣợng rất lớn dữ liệu nhƣ vậy. Xuất phát từ thực tế nhƣ
trên bài toán đƣợc đặt ra là cần có một công cụ nhập điểm tự động thông qua phiếu

Hình 2-1: Hiện trạng quy trình nhập điểm tại trƣờng Đại học An Giang.
Phòng đào tạo gửi phiếu ghi điểm các môn học cho các giảng viên phụ trách
giảng dạy môn học, cứ sau mỗi học kì trƣớc khi kì thi bắt đầu khoảng 1 tuần và sau khi
có kết quả thi, giảng viên sẽ thông báo điểm trong quá trình học tập và điểm thi cho
các sinh viên, các sinh viên sẽ xác nhận lại điểm số xem có sai sót xảy ra không, sau
đó giảng viên sẽ nộp lại phòng khảo thí. Cán bộ ở phòng khảo thí sẽ phụ trách nhập
điểm vào hệ thống cơ sở dữ liệu của website thông báo kết quả học tập của sinh viên
để lƣu lại và để sinh viên có thể tra cứu kết quả học tập của mình khi cần.
Nhƣ vậy với số lƣợng lớn sinh viên nhƣ hiện nay thì công việc nhập liệu điểm
vào cơ sở dữ liệu là một công việc tốn thời gian rất nhiều và công sức của cán bộ nhập
liệu.
 Hiện trạng về mã nguồn mở thƣ viện SVM
Hiện tại giải thuật SVM đã đƣợc các nhà nghiên cứu triển khai thành các thƣ viện gần
nhƣ hoàn chỉnh, có rất nhiều thƣ viện SVM đã đƣợc công bố trên thế giới nhƣ:
- LibSVM: A Library for Support Vector Machines do 2 nhà nghiên cứu Chih-
Chung Chang and Chih-Jen Lin thực hiện, thƣ viện này có thể dùng ngôn ngữ C++
và java đề biên dịch sử dụng.
Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 18

GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An

- LIBLINEAR: A Library for Large Linear Classification do nhóm máy học ở đại
học quốc gia Đài Loan nghiên cứu, đây là một thƣ viện lập trình gồm nhiều thuật
toán phân loại tuyến tính, trong đó có SVM, thƣ viện này có thể dùng
MATLAB/Octave, Java, Python, Ryby interfaces để biên dịch sử dụng.
- SVMlight: của tác giả Thorsten Joachims của trƣờng đại học Cornell nghiên cứu.
Thƣ viện này có thể sử dụng ngôn ngữ C để biên dịch sử dụng.
- SVM.net của Matthew Johnson là phiên bản đƣợc chuyển đổi từ phiên bản
libSVM dành cho java. Nó cung cấp đầy đủ tính năng và hiệu quả giống nhƣ phiên
bản gốc nhƣng cấu trúc đƣợc thay đổi cho phù hợp với nền tảng .Net.

phát triển và sự hoàn chỉnh của giải thuật là cơ sở để áp dụng giải thuật này vào xây
dựng ứng dụng nhập điểm tự động một cách hiệu quả và đơn giản.
Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 20

GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An

Chƣơng 3: GIẢI PHÁP – MÔ HÌNH – SẢN PHẨM
3.1. Mô tả dữ liệu đầu vào và đầu ra
 Dữ liệu đầu vào của chƣơng trình:
Ảnh phiếu điểm
 Dữ liệu đầu ra của chƣơng trình:
File dữ liệu điểm theo định dạng sẵn ( Ví dụ: excel, )
Tra cứu điểm sinh viên.
3.2. Mô tả sơ lƣợc về phiếu điểm
Dƣới đây là hình ảnh của bảng điểm đƣợc phòng khảo thí trƣờng Đại học An Giang
cung cấp cho cán bộ giảng viên ghi lại điểm của các bài thi trƣớc khi nhập điểm vào hệ
thống máy tính lƣu trữ của trƣờng. Qua phân tích bố cục của bảng điểm bao gồm các
khối nhƣ sau:
 Khối thông tin đơn vị tổ chức thi cử;
 Khối thông tin mẫu in;
 Khối tên bảng điểm;
 Khối thông tin bảng điểm;
 Khối thông tin trang bảng điểm;
 Khối bảng điểm;
 Khối thống kê số sinh viên và bài thi của phòng thi;
 Khối ngày tháng năm in bảng điểm;
 Khối thông tin cán bộ coi thi;
 Khối thông tin thanh tra giám sát vào điểm;
 Khối thông tin cán bộ đối chiếu điểm;
 Khối thƣ ký vào điểm.

Nhận dạng ký tự
số viết tay
Lưu trữ dữ liệu

Hình 3-2: Mô hình tổng quát tiến trình nhập điểm tự động.
Phần mềm sẽ gồm 3 quá trình chính:
 Quá trình tiền xử lý và tách vùng ảnh phiếu điểm.
 Quá trình xây dựng mô hình huấn luyện SVM cho nhận dạng ký tự in và ký tự
số.
 Quá trình nhận dạng ký tự.

Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 23

GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An

 Quá trình tiền xử lý ảnh và tách vùng ảnh phiếu điểm:
Ảnh phiếu ghi
điểm
Tách khối bảng
điểm
Tách cột MSSV Tách cột điểm
Tách hàng cột
điểm
Tách hàng cột
MSSV
Tách ký tự MSSV
Tách ký tự điểm
viết tay
Tiền xử lý ảnh
phiếu điểm