Jigsaw puzzles with pieces of unknown orientation
Author:
- 1 June 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636919,p. 382-389
Abstract
This paper 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.Keywords
This publication has 21 references indexed in Scilit:
- A fully automated greedy square jigsaw puzzle solver2011
- Reconstructing strip-shredded documents using color as feature matching2009
- Solving jigsaw puzzles using image featuresPattern Recognition Letters, 2008
- A New Technique for Solving a Jigsaw Puzzle2006
- Reconstructing shredded documents through feature matchingForensic Science International, 2006
- A Texture Based Matching Approach for Automated Assembly of Puzzles2006
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- An automatic jigsaw puzzle solver2002
- Isthmus critical points for solving jigsaw puzzles in computer visionIEEE Transactions on Systems, Man, and Cybernetics, 1991
- On the Shortest Spanning Subtree of a Graph and the Traveling Salesman ProblemProceedings of the American Mathematical Society, 1956