基于边界链码的球链接形状拼图算法

Linked-ball shape jigsaw puzzle solver based on boundary chain code

针对可扩展的球链接形状拼图,提出了一种基于边界链码的拼图算法。首先利用由Morre方法改进的边界检测方法生成边界链码,然后通过原始链与差分链的相互转换实现链接球形状的翻转和旋转,其次基于最大数量链码匹配、合理性检查实现形状拼接,最后通过链码与形状矩阵互相转换完成形状定位和结果显示。矩阵大小为5～9的拼图实验中,一次实验所用拼图次数为1的实验数占比从0. 69下降到0. 02,说明随着拼图矩阵增大,拼图复杂度升高。对矩阵大小为6～10的拼图做1 000次实验,与基于矩阵填充的算法相比,基于边界链码的算法平均用时最高下降了68. 2%,分析表明该算法效率提升的关键是减少了拼图过程形状选择的随机性。

A solver based on boundary chain code was proposed for an extendable linked-ball shape jigsaw puzzle.First,chain code was generated with a modified Morre boundary check method,then mirror and rotation of the shape were implemented by transformation between the differential chain and the origin chain,and the assembly of shapes was completed based on maximum-number chain code matching and new chain s rational check,finally the result show and shape location were achieved by mutual transformation between the chain code and the shape matrix.In the experiments for matrix scale 5 to 9,the ratio of experiment with number of assembly is one dropped from 0.69 to 0.02,which shows the complexity of the jigsaw puzzle increases along with the increase of the matrix scale.Compared with the solver based on matrix filling,the maximum decline of the average time of 1 000 experiments for the jigsaw puzzle with matrix scale 6 to 10 is 68.2%,and the analysis indicates that the key to the efficiency improvement of the solver based on chain code is the reduction of the shape selection randomness in the assembly process.