碎纸片拼接复原(国一)

1、基于分治算法碎纸片的拼接复原模型摘要本文针对不同切割方式碎纸片的拼接问题，通过对图像数字化处理得到灰度矩阵，建立了复原模型并得到复原后的图像。针对单面仅纵切碎纸片的拼接问题，根据完整文件最左边部分无文字的特点，运用matlab编程可确定出第一张碎纸片。随后，根据贪婪算法的思想，以确定位置的碎纸片与剩余未拼接碎纸片相邻边缘灰度值的平方欧氏距离最短为目标函数，可逐步求得碎纸片的拼接顺序,进而将其复原.中文碎纸片顺序为：8、14、12、15、3、10、2、16、1、4、5、9、13、18、11、7、17、0、6；英文碎纸片顺序为：3、6、2、7、15、18、11、0、5、1、9、13、10、8、12

2、、14、17、16、4。本问碎纸片拼接过程没有人工干预，实现了全自动化的拼接。对于既横切又纵切碎纸片拼接问题，本问采用分治算法的思想，先对中、英文碎纸片分别层次聚类分析，将最可能位于同一行的碎纸片归为同一类，其中中文碎纸片分为11类，英文碎纸片分为10类；再对分类后的碎纸片使用编程加人工干预的半自动拼接方式，得到11块仅横切的碎纸片块；最终对得到的11块仅横切的碎纸片块进行类间拼接，实现文件的复原。中文碎纸片第一列顺序为：49、61、168、38、71、14、94、125、29、7、89；英文碎纸片第一列顺序为：191、201、86、19、159、20、208、70、132、171、81。此问

3、中有两次人工干预的过程，第一次位于类内拼接处，第二次位于类间拼接处。中文文件总共干预了33块，英文文件总共干预了40块。考虑双面碎纸片拼接问题时，本问延续了分治算法的思想。由于每张碎纸片含有正反两面，在聚类分析时，可将正反两面的灰度值相加为一列特征值作为它们是否可能位于同一行的依据，进而将双面碎纸片分为9类。再对这9类碎纸片使用编程加人工干预的半自动拼接方式，得到22块仅横切的碎纸片块；最终对这22块仅横切的碎纸片块进行类间拼接，实现文件的复原。复原后文件第1面第一列顺序为：136a、5b、143a、83b、90b、13b、35b、172b、105b、9a、54b；复原后文件第2面碎纸片第一列

4、顺序为：78b、89a、186b、199b、88b、114a、146a、165b、3b、23b、99a。此问中有两次人工干预的过程，第一次位于类内拼接处，第二次位于类间拼接处。【关键词】：碎纸片复原 贪婪算法 平方欧氏距离 分治算法 层次聚类分析 一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下三个问题：问题一：对于给定的来自同一页印刷文字文件的碎纸机破

5、碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达，表格为复原后碎片序号。问题二：对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。问题三：上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的

6、碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、问题分析本文针对的是形状相似碎纸片的拼接问题，需提出相应的拼接模型与算法并对给定的碎纸片进行复原。常规文档碎纸片计算机拼接方法一般利用碎片边缘的尖点特征、尖角特征、面积特征等几何特征，搜索与之匹配的相邻碎纸片并进行拼接，根据题意可知，本文所研究的碎纸片形状相似，这种基于边界几何特征的拼接方法并不适用于边缘形状相似的碎纸片。碎纸片拼接时如果只利用碎片的边界特征，拼接效果并不理想。本文在实行拼接过程时，不但考虑了待拼接碎纸片边缘是否匹配，还考虑了碎片内字迹断线与文字是否匹配【3】。问题一

7、是解决来自同一页且被纵向切断的碎纸片拼接问题。该问题本质上属于碎纸片组合优化问题。如何实现碎纸片的最优组合成为本问以及本文的一个难点。可考虑碎纸片内文字的特点。由于大多数文字文档的文字行方向和表格线方向平行且单一，如果碎片内的文字行或表格在碎片边缘断裂，那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行或表格，凭此特征可以很容易地从形状相似的多碎片中挑选出相邻碎片。因文字行或表格线的高度特征、间距特征的识别比字迹断线识别和文字图像的理解实现起来要容易得多，利用碎片内文字行特征或表格特征拼接形状相似的碎纸片是可行的。运用贪婪算法的思想，现考虑以下的拼接过程：（1）根据碎纸片内文字特点找

