Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 3
GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An
thông tin vào trƣờng học. Vì vậy tôi xây dựng đề tài “Ứng dụng kỹ thuật nhận dạng ký
tự 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” đi đến xây dựng một chƣơng trình nhập điểm tự động cho trƣờng.
2. Mục tiêu của đề tài
Nghiên cứu các cơ sở lý thuyết, giải thuật SVM và các thuật toán xử lý ảnh.
Xây dựng mô hình nhận dạng ký tự bằng giải thuật SVM.
Đƣa ra mô hình làm việc với phiếu điểm tại trƣờng Đại học An Giang.
Tích hợp mô hình nhận dạng ký tự vào quy trình nhập điểm tự động tại trƣờng Đại
học An Giang.
3. Câu hỏi nghiên cứu
SVM là gì? Sử dụng giải thuật SVM vào bài toán nhận dạng nhƣ thế nào? Ƣu
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
Nghiên cứu lý thuyết về thuật toán SVM nhận dạng ký tự viết tay.
Sử dụng mã nguồn mở thƣ viện SVM để xây dựng ứng dụng nhập điểm tự động
cho trƣờng Đại học An Giang.
Nghiên cứu so sánh các giải thuật trong lĩnh vực nhận dạng chữ viết tay từ đó rút ra
điểm mạnh yếu làm tiền để khoa học cho đề tài.
Thực nghiệm ứng dụng nhập điểm thông qua phiếu điểm tự động bằng ứng dụng
thực tế tại 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 5
GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An
Chƣơng 1: CƠ SỞ LÝ LUẬN
1.1. Tổng quan vấn đề nghiên cứu
Tổng quan
Trên thế giới hiện nay có nhiều chƣơng trình nhận dạng chữ viết (chữ in và chữ viết
tay) bằng các thứ tiếng Anh, Nga, v.v… nhƣ các hệ OMNIPAGE, READ-WRITE,
WORD-SCAN, … Ở Việt Nam cũng có một số hệ nhƣ WORC của công ty 3C, VIET-
IN của công ty SEATIC, VNDOCR của Viện Công Nghệ Thông Tin, Image Scon của
Trung Tâm Tự Động Hóa Thiết Kế, hệ WINGIS của công ty DolfSoft…
Nhìn chung, các sản phẩm phần mềm nhận dạng văn bản tiếng Việt chữ in của nƣớc ta
đã thu đƣợc các kết quả khả quan, đặc biệt phần mềm VNDOCR đã đƣợc sử dụng
rộng rãi trong các cơ quan nhà nƣớc. Tuy nhiên về các ứng dụng nhận dạng chữ viết
tay thì còn rất hạn chế vì chƣa đạt đƣợc độ chính xác cao cần thiết để có thể áp dụng
rộng rãi trên thực tế, hiện nay bài toán này thƣờng chủ yếu phục vụ yêu cầu đọc và xử
lý trên các biểu mẫu do các chữ viết tay đƣợc nằm riêng biệt và rõ ràng, ví dụ nhƣ: hóa
đơn, phiếu điều tra, …. . Nhập điểm tự động cũng là một dạng bài toán nhận dạng ký
tự viết tay rời rạc trích xuất từ biểu mẫu cố định.
Có rất nhiều phƣơng pháp sử dụng cho bài toán nhận dạng ký tự đã đƣợc nghiên cứu
từ trƣớc đến nay và đạt kết quả khá khả quan. Dƣới đây là một số kết quả của một số
phƣơng pháp của các nhà nghiên cứu trƣớc trên cùng một bộ dữ liệu chữ viết tay
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 =
)
98.37
8
LIBSVM (RBF, = 0.05, c =
)
96.65
9
AdaBootst.M1 (100trees with C4.5)
95.95
Kết quả nhận dạng với phƣơng pháp SVM đã mức độ trung bình từ 96.65% đến
98.37% và đặc biệt với giải thuật SVM này không cần bất kỳ xử lý nào đặc biệt khi
huấn luyện và thời gian huấn luyện nhanh hơn chỉ mất 30 phút (nhanh hơn 50 lần so
với mạng tích chập CNN của (Simard el al.,03), (O’Neill, 2006) và giải thuật
AdaBootst.M1(Freund & Schapire, 1995), (Witten & Frank, 2005) cần thời gian
huấn luyện gần 1 ngày để đạt độ chính xác nhƣ trong bảng) cho độ chính xác tƣơng
đƣơng (thấp hơn 0.5%).
Tình hình trong nƣớc
Ở Việt Nam, ở một số trƣờng Đại học nhƣ Đại học Hồng Bàng, Đại học Mở, Đại học
Kỹ thuật Công Nghệ Hồ Chí Minh cũng đã có các công trình nghiên cứu về ứng dụng
nhập điểm tự động tuy nhiên các công trình nãy vẫn chƣa thể đƣa vào triển khai thực
tế vì vẫn còn sai sót nhiều trong quá trình nhận dạng.
Tình hình ngoài nƣớc
Nói chung về bài toán nhận dạng ký tự viết tay có thể kể đến nhƣ: hệ thống nhận
dạng chữ viết tay trong lĩnh vực kiểm tra tài khoản ở ngân hàng của nhóm nghiên cứu
Simon và O.Baret (Laoria/CNRS & ENPC, Paris)[]; hệ thống chuyên nhận dạng các
địa chỉ nhƣ ở bƣu điện của J.J.Hull, T.K.Ho, J.Favata, V.Govindaraju và S.N.Srihari ở
trƣờng Đại học NewYord[]; phần mềm đọc phiếu xuất nhập cảnh của Singapore:
Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 7
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à
, trong đó
là số lƣợng mẫu huấn luyện.
Hình 1-2: Phân lớp SVM.[1]
Điều này dẫn đến bài toán trở nên phức tạp hơn trong cả hai mặt: không gian nhớ để
lƣu trữ và độ phức tạp để tính toán. Hơn nữa, siêu phẳng tối ƣu lại nằm trong không
gian đặc trƣng với số chiều cao hơn dựa trên cơ sở lựa chọn hàm nhân. Mà việc lựa
chọn hàm nhân phù hợp cho từng ứng dụng cụ thể buộc ngƣời sử dụng SVM phải thực
hiện nhiều lần huấn luyện với các loại hàm nhân khác nhau tƣơng ứng với các giá trị
tham số khác nhau của chúng. Mặt khác, mục đích của việc huấn luyện SVM là lọc ra
các mẫu huấn luyện có tham gia vào việc tạo siêu phẳng đồng thời loại bỏ các mẫu
không liên quan, các mẫu có tham gia tạo ra siêu phẩm đƣợc gọi là véc tơ tựa (SV –
Support Vector). Có nhiều thuật toán huấn luyện SVM, các thuật toán chặt khúc và
thuật toán phân rã đã phân tích bài toán quy hoạch toàn phƣơng (QP – Quadratic
Programing) ban đần thành một dãy các bài toán QP nhỏ hơn. Các bài toán này đã
chứng tỏ rằng có thể giải các bài toán có kích thƣớc vƣợt quá khả năng lƣu trữ của bộ
nhớ máy tính. Thuật toán SMO có thể xem là trƣờng hợp cá biệt của thuật toán phân
rã, trong mỗi lần lặp SMO giải một bài toán QP với kích thƣớc là hai bằng giải pháp
phân tích, vì vậy không cần phải giải bài toán tối ƣu. Các thuật toán này đã đƣợc cài
đặt trong hầu hết các phần mềm SVM mã nguồn mở hiện nay nhƣ SVMLight,
LIBSVM, SVMTorch và HeroSvm.
Phƣơng pháp trích trọn đặc trƣng WaveletHaar
Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 9
GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An
Phƣơng pháp trích chọn đặc trƣng Wavelet Haar 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.
Hình 1-3: Trích chọn đặc trƣng waveletHaar.[3]
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)
{
N = n div 2;
Chia ảnh thành 4 phần:
;(Hình 3-1)
for(j = 1; j4; j++)
PUSH((
,n),Queue);
}
- Gọi S, S1, S2, S3, S4 là tổng các điểm đen tƣơng ứng với các khối
A,
;
- Tính
- 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
và lúc này 2 giá trị là 0 hoặc 255, giá trị 0 biểu diễn cho màu đen và giá trị 255 biểu
diễn cho màu trắng
Hình 1-4: Ảnh nhị phân; (A) ảnh đầu vào, (B) ảnh nhị phân.
Nhị phân hóa ảnh:
Tiểu luận môn Phƣơng pháp luận và nghiên cứu khoa học Trang 11
GV.CC.TS Nguyễn Văn Y Ngƣời thực hiện: Nguyễn Tấn An
Nhị phân hóa ảnh là quá trình đƣợc thực hiện nhờ vào hàm phân ngƣỡng:
Dest(x, y) = 1 if Source(x, y) >= T
0 if Source(x, y) < T
Trong đó, Source(x,y) là giá trị điểm ảnh ở vị trí (x,y) của ảnh nguồn,
Dest(x,y) là giá trị điểm ảnh tƣơng ứng ở vị trí (x,y) của ảnh đích. T là giá trị
ngƣỡng. Tuy nhiên, giá trị cụ thể của ngƣỡng lại phụ thuộc vào từng ảnh, vùng ảnh
đầu vào đang xét, không thể lấy cố định.
Phép toán hình thái (Morphology)
Phép toán hình thái là những thao tác toán học rời rạc trên tập hợp điểm đó đƣợc
sử dụng để làm rõ những nét đặc trƣng riêng của hình dạng đối tƣợng, do vậy có thể
tính toán hay nhận biết đƣợc chúng một cách dễ dàng. Phần lớn các phép toán hình
thái học đƣợc định nghĩa từ hai phép toán cơ bản là phép co nhị phân (Erosion) và
phép toán giãn nhị phân (Dilation).
- Phép giãn nhị phân (Dilation)
Phép giãn nhị phân của một tập hợp A bởi một phần tử cấu trúc B đƣợc ký hiệu
là và đƣợc định nghĩa qua công thức sau:
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
Nhƣ vậy phép co 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á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
là tập con của
A.
Việc thao tác Erosion ảnh phục vụ nhiều mục đích khác nhau nhƣ bào mòn (thu
nhỏ) thành phần liên thông, lọc biên, có thể khữ nhiễu.
Khung sƣơng của ảnh(Skeletonization)
Khung xƣơng của đối tƣợng ảnh là tập hợp các điểm ảnh cách đều biên của đối
tƣợng, trong luận văn này skeletonization đƣợc dùng để biến các ảnh ký tự số đầu vào
thành những ảnh nét đơn (có độ dày 1 hay 2 điểm ảnh) chính vì vậy khi các ký tự đƣợc
viết dƣới các nét dày hay mỏng khác nhau thì qua phƣơng pháp này đều chuyển về
một chuẩn nhất định, điều này giúp tăng độ chính xác cho việc nhận dạng.
Lƣợc đồ chiếu dọc và lƣợc đồ chiếu ngang
Lƣợc đồ chiếu dọc (Vertical Histogram) và lƣợc đồ chiếu ngang (Horizotal
Histogram) hai loại lƣợc đồ này xây dựng cho đối tƣợng là ảnh nhị phân nhằm thống
kê các điểm ảnh theo chiều dọc hay chiều ngang. Hai lƣợc đồ này ứng dụng chủ yếu
trong phần tách các thành phần bảng điểm trong phần xây dựng ứng dụng sau của luận
văn này.
Lấy lƣợc đồ chiếu ngang bằng cách duyệt từ trên xuống dƣới và từ trái qua phải
của ảnh, qua mỗi dòng pixel ta sẽ tiến hành cộng dồn số pixel đen trên từng dòng. Số
pixel đen trên từng dòng sẽ đƣợc biểu diễn thành một đồ thị với trục nằm dọc là chiều
cao của ảnh còn trục nằm ngang là số pixel đen đếm đƣợc trên dòng. 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-5: Lƣợc đồ chiếu ngang.
Không có nhận xét nào:
Đăng nhận xét