关键词: 智能拼图, 杰卡德度量, 马氏梯度相似度度量（MGC）, 最小生成树

Abstract: To solve jigsaw puzzle, the first step is to obtain similarity measure between pieces, then reassemble the puzzle based on similarity measure. MGC （Mahalanobis Gradient Compatibility） is one of the most effective measures, but there are still some problems existing in the process of practical application. For example, using MGC to reassemble puzzle causes an error image every 30 or 50 times. This paper aims to get a better and more stable algorithm, which will prevent or reduce the emergence of the error images. In this paper, a new measure is proposed to solve this problem. First of all, the effectiveness of Jaccard compatibility is verified and when δ=2 the algorithm has a better performance. Though it is effective, it has a bad performance when the piece is very small, especially less than 20 pixels. Combined Jaccard and MGC together, two new measures called JMGC1 and JMGC2 are produced. In the next part of experiments, comparing MGC with the two new measures, the results show that JMGC2 has the best performance on the test images. The proposed approach can increase the accuracy of reassembling puzzle and decrease the emergence of error images. In the paper, a new measure, called Jaccard compatibility, is introduced. Combined with MGC, the paper proposes two other measures named JMGC1 and JMGC2. With the new measures and a greedy algorithm to find the MST （Minimal Spanning Tree） in the matrix of compatibility, the algorithm can reconstruct image effectively. The experimental results show that the measure is comparable to the state-of-the-art and even outperforms them for some test images. The proposed algorithm has a great improvement in the stability and accuracy, it can bring great convenience in practical application.

Key words: jigsaw puzzle, Jaccard compatibility, Mahalanobis Gradient Compatibility（MGC）, minimal spanning tree