碎纸片的拼接复原模型及其算法研究

姚光督，沈景凤，王文东，滕 泉

(1.上海理工大学 机械工程学院，上海 200093；2.上海材料研究所，上海 200437)

碎纸片的拼接复原模型及其算法研究

姚光督1，沈景凤1，王文东2，滕 泉1

(1.上海理工大学 机械工程学院，上海 200093；2.上海材料研究所，上海 200437)

针对目前司法物证复原、历史文献修复以及军事情报获取等领域就如何快速高效的对破碎纸片进行修复的问题。利用Matlab算法对碎纸片进行处理并得出其灰度矩阵，再通过分析矩阵间的关系，利用Matlab编程并建立数学模型，对具有轮廓形状规则、字符颜色相同、字符间距和行间距相同的碎纸片进行自动拼接复原。在此模型和算法的基础上，加入对不同字符的识别技术，能有效减少拼接错误的概率以及拼接过程中的人工干预，进一步提高碎纸片拼接复原的效率，在碎纸片拼接复原的研究中具有一定的创新性。

破碎文件的拼接；灰度矩阵；Matlab编程；字符识别技术

常规碎纸片拼接复原方法一般利用碎片边缘的尖点特征、尖角特征、面积特征等几何特征，搜索与之匹配的相邻碎纸片并进行拼接，这种基于边界几何特征的拼接方法并不适用于边缘形状相似的碎纸片，当然也不适用解决通过破碎机破碎纸片的拼接与复原问题。因此，对这类边缘相似的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，即拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎片内的字迹断线或碎片内的文字内容是否匹配。本文以2013年全国大学生数学建模竞赛B题为数据来源，模型假设：(1)假设碎纸机切割的小碎片的大小相同且形状规则；(2)假设文件被切割后的所有碎纸片均齐全；(3)假设碎纸片正反两面的内容有差异；(4)假设碎纸片没有材质以及颜色方面的差异。利用现有的技术，完全可以获取碎片文字图片的数字信息，拼接碎片时利用这些信息并适时结合人工干预进行拼接，就能在保证准确率较高的前提下，提高拼接复原的效率。

1 问题分析

由于题目中所给的图片不存在破损，经碎纸机切割后，扫描入计算机的文件可近似成矩形，因此可将图片导入Matlab处理，得出其灰度矩阵，以此来表示碎纸片中字的位置以及分布。观察第一张纸条左边沿有较多的空白边，因此在灰度矩阵中挑选出第1列全等于255的矩阵的则为第一张纸条。与此相对应，原来相对应的两张纸片A、B对应的灰度矩阵a的最右列和灰度矩阵b的最左列是可以完全吻合的。采用此两列的差的平方和作为相似度判定依据，从后18个灰度矩阵的第一列依次与第一张纸片的灰度矩阵的最后一列作相似度比较，则差的平方和最小的值其所在的列为第二张纸片。依次连接可得到修复图片矩阵，再由Matlab生成修复图片，照此模型进行排序，来检验模型是否具有普适性。

2 建模与求解

经观察检验所给的图片不存在破损，经碎纸机切割后，文字的每一部分都会出现在分割后纸条片上，图片中相连文字、标点被分割后，两块墨迹能够相互对应，根据对应灰度矩阵分布来确定碎纸片中字、残缺字的位置及分布。若A、B原为两相接的碎纸片，则A、B对应的灰度矩阵a的最右列和灰度矩阵b的最左列具有较高的相似度，即a与b差的平方和是最小的。现选取纸条T，将纸条T的最左列t与其它所有纸条的最右列分别求其差方，得到与t差的平方和最小的即为与T最吻合的那一条，依次求解直至所有纸条用完。

2.1 建立模型

(1)建立灰度矩阵模型，将给出的19张碎纸条写入Matlab，转换生成19个1 980×72的灰度矩阵，在此灰度矩阵中，0代表墨迹，255表示空白，介于0～255之间的为墨迹边沿灰度；

(2)因为第一张纸条左边沿有较多的空白边，因此在灰度矩阵中挑选出第1列全为255矩阵的则为第一张纸条；

(3)原来连接的两张纸片对应的灰度矩阵,A矩阵的最右列和B矩阵的最左列具有较高的相似度。将依次将后18个灰度矩阵Zk·i与第一个矩阵Yki的最左列分别做差的平方和

