Đề tài Tìm hiểu bài toán nhận dạng kí tự viết tay và phát triển ứng dụng

ĐỒ ÁN TỐT NGHIỆP Đề tài: TÌM HIỂU BÀI TOÁN NHẬN DẠNG KÍ TỰ VIẾT TAY VÀ PHÁT TRIỂN ỨNG DỤNG GVHD : Thầy Nguyễn Đình Thuân SVTH : Nguyễn Đình Cường Lớp : TH40 MSSV : 8D15014 NỘI DUNG BÁO CÁO GỒM 3 PHẦN PHẦN I : GIỚI THIỆU VỀ BÀI TOÁN PHẦN II : TRÌNH BÀY CƠ SỞ LÝ THUYẾT PHẦN III : TRÌNH BÀY CÀI ĐẶT MỘT SỐ ỨNG DỤNG MINH HỌA PHẦN I : GIỚI THIỆU BÀI TOÁN  KHÁI QUÁT TÌNH HÌNH NGHIÊN CỨU  MỤC ĐÍCH CỦA ĐỀ TÀI  GIỚI THIỆU MỘT SỐ ỨNG DỤNG THỬ NGHIỆM PHẦN II CƠ SỞ LÝ THUYẾT XÂY DỰNG CHƯƠNG TRÌNH  LÝ THUYẾT XỬ LÝ ẢNH  LÝ THUYẾT NHẬN DẠNG A. LÝ THUYẾT XỬ LÝ ẢNH MỘT SỐ THUẬT TOÁN TIỀN XỬ LÝ ẢNH I. Lọc mịn ảnh : dùng lọc trung bình, tác dụng hạn chế nhiễu muối tiêu. Ví dụ: sử dụng nhân lọc như sau: II. Nhị phân ảnh : tìm giá trị ngưỡng để phân mức xám ảnh thành 2 mức. Theo Otsu giá trị ngưỡng được xác định như sau: với p(v) ước lượng từ histogram T = (v2=vmax) v0 = vmin : là giá trị cần tìm Trong đó : III. Tách liên thông: Quét ảnh từ trái sang phải và từ trên xuống dưới, các pixel đen liên thông với nhau sẽ được gán chung một nhãn, nếu gặp liên thông mới thì nhãn mới sẽ được gán. Minh họa IV. Chỉnh nghiêng: biến đổi tuyến tính toạ độ điểm ảnh (x,y)=tan-1(Gy/Gx) Gy , Gx là kết quả xoắn điểm ảnh với nhân Sx, Sy : là giá trị trung bình góc nghiêng của các điểm ảnh được xét Ta có : x’= x + tg() y y’= y V. Chuẩn kích thước: Chuẩn kích thước ảnh về kích thước cố định fs(x, y)= f(x/sx ,y/sy ) với sx , sy là tỉ lệ phóng , fs(x,y) giá trị điểm ảnh kết quả ứng với giá trị toạ độ (x,y) VI. Lấp khoảng trống ảnh bằng phép đóng morphology: Sau khi phóng ảnh, ảnh có thể bị rời rạc, răng cưa biên. Để khắc phục tình trạng này ta dùng phép đóng để lấp các khoảng trống làm đầy ảnh. VII. Lấy đường biên và làm trơn đường biên: Phát hiện biên: Bằng cách nhân chập ảnh với phần tử có cấu trúc: Duyệt đường biên : Đường biên kí tự được duyệt theo cách sau: Bước 1: quét ảnh đến khi gặp điểm ảnh đen. Gọi là pixel 1 Bước 2: Lặp Nếu “ điểm ảnh hiện thời là đen ” thì “dò ngược” Ngược lại “sang phải” Đến khi gặp “pixel 1” Mã hoá hướng điểm biên: Sau khi duyệt đường biên, ta tiến hành mã hoá hướng các điểm trên đường biên theo 8 hướng sau: Quy ước: Hình minh hoạ mã hoá biên Làm trơn đường biên: Duyệt theo đường biên, nếu hai điểm liên tiếp trên đường biên có hiệu số hướng lớn hơn 1 thì hiệu chỉnh để hiệu số hướng bằng 1. B. RÚT ĐẶC TRƯNG CỦA KÍ TỰ I. Chia ô: ảnh sau khi tiền xử lí được chia thành các ô vuông nhỏ 8x8. Gom 4 ô kích thước 8x8 thành ô 16x16, các ô 16x16 phủ lên nhau theo hướng ngang và dọc. Trong mỗi ô 16x16 ta chia làm 4 vùng A, B, C, D:   Hình gộp 4 ô 8x8 Hình chia vùng ô 16x16 Vùng A :kích thước 4x4 Vùng B :kích thước 8x8 Vùng C :kích thước 12x12 Vùng D :kích thước 16x16 II. Véctơ đặc trưng: đặc trọng số vùng A, B, C, D tương ứng 4, 3, 2, 1. Gọi xj là một loại đặc trưng, xj được tính cho 1 ô 16x16 như sau: xj=4xj(A) + 3xj(B) + 2xj(C) + xj(D) Với mỗi ô 16x16 ta rút 4 đặc trưng xj (j=1,2,3,4), xj tính như trên. Aûnh kí tự được mô tả x1: số điểm biên có hướng 00 hay (1800) X=(x1, x2, x3, x4…xn ) x2: số điểm biên có hướng 450 hay (-1350) Với n=k*4 , k là tổng số ô 16x16 x3: số điểm biên có hướng 900 hay (-900) xếp chồng lên nhau x4: số điểm biên có hướng 1350 hay (-450) LÝ THUYẾT NHẬN DẠNG  PHÂN LỚP BẰNG PHƯƠNG PHÁP ĐỐI SÁNH  PHÂN LỚP DỰA VÀO HÀM THẾ  PHƯƠNG PHÁP LDA (Linear Disciminant Analysis)  PHÂN LỚP BẰNG MẠNG NƠRON PHÂN LỚP BẰNG MẠNG NƠRON I. Giới thiệu: Mạng nơron tổng quát có cấu trúc phân lớp, gồm 3 lớp: Lớp nhập: nhận giá trị bên ngoài vào Lớp xuất : lớp cuối cùng, sẽ xuất ra kết quả Lớp ẩn : các lớp còn lại (có thể không có) Quá trình nhận dạng của mạng là quá trình ánh xạ một mẫu x từ không gian các đặc trưng vào không gian các lớp. II. Hoạt động: Chỉ có thể ở một trong hai trạng thái: trạng thái ánh xạ và trạng thái học. Trạng thái ánh xạ: thông tin sẽ được lan truyền tiến từ các nút nhập đến các nút xuất và một mẫu x sẽ được ánh xạ thành một kết quả z. Trạng thái học: các trọng số của kết nối sẽ được điều chỉnh theo một thuật toán học để mạng có thể xấp xỉ được một hàm mong muốn nào đó. Thuật toán lan truyền ngược là một thuật toán hiệu quả cho quá trình học của mạng. Minh hoạ mạng nơron III. Giải thuật luyện mạng: Quá trình học của mạng theo thuật toán lan truyền ngược sẽ lặp đi lặp lại các thao tác sau: - Lan truyền tiến: tính kết xuất y của mạng với một mẫu x. - Lan truyền ngược : tính sai số giữa kết xuất y và giá trị đích t và lan truyền ngược sai số này lại để cập nhật trọng số cho mạng. Quá trình học của mạng sẽ dừng khi mạng đạt được một độ lỗi nhất định, hoặc sau giới hạn số lần lặp. Để thay đổi trọng số của mạng nhằm cực tiểu hàm lỗi có thể dùng phương pháp giảm gradient gồm các bước sau: - Chọn ngẫu nhiên một điểm x0 trong không gian trọng số. - Tính độ dốc của hàm lỗi tại x0. - Di chuyển điểm x0 theo hướng dốc nhất của hàm lỗi. Quá trình tính độ dốc và di chuyển điểm x0 được lặp đi lặp lại cho đến khi x0 tiến đến giá trị làm cho hàm lỗi cực tiểu. Ta có công thức cập nhật trọng số theo phương pháp giảm gradient: t : số lần cập nhật trọng số hiện tại  : hệ số học w: trọng số bất kì trong mạng E : hàm lỗi Ta có hàm lỗi sai số trung bình bình phương được sử dụng là: Với (Xk , Zk): tập mẫu học Tk : ánh xạ của Xk qua mạng K : số mẫu học N : số chiều của vectơ output M: số chiều của vectơ input Trong đó : (Xk, Zk) = (xk1,…,xkM; zk1 ,…, zkN) Tk = ánh xạ (Xk) = (tk1 ,…,tkN) Hàm truyền được sử dụng là hàm logistic: Mục đích ánh xạ mẫu trong quá trình lan truyền tiến. Đồ thị PHẦN III MỘT SỐ ỨNG DỤNG MINH HỌA THỬ NGHIỆM  TÁCH LIÊN THÔNG TRONG NHẬN DẠNG VĂN BẢN  NHẬN DẠNG KÍ TỰ VIẾT TAY RỜI RẠC  XỬ LÝ PHIẾU ĐĂNG KÍ MÔN HỌC TÁCH LIÊN THÔNG TRONG NHẬN DẠNG VĂN BẢN Nhận dạng văn bản, là một trong những bài toán có liên quan đến nhận dạng kí tự. Với cơ sở lý thuyết vừa nêu ta hoàn toàn có thể xây dựng được ứng dụng này. I. Quy trình xử lý: II. Thực hiện: nhận dạng văn bản chứa kí tự font Vni-Times, size 12, không nghiêng. Xử lý kí tự được thực hiện như sau: Chuẩn hoá vào lưới ô vuông kích thước 56x48. Xác định đặc trưng như sau: Chia khung chữ thành nhiều ô vuông kích thước 8x8, trên mỗi ô vuông xác định 4 đặc trưng: - Tổng số pixel có hướng 0 hoặc 4 - Tổng số pixel có hướng 1 hoặc 5 - Tổng số pixel có hướng 2 hoặc 6 - Tổng số pixel có hướng 3 hoặc 7 Hướng của pixel được xác định so với pixel ở trung tâm của ô vuông kích thước 8x8. Với một ảnh kí tự ta có được 7x6x4=168 đặc trưng. X=(x1, x2, …xn) , n=168. Giải thuật nhận dạng: Tìm một mẫu trong số các mẫu lưu trữ có đặc trưng gần giống nhất với mẫu cần nhận dạng. Hàm “gần giống ” dựa vào hàm tính khoảng cách ơclit giữa hai véctơ. Hình minh hoạ kết quả. THỬ NGHIỆM NHẬN DẠNG KÍ TỰ VIẾT TAY RỜI RẠC I. Giới thiệu: Chương trình nhận dạng kí tự viết tay, bước đầu thử nghiệm xây dựng bộ nhận dạng cho 2 lớp kí tự: Lớp kí tự chữ cái: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, a, b, d,e, f, g, h, i, j, k, l, m, n, q, r, s, t, v, x, y. Lớp kí tự số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. II. Thực hiện chương trình: Ta có quy trình xử lý như sau: Aûnh đầu vào  lọc ảnh  nhị phân hoá  tách các liên thông chữ  chỉnh nghiêng  chuẩn hóa kích thước  tìm biên  rút đặc trưng trên đường biên  qua bộ phân lớp  quyết định lớp của ảnh nhận dạng  xuất kết quả theo định dạng trật tự kí tự trên hàng. Như vậy: Trong quá trình tiền xử lí, ảnh của kí tự được chuẩn hoá về kích thước chuẩn được chọn là 80x56. Sau khi phát hiện biên và mã hoá đường biên, véctơ đặc trưng của kí tự được xác định như lý thyết đã mô tả về xác định đặc trưng ở phần B mục xác định đặc trưng của kí tự, từ đó ta có X=(x1 , x2 ,… xn) với n=216. Bộ nhận dạng được xây dựng là mạng nơron 2 lớp: 1 lớp vào và 1 lớp ra. Với giải thuật lan truyền ngược và kỹ thuật giảm gradient, chọn  = 0.08. Véctơ X=(x1, x2, …xn) trong quá trình huấn luyện và nhận dạng được chuẩn hoá sao cho các xi được tính lại như sau: Thử nghiệm trên 2 mạng: Mạng thứ nhất thử nghiệm trên 2366 mẫu học, đối với lớp kí tự, được luyện sau 30.000 học kì. Mạng thứ hai thử nghiệm trên 1000 mẫu học, đối với kí tự số, được luyện sau 10.000 học kì. Sau thời gian học mạng thứ nhất và mạng thứ hai phân biệt gần hoàn toàn các mẫu đã học, mạng có khả năng tổng quát tốt. Kết quả: Minh họa nhận dạng kí tự chữ cái. Minh họa nhận dạng kí tự số ỨNG DỤNG XỬ LÝ PHIẾU ĐĂNG KÍ MÔN HỌC I. Giới thiệu: chương trình xử lí phiếu đăng kí môn học có nhiệm vụ nhận dạng thông tin được rút ra từ biểu mẫu, nhằm tiết kiệm chi phí cho việc đăng kí môn học. Aûnh phiếu đăng kí môn học: Từ phiếu này ta rút ra các thông tin: Mã số sinh viên (MSSV). Mã môn học huỷ bỏ, mã lớp huỷ bỏ môn này. - Mã môn học lại, mã lớp học lại môn này Mã môn học vượt, mã lớp học vượt môn này. Như vậy: Từ các thông tin trên ta có thể xác định yêu cầu đăng kí môn học của mỗi sinh viên. II. Quy trình xử lý: thông tin cần lấy trong phiếu được tạo bởi các kí tự số và kí tự chữ: Kí tự số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Kí tự chữ gồm một số kí tự: B, C, D, H, K, L, P, S, T, N. Như vậy có khoảng gần 20 kí tự. Ta có quy trình thực hiện: Định dạng và lấy thông tin từ biểu mẫu: Tìm kiếm dấu hiệu định vị biểu mẫu, lấy thông tin trong vùng dữ liệu bằng cách so khớp với mặt nạ biểu mẫu. Xác định vectơ đặc trưng: Vectơ đặc trưng của kí tự được xác định như trong phần nhận dạng kí tự viết tay đã nêu, ta có vectơ X=(x1 , x2 ,…xn ) với n=216. Nhận dạng vectơ đặc trưng: Xây dựng mạng nơron 2 lớp, để phân biệt 20 kí tự vừa nêu với các thông số: mạng luyện sau 50.000 học kì với 2051 tập mẫu, sử dụng kỹ thuật lan truyền ngược và giảm gradient với  = 0.08. Điểm chốt Lề dọc Lề ngang Vùng dữ liệu Hình minh họa cách rút dữ liệu trong biểu mẫu Ta có kết quả xử lý và nhận dạng: NHẬN XÉT VÀ HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI I. Nhận xét chung: Nhìn chung về cơ bản chương trình đã đáp ứng được yêu cầu đặt ra của đề tài. Ưu điểm: Với những chữ số và chữ cái viết hoa, khả năng nhận dạng của chương trình là tương đối tốt. Việc tách kí tự tương đối chính xác. Chương trình mạng lại nhiều ứng dụng thực tiễn. Nhược điểm: Hệ thống còn hạn chế về giao diện, việc quản lí bộ nhớ chưa được chú trọng, cần thay đổi định dạng file ảnh lưu trữ. II. Hướng phát triển: Tiếp tục nghiên cứu, quan tâm các yếu tố đặc trưng khác để tăng chính xác cho nhận dạng như các đặc trưng: chu vi, diện tích, số các lỗ của kí tự…v.v. Mở rộng bộ nhận dạng cho các kí tự có dấu và phát triển các ứng dụng khác. III. Lời cám ơn: Từ đồ án này em đã bước đầu nắm được một số vấn đề xung quanh bài toán xử lý, nhận dạng ảnh chữ viết tay và phát triển ứng dụng. Qua đây, em xin gửi lời cám ơn chân thành đến thầy Nguyễn Đình Thuân ( giáo viên hướng dẫn), đã tận tình chỉ bảo, tạo điều kiện thuận lợi, động viên giúp em hoàn thành nội dung đồ án này, cám ơn các bạn sinh viên đã đóng góp nhiều ý kiến quý báu giúp chương trình hoàn thiện hơn. TÀI LIỆU THAM KHẢO [1]. “ Nhập môn xử lý ảnh số”, Lương Mạnh Bá – Nguyễn Thanh Thủy, Nhà xuất bản Khoa Học Kỹ Thuật, 1999. [2]. “ Nhận dạng chữ viết tay rời tiếng Việt”, luận án thạc sĩ, Phạm Đại Xuân, Đại học Khoa Học Tự Nhiên TPHCM. [3]. “ Một số phương pháp mới để giải quyết các bài toán trong nhận dạng tiếng Việt”, luận văn thạc sĩ khoa học, Nguyễn Trí Tuấn, Đại học Khoa Học Tự Nhiên TPHCM. [4]. “ Xử lý ảnh và video số”, Nguyễn Kim Sách, Nhà xuất bản Khoa Học Kỹ Thuật. [5]. “ Mạng nơron phương pháp và ứng dụng”, Nguyễn Đình Thúc, Nhà xuất bản Giáo Dục, 2000 . [6]. “ Nhận dạng cảm xúc mặt người”, luận văn tốt nghiệp đại học, Ngô Trung Thành, Đại học Khoa Học Tự Nhiên TPHCM. [7]. “ Ứng dụng mạng nơron nhân tạo trong hệ thống xử lý biểu mẫu tự động”, Hoàng Kiếm (Khoa công nghệ thông tin Đại học Khoa Học Tự Nhiên TPHCM), Nguyễn Hồng Sơn - Đào Minh Sơn ( Trung tâm máy tính, Cục xuất nhập cảnh, Bộ công an). [8]. “ Giáo trình lý thuyết và bài tập Borland Delphi”, Lê Phương Lan -- Hoàng Đức Hải, Nhà xuất bản Giáo Dục, 2000. [9]. “ Practical computer vision using C “, J.R.Parker. [10]. Ebook: “Pattern_Recognition_with_Neural_Networks_in_C++”. [11]. “Extraction of Data from Preprinted Forms” A.Ltaylor, R.Fritzson, J.A.Pastor, Machine Vision Applications, vol.5, pp.211-222,1992. [12]. “ Open CV”, Intel open source computer vision library.