碎纸片拼接与复原摘要本文讲述的是碎纸片拼接复原的问题。

碎纸片拼接复原在情报和考古方面用的较多，有很大的使用价值。

在实际操作中，人工拼接的准确度极高，但随着碎片数量增大，拼接难度将大大提高，这时必须借助计算机来处理，最后辅以人工干预来完成。

针对本文提出的问题，我们的模型不区分文字语言，把图像的灰度值作为建立模型的关键切入点。

使用matlab里的imread函数读入BMP图像，并取得其灰度值矩阵，矩阵中每一元素为图像每一像素的灰度值，通过对其边缘的灰度值进行匹配，求出其拼接顺序。

本文中匹配这一步骤采取求图片两边的一列像素灰度值进行求差绝对值，并将求其均值最小作为匹配原理，匹配度必须小于0.1。

第一问中只涉及到单面碎纸片，而且仅把单张纸进行纵向切碎成规则长条状，所以只需对其左右端像素的灰度值进行采集，然后进行匹配，将匹配度最高的两边连起来。

不过有两条纸的左边和右边全为白色，则将其单独列出来，作为复原后纸张的左右端，最后进行人工校正。

第二问中的纸片数量增多，且涉及到横纵同时切碎的纸片，所以不能直接沿用第一问的方法。

但通过观察，横切出的每一横条上碎纸片文字具有明显的共同点，可以进行快速匹配。

首先确定出第一行，通过寻找灰度矩阵最上面全为255的行数最多的图像，作为拼出第一行的碎片。

再用与刚才相似的方法，不过须取列为255最多的图片作整个复原图第一列。

最后从第二行第二个开始，从左至右从上到下依次匹配上碎片，最后结果需进行人工校正。

第三问由于涉及到双面纸的问题，可以继续沿用第二问的方法，不过拼接标准需要改为两面灰度值匹配度之和，将纸片拼接好后，最后再人工检查其是否拼接完全正确。

此模型还可用于彩色图像的拼接，用RGB颜色系统，同样是导出每一像素的RGB 值，构成矩阵，用与文中相似的办法进行破碎彩色图像的拼接。

关键词：拼接复原图像处理灰度值矩阵匹配1 问题重述B题碎纸片的拼接复原破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

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

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

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

所述问题如下：1. 来自同一页的印刷文字在经过碎纸机纵切以后等到的长条碎片，进行计算机自动拼接复原，并给出相应模型和算法。

此题的内容在附件1和附件2，分别为中英文。

在需要人工干预的地方，写明干预方法与干预的时间点。

复原结果用图片和表格形式分别表达。

2.来自同一页的印刷文字在经过碎纸机横纵切以后等到的小矩形碎片，进行计算机自动拼接复原，并给出相应模型和算法。

此题的内容在附件3和附件4，分别为中英文。

在需要人工干预的地方，写明干预方法与干预的时间点。

复原结果用图片和表格形式分别表达。

3.上述两问都是单面打印的情况，而此问涉及双面打印的纸张。

来自同一页的双面印刷文字在经过碎纸机横纵切以后等到的长条碎片，进行计算机自动拼接复原，并给出相应模型和算法。

此题的内容在附件5，只有英文。

在需要人工干预的地方，写明干预方法与干预的时间点。

复原结果用图片和表格形式分别表达。

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

2 模型假设1、假设所有碎片均完整，并且不出现破损，污损情况。

2、假设纸片在扫描时全为正向扫描，无反方向纸片。

3、假设所有问题给出的碎片均能拼出完整的纸张。

4、假设题目中碎片与真实纸张物理性质相同。

5、假设纸张内容有意义。

3 符号说明4.1 问题一4.1.1理论部分对于这道题，只涉及到纵切的碎片，我们建立模型不区分英文字和中文字（下两问同），并使用求样本均值作为求匹配度关键方法。

⨯⨯，矩阵元素的位置用三维首先需要一个三维的碎片矩阵A，其大小为19807219⨯的复原图矩阵B。

首先需要用imread 直角坐标Oxyz表示，还要一个大小为19801368⨯Oyz矩阵，函数读出碎片的灰度值矩阵，放入A中，每一个碎片占一个二维的198072记为i A，一共19张图，用19个这样的二维矩阵表示，于是构成三维矩阵A。

复原图矩阵B是将碎片的灰度值矩阵按正确的顺序拼接而成的矩阵，也就是最终复原图的灰度值矩阵。

拼接的第一步是要确定最左边的一条碎片，由于只纵切的话，切口几乎都会把部分字切开，所以这里需要做的是扫描矩阵A 的Oxz 第一子矩阵，如果有一列全为255，那么此列所在的二维的198072⨯Oyz 矩阵即为复原图最左边的碎片的灰度值矩阵*i A 。

然后将*i A 的数值读入到复原图矩阵B 的第1列到第72列。

接下来要依次拼接上其他的碎片。

假设碎片矩阵A 中的子矩阵i A 已经拼接上，此时要寻找下一块能够拼接上的碎片，假设为j A 。

此时就需要进行匹配，在此情况的匹配过程中需要先取出已拼接上的子矩阵i A 的最右边第72列的灰度值，并依次取出碎片矩阵A 中剩下的未拼接上的子矩阵的最左边既第1列数值，如图示。

255224199176186203i ⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪= ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭A255223204165198231j ⎛⎫⎪ ⎪ ⎪⎪ ⎪= ⎪⎪ ⎪ ⎪⎪ ⎪⎝⎭A如图中给出的例子，左边矩阵为上一次拼接上的矩阵取出其第72列的部分数值，右边矩阵为剩下的某一矩阵并取出其第一列的部分数值。