8、出第一张碎纸片，即该页的最左边那一张碎片；（2）根据第一张碎纸片，依次找出后面的碎纸片，直到组合完19张碎纸片。问题二是针对同一页但被横、纵向切断的碎纸片拼接问题。相对于第一问的不同，本问的碎纸片是即横切又纵切的情况，这增加了问题的难度。如果继续采用问题一中拼接碎纸片的步骤，在实现过程中会发现，要找出位于完整纸片最左边的碎纸片，将会无法实现。因为我们是根据完整纸片最左边内容为空白这一特征对碎纸片进行的筛选。但由于纸片被横、纵切，很有可能切断位置并未在文字上，而是位于文字间的空隙，这样本来位于复原后中间部分的纸片很有可能变为位于最左边的纸片，将会对碎纸片拼接复原带来错误。由于纸片被分为209张碎

9、纸片，如果对其直接编程复原拼接，碎纸片数量较大，难以实现。可引入分治算法的思想，将该问题分解为便于求解的子问题。考虑到图像在经过数字化后位于同一行的文字灰度值分布相似，可根据这一特点对碎纸片进行聚类分析。再由聚类分析的结果，实行类内拼接，最终人工微调，实现碎纸片的拼接复原。问题三是针对来自同一页但正反面均印有文字的碎纸片拼接问题，该问题可看成对前面两问的拓展。因此，在模型的建立和求解过程中，可以借助于前两问的模型。该问题相对于前两问的难点在于题目只给出了碎纸片的正反面内容，并未告知哪些碎纸片属于同一面。现在碎纸片数量为438张碎纸片，想要直接判别哪些碎纸片属于同一面难度较大。可考虑借助与问题二

10、中将碎纸片聚类的思想，先将碎纸片进行分类，分类后在同一类内碎纸片互相拼接，结合人工干预，得到碎纸片拼接复原图并确定出碎纸片正反面。三、模型假设1、 同一附件中的碎纸片来自于同一页文件，且未缺失；2、 假设碎纸片模型为理想模型，碎纸片厚度为零；3、 碎纸片表面光滑平整无磨损且无污点；4、 假设破碎纸片边缘完好无缺损。四、符号说明符号含义碎纸片数字化后第张纸片的第行第列数据，即该点灰度第张纸片的最后一列与第张纸片第一列第行数据平方欧氏距离未匹配碎纸片的集合第类碎纸片离差平方和五、建模前的准备图形的数字化【2】本文是根据碎纸片内文字行特征来进行判定碎纸片的拼接。故现在的关键是提取碎纸片内的文字信息。

11、这就不得不提到matlab对图形的处理方法，即图形的数字化。图形的数字化是将连续色调的模拟图像经采样量化后转换成数字影像的过程。一幅图像可以定义为一个二维函数，其中和是平面坐标，在坐标点处的振幅称为图像在该点的亮度。黑白图像的亮度用灰度来表示，而彩色图像是由单个的二维图像组合而成的。图像的数字化过程如下面的流程图1所示：图形的采样量化开始图形灰度值矩阵图1 图形的数字化流程图根据上图1图形数字化流程图，对以上步骤进行具体解释：（1）图形的采样图形的采样即要求要用多少点来描述一幅图像，采样结果质量的高低用图像的分辨率来衡量。简单来讲，对二维空间上连续的图像，在水平和垂直方向上等间距地分割成矩形网

12、状结构所形成的微小方格称为像素点。一幅图像就被采样成有限个像素点构成的集合。本题中所给碎纸片为bmp格式，运用matlab程序读取后，该图像数字化为个像素点。（2）量化量化即要求使用多大范围的数值来表示图像采样之后的每一个点。量化的结果是图像能够容纳的颜色总数，它反映了采样的质量。本文采用8位储存一个点，即相当于黑-白间可用0-255个状态进行描述，其中量化后的值越接近0，则表示该点的实际颜色越接近黑色；相反量化后的值越接近255，则表示该点的实际颜色越接近白色。由破碎图片的数量可知，本题中的复原图像经过采样和量化后的结果是一个实数矩阵。由采样过程可知，该矩阵大小为。matlab中读入图像的数

13、据类型为unit8，而在矩阵中使用的数据类型为double。因此，要把图像经相应程序读入后的矩阵中的值转换成double精度类型；如果不转换，在对unit8进行加减时会产生溢出。现一幅图像经过采样、量化与数据转换三个步骤后，该数字图像在matlab中可以很自然地表示为矩阵，如下面矩阵所示：矩阵中各元素值即灰度满足条件为：其中，。六、模型的建立与求解6.1 被纵切后碎纸片的拼接复原模型本问是解决来自同一页且被纵向切断的碎纸片拼接问题。该问题本质上属于碎纸片组合优化问题。由于所给碎纸片形状相似，无法使用尖点特征、尖角特征、面积特征等几何特征来实现碎纸片的拼接。可考虑碎纸片内文字的特点。文字文档的文

