碎纸片的拼接复原分析模型

碎纸片拼接复原的设计与实现摘要破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

由于人工拼接效率较低，我们利用MATLAB软件编写程序，实现碎纸片拼接技术的计算机化，实现批量拼接，以节省人力和时间。

（一）为寻找最吻合拼接方案，利用MATLAB软件中的imread函数，实现了碎纸片与矩阵之间的形式转化以便于碎纸图片的拼接比对。

数值0至255表示图中某一像素点由黑到白的变化程度。

再根据纸张的边界留白较多，通过计算每个矩阵第一列中各向量的元素和，可将所得和数值最大的列向量所在矩阵对应的碎纸片确定为左边界。

经计算知：008图为整体图片的左边界。

根据使吻合参数1980,,72,11{}{}i j k kkP i P jρ==-∑最小的原则，可计算出下一张图片。

重复此步骤，以此类推，每次都挑选出剩余图片中与前一幅图片吻合参数,i jρ最小的作为与之相连接的碎纸图片。

最后可得到行优化。

附件3类比于问题一，用相同的方法找到所有碎纸片的左边界，共11张，分作为入手点，利用MATLAB软件进行图片拼接。

但由于碎纸图片的行特征值有误差，故图片大块拼接正确，但与实际情况有细微差别。

通过简单的人工检测得到准确行的排列顺序，由于行信息充足，借用第一问最终达到正确拼接效果。

结果矩阵如表12 所示。

第二种情况的关键点是找出准确的行特征，由于汉字与英文书写格式不同，汉字均为方块字，易于定位。

而英文由于特殊的书写方式，上下位置不同，不易于找到行特征值。

如：英文字母最为密集行中点位置。

需将附件4图片对应的矩阵转化为0-1列向量（空白行为0，反之则为1）。

利用此方法筛选出位于同一行的碎纸片并进行纸片拼接。

后续拼接方法同附件3。

结果矩阵如表13 所示。

（三）结合双面信息处理边界，得到边界特点。

根据元音字母中心位置得出行高，从而更准确筛选同行图片。

双面信息同时校准，更容易得到拼接顺序，人工干预少。

结果矩阵如表5 所示。

模型一简单易处理，适用于含大量信息的碎纸片拼接且准确度高；模型二针对文字内容的中英文差异分别利用吻合参数和行高作为标准来筛选图片；模型三深入生活实际，考虑日常生活中反正面印刷情况并结合英文印刷特点，实用性高，双面信息同时校准，人工干预少。

关键字：碎纸拼接MATLAB 吻合参数灰度一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。

特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。

随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。

请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。

2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预，请写出干预方式及干预的时间节点。

复原结果表达要求同上。

3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。

附件5给出的是一页英文印刷文字双面打印文件的碎片数据。

请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。

【数据文件说明】(1) 每一附件为同一页纸的碎片数据。

(2) 附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。

(3) 附件3、附件4为纵横切碎片数据，每页纸被切为11×19个碎片。

(4) 附件5为纵横切碎片数据，每页纸被切为11×19个碎片，每个碎片有正反两面。

该附件中每一碎片对应两个文件，共有2×11×19个文件，例如，第一个碎片的两面分别对应文件000a 、000b 。

【结果表达格式说明】复原图片放入附录中，表格表达格式如下：(1) 附件1、附件2的结果：将碎片序号按复原后顺序填入1×19的表格； (2) 附件3、附件4的结果：将碎片序号按复原后顺序填入11×19的表格； (3) 附件5的结果：将碎片序号按复原后顺序填入两个11×19的表格； (4) 不能确定复原位置的碎片，可不填入上述表格，单独列表。

二、模型假设1、 每张碎纸片的形状都是完全相同的长方形且每张碎纸片形状规则；2、 文字打印清晰，无缺墨断墨情况；3、 纸片边缘整齐，无重叠，无损耗；4、 扫描过程中每张碎纸片的位置都是完全平行的，不会出现倾斜的情况；5、 假设恰好能完全拼接，即碎片无缺失，也没有其他碎片混杂；6、 纸片无倒转；7、 碎片文字均为相同字号，字号大小适中； 8、 文字印刷体行高、行间距相同； 9、页边距非0，但较小。

三、字符说明1、{}P i 表示第i 张图片所转化得到的矩阵；2、,{}m n P i 表示第i 个图所形成的矩阵的第m 行n 列对应灰度值；3、{}()P i j 表示第i 个图所形成的矩阵的第j 列；4、,j k ρ表示第j 个图和第k 个图之间的吻合参数（其含义在模型分析中说明），其中两张图的吻合参数越低表示这两张图越吻合；5、i l 表示图i 的0-1列向量四、模型分析本文针对三种碎片拼接类型分别建立数学模型。

模型一简单易处理，适用于单片含大量信息的碎纸片拼接且准确度高；模型二针对文字内容的中英文差异分别利用吻合参数和行高作为标准来筛选图片，且以缩小比对范围的形式应用于庞大数据量的整理进而进行碎片拼接复原；模型三深入生活实际，考虑日常生活中反正面印刷情况并结合英文印刷特点，实用性高，准确度大。

