Solving Square Jigsaw Puzzles Using Dynamic Programming and the Hungarian Procedure

Abstract

Problem statement: To design, implement, and test an algorithm for solving the square jigsaw puzzle problem, which has many applications in image processing, pattern recognition, and computer vision such as restoration of archeological artifacts and image descrambling. Approach: The algorithm used the gray level profiles of border pixels for local matching of the puzzle pieces, which was performed using dynamic programming to facilitate non-rigid alignment of pixels of two gray level profiles. Unlike the classical best-first search, the algorithm simultaneously located the neighbors of a puzzle piece during the search using the well-known Hungarian procedure, which is an optimal assignment procedure. To improve the search for a global solution, every puzzle piece was considered as starting piece at various starting locations. Results: Experiments using four well-known images demonstrated the effectiveness of the proposed approach over the classical piece-by-piece matching approach. The performance evaluation was based on a new precision performance measure. For all four test images, the proposed algorithm achieved 100% precision rate for puzzles up to 8×8. Conclusion: The proposed search mechanism based on simultaneous allocation of puzzle pieces using the Hungarian procedure provided better performance than piece-by-piece used in classical methods.