American Journal of Applied Sciences

Solving Square Jigsaw Puzzles Using Dynamic Programming and the Hungarian Procedure

Naif Alajlan

DOI : 10.3844/ajassp.2009.1941.1947

American Journal of Applied Sciences

Volume 6, Issue 11

Pages 1941-1947

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.

Copyright

© 2009 Naif Alajlan. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.