So recently a few buddies and I decided to tackle an interesting problem-an automatic jigsaw puzzle solver. The goal was to create a robotic system, where you input the pieces of any standard piece jigsaw puzzle, and the system solves the jigsaw automatically. Below is a short video of the system in action.
This post will focus on the Image Processing of the system. The Assembling Algorithmics, Mechanics, and Electronics of the system were very challenging as well, and I plan on posting about them at a later date.
All of our code can be found at my Github. Note that the project is still in progress, therefore the repository might be a little messy. Will publish a release version soon: https://github.com/Royz2123/Puzzle-Solver
So our goal here was to assemble a jigsaw puzzle virtually. Throughout this post, we will demonstrate using a 4 X 5 jigsaw piece puzzle, however, the system works with any jigsaw of any size. The result we wish to achieve is the following assembly (It’ll take 2 posts to get there).
Let’s begin
We had an overhead camera that captured the pieces and sent them to the main computer.
The first problem we encountered was parsing the pieces. As you can see, the edges of the pieces aren’t that clear. Moreover, white pieces blend in with the background, making edge detection even tougher. Our solution to this was to make the background translucent, and shine some LED’s underneath the pieces. This creates a “burnt” effect and produces the following result.
From here we used OpenCV’s masking functions extensively. We thresholded the burnt image using cv2.threshold, in order to create a binary mask image. Then, we used cv2.findContours and crop functions to extract each individual piece.
Awesome! So now we have 20 piece images … how do they fit together? Well, every piece has 4 edges, Each consisting of a unique shape and color vector. How can we extract them? We decided to try and detect the corners of the pieces, and from there to find the edges. Notice that this shape is quite jagged and pointy, and therefore OpenCV’s Harris Corner Detection often created a lot of false positives.
After many attempts, we found a pretty elegant solution: Most points are roughly 90 degrees apart from one another and are themselves roughly 90 degrees too.
We took each piece and chose a pixel that’s roughly in the center. Next, we converted each piece to the Polar Plane using that center pixel and plotted the result using Matplotlib.
Notice how the corners are always pointy and evenly spaced. We used scipys find_peaks method on the plot and played around with the parameters. This was probably the toughest part to get perfectly right in Image Processing for this project.
After finding the corners, finding the edges was much simpler. We traversed from corner to corner along the edges of the piece, storing the pixels as we went along.
That’s it for this post! To summarize, we have now 20 parsed pieces that are ready for assembly. In the next post, we’ll explain how to assemble the final jigsaw puzzle. Feel free to contact us below and we’ll happily answer any questions you might have.