14、字行方向和表格线方向平行且单一，如果碎片内的文字行或表格在碎片边缘断裂，那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行或表格，凭此特征可以很容易地从形状相似的多碎片中挑选出相邻碎片。因文字行或表格线的高度特征、间距特征的识别比字迹断线识别和文字图像的理解实现起来要容易得多，利用碎片内文字行特征或表格特征拼接形状相似的碎纸片是可行的。但考虑到计算机对图像拼接问题的缺陷，可在拼接过程中适当的加人工干预的过程。6.1.1 被纵切后碎纸片的拼接复原模型的建立（一） 碎纸片特征分析由于本问是根据碎纸片内相应的文字信息来进行拼接。碎纸片内文字信息包含字体的大小、高度以及亮度等内容。为了将碎纸

15、片内文字的信息提取出来，对碎纸片进行数字化处理。该过程并不复杂，只需运用matlab相应的程序即可。在将图片输入到matlab中时，图片是以的矩阵存在于matlab软件中。每一点值的大小是由该点颜色所决定。经过数据的量化与转换后，该值大小为0-1。其中该值越接近0，则表示该值所对应点的实际颜色越接近黑色；相反该值越接近1，则表示该点的实际颜色越接近白色。（二） 贪婪算法思想本问采用贪婪算法的部分思想，实现19张仅纵切碎纸片的拼接复原。贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，通过每一步贪心选

16、择，可得到问题的一个最优解。本问根据碎纸片内文字特点找出第一张碎纸片，即该页的最左边那一张碎片。在找到第一张碎纸片后，运用贪婪算法的思想，在剩余18张碎纸片内求最优解，寻找与第一张碎纸片匹配的碎纸片；依此类推，逐步寻找第张碎纸片的匹配纸片，直到19张碎纸片均被匹配。（三）平方欧氏距离定义将19张碎纸片经matlab数字化后得到19个的矩阵。根据附件中碎纸片的编号顺序将19个矩阵合并为一个大小为的矩阵，矩阵中的值，即像素，取值为0-1。其中该值越接近0，则表示该值所对应点的实际颜色越接近黑色；相反该值越接近1，则表示该点的实际颜色越接近白色。该矩阵如下所示：矩阵中各元素值即灰度满足条件为： （6

17、.1.1）其中，。假设第张纸片的第行第列数据为，其中： （6.1.2）当与分别对应于第张纸片数字化后所对应矩阵的第一列与最后一列。令为第张纸片的最后一列与第张纸片第一列第行数据的平方欧氏距离，该值为： （6.1.3）（四）碎纸片拼接模型为了寻找已经确定好位置的第张碎纸片最相匹配的碎纸片，根据图2碎纸片拼接流程图可知，即要求确定好位置的第张碎纸片最后一列与其拼接碎纸片的第一列平方欧氏距离总和最小，数学表达式如下： （6.1.4）根据前面的分析过程，本问借助了贪婪算法的思想。现根据目标函数作最优选择，每做一次贪心选择就将未实现拼接的碎纸片集合。为未匹配碎纸片的集合。集合中碎纸片数量为：。（五） 拼

18、接流程现提取碎纸片所对应的矩阵的第一列与最后一列数据。由于本问讨论的是纸片仅被纵切的情况，分析可发现第一张碎纸片（未被纵切前最左边那张碎纸片）最左边边缘部分均为白色，经数字化处理后所对应矩阵的第一列数据值相同，为1。可根据该特点确定该碎纸片。在确定完第一张碎纸片后，计算第一张碎纸片的最后一列数据与其他18张碎纸片所对应矩阵的第一列数据的距离总和，该距离采用平方欧氏距离。当该距离总和最小时，该张碎纸片即与第一张匹配。因为未被纵切时，图形在水平与垂直方向上的灰度（即亮度）是连续变化的。若两张碎纸片可实现拼接时，第一张碎纸片最后一列数据与其匹配那张碎纸片第一列数据对应连续变化，即两组数据对应的平方欧

19、氏距离总和最小。在确定了第二张碎纸片后，可根据上述方法依次找出后面的17张碎纸片拼接次序。碎纸片拼接流程图如下图2所示：图2 碎纸片拼接流程图6.1.2 被纵切后碎纸片的拼接复原模型的求解现根据matlab编程求解，可得到复原后的图片以及相应的表格。中文与英文复原后图片见附录1与附录2。将中文碎纸片序号按复原后顺序填入下表1，英文填入下表2。表1 中文碎纸片序号按复原后顺序表（纵切）复原后碎纸片序号（中文）008014012015003010002016001004005009013018011007017000006表2 英文碎纸片序号按复原后顺序表（纵切）复原后碎纸片序号（英文）00300