(1)

当s取最小值时，此时s所在的灰度矩阵对应的纸片为第二张纸片；

(4)找到第二张图片后，依次执行步骤(3)循环，依次求出第3,4…张纸片，直到求出矩阵排列顺序。

2.2 建立模型

步骤1算法将图像写入Matlab转化为灰度矩阵。将附件1中000.bmp～019.bmp等19张碎纸条用Matlab转化成19个灰度矩阵Ckj,将这19个矩阵定义成一个k行，j列的19层三维矩阵Akji(i=1,2,3,…,19),并求出这19个行列数均为1 980×72的灰度矩阵，为简化算法运算，方便矩阵的调用，将上述19个灰度矩阵Ckj的第一列和最后一列分别提取出来，组成新矩阵。灰度矩阵的右边沿：取Akji第i层矩阵的最后1列定义新矩阵Zkj

(2)

灰度矩阵的左边沿：取Akji第i个矩阵的最后一列定义新矩阵Ykj

(3)

步骤2选出第一张纸条所在的灰度矩阵，在此问题中，由于纸条第一张有特殊性，最左端边沿存在一段白色边沿，19个灰度矩阵中第一列全为255的为第一张纸片，即满足Zkj=255。求得i=9，即008.bmp为第一张图片，记第一张纸片d(1)=9；

步骤3通过矩阵边沿相似度大小比较进行图片拼接，原本连接的两张纸片切割后，原来相连文字、标点可以根据其墨迹进行对应。对应到灰度矩阵即原来相连的两张纸片A、B对应的灰度矩阵a的最右列和灰度矩阵b的最左列具有较高的相似度，即其差的平方和的值最小。得到第一条纸片为第9条后，将第一条纸片的最右列Zkj依次与剩下的18个矩阵的最左列Ykj做差的平方和

(4)

求得s最小时，Zki与Yki相似度最高，此时的Zki为第2条纸片，然后选取第2条同理得到第3条纸片，直至最后一条纸，由此依次计算得到后18张图片排列顺序，记d(n)=i,n=1，2，3，…，19；

步骤4在第三步算法运算中，为减少算法循环时重复选取已选纸条，减小算法的时间和空间复杂度，在第一步算法执行前增加一项判断去除命令，定义行向量zz(n)= 1,2,3,…,19。在第n次循环中选中第n张纸片为i后，定义zz(n)=0，再做算法循环时判断，如果zz(n)=0，则不执行此操作并自动循环至下一个数,如果前面已选定某一张并进行排序，那么在下一次筛选时不会将这条纸片列入比较范围，可减少运算的量；

步骤5生成复原图片并对图片进行分析检验，第3步中循环结束得到19个矩阵排列顺序，依据该顺序将这19个灰度矩阵按每列拼成一个1 908×1 386的大矩阵，该矩阵即反应了原纸片所有字符的矩阵。最后用Matlab将这个大矩阵转换为图片，则这张图片即为所得复原拼贴图片结果。如果拼接完成的图顺序正确则说明模型比较适合碎纸拼接问题，如拼接图片出现些许差错则进行人工干预，手工对图片进行调整，如出现问题较大，拼出的图片明显错误则对模型进行改进。

3 模型算法求解结果

在Matlab中将19张图片转化成19个灰度矩阵，并将上述模型算法进行编程，得到19个灰度矩阵排列的顺序为i=9,15,13,16,4,11,317,2,5,6,10,14,19,12,8,18,17。图片复原后顺序矩阵为

000101010001000100000000010101000100008425302614593817706

同理，对附件2中英文图片进行复原排序，得到灰度矩阵排列的顺序为i=4,7,2,9,16,19,12,1,6,2,10,14,11,19,13,15,18,17,5。图片复原后顺序矩阵

000000000101010000000001010101010101003627581051930824764

4 模型的检验与分析

拼图时可能存在的问题比较多，例如两张原本不能匹配的纸条，由于一张最左列与不匹配纸条的最右列都有较多的空白，因此可能会出现两张甚至多张都可以进行匹配的情况。如果最后得到复原图片在句法、语义、逻辑性上出现较大偏差，在不合适的拼贴图片处，进行人工干预选择。通过相似度分析，取最小的3个s值，作为3张备选图片，然后根据句法、语义选择出最合适的一张图片，标记此图片对应的灰度矩阵i，将此值带入初始值，然后继续执行程序，反复执行直到得出合适的修复图片。

