基于聚类分析的双面文档半自动拼接

梁慧超　于红斌　乔路遥　崔玉亮

摘 要：针对双面规格碎片，提出了一种基于聚类分析的半自动拼接方法。根据碎片边缘的文字特征，构造碎片的相似性判别函数，进行最大相似性判别并聚类分析，找到同一行的碎片排列，最终实现了文档的横向、纵向拼接，在MATLAB下的实验表明该算法效率高，相对人工干预少。

关键词：聚类分析；边缘特征提取；碎纸片拼接

碎纸片的人工拼接复工作效率很低，随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。目前，国内外在碎片拼接技术的研究中已经取得了一定的成就，如：Ying Shan等提出了一种概率框架的曲线匹配算法[1]，李军等人提出一种改进Harris算子的图像拼接方法[2]，何鹏飞等人提出了基于蚁群优化算法的碎片拼接技术[3]，但这些算法主要解决单面不规则碎片的轮廓提取及匹配上，对于碎片双面均有文字且碎片数量巨大的情况难以适用。

针对当前图像拼接技术的缺陷，本文充分利用文字行的行高、文字行的间距等信息，对碎片进行分类，并综合采用相似性判别函数和聚类分析，最终将同一行的碎片划为一类，拼接时利用碎纸片的边界矩阵，进行最小绝对值距离判别，从形状相似的多碎片中挑选出相邻碎片。该方法便于理解，利用MATLAB软件，容易实现。

1 拼接原理

碎片拼接由于碎片数目过多，故不能人为的进行全过程拼接。首先要将根据碎片特征利用相似性判别函数分进行分类，然后利用聚类分析将属于同一面同一行的碎片聚成一类，在人工筛选划错行的图片后，对碎纸片进行横向和纵向拼接即可。

聚类分析是一组将研究对象分为相对同质的群组的统计分析技术，其依据研究对象（样品或指标）的特征，对研究对象进行分类，达到减少研究对象的数目的目的。因为文档的行高、字间距具有一定规律性，因此可以依据每张碎片的特征，进行聚类分析。

2 拼接步骤

2.1 观察碎片特征

通过观察碎片，根据碎片中完整文字行数、完整空白行数，碎片上方是否为空白、碎片下方是否为空白等特征人工将碎片分为N类。以文献[5]中数据为例，a有3行完整文字、两行完整空白、上方为空白、下方为空白；b有两行完整文字、两行完整空白、碎片上方为空白、碎片下方不为空白；c有两行完整文字、两行完整空白、碎片上方不为空白、碎片下方为空白，这3张碎片分别属于3大类。

人为地将文档分为N类后，挑选出属于每一类的碎片一张作为比较对象，任意碎片Si的特征矢量，求每一个碎片在第i类碎片上的矢量与该矢量上的特征矢量的距离，进行最大相似性判别，为每一碎片分类。但由于文档的双面性，可能会存在差错，为了让位于同一面同一行的碎片聚在一起，在划分好的每一类中，提取各个碎片的反面进行聚类分析，将这些碎片分为m类后，仍需要人工将少数不属于该行的碎片划分开来。

2.2 相邻碎片拼接

若想要找出其左邻碎纸片，只需提取每个碎纸片像素矩阵最左边的一列和最右边的一列，记每个碎纸片的像素矩阵中的最左边一列为ιi，同理，提取每个碎纸片的最右边一列为ri，计算两碎片的相关程度时，可以用绝对值距离[3]表示，此时的目标函数即求下式的最小值：

其中，xik表示像素矩阵第k行的ιi的值，yik表示ri的第k行的值。当k从第1行取到第最后一行时，若此差值的绝对值和最小，则表示两个左右两个边缘的相似性越高，即可认为这两个矩阵是左右相邻的即可确定每个碎纸片左右相邻的碎纸片，从而获得横向同一行上各碎片的排列顺序，同理，用同样方法可获得纵向各行的排列顺序，从而得到拼接复原的完整图像。

3 拼接试验

根据该算法研制了MATLAB程序，并对一实际碎纸片进行了拼接试验。将碎纸片平均切割为418块，根据文字行的分布形式及空白行高人为的将碎纸片分为5类，用MATLAB中的相似度函数对418张碎片做相似处理并用SPSS对该矩阵做聚类分析，然后施加人工干预，将这些图片插入到正确的行类中，最后进行横向纵向拼接。拼接结果的部分图像见图2。

试验表明本文提出的半自动拼接算法误差率较小。

4 结束语

本文提出了基于聚类分析的双面文档碎片半自动拼接方法，实现简单，但只适用于横向、纵向切割的文档碎纸片的拼接，需要加入两次人工干预。

碎片文件的拼接在现实生活中有着广泛的应用，在司法物证复原、历史文献修复、军事情报获取、虚拟仿真培训、工业制造设计等领域，有一定的指导意义。

[参考文献]

[1]Ying Shan etc.New Measurements and Corner一Guidance for Curve Matching With Probabilistic Relaxation[J].International Journal of Computer Vision.2002，46（2）：157-171.

[2]李军，吴洁明.一种改进图像拼接算法的仿真研究[J].计算机仿真，2012，29（2）：273-313.

[3]何鹏飞.基于蚁群优化算法的碎纸拼接[D].国防科学技术大学，2005.

[4]程永清，庄永明，杨静宇.基于矩阵相似度的图像特征抽取和识别[J].计算机研究与发展，1992，14（5）：42-48.

[5]全國大学生数学建模（官网）.2013赛题：[DB/OL]，教育部高等教育司和中国工业与应用数学协会，2013[2013-9-11].http：//www.mcm.edu.cn/problem/2013/2013.html.

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