碎纸片的拼接复原

平安 左帅 平静

摘要：本文利用各碎纸片的灰度值矩阵相似程度进行匹配，解决了同页纵切、同页横纵切不同情况的碎纸片拼接复原问题。

关键词：灰度值相似度模型;聚类;分区块匹配;模拟退火

一、背景分析

碎纸片的拼接主要依据各纸片边缘的灰度值，边缘灰度值相似程度高的纸片其拼接成功的可能性就较大。分别针对同页纵切和同页横纵切不同情况的碎纸片进行分析复原。

要解决同页单面纵切的碎纸片拼接复原问题。建立碎纸片拼接复原模型和算法，对中、英文各一页文件的碎纸片数据进行处理，得到灰度值矩阵，利用文件边缘的特性确定其最左边的碎纸片，根据筛选出的最左边碎纸片将其他碎纸片进行聚类处理。最终找到边界灰度值相似程度较高的碎纸片进行匹配处理，完成拼接复原。要解决同页单面横纵切的碎纸片拼接复原问题，碎纸片数量的增多为该问题加大了难度。可将属于同一横向条状纸片的碎纸片进行聚类，模拟退火算法使碎纸片拼接复原成横向条状纸片，解决纵切产生的横向无序性问题。再对横向条状纸片进行纵向排序，从而解决碎片由于横切产生的纵向无序性问题。必要时，引入人工干预以帮助拼接顺利进行，提高拼接的效率和正确率。

二、模型假设及说明

1.假设碎纸片的完整性良好，即：每个附件中的碎纸片都来自同一文件，且同一文件的所有碎纸片都存在与附件中。

2.假设每个碎纸片的边缘光滑，切割时无毛边产生。

3.假设切割产生的碎纸片尺寸完全相等，即每个碎纸片的灰度值矩阵形式相同。

三、模型的建立与求解

3.1单面纵切碎纸片模型的建立与求解

3.1.1图像的数据处理

对碎纸片进行数据处理，将碎纸片的图像分别导入到 matlab 中，依次得到每个图像的灰度值矩阵，例如第2张碎纸片的灰度值矩阵C1：

其中ai，j（n）意为编号为n的碎纸片的图形灰度值矩阵中第i行第j列的灰度值，满足{a|a∈[0，255]且a∈Z}。

3.1.2建立图像边界的灰度值相似度模型

对于单面纵切的碎纸片复原问题，利用可拼接的两碎纸片相邻边界灰度值相似的原理，从首先确定的文件左边缘的碎纸片开始，其他碎纸片左边界的灰度值逐个与其右边界灰度值对比，找到最相似的碎纸片进行匹配，以此类推，使得破碎文件从左到右依次拼接复原。

首先确定求解灰度值相似的基本函数：

f（b，c）即为编号为 b 的碎纸片最右一列与编号为 c 的碎纸片最左一列对应灰度值的离差和，其中b，c=0，1，...，18且b≠c。f（b，c）min表明此碎纸片b与碎纸片c边界匹配程度最高，其拼接成功的可能性最大，因此选择将碎纸片b与碎纸片c进行拼接。

3.1.3模型的求解

为避免在匹配过程中文件最左边的碎纸片与最右边的碎纸片误接，所以首先进行位于原文件最左侧碎纸片的搜索。通过分析存储的碎纸片灰度值矩阵信息，搜索碎纸片灰度值矩阵左列灰度值元素全为 255 的碎纸片，在图像中表现为左侧全为白色，由此位于原中文文件的最左侧的碎纸片，再分别用附件中的其他碎纸片与已确定的左边界碎纸片进行灰度值匹配，找到使得灰度值相似度函数f（b，c）最小时的碎纸片 c 进行拼接。以此类推，实现碎纸片由左向右依次拼接复原。

3.2纵、横切碎纸片文件复原的模型建立与求解

3.2.1图像的处理

读取每个碎纸片的灰度信息，得到对应的灰度值矩阵Cn，例如第一张碎纸片的灰度值矩阵记为C1;将得到的灰度值矩阵简化处理，得到 0-1 黑白矩阵Bn;在简化的 0-1 矩阵中，我们将灰度值矩阵中非白的像素行存储为 0，否则存储为1。

3.2.2中文碎纸片横向拼接的模型建立与求解

Step1：利用前文的模型和算法，找到文件中的最有可能位于原文件左侧的碎纸片和最有可能位于原文件右侧的碎纸片。引入第一次人工干预，将明显不符合要求的碎纸片淘汰，确定位于原文件两侧的碎纸片。

Step2：聚类模型的建立

0-1 矩陣的黑白分块匹配法，步骤如下，对左侧边缘的图片的 0-1 矩阵进行分析，每次 0-1 变换的交界处即为断点，n 个断点将纸块分成了 n+1 个区域。

区域匹配：首先将奇数区域所在行与其他图片对应行做差，判断差的绝对值之和是否小于所定模糊像素长度。若奇数区域全部符合条件，则将被匹配碎纸片与此边缘碎纸片归为一类;否则，对偶数区域进行同样匹配，若偶数区域全部匹配成功，则归为一类，否则不归为一类。对处理得到的 0-1 矩阵进行聚类分析以减少计算量提高拼接效率。

考虑到碎纸片每行文字的高度不尽相同，反映在图像上就是两碎纸片虽相邻，但其0-1 矩阵中连续为 0 或 1 的行数并非完全相同。所以我们将黑色和白色的边界模糊化，并分析得出，当模糊长度设定为 4 时，每类碎纸片的个数都接近 19，即聚类效果最好。

Step3 对碎纸片进行横向拼接

记每一类碎纸片的复原结果为 N，其中n（k）是复原结果中由左至右的第 k 张碎纸片。则有：

N=（n（1），n（2），...，n（19））.

解空间M可记为M={N（1），N（2），...，N（m）}，其中，N（m）记为碎纸片的第m种拼接顺序。

（2）目标函数：

f（n（k），n（k+1））意为第 k 张碎纸片与第 k+1 张碎纸片的边缘对应灰度值的离差和。当 F（N）取得最小值时，此时的复原顺序为最佳排序。

（3）接受准则

假设碎纸片在拼接顺序为 p 时的匹配程度为F（Np ） ，那么拼接顺序由 p 到 q时就遵循以下规律：

若F（Np）≤F（Nq），接受拼接顺序q;则接受概率：e

确定Tmax =120，Tmin =1;取降温系数 c=0.9。

（4）结束条件

选定的终止温度Tmin=1，判断退火过程是否结束。若T

四、模型分析与评价

通过对结果进行分析，可知本文的模型精确度较高，并对某些特殊情况进行了处理，可以有效合理的解决规则切割的碎纸片拼接复原问题。但该模型也存在缺点，如特殊结构的碎纸片数量过多时，在采用分区块匹配进行聚类时，淘汰的碎纸片数量就会增多，这时引入人工干预拼接的碎纸片数量也加大，一定程度上降低了拼接复原的效率。在边界灰度值相似度模型中，我们运用相邻图片灰度值相似的原理，当两碎纸片相邻边界对应的元素越小越有可能拼接成功，此模型计算简单，运算时间复杂度也不高。但也有可能出现错误拼接的情况，当处于碎纸片左边缘的文字由于切割产生的断线过于细小，这时当某一碎纸片右边缘全白时与之匹配的f（b，c）值也很小，这时这两张碎纸片就会错误拼接。

参考文献

[1]司守奎，孙玺菁，数学建模算法与应用[M]，北京：国防工业出版社，2011

[2]卓金武，Matlab在数学建模中的应用[M]，北京：国防工业出版社，2011