A New Intelligent Jigsaw Puzzle Algorithm Base on Mixed Similarity and Symbol Matrix

摘要

Jigsaw puzzle algorithm is important as it can be applied to many areas such as biology, image editing, archaeology and incomplete crime-scene reconstruction. But, still, some problems exist in the process of practical application, for example, when there are a large number of similar objects in the puzzle fragments, the error rate will reach 30%-50%. When some fragments are missing, most algorithms fail to restore the images accurately. When the number of fragments of the jigsaw puzzle is large, efficiency is reduced. During the intelligent puzzle, mainly the Sum of Squared Distance Scoring (SSD), Mahalanobis Gradient Compatibility (MGC) and other metrics are used to calculate the similarity between the fragments. On the basis of these two measures, we put forward some new methods: 1. MGC is one of the most effective measures, but using MGC to reassemble the puzzle can cause an error image every 30 or 50 times, so we combine the Jaccard and MGC metric measure to compute the similarity between the image fragments, and reassemble the puzzle with a greedy algorithm. This algorithm not only reduces the error rate, but can also maintain a high accuracy in the case of a large number of fragments of similar objects. 2. For the lack of fragmentation and low efficiency, this paper uses a new method of SSD measurement and mark matrix, it is general in the sense that it can handle puzzles of unknown size, with fragments of unknown orientation, and even puzzles with missing fragments. The algorithm does not require any preset conditions and is more practical in real life. Finally, experiments show that the algorithm proposed in this paper improves not only the accuracy but also the efficiency of the operation.