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

Optical charater recognition Nhận dạng ký tự quang học OCR

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.