Solving a 400-piece jigsaw puzzle should be a doddle – but it's won a computer a new world record.
The previous record of 320 pieces was established by a Danish team in 2008 – but their computer could only solve puzzles with simple cartoon-style pictures featuring clear shapes and a limited number of colours.
The new software, developed by Taeg Sang Cho and colleagues at the Massachusetts Institute of Technology, can cope with any image, including photographs of outdoor scenes.
The team diced up 5-megabyte pictures into 400 squares and fed them into the software. Just as a human might, the computer analyses the predominant colours to try to work out what kind of image is hidden in the jumble. It then refers to a database of existing images to roughly arrange the pieces in their likely positions. For instance, a mix of green, grey and blue pieces might imply a landscape scene with grass at the bottom, buildings in the middle and sky at the top.
Having guessed the rough arrangement for the pieces, the software then examines the pixel colour values along the boundaries of each piece and finds those on other nearby pieces that match the closest. It then takes a best guess at the likely neighbouring piece. The strategy is a good one: the computer completed the 400-piece puzzle in just 3 minutes.
Because the software is good at finding image pieces that blend well, Cho hopes it will one day help image-editing packages like Photoshop make manipulated pictures look more realistic.
"If you move a person from one side of a picture to another, our algorithm could highlight the fact that the image will jar if the pixel values are too different," says Cho.
Klaus Hansen at the University of Copenhagen in Denmark, the former world record holder, is happy to lose the title. "Our approach was to use cartoons with clear colour and clear structure. This new probabilistic approach is quite interesting," he says.
Unlike Cho's work on squares, Hansen's team used traditionally shaped jigsaw pieces – but that makes the new algorithm even more impressive, Hansen thinks. "Solving puzzles with square pieces is a challenge, and of course not possible for certain puzzles," he says. "For example, it is impossible to verify that a chessboard cut into 64 black and white squares is reassembled correctly."
Reference: Cho's team will present their work at the IEEE Conference on Computer Vision and Pattern Recognition in San Francisco next month
If you would like