Solving Square Jigsaw Puzzles 
with Loop Constraints


People

Kilho Son
David B. Cooper

Abstract

We present a novel algorithm based on “loop constraints” for assembling non-overlapping square-piece jigsaw puzzles where the rotation and the position of each piece are unknown. Our algorithm finds small loops of puzzle pieces which form consistent cycles. These small loops are in turn aggregated into higher order “loops of loops” in a bottom-up fashion. In contrast to previous puzzle solvers which avoid or ignore puzzle cycles, we specifically seek out and exploit these loops as a form of outlier rejection. Our algorithm significantly outperforms state-of-the-art algorithms in puzzle reconstruction accuracy. For the most challenging type of image puzzles with unknown piece rotation we reduce the reconstruction error by up to 70%. We determine an upper bound on reconstruction accuracy for various data sets and show that, in some cases, our algorithm nearly matches the upper bound.

European Conference on Computer Vision (ECCV) 2014 paper

Paper preprint
Main paper
(PDF, 19.8MB)
Paper preprint
Supplemental material
(PDF, 28.3MB)
Paper preprint
Poster
(PDF, 2.1MB)

Source codes

Source codes will be available soon.

Funding

This work was partially supported by NSF Grant # 0808718 to Kilho Son and David B. Cooper, and NSF CAREER award 1149853 to James Hays.