2013年全国大学生数学建模竞赛B题全国一等奖论文

.碎纸片的拼接复原【摘要】破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。本文主要解决碎纸机切割后的碎纸片拼接复原问题。针对第一问，附件1、2分别为沿纵向切割后的19张中英文碎纸片，本文在考虑破碎纸片携带信息量较大的基础上，利用MATLAB对附件1、2的碎纸片图像分别读入，以数字矩阵的方式进行存储。利用数字矩阵中包含图像边缘灰度这一特征，本文采用贪心算法的思想，在首先确定原文件左右边界的基础上，以Manhattan距离来度量两两碎纸片边界差异度，利用计算机搜索依次从左往右搜寻最匹配的碎纸片进行横向配对并达成排序目的。最终，本文在没有进行人工干预，成功地将附件1、2碎纸片分别拼接复原，得到复原图片见附录2.1、2.2，纵切中文及英文结果表分别如下:9151316411317256101419128181747381619121621014119131518175针对第二问，附件3、4分别为既横切又纵切后的209张中英文碎纸片，本文核心思想仍为贪心算法，整体思路为先对209张碎纸片进行聚类还原成11行，再对分好的每行进行横向排序，最后对排序好的各行进行纵向排序。本文在充分考虑汉字与拉丁字母结构特征差异以及每块碎纸片携带信息减少的基础上，创新地提出一种特征线模型来分别描述汉字及拉丁文字母的特征用于行聚类。对于行聚类后碎片的横向排序，本文综合了广义Jaccard系数、一阶差分法、二阶差分法、Spearman系数等来构建扩展的边界差异度模型，刻画碎片间的差异度。对于计算机横向排序存在些许错误的情况，本文给出了人工干预的位置节点和方式。对于横向排序后的各行，由于在一页纸上，文字的各行是均匀分布的，本文基于各行文字的特征线，在确定首行的位置后，估计出其他行的基准线位置，得到一页的基准线网格，并通过各行基准线在基准线网格上的适配实现纵向的排序。最终，本文成功的将附件3、4碎纸片分别拼接复原得到复原图片及结果表见附录1.3、1.4、2.3、2.4，同时本文给出了横向排序中人工干预的位置节点和方式。针对第三问，附件5为双面文件既横切又纵切后的209张碎片（包含正反面），即包含418张图像。本文整体解决思路同第二问中对于拉丁文碎片的复原类似，并且由于正反两面的特征可以同时作为差异度判断条件，特征信息丰富，综合使用各种差异度函数后可以将各行全部正确排列，无需人工排错，同时正确排序时自然分出两面。以与问题二类似的方法，确定出每一面的第一行后，用基准线网格确定各行的位置并排序。然而由于附件5原件的第3、第4行及第9、第10行的两个切口正好切到了两行行间的空白，同时两面文字高度一致，所以计算机不可能分辨二者是否在同一面，此处必须由人工介入，通过上下文区分。最终，本文成功的将附件5所有碎片分别拼接复原得到复原图片及结果表见附录1.5、1.6、2.5、2.6。对于本问题，本文只在最后模块的上下文判断和横向排列的方法选择时进行了干预，自动化程度高。本文发现在横向排序中，一、二阶差分法对于样本量大的情况适配成功率很高，而广义Jaccard系数及Spearman系数则对样本量小但特征显著的情况适配的成功率更高。关键词：图像拼接复原 贪心算法 差异度 相似系数 文字基准线 一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、模型假设1. 假设原题附件给出的破碎纸片图像是完好无损的。2. 假设原题附件给出的破碎纸片仅包含纯文字内容（中英文），不含表格线等。3. 假设原题附件给出的破碎纸片在切割时无油墨损失。4. 假设原题附件给出的破碎纸片文字方向与切割方向均为水平或垂直。5. 假设原题附件给出的破碎纸片文字均为水平正向，无旋转。三、符号说明序号符号说明1S碎片集2碎片n的右边界向量3碎片n的左边界向量4碎片n与碎片k的边界差异度5L特征线位置6H行高7、标高、余高、空高、字高四、 问题一：仅纵切时的纸片拼接复原4.1问题一的分析本题的所有碎片为形状一致的矩形，且均为黑白文字，文字边缘有灰色部分。由于原图切割前的信息具有一定的连续性，本文希望遵循这一思路，首先确定出碎片中的位置为最左的一个，再以之为基础，在剩下的碎片中寻找可以与之配对（或配对情况最好）的一个碎片。4.2问题一的数学模型4.2.1灰度矩阵与灰度向量模型描述碎片的模型为图像的灰度矩阵，灰度矩阵的每个元素对应到图像上的每个像素点，取值为0（白色）到255（黑色）。每个碎片均可以确定一个同型的灰度矩阵，灰度矩阵的特征反映了图像的特征。灰度矩阵的每一列构成了一个描述局部特征的列向量，在图片上的宽度为1像素。所有碎片构成碎片集S。4.2.2边界差异度模型对于一个给定的碎片，找到可以与之拼接的另一碎片的最重要的特征是其边界的列向量。图片上连续的部分具有类似的结构，则相邻的列向量就具有类似的特征。对碎片集S中的碎片n，其左右边界的灰度向量分别为与，寻找这个向量右侧最匹配的下一个碎片n+1，等价于在剩下的碎片中寻找到向量k，满足边界差异度 （4.1）但是由于并不知道下一个碎片具体是哪一个碎片，所以实际上的值是未知的。然而可以假定两个匹配的碎片的边界差异度的值是所有的边界差异度中最小的。则问题转化为在碎片集S中寻找满足的碎片k。 （4.2）对于边界差异度，可以用多种方法来定义，这个论题将在问题2作更加详细的阐述。将边界向量g视为一个180维空间中的一点，则二者的差异度可以用两点之间的“距离”来描述。此处取Manhattan距离 （4.3）4.3计算流程图1：问题一算法流程说明图问题一的拼接过程使用贪心算法，首先确定出最左侧的碎片1，然后从剩下的样本中寻找与碎片1的边界差异度最小的碎片作为下一个碎片，再寻找与第2个碎片配对的第3个碎片，以此类推。碎片1判别为碎片左侧留白最宽者。4.4问题一的结果本题未经过人工干预，完全由计算机自动拼接出结果如下（图片结果详见附录2.1、2.2）。拼接顺序如下：表1：附件1(仅纵切中文)的顺序表91513164113172561014191281817表2：附件2（仅纵切英文）的顺序表473816191216210141191315181754.5模型评价与推广本模型对于碎纸条为大面积的有较好的识别和排序准确度，能够全自动化进行计算机排序，但是此模型仅适用于比较样本点较丰富的大面积碎纸条，对于细小纸条效果不会太好，在问题二中会对其进行改进。五、 问题二：既纵切又横切时的纸片拼接复原5.1问题二的分析由于问题二破碎纸片为及纵切又横切产生，其复杂程度及处理难度要远远高于问题一。此时采用问题一中单纯的考虑纵切时的方式已经无法解决此文，但仍可以第一问的思想为基础，考虑到本题附件3给出的破碎纸片竖直高度远大于水平长度，即破碎纸片纵向上包含的特征信息远多于横向。若采用先沿横向方向选出每一行包含的碎纸片，再拼接复原该行，再将拼接好的每行沿纵向方向进行拼接，这又回归到问题一这类单方向切断的拼接问题。整体拼接思路如下： 图2：问题二拼接示意图5.2问题二的数学模型问题二在沿用4.2中的模型的基础上，增加几个专门的模型。5.2.1特征线模型文字打印在纸张上时，是沿着一条直线的基准线排列的。由于本文所研究的所有碎片均没有旋转，所有可以用比较简单的方法来搜索基准线。在本文中，基准线是特征线中有特殊意义的一条。确定特征线和基准线的目的有二：一是从碎片集S中将属于同一高度的碎片聚类到第n行碎片子集中，二是通过特征线可以确定行碎片子集的顺序，即各个行碎片子集在纵向的排列，这个内容将在5.2.2详细阐述。a）汉字的特征线（针对附件3）汉字的特性决定了汉字每一行中每个字的高度大致是相同的。尽管可能出现如“一”等高度差异很大的汉字，但是这种情况非常少。所以对于汉字，可以用上下两条特征线来描述汉字的位置，并且只需要少量的样本就能够确定出两条特征线。图3：汉字的特征线对一行汉字的两条特征线，作如图的命名。上边线（基准线）下边线图4：汉字的特征线上边线（基准线）位置与下边线位置之差满足 （5.1）式中为字高。在计算中取。碎片上第n行的基准线位置与下一行基准线位置之间的差异为1个行距H，即 （5.2）对于一个碎片，确定出其中一行的上边线和下边线后，只要对行高做出估计，就可以得到其他行的水平特征线，以此可以估计出该碎片中空行的位置。计算中取行高。 图5：通过特征线和行距估计空行的位置图行高H与字高之间的差值为空高，即行间距： （5.3）式（5.1）、（5.2）和（5.3）表达了汉字各特征线的约束关系。b）拉丁字母的特征线（针对附件4）上边线上标线（基准线）下标线下边线拉丁字母的特征线模式比汉字要复杂。由于拉丁字母相互之间高度差异较大，所以无法照搬汉字的模式。本文用四条特征线来描述一行拉丁字母。图6：拉丁字母的特征线拉丁字母四条特征线的位置分别为：上边线位置，上标线位置，下标线位置，下边线位置。拉丁字母的基准线为上标线。各特征线满足由以下各式决定的约束关系： （5.4）式中：标高，即上标线与下标线的距离；余高，即同侧边线与标线之间的距离。计算中取，。5.2.2基准网格模型由于一页纸上，文字的各行是均匀分布的，所以一旦确定一行的位置就能确定一页纸上所有文字行的基准线的位置。基准线位置的关系满足 （5.5）5.2.3扩展的边界差异度模型由于本题中碎片的更小，碎片的边界向量信息有限，4.2.2中的模型不能满足要求，因此本文拓展了几种计算边界差异度的方法。a）差分的Manhattan距离比较边界向量的差分来确定差异度的目的在于消除数据序列的自相关，使得从有限的边界样本中提取的特征信息受到更少的干扰。此处的边界差异度定义为 （5.6）b）广义Jaccard 系数Jaccard系数又叫做Jaccard相似性系数，用来比较样本集中的相似性和分散性的一个概率。定义集合M与N的相似度函数计算公式如下： （5.7）式中，此处样本M，N为破碎纸片边缘各个像素点灰度的集合，p为样本的维数，在本文中为破碎纸片边缘像素点分布的行数，i为边缘上该像素点在边界上的行数。分别为破碎纸片M和N在第i行边缘上的像素点对应的灰度。用于刻画M与N的边缘匹配度。该系数的值越大，代表匹配性越好。则差异度定义为其相反数 （5.8）c）Spearman相关系数Spearman相关系数：对不服从正态分布的资料、原始资料等级资料、一侧开口资料、总体分布类型未知的资料不符合使用积矩相关系数来描述关联性。此时可采用秩相关，也称等级相关，来描述两个变量之间的关联程度与方向。这类方法对原始变量分布不作要求，属于非参数统计方法。其中最常用的统计量是Spearman秩相关系数，又称等级相关系数。计算步骤：（1）编秩：将两变量X、Y成对的观察值分别从小到大顺序编秩，用pi表示xi的秩次；用qi表示yi的秩次。若观察值相同取平均秩次。（2）将秩次带入公式计算： （5.9）（3）由样本算得的秩相关系数是否有统计学意义，应作假设检验。鉴于本文由图像得到的数字矩阵不具有正态分布的特征，且原始资料数据量较大。我们采用Spearman相关系数来刻画水平方向各碎片拼接在一行的匹配度。图7：Spearman相关系数判断实施步骤与广义Jaccard系数类似，Spearman相关系数越大代表匹配度越高，差异度也定义为其相反数： (5.10)5.3算法的实施与模型的求解图8：问题二算法流程说明图5.3.1标定碎片的特征线a）汉字汉字的特征线模式比较简单，通过一次搜索就可以完成。图9：汉字标定特征线算法示意图b）拉丁字母拉丁字母的特征线模式要复杂得多，本文将之按字母跨越的区域数量分为3种模式予以判别。 模式1 模式2a 模式2b 模式3图10：拉丁字母特征线模式模式1只跨越了标高区域，模式2跨越了标高区域和一个余高区域，而模式3跨越了整个字高区域。标定拉丁字母的特征线需要多次搜索。图11：拉丁文标定特征线算法示意图5.3.2根据特征线将碎片聚类到各行得到各个碎片的特征线之后，根据特征线的位置，可以将各个碎片分类到各行。尽管聚类的目标是各行，但是因为各行的特征线是未知的，所以采用以下的方法：Step1.将第1个碎片定为第1个标准，放入标准库；Step2.对比下一个碎片的特征线与当前标准库中所有标准对比；Step3.若与某个标准的差异小于阈值，则当前碎片聚类到该行；若与所有标准的特征线差异都大于阈值，则该碎片定为下一个标准，放入标准库；Step4.循环步骤2到步骤3，直到所有碎片都已被聚类到某一行。虽然问题中已知总的碎片行数是11，但是因为标定特征线时可能有误差，所以标准的典型性不一定高，有可能导致同一碎片行中差异较大的样本被分为两行，此时碎片行数大于11，需要进行人工干预，将某些碎片行合并。5.3.3碎片的排序A.同一行内各碎片排序沿用4.3的计算方法。由于本问题中，每个碎片至少包含3行文字，不存在由于空行而导致左边界误判的问题，所以对首个碎片的判别依然是有效的。B.同一页各行的排序对于至今得到的11个碎片行，首先寻找首行。基于文字页的性质，首行的判别方法为一行顶部留白最宽者。确定出首行之后，根据首行的基准线，由式（5.5）知可以推算出页面上所有基准线的位置。在第1个碎片行已经放到页面上以后，在剩下的碎片行中搜索基准线与页面上下一条未覆盖基准线相匹配的一个，并继续向下迭代直到找出所有碎片行。至此，该页所有碎片拼接完成。5.4问题二结果5.4.1附件3（中文）的拼接组号方法1234567891011拼接正确数量统计广义Jaccard系数3一阶差分6二阶差分5Spearman相关系数3所有方法综合统计8a）未人工干预时情况（同一行内各碎片排序）我们分别基于四种方法对问附件3（中文）通过行聚类后得到的11组破碎纸片分别进行拼接，综合起来得到7个正确左右拼接的碎纸片行，剩余3个5.4中聚类出的行在左右拼接时出现了一些错误，需要我们进行人工适当的干预。下图组号并非该行在原文件的真实位置，此处仅作为其暂时的代号。注：下表代表该组在该方法下正确左右拼接，代表该组在这方法下正确左右拼接。表3：不同判断方法中文拼接正确数量统计表11行中共3行需要人工干预，人工干预率为27.2%b）人工干预过程（同一行内各碎片排序）有少许错误的组为：3, 8,10组，下面采取人工干预方式进行微调：1.第三组计算机排序为：(表格序号已与下方图片对齐，下同)4954651431862571921781181909512928911881411122计算机排序效果如图12：（红色指示为错误处及干预过程）图12：第三组计算机排序图人工干预：将尾部的11,12整体平移到129前面。下表为干预后顺序表。4954651431862571921781181909511221292891188141人工干预后效果如图13：图13：第三组人工干预排序图2.第八组:计算机排序为：381487416124358118912210313019388167258910546计算机排序效果如图14：（红色指示为错误处及干预过程）图14：第八组计算机排序图人工干预:将46和74对调。下表为干预后顺序表。381484616124358118912210313019388167258910574人工干预后效果如图15：图15：第八组人工干预排序图3.第十组:计算机排序为：711568033202198151331702058515216527608313220017计算机排序效果如图16：图16：第十组计算机排序图人工干预：将尾部的83,132,200,17作为整体插入到80前面。下表为干预后顺序表。711568313220017803320219815133170205851521652760人工干预后效果如图17：图17：第十组人工干预排序图c）纵向拼接（同一页各行的排序）附表3的破碎纸片原文件应为11行*19列，经过本文5.4中的聚类分析先将209个碎纸片分为了11组，当然，此时的每组的碎片应该归属于同一行，但他们在同一行的位置却未能确定。之后我们分别采用4种方法利用各自的特征值对每组碎纸片进行左右拼接，最后我们综合4种方法的结果加上适当的人工干预得出了原文件的11行，但此时这11行纵向相对的位置是不确定的，我们需要对聚类好的各行进行纵向拼接之后得到原文件。我们由基准网格模型经过纵向拼接，得出了本问原文件的图片及碎片位置见附录1.3、2.3。5.4.2附件4（英文）的拼接a）未人工干预时情况（同一行内各碎片排序）我们分别基于四种方法对问附件3（中文）通过行聚类后得到的11组破碎纸片分别进行左右拼接，综合起来得到7个正确左右拼接的碎纸片行，剩余3个5.4中聚类出的行在左右拼接时出现了一些错误，需要我们进行人工适当的干预。下图组号并非该行在原文件的真实位置，此处仅作为其暂时的代号。注：下表中代表该组在该方法下正确左右拼接，代表该组在这方法下正确左右拼接。表4：不同判断方法英文拼接正确数量统计表组号方法1234567891011拼接正确数量统计广义Jaccard系数2一阶差分1二阶差分1Spearman相关系数4所有方法综合统计511行中有6行需要进行微量的人工干预，人工干预度为54.5%。b）人工干预过程（同一行内各碎片排序）有少许错误的组为：1,4,5,7,8,11组，尽管从行数上计算人工干预度达到54.5%，但从下面的人工干预力度来看，实际大部分错误行需要调节的力度很小。下面采取人工干预方式进行微调：1.第一组：计算机排序为:19194931418812112610515511417620271165821821512257计算机排序效果如图18：（红色指示为错误处及干预过程，下同）图18：英文第一组计算机排序图人工干预：202，71，165，82作为整体移到57后面。下表为干预后顺序表：19194931418812112610515511417618215122572027116582人工干预后效果如图19：图19：英文第一组计算机排序图2.第四组：计算机排序为：1917511154190184210418064106439671471493220465计算机排序效果如图20：图20：英文第四组计算机排序图人工干预：39，67，147作为整体移动到65后面。下表为干预后顺序表：1917511154190184210418064106414932204653967147人工干预后效果如图21：图21：英文第四组人工干预排序图3.第五组： 计算机排序为：2082174961119331421686216954192112133118189162197计算机排序效果如图22：图22：英文第五组计算机排序图人工干预：112与197对调。下表为干预后顺序表：2082174961119331421686216954192133118189162197112人工干预后效果如图23：图23：英文第五组人工干预排序图4.第七组：708460146817413719584717215696239912210990185计算机排序为：计算机排序效果如图24：图24：英文第七组计算机排序图人工干预：将109和90，185整体对调。下表为干预后顺序表：708460146817413719584717215696239912290185109人工干预后效果如图25：图25：英文第七组人工干预排序图5.第八组：计算机排序为：159501601879720331153533812312017511296313885139计算机排序效果如图26：图26：英文第八组计算机排序图人工干预：将139移至50前，再将50,160,187,97,203,31移至85后方,最后将1,129,63,138移至153前面。下表为干预后顺序表：159139112963138153533812312017585501601879720331人工干预后效果如图27：图27：英文第八组人工干预排序图6.第十一组： 计算机排序为：81771282001315212587894872121771240102115140193计算机排序效果如图28：图28：英文第十一组计算机排序图人工干预：将尾部的140，193整体移到87前面。下表为干预后顺序表：81771282001315212514019387894872121771240102115人工干预后效果如图29：图29：英文第十一组人工干预排序图c）纵向拼接（同一页各行的排序）附表4的破碎纸片原文件应为11行*19列，经过本文5.4中的聚类分析先将209个碎纸片分为了11组，当然，此时的每组的碎片应该归属于同一行，但他们在同一行的位置却未能确定。之后我们分别采用4种方法利用各自的特征值对每组碎纸片进行左右拼接，最后我们综合4种方法的结果加上适当的人工干预得出了原文件的11行，但此时这11行纵向相对的位置是不确定的，我们需要对聚类好的各行进行纵向拼接之后得到原文件。我们由基准网格模型经过纵向拼接，得出了本问原文件的图片及碎片位置见附录1.4、2.4。5.5模型评价与推广本模型对于破碎纸片的处理原则为计算机自动拼接为主，人工干预为辅。由于中英文字符特征的差异，我们采用在选择方法及算法拼接时分别进行了修正，这符合实际问题差异化处理的原则。同时本模型可通用于类似附件3、4中英文的破碎问题的拼接，由于本文提出了水平特征线的概念并基于水平特征进行拼接，使得本模型对于不同类型的拼接问题，都有一定推广作用。六、问题三：双面打印时的纸片拼接复原6.1问题3的分析由于本文原文件为正反面，附件5给出了418个碎片图片，这加大了拼接的难度。深入分析，若拼好该文件的一面，则另一面必然是拼好，所以本文只需拼出有209张碎片构成的一面文件即可。由于本问仍是横纵切的英文文件碎片进行拼接，核心为对字母的处理，因此本文在模型和算法的设计上同问题二对附件4的处理基本一致。6.2问题三的算法设计: 图30：问题三算法说明由于附件5中正反两面各行的基准线是对齐的，进而总共418个碎片依然可以共同向11个碎片行聚类。到此为止的处理与附件4都是一致的。6.2.1从碎片行中拆分面完全聚类后，一个碎片行中会包含38个碎片，即正反两面同一行的碎片没有分离。但是分离的思路比较简单，因为4.3中判断首位碎片的方法此处依然有效，因而可以容易地找出38个碎片中的两个首位。由于正反面的信息是不同的，所以从其中一个首位开始在余下36个碎片中寻找18个碎片形成正确匹配的一行后，就能够自然分离出两面。但是由于被聚类到同一碎片行的38个碎片本身具有比较高的相似度，在匹配中相互的干扰会比通常高，对人工干预的需求较大。6.2.2基于基准网格模型产生纵向模块通过5.3.3b中的方法找出所有碎片行中的两个首行后，由5.2.2的基准网格模型，可以快速地产生页面的所有基准线。与问题二不同，因为每个基准线的位置有两个碎片行备选，所以此处还需要碎片行的上下边界向量的差异度作为第二判据。但是实际观察各个碎片行会注意到，页中有两个切口的位置为行间，即一行的下边线与下一行的上边线之间，分别在3、4行之间与9、10行之间。则3、4行与9、10行之间是无法进行配对的。图31：第3碎片行与第4碎片行之间的切口不包含任何配对信息进而，此处计算机只能将所有的碎片行组合成6个模块，不能进一步组合这6个模块，必须通过人工干预才能完全组合。6.3问题三的的拼接本文分别基于四种方法对问附件5通过行聚类后得到的11组破碎纸片分别进行左右拼接，综合起来得到8个正确左右拼接的碎纸片行，剩余3个聚类出的行在左右拼接时出现了一些错误，需要我们进行人工适当的干预。下图组号并非该行在原文件的真实位置，此处仅作为其暂时的代号。注：下图中代表该组在该方法下正确左右拼接，代表该组在这方法下正确左右拼接。表5：不同判断方法英文拼接正确数量统计表组号方法1234567891011拼接正确数量统计广义Jaccard系数7一阶差分10二阶差分10Spearman相关系数7所有方法综合统计11横向自动拼接效果非常好，11行全部成功实现自动左右拼接，人工干预率仅为0。每一行的拼接完成后，纵向的拼接基于5.2.2基准网格模型和6.2.2的补充方法，可以顺利得到6个模块，然后通过上下文人工干预得到排列结果。6.4模型评价与推广本模型对于破碎纸片的处理原则为计算机自动拼接为主，人工干预为辅，实际匹配效果较好。同时也发现在双面约束的差异度模型下（一、二阶差分的）Manhattan距离比广义Jaccard系数及Spearman系数则对于拉丁字母的拼接显得更为有效。此模型整体效果较好，人为干预较少，能作为复杂情况下的拼接的基础模型。如果能结合更加严格的差异度判断条件，此模型效果更好。七、模型检验7.1差异度模型检验本文选取了数个差异度计算函数，对各种边界进行综合的计算。从各种函数的适配结果中选取正确结果是本文主要的人工干预点。本文主要使用了边界序列及其一阶、二阶差分的Manhattan距离与广义Jaccard系数及Spearman系数5中差异度计算方法。对问题1，各种函数的差异不显著，问题2中两个系数的效果要好过三种Manhattan距离，二问题3中三种Manhattan距离的效果更好。更加细致的分析显示三种Manhattan距离对边界长、特征信息丰富的碎片匹配效果很好，而两种系数对边界短、特征信息有限的碎片匹配效果更加。综合基于几种评价函数的差异度模型，对碎片的匹配均能起到较好的效果。7.2文字特征线模型检验文字特征线模型对汉字的使用效果很好，模式简单，且聚类效果佳，在对附件3的处理中不需要加入人工干预就能正确完成全部行距类。但是拉丁字母的特征线模型运用效果不如汉字，一方面拉丁字母的特征线模式较复杂，且基准线标定较困难，需要一定的人工干预判断标定正误并调整。八、参考文献1 罗智中.基于文字特征的文档制片半自动拼接J.计算机工程与应用，2012，48（5）：207-210.2 李宇成，田震，游加.一种新的字符特征向量相似度函数J.计算机工程与科学，2013，35（5）：93-99.3 刘琼荪，龚劬，何中市，傅鹂等，数学实验，北京：高等教育出版社，2004.4 姜启源，谢金星，叶俊，数学模型，北京：高等教育出版社，2003.九、附录附录1全文复原结果的表格表达格式1.1附件1中文拼接顺序：915131641131725610141912818171.2附件2英文拼接顺序：473816191216210141191315181751.3附件3中文拼接结果（红色为左右拼接时存在人工干预的碎片）：72081381581266817545174013753569315370166321961681007662142304123147191501791208619526187184954651431862571921781181909511221292891188141141283159821991351273160203169134393151107115176891461021541144015120715514018510811741011131941191232964111201592180483775554420610104981721715961197867699916296131796311616372617720523638148461612435811891221031301938816725891057412513182109197161841101876610615021173157181204139145711568313220017803320219815133170205851521652760943484183904712142124144771121499713616412758431.4 附件4英文拼接结果（红色为左右拼接时存在人工干预的碎片）： 19175111541901842104180641064149322046539671472011481701961989411316478103918010126100617281468651107294015818698241171505595892303746127191949314188121126105155114176182151225720271165821591391129631381535338123120175855016018797203312041108116136733620713515764319945173791611791432082174961119331421686216954192133118189162197112708460146817413719584717215696239912290185109132181956916716316618811114420631303413110252717817142662051015774145831345518563516918315244817712820013152125140193878948721217712401021151.5附件5正面拼接结果：078b111b125a140a155a150a183b174b110a066a108a018b029a189b081b164b020a047a136b089a010b036a076b178a044a025b192a124b022a120b144a079a014a059a060b147a152a005a186b153a084b042b030a038a121a098a094b061b137b045a138a056b131b187b086b200b143b199b011b161a169b194b173b206b156a034a181b198b087a132b093a072b175a097a039b083a088b107a149b180a037b191a065b115b166b001b151b170b041a070b139b002a162b203b090a114a184b179b116b207a058a158a197a154b028b012a017b102b064b208a142a057a024a013a146a171b031a201a050a190b092b19b016b177b053b202a021b130a163a193b073b159a035a165b195a128a157a168a046a067a063b075b167a117b008b068b188a127a040a182b122a172a003b007b085b148b077a004a069a032a074b126b176a185a000b080b027a135b141a204b105a023b133a048a051b095a160b119a033b071b052a062a129b118b101a015b205a082b145a009b099a043a096b109a123a006a104a134a113a026b049b091a106b100b055b103a112a196b054b1.6附件5正面拼接结果：136a047b020b164a081a189a029b018a108b066b110b174a183a150b155b140b125b111a078a005b152b147b060a059b014b079b144b120a022b124a192b025a044b178b076a036b010a089b143a200a086a187a131a056a138b045b137a061a094a098b121b038b030b042a084a153b186a083b039a097b175b072a093b132a087b198a181a034b156b206