Solving Square Jigsaw Puzzle by Hierarchical Loop Constraints

We present a novel computational puzzle solver for square-piece image jigsaw puzzles with no prior information such as piece orientation or anchor pieces. By “piece” we mean a square dd x dd block of pixels, where we investigate pieces as small as 7 × 7 pixels. To reconstruct such challenging puzzle...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on pattern analysis and machine intelligence 2019-09, Vol.41 (9), p.2222-2235
Main Authors: Son, Kilho, Hays, James, Cooper, David B.
Format: Article
Language:English
Subjects:
Algorithms
Anchors
Compatibility
Computational jigsaw puzzle
Computer vision
Dependence
discrete optimization algorithm
Estimation
hierarchical loop constraints
Image reconstruction
Jigsaw puzzles
Linear programming
Mathematical analysis
maximizing consensus
Noise measurement
Pixels
Robustness
Solvers
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a novel computational puzzle solver for square-piece image jigsaw puzzles with no prior information such as piece orientation or anchor pieces. By “piece” we mean a square dd x dd block of pixels, where we investigate pieces as small as 7 × 7 pixels. To reconstruct such challenging puzzles, we propose to find maximum geometric consensus between pieces, specifically hierarchical piece loops. The proposed algorithm seeks out loops of four pieces and aggregates the smaller loops into higher order “loops of loops” in a bottom-up fashion. In contrast to previous puzzle solvers which aim to maximize compatibility measures between all pairs of pieces and thus depend heavily on the pairwise compatibility measures used, our approach reduces the dependency on the pairwise compatibility measures which become increasingly uninformative for small scales and instead exploits geometric agreement among pieces. Our contribution also includes an improved pairwise compatibility measure which exploits directional derivative information along adjoining boundaries of the pieces. We verify the proposed algorithm as well as its individual components with mathematical analysis and reconstruction experiments.
ISSN:0162-8828
1939-3539
2160-9292
DOI:10.1109/TPAMI.2018.2857776