碎纸片拼接复原的数学模型与优化

朱旭++焦熹++李亦凡

摘要 碎纸机裁出的碎纸片的拼接与复原技术是计算机算法与人工干预的结合，兼顾准确度与效率。碎纸片的拼接与复原算法以采用了全新的向量间欧氏距离的匹配模型，在图片数据化处理的基础上，加之针对横向纵向双向切割的文档而编写的检测碎片是否在同一行的辅助程序，和针对英文文件的碎片进行行位置标识从而实现“行分类”的应用扩展程序；核心算法和辅助及扩展程序共同构成了碎纸片拼接复原的数学模型。最终对单面中英文单向和双向实现了裁切的纸张都97%以上的复原，可以说复原模型是成功且有效的。

关键词 碎纸拼接复原 欧氏距离匹配 元胞数组嵌套结构

中图分类号：G642.3

文献标识码：A 文章编号：1002-7661（2015）01-0004-02

破碎纸张文件的拼接修复在司法物证的复原、历史文件的修复以及军事情报的获取的等多个领域都有重要的作用。人工手工拼接的优势在于准确性高但耗时长，相比之下，计算机算法进行的拼接速度快也有能力实现大量破碎文件的拼接，而计算机为主后期加入人工干预的方法就有更强的实用性。但是已有的计算机拼接方式是基于边界几何特征的拼接方法，并不适用于规则裁切的边缘形状相同的碎纸片。本文将针对规则裁切的印有文字的纸张进行全自动和半自动的拼接复原模型建立，利用此类纸张特有的规整性，运用图片信息数据化、矩阵化，使用向量的欧氏距离测定进行匹配还原。

一、建模思路

1.图片数据化处理

计算机拼接以图片的数据化和数据匹配为核心，实现量化处理。碎纸片经过扫描后成为图片形式的数据，通过一定的降噪和对齐处理之后就可以用Matlab以像素为单位转换成为矩阵，对矩阵的边界向量进行匹配，最终得到完整有序的整体矩阵，重新生成为图片。复原的关键点在于图片信息的读取与处理。利用Matlab可将图片中的实体信息转化为矩阵中的数量信息，矩阵的每一个元素分别代表一个像素点上的颜色信息，预设所有的材料均为黑白印刷，暂不考虑由三维向量构成的彩色像素点。Matlab把有黑到白连续变化的灰度值量化为256个灰度级，0-255分别表示亮度从深到浅，对应图像中的颜色为从黑到白。至此，碎片的拼接问题即转化为数值矩阵的运算处理问题。

2.核心拼接算法

①将附件中的碎片图片转化为用于运算的数据。假设纸张由19条纵切的纸条构成，使用MATLAB的unread命令将碎片图片批量导入一个1×19的元胞数组中，即将图片由bmp格式的文件转化为数据类型为uint8的数值矩阵。其中第i张碎片的数值矩阵记为元胞数组的第i个数值矩阵，即c{i}。以任一数值矩阵举例，矩阵的大小为72q1980，其每个元素代表了对应碎片图片的该像素位置的灰度级，大小在0-255之间，纯黑为0，纯白为255。

②删除数值矩阵中的冗余部分。考虑到印刷文字的特点，每两行文字之间会有一定的行间距，该部分的像素全部为白色，对应到矩阵中该处元素数值全部为0，对接下来的匹配运算没有意义。为了提高运算效率，避免冗余的运算，对整体中的空白行进行删除。

③进行碎片间相似度的检测。在进行相似度的检测中，只需用到碎片图片左右边界的各一列像素，即数值矩阵的第1列和第72列列向量；左边界向量记为l{i}，右边界向量记为r{i}。计算19个左边界向量和19个右边界向量两两之间的欧氏距离。

