Computer software sets new record for solving jigsaw puzzle

May 24, 2010 by Lin Edwards report
Two examples of reconstructed images using the estimated local evidence. Please see the original paper for details. Image: Taeg Sang Cho.

(PhysOrg.com) -- Completing jigsaw puzzles is a challenging and popular hobby, but now scientists from the Massachusetts Institute of Technology (MIT) in the U.S. and Tel Aviv University in Israel have for the first time developed a probabilistic graphical model to solve a jigsaw puzzle consisting of 400 square pieces.

The graphical model, developed by Taeg Sang Cho and colleagues can solve puzzles of any image or photograph with a full range of colors, while the previous jigsaw solvers could only handle sharp images of limited colors. The previous record for jigsaw-solving by a computer was achieved in 2008 by a team of Danish scientists, and solved a puzzle consisting of 320 pieces. Their method used cartoons with clear structures and well-defined edges and sharp colors, and the pieces were cut in traditional shapes, which made it easier to solve than a puzzle in which every piece is square.

In their experiments, the team chopped 5-megabyte pictures into 400 squares and fed the data from each into their computer software. The software analyzed the major colors in the squares and arranged them in groups of similar colors. It then referred to a database of images to arrange the pieces in their most likely positions to produce an initial low resolution image. So, for example, a puzzle with a mixture of green, gray and blue would be interpreted as a landscape and the software would first group the bright pieces and blue pieces at the top (since objects in or near the sky are generally brighter, and the sky is often blue), the gray in the middle, interpreted as buildings, and green in the foreground, interpreted as vegetation.

When the pieces were arranged in their approximate positions the computer then checked the pixel colors on the boundaries of each piece and identified neighboring pieces that most closely matched the colors. The software fixed a small number of pieces, called anchor patches, and refined the layout for the remaining pieces to reconstruct the original picture. Using their system, the software was able to successfully reconstruct 20 test images, and could solve a 400-piece in only three minutes.

Cho said that since the software is expert at finding pieces that blend well, it may help make edited pictures more realistic in the future. Cho also hopes the could be useful for other scientific problems, such as DNA/RNA modeling or reassembling fragments of documents or archaeological relics, all of which can be modeled as jigsaw puzzles.

The paper will be presented at the 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) to be held in San Francisco on the 15th to 17th of June.

Explore further: Computerized emotion detector

More information: Project website: people.csail.mit.edu/taegsang/JigsawPuzzle.html

Related Stories

Assembling the jigsaw puzzle of drug addiction

Jan 05, 2008

Using an integrative meta-analysis approach, researchers from the Center for Bioinformatics at Peking University in Beijing have assembled the most comprehensive gene atlas underlying drug addiction and identified five molecular ...

Software 'Chipper' Speeds Debugging

Oct 01, 2007

Computer scientists at UC Davis have developed a technique to speed up program debugging by automatically "chipping" the software into smaller pieces so that bugs can be isolated more easily.

Mood player creates the right atmosphere

Mar 03, 2009

(PhysOrg.com) -- Melancholic songs, dance rhythms or romantic background music? The mood player can recognize musical characteristics and sort songs according to moods. It also blends in suitable images to the rhythm of the ...

Scientists build nanoscale 'jigsaw' puzzles made of RNA

Dec 20, 2004

Scientists at the University of California, Santa Barbara, working at the leading edge of bionanotechnology, are using assembly and folding principles of natural RNA, or ribonucleic acid, to build beautiful ...

Recommended for you

Computerized emotion detector

23 hours ago

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.

Mapping the connections between diverse sets of data

Sep 12, 2014

What is a map? Most often, it's a visual tool used to demonstrate the relationship between multiple places in geographic space. They're useful because you can look at one and very quickly pick up on the general ...

User comments : 2

Adjust slider to filter visible comments by rank

Display comments: newest first

baudrunner
not rated yet May 25, 2010
This one's just begging for a DNA reconstruction analogy. Based on the graphic results, I wouldn't trust it as far as I could throw it. The reconstructed images aren't at all accurate, rather hodge-podge. I wouldn't go with color matching so much as pattern matching. Software could easily match up patterns that are edge-equal in pixel characteristics, after building a database of the 1,600 edges. Only then should the color rules be applied, and then only to orient the image right-side up.
iknow
not rated yet May 26, 2010
awesome. ... now it only needs to put them in the right order and its done.
Is that the end result on pics?