Cornell jigsaw solver uses shape-blind algorithm

Cornell jigsaw solver uses shape-blind algorithm
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

DARPA Shredder Challenge sizzling but no winner yet

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

© 2012 Phys.Org

Citation: Cornell jigsaw solver uses shape-blind algorithm (2012, June 17) retrieved 19 August 2019 from https://phys.org/news/2012-06-cornell-jigsaw-solver-shape-blind-algorithm.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.
0 shares

Feedback to editors

User comments

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