【摘 要】本文旨在解决规则的矩形碎纸片拼接复原问题，要求尽可能实现程序自动拼接，减少人工干预，以提高拼接复原效率。对于单面纵切纸片，我们首先根据图片左侧边缘空白部分的宽度，确定宽度最大的图片为原文件的左边界。接着将左边界图片作为标准图片，以重合边界左右两侧的图片灰度值向量匹配程度为原则，我们定义两张图片边缘灰度值向量的欧氏距离为边缘匹配程度指标，依次搜索最优匹配的图片。整个复原过程并未参与人工干扰。本文建立了边缘灰度值向量最优匹配模型作为基本模型，可完成中英文文件单面纵切的纸片拼接复原。而随着将算法递进，也可以进一步完成单面横纵切、双面横纵切的纸片复原问题。
　　【关键词】匹配度；图片边缘；灰度值
　　一、研究背景
　　图像拼接是数字图像处理的一个重要分支，是将一系列有重叠边界的图像拼接成一幅大型的无缝的高分辨率图像，包括图像采集、图像预处理、图像配准、图像融合以及图像输出。在很多场合下，人们都会用到图像复原技术，而且对拼接的精确度要求极高。破碎文件的拼接是生活中最为简单常见的情况，在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。我们考虑利用计算机技术，来建立对碎纸机处理后的碎纸屑进行复原的数学模型和算法，替代繁琐的人工拼接，以提高拼接复原效率。但这又对文件复原的正确率提出了很高的要求，避免出现伪拼接。针对碎纸片拼接问题，首先我们首要解决的是一种最基础的复原，如何对来自同一页印刷文字文件、并且仅被碎纸机纵切的破碎纸片，设计拼接模型和算法，将文件进行快速准确复原。
　　二、模型假设
　　（一）假设由于碎纸机等外界因素造成的误差忽略不计。
　　（二）假设碎纸机将文件切割成规则矩形，即切割边界都是直线。
　　（三）假设同一页印刷文件的每一行字都有上下两条标准线。
　　（四）假设在复原过程中可以进行适当的人工干预。
　　（五）假设不存在两张图片能够同时与另一张图片匹配。
　　三、符号说明及名词定义
　　四、基本模型建立与算法分析
　　由于在重合的图片边界左右两侧的灰度值较为接近，我们以重合边界两侧灰度值分布的近似程度大小来衡量两张图片的匹配度，并依此寻找最优的匹配图片。我们记图片的灰度值矩阵为。
　　（二）最左侧边缘图片的确定.考虑到原文件左边缘处会留下较大的空白部分，根据图片左边缘所留空白部分的宽度进行判断，先找出位于原文件最左侧的一张图片，记为。然后根据最优匹配定义可以依次往右拼接图片。
　　（三）算法设计.记图片集合，记已经复原的图片集合（集合中的元素顺序即为图片从左往右的拼接顺序），记未排序的图片集合，即。
　　Step1：提取图片的灰度值矩阵，搜索出位于原文件最左侧的图片，此时，；
　　Step2：计算中所有元素与图片匹配度 ，取成立时的为最优匹配图片。记，则此时，
　　Step3：重复Step2，按最优匹配定义依次从集合中选出元素，按顺序放入集合中进行拼接，直到；
　　Step4：最终得到，按照中元素顺序将图片拼接即可完成碎纸片复原。
　　（四）模型结果分析.根据上述复原模型和算法，我们可以成功的对给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切）完成碎纸的拼接复原。同时中文文件和英文文件在碎纸拼接中并未体现出较大差异，由该模型算法都可以复原。说明我们的模型对中英文文件的碎片数据拼接复原均适用，算法稳定性高。
　　参考文献：
　　[1]林小平，周石琳. 一种基于蚁群算法和互信息测度的图像拼接技术[J]. 重庆理工大学学报（自然科学），2013，27（1）：76-81
　　[2]Edson Justino， Luiz S. Oliveira， Cinthia Freitas. Reconstructing shredded documents through feature matching[J]. Forensic Science International 160 （2006） ：140-147
　　[3]Anna Skeoch. An Investigation into Automated Shredded Document Reconstruction using Heuristic Search Algorithms[J].2006.