Solve Sudoku Using Rock 4C+ and Matched Filter

Goal

• From an image of a Sudoku puzzle, extract and (optional) solve the puzzle.

Goal elements

• Extract the puzzle from the image (reshape the image).
• Identify the numbers in each cell. – Correlate the numbers to their respective cell position.
• (optional) Solve the puzzle and display the solution over the image (projecting the solution to the image)

Step 1: Basic Info

I was one of the lucky applicants to receive a Rock 4C+ kit from the kind people of DesignSpark.

The main task of this project is to use Rock 4C+ to recognize digits on sudoku images which are captured from a standard digital camera.

The program accepts an image of Sudoku as input, returns recognized sudoku digits, and (optional) you can use those digits to solve Sudoku.

The mathematical tool I use here is Template Matching (known also as Matched filter).

The software used here is Debian.

Step 2: Software

As we use Debian, we can use standard Debian package repositories.

The distribution contains C, C++ compilers, Perl, Python, etc.

You install programs simply by writing in terminal apt-get .

I used GNU Octave for the recognition of numbers from sudoku images. The Octave is a scientific software alternative to Matlab.

Octave has a lot of functions, and also normxcorr2() function. This function implements normalizes cross-correlation between two images. You can see more info on this function here: http://octave.sourceforge.net/image/function/normxcorr2.html.

We need first to install OpenCV for python and Octave.

pip install opencv-python numpy sklearn

sudo apt-get install octave

Step 3: Algorithm and Installing GNU Octave

This step doesn't require too much time. You just enter: apt-get install octave (assuming you are still logged in as administrator). The code and all test files are in code.rar file.

A little explanation: The sudoku image is preprocessed, reshaped into a track of numbers and the matched filter is applied, so template digits are matched on the original image. Below is a schematic which shows how matched filter works:

First, we need to run Python OpenCV script python perpscorr.py

Original sudoku:

After applying thresholding and perspective removal.

You run the code by typing at the terminal as show in the image below:

You can see that the algorithm works perfectly. Further work could be generating a solution of sudoku (by using backtracking) and additionally using another machine learning technique like SVM (Support Vector Machines) or by using Tensorflow Lite library for neural networks and creating "real-time" algorithm, interfacing webcam with Rock 4c+, which could recognize digits and project a solution of sudoku, and show the solution.

The next project will be using SVM (Support Vector Machines) machine learning techniques for recognizing and solving sudoku.

If you are interested in this topic, the references are below.

References:

1. Lewis, J. P., "Fast Normalized Cross-Correlation," Industrial Light & Magic
2. Haralick, Robert M., and Linda G. Shapiro, Computer and Robot Vision, Volume II, Addison-Wesley, 1992, pp. 316-317.
3. Smart Sudoku Solver, Agarwal Vinayak, Kamat Tarcar Anand, Kurian Shalini Department of Electrical Engineering, Stanford University
4. Martin Byröd, An Optical Sudoku Solver
5. Jennifer Ding, Omar Turk, Sean Peters, Sai Supreeth Mannava, License Plate Recognition Matched Filter Technique