20、6002007015018011000005001009013010008012014017016004根据模型建立过程中第一张碎纸片的确立方法，即编程寻找19张碎纸片数字化所对应矩阵的第一列数据为1的碎纸片。由上面两表可看出中文第一张碎纸片为008，最后一张碎纸片为006；英文第一张碎纸片为003，最后一张碎纸片为004。6.1.3 结果分析本问使用matlab编程，将碎纸片数字化处理，得到灰度值矩阵。提取该矩阵中相应信息，即文字行或表格线的高度、间距等特征，运用计算机实现智能拼接。分析上述过程可发现，本问并未有人工干预，实现了理想的自动化碎纸片拼接过程。6.2 被横、纵切后碎纸片的拼接复原

21、模型6.2.1 被横、纵切后碎纸片的拼接复原模型的建立相对于第一问的不同，本问的碎纸片是即横切又纵切的情况，这增加了问题的难度。如果继续采用问题一中拼接碎纸片的步骤，将很难实现。因为我们是根据完整纸片最左边内容为空白这一特征对碎纸片进行的筛选。但由于纸片被横、纵切，很有可能切断位置并未在文字上，而是位于文字间的空隙，这样本来位于复原后中间部分的纸片很有可能变为位于最左边的纸片，将会对碎纸片拼接复原带来错误。由于纸片被分为209张碎纸片，如果对其直接编程复原拼接，碎纸片数量较大，难以实现。在求解该问题时，由于该问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法

22、直接求出。对于这类问题，可先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。分治算法一般解题步骤为：（1）分解，将要解决的问题划分成若干规模较小的同类问题；（2）求解，当子问题划分得足够小时，用较简单的方法解决；（3）合并，按原问题的要求，将子问题的解合并构成原问题的解。现引入分治算法思想，根据其解题步骤，划分以下三步来实现碎纸片的拼接复原：（1）分解：将碎纸片数字化后矩阵的灰度值作为评判指标，运用层次聚类法对209张

23、碎纸片进行聚类；（2）求解：由聚类所得结果，运用贪婪算法对同类碎纸片进行拼接；再由拼接结果，人工干预得到11张仅被横切的碎纸片；（3）合并：对11张仅被横切的碎纸片运用模型一中的方法实现整张纸片的拼接复原。 碎纸片的层次聚类【4】一幅黑白照片，它在水平与垂直方向上的亮度变化是连续的，在经过数字化后，即表现为它所对应矩阵的灰度值取值是连续的。进而可以了解到，若两张碎纸片位于复原文件中同几行时，那么其对应矩阵灰度值在纵向上分布近似，可根据这一特点对碎纸片进行聚类分析。层次聚类分析是根据观察值或变量之间的亲疏程度，将最相似的对象结合在一起，以逐次聚合的方式，它将观察值分类，直到最后所有样本都聚成一类

24、。本问需对209张碎纸片进行分类，属于对样本（个案），即Q型聚类。Q型聚类使具有共同特点的样本聚齐在一起，以便对不同类的样本进行分析。将209张碎纸片经matlab数字化后得到209个的矩阵，将矩阵进行行相加运算，得到209个的列向量，对应于分别评判209张碎纸片的180个指标。现采用平方欧氏距离测度样本间距离，可将209个碎纸片样本看为维空间中的点，维数代表描述样本的指标数，第张碎纸片与第张碎纸片间距离为，维平方欧氏距离公式为： （6.2.1）选用 法计算类间的距离。设第类碎纸片离差平方和为；第类碎纸片离差平方和为；表示第类碎纸片的集合；表示第类碎纸片的集合。 （6.2.2）其中， （6.2

25、.3）表示第类碎纸片的数量，表示第类碎纸片的数量。现定义： （6.2.4）事实上，若，内部碎纸片间距离很小，则它们能很好地各自聚为一类，并且这两类又能够充分分离（即很大），这时必然有很大。因此，按定义可以认为，两类，之间的距离很大。 碎纸片类内拼接（一）类内拼接模型的建立在经过碎纸片的聚类后，假设将碎纸片分为了类，第类所含碎纸片数量为，的取值为。现需对这类碎纸片进行类内拼接。拼接规则借助模型一中碎纸片拼接模型目标函数。将209张碎纸片经matlab数字化后得到209个的矩阵。矩阵中的值，即像素，取值为0-1。其中该值越接近0，则表示该值所对应点的实际颜色越接近黑色；相反该值越接近1，则表示该点

