Cornell jigsaw solver uses shape-blind algorithm

June 17, 2012 by Nancy Owano, report
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 . 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 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 delivers “state-of-the-art performance for puzzle assembly, whether or not the orientation of the is known.” The paper proposes a tree-based reassembly that greedily merges components “while respecting the geometric constraints of the puzzle problem.”

Explore further: DARPA Shredder Challenge sizzling but no winner yet

More information: Jigsaw Puzzles with Pieces of Unknown Orientation, Computer Vision and Pattern Recognition Conference, (PDF)

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.

via Newscientist

Related Stories

DARPA Shredder Challenge sizzling but no winner yet

November 22, 2011

( -- With only days left until the December 4 Shredder Challenge deadline, DARPA is still asking the sharpest-minded computer scientists and simply the curious if anyone among them has the skills to reconstruct ...

$50,000 to solve the most complicated puzzle ever attempted

November 17, 2011

( -- Every few years the Pentagon’s Defense Advanced Research Projects Agency (DARPA) holds a public competition to stretch the outer limits of what technology can do. Two years ago they dispersed 10 large, ...

Shredder Challenge solved

December 5, 2011

Almost 9,000 teams registered to participate in DARPA's Shredder Challenge. Thirty-three days after the challenge was announced, one small San Francisco-based team correctly reconstructed each of the five challenge documents ...

Recommended for you

What do you get when you cross an airplane with a submarine?

February 15, 2018

Researchers from North Carolina State University have developed the first unmanned, fixed-wing aircraft that is capable of traveling both through the air and under the water – transitioning repeatedly between sky and sea. ...

1 comment

Adjust slider to filter visible comments by rank

Display comments: newest first

not rated yet Jun 17, 2012
Some videos:

Bikes puzzle: http://www.youtub...8ZosrTIA
Yosemite puzzle: http://www.youtub...oYraVcmc

Old version (greedy square): http://www.youtub...u0uBAp9s

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.