This program is designed to solve the Sudoku puzzle, taken from the camera. It uses openCV library for image processing, Keras for image recognition and it uses Backtracking algorithm for saving it.
- Sudoku-Solver
- Table of contents
- Getting Started
- How does it work?
- How to maximize accuracy
- Tests
- Authors
These instructions will get you a copy of the project up and running on your local machine for development and testing purposes.
You need Python 3.4 or later to run Sudoku-Solver. You can have multiple Python versions (2.x and 3.x) installed on the same system without problems.
In Ubuntu, Mint and Debian you can install Python 3 like this:
$ sudo apt-get install python3 python3-pip
For other Linux flavors, OS X and Windows, packages are available at:
For installing follow this link: https://www.tensorflow.org/install/
There are two ways to install Keras:
Install Keras from PyPI (recommended):
sudo pip install keras
Alternatively: install Keras from the GitHub source:
First, clone Keras using git:
git clone https://github.com/keras-team/keras.git
Then, cd to the Keras folder and run the install command:
cd keras
sudo python setup.py install
For more information check https://keras.io/
For installing Pillow enter the following command in the command line:
pip install Pillow
Fro more information check https://pillow.readthedocs.io/en/5.0.0/installation.html
To get all of the files needed to run this program, decide for one of the following options and follow it's steps.
- If the git is not yet installed, check this tutorial how to install it https://www.atlassian.com/git/tutorials/install-git
- Open the console and go to the directory, where you want to download files.
- Use the command
git clone https://github.com/ghribar97/Sudoku-Solver.git. - Files are ready. To run Sudoku-Solver check Quick start.
- Go to the repository page https://github.com/ghribar97/Sudoku-Solver
- Click a big green button "Clone or download" and choose "download ZIP" option.
- After download you must unzip the files with a WinZip software, or any other program.
- Files are ready. To run Sudoku-Solver check Quick start.
To start a program go to the directory where the Sudoku-Solver files are located and execute this command:
$ python3 main.py
After the execution the program should start.
Here, we will briefly look at how the program is working - or at least the most important things. For any details please see the code or contact one of the authors.
The purpose of this step is to extract the outline of Sudoku field.
Lets first take a look at the image we want to process.
For smoothing out the noise a bit, lets first blur the image a bit.
cv2.GaussianBlur(image, (11, 11), 0)
Where the image is our original photo.
With the noise smoothed out, we can now threshold the image. The image can have varying illumination levels, so a good choice for a thresholding algorithm would be an adaptive threshold. It calculates a threshold level several small windows in the image. This threshold level is calculated using the mean level in the window. So it keeps things illumination independent.
cv2.adaptiveThreshold(image, 255, cv2.ADAPTIVE_THRESH_MEAN_C, cv2.THRESH_BINARY, 5, 2, dst=image)
It calculates a mean over a 5x5 window and subtracts 2 from the mean. This is the threshold level for every pixel.
Since we're interested in the borders, and they are black, we invert the image outerBox. Then, the borders of the puzzles are white (along with other noise).
cv2.bitwise_not(image)
This thresholding operation can disconnect certain connected parts (like lines). So dilating the image once will fill up any small "cracks" that might have crept in.
kernel = np.array([[0, 1, 0], [1, 1, 1], [0, 1, 0]], dtype=np.uint8)
cv2.dilate(image, kernel)
Read some more about dilation and erosion: https://www.geeksforgeeks.org/erosion-dilation-images-using-opencv-python/
First, we used the floodfill command. This command returns a bounding rectangle of the pixels it filled. We've assumed the biggest thing in the picture to be the puzzle. So the biggest blob should have be the puzzle.
area = cv2.floodFill(image, None, (x, y), 64)[0]
We iterate through the white pixels (>=128) of the image, which ensure that only the white parts are flooded. Whenever we encounter such a part, we flood it with a dark gray colour (gray level 64). So in the future, we won't be reflooding these blobs. When we encounter a blob, that has bigger area, than the previous maximum, we have to update maximum and get the point of it.
Now, we have several blobs filled with a dark gray colour (level 64). And we also know the point what produces a blob with maximum area. So we floodfill that point with white:
cv2.floodFill(image, None, max_point, (255, 255, 255))
Now, the biggest blob is white. We need to turn the gray color blobs black. We iterate through image again and use this command (if pixel is gray (=64)):
cv2.floodFill(image, None, (x, y), 0)
Which will color the blob to black.
Lets see the result now:
For detecting lines, we used Hough Lines:
cv2.HoughLines(image, 1, np.pi / 180, 200)
Based on each line's rho and theta, we separated them on Horizontals and Verticals. For each of them we calculated the intersection point with others.
Now, when we have all of the points, we can get the most top-left, top-right, bottom-left and bottom-right point, that is white (it is on the blob).
After we have the corner points, we must calculate the biggest distance between them. If the difference between distances is to big, we probably did not detect the complete Sudoku field (It should be square).
The we transformed the perspective to get straight field.
src = np.array([tl, tr, bl, br], np.float32)
dst = np.array([(0, 0), (distance-1, 0), (0, distance-1), (distance-1, distance-1)], np.float32)
matrix = cv2.getPerspectiveTransform(src, dst)
cv2.warpPerspective(original_image, matrix, (distance, distance))
tl, tr, bl, br are the corners of the biggest blob and the distance is the longest line between points. Original_image is the picture, taken form the camera, which has not been changed.
Lets see the result:
The purpose of this step is to get the digit from an image.
After Extracting the Sudoku field we have a clear, straight field, so we can easily divide the field on 81 equal squares.
Like that:
We can easily extract the "small square" of the puzzle. Lets take first one for example:
Before continuing with recognition step, we must once again use some image processing.
We use similar technique as in Image pre-processing. Then we used this command:
contours = cv2.findContours(image, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)[1]
x, y, width, height = cv2.boundingRect(sorted(contours, key=cv2.contourArea)[-1])
Upper function returns the data about the biggest contour in the image (we assume this is the number). If the ratio between width and height is not good enough, the field does not contain any number. Otherwise, proceed with processing. Lets see what is the result of the picture now:
Or a little bit more extreme case:
The image still contains a part of the line. So, we had to crop it and extract the contour section.
Last step before recognizing, is to change the image to look more like the images from the training set. One last time we use:
cv2.bitwise_not(image)
to switch white and black pixels. For the end we put this image to a bigger square white image.
The image now, looks like that:
Finally, the image is now ready for recognizing.
To achieve good results, make sure that you do the following things:
- Image should be flat, not curved, so that the program would recognize field easier.
- The Sudoku's field outline should be thick enough.
- Try to capture puzzle as close to the camera as possible.
- While taking a picture make sure, that there is an appropriate light.
To run the tests for this project go to Tests directory and run mainTester.py Run it with this command:
$ python3 mainTester.py
Test coverage is:
