Nhận diện ký tự bằng KNN

Bài này sẽ hướng dẫn cách nhận diện ký tự bằng knn (phân lớp ký tự). Các ký tự được extract ra từ hình ảnh.

KNN là một thuật toán của Machine Learning (ML). KNN viết tắt của K-Nearest Neighbor. Thuật toán này hiểu đơn giản là tìm k phần tử giống phần tử được test nhất, kết quả là class nào xuất hiện nhiều nhất thì đó là kết quả cần tìm.

Hình minh họa: các điểm dữ liệu xanh đỏ nằm rải rác. Vậy điểm cần tìm trong hình có màu gì?
Câu trả lời là màu đỏ vì lấy 9 điểm gần nhất có 7 điểm màu đỏ và 2 điểm màu xanh.

Để đễ hiểu hơn ta có một ví dụ nhỏ sử dụng KNN để nhận diện các chữ số như sau:

• Lấy 1000 ký tự từ 0-9 để huấn luyện.
• Sau đó lấy 1 ký tự khác để test và lấy tham số k=10 , thuật toán sẽ lấy 10 phần tử giống nhất trong tập huấn luyện .
• Kết quả: trong 10 phần tử giống nhất đó giả sử có 8 ký tự class 3 và 2 ký tự class 5 thì thuật toán trả về kết quả là 3.

Về cách thức chuyển matrix thành dữ liệu để training KNN và viết code thì giống như bài Sử dụng SVM trong OpenCV để nhận diện ký tự.

Các bước thực hiện

1. Chuẩn bị bộ dữ liệu ký tự
2. Train KNN
3. Test (predict) kết quả

Chuẩn bị bộ dữ liệu ký tự

Mình đã chuẩn bị sẵn cho các bạn, bao gồm 2 bộ dữ liệu đi kèm với souce ở cuối bài:

– Train set: 10 folder từ 0 – 9 chứa các ký tự tương ứng.
– Test set: 1 vài ký tự dùng để test độ chính xác

Mình vẽ ký tự màu đỏ vì màu đen – trắng khá là khó nhìn, còn thực tế là sẽ làm với ảnh xám – gray scale. Link download ở cuối bài.

Train KNN

Thuật toán như sau: với mỗi ảnh 2D chuyển thành ảnh 1D. Sau đó ghép các ảnh 1D thành ảnh 2D dùng để huấn luyện.

Ảnh 1D là ảnh có height = 1, có thể xem nó là mảng 1 chiều. Còn ảnh 2D có height > 1 và cũng xem như là mảng 2 chiều.
Thí dụ: ảnh 2D có kích thước 10 x 10 pixels chuyển thành ảnh 1D có kích thước là 100 x 1 pixels.

Ảnh ký tự 2D và chuyển sang 1D (mình tăng height cho các bạn dễ nhìn)

Sau khi ghép các ký tự từ 0 – 9 được hình như sau:

Tiếp theo là tạo 1 danh sách các nhãn của ảnh train, danh sách nhãn cũng là ảnh 1D theo thứ tự. Do đó danh sách nhãn là 0123456789

Code để train nằm ở cuối bài. Sau khi train thì được 1 file text. Mình save lại với đuôi .knn cho dễ phân biệt

Test (predict) kết quả

Lấy 1 ảnh bất kỳ chưa được train để dự đoán kết quả

Download source

Các bạn checkout branch KnnOpenCV để test thuật toán:
Knn Opencv