26、的实际颜色越接近白色。该矩阵如下所示：矩阵中各元素值即灰度满足条件为：其中，。假设第张纸片的第行第列数据为。令为第张纸片的最后一列与第张纸片第一列第行数据的平方欧氏距离，该值为： （6.2.5）为了寻找与第张碎纸片相匹配的碎纸片，那么第张碎纸片最后一列与其拼接碎纸片的第一列平方欧氏距离总和最小，数学表达式如下： （6.2.6）由贪婪算法的思想，现根据目标函数作最优选择，每做一次贪心选择就将未实现拼接的碎纸片集合。为未匹配碎纸片的集合。集合中碎纸片数量为：。上述拼接过程会无条件的拼接下去，直到第类碎纸片中张碎纸片被拼接完成。很显然，这样的拼接过程是错误的。我们需知道何时拼接结束，因此定义无效匹配

27、碎纸片。无效匹配碎纸片即该张碎纸片在上述拼接方式下，有两张以上的碎纸片与之匹配。无效匹配碎纸片共分为三类，如下图3所示：图3 无效匹配碎纸片第一类：碎纸片左边缘或者右边缘无内容，即为空白；第二类：碎纸片左边缘或者右边缘刚好以字结束，即字全部存在于碎纸片中，它的匹配碎纸片边缘无内容；第三类：碎纸片边缘空白部分占大多数，有文字部分占少数，该类无效匹配碎纸片多存在于英文碎片中。因此，根据上述分析，按照正确的拼接方式，与第张碎纸片相匹配的碎纸片满足以下数学表达式： (6.2.7)其中，为未匹配碎纸片的集合，为第一类无效碎纸片集合，为第二类无效碎纸片集合，为第三类无效碎纸片集合。类内拼接过程分为以下三步

28、：Step1：由模型一思路，先找出第类碎纸片中第一张碎纸片，然后根据贪婪算法的思想，按照上述碎纸片匹配规则，依次找出后面的拼接碎纸片，直到找到无效匹配碎纸片结束；Step2：在步骤1完成后，第类碎纸片集合中会有少数量的碎纸片未被拼接。令剩余未被拼接碎纸片中序号最小的碎纸片为中心纸片，按照上述拼接规则，对该中心纸片与剩余纸片进行匹配，直到找到无效匹配碎纸片结束。依此类推，直到第类碎纸片集合中所有碎纸片都进行了匹配；Step3：完成上面两步后，得到了计算机不能再横向拼接的碎纸片块。现进行人工干预，拼成11块相当于仅被横切的碎纸片块。（二）类内拼接算法设计主算法：从左或从右边缘开始拼接（以从左边开始

29、拼接为例）1、 start，读入数据，变量初始化，确定左边缘为白色的纸片集合left_white，并定义一个记录已经已经拼接过的图片集合note； 2、 判断集合left_white是否为空，若为空，则跳至9，否则i=i+1，并继续；3、 从集合left_white中选取一个纸片作为拼接开始的起点left_white(i)，并赋值给表示当前待拼接变量Current4、 判断当前待拼接的纸片Current是否属于已经拼接过的集合note，若属于，则返回2；否则继续；5、 判断拼接的总数是否大于18，即一行的长度，若是则跳至8，否则继续；6、 将当前待拼接的纸片Current与未拼接的纸片按子算法

30、一进行运算，确定与当前待拼接的纸片Current相匹配的纸片集合next；7、 判断集合next的元素个数是否大于1，若是，则表示产生了两个及以上的匹配纸片，拼接无法进行下去，跳至8；否则将next赋值给Current，并返回4；8、 输出拼接完成的纸片，并存入文件夹中；9、 算法结束子算法1：实现Step1的子算法：1、 读取待拼接图片，找出待拼接图片的右边缘；2、 将右边缘与其他图片的左边缘分别相比较，分别计算平方欧式距离distance3、 返回使距离最小的拼接图片。子算法2：实现Step2的子算法：1、 读取待拼接的图片，找出待拼接图片的左边缘和右边缘；2、 将待拼接图片的右边缘分别和

31、其他图片的左边缘计算平方欧式距离distance1；3、 将待拼接图片的左边缘分别和其他图片的右边缘计算平方欧式距离distance2；4、 比较distance1与distance2，若最小值出现在distance1中，则返回对应图片，并采取自左向右拼接的方式；否则返回对应图片，采取自右向左拼接的方式。 碎纸片块类间拼接在经过碎纸片分类，以及运用matlab编程加人工干预的方法拼接后，得到11块仅横向拼接的碎纸片块。现需对这11块仅横向凭借的碎纸片块进行块间拼接。该11块仅横向拼接的碎纸片块与问题1中仅被纵向切割的碎纸片类似，根据碎纸片块上下边缘部分内容可将这11块碎纸片分为两种类型，其中第

