Tóm tắt luận văn Thạc sĩ Khoa học tâm lý: Nghiên cứu nhận dạng chữ số và ứng dụng giải Sudoku

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

17
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu của đề tài là nghiên cứu nhận dạng chữ số và ứng dụng để tìm lời giải cho trò chơi Sudoku. Mời các bạn cùng tham khảo luận văn để nắm chi tiết hơn nội dung nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt luận văn Thạc sĩ Khoa học tâm lý: Nghiên cứu nhận dạng chữ số và ứng dụng giải Sudoku

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG ĐOÀN PHƯỚC MIỀN NGHIÊN CỨU NHẬN DẠNG CHỮ SỐ VÀ ỨNG DỤNG GIẢI SUDOKU Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 LUẬN VĂN THẠC SĨ KỸ THUẬT Người hướng dẫn khoa học: TS. HUỲNH HỮU HƯNG Đà Nẵng - Năm 2016
MỤC LỤC MỞ ĐẦU ....................................................................................................... 1 1. Tính cấp thiết của đề tài ....................................................................... 1 2. Mục tiêu nghiên cứu ............................................................................ 1 3. Đối tượng và phạm vi nghiên cứu ........................................................ 2 4. Phương pháp nghiên cứu ..................................................................... 2 5. Bố cục của đề tài.................................................................................. 3 6. Tổng quan tài liệu nghiên cứu .............................................................. 3 CHƯƠNG 1. XỬ LÝ ẢNH VÀ CÁC KỸ THUẬT NHẬN DẠNG ............ 4 1.1. TỔNG QUAN VỀ XỬ LÝ ẢNH............................................................. 4 1.1.1. Giới thiệu chung ............................................................................ 4 1.1.2. Các bước trong xử lý ảnh ............................................................... 7 1.1.3. Một số khái niệm trong xử lý ảnh [1] ............................................. 8 1.1.4. Một số ứng dụng trong xử lý ảnh ................................................. 11 1.2. CÁC PHÉP TOÁN HÌNH THÁI HỌC [1] ............................................ 11 1.2.1. Phần tử cấu trúc ........................................................................... 12 1.2.2. Phép toán giãn nở (Dilation) ........................................................ 14 1.2.3. Phép toán co ................................................................................ 17 1.2.4. Phép toán mở (Opening) và phép toán đóng (Closing) ................. 22 1.3. MỘT SỐ KỸ THUẬT NHẬN DẠNG [2] ............................................. 22 1.3.1. SVM (Support vector machine) ................................................... 22 1.3.2. Mạng nơron ................................................................................. 26 1.3.3. K -láng giềng gần nhất (KNN - K nearest neighbors)................... 27 1.4. GIẢI SUDOKU ..................................................................................... 28 1.4.1. Bài toán Sudoku........................................................................... 28 1.4.2. Cách giải bài toán Sudoku............................................................ 29
Kết chương ................................................................................................. 30 CHƯƠNG 2. NHẬN DẠNG CHỮ SỐ ...................................................... 31 2.1. TỔNG QUAN VỀ PHƯƠNG PHÁP NHẬN DẠNG CHỮ SỐ ............. 31 2.2. CÁC BƯỚC TRONG NHẬN DẠNG CHỮ SỐ .................................... 32 2.2.1. Tiền xử lý .................................................................................... 32 2.2.2. Khối tách chữ số .......................................................................... 32 2.2.3. Phân đoạn ảnh [1] ........................................................................ 33 2.2.4. Trích chọn đặc trưng .................................................................... 35 2.2.5. Huấn luyện và nhận dạng ............................................................. 35 2.3. MỘT SỐ PHƯƠNG PHÁP NHẬN DẠNG CHỮ SỐ ........................... 36 2.3.1. Nhận dạng chữ số sử dụng phương pháp SVM ............................ 36 2.3.2. Nhận dạng chữ số sử dụng phương pháp K-NN ........................... 48 2.3.3. Nhận dạng chữ số sử dụng phương pháp mạng nơron .................. 50 Kết chương ................................................................................................. 53 CHƯƠNG 3. CÀI ĐẶT VÀ THỬ NGHIỆM ............................................ 54 3.1. CÁC BƯỚC TIỀN XỬ LÝ ẢNH .......................................................... 54 3.1.1. Phương pháp ................................................................................ 54 3.1.2. Các bước xử lý ............................................................................. 56 3.1.3. Kết quả đạt được .......................................................................... 62 3.2. PHƯƠNG PHÁP NHẬN DẠNG BẰNG KNN VÀ MÔ HÌNH NHẬN DẠNG MNIST............................................................................................. 62 3.2.1. Phương pháp ................................................................................ 62 3.2.2. Các bước xử lý ............................................................................. 63 3.2.3. Kết quả đạt được .......................................................................... 63 3.3. NHẬN DẠNG BẰNG SVM ................................................................. 66 3.3.1. Phương pháp SVM tuyến tính ...................................................... 66 3.3.2. Các bước xử lý ............................................................................. 68
3.3.3. Kết quả đạt được .......................................................................... 69 3.4. NHẬN DẠNG BẰNG MẠNG NƠRON ............................................... 71 3.4.1. Phương pháp ................................................................................ 71 3.4.2. Các bước xử lý ............................................................................. 72 3.4.3. Kết quả đạt được .......................................................................... 74 Kết chương ................................................................................................. 75 TÀI LIỆU THAM KHẢO77 QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN THẠC SĨ (BẢN SAO) PHỤC LỤC
DANH MỤC CÁC CHỮ VIẾT TẮT OCR Optical charater recognition Nhận dạng ký tự quang học XLA Xử lý ảnh ANN Artificial Neural Networks Mạng nơron HMM Hidden Markov Model Mô hình Markov ẩn
DANH MỤC CÁC HÌNH Số Tên hình Trang hiệu Mối quan hệ giữa xử lý ảnh, thị giác máy tính và phân tích 1.1 5 ảnh 1.2 Quá trình xử lý ảnh 6 1.3 Sơ đồ tổng quát của hệ thống xử lý ảnh 6 1.4 Số hoá 8 1.5 Bức ảnh kinh điển của xử lý ảnh 9 1.6 Mức xám 10 1.7 Hình dáng của một số phần tử cấu trúc 13 1.8 Phần tử cấu trúc trên ảnh xám 14 1.9 Phép giãn nỡ 15 1.10 Phần tử cấu trúc trên ảnh xám 16 1.11 Ma trận điểm ảnh 16 1.12 Ma trận điểm ảnh sau khi giãn nở 17 1.13 Phép co ảnh 18 1.14 Ma trận cấu trúc ảnh đa mức xám 20 1.15 Ma trận điểm ảnh nguồn 20 1.16 Quá trình co ảnh (1) 20 1.17 Quá trình co ảnh (2) 21 1.18 Kết quả tính toán co ảnh 21 1.19 H2 là mặt phẳng tốt nhất. 23 1.20 Các điểm dữ liệu được biểu diễn trên R+. 24 1.21 Các vector hỗ trợ được chọn. 24
Số Tên hình Trang hiệu 1.22 Siêu phẳng được biểu diễn trên R+. 26 1.23 Khung lưới câu đố Sudoku 29 Siêu phân hoạch tập mẫu từ không gian Rn sang không gian 2.1 36 Rd. Siêu phẳng phân chia dữ liệu với khoảng cách biên lớn 2.2 37 nhất. 2.3 Minh họa cho bài toán phân hai lớp. 38 Khoảng cách phân hoạch d càng lớn thì VC dimension càng 2.4 40 nhỏ. 2.5 Minh họa bài toán phân hai lớp với SVM 42 Bài toán SVM mẫu trong trường hợp không phân tách 2.6 43 tuyến tính. Hàm nhận dạng của SVM 4-vs-rest có giá trị bé nhất, nên 2.7 44 mẫu cần nhận dạng là lớp thứ 4. 2.8 SVM loại trừ 45 2.9 Sơ đồ loại trừ trong các tình huống. 45 2.10 Biểu đồ màu 3D 8 bin vector SVM của xe màu đỏ. 47 2.11 Hình ảnh với mức độ nhiễu khác nhau. 48 2.12 Kiến trúc tổng quát của mạng nơron 51 2.13 Quá trình xử lý thông tin của mạng nơron 51 3.1 Không gian mẫu 55 3.2 Load ảnh vào chương trình 56 3.3 Ảnh trắng đen 57 3.4 Nghịch đảo màu ảnh 57
Số Tên hình Trang hiệu 3.5 Làm đậm các đường viền 58 3.6 Tìm blob 59 3.7 Xoá các blob có giá trị 64 59 3.8 Dò tìm đường thẳng 60 3.9 Khung lưới 60 3.10 Hình sau khi xử lý 61 3.11 Cắt từng ô lưới 61 3.12 Chương trình 62 3.13 Kết quả thuật toán KNN- chọn hình 64 3.14 Kết quả thuật toán KNN- tìm lưới 64 3.15 Kết quả thuật toán KNN- nhận dạng số 65 3.16 Hình SVM chưa huấn luyện 70 3.17 SVM đã huấn luyện 70 3.18 Một số chữ số chưa nhận dạng đúng 74 3.19 Cập nhật các chữ sai, huấn luyện lại 75
1 MỞ ĐẦU 1. Tính cấp thiết của đề tài Nhận dạng ký tự quang học (optical charater recognition - OCR) là một lĩnh vực nghiên cứu được quan tâm rộng rãi và có những ứng dụng thiết thực trong những năm gần đây. Ảnh có chứa các ký tự, sau khi được tiền xử lý bằng các thuật toán xử lý ảnh, các thao tác nhận dạng ký tự thường được thực hiện bằng các phương pháp học có giám sát để nhận dạng được ký tự chứa trong ảnh. Chúng ta có thể dễ dàng nhận thấy lợi ích của OCR như số hóa tài liệu giấy, truy vấn bằng hình ảnh (image based information retrieval...). Ví dụ khi chúng ta đi du lịch, để hiểu được bản chỉ dẫn trên đường khi đó chúng ta thương dùng phần mềm để tra cứu. Khi đó chúng ta có thể dùng camera hoặc smart phone để chụp lại các biển báo, chương trình sẽ nhận dạng phân tích và hiển thị cho chúng ta biết ý nghĩa. Ở Việt Nam, các ứng dụng về xử lý ảnh đã bước đầu được triển khai trên một số lĩnh vực như hệ thống nhận dạng biển số xe ở các bãi đỗ xe ở trường học, siêu thị,hệ thống nhận dạng vân tay chấm công ở các công sở… Tuy nhiên số lượng các ứng dụng được triển khai trên thực tế còn ít, lĩnh vực này sẽ phát triển mạnh mẽ trong tương lai nếu như được quan tâm một cách nghiêm túc. Với nhận thức về tầm quan trọng của OCR, và mong muốn kết hợp OCR vào một ứng dụng cụ thể, tôi chọn đề tài: Nghiên cứu nhận dạng chữ số và ứng dụng giải Sudoku. 2. Mục tiêu nghiên cứu Mục tiêu nghiên cứu của đề tài là nghiên cứu nhận dạng chữ số và ứng dụng để tìm lời giải cho trò chơi Sudoku.
2 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu Đề tài tập trung nghiên cứu xung quanh các đối tượng sau: - Thuật toán K – láng giềng gần nhất (K-Nearest Neighbors) - Thuật toán SVM - Mạng Nơron - Các hình ảnh sudoku 3.2. Phạm vi nghiên cứu Trong khuôn khổ của luận văn thực nghiệm, tác giả nghiên cứu nhận dạng chữ số và xây dựng ứng dụng để tìm lời giải cho trò chơi Sudoku. 4. Phương pháp nghiên cứu Tác giả sử dụng hai phương pháp nghiên cứu chính là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. 4.1. Phương pháp nghiên cứu lý thuyết Tác giả ứng dụng phương pháp nghiên cứu lý thuyết tập trung vào các vấn đề sau: - Các tài liệu về cơ sở lý thuyết: xử lý ảnh số, lọc trích ảnh số, xác định biên, rút trích số, nhận dạng ký tự số. - Nghiên cứu các thuật toán nhận dạng chữ số, chữ viết tay. - Các tài liệu liên quan như Nhận dạng biển số xe, Phương pháp giải trò chơi Sudoku. - Các tài liệu liên quan tới lập trình C++ và thư viện OpenCV. 4.2. Phương pháp thực nghiệm Tác giả ứng dụng phương pháp nghiên cứu thực nghiệm tập trung vào các nội dung sau:
3 - Sử dụng công cụ lập trình C++ kết hợp với thư viện OpenCV để nhận dạng chữ số. - Xây dựng các hàm cần thiết để giải quyết các vấn đề. - Vận dụng kiến thức về xử lý ảnh để nhận dạng các chữ số. Áp dụng thực tế trên trò chơi Sudoku với yêu cầu đầu vào là một bức ảnh gồm các chữ số cho sẵn trên lưới. 5. Bố cục của đề tài Bố cục đề tài dự kiến tổ chức thành 3 chương chính: Chương 1: Xử lý ảnh và các kỹ thuật nhận dạng: Trình bày tổng quan về quá trình xử lý ảnh, một số kỹ thuật nhận dạng được sử dụng trong nhận dạng chữ số, chữ viết tay, trình bày bài toán Sudoku và cách giải quyết bài toán. Chương 2: Nhận dạng chữ số: Trình bày chi tiết về một số phương pháp nhận dạng chữ số, các bước trong nhận dạng chữ số và ứng dụng. Chương 3: Triển khai và kết quả: Trình bày chi tiết về phương pháp nhận dạng, các bước xử lý, trình bày kết quả đạt được, đánh giá kết quả, rút ra kết luận và hướng phát triển. 6. Tổng quan tài liệu nghiên cứu - Tài liệu nghiên cứu về xử lý ảnh, nhận dạng chữ số, nhận dạng bản số xe, thư viện OpenCV, Máy học (học có giám sát, học bán giám sát và học không giám sát), nhận dạng ký tự quang học, thuật toán quay lui. - Ngoài ra còn tham khảo tài liệu của giáo viên hướng dẫn, tiếp thu ý kiến của giáo viên hướng dẫn, tham khảo ý kiến của đồng nghiệp.