Cornell jigsaw solver uses shape-blind algorithm
Source: Nancy Owano
Puzzle assembly begins with each jigsaw piece as its own forest. Forests are merged (by combining and rotating, if necessary) to create assembled subclusters according to the compatibility score that we introduce (MGC), until the puzzle is assembled (a)-(g). The spanning tree in (h) shows the final representation of the solution as well as the order in which edges were added, from early (magenta) to later (yellow). This example has 192 jigsaw pieces. Image: Andrew C. Gallagher
A Cornell scientist has come up with an algorithm that can sift through 10,000 pieces of a jigsaw in 24 hours to complete the puzzle. Andrew Gallagher at Cornell University in Ithaca, New York, wrote the algorithm while working at Eastman Kodak, where he was developing image enhancement algorithms for digital photofinishing. Gallagher, who is with Cornell’s Advanced Multimedia Processing (AMP) Lab, was also among the contestants trying for the DARPA shredded-document challenge last year.
He used his knowledge to compete in DARPA’s grueling challenge, asking contestants to reconstruct a series of shredded documents with levels of increasing difficulty. Gallagher and team did not win but came in at 17th place out of over 9,000 registered teams.
A unique aspect of this jigsaw algorithm is that it only works on jigsaws with square pieces, so that the shape offers no clues. The algorithm calculates a score for each pair, stores the best matches, and uses these in assembling the entire puzzle. It starts with the two pieces that match best, then the next two and onwards. Another notable aspect is that, unlike software that analyses edges of the pieces, Gallagher's looks at the spread of color patterns across many pieces. If one piece becomes progressively lighter from left to right, the piece likely nestles between a lighter piece on the left and darker piece on the right. The algorithm can work on multiple parts of the puzzle at once. Previous methods worked only on a single part.
Beyond Cornell, a computer scientist with similar research interests said Gallagher’s algorithm is helpful for certain puzzle challenges. Ohad Ben-Shahar, in the Computer Science Department at Ben Gurion University, is part of a team that held a previous puzzle-solving record. Ben-Shahar noted Gallagher’s algorithm can be used with puzzles in which the orientation of the pieces is unknown, which is challenging. Ben-Shahar says their team has been working on an algorithm that may match Gallagher’s but results are not yet published. He said in both instances there is always room for improvement. "With little effort, the time to solution could drop significantly below a day." Ben-Shahar and team authored the paper, “A fully automated greedy square jigsaw puzzle solver.”
Gallagher is visiting research scientist at Cornell University's School of Electrical and Computer Engineering. His system will be presented at the Computer Vision and Pattern Recognition Conference in Providence, Rhode Island, running from June 16 to 21. His paper, “Jigsaw Puzzles with Pieces of Unknown Orientation,” notes the algorithm delivers “state-of-the-art performance for puzzle assembly, whether or not the orientation of the pieces is known.” The paper proposes a tree-based reassembly that greedily merges components “while respecting the geometric constraints of the puzzle problem.”
More information: Jigsaw Puzzles with Pieces of Unknown Orientation, Computer Vision and Pattern Recognition Conference, (PDF)
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.
| }
|