32、一种类型为上下边缘部分含有部分文字信息，第二种类型为碎纸片块上下边缘无文字全为空白。对于第一种碎纸片块可借助模型1仅纵切碎纸片拼接模型的方法，将该种类碎纸片实现拼接。而对于第二种碎纸片块而言，它相当于上面碎纸片类内拼接中我们所定义的无匹配碎纸片（即在评判条件为碎纸片间灰度值平方欧式距离最短的情况下，该碎纸片有多于1张碎纸片可与之匹配），现无法编程实现拼接过程，故引入人工干预过程。人工干预实现碎纸片拼接的原则为：段间文字的间距为一定值。将11张仅横向拼接碎纸片块经matlab数字化后得到11个的矩阵。矩阵中的值，即像素，取值为0-1。其中该值越接近0，则表示该值所对应点的实际颜色越接近黑色；相反

33、该值越接近1，则表示该点的实际颜色越接近白色。该矩阵如下所示：矩阵中各元素值即灰度满足条件为：其中，。假设第张碎纸片块的第行第列数据为。令为第张碎纸片块的最后一列与第张碎纸片块第一列第行数据的平方欧氏距离，该值为： （6.2.8）为了寻找与第张碎纸片块相匹配的碎纸片块，那么第张块碎纸片最后一列与其拼接碎纸片块的第一列平方欧氏距离总和最小，数学表达式如下： (6.2.9)其中，为未匹配碎纸片的集合，为第一类无效碎纸片集合，为第二类无效碎纸片集合，为第三类无效碎纸片集合。6.2.2 被横、纵切后碎纸片的拼接复原模型的求解根据模型建立过程中对问题的分析，本问在建模时引入分治算法的思想，现根据该思想的

34、解题步骤，对模型逐步求解，求解结果如下。 聚类结果本问采用平方欧氏距离测度样本间距离，选用 法计算类间的距离，样本归类结果用直观的树形图表达。采用SPSS软件【1】的相关分析模块进行处理，得到附录3与附录4中、英文碎纸片聚类树状图的部分结果，中、英文碎纸片聚类树状图的全部结果见附件6与附件7。我们的最终结果是要得到的表格，故现在将中文碎纸片划分为11 类，这样便于后面拼接仅横切的碎纸片块。根据附件7中英文碎纸片的聚类树状图可发现，英文碎纸片只能分为10类。现将中文碎纸片的第2类聚类树状图展示如下：图4 中文碎纸片第2类树状图由上图4中文碎纸片第2类树状图可读出，第2类碎纸片包含序号为023、1

35、68、050、087、086、195、026、062、120、041、076、018、147、179、191、100、142、001的碎纸片，共18个。下图5为中文碎纸片序号为120、086、195、026聚类效果展示图。图5 中文碎纸片序号为120、086、195、026聚类效果展示图由上图可看出，经层次聚类分析后，得到的第2类碎纸片大部分可以直接拼接，且该类碎纸片间行特征明显相似。同样的对其它类别分析发现，聚类效果同样良好。现将英文碎纸片的第1类聚类树状图展示如下：图6 英文碎纸片第1类树状图由上图6英文碎纸片第1类树状图可读出，第1类碎纸片包含序号为077、115、012、125、052

36、、089、200、048、081、124、087、128、140、193、102、177、072、131、000的碎纸片，共19个。下图7为英文碎纸片序号为140、193、87、89聚类效果展示图：图7英文碎纸片序号140、193、87、89聚类效果展示图由上图可看出，经层次聚类分析后，得到的第1类碎纸片大部分可以直接拼接，且该类碎纸片间行特征明显相似。同样的对其它类别分析发现，聚类效果同样良好。根据附件6与附件7中、英文碎纸片聚类树状图，可统计出中、英文碎纸片各种类的碎片数量，如下表3所示：表3 中、英文碎纸片各种类数量中文碎纸片英文碎纸片种类数量种类数量第1类29第1类19第2类18第2类

37、19第3类19第3类18第4类18第4类38第5类21第5类10第6类19第6类19第7类19第7类21第8类14第8类38第9类21第9类17第10类17第10类10第11类14总和209总和209由上表3可看出，中文碎纸片种类数量最多的是第1类，共29个；最少的是第11类，14个；其余的种类大部分为19个左右。而英文碎纸片各种类数量差异较大，数量最多的是第4类，共38个；最少的是第5类与第10类，各10个。 碎纸片类内拼接结果根据的聚类结果，运用分治算法的思想，将碎纸片实现类内拼接。由于每类碎纸片中或多或少都会出现无效匹配的碎纸片，故无法编程实现仅横切的碎纸片块。现加入人工干预的过程，将分

