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

Waldo                                                                                      

wikipedia.org/Waldo

As a kid, I read Heinlein’s short story, Waldo and I've wanted to build robotic hands ever since. I had a bunch of junk laying around that I bodged together to make an Arduino controlled robotic hand that is designed to fill in the missing numerals on the newspaper Sudoku puzzle. (See previous posts for how the Sudoku solution was obtained.) 








 

Mustek scanner

Waldo’s base was made from a nonfunctioning Mustek flatbed scanner. I use the scanner’s 12V stepper motor, electronics and drive-train to move Waldo’s arm from side-to-side. I mounted a piece of whiteboard to the scanner top for a writing platform.





 

Rack&pinion mechanism

I used a rack–and-pinion mechanism from a discarded medical instrument to move Waldo’s arm from front-to-back. This step motor driven device was mounted onto the scanner’s drive train and required a support wheel riding on an adjustable rail. The arm traverses a 9 x 6 inch area of the writing platform in an (X,Y) fashion.

Waldo's hand

I made a mechanical hand that holds a gel pen refill. There are three degrees of movement actuated by small servo motors. Two of the servos can finely move the pen over a diamond shaped area of about a half inch across. This is used for the detail work of drawing the digits 1 through 9. The third servo can lift the pen off the paper.




 

Waldo nearly finished

A PVC lamp stand (and USB camera) is attached to a box-like scanner cover. I am really happy with the looks of the finished device!








 

A Sudoku Image Recognition Program                                                

Newspaper image capture

It is amazing to me, that the eye can recognize objects so quickly and apparently so easily. I suspect that a significant amount of parallel processing occurs locally in the eye that helps with edge and surface detection. The conscious brain is usually not even aware of what must be the huge amount of computing to make sense of the morning newspaper. I get a glimpse of the enormity of the problem when I open one of those multi language instruction booklets and it takes me a few moments to realize that I’m trying to read German.

A computer is far worse off because the only thing it “knows” is what is going on at a single given pixel. In one image there are a lot of pixels (640x480=307,200) and as the “attention” moves to the next pixel, it forgets what it had just seen. I write algorithms for computers as if I were making instructions for someone with extreme tunnel vision who has little ability to make long term memories.

Gray-scale conversion

But first I must capture a USB camera bitmaped image in the computer. Some kind soul, made this relatively easy in VB6, by writing a short module that utilizes the SendMessage command of the USER32 API. Download at: USBCammod.bas

Then by using simple commands, the USB cam is turned on and images are continuously sent to the windows clipboard. The clipboard data is constantly copied to a VB6 picturebox and you see a live video image in the form’s picturebox. Still images are captured from the clipboard in the same way.

  

mCapHwnd = capCreateCaptureWindow("WebcamCapture", 0, 0, 0, 640, 480, H, 0)

 DoEvents

 SendMessage mCapHwnd, CONNECT, 0, 0

 CamRunning = True

 Do While CamRunning

     SendMessage mCapHwnd, GET_FRAME, 0, 0

     SendMessage mCapHwnd, COPY, 0, 0

     PIC.Picture = Clipboard.GetData

     DoEvents

 Loop

Monochromatic image

A bitmapped color image can be converted to a gray-scale image by averaging each RGB pixel value and then writing the average back into each of the RGB pixel locations. A RGB color value of (10, 9, 2) is converted to gray- scale value of (7, 7, 7). Gray-scale images can be converted into two toned (monochromatic) images by comparing to a cutoff value. Gray-scale values above the cutoff produce white points and values below the cutoff are black points.

Background cutoff values

The trick of making a decent monochrome image is to find where  to set the cutoff. The cutoff needs to be set to unique values in different areas of an image. I used an algorithm that looked at local blocks of 96x96 pixels that found the gray-scale distribution. The highest distribution peek of a newsprint image is always the white background color. I defined the local cutoff value to be the first low (1/4 peek value) distribution area on the dark side of the peek. So now, the gray-scale values of the image are graded against the local cutoff and a strong monochromatic image is produced. I also copy these monochromatic values into a 640x480 byte array because VB6 can do calculations on array data faster than it can draw or read pixel values from an image.

So starting with a monochromatic image of a newspaper, I need to identify the Sudoku grid and determine the beginning values. Here is the algorithm that I used:

Detection of horizontal & vertical lines

    1.    Look for relatively horizontal and vertical lines in the image and overwrite the monochromatic image with these red lines. It  is relatively easy to look at the points along possible lines and grade how many black points are intercepted. If the number of black points passes a threshold, then draw the line.

