Algorithm solves jigsaw puzzles

Algorithm solves jigsaw puzzles

A researcher at Eastman Kodak Research Laboratories (Rochester, NY, USA) has developed a computer algorithm that can assemble the pieces of a virtual jigsaw puzzle into a complete picture.

As with a physical jigsaw puzzle, the object of the computational problem faced by researcher Dr. Andrew Gallagher was how to join up a number of smaller jigsaw pieces to form a complete picture.

To make matters somewhat more complex, Gallagher developed his computer algorithm to solve jigsaw puzzles with square pieces whose orientation was unknown.

In past work on the subject, researchers have assumed that the orientation of each jigsaw piece was known, and only the location of each piece in the completed puzzle was unknown. Consequently, a pair of puzzle pieces can only fit together in four different ways in what is known as a "Type 1" puzzle.


However, when neither the location, nor the orientation, of any piece is known -- a so-called "Type 2" puzzle -- the problem becomes more difficult since a pair of jigsaw pieces can then fit together in any of 16 configurations.

In use, Gallagher demonstrated that his algorithm could achieve perfect reconstruction of jigsaw puzzles containing up to 9600 pieces, the largest automatically solved jigsaw puzzle to date.

An interesting problem in its own right, computational jigsaw assembly also has applications in reassembling archaeological artifacts and recovering shredded documents or photographs.

Dr. Gallagher worked at Eastman Kodak from 1996 to 2012, initially developing image enhancement algorithms for digital photofinishing. These efforts resulted in more than 90 issued US Patents and Kodak's prestigious Eastman Innovation Award in 2005.

This month, he took up the position as Visiting Research Scientist at Cornell University's School of Electrical and Computer Engineering (Ithaca, NY, USA).

His paper "Jigsaw puzzles with pieces of unknown orientation" which details the algorithm he developed can be found here.

-- Dave Wilson, Senior Editor, Vision Systems Design



Get All the Vision Systems Design News Delivered to Your Inbox

Subscribe to Vision Systems Design Magazine or email newsletter today at no cost and receive the latest news and information.

 Subscribe Now

SPONSORED CONTENT

Webcasts

How the newest machine vision standards will affect you

How will the latest developments in machine vision standards affect you? This webcast will answer that question by featuring updates on relevant standards by some of the industry’s most knowledgeab...

How vision systems are changing automotive manufacturing

How do Ford and General Motors leverage machine vision for powertrain manufacturing? How does traditional vision application development serve today’s needs, and what machine vision capabilities co...
Date: June 24, 2015

High-speed imaging and the future of vision systems

What technologies are advancing high-speed imaging? What markets and applications are affected, and what can potential purchasers expect? In this live, interview-style webcast, Vision System Design...
Date: May 28, 2015

PRESS RELEASES

PROFINET® and Multi-Language Support Now Available with Microscan Link

October 9, 2013 Microscan Link connectivity provides vision engineers, programmers, and other users with an easy ...

Microscan’s AutoVISION™ 2.0 Wins 2013 Ringier Technology Innovation Award for Food and Beverage

August 8, 2013 Microscan, a global technology leader in barcode, machine vision and lighting solutions, announce...

Archives

Click here to view archived Vision Systems Design articles