Computer software to solve tricky jigsaws

Research teams from Tel Aviv University, Israel and Massachusetts Institute of Technology, USA have devised a computerised jigsaw puzzle solver, which is far more advanced than any previous programme. The graphical model is able to interpret and solve complex jigsaw puzzles consisting of 400 square pieces. The software could also be useful for complex scientific problems – such as DNA/RNA modelling or reassembling fragments documents or archaeological relics.

Building on their first system, put in place last May, the team have used an innovative approach to solve puzzles that are an order of magnitude larger than ever solved before. The team, led by Taeg Sang Cho developed the first graphical model last May which could solve puzzles of any image or photograph, regardless of the range of colours in the picture. Previous models, could only solve the puzzles if the colours were images were sharp and the colours were bright.
The team chopped a 5-metgabyte picture into 400 squares and fed the data from each into their computer software. The software analysed the major colours in the squares and arranged them in groups of similar colours. 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, grey 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 grey 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 colours on the boundaries of each piece and identified neighbouring pieces that most closely matched the colours. 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.
Their research will be presented this month in the premium CVPR conference: http://www.cvpr2011.org/

Published: Wednesday, 1st June 2011 by Adelle Kehoe