It’s been a while, but we wanted to finish the automatic jigsaw solver saga that we started last year. For a recap of the previous part, check out Part 1. In this part, we focus on the assembly of the actual puzzle.
We finished the previous part after we have already created 20 “parsed” pieces (a parsed piece is an image of a single puzzle piece with detected corners, centroid, and edges).
The assembly of the entire puzzle can be separated into 2 sub-objectives:
- Defining a compatibility metric between edges — This is a fancy way of saying: Do 2 pieces fit this way? Basically, we need to define a function that gets as input 2 edges (we’ll get into that in a bit) and outputs their compatibility.
- Algorithmically solving the puzzle — Assuming we have a compatibility metric, how do we actually go about solving the puzzle? We don’t know the original dimensions of the puzzle (Say “5x4”), So even a brute force approach isn’t trivial. The main balance here is between accuracy and computational complexity. Our metric will never be perfect, so we might need data from quite a few surrounding pieces in order to be sufficiently certain that they fit.
Let’s start off with a metric — intuitively when one goes about matching pieces in a puzzle, they start by looking at pictures that look as if they fit, and then they physically try putting the 2 edges together. So we have 2 compatibility metrics here — a Picture Metric and a Shape Metric.
We started off by implementing the Shape Metric. We extracted the 4 edges of every piece and stored them as separate binary images.
Now in order to compare 2 binary edge images, we need to rotate one of them by 180 degrees, put them on top of each other, and see how well they fit. We did this by flipping one of the images, using the XOR operator between the images, and then adding up all the places where we got a “0”. Notice that the XOR operator is exactly what we need for this problem because it counts all the places where the 2 edges disagree. This happens because we get a “0” either if the edges overlap, or if they leave an empty space between the pieces.
So this defines the Shape Metric — an integer representing how well the edges physically fit together.
We then tried defining the Picture Metric. Admittedly, this metric only partially worked, mainly because of lighting problems. Each puzzle piece had vastly different lighting conditions and therefore the pictures looked very different for the Picture Metric.
We basically tried comparing the colors along the edges of the pieces and tried seeing how close the RGB colors are to each other. As stated before, this didn’t work consistently enough and we mainly relied on the Shape Metric.
Now that we have a compatibility metric, we can go about solving the entire jigsaw puzzle. In the end, we went for an “improved greedy algorithm”. We start off with one piece and build around it until we run out of pieces. At every iteration, we choose the best fitting piece and add it to the current puzzle.
The “greedy” part refers to that we greedily choose the best piece at each stage. Once a piece has been selected, it doesn’t move for the rest of the algorithm, even if it’s wrong. This worked well for relatively small puzzles (~30 pieces at most). We considered a backtracking approach as well but never got around to implementing it.
The “improved” part refers to exploiting structural information we have about the puzzle. Firstly, we classify the 4 corners and the edge pieces of the jigsaw puzzle beforehand. Then, we start off with a corner and fill in the puzzle row by row. At each iteration, we only compare relevant pieces. For instance, when attaching a piece to a corner, we only consider edge and corner pieces. These heuristics reduced computation time and improved accuracy dramatically.
And that’s about it for the software parts of the project! I might go into the hardware details of the project in a later post. Again, feel free to contact us below and we’ll happily answer any questions you might have. All of our code can be found on my Github.
