Computer software sets new record for solving jigsaw puzzle

(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 puzzle 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 software 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.

© 2010 PhysOrg.com