Sudoku Image Recognition                                                                 

Someone had a good question, on how I read the Sudoku image digits and determine the numbers 1 through 9 using VB6.

One hundred grid corners found

The USB camera delivers a bitmaped 640x480 image. The Sudoku grid in the image is a rhomboid of about 300 pixels across, so each small Sudoku cell is only about 30 pixels square. For character recognition proposes, it is very important to have each square’s precise corner coordinates. There are 100 grid corner points, each with VB6 picturebox XY location values. The integer array value of GridX(0,0) is the x location of top and left-most corner of the Sudoku grid. The array value of GridY(9,9) is the Y location of top and right-most corner of the Sudoku grid. Unfortunately, the perfect square of the Sudoku grid is warped by the laws of perspective, such that areas closer to the camera appear larger. In this image, my camera is to the left of the puzzle such that the left part of the grid appears larger than the right. I did some intense calculating until I was able to precisely determine each grid corner location. The grid corners are marked with blue dots.

Cartoons

So, how to determine a number in a grid box? The algorithm I use, is to look for the best match to a cartoon image of the number. I made ten bitmapped cartoon 50x50 images named Cartoon0.bmp to Cartoon9.bmp. I made the cartoon images on photoshop-like software and they are pattered exactly the same as the newspaper Sudoku font. The cartoons have black numbers on a red oval background. To speed up my sluggish VB6 program, I read the cartoon images into an integer array called Cartoon(9, 50, 50) where a value of 0 = white, 1 = black and 2 = red.

Cartoon warping

The cartoons are not the same size or shape of the Sudoku grid boxes; each cartoon must be stretched and warped such that it’s corners match up with the grid corners. Since the cartoons are all the same size, this warping only needs to be done once per grid box and takes the form of 50x50 point look-up arrays named PX(50,50) and PY(50,50). Each pixel of a cartoon gets a corresponding XY coordinate on the Sudoku grid box. First, the four PX&PY corners (0,0), (0,50), (50,0), (50,50) are set equal to the four grid box corners. Then look-ups for the top and bottom rows are calculated by dividing those rows into 50 equal distant points. Now each column has top and bottom coordinates and each column is divided into 50 equal segments. The result is a warped cartoon to perfectly match the Sudoku box. Not only has the square shape of the cartoon been morphed into a rhomboid, but the cartoon number image itself has been morphed into the appropriate shape as if viewed from the perspective of the camera! 

Cartoon pixels are looked at one by one and are graded against the corresponding Sudoku image pixels:

If a black cartoon pixel falls on a black Sudoku pixel; add a point.

If a black cartoon pixel falls on a white Sudoku pixel; subtract two points.

If a red cartoon pixel falls on a white Sudoku pixel; add a point.

If a red cartoon pixel falls on a black Sudoku pixel; subtract two points.

White cartoon points are not graded. Each cartoon has 924 graded points.

The cartoon number with the highest grade is the number in the puzzle.

To get the best possible fit between cartoon and image, I jiggle the cartoon + 7 pixels back-and-forth and up-and-down while grading. If a cell has a very high score with the blank (cartoon0) then it is rapidly marked as an empty cell. Amazingly, smudges and other artifacts on the Sudoku image end up being graded as empty cells.

If the corners of the grid boxes are accurately determined then this method of number recognition works well; better than 99%. This method is font specific, so if other characters or fonts are to be read, then additional cartoons would need to be made. The character recognition is CPU intensive and takes about one second per non-blank character.

This VB6 program is terribly unstructured and gangly. It is not suitable for some kind of plug and play or even for basic sharing for that matter, but I will post some snippets as requested. The integer array Mono(640,480) contains the Sudoku monochromatic image: values of 0 = white and 1 = black. I do not think these snips will help anyone, but good luck just the same.

----------------------------------------------------------------------

Private Sub LoadCartoons() ‘ loads bitmaped cartoon images into Cartoon array

Dim I As Integer, J As Integer, K As Integer

Dim C As Long

For K = 0 To 9

For I = 0 To 50

