全国大学生数学建模竞赛B题全国一等奖论文.docx
《全国大学生数学建模竞赛B题全国一等奖论文.docx》由会员分享，可在线阅读，更多相关《全国大学生数学建模竞赛B题全国一等奖论文.docx（33页珍藏版）》请在冰点文库上搜索。
全国大学生数学建模竞赛B题全国一等奖论文
IMBstandardizationoffice【IMB5AB-IMBK08-IMB2C】
全国大学生数学建模竞赛B题全国一等奖论文
碎纸片的拼接复原
【摘要】
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。
本文主要解决碎纸机切割后的碎纸片拼接复原问题。
针对第一问，附件1、2分别为沿纵向切割后的19张中英文碎纸片，本文在考虑破碎纸片携带信息量较大的基础上，利用MATLAB对附件1、2的碎纸片图像分别读入，以数字矩阵的方式进行存储。
利用数字矩阵中包含图像边缘灰度这一特征，本文采用贪心算法的思想，在首先确定原文件左右边界的基础上，以Manhattan距离来度量两两碎纸片边界差异度，利用计算机搜索依次从左往右搜寻最匹配的碎纸片进行横向配对并达成排序目的。
最终，本文在没有进行人工干预，成功地将附件1、2碎纸片分别拼接复原，得到复原图片见附录、，纵切中文及英文结果表分别如下:
9
15
13
16
4
11
3
17
2
5
6
10
14
19
12
8
18
1
7
4
7
3
8
16
19
12
1
6
2
10
14
11
9
13
15
18
17
5
针对第二问，附件3、4分别为既横切又纵切后的209张中英文碎纸片，本文核心思想仍为贪心算法，整体思路为先对209张碎纸片进行聚类还原成11行，再对分好的每行进行横向排序，最后对排序好的各行进行纵向排序。
本文在充分考虑汉字与拉丁字母结构特征差异以及每块碎纸片携带信息减少的基础上，创新地提出一种特征线模型来分别描述汉字及拉丁文字母的特征用于行聚类。
对于行聚类后碎片的横向排序，本文综合了广义Jaccard系数、一阶差分法、二阶差分法、Spearman系数等来构建扩展的边界差异度模型，刻画碎片间的差异度。
对于计算机横向排序存在些许错误的情况，本文给出了人工干预的位置节点和方式。
对于横向排序后的各行，由于在一页纸上，文字的各行是均匀分布的，本文基于各行文字的特征线，在确定首行的位置后，估计出其他行的基准线位置，得到一页的基准线网格，并通过各行基准线在基准线网格上的适配实现纵向的排序。
最终，本文成功的将附件3、4碎纸片分别拼接复原得到复原图片及结果表见附录、、、，同时本文给出了横向排序中人工干预的位置节点和方式。
针对第三问，附件5为双面文件既横切又纵切后的209张碎片（包含正反面），即包含418张图像。
本文整体解决思路同第二问中对于拉丁文碎片的复原类似，并且由于正反两面的特征可以同时作为差异度判断条件，特征信息丰富，综合使用各种差异度函数后可以将各行全部正确排列，无需人工排错，同时正确排序时自然分出两面。
以与问题二类似的方法，确定出每一面的第一行后，用基准线网格确定各行的位置并排序。
然而由于附件5原件的第3、第4行及第9、第10行的两个切口正好切到了两行行间的空白，同时两面文字高度一致，所以计算机不可能分辨二者是否在同一面，此处必须由人工介入，通过上下文区分。
最终，本文成功的将附件5所有碎片分别拼接复原得到复原图片及结果表见附录、、、。
对于本问题，本文只在最后模块的上下文判断和横向排列的方法选择时进行了干预，自动化程度高。
本文发现在横向排序中，一、二阶差分法对于样本量大的情况适配成功率很高，而广义Jaccard系数及Spearman系数则对样本量小但特征显着的情况适配的成功率更高。
关键词：
图像拼接复原贪心算法差异度相似系数文字基准线
一、问题重述
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。
传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。
特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。
随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。
请讨论以下问题：
1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
复原结果以图片形式及表格形式表达。
2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
如果复原过程需要人工干预，请写出干预方式及干预的时间节点。
复原结果表达要求同上。
3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。
附件5给出的是一页英文印刷文字双面打印文件的碎片数据。
请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。
二、模型假设
1.假设原题附件给出的破碎纸片图像是完好无损的。
2.假设原题附件给出的破碎纸片仅包含纯文字内容（中英文），不含表格线等。
3.假设原题附件给出的破碎纸片在切割时无油墨损失。
4.假设原题附件给出的破碎纸片文字方向与切割方向均为水平或垂直。
。
5.假设原题附件给出的破碎纸片文字均为水平正向，无旋转。
三、符号说明
序号
符号
说明
1
S
碎片集
2
碎片n的右边界向量
3
碎片n的左边界向量
4
碎片n与碎片k的边界差异度
5
L
特征线位置
6
H
行高
7
、
、
、
标高、余高、空高、字高
四、问题一：
仅纵切时的纸片拼接复原
问题一的分析
本题的所有碎片为形状一致的矩形，且均为黑白文字，文字边缘有灰色部分。
由于原图切割前的信息具有一定的连续性，本文希望遵循这一思路，首先确定出碎片中的位置为最左的一个，再以之为基础，在剩下的碎片中寻找可以与之配对（或配对情况最好）的一个碎片。
问题一的数学模型
4.2.1灰度矩阵与灰度向量模型
描述碎片的模型为图像的灰度矩阵，灰度矩阵的每个元素对应到图像上的每个像素点，取值为0（白色）到255（黑色）。
每个碎片均可以确定一个同型的灰度矩阵，灰度矩阵的特征反映了图像的特征。
灰度矩阵的每一列构成了一个描述局部特征的列向量，在图片上的宽度为1像素。
所有碎片构成碎片集S。
4.2.2边界差异度模型
对于一个给定的碎片，找到可以与之拼接的另一碎片的最重要的特征是其边界的列向量。
图片上连续的部分具有类似的结构，则相邻的列向量就具有类似的特征。
对碎片集S中的碎片n，其左右边界的灰度向量分别为
与
，寻找这个向量右侧最匹配的下一个碎片n+1，等价于在剩下的碎片中寻找到向量k，满足边界差异度
（）
但是由于并不知道下一个碎片具体是哪一个碎片，所以实际上
的值是未知的。
然而可以假定两个匹配的碎片的边界差异度
的值是所有的边界差异度
中最小的。
则问题转化为在碎片集S中寻找满足的碎片k。
（）
对于边界差异度
，可以用多种方法来定义，这个论题将在问题2作更加详细的阐述。
将边界向量g视为一个180维空间中的一点，则二者的差异度可以用两点之间的“距离”来描述。
此处取Manhattan距离
（）
计算流程
图1：
问题一算法流程说明图
问题一的拼接过程使用贪心算法，首先确定出最左侧的碎片1，然后从剩下的样本中寻找与碎片1的边界差异度最小的碎片作为下一个碎片，再寻找与第2个碎片配对的第3个碎片，以此类推。
碎片1判别为碎片左侧留白最宽者。
问题一的结果
本题未经过人工干预，完全由计算机自动拼接出结果如下（图片结果详见附录、）。
拼接顺序如下：
表1：
附件1（仅纵切中文）的顺序表
9
15
13
16
4
11
3
17
2
5
6
10
14
19
12
8
18
1
7
表2：
附件2（仅纵切英文）的顺序表
4
7
3
8
16
19
12
1
6
2
10
14
11
9
13
15
18
17
5
模型评价与推广
本模型对于碎纸条为大面积的有较好的识别和排序准确度，能够全自动化进行计算机排序，但是此模型仅适用于比较样本点较丰富的大面积碎纸条，对于细小纸条效果不会太好，在问题二中会对其进行改进。
五、问题二：
既纵切又横切时的纸片拼接复原
问题二的分析
由于问题二破碎纸片为及纵切又横切产生，其复杂程度及处理难度要远远高于问题一。
此时采用问题一中单纯的考虑纵切时的方式已经无法解决此文，但仍可以第一问的思想为基础，考虑到本题附件3给出的破碎纸片竖直高度远大于水平长度，即破碎纸片纵向上包含的特征信息远多于横向。
若采用先沿横向方向选出每一行包含的碎纸片，再拼接复原该行，再将拼接好的每行沿纵向方向进行拼接，这又回归到问题一这类单方向切断的拼接问题。
整体拼接思路如下：
图2：
问题二拼接示意图
问题二的数学模型
问题二在沿用中的模型的基础上，增加几个专门的模型。
5.2.1特征线模型
文字打印在纸张上时，是沿着一条直线的基准线排列的。
由于本文所研究的所有碎片均没有旋转，所有可以用比较简单的方法来搜索基准线。
在本文中，基准线是特征线中有特殊意义的一条。
确定特征线和基准线的目的有二：
一是从碎片集S中将属于同一高度的碎片聚类到第n行碎片子集
中，二是通过特征线可以确定行碎片子集
的顺序，即各个行碎片子集
在纵向的排列，这个内容将在5.2.2详细阐述。
a）汉字的特征线（针对附件3）
汉字的特性决定了汉字每一行中每个字的高度大致是相同的。
尽管可能出现如“一”等高度差异很大的汉字，但是这种情况非常少。
所以对于汉字，可以用上下两条特征线来描述汉字的位置，并且只需要少量的样本就能够确定出两条特征线。
图3：
汉字的特征线
对一行汉字的两条特征线，作如图的命名。
图4：
汉字的特征线
上边线（基准线）位置
与下边线位置
之差满足
（）
式中
为字高。
在计算中取
。
碎片上第n行的基准线位置
与下一行基准线位置
之间的差异为1个行距H，即
（）
对于一个碎片，确定出其中一行的上边线和下边线后，只要对行高做出估计，就可以得到其他行的水平特征线，以此可以估计出该碎片中空行的位置。
计算中取行高
。
图5：
通过特征线和行距估计空行的位置图
行高H与字高
之间的差值为空高，即行间距：
（）
式（）、（）和（）表达了汉字各特征线的约束关系。
b）拉丁字母的特征线（针对附件4）
拉丁字母的特征线模式比汉字要复杂。
由于拉丁字母相互之间高度差异较大，所以无法照搬汉字的模式。
本文用四条特征线来描述一行拉丁字母。
图6：
拉丁字母的特征线
拉丁字母四条特征线的位置分别为：
上边线位置
，上标线位置
，下标线位置
，下边线位置
。
拉丁字母的基准线为上标线。
各特征线满足由以下各式决定的约束关系：
（）
式中：
——标高，即上标线与下标线的距离；
——余高，即同侧边线与标线之间的距离。
计算中取
，
，
。
5.2.2基准网格模型
由于一页纸上，文字的各行是均匀分布的，所以一旦确定一行的位置就能确定一页纸上所有文字行的基准线的位置。
基准线位置的关系满足
（）
5.2.3扩展的边界差异度模型
由于本题中碎片的更小，碎片的边界向量信息有限，4.2.2中的模型不能满足要求，因此本文拓展了几种计算边界差异度
的方法。
a）差分的Manhattan距离
比较边界向量的差分来确定差异度的目的在于消除数据序列的自相关，使得从有限的边界样本中提取的特征信息受到更少的干扰。
此处的边界差异度定义为
（）
b）广义Jaccard系数
Jaccard系数又叫做Jaccard相似性系数，用来比较样本集中的相似性和分散性的一个概率。
定义集合M与N的相似度函数计算公式如下：
（）
式中，此处样本M，N为破碎纸片边缘各个像素点灰度的集合，p为样本的维数，在本文中为破碎纸片边缘像素点分布的行数，i为边缘上该像素点在边界上的行数。
分别为破碎纸片M和N在第i行边缘上的像素点对应的灰度。
用于刻画M与N的边缘匹配度。
该系数的值越大，代表匹配性越好。
则差异度
定义为其相反数
（）
c）Spearman相关系数
Spearman相关系数：
对不服从正态分布的资料、原始资料等级资料、一侧开口资料、总体分布类型未知的资料不符合使用积矩相关系数来描述关联性。
此时可采用秩相关，也称等级相关，来描述两个变量之间的关联程度与方向。
这类方法对原始变量分布不作要求，属于非参数统计方法。
其中最常用的统计量是Spearman秩相关系数
，又称等级相关系数。
计算步骤：
（1）编秩：
将两变量X、Y成对的观察值分别从小到大顺序编秩，用pi表示xi的秩次；用qi表示yi的秩次。
若观察值相同取平均秩次。
（2）将秩次带入公式计算：
（）
（3）由样本算得的秩相关系数是否有统计学意义，应作假设检验。
鉴于本文由图像得到的数字矩阵不具有正态分布的特征，且原始资料数据量较大。
我们采用Spearman相关系数来刻画水平方向各碎片拼接在一行的匹配度。
图7：
Spearman相关系数判断实施步骤
与广义Jaccard系数类似，Spearman相关系数越大代表匹配度越高，差异度也定义为其相反数：
算法的实施与模型的求解
图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.同一行内各碎片排序
沿用的计算方法。
由于本问题中，每个碎片至少包含3行文字，不存在由于空行而导致左边界误判的问题，所以对首个碎片的判别依然是有效的。
B.同一页各行的排序
对于至今得到的11个碎片行，首先寻找首行。
基于文字页的性质，首行的判别方法为一行顶部留白最宽者。
确定出首行之后，根据首行的基准线，由式（）知
可以推算出页面上所有基准线的位置。
在第1个碎片行已经放到页面上以后，在剩下的碎片行中搜索基准线与页面上下一条未覆盖基准线相匹配的一个，并继续向下迭代直到找出所有碎片行。
至此，该页所有碎片拼接完成。
问题二结果
5.4.1附件3（中文）的拼接
组号
方法
1
2
3
4
5
6
7
8
9
10
11
拼接正确数量统计
广义Jaccard系数
√
×
×
×
√
√
×
×
×
×
×
3
一阶差分
√
√
×
√
×
√
√
×
×
×
√
6
二阶差分
×
√
×
√
×
√
√
×
×
×
√
5
Spearman相关系数
√
×
×
×
×
√
×
×
√
×
×
3
所有方法综合统计
√
√
×
√
√
√
√
×
√
×
√
8
a）未人工干预时情况（同一行内各碎片排序）
我们分别基于四种方法对问附件3（中文）通过行聚类后得到的11组破碎纸片分别进行拼接，综合起来得到7个正确左右拼接的碎纸片行，剩余3个中聚类出的行在左右拼接时出现了一些错误，需要我们进行人工适当的干预。
下图组号并非该行在原文件的真实位置，此处仅作为其暂时的代号。
注：
下表√代表该组在该方法下正确左右拼接，×代表该组在这方法下正确左右拼接。
表3：
不同判断方法中文拼接正确数量统计表
11行中共3行需要人工干预，人工干预率为%
b）人工干预过程（同一行内各碎片排序）
有少许错误的组为：
3,8,10组，下面采取人工干预方式进行微调：
1.第三组
计算机排序为：
（表格序号已与下方图片对齐，下同）
49
54
65
143
186
2
57
192
178
118
190
95
129
28
91
188
141
11
22
计算机排序效果如图12：
（红色指示为错误处及干预过程）
图12：
第三组计算机排序图
人工干预：
将尾部的11,12整体平移到129前面。
下表为干预后顺序表。
49
54
65
143
186
2
57
192
178
118
190
95
11
22
129
28
91
188
141
人工干预后效果如图13：
图13：
第三组人工干预排序图
2.第八组:
计算机排序为：
38
148
74
161
24
35
81
189
122
103
130
193
88
167
25
8
9
105
46
计算机排序效果如图14：
（红色指示为错误处及干预过程）
图14：
第八组计算机排序图
人工干预:
将46和74对调。
下表为干预后顺序表。
38
148
46
161
24
35
81
189
122
103
130
193
88
167
25
8
9
105
74
人工干预后效果如图15：
图15：
第八组人工干预排序图
3.第十组:
计算机排序为：
71
156
80
33
202
198
15
133
170
205
85
152
165
27
60
83
132
200
17
计算机排序效果如图16：
图16：
第十组计算机排序图
人工干预：
将尾部的83,132,200,17作为整体插入到80前面。
下表为干预后顺序表。
71
156
83
132
200
17
80
33
202
198
15
133
170
205
85
152
165
27
60
人工干预后效果如图17：
图17：
第十组人工干预排序图
c）纵向拼接（同一页各行的排序）
附表3的破碎纸片原文件应为11行*19列，经过本文中的聚类分析先将209个碎纸片分为了11组，当然，此时的每组的碎片应该归属于同一行，但他们在同一行的位置却未能确定。
之后我们分别采用4种方法利用各自的特征值对每组碎纸片进行左右拼接，最后我们综合4种方法的结果加上适当的人工干预得出了原文件的11行，但此时这11行纵向相对的位置是不确定的，我们需要对聚类好的各行进行纵向拼接之后得到原文件。
我们由基准网格模型经过纵向拼接，得出了本问原文件的图片及碎片位置见附录、。
5.4.2附件4（英文）的拼接
a）未人工干预时情况（同一行内各碎片排序）
我们分别基于四种方法对问附件3（中文）通过行聚类后得到的11组破碎纸片分别进行左右拼接，综合起来得到7个正确左右拼接的碎纸片行，剩余3个中聚类出的行在左右拼接时出现了一些错误，需要我们进行人工适当的干预。
下图组号并非该行在原文件的真实位置，此处仅作为其暂时的代号。
注：
下表中√代表该组在该方法下正确左右拼接，×代表该组在这方法下正确左右拼接。
表4：
不同判断方法英文拼接正确数量统计表
组号
方法
1
2
3
4
5
6
7
8
9
10
11
拼接正确数量统计
广义Jaccard系数
×
×
×
×
×
√
×
×
×
√
×
2
一阶差分
×
√
×
×
×
×
×
×
×
×
×
1
二阶差分
×
×
×
×
×
×
×
×
×
√
×
1
Spearman相关系数
×
√
√
×
×
√
×
×
√
×
×
4
所有方法综合统计
×
√
√
×
×
√
×
×
√
√
×
5
11行中有6行需要进行微量的人工干预，人工干预度为%。
b）人工干预过程（同一行内各碎片排序）
有少许错误的组为：
1,4,5,7,8,11组，尽管从行数上计算人工干预度达到%，但从下面的人工干预力度来看，实际大部分错误行需要调节的力度很小。
下面采取人工干预方式进行微调：
1.第一组：
计算机排序为:
19
194
93
141
88
121
126
105
155
114
176
202
71
165
82
182
151
22
57
计算机排序效果如图18：
（红色指示为错误处及干预过程，下同）
图18：
英文第一组计算机排序图
人工干预：
202，71，165，82作为整体移到57后面。
下表为干预后顺序表：
19
194
93
141
88
121
126
105
155
114
176
182
151
22
57
202
71
165
82
人工干预后效果如图19：
图19：
英文第一组计算机排序图
2.第四组：
计算机排序为：
191
75
11
154
190
184
2
104
180
64
106
4
39
67
147
149
32
204
65
计算机排序效果如图20：
图20：
英文第四组计算机排序图
人工干预：
39，67，147作为整体移动到65后面。
下表为干预后顺序表：
191
75
11
154
190
184
2
104
180
64
106
4
14
升级会员 