close

Sudoku Solver - Part 2

home

Sudoku Solver - Part 2

opencvpython.blogspot.com

Sudoku Solver - Part 2

Hi,

This is the continuation of the article : Sudoku Solver - Part 1

So we start implementing here.

Load the image :

Below is the image I used to work with.

Sudoku Solver - Part 2
Original  Image
So, first we import necessary libraries.

import cv2
import numpy as np

Then we load the image, and convert to grayscale.

img =  cv2.imread('sudoku.jpg')
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

Image Pre-processing :

I have done just noise removal and thresholding. And it is working. So I haven't done anything extra.

gray = cv2.GaussianBlur(gray,(5,5),0)
thresh = cv2.adaptiveThreshold(gray,255,1,1,11,2)

Below is the result :

Sudoku Solver - Part 2
Result of adaptive thresholding
Now two questions may arise :

1) What is the need of smoothing here?
2) Why Adaptive Thresholding ? Why not normal Thresholding using cv2.threshold()  ? 

Find the answers here : Some Common Questions

Find Sudoku Square and Corners :

Now we find the sudoku border. For that, we are taking a practical assumption : The biggest square in the image should be Sudoku Square. In short, image should be taken close to Sudoku, as you can see in the input image of demo.

So a lot of things are clear from this : Image should have only one square, Sudoku Square, or not, Sudoku Square must be the biggest. If this condition is not true, method fails.

It is because, we find the sudoku square by finding the biggest blob ( an independant particle) in the image. So if biggest blob is something other than Sudoku, that blob is processed. So, I think you will keep an eye on it.

We start by finding contours in the thresholded image:

contours, hierarchy = cv2.findContours(thresh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)

Now we find the biggest blob, ie blob with max. area.

For this, first we find area of each blob. Then we filter them by area. We consider a blob for next processing only if its area is greater than a particular value (here, it is 100). If so, we approximate the contours. It removes unwanted coordinate values in the contour and keep only the corners. So if number of corners equal to four, that is a square (actually, a rectangle). If it has the maximum area among all detected squares, it is out Sudoku square.

biggest = None
max_area = 0
for i in contours:
area = cv2.contourArea(i)
if area > 100:
peri = cv2.arcLength(i,True)
approx = cv2.approxPolyDP(i,0.02*peri,True)
if area > max_area and len(approx)==4:
biggest = approx
max_area = area

For you to understand between original contour and approximated contour, I have drawn it on the image (using cv2.drawContours() function). Red line is the original contour, Green line is the approximated contour and corners marked in blue color circles.

Sudoku Solver - Part 2
Border and corners detected
Look at the top edge of sudoku. Original contour ( Red line) grazes on the edge of square and it is curved. Approximated contour ( Green line) just made it into a straight line.

Now, a simple question may arise. What is the benefit of filtering contours with respect to area? What is the need of removing them ? In simple words, it is done for speed up of the program. Although it may give you a little performance ( in the range of few milliseconds), even that will be good for those who want to implement it in real time. For more explanation, visit : Some Common Questions

Summary :

So, in this section, we have found the boundary of sudoku. Next part is the image transformation. I will explain it in next post.

Until then, I would like to know your feedback, doubts etc.

With Regards
ARK
Share

11 Comments on OpenCV-Python: Sudoku Solver - Part 2

  • Anonymous
    on June 07, 2012 | 23:38 Anonymoussaid :
    "great article .
    really i cant wait to read the next part , while i am trying to make some scanned form recognizer
    very useful article thx."
  • abidk
    on June 07, 2012 | 23:45 abidksaid :
    "Thank you. Remaining codes are ready. Just i got busy with other things. Hopes to post remaining, this week itself. Keep visiting."
  • Anonymous
    on June 07, 2012 | 23:49 Anonymoussaid :
    "good news , thanks for sharing"
  • Anonymous
    on June 08, 2012 | 22:06 Anonymoussaid :
    "I like the fact you show how to work with OpenCV's great Python API! Did you think about contributing some samples to OpenCV? I think problems like this would make interesting tutorials, which could be added to OpenCV. And it could be a motivation for people to use Python. :)"
  • abidk
    on June 08, 2012 | 22:55 abidksaid :
    "Yeah, of course, OpenCV is contributing a lot to Python API, especially last two GSoCs. Can you please share your mail id? (You can contact me on abidrahman2@gmail.com)"
  • Anonymous
    on June 18, 2012 | 03:37 Anonymoussaid :
    "I guess you'll be using warpPerspective for the next part? I tried it, and the output comes pretty close to your image in part 1.
    https://docs.google.com/open?id=0B3UoZpy_ZHzFNVo4UlhLUWctNjA"
  • abidk
    on June 18, 2012 | 23:03 abidksaid :
    "Yeah, sure. You are right."
  • solving sudoku
    on July 04, 2012 | 15:42 solving sudokusaid :
    "Occasionally, the Sudoku Solver cannot totally solve the problem for you and when this come about, you will required to click on 'unknown boxes' which in turn will display you some values that will give you a better chance of doing well."
  • Noah Watkins
    on February 12, 2013 | 21:06 Noah Watkinssaid :
    "Hi, I was wondering about a follow up to this article? It sounds like something is working on the sudoku solver front, but I'm unable to find more information. Thanks!"
  • abidk
    on February 12, 2013 | 22:35 abidksaid :
    "Hi, I couldn't prepare remaining part since I was busy with my college. If you want, I have uploaded the full code in github, you can try it : https://github.com/abidrahmank/OpenCV2-Python/tree/master/OpenCV_Python_Blog/sudoku_v_0.0.6"
  • Noah Watkins
    on February 13, 2013 | 22:08 Noah Watkinssaid :
    "Thanks! I was just interested in the code, but I do enjoy your write ups! "
Sudoku Solver - Part 2

Report "Sudoku Solver - Part 2"

Are you sure you want to report this post for ?

Cancel
×