接下来就是匹配过程。

匹配过程遵循以下式子：19801((,1)(,72))1980jik j k k v =-=∑A A然后取这个均值j v 最小的矩阵j A 作为新的一个最佳匹配矩阵，若有两个最小值相等，那么程序报错，并进行人工干预，选择其中最适合的碎片。

最后将最佳匹配的碎片矩阵j A 读入到上一次更新后的复原图矩阵B 相应的位置即可。

然后将上述步骤重复，直到复原图矩阵B 被填满，然后用imshow 函数将复原图输出得到碎纸片拼接后的完整图片。

4.1.2结果分析中文图片程序输出排序结果为：的碎片排序依然是可直接使用计算机的输出结果，不需要人工干预，下面是排序的结果：4.2问题二4.2.1理论部分第二个问题涉及到横纵向都切的纸片，不能单纯地移植上一问的模型和算法，但其建模思想和算法核心是不变的，只是多了一点步骤而已。

并且每一个纸片形状相同，那么同样构造一个三维的碎片矩阵A ，其大小为18072209⨯⨯，依旧一个大小为19801368⨯的复原图矩阵B 。

复原图矩阵B 与碎片矩阵A 的作用和上一问均相同，只是碎片矩阵A 的尺寸有所变化，根据碎片的尺寸和数量而变。

步骤一：那么建立此问题模型的第一步是确定组成复原图第一行的碎片及其顺序。

首先要搜索出组成第一行的碎片，遍历碎片矩阵A 的最上面一个矩阵，既Oxy 面的第一个矩阵，找出整个Oy 一行值全为255的碎片灰度值矩阵i A ，然后从这些矩阵当中，再从第一行开始遍历一次，直到遇到某一行有不为255的值时终止，选择出含有值全为255的行且行数量最多的那些碎片，他们即为组成第一行的碎片。

然后从这些碎片中，找出最左边的一个，也就是整个复原图最左上角的那个碎片。

由于这次加入了横切，那么很有可能有些非边缘的碎片其左右边会出现一列白色的情况，那么就仿照上面一步，扫描整个第一行的碎片，从他们灰度值矩阵i A 的第一列开始扫描。

因为在边缘的碎片由于页边距会产生较大的空白，所以扫描到某列开始出现非255数值为止，全为255列数最多的碎片即为左边的碎片。

接下来此行的匹配仿照上一问，使用下式求匹配度1801((,1)(,72))180jik j k k v =-=∑A A并选择匹配度最小的进行匹配。

每匹配上一个碎片就将其的灰度值矩阵i A 读入到复原图矩阵B 的相应位置。

步骤二：第二步就是确定整个复原图的第一列的碎片。

通过第一步我们已经确定了此列的第一个碎片，下面就是用原来的方法进行匹配，拼接出第一列只不过原来是左右拼接，现在只需改成上下拼接即可。

匹配上以后就将其的灰度值矩阵i A 读入到复原图矩阵B 的相应位置。

255223204165183i ⎛⎫= ⎪⎝⎭A234199203201187j ⎛⎫= ⎪⎝⎭A匹配度计算公式如下：721((1,)(180,))72jik j k k v =-=∑A A图例如下：步骤三：确定了第一行和第一列以后，第三步就要把其他碎片填进去。

这一步需要把匹配度的计算方式作一定更改，取为平均匹配度j v 。

由于我们是将剩下的碎片一块一块由左至右由上到下拼接上，于是我们要同时知道该碎片的上边缘ju v 和左边缘jl v 的匹配度，由两个匹配度来判断是否能匹配。

然后再取这两个匹配度的均值既平均匹配度j v 。

然后取j v 最小的作为最佳匹配碎片。

每匹配上一个碎片，就将其的灰度值矩阵i A 读入到复原图矩阵B 的相应位置。

三个变量的计算公式如下：7211801((1,)(180,))72((,1)(,72))180jiuk ju jilk jl k k v k k v ==⎧-⎪⎪=⎪⎨⎪-⎪=⎪⎩∑∑A AA A ，2ju jlj v v v +=匹配过程如图示：255223204165183iu ⎛⎫= ⎪⎝⎭A255224199176186203il ⎛⎫ ⎪ ⎪ ⎪ ⎪⎪= ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭A 234199203201187255223204165198231j⎛⎫⎪ ⎪⎪ ⎪ ⎪= ⎪ ⎪ ⎪⎪ ⎪ ⎪⎝⎭A按照上述步骤，先分别循环完第一步和第二步，最后循环第三步，即可得到完整的复原图矩阵B ，然后和上问一样，使用imshow 函数将其输出即可得到复原后的拼接图像。

4.2.2结果分析中文图片程序输出排序结果为：从最后的图像结果看来，不需要更改计算机一次显示的结果，说明拼接是正确的。

英文的碎片排序依然是可直接使用计算机的输出结果，不需要人工干预，下面是排序的结果：4.3问题三4.3.1理论部分这个问题只涉及到英文的纸片，不过却是双面的，那么可以沿用上一问的方法，不过需要进行一些改进。

这次要构造两个三维的碎片矩阵a A 和b A ，其大小均为18072209⨯⨯，两个大小为19801368⨯的复原图矩阵a B 和b B 。

开始读入的时候，将文件名有a 和b 的碎片图像，用imread 函数分别按数字顺序读入到碎片矩阵a A 和b A ，接下来进行几个步骤，这里的人工检查会多一点。