Solving jigsaw puzzle with symbol matrixes

摘要

This paper presents a new symbol-matrix-based jigsaw-puzzle algorithm for image reconstruction. The proposed algorithm first calculates the compatibility metric using the SSD (Sum of Squared Distance Scoring) between adjacent pieces. Then the algorithm constructs a matrix to express the location relationship of pieces followed by constructing a symbol matrix to record the number and rotations of pieces. Finally, we use a greed algorithm to reconstruct the images. The proposed algorithm does not require any preset conditions and can reconstruct the images rapidly. The experimental results have shown that the proposed algorithm can accurately reconstruct the images with 28% speed-up in execution time. The results also show that it's very effective to reconstruct the puzzles with missing pieces, which is a useful feature for applications such as artifact reconstruction, biological information reconstruction and incomplete crime-scene reconstruction.