Luận văn nghiên cứu nhận dạng chữ số khmt

  • 11 trang
  • file .pdf
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