38、类拼接后的碎纸片拼接成11块仅横切的碎纸片块，下图8、图9分别所示为11块中、英文碎纸片块中的其中一块。图8 仅横切中文碎纸片块图9 仅横切中文碎纸片块根据上图8、图9可发现，仅横切的碎纸片块在横向上已拼接完成，现只需在纵向上对碎纸片块进行拼接。在碎纸片块纵向上根据文字灰度值以及文字间间距为定值这一特点，很容易实现碎纸片块的拼接。 碎纸片块类间拼接结果在经过计算机编程及人工干预的半自动拼接过程后，得到了中、英文文件复原后图形与表格，中、英文复原图像见附录5与附录6，将中文碎纸片序号按复原后顺序填入下表4，英文填入下表5。如下表4、表5所示：表4 中文碎纸片序号按复原后顺序表（横、纵切）复原后碎

39、纸片序号（中文）4954651431862571921781181909511221292891188141611978676999162961317963116163726177205236168100766214230412314719150179120861952618718381484616124358118912210313019388167258910574711568313220017803320219815133170205851521652760141283159821991351273160203169134393151107115176943484183904712142

40、124144771121499713616412758431251318210919716184110187661061502117315718120413914529641112015921804837755544206101049817217159720813815812668175451740137535693153701663219689146102154114401512071551401851081174101113194119123表5 英文碎纸片序号按复原后顺序表（横、纵切）复原后碎纸片序号（英文）1917511154190184210418064106414932204653

41、967147201148170196198941131647810391801012610061728146865110729401581869824117150559589230374612719194931418812112610515511417618215122572027116582159139112963138153533812312017585501601879720331204110811613673362071351576431994517379161179143208217496111933142168621695419213311818916219711270846014

42、6817413719582817215696239912290185109132181956916716316618811114420631303413110252717817142662051015774145831345518563516918315244817712820013152125140193878948721217712401021156.2.3 结果分析由前文分析可得，通过多次迭代类内拼接算法，最终每一类中剩下的碎纸片具有以下特征：1、 属于三类无效匹配碎片中的一种；2、 其所属类别内无与其相匹配的碎纸片。以上两类碎纸片已经超出上文设计的拼接算法的能力范围，因此在这之后只能通

43、过过人工干预对剩下的碎纸片进行类内和类间的拼接。根据碎纸片类内拼接过程，为了体现碎纸片在聚类后由计算机编程拼接效果更明显，现统计每一类碎纸片中无法用上述类内拼接算法继续进行拼接的碎纸片数量，如下表6所示：表6 每一类碎纸片中无法继续进行拼接的碎纸片数量中文碎纸片英文碎纸片种类数量种类数量第1类4第1类2第2类3第2类1第3类4第3类9第4类3第4类5第5类5第5类4第6类1第6类4第7类2第7类4第8类4第8类6第9类3第9类3第10类2第10类2第11类2总计33总计40通过将表6与表3对比可得每一类碎纸片中人工干预减小的情况如下表7所示：表7 每一类碎纸片中相比类内拼接前减小人工干预的比例

44、中文碎纸片英文碎纸片第1类86.21%第1类89.47%第2类83.33%第2类94.74%第3类78.95%第3类50.00%第4类83.33%第4类86.84%第5类76.19%第5类60.00%第6类94.74%第6类78.95%第7类89.47%第7类80.95%第8类71.43%第8类84.21%第9类85.71%第9类82.35%第10类88.24%第10类80.00%第11类85.71%总计84.21%总计80.86%分析上表可发现，中文碎纸片在聚类后，相比类内拼接前，减小人工干预的比例最大在第6类内达到94.74%，需要人工干预的碎纸片数量由19块减少为1块，即第6类碎纸片拼接

45、成原图片中的一条横行。英文碎纸片在聚类后，相比类内拼接前，减小人工干预的比例最大在第2类内达到94.74%，需要人工干预的碎纸片数量由19块减少为1块，即第2类碎纸片拼接成原图片中的一条横行。同时与中文碎纸片相比之下，英文碎纸片需要人工干预的数量多于中文碎纸片，出现这种现象的原因是英文碎纸片中含有较多数量的第三种类无效匹配碎纸片。根据上述6.2.1 被横、纵切后碎纸片的拼接复原模型的建立与6.2.2模型的求解过程，我们统计可发现，本问共使用了两次人工干预的过程，包括第一次在碎纸片类内拼接过程中，使用人工干预使各类内能通过语义进行拼接的剩余碎纸片进行拼接；第二次是在碎纸片类间拼接过程中，此处使用

