李凡

摘 要：碎纸片的还原在司法物证复原、历史文献修复以及军事情报获取等领域都有重要应用。本文考虑到由于计算机无法自动辨别碎纸片中原有的文字，因此对碎纸片进行了灰度处理，计算出图像中每一个像素点的灰度值，实现了文字信息向数字信息的转化。因为文件的白纸黑字存在明显的区分度，所以运用0-1整数规划模型将切碎片边缘两侧的灰度值之差的绝对值之和最小为目标，利用贪心算法逐步计算，从而复原原有的文件，此技术在文献修复、证物复原等方面存在良好的应用前景。

关键词：灰度处理;贪心算法;0-1整数规划

人工拼接很难在短时间内实现碎纸片文件的复原。近年来计算机技术的开发与运用日渐成熟，人们尝试开发碎纸片的自动拼接技术，用来提高拼接复原效率。基于碎纸片中字迹断线同文字的匹配程度考虑，本文利用0-1整数规划、灰度处理、贪心算法等方法解决该问题，达到了预期的良好结果。建立的模型在汉字识别系统、文物碎片的自动修复、虚拟考古、医学分析等领域都将有很好的应用前景。

1 前期准备

1.1 基于0-1整数规划的图片处理

对碎纸片的图像进行灰度处理，得出图像中每一个像素点的灰度值。为了简化数据处理及其运算，采用0-1整数规划对图像进行二值化处理，利用阈值变换法[1]把灰度图像转换成二值图像。在灰度化处理中，MATLAB默认运用的加权平均法，因此，按下式进行加权计算可得到较合理的灰度图像。

采用最大类间方差法[2]来求阈值，最大类间方差的基本思想是使用一个阈值将整个数据分成两个类，方差的定义如下：

如果两个类之间的方差最大，那么这个阈值就是最佳的阈值。其阈值将由系统自带的函数处理而得来：

描述碎片的模型为图像的各个灰度值所组成的灰度矩阵，即图像上的每个像素点都可以对应到灰度矩阵的每个元素。每个碎纸片均可以确定一个同型的灰度矩阵，因此灰度矩阵的特征可以反映图像的特征，其每一列构成了一个描述局部特征的列向量。

1.2 基于贪心算法思想的搜索

基于碎纸片原图损坏前的内容具有一定的关联性，采用贪心算

法[3]的思想用A1、A2代表两个灰度矩阵，分别对应任一两个碎纸片，则A1矩阵的最后一列元素与A2矩阵的第一列元素之间的偏差距离函数可用下式表示：

2 中文文件的拼接复原

2.1 欧氏距离排出边缘纸片

基于中文文件损毁的原纸张边缘的空白间距大于内部行间距的空白间距的特性，可先根据此特性求出原纸张四周碎纸片的编号，以左侧碎纸片为例。采用0-1整数规划将纸片二值化处理，计算其边界的欧氏距离[4]：

在灰度图像中，一张碎片的图像可以表示为一个二维数组，其中（i，j）对应像素点的灰度值，设为目标点集合，计算边界的欧氏距离。取其距离为0的左侧图形，对每张碎纸片图像的上下边缘进行欧氏距离的比较，准确地排出原纸张四个边缘的碎纸片的顺序，得到边缘复原结果。

2.2 内部纸片的拼接

根据上述已经准确排出原纸张四个边缘的碎纸片的排列顺序，从左上角开始，取碎纸片A1灰度矩阵的最后一列元素与A2灰度矩阵的第一列元素之间的偏差距离最小的作为下一张碎纸片拼接，以此类推。为了确保碎纸片的拼接准确率，内部纸片的排序需要综合上侧碎纸片的下边缘灰度值和左侧纸片的右边缘灰度值[5]，依据公式计算其三张碎纸片间的欧氏距离之和：

选取距离最小的匹配纸片，做下记录，并利用贪心算法的思想，以此为新的已知碎片进行下一步的搜索匹配。根据上述模型，基本不需要外界辅助，基本实现了中文文件横纵切割碎纸片的自动拼接复原。

1.3 英文文件的拼接复原

由于英文的四线三格的特殊书写模式导致其边缘的灰度值数据不足[6]，不能够精确的搜索到正确的碎纸片来进行匹配，因此选取一个右上角的碎片作为试验匹配样本，

为确保得到的碎纸片是合理位置，对碎纸片进行聚类分析从而进一步筛选。为使英文文件的拼接复原更好地解决，本文首先参照中文文件的建模方法，准确找出完整文件周围四个损毁纸片的正确顺序，以左上角为切入点，计算上侧纸片的下边缘灰度值和左侧纸片的右边缘灰度值，依据公式求解其碎纸片间的欧氏距离之和，将欧氏距离之和升序排序，筛选最小的十个碎纸片作为一个解集，并依据确定的最左侧边缘碎片的上边距及其下边距进行聚类分析，在解集范围内寻求最优解。以此类推完成第二列的排序。由模拟仿真所验算，此类先确定解集范围，再进行优化聚类确定正解的数学模型，深度优化了全局筛选出正确的碎纸片的时间复杂度和空间复杂度[5]。

2 结论

在横纵切的碎纸片中，我们分别依据中文、英文的结构特征，选取了先确定边缘，后双变量匹配搜索的数学模型。先边界后内部的逐渐填充的列向排列的方式，省去了横向合并的步骤，并在英文拼接过程中，引入聚类优化的二步筛选过程，在局部内寻求正解，减少了模型的算法复杂性且正确率理想，实现了碎纸片的横纵切割的拼接复原。可推广应用于文字识别系统、文物碎片的修复、虚拟考古、医学分析等领域。此方法资源消耗少、识别速度快，有着很好的应用前景。

参考文献

[1]杨治平.基于自适应多阈值变换编码的图像二值化处理[J].重庆师范学院学报：自然科学版（3）：77-80.

[2]齐丽娜，张博，王战凯.最大类间方差法在图像处理中的应用[J].无线电工程，2006（07）：29-30+48.

[3]李金旭，朱景立，黄悦悦.求解TSP的随机贪心算法[J].漯河职业技术学院学报，2015（05）：32-35.

[4]黄文奇，刘景发.基于欧氏距离的矩形Packing问题的确定性启发式求解算法[J].计算机学报，2006，029（005）：734-739.

[5]徐菲.淺析算法及算法复杂性[J].科技信息，2012，000（033）：247，256.

[6]王文远.基于灰度值数学形态算子处理的各向异性扩散[J].复旦学报：自然科学版，2004，43（5）：884-888.