问题一：利用MATLAB 程序中的imread 函数将附件1的19张碎纸片分别转化成矩阵形式，每一张碎纸片都可转化为一个198072 的矩阵。

for 循环的使用可以很大程度上节省时间、人力，再根据边界准则通过计算首列数字变化来确定其边界。

最后根据吻合参数的大小确定最后的碎纸片拼接顺序。

求解步骤如下：（图1：问题一求解思路图）问题二：同样利用第一问中求得图片左边界的方法，附件3、附件4中两幅图片的左边界。

找出与左边界11张图片同行的其余碎纸图片。

编程筛选出每行的图片，利用问题一中的方法进行计算机拼接，但由于拼接存在一定的误差，所以部分图片拼接不完整正确，在此情况之下进行人工干预，观察图片内容，根据内容手动移动碎纸图片进行拼接。

求解步骤如下：（图2：问题二求解思路图）问题三：对于有双面打印的碎纸片，根据边缘留白情况，可筛选出22个左边界，并根据字母中点所在行的行高分为11类。

并根据行高对其他图片进行筛选分类。

引入人工干预，完成效果拼接。

求解步骤如下：（图3：问题三求解思路图）五、模型建立与求解5.1附件1中碎纸片拼接图片是否能拼接，重点要看边缘的吻合程度，于是我们首先给出定义：,{}m n P i 表示第i 个图所形成的矩阵的第m 行n 列对应灰度值，则第i 个图与第j 个图所分别形成矩阵的第m 行n 列的差的绝对值，即,,()()m n m n P i P j ρ=-记为第i 个图与第j 个图在边缘点(,)m n 的吻合参数，其中两张图在该点的吻合参数越低表示这两张图该点越吻合。

对于两图边缘列，则有1980,,72,11{}{}i j k k k P i P j ρ==-∑，为边缘的吻合参数，其中两张图边缘的吻合参数越低表示这两张图越吻合； 故，我们用作为全局的吻合参数，其中的限定条件为[][]i j i j A A ≠≠当时，具体求解过程如下：1）为将19张碎纸片拼凑成一幅完整图片，需对由每一张碎纸片转化得到的数字矩阵进行处理。

其中000图转化为矩阵{}1P ,001图转化为矩阵{}2P ，··· ，018图转化为矩阵{}19P 。

（见数据表1）2）第i 个图所形成的矩阵的第1列就是第i 个图的左边界，第72列表示第i 个图的右边界，列中数字的变化表示图边缘文字的灰度变化。

灰度是指黑白图像中点的颜色深度，范围一般从0到255。

白色为255，黑色为0。

将每个矩阵首列向量的每个元素相加求和，因为完整图片的左右边界均为空白，故求和数值越大代表空白越多，通过计算找出19个矩阵中，首列数字无变化的（即首列向量和最大的）矩阵为由008图所形成矩阵{}9P 。

则可确定008图为最后完整图的左边界。

3）再利用for 循环语句将矩阵{}9P 的最后一个列向量与另外每个矩阵的第一个列向量元素对应相减，会得到由每个元素差值组成的新向量。

再将得到的新向量中的每个元素的绝对值相加求和得到一个数值。

不妨将此求和所得数值称为两向量的吻合参数，记为ρ。

4）吻合参数最小的矩阵所对应的碎纸片即为第二张。

从而我们得到数学模型： 第二个图为：达到该最小值时所对应的矩阵为第i 个矩阵{}P i ，我们用2()t i =表示为所选出的第i 个矩阵的标码，以便后续求解；5）依据第二张碎纸片所对应矩阵的最后一列与其他矩阵第一列对应元素相减，再绝对值求和进行吻合参数的比较，从而第三个图为：达到该最小值时所对应的矩阵为第i 个矩阵{}P i ，我们用3()t i =表示为所选出的第i 个矩阵的标码，以便后续求解；以此类推:排序后的第j 个图为：1211980,1,72,1119,9,, (1){t}{}min j j t i j k k i i i t i t k P P i ρ---≤≤≠≠≠==-∑，达到该最小值时所对应的矩阵为第i 个矩阵{}P i ，我们用()j t i =表示为所选出的第i 个矩阵的标码；6）以此类推，第18个图为：172171980,17,72,1119,9,, (1){t}{}mintik k i i i t i t k P P i ρ≤≤≠≠≠==-∑，达到该最小值时所对应的矩阵为第i 个矩阵{}P i ，对应第i 个图为排序后第18个图，剩余的一个自然为最后一图即图片右边界。

通过实际拼接实践，我们可以知道，局部拼接复原结果即全局最优拼接复原结果。

最后我们得到附件1的拼接顺序：5.2附件2中碎纸片拼接附件2的处理办法与附件1相同，利用所有矩阵的第一列先找到所有碎纸片中的左边界，再根据吻合参数ρ确定碎纸片的拼接顺序。

最后我们得到附件2的拼接顺序：由于附件1和附件2中碎纸片的行高较高，所以在吻合参数的计算过程中相对误差很小，利用在MATLAB软件中编写的程序即可求出附件1和附件2所有碎纸片的正确拼接顺序，故在此问中不涉及人工干预。