46、人工干预过程是将分属在不同类别内的碎纸片进行横向拼接，以及得到求解模型6.2.9拼接的碎纸片后，进行人工干预全图复原。最终得到的全图中行与行之间的行间距应基本相等，如附录6、8所示。6.3 双面碎纸片拼接模型6.3.1 双面碎纸片拼接模型本问题是针对来自同一页但正反面均印有文字的碎纸片拼接问题，该问题可看成对前面两问的拓展。因此，在模型的建立和求解过程中，可以借助于前两问的模型。该问题相对于前两问的难点在于题目只给出了碎纸片的正反面内容，但并未告知哪些碎纸片属于同一面。现在碎纸片数量为438张碎纸片，想要直接判别哪些碎纸片属于同一面难度较大。可考虑将双面碎纸片拼接问题转换为两页单面碎纸片的拼接

47、问题。经此转换后，相当于问题二中单面碎纸片数量增加了一倍。因此可考虑借助问题二模型的建立与求解过程，实现双面碎纸片的拼接复原。根据模型二，引入分治算法思想，划分以下三步来实现碎纸片的拼接复原：（1）分解：将碎纸片数字化后矩阵的灰度值作为评判指标，运用层次聚类法对418张碎纸片进行聚类；（2）求解：由聚类所得结果，运用贪婪算法对同类碎纸片进行拼接；再由拼接结果，人工干预得到22张仅被横切的碎纸片；（3）合并：对22张仅被横切的碎纸片运用模型一中的方法实现整张纸片的拼接复原。 分类模型将418张碎纸片经matlab数字化后得到418个的矩阵，将矩阵进行行相加运算，得到418个的列向量。将同一碎纸片

48、正反面的列向量对应相加，得到209个的列向量，对应于分别评判209张碎纸片正反面的180个指标。采用平方欧氏距离测度样本间距离，可将209张碎纸片样本看为维空间中的点，维数代表描述样本的指标数，第张碎纸片与第张碎纸片间距离为，维平方欧氏距离公式为： （6.3.1）选用 法计算类间的距离。设第类碎纸片离差平方和为；第类碎纸片离差平方和为；表示第类碎纸片的集合；表示第类碎纸片的集合。 （6.3.2）其中， （6.3.3）表示第类碎纸片的数量，表示第类碎纸片的数量。现定义： （6.3.4） 类内拼接模型在经过碎纸片的聚类后，假设将碎纸片分为了类，第类所含碎纸片数量为，的取值为。现需对这类碎纸片进行类

49、内拼接。拼接规则借助模型一中碎纸片拼接模型目标函数。将418张碎纸片经matlab数字化后得到418个的矩阵。该矩阵如下所示：矩阵中各元素值即灰度满足条件为：其中，。假设第张碎纸片块的第行第列数据为。令为第张纸片的最后一列与第张纸片第一列第行数据的平方欧氏距离，该值为： （6.3.5）为了寻找与第张碎纸片相匹配的碎纸片，那么第张碎纸片最后一列与其拼接碎纸片的第一列平方欧氏距离总和最小，数学表达式如下： (6.3.6)其中，为未匹配碎纸片的集合，为第一类无效碎纸片集合，为第二类无效碎纸片集合，为第三类无效碎纸片集合。 类间拼接模型经过类内拼接的求解过程，可将418张碎纸片拼接为22块，该22块碎

50、纸片块相当于仅横向拼接的碎纸片块，这种碎纸片块与问题1中仅被纵向切割的碎纸片类似。现根据碎纸片块上下边缘部分内容可将这22块碎纸片分为两种类型，其中第一种类型为上下边缘部分含有部分文字信息，第二种类型为碎纸片块上下边缘无文字全为空白。对于第一种碎纸片块可借助模型1仅纵切碎纸片拼接模型的方法，将该种类碎纸片实现拼接。而对于第二种碎纸片块而言，它相当于上面碎纸片类内拼接中我们所定义的无匹配碎纸片（即在评判条件为碎纸片间灰度值平方欧式距离最短的情况下，该碎纸片有多于1张碎纸片可与之匹配），现无法编程实现拼接过程，故引入人工干预过程。人工干预实现碎纸片拼接的原则为：段间文字的间距为一定值。第一种碎纸片块拼接模型，如上述 类内拼接模型所示。6.3.2 双面碎纸片拼接模型求解根据模型建立过程中对问题的分析，本问在建模时引入分治算法的思想，现根据该思想的解题步骤，对模型逐步求解，求解结果如下。本问采用平方欧氏距离测度样本间距离，选用 法计算类间的距离，样本归类结果用直观的树形图表达。采用SPSS软件的相关分析模块进行处理，得到附录7双面碎纸片聚类树状图的部分结果，双面碎