Sudoku Solver - Real time Image

My last post was about solving a sudoku which was a binary image. This time I tried to solve a real time sudoku image. A real time image requires some kind of Image processing to be done before its sent to solve sudoku. Here also I am going to use the KNearest Machine learning algorithm that is available in Opencv.

Int main()

The Image shown below is a real time Image of a sudoku. I will use this image to show the steps that are needed to be done before you use it for recognizing the digits. When I searched in google I found out a good post which speaks about extracting the sudoku from the paper and it helped me achieve this.

Original Image

First the image is filtered with 3X3 gaussian kernel to remove some amount of noise present in the image. Then a adaptive thresholding technique is applied on the image. A closing operation is done on the thresholded image which does a dilation followed by erosion on the image. The closed and gray images are divided to get a narrow histogram which when normalized increases the brightness and the contrast of the image.

Code:

import sys
from matplotlib import pyplot as plt
import numpy as np
import cv2
deflt="D:\Sriram\pyprograms\sudoku\\"
img=cv2.imread("D:\Sriram\pyprograms\sudoku\sudoku.jpg",1)
img=cv2.GaussianBlur(img,(3,3),0)
frame=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
kernel=cv2.getStructuringElement(cv2.MORPH_ELLIPSE,(11,11))
close=cv2.morphologyEx(frame,cv2.MORPH_CLOSE,kernel)
div=np.float32(frame)/(close)
res=np.uint8(cv2.normalize(div,div,0,255,cv2.NORM_MINMAX))
res2=cv2.cvtColor(res,cv2.COLOR_GRAY2BGR)
#plt.imshow(res2),plt.title("res2")
#plt.xticks([]),plt.yticks([])
#plt.show()

Let us now mask out the sudoku part in the image by finding the contours. This done with assumption that sudoku occupies highest area inside the Image. A 5 % approximation is done on the contour to get a perfect shape. Finally the contour with highest area which has 4 vertices is taken out. After finding the biggest contour the sudoku is masked out by creating a mask image which has same dimensions as that of our input image. The biggest contour is filled with white while all other pixels are given zero. The mask and the res are bitwise anded to get the masked image.

thresh=cv2.adaptiveThreshold(res,255,cv2.ADAPTIVE_THRESH_GAUSSIAN_C,cv2.THRESH_BINARY_INV,11,2)
#tempthresh=cv2.resize(thresh,(450,450))
#cv2.imshow("thresh",tempthresh)
_,cnt,hr = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)
keys = [i for i in range(48,58)]
area=0
temparea=0
p=0
bestapprox=None
for i in range(len(cnt)):
 temparea=cv2.contourArea(cnt[i])
 if temparea>1000:
  peri=cv2.arcLength(cnt[i],True)
  epsilon=0.05*peri
  approx=cv2.approxPolyDP(cnt[i],epsilon,True)
  if len(approx)==4 and temparea>area:
   area=temparea
   bestapprox=approx
   p=i
img=cv2.polylines(img,[bestapprox],True,(0,255,0),3)
cv2.drawContours(img,cnt,p,(255,0,0),2)
(x,y)=thresh.shape
mask=np.zeros((x,y),np.uint8)
mask=cv2.drawContours(mask,cnt,p,255,-1)
mask=cv2.drawContours(mask,cnt,p,0,2)
masked=cv2.bitwise_and(mask,res)
cv2.imshow("masked",masked)
cv2.waitKey(0)

Now comes the part of extracting the each and every individual box in the image. Let us first find all the box points in the sudoku. For that we take Sobel in both x and y directions which gives us the edges in the respective directions, when we take absolute value of the Sobel. Absolute is taken to make negative peaks also to act as positive peaks in the image. When Sobel taken in the both the directions are anded we get box points of the image (not exactly).  The results looks as shown below.

kernelx = cv2.getStructuringElement(cv2.MORPH_RECT,(2,10))
dx = cv2.Sobel(masked,cv2.CV_16S,1,0)
dx = cv2.convertScaleAbs(dx)
cv2.normalize(dx,dx,0,255,cv2.NORM_MINMAX)
ret,close = cv2.threshold(dx,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
#cv2.imshow("dx",close)
close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernelx,iterations = 1)
_,contour, hr = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
for cnt in contour:
    x,y,w,h = cv2.boundingRect(cnt)
    if h/w > 5:
        cv2.drawContours(close,[cnt],0,255,-1)
    else:
        cv2.drawContours(close,[cnt],0,0,-1)
close = cv2.morphologyEx(close,cv2.MORPH_CLOSE,None,iterations = 2)
closex = close.copy()
#cv2.imshow("closex",closex)

