SuDoKu!

Hello Everyone!

So, this is my first blog post!

Here I’ll talk about a very simple app that i tried to make.

It is a Sudoku Grabber.
It takes an image as the input and extracts the Sudoku and the individual digits from the image.

I’ll start by describing the different techniques i have used and then a step-by-step explanation of my algorithm.

The basic technique used is the application of contours in an image.
Simply put Contours are nothing but boundaries of a particular pattern. Identification of the different connected components in an image.
Say for example the image shown below has a circle , a square and some text. The second image shows us the different contours in that image. It has Identified the circle , the square and the different alphabets separately(White parts in the second image are contours).

Circle , Square , Text

Contours

So, we will basically extract the different contours in our input image and then try to identify the correct contour that represents our SuDoKu grid. For this I have made an assumption that the contour with the largest area will be our grid. It is a safe assumption to make because anyone would focus on the SuDoKu more for our purpose.

Let’s start!

1. Prepare the Image.
   First apply an adaptive threshold on the image.
   Adaptive Threshold forms a binary version of the image, which will be used for finding the contours in the image. Binary Images are also easy to operate on.

   Mat thresh(Mat img)
   {
   cvtColor(img,img,CV_BGR2GRAY);
   Mat img_t=Mat::zeros(img.size(),CV_8UC3);
   adaptiveThreshold(img,img_t,255,ADAPTIVE_THRESH_MEAN_C,THRESH_BINARY_INV,5,10);
   return img_t;
   }

   The above code takes an input image converts it to a gray scale image first and then thresholds the image.

   

   Adaptive Threshold

2. Extract the Grid.
   
   Next step is to extract the grid from the thresholded image.
   This is where we find contours in our image.

   Mat grid_extract(Mat img)
   {
     int index;
     double max;
     Mat grid;
     grid=Mat::zeros(img.size(),CV_8UC1);
     vector<vector<Point> > contour;
     vector<Vec4i> h;
     vector<Point> req;
   
     findContours(img,contour,h,CV_RETR_TREE,CV_CHAIN_APPROX_SIMPLE,Point(0,0));
   

   The above code snippet we initialize a new Mat type Image and a vector of vectors which will store our contours.

   We actually find contours in line 11.
   After finding the contours we find out the contour with the maximum area.

     max=contourArea(contour[0]);
     for(int i=0;i<contour.size();i++)
     {
       double temp;
       temp=contourArea(contour[i]);
       if(max<temp)
       {
         max=temp;
         index=i;
         req=contour[i];
       }
     }
   

   Displaying the grid.

     drawContours(grid,contour,index,Scalar(255,255,255),CV_FILLED,8,h);
     namedWindow("Grid",0);
     imshow("Grid",grid);
     waitKey(0);
     return grid(boundingRect(req));
   }
   

   

   Extracted Grid

3. Extracting Digits from the Grid.After having extracted the grid from the given image, we now have to extract the digits.This is a two step process.
   From the grid first remove the Grid Lines and then extract the digits.
   1. Removing Grid Lines. Hough Transformation is a very good way of detecting shapes(lines , circles….) in an image. Using this we will detect grid lines in our image and remove them.
      
      After detecting lines in our grid(using Hough Transform) we will iterate over each line one by one and paint the line black. We are painting our lines black to merge them with the background(which is black after Adaptive Thresholding), which is as good as removing them from our image.

      //Function to remove the lines from the grid(To seperate out digits from the grid)
      Mat hough(Mat img)
      {
      	vector<Vec4i> lines;
      	HoughLinesP(img,lines,1,CV_PI/180,100,30,10);
      	for(int i=0; i<lines.size();i++)
      	{
      		Vec4i l=lines[i];
      		line(img,Point(l[0],l[1]),Point(l[2],l[3]),Scalar(0,0,0),10,CV_AA);
      	}
      	imshow("Digits",img);
      	waitKey(0);
      	return img;
      }
      

      After this operation parts we are left with only the digits.

      

      After Hough Transformation

   2. Extracting Digits. To extracts digits again we will use contours. We will again find contours in our image.
      Contours that we get this time will be our digits only.

      void digit_extract(Mat img)
      {
      	Mat digit;
      	vector<vector<Point> > contour;
      	vector<Vec4i> h;
      
      	findContours(img,contour,h,CV_RETR_TREE,CV_CHAIN_APPROX_SIMPLE,Point(0,0));
      	for(int i=0;i<contour.size();i++)
      	{
      		vector<Point> temp;
      		temp=contour[i];
      		img(boundingRect(temp)).copyTo(digit);
      		namedWindow("Digit",0);
      		imshow("Digit",digit);
      		waitKey(500);
      	}
      }
      

      To operate on the digits separately(like digit recognition…) we can set a ROI in our image(Line 12).

      

      2(Scaled UP image)

      

      3(Scaled UP image)

Finally we now have the digits extracted. 🙂

To further build upon this we can actually solve the puzzle using the extracted information.

🙂
Salil