碎片拼接 基于模拟退火算法与系统聚类法，文章首先依次介绍了

摘要：基于模拟退火算法和系统聚类方法，首先介绍了仅纵向切割、横向切割和纵向切割以及双面打印三种情况下碎纸碎片的拼接和修复要点。 。 然后对全文进行审阅。 总结与展望。

关键词：碎片化； 拼接； 恢复; 模拟退火算法； 系统聚类法

碎纸碎片的拼接与修复在历史文物鉴定、法医鉴定、情报获取等诸多领域有着极其重要的应用。 随着计算机技术的发展碎片拼接，传统的手工修复方法带来的效率低下的弊端日益凸显。 因此，通过数学建模方法获得碎纸碎片自动拼接修复模型，以提高拼接效率显得尤为重要。 对此已有文献报道。 已有一些研究[1-3]。 本文以2013年全国大学生数学建模竞赛B题为例，基于模拟退火算法和系统聚类分析，介绍了仅纵向切割、横向切割和纵向切割三种情况下的碎纸情况，和双面打印。 胶片拼接与修复要点。

1 仅纵向切割碎纸拼接恢复要点

第6步：冷却。 选择冷却系数θ（通常是接近1的数字）进行冷却，即将T替换为θT，得到新的温度。

步骤7：算法终止条件。 使用选定的终止温度Te来确定退火过程是否完成。 如果T

这样，由于切碎的纸片较大，图片信息更加明显，因此无需人工干预，回收率可以达到100%。 附录2中的英文图片可以类似处理。

2 水平和垂直切割纸片的拼接和恢复要点

对于既有横切又有竖切的碎纸片的拼接还原，如果用上题的方法直接拼接全部209张图片，一方面必然会导致算法运行效率大大降低; 另一方面，由于微分每张图片之间的边界差异的灰度值信息较少，很容易导致拼接时重码率较高、恢复率较低。 因此，我们采用的方法是首先提取所有图片的行特征； 然后对209张图片建立行聚类模型，按照上题的方法对每一行进行聚类并重新排列图片； 最后，对相似的行进行水平排序，可以将碎片拼接起来还原。 具体步骤如下：

第一步是提取图像的行特征。 使用读取到的图像将每幅图像转换为180*72的灰度值矩阵； 那么可以计算出汉字高度为40像素，行距为31像素。

第二步是建立行聚类模型。 主要思想是位于同一水平行的图片具有相同的空白行分布特征。 所谓空白行，是指该行中正好有72个像素点的灰度值等于255（这样的行赋值为1，否则赋值为0）； 所谓分布特征是指每张图片的180行。 ，空行分布的位置或范围。 因此，每张图片中空白行的分布对应着一个180维的向量，可以称为特征向量，其元素为1或0，第i张图片的特征向量记为etai。 为了使系统聚类方法能够顺利运行，此时需要人工干预，即根据字符高度和行距补充包含大空白行的图片的信息，以及新的空白行分布范围得到图片。 最后我们可以使用系统聚类方法中的最短距离法（类间）进行聚类，但此时图片之间的距离为d'(i,j) = ηi-ηj1。 通过调整最短距离值，将所有209张图像分为11个类别（行），每个类别（行）包含19张图像。 然后按照上一题的方法对每一行进行聚类，并重新排列各列之间的图片。 由于信息量较小，边界区分不明显，有时需要人工干预。

第三步，将拼接后的相似行进行水平排序，还原附录3中的片段。

附录4中的英文图片可类似处理。 与上述方法的区别仅限于中英文字符的不同特征导致中英文图片的预处理方法不同以及图片特征提取方法不同。

3 双面打印文字片段拼接还原要点

对于文字双面打印，解决方法与第二个问题基本相同。 首先，使用系统聚类方法将所有418张图片分为11类。 现在每个类别包含38张图片，然后重新排列它们以获得同一行的正面和背面。 使用模拟退火算法求解时，同一个初始值理论上对应两个最终值。 因此，在重新排列时需要充分利用文本的双面信息。 您可以选择前后路径总和最小的安排作为恢复方案。 由于边界区分不明显，有时需要人工干预。 与第二题第三步相同，同时考虑正面和负面信息，最终还原附录5中的片段。

4 总结与展望

从回收率的角度来看，本文基于模拟退火算法和系统聚类分析建立的模型是非常有效的。 缺点是不再适合切割不均匀且文字歪斜的纸片。 因此，建立一个更通用的模型是我们的下一个目标。

参考

[1]王晓瑞，吴新才，李军.模拟退火算法改进策略在模板匹配中的应用[J]. VIP 信息，1997 年。

[2] 罗志忠. 基于文本特征的文档片段半自动拼接[J]. 计算机工程预测应用，2012，48(5)：207-210。

[3]蒋启元，谢金星，叶军。数学模型[M]． 高等教育出版社，2003。