当前位置:文档之家› 2013年全国大学生数学建模竞赛B题全国一等奖论文

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

碎纸片的拼接复原【摘要】破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。

本文主要解决碎纸机切割后的碎纸片拼接复原问题。

针对第一问,附件1、2分别为沿纵向切割后的19张中英文碎纸片,本文在考虑破碎纸片携带信息量较大的基础上,利用MATLAB对附件1、2的碎纸片图像分别读入,以数字矩阵的方式进行存储。

利用数字矩阵中包含图像边缘灰度这一特征,本文采用贪心算法的思想,在首先确定原文件左右边界的基础上,以Manhattan距离来度量两两碎纸片边界差异度,利用计算机搜索依次从左往右搜寻最匹配的碎纸片进行横向配对并达成排序目的。

最终,本文在没有进行人工干预,成功地将附件1、2碎纸片分别拼接复原,得到复原图片见附录2.1、2.2,纵切中文及英文结果表分别如下:为先对本文3、第4行及第9Spearman拼接复原1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片拼接复原模型和算法,并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预,请写出干预方式及干预的时间节点。

复原结果以图片形式及表格形式表达。

2. 对于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法,并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。

如果复原过程需要人工干预,请写出干预方式及干预的时间节点。

复原结果表达要求同上。

3. 上述所给碎片数据均为单面打印文件,从现实情形出发,还可能有双面打印文件的碎纸片拼接复原问题需要解决。

附件5给出的是一页英文印刷文字双面打印文件的碎片数据。

请尝试设计相应的碎纸片拼接复原模型与算法,并就附件5的碎片数据给出拼接复原结果,结果表达要求同上。

二、模型假设1. 假设原题附件给出的破碎纸片图像是完好无损的。

2. 假设原题附件给出的破碎纸片仅包含纯文字内容(中英文),不含表格线等。

3. 假设原题附件给出的破碎纸片在切割时无油墨损失。

4. 假设原题附件给出的破碎纸片文字方向与切割方向均为水平或垂直。

5. 假设原题附件给出的破碎纸片文字均为水平正向,无旋转。

三、符号说明255所有碎片构成碎片集S 。

4.2.2边界差异度模型对于一个给定的碎片,找到可以与之拼接的另一碎片的最重要的特征是其边界的列向量。

图片上连续的部分具有类似的结构,则相邻的列向量就具有类似的特征。

对碎片集S 中的碎片n ,其左右边界的灰度向量分别为,n R g 与,n L g ,寻找这个向量右侧最匹配的下一个碎片n +1,等价于在剩下的碎片中寻找到向量k ,满足边界差异度(,)(,1)n k n n δδ=+ (4.1)但是由于并不知道下一个碎片具体是哪一个碎片,所以实际上(,1)n n δ+的值是未知的。

然而可以假定两个匹配的碎片的边界差异度(,1)n n δ+的值是所有的边界差异度(,)n k δ中最小的。

则问题转化为在碎片集S 中寻找满足的碎片k 。

(,)min (,),n k n i i S δδ=∈ (4.2)对于边界差异度δ,可以用多种方法来定义,这个论题将在问题2作更加详细的阐述。

将边界向量g 视为一个180维空间中的一点,则二者的差异度可以用两点之间的“距离”来描述。

此处取Manhattan 距离,,(,)n R k Ln k g g δ=-∑ (4.3)4.3计算流程图1:问题一算法流程说明图问题一的拼接过程使用贪心算法,首先确定出最左侧的碎片1,然后从剩下的样本中寻找与碎片1的边界差异度最小的碎片作为下一个碎片,再寻找与第2个碎片配对的第3个碎片,以此类推。

碎片1判别为碎片左侧留白最宽者。

4.4问题一的结果4.55.15.25.2.1文字打印在纸张上时,是沿着一条直线的基准线排列的。

由于本文所研究的所有碎片均没有旋转,所有可以用比较简单的方法来搜索基准线。

在本文中,基准线是特征线中有特殊意义的一条。

确定特征线和基准线的目的有二:一是从碎片集S 中将属于同一高度的碎片聚类到第n 行碎片子集n S 中,二是通过特征线可以确定行碎片子集n S 的顺序,即各个行碎片子集n S 在纵向的排列,这个内容将在5.2.2详细阐述。

