Tài liệu Tìm hiểu mạng neural hamming và ứng dụng trong bài toán nhận dạng chữ cái tiếng việt

.. ĐẠI HỌC THÁI NGUYÊN TÌM HIỂU MẠNG NEURAL HAMMING VÀ ỨNG DỤNG TRONG BÀI TOÁN NHẬN DẠNG CÁC CHỮ CÁI TIẾNG VIỆT Thái Nguyên – 2013 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TÌM HIỂU MẠNG NEURAL HAMMING VÀ ỨNG DỤNG TRONG BÀI TOÁN NHẬN DẠNG CÁC CHỮ CÁI TIẾNG VIỆT Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.48.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Ngƣời hƣớng dẫn khoa học: TS. Lê Quang Minh Thái Nguyên – 2013 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ LỜI CẢM ƠN Để hoàn thành bản luận văn này, bên cạnh sự nỗ lực cố gắng của bản thân còn có sự hƣớng dẫn nhiệt tình của quý Thầy Cô, cũng nhƣ sự động viên ủng hộ của gia đình và bạn bè trong suốt thời gian học tập nghiên cứu và thực hiện luận văn thạc sĩ. Xin chân thành bày tỏ lòng biết ơn đến Thầy giáo TS. Lê Quang Minh, ngƣời đã hết lòng giúp đỡ và tạo mọi điều kiện tốt nhất cho tôi hoàn thành luận văn này. Xin gửi lời tri ân nhất của tôi đối với những điều mà Thầy đã dành cho tôi. Xin chân thành bày tỏ lòng biết ơn đến toàn thể quý Thầy Cô trong trƣờng Đại học Công nghệ Thông tin & Truyền thông cũng nhƣ quý Thầy Cô đã tận tình truyền đạt những kiến thức quý báu và tạo mọi điều kiện thuận lợi cho tôi trong suốt quá trình học tập, nghiên cứu và cho đến khi thực hiện luận văn. Xin chân thành bày tỏ lòng biết ơn đến gia đình, những ngƣời đã không ngừng động viên, hỗ trợ và tạo mọi điều kiện tốt nhất cho tôi trong suốt thời gian học tập và thực hiện luận văn. Cuối cùng, tôi xin chân thành bày tỏ lòng biết ơn đến các anh chị và các bạn bè đồng nghiệp đã hỗ trợ cho tôi trong suốt quá trình học tập, nghiên cứu và thực hiện luận văn một cách hoàn chỉnh. Thái Nguyên, tháng 11 năm 2013 Học viên thực hiện Phùng Văn Kiệm Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ MỤC LỤC LỜI CẢM ƠN ..................................................................................................... 3 MỤC LỤC .......................................................................................................... 4 DANH MỤC CÁC TỪ VIẾT TẮT ...................................................................... 7 DANH MỤC HÌNH VẼ....................................................................................... 8 MỞ ĐẦU............................................................................................................ 1 CHƢƠNG I: TỔNG QUAN VỀ HIỆN TRẠNG CÁC BÀI TOÁN NHẬN DẠNG VÀ THIẾT LẬP BÀI TOÁN NGHIÊN CỨU ........................................ 3 1.1 Tổng quan về bài toán nhận dạng ............................................................ 3 1.2. Cụ thể về bài toán nhận dạng chữ cái Tiếng Việt ................................... 4 1.3. Thiết lập bài toán .................................................................................... 4 1.3.1. Ảnh đầu và ....................................................................................... 5 1.3.2. Tiền sử lý .......................................................................................... 5 1.3.2.1. Nhị phân hóa ảnh........................................................................... 5 1.3.2.2. Lọc nhiễu ....................................................................................... 6 1.3.2.3. Chuẩn hóa kích thƣớc ảnh ............................................................. 7 1.3.2.4. Làm trơn biên chữ ......................................................................... 7 1.3.2.5. Làm đầy chữ .................................................................................. 8 1.3.2.6. Làm mảnh chữ ............................................................................... 8 1.3.2.7. Điều chỉnh độ nghiêng của văn bản .............................................. 8 1.3.3. Quá trình biến đổi ảnh ...................................................................... 9 1.3.3.1. Biến đổi Fourier ............................................................................ 9 1.3.3.2. Biến đổi Wavelet ........................................................................... 9 1.3.3.3. Phƣơng pháp mô men.................................................................... 9 1.3.3.4. Khai triển Karhunent-Loeve ......................................................... 9 1.3.4. Nhận dạng ...................................................................................... 10 1.3.4.1. Đối sánh mẫu ............................................................................... 10 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 1.3.4.2. Phƣơng pháp tiếp cận cấu trúc .................................................... 11 1.3.4.3. Mô hình Markov ẩn (HMM - Hidden Markov Model)............... 13 1.3.4.4. Máy véc tơ tựa (SVM) ................................................................ 13 1.3.4.5. Mạng nơ ron ................................................................................ 14 1.3.5. Kết quả ........................................................................................... 15 1.4. Kết luận ................................................................................................. 15 CHƢƠNG II: TÌM HIỂU MẠNG NEURAL VÀ MẠNG HAMMING ........... 16 2.1. Mạng Neural ......................................................................................... 16 2.1.1. Khái niệm mạng Neural ................................................................. 16 2.1.2. Lịch sử phát triển mạng Neural ...................................................... 16 2.1.3 Đặc trƣng của mạng neural ............................................................. 18 2.1.3.1 Tính phi tuyến .............................................................................. 18 2.1.3.2 Tính chất tƣơng ƣớng đầu vào đầu ra .......................................... 19 2.1.3.3 Tính chất thích nghi...................................................................... 19 2.1.3.4 Tính chất đƣa ra lời giải có bằng chứng....................................... 19 2.1.3.5 Tính chất chấp nhận sai xót .......................................................... 20 2.1.3.6 Khả năng cài đặt VLSI(Very-large-scale-intergrated) ................. 20 2.1.3.7 Tính chất đồng dạng trong phân tích và thiết kế .......................... 20 2.1.4 Phân loại mạng neural nhân tạo ...................................................... 21 2.1.4.1 Phân loại theo kiểu liên kết neural ............................................... 21 2.1.4.2 Một số loại mạng neural ............................................................... 21 2.1.5 Xây dựng mạng neural .................................................................... 23 2.1.6 Huấn luyện mạng neural ................................................................. 25 2.1.6.1 Phƣơng pháp học .......................................................................... 25 2.1.6.2 Thuật toán học .............................................................................. 26 2.1.7 Ứng dụng của mạng neural ............................................................. 31 2.2 Mạng Hamming ..................................................................................... 32 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 2.2.1 Kiến trúc mạng Hamming ............................................................... 32 2.2.2 Thuật toán học điển hình của mạng Neural .................................... 34 2.3 Kết luận .................................................................................................. 40 CHƢƠNG III: ỨNG DỤNG MẠNG HAMMING TRONG BÀI TOÁN NHẬN DẠNG CÁC CHỮ CÁI TIẾNG VIỆT ................................................. 41 3.1. Đặc thù và khó khăn của bài toán nhận dạng chữ cái Tiếng Việt ........ 41 3.2 Thuật toán chung của chƣơng trình ....................................................... 43 3.3 Cấu trúc mạng Neural Hamming của chƣơng trình nhận dạng các chữ cái Tiếng Việt ................................................................................. 44 3.4. Xây dựng chƣơng trình nhận dạng chữ cái Tiếng Việt ........................ 46 3.4.1 Công cụ và ngôn ngữ lập trình ........................................................ 46 3.4.2 Xây dựng chƣơng trình ................................................................... 46 3.4.2.1 Xây dựng mô hình mạng Neural Hamming và các tín hiệu đầu vào ........................................................................................ 46 3.4.2.2 Định vị và thu gọn kích cỡ ảnh ................................................... 48 3.4.2.3 Xây dựng thuật toán ..................................................................... 49 3.4.2.4 Nhận dạng ................................................................................... 50 3.4.2.5 Giao diện chƣơng trình................................................................. 54 3.5 Thử nghiệm chƣơng trình ...................................................................... 54 3.6 Nhận xét chung quá trình thử nghiệm nhận dạng chữ cái Tiếng Việt và kết luận chƣơng 3 ..................................................................... 60 KẾT LUẬN...................................................................................................... 62 TÀI LIỆU THAM KHẢO ............................................................................... 63 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ DANH MỤC CÁC TỪ VIẾT TẮT Từ Ý nghĩa RBF Radial Basic Function HMM Hidden Markov Model SVM Support Vector Machines 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 Insitute of Standard and Technology of the United States) SV Support Vector SOM Self Origanizing Map ANN Artificial Neural Network VLSI Very-large-scale-intergrated MLP Multi Layer Perceptron LMS Least Means Square Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ DANH MỤC BẢNG, HÌNH VẼ Bảng 3.1: Kết quả nhận dạng các chữ cái Tiếng Việt Font Times New Roman ........ 57 Bảng 3.2: Kết quả nhận dạng các chữ cái Tiếng Việt Font Arial ................... 59 Hình 1.1. Sơ đồ hệ thống nhận dạng ................................................................. 5 Hình 1.2. Nhị phân hóa ảnh .............................................................................. 6 Hình 1.3. Nhiễu đốm và nhiễu vệt .................................................................... 6 Hình 1.4.Chuẩn hóa kích thƣớc ảnh các ký tự “A” và “P” ............................... 7 Hình 1.5.(a) Ảnh gốc, (b) Ảnh sau khi đƣợc làm trơn biên .............................. 7 Hình 1.6. Làm mảnh chữ ................................................................................... 8 Hình 1.7. Hiệu chỉnh độ nghiêng của văn bản .................................................. 8 Hình 2.1: Mạng tiến với một mức neural ........................................................ 21 Hình 2.2: Mạng tiến kết nối đầy đủ với một mức ẩn và một mức đầu ra ...... 22 Hình 2.3: Mạng hồi quy không có neural ẩn và không có vòng lặp tự phản hồi ...... 23 Hình 2.4: Mạng hồi quy có các neural ẩn ....................................................... 23 Hình 2.5: Sơ đồ đồ thị có hƣớng đơn giản ...................................................... 24 Hình 2.6 Cấu trúc mạng hamming .................................................................. 32 Hình 2.7 Sơ đồ khối thuật toán lan truyền ngƣợc ........................................... 39 Hình 3.1 Phân tích chữ cái cỡ 30x20 thành các điểm ảnh .............................. 41 Hình 3.2 Phân tích chữ cái cỡ 60x30 thành các điểm ảnh .............................. 42 Hình 3.3 Sơ đồ thuật toán chung của chƣơng trình ........................................ 43 Hình 3.4 Lƣu đồ quá trình xử lý ảnh ............................................................... 44 Hình 3.5 Cấu trúc mạng Neural ...................................................................... 45 Hình 3.6. Hàm truyền của Neural lớp 1 .......................................................... 45 Hình 3.7 Quá trình xử lý ảnh trong thuật toán ................................................ 47 Hình 3.8. Định vị trí các biên của ảnh ............................................................ 48 Hình 3.9. Hàm truyền của Neural lớp thứ 2 .................................................... 49 Hình 3.10 Sơ đồ hàm đầu ra ............................................................................ 51 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ Hình 3.11 Giao diện của chƣơng trình ............................................................ 54 Hình 3.12 Kết quả nhận dạng chữ Â với kích thƣớc là 80x50 và độ nhiễu 25%..... 55 Hình 3.13 Kết quả nhận dạng chữ Â với kích thƣớc là 80x50 pixel và độ nhiễu là 35% ................................................................................... 55 Hình 3.14 Kết quả nhận dạng chữ Â với kích thƣớc là 60x30 pixel và độ nhiễu là 25% ................................................................................... 56 Hình 3.15 Kết quả nhận dạng chữ Â font Arial với kích thƣớc 60x30 pixel với độ nhiễu 25% .................................................................................. 56 Hình 3.16 Bảng kết quả trọng số đầu ra ảnh không tính nhiễu....................... 57 Hình 3.17 Bảng kết quả trọng số đầu ra ảnh có tính nhiễu ............................. 57 Hình 3.18 So sánh giữa ảnh đầu vào và ảnh mẫu ........................................... 60 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 1 MỞ ĐẦU Từ lâu các nhà khoa học đã nhận thấy những ƣu điểm của bộ óc con ngƣời và tìm cách bắt chƣớc để thực hiện trên những máy tính, tạo cho nó có khả năng học tập, nhận dạng và phân loại. Vì vậy các nhà khoa học đã nghiên cứu và sáng tạo ra mạng Neural nhân tạo. Nó thực sự đƣợc chú ý và nhanh chóng trở thành một hƣớng nghiên cứu đầy triển vọng đặc biệt là lĩnh vực nhận dạng. Và bài toán nhận dạng ký tự là một bài toán con trong lớp các bài toán nhận dạng, xử lý ảnh. Hiện nay trên thế giới, các sản phẩm nhận dạng ký tự đã đƣợc triển khai tƣơng đối rộng rãi. Tuy nhiên đây là các sản phẩm nhận dạng ký tự tiếng Anh, do đó đối với nhận dạng ký tự tiếng Việt thì chỉ có ngƣời Việt Nam mới có thể phát triển đƣợc. Ở nƣớc ta trong một vài năm gần đây cũng đã có một số sản phẩm nhận dạng tiếng việt đƣợc triển khai trên thị trƣờng. Nhƣng các sản phẩm này đƣợc bán trên thị trƣờng dƣới dạng đóng kín nên việc để phát triển thành phần mềm tự động cập nhật ảnh là điều không thể. Vì vậy nên tôi đã chọn đề tài: “Tìm hiểu mạng Neural Hamming và ứng dụng trong bài toán nhận dạng các chữ cái Tiếng Việt”. Hệ thống chữ cái Tiếng Việt là đƣợc xây dựng dựa trên chữ cái Latinh có thêm chữ ghép và dấu phụ. Do đó việc nhận dạng sẽ gặp khó khăn hơn so với chữ cái Latinh thông thƣờng và cần phải có thuật toán xử lý đem lại độ chính xác cao. Trong khuôn khổ, thời lƣợng của luận văn, tôi đƣa ra một chƣơng trình mô phỏng mạng Neural nhận dạng 29 chữ cái Tiếng Việt từ A đến Y và 10 chữ số từ 0 đến 9. Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 2 Luận văn đƣợc sắp xếp và chia thành 3 chƣơng chính: Chƣơng 1: Tổng quan về hiện trạng các bài toán nhận dạng và thiết lập bài toán nghiên cứu Chƣơng 2: Tìm hiểu về mạng Neural và khoảng cách Hamming Chƣơng 3: Ứng dụng mạng neural Hamming trong bài toán nhận dạng các chữ cái Tiếng Việt Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 3 CHƢƠNG I TỔNG QUAN VỀ HIỆN TRẠNG CÁC BÀI TOÁN NHẬN DẠNG VÀ THIẾT LẬP BÀI TOÁN NGHIÊN CỨU 1.1 Tổng quan về bài toán nhận dạng Nhận dạng chữ 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: 1) 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. 2) 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 toán nhận dạng chữ in đã đƣợc giải quyết gần nhƣ trọn vẹn (sản phẩm FineReader 11 của hãng ABBYY có thể nhận dạng chữ in theo 20 ngôn ngữ khác nhau trong đó có cả Việt Nam, phần mềm nhận dạng chữ Việt in VnDOCR 4.0 của Viện Công nghệ Thông tin Hà Nội có thể nhận dạng đƣợc các tài liệu chứa hình ảnh, bảng và văn bản tiếng Việt với độ chính xác trên 99%,...). Tuy nhiên trên thế giới cũng nhƣ ở Việt Nam, bài toá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 toà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 tay 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ẫn với các nhiễu. Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 4 1.2. Cụ thể về bài toán nhận dạng chữ cái Tiếng Việt Hiện nay cũng có rất nhiều bài báo đề cập đến bài toán nhận dạng kí tự quang học, nhằm cải tiến các phƣơng pháp phân đoạn ảnh, nhận dạng. Song vẫn chƣa giải quyết một cách triệt để những vấn đề khó khăn của bài toán thƣờng gặp phải. Đặc biệt là đối với việc nhận dạng các kí tự tiếng Việt, gặp rất nhiều khó khăn, do tính riêng biệt của tiếng Việt: Số kí tự nhiều, các kí tự lại có dấu…Nên bài toán vẫn còn thu hút đƣợc sự quan tâm, nghiên cứu nhằm giải quyết những vấn đề khó khăn của bài toán một cách triệt để. Một số hệ nhận nhận dạng văn bản đã và đang đƣợc áp dụng rất nhiều vào ứng dụng nhƣ FineReader của hãng AABBYY, OmmiPage của hãng Scansoft đƣợc dùng để nhận dạng các văn bản tiếng Anh,… VNDOCR của Viện công nghệ thông tin cho các văn bản tiếng Việt. 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óa đơn, phiếu điều tra ... Khó khăn lớn nhất khi nghiên cứu bài toán nhận dạng chữ cái tiếng Việt 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 nhận dạng cũng nhƣ lựa chọn mô hình nhận dạng. 1.3. Thiết lập bài toán Đề tài mà tôi thực hiện là: “Ứng dụng mạng Neural Hamming trong bài toán nhận dạng các chữ cái Tiếng Việt”, công việc chính là “Xây dựng chƣơng trình nhận dạng các chữ cái Tiếng Việt” ý tƣởng bài toán nhƣ sau: Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 5  Phân tích ảnh cho ký tự: Chia ảnh và tách ký tự theo từng vùng giới hạn;  Chuyển đổi kí tự sang ma trận điểm ảnh;  Chuyển thành ma trận tuyến tính và đƣa vào mạng neural;  Đƣa vào mạng neural tính giá trị đầu ra. Các bƣớc giải quyết bài toán sử dụng mạng neural Hamming nhận dạng chữ cái Tiếng Việt mô tả theo tiến trình chung nhƣ sau: Ảnh đầu vào Tiền xử lý Quá trình biến đổi ảnh Nhận dạng Kết quả Hình 1.1. Sơ đồ hệ thống nhận dạng 1.3.1. Ảnh đầu và Với đầu vào là các file ảnh *.bmp có kích cỡ ảnh là 150 x 150. Sau khi đã nạp mẫu cần nhận dạng ta tiến ảnh các thao tác xử lý ảnh để tách ra ký tự. Ta có thể xác định đƣợc ký tự dựa vào đƣờng biên của ký tự. Trải qua các bƣơc tiền xử lý ảnh: lọc mịn ảnh, nhị phân, chỉnh nghiêng, chuẩn kích thƣớc, lấp khoảng trống, lấy biên, ta thu đƣợc ảnh ký tự với biên của nó. 1.3.2. Tiền sử 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 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.3.2.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 toán phân tích hoặc nâng cao chất lƣợng ảnh nào, nó Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 6 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 đề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.3.2.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...). Để 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. Hình 1.3. Nhiễu đốm và nhiễu vệt Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 7 1.3.2.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 toá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.3.2.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 toán làm trơn biên để khắc phục [8]. (a) (b) Hình 1.5.(a) Ảnh gốc, (b) Ảnh sau khi đƣợc làm trơn biên Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 8 1.3.2.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.3.2.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 ngoà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. Hiện nay có nhiều phƣơng pháp làm mảnh chữ, các thuật toán tìm xƣơng có thể tham khảo ở [8]. Hình 1.6. Làm mảnh chữ 1.3.2.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, một số kỹ thuật hiệu chỉnh độ nghiêng khác có thể tìm thấy trong [8]. Hình 1.7. Hiệu chỉnh độ nghiêng của văn bản Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 9 1.3.3. Quá trình biến đổi ảnh 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ữ: 1.3.3.1. 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 [9,10]. 1.3.3.2. 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ữ thành các ký tự hoặc từ đƣợc mô tả bằng các hệ so wavelet theo các mức độ khác nhau đối với từng giải pháp. Sau đó các hệ so wavelet đƣợc chuyển qua một máy phân lớp để phục vụ cho việc nhận dạng [11,12]. 1.3.3.3. 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 [13]. 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. 1.3.3.4. 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 [14], Khai triển Karhunent-Loeve đƣợc dùng trong một số bài toá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 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 10 States). Vì việc khai triển này đòi hỏi phải sử dụng các thuật toán có khối lƣợng tính toán rất lớn nên việc sử dựng các đặc trƣng Karhunent-Loeve trong các bài toá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 toá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. 1.3.4. Nhận dạng 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, SVM và mạng nơ ron. 1.3.4.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, toá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 [15,16]. Mặc dù phƣơng pháp đối sánh trực tiếp đơn giản và có một cơ sở toá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 [17]. Ý 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 Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/ 11 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 [18,19]. Đố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 toàn cục của một số hàm [20]. 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.4.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 [21,22]. Phƣơng pháp này đặt vấn đề để giải quyết bài toá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 toá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. Số hóa bởi trung tâm học liệu http://www.lrc.tnu.edu.vn/