条状碎片文件自动复原的探讨与研究

刘俊玮 王子豪 宋嵩焘

【摘要】破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.有关碎片文件复原的研究已很多，而本文提出的条状碎片文件复原无法用几何形状的方法，文中通过提取碎片剪裁边缘的像素特征，构建了基于其灰度值的相似指标，并针对汉字与英文的不同特点，建立了普适较高的碎片复原数学模型，设计了相应的算法，完成了对不同碎片的半自主拼接.

【关键词】条状碎片；文件复原；灰度；像素匹配

一、引 言

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统上，拼接复原工作需由人工完成，准确率较高，但效率很低.特别是当碎片数量巨大，人工拼接很难在短时间内完成任务.随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率.但由于目前计算机数字分析图像能力的限制，让计算机对碎片进行完全意义上的自动化拼接也几乎不太可能.在以往的碎片文件复原中，由于碎片形状都是不规则的，所以可以按几何形状匹配的方法使文件复原.在本文中对于条状碎片文件复原问题，由于对应的是规则碎片，无法采用常用的几何形状匹配的方法，笔者通过改进只能用于规则碎片的zhegean复原方法，应用于条状碎片的匹配，通过采集碎片剪裁边的像素点信息，建立一维匹配数学模型.由于单一条状碎片能够提供足够多的匹配信息，利用该模型，无须进行人为调整即可达到条状碎片的完美拼接.

二、问题提出

对于给定的来自同一页印刷文字仅纵切的碎纸片，并假定：

（1）剪裁后的碎片在边缘处无像素损失；

（2）碎片不存在倒置或侧置的拼接情况；

（3）所提供碎片能够拼凑为完整文段，不存在错误碎片.

由于碎纸片均为条状碎片或大小相同、形状规则的矩形块状，因此无法采用典型的基于碎片边缘几何特征的拼接方法，也无法使用基于强大数据库文字识别算法，只能依据图形的像素分布特征进行匹配.因此，本文依据图像边缘每一像素点的灰度值构建匹配向量，引入相似性指标，并建立像素点灰度匹配机制，同时辅以人工调整，最终完成匹配.

三、模型的建立与求解

任意一张图片都相当于是由一个个像素平铺构成的面，因此在碎片的边缘分布着这样一列像素点，它记录了剪裁边缘每一点的灰度值.若两张碎片是相邻的，当有文字在剪裁边缘被截断时，其中一张碎片的左边缘与另一张碎片的右边缘在对应的同一个像素点处的灰度值应该十分接近，即当有一黑色“横”被截断时，边缘将有一系列像素点的灰度值均为0，因此也应有另一碎片在对应位置有一列像素点的灰度值为0去与之匹配，从而补全这一“横”.

而在问题的假设中是针对完成条状碎片的拼接，因而无须考虑上下边缘的像素特征，而由于条状碎片的左右边缘较长，像素点分布较多，而不能匹配的任意两块碎片在左右边缘处的像素应该是差异明显的，只需通过灰度值构建匹配向量，比较像素点灰度值相似程度，即可完成匹配.

1.像素点灰度值相似性指标的构建

对于一张编号为i，由m×n个像素组成的碎片，取其边缘每个像素点的灰度值r1，r2，…，rk（其中k=m，n），将其构建为一匹配向量：

Ri=（r1，r2，…，rk）.1

图1 匹配向量位置示意图选取编号分别为i和j的两块碎片，在相同长度的剪裁处分别有各自像素点灰度值的匹配向量Ri和Rj，如图1所示.

由于相邻碎片在剪裁边缘匹配向量近乎相同，为对比任意两块碎片边缘处像素的相似程度，基于Euclidean距离，构造像素灰度相似评价指标：

fij=-∑ni，j=1

i≠j（Ri-Rj）2.2

图2 任意碎片相似程度计算示意图fij越大表明相似程度越高，Ri与Rj各个元素间越接近，即各个像素点灰度值越接近，从而说明两块碎片越有可能相邻.由此可计算出任意一块碎片左右两个边缘f1、 f2与其他碎片某一边的相似程度，如图2所示.

