Cornell jigsaw solver uses shape-blind algorithm

Jun 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

(Phys.org) -- 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: MIT groups develop smartphone system THAW that allows for direct interaction between devices

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.

via Newscientist

Related Stories

DARPA Shredder Challenge sizzling but no winner yet

Nov 22, 2011

(PhysOrg.com) -- 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 ...

Shredder Challenge solved

Dec 05, 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

Who drives Alibaba's Taobao traffic—buyers or sellers?

Sep 18, 2014

As Chinese e-commerce firm Alibaba prepares for what could be the biggest IPO in history, University of Michigan professor Puneet Manchanda dug into its Taobao website data to help solve a lingering chicken-and-egg question.

Computerized emotion detector

Sep 16, 2014

Face recognition software measures various parameters in a mug shot, such as the distance between the person's eyes, the height from lip to top of their nose and various other metrics and then compares it with photos of people ...

Cutting the cloud computing carbon cost

Sep 12, 2014

Cloud computing involves displacing data storage and processing from the user's computer on to remote servers. It can provide users with more storage space and computing power that they can then access from anywhere in the ...

Teaching computers the nuances of human conversation

Sep 12, 2014

Computer scientists have successfully developed programs to recognize spoken language, as in automated phone systems that respond to voice prompts and voice-activated assistants like Apple's Siri.

User comments : 1

Adjust slider to filter visible comments by rank

Display comments: newest first

NeutronicallyRepulsive
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