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: Physicist's algorithm simplifies biological imaging -- and also solves Sudoku puzzles

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

$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, ...

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 ...

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

Inferring urban travel patterns from cellphone data

August 29, 2016

In making decisions about infrastructure development and resource allocation, city planners rely on models of how people move through their cities, on foot, in cars, and on public transportation. Those models are largely ...

How machine learning can help with voice disorders

August 29, 2016

There's no human instinct more basic than speech, and yet, for many people, talking can be taxing. 1 in 14 working-age Americans suffer from voice disorders that are often associated with abnormal vocal behaviors - some of ...

Apple issues update after cyber weapon captured

August 26, 2016

Apple iPhone owners on Friday were urged to install a quickly released security update after a sophisticated attack on an Emirati dissident exposed vulnerabilities targeted by cyber arms dealers.

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.