基于文档内容的碎纸拼接技术

陈黎黎，国红军

(宿州学院 信息工程学院，安徽 宿州 234000)

破碎文件的拼接技术在刑侦案件中的物证复原、考古研究中的历史文件和壁画修复以及军事情报获取等领域发挥着极其重要的作用.早期，碎片拼接复原工作是由人通过手工操作完成的，尽管拼接复原的准确率较高，但工作效率极低，特别是当碎片数量巨大时，手工拼接过程费时费力，一般很难在较短的时间内完成.随着计算机技术的飞速发展，为提高破碎文件的拼接和复原效率，人们逐步开始研究文件碎纸片自动拼接技术，即从许多散乱的文件碎片中，借助计算机通过特征匹配技术来识别出相邻的碎片，进而重现整个文件的原貌.

1 问题的提出

目前，国内外有关碎片拼接的方法有很多种.根据碎片特征可分为基于轮廓、色彩、纹理等特征的图像碎片拼接；根据碎片形状可分为规则碎片和不规则碎片的拼接；根据碎片的空间特征可分为二维和三维图像碎片的拼接等.

大部分对碎片拼接复原方法的研究主要集中在碎片轮廓的匹配上，即基于轮廓的碎片拼接技术研究.许多学者提出了大量的算法，如，Helena Cristina da Gama Leitao etc[1]提出了一种典型的解决平面图像碎片匹配算法.H.J.Wolfson等[2]运用串匹配的技术查询最大匹配子串，解决了平面曲线匹配的问题.Ying Shan等[3]提出了一种概率框架的曲线匹配算法.朱良家等[4]对碎纸轮廓提取技术进行研究，通过对候选集评分的方式实现了对图像碎片的拼接.朱延娟等[5]提出基于Hausdorff距离的多尺度轮廓匹配算法等.这些算法实现了对碎片轮廓的匹配，已取得了一定的成果.但是，通常被碎纸机切碎的带有文字或图像信息的文档，其边缘是规则的，以上算法对这类碎片进行拼接复原时显然会失效[6].因此，研究基于文档内容的规则碎纸拼接技术是十分必要的.本文讨论的是被碎纸机横向或纵向规则切开的碎片的拼接复原技术，并在研究过程中做如下假设：

假设一：任意两碎纸片的长度、宽度相等.

假设二：任意两碎纸片间的厚度与纸张材料相同.

假设三：任意碎纸片在切割后无信息丢失(即无破损).

假设四：所有碎纸片无丢失、无多余、无沾污.

2 碎片预处理

为方便计算机对文件碎片进行拼接处理，首先将每张碎片通过扫描仪转换为bmp格式的图片并传输到计算机中，然后再对碎片图像进行预处理.

由于扫描文件碎片的时候可能会发生倾斜现象，为此需要对倾斜图像进行调整.首先，找到倾斜图像的1至50列每一列最上面像素值为0的点，从这50个点中选出最上面的点.按此方法找出第51至100列(碎片图像的宽度总列数大于100)中处于最上面的像素值为0的点.利用这两个点找出平行于碎片中文字的直线，如图1.

图1 发生倾斜的碎片

然后根据直线的斜率进行碎片角度的调整，调整后的碎片图像如图2所示.

图2 调整方向后的碎片

本文以每页打印纸被纵切19条碎片为例，其中的某一条文件碎片经预处理后如图3所示.

图3 预处理后的纵切碎片

3 碎片的特征提取与匹配

经过预处理后的图像，按其图像的行数构建一个长度与之相等的一维数组.对图像进行逐行扫描，若此行含有像素值为0的点，则将对应此行的数组元素值设置为0，否则为1.图3对应的纵切碎片经上述转换后提取出的匹配特征如图4所示.

图4 图片的匹配特征

某一页面被纵切成的19条文件碎片按如上方法提取出对应的匹配特征后，将每条碎片的特征与其余的18条碎片的特征进行比较，以寻找匹配的碎片，具体步骤为：

1) 为每条碎片i建立一个匹配数组number(i,19);

2) 碎片i与其余每条碎片j进行特征比较.如果两碎片相应位置的特征值相等，则进行umber(i, j) = number(i, j) + 1;

3) 找出碎片i的匹配数组number(i, 19)中的最大值number(i, k),则对应这个最大值number(i, k)的碎片k即为碎片i的匹配碎片.

从实验结果来看，在实验中出现了许多碎片与某一条碎片匹配度极高的情况.究其原因，是因为在碎片匹配特征提取的时候，仅考虑了碎片在一整行上的总体特征，忽略了每行左右切割边界处特征的相异性，提取的特征比较粗糙，所以造成了匹配效率较低的现象.

4 碎片匹配算法改进

为提高碎片的配准率，同时确保能够准确分辨出两碎片的左右关系，需要对上述匹配算法进行改进.在对碎片特征进行提取时，分别考虑每条碎片的左右边界特征，将每条碎片的右边界(最后一列)特征与其余碎片的左边界(第一列)特征进行对比，以此确定是否匹配，对应的算法流程如图5：

5 实验结果

我们将来自同一页面，内容为英文的19条纵切文件碎片(图6所示)进行随机编号，即000号-018号，对这些碎片建立拼接复原模型，并按如上算法进行了拼接实验，结果如下：

英文碎片拼接顺序编号：003，006，002，007，015，018，011，000，005，001，009，013，010，008，012，014，017，016，004.

经过与原文对比，上述实验结果完全正确.

文档碎片拼接复原技术是信息安全中的重要技术，它在警方获取证物及其他重要信息的获取等方面担负重要角色.鉴于文档碎片拼接复原技术的重要性，世界上已经开展了相关研究，但能够查阅到的资料相对比较少.目前在文档碎片拼接方面主要使用曲线的特征来进行碎片拼接，计算量非常大.本文在借鉴基于曲线特征的碎片匹配相关技术的基础上提出了对沿文字方向纵向规则切开的碎片拼接方法.最后通过实验对本人提出的算法和方法进行了验证.实验结果说明，该方法具有简单、方便、快速、高效的特点.

但本文在许多方面仍有待进一步研究，主要包括以下几点：

1) 本文提出的文档碎片拼接技术面向的对象过于理想化，应用的领域有局限性.

2) 本算法仅适用于单面规则纵切的碎片的拼接复原，对于纵横切碎的文档碎片，以及双面纵横切碎的文档碎片在拼接时需要考虑的因素较为复杂，其拼接复原算法还有待研究.

图5 碎片匹配算法流程

图6 英文纵切碎片

图7 碎片拼接结果

[1] LEITAO H C G, STOLFI J.A Multiscale Method for the Reassembly of Two-Dimensional Fagmented Ojects[J].IEEE Trans Patt Anal Machine Intell,2002,24(9):1239-1251.

[2] WOLFSON H J. On Curve Matching[J].IEEE Transactions on Pattern Analysis and Machine Intelligence.1990,12(5):483-489.

[3] SHAN Ying, ZHANG Zhengyou.New Measurements and Corner-Guidance for Curve Matching with Probabilistic Relaxation[J].International journal of Computer Vision.2002,46(2):157-171.

[4] ZHU Liangjia, ZHOU Zongtan, HU Dewen.Globally Consistent Reconstruction of Ripped-Up Documents[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2008,30(1):1-13.

[5] 朱延娟,周来水,张丽艳,等.基于Hausdorff距离的多尺度轮廓匹配算法[J].中国机械工程,2004,15(17):1553-1561.

[6] 罗智中.基于文字特征的文档碎纸片半自动拼接[J].计算机工程与应用,2012,48(5):207-210.