kernely=cv2.getStructuringElement(cv2.MORPH_RECT,(10,2))
dy=cv2.Sobel(masked,cv2.CV_16S,0,2)
dy=cv2.convertScaleAbs(dy)
cv2.normalize(dy,dy,0,255,cv2.NORM_MINMAX)
ret,close=cv2.threshold(dy,0,255,cv2.THRESH_BINARY+cv2.THRESH_OTSU)
close=cv2.morphologyEx(close,cv2.MORPH_DILATE,kernely,iterations=1)
_,cnt, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
for i in range(len(cnt)):
    x,y,w,h = cv2.boundingRect(cnt[i])
    if w/h > 5:
        cv2.drawContours(close,cnt,i,255,-1)
    else:
        cv2.drawContours(close,cnt,i,0,-1)
close = cv2.morphologyEx(close,cv2.MORPH_CLOSE,None,iterations = 2)
closey=close
#cv2.imshow("closey",closey)
grid=cv2.bitwise_and(closex,closey)
#cv2.imshow("grid",grid)

The grid image as shown above does not give us exact box points, so we find contours in the grid, and we take centroid of all those contours using moments function that is available in Opencv.

Now there are two ways in which you get the exact output image,

Exact method:

In this method we take care of convexity defects and correct them by making some perspective transform for the whole image. But in my code I go to this method only when the length of the centroid array is 100. I hope when the paper is stiff and when it is resting on a table the probability that it gets a convexity defect is less hence with this assumption when we don’t have the above condition satisfied we go for the approximate method.

Approximate method:

This is just a normal method of taking a perspective transform and of the input image. This could have done at first without taking all the sobel stuff and finding the grid points but this method does not give us the exact sudoku structure, hence I prefer to check for the getting all the grid points, we don’t get all the grid points sometimes (Many times actually) hence if the numbers of grid points is higher than certain value we can have an assumption that we have got the exact structure of sudoku and make approximate image of sudoku.

Exact method code:

_,contour, hier = cv2.findContours(grid,cv2.RETR_LIST,cv2.CHAIN_APPROX_SIMPLE)
cent=[]
for cnt in contour:
 mom=cv2.moments(cnt)
 (x,y)=int(mom['m10']/mom['m00']),int(mom['m01']/mom['m00'])
 cent.append((x,y))
 cv2.circle(img,(x,y),4,(0,255,0),-1)
ce=np.array(cent,np.uint32)
ce=ce.reshape((100,2))
ce2=ce[np.argsort(ce[:,1])]
#print ce2 
b = np.vstack([ce2[i*10:(i+1)*10][np.argsort(ce2[i*10:(i+1)*10,0])] for i in xrange(10)])
#print b
points = b.reshape((10,10,2))
print points
output=np.zeros((450,450,3),np.uint8)
for i in xrange(3):
 for j in range(3):
  partimg=np.array([points[i*3,j*3,:],points[(i)*3,(j+1)*3,:],points[(i+1)*3,(j+1)*3,:],points[(i+1)*3,j*3,:]],np.float32)
  print partimg
  dest=np.array([[j*150,i*150],[(j+1)*150,(i)*150],[(j+1)*150,(i+1)*150],[(j)*150,(i+1)*150]],np.float32)
  gpres=cv2.getPerspectiveTransform(partimg,dest)
  warp=cv2.warpPerspective(res2,gpres,(450,450))
  output[i*150:(i+1)*150,j*150:(j+1)*150]=warp[i*150:(i+1)*150,j*150:(j+1)*150]

cv2.rectangle(output,(0,0),(450,450),0,1)
cv2.imshow("output",output)

Output Image:

Exact method analysis:

                       First of all reshape the array into a 100x2 form. Now sort the array in the order of increasing y axis values. Now sort the array in the order of increasing x axis values by taking 10 values at a time. This process is done because the points we have found will not be in the order we expected and hence we do so to get them in the required form. Now we have all the points in the perfect order. Let us take the outer square points which consists of 9 boxes inside it and apply perspective transform to them to get our desired output image.

Approx method code:

dest=np.array(bestapprox,np.float32)
nw=np.array([[0,0],[0,450],[450,450],[450,0]],np.float32)
M=cv2.getPerspectiveTransform(dest,nw)
output=cv2.warpPerspective(res2,M,(450,450))

Approx method analysis :

                       Just take the best approx points and apply perspective transform to the image. Here I take my output image to be 450X450.

And Now we have successfully extracted the sudoku from the paper. Now it's time for training the OCR and giving the values of the matrix to sudoku solver. I have written some code for training my sudoku which can be used to for generating training data. Literally I did not succeed much, on training my OCR. But sometimes it worked good.

Follow the same steps for generating a training data.

Now coming back to the testing. Take each and every 50X50 box as in my case and give it to the findNearest function. And now solve the sudoku in the same way as I mentioned in the previous post.

The solved sudoku image is shown below.

 The image I used was an example image which was used in opencv documentation. I have tried the same using a real time image. The image I used is shown below.

input

The blue line shows the original contour found. The green line shows the approximated contour.
The processed output image is shown below.

Output

The above image shows the output of the above input image. The sudoku is solved the same way as mentioned in the previous post.

My github link : Github Link for source code

Thanks to
Referring sites : Removing convexity defects
                          Digit Recognition
                          http://opencvpython.blogspot.in/

Thank you
Happy Coding :)
Cheers!!
#IIE