How to remove convexity defects in a Sudoku square?

I have a solution that works, but you'll have to translate it to OpenCV yourself. It's written in Mathematica.

The first step is to adjust the brightness in the image, by dividing each pixel with the result of a closing operation:

src = ColorConvert[Import["http://davemark.com/images/sudoku.jpg"], "Grayscale"];white = Closing[src, DiskMatrix[5]];srcAdjusted = Image[ImageData[src]/ImageData[white]]

The next step is to find the sudoku area, so I can ignore (mask out) the background. For that, I use connected component analysis, and select the component that's got the largest convex area:

components =   ComponentMeasurements[    ColorNegate@Binarize[srcAdjusted], {"ConvexArea", "Mask"}][[All,     2]];largestComponent = Image[SortBy[components, First][[-1, 2]]]

By filling this image, I get a mask for the sudoku grid:

mask = FillingTransform[largestComponent]

Now, I can use a 2nd order derivative filter to find the vertical and horizontal lines in two separate images:

lY = ImageMultiply[MorphologicalBinarize[GaussianFilter[srcAdjusted, 3, {2, 0}], {0.02, 0.05}], mask];lX = ImageMultiply[MorphologicalBinarize[GaussianFilter[srcAdjusted, 3, {0, 2}], {0.02, 0.05}], mask];

I use connected component analysis again to extract the grid lines from these images. The grid lines are much longer than the digits, so I can use caliper length to select only the grid lines-connected components. Sorting them by position, I get 2x10 mask images for each of the vertical/horizontal grid lines in the image:

verticalGridLineMasks =   SortBy[ComponentMeasurements[      lX, {"CaliperLength", "Centroid", "Mask"}, # > 100 &][[All,       2]], #[[2, 1]] &][[All, 3]];horizontalGridLineMasks =   SortBy[ComponentMeasurements[      lY, {"CaliperLength", "Centroid", "Mask"}, # > 100 &][[All,       2]], #[[2, 2]] &][[All, 3]];

Next I take each pair of vertical/horizontal grid lines, dilate them, calculate the pixel-by-pixel intersection, and calculate the center of the result. These points are the grid line intersections:

centerOfGravity[l_] :=  ComponentMeasurements[Image[l], "Centroid"][[1, 2]]gridCenters =   Table[centerOfGravity[    ImageData[Dilation[Image[h], DiskMatrix[2]]]*     ImageData[Dilation[Image[v], DiskMatrix[2]]]], {h,     horizontalGridLineMasks}, {v, verticalGridLineMasks}];

The last step is to define two interpolation functions for X/Y mapping through these points, and transform the image using these functions:

fnX = ListInterpolation[gridCenters[[All, All, 1]]];fnY = ListInterpolation[gridCenters[[All, All, 2]]];transformed =  ImageTransformation[  srcAdjusted, {fnX @@ Reverse[#], fnY @@ Reverse[#]} &, {9*50, 9*50},   PlotRange -> {{1, 10}, {1, 10}}, DataRange -> Full]

All of the operations are basic image processing function, so this should be possible in OpenCV, too. The spline-based image transformation might be harder, but I don't think you really need it. Probably using the perspective transformation you use now on each individual cell will give good enough results.

Nikie's answer solved my problem, but his answer was in Mathematica. So I thought I should give its OpenCV adaptation here. But after implementing I could see that OpenCV code is much bigger than nikie's mathematica code. And also, I couldn't find interpolation method done by nikie in OpenCV ( although it can be done using scipy, i will tell it when time comes.)

1. Image PreProcessing ( closing operation )

import cv2import numpy as npimg = cv2.imread('dave.jpg')img = cv2.GaussianBlur(img,(5,5),0)gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)mask = np.zeros((gray.shape),np.uint8)kernel1 = cv2.getStructuringElement(cv2.MORPH_ELLIPSE,(11,11))close = cv2.morphologyEx(gray,cv2.MORPH_CLOSE,kernel1)div = np.float32(gray)/(close)res = np.uint8(cv2.normalize(div,div,0,255,cv2.NORM_MINMAX))res2 = cv2.cvtColor(res,cv2.COLOR_GRAY2BGR)

Result :

2. Finding Sudoku Square and Creating Mask Image

thresh = cv2.adaptiveThreshold(res,255,0,1,19,2)contour,hier = cv2.findContours(thresh,cv2.RETR_TREE,cv2.CHAIN_APPROX_SIMPLE)max_area = 0best_cnt = Nonefor cnt in contour:    area = cv2.contourArea(cnt)    if area > 1000:        if area > max_area:            max_area = area            best_cnt = cntcv2.drawContours(mask,[best_cnt],0,255,-1)cv2.drawContours(mask,[best_cnt],0,0,2)res = cv2.bitwise_and(res,mask)

Result :

3. Finding Vertical lines

kernelx = cv2.getStructuringElement(cv2.MORPH_RECT,(2,10))dx = cv2.Sobel(res,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)close = cv2.morphologyEx(close,cv2.MORPH_DILATE,kernelx,iterations = 1)contour, hier = 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()

Result :

4. Finding Horizontal Lines

kernely = cv2.getStructuringElement(cv2.MORPH_RECT,(10,2))dy = cv2.Sobel(res,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)contour, hier = cv2.findContours(close,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)for cnt in contour:    x,y,w,h = cv2.boundingRect(cnt)    if w/h > 5:        cv2.drawContours(close,[cnt],0,255,-1)    else:        cv2.drawContours(close,[cnt],0,0,-1)close = cv2.morphologyEx(close,cv2.MORPH_DILATE,None,iterations = 2)closey = close.copy()

Result :

Of course, this one is not so good.

5. Finding Grid Points

res = cv2.bitwise_and(closex,closey)

Result :

6. Correcting the defects

Here, nikie does some kind of interpolation, about which I don't have much knowledge. And i couldn't find any corresponding function for this OpenCV. (may be it is there, i don't know).

Check out this SOF which explains how to do this using SciPy, which I don't want to use : Image transformation in OpenCV

So, here I took 4 corners of each sub-square and applied warp Perspective to each.

For that, first we find the centroids.

contour, hier = cv2.findContours(res,cv2.RETR_LIST,cv2.CHAIN_APPROX_SIMPLE)centroids = []for cnt in contour:    mom = cv2.moments(cnt)    (x,y) = int(mom['m10']/mom['m00']), int(mom['m01']/mom['m00'])    cv2.circle(img,(x,y),4,(0,255,0),-1)    centroids.append((x,y))

But resulting centroids won't be sorted. Check out below image to see their order:

So we sort them from left to right, top to bottom.

centroids = np.array(centroids,dtype = np.float32)c = centroids.reshape((100,2))c2 = c[np.argsort(c[:,1])]b = np.vstack([c2[i*10:(i+1)*10][np.argsort(c2[i*10:(i+1)*10,0])] for i in xrange(10)])bm = b.reshape((10,10,2))

Now see below their order :

Finally we apply the transformation and create a new image of size 450x450.

output = np.zeros((450,450,3),np.uint8)for i,j in enumerate(b):    ri = i/10    ci = i%10    if ci != 9 and ri!=9:        src = bm[ri:ri+2, ci:ci+2 , :].reshape((4,2))        dst = np.array( [ [ci*50,ri*50],[(ci+1)*50-1,ri*50],[ci*50,(ri+1)*50-1],[(ci+1)*50-1,(ri+1)*50-1] ], np.float32)        retval = cv2.getPerspectiveTransform(src,dst)        warp = cv2.warpPerspective(res2,retval,(450,450))        output[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1] = warp[ri*50:(ri+1)*50-1 , ci*50:(ci+1)*50-1].copy()

Result :

The result is almost same as nikie's, but code length is large. May be, better methods are available out there, but until then, this works OK.

RegardsARK.

You could try to use some kind of grid based modeling of you arbitrary warping. And since the sudoku already is a grid, that shouldn't be too hard.

So you could try to detect the boundaries of each 3x3 subregion and then warp each region individually. If the detection succeeds it would give you a better approximation.