最终可以得到任意两块碎片间的相似程度，并得到相似矩阵：

F=f1，2…f1，n

fn-1…fn，n-1 .3

2.像素点灰度值的一维匹配模型的建立

令集合为复原前的碎片集合，并规定：

titj=1，ti与tj相邻

0，ti与tj不相邻4

从而建立一维像素灰度值匹配的规划模型，即：

max a=∑fij

s.t. ti，tj∈S 5

titj=1

一维像素灰度匹配算法中，首先构造像素灰度值构成的向量，然后计算两向量间的距离，距离越小则说明两张碎片越有可能匹配，公式2中的距离fij表示两个碎片相邻像素点的灰度差，公式2是用来衡量整个剪裁边缘的整体差异的.

（1）扫描读取条状碎片左右列边缘的灰度值，并记录得到匹配向量R=（r1，r2，…，rm），并确定起始碎片；

（2）记最后归入的纸片为ti，遍历所有的fij，tjS，选择使fij的纸片tmax，令tmax∈S，使其排在ti的左侧；

（3）重复（2），直至所有ti都属于S；

（4）判断结果是否正确.若正确，算法结束；否则，返回发生错误的节点进行人工干预后继续进行.

四、实验结果

实验材料用一个页面的汉字纸质材料，从纵向裁剪为成18条长条碎片，并给予随机编号，部分汉字碎片如图3（a）所示.同理英文纸质材料，也从纵向裁剪为成18条长条碎片，并给予随机编号，部分英文碎片如图3（b）所示.分别把汉字与英文字母的条形碎片通过扫描后形成图像文件，然后根据所建立的像素点灰度值的一维匹配模型公式5，应用Matlab程序分别进行求解，求解的最后结果是根据模型计算出各碎片复原后的编号排列.图4、图5所示分别是复原后汉字碎片图像与英文碎片图像.

图3 复原前的汉字碎片图像及英文碎片图图4 复原后的汉字图像五、结 论

文中针对条状碎纸的文件复原进行研究，由于条状碎纸的复原无法采用几何形状的图像特征算法，而对于规则碎片而言只能通过采集碎片剪裁边的像素点信息，建立一维像素灰度匹配碎纸片拼接复原数学模型，并针对给出的中、英文各一页文件的碎片数据进行拼接复原.由于单一条状碎片能够提供足够多的匹配信息，利用该模型，无须进行人为调整即可达到条状碎片的完美拼接，这表明本文设计的算法是切实可行的.

图5 复原后的英文图像

【参考文献】

[1]樊少荣，周明全，姬利艳.考古文物的数字化过程研究[J].微机发展，2004，12：21-23.

[2]李春龙，周明全，成欣.轴对称破碎文物的虚拟复原方法[J].计算机辅助设计与图形学学报，2006，5：620-624.

[3]王辉，吴钦章.基于图像质量评价的自动图像复原技术[J].传感技术学报，2012， 25（7）：930- 935.

[4]方帅，王勇，曹洋等.单幅雾天图像复原[J].电子学报，2010， 38（10）：2279-2284.

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

[6]Mark M.Meershchaert.Mathematical Modeling （Third Edition）.北京：机械工业出版社，2010.

[7]刘金根，吴志鹏.一种基于特征区域分割的图像拼接算法[J].西安电子科技大学学报，2002（6）： 768-771.

[8]罗智中.基于线段扫描的碎纸片边界检测算法研究[J].仪器仪表学报，2011（2）：289-294.

[9]Elsasser B，Hoschek J.Approximation of digitized points by surfaces of revolution [J].Computers & Graphics，1996，20（1）：85-94.

[10]Calio F，Moroni G，Rasella M.A particular class of soline in reconstruction of revolution surfaces from 3D data measured by CMM[J].Robotics and Computer Integrated Manufacturing， 2003， 19（1/2）：219-224.