基于0－1 规划模型的规则中文碎片拼接复原研究

沈鸿平，章毅鹏，王义康

(中国计量学院 理学院，浙江 杭州 310018)

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域均有着重要的应用［1］。传统的拼接复原工作需由人工完成，虽准确率较高，但效率较低。尤其是当碎片数量巨大时，人工拼接难以在短时间内完成。随着计算机技术的发展，人们试图开发碎片自动拼接技术，以提高拼接复原效率。目前二维碎片拼接研究主要集中在两方面:一是基于不规则碎片的轮廓拼接研究［2－6］，不规则碎片研究在拼接过程中可利用边界轮廓信息进行形状匹配;另一方面是基于碎片文本信息及其特征的拼接研究［7－9］，由于汉字复杂多样，语义识别较为复杂，在解决拼接问题的同时会带来诸多新问题。以上两者比较而言，由于轮廓边界几何特征信息量较少，对其数学模型的研究便显得更为困难。

本文在基于碎片边界轮廓无明显几何匹配特征信息的情况下，通过对碎片内文字行平面分布特征以及行特征信息获取方法的研究，建立基于0－1 规划的中文规则碎片拼接模型。考虑到模型本身的复杂性和求精确解的困难性，提出利用贪婪算法进行求解，并对某一碎片文件进行了拼接模拟仿真，结果表明该方法效果良好。

1 样本数据及图像预处理

样本数据为某一中文文件的规则碎片，来自同一页印刷文字文件，一共209 张矩形碎片，每张矩形碎片大小相同，长与高分别是6.35 cm 和2.96 cm，碎片内文字均为简体中文，且行间距、字间距均相同。图1 为部分碎片图样。

图1 部分碎片图样(6 张)

为了从数字处理角度来进行匹配分析，需应用计算机图像处理技术对碎片进行处理、修饰或转换，从而产生一张数字化的碎片。本文采用图像灰度化方法［10］，将样本中的209 张碎片进行灰度化，每张碎片均产生一个180×72 的矩阵，矩阵的元素为像素点的灰度值，介于0 ～255 之间，其中0 表示黑色，255 表示白色，越接近0 则黑色越深，越接近255 则白色越明显。

碎片上的主要信息由黑白两种颜色构成，为将整个碎片呈现出明显的黑白视觉效果，尽量排除其他色彩噪声的干扰，利用图像二值化的方法［10］，将每张碎片的灰度矩阵二值化，通常采用设置阈值的方法，这里设置阈值为128，即将灰度值＜128 的变成0，否则灰度值为255。将碎片进行灰度化和二值化处理，每张碎片均对应于一个由0 和255 元素构成的数字矩阵。若对二值化的数字矩阵进行图像逆变换处理则可还原成原有碎片图样。碎片数字化处理及反演的全过程如图2 所示。

图2 碎片数字化处理及反演过程示意图

2 0－1 规划拼接模型的建立

对于拼接复原该中文文件碎片，考虑到碎片拼接的唯一性，设定若两片碎片可拼接则取值为1，否则取为0，从而可设0－1 变量为

对于每个碎片的左端而言，至多只有一个碎片与其进行右邻拼接;而对于每个碎片的上端而言，至多只有一个碎片与其下邻拼接。因此可得到拼接约束为

假设209 张碎片样本构成的文本为a 行b 列，即每一行的碎片为b 张，每一列为a 张。则每一行有(b－1)对碎片匹配，同样每一列有(a－1)对碎片匹配，从而可得到总匹配拼接约束为

由式(2)～式(4)得到碎片拼接的0－1 规划模型为

3 基于贪婪算法的模型求解

假设有N 张碎片，根据自由拼接方式，则有N!种拼接情形，对于每一种情况计算每张碎片和其近邻碎片的欧氏距离，从而得到总体匹配度，再对其进行比较，则计算量过大，难以实现。因而对于式(5)所描述的0－1 规划拼接模型，当碎片数量较多时，求其精确解较为困难。故本文提出了一种贪婪算法，能够较快地实现碎片拼接复原。

贪婪算法［11］，其基本思想是对所有碎片先按行拼接，待每行均拼接完成后，再按列拼接复原成完整的图片文件。对于行拼接过程，则按行向欧氏距离总和最小进行匹配，考虑左右两张碎片的拼接。仍采用模型(5)中两两欧氏距离ρ 作为指标，以任意一张碎片开始，先按向右方向进行拼接，若左右碎片的欧氏距离ρlr最小时恰好是相邻关系，则将其拼接在一起，否则将进行人工干预，即将欧氏距离次小的碎片作为右端碎片，再与左端碎片进行拼接并进行文本内容判别，直到找到最符合该端碎片的右端碎片。如此循环，直到将所有碎片按行进行拼接完成。得到行碎片后再进行列拼接，按纵向欧氏距离总和最小进行匹配，从而最终拼接出完整的图片文件。

为减少计算量，本文首先采用聚类分析的方法对碎片进行分类。将碎片的每行文字看作一条粗线，称之为粗基线。分类的标准是将粗基线平面位置一致的碎片归于一类，粗基线的宽度为文字在碎片中的高度，碎片粗基线特征提取示意图如图3 所示。

图3 某张碎片与其粗基线对照图

