基于线性规划的碎纸片拼接复原模型

毛星雨

（西南科技大学理学院 四川 绵阳 621010）

1 引言

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

2 模型预处理

由于图片信息中仅有字的黑色和空白处的白色两种截然相反的信息，而且为了进一步简化计算，本文采用二值化而非灰度图像进行碎纸片图像的处理，得到每条碎纸片像素大小为1980×72（长×宽），像素点取值0或1，分别表示图像颜色的黑与白。

为进行图像的整合，首先对其边缘信息进行提取，并用19×2的矩阵edge[i，j]存储每一条碎片的边缘像素点信息。从而可以进一步就建立一个19×2的count[i，j]矩阵，该矩阵存储每一条碎片边缘取值为0的像素点的数量。

根据count矩阵，可得到edge[i，0]=0的碎片，由于其黑色像素点的数量为0，所以该碎片在原始文件中处于最左端的位置。

为进一步提高匹配精确性，需要另外一个参数对碎片进行数据采集。而由于图片的行上像素点较列上像素点少很多，所以本文提取碎片图像的行特征进行处理。首先确定碎片顶端取值为0的像素点的位置，以其作为上边界，依次向下取w为行宽（这里取w=40pixels以保证能容纳每一个文字）直至下边缘，得到每一条碎片的行数为然后取作为最终确定的行数，然后同理对生育碎片进行行化。最终将每一条碎片划分为28行。

3 模型建立

为了衡量两个碎片间的匹配程度，本文引入匹配度Mij定义如下：

其中，n为行的总数，mijk表示碎片i和碎片j第k行之间的匹配度，Mij表示碎片i和碎片j之间的匹配度。

首先需要确定最左侧的碎片，然后根据匹配度的定义可以计算各个碎片两两之间的匹配度，从而将问题简化为：已知最左侧的碎片，然后一个个根据匹配度最大原则拼接。

可以看出，这个问题类似于旅行商问题，将它们进行类比后进一步解释为：

图1 问题简化示意图

图中 节点表示碎片，有向线段长度表示权值ωij，且ωij=1-Mij，箭头指向表示前一条碎片右侧边缘到后一条碎片左侧边缘。

现在问题转变为寻找一条回路遍历所有的节点使得权值之和达到最小的TSP问题。假设图中存在Hamilton回路，有n个节点，图中（i，j）边的权重为ωij，设决策变量为χij=1说明弧进入到Hamilton回路中。

4 模型求解

通过一系列分析，将求解转化为线性规划最大值的求解，具体步骤为：

（1）将所有碎片数据进行处理，组成碎片集，选择出最左端的碎片，记为Si，然后将其从碎片集合中移除。

（2）提取Si碎片右侧边缘数据，将其与碎片池中碎片左侧边缘数据意义配对并求出匹配度Mij。

（3）选择匹配度最大的碎片作为碎片Si的右侧碎片，并将其更新为新的Si碎片，将该碎片从碎片集合中移除。

（4）重复步骤2～3直至碎片集合为空。

由于该算法使用统计量构建匹配度，很好的避免了中英文之间的差异性，适用性较好，在实际的应用中都收到了很好的效果。通过求解结果发现，利用贪心策略求解得到了全局最优解，原因在于匹配度的定义较好。同时由于碎片两侧提供的信息量大，很好的避免了中英文之间的差异性。若碎片规格变小，信息量减少，中英文之间差异性的讨论显得十分有必要。

5 结语

本文解决的是纸片规则竖直切割的拼接复原问题，但是实际生活中许多类似的纸片的损伤很可能是不规则的如按照斜线分割。所以考虑如果将纸片分割，将平行于切割方向的方向看做水平或者竖直的情况，剩下的部分再单独讨论，这样可以将本文的模型推向更普适的情况。此模型整体效果较好，人为干预较少，能够在较复杂的情况下完成碎纸片的拼接。