Computational Jigsaw Puzzle Solving

Welcome

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 reseach, 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 larest 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 below.

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

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 slolution.

Papers

• CVPR 2011 paper.
• CVPR 2011 Supplemental material : Shows many solver’s results on the images data bases.
• Thesis by Dolev Pomeranz

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.  

A 432 piece puzzle		The solver in action.
A 805 piece puzzle		The solver in action.
A 3300 piece puzzle		The solver in action.
A 10000 piece puzzle		The solver in action.

Credits

Who and Where…

This research is a joint work by Dolev Pomeranz, Michal Shemesh and Ohad Ben-Shahar of the Computer Science Department, Ben-Gurion University of The Negev, Beer Sheva, Israel It was published in the Proceedings of the IEEE conference on Computer Vision and Pattern Recognition (CVPR), 2011, and was also presented in the 2011 Israel Computer Vision Day, and the Israel Machine Vision Conference (IMVC) 2012.  

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.