基于碎纸片的拼接复原算法及MATLAB实现

一、问题描述

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：

（1）对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。

（2）对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。

（3）上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。

二、拼接中存在的几个主要问题及解决方案

为了将碎片拼接成一幅完整的图片，需要解决的问题有以下几个方面：

1. 如何判断两个碎片是否为相邻碎片？
2. 如何控制两两拼接的循环执行直至拼接完成？
3. 如何判断碎片是否为边界碎片？
4. 如果碎片的某个边界刚好完全是空白，则将其判断为原图的边界还是相邻文字的空隙？

（5） 对于既有纵切又有横切的单面图片，如何拼接？

（6） 对于对于既有纵切又有横切的双面图片，如何拼接？

 针对上述问题，我们给出以下解决方案：

1．问题（1）的解决方案

为了减少计算量和便于处理，我们将原灰度图像转换成二值图像，此转换不影响文字类图片的质量，也不会影响拼接效果。

一般而言，相邻碎片的边缘都具有很强的相似性，我们通过判断碎片矩阵的对应边界列的相似程度来确定两矩阵存储的碎片是否为相邻碎片。为了确定两列向量的相似程度，我们利用其信噪比值psnr来衡量，psnr的值越大，说明两者的相似程度越高。在拼接过程中可能会存在这种现象：也许存在多幅待拼碎片与已拼图片的信噪比相同，为了从中选择一幅正确的碎片作为当前碎片的邻接碎片，我们可以人为介入从语义上进行判断。也有可能待拼碎片与已拼图片的信噪比大，但是并不是已拼图片的邻接图片，反而次小信噪比的碎片是邻接碎片。这是因为用信噪比去衡量邻接碎片边缘的相似度也存在概率性误差。对于以上两种情况，我们都需要在程序运行期间进行人工干预，即程序在拼接时需要与用户进行交互。思想如下：拼接函数f2()和f3()拼接时都会将当前已拼图片与所有待拼碎片的信噪比进行求解，并将所得信噪比序列存入一维数组中，然后通过排序函数paixu2()进行自小而大的排序，然后通过循环控制，从已排序数组的最后一个元素逐个向前尝试，每尝试一次都要与用户交互，用户根据图片语义判断拼接正确与否，如果正确，则给出‘YES’的输入，程序终止拼接；如果否，则给出‘NO’的输入，程序继续尝试剩余碎片，直到找到正确邻接碎片为止。实验证明，用该种方法对单纯纵切碎片的情况非常有效。

2．问题（2）的解决方案

在拼接的过程中，需要考虑如下几种情况：

① 如果选取的第一幅碎片刚好是原图的左侧边缘碎片，则只需要在其右侧进行拼接，直到完毕。

② 如果选取的第一幅碎片刚好是原图的右侧边缘碎片，则只需要在其左侧进行拼接，直到拼接完毕。

③ 如果选取的第一幅碎片刚好是原图的内部某一碎片，则既要进行右侧拼接，又要进行左侧拼接。

针对以上三种情况，我们编写了两个拼接函数，其中函数f2()实现两碎片的右侧拼接，函数f3()实现两碎片的左侧拼接。通过反复调用两函数实现整幅图的拼接。为了确定是选择函数f2()还是函数f3()，依照以下思路进行：

从所有碎片中首先选择一个碎片，判断其是否为右侧边缘碎片，如果否，则对其进行右侧拼接，则反复调用右拼函数f2()，直到右边缘，然后再调用左拼函数f3()进行左拼，直到左边缘；如果是，则直接调用左拼函数f3()进行左拼，直到左边缘。

3．问题（3）的解决方案

在拼接过程中需要判断是否已经拼接到原图的边缘，为了解决该问题，我们在设计函数f2()和f3()时，分别用它们的返回值的一个分量来标志是否调用成功。如果函数按psnr的逆序试了所有剩余碎片都未能找到合适的碎片，说明当前待拼图片是边界图片， 此时返回值分量flag的值为0，否则返回1。

4．问题（4）的解决方案

对于此种情况可以不做特殊处理，只需要调用拼接函数f2()或f3()进行拼接。如果刚好是边界，而剩余碎片个数为n，则人机交互n次才能判断该图片为边界碎片，而且人为根据语义做出判断时，也浪费了很多精力。为了避免该情况发生，我们将边界完全为空白的情况处理为边界。也可以在程序中直接把该处理对应的代码去掉，其余代码不需做任何改动，不足是增加了人工干预次数。当然，我们假定，在纵切时没有刚好完全切在空白处的情况，否则程序会给出错误的结果。程序实现时，具体处理方法如下：以f2()为例，首先测试碎片矩阵的大小，如果该碎片矩阵的右侧边界分量各元素值的和与碎片的行数之差小于一个阀值，我们就认为该碎片为边缘碎片，停止拼接。因为碎片已被处理为二值图像，在二值图像中，白色像素值为1，黑色像素值为0，而边缘通常是纯白的，在考虑有极少杂色的情况下，我们给了一个阀值。左侧边缘判定方法一样。

5．问题（5）的解决方案

对于既有纵切又有横切的图片，我们按如下思想进行拼接：利用纵切图片的拼接思想首先将碎片拼接成多个横条图片，然后将每个横条图片的矩阵进行转置，最后再次利用纵切拼接思想对横条图片进行拼接，拼接完毕后，将得到的最终矩阵进行转置，最终得到整幅图片。在实现过程中，存在以下细节需要处理：

整个过程中需要多次调用纵切拼接函数将碎片拼接成多个横条图片，所以，需要在每次成功拼接一个横条图片时将当前已参与拼接的碎片从剩余碎片中分离出来，这就需要用到分离函数ff()。

6．问题（6）的解决方案

   单面纵横切的算法和思想完全可以拓展到双面纵横切的情形，区别在于：在将所有碎片拼接成横条形图片后，再进行横条拼接时要产生两幅图像。为了能生成两幅图像，需要在单面纵横切拼接算法的基础上做以下处理：在拼接过程中要将参与拼接的图片与剩余图片分离出来；从一个图片开始拼起，如果遇到两个边界都已经找到了，说明第一个图片已经拼接完毕，然后再将剩余碎片拼接成另一面图像。因时间关系，我们未能编程实现。