Đồ án 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ìm hiểu bài toán nhận dạng kí tự viết tay và phát triển ứng dụng”  Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 1 LỜI NÓI ĐẦU Nhận dạng kí tự, đặc biệt kí tự viết tay là bài tốn có nhiều ứng dụng thực tiễn. Về mặt lý thuyết, chưa có phương pháp nào hồn chỉnh cho cho bài tốn này do tính phức tạp, sự biến dạng của dữ liệu đầu vào. Những năm gần đây, cùng vơí sự phát triển của lý thuyết nhận dạng, công nghệ xử lý ảnh, đã có nhiều nghiên cứu mang lại một số kết quả cho bài tốn nhận dạng kí tự viết tay, từ đó mở ra hàng loạt ứng dụng thực tế. Mục tiêu của đồ án nhằm giới thiệu một cách tiếp cận bài tốn nhận dạng chữ viết tay với một số ràng buộc, nhằm từng bước đưa vào ứng dụng thực tiễn. Mặc dù hết sức cố gắng, song do thời gian có hạn và những hạn chế bản thân nên đồ án có thể còn thiếu sót, mong tiếp tục nhận được sự chỉ bảo của Thầy, Cô và ý kiến đóng góp của các bạn sinh viên để đồ án được hồn thiện hơn. Em xin chân thành cảm ơn. Nha Trang Ngày 10 tháng 9 năm 2003 Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 2 NHẬN XÉT CỦA GIÁO VIÊN. ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... ............................................................................................................................... Giáo viên nhận xét PHẦN I Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 3 TỔNG QUAN VÀ CƠ SỞ LÝ THUYẾT TIỀN XỬ LÝ ẢNH KÍ TỰ CHƯƠNG I TỔNG QUAN I. Giới thiệu bài tốn: Nhận dạng kí tự, đặc biệt kí tự viết tay là bài tốn có nhiều ứng dụng thực tế. Máy tính xử lí, nhận dạng các biểu mẫu, phiếu điều tra tự động, bằng cách này ta có thể tiết kiệm được nhiều chi phí về thời gian, công sức cũng như các chi phí khác cho việc nhập dữ liệu. Ngày nay cùng với sự phát triển về mặt lý thuyết, công nghệ, có rất nhiều hướng đi cho việc giải quyết bài tốn này như: nhận dạng kí tự dựa trên cấu trúc hay cách tiếp cận khác như dùng: logic mờ, giải thuật di truyền, mô hình xác suất thống kê, mô hình mạng nơ ron. Đặc biệt trong những năm gần đây mô hình mạng nơron được quan tâm nhiều do khả năng tổng hợp của mô hình và sự phát triển về tốc độ xử lí của máy tính. Trên thế giới hiện nay có nhiều chương trình nhận dạng chữ viết (chữ in và viết tay) bằng các thứ tiếng Anh, Nga, v.v... như các hệ OMNIPAGE, READ- WRITE, WORD-SCAN,... Ở Việt Nam cũng có một số hệ như WORC của công Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 4 ty 3C, VIET-IN của công ty SEATIC, VNDOCR của Viện Công Nghệ Thông Tin, Image Scon của Trung Tâm Tự Động Hóa Thiết Kế, hệ WINGIS của công ty DolfSoft... Nhìn chung, các sản phẩm phần mềm nhận dạng văn bản Tiếng Việt chữ in của nước ta đã thu được kết quả khả quan, đặc biệt phần mềm VNDOCR đã được sử dụng rộng rãi trong các cơ quan nhà nước. Riêng phần nhận dạng kí tự viết tay vẫn đang được nghiên cứu và phát triển nhằm phục vụ cho các yêu cầu khác nhau như đọc và xử lý các biểu mẫu: hố đơn, phiếu điều tra ... Với mục tiêu tìm hiểu bài tốn nhận dạng ảnh kí tự viết tay không trực tuyến (off-line), đồng thời sử dụng kết quả vào việc xử lí phiếu đăng kí môn học của Trường Đại Học Thuỷ Sản Nha Trang. Nội dung đồ án là sự thử nghiệm xây dựng chương trình nhận dạng ảnh kí tự viết tay nêu trên, bằng cách sử dụng mạng nơron để nhận dạng kí tự, dựa trên tập mẫu kí tự đã được mã hố bởi đặc trưng của đường biên. Trong quá trình tìm hiểu lý thuyết và xây dựng chương trình, em đã tham khảo nhiều nguồn tài liệu, trong đó ý tưởng xác định véc tơ đặc trưng của kí tự viết tay sử dụng trong đồ án này được tham khảo từ luận án thạc sĩ “ Nhận dạng chữ viết tay rời Tiếng Việt”, của tác giả Phạm Đại Xuân, Đại học khoa học tự nhiên Thành Phố Hồ Chí Minh. II. Cấu trúc, nội dung của đồ án: Nội dung của đồ án được chia làm 4 phần: Phần I: Giới thiệu tổng quan và cơ sở lý thuyết tiền xử lí ảnh kí tự, gồm 3 chương: Chương 1: Giới thiệu tổng quan. Chương 2: Giới thiệu cơ sở lí thuyết tiền xử lí ảnh kí tự. Chương 3: Giới thiệu cách xác định đặc trưng của kí tự. Phần II: Giới thiệu các mô hình nhận dạng, gồm 2 chương. Chương 1: Giới thiệu một số kĩ thuật phân lớp: đối sánh, sử dụng hàm thế, phương pháp LDA. Chương 2: Giới thiệu mô hình mạng nơ ron cho bài tốn nhận dạng. Phần III: Giới thiệu một số ứng dụng và đánh giá kết luận gồm 4 chương . Chương 1: Giới thiệu ứng dụng kĩ thuật tách liên thông cho việc tách liên thông kí tự trong văn bản. Chương 2: Xây dựng, đánh giá chương trình nhận dạng kí tự viết tay. Chương 3: Đưa kết quả vào ứng dụng xây dựng chương trình xử lí phiếu đăng kí môn học cho sinh viên ở trường Đại học Thuỷ Sản Nha Trang. Chương 4: Đánh giá kết luận và nêu hướng phát triển của đề tài. Phần IV : Phụ lục giới thiệu giao diện chương trình. Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 5      dvvpvveE j j j    1 22 CHƯƠNG II CƠ SỞ LÝ THUYẾT TIỀN XỬ LÍ ẢNH KÍ TỰ I. Lọc mịn ảnh: Lọc mịn ảnh là một lọc thông thấp, giá trị của một điểm ảnh là trung bình trọng số của các điểm ảnh lân cận, hay giá trị điểm ảnh là kết quả của quá trình xoắn (convole) của các điểm ảnh lân cận với một nhân. Nhân có kích thước tuỳ ý 3x3, 5x5, kích thước nhân càng lớn thì càng nhiều điểm lân cận ảnh hưởng vào điểm ảnh kết quả. Ví dụ một số nhân lọc mịn ảnh như sau: Lọc mịn ảnh có tác dụng hạn chế ảnh nhiễu muối tiêu. II. Nhị phân ảnh: Nhị phân ảnh mức xám là tìm giá trị ngưỡng sao cho các điểm ảnh có giá trị lớn hơn ngưỡng được gọi là trắng(nền) và các điểm ảnh có giá trị nhỏ hơn ngưỡng được gọi là đen (đối tượng). Tiêu chuẩn xác định ngưỡng thường sử dụng nhất là sử dụng sai số bình phương trung bình giữa giá trị mẫu v và mức tái thiết r(v). (ký hiệu MSE) Ta có: Trong đó p(v) là hàm mật độ xác suất của biến ngẫu nhiên v, có thể coi xấp xỉ bằng histogram của ảnh. Với một số cho trước L các mức xám MSE được biểu diễn bởi: E 2e =         dvvpvrvvrvE    0 22 1 1 1 1 1 1 1 1 1 1/9 1 1 1 1 2 1 1 1 1 1/10 1 1 1 1 4 1 1 1 1 1/12 Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 6     1..1 1...1 2 1 1 1          Lj dvvp dvvvp r Lj rr v j j j j v v v v j jj j Do r(v)=rj là hằng số trong đoạn [vj , vj+1]. Với p(v) cho trước và số mức tái thiết L cố định, các mức quyết định vj , j= 1…L-1 và các mức tái thiết rj , j=0..L-1 cực tiểu hố MSE tuân theo quan hệ sau: Tuy nhiên, không có cách giải quyết dưới dạng khép kín nào tồn tại trừ khi chấp nhận một số phép xấp xỉ. Bây giờ ta xem xét trường hợp ngoại lệ nhưng quan trọng với L=2. Đó là trường hợp nhị phân hố ảnh. Khi đó MSE trở thành: Giả sử rằng p(v) có thể ước lượng từ histogram và v0, v2 tương ứng với vmin, vmax. Còn lại ba tham số cần được tính tốn đó là r0, r1, và v1. Tham số v1 gọi là ngưỡng nhị phân hố. Hơn nữa r0(v1) và r1(v1) cực tiểu MSE, với một giá trị cho trước của vj, đơn giản là những giá trị trung bình trong đoạn tương ứng: Như vậy đủ để biến đổi v1 từ v0 đến v2. MSE được tính bằng cách thay r0 và r1 bằng r0(v1) và r1(v1) tương ứng và chọn vl* sao cho MSE là cực tiểu. Otsu đề nghị một cách tương tự nhưng tiêu chuẩn đơn giản hơn về mặt tính tốn dựa trên phân tích biệt số. Trong công thức này, MSE tương đương với phương sai lớp trong W2(v1). Nếu W2(v1) được bổ sung vào phương sai lớp giữa             1 0 2 1 2 1 2 0 2 v v v v dvvprvdvvprveE         1 0 1 0 10 v v v v dvvp dvvvp vr         2 1 2 1 11 v v v v dvvp dvvvp vr Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 7 B 2(v1), ta được tồn bộ biến đổi T2( độc lập v1). Như vậy, thay vì cực tiểu MSE, giải thuật của Otsu cực đại phương sai giữa lớp: Trong đó: Và Biểu thức có thể đơn giản thành : Thật ra, còn tồn tại một số tiêu chuẩn lượng hố khác, chẳng hạn entropy, cũng trên histogram của mức xám. Histogram có thể được tính từ tồn bộ ảnh hoặc từ lân cận địa phương giới hạn xung quanh ảnh đang xét. III. Đánh nhãn thành phần liên thông: Khái niệm liên thông trong kí tự có thể xem như tập hợp các điểm ảnh liền nhau tạo nên kí tự, mục tiêu của giải thuật này là lọc ra những kí tự có trong ảnh. 1. Tách liên thông bằng kĩ thuật đệ quy : Để tách liên thông ta nghĩ ngay đến kỹ thuật đệ quy cấp 8 (tại mỗi bước chúng ta có tối đa 8 lựa chọn tiếp theo). Quy ước : Điểm (x, y) : cho biết giá trị điểm tại toạ độ (x, y). =1 màu chữ =0 màu nền Height : Chiều cao ảnh Width : Chiều rộng ảnh Ta có giải thuật như sau: // Đưa tất cả các điểm liên thông với Điểm(x,y) vào liên thông t Procedure Chonvao((x,y) :điểm, t :liênthông) Begin If (Điểm(x, y)=1) AND (NOT đã_xét[x,y]) then Begin Them_vao_lien_thong(t,(x, y));           2111121010*1 maxarg TT vvpvvpv                        max2 1 1 11 1110 111 110 1 1 vv v vv vvv vvp vvp T T                          1 0 1 0 1 1 v v v v dvvvpv dvvpv                      11 2 11* 1 1 . maxarg vv vvv T   Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 8 Đã_xét[x, y] :=True ; For i :=x-1 to x+1 do For j:= y-1 to y+1 do If ( i x) or (jy) then Chonvao((i, j),t); End; End ; // Ta có thủ tục tách liên thông đệ quy như sau : Procedure TáchLiênThôngĐQ(VAR LT: Danh_Sách_Liên_Thông) Begin T:= t:= For j:=1 to Height do For i:=1 to Width do đã_xét[i, j]:=False; For j:=1 to Height do For i:=1 to Width do If (Điểm(x, y)=1) AND( NOT Đã_xét[i, j]) then Begin Chonvao( (i, j ),t); Thêm _liên_thông_vào_Danh_Sách(T, t) ; t := ; End ; End; Nhận xét: Thuật tốn này chỉ có ý nghĩa minh hoạ bản chất của tách liên thông. Ta không chọn thuật tốn này cài đặt vì chi phí đệ quy quá cao, chưa kể tốc độ thực hiện. 2. Giải thuật cải tiến: Để gán nhãn cho thành phần liên thông ta có thể duyệt theo từng đường chạy. Kỹ thuật này gán cho mỗi thành phần liên thông của ảnh nhị phân một nhãn riêng biệt. Nhãn thường là các số tự nhiên bắt đầu từ một đến tổng số các thành phần liên thông trong ảnh input. Giải thuật phát biểu như sau: Quét ảnh từ trái sang phải và từ trên xuống dưới. Trong dòng thứ nhất chứa pixel đen, một nhãn duy nhất được gán cho mỗi đường chạy liên tục của pixel đen. Với mỗi pixel đen của dòng tiếp theo, các pixel lân cận dòng trước và pixel bên trái được xem xét (hình vẽ a ). Nếu bất kì pixel lân cận nào được gán nhãn, nhãn tương tự được gán cho pixel đen hiện thời; ngược lại, nhãn tiếp theo chưa được sử dụng được chọn. Thủ tục này được sử dụng cho đến dòng cuối của ảnh. Lúc kết thúc tiến trình này, một thành phần liên thông có thể chứa các pixel có các nhãn khác nhau vì khi chúng ta xem xét lân cận của pixel đen, chẳng hạn pixel “?” (trong hình c), pixel đối với lân cận trái và những lân cận trong dòng trước có thể gán nhãn một cách riêng biệt. (Trong ví dụ này, chúng ta sử dụng nhãn của lân cận trái). Một tình huống như vậy phải được xác định và ghi lại. Sau Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 9 . . . . . . P P P . . L ? . . . . . . . tiến trình quét ảnh, việc gán nhãn được hồn tất bằng cách “thống nhất mâu thuẫn các nhãn” và gán lại các nhãn chưa sử dụng. Để minh hoạ ta có các hình biểu diễn sau: Hình a. lân cận của “?” P= dòng trước; L=lân cận trái IV. Chỉnh nghiêng: Chỉnh nghiêng ảnh là một phép biến đổi tuyến tính của toạ độ điểm ảnh. Trước hết ta phải xác định góc nghiêng tổng thể của đối tượng, và ta dịch chuyển điểm ảnh đối tượng theo phương ngang tuỳ theo giá trị góc nghiêng tổng thể này và giá trị y của điểm này. Hình a Hình b Chuyển gớc toạ độ về trọng tâm ảnh như hình b Góc nghiêng của kí tự được qui ước tính là góc từ trục tung, hướng về bên trái có giá trị dương, hướng về bên phải có giá trị âm. 0 + - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . * * * * . . * * * . . . . . 1 1 1 1 . . 2 2 2 . . . . . . * * * . . * * * * . . . . . 1 1 1 . . 2 2 2 2 . . . . * * * * . * * * * * . . . . 1 1 1 1 . 2 2 2 2 2 . . . . . . * * * * * . . . . . . . . . 1 1 ? * * . . . . . . . . . * * * * * * . * . . .  . . . * * * * * * . * . . . * * . . . . . . . . * * . . * * . . . . . . . . * * . . . * * . . . . . . . * * . . . * * . . . . . . . * * . . . * * . . . . . . . . . . . . * * . . . . . . . . . . . Hình b . Aûnh ban đầu Hình c . Tiến trình gán nhãn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 . . 2 2 2 . . . . . 1 1 1 1 . . 1 1 1 . . . . . . 1 1 1 . . 2 2 2 2 . . . . . 1 1 1 . . 1 1 1 1 . . . . 1 1 1 1 . 2 2 2 2 2 . . . . 1 1 1 1 . 1 1 1 1 1 . . . . . . 1 1 1 1 1 . . . . . . . . . 1 1 1 1 1 . . . . . . . . . 1 1 1 1 1 1 . 3 . . .  . . . 1 1 1 1 1 1 . 2 . . . 4 4 . . . . . . . . 3 3 . . 3 3 . . . . . . . . 2 2 . . . 4 4 . . . . . . . 3 3 . . . 3 3 . . . . . . . 2 2 . . . 4 4 . . . . . . . . . . . . 3 3 . . . . . . . . . . . Hình d . Sau khi quét đầy đủ Hình e .Kết quả sau cùng Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 10 Góc nghiêng tổng thể kí tự là hướng trung bình của các điểm ảnh đối tượng có giá trị góc khoảng –450 đến 450 theo quy ước tính góc trên . Các điểm ảnh đối tượng có hướng ngồi khoảng –450 đến 450 không tính. Giả sử gọi  là góc nghiêng tổng thể của kí tự , điểm ảnh đối tượng p(x,y) (trong hệ toạ độ mới ) sẽ có toạ độ mới là p(x’ ,y’) (trong hệ toạ độ mới ) với : Để tính góc nghiêng tổng thể ta phải tính được hướng của các điểm ảnh đối tượng. Hướng tại một điểm ảnh đối tượng được tính nhờ vào vectơ gradient điểm ảnh đó. Vectơ gradient tại một điểm ảnh (x, y)là: Độ lớn vectơ gradient tại (x,y) được tính bởi: Hướng của vectơ gradient tại(x,y) được tính bởi: Gx và Gy là kết quả xoắn (convolve) với nhân Sobel Sx và Sy: Hình . Các nhân của bộ lọc Sobel Chú ý: góc tính theo gradient tại mỗi điểm ảnh đối tượng là góc so với trục x và chỉ xét những điểm có hướng của vectơ gradient thoả trong khoảng [450,1350] hay [-1350,-450]. V. Chuẩn kích thước: Chuẩn kích thước ảnh kí tự về một kích thước cố định và phóng sát bốn biên của ảnh. Phóng ảnh là thực hiện phép biến đổi sau: Với (x, y) là toạ độ điểm ảnh sau khi phóng và sx ,sy là tỷ lệ phóng theo trục x và y tương ứng, fx(x,y) là giá trị điểm ảnh kết quả ứng với giá trị toạ độ (x, y). Chú ý: -1 0 1 -2 0 2 -1 0 1 Sx -1 -2 -1 0 0 0 1 2 1 Sy   yy ytgxx   ' '                         y f x f G G f y x 22 yx GGf            x y G G yx 1tan,    yxs sysxfyxf ,,  Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 11 0 1 0 1 1 1 0 1 0 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 thực hiện một số xử lý bằng phép đóng morphology: VI. Lấp khoảng trống ảnh bằng phép đóng morphology: 1. Một số định nghĩa: Giả sử A và B là hai tập trong không gian Z2, aЄ A thì a=(a1, a2) Phép dịch chuyển của tập A đối với x=(x1, x2) ký hiệu(A)x , được định nghĩa. Phép phản chiếu của tập B, ký hiệu B*, được định nghĩa: Phép bù của một tập A, ký hiệu Ac, được định nghĩa: Hiệu của hai tập hợp A và B, ký hiệu A-B, được định nghĩa: 2. Phép giãn: Giả sử A, B là hai tập thuộc Z2,  là tập hợp rỗng, phép giãn của A đối với B, ký hiệu AB, được định nghĩa: Tập B thường được gọi là thành phần cấu trúc. 3. Phép co: Giả sử A, B là hai tập thuộc Z2, phép co của A đối với B, ký hiệu AB được định nghĩa: 4. Phép đóng: Giả sử A, B là hai tập thuộc Z2, phép đóng của A đối với B, ký hiệu AB được định nghĩa: Tức phép đóng là phép do thực hiện phép mở rồi thực hiện phép đóng lên kết quả vừa có. Phép đóng có tác dụng làm đầy những khoảng nhỏ (tuỳ thuộc vào thành phần cấu trúc B) thường xảy ra trên đường biên. Thành phần cấu trúc thường được sử dụng là thành phần cấu trúc đối xứng có gốc (0, 0) là ở tâm như hình:    A a vôùi  ,xaccA x  B bôùi  vbxxB ,*  AxxAC   BxAxxBA  ,    ABxBA x*   ABxBA x    BBABA  Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 12 Nhưng do ảnh được quét với độ phân giải 300 dpi, và đối với những chữ có bụng được viết khá nghiêng thì khi thực hiện phóng với thành phần cấu trúc trên, tức thực hiện phép giãn rồi thực hiện phép co, thì phép giãn làm cho phần bụng bị dính lại với nhau do với mỗi hướng ngang và đứng đều được giãn 2 điểm ảnh. Để hạn chế điều này ta sử dụng 2 thành phần cấu trúc không đối xứng và thực hiện phép đóng 2 lần trên 2 thành phần cấu trúc này, vì khi thực hiện phép giãn thì chỉ cần giãn về 1 phía: Các thành phần cấu trúc không đối xứng. VII. Lấy đường biên và làm trơn đường biên: 1. Phát hiện biên: Biên của ảnh được thiết lập bằng cách nhân chập ảnh với phần tử có cấu trúc: 2. Dò biên và mã hố đường biên: Ta có giải thuật dò tìm biên như sau: Bước 1: Quét ảnh đến khi gặp điểm ảnh đen. Gọi nó 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” Minh hoạ dò biên 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 1 2 12 3 5 11 4 6 10 9 8 7 Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 13 3. Xác định hướng của điểm biên (Freeman code): Các hướng được quy ước như sau: Với hướng quy ước trên, đường biên được mã hố như sau: 4. Làm trơn đường biên: Làm trơn đường biên là 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ì có thể hiệu chỉnh để có đường biên mà hai điểm liên tiếp có hiệu số hướng bằng 1. Theo mã hướng Freeman, hiệu số hướng của 2 điểm liên tiếp nhau trên đường biên được định nghĩa : Goi ci là mã hướng tại điểm biên đang xét pi , ci+1 là mã hướng của điểm kế tiếp trên đường biên pi+1 Đặt d=ci+1-ci và Dabs=|d| nếu |d|4 Và dabs=8-|d| nếu |d|>4 Ta có các trường hợp sau: a. dabs1 : Điểm biên trơn. b. dabs=2 và ci chẵn, ci+1 chẵn : bỏ pi+1 và thay hướng pi như sau: 0 1 2 3 4 5 6 7 Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 14 Dabs=2 và ci chẵn , ci+1 chẵn c. dabs=2 và ci lẻ , ci+1 lẻ : Bỏ pi+1 và thay hướng pi như hình Dabs=2 và ci lẻ, ci+1 lẻ d. dabs=3 , ci chẵn, ci+1 lẻ e. dabs=3, ci lẻ, ci+1 chẵn Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 15 Minh hoạ ảnh kí tự sau quá trình tiền xử lý. Aûnh ban đầu Ảnh qua tiền xử lý CHƯƠNG III RÚT ĐẶC TRƯNG I. Giới thiệu đặc trưng hướng: Hướng các điểm trên đường biên của kí tự mô tả khá đầy đủ về kí tự. Đặc trưng của ảnh được xác định là hướng của các điểm ảnh trên biên. Việc chọn đặc trưng để nâng cao độ chính xác của bài tốn nhận dạng là hết sức khó khăn, đòi hỏi rất nhiều thời gian và quyết định rất nhiều đến độ chính xác. Hơn nữa, do biến dạng khá lớn trong chữ viết tay nên để hạn chế người ta thường chia ô trên ảnh và Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 16 đặc trưng được rút trong các ô đó, việc chọn các ô phủ lấp lên nhau cũng không ngồi mục đích trên. II.Chia ô: Aûnh kí tự sau khi tiền xử lý kích thước được chuẩn về mn điểm ảnh, ảnh được chia nhỏ thành các ô vuông nhỏ kích thước 88 điểm ảnh như hình: Hình minh hoạ cách chia ô kí tự. Gom 4 ô kích thước 8x8 thành ô kích thước 16x16, và các ô kích thước 16x16 này được phủ lên nhau một nữa theo hai hướng ngang và dọc. Trên mỗi ô kích thước 16x16 sẽ rút đặc trưng theo 4 hướng (00, 450, 900,1350) . Mỗi ô này được chia làm 4 phần theo điểm tâm của ô, phần trung tâm A có kích thước 4x4 điểm ảnh, phần B có kích thước 8x8 điểm ảnh trừ đi phần A, phần C có kích thước 12x12 điểm ảnh trừ đi phần B và A, và phần D là phần còn lại của ô có kích thước 16x16 trừ đi phần C, B và A. Ta có hình minh hoạ các phần A, B, C, D trong mỗi ô vuông 16x16 D C B A n m Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 17 Đặc trọng số vùng A, B, C và D tương ứng là 4, 3, 2, và 1 . Gọi xj là một loại đặc trưng, xj được tính cho một ô kích thước 16x16 như sau: III. Đặc trưng hướng của đường biên: Aûnh để rút đặc trưng này là ảnh chỉ chứa đường biên. Với mỗi ô kích thước 16x16 điểm ảnh, ta rút ra 4 đặc trưng xj (j=1, 2, 3, 4), xj được tính như công thức trên, x1 là số điểm biên có hướng 00 hay(1800), x2 là số điểm biên có hướng 450(hay -1350), x3 là số điểm có hướng 900 (hay –900) và x4 là số điểm có hướng 1350 (hay -450). Như vậy ảnh kí tự sẽ được mô tả dưới dạng : Trong đó n=k*4 , với k là tổng số ô vuông 16x16 xếp chồng lên nhau. PHẦN II CÁC MÔ HÌNH NHẬN DẠNG xj=4xj(A) +3xj(B) +2xj(C) + xj(D) X=(x1, x2, x3, x4…….xn) Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 18 CHƯƠNG I GIỚI THIỆU CÁC MÔ HÌNH PHÂN LỚP, NHẬN DẠNG I. Khái quát tình hình nghiên cứu, ứng dụng lý thuyết nhận dạng: Lý thuyết nhận dạng là một lĩnh vực khoa học mới phát triển nhưng đã đạt được nhiều thành tựu đáng kể về lý luận và ứng dụng trong thực tiễn, chứng tỏ khả năng của máy tính điện tử, có thể mô hình hố được một số chức năng tương đối phức tạp của trí tuệ con người. Cho đến nay cơ sở tốn học của lý thuyết nhận dạng được xây dựng và phát triển đồng thời theo các hướng chính sau đây: - Lý thuyết thống kê nhận dạng. - Lý thuyết cấu trúc về nhận dạng. - Lý thuyết đại số về nhận dạng. Mỗi lý thuyết nói trên đều có mục đích, đối tượng nghiên cứu và phương pháp giải quyết vấn đề khác nhau. Lý thuyết thống kê về nhận dạng là một nhánh phát triển từ thống kê tốn học, sử dụng các phương pháp cơ bản của thống kê tốn để nghiên cứu vấn đề nhận dạng có yếu tố ngẫu nhiên và lượng thông tin đủ lớn. Công trình đầu tiên ở phương Tây theo hướng này là của Sebestyen, mới đây hai nhà tốn học Liên Xô là Vapnhic và Trecvonenkix đã cho ra một tài liệu khá đầy đủ về vấn đề này. Lý thuyết cấu trúc về nhận dạng cho tới nay vẫn chưa được xây dựng hồn chỉnh. Các nghiên cứu theo hướng này tập trung vào nghiên cứu các đối tượng mà có thể coi như tập hợp các đối tượng sơ cấp liên hệ với nhau bởi một số liên kết chuẩn. Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 19 Gần đây, một số nhà tốn học có cố gắng xây dựng cấu trúc đại số cho đối tượng và thuật tốn nhận dạng, những công trình này cho thấy triển vọng của một lý thuyết đại số về nhận dạng đang hình thành ngày càng rõ nét . Do nhu cầu cấp bách phải giải quyết các vấn đề thực tiễn hoạt động sản xuất, nghiên cứu khoa học kỹ thuật hiện đại đặt ra, cùng với các kỹ thuật tin học mới phát triển (đặc biệt là máy tính điện tử ), nhiều chuyên gia thuộc các lĩnh vực hoạt động khác nhau cũng đã đề xuất và sử dụng các mô hình, thuật tốn nhận dạng trên cơ sở thực nghiệm, theo cách tiếp cận heuristic. Song song với việc xây dựng cơ sở lý thuyết nhận dạng, các hoạt động nghiên cứu ứng dụng lý thuyết nhận dạng cũng tiến hành mạnh mẽ và rộng khắp trên nhiều lĩnh vực khác nhau ở nhiều nước trên thế giới. II. Một số khái niệm về nhận dạng: 1.Nhận dạng: Một biểu diễn là giá đỡ (cái mang) thông tin, thường biểu diễn dưới dạng sau: Mỗi xi biểu diễn kết quả của một phép đo. Tập hợp các biểu diễn xác định X được gọi là không gian biểu diễn. Ví dụ không gian vectơ. Giải thích một biểu diễn nghĩa là cho một kết quả chẳng hạn một cái tên. Giả sử: ta có tập hợp các tên là: Không gian giải thích là một tập thoả các luật, thao tác nào đấy. Một định danh là một ánh xạ của không gian biểu diễn vào không gian giải thích. Mục đích nhận dạng là thực hiện ánh xạ này và tìm thuật tốn để thực hiện trên tồn X. Một thuật tốn như vậy gọi là tốn tử nhận dạng. 2. Tập mẫu nhận dạng: Dữ liệu cho bài tốn nhận dạng thường được biểu diễn qua tập mẫu học T với T=(xq, ) là tập các cặp (dữ liệu - tên). 3. Độ đồng dạng và dị dạng: Là hai chỉ số thường dùng để xây dựng trên quan hệ gần thứ tự trên các cặp đặc biệt khoảng cách giữa hai đối tượng là một chỉ số dị dạng thoả mãn 3 tiên đề: - (x, y) 0 , (x, x)=0 - (x, y)= (y, x) - (x, z) (x, y)+ (y, z) 4. Khoảng cách đối tượng:  nxxxxX 321 ,,  p ,, 21       nxxx X ,,: : 21 Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 20 Các hàm đặc trưng quan sát có thể dẫn đến một quan hệ gần thứ tự giữa 1 đối tượng X và các khái niệm Ai, nghĩa là với mọi i, j có thể thiết lập một quan hệ : (X, Ai)  (X, Aj) Quan hệ này thường được thiết lập nhờ một khoảng cách đối tượng, ký hiệu: D(X, A). Nếu muốn phân lớp hoặc định danh X có thể dùng thông tin này. Giả sử Ci là lớp phân hoạch tương ứng với khái niệm đại diện Ai ; X được gán vào Ci nếu D(X, Ai) là nhỏ nhất. III. Một số thuật tốn phân lớp: Có nhiều giải pháp phân lớp, trong thời gian qua em đã tìm hiểu và thử nghiệm một số giải pháp sau: 1. Xếp lớp khoảng cách cực tiểu: Giả thiết là mỗi lớp mẫu được biểu diễn bằng một vectơ đơn (hoặc trung bình). Trong đó Nj là số vectơ mẫu từ lớp j, M là số lớp cần phân biệt và tổng được xác định từ các vectơ này, cách xác định lớp của một vectơ mẫu x chưa biết là chỉ định nó cho lớp đơn điệu gần nhất. Dùng khoảng cách Euclid để xác định độ gần sẽ giảm được tính tốn. Trong đó  a =(aTa )1/2 là dạng Euclid. Sau đó ta chỉ định x cho lớp j nếu Dj(x) là khoảng cách ngắn nhất. Đó là khoảng cách ngắn nhất dùng trong biểu diễn. Ta dễ dàng nhìn thấy nó tương đương với việc đánh giá bằng hàm số Và chỉ định x cho lớp j, nếu dj(x) cho giá trị số lớn nhất. 2. Thuật tốn hàm thế: Phương pháp nhận dạng theo hàm thế được ứng dụng nhiều trong thực tiễn. Việc sử dụng hàm thế được được xuất phát từ nghĩa thế điện trong trường điện từ: Trong không gian có điện tích q tại A thì xung quanh nó có điện trường theo mọi phía. Tại điểm M của không gian ta có thế gây ra bởi q là: a : hằng số q: độ lớn điện tích q r: khoảng cách từ M tới q Các dạng hàm thế thường dùng trong thuật tốn nhận dạng: Mjx N m jxj j ,2,1 1      MjmxxD jj ,2,1;    Mjmmmxxd jTjjTj ,2,12 1    2. r qaM  Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 21 Ở đây , C1, C2 là các hằng số cho trước. (S, S’) là khoảng cách S và S’ (=0, 1, 2..) Cách tính thế đối với mỗi lớp: mj: số mẫu của Kj St: mẫu thuộc Kj Ta có luật quyết định: Chú ý : Việc tính thế đối với mỗi lớp, có thể bổ sung trọng số mẫu (St) : Nhận xét: Nếu chọn  là hàm khoảng cách Euclid thì giải thuật hàm thế này gần giống với cách xếp lớp theo khoảng cách cực tiểu. 3. Phương pháp LDA (Linear Discriminant Analysis): Phương pháp LDA cho trường hợp phân biệt 2 lớp, LDA sẽ tìm một phương chiếu mà phân biệt tốt nhất các mẫu thuộc hai lớp khác nhau trong tập mẫu. Giả sử ta có một tập gồm n mẫu học X bao gồm các vectơ cột d chiều: Trong đó n1 mẫu thuộc về lớp C1 và nằm trong tập con X1, n2 mẫu thuộc về lớp C2 và nằm trong tập con X2. Giả sử ta có một vectơ d chiều w, tích vô hướng y=wTx biểu diễn hình chiếu của vectơ x lên phương w. Ta sẽ tìm một phương chiếu w nhằm tối ưu hố độ phân biệt giữa các mẫu thuộc 2 lớp C1 và C2. Điều này tương đương với việc giảm số chiều của vectơ đặc trưng xuống còn 1 chiều. Ta gọi mi, i=1, 2 là trị trung bình của các mẫu tương ứng với 2 lớp C1 và C2.        '21 ' ,' ,. 1, , ' SSCC SS eSS ss               j K t S t j j SSm KS ,1,     K S, max arg   jKS, neáujKS      t KS t j j SSSm KS jt  .,1,      nixxxx Tdiiii  1,, 21     iXxi i xn m 1 Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 22 || ~ 2 ~ 1 mm  Và tương ứng là trung bình của các mẫu được chiếu lên phương w: Trong đó y là hình chiếu của x lên w. Yi là tập các hình chiếu của các x  Xi lên w. Ta có thể xem là một độ đo cho tính phân biệt giữa hai tập Y1 và Y2 . Tuy nhiên để có được sự phân biệt tốt giữa hai tập khi chiếu lên phương w, ta cần có độ sai khác giữa hai trị trung bình này khá lớn hơn so với độ lệch chuẩn nội tại của mỗi tập ( có thể xem như độ rộng của đám mây các mẫu). Thay vì sử dụng phương sai của mỗi tập ta sẽ sử dụng một độ đo khác, gọi là độ rải (scatter) cho các hình chiếu của các mẫu thuộc lớp Ci như sau: Phương pháp LDA sẽ tìm giá trị w để cực đại hố hàm tiêu chuẩn sau đây: Để thấy J(w) là một hàm theo w ta định nghĩa các ma trận SB và Sw như sau: SW được gọi là ma trận rải nội lớp (within-class scatter matrix) SB được gọi là ma trận rải liên hợp (between-class scatter matrix) Ta có: Nên Tương tự ta cũng có: im ~ i T Xx T iYyi i mwxw n y n m ii    11~ 2~~          iYy ii mys 2~ 2 2~ 1 2 2 ~ 1 ~ ||)( ss mmwJ        2 1 ))(( i Xx T iiW i mxmxS T B mmmmS ))(( 2121  2 is =    iXx i TT mwxw 2)( =    iXx T ii T wmxmxw ))(( 2 2 1 2s s  = w TSWw Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 23 Do đó: Để xác định w sao cho J(w) cực đại ta cho đạo hàm riêng J(w) theo w bằng 0 kết quả ta sẽ được: Với  là trị riêng, giải bài tốn tìm trị riêng ta sẽ có: Đây là kết quả tìm được của phương pháp LDA đối với trường hợp chỉ có 2 lớp. Sau khi đã tìm được w, mỗi vectơ x cần nhận dạng sẽ được xử lý như sau: lấy x trừ đi trung bình của mẫu học rồi chiếu lên phương w ta được một giá trị vô hướng, tính khoảng cách từ giá trị vô hướng này trên im ~ của mỗi lớp này chia cho độ lệch chuẩn 2~ i ta được một độ đo khoảng cách từ x đến các cụm ứng với mỗi lớp. i=1..2 x sẽ được gán vào lớp ứng với cụm gần nhất. Để phân biệt được n lớp ta xây dựng n bộ phân loại 2 lớp theo phương pháp nêu trên. Mỗi bộ phân loại sẽ phân biệt một lớp với n-1 lớp còn lại. Nếu một vectơ đầu vào được xếp vào cả hai lớp thì ta sẽ sử dụng khoảng cách di nêu trên để quyết định nó thuộc vào lớp nào. Nếu một vectơ không được xếp vào lớp nào thì coi như không nhận dạng được. Phần tiếp theo xin trình bày cách phân lớp dựa trên mô hình mạng nơron lan truyền ngược, em dành một chương riêng để giới thiệu về mô hình này. 2 1 2( )m m  = w TSBw. J(w) = wSw wSw W T B T . SB w = SW w )( 21 1 mmSw W   1 ( ) i i x m w md       Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 24 CHƯƠNG II PHÂN LỚP DỰA TRÊN MẠNG NƠRON LAN TRUYỀN NGƯỢC Sơ lược về mạng nơron MLP (Multi-Layer Perception ) với thuật tốn lan truyền ngược: I. Giới thiệu: Xét về mặt cấu trúc, MLP có cấu trúc phân lớp. Các cung được nối từ một nút ở lớp này đến các nút ở lớp kế tiếp. Hai nút trong cùng một lớp thì không kết nối với nhau. Mỗi nút trong một lớp nhận giá trị từ các nút ở lớp liền trước, tổng hợp lại theo trọng số của cung kết nối và chuyển giá trị kết xuất của nó cho các nút ở lớp liền sau. Lớp đầu tiên nhận giá trị từ bên ngồi vào và được gọi là lớp nhập (input). Các nút trong lớp nhập được gọi là nút nhập. Lớp cuối cùng sẽ xuất ra kết quả của mạng và được gọi là lớp xuất (output). Các nút trong lớp xuất được gọi là nút xuất. Các lớp còn lại được gọi là lớp ẩn và các nút tương ứng được gọi là nút ẩn. Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 25 Hình minh hoạ mô hình mạng nơron 4 lớp:1 lớp nhập, 2lớp ẩn và một lớp xuất . Quá trình nhận dạ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. Cũng như vậy, MLP thực chất là một hàm ánh xạ một vectơ đầu vào x thành một vectơ đầu ra z. Hàm này có đặc tính sau: 1. Nó là hàm phi tuyến (nonlinear) . 2. Nó có tính ổn định (stable). Nghĩa là nếu một giá trị x0 được ánh xạ thành một giá trị z0 thì một giá trị x1 “gần” với x0 sẽ được ánh xạ thành một giá trị y1 gần với y0. Hay ta có thể nói, sai số nhỏ ánh xạ thành sai số nhỏ. Mạng nơron cũng có thể ánh xạ một giá trị x2 xa x0 thành một giá trị y2 gần với y0 (ánh xạ nhiều một). Thực tế mạng nơron là một bộ máy nội suy và ngoại suy phi tuyến. Một mạng chỉ với một lớp ẩn là đã có thể xấp xỉ bất cứ một hàm phi tuyến nào thông qua một số mẫu trong tập mẫu. Để đạt được điều này, ta cần luyện mạng bằng cách thay đổi các trọng số để ánh xạ từ các giá trị trong tập mẫu đến các giá trị đích mong muốn. Quá trình luyện mạng này cần có tập các vectơ mẫu đầu vào và đầu ra mong muốn tương ứng. Do đó, quá trình học này là quá trình học có giám sát. II. Hoạt động: Mạng nơron MLP 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 tốn học để mạng có thể xấp xỉ được một hàm mong muốn nào đó. Thuật tốn lan truyền ngược là một thuật tốn hiệu quả cho quá trình học của MLP. Tiếp theo đây em xin trình bày chi tiết hơn về hai trạng thái này của mạng. 1. Trạng thái ánh xạ: Như đã nói, ở trạng thái ánh xạ, mỗi vectơ đầu vào x sẽ được ánh xạ thành một vectơ kết quả z. Quá trình này được thực hiện như sau: Đầu tiên vectơ mẫu x sẽ được đưa vào lớp nhập. Mỗi nơron trong lớp nhập sẽ mang giá trị của một thành phần của x. Các nút nhập sẽ không tính tốn gì cả mà gửi trực tiếp giá trị của nó đến các nơron ở lớp tiếp theo. Tại mỗi nơron của các lớp tiếp theo, một thao tác giống nhau sẽ được thực hiện. Đầu tiên nó sẽ tính tổng trọng hố của tất cả các giá trị được gửi tới. Sau đó một hàm truyền sẽ được áp dụng trên tổng trọng hố này để cho giá trị xuất của nút này. Hàm truyền có tác dụng nén giá trị của tổng trọng hố vào một miền giới hạn nào đó. Giá trị này được Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 26 truyền cho các nơron ở lớp kế tiếp. Cứ thế thông tin được lan truyền cho đến lớp xuất của mạng. Để đơn giản ta khảo sát mạng gồm 3 lớp: 1 lớp vào, 1 lớp ẩn và 1 lớp xuất. Thực tế cũng chỉ cần mạng 3 lớp là đủ để xấp xỉ các loại hàm. Đối với nút ẩn ta có: Tổng trọng gửi tới nút j là: Kết xuất của mạng có J nút ẩn là: Trong đó I là số nút nhập xi, aij là các trọng từ input i đến nút ẩn j và a0j là trọng ngưỡng của nút ẩn j, g(x) là hàm truyền. Đối với mạng K nút xuất ta có: Tổng trọng gửi tới nút xuất k là: Kết xuất của mạng: Trong đó J là số nút ẩn với các kết xuất yj, bjk là các trọng trên các cung liên kết từ nút ẩn j đến nút xuất thứ k, còn b0k là trọng ngưỡng của nút xuất thứ k, g(vk) là hàm truyền theo k. Ta có sơ đồ thể hiện các thao tác được thực hiện tại mỗi nơron. Một số hàm truyền thường được sử dụng là: - Hàm sigmoid (hay hàm logistic) được xác định bởi:    I i iijjj xaau 1 0 Jjugy jj ,...1)(     J j jjkkk ybbv 1 0 Kkvgz kk ,..1)(  axe xf   1 1)( Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 27 Hình vẽ đồ thị hàm logistic (a=1). Miền giá trị của hàm là(0, 1). - Hàm tanh (tan- hyperbol) Đồ thị hàm tanh. Miền giá trị của hàm là (-1, 1). Hàm này có miền giá trị tương ứng là (0, 1) và (-1, 1). Việc sử dụng hàm logistic (a=1) hay hàm tanh thực ra là tương đương với nhau vì chúng liên hệ tuyến tính với nhau. Việc sử dụng các hàm truyền khác nhau có liên hệ với các khoảng giá trị khác nhau của trọng số. (Thực tế cho thấy, hàm tanh thường cho tốc độ hội tụ nhanh hơn trong quá trình học ). Các hàm truyền có thể được áp dụng vào các nút xuất hoặc không tuỳ vào mục đích ánh xạ của mạng. Nếu ta cần có một số giới hạn nhất định đối với đầu ra, ta sẽ áp dụng một hàm truyền thích hợp cho các nút xuất. Khi mạng nơron được ứng dụng cho nhận dạng thì quá trình nhận dạng chính là quá trình ánh xạ của mạng nơron. 2. Trạng thái học: Xét mạng MLP có một lớp ẩn với thuật tốn lan truyền ngược. -6 -4 -2 2 4 6 0.2 0.4 0.6 0.8 1 xx xx ee eexf     )( -4 -2 2 4 -1 -0.5 0.5 1 Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 28 Thuật tốn lan truyền ngược là thuật tốn hữu hiệu cho quá trình học của MLP. Thuật tốn này sẽ cập nhật trọng số dựa trên một hàm lỗi E giữa kết xuất của mạng với giá trị đích. Mục đích của việc học có giám sát bằng MLP là cực tiểu hố hàm lỗi này. Kỹ thuật cơ bản để cực tiểu hố hàm lỗi là phương pháp giảm gradient. Mặc dù phương pháp này có thể dẫn đến một cực tiểu cục bộ, nhưng nó được áp dụng rộng rãi vì tính đơn giản của nó. Thực tế cũng cho thấy trong hầu hết trường hợp phương pháp giảm gradient đều cho kết quả chấp nhận được. Quá trình học của mạng MLP theo thuật tố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 sẽ dừng khi mạng đã đạt được một độ lỗi nhỏ nhất định. a. Phương pháp giảm gradient: Phương pháp giảm gradient gồm các bước chính 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 (có thể là hàm lỗi cực tiểu địa phương). b. Cập nhật trọng số theo phương pháp giảm gradient: Phương pháp cập nhật trong số theo hướng giảm gradient sẽ dựa trên đạo hàm riêng phần của hàm lỗi E đối với trọng số đang xét theo công thức sau: trong đó: t là chỉ số của lần cập nhật trọng số hiện tại.  được gọi là hệ số học (learning rate). w là một trọng số bất kì trong mạng: aij hoặc bij Công thức trên có thể diễn dịch như sau: cập nhật lại trọng số theo hướng ngược hướng của gradient với độ dài vectơ dịch chuyển phụ thuộc vào  và độ lớn của vectơ đạo hàm. Nếu trọng số được cập nhật theo hướng ngược với gradient một độ dịch chuyển vừa phải, thì giá trị của hàm lỗi sẽ giảm đi so với trước khi cập nhật. Giá trị của  có ảnh hưởng lớn đến tốc độ hội tụ của thuật tốn. Nếu  lớn thì độ dịch chuyển lớn, kết xuất của mạng có thể dao động rất thất thường (vì có thể nhảy qua điểm cực tiểu) và thuật tốn khó hội tụ. Nếu  nhỏ, ta phải cần rất nhiều bước lặp để đi đến được vị trí cực tiểu của hàm lỗi. c. Quy tắc tính đạo hàm lỗi: )()()1( t w Etwtw ij ijij     Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 29 Sai số trung bình bình phương thường được sử dụng để đo lường sự trùng khớp giữa ánh xạ ( ký hiệu NN) cần xây dựng với hàm đích cho trước (qua tập mẫu). Cho tập mẫu: =(Xk, Zk) =(xk1, …,xkM;zk1,…,zkN ); xki, zkj  R ; i= 1,…,M; j=1,…,N; k=1,…,K, gọi Tk= NN(Xk)=(tk1,…,tkN) thì sai số trung bình bình phương sẽ là: Đạo hàm hàm lỗi có thể được tính dựa vào quy tắc chuỗi như sau: Ta xét từng trường hợp cụ thể: Trọng số nút xuất: Ta có chuỗi tính đạo hàm hàm lỗi theo trọng số giữa lớp ẩn và lớp xuất: Một nút xuất không ảnh hưởng gì đến sai số của các nút xuất khác trong lớp xuất. Để đơn giản trong công thức ta bỏ qua chỉ số của các nút xuất, nếu nút xuất đang xét có giá trị thực là z và giá trị đúng của nút đó là t, thì sai số bình phương là: Từ đó ta có: Mặt khác độ dốc hàm logistic được tính như sau: Tính số hạng thứ 3, v/b trong công thức E/b Ta có: Xét với b0 ta có: v/b0 =1 Với trọng số bj, ta có: v/bj =yj Đặt: KN tz E N n K k knkn . )( 2 1 1 1 2     w w w w w E w E n           2 1 1 b v v z z E b E          2)( 2 1 tzE  tz z E    )1()( ' zz v zvg        J j jj ybbv 1 0 v z z Ep      Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 30 Ta có: p=(z-t)z(1-z) Như vậy: Xét trọng số nút ẩn: Ta có đạo hàm của hàm lỗi đối với các trọng số của một nút ẩn: Các nút ẩn tự chúng không tạo lỗi nhưng chúng góp phần tác động vào lỗi của các nút xuất. Những tác động này cũng xác định theo luật chuỗi: (trong công thức này chỉ số j đã được bỏ đi vì chỉ có một nút ẩn tham gia) Công thức trên cho thấy ảnh hưởng của nút ẩn vào hàm E là một tổng theo tất cả các nút xuất (k=1…K) của tích ba số hạng. Hai số hạng đầu trong tích đó có ý nghĩa tương tự như phần trên. Ở trên ta đặt tích này là p. Lượng p này lan truyền ngược từ nút xuất đến nút ẩn. Nếu ta cho p một chỉ số cho biết nó thuộc về nút xuất nào, ta có thể viết phương trình trên lại như sau: Xét số hạng vk/ y ta có: Như vậy: Ta tiếp tục xét y/u trong chuỗi tính E/a Đặt :         Jjpy jp b E jj 0 a u u y y E a E          y v v z z E y E k k k K k k           1        K k k k y v p y E 1 k k b y v         K k kk bpy E 1 )1( yy u y    u y y Eq      Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 31 Ta có: Và cuối cùng u/a, trong chuỗi tính E/a chính là thay đổi của u đối với thay đổi của một trọng số. Nó phụ thuộc vào loại trọng số. Đối với trọng ngưỡng a0, ta có: Với các trọïng trên cung nối trực tiếp ai, i>0 ta có: Tóm lại: 3. Một vài kỹ thuật luyện mạng: a. Học theo lô: Như đã nói trong phần trước, trọng số của mạng được cập nhật khi tất cả các mẫu học đều đã được đưa vào mạng (học theo bước học). Đây là một kỹ thuật học theo lô. Trong cách học thông thường của thuật tốn lan truyền ngược, mỗi khi ta đưa vào mạng một mẫu học đạo hàm hàm lỗi được tính và trọng số được cập nhật ngay, sau đó mẫu học tiếp theo được đưa vào mạng và quá trình trên được lặp lại cho từng mẫu học. Mỗi bước trong quá trình trên gọi là một bước lặp. Khi tất cả các mẫu trong tập học đã được đưa vào mạng, ta hồn tất bước học. Cách cập nhật này có thể dẫn đến trường hợp ở một bước lặp p trọng số được cập nhật sao cho giảm E(p), nhưng ở một bước lặp q khác, trọng số lại được cập nhật sao cho tăng E(q). Kết quả là một bước học sẽ chứa đựng sự tự mâu thuẫn trong nó, cụ thể sẽ có một bước lặp làm ngược lại với những kết quả đã đạt được ở những bước trước một cách cục bộ tại một trọng số. Điều này làm cho quá trình học nhiễu loạn và kém hiệu quả. Cách học theo bước giúp ta tránh được hiện tượng này. Trong phương pháp này trọng số sẽ được cập nhật sau mỗi bước học. Nghĩa là tất cả các mẫu học sẽ được đưa vào mạng và các đạo hàm riêng phần ứng với mỗi trọng số và mỗi mẫu học sẽ được tính tốn. Sau đó đạo hàm riêng phần ứng với mỗi trọng số sẽ được tính bằng tổng tất cả các đạo hàm riêng phần ứng với trọng số đó trên tất cả các mẫu học. )1( 1 yybpq K k kk          1 0    a u i i x a u            0 0 iqx iq a E ii Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 32 Phương pháp học theo bước học đã được ứng dụng rộng rãi trong các hệ thống xử lý lớn nhờ khả năng áp dụng việc xử lý song song cho việc tính tốn các đạo hàm riêng phần. b. Ngăn chặn quá khớp: Quá khớp: Là trường hợp mạng thuộc hết dữ liệu học ( kể cả nhiễu), lúc đó nó sẽ trả lời chính xác những gì nó được học còn những gì nó không được học thì không quan tâm. Nghĩa là mạng không có khả năng tổng quát hố, mà tổng quát lại là điều ta cần khi sử dụng mạng. Cách khắc phục: Có nhiều cách khắc phục tình trạng này song cách đơn giản nhất là: Chia mẫu thành tập luyện và tập kiểm tra. Luyện mạng với tập mẫu luyện, nhưng định kỳ ngừng luyện để đánh giá sai số bằng tập mẫu kiểm tra. Mỗi lần ngừng lại để đánh giá sai số trên mẫu kiểm tra, cần lưu lại các trọng số. Khi sai số trên mẫu kiểm tra đi lên, thì quá khớp đã bắt đầu. Do vậy, ta ngừng luyện, trở về trọng sinh lỗi thấp nhất trên mẫu kiểm tra. PHẦN III KẾT QUẢ THỬ NGHIỆM Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 33 CHƯƠNG I MINH HỌA ỨNG DỤNG GIẢI THUẬT TÁCH THÀNH PHẦN LIÊN THÔNG TRONG BÀI TỐN NHẬN DẠNG ẢNH VĂN BẢN Trước khi xây dựng chương trình nhận dạng kí tự viết tay, em xin giới thiệu một ứng dụng có liên quan đến nhận dạng kí tự, đó là ứng dụng nhận dạng ảnh văn bản. Với cơ sở lí thuyết vừa nêu ta hồn tồn có thể xây dựng được ứng dụng này. I. Nhận dạng một văn bản: Giả thiết coi đầu vào chỉ là một ảnh văn bản đơn giản: chỉ có một cột và gồm các kí tự ( tuy nhiên không nhất thiết chỉ chứa kí tự vì có thể hồn tồn loại bỏ các liên thông là hình ảnh nếu căn cứ vào kích thước của chúng). Ta có sơ đồ nhận dạng như sau: Tách liên thông Khử liên thông đặc biệt Xác định hàng liên thông Sửa lỗi xác định hàng Tách liên thông dính Nhận dạng các liên thông Aûnh văn bản đơn Tập các liên thông ( còn liên thông đặc biệt & liên thông dính) Tập liên thông đã được xử lý Các liên thông đã được sắp xếp theo hàng Trật tự các liên thông trên hàng được xếp lại Vị trí các liên thông đã được xếp đúng Văn bản có thể hiệu chỉnh Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 34 II. Minh hoạ chương trình: Chương trình sau đây minh hoạ cho nhận dạng văn bản chứa kí tự font Vni- Times, size 12.Việc nhận dạng từng kí tự được thực hiện như sau: Kí tự được chuẩn hố vào lưới ô vuông kích thước 56x48 điểm ảnh. Cách xác định đặc trưng của font chữ in như sau: Chia khung kí tự thành nhiều ô vuông nhỏ kích thước 8x8. Trên mỗi ô vuông nhỏ ta xác định 4 đặc trưng gồm: - 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. Như vậy với một ảnh kí tự ta sẽ có được 7x6x4=169 đặc trưng, X=(x1, x2, …xn) n=169. Giải thuật nhận dạng trong chương trình dựa trên ý tưở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 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 vectơ. Chương trình minh hoạ cho nhận dạng văn bản tiếng Việt không chứa kí tự đặc biệt, kết quả cho thấy việc tách chữ và xác định hàng tương đối chính xác, độ chính xác nhận dạng khoảng 93-95%. Thực hiện như sau: Nạp ảnh văn bản cần nhận dạng vào, sau đó nhấn nút nhận dạng để xem kết quả. Ta có hình minh hoạ kết quả nhận dạng: Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 35 CHƯƠNG II CHƯƠNG TRÌNH NHẬN DẠNG KÍ TỰ VIẾT TAY I. Giới thiệu chương trình: Chương trình nhận dạng các kí tự viết tay không trực tuyến, ảnh kí tự nhận dạng được thu nhận qua máy quét hoặc viết trực tiếp vào vùng nhận dạng. Aûnh có thể chứa nhiều kí tự, được viết trên nhiều hàng khác nhau. Tuỳ vào mục đích ứng dụng cần phát triển mà ta xây dựng tập mẫu cho mỗi ứng dụng. Bước đầu thử nghiệm em xây dựng bộ nhận dạng cho 2 lớp kí tự gồm: kí tự là chữ cái không có dấu và kí tự là chữ số. 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. Do một số kí tự khi viết hoa hay viết thường đều giống nhau, chỉ khác nhau về mặt kích thước, do đó đối với những kí tự này ta có thể xét thêm kích thước của chữ, nếu kích thước lớn hơn một ngưỡng nhất định thì coi là chữ hoa, ngược lại là chữ thường. Về mặt kí tự số ta sẽ không phân biệt được số “0” và kí tự chữ “O”, do đó chương trình tách riêng nhận dạng kí tự chữ và nhận dạng số. Chương trình được cài đặt bằng công cụ lập trình Borland Delphi 5.0 chạy trên môi trường Windows. 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 hố  tách các liên thông chữ  chỉnh nghiêng  chuẩn hố 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. Với ảnh đầu vào là ảnh xám, định dạng file là *.bmp, được scan với độ phân giải 300 dpi, tỉ lệ 100%. Ta có quy trình nhận dạng được chia làm các giai đoạn như sau : 1. Tiền xử lí: - Lọc ảnh: Lọc ảnh nhằm giảm bớt nhiễu bằng giải thuật lọc trung bình. - Nhị phân ảnh: Dựa vào giải thuật Otsu đã trình bày tiến hành phân ngưỡng, tạo ra ảnh nhị phân chứa giá trị 0 và 1: 0 tượng trưng cho điểm thuộc nền, 1 tượng trưng cho điểm thuộc đối tượng. Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 36 - Tách liên thông: Dùng giải thuật tách liên thông để tách các kí tự ra khỏi ảnh. - Chỉnh nghiêng và chuẩn kích thước: Tiến hành chỉnh nghiêng và chuẩn hố kí tự về kích thước chuẩn là 80x56. 2. Trích chọn đặc trưng: Có thể thấy rằng cấu trúc một kí tự có thể mô tả một cách chính xác qua các đường biên của miền liên thông. Do đó cấu trúc hố đường biên của một miền liên thông được xác định như sau: Bước 1: Phát hiện biên của kí tự Bước 2: Mã hố đường biên kí tự bằng mã xích. Bước 3: Tiến hành chia kí tự ra nhiều ô nhỏ và xác định đặc trưng của kí tự theo mô tả lí thuyết đã trình bày ở phần II, chương III. Kết quả ta có véctơ đặc trưng của kí tự là: X=(x1, x2,…xn) với n=216 3. Bộ phân lớp: Qua thử nghiệm các bộ phân lớp đã trình bày cho thấy: phân lớp kí tự bằng mạng nơron cho kết quả vượt trội hơn. Mạng nơron được thiết kế để nhận dạng là mạng 2 lớp:1 lớp vào và một lớp ra, với giải thuật lan truyền ngược và kỹ thuật giảm gradient, chọn 08.0 . Véctơ X=(x1, x2, ... xn) trong quá trình huấn luyện và nhận dạng được chuẩn hố sao cho 1X , nghĩa là các thành phần của véctơ X được tính lại như sau: Mạng thứ nhất được thử nghiệm trên 2366 mẫu học đối với lớp kí tự chữ. Mạng thứ hai thử nghiệm trên 1000 mẫu học đối với kí tự số. Mạng thứ nhất luyện sau 30.000 học kì. Mạng thứ hai luyện sau 10.000 học kì. Kết quả: Sau thời gian học mạng thứ nhất và mạng thứ hai phân biệt gần hồn tồn các mẫu đã học, đặc biệt khả năng tổng quát của mạng rất cao. Bảng kết quả thử nghiệm trên một số người: Người thứ 1: Mẫu số Mẫu chữ: Mẫu số 0 1 2 3 4 5 6 7 8 9 Số mẫu thử 176 102 113 116 96 107 140 161 143 121 Số mẫu sai 0 0 0 0 0 0 0 0 3 1 Tỷ lệ đúng 100% 100% 100% 100% 100% 100% 100% 100% 97,9% 99,1% Kí tự Số mẫu Số mẫu lỗi Độ chính xác A 109 2 98.17% B 116 3 97.41% C 132 2 98.48% D 99 0 100% E 114 0 100% ni X xx ii ..1 Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 37 Kí tự Số mẫu Số mẫu lỗi Độ chính xác a 148 0 100% b 133 6 95.49% d 122 0 100% e 100 17 83% f 105 0 100% g 113 4 96.46% h 127 0 100% i 159 13 91.82 j 161 1 99.38 k 116 0 100% l 100 19 81% m 136 0 100% n 158 20 87.34% q 142 0 100% r 139 6 97.79% Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 38 Người thứ 2: Mẫu số: Mẫu chữ: Kí tự Số mẫu Số mẫu lỗi Độ chính xác A 124 6 95.16% B 120 6 95% C 104 2 98.08% D 113 0 100% E 116 2 98.28% F 120 1 99.17% G 101 0 100% H 109 0 100% I 110 10 90.91% J 127 4 96.85% K 103 7 93.2% L 102 2 98.04% M 118 0 100% Mẫu số 0 1 2 3 4 5 6 7 8 9 Số mẫu thử 105 100 92 97 100 97 104 100 101 100 Số mẫu sai 0 0 0 0 0 0 1 1 4 0 Tỷ lệ đúng 100% 100% 100% 100% 100% 100% 99% 99% 96% 100% Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 39 Kí tự Số mẫu Số mẫu lỗi Độ chính xác a 102 0 100% b 113 13 88.5% d 98 0 100% e 113 19 83.19% f 108 6 94.44% g 110 10 90.91% h 100 9 91% i 115 29 74.78% j 120 3 97.5% k 102 14 86.27 l 134 34 74.63% m 102 0 100% n 103 18 82.52% q 100 1 99% r 100 4 94% s 107 11 90.6% t 130 13 90% v 100 15 85% x 100 14 86% y 103 0 100% Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 40 III. Minh hoạ một số kết quả: Nhận dạng kí tự số : Aûnh viết bằng mouse : Kết quả: Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 41 Aûnh kí tự viết trên giấy : Kết quả: Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 42 Nhận dạng kí tự chữ: Aûnh viết bằng mouse: Kết quả: Aûnh nhận dạng: Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 43 Kết quả: Aûnh kí tự viết trên giấy: Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 44 Kết quả: Aûnh kí tự: Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 45 Kết quả: CHƯƠNG III ỨNG DỤNG XỬ LÍ PHIẾU ĐĂNG KÍ MÔN HỌC I. Giới thiệu: Phiếu đăng kí môn học dùng ở phòng đào tạo Trường Đại Học Thuỷ Sản Nha Trang, là một biểu mẫu nhằm mục đích thu nhận thông tin đăng kí môn học của sinh viên, bao gồm các môn học được sinh viên đăng kí học và các môn sinh viên hủy bỏ. Với số lượng sinh viên ngày càng tăng, chương trình xử lí phiếu đăng kí môn học này nhằm giúp việc đăng kí môn học được nhanh chóng, tiết kiệm thời gian và công sức nhập dữ liệu cho nhân viên phòng đào tạo. Mẫu phiếu có dạng như sau: Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 46 Yêu cầu xử lí: Từ phiếu đã điền đầy đủ thông tin, chương trình sẽ lấy ra các thông tin sau: - Mã số sinh viên (MSSV). - Mã các môn học huỷ bỏ, mã lớp sinh viên sẽ huỷ bỏ môn này. - Mã các môn học đăng kí học lại, mã lớp sinh viên sẽ học lại các môn này. - Mã các môn học đăng kí học vượt, mã lớp sinh viên sẽ học vượt các môn này. Như vậy từ các thông tin trên ta sẽ xác định được yêu cầu đăng kí môn học của mỗi sinh viên. Ta có sơ đồ quy trình thực hiện của hệ thống đăng kí môn học tự động như sau: Phiếu đăng kí môn học Thiết bị thu nhận ảnh Xử lí, nhận dạng ảnh thu được CSDL Lưu trữ CSDL Kiểm tra Chỉnh sửa dữ liệu file ảnh Kết quả Dữ liệu đã kiểm tra Kết quả Y/c kiểm tra K/q kiểm tra Tìm kiếm K/q tìm kiếm Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 47 Hình vẽ: Sơ đồ mô hình của hệ xử lí phiếu đăng kí môn học tự động Trên đây là mô hình tổng thể cho hệ thống vừa nêu, tuy nhiên để áp dụng vào thực tế cần phải có một hệ thống quản lí sinh viên và các môn học. Việc kiểm tra tính đúng đắn của dữ liệu và lưu trữ dữ liệu sẽ do hệ thống này đảm nhiệm, mục tiêu của thử nghiệm này là thực hiện công đoạn: xử lí và nhận dạng ảnh thu được để cho ra kết quả có thể chỉnh sửa. II. Thực hiện chương trình: Chương trình thử nghiệm xử lí thông tin phiếu đăng kí môn học có nhiệm vụ lọc ra các thông tin ghi trong phiếu nêu trên. Qua khảo sát cho thấy, kí tự ghi trong phiếu gồm: Kí tự số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Kí tự chữ ( yêu cầu là chữ viết hoa ) gồm một số kí tự: B, C, D ,H , K, L , P, S, T, N,... Ví dụ: Mã số sinh viên: 8D15014 Mã số môn học: 10221 (tốn cao cấp A3) Mã lớp MH: TH40, NT41... Ta có chương trình thực hiện như sau: 1. Định dạng và lấy thông tin từ biểu mẫu: Aûnh phiếu đăng kí môn học bước đầu thử nghiệm được lưu dạng file *.bmp, scan với độ phân giải 300 dpi và kích thước 100%. Aûnh quét vào cho phép độ nghiêng vừa phải từ 10 – 50. Ta có quy trình định dạng và lấy thông tin từ biểu mẫu được thực hiện như sau: Bước 1: Tìm kiếm dấu hiệu định vị biểu mẫu. Bước 2: Loại bỏ các vùng thông tin in trước bằng cách so khớp với mặt nạ mẫu. Bước 3: Lấy thông tin vùng dữ liệu. a. Tìm kiếm dấu hiệu định vị biểu mẫu: Dấu hiệu định vị biểu mẫu là một điểm chuẩn trong biểu mẫu, dựa vào điểm chuẩn này ta sẽ xác định toạ độ của các vùng dữ liệu còn lại. Aûnh phiếu đăng kí môn học Kết quả nhận dạng Aûnh từng kí tự Mẫu vectơ đặc trưng Định dạng và lấy thông tin từ biểu mẫu Xác định véctơ đặc trưng của kí tự Nhận dạng véctơ đặc trưng Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 48 Toạ độ điểm chuẩn được sử dụng trong chương trình là giao điểm giữa lề trái biểu mẫu và đường thẳng ngang qua tiêu đề của biểu mẫu. Việc xác định lề trái và đường thẳng ngang qua tiêu đề của biểu mẫu dựa vào sự biến thiên năng lượng mức xám của biểu mẫu: Nếu ta kiểm tra biểu mẫu từ trái sang phải thì lề trái của biểu mẫu chính là vùng có mức năng lượng thay đổi cao đầu tiên. Tương tự nếu xét theo hướng ngang từ đầu biểu mẫu đến cuối biểu mẫu thì tiêu đề ngang của biểu mẫu là vùng có mức năng lượng thay đổi cao đầu tiên. Ta có hình minh hoạ: Hình minh hoạ xác định điểm chuẩn trong biểu mẫu. Điểm chuẩn Lề trái Lề tiêu đề Vùng dữ liệu Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 49 b. Loại bỏ thông tin in trước bằng cách so khớp với mặt nạ mẫu: Căn cứ vào điểm chuẩn ta định vị toạ độ từng ô của của vùng dữ liệu gồm: các ô chứa mã số sinh viên, các ô chứa thông tin đăng kí môn học. Tọa độ các ô này đã được xác định trước so với điểm chuẩn vừa nêu, ta xem các ô đó như một mặt nạ mẫu. c. Lấy thông tin vùng dữ liệu: Aûnh kí tự trong mỗi ô vuông nhỏ lần lượt được cắt ra, chuẩn bị xử lý để xác định véctơ đặc trưng. Chú ý cần phải loại bỏ nhiễu gây ra bởi các đường khung xung quanh kí tự trước khi đưa vào bộ xử lý lấy đặc trưng của kí tự. Cách giải quyết: ta có thế căn cứ vào mật độ phân bố của các điểm đen trên đường chạy lân cận của 4 cạnh khung kí tự, tỉ số phân bố số điểm đen và điểm trắng trên mỗi đường chạy này đểphân biệt đâu là nhiễu do khung xung quanh kí tự gây ra. Ví dụ: Hình minh hoạ kí tự bị nhiễu do cắt phạm đường khung. Sau khi loại bỏ hiện tượng nhiễu này, ảnh kí tự được đưa vào bộ xác định véctơ đặc trưng để xử lý và rút ra vectơ đặc trưng cho kí tự cần nhận dạng. 2. Xác định vectơ đặc trưng của kí tự: Trươc tiên, ảnh kí tự được lọc nhiễu, chỉnh nghiêng, và chuẩn hố về kích thước chuẩn 80x56. Sau đó, tiến hành xác định véctơ đặc trưng kí tự như trong chương trình thử nghiệm nhận dạng chữ viết tay vừa nêu, dựa trên cơ sở lý thuyết đã trình bày ở phần II, chương III. Như vậy với mỗi kí tự ta sẽ xác định được một véctơ đặc trưng mô tả đường biên có dạng sau: X=(x1, x2, ...xn), n=216. Trong đó n là số chiều của véctơ X, hay còn là số đặc trưng của kí tự. 3. Nhận dạng véctơ đặc trưng: Chương trình sử dụng mạng nơron trong phần ứng dụng nhận dạng chữ viết tay để tiến hành phân lớp các kí tự. Nhiễu do cắt phạm khung ô vuông của biểu mẫu Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 50 Do đặc điểm dữ liệu cần phân lớp chỉ gồm các kí tự số, và một số kí tự viết hoa, nên số lớp kí tự được thu nhỏ lại, điều này nâng cao khả năng nhận biết và độ chính xác của mạng. Cụ thể mạng huấn luyện cho 20 lớp kí tự gồm : Kí tự số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Kí tự chữ hoa: B, C, D, H, K, L, N, P, S, T. Mạng được huấn luyện sau 50.000 học kì với tập mẫu gồm 2051 véctơ đặc trưng của kí tự, hệ số 08.0 . Kết quả khả năng phân lớp của mạng là tương đối tốt. Nhận xét: Có những vị trí mà ta biết trước chắc chắn dữ liệu là kí tự chữ hay kí tự số, do đó có thể sử dụng ràng buộc này để tăng độ chính xác cho việc phân lớp của mạng. III. Minh hoạ một số kết quả: Aûnh phiếu đăng kí môn học được điền đầy đủ thông tin. Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 51 Kết quả xử lí: Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 52 Hình minh hoạ kết quả lấy thông tin phiếu đăng kí môn học. Aûnh phiếu đăng kí môn học được ghi trực tiếp trong chương trình. Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 53 Kết quả xử lí: Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 54 Hình minh hoạ kết quả xử lí phiếu đăng kí môn học CHƯƠNG IV ĐÁNH GIÁ KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI I. Nhận xét chung: Nhìn chung đồ án đã hồn thành về mặt cơ bản nội dung đã đề ra. Đó là sự kết hợp giữa xử lí ảnh và lý thuyết nhận dạng nhằm giải quyết một phần bài tốn nhận dạng chữ viết tay và phát triển một số ứng dụng dựa trên kết quả đã đạt được. Mặc dù hết sức cố gắng, song sai sót là điều không tránh khỏi. Để đánh giá chính xác hiệu quả của chương trình cần nhiều thời gian và những kiểm nghiệm thực tế. Theo ý kiến chủ quan em, trong quá trình thử nghiệm và cài đặt chương trình có thể rút ra những nhận xét sau: Ưu điểm: Khả năng nhận dạng các kí tự chữ số và kí tự chữ cái viết hoa là tương đối tốt, với trạng thái viết thoải mái, bình thường và kiểu chữ viết không phức tạp. Điều này cho thấy hướng đi của lý thuyết đề ra là hợp lý, làm nền tảng cơ sở cho sự phát triển ứng dụng sau này của hệ thống. Việc tách các kí tự ra khỏi văn bản tương đối chính xác. Ta chỉ mất nhiều thời gian cho quá trình huấn luyện mạng, song quá trình nhận dạng thì đơn giản và nhanh chóng. Với cơ sở lý thuyết đã nêu và những thử nghiệm cho thấy dựa vào đó ta có thể xây dựng được nhiều ứng dụng khác nhau. Nhược điểm: Chương trình đang ở mức thử nghiệm, chưa áp dụng vào thực tế. Hệ thống cài đặt còn hạn chế về giao diện, việc quản lí bộ nhớ chưa được chú trọng, cụ thể cần phải thay đổi định dạng file ảnh lưu trữ vì kích thước định dạng file *.bmp là quá lớn. II. Hướng phát triển: Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 55 Để nâng cao hiệu quả, độ chính xác nhận dạng ta có thể phối hợp nhiều mô hình phân lớp với nhau. Bên cạnh đặc trưng mô tả đường biên của kí tự ta cần quan tâm đến một số đặc trưng hình học khác như : - Kích thước theo phương x, y và tỷ lệ của chúng. - Chu vi, diện tích của kí tự. - Số các lỗ của kí tự. - Số euler = (Số thành phần liên thông ) – (Số lỗ của kí tự). Một vấn đề khác chưa được đề cập đến đó là nhận dạng các kí tự viết tay có dấu. Các vấn đề này vẫn đang được tìm hiểu và thử nghiệm song song với việc phát triển những ứng dụng dựa trên kết quả đạt được nhằm hồn thiện chương trình. 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 tố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 hồ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 hồn thiện hơn. Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 56 PHẦN IV PHỤ LỤC GIỚI THIỆU GIAO DIỆN CHƯƠNG TRÌNH A. CHƯƠNG TRÌNH THỬ NGHIỆM NHẬN DẠNG KÍ TỰ VIẾT TAY VÀ PHIẾU ĐĂNG KÍ MÔN HỌC. Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 57 Hình 1. Form chính của chương trình. Chức năng: - Chọn ứng dụng cần thử nghiệm: nhận dạng kí tự, chữ số, nhận dạng phiếu đăng kí môn học. - Nạp trọng số tương ứng cho ứng dụng cần thử nghiệm. - Nạp mẫu và huấn luyện mạng nơron. Hình 2. Form nhận dạng: chức năng nạp ảnh, hoặc viết trực tiếp vào vùng trắng để nhận dạng cho ra kết quả. Hình 3. Form lấy đặc trưng của mẫu học. Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 58 Chức năng lấy véctơ đặc trưng hướng đường biên của mẫu học. Hình 3. Form minh hoạ tiến trình luyện mạng của mạng nơron. B. CHƯƠNG TRÌNH THỬ NGHIỆM NHẬN DẠNG VĂN BẢN TIẾNG VIỆT CHỮ IN. Hình 1. Form chính của chương trình. Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 59 Chức năng: Nạp dữ liệu, nhận dạng ảnh văn bản bằng phương pháp đối sánh. Hình 2. Form nhận dạng ảnh văn bản, chức năng nhận dạng ảnh văn bản và cho ra kết quả. 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 tố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”, Hồng Kiếm (Khoa công nghệ thông tin Đại học Khoa Học Tự Nhiên Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 60 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 -- Hồ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. MỤC LỤC Trang Lời nói đầu ............................................................................................. 1 Nhận xét của giáo viên ........................................................................... 2 Phần I: Tổng quan và cơ sở lý thuyết tiền xử lý ảnh kí tự........................ 3 Chương I: Tổng quan ................................................................... 4 I. Giới thiệu bài tốn ....................................................... 4 II. Cấu trúc nội dung của đồ án ..................................... 5 Chương II: Cơ sở lý thuyết tiền xử lý ảnh kí tự ............................ 6 I. Lọc mịn ảnh .............................................................. 6 II. Nhị phân ảnh ............................................................ 6 III. Đánh nhãn thành phần liên thông ............................ 8 1. Tách liên thông bằng kỹ thuật đệ quy ................ 8 2. Giải thuật cải tiến .............................................. 9 IV. Chỉnh nghiêng ...................................................... 11 V. Chuẩn kích thước ................................................... 12 VI. Lấp khoảng trống ảnh bằng phép đóng morphology ................................................................ 12 1. Một số định nghĩa ........................................... 12 2. Phép giãn ........................................................ 13 3. Phép co ........................................................... 13 4. Phép đóng ....................................................... 13 VII. Lấy đường biên và làm trơn đường biên .............. 14 Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 61 1. Phát hiện biên ................................................. 14 2. Dò biên và mã hố đường biên ......................... 14 3. Xác định hướng của điểm biên ....................... 15 4. Làm trơn đường biên ...................................... 15 Chương III: Rút đặc trưng ......................................................... 18 I. Giới thiệu đặc trưng hướng ...................................... 18 II. Chia ô..................................................................... 18 III. Đặc trưng hướng của đường biên .......................... 19 Phần II: Các mô hình nhận dạng ........................................................... 20 Chương I: Giới thiệu các mô hình phân lớp, nhận dạng ............. 21 I. Khái quát tình hình nghiên cứu, ứng dụng lý thuyết nhận dạng ............................................................... 21 II. Một số khái niệm về nhận dạng .............................. 22 1. Nhận dạng ...................................................... 22 2. Tập mẫu nhận dạng ......................................... 22 3. Độ đồng dạng và dị dạng ................................ 22 4. Khoảng cách đối tượng ................................... 22 III. Một số thuật tốn phân lớp ..................................... 23 1. Xếp lớp khoảng cách cực tiểu ......................... 23 2. Thuật tốn hàm thế ........................................... 23 3. Phương pháp LDA (Linear Discriminant Analysis) ........................... 24 Chương II: Phân lớp dựa trên mạng nơron lan truyền ngược ..... 28 I. Giới thiệu ................................................................ 28 II. Hoạt động............................................................... 29 1. Trạng thái ánh xạ ............................................ 29 2. Trạng thái học ................................................. 32 a. Phương pháp giảm gradient ....................... 32 b. Cập nhật trọng số theo phương pháp giảm gradient ............................................. 32 c. Quy tắc tính đạo hàm lỗi ............................ 33 3. Một vài kỹ thuật luyện mạng........................... 36 a. Học theo lô ................................................ 36 b. Ngăn chặn quá khớp .................................. 36 Phần III: Kết quả thử nghiệm ............................................................... 37 Chương I: Minh hoạ ứng dụng giải thuật tách thành phần liên thông trong bài tốn nhận dạng ảnh văn bản ............... 38 I. Nhận dạng một văn bản ........................................... 38 II. Minh hoạ chương trình ........................................... 39 Chương II: Chương trình nhận dạng kí tự viết tay ..................... 40 I. Giới thiệu chương trình ........................................... 40 II. Thực hiện chương trình .......................................... 40 1. Tiền xử lý ....................................................... 41 Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 62 2. Trích chọn đặc trưng ....................................... 41 3. Bộ phân lớp .................................................... 41 III. Minh hoạ một số kết quả ....................................... 46 Chương III: Ứng dụng xử lý phiếu đăng kí môn học ................. 52 I. Giới thiệu ................................................................ 52 II. Thực hiện chương trình .......................................... 54 1. Định dạng và lấy thông tin từ biểu mẫu........... 54 a. Tìm dấu hiệu định vị biểu mẫu .................. 54 b. Loại bỏ thông tin in trước bằng cách so khớp với mặt nạ mẫu ................................. 56 c. Lấy thông tin vùng dữ liệu ......................... 56 2. Xác định véctơ đặc trưng của ký tự ................. 56 3. Nhận dạng véc tơ đặc trưng ............................ 57 III. Minh hoạ một số kết quả ....................................... 58 Chương IV: Đánh giá kết luận và hướng phát triển của đề tài 62 I. Nhận xét chung........................................................ 62 II. Hướng phát triển .................................................... 62 III. Lời cám ơn ............................................................ 63 Phần IV: Phụ lục giới thiệu giao diện chương trình ............................... 64 A. Chương trình thử nghiệm nhận dạng kí tự viết tay và phiếu đăng kí môn học ...................................................... 65 B. Chương trình thử nghiệm nhận dạng văn bản tiếng Việt chữ in.................................... ................................................. 67 Tài liệu tham khảo:.......... .................................................................... 68 Mục lục:.................................... ............................................................. 69 Nhận dạng kí tự viết tay và phát triển ứng dụng SVTH : NguyễnĐình Cường Trang 63