Automatic Jigsaw Puzzle Assembly using Computer Vision and Optimization Algorithms

This Paper presents an approach to solving jigsaw puzzles using a known algorithm called Prim’s minimum spanning tree algorithm. The proposed system is meant to be an interface for assembling jigsaw puzzles; the goal is to have the system fast, precise, reliable, and extensible. Using a range of computer vision techniques and graph theory, the algorithm deals with the computational complexity of pieces’ identification, matching, and growth in the size of the puzzle. The methodology is initially performed by normalizing the puzzle piece images and using a similarity matrix to analyze the compatibility between pieces. Based upon Prim’s minimum spanning tree, the algorithm derives a tree that provides the summation of weights that indicate how compatible the constructed pieces are. It also helps to reconstruct the picture in the puzzle precisely, given a certain time frame taken by the program. Testing scenarios prove that the algorithm’s performance is characterized by high accuracy and low time complexity, especially while handling square and rectangular pieces. The system also operates at its best for the number of puzzles that do not exceed a hundred, with minimal CPU usage and RAM rates. The described case of the employed algorithm demonstrates the practicality of the time complexity over the brute-force approach. Although the algorithm has many advantages, it has some shortcomings when solving puzzles of irregular shapes and having only single-color pictures.