碎纸片的拼接复原研究

赵辰 乔振宇 李思漫

（辽宁工程技术大学电子与信息工程学院，辽宁葫芦岛 125105）

1 问题重述

对于只有纵切的碎片文件（要求其来自同一种印刷格式），建立拼接模型以及算法，进行碎片的拼合，在复原过程中，若需要部分人工干预，表示出干预方式及干预过程的时间节点。最后，通过完整图片表示出复原结果。

在既有纵切又有横切的情况下，请设计模型以及算法，进行碎片的拼合，复原结果以图片形式表达。

2 模型的假设

2.1 假设题目所给的所有碎片拥有相同的大小及尺寸，其边缘的轮廓是正常且形状规则的矩形。

2.2 假设所给破碎文件四周边界上的文字和符号都是完整的。

2.3 所有碎片中的文字印刷格式、颜色、字号一致，同时字体颜色与背景颜色有较大的区别。

3 问题的分析

针对在碎纸片被纵切的特殊情况下，是首先利用matlab 转化，分别通过转化计算出各一张碎纸片的转化灰度和二值矩阵，然后通过转化灰度为二和一值矩阵，得出两张不同碎纸片上的边缘二和一值矩阵向量值在矩阵上的差异，同时通过转化灰度和二值矩阵计算得出纸片文字号和行列号在位置上的差异，按照此方法依次从左至右找到相邻碎片，最终复原碎片。

针对纸片被纵切和横切的情况下，这个问题属于二维复原问题，不仅要考虑碎片左右端特征，还要考虑上下端特征。考虑到特征因子难以满足问题的要求，故增加两个特征因子-空白行和向左（向右）最小边距。

4 模型的建立与求解

4.1 纸片纵切问题的求解

首先将每幅图片依次进行灰度处理，得到一个1980 行、72列的灰度值矩阵。碎纸片的测量寻找灰度方向一般为从左向右，找到左侧每块碎纸片的两个灰度测量矩阵的最后一列，再依次找到右侧碎片硬纸片的灰度矩阵第一列，让这两列的灰度值相同，则这两个碎片为相邻图片。按这种循环多次比较，直到判断出碎纸片的正确顺序。

4.1.1 首先选取一个图片，先将它进行格式转化，将其灰度化和二值化。

4.1.2 将这些灰度后的图片进行二值化，二值化之后产生矩阵部分矩阵不予给出，最后得到全部矩阵。

①首先进行滤波的处理，滤出其的噪声，再进行平滑图像处理为第一步；

②其次就是进行直线边界的分析提取。依据关于形态边界梯度的数学算子分析公式，通过3*3 的8 个不同连通边际结构边界元素，分别对其图像进行连通边界的运算提取，得到8 幅不同的连通边界结构图像，其次就是得到这些边界图像在其固定的边界位置上的每个像素的数值，运算之后得到所在边界上的图像e1；

③系统使用直方照片图阈的二值化计算方法，对计算得到的直方图片数据进行图像二值化，最终用户可以接收到图片二值化后的图像；

④对应的图像图象e1 使用阈值统计分析方法二次阈值化，得到二次阈值化的图像图象e2；

⑤将二值化图像e2 的每个像素，通过位反运算，得到一个新的二值图像e3；

⑥最终结合之前的三个图，输出二值图像G。

4.1.3 按照此方法依次对碎纸片进行处理，分别求得每一幅图片右侧吻合度最高的图片，最后读取十九张图片之后得到全部的边缘距离矩阵，依据这些边缘距离矩阵求出和纸片右相邻的纸片，最后求出文件中最左边的碎片，从而记录上一张碎纸条，然后记录下一张碎纸片。最后存取整张图片，得到复原图。（表1、2）

表1 问题一附件1 的拼接序号表

4.2 纸片被纵切和横切的求解

我们先利用上述模型中的的灰度化后的模型进行二值化处理，得到相对应的二值化模型，进行碎片的复原。然后再将拼接好的已经被拼接的部分变为碎片，最后可以得到经过还原处理出来的碎片纸张，利用由每个碎片纸张组成的数据文件夹对数据模块进行综合模拟并用仿真进行处理。

4.2.1 空白行特征因子定义

对于碎片的灰度矩阵Aj（j=1，2，……，19），构造的列向量cj，cj（m）代表列向量第m 行元素。cj用以记录Aj的空白行位置。

图1 像素矩阵示意图

4.2.2 向左（向右）最小边距特征因子定义

将Ai灰度作为矩阵的向左或者向右的最小边的间距分别记为li1，li2。向左的最小边长间距为每个碎片最左端向右然后开始继续排列的碎片空白最小像素的排列次序个数；同时向右的最小边长间距为每个碎片最左中右端向左然后开始继续排列的碎片空白最小像素的排列次序个数。

4.2.3 找到与头碎片同行的剩余碎片，并给出模型和算法

找到与头碎片Aleft1同行的剩余碎片。若碎片Aj与Aleft1属于同一行排列，在理论上有cleft1=cj。但由于本问题利用未二值化的灰度矩阵分析，故需要考虑字符边缘白噪声造成的误差。故给出一个阈值DH，若有|cleft1-cj|

4.2.4 复原同行碎片的最优化模型

现为灰度矩阵As寻找右相邻碎片。目标为在可供匹配的所有灰度矩阵中找寻与灰度矩阵As边缘匹配程度最大者，即边缘误差最小者。据劈开位置可分为两类分别对应情况一：从两字符间留白部分劈开；情况二从某字符中间劈开。

观察发现部分碎片无法根据边缘匹配程度来选择相邻图片，进过试用比较，可以利用下述不等式来排除此类图片的干扰。

表2 问题一附件2 的拼接序号表

其中Th 为可以复原一个图片的集合文字灰度间距，集合F是由一个可以提供完整匹配的文字碎片点和全体文字灰度矩阵集合构成。Th 单位：像素。

4.2.5 复原同行碎片的图论模型

现为灰度矩阵A1寻找右相邻碎片。

则求问题转化为在非负有向图中寻找一条权值最小的哈密尔顿路径的问题。

4.2.6 人工干预方式与时间节点

在对每行碎片利用复原同行碎片的最优化模型复原时，当两图片间的ε 值虽较其余的小，但图片实际上是不连续的，此外还可能发生多组合的ε 值相同且最优，这时候也需要人工干预获得连续的相邻图片组合。

通过MATLAB 程序求解得。（表3）

表3 问题二附件3 的拼接序号表

5 模型的评价

针对不同情况碎纸机的碎片类型、大小和纸片尺寸，我们在问题模型中对具体不同问题模型进行了具体的数据分析，设计了不同的模型算法应用来正确应对每种不同情况，并重新复原了碎片机纸片。对于英文模型中，中文和简体英文的不同字符匹配特点，本文对模型充分进行挖掘，使得本模型的字符匹配度和准确度较高。在纸片模型中及其相关匹配参数对不同算法的纸片匹配度和准确率的提高影响较大，因此在对于不同碎片的纸片时，相关匹配参数都必需被重新进行设定。模型中对于缺乏针对性和碎纸片的正确语义进行分析，同时对于其他模型，应该进一步考虑减少人工干预的实际参与者数量。在碎片调整碎块行距的计算过程中，可以直接根据碎片行的调整行距物理特征直接判断计算行距得出调整结果，而不是先判断调整碎块行片段再直接评判调整行距。分组时如果考虑到了带有碎片的部分具有文本结构特征，所以还是你可以选择可虑用碎片聚合归类分组方法或者使用人工智能中模式识别分类方法来叫做碎片分组用来代替用本文所用的碎片分类分组算法。