3

I'm writing an Android app to extract a Sudoku puzzle from a picture. For each cell in the 9x9 Sudoku grid, I need to determine whether it contains one of the digits 1 through 9 or is blank. Here are the broad strokes of my algorithm:

  • Adaptive threshold the puzzle
  • Dilate to reduce the number of contours to consider
  • Find the contours of the puzzle and warp it to a square
  • Divide the square into 81 equal cells; look for cells with at least 20% white pixels
  • Find the white blob closest to the centre of these cells and get its bounding rectangle
  • Use character recognition (k-nearest neighbours/Tesseract/etc.) on the portion of the image inside the bounding rectangle

Although I can remove the thick outer border of the Sudoku puzzle using a simple floodfill, the inner gridlines are not contiguous, even after dilation, and cannot be removed so easily. For illustration, here is a sample Sudoku after removing the outer grid lines:

enter image description here

Problem: Sometimes, there are enough gridlines in a cell that more than 20% of its pixels are white, so I misdetect that cell as having a number in it. Here is an example of such a cell:

enter image description here

I've considered unwarping the image to reduce the visibility of the inner gridlines. I could use a Hough Transform or the method described in this post to find the gridlines as a prelude to unwarping. However, I don't see any other significant benefits to unwarping, and it should be both safer and easier to just remove the gridlines entirely.

Alternatively, I could modify my pre-processing so that the inner gridlines remain intact. Currently my pre-processing is:

    Imgproc.GaussianBlur(mat, mat, new Size(11,11), 0);
    Imgproc.adaptiveThreshold(mat, matBW, 255, 
        Imgproc.ADAPTIVE_THRESH_MEAN_C, Imgproc.THRESH_BINARY_INV, 5, 2);
    Mat kernel = Imgproc.getStructuringElement(Imgproc.MORPH_CROSS, new Size(3, 3));
    Imgproc.dilate(matBW, matBW, kernel);

The Gaussian Blur is necessary to reduce noise before thresholding. The dilation is to make sure the outer gridlines are connected, but is not enough to reconnect the inner lines.

How can I consistently remove the inner gridlines, without affecting the rest of the image?

Many thanks.

Community
  • 1
  • 1
1''
  • 26,823
  • 32
  • 143
  • 200
  • I may be missing something obvious, but *why* do you need to remove the gridlines? If you already have the recognized digits arranged in a grid, can't you just re-synthesize the image? – loopbackbee Nov 08 '12 at 03:02
  • My purpose is to figure out which digits are in each cell of the Sudoku grid. To do this, I need to recognize which cells have nothing in them. If the gridlines are still there, some of the cells will appear to have something in them since more than 20% of the pixels may be white. – 1'' Nov 08 '12 at 03:22
  • @Hammer I referred to that post in my question :) SO should make their links darker. – 1'' Nov 08 '12 at 03:54

1 Answers1

2

If you don't want to make a proper unwarp, it's probably worthwhile to use smaller cells for the digit_present test.

Let's say the top left cell has coordinates (x1,y1,x2,y1)==(0,0,10,10). You could define a new cell as (x1+k,y1+k,x2-k,y2-k), k=min(x2-x1,y2-y1)/4

Another strategy that may work is to use erode before the test, depending on the thickness of the grid lines vs the digits'.

At last, you could feed all the cells to your classifier, and use its confidence indexes, if any; if the classifier confidence is too low, it's probably not a digit.

If all these approaches fails, in order to do a fill you'll have to obtain the warping of the grid lines anyway, so you might as well do the unwarping

loopbackbee
  • 21,962
  • 10
  • 62
  • 97
  • These are all very good suggestions. Unfortunately, they all have drawbacks. Erode pushes some cells with a digit below 20% white pixels. Using smaller cells cuts off some numbers which, due to warping, are near the edge of the cell. The best solution may be to unwarp and then use slightly smaller cells (maybe 1/10th rather than 1/4 off each side). – 1'' Nov 08 '12 at 16:37
  • Also, you might like to take a look at my edit to the OP. I'm wondering if I could modify my pre-processing to keep the inner lines connected from the start. – 1'' Nov 08 '12 at 16:52
  • 1
    @1'' Cutting off some numbers should not be a problem, as long as some part of the number is still inside the cell - you don't need to use the same cells for the digit_present test and for classification. About your pre-processing, I'd try to change the threshold value (2), and maybe the block size too. – loopbackbee Nov 08 '12 at 17:33
  • Actually, it seems like 5 and 2 are the optimal values. Over a wide range of values, it's impossible to get the parts of the thin gridlines right next to the thick gridlines to turn white, probably because the threshold is lowered too much by all the black pixels of the outer gridlines. – 1'' Nov 08 '12 at 23:52
  • Great point about using different cells for the two tests, though! That may very well be the best solution. – 1'' Nov 08 '12 at 23:53
  • @1'' Great! I hope you fare well on the classification :) – loopbackbee Nov 09 '12 at 23:34