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

摘要： 智能拼图算法常用的方法是先求出各个碎片之间的相似度度量，再根据度量还原图像。MGC（马氏梯度相似度度量）是其中一种很有效的度量，但在实际运用过程中，如果碎片中有大量相似物体存在时，算法不能很好地还原图像，会出现类似于“乱码”的情况。提出了一种利用Jaccard（杰卡德）度量，结合MGC度量，计算图像碎片之间的相似度，再利用贪心策略还原图像。实验结果表明，对于由自选图像随机生成的碎片，算法能够更准确地还原图像，并且能减小出现“乱码”图像的概率。提出了把Jaccard度量和MGC度量相结合的方法运用在智能拼图的还原中，尤其是当拼图碎片中有很多相似物体的情况下，该方法能明显地减少“乱码”现象，同时实验仿真结果证明了提出的方法比单纯的MGC方法具有抗噪性强和拼图准确率高的特点，在考古学碎片图片和文字复原、计算机取证、图像合成和场景无缝拼接等领域有一定的实用价值。

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