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 Vietnamese Handwritten Character Recognition By Combining SVM and Haar Wavelet Features Phạm Anh Phương, Ngô Quốc Tạo, Lương Chi Mai Abstract: This paper proposes a recognition model for hơn do bộ ký tự tiếng Việt có nhiều chữ có hình dáng isolated Vietnamese handwritten character recognition. rất giống nhau, chỉ khác nhau chút ít về phần dấu. Do Based on connected regions of image we try to determine đó có rất ít kết quả nghiên cứu về nhận dạng chữ viết character image that belongs to a group of characters tay tiếng Việt và các kết quả nghiên cứu chủ yếu cũng which has either diacritical mark or not. In our model, chỉ tập trung vào chữ viết tay online [9]. Bài toán character part and its diacritical mark part could be sepa- chúng tôi đặt ra ở đây là xây dựng một mô hình nhận rately defined and they come independently for recogni- dạng chữ Việt viết tay hạn chế. Chúng tôi giới hạn tion. Hence, we apply SVM (Support Vector Machines) classification where Haar wavelet features from a mark phạm vi của bài toán theo một số qui định như: các part and a character part are extracted independently. chữ viết phải có một khoảng cách tương đối, giữa Finally, we join classified results together to have recogni- phần chữ và phần dấu phải tách rời nhau. Bộ ký tự tion outcome. Our test results over Vietnamese handwrit- tiếng Việt bao gồm tập ký tự không dấu {A, B, C, D, ing with 50,000 character samples collecting from 655 Đ, E, G, H, I, K, L, M, N, O, P, Q, R, S, T, U, V, X, individuals show that the accuracy of our recognition Y} và các ký tự có dấu {Ă, Â, À, Ả, Ã, Á, Ạ, Ằ, Ẳ, model is over 88%. Ẵ, Ắ, Ặ, Ầ, Ẩ, Ẫ, Ấ, Ậ, Ê, È, Ẻ, Ẽ, É, Ẹ, Ề, Ể, Ễ, Ế, Ệ, Keywords: Vietnamese handwritten character recogni- Ì, Ỉ, Ĩ, Í, Ị, Ô, Ơ, Ò, Ỏ, Õ, Ó, Ọ, Ồ, Ổ, Ỗ, Ố, Ộ, Ờ, Ở, tion, SVM. Ỡ, Ớ, Ợ, Ư, Ù, Ủ, Ũ, Ú, Ụ, Ừ, Ử, Ữ, Ứ, Ự, Ỳ, Ỷ, Ỹ, I. GIỚI THIỆU Ý, Ỵ}. Nhận dạng chữ viết tay đang là vấn đề thách thức SVM (Support Vector Machines) là một phương lớn đối với các nhà nghiên cứu, bài toàn này chưa thể pháp máy học tiên tiến đã có nhiều thành công không giải quyết trọn vẹn được vì nó phụ thuộc quá nhiều chỉ trong các lĩnh vực khai phá dữ liệu mà còn trong vào người viết và sự biến đổi quá đa dạng trong cách lĩnh vực nhận dạng. Trong những thập niên gần đây, viết và trạng thái tinh thần của từng người viết. Cho SVM được đánh giá là một trong những phương pháp đến nay, bài toán nhận dạng chữ viết tay cũng đã có phân lớp có độ chính xác rất cao và nó cũng đã được một số kết quả khả quan, yếu tập trung trên các tập dữ áp dụng nhiều trong các bài toán nhận dạng chữ viết liệu chữ số viết tay như USPS và MNIST [4,5,6], một tay [3,4,5,6]. Vì vậy chúng tôi đề xuất một mô hình số kết quả khác mở rộng đối với các chữ cái hệ La nhận dạng chữ Việt viết tay hạn chế trên cơ sở tinh, Hy lạp... [2,7]. Đặc biệt đối với việc nhận dạng phương pháp phân lớp SVM. Trích chọn đặc trưng chữ viết tay tiếng Việt lại càng gặp nhiều khó khăn phục vụ cho công việc huấn luyện và nhận dạng là 1 một bước rất quan trọng trong một hệ thống nhận dạng. Có rất nhiều phương pháp trích chọn đặc trưng hiệu quả có thể áp dụng cho chữ viết tay như: ma trận trọng số, toán tử Kirsch, các biểu đồ chiếu...[4,5,7], trong bài báo này chúng tôi sử dụng ý tưởng của phương pháp trích chọn đặc trưng wavelet Haar [8] cho mô hình nhận dạng chữ viết tay tiếng Việt. Dựa trên cơ sở các thành phần liên thông của ảnh, chúng tôi phân tập ký tự tiếng Việt thành 3 nhóm và Hình 1. Siêu phẳng tách với khoảng cách lề cực đại. tách các ký tự có dấu thành các phần rời nhau. Sau đó 2 2 chúng tôi xây dựng các máy phân lớp SVM để nhận Khoảng cách lề giữa hai lớp là = . Để nới w.w 2 dạng cho từng phần chữ và dấu. Các kết quả thực w nghiệm cho thấy mô hình nhận dạng của chúng tôi có lỏng điều kiện phân lớp, thêm vào một số yếu tố cân độ chính xác tương đối cao. bằng và việc huấn luyện SVM chính là giải bài toán Phần còn lại của bài báo này có cấu trúc như sau: tối ưu có ràng buộc: Phần 2 tóm tắt những ý tưởng cơ bản của phương 1 N pháp phân lớp SVM nhị phân. Phần 3 phát họa kiến min w,b 2 w.w + C ∑ξ i=1 i (2) trúc của mô hình nhận dạng, thuật toán trích chọn đặc sao cho: trưng Haar wavelet và xây dựng các máy phân lớp SVM phục vụ cho việc nhận dạng. Phần 4 là các kết yi(w. Φ(xi) + b) ≥ 1-ξi quả thực nghiệm trên tập dữ liệu viết tay tiếng Việt ξi ≥ 0, ∀i, trong đó C là tham số nới lỏng mà chúng tôi thu thập được. Cuối cùng là phần kết điều kiện phân lớp [1]. luận. Thay vì giải bài toán (2), ta giải bài toán đối ngẫu II. PHƯƠNG PHÁP PHÂN LỚP SVM của nó bằng cách giải bài toán qui hoạch toàn phương Hàm mục tiêu của một máy phân lớp SVM nhị phân (QP-Quadratic programming): có thể được phát biểu như sau: ⎛ 1 ⎞ max ⎜ α1 − α T Hα ⎟ (3) g(x) = w.Φ(x) + b (1) α ⎝ 2 ⎠ trong đó, véc tơ đầu vào x∈ R D , w là véc tơ chuẩn N của siêu phẳng phân cách trong không gian đặc trưng thỏa mãn: 0≤αi≤C, ∀i và ∑α y = 0, i =1 i i được sinh ra từ ánh xạ Φ(x): R D → R F (F > D, Φ(x) trong đó α =[α1,..., αN]T và H là ma trận kích thước có thể tuyến tính hoặc phi tuyến) và b là độ lệch so N×N được gọi là ma trận nhân (kernel matrix) với mỗi với gốc tọa độ. Ban đầu, SVM được thiết kế cho bài phần tử H(i,j) = yiyjΦ(xi).Φ(xj). toán phân lớp nhị phân, do đó dấu của g(x) cho biết Giải bài toán QP (3) ta thu được: véc tơ x thuộc lớp +1 hay lớp -1. N Cho tập mẫu {(x1,y1),...,(xN,yN)} trong đó xi∈RD và w= ∑ αi yi Φ(x i ) (4) yi∈{±1}, mục tiêu của phương pháp phân lớp SVM là i =1 tìm một siêu phẳng phân cách sao cho khoảng cách lề Mỗi mẫu huấn luyện xi tương ứng với một hệ số (margin) giữa hai lớp đạt cực đại (Hình 1). Lagrange αi. Sau khi huấn luyện, các mẫu có αi>0 được gọi là véc tơ hỗ trợ. 2 Thế (4) vào (1), ta có : Để thuận tiện cho việc xử lý sau này, chúng tôi N biến đổi ảnh đầu vào từ ảnh đa cấp xám thành ảnh nhị g(x) = ∑ αi yi Φ (x i ).Φ (x) + b i =1 (5) phân. Giả sử Φ(xi).Φ(xj) = K(xi,xj). Nghĩa là, tích vô hướng trong không gian đặc trưng tương đương với một hàm nhân K của không gian đầu vào. Vì vậy, ta không cần phải tính trực tiếp các giá trị Φ(xi), Φ(xj) mà chỉ cần tính tích vô hướng <Φ(xi).Φ(xj)> gián tiếp thông qua hàm nhân K(xi,xj). Nếu sử dụng hàm nhân là hàm tuyến tính thì SVM được gọi là SVM tuyến tính, ngược lại thì gọi là SVM phi tuyến. Như vậy, hàm mục tiêu cho bài toán phân lớp SVM nhị phân có dạng: N g(x) = ∑ α i yi K(x i , x) + b (6) i =1 Chỉ có các véc tơ hỗ trợ tham gia vào việc xây dựng siêu phẳng phân cách, do đó một mẫu x sẽ được phân lớp theo hàm quyết định: ⎛ NSV ⎞ f (x) = sgn ⎜ ∑ αi yi K(x i , x) + b ⎟ (7) Hình 2. Kiến trúc của mô hình nhận dạng ⎝ i =1 ⎠ trong đó, NSV là số véc tơ hỗ trợ. III. MÔ HÌNH NHẬN DẠNG CHỮ VIỆT VIẾT TAY HẠN CHẾ Trong phần này, chúng tôi 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 hạn chế (Hình 2). 1. Tiền xử lý (a) Nhiễu đốm (b) Nhiễu vệt dài Hình 3. Một số nhiễu thường gặp khi quét ảnh 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. Khi quét ảnh Chuẩn hóa ảnh theo vùng liên thông thường gặp các loại nhiễu, vì vậy chúng tôi sử dụng Chuẩn hóa ảnh nhằm mục đích tạo điều kiện thuận một số kỹ thuật lọc nhiễu để khử các nhiễu đốm và tiện cho công đoạn tách ảnh thành từng phần chữ và nhiễu vệt dài. Đối với nhiễu đốm, sử dụng các bộ lọc dấu. trung bình và lọc trung vị, còn với các nhiễu vệt dài Bước 1: Xác định các vùng liên thông trên ảnh (Hình thì chúng tôi sử dụng phương pháp khử các vùng liên 4). thông nhỏ (Hình 3). 3 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 5c). 2. Phân nhóm sơ bộ Dựa vào số thành phần liên thông chúng tôi tách (a) (b) bộ ký tự tiếng Việt thành 3 nhóm: Hình 4. Chuẩn hóa ảnh. (a) Ảnh gốc (b) Xác định các vùngƒ Nhóm 1: Nhóm có 1 vùng liên thông {A, B, C, D, Đ, liên thông và đánh thứ tự các vùng liên thông. E, G, H, I, K, L, M, N, O, P, Q, R, S, T, U, V, X, Y, 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 4b). ƒ Nhóm 2: Nhóm có 2 vùng liên thông {Ă, Â, À, Ả, Ã, Bước 3: Á, Ạ, Ê, È, Ẻ, Ẽ, É, Ẹ, Ì, Ỉ, Ĩ, Í, Ị, Ô, Ò, Ỏ, Õ, Ó, Ọ, Ờ, Ở, Ỡ, Ớ, Ợ, Ù, Ủ, Ũ, Ú, Ụ, Ừ, Ử, Ữ, Ứ, Ự, Ỳ, Ỷ, Ỹ, - 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 5a). ƒ Nhóm 3: Nhóm có 3 vùng liên thông { Ằ, Ẳ, Ẵ, Ắ, Ặ, Ầ, Ẩ, Ẫ, Ấ, Ậ, Ề, Ể, Ễ, Ế, Ệ, Ồ, Ổ, Ỗ, Ố, Ộ} 3. Trích chọn đặc trưng Chúng tôi sử dụng ý tưởng của phương pháp trích chọn đặc trưng wavelet Haar [8] để chọn tập đặc trưng cho mỗi ảnh ký tự đầu vào. (a) (b) (c) Hình 5. Chuẩn hóa các vùng liên thông. - 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. Hình 6. Quá trình trích chọn đặc trưng Ngược lại: Tách ảnh thành 2 phần: phần chữ và Từ ảnh nhị phân kích thước 2n×2n (Hình 6), quá phần dấu. Chuẩn hóa phần chữ về kích thước chuẩn trình trích chọn đặc trưng được mô tả theo thuật toán 16×16 và phần dấu về kích thước chuẩn 8×8 (Hình sau: 5b). - Nếu ảnh có 3 vùng liên thông: Procedure HaarFeature Nếu S(3) = Min{S(i)} thì dấu của phần liên thông Input Ma trận vuông (A,n) cấp 2n. 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 Output Tập các đặc trưng {F1, F2,..., F2n ×2n }. phần liên thông 2 về kích thước chuẩn 16×16. Method Ngược lại: Tách ảnh thành 3 phần từ các vùng liên 1. Khởi tạo: Queue = ∅; thông. Chuẩn hóa các vùng liên thông 1 và 2 về kích i = 1; 4 2. - Tính Fi= Tổng các điểm đen trong toàn bộ ma do đó hệ phương trình có nghiệm duy nhất. Vì vậy, trận (A,n); theo cách trích chọn đặc trưng của thuật toán Haar- - PUSH((A,n), Queue); Feature thì ma trận A bất biến với n=1. 3. While Queue ≠∅ Do Giả sử mệnh đề đúng với n=k. Ta sẽ chứng minh { mệnh đề đúng với n=k+1. - POP(Queue, (A,n)); 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 - if (n>1) mỗi một phần tư của ma trận vuông A cấp 2k+1 bất { biến thì ma trận vuông A cũng bất biến theo phương n = n DIV 2; pháp trích chọn đặc trưng của thuật toán HaarFeature. Chia ảnh thành 4 phần: A1, A2, A3, A4; Thật vậy, giả sử ma trận vuông A cấp 2k+1 được chia for (j=1; i ≤ 4; j++) thành 4 khối con A1, A2, A3, A4 kích thước 2k có tổng PUSH((Aj,n), Queue); 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 - Gọi S, S1, S2, S3, S4 là tổng các điểm đen duy nhất X1=S1, X2=S2, X3=S3, X4=S4 tương ứng với tương ứng với các khối A, A1, A2, A3, A4; 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 - Tính Fi+1 = S1 + S2; thuật toán HaarFeature nên ma trận A cũng bất biến Fi+2 = S2 + S3; theo phương pháp trích chọn đặc trưng trên . Fi+3 = S4; Trong thực nghiệm, với phần chữ chúng tôi chọn - i = i + 3; 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, Phương pháp tính nhanh tổng các điểm đen trong như vậy có tất cả 64 đặc trưng. trong thuật toán trên có thể tham khảo trong [8]. Với phương pháp trích chọn đặc trưng này thì sẽ tạo Mệnh đề (tính bất biến của đặc trưng): Cho ma trận ra một dãy số các đặc trưng giảm dần. Với cùng một vuông A cấp 2n, n nguyên dương. Theo phương pháp chữ thì các giá trị lớn ở đầu dãy tương đối ổn định, có trích chọn đặc trưng của thuật toán HaarFeature thì thể đại diện cho hình dạng khái quát của chữ; còn các ma trận A bất biến đối với các đặc trưng được trích giá trị ở cuối dãy nhỏ dần và không ổn định, thể hiện chọn. sự đa dạng trong từng chi tiết của chữ. Chứng minh 4. Xây dựng các máy phân lớp SVM Dùng phương pháp quy nạp. Trong phần này, chúng tôi sẽ xây dựng 3 máy phân Ta chứng minh mệnh đề đúng với n=1. Thật vậy, lớp SVM, sử dụng tập đặc trưng được trích chọn ở giả sử x1, x2, x3, x4 là 4 phần tử của ma trận vuông cấp trên để huấn luyện phân lớp và nhận dạng. 2. Theo phương pháp trích chọn đặc trưng trên ta có hệ phương trình: Đối với phần chữ có kích thước 16×16, có tất cả 256 đặc trưng. Còn phần dấu với kích thước 8×8, như ⎧ x1 + x2 + x3 + x4 = S 1 1 1 1 ⎪ x +x vậy có 64 đặc trưng được trích chọn. ⎪ 1 2 = S1 + S 2 1 1 0 0 ⎨ và = 1 ≠ 0 ƒ SVM1: phân lớp đối với nhóm ký tự có 1 vùng liên ⎪ x2 + x3 = S 2 + S3 0 1 1 0 thông {A, B, C, D, Đ, E, G, H, I, K, L, M, N, O, P, Q, ⎪⎩ x4 = S 4 0 0 0 1 R, S, T, U, V, X, Y, Ơ, Ư}. 5