Luận án Nghiên cứu khoa học toán ứng dụng

MỤC LỤC DANH MỤC CÁC KÝ HIỆU, CỤM TỪ VIẾT TẮT ................................................5 DANH MỤC CÁC BIỂU BẢNG..................................................................................7 DANH MỤC CÁC HÌNH VẼ.......................................................................................8 PHẦN MỞ ĐẦU ..........................................................................................................10 CHƯƠNG 1: TỔNG QUAN VỀ NHẬN DẠNG CHỮ VIẾT TAY........................13 1.1. GIỚI THIỆU...........................................................................................................13 1.2. MÔ HÌNH TỔNG QUÁT CỦA MỘT HỆ NHẬN DẠNG CHỮ VIẾT TAY ........15 1.2.1. Tiền xử lý ......................................................................................................16 1.2.1.1. Nhị phân hóa ảnh .................................................................................16 1.2.1.2. Lọc nhiễu ..............................................................................................16 1.2.1.3. Chuẩn hóa kích thước ảnh ...................................................................17 1.2.1.4. Làm trơn biên chữ ................................................................................17 1.2.1.5. Làm đầy chữ .........................................................................................18 1.2.1.6. Làm mảnh chữ ......................................................................................18 1.2.1.7. Điều chỉnh độ nghiêng của văn bản.....................................................18 1.2.2. Khối tách chữ ................................................................................................19 1.2.2.1. Tách chữ theo chiều nằm ngang và thẳng đứng ..................................19 1.2.2.2. Tách chữ dùng lược đồ sáng ................................................................19 1.2.3. Trích chọn đặc trưng .....................................................................................20 1.2.3.1. Biến đổi toàn cục và khai triển chuỗi...................................................20 1.2.3.2. Đặc trưng thống kê...............................................................................22 1.2.3.3. Đặc trưng hình học và hình thái ..........................................................23 1.2.4. Huấn luyện và nhận dạng ..............................................................................24 1.2.5. Hậu xử lý .......................................................................................................24 1.3. CÁC PHƯƠNG PHÁP NHẬN DẠNG CHỮ VIẾT TAY ......................................25 1.3.1. Đối sánh mẫu.................................................................................................25 1.3.2. Phương pháp tiếp cận cấu trúc ......................................................................26 1 1.3.2.1. Phương pháp ngữ pháp (Grammatical Methods):...............................27 1.3.2.2. Phương pháp đồ thị (Graphical Methods):..........................................28 1.3.3. Mạng nơ ron ..................................................................................................28 1.3.4. Các phương pháp thống kê............................................................................29 1.3.4.1. Nhận dạng phi tham số.........................................................................29 1.3.4.2. Nhận dạng có tham số ..........................................................................30 1.3.4.3. Mô hình Markov ẩn (HMM - Hidden Markov Model).........................30 1.3.5. Máy véc tơ tựa (SVM) ..................................................................................30 1.3.6. Kết hợp các kỹ thuật nhận dạng ....................................................................31 1.3.6.1. Kiến trúc tuần tự ..................................................................................31 1.3.6.2. Kiến trúc song song..............................................................................32 1.3.6.3. Kiến trúc lai ghép.................................................................................32 1.4. KẾT LUẬN.............................................................................................................33 CHƯƠNG 2: PHƯƠNG PHÁP MÁY VÉC TƠ TỰA .............................................34 2.1. GIỚI THIỆU ...........................................................................................................34 2.2. SVM TUYẾN TÍNH...............................................................................................35 2.2.1. Siêu phẳng với khoảng cách lề cực đại .........................................................36 2.2.2. Tìm siêu phẳng tối ưu....................................................................................38 2.2.3. Phân lớp mềm................................................................................................39 2.3.4. Giải bài toán tối ưu........................................................................................40 2.3. SVM PHI TUYẾN ..................................................................................................45 2.3.1. Không gian đặc trưng....................................................................................46 2.3.2. Hàm nhân ......................................................................................................47 2.4. LÝ THUYẾT CHIỀU VC.......................................................................................48 2.4.1. Cực tiểu hóa rủi ro cấu trúc ...........................................................................48 2.4.2. Cực tiểu hóa rủi ro thực nghiệm....................................................................49 2.4.3. Cực tiểu hóa cận rủi ro ..................................................................................50 2.5. CÁC THUẬT TOÁN HUẤN LUYỆN SVM..........................................................52 2.5.1. Thuật toán chặt khúc .....................................................................................52 2.5.2. Thuật toán phân rã .........................................................................................53 2.5.3. Thuật toán SMO ............................................................................................54 2 2.5.3.1. Tối ưu hai nhân tử Lagrange ...............................................................54 2.5.3.2. Chọn hai nhân tử để tối ưu theo phương pháp heuristic .....................56 2.6. SVM ĐA LỚP.........................................................................................................56 2.6.1. Chiến lược một chống một (OVO: One – versus – One)..............................56 2.6.2. Chiến lược một chống phần còn lại (OVR: One – versus – Rest) ................57 2.6.3. Chiến lược phân cấp......................................................................................57 2.7. ỨNG DỤNG SVM VÀO BÀI TOÁN NHẬN DẠNG CHỮ VIẾT TAY RỜI RẠC .......................................................................................................................................58 2.7.1. Tiền xử lý ......................................................................................................58 2.7.2. Trích chọn đặc trưng .....................................................................................59 2.7.3. Huấn luyện mô hình và nhận dạng................................................................59 2.7.4. Kết quả thực nghiệm .....................................................................................59 2.8. KẾT LUẬN.............................................................................................................63 CHƯƠNG 3: ÁP DỤNG MÁY VÉC TƠ TỰA VÀO BÀI TOÁN NHẬN DẠNG CHỮ VIỆT VIẾT TAY RỜI RẠC.............................................................................65 3.1. TRÍCH CHỌN ĐẶC TRƯNG CHO BÀI TOÁN NHẬN DẠNG CHỮ VIẾT TAY RỜI RẠC .......................................................................................................................65 3.1.1. Trọng số vùng (Zoning) ................................................................................65 3.1.2. Biểu đồ chiếu (Projection histograms) ..........................................................66 3.1.3. Trích chọn theo chu tuyến (Contour Profile) ................................................66 3.1.4. Trích chọn đặc trưng wavelet Haar ...............................................................67 3.1.5. Kết quả thực nghiệm .....................................................................................69 3.2. NHẬN DẠNG CHỮ VIỆT VIẾT TAY RỜI RẠC .................................................70 3.2.1. Đặt vấn đề......................................................................................................70 3.2.2. Xây dựng mô hình nhận dạng chữ Việt viết tay rời rạc ................................71 3.2.2.1. Tiền xử lý ..............................................................................................71 3.2.2.2. Phân nhóm sơ bộ ..................................................................................74 3.2.2.3. Trích chọn đặc trưng............................................................................75 3.2.2.4. Xây dựng các máy phân lớp SVM ........................................................75 3.2.3. Kết quả thực nghiệm .....................................................................................75 3.3. CẢI TIẾN TỐC ĐỘ NHẬN DẠNG CHỮ VIỆT VIẾT TAY RỜI RẠC ................77 3 3.3.1. Rút gọn số chiều của các véc tơ đặc trưng ....................................................77 3.3.2. Cải tiến tốc độ của các máy phân lớp SVM ..................................................78 3.3.2.1. Phương pháp tập thu gọn.....................................................................78 3.3.2.2. Phương pháp Bottom – Up...................................................................80 3.3.3. Kết quả thực nghiệm .....................................................................................85 3.4. KẾT LUẬN.............................................................................................................86 PHẦN KẾT LUẬN ......................................................................................................87 DANH MỤC CÁC CÔNG TRÌNH Đà CÔNG BỐ CỦA TÁC GIẢ......................90 TÀI LIỆU THAM KHẢO...........................................................................................91 4 DANH MỤC CÁC KÝ HIỆU, CỤM TỪ VIẾT TẮT Ký hiệu Thuật ngữ HMM Hidden Markov Model (Mô hình Markov ẩn) kernel hàm nhân KKT Karush-Kuhn-Tucker k-NN k – láng giềng gần nhất LP Hàm Lagrange của bài toán gốc (primal) LD Hàm Lagrange của bài toán đối ngẫu (dual) L2 Không gian các hàm khả vi liên tục cấp 2 MD Marginal Difference MMD Maximum Marginal Difference 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) OVO One – versus – One OVR One – versus – Rest off-line ngoại tuyến on-line trực tuyến QP Quadratic Programing (quy hoạch toàn phương) RBF Radial Basic Function 5 SOM Self Origanizing Map SMO Sequential Minimal Optimization SV Support vector (véc tơ tựa) SVM Support Vector Machines (Máy véc tơ tựa) TSMN two-stage multinetwork (máy phân lớp đa mạng hai giai đoạn) USPS United States Postal service VC Vapnik – Chervonenkis working set tập làm việc ||w||2 Chuẩn Euclide của siêu phẳng 6 DANH MỤC CÁC BIỂU BẢNG Bảng 2.1. Kết quả thực nghiệm trên tập USPS ..................................................... 57 Bảng 2.2. Kết quả thực nghiệm trên tập MNIST ................................................... 57 Bảng 2.3. Kết quả thực nghiệm với các hàm nhân khác nhau trên tập USPS. ...... 58 Bảng 2.4. Kết quả huấn luyện với hàm nhân Gausse. ........................................... 58 Bảng 2.5. Kết quả huấn luyện với kích thước cache khác nhau. ........................... 59 Bảng 2.6. So sánh kết quả nhận dạng của SVM với các mô hình mạng nơ ron. ... 59 Bảng 2.7. So sánh một số phương pháp phân lớp trên bộ dữ liệu MNIST.................. 60 Bảng 3.1. Kết quả nhận dạng theo các loại đặc trưng khác nhau. ....................... 67 Bảng 3.2. Kết quả nhận dạng trên các tập dữ liệu tiếng Việt viết tay rời rạc. ...... 74 Bảng 3.3. Kết quả nhận dạng trên tập dữ liệu TestData5. .................................... 82 7 DANH MỤC CÁC HÌNH VẼ Hình 1.1. Sơ đồ tổng quát của một hệ thống nhận dạng chữ viết tay. ................... 12 Hình 1.2. Nhị phân hóa ảnh. .................................................................................. 13 Hình 1.3. Nhiễu đốm và nhiễu vệt. ....................................................................... 14 Hình 1.4. Chuẩn hóa kích thước ảnh các ký tự “A” và “P”. .................................. 14 Hình 1.5. (a) Ảnh gốc, (b) Ảnh sau khi được làm trơn biên. ................................. 15 Hình 1.6. Làm mãnh chữ........................................................................................ 15 Hình 1.7. Hiệu chỉnh độ nghiêng của văn bản. ...................................................... 16 Hình 1.8. Tách dòng chữ dựa trên histogram theo chiều ngang của khối chữ. ..... 16 Hình 1.9. Xác định khoảng cách giữa hai kí tự và giữa hai từ............................... 17 Hình 2.1. Siêu phẳng tách tuyến tính. .................................................................... 34 Hình 2.2. So sánh hiệu quả phân lớp giữa máy tuyến tính thông thường với SVM. .. 34 Hình 2.3. Siêu phẳng tách hai lớp ‘o’ và ‘+’. ........................................................ 35 Hình 2.4. Phân lớp mềm......................................................................................... 36 Hình 2.5. Ánh xạ dữ liệu vào không gian đặc trưng. ............................................ 42 Hình 2.6. Độ tin cậy VC tăng theo h...................................................................... 47 Hình 2.7. Họ hàm được chia làm các tập con theo chiều VC tăng dần. ................ 47 Hình 2.8. Không phải 3 điểm nào cũng tách được bởi đường thẳng. .................... 48 Hình 2.9. Với 3 điểm không thẳng hàng trong R2 thì luôn tách được .................. 49 Hình 2.10. Mô hình nhận dạng chữ viết tay rời rạc. .............................................. 55 Hình 2.11. Chọn đặc trưng ma trận nhị phân......................................................... 56 Hình 2.12. Các mẫu chữ viết tay trích từ tập các tập dữ liệu USPS và MNIST.... 57 8 Hình 3.1. Trích chọn đặc trưng trọng số vùng. ...................................................... 62 Hình 3.2.Trích chọn các biểu đồ chiếu ngang, dọc và 2 đường chéo. ................... 63 Hình 3.3. Trích chọn các khối bên ngoài của chữ.................................................. 63 Hình 3.4. Quá trình trích chọn đặc trưng ............................................................... 64 Hình 3.5. Dãy đặc trưng wavelet Haar................................................................... 66 Hình 3.6. Kiến trúc của hệ nhận dạng chữ viết tay tiếng Việt ............................... 69 Hình 3.7. Một số nhiễu thường gặp khi quét ảnh................................................... 69 Hình 3.8. Chuẩn hóa ảnh. ...................................................................................... 70 Hình 3.9. Chuẩn hóa các vùng liên thông. ............................................................ 70 Hình 3.10. Các mẫu trích từ tập ký tự viết tay tiếng Việt. ..................................... 73 Hình 3.11. Độ sai lệch lề giữa siêu phẳng gốc và siêu phẳng đơn giản hóa.......... 81 9 PHẦN MỞ ĐẦU Tính cấp thiết của đề tài Nhận dạng chữ là một lĩnh vực đã được quan tâm nghiên cứu và ứng dụng từ nhiều năm nay theo hai hướng chính: 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à hiệu quả nhập thông tin vào máy tính trực tiếp từ các nguồn tài liệu. • 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ý chứng từ, hóa đơn, phiếu ghi, bản thảo viết tay... Nhận dạng chữ viết tay được tách thành hai hướng phát triển: nhận dạng chữ viết tay trực tuyến (on-line) và nhận dạng chữ viết tay ngoại tuyến (off-line). • Đến thời điểm này, bài toán nhận dạng chữ in đã được giải quyết gần như trọn vẹn (sản phẩm FineReader 9.0 của hãng ABBYY có thể nhận dạng chữ in theo 20 ngôn ngữ khác nhau, phần mềm nhận dạng chữ Việt in VnDOCR 4.0 của Viện Công nghệ Thông tin Hà Nội có thể nhận dạng được các tài liệu chứa hình ảnh, bảng và văn bản tiếng Việt với độ chính xác trên 98%,...). Tuy nhiên trên thế giới cũng như ở Việt Nam, bài toán 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 vì nó phụ thuộc quá nhiều 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 tinh thần của từng người viết. Đặc biệt đối với việc nghiên cứu nhận dạng chữ viết tay tiếng Việt lại càng gặp nhiều khó khăn hơn do bộ ký tự tiếng Việt có thêm phần dấu, rất dễ nhầm lẫm với các nhiễu. Vì vậy, đến thời điểm này có rất ít công trình công bố chính thức về các kết quả nghiên cứu nhận dạng chữ viết tay tiếng Việt. Điều này chính là động lực thúc đẩy luận án cố gắng nghiên cứu để đề xuất các giải pháp hữu hiệu cho bài toán nhận dạng chữ viết tay tiếng Việt. 10 Mục tiêu của luận án Trong những năm gần đây, máy véc tơ tựa (SVM – Support Vector Machines) được biết đến như một hướng tiếp cận phân lớp hiệu quả và đã được áp dụng thành công trong nhiều ứng dụng thực tiễn. Vì vậy, mục tiêu của luận án là nghiên cứu phương pháp máy véc tơ tựa để ứng dụng vào bài toán nhận dạng chữ viết tay rời rạc (isolated handwritten character recognition). Từ nay về sau, trong luận án này sẽ sử dụng cụm từ viết tắt SVM thay cho thuật ngữ máy véc tơ tựa. Phạm vi nghiên cứu Bài toán nhận dạng chữ viết tay hiện nay vẫn chưa đạt được nhiều kết quả khả quan bởi những thách thức sau: Với mỗi người viết khác nhau, chữ viết có độ nghiêng khác nhau (nhiều/ít, trái/phải...). • Khoảng cách giữa các kí tự và các dấu trong cùng một văn bản thường khác nhau nên rất khó tách được các ký tự, các dấu. • Cùng một kí tự trong văn bản do một người viết nhiều khi cũng có độ rộng, hẹp, cao, thấp khác nhau... • Luận án giới hạn phạm vi nghiên cứu trong khuôn khổ chữ Việt viết tay rời rạc. Chữ viết tay rời rạc ở đây được hiểu là các ký tự viết tay tách biệt, giữa phần dấu và phần chữ phải tách rời. Bài toán đặt ra là xây dựng một mô hình hiệu quả cho việc nhận dạng chữ Việt viết tay rời rạc. Những đóng góp mới của luận án Đề xuất mô hình hiệu quả cho bài toán nhận dạng chữ Việt viết tay rời rạc dựa trên cơ sở phân lớp SVM. ƒ Đề xuất một giải pháp để tăng tốc độ nhận dạng chữ Việt viết tay rời rạc trên cơ sở rút gọn số chiều của các véc tơ đặc trưng đầu vào và áp dụng phương pháp tập thu gọn để giảm thiểu số véc tơ tựa nhằm tăng tốc độ phân lớp của SVM. ƒ 11 Đề xuất một phương pháp trích chọn đặc trưng hiệu quả cho bài toán nhận dạng chữ viết tay rời rạc theo ý tưởng của phép biến đổi wavelet Haar và chứng minh được tính bất biến của đặc trưng theo phép biến đổi wavelet đối với ảnh ký tự đầu vào. ƒ Bố cục của luận án Luận án được phân thành ba chương với cấu trúc như sau: Chương 1: Tổng quan về nhận dạng chữ viết tay. Chương này giới thiệu tổng quan về tình hình nghiên cứu trong lĩnh vực nhận dạng chữ vi