Solving Square Jigsaw Puzzle by Hierarchical Loop Constraints
- 19 July 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 41 (9), 2222-2235
- https://doi.org/10.1109/tpami.2018.2857776
Abstract
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 d x d block of pixels, where we investigate pieces as small as 7 x 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.Funding Information
- NSF (#0808718)
This publication has 28 references indexed in Scilit:
- An Encryption-then-Compression System for JPEG/Motion JPEG StandardIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2015
- Axially Symmetric 3D Pots Configuration System Using Axis of Symmetry and Break CurvePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- A Genetic Algorithm-Based Solver for Very Large Jigsaw PuzzlesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2013
- Solving Square Jigsaw Puzzles Using Dynamic Programming and the Hungarian ProcedureAmerican Journal of Applied Sciences, 2009
- A Survey of Statistical Network ModelsFoundations and Trends® in Machine Learning, 2009
- Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and ComplexityGraphs and Combinatorics, 2007
- Photo tourismPublished by Association for Computing Machinery (ACM) ,2006
- A Biologically Inspired Algorithm for the Recovery of Shading and Reflectance ImagesPerception, 2004
- Network biology: understanding the cell's functional organizationNature Reviews Genetics, 2004
- On the shortest spanning subtree of a graph and the traveling salesman problemProceedings of the American Mathematical Society, 1956