Square Jigsaw Puzzle Solving
Introduction
It is quite likely that you, the reader, have tried to solve jigsaw puzzles before. Could computers do the same once given the bag of pieces? This problem has been studied progressively (though sporadically) since the 1960's, but only recently could algorithms began to handle problems of reasonable size at reasonable success rate. In 2011 we were proud to be the first group to have devised a computational solution which is both fully automatic, requires no manually provided hints, operates on puzzles having thousands of pieces, and does not with near perfect performance. As has become common in the field, we too focus on square pieces, if nothing else then for the elimination of shape cues that sometimes assist us (humans) when we solve such puzzles.
In the page below you will find and download material related to our research, including all the code, papers, image databases, and demos. But as a teaser, here on the right we are proud to present the first ever solution to the latest puzzle ever attempted by an automatic solver to date (July 2011) – no less than 10,000 pieces! A different visualization of this solution is also shown later on.
Downloads
Download Matlab Code (please refer to the Programmer’s Manual for additional documentation and instructions)
- GeneratePuzzle.m – A function that scrambles an image
- JigsawSolver.m – The greedy jigsaw (V 2.19) solver code
Download Puzzle Data Sets
- The Cho et al. (2010) dataset: 20 images. 432 parts of size 28×28. Solver’s source code included
- The McGill Calibrated Colour Image Database: 20 images. 540 parts of size 28×28.
- BGU-805 Dataset: 20 images. 805 parts of size 28×28. If you need to use it, please cite our CVPR 2011 paper.
- BGU-2360 Dataset: 3 images. 2360 parts of size 28×28. If you need to use it, please cite our CVPR 2011 paper.
- BGU-3300 Dataset: 3 images. 3300 parts of size 28×28. If you need to use it, please cite our CVPR 2011 paper.
Selected Demos (Higher quality than YouTube)
- JigsawSolverInActionMovie.wmv: The greedy solver in action on a modest size problem
- JigsawSolverVisualizationMovie.wmv: Visualization of the solution from randomly scrambled state to solved state.
- JigsawSolverInAction-540parts.wmv: The solver in action on a 540 piece puzzle from the McGill DB.
- JigsawSolverInAction-805parts.wmv: The solver in action on a 805 piece puzzle from the BGU-805 DB.
- JigsawSolverInAction3300parts.wmv: The solver in action on a 3300 piece puzzle from the BGU-3300 set.
- JigsawSolverInActionBiggestPuzzle-10000parts.wmv: The solver in action on a 10,000 piece puzzle.
- JigsawSolverVisualization10000parts.wmv: Visualization of the 10,000 piece solution.
Papers
- CVPR 2011 paper.
- CVPR 2011 Supplemental material: Shows many solver’s results on the images data bases.
- Thesis by Dolev Pomeranz
Talk
This work was presented at the 2011 Israel Computer Vision Day
Inline Demos
While our solver is available for download and experimentation, below you will find several demos covering a range of puzzle sizes and complexity. Each row in the table below shows on the left a visualization of the solution from an initial scrambled state to the final state obtained at the end of the computation, and on the right the actual progression of the solution from the single seed piece till the final state. All demos are available also in YouTube, but you may also download better quality videos in the Download section below.
Inline Demos
While our solver is available for download and experimentation, below you will find several demos covering a range of puzzle sizes and complexity. Each row in the table below shows on the left a visualization of the solution from an initial scrambled state to the final state obtained at the end of the computation, and on the right the actual progression of the solution from the single seed piece till the final state. All demos are available also in YouTube, but you may also download better quality videos in the Download section below.
Robotic Solver
Why stop at puzzles inside the computer? Indeed, physical puzzles present new challenges, especially when it comes to the robust acquisition of piece appearance in the presence of noise, loosely controlled illumination, and aliasing due to pieces that are not aligned with the camera grid. We’ve made the first step, though, and the video below presents our prototype system.
Acknowledgments
This work was funded in part by the US Air Force European Office of Aerospace Research and Development (grant number FA8655-09-1-3016), the Israel Science Foundation (ISF grant No. 1245/08) and the European Commission in the 7th Framework Programme (CROPS GA no 246252). We also thank the generous support of the Frankel fund, the Paul Ivanier center for Robotics Research and the Zlotowski Center for Neuroscience at Ben-Gurion University.