Abstract:

Solving a jigsaw puzzle entails arranging a fixed set of pieces such that they reconstruct an original source image. With a traditional jigsaw puzzle, finding the solution is straightforward as interpiece mechanical incongruence and knowledge of the solution image reduce the number of possible piece permutations.

This project proposes an algorithm that can simultaneously reconstruct multiple jigsaw puzzles consisting of uniform, square pieces. Unlike previous work, the algorithm takes no outside information (e.g., number of input puzzles). In contrast, the algorithm uses the image information from the bag of individual, input pieces.

CS297 Results

• A literature review of existing techniques to solve jigsaw puzzles.
• A puzzle generator implemented using OpenCV that takes an image file as the input
• An enhanced implementation of a greedy solver based off the approach proposed by Paikin & Tal (see the references for the specific paper).
• Visualization tools for solutions to puzzle solver solutions as well as best buddy relationships.

Proposed Schedule

Key Deliverables:

• Software
  • Implementation of a segmentation algorithm to determine with a high degree of confidence portions of the solution that are assembled correctly.
  • Improvements to segmentation techniques to support the potential for missing pieces.
  • An algorithm for estimating the number of input puzzles to the solver.
  • A set of metrics used to measure the quality of solutions when solving multiple jigsaw puzzles simultaneously.
• Report
  • Complete a thesis write-up.
  • Complete source code and thesis defense presentation.

Innovations and Challenges

• In traditional jigsaw puzzles, pieces usually have unique or significantly different shapes. This significantly simplifies jigsaw puzzle solving since shape alone can be used to definitively determine that some pieces are not adjacent. In constrast, the puzzle pieces in this are equal sized squares which eliminates the use of shape in determining piece adjacency.
• Most previous work on the jigsaw puzzle problem focused on solving only a single puzzle at a time. Solving multiple (in particular) large puzzles increases the number of piece permutations and introduces the complexity of dividing the input set of pieces into disjoint subsets.
• Puzzles with missing pieces are more difficult since one cannot assume all internal pieces have a neighbor. What is more, missing puzzle pieces increase the likelihood that two puzzle pieces will have an artificially high pairwise similarity. Both of these increase the difficulty in solving a puzzle.
• Develop the first solver that takes no outside input other than the bag of puzzle pieces.

References:

• A. C. Gallagher, Jigsaw puzzles with pieces of unknown orientation, in Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), CVPR 12, pp. 382389, IEEE Computer Society, 2012.
• D. Pomeranz, M. Shemesh, and O. Ben-Shahar, A fully automated greedy square jigsaw puzzle solver, in Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), CVPR 11, pp. 916, IEEE Computer Society, 2011.
• D. Sholomon, O. David, and N. S. Netanyahu, A genetic algorithm-based solver for very large jigsaw puzzles, in Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), CVPR 13, pp. 17671774, IEEE Computer Society, 2013.
• G. Bradski, The OpenCV library, Dr. Dobbs Journal of Software Tools, Nov. 2000.
• G. Paikin and A. Tal, Solving multiple square jigsaw puzzles with missing pieces, in Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), CVPR 15, IEEE Computer Society, 2015.