Introduction

For our project we wanted to tackle the age old problem of solving a puzzle. Puzzle solving has applications in archaeology where you can take multiple images of disjoint artifacts and try to rebuild an image of what the original piece looked like. It can also be used for information retrieval by taking pictures of shredded paper and piecing it back together. While it does have useful applications as listed earlier, our main motivation for this project was to have fun and learn by doing! We had to apply a wide range of Computer Vision tools to be able to do this and in the next section we walk the reader through our approach.

While we have tested out the algorithm on multiple puzzles, we focus on one as we walk the reader through the algorithm.

Approach

Our main idea was to first get all the possible solutions based on the shape of the pieces and then decide which solution out of all the possible solutions was the best based on matching the color near the intersection of the two puzzles. This mimics the “human” way of solving puzzles too.

We went about this in the following manner:

• As the starting point, we took a picture of all the pieces of the puzzle spread out.
• We obtained a tight boundary of all the pieces.
  • We did this by first obtaining a rough outline of the pieces using Sobel edge detection.
  • We then fudge the edges obtained and dilate it.
  • We then fill in inside the edges and take the boundary of this filled in image.
  • By doing this we are able to obtain all the boundaries and by counting the number of boundaries obtained we know the number of pieces too.
• After having obtained the boundary of the pieces, the next step was to straighten out the pieces.
  • We did this by getting the dominant hough lines through every piece. Since the dominant Hough line is along the edge of the piece we are able to straighten out all the pieces by rotating them with the angle of the dominant line.
• Having rotated all the pieces and before we could build all the possible solutions based on shape alone, we first had to classify all the pieces.
  • We used the convention of +1 being a protrusion, -1 being an indentation and 0 being a flat edge.
  • Using this convention, we know that pieces with a 0 (with a straight edge) belongs on the outer boundary and we know that two pieces can match up only if one of them has a +1 (protrusion) and the other one has a -1 (intrusion)
  • To start the classification we first drew lines offset a certain distance from each edge of the piece. By determining the pattern along each line we were able to determine if the edge was a protrusion, indentation, or flat edge.
  • We start with the left side of the piece and work counterclockwise around the piece classifying each edge.
• Now that all the pieces were classified we looked at all the possible solutions based on shape alone.
  • We start with a corner piece and orient it so that the corner is in the top left. By evaluating which pieces can feasibly match we build all possible solutions up row by row. In addition to checking that a piece with a protrusion matches a piece with an intrusion, we also check to make sure that straight edges properly match (a piece with a straight edge on the left must join with another piece that also has a straight edge on the left) and that a piece isn't used multiple times.
• Based on the shape alone, we were getting up to 48 different solutions for a puzzle so it was not enough to stop at this point.
• In our initial project proposal we had talked about using a picture of the solved puzzle as an input to our algorithm and matching all the possible solutions to it. While this was a way to go about it, we felt it was too easy. In addition, in a real world application, such as information retrieval mentioned earlier, the whole point was that we don’t have the final image and are trying to build the final image using only disjoint partial images.
• So instead we came up with a way to match the puzzle pieces based on their color content. The idea is that when we put together two pieces the color near the edges where they join are similar. So we looked at the one third of a piece that was closer to the joining edge and matched it to the one third of the other piece.
• Color histograms were used to do the color matching.
• By doing this we were able to give each of the possible solutions a score, with a lower value representing less color variation across the joining edges and hence a better solution.
• We observed that the correct solution was generally in the best 3 possible solutions but not always the absolute best solution. This happened because a lot of times, there isn’t a sharp difference in color between different pieces so it is difficult to pick the best match. This problem was made worse due to the quality of the camera and lighting. Shadows on light images made them more likely to be paired with dark images and glare on some dark images made them more likely to be paired with light images.
• To fix this we came with up an extra penalty for pieces that didn’t fit together well due to their size ratios.
• This finally fixed the problem for us and led us to obtain the correct solution of the puzzle as our best solution.
• When presenting the final solution we also make sure we start with the correct top left corner piece so that the puzzle orients correctly. Otherwise we end up with solutions that just needed to be rotated.

We will now illustrate the process described above using the pictures we generated

Step 1: Obtaining the boundaries

Step 2: Straighten out the pieces

Step 3: Classify all the pieces

Step 4: Obtain all possible solutions based on shape alone (few shown for brevity)

Notice that all these solutions are physically possible. Also notice that solution 1 and 3 are only off by a single pair

Step 5: Use color matching to give every solution a value. (the lower the better)

Step 6: After color matching we are able to get the final result

Another example: Superman

3rd Example: Anna from the movie Frozen

Results/Conclusion

• We are able to solve a puzzle given an image of its spread out pieces and we are able to do so without requiring an image of the final puzzle that is printed on the box.
• On the box of the puzzles that we tried it said 6+ years but it only took us a month (we have other classes too) to develop this algorithm and now we can solve it in under 2 minutes! Woohoo!

Future Work

• The biggest obstacle in our work was being able to take proper pictures when the puzzle pieces are spread out.
• We tend to have glare and shadows which confuses the algorithm.
• Dark images with glare can look like a bright image and their color can be off making it difficult to appropriately place the piece.
• In the future, work can be done to develop an algorithm that is more robust to lighting changes.

Bibliography

1. VT Fall 2017, ECE 5554. HW1(edge detection),HW5(color matching)

2. Using Computer Vision to Solve Jigsaw Puzzles, Travis V. Allen, Stanford University