碎纸片还原技术的研究

张立臣 肖松平 王国庆 谢冬雪 周旭

摘 要：碎纸片的还原在司法物证复原、历史文献修复以及军事情报获取等领域都有重要应用。本文考虑到计算机不能自动识别图片中的文字所以对文字进行了灰度处理得出图像中每一个像素点的灰度值，将文字信息转化为数字信息，得到一个1980×72的数字矩阵。而切割处的灰度值应该是近似相等的。由于白纸黑字的区分度是比较好的，因此采用0-1整数规划模型以及聚类分析，以切割处左右两端的灰度值相差绝对值之和最小为目标，利用贪心算法逐步搜索，最终拼出完整的印刷文字文件。准确还原碎纸片对文献修复、证物复原等都提供了良好的理论基础。

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

0引言

破碎文件的拼接以及汉字识别应用的领域越来越广泛，更高的要求了识别资源的实时性。本文建立的模型可推广应用于汉字识别系统，资源消耗少、识别速度快，有着很好的应用前景。还可以推广到类似的研究方向如在文物碎片的自动修复、虚拟考古、医学分析等領域。

1.前期准备过程

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

选取格式为MBP且位图数据为8的材料，对数据进行灰度化处理过程中，需要将其转化为RGB三通道颜色格式，使用24位来表示一个像素点。同时考虑到JPEG格式的图形具有容量小，处理稳定的特点，因此将其转化为24位深度的JPEG格式。之后，对碎纸片的图像进行灰度处理，得出图像中每一个像素点的灰度值。而灰度值本身的大小则取决于像素点中所含的红、绿、蓝三种成分。为了简化数据处理及其运算，采用0-1整数规划对图像进行二值化处理，将使用阈值变换法[1]把灰度图像转换成二值图像。所谓二值图像， 一般意义上是指只有纯黑（0）、纯白（255）两种颜色的图像。

在灰度化处理中，MATLAB 默认运用的加权平均法，即加权平均法根据重要性及其它指标，将三个分量以不同的权值进行加权平均。因此，按下式对RGB 三分量进行加权平均能得到较合理的灰度图像。

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

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

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

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

由于附件中所给碎纸片均为白纸黑字，因此原图切割前的信息具有一定的连续性，本文对于问题一的拼接过程使用贪心算法的思想[3]。问题一只考虑纵切的情况，因此设 、 分别左右的表示两个碎纸片所对应的灰度矩阵，则 矩阵的最后一列元素与 矩阵的第一列元素之间的偏差距离函数可以表示为：

其中，A1（n，72） 代表A1 矩阵的第72列，An（n，1） 代表An 矩阵的第一列，若存在An 使得y（A1，An） 达到最小，则An 代表的碎纸片即可与A1 代表的碎纸片拼接，通过MATLAB 来实现。最初得出的结果为大体碎片均可以成功拼接复原，但就整张纸而言，从中间位置处左右颠倒，由于给定的来自同一页印刷文字文件左右两端均为空白由上述函数求值很容易可以求得最小值，因此在贪心算法搜索过程中优先把左右两端进行了拼接。本文首先确定出最左侧的碎片即左侧空白最宽，然后从剩下的样本中寻找与碎纸片的边界差异度最小的碎片作为下一个碎片，再寻找与第2个碎片配对的第3个碎片，以此类推，解决了碎纸片整篇存在左右颠倒的情况，并且减少了计算量。最终，在没有进行人工干预，成功地将附件1、2碎纸片分别拼接复原，模型简单操作简单，准确率高达100%。

2.横、纵切的单面碎纸片的拼接复原模型

2.1中文文件的拼接复原

2.1.1欧氏距离排出边缘纸片

由题意及附件所给信息可知，对于中文的文件，撕碎的原纸张四周的空白间距大于行间距的空白间距，因此可先根据空白间距较大的特点求出原纸张四周碎纸片的编号，以左侧为例。考虑到节约算法的空间复杂度，本问舍弃了全局搜索的贪心算法，巧妙利用题一中拟合的思想，采用0-1整数规划对109张图进行二值化处理后，求其边界的欧式距离[4]：

在灰度图像中，一张纸张的图像可以表示为一个二维数组，其中（i，j） 对应的像素点的灰度值，设 为目标点集合，计算边界的欧氏距离。取其距离为0的左侧图形，对每张碎纸片图像的上下边缘进行欧氏距离的比较，得出可在无人工干扰的情况下自动排出左侧的纸片顺序，按照上述方法计算欧式距离，可以较快地自动排出原纸张右侧、上侧、下侧的碎纸片的拼接顺序。

在无人工干预的情况下，准确地排出原纸张四个边缘的碎纸片的顺序，得到边缘复原结果，并在一定程度上节约了算法的空间复杂度[5]。

2.1.2内部纸片的拼接

根据上述已经准确排出原纸张四个边缘的碎纸片的排列顺序，从左上角开始，在问题一中取碎纸片A1灰度矩阵的最后一列元素与A2 灰度矩阵的第一列元素之间的偏差距离[12]最小的作为下一张碎纸片拼接，以此类推。在问题二中，采取上述的方法进行模拟运行，发现由于碎纸片的数目增多，匹配率达不到预期的目标，往往需要人工干预进行调整，故为了确保碎纸片的拼接准确率，需要考虑引入更多的有关变量来进行匹配搜索。经过演绎推理，碎纸片由于横纵切，因此内部纸片的排序需要综合上侧碎纸片的下边缘灰度值和左侧纸片的右边缘灰度值，依据公式计算其三张碎纸片间的欧氏距离之和：

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

3. 结论

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

参考文献：

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

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