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:
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:
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.
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
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