基于矩阵边缘特征向量比较法的碎纸片拼接复原

温跃飞

摘 要 对于采用纵横切割，边缘几何特征几乎相同的碎片，我们采用矩阵边缘列向量的相似性来进行两两匹配，在出现无法正确匹配时进行必要的人工干预，最终实现碎片的拼接复原。由于平时的切割不可能全部都是纵向切割，所以将横纵切割的单面和双面的碎片转换成纵向切割进行拼接。

关键词 边缘特征向量 穷举法 灰色关联分析 文字行特征 人工干预

中图分类号：TP391 文献标识码：A

0引言

破碎文件的复原工作在司法物证复原，历史文献的修复和军事情报的获取等领域都具有重要的意义，传统的人工修复虽然准确率高，但是效率很低，特别是在纸片的数量较多，破碎程度较大的情况下，光靠人工复原可能很难再短时间内完成拼接工作，这样就会影响物证复原，文献修复和情报获取的进度。是否可以在计算机的帮助下，试着对碎纸片进行拼接，从而加快人工复原的速度，提高复原的效率。平面碎片匹配复原技术的研究有着重要的理论和现实意义，己成为模式识别、计算机视觉等领域的重要研究课题。本文采用计算机编程和人工干预的方法实现对横纵切割碎纸片的拼接。

1纵向切割碎纸片的拼接复原模型

1.1模型流程图

1.2获取数据

将碎片的文件导入到MATLAB，由软件读取出每张图片文件的像素信息，并且这些信息可以由MATLAB转换为一个数字矩阵。

程序语句：

Imread（‘图片路径＼*.bmp）

通过MATLAB处理得到的数字矩阵可以得到每个矩阵的边缘特征向量，之后可以利用得到的边缘特征向量进行两两比较。

1.3数据预处理和模型的建立

由MATLAB得到数字矩阵之后，选取数字矩阵的左右边缘向量L，R，向量里的数字“0”代表图片中黑色的点，“255”代表图片中白色的点，介于“0”和“255”之间的数字代表图片中灰色的点。可以比较任意一张图片的右边和其余每张图片的左边，如果两张图片是相邻的图片，那么左边图片的右边缘所表示的向量R和右边图片的左边缘所表示的向量L应该是相关联的，同样的，如果两张图片不是相邻的，那么右边缘和左边缘应该是不能匹配的，也就是说是不关联的，这样就可以筛选出两张相邻的图片。在此模型中，在进行拼接之前进行人工干预，通过观察碎片的边缘留白的距离，字体边缘的整齐程度以及图片上内容，可以确定出哪张图片为完整图片中的最左边的纵切碎片。

在确定了最左边的纵切碎片之后，通过MATLAB读取该碎片的像素数字矩阵的右边缘特征向量R0，并和剩下的图片的左边缘特征向量进行比较，选出能够匹配的那张图片（设为R1），接着再比较1图片的右边缘向量R1和剩下图片的左边缘向量，再次选出能够匹配的那张图片，以此类推，可以将所有图片都匹配出来，即完成了拼接的工作。

2横纵切割单面碎纸片的拼接复原模型

通过对数据矩阵的观察可以看出，如果两个片段是属于同一行的，那么它们的图案中从最上方开始往下检测，第一次出现全部都是白色像素值255的数字矩阵中的行数应该是相同的。

上图是两张碎片图片，从他们的部分数字矩阵可以看出他们出现第一个一行全部都是白色像素点的行的行数h是相同的，都是在“上”字和“风”字的最下沿。说明这两张图片有很大的可能是在同一行的，剩下的图片可以采用同样的方法进行分类。

每张图片转换成数字矩阵之后，如果其中某一行的数字全部都是255，那么说明原图片中这一行全部都是白色，即说明这一行没有汉字或字母。每张图片转换成数字矩阵之后，矩阵的每行有72个数字，我们定义为，当一行全部都是255时，即=18360，然后计算代表每张图片的数字矩阵中第一次出现总和为18360的行数h，其中如果有行数h相同的，那么基本上可以确定它们是属于一行的。

那么此时就可以得到N个类，每个类当中都有M个片段，而这M个片段都是在一行的，这M个片段可以看成是把一个横行作为整体的图片纵切后得到碎片，这就回归到了纵向的问题，可以利用纵向中的模型将每一类中的M个片段复原成一个横行的整体。复原完成后的N个完整的横行，将这N个完整的横行旋转90度得到新的N个完整的纵行，又可以看成这N个片段是由一个整体纵切得到的，再次回归到纵向切割问题，利用纵向切割的模型可以将最后的N个片段复原，得到原本完整的图片。

3横纵切割双面碎纸片的拼接复原模型

由于一般正反两面切割问题中的碎纸片数量庞发，也信息量较复杂。首先，无法确定在这些碎片中哪些是属于正面的，哪些是属于反面的，这样就不能直接用横纵切割问题所才用的先分类的方法了，因为如果直接对行进行分类的话，很有可能将正反两面的一行分到了一起，这样仍然无法将属于同一行的碎片分类出来，所以只能先从整体出发，用人工干预找出一些明显属于最边缘的碎片。当找到了一定数量的最边缘碎片的时候就能利用灰色关联分析法对与最边缘碎片相关联的碎片进行筛选了。

3.1利用灰色关联分析法对最边缘附近的碎片进行筛选

灰色关联分析法可对样本数据量较小的系统进行综合分析，且计算量很小。但这种方法中的某些参数如指标权重和分辨系数需要人为指定。必要时，可将上述几种综合评价与决策方法结合起来使用。比如，可先用层次分析法确定指标权重，然后再用灰色关联分析法，可取得精度较高的结果。

根据灰色关联分析，可以在剩下的碎片中找出跟边缘碎片关联度最大的碎片，剩下的碎片都可以用这样的方法进行拼接。可以利用灰色关联分析法找出一些行或者列的片段，这样在之后的拼接中就可以运用横纵切割问题中的模型了。

3.2拼接实验

经过灰色关联分析的处理之后已经得到了一些行或者列的片段，这样其实就将正反两面切割问题转化为了横纵切割问题中的问题，在找到行（或列）的片段之后，就將这些行（或列）的片段作为一个大类，将每个大类进行旋转，得到纵列（若得到的是列就不用旋转了），得到纵列后就转化为纵向切割问题了，那么利用程序一就可以将纵列复原拼接了。

这样就可以正确复原正反两面中的一面，那么另一面也就正确的复原了。

4总结

采用MATLAB读取图片像素信息的方法，可以很好的保持图片原有的信息，同时能够准确的将图片的信息以矩阵的形式反映给读者，有较强的实用性。另外，用矩阵的形式来表达也有利于采用边缘边缘特征向量比较的方法。

在考虑横纵切割问题的时候充分利用纵向切割问题所建立的模型，通过将原本横纵切割的碎纸片先进行横行的拼接，使其转换成N个大类，再将得到的横向的片段旋转90度得到转换成纵向的片段，利用纵向切割的模型来解决。节约了重新编写对应横纵切割问题的程序的时间，同时也充分的利用了两个问题之间的连贯性，以纵向切割为基础，利用已经得到的结论来解决更加困难的问题。

参考文献

[1] 马艳， 张治辉（著）.种边缘检测算子的比较.工矿自动化出版社，2004.1：54～P55.

[2] 贾海燕，朱良家，周宗潭，胡德文（著）.一种碎纸自动拼接中的形状匹配方法[J]. 计算机仿真，2006.3：66.

[3] 孙文方，赵亦工. 基于有限Radon变换的图像纹理方向的检测. 计算机应用，2005.25（z1）.