For J = 0 To 50

    C = picCartoon(K).Point(I, J)

    If C < 10 Then Cartoon(K, I, J) = 1 ' Black

    If C > 99999 Then Cartoon(K, I, J) = 0 ' White

    If C > 10 And C < 99999 Then Cartoon(K, I, J) = 2 ' red

Next J

Next I

Next K

End Sub

'----------------------------------------------------------------------

‘This is where I make cartoon point lookup arrays PX(50,50) and PY(50,50).

‘GX and GY are the cell of interest upper left grid point values.

‘GX and GY values are integers from 0 to 8.

‘XOff and Yoff are offset values I use to giggle the cartoon for the best fit.

Private Sub MakeLookups(GX As Integer, GY As Integer, XOff As Integer, YOff As Integer) ' fill PX and PY arrays

Dim I As Integer, J As Integer

Dim dX As Integer, dY As Integer

‘These are the lookups for the four corners of the cartoon.

PX(0, 0) = GridX(GX, GY) + XOff: PY(0, 0) = GridY(GX, GY) + YOff

PX(0, 50) = GridX(GX, GY + 1) + XOff: PY(0, 50) = GridY(GX, GY + 1) + YOff

PX(50, 0) = GridX(GX + 1, GY) + XOff: PY(50, 0) = GridY(GX + 1, GY) + YOff

PX(50, 50) = GridX(GX + 1, GY + 1) + XOff: PY(50, 50) = GridY(GX + 1, GY + 1) + YOff

dX = PX(50, 0) - PX(0, 0) 'pos

dY = PY(50, 0) - PY(0, 0) ' top row deltas ±

For I = 1 To 49                  ' Calculate  cartoon lookups

    PX(I, 0) = Int(PX(0, 0) + dX * I / 50 + 0.5) 'Top row

    PY(I, 0) = Int(PY(0, 0) + dY * I / 50 + 0.5)

Next I

dX = PX(50, 50) - PX(0, 50) 'pos

dY = PY(50, 50) - PY(0, 50) ' bottom row deltas ±

For I = 1 To 49                  ' Calculate  cartoon lookups

    PX(I, 50) = Int(PX(0, 50) + dX * I / 50 + 0.5) 'bottom row

    PY(I, 50) = Int(PY(0, 50) + dY * I / 50 + 0.5)

Next I

For I = 1 To 49 ' calculate column cartoon lookups

    dY = PY(I, 50) - PY(I, 0) 'pos

    dX = PX(I, 50) - PX(I, 0) ' colunm deltas ±

                

    For J = 1 To 49

        PY(I, J) = Int(PY(I, 0) + dY * J / 50 + 0.5) 'columns

        PX(I, J) = Int(PX(I, 0) + dX * J / 50 + 0.5)

    Next J

Next I

End Sub

'----------------------------------------------------------------------

‘A single cartoon (Number) is scored against a Sudoku cell. A score is returned.

Private Function ScoreCell(Number As Integer) As Integer

Dim C As Integer, Total As Integer, S As Integer

ScoreCell = 0

Total = 0

For I = 0 To 50

For J = 0 To 50

    C = Cartoon(Number, I, J)

    If C <> 0 Then Total = Total + 1 'total non-white points (924)

   

    If C = 1 Then 'black cartoon

        Total = Total + 1

        If Mono(PX(I, J), PY(I, J)) = 1 Then S = S + 1 'black on black

        If Mono(PX(I, J), PY(I, J)) = 0 Then S = S - 2 'black on white

    End If

    If C = 2 Then ' red cartoon

        If Mono(PX(I, J), PY(I, J)) = 0 Then S = S + 1 ' red on white

        If Mono(PX(I, J), PY(I, J)) = 1 Then S = S - 2 ' red on black

    End If

     

Next J

Next I

If Total = 0 Then Exit Function

ScoreCell = S / Total * 100

If Number = 0 Then ScoreCell = ScoreCell - 20 ' blank cell is a little too hot!

End Function
'----------------------------------------------------------------------