基于Matlab实现碎纸片的拼接复原研究

王松林 王苑茹

【摘要】破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.本文主要结合重要文件不慎被损坏的修复这一背景，针对碎纸机切碎的碎纸片进行拼接复原研究.主要研究内容有：利用Matlab软件将图像信息转化为数字信息，得到碎纸片的数据矩阵，再对碎纸片进行边界提取.通过进行边界匹配，对各碎纸片的边界序列进行匹配.在碎纸片的边界序列匹配中运用了灰色关联度分析的匹配方法.最后利用Matlab软件图片处理工具箱，依据边界匹配得到的相邻顺序编号对碎纸片进行了拼接、复原.

【关键词】图像转化；Matlab编程；边界匹配；碎纸片复原

一、研究背景及意义

历史上曾出现过将大量绝密文件进行销毁的案例，在司法鉴定领域也存在类似的问题.本课题的目标是利用计算机辅助的方法对碎纸机切碎的纸片进行拼接、复原.本文主要讨论的是针对碎纸机切碎的纸片进行拼接、复原的关键技术.本文对碎纸片进行了整体分析，利用Matlab软件的图片处理工具箱把碎纸片图像信息进行量化，用灰色关联度分析法找出相邻碎纸片之间的拼接关系，最后利用Matlab软件的图片处理工具箱对碎纸片拼接复原.本文主要结合重要文件不慎被损坏的修复这一应用背景，针对碎纸机切碎的碎纸片进行拼接和复原的研究.

二、碎纸片预处理

（一）图像预处理

本文研究采用的碎纸片是一张单面打印的A4纸由碎纸机切碎后得到的规则的矩形小碎纸片，共计209张小碎纸片，并将每张纸片依次编号为k（k=001，…，209）.为了便于计算和处理，先利用图像扫描仪对每张小碎纸片进行扫描，得到每张小碎纸片的电子图像信息[2]，如表1所示.

再利用计算机Matlab软件的图片处理工具箱的a=imread（filename，fmt）命令，将每张小碎纸片的图像信息转化可直接利用的数字信息，得到每张碎纸片的数字信息均为一个72×180阶的数据矩阵.

（二）数据转化及序列提取[3]

利用Matlab软件将图像信息转化成可直接利用的数字信息，得到每张图片的数字信息矩阵后，由于拼接时只研究每张纸片的边界，不用考虑碎纸片边界内部的数字信息，所以再对每张图像的72×180阶的数据矩阵提取第一列和最后一列，分别得到相应的数据序列如下：

左边界的序列X1k=（x1，x2，…，x180），k=1，2，…，209.

右边界的序列X2k=（x1，x2，…，x180），k=1，2，…，209.

三、灰色关联度匹配模型

由于碎纸片边界序列因素之间关系比较复杂，在此采用灰色关联度的方法对各碎纸片的边界进行匹配.灰色关联度是两个系统或两个序列间关联性大小的量度，它描述系统发展过程中序列间相对变化的情况.关联度是考查两数列的接近程度，它的大小反映了两列数据的相互影响程度，关联度大，则说明两因素间的相互影响程度大.如果两序列在匹配过程中相对变化态势一致性高，则两者的灰色关联度大；反之，灰色关联度就小.在此我们利用灰色关联度的方法来匹配两个应该拼接在一起的边界序列.

通过对碎纸片研究分析发现，左右字间距明显小于上下行间距，且左右边界的序列数据多于上下边界序列的数据，因此，先进行横向即左右边界匹配，精確度更高，再进行纵向即上下边界匹配，最后得到复原碎纸文件.

（一）确定匹配序列

对碎纸片的序列进行匹配，先考虑左右边界拼接的情况.首先确定参考序列（又称母序列），这里选取任意一张碎纸片右边界的序列作为参考序列：X2a=（x1，x2，…，x180），1≤a≤209.为了和选取的碎纸片的右边界进行匹配，则将剩下的208张碎纸片的左边界的序列作为比较序列（又称子序列）：X1b=（x1，x2，…，x180），b=1，2，…，a-1，a+1，…，209.若选取的碎纸片的右边界和剩下的208张碎纸片中的其中一张进行了关联度最大的匹配，则认为这两张碎纸片可以拼接在一起.接着就取该碎纸片的右边界作为参考序列，继续和剩下的左边界比较序列进行关联度匹配，直至左右边界拼接结束为止.

再考虑上下边界拼接的情况.由于上面已经对209张小碎纸片进行了左右拼接，左右拼接结束后，209张小碎纸片变成了若干张（假设为h张）横向的纸条.这时再对得到的h张横向纸条利用Matlab软件的图片处理工具箱的a=imread（filename，fmt）命令进行数据提取，分别提取每张横向纸条的第一行和最后一行，分别得到数据序列如下：

上边界的序列Y1h=（y1，y2，…，yn）.

下边界的序列Y2h=（y1，y2，…，yn）.

这里同样选取h张横向纸条中的任意一张碎纸片的下边界的序列作为参考序列：Y2c=（y1，y2，…，yn），1≤c≤h.为了和选取的碎纸片的上边界进行匹配，则将剩下的h-1张横向纸条的上边界的序列作为比较序列：Y1d=（y1，y2，…，yn）.d=1，2，…，c-1，c+1，…，h.若选取的横向纸条的下边界和剩下的h-1张横向纸条中的一张进行了关联度最大的匹配，则认为这两张横向纸条可以拼接在一起.接着就取该横向纸条的下边界作为参考序列，继续和剩下的上边界比较序列进行关联度匹配，直至上下边界拼接结束为止.最后进行碎纸片的拼接及复原.

（二）序列元素的标准化

由于序列中的数据可能因量纲不同，不便于比较或在比较时难以得到正确的结论.因此，在进行灰色关联度分析时，一般都要进行数据的无量纲化处理.利用Matlab软件的图片处理工具箱的a=imread（filename，fmt）命令进行图片信息转化为数字信息，本身就是在同一量纲下进行转化的，所以这里不再对各序列的数据进行标准化.

（三）计算序列的关联系数[4]

ρ∈（0，∞），称为分辨系数.ρ越小，分辨力越大，一般ρ的取值区间为（0，1），具体取值可视情况而定.当ρ≤0.5436时，分辨力最好，通常取ρ=0.5，这里也取ρ=0.5来进行关联度分析.

（四）计算序列的关联度

（五）序列的关联度排序

两序列之间的关联程度，主要是用关联度的大小顺序描述，将所有匹配关联度的大小进行排序，选出最大的，作为左右边界相匹配的碎纸片.将子序列对同一母序列的关联度按大小顺序排列起来，如果r1

若任意取一张碎纸片的右边界和剩下的208张碎纸片中的一张进行关联度匹配，并获得了关联度的最大值，则认为这两张碎纸片可以拼接在一起.接着就取该碎纸片的右边界作为参考序列，继续和剩下的序列进行关联度匹配，直到匹配完成为止.

四、灰色关联度匹配算法

（一）数据转化及序列提取过程

步骤一：

对209张碎纸片进行编号，利用Matlab软件图片处理工具箱的a=imread（filename，fmt）命令，将图像信息转化为可直接利用的数字信息，得到每张碎纸片的数字信息均为一个72×180阶的数据矩阵Xij.

步骤二：

先提取得到每张图片的左右边界序列，利用Matlab软件编程提取出所有碎纸片左边界序列X1k和右边界序列X2k.

步骤三：

建立灰色关联度的匹配模型，对每一对碎纸片左右边界序列进行序列匹配，可以得出一系列左右边界的关联度数据.利用Excel办公软件的筛选功能，进行数据统计，选出每个碎纸片左右边界序列的最大关联度，得出左右相邻的碎纸片编号.重复此步骤，再进行人工干预得到h张横向纸条.

步骤四：

从数据矩阵Xij提取得到的h张横向纸条文件对应的上下碎纸序列，利用灰色关联度的匹配模型，对h张横向纸条较大碎纸片进行上下边界序列匹配.同理得出一系列上下边界的关联度数据，利用Excel办公软件的筛选功能，进行数据统计，选出每个碎纸片上下边界序列的最大关联度，得出上下相邻的碎纸片编号.

步骤五：

利用Matlab图片处理工具箱的imshow命令對碎纸片文件进行复原，并输出到一个完整的图片文件中.

（二）关联度匹配模型算法步骤[5]

步骤一：

对209张碎纸片顺序编号为k1，k2，…，k209，利用Matlab软件图片处理工具箱的a=imread（filename，fmt）命令，把碎纸片图像文件数据化得到数据矩阵Xij.

步骤二：

由数据转化和序列提取，得到每张图片的左右边界序列，利用Matlab软件编程，对建立的灰色关联度匹配模型进行实现.

步骤三：

由步骤二得到了209张碎纸片的左右边界序列的匹配的关联度，可以得出一系列左右边界的关联度数据.利用Excel办公软件的筛选功能，进行数据统计，选出每个碎纸片左右边界序列的最大关联度，得出左右相邻的碎纸片编号.重复此步骤，再进行人工干预得到h张横向纸条.

步骤四：

由步骤二、三，将209张碎纸片拼接成h张横向纸条，这h张横向纸条的横向拼接已经完成.从数据矩阵Xij中提出这h张横向纸条的上边界序列Y1h和下边界序列Y2h.

步骤五：

先对得到的h张横向纸条进行编号（z1，z2，…，zh），分别提取h张横向纸条上下边界序列，利用Matlab软件编程，对建立的灰色关联度匹配模型进行实现.

步骤六：

将运行Matlab软件求解得到一系列相关的关联度，再进行人工干预，选取上下边界序列关联度最大的两张图片进行拼接；

步骤七：

最后将各相邻碎纸片的拼接顺序进行列表汇总，再利用Matlab软件图片处理工具箱的imshow命令对所有碎纸片进行拼接、复原.

（三）碎纸片的拼接、复原结果

由左右边界和上下边界的灰色关联度的分析，灰色关联度越大则数据关系越紧密，碎纸片之间的吻合程度就越高.选取关联度最大的两张碎纸片作为相邻的碎纸片进行拼接.最后用得到的相邻碎纸片拼接顺序表，利用Matlab软件图片处理工具箱的imshow命令，将碎纸片顺序编号依次输入Matlab软件，将各碎纸片进行拼接，最终对碎纸片进行复原.

五、结 论

本文是对由碎纸机切碎的碎纸片进行拼接、复原的研究.本文的研究方法适合任何内容、任何形式、任何文字等的图片，使本方法适用更加广泛.本文研究的方法对于图片信息数据化转换较快、较方便，运用灰色关联度分析方法，对于数据信息较多的碎纸图片匹配精确度较高.本文的研究方法可以进行大量推广，我们建立的灰色关联度分析方法模型，可以大量应用于各种内容碎纸图片拼接问题中的各碎纸图片拼接吻合程度大小的计算以及各张碎纸片的拼接、复原.

【参考文献】

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

[2]萧树铁，姜启源，张立平.数学实验：第2版[M].北京：高等教育出版社，2006.

[3]汪晓银，周保平.数学建模与数学实验[M].北京：科学出版社，2010.

[4]熊翠琳，李旭东.贵州人口受教育程度与经济发展灰色关联分析[J].贵州师范大学学报，2012：119-120.

[5]姜启源，谢金星，叶俊.数学模型：第3版[M].北京：高等教育出版社，2003.