5 结束语

随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，本文提出的模型和相应求解算法可以在尽量少人工干预的情况下，对具有轮廓形状规则、字符颜色相同、字符间距和行间距相同的特点的碎纸片进行自动拼接还原。但在实际自动拼接过程中，如果出现一次相邻碎纸片拼接错误，那么就有可能导致后续一系列的拼接错误。因此，如何能够及时发现拼接错误，以及提高拼接的准确率是本文所提出的模型需要继续改进的地方。综合上述问题，在本文提出的模型和算法的基础上，加入对字符的识别技术，则能够有效减少拼接的错误概率，并减少拼接过程中的人工干预。

[1] Ester M,Kriegel H P,Sander J.A density based algorithm for discovering clusters in large spatial databases with noise[C].Portland,Oregon:Proceeding of 2nd International Conference on Knowledge Discovery and Data Mining,1996.

[2] 罗智中.基于文字特征的文档碎纸片半自动拼接[J].华东交通大学,2012,48(5):207-210.

[3] 徐少帅,刘奥强,毛思奇.基于Matlab的碎纸片拼接问题的数学模型[J].科协论坛,2013(12):232-233.

[4] 赵玉峰.计算机图形学的发展及应用[J].科技信息,2008(16):68-71.

[5] 王斌,舒华忠,施朝健.一种基于轮廓线的形状描述和匹配方法[J].电子与信息学报,2008,30(4):949-952.

[6] 刘金根,吴志鹏.一种基于特征区域分割的图像拼接算法[J].西安电子科技大学学报,2002,29(6):768-771.

[7] 贾海燕,朱良家,周宗潭,等.一种碎纸自动拼接中的形状匹配方法[J].计算机仿真,2007,23(11):180-183.

[8] 朱延娟,周来水.二维非规则碎片的匹配算法[J].计算机工程,2007,33(24):7-9.

[9] 徐雅平,王运生,董渊文,等.碎纸片的拼接复原[J].上海商学院学报,2013,14(5):79-84.

[10] 王俊杰.图像配准的方法[EB/OL].(2013-09-14)[2016-11-15]http://www.docin.com/p-211110983.

[11] 何正风.Matlab概率与数理统计分析[M].北京:机械工业出版社,2012.

[12] 楼顺天.Matlab 7.x程序设计语言[M].西安:西安电子科技大学出版社,2007.

[13] 李航.统计学习方法[M].北京:清华大学出版社,2012.

[14] 史程鹏,王明泉,侯慧玲,等.基于像素相关度的射线图像拼接改进算法研究[J].核电子学与探测技术,2009,29(6):1501-1503.

[15] 刘孟娟.基于聚类分析和灰度值匹配的碎片文件拼接复原[J].价值工程,2013,32(32):209-211.

Scraps of Paper Splicing Model and Algorithm Research

YAO Guangdu1,SHEN Jingfeng1,WANG Wendong2,TENG Quan1

(1. School of Mechanical Engineering,Shanghai University of Science and Technology,Shanghai 200093,China;2.Shanghai Research Institute of Materials,Shanghai 200437,China)

In order to solve the problem of how to reconstruct the broken paper pieces quickly and efficiently in the fields of judicial evidence restoration,historical document restoration and military information acquisition,the paper uses the Matlab algorithm to deal with the shredding and gets the gray matrix,and then analyze the inter and the mathematic model was built by using Matlab. The paper was automatically reconstructed with the contour rule,the same character color,the same spacing between characters and the line spacing. Based on this model and algorithm,the recognition technology of different characters can be added to reduce the probability of mosaic errors and human intervention in the process of splicing,and further improve the efficiency of splicing recovery,it has some innovation in the study of splicing restoration.

fractal file stitching; gray matrix; Matlab programming; character recognition technology

TP301.6

A

1007-7820(2017)11-100-03

2016- 12- 04

姚光督(1992-)，男，硕士研究生。研究方向：优化设计。沈景凤(1968-)，女，博士，副教授。研究方向：机械设计与理论等。

10.16180/j.cnki.issn1007-7820.2017.11.027