Đại Học Quốc Gia Tp Hồ Chí Minh TRƯỜNG ĐẠI HỌC BÁCH KHOA - NGÔ QUANG TÂN NHẬN DẠNG CHỮ VIẾT TIẾNG VIỆT DÙNG MÔ HÌNH MỜ HAI CHIỀU Chuyên Ngành: KỸ THUẬT VÔ TUYẾN - ĐIỆN TỬ Mã Số Ngành: 2.07.01 LUẬN VĂN THẠC SĨ TP HỒ CHÍ MINH, tháng năm 2006 CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH Cán hướng dẫn khoa học: PGS-TS Lê Tiến Thường TS Hồng Đình Chiến Ký tên Ký tên Cán chấm nhận xét 1: TS Nguyễn Đức Thành Ký tên Cán chấm nhận xét 2: TS Nguyễn Như Anh Ký tên Luận văn thạc sĩ bảo vệ HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày 14 háng năm 2006 TRƯỜNG ĐẠI HỌC BÁCH KHOA PHÒNG ĐÀO TẠO SĐH CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM ĐỘC LẬP – TỰ DO – HẠNH PHÚC Tp HCM, ngày 14 tháng năm 2006 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: NGÔ QUANG TÂN Phái: Nam Ngày, tháng, năm sinh: 22.09.1979 Nơi sinh: TP HCM Chuyên ngành: Kỹ thuật vô tuyến – điện tử MSHV: 01404347 I- TÊN ĐỀ TÀI: NHẬN DẠNG CHỮ VIẾT TIẾNG VIỆT DÙNG MƠ HÌNH MỜ HAI CHIỀU II-NHIỆM VỤ VÀ NỘI DUNG: - Tìm hiểu tổng quan hệ thống nhận dạng chữ viết tay Tìm hiểu phương pháp trích đặc trưng chữ viết tay phương pháp phân loại cho hệ thống nhận dạng Chọn phương pháp trích đặc trưng chữ viết tay, dùng giải thuật mờ K lân cận gần mạng Neural để phân loại ký tự viết tay đầu vào Đề nghị cơng việc để hồn thiện hệ thống nhận dạng chữ viết tay III- NGÀY GIAO NHIỆM VỤ IV- NGÀY HOÀN THÀNH NHIỆM VỤ V- CÁN BỘ HƯỚNG DẪN CÁN BỘ HƯỚNG DẪN : 06.02.2006 : 30.06.2006 : PGS-TS LÊ TIẾN THƯỜNG TS HỒNG ĐÌNH CHIẾN CHỦ NHIỆM NGÀNH CN BỘ MÔN QL CHUYÊN NGÀNH Nội dung đề cương luận văn thạc sĩ Hội đồng chun ngành thơng qua Ngày TRƯỞNG PHỊNG ĐT – SĐH tháng năm TRƯỞNG KHOA QL NGÀNH LỜI CÁM ƠN Tôi chân thành gởi lời biết ơn sâu sắc Thầy Giáo Hướng dẫn PGS-TS Lê Tiến Thường TS Hồng Đình Chiến công tác Khoa Điện – Điện tử, trường ĐH Bách khoa, ĐH Quốc Gia Tp Hồ Chí Minh tận tình hướng dẫn, định hướng, tạo nhiều điều kiện thuận lợi, giúp đỡ tơi hồn thành luận văn thạc sĩ thông qua buổi báo cáo định kỳ Chân thành cám ơn Quý Thầy Cô tận tình giảng dạy, trang bị kiến thức cần thiết suốt thời gian năm học tập nghiên cứu trường Chân thành cám ơn Phòng Đào Tạo Sau Đại Học, trường Đại học Bách Khoa Tp Hồ Chí Minh tạo điều kiện tốt cho tơi suốt khóa học Chân thành cám ơn đồng nghiệp tổ Kỹ thuật truyền dẫn – Trung tâm chuyển mạch truyền dẫn Ứng cứu thông tin – Công ty Điện thoại Tây – Bưu điện TP HCM tạo điều kiện thuận lợi cho tơi suốt q trình học tập Và cuối cùng, cám ơn bạn học viên cao học ngành Kỹ thuật Vơ tuyến – Điện tử khóa 15, gia đình bạn bè ủng hộ, giúp đỡ tơi học tập thực luận văn tốt nghiệp Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến ABSTRACT The research work described in this dissertation is aimed at developing improved handwritten character classifiers for use in off-line handwritten word recognition The bar-features are calculated on binary images of isolated characters that need not be size normalized Initially, eight features images are generated Each features image corresponds to one of the directions: east, northeast, north, and northwest, in either the foreground or the background Each feature image has an integer value at each location that represents the length of the longest bar that fits at that point in that direction A fuzzy K-nearst neighbor algorithm is used for classification the ambiguous handwritten characters Besides, a multi-layer feedforward neural network is also designed for recognition These new mothodologies have resulted in significant improvements in handwritten word recognition performance Recognition rates of over 90% were achieved using a single word recognition and an average lexicon size of 100 TĨM TẮT Thời gian gần có nhiều phương pháp nhận dạng chữ viết tay gồm có: sử dụng suy luận Bayes, mạng Neural, logic mờ, biến đổi Wavelet…Trong luận văn này, công việc nghiên cứu hướng đến việc phát triển cải tiến phân loại nhận dạng chữ viết tay off-line Các đặc điểm tính ảnh nhị phân ký tự viết tay mà không cần chuẩn hóa kích thước ảnh Ban đầu, tám ảnh đặc điểm tạo ra, ảnh đặc điểm tương đương với hướng: đông, bắc, đông-bắc tây-bắc cho ảnh foreground background Mỗi ảnh đặc điểm có giá trị nguyên vị trí biểu diễn cho chiều dài đoạn dài tương ứng với điểm hướng Giải thuật mờ K-lân cận gần dùng để phân loại chữ viết tay không rõ ràng Ngoài ra, mạng neuron truyền thẳng nhiều lớp thiết kế cho nhận dạng chữ viết tay Các phương pháp cho kết với cải tiến nhiều hiệu nhận dạng chữ viết tay Tỷ lệ nhận dạng đạt 90% việc nhận dạng từ với nguồn từ vựng huấn luyện khoảng 100 từ Trang HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến MỤC LỤC DANH SÁCH CÁC HÌNH Chương : GIỚI THIỆU 1.1 Đặt vấn đề 1.2 Tổng quan tình hình nghiên cứu 1.3 Mục tiêu đề tài 11 1.4 Nội dung nghiên cứu 11 1.5 Bố cục luận văn 12 Chương : CÁC VẤN ĐỀ TRONG NHẬN DẠNG CHỮ VIẾT .13 2.1 Sự phát sinh chữ viết tay 13 2.2 Các khó khăn nhận dạng ký tự viết tay 13 2.3 Các loại nhận dạng ký tự viết tay .15 Chương : GIẢI THUẬT MỜ K-LÂN CẬN GẦN NHẤT 17 3.1 Giới thiệu 17 3.2 Các tập hợp mờ 18 3.3 Các giải thuật K lân cận gần 19 3.3.1 Giải thuật rõ K-NN 19 3.3.2 Phân nhóm mờ K-NN 20 Chương : MẠNG NEURON NHÂN TẠO .23 4.1 Giới thiệu mạng Neural nhân tạo 23 4.2 Mơ hình neuron nhân tạo .25 4.3 Phân loại mạng nơron 26 4.3.1 Theo kiểu liên kết nơron .26 4.3.2 Theo số lớp 27 4.4 Các cách tiếp cận mạng nơron .28 4.5 Khả tính tốn biểu diễn phụ thuộc liệu mạng nơron 29 4.6 Xác định cấu trúc mạng tối ưu .30 Trang HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mô hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến 4.7 Tổng qt hóa mạng neuron .31 4.7.1 Nhiễu .31 4.7.2 Vấn đề khớp 31 4.7.3 Kích thước mẫu .31 4.8 Ánh xạ mạng neuron 32 4.9 Mạng Perceptron 33 4.9.1 Kiến trúc mạng 33 4.9.2 Huấn luyện mạng 35 4.9.3 Khả ứng dụng cho nhận dạng ảnh 37 4.10 Mạng Perceptron đa lớp .38 4.10.1 Kiến trúc mạng 38 4.10.2 Huấn luyện mạng 40 4.10.3 Khả ứng dụng cho nhận dạng ảnh 46 4.11 Mạng kết hợp tuyến tính 47 4.11.1 Kiến trúc mạng 47 4.11.2 Huấn luyện mạng 48 4.11.3 Khả ứng dụng cho nhận dạng ảnh 49 4.12 Mạng Kohonen 49 4.12.1 Kiến trúc mạng 49 4.12.2 Huấn luyện mạng 51 4.12.3 Khả ứng dụng cho nhận dạng ảnh 52 Chương : NHẬN DẠNG ẢNH 54 5.1 Nguyên lý nhận dạng ảnh 54 5.1.1 Giới thiệu chung 54 5.1.2 Các khái niệm 54 5.2 Tiến trình nhận dạng ảnh .56 5.2.1 Thu thập liệu (Data Collection) .57 5.2.2 Tiền xử lý (Preprocessing) 57 5.2.3 Phân đoạn (Segmentation) 57 Trang HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến 5.2.4 Tiêu chuẩn hóa (Normalization) 57 5.2.5 Trích chọn đặc trưng (Feature Extraction) .58 5.2.6 Phân lớp (Classification) .58 5.2.7 Hậu xử lý (Postprocessing) 58 5.3 Các phương pháp số nhận dạng ảnh 59 5.3.1 Trích chọn đặc trưng .59 5.3.2 Kỹ thuật phân lớp mẫu 63 5.4 Phương pháp nhận dạng cấu trúc 70 5.4.1 Biểu diễn đặc trưng mẫu phương pháp cấu trúc 70 5.4.2 Kỹ thuật phân lớp mẫu 72 Chương : DÙNG MATLAB NHẬN DẠNG CHỮ VIẾT TAY .76 6.1 Mô tả chương trình mơ 76 6.2 Quá trình thực .77 6.2.1 Lọc nhiễu: 77 6.2.2 Chuẩn lại kích thước ảnh ngõ vào .78 6.2.3 Trích đặc điểm định hướng ký tự viết tay 78 6.2.4 Phân loại mẫu cần nhận dạng 82 6.2.5 Phân loại dùng giải thuật mờ K lân cận gần nhất: 82 6.2.6 Phân loại dùng mạng neural 86 6.3 Kết thực 90 Chương : KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ĐỀ TÀI 91 7.1 Kết luận 91 7.2 Hướng phát triển đề tài .91 TÀI LIỆU THAM KHẢO 92 LÝ LỊCH TRÍCH NGANG 94 Trang HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hoàng Đình Chiến DANH SÁCH CÁC HÌNH Hình 2.1: Các q trình lý-sinh tâm-vật lý việc tạo chữ viết tay .13 Hình 2.2: Ba loại từ viết tay: chữ viết thường, chữ in hoa chữ kết hợp 14 Hình 2.3: Quá trình nhận dạng từ viết tay 16 Hình 4.1: Dạng neuron McCulloch Pitts 23 Hình 4.2: Mơ hình nơron nhân tạo .25 Hình 4.3: Khả tính toán mạch sở nơron 26 Hình 4.4: Mạng nơron truyền thẳng nhiều lớp 27 Hình 4.5: Mạng nơron hồi qui 27 Hình 4.6: Học tham số có giám sát .29 Hình 4.7: Mơ hình mạng Perceptron lớp 34 Hình 4.8: Biên định khơng gian mẫu 35 Hình 4.9: Khơng gian mẫu khả tách tuyến tính 37 Hình 4.10: Khơng gian mẫu khơng khả tách tuyến tính 37 Hình 4.11: Phân lớp khơng gian mẫu với mạng Perceptron nơron lớp 38 Hình 4.12: Mạng Perceptron đa lớp (MLP) 39 Hình 4.13: Mạng MLP giải toán XOR 40 Hình 4.14: Phân lớp mẫu với mạng MLP lớp 47 Hình 4.15: Kiến trúc mạng tuyến tính 48 Hình 4.16 Quan hệ lân cận lớp Kohonen .50 Hình 4.17: Kiến trúc mạng Kohonen .51 Hình 4.18: Mã hóa vector đầu vào với mạng SOFM 52 Hình 5.1: Tiến trình xử lý ảnh 56 Hình 5.2: Phương pháp lưới 61 Hình 5.3: Phương pháp cung 61 Hình 5.4: Phương pháp tìm kiếm khối khơng gian mẫu 64 Hình 5.5 : Phương pháp phân lớp khoảng cách tối thiểu 65 Hình 5.6 Phương pháp cấu trúc biểu diễn mẫu .71 Trang HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến Hình 5.7: Phân lớp phân tích cú pháp 74 Hình 5.8: Phân lớp nguyên mẫu tượng trưng 75 Hình 6.1: Sơ đồ khối hệ thống nhận dạng từ dựa phân đoạn 76 Hình 6.2: Quá trình nhận dạng chữ viết chương trình mơ .77 Hình 6.3: Ký tự có nhiễu muối tiêu (a), ký tự sau lọc nhiễu (b) 77 Hình 6.4: Quá trình tạo vector đặc trưng chữ ngõ vào 78 Hình 6.5: Cách phân chia 15 vùng chồng lấp ảnh ngõ vào .79 Hình 6.6: Ảnh vector đặc điểm e(i,j) ký tự A 80 Hình 6.7: Một số ký tự viết tay mẫu 81 Hình 6.8: Vector đặc trưng ký tự viết tay A 81 Hình 6.9: Vector đặc trưng ký tự viết tay K 82 Hình 6.10: Lưu đồ giải thuật phân nhóm mờ K-lân cận gần 84 Hình 6.11: Các ký tự in hoa viết tay xác định giải thuật mờ K lân cận gần Các ký tự “A”, “M”, “W” “I” 85 Hình 6.12: Sai số huấn luyện với chữ viết hoa (UPPERCASE) 89 Hình 6.13: Sai số huấn luyện với chữ viết thường (lowercase) .89 Trang HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến chuẩn hóa lại từ đến cách chia cho tổng lớn vùng Vector đặc điểm có kích thước 15 x = 120 Chính xác là, gọi f1, f2, …, f8 ảnh đặc điểm kết hợp với mẫu ngõ vào zi biểu diễn vùng hình chữ nhật có kích thước h/3 x w/2 có tọa độ góc trái phía (r0, c0) Giá trị đặc điểm thứ k tương ứng với vùng zi là: z ik = N h w r0 + c0 + ∑∑f r = r0 c = c0 k (6.1) (r , c) N = w fk = e, ne, nw N = h fk = n Vector đặc trưng gồm có 120 giá trị (zik : i = 1, 2, …, 15 k = 1, 2, …, 8) đặc điểm dùng vector đặc điểm cho phần nhận dạng ký tự Hình 6.6: Ảnh vector đặc điểm e(i,j) ký tự A Trang 80 HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mô hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến Một số ký tự viết tay làm liệu mẫu tập Training: Hình 6.7: Một số ký tự viết tay mẫu 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 20 40 60 80 100 120 Hình 6.8: Vector đặc trưng ký tự viết tay A Trang 81 HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hoàng Đình Chiến 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 20 40 60 80 100 120 Hình 6.9: Vector đặc trưng ký tự viết tay K 6.2.4 Phân loại mẫu cần nhận dạng Các ảnh ký tự viết tay ngõ vào tập hợp ảnh với số lượng lớn nhiều cách viết nhiều người viết khác nhau, gồm có chữ viết hoa chữ thường Với ảnh ký tự ta tạo vector đặc điểm gồm 120 giá trị tương ứng cho ký tự Từ tập hợp mẫu ta dùng phương pháp phân loại để xuất 26 ký tự ngõ Trong luận văn này, dùng hai phương pháp phân loại là: phân loại dùng giải thuật mờ K lân cận gần (The fuzzy K-nearest neighbor algorithm) phân loại dùng mạng Neural (Neural Networks) 6.2.5 Phân loại dùng giải thuật mờ K lân cận gần nhất: Cho W = {x1,x2,…,xn} tập hợp gồm n mẫu gán nhãn Cho ui(x) giá trị phụ thuộc gán vào vector x (được tính tốn), uij phụ thuộc phân nhóm i vector thứ j tập hợp mẫu gán nhãn cho K lân cận gần Trang 82 HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến Giải thuật sau: BEGIN Ngõ vào x, phân loại chưa biết Chọn K, ≤ K ≤ n Khởi tạo i = DO UNTIL (K lân cận gần để tìm thấy x) Tính khoảng cách từ x tới xi IF (i ≤ K) THEN Cho x i vào tập hợp K lân cận gần ELSE (xi gần x lân cận gần trước) THEN Xóa giá trị xa K lân cận gần Cho xi vào tập hợp K lân cận gần END IF END DO UNTIL Khởi tạo i = DO UNTIL (x gán phụ thuộc vào tất phân nhóm) Tính ui(x) sử dụng biểu thức (6.2) Tăng i END DO UNTIL END Lưu đồ giải thuật phân nhóm mờ K-lân cận gần (hình 6.10): Với mẫu ngõ vào x Trong đó: ⎛ ⎞ ⎜ ⎟ u ij ⎜ ∑ ⎟ j =1 ⎜ x − x j m −1 ⎟ ⎝ ⎠ u i ( x) = ⎞ K ⎛ ⎜ ⎟ ∑ ⎜ ⎟ j =1 ⎜ x − x m −1 ⎟ j ⎝ ⎠ K Trang 83 (6.2) HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến Start i=1 Chọn K, ≤ K ≤ n Tính dist(x,xi) Y i≤K xi ∈ {WK } N dist ( x, xi ) ≤ dist ( x, {WK } Y xi ∈{WK} Xóa Max{WK} N Tăng i Y i≤n N End Hình 6.10: Lưu đồ giải thuật phân nhóm mờ K-lân cận gần Trang 84 HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến Như ta thấy (6.2), phụ thuộc gán vào x bị ảnh hưởng nghịch đảo khoảng cách từ lân cận gần phụ thuộc phân nhóm chúng Nghịch đảo khoảng cách cho ta trọng số phụ thuộc vector nhiều gần cách xa vector xét Các mẫu gán nhãn gán phụ thuộc phân nhóm nhiều cách Trước hết, chúng cho phụ thuộc hồn tồn phân nhóm mà chúng chưa biết khơng có phụ thuộc tất phân nhóm Bước gán phụ thuộc mẫu dựa vào khoảng cách từ trung tâm phân nhóm dựa vào khoảng cách từ mẫu gán nhãn phân nhóm chúng phân nhóm khác, sau sử dụng phụ thuộc cuối phân loại Áp dụng giải thuật phân nhóm mờ K-lân cận gần này, tập hợp huấn luyện Training ma trận gồm 120 cột tương ứng với số giá trị vector đặc điểm 20 hàng tương ứng với số lượng người viết ký tự viết tay cho giải thuật huấn luyện Sau đó, để nhận dạng ký tự viết tay đưa vào hệ thống, ký tự viết tay ngõ vào tạo ma trận mẫu Sample gồm 120 cột hàng Sử dụng giải thuật mờ K lân cận gần với m = biểu thức (6.2) (khoảng cách Euclide) ta phân nhóm ma trận Sample ma trận Training huấn luyện xuất giá trị ký tự Hình 6.11: Các ký tự in hoa viết tay xác định giải thuật mờ K lân cận gần Các ký tự “A”, “M”, “W” “I” Trang 85 HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến 6.2.6 Phân loại dùng mạng neural Thiết kế mạng neuron: Bài tốn đặt sau có vector đặc trưng, ta cần phân loại ký tự xét ký tự số 26 ký tự bảng chữ Để xây dựng mạng neuron, ta cần xác định số neuron lớp vào, số neuron lớp ra, số lớp ẩn số neuron lớp ẩn • Ở có 26 lớp đầu tương ứng với 26 ký tự bảng chữ nên số neuron đầu 26 hàm kích hoạt purelin • Vector đặc trưng có 120 thành phần nên lớp neuron vào mạng có 120 neuron • Mạng neuron thiết kế mạng neuron truyền thẳng perceptron đa lớp MLP, giải thuật học lan truyền ngược có giám sát • Thừ nghiệm thực tế cho thấy số lớp ẩn lớn mạng cho kết không thay đổi mà cấu trúc mạng lại phức tạp Vì vậy, chọn xây dựng mạng MLP có lớp neuron ẩn Số neuron lớp ẩn 60, hàm kích hoạt lớp ẩn hàm tansig Huấn luyện mạng Phần liệu mẫu phân làm thành tập con: tập mẫu học, tập kiểm soát (để xác định dừng trình học) tập kiểm thử (để kiểm tra khả nhận dạng) Chương trình mơ thuật tốn huấn luyện mạng neuron phân loại ký tự thực mơi trường tính tốn kỹ thuật Matlab Giải thuật học lan truyền ngược trung bình bình phương sai số có giám sát Bước 1: khởi tạo trọng số cho lớp ẩn W2(t ) (i, j ) lớp xuất W3( n ) ( j, k ) cho lần lặp mẫu nhập nên t=1 n=1 Các trọng số nút ẩn khởi tạo cho cặp đôi đối xứng Chúng số ngẫu nhiên phải đủ nhỏ để đảm bảo tổng trọng hóa nút mẫu xấp xỉ Các trọng số nút xuất khởi tạo cho giá trị ngõ ký tự 0.4 ký tự lại -0.4 Trang 86 HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến Bước 2: Tính tổng ngõ nhập sau gia trọng cho lớp ẩn I net 2( t ) (n, j ) = ∑ X I (n, i )W2( t ) (i, j ) + bσj I số lớp nhập XI(n,i): ngõ neuron thứ i lớp vào ứng với mẫu thứ n bσj giá trị ngưỡng neuron thứ j lớp nhập Bước 3: Tính ngõ cho neuron lớp ẩn với hàm truyền đạt tansig X 2( t ) (n, j ) = tan sig (net 2( t ) (n, j )) Bước 4: Tính tổng ngõ nhập sau gia trọng cho lớp xuất J net 3( t ) (n, k ) = ∑ X (n, j )W3(t ) ( j , k ) + bσk Bước 5: Tính ngõ cho neuron lớp xuất ngõ cho toàn mạng với hàm ngưỡng purelin: X 3( t ) (n, k ) = purelin(net 3( t ) ) Bước 6: Tính sai số trọng cho lớp xuất: ΔW3(t ) ( j , k ) = −ηδ 3(t ) (k ) X 3( t ) (n, k ) + μΔW3(t −1) ( j , k ) δ 3(t ) (k ) = ηX 3(t ) (n, k )[1 − X 3(t ) (n, k )][d (n, k ) − X 3(t ) (n, k )] đó: ΔW3( t ) ( j , k ) sai số lần lặp t trọng số W3( t ) ( j , k ) lớp xuất X 3( t ) (n, k ) ngõ neuron thứ k lớp xuất ứng với mẫu n d (n, k ) ngõ yêu cầu neuron k ứng với mẫu thứ n η hệ số học μ hệ số momentum Bước 7: Tính sai số trọng cho lớp ẩn Trang 87 HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mô hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến ΔW2( t ) (i, j ) = −ηδ 2( t ) ( j ) X 2( t ) ( n, j ) + μΔW2( t −1) (i, j ) δ 2(t ) ( j ) = ηX 2(t ) (n, j )[1 − X 2(t ) (n, j )]⎢∑ W3(t ) ( j , k )δ 3(t ) (k )⎥ ⎡ δ (k ) = ηX (n, k )[1 − X (t ) (t ) (t ) K ⎤ ⎣1 ⎦ (t ) (n, k ) d (n, k ) − X (n, k ) ][ ] Bước 8: Tính lại trọng số cho lớp ẩn lớp xuất W3( t −1) ( j , k ) = W3( t ) ( j , k ) + ΔW3( t ) ( j , k ) W2( t −1) (i, j ) = W2( t ) (i, j ) + ΔW2( t ) (i, j ) Lặp lại từ bước đến mẫu thứ N Bước 9: Tính sai số ngõ mạng ngõ yêu cầu: msei = n n 2 ( ) e ( k ) = ∑ i ∑ [d i (k ) − X (k )] m k =t m k =t Nếu sai số đạt yêu cầu cho tất mẫu việc huấn luyện dừng lại, lưu lại trọng số Nếu sai số khhông đạt yêu cầu cho n=1 lặp lại từ bước Nhận dạng Bước 1: Lấy trọng số lớp ẩn W2 lớp xuất W3 từ tập liệu Bước 2: Tính net2(j) cho neuron j lớp ẩn Bước 3: Tính X2(j) cho neuron j lớp ẩn Bước 4: Tính net3(k) cho neuron k lớp xuất Bước 5: Tính X3(k) cho neuron k lớp xuất Bước 6: Tính trung bình bình phương sai số ngõ mạng với ngõ mong muốn: msei = n n ( ) [d i (k ) − X (k )]2 e ( k ) = ∑ ∑ i m k =t m k =t (6.3) Kết loại ký tự thứ i 26 loại ký tự msei đạt giá trị nhỏ Trang 88 HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến Performance is 9.12761e-005, Goal is 0.0001 10 Training-Blue Goal-Black 10 -1 10 -2 10 -3 10 -4 10 -5 10 10 15 15 Epochs Hình 6.12: Sai số huấn luyện với chữ viết hoa (UPPERCASE) Performance is 7.81596e-005, Goal is 0.0001 10 Training-Blue Goal-Black 10 -1 10 -2 10 -3 10 -4 10 -5 10 14 Epochs 10 12 14 Hình 6.13: Sai số huấn luyện với chữ viết thường (lowercase) Trang 89 HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến 6.3 Kết thực Dữ liệu mẫu huấn luyện gồm chữ viết 100 người, chữ viết in hoa chữ viết thường, cộng với số ảnh viết tay thu thập Internet http://www.cedar.buffalo.edu/Databases/CDROM1/words.html nhiều trang web khác Trong chữ viết 100 người gồm có 26 loại chữ viết in hoa, 26 chữ viết thường Trong trình huấn luyện chữ viết in hoa, ta có: 26 x 100 vector đặc điểm Mỗi vector đặc điểm có 120 thành phần giá trị khoảng [0 1] Tính tương tự cho chữ viết thường 100 người Sau huấn luyện cho tập liệu trên, ta lấy tiếp chữ viết 10 người khác làm tập thử cho hệ thống nhận dạng, tỷ lệ nhận dạng gần xác (trên 90%) Với tập huấn luyện tương tự trên, chương trình ứng dụng “Phân loại địa thư tự động” với tập huấn luyện tên 64 tỉnh thành nước, tập hợp mẫu với số lượng vừa phải, phù hợp với nhận dạng chữ viết tay dùng giải thuật mờ K-lân cận gần nhất, chương trình ứng dụng hữu ích việc phân loại vùng cho thư tay, phân loại thư nhanh xác (trên 90%) Trang 90 HVTH: KS Ngơ Quang Tân Nhận dạng chữ viết tiếng Việt dùng mô hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến Chương : KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ĐỀ TÀI 7.1 Kết luận Tác giả trình bày hai phương pháp phân loại ký tự viết tay: dùng giải thuật mờ Klân cận gần dùng mạng neuron • Nếu xét phân loại cấp độ từ dùng giải thuật phân loại mờ tỏ hiệu dùng mạng neuron, xác kể với chữ viết xấu, đồng thời hiệu cho ứng dụng nhận dạng với số lượng mẫu vừa phải, khơng mang tính tổng qt hóa • Nếu dùng mạng neuron tỏ hiệu cấp độ ký tự, tổng qt hóa cho nhận dạng địi hỏi có giải thuật phân đoạn từ thành ký tự, từ nhận dạng ký tự tái tạo lại thành từ Trong luận văn trình bày ứng dụng nhận dạng cấp độ từ, thể tính hiệu với số lượng mẫu huấn luyện không lớn “Phân loại địa thư tự động”, giảm bớt nhân lực, thời gian ngành bưu việc phân loại thư với mã Tỉnh cách nhanh chóng Do thời gian điều kiện thực đề tài có hạn nên kết đề tài cịn hạn chế, chưa đánh giá xác tỷ lệ nhận dạng ký tự viết tay, số lượng mẫu thu thập dừng số lượng nhỏ nên cần thêm thời gian để hồn thiện chương trình 7.2 Hướng phát triển đề tài • Sự nhận dạng tạo ứng dụng thiết thực tùy theo nhu cầu, đối tượng áp dụng Nếu có thời gian tiếp tục nghiên cứu phương pháp khác để trích vector đặc trưng ảnh ký tự ngõ vào • Sự kết hợp giải thuật mờ K-lân cận gần với mạng Neuron nhận dạng chữ viết tay, cho kết với tỷ lệ xác cao • Nhận dạng dấu sắc, huyền, hỏi, ngã, nặng tiếng Việt nhận dạng chúng cách riêng biệt Tuy nhiên, xét tổ hợp chúng với nguyên âm có tiếng Việt nhận dạng giống ký tự thơng thường • Phát triển giải thuật phân đoạn từ thành ký tự, kết hợp với phương pháp phân loại Fuzzy-Neuron tạo hệ thống nhận dạng chữ viết tay có kết tốt Trang 91 HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến TÀI LIỆU THAM KHẢO Mathew Kerwin, “A Fuzzy K-Nearest Neighbor Algorithm Review and Critical Analysis”, 17-Nov-2005 Gader.P, M.Mohamed, and J.H.Chiang, “ Comparision of Crisp and Fuzzy Character Networks in Handwritten Word Recognition”, IEEE Trans Fuzzy Systems, 1995 Gader.P, M.Mohamed, and J.H.Chiang, “ Handwritten Word Recognition with Character and Inter-Character Neural Networks”, IEEE Trans System Man Cybernetics, 1993 J.M.Keller, M.R.Gray, and J.A.Givens, “ A fuzzy k-nearest neighbor algorithm”, IEEE Trans Syst., Man, Cybern., vol SMC-15, no.4, pp 580-585 July/August, 1985 R.M.Bozinovic and S.N.Srihari, “ Off-line cursive script word recognition”, IEEE Trans Pattern Anal Machine Intell, vol.11, no.1, Jan 1989 H.Shida and S.Mori, “Algebraic Description of Curve Structure”, IEEE PAMI-14, pp.516-533, 1992 H.Nishida, “Structural Feature Extraction on Multiple bases with Application to Handwriting”, Proc 2nd International Conference on Document Analysis and Recognition, Tsukuba Science City, Japan, pp 27-30, 1993 A.K Chhabra, Z An, D Balick, G Cerf, K Loris, P Sheppard, R Smith, B Witner, “High-order Statistically Derived Combinations of Geomtric Features for Hand-printed Character Recognition”, Proc 2nd International Conference on Document Analysis and Recognition, Tsukuba Science City, pp.397-401, 1993 J.C.Pettier, J.Camillerapp, “Script Representation by a Generalized Skeleton”, Proc 2nd International Conference on Document Analysis and Recognition, Tsukuba Science City, Japan, pp 850-853, 1993 10 J C Simon, “Off-line Cursive Word Recognition”, Proc IEEE, pp.1150-1161, 1992 11 J C Simon, K Zerhoumi, “Robust Description of a Line Image”, Proc 1st International Conference on Document Analysis and Recognition”, Saint-Malo, France, pp 3-14, 1991 12 J C Simon, O Baret, “Regularities and Singularities in Line Pictures”, Structured Document Analysis, H S Baird, H Bunke, K Yamamoto (eds), Springer Verlag, pp 261-281, 1992 13 L D Hamon, “Automatic Recognition of Printed and Scirpt”, Proc IEEE, pp 1165-1177,1972 Trang 92 HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến 14 C Y Suen, M Berthod and S Mori, “Automatic Recognition of Hand-printed Characters – the state of the art”, Proc IEEE, pp 469-485, 1980 15 S Mori, C Y Suen and K Yamamoto, “Historical review of OCR research and Development”, Proc IEEE, pp 1029-1058, 1992 16 M K Brown, “Cursive Script Recognition”, Ph D Dissertation, University of Michigan, Ann Arbor, MI, 1981 17 R Farag, “Word-level Recognition of Cursive Script”, IEEE C-28, pp 172-175, 1979 18 S W Lam, A Bhate and S N Srihari, “A sliding Window Technique for Word Recognition”, SPIE – Document Recognition II, San Jose, vol 2422, pp 38 – 45 19 S X Zhao and S N Srihari, “Word Recognition using a Lexicon Constrained by First/Last Character Decisions, SPIE – Document Recognition II, San Jose, vol 2422, pp 98-104,1995 20 T Hong, J J Hull and S N Srihari, “A unified Approach Towards Text Recognition”, SPIE – Document Recognition II, San Jose, vol 2660, pp 27-36, 1981 21 S Madhvanath and V Govindaraju, “Holistic Lexicon Reduction for Handwritten Word Recognition”, SPIE – Document Recognition III, San Jose, pp 224-234, 1996 22 G Kim and Govindaraju, “Efficient Chain Code based Image Manipulation for Handwritten Word Recognition”, SPIE, vol 2660, pp 262-272, 1996 23 K C Hayes, “Reading Handwritten Words using Hierarchical Relaxation”, CGIP14, pp.344-364, 1980 24 J T Favata and S N Srihari, “Recognition of Handwritten Words for Address Reading”, Proc 4th U.S Postal Service Advanced Technology Conference, Washington DC, pp 191-205, 1990 25 V Ramanaprasad, Y Shin and S N Srihari, “Reading Hand-printed Addresses on IRS Tax Forms”, SPIE, vol 2660, pp 243-250, 1996 26 J Camillerapp, G Lorette, G Menier and H Oulhadj, “Off-line and On-line methods for cursive handwriting recognition”, In: S Impedovo and J C Simon, Eds., 27 L A Zadeh, “Fuzzy Sets”, Inf Control, vol.8, pp 338-353, 1965 28 J C Bezdek, “Pattern Recognition with Fuzzy Objective Function Algorithm”, New York: Plenum Press, 1981 29 P Picton, “Introduction to Neural Networks”, MacMilan Press, 1994 Trang 93 HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mơ hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến LÝ LỊCH TRÍCH NGANG • • • • • Họ tên học viên: NGÔ QUANG TÂN Ngày tháng năm sinh: 22/09/1979 Chuyên ngành: Kỹ thuật vô tuyến – điện tử Địa liên lạc: 39 Nam Cao P.Tân Phú Q9 TP.HCM E-mail: quangtandem@yahoo.com Phái: Nam Nơi sinh: TP HCM MSHV: 01404347 Q TRÌNH ĐÀO TẠO • 9/1997 – 2/2002: học Đại học Bách Khoa Tp.HCM - chuyên ngành: Điện tử - Viễn thơng • 9/2004 – 6/2006: học Sau Đại học Đại học Bách Khoa Tp.HCM - chuyên ngành: Kỹ thuật vơ tuyến – điện tử Q TRÌNH CƠNG TÁC: • 5/2002 – 7/2003: làm việc công ty KASATI • 9/2003 – 12/2003: làm việc công ty TMA Solutions • 12/2003 – nay: làm việc cơng ty Điện thoại Tây – Bưu điện Tp.HCM Trang 94 HVTH: KS Ngô Quang Tân ... hiệu nhận dạng chữ viết tay Tỷ lệ nhận dạng đạt 90% việc nhận dạng từ với nguồn từ vựng huấn luyện khoảng 100 từ Trang HVTH: KS Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mô hình mờ hai chiều. .. Ngô Quang Tân Nhận dạng chữ viết tiếng Việt dùng mô hình mờ hai chiều THD: PGS.TS Lê Tiến Thường TS Hồng Đình Chiến Chương : CÁC VẤN ĐỀ TRONG NHẬN DẠNG CHỮ VIẾT 2.1 Sự phát sinh chữ viết tay Các... ĐỀ TÀI: NHẬN DẠNG CHỮ VIẾT TIẾNG VIỆT DÙNG MƠ HÌNH MỜ HAI CHIỀU II-NHIỆM VỤ VÀ NỘI DUNG: - Tìm hiểu tổng quan hệ thống nhận dạng chữ viết tay Tìm hiểu phương pháp trích đặc trưng chữ viết tay