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).

6 thoughts on “Tugas Kuliah: Sudoku Solver”

  1. om bisa di jelasin yang pengenalan angkanya? ini kayak ocr itu ya? algoritmanya kalo di opencv dong om,, step by step…..

    1. untuk pengenalan angkanya menggunakan cara klustering, sudah dijelaskan pada artikel di atas, untuk selengkapnya silahkan dibaca kembali, mulai dari bagian:

      “Untuk melakukan pengenalan angka, saya menggunakan proses ……”

  2. Hi,

    Saya tertari dengan GetPerspectiveTransform() bisa align bentuk papan sudoku yang tadinya miring.

    Pertanyaannya : bgm mengetahui sudut kemiringannya? ada fungsinya di opencv?
    Terima kasih atas pencerahannya

    Salam

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s