How do you feel about this article? Help us to provide better content for you.
Thank you! Your feedback has been received.
There was a problem submitting your feedback, please try again later.
What do you think of this article?
- From an image of a Sudoku puzzle, extract and (optional) solve the puzzle.
- 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
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
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.
- Lewis, J. P., "Fast Normalized Cross-Correlation," Industrial Light & Magic
- Haralick, Robert M., and Linda G. Shapiro, Computer and Robot Vision, Volume II, Addison-Wesley, 1992, pp. 316-317.
- Smart Sudoku Solver, Agarwal Vinayak, Kamat Tarcar Anand, Kurian Shalini Department of Electrical Engineering, Stanford University
- Martin Byröd, An Optical Sudoku Solver
- Jennifer Ding, Omar Turk, Sean Peters, Sai Supreeth Mannava, License Plate Recognition Matched Filter Technique