extracting a sudoku puzzle from a photo

After a little pacing, I came up with this solution for part 1 of the sudoku solver.

2887035105_a4f6a2421f

(can’t remember where I got the image – national championship, philadelphia). First, we convert the image into black/white.

bw

Then we remove all the black dots which don’t have another black dot to the top/right/bottom/left. That cleans it up just a little, but every little helps.

Now, we extract every grouping of black pixels, using the flood fill algorithm. Discard any with less than, say, 300 black pixels in total (too small to be the frame we’re looking for). Here are clips of the remaining images:

bw_0bw_1bw_2bw_3bw_4

One cool thing about a square is that in a cropped image of the square (cropped close to the edge of it), the ratio of width/height of the image is almost exactly 1:1. This is true even if you rotate the image (around the Z axis). The ratio can change if the square is tilted back or turned in some way, but we will assume that someone photoing a sudoku grid will be facing it square.

So, from those images, we choose the one which is closest in ratio to 1:1. to do this, just divide width by height. if the number is less than 1, divide height by width. If the number is greater than, say, 1.1, discard the image. In this case, there’s just one image remaining:

bw_final

In the case I’ve presented, there was just one image remaining. I had one more trick up my sleeve in case there was more than one, and that was to choose the image which had the lowest ratio of black to white pixels.

Anyway – now we have the grid, so I’ll get to the number recognition next.

3 Comments.

  1. Good idea – may be something that you could potentially make money from!

  2. This is getting interesting. Waiting for the next post on OCR.

  3. working on it 😉 I’ve already discarded single layer feed forward networks as candidates (too pattern-specific), and multi-layer FFNs as well (too hard to train), so am writing a recurrent network to see if that works any better

%d bloggers like this: