基于灰度矩阵的中文碎纸片的拼接复原算法

王欣洁

摘要：主要对碎纸片的拼接复原问题进行分析，分别对仅纵切和横纵切两种切割方式建立了模型进行求解，主要思想是对碎片的灰度值矩阵进行处理，利用文字所处的位置信息、空格的分布情况、碎片的边界信息（文字的链接情况）等信息，对所给的碎纸片进行拼接复原。对2013年“高教社杯”大学生数学建模竞赛B题附件中的中文碎片进行拼接，拼接效率高，算法可行。

关键词：灰度值矩阵； 差异度量； 贪心算法； 相容性； 边界特征

中图分类号：TP312 文献标识码：A文章编号：2095-2163（2013）06-0095-04

0问题提出

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。为了提高拼接复原效率，人们试图利用计算机，实现碎纸片的自动拼接。本文对2013高教社杯全国大学生数学建模竞赛B题中提出的碎纸片拼接复原问题进行研究，主要研究其中中文碎片的拼接复原。

1模型假设和符号说明

研究前，需要做出如下假设：假设所给碎片均无噪声污染；各碎片之间互有关联；并且只考虑打印稿，而不涉及手写稿；同时也要假设文件中的文字行间距确定；没有相同的两个碎片；以及附件所给碎片的原文件页边距不为零。

本文中用到的符号如下：

Ai：第i个碎片图像的灰度值矩阵；

aikm：第i个碎片图像的灰度值矩阵中第k行m列元素；

d（Ai，Aj）：两矩阵的列差异度；

N1：附件1、2碎片个数；

N2 ：附件3、4碎片个数；

F：复原序列；

d（r）（Ai，Aj）：两矩阵的行差异度；

S1R：排在左侧的第R张碎片；

GR：第R个相容的碎片集合

2问题分析

2.1仅纵切问题的分析

对于仅纵切的情形，各碎片的边界特征信息（文字的链接情况）较为丰富，故可以利用边界特征进行拼接复原。首先根据左侧的第一张碎片通常存在着左边的页边距的特点，即其灰度值矩阵中左边几列的元素均为255，从而可以找出排在左边的第一张碎片。对于仅纵切的规则图形的拼接问题，只需考虑横向连接，由于纵切产生的边界特征信息较多，在此引入相邻的两幅碎片的边界差异度量[1]。

定义1：设Ai和Aj均为r×l矩阵，aikm为矩阵Ai中第k行m列元素，ajkn为矩阵Aj中第k行n列元素，称

dm，n（Ai，Aj）=∑rk=1|aikm-ajkn|

为矩阵Ai第m列与Aj的第n列的差异度量，其中1≤k≤r，1≤m，n≤l。特殊地，用d（Ai，Aj）表示矩阵Ai最后一列与Aj的第1列的差异度量。

2.2横纵切问题的分析

对于纵横切的情形，在增加横切之后，两图片边界处共同信息量大大减少，故需要更进一步地挖掘可用信息。汉字是方块字，每个字所占的位置基本都是一致的，均可以填在一个“田”字格中。

首先找出排在左侧的11张图片，可以判定两碎片中汉字所在位置位于同一行的图片应该拼接在同一行中，将这样的碎片定义为相容的碎片，下面给出碎片相容性的定义。

定义2：如果两幅碎片上的汉字所在行的位置不矛盾时称为两幅碎片是相容的。

例如：图1中所给的七幅图片均为相容的，图中黑色部分为汉字所在的位置，其中汉字也可以是半个字。

在相容碎片的集合中，按照上小节中问题一的方法，找出列差异度量最小的排列，即可将每一类相容碎片进行横向拼接复原，然后还需要对碎片进行纵向拼接，如果横切时是从字中间切开的，则需要考虑碎片的灰度值矩阵的行差异度量。下面定义两矩阵的行差异度量。[2]

定义3：设Ai和Aj均为r×l矩阵，aimk为矩阵Ai中第m行k列元素，ajnk为矩阵Aj中第n行k列元素，称

d（r）m，n（Ai，Aj）=∑lk=1|aimk-ajnk|（1）

为矩阵Ai第m行与Aj的第n行的差异度量，其中1≤k≤r，1≤m，n≤l。特殊地，用d（r）（Ai，Aj）表示矩阵Ai最后一行与Aj的第1行的差异度量。

如果横切时是从空行之间切开的，则上下两个碎片的差异度量为0，则可能会出现拼接错误，这时可以在假设每行的行距相等的基础上，若计算得到一张碎片下边界的空白处在其相应的灰度值矩阵中所占的行数和另一张碎片上边界的空白处在其相应的灰度值矩阵中所占的行数之和恰好等于文字间因行距所形成的的空白处而构成的灰度值矩阵行数，则这两张碎片即为上下拼接[3]。

3模型建立与求解

3.1仅纵切的模型建立与求解

如果两个碎片的列差异度越小，说明这两块碎片拼接在一起的可能性就越大，建立基于矩阵列边缘差异度的碎片复原模型，目标函数为寻找所有碎片全排列中边缘的列差异度和的最小值， 其公式为：

min f=∑N1-1i=1d（Aki，Aki+1）（2）

式中，k1，…，ki，ki+1，…，kN1为1，…，i，i+1，…，N1的全排列，由最小值对应的排列可以得到拼接序列[4]。

