New Software Uses Probability Algorithm to Assemble Jigsaw Puzzles at Record Speed
When it comes to complex games like chess, computers can compete with the world’s best humans. But complicated jigsaw puzzles...
When it comes to complex games like chess, computers can compete with the world’s best humans. But complicated jigsaw puzzles have largely had computers stumped — until now.
A Massachusetts Institute of Technology team has set a new world record for a jigsaw-puzzle-solving computer algorithm. The software solved a 400-piece puzzle in three minutes, New Scientist reports.
The software can handle any image, even photographs of outdoor scenes. The previous record was 320 pieces, set by a Danish team in 2008, but that software could only solve simple puzzles with clear shapes and limited colors.
The new software is adept at finding image pieces that blend well, so its inventor, MIT grad student Taeg Sang Cho, hopes it could improve photo-editing programs like Photoshop. It could make Photoshopped images look more realistic, for instance.
To train the software, Cho and his colleagues chopped 5-megabyte pictures into 400 squares. The computer analyzed the predominant colors and referenced a database of existing images to roughly arrange the pieces. It uses the same common-sense approach a person would — lots of blue pieces could indicate sky, for instance, and a mixture of blue, gray and green could indicate a landscape with sky, buildings and grass.
From there, the computer’s work gets more complex. It examines the pixel color values along the boundaries of each piece, and uses a probabilistic approach to find similar values on pieces that look alike, stitching the images back together.
It’s much harder to do this with squares than with traditional jigsaw pieces, but as Cho and his colleagues write in a paper about the findings, that’s a good thing.
“This is a good framework for analyzing structural regularities in natural images since it requires us to focus on the image content to solve the puzzle,” the paper says (PDF).
Cho and his team will present their work at the IEEE Conference on Computer Vision and Pattern Recognition in San Francisco next month.