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: UT Dallas professor to develop framework to protect computers' cores

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

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?

More news stories

Ex-Apple chief plans mobile phone for India

Former Apple chief executive John Sculley, whose marketing skills helped bring the personal computer to desktops worldwide, says he plans to launch a mobile phone in India to exploit its still largely untapped ...

Airbnb rental site raises $450 mn

Online lodging listings website Airbnb inked a $450 million funding deal with investors led by TPG, a source close to the matter said Friday.

Health care site flagged in Heartbleed review

People with accounts on the enrollment website for President Barack Obama's signature health care law are being told to change their passwords following an administration-wide review of the government's vulnerability to the ...

A homemade solar lamp for developing countries

(Phys.org) —The solar lamp developed by the start-up LEDsafari is a more effective, safer, and less expensive form of illumination than the traditional oil lamp currently used by more than one billion people ...

NASA's space station Robonaut finally getting legs

Robonaut, the first out-of-this-world humanoid, is finally getting its space legs. For three years, Robonaut has had to manage from the waist up. This new pair of legs means the experimental robot—now stuck ...

Filipino tests negative for Middle East virus

A Filipino nurse who tested positive for the Middle East virus has been found free of infection in a subsequent examination after he returned home, Philippine health officials said Saturday.

Egypt archaeologists find ancient writer's tomb

Egypt's minister of antiquities says a team of Spanish archaeologists has discovered two tombs in the southern part of the country, one of them belonging to a writer and containing a trove of artifacts including reed pens ...