Đề tài Toán ứng dụng

; 67 } - 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, A1, A2, A3, A4; - Tính Fi+1 = S1 + S2; Fi+2 = S2 + S3; Fi+3 = S4; - i = i + 3; } Phương pháp tính nhanh tổng các điểm đen trong trong thuật toán trên có thể tham khảo trong [21]. Mệnh đề (tính bất biến của đặc trưng theo phép biến đổi wavelet): Cho ma trận vuông A cấp 2n, n nguyên dương. Theo phương pháp trích chọn đặc trưng của thuật toán HaarFeature thì ma trận A bất biến đối với các đặc trưng được trích chọn. Chứng minh: Dùng phương pháp quy nạp. Ta chứng minh mệnh đề đúng với n=1. Thật vậy, giả sử x1, x2, x3, x4 là bốn phần tử của ma trận vuông cấp 2. Theo phương pháp trích chọn đặc trưng trên ta có hệ phương trình: 1 2 3 4 1 2 1 2 2 3 2 4 4 3 x x x x S x x S S x x S x S + + + =⎧⎪ + = +⎪⎨ + = +⎪⎪ =⎩ S và 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 1 = ≠ do đó hệ phương trình có nghiệm duy nhất. Vì vậy, theo cách trích chọn đặc trưng của thuật toán HaarFeature thì ma trận A bất biến với n=1. Giả sử mệnh đề đúng với n=k. Ta sẽ chứng minh mệnh đề đúng với n=k+1. Rõ ràng ma trận vuông cấp 2k+1 có kích thước gấp 4 lần ma trận vuông cấp 2k. Ta sẽ chứng minh rằng nếu mỗi một phần tư của ma trận vuông A cấp 2k+1 bất biến 68 thì ma trận vuông A cũng bất biến theo phương pháp trích chọn đặc trưng của thuật toán HaarFeature. Thật vậy, giả sử ma trận vuông A cấp 2k+1 được chia thành 4 khối con A1, A2, A3, A4 kích thước 2k có tổng các điểm đen tương ứng là S1, S2, S3, S4. Với cách chia thành 4 khối như vậy thì ma trận A sẽ có nghiệm duy nhất X1=S1, X2=S2, X3=S3, X4=S4 tương ứng với các phần tử A1, A2, A3, A4. Mà mỗi khối Ai, i=1..4 là bất biến theo phương pháp trích chọn đặc trưng của thuật toán HaarFeature nên ma trận A cũng bất biến theo phương pháp trích chọn đặc trưng trên. Trong thực nghiệm, với phần chữ chúng tôi chọn n=4, như vậy ta có: 1 + 3 + 4×3 + 4×4×3 + 4×4×4×3 = 256 đặc trưng, còn với phần dấu chúng tôi chọn n=3, như vậy có tất cả 64 đặc trưng. Hình 3.5. Dãy đặc trưng wavelet Haar. 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 của chữ (hình 3.5). 3.1.5. Kết quả thực nghiệm Trong phần này, luận án cài đặt thử nghiệm mô hình nhận dạng chữ viết tay rời rạc với các loại đặc trưng đã nêu trên đối với bộ dữ liệu MNIST và tập dữ liệu chữ viết tay tiếng Việt không dấu rời rạc VietCHAR. Tập dữ liệu VietCHAR bao gồm 10000 mẫu ký tự viết tay tiếng Việt không dấu, trong đó sử dụng 8000 mẫu dùng để huấn luyện và 2000 mẫu phục vụ cho việc nhận dạng. Các kết quả thực nghiệm ở chương 2 cho thấy mô hình SVM được xây dựng theo chiến lược OVO có độ chính xác phân lớp tốt nhất. Vì vậy, phần này sẽ xây dựng 69 các máy phân lớp nhị phân theo chiến lược OVO, sử dụng thuật toán huấn luyện SMO với hàm nhân Gausse. Bảng 3.1. Kết quả nhận dạng theo các loại đặc trưng khác nhau. Độ chính xác Loại đặc trưng Số chiều của véc tơ đặc trưng MNIST VietCHAR Zoning 64 97.5% 79.3% Projection histograms 94 97.0% 76.8% Contour profiles 64 96.4% 75.1% wavelet Haar 256 97.8% 82.7% Các kết quả thực nghiệm ở bảng 3.1 cho thấy sử dụng đặc trưng wavelet Haar vào bài toán nhận dạng chữ viết tay rời rạc cho độ chính xác cao hơn so với sử dụng các đặc trưng khác. Tuy nhiên, do bộ ký tự tiếng Việt quá đa dạng nên việc áp dụng các đặc trưng này lên tập dữ liệu viết tay tiếng Việt vẫn chưa đạt hiệu quả cao. Mặt khác, tốc độ phân lớp trên tập dữ liệu VietCHAR rất chậm do quá trình phân lớp phải duyệt qua quá nhiều máy phân lớp nhị phân. Vì vậy cần phải xây dựng một mô hình hiệu quả hơn nhằm tăng tốc độ cũng như độ chính xác cho bài toán nhận dạng chữ Việt viết tay rời rạc. Trong phần sau, luận án sẽ đề xuất 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. 3.2. NHẬN DẠNG CHỮ VIỆT VIẾT TAY RỜI RẠC 3.2.1. Đặt vấn đề Toàn bộ tập ký tự tiếng Việt có tất cả 99 ký tự, bao gồm: các chữ số {0,...,9}, các ký tự không dấu {A, B, C, D, Đ, E, G, H, I, K, L, M, N, O, P, Q, R, S, T, U, V, X, Y} và các ký tự có dấu {Ă, Â, À, Ả, Ã, Á, Ạ, Ằ, Ẳ, Ẵ, Ắ, Ặ, Ầ, Ẩ, Ẫ, Ấ, Ậ, Ê, È, Ẻ, Ẽ, É, Ẹ, Ề, Ể, Ễ, Ế, Ệ, Ì, Ỉ, Ĩ, Í, Ị, Ô, Ơ, Ò, Ỏ, Õ, Ó, Ọ, Ồ, Ổ, Ỗ, Ố, Ộ, Ờ, Ở, Ỡ, Ớ, Ợ, Ư, Ù, Ủ, Ũ, Ú, Ụ, Ừ, Ử, Ữ, Ứ, Ự, Ỳ, Ỷ, Ỹ, Ý, Ỵ}. Bài toán chúng tôi đặt ra ở đây là xây dựng một mô hình nhận dạng chữ Việt viết tay rời rạc. Bài toán này được xem như một ứng dụng với quy mô lớn. Khi giải bài toán này sẽ vấp phải một số vấn đề sau: 70 0 Để đảm bảo độ chính xác cho hệ thống nhận dạng, mỗi lớp phải có một số lượng mẫu đủ lớn để huấn luyện. 0 Bùng nổ số lớp (99 lớp). Nếu sử dụng chiến lược OVO cho bài toán phân lớp thì hệ thống phải xây dựng 4851 máy phân lớp SVM nhị phân. Điều này sẽ làm cho hệ thống huấn luyện và nhận dạng rất chậm, khó có thể đáp ứng được cho các ứng dụng thời gian thực, thậm chí không đủ không gian nhớ để hệ thống huấn luyện do số véc tơ tựa sinh ra lớn hơn rất nhiều lần so với tổng số lượng mẫu tham gia huấn luyện. 0 Bộ ký tự tiếng Việt có nhiều ký tự với hình dáng rất giống nhau, chỉ khác nhau chút ít về phần dấu. Do đó rất khó để phân biệt đối với chữ viết tay, điều này dẫn đến độ chính xác của hệ thống nhận dạng không cao. Trong phần tiếp theo, luận án sẽ đề xuất mộ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. 3.2.2. Xây dựng mô hình nhận dạng chữ Việt viết tay rời rạc Phần này sẽ trình bày chi tiết kiến trúc của mô hình nhận dạng chữ Việt viết tay rời rạc. Trên cơ sở các thành phần liên thông của ảnh, mô hình này phân tập ký tự tiếng Việt thành ba nhóm và tách các ký tự có dấu thành các phần rời nhau. Sau đó xây dựng các máy phân lớp SVM để nhận dạng cho từng phần chữ và phần dấu, cuối cùng ghép nối các kết quả nhận dạng của các phần chữ và dấu để có kết quả nhận dạng cuối cùng (hình 3.6). 3.2.2.1. Tiền xử lý Mục đích của giai đoạn tiền xử lý nhằm tăng độ chính xác của hệ thống nhận dạng. Ảnh quét vào thường hay bị nhiễu, các loại nhiễu phổ biến là nhiễu đốm và nhiễu vệt (hình 3.7). Để khử nhiễu đốm, sử dụng các bộ lọc trung bình và lọc trung vị là hiệu quả nhất, còn đối với các nhiễu vệt thì sử dụng phương pháp khử các vùng liên thông nhỏ tỏ ra hữu hiệu hơn. 71 Hình 3.6. Kiến trúc của hệ nhận dạng chữ viết tay tiếng Việt (a) Nhiễu đốm (b) Nhiễu vệt dài Hình 3.7. Một số nhiễu thường gặp khi quét ảnh Để thuận tiện cho việc xử lý sau này, ảnh đầu vào được biến đổi từ ảnh đa cấp xám thành ảnh nhị phân. 72 Chuẩn hóa ảnh theo vùng liên thông Chuẩn hóa ảnh nhằm mục đích tạo điều kiện thuận tiện cho công đoạn tách ảnh thành từng phần chữ và dấu. Bước 1: Xác định các vùng liên thông trên ảnh (Hình 3.8). Bước 2: Sắp xếp các vùng liên thông theo thứ tự từ trên xuống (hình 3.8b). (a) (b) Hình 3.8. 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. Bước 3: (a) (b) (c) Hình 3.9. Chuẩn hóa các vùng liên thông. - Nếu ảnh chỉ có 1 vùng liên thông: Chuẩn hóa ảnh về kích thước chuẩn 16×16 (hình 3.9a). - Nếu ảnh có 2 vùng liên thông: Gọi S(i) là diện tích vùng liên thông thứ i. Nếu S(1)>S(2) thì dấu của phần liên thông 2 là dấu nặng (.) và chỉ cần chuẩn hóa vùng liên thông 1 về kích thước chuẩn 16×16. 73 Ngược lại: Tách ảnh thành 2 phần: phần chữ và phần dấu. Chuẩn hóa phần chữ về kích thước chuẩn 16×16 và phần dấu về kích thước chuẩn 8×8 (hình 3.9b). - Nếu ảnh có 3 vùng liên thông: Nếu S(3) = Min{S(i)} thì dấu của phần liên thông này là dấu nặng (.). Do đó chỉ cần chuẩn hóa thành phần liên thông 1 về kích thước chuẩn 8×8 và thành phần liên thông 2 về kích thước chuẩn 16×16. Ngược lại: Tách ảnh thành 3 phần từ các vùng liên thông. Chuẩn hóa các vùng liên thông 1 và 2 về kích thước chuẩn 8×8 và chuẩn hóa vùng liên thông 3 về kích thước chuẩn 16×16 (hình 3.9c). 3.2.2.2. Phân nhóm sơ bộ Dựa vào số thành phần liên thông để tách bộ ký tự tiếng Việt thành 3 nhóm: ƒ Nhóm 1: Nhóm có 1 vùng liên thông {A, B, C, D, Đ, E, G, H, I, K, L, M, N, O, P, Q, R, S, T, U, V, X, Y, Ơ, Ư}. ƒ Nhóm 2: Nhóm có 2 vùng liên thông {Ă, Â, À, Ả, Ã, Á, Ạ, Ê, È, Ẻ, Ẽ, É, Ẹ, Ì, Ỉ, Ĩ, Í, Ị, Ô, Ò, Ỏ, Õ, Ó, Ọ, Ờ, Ở, Ỡ, Ớ, Ợ, Ù, Ủ, Ũ, Ú, Ụ, Ừ, Ử, Ữ, Ứ, Ự, Ỳ, Ỷ, Ỹ, Ý, Ỵ}. ƒ Nhóm 3: Nhóm có 3 vùng liên thông { Ằ, Ẳ, Ẵ, Ắ, Ặ, Ầ, Ẩ, Ẫ, Ấ, Ậ, Ề, Ể, Ễ, Ế, Ệ, Ồ, Ổ, Ỗ, Ố, Ộ} Với cách phân nhóm này thì các máy phân lớp SVM được xây dựng cho từng nhóm đều rất khả thi. Đối với nhóm 2 và 3, mặc dù số lớp rất lớn nhưng tất cả đều xuất phát từ các nguyên âm {A, E, I, O, U, Y} và các dấu {/, \, ?, ~, ^, ∨} (sắc, huyền, hỏi, ngã, dấu ô và dấu ă). Vì vậy đối với hai nhóm này, chỉ cần xây dựng một máy phân lớp SVM cho các nguyên âm và một máy cho các dấu là đủ, sau khi có kết quả nhận dạng thì kết nối chúng với nhau để có kết quả nhận dạng cuối cùng. Còn đối với nhóm 1, tuy số lớp hơi nhiều nhưng hoàn toàn có thể xử lý được trong một máy tính cá nhân thông thường. 74 Vì vậy, việc phân nhóm sơ bộ này sẽ khắc phục được sự bùng nổ số lớp, giúp cho việc giải bài toán nhận dạng chữ Việt viết tay rời rạc có thể thực hiện được trên các máy tính cá nhân. 3.2.2.3. Trích chọn đặc trưng Trong thực nghiệm, luận án cài đặt thử nghiệm trên hai loại đặc trưng: ƒ Kết hợp các đặc trưng thống kê (ZPC - Zones, Projection histograms và Contour profiles): Với phần chữ, chúng tôi chọn kích thước ảnh 16×16, như vậy mỗi véc tơ đầu vào có tất cả : 64 + 94 + 64 = 222 đặc trưng, còn phần dấu với kích thước ảnh 8×8 thì véc tơ đầu vào sẽ có 16 + 46 +32 = 94 đặc trưng. ƒ Đặc trưng wavelet Haar: Với phần chữ, chúng tôi chọn kích thước ảnh 16×16, như vậy mỗi véc tơ đầu vào có tất cả : 1 + 3 + 4×3 + 4×4×3 + 4×4×4×3 = 256 đặc trưng, còn phần dấu với kích thước ảnh 8×8 thì véc tơ đầu vào có 64 đặc trưng. 3.2.2.4. Xây dựng các máy phân lớp SVM Với việc phân nhóm sơ bộ như trên, chỉ cần xây dựng 3 máy phân lớp SVM, sử dụng một trong hai loại đặc trưng để huấn luyện phân lớp và nhận dạng. ƒ SVM1: Máy phân lớp đối với nhóm ký tự có 1 vùng liên thông {A, B, C, D, Đ, E, G, H, I, K, L, M, N, O, P, Q, R, S, T, U, V, X, Y, Ơ, Ư}. ƒ SVM2: đối với các ký tự có dấu thì phần chữ đều là các nguyên âm, vì vậy máy này chỉ phân lớp các nguyên âm {A, E, I, O, U, Y}. ƒ SVM3: phân lớp các dấu {/, \, ?, ~, ^, ∨} (sắc, huyền, hỏi, ngã, dấu ô, dấu ă). 3.2.3. Kết quả thực nghiệm Dữ liệu chữ viết tay tiếng Việt được thu thập từ 655 người viết khác nhau, đối tượng chủ yếu là sinh viên. Mỗi người viết khoảng 200 chữ in hoa, các ký tự được viết rời rạc. Chúng tôi chọn lọc ra 52485 mẫu để tiến hành thực nghiệm, trong đó có 20925 mẫu ký tự không dấu, 2485 mẫu các dấu tiếng Việt, phần còn lại là các 75 mẫu ký tự có dấu. Trong 20925 mẫu chữ không dấu, chúng tôi sử dụng 13782 mẫu để huấn luyện, phần còn lại phục vụ cho việc nhận dạng (hình 3.10). Hình 3.10. Các mẫu trích từ tập ký tự viết tay tiếng Việt. Ba tập dữ liệu sau đây được xây dựng để phục vụ cho việc huấn luyện 3 máy phân lớp SVM: • TrainData1: Tập các dấu tiếng Việt {/, \, ?, ~, ^, ∨}, với 2485 mẫu. • TrainData2: Tập các chữ cái nguyên âm tiếng Việt {A, E, I, O, U, Y}, với 4128 mẫu được lấy ra từ 13782 mẫu chữ không dấu. • TrainData3: Tập các chữ cái tiếng Việt không dấu {A, B, C, D, Đ, E, G, H, I, K, L, M, N, O, P, Q, R, S, T, U, V, X, Y, Ơ, Ư}, với 13782 mẫu. Tập dữ liệu phục vụ cho việc nhận dạng (test) bao gồm 36218 mẫu, trong đó có 7143 mẫu chữ không dấu và 29075 mẫu chữ có dấu. Để thuận lợi cho việc đánh giá độ chính xác đối với từng nhóm ký tự theo vùng liên thông, 5 tập dữ liệu được xây dựng để phục vụ cho việc nhận dạng, các tập dữ liệu này phân bố như sau: • TestData1: Tập các ký tự tiếng Việt có 1 vùng liên thông, với 7143 mẫu. • TestData2: Tập các nguyên âm tiếng Việt, với 1500 mẫu được trích ra từ 7143 mẫu của TestData1. • TestData3: Tập các ký tự tiếng Việt có 2 vùng liên thông, với 16856 mẫu. 76 • TestData4: Tập các ký tự tiếng Việt có 3 vùng liên thông, với 12219 mẫu. • TestData5 = TestData1 ∪ TestData3 ∪ TestData4. 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. Độ chính xác Tập mẫu Số mẫu ZPC wavelet Haar TestData1 7143 84.3% 82.2% TestData2 1500 99.7% 99.6% TestData3 16856 92.2% 90.7% TestData4 12219 91.6% 87.8% TestData5 36218 90.5% 88.1% Kết quả thực nghiệm ở bảng 1 cho thấy tập TestData2 cho độ chính xác cao hơn nhiều so với tập TestData1. Do tập TestData2 chỉ chứa 6 nguyên âm với các hình dáng rất khác nhau nên ít bị nhầm lẫn, trong khi đó tập TestData 1 lại phải phân biệt quá nhiều chữ cái với hình dáng tương tự nhau ({B,Đ},{C,G},{U,Ư,V},...) nên rất dể bị nhầm lẫn, vì vậy mà độ chính xác không cao. Có thể do công đoạn tách dấu và ghép dấu chưa được tốt nên các tập TestData3 và TestData4 đạt độ chính xác không cao bằng tập TestData 2. Kết quả nhận dạng cuối cùng ở tập TestData5 cho thấy việc sử dụng các tập đặc trưng được lựa chọn kết hợp với SVM vào bài toán nhận dạng chữ Việt viết tay rời rạc đạt độ chính xác tương đối cao. 3.3. CẢI TIẾN TỐC ĐỘ NHẬN DẠNG CHỮ VIỆT VIẾT TAY RỜI RẠC Trong phần này, các đặc trưng của các véc tơ đầu vào sẽ được rút gọn và áp dụng phương pháp tập thu gọn [84] để giảm thiểu tối đa số véc tơ tựa của các SVM nhị phân nhằm cải tiến tốc độ nhận dạng. 3.3.1. Rút gọn số chiều của các véc tơ đặc trưng Phần này tìm cách rút gọn số chiều của tập đặc trưng ZPC. Thay vì lấy toàn bộ các đặc trưng, đối với mỗi dòng, cột hoặc đường chéo của ảnh, chỉ lấy xen kẻ các 77 đặc trưng để giảm đi một nửa đặc trưng của véc tơ đầu vào. Như vậy đối với ảnh kích thước 16×16, véc tơ đầu vào chỉ còn lại 111 đặc trưng, còn đối với ảnh kích thước 8×8, véc tơ đầu vào chỉ còn lại 47 đặc trưng. 3.3.2. Cải tiến tốc độ của các máy phân lớp SVM Phần này áp dụng phương pháp tập thu gọn theo hướng tiếp cận của Burges (1996) [84] nhằm tăng tốc độ nhận dạng của các máy phân lớp SVM nhị phân. Quá trình thu gọn các véc tơ tựa được thực hiện bằng cách lựa chọn hai véc tơ tựa gần nhất của cùng một lớp và thay thế chúng bằng một véc tơ mới cho tới khi có được tập véc tơ thu gọn tương đương với tập các véc tơ tựa ban đầu. Tập thu gọn có một số tính chất sau đây: ƒ Các véc tơ thu gọn xuất hiện trong hàm quyết định phân lớp SVM cũng có chức năng tương đương như các véc tơ tựa xuất hiện trong hàm quyết định phân lớp của SVM gốc, tuy nhiên chúng không phải là các véc tơ tựa. Vì vậy chúng không nhất thiết phải nằm trên lề phân cách của siêu phẳng tối ưu. ƒ Khác với các véc tơ tựa, các véc tơ thu gọn không phải là các mẫu huấn luyện. Chúng được tính toán để thay thế cho các véc tơ tựa của SVM gốc đã được huấn luyện. ƒ Phương pháp tập thu gọn có thể áp dụng được ở bất kỳ ứng dụng nào có sử dụng phương pháp phân lớp SVM. Phương pháp tập thu gọn có thể trình bày tóm tắt như sau: 3.3.2.1. Phương pháp tập thu gọn Đối với bài toán phân lớp nhị phân, luật quyết định SVM được cho bởi công thức: 1 ( , ) SVN i i i y sign K x x b = ⎛= α⎜⎝ ⎠∑ ⎞+ ⎟ (3.1) 78 trong đó αi là các trọng số của các véc tơ tựa xi, x là véc tơ đầu vào cần phân lớp, K(x,xi) là một hàm nhân trong không gian đặc trưng, b là độ lệch của siêu phẳng so với gốc tọa độ và NSV là số véc tơ tựa. Ý tưởng chính của phương pháp tập thu gọn là tìm số nhỏ nhất NZ<NSV, và tập thu gọn tương ứng {(zi, βi)}, i=1...NZ sao cho ρ = |Ψ’ - Ψ| đạt cực tiểu, tức là tìm cách xấp xỉ véc tơ chuẩn Ψ của siêu phẳng tối ưu gốc bởi véc tơ chuẩn Ψ’ của siêu phẳng tối ưu theo tập thu gọn sao cho sai số về độ chính xác phân lớp của SVM đạt cực tiểu, trong đó: 1 ( ) SVN i i i x = Ψ = α Φ∑ và 1 ' ( ZN )j j j z = Ψ = β Φ∑ với NZ < NSV, zi ∈ RD, βi ∈ R. Như vậy, để phân lớp một mẫu x, (3.1) được thay bởi 1 ( , ) ZN i i i y sign K x z b = ⎛= β⎜⎝ ⎠∑ ⎞+ ⎟ j (3.2) trong đó NZ < NSV, và tập thu gọn tương ứng là {(zi,βi)}i=1,...,Nz. Phương pháp xây dựng tập thu gọn (Burges, 1996) bắt đầu bằng cách thay thế Ψ với ảnh của một véc tơ đầu vào và trọng số tương ứng của nó (z1, β1), sau đó lặp lại việc tìm (zm+1, βm+1) sao cho ảnh của nó xấp xỉ với các véc tơ Ψm (Ψ0= Ψ): 1 1 ( ) ( ) SVN m m i i j i j x z = = Ψ = α Φ − β Φ∑ ∑ (3.3) Trong nhiều trường hợp không thể tìm ra chính xác zm và βm để Ψm=0 thì zm là các véc tơ sao cho 2 1 1 1 1 ( ) ( ) ( ) ( ) SV m m m N m i i j j m m i j z x z z − − = = ρ = Ψ −β Φ ⎛ ⎞= α Φ − β Φ −β Φ⎜ ⎟⎝ ⎠∑ ∑ (3.4) đạt cực tiểu. 79 Trong trường hợp tổng quát, có thể dùng các kỹ thuật tối ưu không ràng buộc để cực tiểu hóa ρ. Hạn chế của các phương pháp này là chúng có thể mắc phải một số cực tiểu địa phương của hàm ρ. Để ngăn chặn tình huống cực tiểu địa phương, việc tìm kiếm mỗi véc tơ mới buộc phải lặp lại nhiều lần các giá trị khởi tạo khác nhau. Có nhiều kỹ thuật để xây dựng tập thu gọn. Phần này sử dụng phương pháp Bottom-Up của Nguyễn Đức Dũng và Hồ Tú Bảo [20] để tìm tập thu gọn. Ý tưởng chính của phương pháp Bottom-Up là thay thế hai véc tơ tựa gần nhất thuộc về cùng một lớp bởi một véc tơ mới cho đến khi ρ=|ψ’-ψ| đạt cực tiểu. Thông qua việc phân tích mối quan hệ giữa các véc tơ trong không gian đầu vào và không gian đặc trưng, phương pháp này tạo ra các véc tơ mới bằng cách tìm điểm cực đại duy nhất của hàm một biến trong khoảng (0,1) mà không cần phải tìm cực tiểu của một hàm nhiều biến với các giá trị cực tiểu địa phương trong các phương pháp tập thu gọn trước đây. 3.3.2.2. Phương pháp Bottom – Up 1) Đơn giản hóa hai véc tơ tựa Giải pháp SVM có thể phân tích theo một quan điểm sau: nếu mỗi ảnh của các véc tơ tựa trong không gian đặc trưng được sử dụng như một lực li iF = α ψ trên siêu phẳng tối ưu thì giải pháp SVM này thỏa mãn các điều kiện cân bằng: tổng của các lực và mô men quay sẽ bị triệt tiêu (với lψ là modul của véc tơ Ψ) (Burges, 1998 [12]). Trong hệ cân bằng này, nếu thay thế hai lực bằng một lực khác tương đương thì trạng thái cân bằng của hệ thống không thay đổi. Trong một giải pháp SVM, nếu ta thay thế hai ảnh Φ(xi) và Φ(xj) của hai véc tơ tựa thuộc cùng một lớp bằng một véc tơ M = m.Φ(xi) + (1-m).Φ(xj), trong đó m= αi/( αi+αj) và trọng số tương ứng của véc tơ M là αm= (αi+αj), thì với bất kỳ điểm x nào trong không gian đầu vào, công thức (3.1) cũng có thể tính toán theo (NSV -1) véc tơ: 1, , ( , ) . ( ) SVN k k m k k i k j y sign K x x M x b = ≠ ≠ ⎛ ⎞= α +α Φ⎜ ⎟⎝ ⎠∑ + (3.5) 80 Tuy nhiên, M không thể sử dụng một cách trực tiếp vì M là véc tơ trong không gian đặc trưng. Vì vậy phải sử dụng tiền ảnh của nó (chẳng hạn như tính toán theo một số véc tơ đầu vào z mà Φ(z) = M), và trong nhiều trường hợp không thể tìm chính xác tiền ảnh của M. Sau khi thử tìm chính xác tiền ảnh, xấp xỉ M bởi Φ(z) của một số véc tơ đầu vào z. Xấp xỉ tối ưu này có thể đạt được nếu chọn một véc tơ z sao cho giá trị 2( )M z−Φ đạt cực tiểu, hoặc trong các trường hợp khác, phải giải bài toán tối ưu: 2min ( ) z M z−Φ (3.6) Các mệnh đề sau đây sẽ cho cách để tìm véc tơ z một cách hiệu quả mà chỉ cần tìm điểm cực đại duy nhất của hàm một biến trên khoản (0,1). Mệnh đề 3.1: Cho hàm nhân Gaussian K(x,y)=exp(-γ||x-y||2), xấp xỉ tối ưu theo chuẩn 2 của M = m.Φ(xi) + (1-m).Φ(xj), m= αi/( αi+αj), αiαj>0, là ảnh của z được xác định bởi: z = k.xi + (1-k).xj (3.7) trong đó k là điểm cực đại của 2(1-k) k ij ij( ) . (1 ). 2 f k m C m C= + − (3.8) với Cij=K(xi,xj). Chứng minh: Xem [20]. Mệnh đề 3.2: Cho hàm nhân đa thức K(x,y)=(x.y)p, xấp xỉ tối ưu theo chuẩn 2 của M = m.Φ(xi) + (1-m).Φ(xj), m= αi/( αi+αj), αi.αj>0, là ảnh của z được xác định bởi: 1/ * * pM z z = z (3.9) trong đó z*= k.xi + (1-k).xj và k là điểm cực đại của h(k): h(k)=||M||u(k)v(k) với 81 / 22 2 2 2 1( ) 2( . ) (1 ) (1 ) p i i j j u k x k x x k k x k = ⎡ ⎤+ − + −⎣ ⎦ (3.10) 2 p 2 i( ) [x ( . )(1 )] (1 )[( . ) (1 )]i j i j jv k m k x x k m x x k x k= + − + − + − p (3.11) Chứng minh: Xem [20]. Điểm quan trọng trong hai mệnh đề trên là cả f(k) và h(k) đều là hàm một biến và có điểm cực đại duy nhất trên khoảng (0,1). Mệnh đề 3.3: Hệ số tối ưu β đối với việc xấp xỉ αmM = m.Φ(xi) + (1-m).Φ(xj) bởi βΦ(z) là 2 . ( ) ( ) mM z z α Φβ = Φ (3.12) Phương trình (3.12) dùng để tìm trọng số của mỗi véc tơ mới được xây dựng. Đối với tập tất cả các véc tơ thu gọn, mệnh đề sau dùng để tính lại tất cả các trọng số để có được một xấp xỉ tốt hơn. Mệnh đề 3.4: (Schoelkopf et al., 1999) [86] Các hệ số tối ưu β=( β1,..., βNz) đối với việc xấp xỉ 1 ( ) SVN i i i x = Ψ = α Φ∑ bởi 1 ' ZN ( )j j j z = Ψ = β Φ∑ (với (Φ(z1),..., Φ(zNz)) độc lập tuyến tính) được cho bởi β=(Kz)-1Kzxα (3.13) trong đó Kijz= Φ(zi).Φ(zj) và Kijzx= Φ(zi).Φ(xj). Theo Schoelkopf và các cộng sự [86], (3.13) luôn cho các hệ số tối ưu để đạt được một giải pháp xấp xỉ giải pháp SVM gốc. 2) Đơn giản hóa giải pháp véc tơ tựa Thủ tục đơn giản hóa lặp lại việc thay thế hai véc tơ tựa xi và xj bằng một véc tơ mới z bằng cách sử dụng phương pháp đã được mô tả trong phần 3.3.2.1. Việc xử lý này có thể xem là một thủ tục phân cụm theo chiến lược phân cấp từ dưới lên (bottom-up), chiến lược này có hai vấn đề cần xem xét: Thứ nhất, tìm cách để lựa 82 chọn một cặp véc tơ tựa tốt để đơn giản hóa; thứ hai, khi nào thì dừng công việc đơn giản hóa. Lựa chọn heuristic Một cách tổng quát, cần tìm một cặp véc tơ tựa để cực tiểu giá trị d(β) = |(αmM - β Φ(z)). Φ(x)|,với mọi véc tơ đầu vào x. Tuy nhiên, không thể dùng tiêu chuẩn này vì độ phức tạp tính toán quá lớn. Hơn nữa, điều quan tâm nhất là giải pháp gốc và giải pháp cuối cùng, do đó việc xấp xỉ các giải pháp tốt tại mọi bước trung gian hoàn toàn không cần thiết. Lựa chọn heuristic là cơ sở cho việc đánh giá sai lệch giữa hai véc tơ M = m.Φ(xi) + (1-m).Φ(xj) và Φ(z) trong (3.6). Đối với các hàm nhân RBF, có thể lựa chọn xi và xj để có một giá trị cực đại Cij=K(xi,xj), trong (3.8) nếu Cij lớn hơn thì f(k) cũng lớn hơn hay độ sai lệch giữa M và Φ(z) là nhỏ hơn (nếu f(k)=1 thì độ sai lệch bằng 0). Điều này tương đương với việc chọn hai véc tơ tựa gần nhau trong cùng một lớp. Nói cách khác, đối với việc lựa chọn heuristic, thử xấp xỉ hai hàm nhân Gausse RBF bằng một hàm RBF khác, bằng trực giác dễ thấy rằng các cặp điểm càng gần nhau càng được xấp xỉ tốt hơn. Việc lựa chọn heuristic cũng được áp dụng tương tự đối với hàm nhân đa thức. Điều kiện dừng Các giải pháp đơn giản hóa phần lớn đều có sai lệch so với các giải pháp SVM gốc, do đó các giải pháp đơn giản hóa véc tơ tựa có thể làm giảm độ chính xác phân lớp của SVM. Để khắc phục điều này, cần giám sát độ sai lệch giữa hai giải pháp trong quá trình xử lý đơn giản hóa. Vì vậy quá trình đơn giản hóa sẽ dừng lại khi không còn bất kỳ cặp véc tơ tựa nào được thay bằng véc tơ mới mà tạo ra độ sai lệch vượt quá một ngưỡng cho trước. Đại lượng sau đây được gọi là độ sai lệch lề cực đại (MMD – Maximum Marginal Difference) dùng để ước lượng độ sai lệch giữa hai giải pháp véc tơ tựa. Định nghĩa 3.1: Giả sử khoảng cách từ một điểm Φ(x) tới siêu phẳng tối ưu gốc là d (d bằng 1 khi x là một véc tơ tựa nằm trên lề của siêu phẳng), và d’ là khoảng cách từ Φ(x) tới siêu phẳng mới được xác định bằng giải pháp đơn giản hóa. Độ sai lệch lề (MD) trên Φ(x) liên quan đến hai giải pháp là 83 MD(Φ(x))=|d-d’| (3.14) và độ sai lệch giữa hai giải pháp được định nghĩa như sau 1... ( ( )) SV ii N MMD Max MD x = = Φ (3.15) trong đó x1,..., SVNx là các véc tơ tựa gốc. 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. MMD dùng để đo sự sai lệch giữa hai khoảng cách từ ảnh của các véc tơ tựa gốc tới hai siêu phẳng lề H1 hoặc H2 để ước lượng độ sai lệch giữa hai giải pháp véc tơ tựa. Lý do không sử dụng độ sai lệch giữa hai véc tơ chuẩn của hai siêu phẳng ||ψ-ψ’|| ở đây là đại lượng này phụ thuộc quá nhiều vào ||ψ|| và ||ψ’||. Đối với các bài toán phức tạp (||ψ|| rất lớn) thì một độ sai lệch nhỏ giữa hai siêu phẳng có thể tạo nên một độ sai lệch ||ψ-ψ’|| rất lớn, trong khi đối với các bài toán phân lớp đơn giản hơn, một ||ψ-ψ’|| nhỏ tương ứng với một độ sai lệch lớn giữa các siêu phẳng. Vì vậy, ||ψ-ψ’|| sẽ tạo nên một sai lệch lớn giữa hai giải pháp. Sau đây là thuật toán đơn giản hóa giải pháp véc tơ tựa. Thuật toán này lặp lại việc chọn lựa hai véc tơ tựa trong cùng một lớp và thử thay thế chúng bởi một véc tơ mới. Thuật toán dừng lại khi không còn việc thay thế nào được thực hiện, cuối cùng cập nhật lại tất cả các véc tơ thu gọn và các hệ số của nó để đạt được một xấp xỉ tốt hơn: Input Tập gồm NSV véc tơ tựa {x1,..., SVNX }; Ngưỡng MMD θ; 84 Output Một tập gồm NZ véc tơ thu gọn, NZ < NSV. Method 1. PairList = {(xi,xj) | i=1,...,NSV, arg mink(||xi - xk||2), 1≤ k ≤ NSV, αiαk > 0}. 2. Sắp xếp các cặp trong PairList tăng dần theo độ sai lệch giữa hai véc tơ trong mỗi cặp; 3. PairID = 1; NZ = NSV; 4. Repeat - Gọi (xi,xj) là cặp được đánh chỉ số PairID trong PairList; - Thử thay xi và xj bởi z theo (3.7) hoặc (3.9) và trọng số β của z bởi (3.13); - If việc thay thế tạo ra MMD ≤ θ Then Thay xi và xj bởi z; Nz = Nz – 1; Cập nhật PairList; PairID = 1; Else PairID = PairID + 1; Until ; 5. Tính lại các hệ số của tất cả các véc tơ thu gọn bằng cách sử dụng (3.13); 6. Tối ưu toàn bộ tập thu gọn bằng cách áp dụng giai đoạn 2 trong [86]; 7. Return Tập thu gọn; 3.3.3. Kết quả thực nghiệm Bảng 3.3. Kết quả nhận dạng trên tập dữ liệu TestData5. Phương pháp Độ chính xác Thời gian ORG 90.5% 1928 giây RDM 90.5% 1279 giây RSM 90.4% 461 giây RDM+RSM 90.4% 218 giây 85 Bảng 3.3 trình bày một số kết quả thực nghiệm theo bốn phương án: Phương án ban đầu (ORG), thu gọn số chiều của các véc tơ đầu vào (RDM), sử dụng SVM với tập thu gọn (RSM) và cuối cùng là kết hợp cả hai phương án RDM và RSM. Kết quả thực nghiệm ở bảng 3.3 cho thấy mô hình cải tiến sử dụng cả hai phương án RDM và RSM thì tốc độ nhận dạng tăng lên 9 lần so với phương án gốc với sai số về độ chính xác phân lớp có thể chấp nhận được. 3.4. KẾT LUẬN Chương này đã đề xuất một phương trích chọn đặc trưng hiệu quả 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 này. Tác giả cũng đề xuất mộ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. Kết quả thực nghiệm cho thấy mô hình nhận dạng chữ Việt viết tay rời rạc do chúng tôi đề xuất là khả thi và đạt độ chính xác tương đối cao. Chương này cũng đề xuất hướng cải tiến để tăng tốc độ nhận dạng bằng cách rút gọn số chiều của các véc tơ đặc trưng kết hợp với phương pháp tập thu gọn để giảm tối đa số véc tơ tựa của SVM, điều này đã cải thiện đáng kể tốc độ nhận dạng. Các kết quả của chương này đã được tác giả công bố trong [4,5,6]. Các kết quả này chưa được so sánh với các kết quả khác vì bộ dữ liệu thực nghiệm chữ viết tay tiếng Việt do tác giả tự thu thập, hơn nữa hiện nay vẫn chưa có công trình công bố chính thức nào về nhận dạng chữ Việt viết tay rời rạc. 86 PHẦN KẾT LUẬN Các kết quả chính của luận án Luận án đã nghiên cứu tổng quan về một hệ nhận dạng chữ viết tay, bao gồm các bước quan trọng như: tiền xử lý, tách chữ, trích chọn đặc trưng, huấn luyện và nhận dạng, hậu xử lý. Các kết quả chính của luận án tập trung vào hai giai đoạn trích chọn đặc trưng và huấn luyện/nhận dạng, đây là hai khâu quan trọng nhất trong một hệ thống nhận dạng nhữ viết tay. Trong các phương pháp học máy tiên tiến hiện nay thì SVM được đánh giá là một trong những phương pháp phân lớp có độ chính xác cao. Vì vậy, luận án đã tập trung nghiên cứu lý thuyết SVM kết hợp với một số phương pháp trích chọn đặc trưng hiệu quả để áp dụng vào bài toán nhận dạng chữ Việt viết tay rời rạc. Cụ thể, luận án đã đạt được những kết quả sau: 1. Đề xuất mộ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ở lý thuyết SVM. Thông qua việc phân tích các thành phần liên thông của ảnh, mô hình nhận dạng phân hoạch tập ký tự tiếng Việt thành 3 nhóm và tách các ký tự có dấu thành các phần rời nhau để thuận tiện cho việc nhận dạng từng phần chữ và phần dấu. Điều này giúp cho bài toán có thể giải được trên một máy tính cá nhân bình thường với độ chính xác tương đối cao. Kết quả này đã được công bố trong [4]. 2. Đề 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 của các máy phân lớp nhị phân nhằm cải thiện tốc độ phân lớp của SVM. Kết quả này đã được công bố trong [5]. 87 3. Đề 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 theo ý tưởng của phép biến đổi wavelet Haar và đã chứng minh tính bất biến của đặc trưng đối với ảnh ký tự đầu vào. Kết quả này đã được công bố trong [6]. 4. Một số kết quả nghiên cứu khác về nhận dạng chữ viết tay rời rạc khác trong luận án được thực hiện trên các tập dữ liệu chuẩn USPS và MNIST. Các kết quả này đã được công bố trong [1,2,3]. 5. Xây dựng được một cơ sở dữ liệu chữ viết tay tiếng Việt với hơn 100000 mẫu ký tự chữ viết tay rời rạc. Đây là một nguồn dữ liệu rất cần thiết cho việc nghiên cứu nhận dạng chữ viết tay tiếng Việt trong tương lai. Hướng nghiên cứu Nhận dạng chữ viết tay là lĩnh vực nghiên cứu khó, liên quan đến nhiều lĩnh vực khác như xử lý ảnh, trí tuệ nhân tạo, lý thuyết học máy, xác suất thống kê, toán ứng dụng... Vì vậy, cho đến nay nhận dạng chữ viết tay vẫn là một bài toán mở thách thức các nhà nghiên cứu. Luận án này có thể phát triển theo các hướng sau: 1. Nghiên cứu các bất biến trên các dạng chữ viết tay để trích chọn đặc trưng cho bài toán nhận dạng. 2. SVM là một phương pháp máy học tiên tiến đang được áp dụng rộng rãi trong các ứng dụng thực tế. Tuy nhiên phương pháp này cũng có một số nhược điểm, chẳng hạn như tốc độ phân lớp chậm, trong giai đoạn huấn luyện SVM đòi hỏi không gian nhớ rất lớn, do đó các bài toán huấn luyện với số lượng mẫu lớn sẽ gặp trở ngại trong vấn đề lưu trữ. Đây cũng là một vấn đề cần nghiên cứu cải tiến để SVM có thể áp dụng vào các bài toán với quy mô lớn. 3. Chất lượng phân lớp của SVM phụ thuộc vào hai yếu tố chính: giải bài toán QP và lựa chọn hàm nhân. Việc giải bài toán QP luôn luôn đạt được giải pháp tối ưu. Do đó, vấn đề nghiên cứu lý thuyết SVM hiện nay đều tập trung vào việc lựa chọn hàm nhân. Việc lựa chọn hàm nhân và các tham số của nó như thế nào 88 để SVM phân lớp tốt hơn là vấn đề mà luận án sẽ tiếp tục nghiên cứu trong tương lai. 4. Để có được một hệ thống nhận dạng chữ viết hoàn chỉnh thì không thể không nhắc đến giai đoạn hậu xử lý. Đây là giai đoạn ghép nối các kí tự đã nhận dạng thành các cụm từ có ý nghĩa 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. Giai đoạn này góp phần đáng kể vào việc nâng cao chất lượng của hệ thống nhận dạng. Xử lý ngôn ngữ tự nhiên mà cụ thể là mô hình ngôn ngữ thống kê N-Grams đã được áp dụng rất hiệu quả trong việc kiểm tra chính tả ở công đoạn hậu xử lý của các hệ thống nhận dạng chữ viết. Đây cũng là lĩnh vực cần được nghiên cứu triển khai ứng dụng đối với các hệ thống nhận dạng chữ viết. 5. Nhận dạng chữ viết tay được xem là bài toán có quy mô lớn. Vì vậy, cần có những nghiên cứu kết hợp các phương pháp phân lớp nhằm nâng cao chất lượng cũng như tốc độ nhận dạng cũng là vấn đề mà tác giả quan tâm. 6. Tiếp tục nghiên cứu để mở rộng mô hình nhận dạng cho chữ Việt viết thường. 89 DANH MỤC CÁC CÔNG TRÌNH Đà CÔNG BỐ CỦA TÁC GIẢ [1] Phạm Anh Phương, Ngô Quốc Tạo, Lương Chi Mai, “Ứng dụng SVM cho bài toán phân lớp nhận dạng”, Kỷ yếu Hội thảo khoa học Quốc gia lần thứ ba về nghiên cứu, phát triển và ứng dụng Công nghệ thông tin và Truyền thông (ICT.rda’06), nhà xuất bản Khoa học và Kỹ thuật, Hà nội, 20-21/05/2006, tr. 393-400. [2] Phạm Anh Phương, “Nhận dạng chữ viết tay hạn chế với mô hình SVM”, Tạp chí khoa học Đại học Huế, ISSN 1859-1388, số 42, 2007, tr. 157-165. [3] Phạm Anh Phương, “Áp dụng một số chiến lược SVM đa lớp cho bài toán nhận dạng chữ viết tay hạn chế”, Tạp chí khoa học Đại học Huế, ISSN 1859-1388, số 45, 2008, tr. 109-118. [4] Pham Anh Phuong, Ngo Quoc Tao, Luong Chi Mai, “An Efficient Model for Isolated Vietnamese Handwritten Recognition”, The Fourth International Conference on Intelligent Information Hiding and Multimedia Signal Processing, IEEE Computer Society, Harbin, China, August 15 - 17, 2008, pp. 358-361. [5] Pham Anh Phuong, Ngo Quoc Tao, Luong Chi Mai, “Speeding Up Isolated Vietnamese Handwritten Recognition by Combining SVM and Statistical Features”, IJCSES International Journal of Computer Sciences and Engineering Systems, ISSN 0973-4406, Vol.2, No.4, October 2008, pp. 243- 247. [6] Phạm Anh Phương, Ngô Quốc Tạo, Lương Chi Mai, “Trích chọn đặc trưng wavelet Haar kết hợp với SVM cho việc nhận dạng chữ viết tay tiếng Việt”, Tạp chí Công nghệ Thông tin và Truyền thông, ISSN 0866-7039, kỳ 3, số 20, 10-2008, tr. 36-42. 90 TÀI LIỆU THAM KHẢO Tiếng Việt [1] Hoàng Kiếm, Nguyễn Hồng Sơn, Đào Minh Sơn, “Ứng dụng mạng nơron nhân tạo trong hệ thống xử lý biểu mẫu tự động”, Kỷ yếu hội nghị kỷ niệm 25 năm thành lập Viện Công nghệ Thông tin, 2001, tr. 560-567. [2] Bùi Minh Trí, “Quy hoạch toán học”, Nhà xuất bản Khoa học và kỹ thuật, Hà nội, 2006. [3] Lê Hoài Bắc, Lê Hoàng Thái, “Neural Network & Genetic Algorithm in Application to Handwritten Character Recognition”, Tạp chí Tin học và Điều khiển học, Tập 17, số 4, 2001, tr. 57-65. [4] Nguyễn Thị Thanh Tân, Ngô Quốc Tạo, “Một cấu trúc mạng nơ ron thích hợp cho việc nhận dạng chữ số viết tay”, Kỷ yếu hội thảo FAIR03, NXB KH&KT Hà Nội, 2004, tr. 200-210. [5] Nguyễn Thị Thanh Tân, Lương Chi Mai, “Phương pháp nhận dạng từ viết tay dựa trên mô hình mạng nơ ron kết hợp với thống kê từ vựng”, Tạp chí Tin học và Điều khiển học, Tập 22, số 2, 2006, tr. 141-154. Tiếng Anh [6] T.Fujisaki, H.S.M.Beigi, C.C.Tappert, M.Ukelson and C.G.Wolf, “Online Recognition of Unconstrained Handprinting: A stroke-based”, From Pixels Features III: Frontiers in Handwriting Recognition, S.Impedovo and J.C.Simon (eds.), 1992, pp. 297-312. [7] J.C.Simon and O.Baret, “Cursive Words Recognition”, From Pixels Features III: Frontiers in Handwriting Recognition, S.Impedovo and J.C.Simon (eds.), 1992, pp. 241-260. 91 [8] J.J.Hull, J.Favata, V.Govindaraju and S.N.Srihari, “Combination of segmentation-based and Wholistic Handwritten Word Recognition Algorithms”, From Pixels Features III: Frontiers in Handwriting Recognition, S.Impedovo and J.C.Simon (eds.), 1992, pp. 261-272. [9] V. N. Vapnik, “The Nature of Statistical Learning Theory”, Springer Verlag, 1995. [10] V. N. Vapnik, “Statistical Learning Theory”, N. Y.: John Wiley & Sons, 1998. [11] J. Friedman., “Another Approach to Polychotomous Classifications”, Technical report, Stanford university, US, 1996. [12] Christopher J. C. Burges, “A Tutorial on Support Vector Machines for Pattern Recognition”, Data Mining and Knowledge Discovery, ISSN:1384-5810, Vol. 2, No. 2, 1998, pp. 121-167. [13] J. Platt, “Fast Training of Support Vector Machines Using Sequential Minimal Optimization”, In Advences in Kernel Methods - Support Vector Learning, pp. 185-208, Cambridge, M.A, 1999, MIT Press. [14] Nello Cristianini and John Shawe-Taylor, “An Introduction to Support Vector Machines and other kernel-based learning methods”, Cambridge University Press, 2000. [15] J. Platt, N. Cristianini and J. Shawe-Taylor, “Large Margin DAGs for Multiclass Classification”, In Advances in Neural Information Processing Systems, volume 2, pp. 547-553, 2000. [16] T. Joachims, “Making large-Scale Support Vector Machine Learning Practical”, in Advances in Kernel Methods - Support Vector Learning, B. Schölkopf and C. Burges and A. Smola (ed.), MIT-Press, Cambridge, MA, 1998. [17] R. Collobert and S. Bengio, “Svmtorch: Support Vector Machines for Large- scale Regression Problems”, The Journal of Machine Learning Research, Vol. 1, 2001, pp 143 – 160. 92 [18] J. X. Dong, A. Krzyzak and C. Y. Suen, “A Fast SVM Training Algorithm”, International Journal of Pattern Recognition and Artificial Intelligence, vol. 17, no. 3, 2003, pp. 367 – 384. [19] Chih-Chung Chang and Chil-Jen Lin, “LIBSVM: a Library for Support Vector Machines”, National Taiwan University, 2004. [20] Nguyen, D.D., Ho, T.B., A Bottom-up Method for Simplifying Support Vector Solutions, IEEE Transactions on Neural Networks, Vol.17, No. 3, 2006, pp. 792-796. [21] Viola, P., Jones, M., “Rapid object detection using a boosted cascade of simple features”, Proc. Intl. Conf. on Computer Vision and Pattern Recognition (CVPR), Volume 1, pp. 511–518 , 2001. [22] Gorgevik D., Cakmakov D., “An Efficient Three-Stage Classifier for Handwritten Digit Recognition”, Proceedings of 17 Int. Conference on Pattern Recognition, ICPR2004 th , Vol. 4, pp. 507-510, IEEE Computer Society, Cambridge, UK, 23-26 August 2004. [23] Cakmakov D., Gorgevik D., “Handwritten Digit Recognition Using Classifier Cooperation Schemes”, Proceedings of the 2nd Balkan Conference in Informatics, BCI 2005, pp. 23-30, Ohrid, November 17-19, 2005. [24] G. Vamvakas, B. Gatos, I. Pratikakis, N. Stamatopoulos, A. Roniotis and S.J. Perantonis, "Hybrid Off-Line OCR for Isolated Handwritten Greek Characters", The Fourth IASTED International Conference on Signal Processing, Pattern Recognition, and Applications (SPPRA 2007), ISBN: 978- 0-88986-646-1, Innsbruck, Austria, February 2007, pp. 197-202. [25] Ngo Quoc Tao, Pham Van Hung, “Online Continues Vietnamese Handwritten Character Recognition based on Microsoft Handwritten Character Recognition Library”, IEEE Asia Pacific Conference on Circuits and Systems, APCCAS 2006, Singapore, pp. 2024-2026. 93 [26] Sergios Theodoridis and Konstantinos Koutroumbas, “Pattern Recognition”, Academic Press, 2006. [27] Robert A. Dunne, “A Statistical Approach to Neural Networks for Pattern”, N. Y.: John Wiley & Sons, 2007. [28] Mohamed Cheriet, Nawwaf Kharma, Cheng-Lin Liu And Ching Y. Suen, “Character Recognition Systems: A Guide for Students and Practioners”, N. Y.: John Wiley & Sons, 2007. [29] S. S. Wang, P. C. Chen, W. G. Lin, “Invariant Pattern Recognition by Moment Fourier Descriptor”, Pattern Recognition, vol.27, pp.1735-1742, 1994. [30] X. Zhu, Y. Shi, S. Wang, “A New Algorithm of Connected Character Image Based on Fourier Transform”, in Proc. 5th Int. Conf. Document Analysis and Recognition, pp.788-791, Bangalore, India, 1999. [31] S. W. Lee, Y. J. Kim, “Multiresolutional Recognition of Handwritten Numerals with Wavelet Transform and Multilayer Cluster Neural Network”, in Proc. 3rd Int. Conf. Document Analysis and Recognition, pp.1010-1014, Montreal, Canada, 1995. [32] T. Shioyama, H. Y. Wu, T. Nojima, “Recognition Algorithm Based On Wavelet Transform For Handprinted Chinese Characters”, in Proc. 14th Int. Conf. Pattern Recognition, vol.1, pp.229-232, 1998. [33] Y. C. Chim, A. A. Kassim, Y. Ibrahim, “Character Recognition Using Statistical Moments”, Image and Vision Computing, vol.17, pp.299-307, 1999. [34] D. Trier, A. K. Jain, T. Taxt, “Feature Extraction Method for Character Recognition - A Survey”, Pattern Recognition, vol.29, no.4, pp.641-662, 1996. [35] N. Arica, F. T. Yarman Vural, “One Dimensional Representation Of Two Dimensional Information For HMM Based Handwritten Recognition”, Pattern Recognition Letters, vol.21 (6-7), pp.583-592, 2000. 94 [36] H. Bunke, M. Roth, E. G. Schukat-Talamazzani, “Off-line Recognition of Cursive Script Produced by Cooperative Writer”, in Proc. 12th Int.Conf. Pattern Recognition, pp. 146-151, Jerusalem, Israel, 1994. [37] H. Nishida, “Structural Feature Extraction Using Multiple Bases”, Computer Vision and Image Understanding, vol.62 no1, pp. 78-89, July 1995. [38] M. Cote, E. Lecolinet, M. Cheriet, C. Y. Suen, “Reading of Cursive Scripts Using A Reading Model and Perceptual Concepts, The PERCEPTO System”, Int. Journal Document Analysis and Recognition, vol.1, no.1, pp.3-17, 1998. [39] A. Kundu, Y. He, “On optimal Order in Modeling Sequence Of Letters in Words Of Common Language As a Markov Chain”, Pattern Recognition, vol.24, no.7, pp.603 - 608, 1991. [40] M. Okamoto, K. Yamamoto, “On-line Handwriting Character Recognition Method with Directional Features and Direction Change Features”, in Proc. 4th Int. Conf. Document Analysis and Recognition, pp.926-930, Ulm, Germany, 1997. [41] J. Rocha, T. Pavlidis, “A Shape Analysis Model”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol.16, no.4, pp.394-404, 1994. [42] D. Guillevic, C. Y. Suen, “HMM-KNN Word Recognition Engine for Bank Cheque Processing”, in Proc. 14th Int. Conf. Pattern Recognition, pp. 1526- 1529, Brisbane, Australia, 1998. [43] M. Sekita, K. Toraichi, R. Mori, K. Yamamoto, H. Yamada, “Feature Extraction of Handwritten Japanese Characters by Spline Functions for Relaxation Matching”, Pattern Recognition, vol.21, no.1, pp. 9-17, 1988. [44] W. Lu, Y. Ren, C. Y. Suen, “Hierarchical Attributed Graph Representation and ecognition of Handwritten Chinese Characters”, Pattern Recognition, vol. 24, no.7, pp. 617-632, 1991. [45] S. Madhvanath, E. Kleinberg, V. Govindaraju, S. N. Srihari, “The HOVER System for Rapid Holistic Verification of Off-line Handwritten Phrases”, in 95 Proc. 4th Int. Conf. Document Analysis and Recognition, pp.855-890, Ulm, Germany,1997. [46] S. W. Lee, Y. J. Kim, “Direct Extraction of Topographic Features for Gray Scale Character Recognition”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol.17, no.7, pp.724-729, 1995. [47] M. Bokser, “Omnifont Technologies”, Proc. of the IEEE, vol.80, no.7, pp.1066-1078, 1992. [48] I. Guyon, F. Pereira, “Design of a Linguistic Postprocessor Using Variable Memory Length Markov Models”, in Proc. 3rd Int. Conf.Document Analysis and Recognition, pp.454-457, Montreal, Canada, 1995. [49] A. Kornai, K. M. Mohiuddin, S. D. Connell, “Recognition of Cursive Writing on Personal Checks”, in Proc. Int. Workshop Frontiers in Handwriting Recognition, pp. 373-378, Essex, 1996. [50] P. D. Gader, B. Forester, M. Ganzberger, A. Gillies, B. Mitchell, M.Whalen, and T. Yocum, “Recognition of Handwritten Digits Using Template and Model Matching”, Pattern Recognition, vol.24, no.5, pp.421-431, 1991. [51] D. Tubbs, “A Note on Binary Template Matching”, Pattern Recognition, vol.22, no.4, pp.359 - 365, 1989. [52] A. K. Jain, D. Zongker, “Representation and Recognition of Handwritten Digits Using Deformable Templates”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol.19, no.12, pp.1386-1391, 1997. [53] J. Hu, T. Pavlidis, “A Hierarchical Approach to Efficient Curvilinear Object Searching”, Computer Vision and Image Understanding, vol.63(2), pp. 208- 220, 1996. [54] C. C. Tappert, “Cursive Script Recognition by Elastic Matching”, IBM Journal of Research and Development, vol.26, no.6, pp.765-771, 1982. 96 [55] Keith E. Price, “Relaxation Matching Techniques Comparison”, IEEETrans. Pattern Analysis and Machine Intelligence, vol.7, no.5, pp. 617-623, 1985. [56] M. Shridhar, A. Badreldin, “High Accuracy Syntactic Recognition Algorithm for Handwritten Numerals”, IEEE Trans. Systems Man and Cybernetics, vol.15, no.1, pp.152 - 158, 1985. [57] M. Tayli, A I. Ai-Salamah, “Building Bilingual Microcomputer System” Communications of the ACM, vol.33, no.5, pp.495-504, 1990. [58] T. Pavlidis, “Recognition of Printed Text under Realistic Conditions”, Pattern Recognition Letters, pp. 326, 1993. [59] W. H. Tsai, K.S.Fu, “Attributed Grammar- A Tool for Combining Syntactic and Statistical Approaches to Pattern Recognition”, IEEE Trans. System Man and Cybernetics, vol.10, no.12, pp. 873-885, 1980. [60] A. W. Senior, A. J. Robinson, “An Off-Line Cursive Handwriting Recognition”, IEEE Trans. Pattern Recognition and Machine Intelligence, vol.20, no.3, pp. 309-322, 1998. [61] D. Bouchaffra, V. Govindaraju, S. N. Srihari, “Postprocessing of Recognized Strings Using Nonstationary Markovian Models”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol.21, no.10, pp. 990-999, 1999. [62] H. Y. Kim, J. H. Kim, “Handwritten Korean Character Recognition Based on Hierarchical Random Graph Modeling”, in Proc. Int. Workshop Frontiers in Handwriting Recognition, pp. 577-586, Korea, 1998. [63] W. Lu, Y. Ren, C. Y. Suen, “Hierarchical Attributed Graph Representation and Recognition of Handwritten Chinese Characters”, Pattern Recognition, vol. 24, no.7, pp. 617-632, 1991. [64] H. D. Block, B. W. Knight, F. Rosenblatt, “Analysis of A Four Layer Serious Coupled Perceptron”, II. Rev. Modern Physics, vol.34, pp.135-152, 1962. 97 [65] I. S. Oh, J. S. Lee, S. M. Choi, K. C. Hong, “Class-expert Approach to Unconstrained Handwritten Numeral Recognition”, in Proc.5th Int. Workshop Frontiers in Handwriting Recognition, pp. 95-102, Essex, England, 1996. [66] L. F. C. Pessoa, P. Maragos, “Neural Networks with Hybrid Morphological/Rank/Linear Nodes: A Unifying Framework with Applications to Handwritten Character Recognition”, Pattern Recognition, vol.33, pp. 945- 960, 2000. [67] T. Kohonen, “Self Organizing Maps”, Springer Series in Information Sciences, vol.30, Berlin, 1995. [68] S. Smith, M. Borgoin, K. Sims, H. Voorhees, “Handwritten Character Classification Using Nearest Neighbor in Large Databases”, IEEE Trans. Pattern Recognition and Machine Intelligence, vol.16, no.9, pp. 915-919, 1994. [69] S. O. Belkasim, M. Shridhar, M. Ahmadi, “Pattern Recognition with Moment Invariants: A comparative Survey”, Pattern Recognition, vol.24, no.12, pp. 1117-1138, 1991. [70] Rabiner L.R - "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition" - Proceedings of IEEE, VOL.77, NO.2, FEB 1989, pp. 257-286. [71] M. Y. Chen, A. Kundu, J. Zhou, “Off-line Handwritten Word Recognition Using a Hidden Markov Model Type Stochastic Network”, IEEE Trans. Pattern Recognition and Machine Intelligence, vol.16, pp.481-496, 1994. [72] M. Y. Chen, A. Kundu, S. N. Srihari, “Variable Duration Hidden Markov Model and Morphological Segmentation for Handwritten Word Recognition”, IEEE Trans. Image Processing, vol.4, pp.1675-1688, 1995. [73] A. Kornai, K. M. Mohiuddin, S. D. Connell, “An HMM-Based Legal Amount Field OCR System For Checks”, IEEE Trans, Systems, Man and Cybernetics, pp. 2800-2805, 1995. 98 [74] M. A. Mohamed, P. Gader, “Generalized Hidden Markov Models – Part II: Application to Handwritten Word Recognition”, IEEE Trans. Fuzzy Systems, vol.8, no.1, pp.82-95, 2000. [75] M. A. Mohamed, P. Gader, “Handwritten Word Recognition Using Segmentation-Free Hidden Markov Modeling and Segmentation Based Dynamic Programming Techniques”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol.18, no.5, pp.548-554, 1996. [76] M. Nakagava, T. Oguni, A. Homma, “A coarse classification of on-line handwritten characters” in Proc. 5th Int. Workshop Frontiers in Handwriting Recognition, pp. 417-420, Essex, England, 1996. [77] S. Gopisetty, R. Lorie, J. Mao, M. Mohiuddin, A. Sorin, E. Yair, “Automated forms-processing Software and Services”, IBM Journal of Research and Development, vol. 40, no. 2, pp.211-230, 1996. [78] J. Park, V. Govindaraju, S. N. Srihari, “OCR in A Hierarchical Feature Space”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol.22, no.4, pp.400- 407, 2000. [79] H. Drucker, R. Schapire, P. Simard, “Improving Performance in Neural Networks Using a Boosting Algorithm” in Advances in NIPS, S. J. Hanson, J. Cowan, L. Giles, Eds. Morgan Kaufmann, 1993, pp.42-49. [80] L. Lam C. Y. Suen, “Increasing Experts for Majority Vote in OCR: Theoretical Considerations and Strategies”, in Proc. Int. Workshop Frontiers in Handwriting Recognition, pp. 245-254, Taiwan, 1994. [81] H. J. Kang, S. W. Lee, “Combining Classifiers based on Minimization of a Bayes Error Rates”, in Proc. 5th Int. Conf. Document Analysis and Recognition, pp.398-401, Bangalore, India, 1999. [82] Y. Tang, L. T. Tu, J. Liu, S. W. Lee, W. W. Lin, I. S. Shyu, “Off-line Recognition of Chinese Handwriting by Multifeature and Multilevel 99 Classification”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol.20, no.5, pp.556-561, 1998. [83] R. M. Bozinovic, S. N. Srihari, “Off-line Cursive Script Word Recognition”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol.11, no.1, pp.68- 83, 1989. [84] C. J. C. Burges, “Simplified support vector decision rules”, Proc. 13th International Conference on Machine Learning, San Mateo, CA, 1996, pp. 71– 77. [85] Osuma E., Freund R., Girosi F., An Improved Training Algorithm for Support Vector Machines, Proc IEEE NNSP ’97, 1997, pp. 276-285. [86] B. Schoelkopf, S. Mika, C. J. C. Burges, P. Knirsch, K. Muller, G. Ratsch and A. J. Smola, “Input space versus feature space in kernel-based methods”, IEEE Trans. Neural Networks, vol. 10, no. 5, pp. 1000-1017, 1999. 100