基于0-1边缘灰度匹配的英文碎纸片复原

赵静文 马毓华 张新雨 王淑萍 郭珈珲

【摘 要】破碎文件拼接复原在许多领域内有着极为重要的应用，成为新的“黑科技”。为代替古老的人工复原方法，尝试实现机器化操作提高复原效率，本文基于碎纸片边缘灰度向量（矩阵）的匹配度计算进行拼接复原。对双面英文纸片纵、横切的情况，首先仍采用k均值聚类算法进行聚类，将处在同一行的正反两面碎片划为一类，其次利用镜像原理处理得到新型碎片，对新型碎片采用0-1边缘灰度匹配完成横向拼接，然后基于0-1灰度值匹配度的基础上，利用特殊化的TSP复原优化模型优化纵向拼接，从而使碎图复原。

【关键词】0-1两值化处理;匹配度K均值聚类;灰度垂直投影;镜像原理 一、背景提出

破碎文件的拼接复原技术在应用层面起着极为重要的作用，不管是司法物证、历史文献修复或者是军事情报获取等都扮演着重要角色。在以往，复原工作往往由人工来完成，虽然说人工复原文件准确率较高，但效率很低。尤其在文件被严重破碎分割的情况下，短时间内想通过人工来复原，更是难上加难。伴随现代技术发展，本文试论述切割后碎片的复原方法。

二、实现过程

（一）预处理

通过观察被切割的双面英文碎纸片图片可知，碎纸片之间的切割长度一致，并且碎片正反面的英文字母是在相同的位置上。因此可利用此现象进行聚类分析，将处在同一行的英文碎片的正反面划分到一类，从而简化对比的复杂度。

（二）碎片的聚类以及镜像处理

1.碎片的聚类分析模型

首先对双面英文碎片进行划分，由于英文字符是完全按照四线三格印刷的，所以首先定义a为英文四线三格中间一格的宽度，由于a为常量，故通过MATLAB可以求出a的确定值;其次通过MATLAB将碎片全部导入，求出碎片的灰度图像的水平投影，根据投影图像的特征，可以观察出英文的四线三格的每一条线都会对应一个图像峰值，取较明显的峰值与峰值之间的间距;然后令Wi为峰值间距极度接近a的条形块的位置，此位置便为四线三格的中间一格位置。最后通过k均值聚类算法依据Wi来划分碎片。k均值聚类算法是一种多次选择迭代的分类算法，所以能够最大程度的完成划分。

2.聚类的人工干预

理想的划分结果是将416个碎片划分聚类划分为11组，但是MATLAB实际操作起来并达不到这么高的准确度，所以此处需要加入人工干预。根据MATLAB的实际分组来找出不应该出现的组别和不应该出现在某一组的其他碎片，通过肉眼的观察来尽可能的分成11个组，每一组19个碎片。

3.碎片的鏡像化处理模型

由聚类划分得到的碎片虽都是同一行的，但是其中包括正反a，b两面的碎片，所以组内拼接时仍需要匹配很多次，这样会大大降低碎片的复原准确率。据此，提出镜像化处理优化模型，根据观察以及空间立体特征可得出，从碎片的正面看到的反面，其实是反面的镜像，故据此将一张碎片的反面镜像提取到正面上。

对于一张双面英文碎片，现无法确定正反面，故需讨论两种情况，一种是000a为正面，那么把000b作为反面，将其镜像附在000a下方;另一种是000b为正面，那么把000a作为反面，将其镜像附在000b下方，即可得到两种新的碎片。

（三）TSP复原优化算法

由初步的复原效果，可以发现纵向拼接时会因为边缘没有字母的切割点而造成拼接困难，基于此，提出TSP复原优化模型。此模型的原型是旅行商问题，在某种限定下，求得optimization解，使得总路径最短。本题利用此算法来优化0-1灰度值匹配复原模型，使得那些边缘没有切割点的片段找到最佳匹配，具体算法如下：

（四）碎片复原过程

1.按聚类横向复原

把经过处理的碎片，通过MATLAB重新读入，可以得出新碎片的边缘灰度矩阵，然后将其根据灰度值的阈值来0-1化，最终得到灰度0-1矩阵。仍先根据碎片最左侧的灰度分布值的特点，利用算法找出最左侧的碎片，根据匹配度依次寻找能与前一碎片的右侧边缘匹配度最高的碎片进行逐个拼接。

在拼接时，我们是抽象出了一个量——匹配度，来衡量碎片是否相邻，由于此题中已经通过镜像法，在对图片进行匹配拼接时，同时考虑了正反两面的匹配度，不仅增大了检测的边缘长度，还一次性检验了两个面。大大的降低了失误率，所以当匹配度低于90%的时候检验就可以。其余地方的匹配则无需干预。

2.碎纸条的纵向复原

经过横向拼接好的碎纸条已经可以看得出正反面，我们只取正面的初步复原的图来进行纵向拼接，利用0-1化的灰度矩阵先把边缘有切割到字母的图拼接在一起，得到e个新的片段，这e个片段的上下边缘至少有一个边缘是空白的，然后根据提出的TSP复原优化模型来寻求e个片段的最优化匹配方式。

3.人工干预及复查

可再进行一步人工干预，看每个字母是否完整，最后阅读全文看是否是一篇完整的文章。

【参考文献】

[1]蔡志杰.碎纸片拼接复原的数学模型与方法[J].高等数学研究，2016（04）.

[2]陶佳琪，郑路通，杨雯雯，买阿丽，孙国伟.单页单面英文纵切横切碎片拼接复原算法[J].运城学院学报.2013（5）.

[3]碎纸片的拼接复原.

https：//blog.csdn.net/z1143709608/article/details/60139479.2017

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

[5]沈恒范.详解MATLAB数字图像处理[M].电子工业出版社，2010.

[6]张甜.Stata统计分析语行业应用案例详解[M].清华大学出版社，2014.

[7]汪晓银.周保平.数学建模与数学实验[M].北京：科学出版社，2012.

作者简介：赵静文（1999—），女，山东枣庄人，汉族，本科，单位：青岛理工大学，研究方向：数学与应用数学。