基于相似度分析的碎纸片拼接复原

孙鹏程+耿大猛+常晶晶+王玲

摘 要：现实生活中，传统拼接复原工作需要手动拼接，虽准确度较高，但拼接难度较大，效率较低，特别是当碎片的数量极大时，人工手动拼接工作将很难在短时间内完成。基于上述背景，该文利用matlab软件，对碎纸片二值化矩阵中的边缘矩阵进行提取，为减少拼接工作量，该文通过观察并计算出文档中最左端碎片的排列方式，最后应用统计学中的相关系数最大的条件找到最左端碎片的最佳匹配行，并以此方法完成拼接，得到的拼接结果较为完整，证明方法拼接效果良好。

关键词：图像识别 二值化 相关系数 边缘矩阵

中图分类号：TP301 文献标识码：A 文章编号：1672-3791（2017）01（b）-0040-02

传统人手撕碎片总是无规则的，其拼接一般是利用基于碎片几何特征的方法，但这种方法对边缘规则的碎片的拼接效果不是很理想，该文针对目前碎片拼接领域存在的这种不足，进行完善并设计了拼接边缘规则碎片的方法。

该文利用研究出的拼接边缘规则碎片的方法，解决2013年数学建模国赛B题的碎片拼接问题，对附件中给出的209张横纵切中英文碎片进行二值化处理，然后对得到的边缘矩阵进行相关分析，依据相关性分析完成最终的拼接。

1 图像处理及分析

灰度变换指黑白图片的黑白变换或者彩色图片的色彩变换，一张彩色图片的像素矩阵中的每个像素由RGB 3种颜色按照规定比例混合而成的一种颜色表示，在处理图像时，RGB会由于环境光源太暗而偏小，造成图像不清晰，若光源太亮，则会导致图像曝光率太高而泛白，该文通过灰度变换方法，将RGB值调到合适的程度。灰度RGB的范围是0～255，表示亮度从深到浅，对应图像中的颜色从黑到白。该文运用matlab软件对209张碎纸片分别进行灰度处理。

2 相似度分析

二值化处理是指通过对灰度变换后的图像设定阈值而将RGB灰度值分为两部分，并分别用0、1表示，最终得到二值化矩阵的方法。该文通过对209张既横切又纵切的碎片进行二值化处理，得到每张碎片的上下左右边缘矩阵，通过matlab编程对边缘矩阵的数值进行获取，若碎片中的文字被横切或纵切，利用统计方法对所有碎片的上下、左右边缘矩阵分别进行相关性分析，并计算出两边缘矩阵的相关系数，计算顺序为从上到下或从左到右，选取其中相关系数最大的两张碎片即为能够互相匹配的碎片，计算方法为，例如：中文碎片049、054、065、143、186、002、057能够拼接在同在一行，碎片左右边缘相关系数为0.921 4、0.894 7、0.912 3、0.945 3、0.856 8、0.883 6，经观察比较，上述相关系数均为同比系数中最大。图1、2为两张完成拼接的碎片，观察其拼接之后的“断”“a”，可发现其边缘矩阵的相似性。

3 确定文档首列

首先进行首列的选取，由于第一列每张碎片左边缘矩阵中空白行列数为一固定值，据此条件在209张碎片中选取出第一列中的11张碎片，具体操作方案为：通过matlab编程确定出每张碎片的二值化矩阵，并对这些数据进行筛选，统计出209张碎片中的左边缘空白矩阵的个数，得出众数为中文11个，英文14个，其中左边缘矩阵个数恰为众数的碎片即为备选碎片，最后通过人工干预选出第一列中的11张碎片；其次对选出的11张碎片进行排列，对于材料中的中文碎片，可分析每个汉字纵向最大占有距离为40个像素点，中文行间距最大占有距离为30个像素点，如图3所示，然后将第一列的碎片分为两类：一类是横向切割处为汉字；另一类是横向切割处为空白行。对于第一类，拟采用相关系数法进行拼接，进行纵向排序；对于第二类碎片的拼接方法，根据两相邻行字符之间空白最大占有距离为30个像素点的条件，用matlab进行分析计算得到与待匹配碎片匹配度最高的碎片。对于材料中的英文碎片，由于每个英文字母大小不一，故将其放入四线三格中表示，并发现所有英文字母均占满四线三格中的第二格，据此观察二值化矩阵中，四线三格的中间行所占最大像素点行数为25，由此确定四线三格的具体分布，如图4所示，任意一个英文图片碎片，通过matlab从文档上边界进行数值捕捉，当出现任意25行像素矩阵数值之和最小时就可以确定出此时对应的这25行中最上边的一行就是虚拟四线三格中的第2行，具体实现公式为：，经测算，相邻两个四线三格中间行最大垂直距离为40个像素点，然后再将拼接的碎片进行同样的分类，对于横向切割处为空白行的碎片，利用相邻两四线三格中间行的行间距为40个像素点的条件，应用matlab进行分析计算，得到相配碎片，并综合所有碎片数据，最终得出第一列英文碎片的排列结果。

另外，中英文第一列纵向匹配若出现一行或多行无字情况，需自行人工干预，按照原始参数，对所有无字行进行假设添字。对于添字处理后的中文碎片，依旧根据两相邻字符之间的行间距为30个像素点的条件，找到其最佳匹配碎片，完成纵向拼接。对于英文碎片的空白行，该文仅对英文字母四线三格中的中间格进行添字处理，根据相邻两个四线三格中间行垂直距离为40个像素点的条件，找到最佳匹配碎片，完成拼接。

4 所有纸片的拼接复原

对于已确定的第一列的碎片，需要对每一个分别进行横向排列，分析全部碎片二值化矩阵信息，提取所有碎片的左右边缘矩阵。以第一列的每一个碎片为起点，依旧利用统计学中的相关系数计算方法，从左向右进行计算，通过筛选找出与每个碎片的右边缘矩阵相关系数最大的矩阵，并将其还原为碎片，此碎片即为最佳匹配者。依据此法，完成对全文拼接。

5 结论与分析

该文对图像边界及其文字进行研究，提出了一种基于相似度分析对碎纸片进行拼接复原的方法，该方法利用matlab软件对二值化图像的边缘矩阵进行了比较，并利用边缘矩阵的相关系数，找到最佳匹配者，最终完成题材中的碎片拼接难题。该方法减少了大量人工干预，实现简单，不依赖于碎片的几何特征，可靠性比较好，在司法物证复原、历史文献修复以及军事情报获取方面有显著作用。

参考文献

[1] 房然然.二维碎片自动拼接技术研究[D].山东師范大学，2015.

[2] 庄俊东.基于数字图像处理的人民币碎片拼接方法的研究[D].上海交通大学，2010.

[3] 刘赐德，苗楠茜，常清，等.改进的规则碎片拼接复原算法[J].南阳师范学院学报，2014（3）：22-24.