文中利用贪心算法[5]求解上述问题，具体算法过程如下：

算法1：

（1）将附件碎片文件用imread命令导入MATLAB中，生成N1个r×l的灰度值矩阵Ai，存储于1×N1的元胞cell中，cell={datal，…，datai}，每个Ai中的元素aikm存储在元胞内的数组datai中；

（2）对每个Ai的左侧的4列灰度值进行按列求和，找出最大值的碎片，即为排在最左侧的第一张碎片，记录其灰度值矩阵为A1，同时记录位置并保存于向量sorts中[6]；

（3）根据定义1，在其余Ai中找出与A1的列差异度量最大的灰度值矩阵，记为A2，则A2应与A1拼接；并把矩阵A1与A2按行连接，存入数组dataall中，再将其位置添加入向量sorts中；

（4）从A2出发重复步骤（3），依次找出A3，A4，…，AN1；

（5）输出F即为碎片复原顺序；

（6）将灰度值矩阵（dataall）转化为复原图片，并输出到当前MATLAB工作目录中。

利用MATLAB7.0对算法1编程求解[4，6-8]，其中N1=19，r=1 980，l=72，i，j=1，2，… 19，m=72，n=1，经调试可知，最左边第一张碎片灰度值矩阵中左边8列元素均为255，将2013高教社杯全国大学生数学建模竞赛B题中附件1中的图片存入MATLAB当前工作目录，即可输出碎片复原顺序如表1所示。因篇幅所限，复原图片本文并未列出。

表1附件1碎片复原顺序

3.2横纵切模型的建立与求解

由问题分析可知，对于纵横切片的情形，建立基于相容性的碎片复原模型[9]，目标函数为寻找所有碎片全排列中边缘的列差异度和的最小值[2，9]，如同式（2），利用贪心算法求解上述问题，具体算法过程如下：

算法2：

（1）将附件碎片文件导入MATLAB中，生成N2个r×l的灰度值矩阵Ai，存储于1×N2的元胞中；

（2）在N2个灰度值矩阵Ai中寻找左侧几列灰度值均为255的碎片，即为排在左侧的R张碎片：S11，S12，…，S1R；

（3）对S11，寻找与之相容的碎片，放入一个集合G1中；

（4）重复步骤（3），依次寻找分别与S12，…， S1R相容的碎片，也按序放入集合G2，…，GR中；

（5）在G1中，利用算法1的步骤（3），从S11出发，寻找差异度量最小的排列，并保存此排列的灰度值矩阵，且输出；

（6）从G2出发到GR，重复步骤（5）；

（7）按照定义3计算G1复原图与G2到GR复原图的灰度值矩阵的行差异度量，同时寻找行差异度量最小的排列，并保存此排列的灰度值矩阵；

（8）将灰度值矩阵转化为复原图片，并输出到当前MATLAB工作目录中。

利用MATLAB7.0对算法2编写程序求解，其中R=11，L=19，N2=209，r=180，l=72，i，j=1，2，…，R，m=180，n=1，将2013高教社杯全国大学生数学建模竞赛B题中附件3中的图片存入MATLAB当前工作目录，运行程序，首先输出排在左侧的11张碎片序号，如表3所示。表3附件3中排在左侧的11张碎片序号

4模型评价

4.1模型的优点

在模型一中将各碎片数字化产生相应的灰度值矩阵，作为处理对象，定义两矩阵列差异度量，作为衡量拼接是否合理的标准，目标函数简单明了，便于理解，且同时具有较高的准确度；在模型二中巧妙运用汉字文字及排版特征，定义了相容集合和两矩阵行差异度量，作为衡量拼接是否合理的标准，利用文字的位置、空格位置、文字在边缘处的链接情况进行还原。此模型可以有效解决纵横切的大量碎片拼接复原的实际问题；

4.2模型的缺点

在模型一中的灰度值矩阵中，只考虑了边缘列向量或行向量，却未有效利用碎片数据；在模型二中只考虑打印版的汉字文件，不能较为有效地处理手写体文件和英文文件碎片拼接问题。

这些模型中只用边界的空格信息、文字的位置、文字在边缘处的链接情况。另外，由于不同字体的结构不同，所以此算法只适用于中文碎片的拼接复原，对于更加复杂的还原问题，则需要考虑更多的信息。

参考文献：

[1]沈庭芝，方子文.数字图像处理及模式识别[M].北京：北京理工大学出版社，1998-06

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

[3]何鹏飞， 周宗潭，胡德文. 基于蚁群优化算法的碎纸拼接[J].计算机工程与科学，2011（7）：67-73.

[4]苏金鹏，阮沈勇.MATLAB实用教程[M].北京：电子工业出版社 ，2005-07

[5]姜启源，谢金星，叶俊. 数学模型（第四版）[M]. 北京：高等教育出版社，2011-01.

[6]于殿泓. 图像检测与处理技术[M].西安：西安电子科技大学出版，2006-12.

[7]杨淑莹，李兰友. 图像模式识别—VC++技术实现[M].北京：清华大学出版社，2005-07.

[8]任玉杰. 数值分析及其MATLAB实现[M].北京：高等教育出版社，2007-03.

[9]贾海燕.碎纸自动拼接关键技术研究[D].国防科技大学硕士论文，2005-11.