Jigsaw Puzzles with Pieces of Unknown Orientation

Solved Puzzle with Jumbled Pieces

Building Mixed Puzzles. The jigsaw pieces from 3 puzzles are mixed together (top). Each puzzle has 600 jigsaw pieces, each jigsaw piece is 28  28, and is a Type 2 puzzle having rotated jigsaw pieces. Our tree-based reassembly is still able to assemble the puzzles (bottom), even with no information about the number of puzzles mixed together, or their dimensions. A few mistakes occur in two of the component puzzles, some of which could be fixed with our trimming step.



This work introduces new types of square-piece jigsaw puzzles: those for which the orientation of each jigsaw piece is unknown. We propose a tree-based reassembly that greedily merges components while respecting the geometric constraints of the puzzle problem. The algorithm has state-of-the-art performance for puzzle assembly, whether or not the orientation of the pieces is known. Our algorithm makes fewer assumptions than past work, and success is shown even when pieces from multiple puzzles are mixed together. For solving puzzles where jigsaw piece location is known but orientation is unknown, we propose a pairwise MRF where each node represents a jigsaw piece’s orientation. Other contributions of the paper include an improved measure (MGC) for quantifying the compatibility of potential jigsaw piece matches based on expecting smoothness in gradient distributions across boundaries.

Andrew Gallagher

A. Gallagher, "Jigsaw Puzzles with Pieces of Unknown Orientation," IEEE Conference on Computer Vision and Pattern Recognition 2012.



author = {A. Gallagher},

title = {Jigsaw Puzzles with Pieces of Unknown Orientation},

booktitle = {Proc. CVPR},

year = {2012},




PuzzleAssembly_CVPR2012F.pptx (Draft Version)
A webcast video of the talk is here.

Videos of Puzzle Assembly

http://www.youtube.com/watch?v=g5x8ZosrTIA; A 600-piece bicycle puzzle assembly.
http://www.youtube.com/watch?v=mhjZD4oxALs; A 600-piece Yosemite puzzle assembly.

Demo Software for MGC score, and tree-based reassembly is here.

This work was noticed in the media! [NewScientist][SlashDot][Phys.org][MSNBC]