Cleaned up image

    2.    Cleanup the image by removing all red pixels that had not overwritten monochromatic black.

Flood-fill with yellow

    3.    Starting from the image edges, flood-fill all white or black pixels with the color yellow. The yellow flood does not cross the solid red lined boarder of the Sudoku grid and leaves it’s interior cells white with black numbers.

    4.    Record the coordinates of the four corners of the Sudoku grid by detecting the first white pixels found, while working diagonally inward from the image corners. I had to made a test that eliminated corner detection false alarms (small islands of white in the sea of yellow).

Corner detection & parsing

    5.    Using the four Sudoku corner coordinates, calculate the coordinates of all 81 cell corners (marked by blue dots).

    6.    Parse each Sudoku cell by grading the number of pixels that match an idealized cartoon of the numbers 1 to 9 and a blank. The cartoon image corners are stretched to match up with each of the Sudoku cell corners. The cartoon is then jiggled around a bit, left & right, up & down, to find the best fit to the monochrome image. The highest scoring cartoon should be the correct cell value. Draw in the cell value (overwrites in red).

Puzzle solved

    7.    Solve the puzzle by repeatedly applying the LookForSingles and the LookForPairs algorithms. Draw in the cell value.

    8.    Write the solution and cell coordinates to a text file stored on the hard drive. (To be used in a future project)

The program is long, gangly and uses 50% of the CPU power for 37 seconds to visual recognize a Sudoku puzzle and parse the starting numbers. The puzzle solving part  takes less than a second. I include here, a captured screen video of the program running. The video capture software heavily uses the CPU and slows the Sudoku recognition considerably. In the video, it takes 108 seconds to identify and solve the puzzle.

Sudoku Solving Program                                                                          

Newspaper Sudoku

Well I got so discussed with the Stirling engine project that my mind started looking for diversions and, before I knew it, I was writing another image recognition program.

Sudoku solving program

A couple of years ago, I wrote a Sudoku VB6 program where I could enter the starting numbers into a 9x9 grid and the computer would fill in the remaining blank cells with the solution. I used the program to find out where I went wrong when I made a mistake doing a Sudoku, so I could back track and finish the puzzle. When writing the program, I realized right away that using a brute–force approach of looking for all possible puzzle number combinations was not going to work, due to the very high number of possibilities (Wiki says 6.67×10²¹⁾. In the program, I used the same algorithms that I apply when solving a puzzle.  I am not sure if all puzzles can be completely solved by these two algorithms but the program routinely solves the daily puzzles from the newspaper in a few tenths of a second.

Sudoku single

The Look-For-Singles algorithm finds what I call give-away-cells; cells that could only be filled by a single number.  Say a row contained the numbers 12345678. The empty cell could only be a nine. The way the algorithm detects this cell is by first filling all 81 cells of a grid with the string “123456789”,  then as each new answer is entered in the grid, that digit is removed from each cell string in that row, in that column and in that block. If any of the resulting cell strings diminish to the length of one character then a new result has been found.

Another Sudoku single

 In addition, any row, column or block that contains only one instance of a number, is also a solution. These processes are repeated until no new results are found. Newspaper Sudoku puzzles with one, two or three star difficulty ratings can usually be solved using this algorithm alone.

Sudoku Pair

If the Singles algorithm leaves some cells unsolved then the Look-For-Pairs algorithm is used. It looks for pairs of cells where the same two numbers are only possible in each. Say the top row contained the numbers BBB4567BB (B = a blank cell) and the top left block also contained the numbers 8 & 9. Each of the two empty cells at the end of the top row could only contain an eight or a nine. You still don't know which of those two cells contains the 8 & 9, but you can eliminate all other possible solutions. When the other solutions are eliminated from paired cells, it sometimes leaves adjacent rows, columns or blocks with new single solutions that the Look-For-Singles algorithm can find. 

So these two algorithms are repeatedly run until no additional answers are found. Newspaper Sudoku puzzles with four or five star difficulty ratings can usually be solved using one to three passes of these algorithms.

When I find that I’ve gone wrong solving a Sudoku puzzle, I get pretty irritated. Then I go to the puzzle solver program and get even more irritated tediously entering the 20 to 30 starting  numbers to find I’ve made a mistake doing that too. I kept thinking that the damn computer should be able to read the damn puzzle and solve it. So I wrote a program to do just that!