Finding the limits of what I can chew (Patreon)

There’s a famous anecdote about a professor back in the 60s giving a student researcher the task of getting computer vision "working" as a summer project. That was a bit of an underestimation of the problem as to this day thousands of researchers are still working on computer vision.

I hope I’m not still working on this puzzle robot when I'm 80, but boy do I feel their hubris. You see the reason I wanted to do the puzzle robot was that I knew it was a hard and interesting software problem, but also something thought I should be able to knock out in a few weeks...

Before starting the project I roughed out what I thought was a viable jigsaw solving algorithm. It was designed to deal with what I predicted would be the fundamental challenge: ambiguous piece fitting. Puzzles have many pieces that are a near perfect fit, but don't actually work when you try to assemble the rest of the puzzle. This means you can't just look at two pieces and determine if they fit - you have to consider the entire puzzle. 

These pieces don't actually fit...

The simple algorithmic way to solve this would be to figure out all possible connections between every piece and try every possible combination of all the puzzle pieces until you get one that works. The slight issue with this approach is that the number of possible combinations is a good practical approximation of infinity. You could do it, but it would take a computer thousands of years.

Knowing this, my algorithmic strategy centered around several strategies to narrow down the possible solutions and hopefully solving the puzzle in a reasonable time. What I didn't anticipate was the difficulty of getting accurate (enough) physical measurements of each piece. 

Measuring a puzzle piece with a camera will always have some amount of error. This error will make the computer think the pieces are a slightly different shape than they are in reality. If you are too strict when you compare pieces, you might conclude pieces that actually fit, don't. To account for this there needs to be some wiggle room in your comparisons. The downside of wiggle room is that it usually results in a bunch of pieces that might fit. 

Is this a bad fit, or is it a good fit with a bad camera measurement???

If you have a lot of error in your camera measurements, you will need a wide tolerance which will make it look like a metric-heck-ton of pieces potentially fit together. Unfortunately for me, there's a lot of error in my measurements. When I feed all the camera images into my algorithm it does the computer equivalent of making the skull with crossed eyes emoji followed by the tombstone emoji and then pinwheeling indefinitely.

You may recall that I used high quality telecentric lenses specifically to get accurate measurements of the pieces. Unfortunately a high quality lens doesn't really help if you're using a low quality puzzle. The puzzle I'm using has many incomplete cuts which gives the pieces fuzzy edges which makes the actual shape of the piece ambiguous. The other challenge is self inflicted: to get an all white puzzle I had to buy a not-white puzzle and paint it. Painting the puzzle resulted in many pieces with small droplets of white paint stuck to the edges which thoroughly mucks up my algorithm. 

I would love to just buy my way out of this problem with a higher quality puzzle but I can’t find another puzzle with similar piece count and dimensions to fit on my robot table, nor can I find any big all-white puzzles.

I spent much longer than I should have trying to fix these issues in software. It was a protracted cat and mouse game of implementing heuristics that would get the solver working better, but then running into a new issue. I kept saying “one more day and it should work” for 3 weeks before my card tower of software heuristics became too unwieldly ridiculous even for me and I decided to rethink my life choices. 

My tack now has been to de-garbagify the input by physically fixing the puzzle pieces. I started by manually cleaning up the edge with a razor blade, but after timing myself doing 50 pieces I had a projected completion time of 63 hours. I’d be willing to do that if I had to, but it motivated me to think harder and I came up with the idea of vibratory tumbling all of the pieces for several hours to remove any burrs, fuzzies, bits of paint, etc.

I ran the pieces in the tumbler and it is a MASSIVE improvement to the piece images. False matches are way down and I think it took the project from intractable to “I think there’s a chance.” Territory.

I’m still not out of the woods. I spent the past week trying to get my ‘solution-space-reduction’ algorithm working. It keeps telling me that it solved the puzzle, but when I look at the results it is telling me the correct solution is to randomly stack all the pieces in an overlapping pile. It also doesn’t help that my puzzle is missing several pieces...

So that’s where I’m at and hopefully explains why this one is taking me a long while to complete. I say this every time, but I’m definitely going to try to do something easier for the next project ;)

Thank you all so much for the support! You enable hard long projects like this to be done.

- Shane