›

Đồ án Đồ ánTìm hiểu một số phương pháp trích chọn đặc trưng cho nhận dạng chữ viết - Ngô Quốc Tạo

pdf 53 trang huongle 2460
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Đồ ánTìm hiểu một số phương pháp trích chọn đặc trưng cho nhận dạng chữ viết - Ngô Quốc Tạo", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_do_antim_hieu_mot_so_phuong_phap_trich_chon_dac_trung.pdf

Nội dung text: Đồ án Đồ ánTìm hiểu một số phương pháp trích chọn đặc trưng cho nhận dạng chữ viết - Ngô Quốc Tạo

  1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHỊNG o0o ĐỒ ÁN TỐT NGHIỆP NGÀNH CƠNG NGHỆ THƠNG TIN HẢI PHỊNG 2013
  2. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHỊNG o0o TÌM HIỂU MỘT SỐ PHƢƠNG PHÁP TRÍCH CHỌN ĐẶC TRƢNG CHO NHẬN DẠNG CHỮ VIẾT ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng nghệ Thơng tin HẢI PHỊNG - 2013
  3. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHỊNG o0o TÌM HIỂU MỘT SỐ PHƢƠNG PHÁP TRÍCH CHỌN ĐẶC TRƢNG CHO NHẬN DẠNG CHỮ VIẾT ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng nghệ Thơng tin Giáo viên hƣớng dẫn: PGS TS Ngơ Quốc Tạo Sinh viên thực hiện: Nguyễn Sơn Hà Mã số sinh viên: 1351010034 HẢI PHỊNG - 2013
  4. BỘ GIÁO DỤC VÀ ĐÀO TẠO CỘNG HỊA XA HỘI CHỦ NGHĨA VIỆT NAM TRƢỜNG ĐẠI HỌC DÂN LẬP HẢI PHỊNG Độc lập - Tự do - Hạnh phúc o0o NHIỆM VỤ THIẾT KẾ TỐT NGHIỆP Sinh viên: Nguyễn Sơn Hà Mã SV: 1351010034 Lớp: CT1301 Ngành: Cơng nghệ Thơng tin Tên đề tài:Tìm hiểu một số phƣơng pháp trích chọn đặc trƣng cho nhận dạng chữ viết.
  5. NHIỆM VỤ ĐỀ TÀI 1. Nội dung và các yêu cầu cần giải quyết trong nhiệm vụ đề tài tốt nghiệp a. Nội dung - Giới thiệu về trích chọn đặc trƣng:Đặc trƣng bất biến,khả năng khơi phục. - Trích chọn đặc trƣng từ ảnh đa cấp xám:Đối sánh mẫu,mẫu biến dạng,biến đổi ảnh Unitar,bất biến hình học,bất biến Zenite. - Trích chọn đặc trƣng từ ảnh nhị phân:Đối sánh mẫu,mẫu biến dạng,biến đổi ảnh Unitar,bất biến hình học. - Trích chọn đặc trƣng từ biên ảnh:Chiếu nghiêng,tách vùng,xấp xỉ đƣờng cong,mơ tả Fourier. - Trích chọn đặc trƣng từ biểu diễn véc tơ: Đối sánh mẫu,mẫu biến dạng,đặc trƣng rời rạc,biểu diễn đồ thị,biểu diễn Fourier. b. Các yêu cầu cần giải quyết - Hiểu nội dung trích chọn đặc trƣng theo đối sánh - Viết xong đồ án - Cài đặt thử nghiệm chƣơng trình trích đặc trƣng
  6. CÁN BỘ HƢỚNG DẪN ĐỀ TÀI TỐT NGHIỆP Ngƣời hƣớng dẫn thứ nhất: Họ và tên: Ngơ Quốc Tạo Học hàm, học vị: Phĩ giáo sƣ Tiến sĩ Cơ quan cơng tác: Viện Cơng nghệ thơng tin,Viện Hàn Lâm Khoa học và Cơng nghệ Viêt Nam. Nội dung hƣớng dẫn: Ngƣời hƣớng dẫn thứ hai: Họ và tên: Học hàm, học vị: Cơ quan cơng tác: Nội dung hƣớng dẫn: Đề tài tốt nghiệp đƣợc giao ngày .tháng .năm 2013. Yêu cầu phải hồn thành trƣớc ngày .tháng .năm 2013. Đã nhận nhiệm vụ: Đ.T.T.N Đã nhận nhiệm vụ: Đ.T.T.N Sinh viên Cán bộ hƣớng dẫn Đ.T.T.N Nguyễn Sơn Hà PGS TS Ngơ Quốc Tạo Hải Phịng, ngày tháng năm 2013 HIỆU TRƢỞNG GS.TS.NGƯT Trần Hữu Nghị
  7. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng PHẦN NHẬN XÉT TĨM TẮT CỦA CÁN BỘ HƢỚNG DẪN 1. Tinh thần thái độ của sinh viên trong quá trình làm đề tài tốt nghiệp: 2. Đánh giá chất lƣợng của đề tài tốt nghiệp (so với nội dung yêu cầu đã đề ra trong nhiệm vụ đề tài tốt nghiệp) 3. Cho điểm của cán bộ hƣớng dẫn: (Điểm ghi bằng số và chữ) Ngày tháng năm 2013 Cán bộ hƣớng dẫn chính (Ký, ghi rõ họ tên) Nguyễn Sơn Hà - CT1301
  8. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng PHẦN NHẬN XÉT ĐÁNH GIÁ CỦA CÁN BỘ CHẤM PHẢN BIỆN ĐỀ TÀI TỐT NGHIỆP 1. Đánh giá chất lƣợng đề tài tốt nghiệp (về các mặt nhƣ cơ sở lý luận, thuyết minh chƣơng trình, giá trị thực tế). 2. Cho điểm của cán bộ phản biện (Điểm ghi bằng số và chữ) Ngày tháng năm 2013 Cán bộ chấm phản biện (Ký, ghi rõ họ tên) Nguyễn Sơn Hà - CT1301
  9. LỜI CẢM ƠN Trƣớc tiên em xin đƣợc bày tỏ sự trân trọng và lịng biết ơn đối với thầy giáo PGS.TS. Ngơ Quốc Tạo- Trƣởng phịng Nhận dạng và Cơng nghệ tri thức,Viện Cơng nghệ thơng tin,Viện Hàn Lâm Khoa Học và Cơng nghệ Việt Nam. Trong suốt thời gian làm đồ án tốt nghiệp, thầy đã dành rất nhiều thời gian quí báu để tận tình chỉ bảo, hƣớng dẫn, định hƣớng cho em thực hiện đồ án. Em xin đƣợc cảm ơn các thầy cơ giáo Trƣờng Đại học Dân lập Hải phịng đã giảng dạy trong quá trình học tập, thực hành, làm bài tập, giúp em hiểu thấu đáo hơn các nội dung học tập và những hạn chế cần khắc phục trong việc học tập, nghiên cứu và thực hiện bản đồ án này. Em xin cảm ơn các bạn bè và nhất là các thành viên trong gia đình đã tạo mọi điều kiện tốt nhất, động viên, cổ vũ trong suốt quá trình học tập và đồ án tốt nghiệp. Do thời gian và kiến thức cĩ hạn nên khơng tránh khỏi những thiếu sĩt nhất định. Em rất mong nhận đƣợc sự đĩng gĩp quý báu của thầy cơ! Em xin chân thành cảm ơn! Hải Phịng, ngày tháng năm 2013. Sinh viên Nguyễn Sơn Hà
  10. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng MỤC LỤC LỜI CÁM ƠN DANH MỤC HÌNH DANH MỤC CÁC KÝ HIỆU, CỤM TỪ VIẾT TẮT PHẦN MỞ ĐẦU 5 TĨM TẮT ĐỀ TÀI 7 CHƢƠNG 1. TỔNG QUAN VỀ CHỮ VIẾT VÀ LÝ THUYẾT NHẬN DẠNG 8 1.1. GIỚI THIỆU 8 1.2. MƠ HÌNH TỔNG QUÁT CỦA MỘT HỆ NHẬN DẠNG CHỮ VIẾT TAY 8 1.2.1. Tiền xử lý 8 1.2.2. Khối tách chữ : 13 1.2.3. Trích chọn đặc trƣng: 14 1.2.4. Huấn luyện và nhận dạng : 14 1.2.5. Hậu xử lý : 14 1.3. CÁC PHƢƠNG PHÁP NHẬN DẠNG CHỮ VIẾT TAY 15 1.3.1. Đối sánh mẫu: 15 1.3.2. Phƣơng pháp tiếp cận cấu trúc: 16 1.3.3. Mạng nơ ron 17 1.3.4. Mơ hình Markov ẩn (HMM - Hidden Markov Model) : 20 1.3.5. Máy véc tơ tựa (SVM) : 21 1.3.6. Kết hợp các kỹ thuật nhận dạng : 23 1.3.7. Kết luận 24 CHƢƠNG 2: TỔNG QUAN VỀ TRÍCH CHỌN ĐẶC TRƢNG VÀ MỘT SỐ PHƢƠNG PHÁP TRÍCH CHỌN ĐẶC TRƢNG TRONG NHẬN DẠNG CHỮ VIẾT 25 2.1. Trích chọn đặc trƣng 25 2.1.1. Biến đổi tồn cục và khai triển chuỗi 25 2.1.2. Đặc trƣng thống kê 26 2.1.3. Đặc trƣng hình học và hình thái 27 2.2. Đặc trƣng bất biến 28 2.3. Khả năng khơi phục 29 2.4. Trích chọn đặc trƣng từ ảnh đa cấp xám 29 2.4.1. Giới thiệu 29 2.4.2. Đối sánh mẫu 30 2.4.3. Mẫu biến dạng 30 Nguyễn Sơn Hà - CT1301 1
  11. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng 2.4.4. Biến đổi ảnh Unitar 30 2.4.5. Bất biến Zenite 31 2.5. Trích chọn đặc trƣng từ ảnh nhị phân: 31 2.5.1. Giới thiệu 31 2.5.2. Biến đổi ảnh Unitar 32 2.5.3. Bất biến hình học 32 2.6. Trích chọn đặc trƣng từ biên ảnh: 32 2.6.1. Giới thiệu 32 2.6.2. Tách vùng 32 2.6.3. Xấp xỉ đƣờng cong: 33 2.6.4. Mơ tả Fourier: 33 2.7. Trích chọn đặc trƣng từ biểu diễn véc tơ: 33 2.7.1. Giới thiệu 33 2.7.2. Đối sánh mẫu 34 2.7.3. Mẫu biến dạng 34 2.7.4. Đặc trƣng rời rạc 34 2.7.5. Biểu diễn Fourier 34 CHƢƠNG 3: CHƢƠNG TRÌNH THỬ NGHIỆM 36 3.1. Giới thiệu 36 3.2. Xây dựng giao diện vẽ 36 3.3. Xử lý dữ liệu (phân tích ảnh) 37 3.4. Kết quả nhận dạng 39 3.5. Đánh giá, nhận xét 39 KẾT LUẬN 43 TÀI LIỆU THAM KHẢO 44 Nguyễn Sơn Hà - CT1301 2
  12. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng DANH MỤC CÁC HÌNH Hình 1.1. Sơ đồ tổng quát của một hệ nhận dạng chữ viết tay 9 Hình 1.2. . Nhị phân hĩa ảnh 10 Hình 1.3. Nhiễu đốm và nhiễu vệt 10 Hình 1.4. Chuẩn hĩa kích thƣớc ảnh các ký tự “A” và “P” 11 Hình 1.5. (a) Ảnh gốc, (b) Ảnh sau khi đƣợc làm trơn biên 11 Hình 1.6. Làm mảnh chữ. 12 Hình 1.7. Hiệu chỉnh độ nghiêng của văn bản 12 Hình 1.8. Tách dịng chữ dựa trên histogram theo chiều ngang của khối chữ 13 Hình 1.9. Xác định khoảng cách giữa hai kí tự và giữa hai từ dựa trên histogram theo chiều thẳng đứng của dịng chữ 14 Hình 2.1. Mơ hình nhận dạng chữ viết tay rời rạc 22 Hình 2.2 Quá trình tìm giới hạn ký tự 37 Hình 2.3 Quá trình lấy mẫu xuống 38 Hình 2.4. Quá trình ánh xạ từ ma trận điểm sang ma trận giá trị 41 Hình 2.5.Giao diện chính của chƣơng trình 41 Hình 2.6.Giao diện của chƣơng trình sau khi nhận dạng chữ viết xong 41 Hình 2.7.Giao diện của ơ thêm chữ viết 42 Hình 2.8. Giá trị của các ơ vùng khi đƣợc nhận dạng 42 Nguyễn Sơn Hà - CT1301 3
  13. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng DANH MỤC CÁC KÝ HIỆU, CỤM TỪ VIẾT TẮT HMM Markov Model (Mơ hình Markov ẩn) off-line ngoại tuyến on-line trực tuyến OCR Optical Character Recognition (nhận dạng chữ quang học) SVM Support Vector Machines (Máy véc tơ tựa) SOM Self Origanizing Map USPS United States Postal service MNIST bộ mẫu chữ số viết tay NIST - Viện Cơng nghệ và Tiêu chuẩn Quốc gia Hoa Kỳ (National Institute of Standard and Technology of the United States) SV Support vector (véc tơ tựa) working set tập làm việc k-NN k – láng giềng gần nhất Nguyễn Sơn Hà - CT1301 4
  14. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng PHẦN MỞ ĐẦU Cơng nghệ thơng tin ngày càng phát triển và cĩ vai trị hết sức quan trọng khơng thể thiếu trong cuộc sống hiện đại. Con ngƣời ngày càng tạo ra những cỗ máy thơng minh cĩ khả năng tự nhận biết và xử lí đƣợc các cơng việc một cách tự động, phục vụ cho lợi ích của con ngƣời. Trong những năm gần đây, một trong những bài tốn nhận đƣợc nhiều sự quan tâm và tốn nhiều cơng sức nhất của lĩnh vực cơng nghệ thơng tin, đĩ chính là bài tốn nhận dạng. Tuy mới xuất hiện chƣa lâu nhƣng nĩ đã rất đƣợc quan tâm vì tính ứng dụng thực tế của bài tốn cũng nhƣ sự phức tạp của nĩ. Nhận dạng chữ viết là một lĩnh vực đã đƣợc quan tâm nghiên cứu và ứng dụng từ nhiều năm nay theo hai hƣớng chính: -Nhận dạng chữ in: phục vụ cho cơng việc tự động hĩa đọc tài liệu, tăng tốc độ và hiệu quả nhập thơng tin vào máy tính trực tiếp từ các nguồn tài liệu. -Nhận dạng chữ viết tay: với những mức độ ràng buộc khác nhau về cách viết, kiểu chữ phục vụ cho các ứng dụng đọc và xử lý chứng từ, hĩa đơn, phiếu ghi, bản thảo viết tay Nhận dạng chữ viết tay đƣợc tách thành hai hƣớng phát triển: nhận dạng chữ viết tay trực tuyến (on-line) và nhận dạng chữ viết tay ngoại tuyến (off-line). Đến thời điểm này, bài tốn nhận dạng chữ in đã đƣợc giải quyết gần nhƣ trọn vẹn .Tuy nhiên trên thế giới cũng nhƣ ở Việt Nam, bài tốn nhận dạng chữ viết tay vẫn cịn là vấn đề thách thức lớn đối với các nhà nghiên cứu. Bài tồn này chƣa thể giải quyết trọn vẹn vì nĩ phụ thuộc quá nhiều vào ngƣời viết và sự biến đổi quá đa dạng trong cách viết và trạng thái tinh thần của từng ngƣời viết. Đặc biệt đối với việc nghiên cứu nhận dạng chữ viết tiếng Việt lại càng gặp nhiều khĩ khăn hơn do bộ ký tự tiếng Việt cĩ thêm phần dấu, rất dễ nhầm lẫm với các nhiễu. Trích chọn đặc trƣng trong nhận dạng chữ viết là việc tìm và chọn ra các đặc trƣng đặc thù của mỗi chữ viết,qua đĩ là đầu vào cho quá trình nhận dạng.Bên canh việc lựa chọn một thuật tốn nhận dạng phù hợp thì việc tìm ra phƣơng pháp trích chọn đặc trƣng thích hợp sẽ nâng cao độ chính xác và giảm thời gian nhận dạng cho tồn bộ hệ thống, Với sự hấp dẫn của bài tốn và những thách thức cịn đang ở phía trƣớc, với niềm đam mê cơng nghệ hiện đại và những ứng dụng thực tế tuyệt với của nĩ, với khát khao khám phá và chinh phục những tri thức mới mẻ em đã chọn đê tài Nguyễn Sơn Hà - CT1301 5
  15. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng nghiên cứu: Tìm hiểu một số phƣơng pháp trích chọn đặc trƣng cho nhận dạng chữ viết làm để tài nghiên cứu và bảo vệ luận văn tốt nghiệp của mình. Về lý thuyết : - Tìm hiểu khái quát về chữ viết và lý thuyết nhận dạng. - Tìm hiểu về trích chọn đặc trƣng cho nhận dạng chữ viết. Về thực tiễn : - Cài đặt thử nghiệm chƣơng trình đã tìm hiểu đƣợc. Bài báo cáo đƣợc trình bày trong 3 chƣơng: - Chƣơng 1: Trình bày tổng quan về chữ viết và lý thuyết nhận dạng. - Chƣơng 2: Tổng quan về trích chọn đặc trƣng và một số phƣơng pháp trích chọn đặc trƣng cho nhận dạng chữ viết. - Chƣơng 3:Chƣơng trình thử nghiệm. - Kết luận: Tĩm tắt những vấn đề tìm hiểu đƣợc trong bài, các vấn đề liên quan và đƣa ra hƣớng phát triển trong tƣơng lai. Nguyễn Sơn Hà - CT1301 6
  16. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng TĨM TẮT ĐỀ TÀI Bài báo cáo đồ án tốt nghiệp của em, nghiên cứu về “Một số phƣơng pháp trích chọn đặc trƣng cho nhận dạng chữ viết”. Nội dung nghiên cứu gồm 3 chƣơng nhƣ sau: - CHƢƠNG 1: Tổng quan về chữ viết và lý thuyết nhận dạng Chƣơng này nghiên cứu tổng quan về chữ viết và lý thuyết nhận dạng. Nhận dạng chữ là lĩnh vực đƣợc nhiều nhà nghiên cứu quan tâm và cho đến nay lĩnh vực này cũng đã đạt đƣợc nhiều thành tựu lớn lao cả về mặt lý thuyết lẫn ứng dụng thực tế.Đồng thời nêu mơ hình tổng quát của một hệ nhận dạng chữ viết - CHƢƠNG 2: Tổng quan về trích chọn đặc trƣng và một số phƣơng pháp trích chọn đặc trƣng cho nhận dạng chữ viết. Chƣơng này nghiên cứu tổng quan về trích chọn đặc trƣng và một số phƣơng pháp trích chọn đặc trƣng cho nhận dạng chữ viết.Giới thiệu về trích chọn đặc trƣng:Đặc trƣng bất biến,khả năng khơi phục ; trích chọn đặc trƣng từ ảnh đa cấp xám( Đối sánh mẫu,mẫu biến dạng,biến đổi ảnh Unitar,bất biến hình học,bất biếnZenite );trích chọn đặc trƣng từ ảnh nhị phân ( Đối sánh mẫu,mẫu biến dạng,biến đổi ảnh Unitar,bất biến hình học ); trích chọn đặc trƣng từ biên ảnh( Chiếu nghiêng,tách vùng,xấp xỉ đƣờng cong,mơ tả Fourier);trích chọn đặc trƣng từ biểu diễn vectơ( Đối sánh mẫu,mẫu biến dạng, đặc trƣng rời rạc,biểu diễn đồ thị, biểu diễn Fourier ). - CHƢƠNG 3 :Chƣơng trình thử nghiệm. Nguyễn Sơn Hà - CT1301 7
  17. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng CHƢƠNG 1. TỔNG QUAN VỀ CHỮ VIẾT VÀ LÝ THUYẾT NHẬN DẠNG 1.1. GIỚI THIỆU Nhận dạng chữ là lĩnh vực đƣợc nhiều nhà nghiên cứu quan tâm và cho đến nay lĩnh vực này cũng đã đạt đƣợc nhiều thành tựu lớn lao cả về mặt lý thuyết lẫn ứng dụng thực tế. Lĩnh vực nhận dạng chữ đƣợc chia làm hai loại: Nhận dạng chữ in và nhận dạng chữ viết tay. Đến thời điểm này, nhận dạng chữ in đã đƣợc giải quyết gần nhƣ trọn vẹn. Tuy nhiên, nhận dạng chữ viết tay vẫn đang là vấn đề thách thức lớn đối với các nhà nghiên cứu. Nhận dạng chữ viết tay đƣợc phân ra làm hai loại: nhận dạng chữ viết tay on-line (trực tuyến) và nhận dạng chữ viết tay off-line (ngoại tuyến). Nhận dạng chữ viết tay on-line đƣợc thực hiện trên cơ sở lƣu lại các thơng tin về nét chữ nhƣ thứ tự nét viết, hƣớng và tốc độ của nét viết trong quá trình nĩ đang viết. Đây chính là cơ sở để máy tính nhận diện đƣợc các chữ cái, do đĩ việc nhận dạng khơng gặp quá nhiều khĩ khăn.Ngƣợc lại, đối với nhận dạng chữ viết tay off-line, dữ liệu đầu vào là ảnh văn bản đƣợc quét vào nên việc nhận dạng cĩ độ khĩ cao hơn nhiều so với nhận dạng chữ viết tay on-line. Do dữ liệu đầu vào là ảnh văn bản nên nhận dạng chữ viết tay off-line và nhận dạng chữ in cịn đƣợc gọi chung là nhận dạng chữ quang học (OCR - Optical Character Recognition). Khĩ khăn lớn nhất khi nghiên cứu bài tốn nhận dạng chữ viết tay là sự biến thiên quá đa dạng trong cách viết của từng ngƣời. Cùng một ngƣời viết nhƣng đơi khi cũng cĩ nhiều sự khác biệt trong cách viết tuỳ thuộc vào từng ngữ cảnh, kiểu viết của một ngƣời cũng cĩ thể thay đổi theo thời gian hoặc theo thĩi quen Điều này gây ra nhiều trở ngại trong việc trích chọn đặc trƣng cũng nhƣ lựa chọn mơ hình nhận dạng. 1.2. MƠ HÌNH TỔNG QUÁT CỦA MỘT HỆ NHẬN DẠNG CHỮ VIẾT TAY 1.2.1. Tiền xử lý Giai đoạn này gĩp phần làm tăng độ chính xác phân lớp của hệ thống nhận dạng, tuy nhiên nĩ cũng làm cho tốc độ nhận dạng của hệ thống chậm lại. Vì vậy, tùy thuộc vào chất lƣợng ảnh quét vào của từng văn bản cụ thể để chọn một hoặc một vài chức năng trong khối này. Nếu cần ƣu tiên tốc độ xử lý và chất lƣợng của Nguyễn Sơn Hà - CT1301 8
  18. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng máy quét tốt thì cĩ thể bỏ qua giai đoạn này. Khối tiền xử lý bao gồm một số chức năng: Nhị phân hĩa ảnh, lọc nhiễu, chuẩn hĩa kích thƣớc ảnh, làm trơn biên chữ, làm đầy chữ, làm mảnh chữ và xoay văn bản. 1.2.1.1. Nhị phân hĩa ảnh Nhị phân hĩa ảnh là một kỹ thuật chuyển ảnh đa cấp xám sang ảnh nhị phân. Trong bất kỳ bài tốn phân tích hoặc nâng cao chất lƣợng ảnh nào, nĩ cũng cần thiết để xác định các đối tƣợng quan trọng. Nhị phân hĩa ảnh phân chia ảnh thành 2 phần: phần nền và phần chữ. Hầu hết các phƣơng pháp nhị phân hĩa ảnh hiện nay Nguyễn Sơn Hà - CT1301 9
  19. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng đều lựa chọn một ngƣỡng thích hợp theo cƣờng độ sáng của ảnh và sau đĩ chuyển tất cả các giá trị độ sáng lớn hơn ngƣỡng đĩ thành một giá trị độ sáng (ví dụ “trắng”) và tất cả các giá trị bé hơn ngƣỡng thành một giá trị độ sáng khác (“đen”). Hình 1.2. Nhị phân hĩa ảnh. 1.2.1.2. Lọc nhiễu Nhiễu là một tập các điểm sáng thừa trên ảnh. Khử nhiễu là một vấn đề thƣờng gặp trong nhận dạng, nhiễu cĩ nhiều loại (nhiễu đốm, nhiễu vệt, nhiễu đứt nét ). Hình 1.3. Nhiễu đốm và nhiễu vệt. Để khử các nhiễu đốm (các nhiễu với kích thƣớc nhỏ), cĩ thể sử dụng các phƣơng pháp lọc (lọc trung bình, lọc trung vị ). Tuy nhiên, với các nhiễu vệt (hoặc các nhiễu cĩ kích thƣớc lớn) thì các phƣơng pháp lọc tỏ ra kém hiệu quả, trong trƣờng hợp này sử dụng phƣơng pháp khử các vùng liên thơng nhỏ tỏ ra cĩ hiệu quả hơn. Nguyễn Sơn Hà - CT1301 10
  20. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng 1.2.1.3. Chuẩn hĩa kích thƣớc ảnh Hình 1.4. Chuẩn hĩa kích thước ảnh các ký tự “A” và “P”. Việc chuẩn hĩa kích thƣớc ảnh dựa trên việc xác định trọng tâm ảnh, sau đĩ xác định khoảng cách lớn nhất từ tâm ảnh đến các cạnh trên, dƣới, trái, phải của hình chữ nhật bao quanh ảnh. Thơng qua khoảng cách lớn nhất đĩ, cĩ thể xác định đƣợc một tỷ lệ co, giãn của ảnh gốc so với kích thƣớc đã xác định, từ đĩ hiệu chỉnh kích thƣớc ảnh theo tỷ lệ co, giãn này. Nhƣ vậy, thuật tốn chuẩn hĩa kích thƣớc ảnh luơn luơn đảm bảo đƣợc tính cân bằng khi co giãn ảnh, ảnh sẽ khơng bị biến dạng hoặc bị lệch. 1.2.1.4. Làm trơn biên chữ: Đơi khi do chất lƣợng quét ảnh quá xấu, các đƣờng biên của chữ khơng cịn giữ đƣợc dáng điệu trơn tru ban đầu mà hình thành các đƣờng răng cƣa giả tạo. Trong các trƣờng hợp này, phải dùng các thuật tốn làm trơn biên để khắc phục. (a) (b) Hình 1.5. (a) Ảnh gốc, (b) Ảnh sau khi được làm trơn biên. Nguyễn Sơn Hà - CT1301 11
  21. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng 1.2.1.5. Làm đầy chữ Chức năng này đƣợc áp dụng với các ký tự bị đứt nét một cách ngẫu nhiên. Ảnh đứt nét gây khĩ khăn cho việc tách chữ, dễ bị nhầm hai phần liên thơng của ký tự thành hai ký tự riêng biệt, tạo nên sai lầm trong quá trình nhận dạng. 1.2.1.6. Làm mảnh chữ Đây là một bƣớc quan trọng nhằm phát hiện khung xƣơng của ký tự bằng cách loại bỏ dần các điểm biên ngồi của các nét. Tuy nhiên, quá trình làm mảnh chữ rất nhạy cảm với việc khử nhiễu. Hình 1.6. Làm mảnh chữ. 1.2.1.7. Điều chỉnh độ nghiêng của văn bản Do trang tài liệu quét vào khơng cẩn thận hoặc do sự cố in ấn, các hàng chữ bị lệch so với lề chuẩn một gĩc α, điều này gây khĩ khăn cho cơng đoạn tách chữ, đơi khi khơng thể tách đƣợc. Trong những trƣờng hợp nhƣ vậy, phải tính lại tọa độ điểm ảnh của các chữ bị sai lệch. Cĩ nhiều kỹ thuật để điều chỉnh độ nghiêng, kỹ thuật phổ biến nhất dựa trên cơ sở biểu đồ chiếu (projection profile) của ảnh tài liệu; một số kỹ thuật dựa trên cơ sở các phép biến đổi Hough và Fourier. Hình 1.7. Hiệu chỉnh độ nghiêng của văn bản Nguyễn Sơn Hà - CT1301 12
  22. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng 1.2.2. Khối tách chữ : Khối này cĩ nhiệm vụ tách từng ký tự ra khỏi văn bản. Chỉ khi nào văn bản đƣợc tách và cơ lập đúng từng ký tự đơn ra khỏi tổng thể văn bản thì hệ thống mới cĩ thể nhận dạng đúng ký tự đĩ. Sau đây là một số phƣơng pháp tách chữ thơng dụng: 1.2.2.1. Tách chữ theo chiều nằm ngang và thẳng đứng Phƣơng pháp này thƣờng áp dụng cho chữ in. Khác với chữ viết tay, kích thƣớc và kiểu chữ cố định, phải tuân theo một số quy định in ấn, các chữ phải nằm gọn trong một khung nên việc cơ lập một ký tự đơn cĩ thể đồng nhất với việc tìm ra khung bao của chữ đĩ tại vị trí của nĩ trong văn bản. Tách chữ theo chiều nằm ngang và thẳng đứng là tìm một hình chữ nhật cĩ cạnh thẳng đứng và nằm ngang chứa trọn một ký tự ở bên trong. 1.2.2.2. Tách chữ dùng lƣợc đồ sáng Hình 1.8. Tách dịng chữ dựa trên histogram theo chiều ngang của khối chữ Đối với chữ viết tay thì việc tìm đƣờng phân cách giữa các dịng và các ký tự trong văn bản thƣờng rất khĩ khăn. Trong trƣờng hợp này, khơng thể tìm đƣờng phân cách theo nghĩa thơng thƣờng mà phải hiểu là đƣờng phân cách với số điểm cắt hai dịng là ít nhất. Khi đĩ phải xây dựng lƣợc đồ sáng của các dịng chữ, từ đĩ các đoạn thấp nhất trên lƣợc đồ chính là đƣờng phân cách cần tìm (hình 1.8 và 1.9). Nguyễn Sơn Hà - CT1301 13
  23. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng Hình 1.9. Xác định khoảng cách giữa hai kí tự và giữa hai từ dựa trên histogram theo chiều thẳng đứng của dịng chữ. 1.2.3. Trích chọn đặc trƣng: Trích chọn đặc trƣng đĩng vai trị cực kỳ quan trọng trong một hệ thống nhận dạng. Trong trƣờng hợp đơn giản nhất, ảnh đa cấp xám hoặc ảnh nhị phân đƣợc sử dụng cho việc nhận dạng. Tuy nhiên, trong hầu hết các hệ nhận dạng, để giảm độ phức tạp và tăng độ chính xác của các thuật tốn phân lớp thì địi hỏi các đặc trƣng đƣợc trích chọn phải rút gọn lại càng nhỏ càng tốt nhƣng vẫn phải đảm bảo đƣợc thơng tin của ký tự. Với mục tiêu này, một tập các đặc trƣng đƣợc trích chọn cho mỗi lớp sao cho cĩ thể phân biệt đƣợc với các lớp khác. 1.2.4. Huấn luyện và nhận dạng : Đây là giai đoạn quan trọng nhất, giai đoạn này quyết định độ chính xác của hệ thống nhận dạng. Cĩ nhiều phƣơng pháp phân lớp khác nhau đƣợc áp dụng cho các hệ thống nhận dạng chữ viết tay. 1.2.5. Hậu xử lý : Đây là cơng đoạn cuối cùng của quá trình nhận dạng. Cĩ thể hiểu hậu xử lý là bƣớc ghép nối các kí tự đã nhận dạng thành các từ, các câu, các đoạn văn nhằm tái hiện lại văn bản đồng thời phát hiện ra các lỗi nhận dạng sai bằng cách kiểm tra chính tả dựa trên cấu trúc và ngữ nghĩa của các từ, các câu hoặc các đoạn văn. Việc phát hiện ra các lỗi, các sai sĩt trong nhận dạng ở bƣớc này gĩp phần đáng kể vào việc nâng cao chất lƣợng nhận dạng. Cách đơn giản nhất để kết nối các thơng tin ngữ cảnh là tận dụng một từ điển để điều chỉnh các lỗi của hệ thống nhận dạng. Nguyễn Sơn Hà - CT1301 14
  24. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng 1.3. CÁC PHƢƠNG PHÁP NHẬN DẠNG CHỮ VIẾT TAY Cĩ nhiều phƣơng pháp nhận dạng mẫu khác nhau đƣợc áp dụng rộng rãi trong các hệ thống nhận dạng chữ viết tay. Các phƣơng pháp này cĩ thể đƣợc tích hợp trong các hƣớng tiếp cận sau: Đối sánh mẫu, thống kê, cấu trúc, mạng nơ ron và SVM. 1.3.1. Đối sánh mẫu: Kỹ thuật nhận dạng chữ đơn giản nhất dựa trên cơ sở đối sánh các nguyên mẫu (prototype) với nhau để nhận dạng ký tự hoặc từ. Nĩi chung, tốn tử đối sánh xác định mức độ giống nhau giữa hai vé tơ (nhĩm các điểm, hình dạng, độ cong ) trong một khơng gian đặc trƣng. Các kỹ thuật đối sánh cĩ thể nghiên cứu theo ba hƣớng sau: Đối sánh trực tiếp: Một ký tự đầu vào là ảnh đa cấp xám hoặc ảnh nhị phân đƣợc so sánh trực tiếp với một tập mẫu chuẩn đã đƣợc lƣu trữ. Việc so sánh dựa theo một độ đo về sự tƣơng đồng nào đĩ (chẳng hạn nhƣ độ đo Euclide) để nhận dạng. Các kỹ thuật đối sánh này cĩ thể đơn giản nhƣ việc so sánh một – một hoặc phức tạp hơn nhƣ phân tích cây quyết định . Mặc dù phƣơng pháp đối sánh trực tiếp đơn giản và cĩ một cơ sở tốn học vững chắc nhƣng kết quả nhận dạng của nĩ cũng rất nhạy cảm với nhiễu. Các mẫu biến dạng và Đối sánh mềm: Một phƣơng pháp đối sánh khác là sử dụng các mẫu biến dạng, trong đĩ một phép biến dạng ảnh đƣợc dùng để đối sánh một ảnh chƣa biết với một cơ sở dữ liệu ảnh đã biết . Ý tƣởng cơ bản của đối sánh mềm là đối sánh một cách tối ƣu mẫu chƣa biết với tất cả các mẫu cĩ thể mà các mẫu này cĩ thể kéo giãn ra hoặc co lại. Chỉ một khơng gian đặc trƣng đƣợc thành lập, các véc tơ chƣa biết đƣợc đối sánh bằng cách sử dụng quy hoạch động và một hàm biến dạng . Đối sánh giảm nhẹ: Đây là một kỹ thuật đối sánh ảnh ở mức độ tƣợng trƣng, kỹ thuật này sử dụng hình dáng đặc trƣng cơ bản của ảnh ký tự. Thứ nhất, các vùng đối sánh đã đƣợc nhận biết. Sau đĩ, trên cơ sở một số vùng đối sánh đƣợc đánh giá tốt, các phần tử của ảnh đƣợc so sánh với các vùng đối sánh này. Cơng việc này địi hỏi một kỹ thuật tìm kiếm trong một khơng gian đa chiều để tìm cực đại tồn cục của một số hàm . Nguyễn Sơn Hà - CT1301 15
  25. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng Các kỹ thuật đối sánh mẫu chỉ áp dụng tốt đối với nhận dạng chữ in, cịn đối với chữ viết tay thì các kỹ thuật này tỏ ra kém hiệu quả. 1.3.2. Phƣơng pháp tiếp cận cấu trúc: Cách tiếp cận của phƣơng pháp này dựa vào việc mơ tả đối tƣợng nhờ một số khái niệm biểu diễn đối tƣợng cơ sở trong ngơn ngữ tự nhiên. Để mơ tả đối tƣợng ngƣời ta dùng một số dạng nguyên thuỷ nhƣ đoạn thẳng, cung, Mỗi đối tƣợng đƣợc mơ tả nhƣ một sự kết hợp của các dạng nguyên thuỷ. Các quy tắc kết hợp các dạng nguyên thuỷ đƣợc xây dựng giống nhƣ việc nghiên cứu văn phạm trong một ngơn ngữ, do đĩ quá trình quyết định nhận dạng là quá trình phân tích cú pháp. Phƣơng pháp này đặt vấn đề để giải quyết bài tốn nhận dạng chữ tổng quát. Tuy vậy, cho đến nay cịn nhiều vấn đề liên quan đến hệ nhận dạng cú pháp chƣa đƣợc giải quyết độc lập và chƣa xây dựng đƣợc các thuật tốn phổ dụng. Hiện nay, nhận dạng theo cấu trúc phổ biến là trích trọn các đặc trƣng của mẫu học, phân hoạch bảng ký tự dựa trên các đặc trƣng này, sau đĩ ảnh cần nhận dạng sẽ đƣợc trích chọn đặc trƣng, sau đĩ so sánh trên bảng phân hoạch để tìm ra ký tự cĩ các đặc trƣng phù hợp. Đối với nhận dạng chữ viết tay rời rạc dựa theo cấu trúc xƣơng và đƣờng biên, cơng việc này địi hỏi phải xây dựng các đặc trƣng của chữ, đặc biệt là đặc trƣng về các điểm uốn, điểm gấp khúc và đặc trƣng của các nét. Sau khi tiến hành cơng đoạn tiền xử lý, cơng việc tách các nét đƣợc tiến hành thơng qua các điểm chạc. Sau đĩ trích chọn đặc trƣng cấu trúc xƣơng của chữ, mỗi nét đặc trƣng bởi cặp chỉ số đầu và cuối tƣơng ứng với thứ tự của điểm chạc đầu và điểm chạc cuối. Cuối cùng là xây dựng cây tìm kiếm, dựa vào đặc trƣng về cấu trúc xƣơng và cấu trúc biên để phân tập mẫu học thành các lớp. Quá trình tìm kiếm để phân lớp đƣợc tiến hành qua hai bƣớc: Xác định lớp tƣơng ứng với mẫu vào và tìm kiếm trong lớp đĩ mẫu nào gần giống với mẫu vào nhất . Các phƣơng pháp cấu trúc áp dụng cho các bài tốn nhận dạng chữ đƣợc phát triển theo hai hƣớng sau: 1.3.2.1. Phƣơng pháp ngữ pháp (Grammatical Methods) Giữa thập niên 1960, các nhà nghiên cứu bắt đầu xét các luật của ngơn ngữ học để phân tích tiếng nĩi và chữ viết. Sau đĩ, các luật đa dạng của chính tả, từ vựng và ngơn ngữ học đã đƣợc áp dụng cho các chiến lƣợc nhận dạng. Các phƣơng pháp ngữ pháp khởi tạo một số luật sinh để hình thành các ký tự từ một tập các cơng Nguyễn Sơn Hà - CT1301 16
  26. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng thức ngữ pháp nguyên thủy. Các luật sinh này cĩ thể kết nối bất kỳ kiểu đặc trƣng thống kê và đặc trƣng hình thái nào dƣới một số cú pháp hoặc các luật ngữ nghĩa. Giống nhƣ lý thuyết ngơn ngữ, các luật sinh cho phép mơ tả các cấu trúc câu cĩ thể chấp nhận đƣợc và trích chọn thơng tin theo ngữ cảnh về chữ viết bằng cách sử dụng các kiểu ngữ pháp khác nhau . Trong các phƣơng pháp này, việc huấn luyện đƣợc thực hiện bằng cách mơ tả mỗi ký tự bằng một văn phạm Gi. Cịn trong pha nhận dạng thì chuỗi, cây hoặc đồ thị của một đơn vị viết bất kỳ (ký tự, từ hoặc câu) đƣợc phân tích để quyết định văn phạm của mẫu đĩ thuộc lớp nào. Các phƣơng pháp ngữ pháp hầu hết đƣợc sử dụng trong giai đoạn hậu xử lý để sửa các lỗi mà khối nhận dạng đã thực hiện sai . 1.3.2.2. Phƣơng pháp đồ thị (Graphical Methods) Các đơn vị chữ viết đƣợc mơ tả bởi các cây hoặc các đồ thị. Các dạng nguyên thủy của ký tự (các nét) đƣợc lựa chọn bởi một hƣớng tiếp cận cấu trúc. Đối với mỗi lớp, một đồ thị hoặc cây đƣợc thành lập trong giai đoạn huấn luyện để mơ tả các nét, các ký tự hoặc các từ. Giai đoạn nhận dạng gán một đồ thị chƣa biết vào một trong các lớp bằng cách sử dụng một độ đo để so sánh các đặc điểm giống nhau giữa các đồ thị. Cĩ rất nhiều hƣớng tiếp cận khác nhau sử dụng phƣơng pháp đồ thị, tiêu biểu là hƣớng tiếp cận đồ thị phân cấp đƣợc dùng trong việc nhận dạng chữ viết tay Trung Quốc và Hàn Quốc. 1.3.3. Mạng nơ ron Một mạng nơ ron đƣợc định nghĩa nhƣ một cấu trúc tính tốn bao gồm nhiều bộ xử lý “nơ ron” đƣợc kết nối song song chằng chịt với nhau. Do bản chất song song của các nơ ron nên nĩ cĩ thể thực hiện các tính tốn với tốc độ cao hơn so với các kỹ thuật phân lớp khác. Một mạng nơ ron chứa nhiều nút, đầu ra của một nút đƣợc sử dụng cho một nút khác ở trong mạng và hàm quyết định cuối cùng phụ thuộc vào sự tƣơng tác phức tạp giữa các nút. Mặc dù nguyên lý khác nhau, nhƣng hầu hết các kiến trúc mạng nơ ron đều tƣơng đƣơng với các phƣơng pháp nhận dạng mẫu thống kê . Các kiến trúc mạng nơ ron cĩ thể đƣợc phân thành hai nhĩm chính: mạng truyền thẳng và mạng lan truyền ngƣợc. Trong các hệ thống nhận dạng chữ, các mạng nơ ron sử dụng phổ biến nhất là mạng perceptron đa lớp thuộc nhĩm mạng Nguyễn Sơn Hà - CT1301 17
  27. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng truyền thẳng và mạng SOM (Self Origanizing Map) của Kohonen thuộc nhĩm mạng lan truyền ngƣợc. Mạng perceptron đa lớp đƣợc đề xuất bởi Rosenblatt đƣợc nhiều tác giả sử dụng trong các hệ nhận dạng chữ viết tay. Hầu hết các nghiên cứu phát triển nhận dạng chữ viết tay hiện nay đều tập trung vào mạng SOM. SOM kết hợp trích chọn đặc trƣng và nhận dạng trên một tập lớn các ký tự huấn luyện. Mạng này chứng tỏ rằng nĩ tƣơng đƣơng với thuật tốn phân cụm k-means. Với thuật tốn đơn giản nhƣng rất hiệu quả, cùng với thành cơng của mơ hình này trong các ứng dụng thực tiễn, mạng nơ ron hiện đang là một trong các hƣớng nghiên cứu của lĩnh vực học máy. Mạng nơ ron tỏ ra phù hợp với các bài tốn đối sánh, phân loại mẫu, xấp xỉ hàm, tối ƣu hố, lƣợng tử hố véc tơ và phân hoạch khơng gian dữ liệu, trong khi các phƣơng pháp truyền thống khơng đủ khả năng giải quyết các vấn đề nêu trên một cách hiệu quả. Đặc biệt trong các hệ thống nhận dạng sử dụng mạng nơ ron đã đạt đƣợc tỉ lệ nhận dạng khá chính xác, cĩ thể so sánh với các phƣơng pháp nhận dạng cấu trúc, thống kê, 1.3.3.1. Đặc trƣng của mạng nơron Tính phi tuyến Một nơron cĩ thể tính tốn một cách tuyến tính hay phi tuyến. Một mạng nơron cấu thành bởi các nơron phi tuyến thì cũng sẽ cĩ tính phi tuyến. Hơn nữa, điều đặc biệt là tính phi tuyến này đƣợc phân tán trên tồn mạng. Tính phi tuyến là một thuộc tính rất quan trọng, nhất là khi các cơ chế vật lý sinh ra các tín hiệu đầu vào (ví dụ tín hiệu tiếng nĩi) vốn là phi tuyến. 1.3.3.1.1. Tính chất tƣơng ứng đầu vào, đầu ra Mặc dù khái niệm “học” (hay “huấn luyện”) chƣa đƣợc bàn đến nhƣng để hiểu đƣợc mối quan hệ đầu vào-đầu ra của mạng nơron, chúng ta sẽ đề cập sơ qua về khái niệm này. Một mơ hình học phổ biến đƣợc gọi là “học cĩ thầy” (hay “học cĩ giám sát”), liên quan đến việc thay đổi các trọng số liên kết của mạng nơron bằng việc áp dụng một tập hợp các mẫu tích luỹ. Mỗi một mẫu bao gồm một tín hiệu đầu vào và một đầu ra mong muốn tƣơng ứng. Các trọng số liên kết của mạng đƣợc biến đổi sao cho cĩ thể cực tiểu hố sự sai khác giữa đầu ra mong muốn và đầu ra thực sự của mạng theo một tiêu chuẩn thống kê thích hợp. Sự tích luỹ của mạng đƣợc lặp lại với nhiều ví dụ trong tập hợp cho tới khi mạng đạt tới một trạng thái ổn định mà ở đĩ khơng cĩ một sự thay đổi đáng kể nào của các trọng số liên kết. Các ví dụ tích luỹ đƣợc áp dụng trƣớc cĩ thể đƣợc áp dụng lại trong thời gian Nguyễn Sơn Hà - CT1301 18
  28. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng của phiên tích luỹ nhƣng theo một thứ tự khác. Nhƣ vậy, mạng nơron học từ các ví dụ bằng cách xây dựng nên một tƣơng ứng đầu vào - đầu ra cho vấn đề cần giải quyết. 1.3.3.1.2. Tính chất thích nghi Các mạng nơron cĩ một khả năng mặc định là cĩ thể biến đổi các trọng số liên kết tuỳ theo sự thay đổi của mơi trƣờng xung quanh. Đặc biệt, một mạng nơron đã đƣợc tích luỹ để hoạt động trong một mơi trƣờng xác định cĩ thể đƣợc tích luỹ lại một cách dễ dàng khi cĩ những thay đổi nhỏ của các điều kiện mơi trƣờng. 1.3.3.1.3. Tính chất đƣa ra lời giải cĩ bằng chứng Trong ngữ cảnh phân loại mẫu, một mạng nơron cĩ thể đƣợc thiết kế để đƣa ra thơng tin khơng chỉ về mẫu đƣợc phân loại, mà cịn về sự tin cậy của quyết định đã đƣợc thực hiện. Thơng tin này cĩ thể đƣợc sử dụng để loại bỏ các mẫu mơ hồ hay nhập nhằng. 1.3.3.1.4. Tính chất chấp nhận sai sĩt Một mạng nơron, đƣợc cài đặt dƣới dạng phần cứng, vốn cĩ khả năng chấp nhận lỗi, hay khả năng tính tốn thơ (chứ khơng nhạy cảm lỗi). Tức là, tính năng của mạng nơron chỉ thối hố (chứ khơng đổ vỡ) khi cĩ những điều kiện hoạt động bất lợi. Ví dụ, nếu một nơron hay các liên kết kết nối của nĩ bị hỏng, việc nhận dạng lại một mẫu đƣợc lƣu trữ sẽ suy giảm về chất lƣợng. Tuy nhiên, do bản chất phân tán của thơng tin lƣu trữ trong mạng nơron, sự hỏng hĩc cũng đƣợc trải ra trên tồn mạng. Nhƣ vậy, về cơ bản, trong trƣờng hợp này một mạng nơron sẽ thể hiện một sự thối hố về tính năng hơn là sự đổ vỡ trầm trọng. 1.3.3.1.5. Khả năng cài đặt VLSI (Very-Large-Scale-Intergrated) Bản chất song song đồ sộ của một mạng nơron làm cho mạng nơron đĩ rất nhanh trong tính tốn đối với một số cơng việc. Đặc tính này cũng làm cho một mạng nơron cĩ khả năng phù hợp trong việc cài đặt sử dụng kỹ thuật Very -large- scale-intergrated (VLSI). Kỹ thuật này cho phép xây dựng những mạch cứng tính tốn song song quy mơ lớn. Chính vì vậy, ƣu điểm nổi bật của VLSI là mang lại những phƣơng tiện hữu hiệu để cĩ thể xử lý đƣợc những hành vi cĩ độ phức tạp cao. Nguyễn Sơn Hà - CT1301 19
  29. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng 1.3.3.1.6. Tính chất đồng dạng trong phân tích và thiết kế Về cơ bản, các mạng nơron cĩ tính chất chung nhƣ là các bộ xử lý thơng tin. Điều này áp dụng cho tất cả các lĩnh vực cĩ liên quan tới việc ứng dụng mạng nơron. Đặc tính này thể hiện ở một số điểm nhƣ sau:  Các nơron, dƣới dạng này hoặc dạng khác, biểu diễn một thành phần chung cho tất cả các mạng nơron.  Tính thống nhất này đem lại khả năng chia sẻ các lý thuyết và các thuật tốn học trong nhiều ứng dụng khác nhau của mạng nơron.  Các mạng tổ hợp (modular) cĩ thể đƣợc xây dựng thơng qua một sự tích hợp các mơ hình khác nhau. 1.3.3.1.7. Một số ứng dụng chính của mạng nơron - Aerospace: Phi cơng tự động, giả lập đƣờng bay, các hệ thống điều khiển lái máy bay, bộ phát hiện lỗi. - Automotive: Các hệ thống dẫn đƣờng tự động cho ơ tơ, các bộ phân tích hoạt động của xe. - Banking: Bộ đọc séc và các tài liệu, tính tiền của thẻ tín dụng. - Defense: Định vị - phát hiện vũ khí, dị mục tiêu, phát hiện đối tƣợng, nhận dạng nét mặt, các bộ cảm biến thế hệ mới, xử lý ảnh radar, - Electronics: Dự đốn mã tuần tự, sơ đồ chip IC, điều khiển tiến trình, phân tích nguyên nhân hỏng chip, nhận dạng tiếng nĩi, mơ hình phi tuyến. - Entertainment: Hoạt hình, các hiệu ứng đặc biệt, dự báo thị trƣờng. - Financial: Định giá bất động sản, cho vay, kiểm tra tài sản cầm cố, đánh giá mức độ hợp tác, phân tích đƣờng tín dụng, chƣơng trình thƣơng mại qua giấy tờ, phân tích tài chính liên doanh, dự báo tỷ giá tiền tệ. - Insurance: Đánh giá việc áp dụng chính sách, tối ƣu hĩa sản phẩm. 1.3.4. Mơ hình Markov ẩn (HMM - Hidden Markov Model) : HMM là một mơ hình xác suất hữu hạn trạng thái theo kiểu phát sinh tiến trình bằng cách định nghĩa xác suất liên kết trên các chuỗi quan sát. Mỗi chuỗi quan sát đƣợc sinh ra bởi một chuỗi các phép chuyển trạng thái, bắt đầu từ trạng thái khởi đầu cho đến khi thu đƣợc trạng thái kết thúc. Tại mỗi trạng thái thì một phần tử của chuỗi quan sát đƣợc phát sinh ngẫu nhiên trƣớc khi chuyển sang trạng thái tiếp theo. Nguyễn Sơn Hà - CT1301 20
  30. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng 1.3.5. Máy véc tơ tựa (SVM) : 1.3.5.1. Giới thiệu: Cho đến nay, việc nhận dạng chữ viết tay vẫn chƣa cĩ đƣợc một giải pháp tổng thể, các ứng dụng của nĩ cũng chỉ giới hạn trong phạm vi hẹp. Các kết quả chủ yếu về lĩnh vực này chỉ tập trung trên các tập dữ liệu chữ số viết tay chuẩn nhƣ USPS và MNIST, bên cạnh đĩ cũng cĩ một số cơng trình nghiên cứu trên các hệ chữ cái tiếng La tinh, Hy Lạp, Trung Quốc, Việt Nam tuy nhiên các kết quả đạt đƣợc cũng cịn nhiều hạn chế. Các giải pháp tiếp cận để giải bài tốn nhận dạng chữ viết tay khá phong phú, một số phƣơng pháp học máy thƣờng đƣợc áp dụng nhƣ: mơ hình Markov ẩn, mạng nơ ron hay phƣơng pháp máy véc tơ tựa (SVM - Support Vector Machines). Trong đĩ SVM đƣợc đánh giá là phƣơng pháp học máy tiên tiến đang đƣợc áp dụng rộng rãi trong các lĩnh khai phá dữ liệu và thị giác máy tính SVM gốc đƣợc thiết kế để giải bài tốn phân lớp nhị phân, ý tƣởng chính của phƣơng pháp này là tìm một siêu phẳng phân cách sao cho khoảng cách lề giữa hai lớp đạt cực đại. Khoảng cách này đƣợc xác định bởi các véc tơ tựa (SV - Support Vector), các SV này đƣợc lọc ra từ tập mẫu huấn luyện bằng cách giải một bài tốn tối ƣu lồi. 1.3.5.2. Mơ hình nhận dạng chữ viết tay rời rạc: Trong phần này, sẽ tập trung xây dựng mơ hình nhận dạng chữ viết tay rời rạc theo phƣơng pháp phân lớp SVM. Cơng việc đƣợc thực hiện theo hai bƣớc chính sau đây: Bƣớc 1: Xây dựng mơ hình huấn luyện. Tập dữ liệu huấn luyện sau khi qua các khâu tiền xử lý và trích chọn đặc trƣng sẽ đƣợc đƣa vào máy huấn luyện phân lớp SVM. Sau khi kết thúc quá trình huấn luyện, hệ thống sẽ lƣu lại giá trị các tham số của hàm quyết định phân lớp để phục vụ cho việc nhận dạng sau này. Quá trình huấn luyện tiêu tốn khá nhiều thời gian, tốc độ huấn luyện nhanh hay chậm tùy thuộc vào từng thuật tốn huấn luyện, chiến lƣợc phân lớp SVM cũng nhƣ số lƣợng mẫu tham gia huấn luyện. Bƣớc 2: Phân lớp nhận dạng. Nguyễn Sơn Hà - CT1301 21
  31. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng Dựa vào giá trị các tham số của hàm quyết định thu đƣợc ở Bƣớc 1, một mẫu mới x sau khi đã qua các khâu tiền xử lý và trích chọn đặc trƣng sẽ đƣợc đƣa vào tính tốn thơng qua hàm quyết định để xác định lớp của mẫu x (Hình 2.1). Hình 2.1. Mơ hình nhận dạng chữ viết tay rời rạc. 1.3.5.3. Đánh giá hiệu quả phân lớp SVM SVM là một phƣơng pháp học máy tiên tiến cĩ cơ sở tốn học chặt chẽ và đạt độ chính xác phân lớp cao. Tuy nhiên, hạn chế lớn nhất của SVM là tốc độ phân lớp chậm, tùy thuộc vào số lƣợng vectơ tựa thu đƣợc sau khi huấn luyện. Một hạn chế khác của SVM là pha huấn luyện địi hỏi khơng gian nhớ lớn, vì vậy việc huấn luyện đối với các bài tốn cĩ số lƣợng mẫu lớn sẽ gặp trở ngại trong vấn đề lƣu trữ. Bản chất nhị phân cũng là một hạn chế của SVM, việc mở rộng khả năng của SVM để giải quyết các bài tốn phân loại nhiều lớp là vấn đề khơng đơn giản. Cĩ nhiều chiến lƣợc đƣợc đề xuất để mở rộng SVM cho bài tốn phân loại nhiều lớp với những điểm mạnh, yếu khác nhau tùy thuộc vào từng loại dữ liệu cụ thể. Cho đến nay, việc lựa chọn các chiến lƣợc phân lớp vẫn thƣờng đƣợc tiến hành trên cơ sở thực nghiệm. Bài tốn huấn luyện SVM thực chất là bài tốn qui hoạch tồn phƣơng (QP) trên một tập lồi, do đĩ luơn luơn tồn tại nghiệm tồn cục và duy nhất, đây là điểm khác biệt rõ nhất giữa SVM so với mạng nơ ron, vì mạng nơ ron vốn tồn tại nhiều Nguyễn Sơn Hà - CT1301 22
  32. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng cực trị địa phƣơng. Bản chất của SVM là việc phân lớp đƣợc thực hiện gián tiếp trong khơng gian đặc trƣng với số chiều cao hơn số chiều của khơng gian đầu vào thơng qua hàm nhân. Do đĩ, hiệu quả phân lớp của SVM phụ thuộc vào hai yếu tố: giải bài tốn QP và lựa chọn hàm nhân. Việc giải bài tốn QP luơn luơn đạt đƣợc giải pháp tối ƣu nên mọi cố gắng trong nghiên cứu lý thuyết SVM tập trung vào việc lựa chọn hàm nhân. Lựa chọn hàm nhân và các tham số của nĩ nhƣ thế nào để SVM phân lớp tốt nhất vẫn là một bài tốn mở. Tốc độ phân lớp của SVM bị đánh giá là chậm so với các phƣơng pháp phân lớp khác, tùy thuộc vào số lƣợng vectơ tựa thu đƣợc sau khi huấn luyện. Vì vậy, cĩ nhiều cơng trình tập trung nghiên cứu để giảm tối đa số lƣợng vectơ tựa nhằm tăng tốc độ phân lớp của SVM, một số kết quả nghiên cứu cĩ giá trị về SVM đã đƣợc cơng bố trong các cơng trình . Muốn áp dụng kỹ thuật phân lớp SVM vào bài tốn nhận dạng chữ viết tay tiếng Việt, cần phải cĩ những giải pháp để tránh bùng nổ số phân lớp cũng nhƣ giảm tối đa số vectơ tựa để tăng tốc độ nhận dạng. 1.3.6. Kết hợp các kỹ thuật nhận dạng : Các phần đã trình bày ở trên cho thấy rằng cĩ nhiều phƣơng pháp phân lớp cĩ thể áp dụng đối với các hệ nhận dạng chữ viết tay. Tất cả các phƣơng pháp trên đều cĩ những ƣu điểm và nhƣợc điểm riêng. Vấn đề đặt ra là các phƣơng pháp trên cĩ thể kết hợp với nhau theo một cách nào đĩ để nâng cao chất lƣợng nhận dạng hay khơng? Nhiều cơng trình nghiên cứu kiến trúc phân lớp theo ý tƣởng kết hợp các phƣơng pháp phân lớp đã nêu trên. Các hƣớng tiếp cận kiến trúc kết hợp để phân lớp cĩ thể chia thành ba nhĩm sau: Kiến trúc tuần tự, kiến trúc song song và kiến trúc lai ghép. 1.3.6.1. Kiến trúc tuần tự Kiến trúc này chuyển kết quả đầu ra của một máy phân lớp thành đầu vào của máy phân lớp tiếp theo. Cĩ bốn chiến lƣợc cơ bản đƣợc sử dụng trong kiến trúc tuần tự, đĩ là dãy, chọn lựa, boosting và thác nƣớc. Trong chiến lƣợc về dãy, mục tiêu của mỗi giai đoạn là thu gọn số lớp mà mẫu đầu vào cĩ thể thuộc về các lớp đĩ. Số lớp cĩ thể thu gọn tại mỗi giai đoạn sinh ra nhãn của mẫu ở giai đoạn cuối cùng . Trong chiến lƣợc chọn lựa, đầu tiên máy phân lớp gán mẫu chƣa biết vào một nhĩm ký tự gần giống nhau. Các nhĩm này tiếp tục đƣợc phân lớp ở các giai Nguyễn Sơn Hà - CT1301 23
  33. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng đoạn sau đĩ theo một cây phân cấp. Tại mỗi mức của cây, nhánh con cùng mẹ là giống nhau theo một độ đo nào đĩ. Vì vậy, các máy phân lớp thực hiện phân lớp từ thơ đến tinh dần trong các nhĩm nhỏ . Đối với chiến lƣợc boosting, mỗi máy phân lớp điều khiển một số lớp, các máy phân lớp ở phía trƣớc khơng thể điều khiển đƣợc các lớp của các máy phân lớp ở phía sau . Cuối cùng, trong chiến lƣợc thác nƣớc, các máy phân lớp đƣợc kết nối từ đơn giản đến phức tạp. Các mẫu khơng thỏa mãn ở một mức độ tin cậy nào đĩ thì phải thơng qua một máy phân lớp mạnh hơn trong một giới hạn nào đĩ của các đặc trƣng hoặc các chiến lƣợc nhận dạng khác . 1.3.6.2. Kiến trúc song song Kiến trúc này kết nối kết quả của các thuật tốn phân lớp độc lập bằng cách sử dụng nhiều phƣơng pháp khác nhau. Trong số các kiến trúc này, tiêu biểu nhất là phƣơng pháp bỏ phiếu và luật quyết định Bayes. 1.3.6.3. Kiến trúc lai ghép Kiến trúc này là một sự lai ghép giữa hai kiến trúc tuần tự và song song. Ý tƣởng chính là kết hợp các điểm mạnh của cả hai kiến trúc trên và chặn bớt những khĩ khăn trong việc nhận dạng chữ viết. 1.3.7. Kết luận Chƣơng này đã giới thiệu một cách tổng quan về lĩnh vực nhận dạng chữ viết. Cho đến nay các kết quả nghiên cứu nhận dạng chữ viết tay vẫn cịn hạn chế, các ứng dụng chủ yếu chỉ tập trung ở một số lĩnh vực hẹp. Đặc biệt cĩ rất ít kết quả liên quan đến nhận dạng chữ viết tay tiếng Việt, các kết quả nghiên cứu cũng chỉ tập trung vào chữ Việt viết tay on-line . Cĩ nhiều kỹ thuật tiên tiến đang đƣợc áp dụng cho bài tốn nhận dạng chữ viết tay nhƣ HMM, mạng nơ ron, k-láng giềng gần nhất, luật quyết định Bayes, SVM Trong số các kỹ thuật này thì SVM đƣợc đánh giá là phƣơng pháp cĩ độ chính xác phân lớp cao và phƣơng pháp luận của nĩ đƣợc xây dựng dựa trên một nền tảng tốn học rất chặt chẽ. Nguyễn Sơn Hà - CT1301 24
  34. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng CHƢƠNG 2: TỔNG QUAN VỀ TRÍCH CHỌN ĐẶC TRƢNG VÀ MỘT SỐ PHƢƠNG PHÁP TRÍCH CHỌN ĐẶC TRƢNG TRONG NHẬN DẠNG CHỮ VIẾT 2.1. Trích chọn đặc trƣng Trích chọn đặc trƣng đĩng vai trị cực kỳ quan trọng trong một hệ thống nhận dạng. Trong trƣờng hợp đơn giản nhất, ảnh đa cấp xám hoặc ảnh nhị phân đƣợc sử dụng cho việc nhận dạng. Tuy nhiên, trong hầu hết các hệ nhận dạng, để giảm độ phức tạp và tăng độ chính xác của các thuật tốn phân lớp thì địi hỏi các đặc trƣng đƣợc trích chọn phải rút gọn lại càng nhỏ càng tốt nhƣng vẫn phải đảm bảo đƣợc thơng tin của ký tự. Với mục tiêu này, một tập các đặc trƣng đƣợc trích chọn cho mỗi lớp sao cho cĩ thể phân biệt đƣợc với các lớp khác. Cĩ hàng trăm phƣơng pháp trích chọn đặc trƣng cho ảnh văn bản, nhƣng chung quy lại, các phƣơng pháp này đƣợc gom lại thành ba nhĩm chính sau: 2.1.1. Biến đổi tồn cục và khai triển chuỗi Một tín hiệu liên tục thƣờng chứa nhiều thơng tin và chúng cĩ thể sử dụng làm các đặc trƣng cho mục đích phân lớp. Các đặc trƣng đƣợc trích chọn cũng cĩ thể đúng đối với việc xấp xỉ các tín hiệu liên tục thành các tín hiệu rời rạc. Một cách để biểu diễn một tín hiệu là sử dụng một tổ hợp tuyến tính của một dãy các hàm đơn giản hơn. Các hệ số của tổ hợp tuyến tính cung cấp một tri thức giải mã vừa đủ, chẳng hạn nhƣ các phép biến đổi hoặc khai triển chuỗi. Một số biến dạng khác nhƣ các phép dịch chuyển và phép quay là bất biến dƣới các phép biến đổi tồn cục và khai triển chuỗi. Sau đây là một số phƣơng pháp biến đổi và khai triển chuỗi thƣờng đƣợc áp dụng trong lĩnh vực nhận dạng chữ: Biến đổi Fourier: Một trong những tính chất nổi bật nhất của phép biến đổi Fourier là khả năng nhận dạng các ký tự cĩ sự thay đổi về các tƣ thế khác nhau, các phép biến đổi này đã đƣợc áp dụng để nhận dạng ký tự theo nhiều cách khác nhau . Biến đổi Wavelet: Phép biến đổi này là một dãy các kỹ thuật khai triển cho phép mơ tả đặc trƣng của ảnh ở các mức độ khác nhau. Các cơng đoạn tách chữ Nguyễn Sơn Hà - CT1301 25
  35. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng thành các ký tự hoặc từ đƣợc mơ tả bằng các hệ số wavelet theo các mức độ khác nhau đối với từng giải pháp. Sau đĩ các hệ số wavelet đƣợc chuyển qua một máy phân lớp để phục vụ cho việc nhận dạng . Phƣơng pháp mơ men: Theo phƣơng pháp này, ảnh gốc sẽ đƣợc thay thế bằng một tập các đặc trƣng vừa đủ của để nhận dạng các đối tƣợng bất biến đối với các phép thay đổi tỷ lệ, tịnh tiến hoặc quay. Các mơ men đƣợc xét nhƣ các dãy khai triển đặc trƣng vì ảnh gốc cĩ thể xây dựng lại một cách đầy đủ từ các hệ số mơ men. Khai triển Karhunent-Loeve: Việc khai triển này nhằm phân tích các véc tơ riêng để rút gọn số chiều của tập đặc trƣng bằng cách tạo ra các đặc trƣng mới là tổ hợp tuyến tính của các đặc trƣng gốc. Đây chỉ là một phép biến đổi tối ƣu trong một số giới hạn nào đĩ của việc nén thơng tin. Khai triển Karhunent-Loeve đƣợc dùng trong một số bài tốn nhận dạng mẫu nhƣ nhận dạng mặt ngƣời, nĩ cũng đƣợc sử dụng trong hệ thống OCR của Viện Cơng nghệ và Tiêu chuẩn Quốc gia Hoa Kỳ (NIST – National Institute of Standards and Technology of the United States). Vì việc khai triển này địi hỏi phải sử dụng các thuật tốn cĩ khối lƣợng tính tốn rất lớn nên việc sử dụng các đặc trƣng Karhunent-Loeve trong các bài tốn nhận dạng chữ khơng đƣợc phổ biến rộng rãi. Tuy nhiên, để tăng tốc độ tính tốn cho các máy phân lớp, các đặc trƣng này trở nên thiết thực hơn cho các hệ nhận dạng chữ trong những năm gần đây. 2.1.2. Đặc trƣng thống kê Các đặc trƣng thống kê của ảnh văn bản bảo tồn các kiểu biến đổi đa dạng về hình dáng của chữ. Mặc dù các kiểu đặc trƣng này khơng thể xây dựng lại ảnh gốc, nhƣng nĩ đƣợc sử dụng để thu nhỏ số chiều của tập đặc trƣng nhằm tăng tốc độ và giảm thiểu độ phức tạp tính tốn. Sau đây là một số đặc trƣng thống kê thƣờng dùng để biểu diễn ảnh ký tự: Phân vùng (zoning): Khung chứa ký tự đƣợc chia thành một vài vùng chồng nhau hoặc khơng chồng nhau. Mậc độ của các điểm ảnh trong các vùng khác nhau đƣợc phân tích và tạo thành các đặc trƣng . Nguyễn Sơn Hà - CT1301 26
  36. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng Các giao điểm và khoảng cách: Một đặc trƣng thống kê phổ biến là số giao điểm giữa chu tuyến của chữ với một đƣờng thẳng theo một hƣớng đặc biệt nào đĩ. Các phép chiếu: Các ký tự cĩ thể đƣợc biểu diễn bằng cách chiếu các giá trị mức xám của từng điểm lên trên các dịng theo các hƣớng khác nhau. Các đặc trƣng này tạo ra dãy tín hiệu một chiều từ ảnh hai chiều . Đặc trƣng hƣớng: Các ký tự bao gồm các nét chữ, các nét này là các đoạn thẳng cĩ hƣớng, các cung hoặc các đƣờng cong. Hƣớng của các nét đĩng vai trị quan trọng trong việc so sánh sự khác nhau giữa các ký tự. Các ký tự đƣợc mơ tả nhƣ các véc tơ mà các phần tử của nĩ là các giá trị thống kê về hƣớng. Để trích chọn các đặc trƣng này, gĩc định hƣớng của nét chữ phải đƣợc phân chia thành một số vùng cố định và số các đoạn của nét chữ trong mỗi vùng gĩc đƣợc chọn nhƣ một giá trị đặc trƣng. Vì vậy, tập các số lƣợng của các đoạn định hƣớng sẽ tạo thành một biểu đồ đƣợc gọi là biểu đồ hƣớng và các đặc trƣng về biểu đồ hƣớng cĩ thể gọi chung là đặc trƣng hƣớng. Các ảnh ký tự đƣợc phân rã thành các mặt phẳng định hƣớng và một độ đo khoảng cách đƣợc tính giữa các mặt phẳng đĩ với mẫu của mỗi lớp. Hƣớng nét chữ cục bộ của một ký tự cĩ thể đƣợc xác định bằng nhiều cách khác nhau: hƣớng của xƣơng, phân đoạn nét chữ, mã hĩa chu tuyến, hƣớng đạo hàm . Hiện nay, các đặc trƣng mã hĩa chu tuyến và hƣớng đạo hàm đƣợc áp dụng rộng rãi vì chúng dễ cài đặt và xấp xỉ bất biến với sự biến đổi đa dạng của các nét chữ. 2.1.3. Đặc trƣng hình học và hình thái Các tính chất cục bộ và tồn cục khác nhau của các ký tự cĩ thể đƣợc biểu diễn bằng các đặc trƣng hình học và hình thái. Các kiểu đặc trƣng này cũng cĩ thể giải mã một số tri thức về cấu trúc của đối tƣợng ảnh hoặc cĩ thể cung cấp một số tri thức nhƣ sắp xếp các thành phần để tạo ra đối tƣợng. Các loại đặc trƣng này cĩ thể phân thành các nhĩm sau: Trích chọn và đếm các cấu trúc hình thái: trong nhĩm đặc trƣng này, một cấu trúc đã xác định đƣợc tìm kiếm trong một ký tự hoặc một từ. Số lƣợng vị trí hoặc quan hệ vị trí của các cấu trúc trong ký tự này tạo thành các đặc trƣng biểu diễn ký tự. Thơng thƣờng, các cấu trúc nguyên thủy (các đoạn thẳng, các cung) là các nét tạo ra ký tự. Các ký tự và các từ cĩ thể đƣợc mơ tả bằng cách trích chọn và đếm nhiều loại đặc trƣng về hình thái nhƣ các điểm cực đại và cực tiểu, các điểm chĩp trên và chop dƣới của một ngƣỡng nào đĩ, mở rộng cho các điểm trái, phải, trên, Nguyễn Sơn Hà - CT1301 27
  37. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng dƣới và các giao điểm, các điểm nhánh, điểm cuối đoạn thẳng, hƣớng của một nét từ một điểm đặc biệt, các điểm cơ lập đã tạo nên các ký tự . Đo và xấp xỉ các tính chất hình học: Trong nhiều cơng trình nghiên cứu , các ký tự đƣợc biểu diễn bằng độ đo của các đại lƣợng hình học nhƣ tỷ số giữa chiều rộng và chiều cao của hộp chứa ký tự, quan hệ khoảng cách giữa hai điểm, so sánh độ dài giữa hai nét, độ rộng của một nét, khối lƣợng chữ hoa và chữ thƣờng của các từ, độ dài từ. Một độ đo tiêu biểu rất quan trọng nữa là độ cong hoặc thay đổi độ cong . Các đại lƣợng hình học đo đƣợc cĩ thể xấp xỉ bởi một tập các đặc trƣng hình học vừa đủ và thuận tiện hơn . Đồ thị và cây: Đầu tiên, các từ hoặc các ký tự đƣợc phân chia thành một tập các đối tƣợng nguyên thủy nhƣ các nét, các điểm chạc Sau đĩ, các thành phần nguyên thủy đƣợc thay thế bằng các thuộc tính hoặc các đồ thị liên quan . Cĩ hai loại đặc trƣng ảnh đƣợc mơ tả bằng đồ thị. Loại thứ nhất sử dụng các tọa độ của hình dáng ký tự . Loại thứ hai là một đặc trƣng trừu tƣợng, các nút của đồ thị tƣơng ứng với các nét chữ và các cạnh của đồ thị tƣơng ứng với các mối quan hệ giữa các nét chữ . Cây cũng cĩ thể dùng để biểu diễn các từ và các ký tự với một tập các đặc trƣng theo một quan hệ phân cấp . Trích chọn đặc trƣng hầu hết đƣợc thực hiện trên ảnh nhị phân. Tuy nhiên, việc nhị phân hĩa ảnh đa cấp xám cĩ thể xĩa đi một số thơng tin quan trọng của các ký tự. Trong trƣờng hợp này, cũng cĩ một số cơng trình nghiên cứu để trích chọn các đặc trƣng trực tiếp từ các ảnh đa cấp xám . Cuối cùng, mục đích chính của việc trích chọn đặc trƣng là lựa chọn một tập đặc trƣng phục vụ cho việc phân lớp sao cho hệ thống nhận dạng đạt độ chính xác cao nhất với số lƣợng phần tử đƣợc trích chọn ít nhất. Luận án chỉ tập trung nghiên cứu một số đặc trƣng thống kê và đặc trƣng wavelet cho bài tốn nhận dạng chữ Việt viết tay rời rạc. 2.2. Đặc trƣng bất biến Để nhận ra nhiều biến thể của cùng một đối tƣợng, tính năng là bất biến cho một số biến đổi trên các đối tƣợng cần phải đƣợc sử dụng. Bất biến là các tính năng cĩ giá trị xấp xỉ nhƣ nhau, Ví dụ:dịch, thu nhỏ, xoay, kéo dài, sai lệch hoặc nhân đơi .Tuy nhiên, khơng phải tất cả các biến thể giữa các đối tƣợng trong cùng một lớp(ví dụ: tiếng ồn, suy thối và sự vắng mặt hay hiện diện của serifs) cĩ thể đƣợc mơ hình sử dụng bất biến. Kích thƣớc và bất biến dịch cĩ thể dễ dàng đạt đƣợc. Việc phân Nguyễn Sơn Hà - CT1301 28
  38. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng định các đặc điểm cá nhân cĩ thể tự cung cấp các ƣớc tính về kích thƣớc và vị trí, nhƣng các tính năng phƣơng pháp khai thác thƣờng cĩ thể cung cấp chính xác hơn ƣớc tính. Quay bất biến là quan trọng nếu các đối tƣợng đƣợc cơng nhận cĩ thể xảy ra trong định hƣớng bất kỳ. Tuy nhiên,nếu tất cả các đối tƣợng đƣợc dự kiến sẽ cĩ cùng luân chuyển, sau đĩ tính năng quay biến thể nên đƣợc sử dụng để phân biệt giữa các ký tự nhƣ "6" và "9", và "n" và "u". Một lựa chọn khác là sử dụng tính năng bất biến, thêm vào các phát hiện rota-gĩc hĩa. Nếu gĩc quay bị hạn chế giữa - 45 và 45 °, các đối tƣợng đĩ, nĩi 180 °quay của nhau cĩ thể đƣợc phân biệt.cùng nguyên tắc cĩ thể đƣợc sử dụng cho các tính năng kích thƣớc bất biến, nếu một muốn nhận dấu chấm câu ngồi nhân vật và muốn phân biệt giữa, nĩi rằng, ".""o" và "O", và "," và "9". 2.3. Khả năng khơi phục Đối với một số phƣơng pháp , khơi phục lại chính xác cĩ thể yêu cầu một số lƣợng lớn tính năng, xấp xỉ hợp lý của hình dạng đối tƣợng ban đầu thƣờng cĩ thể thu đƣợc bằng cách chỉ sử dụng một số lƣợng nhỏ các tính năng với mức cao nhất nội dung thơng tin . Hy vọng là các tính năng này cũng cĩ quyền phân biệt đối xử cao . Bởi khơi phục lại hình ảnh trong tính năng trích xuất, một trực quan cĩ thể kiểm tra xem một số tính năng đƣợc sử dụng để nắm bắt đƣợc cơ bản cấu trúc của các đối tƣợng. Khơi phục cũng cĩ thể đƣợc sử dụng để kiểm sốt chính thức rằng việc thực hiện là chính xác hay khơng. 2.4. Trích chọn đặc trƣng từ ảnh đa cấp xám 2.4.1. Giới thiệu Một thách thức lớn trong phƣơng pháp này là xác định vị trí,địa điểm của đối tƣợng.Ngƣời ta cĩ thể sử dụng một phƣơng pháp thích ứng để cĩ đƣợc một hình ảnh nhị phân tốt và sử dụng kết nối thành phần của kích thƣớc đối tƣợng dự kiến để xác định vị trí đối tƣợng cần xác định. Tuy nhiên, phƣơng pháp này thƣờng đƣợc sử dụng khi cơng nhận dựa trên ảnh nhị phân đại diện, do đĩ vấn đề vẫn chƣa đƣợc giải quyết cho những hình ảnh khĩ. Ngƣời ta cĩ thể phải dùng đến phƣơng pháp tiếp cận tất cả các địa điểm cĩ thể trong hình ảnh. Tuy nhiên, sau đĩ ngƣời ta phải giả định một kích thƣớc tiêu chuẩn cho một hình ảnh, là sự kết hợp của tất cả các kích thƣớc các đối tƣợng cần xác định và địa điểm dựa trên sự tính tốn. Cách tiếp cận khơng thể đƣợc sử dụng nếu kích thƣớc đối tƣợng dự kiến thay đổi. Nguyễn Sơn Hà - CT1301 29
  39. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng 2.4.2. Đối sánh mẫu Chúng ta khơng nhận thức đƣợc hệ thống OCR sử dụng mẫu phù hợp với hình ảnh xám. Tuy nhiên, kể từ khi mẫu phù hợp là một hình ảnh khá chuẩn kỹ thuật xử lý, chúng ta đã bao gồm hồn chỉnh. Trong mẫu phù hợp với các bƣớc tính năng khai thác đƣợc bỏ hồn tồn và hình ảnh chính đƣợc sử dụng nhƣ là một "vector". Trong giai đoạn cơng nhận, một biện pháp giữa các mẫu TJ và hình ảnh Z đƣợc tính tốn. Các thơng số Tk, trong đĩ cĩ các biện pháp tƣơng tự cao nhất, là xác định và nếu sự tƣơng đồng này là trên một quy định ngƣỡng, sau đĩ các hình ảnh đƣợc gán nhãn lớp k. Ngƣợc lại, các nhân vật cịn lại khơng đƣợc phân loại. Trong trƣờng hợp một biện pháp đồng dạng, mẫu T k cĩ biện pháp đồng dạng thấp nhất đƣợc xác định và nếu dƣới mức quy định, các đối tƣợng đƣợc dán lớp nhãn k. 2.4.3. Mẫu biến dạng Mẫu biến dạng đã đƣợc sử dụng rộng rãi trong nhiều cơng nhận đối tƣợng. Các mẫu đƣợc sử dụng là bộ xƣơng nhân vật. Nĩ khơng phải là rõ ràng cách vị trí ban đầu của các mẫu đƣợc chọn. Nếu tất cả các vị trí cĩ thể cĩ trong các hình ảnh đã đƣợc xét xử, thì thời gian tính tốn sẽ đƣợc ngăn cấm. 2.4.4. Biến đổi ảnh Unitar Trong mẫu phù hợp, tất cả các điểm ảnh trong hình ảnh xám đƣợc sử dụng nhƣ một biến đổi Unitar để hình ảnh giảm về số lƣợng các tính năng trong khi bảo quản hầu hết các thơng tin về hình dạng . Trong khoảng thời gian chuyển đổi, các điểm ảnh đƣợc sắp xếp và các điểm ảnh với mức cao nhất đƣợc sử dụng nhƣ tính năng . Biến đổi Unitar phải đƣợc áp dụng để cĩ đƣợc ƣớc tính của phƣơng sai của các điểm ảnh trong khơng gian chuyển đổi. Các tính năng đƣợc lấy từ biến đổi Unitar là khơng bất biến , vì vậy những hình ảnh đầu vào phải đƣợc luân chuyển đến một định hƣớng tiêu chuẩn nếu xoay ký tự cĩ thể xảy ra . Hơn nữa, những hình ảnh đầu vào cĩ đƣợc chính xác kích thƣớc tƣơng tự , do đĩ, một rộng hoặc tái lấy mẫu là cần thiết nếu kích thƣớc cĩ thể khác nhau . các đơn nhất biến đổi là khơng chiếu sáng bất biến , nhƣng đối với các Fourier chuyển đổi hình ảnh giá trị tại gốc là tỷ lệ thuận với giá trị điểm ảnh trung bình của đầu vào hình ảnh , do đĩ tính năng này cĩ thể bị xĩa để cĩ đƣợc sang Ness bất biến . Cho tất cả các biến đổi đơn nhất , một nghịch đảo chuyển đổi tồn tại , vì vậy hình ảnh nhân vật ban đầu cĩ thể đƣợc xây dựng lại. Nguyễn Sơn Hà - CT1301 30
  40. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng 2.4.5. Bất biến Zenite Zernike khoảnh khắc đã đƣợc sử dụng bởi một số tác giả cho nhận dạng ký tự nhị phân rắn ký tự. 2.5. Trích chọn đặc trƣng từ ảnh nhị phân: 2.5.1. Giới thiệu Một ảnh raster nhị phân thu đƣợc bằng một hoặc tồn cầu binarization địa phƣơng thích nghi của đầu vào hình ảnh xám . Trong nhiều trƣờng hợp ,các phân đoạn của đối tƣợng là thực hiện chỉ đơn giản bằng cách cách ly các thành phần đƣợc kết nối. Tuy nhiên , cho hình ảnh khĩ khăn, một số đối tƣợng cĩ thể chạm vào hoặc chồng chéo nhau đối tƣợng in khác hoặc khác . Một vấn đề khác xảy ra khi đối tƣợng đƣợc phân mảnh thành hai hoặc nhiều thành phần đƣợc kết nối, vấn đề cĩ thể đƣợc giảm nhẹ phần nào bằng cách chọn một phƣơng pháp thích nghi tốt hơn , nhƣng Trier và Taxt đã chỉ ra rằng ngay cả tốt nhất phƣơng pháp binarization địa phƣơng thích ứng cĩ thể vẫn cịn khơng dẫn đến đối tƣợng bị cơ lập hồn tồn . Phƣơng pháp phân đoạn đối tƣợng cảm động là do Westall và Narasimha ,Fujisawa và trong các cuộc điều tra .Tuy nhiên , các phƣơng pháp giả định rằng các đối tƣợng xuất hiện trong chuỗi cùng nội dung và cĩ định hƣớng đƣợc biết đến . Trong bản đồ thủy văn) , ví dụ, một số đối tƣợng chạm vào hoặc chồng chéo lên nhau đƣờng , hoặc các ký tự liên lạc từ một dịng văn bản . Một phƣơng pháp dựa trên xám đƣợc tích hợp và phân khúc . Phƣơng pháp này cho một tốt hơn hiệu suất, kể từ khi thơng tin thu đƣợc trong topo - bƣớc phân tích đồ họa đƣợc sử dụng trong phân chia các ảnh nhị phân . Bƣớc phân khúc cũng xử lý xoay đối tƣợng và đối tƣợng chạm vào từ văn bản khác nhau dây . Đại diện raster nhị phân của một đối tƣợng là đơn giản hĩa của các đại diện xám . các chức năng chụp ảnh Z ( x, y) bây giờ cĩ trên hai giá trị ( nĩi , 0 và 1) thay vì , nĩi 256 giá trị màu xám cấp . này cĩ nghĩa là tất cả các phƣơng pháp phát triển cho màu xám - đại diện quy mơ đƣợc áp dụng cho các nhị phân rắn raster đại diện là tốt. Vì vậy , chúng ta sẽ khơng lặp lại mơ tả đầy đủ của mỗi phƣơng pháp , nhƣng chỉ chỉ ra sự đơn giản hĩa trong các tính tốn trong volved cho mỗi phƣơng pháp khai thác tính năng này. Nĩi chung , bất biến để chiếu sáng khơng cịn phù hợp , nhƣng các invariances khác .Một ảnh nhị phân rắn cĩ thể đƣợc chuyển đổi sang khác cơ quan đại diện , chẳng hạn nhƣ các đƣờng viền ngồi của char bộ phận cơng tác , các cấu hình đƣờng viền , hoặc các bộ xƣơng và tính năng cĩ thể đƣợc chiết xuất từ một trong các đại diện là tốt. Với mục đích thiết kế Nguyễn Sơn Hà - CT1301 31
  41. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng OCR hệ thống , mục tiêu của việc chuyển đổi này là để bảo vệ thơng tin liên quan về các hình và loại bỏ một số thơng tin khơng cần thiết. 2.5.2. Biến đổi ảnh Unitar NIST dựa trên hình thức hệ thống nhận dạng tay-in sử dụng Karhunen-Loeve chuyển đổi để trích xuất các tính năng từ các đại diện raster nhị phân. Hiệu quả của nĩ là tuyên bố đƣợc tốt, và hệ thống OCR này cĩ sẵn trong phạm vi cơng cộng . 2.5.3. Bất biến hình học Một hình ảnh nhị phân cĩ thể đƣợc coi là một trƣờng hợp đặc biệt một hình ảnh màu xám cấp với Z (x, y) = 1 cho các điểm ảnh và in ấn Z (zi, Yl) = 0 cho các điểm ảnh nền. 2.6. Trích chọn đặc trƣng từ biên ảnh: 2.6.1. Giới thiệu Đƣờng cong đƣờng viền bên ngồi khép kín của một ảnh là một đƣờng cong tuyến tính piecewise khép kín đi qua trung tâm của tất cả các điểm ảnh mà bốn kết nối đến bên ngồi nền và khơng cĩ điểm ảnh khác. Sau đƣờng cong, các điểm ảnh đƣợc truy cập trong, nĩi, ngƣợc kim đồng hồ trật tự và đƣờng cong cĩ thể truy cập vào một điểm ảnh cạnh hai lần địa điểm mà đối tƣợng là rộng một điểm ảnh. mỗi dịng bộ phận là một đƣờng thẳng từ tâm điểm ảnh tới 8 láng giêng. 2.6.2. Tách vùng Kimura và Shridhar đƣợc sử dụng phân vùng trên đƣờng viền đƣờng cong. Trong mỗi khu vực, các phân đoạn đƣờng đồng mức đƣợc- tween pixel lân cận đã đƣợc nhĩm lại theo định hƣớng: ngang (0 °), thẳng đứng (90 °) và hai đƣờng chéo định hƣớng (45, 135 °). Số đoạn đƣờng mỗi định hƣớng đƣợc tính . Takahashi cũng đƣợc sử dụng biểu đồ định hƣớng từ khu vực, nhƣng sử dụng theo chiều dọc, ngang và đƣờng chéo lát nhƣ khu vực thêm vào bên ngồi đƣờng viền khi thực hiện các biểu đồ. Hơn nữa, Takahashi xác định điểm cong cao dọc theo hai đƣờng viền bên ngồi và bên trong. Đối với mỗi điểm, giá trị độ cong, tiếp tuyến đƣờng viền và vị trí của khu, điểm đƣợc trích xuất. thời gian này một mạng lƣới thƣờng xuyên đƣợc sử dụng nhƣ khu vực. Khi các đƣờng cong đƣờng viền là gần với biên giới khu vực, sự thay đổi nhỏ trong các đƣờng viền cong cĩ thể dẫn đến sự thay đổi lớn trong các khai thác các tính năng. Họ đã cố gắng để bù đắp cho điều này bằng cách sử dụng biên giới mờ. Điểm gần biên giới khu vực là cho Nguyễn Sơn Hà - CT1301 32
  42. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng các giá trị thành viên mờ để hai hoặc bốn khu vực và các thành viên mờ giá trị số tiền cho một . 2.6.3. Xấp xỉ đƣờng cong: Trên các đƣờng viền nhân vật bên ngồi và áp gần đúng đƣờng cong giữa hai điểm dừng với một chức năng . Sau đĩ , cả hai Đƣờng cong và các thơng số đƣờng cong đƣợc sử dụng nhƣ các tính năng . Xấp xỉ đƣờng cong đƣờng viền bên ngồi với một đƣờng cong spline, mà sau đĩ đƣợc làm nhẵn. các trơn spline đƣờng cong đƣợc chia thành các phần bằng nhau M -chiều dài đƣờng cong . Đối với mỗi phần , độ cong trung bình đƣợc tính bằng cơng thức xác định . Ngồi ra, khoảng cách từ arithme - tic nghĩa của điểm uốn cong để N nhƣ nhau điểm khoảng cách đều nhau trên các đƣờng viền đƣợc đo . bằng cách nhân rộng spline đƣờng cong xấp xỉ của nhân vật để một tiêu - kích thƣớc Sở NN & PTNT trƣớc khi tính năng này đƣợc đánh giá , các tính năng sẽ trở thành kích thƣớc bất biến. Các tính năng đã dịch bất biến của tự nhiên, nhƣng phụ thuộc vào quay. 2.6.4. Mơ tả Fourier: Trƣớc khi Kuhl ,Giardina và Lin và Hwang, mơ tả Fourier khác đã đƣợc phát triển bởi Zahn ,Roskies và Granlund. .Trong Zahn và Roskies ,các gĩc cạnh khác nhau-là 1 nghiệm . 2.7. Trích chọn đặc trƣng từ biểu diễn véc tơ: 2.7.1. Giới thiệu Một số lƣợng áp đảo của các thuật tốn mỏng tồn tại và một số nghiên cứu đánh giá gần đây cho manh mối để họ giá trị và bất lợi. Nhiệm vụ của một trong những quyền thƣờng liên quan đến một sự thỏa hiệp , một muốn một điểm ảnh rộng bộ xƣơng tám kết nối với chi nhánh giả hoặc các nút di dời , một số loại mạnh mẽ để luân chuyển và tiếng ồn và tại đồng thời một nhanh chĩng và dễ dàng thực hiện các thuật tốn mỏng dƣờng nhƣ là một ứng cử viên tốt, mặc dù thực hiện của nĩ là một việc phức tạp . Một biểu đồ đối tƣợng cĩ thể đƣợc bắt nguồn từ các bộ xƣơng bởi nĩ xấp xỉ với một số đƣờng thẳng phân đoạn và các điểm giao nhau . Vịng cung cĩ thể đƣợc sử dụng cho phần cong của bộ xƣơng . Nguyễn Sơn Hà - CT1301 33
  43. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng Phƣơng pháp này rất hữu ích khi thậm chí tốt nhất cĩ sẵn phƣơng pháp khơng thể bảo tồn hình dạng bộ phận làm việc trong các hình ảnh. 2.7.2. Đối sánh mẫu Mẫu phù hợp ở dạng tinh khiết của nĩ rất khơng phù hợp cho bộ xƣơng đối tƣợngvật, vì rất cĩ thể là nhỏ 2.7.3. Mẫu biến dạng Mẫu biến dạng đã đƣợc sử dụng bởi Burr và Wakahara cơng nhận nhân vật skel - etons . Trong cách tiếp cận Wakahara , mỗi mẫu là de - hình thành trong một số bƣớc nhỏ , đƣợc gọi là affine địa phƣơng biến đổi ( LAT ) để phù hợp với mơ hình đầu vào ứng cử viên Số lƣợng và kiểu chuyển đổi trƣớc khi trận đấu thu đƣợc cĩ thể đƣợc sử dụng nhƣ một khơng giống nhau - biện pháp ity giữa các bản mẫu và các đầu vào mẫu . 2.7.4. Đặc trƣng rời rạc Từ các nhân vật mỏng , các tính năng sau đây cĩ thể đƣợc trích xuất: < 1,82 s số lƣợng của các vịng , số lƣợng T- khớp , số lƣợng X - khớp , số lƣợng uốn cong điểm, chiều rộng và chiều cao của tỷ lệ kèm theo hình chữ nhật ;sự hiện diện của một dấu chấm bị cơ lập , tổng số lƣợng thiết bị đầu cuối và số lƣợng thiết bị đầu cuối trong mỗi bốn hƣớng N , S , W và E , số lƣợng bán vịng trịn trong mỗi bốn hƣớng , và số lƣợng các giao cắt theo chiều dọc và trục ngang , tƣơng ứng, các trục đặt trên các trung tâm của lực hấp dẫn .Ngƣời ta cĩ thể sử dụng giao cắt với nhiều chồng dịng nhƣ tính năng , và trong thực tế , điều này đã đƣợc thực hiện trong đầu OCR hệ thống , tl ) Tuy nhiên , các tính năng này một mình làm khơng dẫn đến hệ thống nhận dạng mạnh mẽ , nhƣ số lƣợng dịng chồng đƣợc tăng lên, các tính năng kết quả ít mạnh mẽ với sự thay đổi trong các phơng chữ ( dùng cho máy ký tự in ) và biến đổi trong hình dạng nhân vật và văn bản phong cách (ký tự viết tay ) 2.7.5. Biểu diễn Fourier Các phƣơng pháp mơ tả Fourier cho đƣờng nét nhân vật cũng cĩ thể sử dụng cho bộ xƣơng nhân vật hoặc đồ thị nhân vật , kể từ bộ xƣơng hoặc đồ thị cĩ thể đƣợc đi qua để tạo thành một đƣờng cong đĩng cửa ,nhấn mạnh các biểu đồ nhân vật với hai dịng kết thúc , khơng cĩ các nút và khơng cĩ vịng, , trong khi đối với đồ thị với các nút giao hoặc vịng, tất cả các mơ tả sẽ cĩ giá trị khác khơng . Nguyễn Sơn Hà - CT1301 34
  44. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng Các đặc tính cho phép quay và kích thƣớc bất biến tính năng này cũng đã đƣợc tìm thấy , trƣờng hợp của cùng một nhân vật mà xảy ra đƣợc khác nhau đối với các loại trên với sẽ cĩ đƣợc vector tính năng rất khác nhau . Giải pháp là trƣớc khi phân loại các đồ thị ký tự vào một trong ba loại và sau đĩ sử dụng một phân loại riêng cho từng loại . Nguyễn Sơn Hà - CT1301 35
  45. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng CHƢƠNG 3: CHƢƠNG TRÌNH THỬ NGHIỆM 3.1. Giới thiệu Trong luận văn này do hạn chế về mặt thời gian và độ phức tạp của nhận dạng chữ viết tay tiếng Việt cho nên chỉ hạn chế mơ phỏng nhận dạng ký tự viết tay tiếng Việt rời rạc trực tuyến. Các ký tự tiếng Việt gồm ký tự khơng dấu {A, B, C, D, Đ, E, G, H, I, K, L, M, N, O, P, Q, R, S, T, U, V, X, Y} và ký tự cĩ dấu {Ă, Â, À, Ả, Ã, Á, Ạ, Ằ, Ẳ, Ẵ, Ắ, Ặ, Ầ, Ẩ, Ẫ, Ấ, Ậ, Ê, È, Ẻ, Ẽ, É, Ẹ, Ề, Ể, Ễ, Ế, Ệ, Ì, Ỉ, Ĩ, Í, Ị, Ơ, Ơ, Õ, Ỏ, Õ, Ĩ, Ọ, Ồ, Ổ, Ỗ, Ố, Ộ, Ờ, Ở, Ỡ, Ớ, Ợ, Ƣ, Ù, Ủ, Ũ, Ư, Ụ, Ừ, Ử, Ữ, Ứ, Ự, Ỳ, Ỷ, Ỹ, Ý, Ỳ}. Chƣơng trình này cĩ thể nhận dạng ký tự viết tay do ngƣời sử dụng vẽ chúng, chức năng này tƣơng tự nhƣ nhận dạng ký tự viết tay sử dụng các thiết bị cầm tay PDA (Personal Digital Assistant ). Chƣơng trình gồm một giao diện đơn giản cho phép ngƣời sử dụng dùng chuột vẽ ký tự cần nhận dạng và tiến hành nhận dạng. Khi vẽ ký tự cĩ một hình chữ nhật xung quanh ký tự đĩ.Mục đích của hình chữ nhật này là để cắt bất kỳ khoảng trắng nào khơng liên quan đến ký tự làm cho chƣơng trình cĩ khả năng khơng cần quan tâm đến vị trí của ký tự đƣợc viết. Ta cĩ thể vẽ ký tự ở giữa, trên, dƣới hay bất kỳ một vị trí khác nhƣng chƣơng trình vẫn cĩ khả năng nhận dạng đúng. Các bƣớc giải quyết bài tốn sử dụng trích chọn đặc trƣng nhận dạng chữ viết: - Xây dựng giao diện vẽ. - Xử lý dữ liệu (phân tích ảnh). - Xây dựng Chƣơng trình - Nhận dạng chữ viết 3.2. Xây dựng giao diện vẽ - Xây dựng một giao diện đồ họa, cho phép ngƣời sử dụng dùng chuột vẽ ký tự cần nhận dạng. Nguyễn Sơn Hà - CT1301 36
  46. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng - Tìm giới hạn trên, giới hạn dƣới, trái, phải của ký tự sau khi đƣợc vẽ. - Cắt bỏ tất cả các khoảng trắng xung quanh ký tự đƣợc vẽ thu đƣợc ảnh chỉ cĩ hồn tồn ký tự. Nhƣ thế quy về xử lý ảnh chỉ cĩ mỗi ký tự, khơng quan tâm ký tự đƣợc vẽ ở vị trí nào: bên trên hay dƣới, bên trái hay bên phải Hình 2.2 Quá trình tìm giới hạn ký tự - Thực hiện lấy mẫu xuống ảnh của ký tự bằng cách ánh xạ ký tự vào một lƣới cĩ kích thƣớc 10*10. Bằng cách này ta quy ký tự về một kích thƣớc cố định, nhƣ vậy khơng cần quan tâm đến kích thƣớc ký tự đƣợc vẽ vào là to hay nhỏ. Hình 2.3 Quá trình lấy mẫu xuống 3.3. Xử lý dữ liệu (phân tích ảnh) Quá trình phân tích ảnh là quá trình tìm ra đặc tính của ký tự.Các điểm ảnh này chính là giá trị đầu vào cho cả quá trình huấn luyện và quá trình kiểm tra. Quá trình phân tích này dựa trên việc nhận dạng từ ảnh ngƣời sử dụng vẽ vào bằng Nguyễn Sơn Hà - CT1301 37
  47. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng phƣơng pháp tìm các điểm đen RGB(0,0,0) hoặc điểm trắng RGB(255,255,255). Kết quả thu đƣợc là ma trận điểm ảnh. Sau đĩ ma trận này sẽ đƣợc ánh xạ thành vector đầu vào cĩ kích thƣớc 100 phần tử.Trƣớc khi đƣa vào mạng vector này cịn đƣợc xử lý làm nổi điểm ảnh thành vector gồm các phần tử 0.5 và -0.5. Hình 2.4. Quá trình ánh xạ từ ma trận điểm sang ma trận giá trị - Ký tự: Chứa các chữ mẫu dùng để trích chọn - Giá trị: Lƣu trữ giá trị các chữ mẫu dùng để trích chọn - Nhận dạng: Vùng để vẽ chữ lên. - Tập mẫu: Chứa các chữ mẫu dùng để trích chọn. - Tải mẫu: Tải tập chữ mẫu đã tạo sẵn trong file: TapMau.xml - Thêm chữ: Ghi lại tập chữ mẫu vào file: TapMau.xml - Trích chọn đặc trƣng:Trích chọn đặc trƣng trọng số vùng chữ viết - Xĩa chữ: Xĩa một chữ mẫu đƣợc chọn ra khỏi file TapMau.xml - Nhận dạng: Nhận dạng chữ vẽ vào. - Thơng tin: Giới thiệu sơ bộ về chƣơng trình Chúng ta cĩ thể tải tập chữ ra từ file tạo sẵn TapMau.xml bằng cách nhấn nút “Tải mẫu” hoặc chúng ta cĩ thể tự nhập mẫu để trích chọn bằng cách vẽ chữ vào vùng vẽ ký tự rồi nhấn “Thêm chữ”, khi đĩ cĩ một hộp thoại nhắc bạn đánh vào chữ tƣơng ứng để khi nhận dạng nĩ sẽ chỉ ra chữ tƣơng ứng với chữ vừa vẽ. Nguyễn Sơn Hà - CT1301 38
  48. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng Sau khi nhập xong tập mẫu thì nhấn nút “Trích chọn đặc trƣng”. Quá trình trích chọn hồn thành, cĩ thể thực hiện nhận dạng chữ bằng cách vẽ chữ rồi nhấn “Nhận dạng”. Khi đĩ chữ đƣợc hiển thị trên lƣới kích thƣớc 10*10. Cĩ thể xĩa chữ hoặc xĩa mẫu trong tập mẫu bằng cách chọn chữ cần xĩa rồi nhấn nút “Xĩa chữ”. 3.4. Kết quả nhận dạng - Để nhận dạng chữ ta vẽ chữ cần nhận dạng vào vùng vẽ chữ (vùng chữ nhật màu trắng, ngay bên dƣới phần “Nhận dạng”). - Ký tự đồng thời đƣợc hiển thị trên lƣới kích 10*10 (vùng ơ vuơng màu xanh, bên phải giao diện chƣơng trình). - Nhấn nút nhận dạng. - Chữ nhận dạng tƣơng ứng với chữ cần nhận dạng đã đƣợc vẽ sẽ đƣợc hiển thị ra màn hình. 3.5. Đánh giá, nhận xét Chƣơng trình cĩ thể nhận dạng với độ chính xác rất cao.Nếu chữ nhận dạng chƣa đƣợc chính xác ta cĩ thể thêm mẫu và trích chọn lại cho chữ đĩ đến khi nhận dạng đƣợc chữ đĩ chính xác. Nếu các chữ gần giống nhau khi nhận dạng dễ lẫn sang nhau thì khi trích chọn ta thêm mẫu tƣơng ứng với các chữ đến khi nào đạt đƣợc tỷ lệ nhận dạng cao. Chƣơng trình nhận dạng chính xác hơn với các chữ khơng dấu đến 96%, đối với chữ cĩ dấu thì độ chính xác lớn hơn 85%.Đối với chữ cĩ dấu độ chính xác giảm hơn so với trƣờng hợp khơng cĩ dấu vì trƣờng hợp này các chữ khác nhau rất ít, nên số lƣợng mẫu trích chọn cho các các chữ cĩ dấu cần nhiều hơn. Để nhận dạng đƣợc nhiều kiểu viết khác nhau thì tập mẫu cho mỗi chữ phải cĩ nhiều dạng phong phú, tƣơng ứng với các cách viết mà ngƣời sử dụng cĩ thể viết ra. Quá trình huấn luyện này giải quyết đƣợc khía cạnh phức tạp của bài tốn nhận dạng chữ viết tay đĩ là sự đa dạng của chữ viết tay, đặc biệt là chữ viết tay tiếng Việt. Nhƣ vậy chƣơng trình minh họa cho nhận dạng chữ viết tay tiếng Việt trực tuyến đã đạt đƣợc mục tiêu của bài tốn phức đặt ra. Nghiên cứu về trích chọn đặc trƣng đã là một hƣớng nghiên cứu hiện nay cịn rất mới mẻ và cĩ nhiều hứa hẹn. Nguyễn Sơn Hà - CT1301 39
  49. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng Với hƣớng tiếp cận mới này áp dụng cho giải quyết bài tốn nhận dạng chữ viết tay tiếng Việt trực tuyến vốn rất phức tạp ở những đặc điểm: - Chữ viết tay trực tuyến phải thêm phần tạo giao diện để vẽ chữ, so với việc nhập đầu vào là file ảnh của chữ viết tay. - Chữ viết tay thì hình dạng của chữ rất phong phú đa dạng phụ thuộc nhiều vào ngƣời viết, bởi mỗi ngƣời cĩ một cách viết khác nhau. - Chữ viết tay tiếng Việt cĩ số lƣợng lớn, lớn hơn rất nhiều so với các chữ theo các chuẩn khác. Ví dụ: chuẩn tiếng Việt cĩ 89 ký tự gồm ký tự khơng dấu và cĩ dấu, chuẩn tiếng Anh chỉ gồm 26 ký tự khơng dấu. Mặt khác các ký tự lại rất giống nhau nên dễ nhầm lẫn trong quá trình nhận dạng. Nhƣ vậy khi giải quyết bài tốn ở đây phải đáp ứng đƣợc các yêu cầu: - Giải quyết đƣợc sự phức tạp của việc xử lý dữ liệu đầu vào. - Giải quyết đƣợc việc xử lý khối lƣợng dữ liệu lớn. - Giải quyết đƣợc độ chuẩn xác trong quá trình nhận dạng. - Giải quyết đƣợc mức độ tổng quát, đa dạng, phong phú trong quá trình xây dựng và trích chọn để đạt đƣợc độ chính xác cao khi nhận dạng. Chƣơng trình thử nghiệm đƣợc xây dựng bằng ngơn ngữ C# sử dụng bộ Visual Studio 2012. Nguyễn Sơn Hà - CT1301 40
  50. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng Một số giao diện chƣơng trình Hình 2.5.Giao diện chính của chƣơng trình Hình 2.6.Giao diện của chƣơng trình sau khi nhận dạng chữ viết xong Nguyễn Sơn Hà - CT1301 41
  51. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng Hình 2.7.Giao diện của ơ thêm chữ viết Hình 2.8. Giá trị của các ơ vùng khi đƣợc nhận dạng Nguyễn Sơn Hà - CT1301 42
  52. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng KẾT LUẬN A. Kết quả đạt đƣợc: Trong quá trình nghiên cứu và hồn thành bài báo cáo đồ án tốt nghiệp “Tìm hiểu một số phƣơng pháp trích chọn đặc trƣng cho nhận dạng chữ viết”, em đã thu nhận đƣợc thêm rất nhiều kiến thức và cũng nhận thấy trích chọn đặc trƣng cho nhận dạng chữ viết là một lĩnh vực rộng lớn và đƣợc ứng dụng rất mạnh mẽ. Hơn thế nữa nĩ cịn rất nhiều vấn đề mà chúng ta cần khám phá. Trong đề tài của mình em đã cố gắng tìm hiểu và nghiên cứu tổng quan về lý thuyết nhận dạng chữ viết và phƣơng pháp trích chọn đặc trƣng cho việc nhận dạng chữ viết. Cài đặt thử nghiệm chƣơng trình trích đặc trƣng cho việc nhận dạng các chữ cái khơng dấu. Do thời gian thực hiện hạn chế và kiến thức cịn hạn chế nên em mới chỉ nghiên cứu đƣợc một số lý thuyết cơ bản trong trích chọn đặc trƣng. Cịn nhiều lý thuyết cũng nhƣ kỹ thuật em vẫn chƣa tìm hiểu, khai thác và ứng dụng vào các bài tốn thực tế. Mặc dù đã rất cố gắng, song do năng lực và trình độ cĩ hạn nên trong quá trình thực hiện bài thực tập em đã khơng tránh khỏi những thiếu sĩt. Kính mong các thầy cơ và các bạn quan tâm giúp đỡ chỉ bảo để chƣơng trình của em một hồn thiện hơn. B. Hƣớng phát triển trong tƣơng lai Trong thời gian tới em sẽ cố gắng tiếp tục nghiên cứu, tìm hiểu thêm một số kiến thức về trích chọn đặc trƣng cho việc nhận dạng chữ viết nĩi riêng và lý thuyết nhận dạng nĩi chung. Nguyễn Sơn Hà - CT1301 43
  53. Đồ án tốt nghiệp Trƣờng ĐH Dân Lập Hải Phịng TÀI LIỆU THAM KHẢO Tiếng Việt [1] Hồng Kiếm, Nguyễn Hồng Sơn, Đào Minh Sơn, “Ứng dụng mạng nơron nhân tạo trong hệ thống xử lý biểu mẫu tự động”, Kỷ yếu hội nghị kỷ niệm 25 năm thành lập Viện Cơng nghệ Thơng tin, 2001, tr. 560-567. [2] Bùi Minh Trí, “Quy hoạch tốn học”, Nhà xuất bản Khoa học và kỹ thuật, Hà nội, 2006. [3] Lê Hồi Bắc, Lê Hồng Thái, “Neural Network & Genetic Algorithm in Application to Handwritten Character Recognition”, Tạp chí Tin học và Điều khiển học, Tập 17, số 4, 2001, tr. 57-65. [4] Nguyễn Thị Thanh Tân, Ngơ Quốc Tạo, “Một cấu trúc mạng nơ ron thích hợp cho việc nhận dạng chữ số viết tay”, Kỷ yếu hội thảo FAIR03, NXB KH&KT Hà Nội, 2004, tr. 200-210. [5] Nguyễn Thị Thanh Tân, Lƣơng Chi Mai, “Phƣơng pháp nhận dạng từ viết tay dựa trên mơ hình mạng nơ ron kết hợp với thống kê từ vựng”, Tạp chí Tin học và Điều khiển học, Tập 22, số 2, 2006, tr. 141-154. [5.1]. Phạm Anh Phƣơng, Ngơ Quốc Tạo, Lƣơng Chi Mai, “Ứng dụng SVM cho bài tốn phân lớp nhận dạng”, Kỷ yếu Hội thảo khoa học Quốc gia lần thứ ba về nghiên cứu, phát triển và ứng dụng Cơng nghệ thơng tin và Truyền thơng (ICT.rda’06), nhà xuất bản Khoa học và Kỹ thuật, Hà nội, trang 393-400, 20- 21/05/2006. [5.2]. Phạm Anh Phƣơng, Ngơ Quốc Tạo, Lƣơng Chi Mai, “Trích chọn đặc trƣng wavelet Haar kết hợp với SVM cho việc nhận dạng chữ viết tay tiếng Việt”, Tạp chí Cơng nghệ Thơng tin và Truyền thơng, ISSN 0866-7039, kỳ 3, số 20, 10-2008, tr 36-42. [5.3]. Phạm Anh Phƣơng, “Áp dụng một số chiến lƣợc SVM đa lớp cho bài tốn nhận dạng chữ viết tay hạn chế”, Tạp chí khoa học Đại học Huế, ISSN 1859- 1388, số 45, 2008, tr. 109-118. [5.4]. Nguyễn Thị Thanh Tân, Lƣơng Chi Mai, “Phƣơng pháp nhận dạng từ viết tay dựa trên mơ hình mạng nơ ron kết hợp với thống kê từ vựng”, Tạp chí Tin học và Điều khiển học, Tập 22, số 2, 2006, tr. 141-154. Tiếng Anh [6] ivind Due Trier, Anil K.Jain, Feature Extraction methods for character recognition:Survey,Pattern Recognition 29(4):641-662(1996). [7] Mark S, Nixon Alberto S. Aguado, Feature Extraction & Image Processing,2nd Edition from Mark Nixon, Alberto S Aguato. ISBN-9780080556727, 2002. Nguyễn Sơn Hà - CT1301 44