Waldo Success                                                                                     

The green LED  is viewed as white!

It turns out that the green LED was not the best way to detect Waldo’s hand position. The bright LED caused the camera to go to total light saturation at that spot, so the camera registered pixel RGB levels of 255, 255, 255, which is white, not green. The background is already white. I could blink the LED and look for the spot that changed brightness but I would need to capture and process two images per move and would at least double the detection time.

Black ink has some blue pixels!

What I need to use for location detection, is a unique color. I have covered Waldo’s hand with a Child’s red glove that has green lettering on the back, so those colors are no good. I tried seeking out the color blue, but unhappily, the black pen ink, when looked at by the camera, is digitalized into a whole host of pixel colors, including blue. 

Yellow target between thumb & finger,.

There are very few yellow pixels in the images, so I glued a bright yellow 3mm plastic disk at he head of the pen and used an algorithm looking for small blocks of pixels (3x3) that had values of blue < 20, Green > 120 and Red > 120. Since most pixels in the images have lots of blue, those blocks are quickly eliminated and the hand position detection takes only about a half second per captured image.

Yellow target pixels.

I had to make a crazy math function that uses the current stepper position of Waldo’s hand, the current position of the yellow dot and the Sudoku image cell’s target position to calculate an estimate of where to next move Waldo’s hand. The XY steppers moves are not exact but they get the hand to within 90% of where it should be. I capture another image and move the hand again to within 99% of the target position. I do three consecutive moves to each target position.

Waldo filled-in puzzle.

 So the steppers move the pen to the center of an empty Sudoku square and the hand servos fill in the number. The process is very similar to how humans write and the hand has an uncanny human look about it. It takes about three seconds to move to each cell location and write a digit. The writing process takes about 3.5 minutes for a Sudoku puzzle. The whole process, from capturing the first image of the Sudoku to completely filled in puzzle, takes 4 minutes and 40 seconds.

Check out the amateur video.

Waldo Nuts and Bolts                                                                    

Waldo wiring layout.

The problem with bodging things together is that the various parts do not use the same supply voltage. A 12 VDC, 4Amp wall-wartish supply provides power for the scanner stepper motor. For $2.19 each (eBay), I bought a bunch of adjustable Step-Down DC switching converters, that take the 12v supply and convert to 4.1V for the rack-and-pinion motor and to 6.0V for the servos. The Arduino likes 9V for its supply but since I will always be USB connected to my computer, I let the USB supply it’s power.

Waldo's wiring.

The Arduino provides the timing signals for the step motors and servos. The TD62003AP driver for the scanner’s six wire stepper motor resides on the original scanner board but I had to make an H-bridge motor driver (SN754410NE $2.58 from Mouser) for the four wire rack-and-pinion stepper motor.

X and Y position flag sensors.

A couple of scavenged flag sensors are placed so stepper home positions can be determined. I wired in a momentary “start” switch on the scanner case to notify the host when to capture a Sudoku image and to begin analysis of the image.

VB6 Waldo interface.

A VB6  interface program on my computer sends character string commands that the Arduino decodes into actions. Codes “0N” through “9N” execute predefined servo movements that drops the pen to the paper, draws the called character and then lifts the pen. Codes “0X” through “0052X” move Waldo’s arm to the X step positions 0 to 2500. Note, I send the string digits in reverse order (the least significant digit is sent first.)  Codes “0Y” through “005Y” move Waldo’s arm in the Y direction;  step positions 0 to 500 (again sent in reverse order). Codes “1L” and “0L” turn the LED on and off. Code “H” homes Waldo’s arm to X = 0 and Y = 0. 

Meanwhile, the USB camera is watching a green LED on the head of the pen to determine the pen’s location within it’s field of view. This process turned out to be more difficult than I expected and I'm still working on some glitches. Frustratingly, the USB camera controls cause conflicts with the Arduino USB communication and visa-versa. I have worked out what seems to be an overly complicated timing scheme using five VB6 timer controls and I have successfully filled in one puzzle. The detection of the green LED in the camera image is taking too long and it is still a bit unreliable. By the net post, I hope to have video of the completed project. 

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
'----------------------------------------------------------------------