?2552550???Ai??255220150?
?25500???矩阵的中元素表示该位置图片的灰度，255表示为白，0为黑，图片中信息为黑白文字
信息，但由于文字信息会存在阴影，所以矩阵中出现了介于0-255的元素。为了方便应用，并查阅相关资料所得，可以对于本题中的黑白图片做[2]二值化处理，可将上面例子中的Ai转化为如下的矩阵：
?001???Bi??011?
?011???其中白色用0值表示，非白色用1表示。
将附件1中的19张图片做如上处理得到各自的二值化后的矩阵Bi，矩阵均为
1980?72的矩阵，这里我们分别将每张图片的Bi矩阵第1列和第72列提取出来做一新
的二维边缘矩阵Ci，它是1980?2的矩阵。通过对所有图片矩阵的分析可以发现C6、C8矩阵中均有一列为0，所以可以认为编号为006和008的图片为原完整文件的一端，在做题过程中无需考虑会存在其他白边与白边拼接的情况。
两张图片匹配的原则可以根据下面的图1、图2来表示。
图1.图片未倒置 图2.图片倒置
如图1，当图片未出现倒置情况时，即题目中的图片均是正常摆放，将左边矩阵的第二列元素与右边矩阵的第一列元素进行两两匹配。记录元素相同的个数，个数除以1980为左边矩阵第二列对右边矩阵第一列的边缘匹配度，记为：
Dij?元素相同的数量
1980将所有碎纸片的二值化矩阵做如上匹配可依次选取与其匹配的碎纸片。
图1中左边矩阵第一列与右边矩阵第二列匹配的原则与上述相同，不再重述。
4
如图2，当图片出现倒置情况时，正常情况下应是左边矩阵的第二列元素与右边矩
阵的第一列元素进行两两匹配，若倒置后，则应该是左边矩阵的第二列元素与右边矩阵的第二列元素倒置顺序进行比较，同样记录相同元素的个数并计算匹配度。
图2中左边矩阵第一列元素与右边矩阵第一列元素的匹配原则与上述相同，不再重综合图一图二我们可以做出4个边缘匹配度的矩阵，即未倒置时矩阵第一列与其他述。
矩阵第二列的边缘匹配度、未倒置时矩阵第二列与其他矩阵第一列的边缘匹配度、倒置时矩阵第一列与其他矩阵第一列的边缘匹配度、倒置时矩阵第二列与其他矩阵第二列的边缘匹配度。由于（未）倒置时矩阵第一列与其他矩阵第二列匹配在思想上同（未）倒置时矩阵第二列与其他矩阵第一列匹配相同，所以这里只需考虑其中一种情况即可。
任选其中一例说明，由于碎纸片倒置情况未知，需要考虑未倒置时的情况与倒置式的情况，未倒置时矩阵第一列与其他矩阵第二列的边缘匹配度矩阵第一行最大值与倒置时矩阵第一列与其他矩阵第一列的边缘匹配度第一行的最大值进行比较，选取匹配度大的作为拼接的纸片，即编号为000的碎纸片要与该纸片拼接。以此类推把19张碎纸片拼接完成后做人工处理。
4.1.2英文碎纸片的复原分析
将附件2的19张图片做4.11中处理得到二值化后的矩阵Bi，矩阵均为1980?72的矩阵，这里我们分别将每张图片的Bi矩阵第1列和第72列提取出来做一新的二维边缘矩阵Ci，它是1980?2的矩阵。通过对所有图片矩阵的分析可以发现C3 、C4矩阵中均有一列为0，所以可以认为编号为003和004的图片为原完整文件的一端，在做题过程中 无需考虑会存在其他白边与白边拼接的情况。
做如上判断后解题过程同4.11。
4.2问题二的分析
4.2．1中文碎纸片的分析
此问中同4.1的图片处理方法，也需要将209张碎纸片进行同样的图像处理转化为灰度矩阵后进行二值化处理得到处理后的矩阵。根据结果知此问中的图片转化后的矩阵为72?180的矩阵，列数由第一问中的1980变为180，虽然数量变少，但是图片数量由19张变为了209张。若同样使用4.1中的边缘匹配的方法，一张碎纸片对应其他208张碎纸片的边缘匹配相同的像素点有208种情况，变化范围为0-180，可知若直接采用4.1中的方法得到的结果可能出现多个相同或无法判断的情况，所以这里我们先考虑附件3中碎纸片的特性。
观察下面的图3可以发现，通过查阅资料分析[2]基于文字特征的文档碎纸片半自动拼接，每一行的绝大多数中文文字均可认为拥有同一上界、同一下界（图3最右端出现了“一”字，但是同行还存在其他文字，可以认为同一行文字有同一上界与同一下界），
5
我们可以根据这一特性使用软件将[3]匹配度高及位置相同的碎纸片归类为一组。方法为：搜索每一张碎纸片转化后二值化矩阵Ci的每一行，若矩阵该行中存在数值1，则将该行全部赋值为1，若这一行元素全为0，则将该行全部赋值为0，其中1表示本行存在灰度小于255的像素，0表示不存在灰度小于255的像素，这样将209张碎纸片做出[4]新的二值化矩阵Ei，之后同4.1的分析取边缘做边缘匹配得修改后的[6]边缘匹配度矩阵
D，匹配度高则说明碎纸片的文字信息处于同一水平位置，见下图图4，之后再人工干
预，得到较优的结果。
图3.处理的图片
图4.再次处理后的图片
得到很多组有相同位置的的碎纸片后，在每一组内采用4.1的中的边缘匹配方法，这里为了防止出现两白边匹配造成碎纸片连接混乱的现象，要加以限制。方法为：若在组内做边缘匹配出现匹配度为1的情况，则暂时不连接此碎纸片，从剩余的碎纸片出发做边缘匹配与其他碎纸片连接，直到组内所有碎纸片均已覆盖。
这样再通过一定的人工干预可以得到拼接复原后的的11横行碎纸片，在同样使用
6
4.1的边缘匹配方法，[7]将得到的11行的碎纸条的长边进行边缘匹配做出11?11的匹配度矩阵后找最大匹配度作为连接的碎纸条，同样为了防止出现两白边匹配造成碎纸片连接混乱的现象，要加以限制。方法为：若在组内做边缘匹配出现匹配度为1的情况，则暂时不连接此碎纸片，从剩余的碎纸片出发做边缘匹配与其他碎纸片连接，直到11张拼接后的碎纸片均已覆盖。最后加以人工处理，得到完整的原文件。
4.2.2英文碎纸片的分析
同4.2.1中的分析相同，通过观察我们可以发现碎纸片的英文在位置上也有一定的规则可循。如下图图5。
图5.演示的图片
可以发现英文字母的主要的部分拥有同一上界和同一下界，但是跟中文不同，英文中会出现一些“y”、“b”之类的字母，为了同样使用4.2.1中的方法我们通过观察附件4中图片的像素情况，将图片中每一行中黑色像素数少于13的及字母的次要部分转变为二值化矩阵中的0，将每一行中黑色像素大于等于13的及字母的主要部分转化为二值化矩阵中的1，这样得到的新的二值化矩阵Ei，可认为图像转变为图6的方式，同样使用4.2.1中的分析方法将新的二值化矩阵做边缘匹配，匹配度高的可以认为两碎纸片在原纸张中位于同一行，把匹配度高于0.9的元素分为一组后，对每一组进行边缘匹配。
由于考虑到英文字符的情况，在4.1的基础上，我们对于组内图片原始二值化矩阵的边缘匹配度矩阵D每一行的搜索，在这里我们若矩阵的任意一行中出现匹配度大于0.9的元素个数超过2个，我们加以人工干预，根据文章的格式、内容选择应该连接的碎纸片，其他过程与4.1相同，区别仅为本文中需要对软件执行过程进行人工干预，其他相同的步骤不在重述。
7
图6.演示图片
4.3问题三的分析
本问在问题二英文碎纸片的基础上还需要考虑纸片是否处于同一面，虽然数据量增加了一倍，但是判断碎纸片是否连接的标准由一面增加到了两面。本不对应的两张碎纸片一面的拼接复原情况好而令一面复原情况也好的情况只是个别的案例，所以可以将碎纸片两面边缘匹配度之和作为评判两张是否匹配的标准建立边缘匹配度之和矩阵F，在这里可以先认为匹配度之和高于1.9的情况为匹配结果优秀。若仅将匹配度之和作为评判标准，基于4.2.2中的求解过程，英文碎纸片的纯计算机复原结果较差，所以还需要在计算机匹配碎纸片的过程中每一步都要进行人工干预判断、选择。
以纸片000与001为例，匹配方式可能为：
000a???001a?①： ?000b???001b?②：
000a???00b1?③： ?000b???00a1?④：为了找出碎纸片如何对应，则将①②的边缘匹配度相加得到边缘匹配度之和，将③
④的边缘匹配度相加得边缘缘匹配度之和，两者的和做出比较。若仅有一个大于等于1.9，则计算机输出该匹配度，人工判断是否碎纸片是否匹配；若两者均大于等于1.9，计算机把两个匹配度之和输出，人工选择判断碎纸片应是否匹配与如何匹配；若两者均小于1.9，则计算输出最大者，人工判断碎纸片是否匹配。
若出现计算机给出的结果人工判断后发现匹配错误，则记录当前匹配成功的碎纸片上述的结果可以得到一些在同一横行的碎纸片的拼接，再次根据这些新的碎纸片的信息并在剩下的碎纸片中重新开始计算机匹配与人工判断。
边缘匹配度之和的情况通过上述人机结合的方法拼出11张横行的碎纸片，剩下的就是应该如何把11张横行的碎纸片拼接成完整的一份纸张，这里将11张横行碎纸片的上下长边进行两两匹配，以两面边缘匹配度之和的方法按照上述的方法将11横行的碎纸片拼接完毕。
8