对于每张碎片，可提取碎片特征向量δ=(h1，h2，…，hk，H)来描述其每行文字到该碎片顶端的距离，直接反映了其文字分布特征。其中hk表示第k 行文字底部到该碎片顶端的距离，H 表示碎片高度，由H 和hk可得到碎片下端空白的高度。

在聚类分析的基础上，通过人工判别，对误分类的碎片适当地引入人工拼接，从而完成整张纸片的拼接复原。基于贪婪算法的碎片拼接复原流程如图4所示。

图4 基于贪婪算法的碎片拼接复原流程图

4 仿真计算与分析

将样本数据中的每张碎片进行随机编号，编号为0，1，2，…，208。首先对碎片进行聚类，在209 张碎片中找到任意一张碎片δ=(h1，h2，…，hk，H)，以该碎片向量作为聚类中心，以碎片边界向量间欧氏距离为匹配度量，并设定样本距离的适当阈值，再进行聚类，则将可能位于同一行的碎片聚为一类。其次，在余下的碎片中再任选一张碎片δ″，同理用上述方法找出与其同类的碎片。如此循环，直到将碎片聚成若干类。

试验结果表明，对本文的样本文件归类，粗基线位置上下波动范围阈值可设为±2，即在粗基线位置附近2 个像素点的位置偏差均视为同一类。经过聚类后得到的分类结果如表1 所示。

表1 基于聚类分析的碎片分类结果

从表1 中可看出，特征明显聚在一起的有11 类，如第1 类中共有19 张碎片，其编号分别为:0，7，32，…，208;而对于某些类中仅有较少碎片的视作未归类碎片，即表1 中最后一列编号为60，102，114，…，185的碎片，这些碎片数量较少，将可能通过人工干预的方式进行分类到前面的11 类中。归类结果中有9 类各分到19 张碎片，而第7 类、第8 类不到19 张，第12 列为未被归入任何类的碎片，从而可推测拼接过程每行可能有19 个碎片。

利用上述贪婪算法进行计算，结果表明，上述9 类中，每一类碎片恰好组成了原文件中某一行碎片块。对于第7 类，首先按照上述算法将已归类好的碎片进行拼接，然后对缺少的碎片利用人工干预的方法在未归类中寻找相匹配的碎片即可。对于第8 类，将未归类中剩余的碎片也归为第8 类，并采用上述算法对第8 类进行拼接。从而得到该文件是由11×19 张小矩形碎片组成，并已将11 行碎片拼接完成。再将11 张碎片块按列进行人工拼接，得到一张完整的原文件。

试验结果表明，对于209 张碎片进行完全拼接复原，人工干预的次数为30 次，算法的行拼接计算量是21 945 次，列拼接计算量是55 次，总计算量为22 000次，相比自由拼接方式下的N!种组合方法的计算量有大幅减少。图5 为某相邻两行的拼接结果。

图5 某两行的拼接结果

5 结束语

本文通过碎片文件进行分析，并考虑了其他色彩噪音的干扰，建立了0－1 规划拼接复原的数学模型，并提出利用贪婪算法进行模型求解，同时利用由209张碎片组成的文件数据进行模拟仿真。仿真结果表明，模型对碎片拼接问题进行了准确的数学描述，随着碎片数量的增加，模型计算量快速增大，而提出的贪婪算法能够较好地解决计算量问题，并能实现碎片快速分类和拼接。本文的结果是基于规则边界且大小相同的矩形碎片，实际中受破碎方式、碎片形状、色彩污染等各种因素的影响，碎片拼接复原异常复杂，深入考虑碎片拼接机制，建立更精确的模型，将可能取得更好的结果。

［1］ 杨洛斌.形状匹配技术在文物复原中的研究与应用［D］.西安:西北大学，2002.

［2］ 贾海燕，朱良家，周宗潭，等.一种碎片自动拼接中的形状匹配方法［J］.计算机仿真，2006，23(11):180－183.

［3］ 罗智中.基于线段扫描的碎片边界检测算法研究［J］.仪器仪表学报，2011，23(2):289－294.

［4］ 谢萍，马小勇，张宪民，等.一种快速的复杂多边形匹配算法［J］.计算机工程，2003，29(16):177－181.

［5］ 朱延娟，周来水.二维非规则碎片的匹配算法［J］.计算机工程，2007，33(24):7－9.

［6］ 张欣卜，彦龙，朱良家，等.物证复原系统中的碎纸轮廓提取技术研究［J］.计算机仿真，2006，23(11):184－187.

［7］ EFTHYMIA T，IOANNIS P.Automatic color based reassembly of fragmented images and paintings［J］.IEEE Transactions on Image Processing，2009，19(3):680－690.

［8］ NASIR M，ANANDABRATA P.Automated reassembly of file fragmented images using greedy algorithms［J］.IEEE Transactions on Image Processing，2006，15(2):385－393.

［9］ 罗智中.基于文字特征的文档碎纸片半自动拼接［J］.计算机工程与应用，2012，48(5):207－210.

［10］阮秋琦.数字图像处理学［M］.北京:电子工业出版社，2001.

［11］杨克昌.计算机常用算法与程序设计案例教程［M］.北京:清华大学出版社，2011.