Tugas Kuliah: Sudoku Solver

Beberapa hari ini saya sedang mencoba membuat program untuk mengenali (identifikasi) papan permainan Sudoku menggunakan webcam laptop.  Program ini merupakan salah satu tugas dari matakuliah Pengenalan Pola yang saya ambil.  Setelah beberapa kali mengutak-atik, saya berhasil mengenali dan menentukan lokasi papan Sudoku dari gambar yang diambil oleh webcam, seperti berikut:

Asumsi awal yang saya gunakan dalam membuat Sudoku Solver ini:

  • Gambar papan sudoku dalam warna hitam-putih
  • Gambar papan sudoku akan mendominasi gambar yang diambil oleh webcam

Secara garis besar, langkah yang telah saya tempuh sejauh ini:

  • Ambil gambar dari webcam
  • Lakukan proses edge detection dengan menggunakan algoritma Canny Edges
  • Dari hasil algoritma Canny Edges, berikutnya adalah mendeteksi adanya bentuk persegi (rectangle) dengan algoritma Hough Transformation.
  • Dari seluruh persegi yang didapatkan, ambil persegi yang berukuran paling besar

Langkah berikutnya:

  • Melakukan proyeksi gambar papan yang ditemukan ke bentuk persegi empat (bujur sangkar), sepertinya bisa dilakukan dengan algoritma transformasi perspektif (?)

**Update** (15 Mei 2011) 17:00 WIB

OpenCV (pada wrappernya, EmguCV) menyediakan fungsi WarpPerspective dengan memanggil fungsi WarpPerspective().  Fungsi ini membutuhkan matrix transformasi (Homography Matrix), yang didapatkan dari membandingkan gambar yang hendak diproyeksikan dengan bidang gambar tujuan.  Homography Matrix dapat dengan mudah didapatkan dengan memanggil fungsi GetPerspectiveTransform().  Dengan menggunakan algoritma transformasi perspektif ini, program dapat mengatasi bentuk papan sudoku yang tidak persegi saat gambarnya diambil menggunakan webcam. Untuk lebih jelasnya silahkan perhatikan gambar berikut:

  • Melakukan pengenalan angka-angka
  • Menyelesaikan Sudoku tersebut (brute force? backtracking?)

Sepertinya tugas kuliah ini sudah menjadi lebih rumit dari dugaan semula 😦

*tambahan : untuk membuat program ini saya menggunakan bahasa pemrograman C# (bagian dari Visual Studio .NET) dan menggunakan library Emgu CV (wrapper OpenCV untuk .NET).

*Update 26 Mei 2011

Untuk melakukan pengenalan angka, saya menggunakan proses clustering. Area gambar dibagi menjadi 9 x 9 kotak, kemudian masing-masing kotak diperkecil lagi dengan mengurangi panjang dan lebarnya.  Pemotongan ini bertujuan untuk menghilangkan gambar garis tepi yang sering kali muncul.  Hasil akhir dari setiap kotak angka adalah gambar berukuran 44 x 44.  Dari gambar tersebut kemudian didapatkan 16 area (masing-masing berukuran 11 pixel).  Dari masing-masing area diambil rasio titik berwarna hitam dengan titik berwarna lain, sehingga didapatkan sebuah vektor berukuran 16 dimensi untuk masing-masing kotak angka.

Saya mengambil beberapa variasi gambar angka untuk angka 1 – 9 serta kotak kosong untuk data training.  Dalam hal ini, training yang dilakukan adalah supervised training.  Gambar-gambar yang menunjukkan angka yang sama dimasukkan ke dalam cluster yang sama, kemudian dari masing-masing cluster ditentukan centroidnya dengan cara menghitung rata-rata vektor 16 dimensi dari masing-masing anggota cluster tersebut.

Kemudian angka yang akan diidentifikasi diambil vektor berukuran 16 dimensi, kemudian dilakukan perhitungan jarak (dengan Euclidean Distance) dengan centroid masing-masing cluster.  Hasil akhir identifikasi angka ditentukan oleh jarak terdekat ke centroid pada suatu cluster.  Artinya, angka tersebut masuk ke dalam cluster tersebut.

Untuk menyelesaikan puzzlenya, saya menggunakan cara brute-force (mencoba semua kemungkinan).