Faster Jigsaw Solving
Faster Jigsaw Solving
Written by Alex Armstrong   
Monday, 18 June 2012

You might imagine that computers would be good at solving jigsaw puzzles, but the task is harder than you think. Pattern matching is fairly easy when you have a specified orientation. If you try it when you don't know which way to hold the pieces, you'll soon see the problem.

If you think that you solve a mean jigsaw, consider that the latest algorithm can manage 10,000 pieces in 24 hours - three times last year's record of 3,300 pieces. Andrew Gallagher at Cornell University in Ithaca, New York has improved the standard approach by copying what humans do  in finding groups of pieces that best match and working outwards from there.

 

jigsawalgo

9600-piece puzzle solved!

The algorithm tackles problems with square pieces which is harder than the traditional shaped interlocking puzzle because you have no orientation clues. It can even solve puzzles that are mixed together without being told how many puzzles the pieces come from or their dimensions.

Before you think that the problem is easy, consider how many possible arrangements there are of even a small number of pieces. Clearly you can't just try every combination - and even if you did how would you recognize that you had a solution? Indeed puzzle assembly is an NP-hard problem.

 

jigsawspan

 

The algorithm used is a greedy tree-based method and a new measure of piece similarity. The measure of similarity is based on the well-known Mahalanobis distance, which scales the distance between distributions by their dispersion. The new measure compares pieces using the intensity gradient near the edge scaled by the covariance of the color channel. The greedy tree-based assembly builds a minimum-spanning tree with constraints to make sure that only one piece is placed against another. To make the problem tractable, a heuristic is used to find an approximate solution in reasonable time.

You can see the algorithm in action in the following two videos:

 600-piece bicycle

 

600-piece Yosemite

 

If you think that jigsaw puzzles are a bit frivolous, then notice that similar algorithms can be used to put shredded documents back together - as per the recent DARPA challenge.

The real question is can you do better?

With video input being no problem and GPUs readily available, this is one AI task anyone can attempt.

 

More Information

Jigsaw Puzzles with Pieces of Unknown Orientation

Related Articles

DARPA Shredder Challenge

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin,  or sign up for our weekly newsletter.

 

Banner


Growing Demand For Data Visualization
19/01/2018

A new survey of Trends in Web Technologies confirms that web technology is now the backbone of application development for most companies  and reveals that data visualization is one of  [ ... ]



How Meltdown Works
05/01/2018

The news is full of Meltdown and Spectre attacks that appear to work on a wide range of current CPUs, particularly on Intel processors dating from 1995 on. The interesting part of the story is how the [ ... ]


More News

 

 
 

 

blog comments powered by Disqus

 

 

 

 

 

Last Updated ( Monday, 18 June 2012 )
 
 

   
Banner
Banner
RSS feed of news items only
I Programmer News
Copyright © 2018 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.