碎纸片的拼接复原模型

邓方清　邓小安

【摘要】针对碎纸片的拼接复原问题，本文从边缘像素矩阵入手，通过对该矩阵数据的标准化处理、求取像素平均值、定义像素255的频率、矩阵分块等方法，运用相关的匹配度算法分析，建立了纵切又横切的碎片拼接复原模型.

【关键词】像素矩阵；聚类；距离匹配度算法

一、引言

据了解，传统上，拼接复原工作需由人工完成，准确率和效率都很低.特别是当碎片数量巨大，人工拼接很难在短时间内完成任务.大量的实例证明，碎纸拼接技术在司法物证复原、历史文献修复等领域都有着非常重要的应用.所以提高碎纸数量巨大拼接复原的效率和开发碎纸片的自动拼接技术具有重要的研究意义.本文研究被横切成11条、纵切成的19条碎片进行拼接复原，结果显示，拼接复原相似度高.

二、纵切又横切的碎片拼接复原模型

1.边缘像素矩阵

碎纸片的左右两边或上下两边的被横纵切的线条是平直的，得到第i条碎片的像素矩阵：

从中各自选取左右边缘一列的像素矩阵作为边缘像素矩阵以便于建立模型时可以进行像素点的距离匹配度分析.

2.数据标准化处理

假设第i条碎纸片取值为aij.将各个影响因素的值aij转换成标准化指标值

（一）模型的建立

针对中文碎片拼接复原模型，先通过求取像素平均值、点像素255单文本数据的频率等数据处理方法来对209条碎纸片的边缘像素矩阵进行分块，再逐步进行聚类分析，从而得到11组包含19个碎纸片左右边缘的匹配组合，接着在得到条横切的碎纸片后，通过比较分析每条新的碎纸条上下两边边缘矩阵对应的空白或字体的宽度之和来进行横条的上下拼接.从而使所有碎纸条得以拼接复原.

1.纵切碎纸片模型问题

假设C表示209条碎纸片的拼接复原图形，Ci表示第i条的像素矩阵，如下所示：

由以上的算法可知，开始时，在Pl的第1列，顶部分、中部分和底部分共三部分各自都选取了匹配数值最大的前19位匹配度.在各自得到了19个可以拼接复原的组合后，统计出并记录下连续在顶、中、底三部分中都有被选取出来的组合，以及在任意两部分或只有一部分被选取出来的组合.如果在三部分都被选取出来的组合，则准确率极高地说明它们的匹配度很高，将其分成一类.如此计算可得出11类碎纸片，可以将这11类中的每一类拼接复原成原图形的11条横条.

2.纵切碎纸片模型问题

解决了碎纸片被纵切的拼接复原问题后，接着就是要将这11条横条上下拼接复原成完整的原图形.本文借助行高、行间距，根据它们的一般不变性，寻找11条横条的最佳匹配组合.具体过程如下：

Ui=ui，-ui，当Ma矩阵所有元素为255否则

Di=di，-di，当Ma′矩阵所有元素为255否则

其中ui，di>0，Ma是上边缘像素矩阵，Ma′下边缘像素矩阵.所以，可知，本文用正数代表像素值为255的白色边缘，负数代表存在像素值为0的有字边缘，ui表示上边界空白边缘的最大宽度，-ui表示上边界字体边缘的最大宽度，而di表示下边界空白边缘的最大宽度，-di表示下边界字体边缘的最大宽度.

定义Q1和Q2：

Q1=ux+dyx，y∈[1，11]且x≠y

Q2=|-ux|+|-dy|=ux+dyx，y∈[1，11]且x≠y

在上述等式定义的过程中，假设原图形文件中文本的行间距为H1，行宽为H2.先任意依次取所有碎纸片的上边缘空白宽度和不同碎纸片的下边缘空白宽度进行加法求和的运算，判断Q1与H1的大小关系；接着在依次取所有碎纸片的下边缘字体宽度和不同碎纸片的上边缘字体宽度进行加法求和的运算，判断Q2与H2的大小关系.

若Q1=H1，则说明第y条碎纸片的下边缘空白的宽度与第x条碎纸片的上边缘空白的宽度之和等于文件中文本的行间距，即可知，第y条碎纸片应拼接复原在第x条碎纸片的上方.若Q2=H2则说明第y条碎纸片的下边缘字体的宽度与第x条碎纸片的上边缘字体的宽度之和等于文件中文本的行宽，即可知，第y条碎纸片应拼接复原在第x条碎纸片的上方.如此计算循环下去，结合先前进行纵切的拼接复原，剩下的11条碎纸条也可上下拼接复原成原图形文件.

（二）模型求解

使用MATLAB获取每一条碎纸片的像素矩阵，对之中的每行像素值进行平均值求取，计算接连的六个平均值为一个单位进行像素255数据单文本的频率，进而得到一个矩阵30×209矩阵B，

如果在1，2，3三部分都被选取出来的组合，则准确率极高地说明它们的匹配度很高，将其分成一类.最终聚类形成了11个组合类.接着，对这11个类进行匹配分析得到11条横切的碎纸片.通过比较每条新的碎纸条上下两边空白或字体的宽度来进行横条的上下拼接.

三、结束语

通过对此模型的结果研究显示，本文的碎纸片复原模型的拼接相似度很高.对于碎纸片较少时，可以不需要人工干预，而碎纸片数量非常大时，极其需要人工的干预.本模型只适用于单面规则的碎纸片复原，而且在自动拼接的过程中，如果出现一次相邻碎纸片拼接错误，那么就有可能导致后续一系列的拼接错误.所以应减少人工的干预次数.

【参考文献】

[1]贾海燕.碎纸自动拼接关键技术研究[D].长沙：国防科学技术大学，2005.

[2]张国林.基于汉字识别的碎纸片拼接复原模型研究[J].科技广场，2014（01）：62-64.