碎纸片的拼接复原

摘 要：关于破碎文件的拼接复原是我们现实生活中的实际问题，主要就是根据碎纸片边缘的字迹、文字之间的行高、间距等特征，确定合理的拼接方案。本文作者通过建立合理模型，采用灰度值矩阵，进行计算机计算，再通过人工干预，最终得到完整的拼接结果。

关键词：灰度值矩阵；匹配模型；Pearson相关系数；人工干预

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。

1 模型的假设与符号说明

1.1模型的假设

（1）假设所有碎纸片原有的文本中字与字、行距、段落间距是相同的；

（2）假设所有的碎纸片都能拼接上，没有多余或者缺少；

（3）假设所有碎纸片的文字字体大小相等；

（4）假设每篇文本的左右页边距、上下页边距相同，且距离适中；

（5）假设文本读取方向从左往右、从上往下。

1.2模型的符号说明

[ai]：碎纸片左边缘字迹的灰度矩阵；[bj]：碎纸片右边缘字迹的灰度矩阵；[A]：所有碎纸片左边字迹的灰度矩阵；[B]：所有碎纸片右边缘字迹的灰度矩阵；[D]：所有碎纸片左右边缘字迹灰度值的差异度；[dij]：左边缘[i]与右边缘[j]的灰度值差异度；[xij]：0-1变量，当左边缘[i]与右边缘[j]配对时取1，否则取0；[mi]：序号为[mi]的碎纸片；[am，n]：矩阵[ai]中的元素；[bm，n]：矩阵[bj]中的元素

2 问题的分析

我们对于附件一中来自同一页印刷文字文件的碎纸机破碎的纸片（仅纵切），建立碎纸片拼接复原模型和算法。通过观察可以发现，文字文档的文字行方向是平行并且单一的，如果某一个碎纸片内的文字行在边缘处断裂，那么与它相邻的碎纸片在边缘处也一定具有相同高度的文字行，我们凭借此特征可以从碎纸片边缘字迹相似的多个碎片中挑出相邻的碎片。

首先，根据每张碎纸片边缘的字迹断线，利用matlab来获取纸片左右边线字迹的灰度值，其中每张碎片左右边缘的字迹灰度为两个[1980×1]阶的灰度值矩阵。接着利用欧氏距离来计算，所得到的值越小，那么两张碎纸片的相似度就越高。在此基础上，得出所有纸片的边缘的差异度，形成一个两两之间的差异度矩阵[D]。最后，我们将问题的求解转化为19对边缘的匹配问题，即确定一个合理的配对方案，使得总的差异度最小。

3模型的建立与求解

3.1问题的求解

问题要求对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法。我们是这样考虑的：

根据每张碎纸片边缘的字迹断线，获取纸片左右边线字迹的灰度值。每张碎片左右边缘的字迹灰度为两个[1980×1]阶的灰度值矩阵。利用欧氏距离计算所有碎纸片的左边缘字迹与所有右边缘字迹的差异程度，所得到的值越小，那么两张碎纸片的相似度就越高。

3.1.1碎纸片的图像预处理

为了得到每张碎片左右边缘字迹的灰度值矩阵，我们将19张中文碎纸片导入到matlab中得到一个[1980×72]的灰度矩阵数据，由于碎纸片仅纵切，并且在拼接时是左右拼接的，因此选取每个矩阵的首列和尾列，即为边缘字迹的灰度矩阵。

以附件一中的000序号碎纸片为例，该碎纸片的左边缘字迹的灰度矩阵[a1]为

（255，255，255[…][…]46，255，255，160，99，29，[……]255，255，255）T ，右边缘的字迹灰度矩阵[b1] 为（255，255，255，[……]168，187，198，199，201，[……]，255，255，255）T 。

将所有的左边缘矩阵[ai]并在一起，所有的右边缘矩阵[bj]并在一起，可以得到左边缘矩阵[A=（a1，a2，……a19）]，右边缘矩阵[B=（b1，b2，……b19）]，利用欧氏距离公式，计算左边字迹灰度[i]与右边缘[j]的差异值[dij]为：

[dij=（ai1-bj1）2+（ai2-bj2）2+…（ain-bjn）2]，

其中[ai1，ai2，...ain]为矩阵[ai]中的元素，[bj1，bj2，...bjn]为[bj]矩阵中的元素。

3.1.2碎纸片的合理配对

经过分析讨论，对于每一碎纸片，仅仅只看与它差异度最小的碎纸片，发现最终的结果并不是全部匹配成功的，因此我们需要综合来考虑所有碎纸片的合理匹配，即确定一个合理的配对方案，使得总的差异度最小[2]。

为了反映左边缘[i]与右边缘[j]是否成功配对，我们引入0-1变量[xij]，使得 [xij=1，边缘i与边缘j 配对成功0，边缘i与边缘j未配对成功]

于是我们可以将问题的求解归结为所有19对边缘（分为左、右边缘）如何合理配对能够使得总的差异度值[i=119j=119dijxij]最小。

接着，讨论配对优化模型的约束条件。由于每一个左边缘只能与另一个右边缘配对，因此有

[j=119xij=1，i=1，2，…19]；[i=119xij=1，j=1，2，…19]。

这是一个0-1规划问题，为了防止运算结果出现碎片自身拼接的现象以及方便计算的需要，我们将差异度矩阵[D]中的对角线的数值设为10000。接着利用LINGO软件[3]编程求解可以得到碎纸片的最优的配对方案（程序代码见附录）如表一所示：

表一 英文文字碎片的复原顺序

[3＼&6＼&2＼&7＼&15＼&18＼&11＼&0＼&5＼&1＼&9＼&13＼&10＼&8＼&12＼&14＼&17＼&16＼&4＼&]

4模型的优缺点及改进方向

4.1模型的优点

（1）本文的碎片拼接复原选取了匹配的方法，建立了0-1规划模型，使得求解结果唯一并且具有很高的准确性，也在一定程度上简化了人工干预。

（2）我们运用了Pearson相关系数，利用系数的大小关系来确 定某一碎纸片的相邻碎纸片，思想简洁易懂，并且结果具有说服力。

（3）在每一次的拼接中，我们的首要工作是寻找原文本的起始碎片（或结尾碎片），这大大方便了之后的拼接。

4.2 模型的缺点

（1）拼接模型的灵活性不够强，不能够将其通过适当的改变通用于中英文文字碎片的拼接；

（2）由于碎片数量较大，仅仅利用英文文本拼接算法，不能够完全避免一张碎片的正反两面拼接在一起的情况，使得结果带有较大部分的人工干预。

5模型的改进方向

我们认为为了使得算法的结果更加可靠，可以先进行分类，缩小算法寻找适合拼接碎片的范围，从而减小人工干预对结果的影响。在本文的英文字母拼接中，我们只是考虑了拼接碎纸片的边缘是否匹配。除此之外其拼接准确度无疑比单纯利用文字边界的灰度特征方法要好很多。

参考文献：

[1] 刘卫国.MATLAB程序设计与应用[M].北京：高等教育出版社，2006

[2] 韩中庚.数学建模方法及其应用.北京：高等教育出版社[M].2009

[3] 袁新生，邵大宏， 郁时炼.LINGO和Excel在数学建模中的应用[M].北京：科学出版社，2007

[4] 贾海燕.一种碎纸自动拼接中的形状匹配方法[J].计算机仿真，23（11）：180-183，2006