a )汉字的特征线(针对附件3)汉字的特性决定了汉字每一行中每个字的高度大致是相同的。

尽管可能出现如“一”等高度差异很大的汉字,但是这种情况非常少。

所以对于汉字,可以用上下两条特征线来描述汉字的位置,并且只需要少量的样本就能够确定出两条特征线。

图3:汉字的特征线对一行汉字的两条特征线,作如图的命名。

图4:汉字的特征线上边线(基准线)位置1L 与下边线位置2L 之差满足12c L L h -= (5.1)式中c h 为字高。

在计算中取44c h =。

碎片上第n 行的基准线位置1,n L 与下一行基准线位置1,1n L +之间的差异为1个行距H ,即1,1,1n n L L H +-= (5.2)行高 (5.3)式(b 3。

拉丁字 (5.4) 式中:m h 5.2.21,1,n k (5.5)5.2.3扩展的边界差异度模型由于本题中碎片的更小,碎片的边界向量信息有限,4.2.2中的模型不能满足要求,因此本文拓展了几种计算边界差异度δ的方法。

a )差分的Manhattan 距离比较边界向量的差分来确定差异度的目的在于消除数据序列的自相关,使得从有限的边界样本中提取的特征信息受到更少的干扰。

此处的边界差异度定义为,,(,)n R k Ln k g g δ=∆-∆∑ (5.6)上边线(基准线) 下边线b )广义Jaccard 系数Jaccard 系数又叫做Jaccard 相似性系数,用来比较样本集中的相似性和分散性的一个概率。

定义集合M 与N 的相似度函数计算公式如下:122111(,)pi ii pppiii ii i i m nsim M N m n m n=====+-∑∑∑∑ (5.7)式中,此处样本M ,N 为破碎纸片边缘各个像素点灰度的集合,p 为样本的维数,在本文中为破碎纸片边缘像素点分布的行数,i 为边缘上该像素点在边界上的行数。

,i i m n 分别为破碎纸片M 和N 在第i 行边缘上的像素点对应的灰度。

(,)sim M N 用于刻画M 与N 的边缘匹配度。

该系数的值越大,代表匹配性越好。

则差异度δ定义为其相反数(5.8)c )s r ,又称等(1的秩次。

若(2 (5.9) (3相关系数 (5.10)5.35.3.1a )汉字图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)未人工干预时情况(同一行内各碎片排序)我们分别基于四种方法对问附件3(中文)通过行聚类后得到的11组破碎纸片分别进行拼接,综合起来得到7个正确左右拼接的碎纸片行,剩余3个5.4中聚类出的行在左右拼接时出现了一些错误,需要我们进行人工适当的干预。

下图组号并非该行在原文件的真实位置,此处仅作为其暂时的代号。

注:下表√代表该组在该方法下正确左右拼接,×代表该组在这方法下正确左右拼接。

表3:不同判断方法中文拼接正确数量统计表11行中共3行需要人工干预,人工干预率为27.2%b)人工干预过程(同一行内各碎片排序)1.计算机排序效果如图12:人工干预后效果如图13:2.3.图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:不同判断方法英文拼接正确数量统计表2.第四组:计算机排序为:计算机排序效果如图20:图20:英文第四组计算机排序图人工干预:39,67,147作为整体移动到65后面。

下表为干预后顺序表: 人工干预后效果如图21: 图21:英文第四组人工干预排序图3.第五组: 计算机排序为:计算机排序效果如图22:图22:英文第五组计算机排序图人工干预:112与197对调。

下表为干预后顺序表: 人工干预后效果如图23:图23:英文第五组人工干预排序图4.第七组:计算机排序为: 计算机排序效果如图24:图24:英文第七组计算机排序图人工干预:将109和90,185整体对调。

下表为干预后顺序表: 人工干预后效果如图25:5.计算机排序效果如图26:人工干预后效果如图27:6.计算机排序效果如图28: 图28:英文第十人工干预后效果如图29: 图29:英文第十c 但此时这11行纵向相对的位置是不确定的,我们需要对聚类好的各行进行纵向拼接之后得到原文件。

我们由基准网格模型经过纵向拼接,得出了本问原文件的图片及碎片位置见附录1.4、2.4。

相关主题