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

1碎纸片的拼接复原【摘要】破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。本文主要解决碎纸机切割后的碎纸片拼接复原问题。针对第一问，附件1、2分别为沿纵向切割后的19张中英文碎纸片，本文在考虑破碎纸片携带信息量较大的基础上，利用MATLAB对附件1、2的碎纸片图像分别读入，以数字矩阵的方式进行存储。利用数字矩阵中包含图像边缘灰度这一特征，本文采用贪心算法的思想，在首先确定原文件左右边界的基础上，以Manhattan距离来度量两两碎纸片边界差异度，利用计算机搜索依次从左往右搜寻最匹配的碎纸片进行横向配对并达成排序目的。最终，本文在没有进行人工干预，成功地将附件1、2碎纸片分别拼接复原，得到复原图片见附录2.1、2.2，纵切中文及英文结果表分别如下:47381619121621014119131518175针对第二问，附件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系数则对样本量小但特征显著的情况适配的成功率更高。关键词：图像拼接复原贪心算法差异度相似系数文字基准线915131641131725610141912818172一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、模型假设1.假设原题附件给出的破碎纸片图像是完好无损的。2.假设原题附件给出的破碎纸片仅包含纯文字内容（中英文），不含表格线等。3.假设原题附件给出的破碎纸片在切割时无油墨损失。4.假设原题附件给出的破碎纸片文字方向与切割方向均为水平或垂直。。5.假设原题附件给出的破碎纸片文字均为水平正向，无旋转。三、符号说明序号符号说明1S碎片集2,nRg碎片n的右边界向量3,nLg碎片n的左边界向量4(,)nk碎片n与碎片k的边界差异度5L特征线位置6H行高7mh、rh、bh、ch标高、余高、空高、字高3四、问题一：仅纵切时的纸片拼接复原4.1问题一的分析本题的所有碎片为形状一致的矩形，且均为黑白文字，文字边缘有灰色部分。由于原图切割前的信息具有一定的连续性，本文希望遵循这一思路，首先确定出碎片中的位置为最左的一个，再以之为基础，在剩下的碎片中寻找可以与之配对（或配对情况最好）的一个碎片。4.2问题一的数学模型4.2.1灰度矩阵与灰度向量模型描述碎片的模型为图像的灰度矩阵，灰度矩阵的每个元素对应到图像上的每个像素点，取值为0（白色）到255（黑色）。每个碎片均可以确定一个同型的灰度矩阵，灰度矩阵的特征反映了图像的特征。灰度矩阵的每一列构成了一个描述局部特征的列向量，在图片上的宽度为1像素。所有碎片构成碎片集S。4.2.2边界差异度模型对于一个给定的碎片，找到可以与之拼接的另一碎片的最重要的特征是其边界的列向量。图片上连续的部分具有类似的结构，则相邻的列向量就具有类似的特征。对碎片集S中的碎片n，其左右边界的灰度向量分别为,nRg与,nLg，寻找这个向量右侧最匹配的下一个碎片n+1，等价于在剩下的碎片中寻找到向量k，满足边界差异度(,)(,1)nknn（4.1）但是由于并不知道下一个碎片具体是哪一个碎片，所以实际上(,1)nn的值是未知的。然而可以假定两个匹配的碎片的边界差异度(,1)nn的值是所有的边界差异度(,)nk中最小的。则问题转化为在碎片集S中寻找满足的碎片k。(,)min(,),nkniiS（4.2）对于边界差异度，可以用多种方法来定义，这个论题将在问题2作更加详细的阐述。将边界向量g视为一个180维空间中的一点，则二者的差异度可以用两点之间的“距离”来描述。此处取Manhattan距离,,(,)nRkLnkgg（4.3）44.3计算流程图1：问题一算法流程说明图问题一的拼接过程使用贪心算法，首先确定出最左侧的碎片1，然后从剩下的样本中寻找与碎片1的边界差异度最小的碎片作为下一个碎片，再寻找与第2个碎片配对的第3个碎片，以此类推。碎片1判别为碎片左侧留白最宽者。4.4问题一的结果本题未经过人工干预，完全由计算机自动拼接出结果如下（图片结果详见附录2.1、2.2）。拼接顺序如下：表1：附件1(仅纵切中文)的顺序表表2：附件2（仅纵切英文）的顺序表473816191216210141191315181754.5模型评价与推广本模型对于碎纸条为大面积的有较好的识别和排序准确度，能够全自动化进行计算机排序，但是此模型仅适用于比较样本点较丰富的大面积碎纸条，对于细小纸条效果不会太好，在问题二中会对其进行改进。五、问题二：既纵切又横切时的纸片拼接复原5.1问题二的分析由于问题二破碎纸片为及纵切又横切产生，其复杂程度及处理难度要远远高于问题一。此时采用问题一中单纯的考虑纵切时的方式已经无法解决此文，但仍可以第一问的思想为基础，考虑到本题附件3给出的破碎纸片竖直高度远大于水平长度，即破碎纸片纵向上包含的特征信息远多于横向。若采用先沿横向方向选出每一行包含的碎纸片，再拼接复原该行，再将拼接好的每行沿纵向方向进行拼接，这又回归到问题一这类单方向915131641131725610141912818175切断的拼接问题。整体拼接思路如下：图2：问题二拼接示意图5.2问题二的数学模型问题二在沿用4.2中的模型的基础上，增加几个专门的模型。5.2.1特征线模型文字打印在纸张上时，是沿着一条直线的基准线排列的。由于本文所研究的所有碎片均没有旋转，所有可以用比较简单的方法来搜索基准线。在本文中，基准线是特征线中有特殊意义的一条。确定特征线和基准线的目的有二：一是从碎片集S中将属于同一高度的碎片聚类到第n行碎片子集nS中，二是通过特征线可以确定行碎片子集nS的顺序，即各个行碎片子集nS在纵向的排列，这个内容将在5.2.2详细阐述。a）汉字的特征线（针对附件3）汉字的特性决定了汉字每一行中每个字的高度大致是相同的。尽管可能出现如“一”等高度差异很大的汉字，但是这种情况非常少。所以对于汉字，可以用上下两条特征线来描述汉字的位置，并且只需要少量的样本就能够确定出两条特征线。图3：汉字的特征线对一行汉字的两条特征线，作如图的命名。6图4：汉字的特征线上边线（基准线）位置1L与下边线位置2L之差满足12cLLh（5.1）式中ch为字高。在计算中取44ch。碎片上第n行的基准线位置1,nL与下一行基准线位置1,1nL之间的差异为1个行距H，即1,1,1nnLLH（5.2）对于一个碎片，确定出其中一行的上边线和下边线后，只要对行高做出估计，就可以得到其他行的水平特征线，以此可以估计出该碎片中空行的位置。计算中取行高68H。图5：通过特征线和行距估计空行的位置图行高H与字高ch之间的差值为空高，即行间距：cbHhh（5.3）式（5.1）、（5.2）和（5.3）表达了汉字各特征线的约束关系。b）拉丁字母的特征线（针对附件4）拉丁字母的特征线模式比汉字要复杂。由于拉丁字母相互之间高度差异较大，所以无法照搬汉字的模式。本文用四条特征线来描述一行拉丁字母。图6：拉丁字母的特征线拉丁字母四条特征线的位置分别为：上边线位置0L，上标线位置1L，下标线位置2L，上边线（基准线）下边线上边线上标线（基准线）下标线下边线7下边线位置3L。拉丁字母的基准线为上标线。各特征线满足由以下各式决定的约束关系：0123121,2,22rmnnmrcmrbLLLLhLLhLLHhhhhhhH（5.4）式中：mh——标高，即上标线与下标线的距离；rh——余高，即同侧边线与标线之间的距离。计算中取28mh，12rh，12bh。5.2.2基准网格模型由于一页纸上，文字的各行是均匀分布的，所以一旦确定一行的位置就能确定一页纸上所有文字行的基准线的位置。基准线位置的关系满足1,1,()nkLLnkH（5.5）5.2.3扩展的边界差异度模型由于本题中碎片的更小，碎片的边界向量信息有限，4.2.2中的模型不能满足要求，因此本文拓展了几种计算边界差异度的方法。a）差分的Manhattan距离比较边界向量的差分来确定差异度的目的在于消除数据序列的自相关，使得从有限的边界样本中提取的特征信息受到更少的干扰。此处的边界差异度定义为,,(,)nRkLnkgg（5.6）b）广义Jaccard系数Jaccard系数又叫做Jaccard相似性系数，用来比较样本集中的相似性和分散性的一个概率。定义集合M与N的相似度函数计算公式如下：122111(,)piiipppiiiiiiimnsimMNmnmn（5.7）式中，此处样本M，N为破碎纸片边缘各个像素点灰度的集合，p为样本的维数，在本文中为破碎纸片边缘像素点分布的行数，i为边缘上该像素点在边界上的行数。,iimn分别为破碎纸片M和N在第i行边缘上的像素点对应的灰度