④根据得出的距离对碎片进行匹配和排序。优先匹配距离最短即相似度最高的两个边界。找到一组相似度最高的两碎片边界，将该两边界分别与其他所有边界的距离替换为10000，保证其不再干扰随后的匹配运算。此处需要进行人工干预，因为碎片纸条中有两条是原文本文件的最左，右一条。最后得出碎片排列的编号顺序，记为C。

⑤拼接并生成完整的图像。按照上一步骤中得出的编号顺序C依次对碎片的数值矩阵c{i}进行拼接，得到完整图像的数值矩阵，记为Cdata。再根据Cdata生成图像。

⑥人工检查复原结果是否合理。

3.拼接模型的深度优化

①垂直双向裁剪的拼接方案。针对纸张被垂直横纵切为粒状的情况，复原模型可以转化为对碎纸片的分类。分类的原理依然是矩阵边界向量的欧氏距离计算，测定适度的界限如1100，将欧氏距离小于1100的纸片归为一类，并默认一类纸片代表出于同一行的所有纸片。在横向拼接完毕后，纸片部分复原为若干横条，拼接难度明显降低，随后的工作完全可以由人工完成。

②辅助性降噪处理。如果纸张扫描后的图片有干扰性噪点，可以在图片导入前先追加一步降噪处理，此过程需要人工干预，对照片处理后的质量进行监控。同时，如果同一批次的扫描照片噪点程度相似也可先进行批量处理，人工只需检查处理后的图像，挑选不合格的图片返回二次处理。最终达到的目的是将扫描图片内的干扰性噪点降到最低，同时不影响文字和图像资料的检测。选用Matlab也可以进行降噪工作，要求先将图片数据二值化，将二值化后的图像表示为函数g（X，y），噪声信号为n（X，y），去噪后的图像为e（X，y）一g（x，y）-n（X，v）。

③含有图片纸张的图片优先处理方案。如果在纸张上出现了图片则要优先对图片进行拼接，当图片特征很明显的是可以仅采取人工手工拼接的方法，当图形较为复杂，拼接特征不明显时可以用计算机算法来拼接。具体的操作是先将碎片扫描如电脑生成图片文件并进行必要的降噪和二值化处理，再将距离剪裁边界5-15像素的区域选为研究区域，针对区域内的点的分布做函数拟合，可以假设在10-30像素内的图像线条基本为直线，拟合的函数便简化为一次函数，对剪裁边界以外5-15像素范围内的函数图像进行预测，最后将预测的函数图像与可配对的边界函数检测进行匹配，寻找匹配度高的优先匹配即可生成完整文件，辅之以一定的人工校对。

二、实用性讨论

本模型适用于所有印有文字的，规则裁切的纸张的拼接复原。印有文字的原始资料具有手写资料所不具有的规则性，即其有严格的字体、字号、页边距、行距等规范，而这些规范也自然成为后期拼接时有效的利用点。如相邻两行间的行距可以默认为相同，而整个纸张无论是横向还是纵向碎纸，都可以与文字和行间的方向构成稳定关系，相应的在由图片形成的矩阵中如果出现连续的若干横向量都为零，则可以认为是上下页边距或行间，同理连续列向量为零则可认为是边界或纵向的分割空白区域，纵向文字材料刚好相反。

几乎所有黑白印刷的纸张的修复基本上都可以用已给出的修复模型再配合辅助方案实现完全修复。而彩色的文件的修复则只需将原有的黑白二值的运算和匹配换为相应的三维向量的提取运算和匹配即可。且彩色的材料具有更强的连续型，匹配时的匹配度也会更高。

以图片数字化处理为基础，以元胞数组嵌套结构为媒介，以向量欧氏距离的测定和匹配为核心的碎纸拼接复原模型在实际的运用中显现出了良好的效果，修复率均在97%以上，运行平稳，高效便捷。而广泛的适用范围和简洁的操作更使其在实际运用中显现出强有力的优势。本模型在全国大学生数学建模竞赛（B组题）中取得了山东省二等奖的成绩。