目的 结合图像处理技术和英文字母特征,提出一种基于聚类和全局优化的双面碎纸拼接复原算法。方法 利用图像处理技术,消除同行字母的处于不同高度部分。再分别基于处理前后的碎纸片,分别提出碎片与行之间匹配程度以及刻画相邻碎片两两匹配的特征参数(像素差与相关系数)。利用上述两特征参数,将问题转化为两个子优化问题:子问题1,基于像素差的最大值最小目标,建立全局最优聚类模型,确定所有碎片的行分类;子问题2,将同一行中相邻碎片的匹配问题转化为旅行商问题(TSP),并基于相关系数对每一行建立全局优化模型。结果 仿真实验结果表明,图像处理技术能有效地消除同行字母处于不同高度的负影响。同时,获取的两个特征参数能很好地刻画碎片之间的匹配,复原准确率达到90%以上。结论 实验结果表明,该算法能保证高复原率且降低复杂度,对碎纸机碎纸拼接复原具有良好的实际意义。

Objective By combining an image processing technique with English letter feature, we propose a new algorithm based on clustering and global optimization for double-sided shred restoration. Method The image processing technique is applied to eliminate the parts of letters at different height levels. The parameters (pixel difference) that describe the matching degree of adjacent shreds based on preprocessing images are obtained. The parameters (correlation coefficient) of the matching degree of shreds and the rows based on post-processing images are also obtained. The optimization problem is converted into two sub-problems by using these parameters. The first problem is to establish a global optimal clustering model that minimizes the maximum target of pixel difference. The second problem is to translate the problem of matching adjacent shreds in the same row into a traveling salesman problem (TSP). A global optimization model is developed to solve the TSP for each row. Result Our simulation result demonstrates that the proposed image processing technique considerably eliminates the negative influences of the letter parts in different levels. The two feature parameters can capture most information of the matching degree. Recovery accuracy reaches over 90%. Conclusion This study presents an efficient algorithm for shred restoration based on clustering and global optimization. Experimental results show that the proposed algorithm can significantly reduce the complexity of the optimization problem with good restoration result. The proposed algorithm has practical significance in shred restoration for paper shredders.