New Software Uses Probability Algorithm to Assemble Jigsaw Puzzles at Record Speed

Jigsaw Puzzle A new computer algorithm can solve 400-piece jigsaw puzzles in just three minutes. The first column is the real photo; the second is how the computer sees it; the third is "estimated evidence," as the computer would see it; and the fourth shows the patch ranking map used to pinpoint specific areas of the picture. Taeg Sang Cho

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.

Related Articles

	Efficient New Object Recognition Software Uses Smarter Piece-By-Piece Approach
	Object-Detection Software to Enable Search Within Videos
	Computer Algorithm Can Recognize Sarcasm (Which Is Just Soooo Cool)

Tags

Technology, Rebecca Boyle, algorithms, detection software, Photos, Photoshop, puzzles, visual algorithms

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.

[New Scientist]