全国大学生数学建模比赛B题答案Word格式.docx
《全国大学生数学建模比赛B题答案Word格式.docx》由会员分享，可在线阅读，更多相关《全国大学生数学建模比赛B题答案Word格式.docx（29页珍藏版）》请在冰点文库上搜索。
复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。
2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。
复原结果表达要求同上。
3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。
附件5给出的是一页英文印刷文字双面打印文件的碎片数据。
请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。
【数据文件说明】
（1）每一附件为同一页纸的碎片数据。
（2）附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。
（3）附件3、附件4为纵横切碎片数据，每页纸被切为11×
19个碎片。
（4）附件5为纵横切碎片数据，每页纸被切为11×
19个碎片，每个碎片有正反两面。
该附件中每一碎片对应两个文件，共有2×
11×
19个文件，例如，第一个碎片的两面分别对应文件000a、000b。
【结果表达格式说明】
复原图片放入附录中，表格表达格式如下：
（1）附件1、附件2的结果：
将碎片序号按复原后顺序填入1×
19的表格；
（2）附件3、附件4的结果：
将碎片序号按复原后顺序填入11×
（3）附件5的结果：
将碎片序号按复原后顺序填入两个11×
（4）不能确定复原位置的碎片，可不填入上述表格，单独列表。
二、模型假设
①假设题目中的碎纸图片与真实文件纸张大小、颜色、边缘情况相同。
②假设题目中的碎纸照片边缘完整，不存在破损。
③假设所有碎纸片的扫描情况相同。
④假设人工干预后可以得到正确结果。
⑤假设原文件纸张的内容具有意义。
三、符号说明
符号
符号意义
编号为
的图片的灰度矩阵
的图片经二值化处理后的矩阵
的图片的二维边缘矩阵
、
边缘匹配度矩阵
编号为i的图片在此处理后的二值化矩阵
边缘匹配度之和矩阵
*其他未提及的符号会在文章中说明。
四、问题分析
4.1问题一的分析
4.1．1中文碎纸片的复原分析
问题1、2、3附件1、2、3、4、5中的碎纸片均为一份纸张撕裂所得，所以碎纸片中不会存在含有相同信息的公共部分，这里进行强调，下面不再重述。
附件1中所给的图片为[5]扫描原纸张碎片后得到的BMP格式的图片，图片像素均为
，使用[1]matlab中的iamread函数可以做出图片的灰度矩阵
，举例如下（由于该像素图片转换后为
的矩阵，论文中无法放置，所以仅简单举例说明，论文中若还出现庞大的矩阵，同本说明）：
矩阵的中元素表示该位置图片的灰度，255表示为白，0为黑，图片中信息为黑白文字信息，但由于文字信息会存在阴影，所以矩阵中出现了介于0-255的元素。
为了方便应用，并查阅相关资料所得，可以对于本题中的黑白图片做[2]二值化处理，可将上面例子中的
转化为如下的矩阵：
其中白色用0值表示，非白色用1表示。
将附件1中的19张图片做如上处理得到各自的二值化后的矩阵Bi，矩阵均为
的矩阵，这里我们分别将每张图片的Bi矩阵第1列和第72列提取出来做一新的二维边缘矩阵Ci，它是
的矩阵。
通过对所有图片矩阵的分析可以发现C6、C8矩阵中均有一列为0，所以可以认为编号为006和008的图片为原完整文件的一端，在做题过程中无需考虑会存在其他白边与白边拼接的情况。
两张图片匹配的原则可以根据下面的图1、图2来表示。
图1.图片未倒置图2.图片倒置
如图1，当图片未出现倒置情况时，即题目中的图片均是正常摆放，将左边矩阵的第二列元素与右边矩阵的第一列元素进行两两匹配。
记录元素相同的个数，个数除以1980为左边矩阵第二列对右边矩阵第一列的边缘匹配度，记为：
将所有碎纸片的二值化矩阵做如上匹配可依次选取与其匹配的碎纸片。
图1中左边矩阵第一列与右边矩阵第二列匹配的原则与上述相同，不再重述。
如图2，当图片出现倒置情况时，正常情况下应是左边矩阵的第二列元素与右边矩阵的第一列元素进行两两匹配，若倒置后，则应该是左边矩阵的第二列元素与右边矩阵的第二列元素倒置顺序进行比较，同样记录相同元素的个数并计算匹配度。
图2中左边矩阵第一列元素与右边矩阵第一列元素的匹配原则与上述相同，不再重述。
综合图一图二我们可以做出4个边缘匹配度的矩阵，即未倒置时矩阵第一列与其他矩阵第二列的边缘匹配度、未倒置时矩阵第二列与其他矩阵第一列的边缘匹配度、倒置时矩阵第一列与其他矩阵第一列的边缘匹配度、倒置时矩阵第二列与其他矩阵第二列的边缘匹配度。
由于（未）倒置时矩阵第一列与其他矩阵第二列匹配在思想上同（未）倒置时矩阵第二列与其他矩阵第一列匹配相同，所以这里只需考虑其中一种情况即可。
任选其中一例说明，由于碎纸片倒置情况未知，需要考虑未倒置时的情况与倒置式的情况，未倒置时矩阵第一列与其他矩阵第二列的边缘匹配度矩阵第一行最大值与倒置时矩阵第一列与其他矩阵第一列的边缘匹配度第一行的最大值进行比较，选取匹配度大的作为拼接的纸片，即编号为000的碎纸片要与该纸片拼接。
以此类推把19张碎纸片拼接完成后做人工处理。
4.1.2英文碎纸片的复原分析
将附件2的19张图片做4.11中处理得到二值化后的矩阵Bi，矩阵均为
通过对所有图片矩阵的分析可以发现C3、C4矩阵中均有一列为0，所以可以认为编号为003和004的图片为原完整文件的一端，在做题过程中
无需考虑会存在其他白边与白边拼接的情况。
做如上判断后解题过程同4.11。
4.2问题二的分析
4.2．1中文碎纸片的分析
此问中同4.1的图片处理方法，也需要将209张碎纸片进行同样的图像处理转化为灰度矩阵后进行二值化处理得到处理后的矩阵。
根据结果知此问中的图片转化后的矩阵为
的矩阵，列数由第一问中的1980变为180，虽然数量变少，但是图片数量由19张变为了209张。
若同样使用4.1中的边缘匹配的方法，一张碎纸片对应其他208张碎纸片的边缘匹配相同的像素点有208种情况，变化范围为0-180，可知若直接采用4.1中的方法得到的结果可能出现多个相同或无法判断的情况，所以这里我们先考虑附件3中碎纸片的特性。
观察下面的图3可以发现，通过查阅资料分析[2]基于文字特征的文档碎纸片半自动拼接，每一行的绝大多数中文文字均可认为拥有同一上界、同一下界（图3最右端出现了“一”字，但是同行还存在其他文字，可以认为同一行文字有同一上界与同一下界），我们可以根据这一特性使用软件将[3]匹配度高及位置相同的碎纸片归类为一组。
方法为：
搜索每一张碎纸片转化后二值化矩阵
的每一行，若矩阵该行中存在数值1，则将该行全部赋值为1，若这一行元素全为0，则将该行全部赋值为0，其中1表示本行存在灰度小于255的像素，0表示不存在灰度小于255的像素，这样将209张碎纸片做出[4]新的二值化矩阵
，之后同4.1的分析取边缘做边缘匹配得修改后的[6]边缘匹配度矩阵
，匹配度高则说明碎纸片的文字信息处于同一水平位置，见下图图4，之后再人工干预，得到较优的结果。
图3.处理的图片
图4.再次处理后的图片
得到很多组有相同位置的的碎纸片后，在每一组内采用4.1的中的边缘匹配方法，这里为了防止出现两白边匹配造成碎纸片连接混乱的现象，要加以限制。
若在组内做边缘匹配出现匹配度为1的情况，则暂时不连接此碎纸片，从剩余的碎纸片出发做边缘匹配与其他碎纸片连接，直到组内所有碎纸片均已覆盖。
这样再通过一定的人工干预可以得到拼接复原后的的11横行碎纸片，在同样使用4.1的边缘匹配方法，[7]将得到的11行的碎纸条的长边进行边缘匹配做出
的匹配度矩阵后找最大匹配度作为连接的碎纸条，同样为了防止出现两白边匹配造成碎纸片连接混乱的现象，要加以限制。
若在组内做边缘匹配出现匹配度为1的情况，则暂时不连接此碎纸片，从剩余的碎纸片出发做边缘匹配与其他碎纸片连接，直到11张拼接后的碎纸片均已覆盖。
最后加以人工处理，得到完整的原文件。
4.2.2英文碎纸片的分析
同4.2.1中的分析相同，通过观察我们可以发现碎纸片的英文在位置上也有一定的规则可循。
如下图图5。
图5.演示的图片
可以发现英文字母的主要的部分拥有同一上界和同一下界，但是跟中文不同，英文中会出现一些“y”、“b”之类的字母，为了同样使用4.2.1中的方法我们通过观察附件4中图片的像素情况，将图片中每一行中黑色像素数少于13的及字母的次要部分转变为二值化矩阵中的0，将每一行中黑色像素大于等于13的及字母的主要部分转化为二值化矩阵中的1，这样得到的新的二值化矩阵
，可认为图像转变为图6的方式，同样使用4.2.1中的分析方法将新的二值化矩阵做边缘匹配，匹配度高的可以认为两碎纸片在原纸张中位于同一行，把匹配度高于0.9的元素分为一组后，对每一组进行边缘匹配。
由于考虑到英文字符的情况，在4.1的基础上，我们对于组内图片原始二值化矩阵的边缘匹配度矩阵
每一行的搜索，在这里我们若矩阵的任意一行中出现匹配度大于0.9的元素个数超过2个，我们加以人工干预，根据文章的格式、内容选择应该连接的碎纸片，其他过程与4.1相同，区别仅为本文中需要对软件执行过程进行人工干预，其他相同的步骤不在重述。
图6.演示图片
4.3问题三的分析
本问在问题二英文碎纸片的基础上还需要考虑纸片是否处于同一面，虽然数据量增加了一倍，但是判断碎纸片是否连接的标准由一面增加到了两面。
本不对应的两张碎纸片一面的拼接复原情况好而令一面复原情况也好的情况只是个别的案例，所以可以将碎纸片两面边缘匹配度之和作为评判两张是否匹配的标准建立边缘匹配度之和矩阵
，在这里可以先认为匹配度之和高于1.9的情况为匹配结果优秀。
若仅将匹配度之和作为评判标准，基于4.2.2中的求解过程，英文碎纸片的纯计算机复原结果较差，所以还需要在计算机匹配碎纸片的过程中每一步都要进行人工干预判断、选择。
以纸片000与001为例，匹配方式可能为：
为了找出碎纸片如何对应，则将①②的边缘匹配度相加得到边缘匹配度之和，将③④的边缘匹配度相加得边缘缘匹配度之和，两者的和做出比较。
若仅有一个大于等于1.9，则计算机输出该匹配度，人工判断是否碎纸片是否匹配；
若两者均大于等于1.9，计算机把两个匹配度之和输出，人工选择判断碎纸片应是否匹配与如何匹配；
若两者均小于1.9，则计算输出最大者，人工判断碎纸片是否匹配。
若出现计算机给出的结果人工判断后发现匹配错误，则记录当前匹配成功的碎纸片信息并在剩下的碎纸片中重新开始计算机匹配与人工判断。
上述的结果可以得到一些在同一横行的碎纸片的拼接，再次根据这些新的碎纸片的边缘匹配度之和的情况通过上述人机结合的方法拼出11张横行的碎纸片，剩下的就是应该如何把11张横行的碎纸片拼接成完整的一份纸张，这里将11张横行碎纸片的上下长边进行两两匹配，以两面边缘匹配度之和的方法按照上述的方法将11横行的碎纸片拼接完毕。
五、模型的建立与求解
5.1问题一的模型建立与求解
5.1.1中文碎纸片的拼接复原
根据4.1.1中的分析，做出
的矩阵D、矩阵D’、矩阵D’’、矩阵D’’’（这里仅做出D’与D’’，其他两个矩阵仅在下面的说明中会提及，但不会使用），元素Dij为碎纸片图像未倒置时矩阵i的第二列与矩阵j第一列的边缘匹配度，元素Dij’为碎纸片图像倒置时矩阵i的第二列与矩阵j的第二列的边缘匹配度，元素Dij’为碎纸片图像倒置时矩阵i的第一列与矩阵j第一列的边缘匹配度，元素Dij’’为碎纸片图像未倒置时矩阵i的第一列与矩阵j第二列的边缘匹配度。
对于得到的两个矩阵
，从i=0即第0行（为方便说明）开始，找到这一行中最大的匹配度
，两者进行大小比较：
1）若
大于等于
，把
所处列数赋值为新的i，找到这一行中的最大匹配度
，两者进行大小比较，重复上述过程直到i重新变为0。
若i经过19次后返回0，则可以认为所有的碎纸片已拼接在一起，仅需把两个空白端分开后再做人工调整，则可得到结果；
若i少于19次变化后变为0，则认为部分碎纸片未拼在一起，要把剩余的纸片拼接在一起后做人工调整。
2）若
小于
所处的列数赋值为新的i，找到矩阵
这一行中的最大匹配度
，两者进行大小比较，其他过程与上述分析类似，不再进行说明，重复上述过程直到i重新变为0。
根据所得两个矩阵
的情况，发现任意一行的
大于
，可以一定程度说明碎纸片中不存在倒置的情况，仅按上述
的情况做分析即可。
该方法可以用图7的matlab软件编程流程图来表示。
可以看出由于问题一中的数据量较小，为了方便我们仅对计算机的编程结果进行人工干预，而不对过程做人工干预。
图7.流程图
得到的结果见表1：
表1.计算机拼图位置表格1
000
006
008
014
012
015
003
010
002
016
001
004
005
009
013
018
011
007
根据表种情况可已发现碎纸片006和碎纸片008连接在一起，发生这种情况的原因是两白边边缘匹配度为1.0，所以他们匹配在了一起，根据实际情况，可以判定碎纸片008为正常放置情况下原纸张的左端，所以重新指定表格，以碎纸片008作为纸片的开端，表格见表2，在使用matlab中的imshow（）函数，得到人机结合后的复原图片。
表2.修改后的拼图位置表格2
5.1.2英文碎纸片的拼接复原
根据4.1.1与4.1.2的分析，模型建立求解同5.1.1。
使用计算求解的结果见表3。
表3.计算机拼图位置表格3
017
根据表种情况可已发现碎纸片003和碎纸片004连接在一起，发生这种情况的原因是两白边边缘匹配度为1.0，所以他们匹配在了一起，根据实际情况，可以判定碎纸片003为正常放置情况下原纸张的左端，所以重新指定表格，以碎纸片003作为纸片的开端，表格见表3，在使用matlab中的imshow（）函数，人机结合后的复原图片见图片5。
表4.修改后的拼图位置表格4
5.2问题二模型的建立与求解
5.2．1中文碎纸片复原的模型建立与求解
搜索每一张碎纸片转化后二值化矩阵
的每一行，若存在黑色即矩阵该行中存在数值1，则将该行全部赋值为1，若这一行不存在黑即此行元素全为0，则将该行全部赋值为0，这样将209张碎纸片做出新的二值化矩阵
，之后同5.1的求解过程做边缘匹配，做出矩阵大小为
（由于矩阵太大，在论文中不作出），元素
为处理后的碎纸片边缘二值化矩阵i的第二列与处理后的碎纸片边缘二值化矩阵j第一列的边缘匹配度，匹配度高则说明碎纸片的文字信息处于同一水平位置。
在矩阵
中每一行选取匹配度大于0.9的元素，进行统计分组，可得结果如下表表5.
表5.分组情况
序号
碎纸片编号
1
07455368126137138158174175208
2
118232630415062768687100120142147168179191195
3
2112228495457659195118129141143178186188190192
4
3123139517382107115128134135159160169176199203
5
440101108113114117119123140146151154155185194207
6
51029374448555964759298104111171172180201206
7
619203652616367697278799699116131162163177
8
892574105
9
18213
10
15
17
33
80
83
132
133
156
198
200
202
11
162166106109110139145150157173181184187197204
12
243538468188103122130148161167189193
13
276085152165170205
14
32567093153166196
15
34424347587784909497112121124127136144149164183
16
17
71
18
89
19
102
20
125
可以看出在取匹配度为0.9及以上时，分出了20个组，其中组内元素最多的为19，组内元素最少的为1。
而最后的结果应该为11行，我们需要对这些组中的元素进行合并后得到11行，所以我们要先考虑元素数量为19的组，再考虑其他元素数多的组，对组内图片进行5.1中的边缘匹配，匹配后的结果在与元素数少的组做匹配与人工处理。
以序号2的组为例，该组包含19个元素，对于组内的19个元素的原始二值化矩阵进行上述中的边缘匹配，通过结果观察本题模型第一步确定模型的的可行性，其他的组的处理情况相同，不再重述。
结果如下，见表6。
表6.内部分组
分组
062-142-030-041-023-147-191-050-179-120-086-195-026-001-087-018
168-100-076
分别复原得到图片，观察下面的图8、图9。
图8
图9
对于第二问中文碎纸片的复原问题，通过上面的结果发现匹配结果较好，对于中文的碎纸片的拼接复原即使过程中未加入人工干预也可以得到较优的结果。
可以发现该组中文字的位置符合我们的想象，及同一行中的文字拥有同一上界和同一下界，在这一组中matlab软件很好的将碎纸片拼接出来，思考为什么会出现上面图9图10两者不能匹配在一起的原因。
可以发现拼接复原后的图8、图9左右两侧均存在白边，仅从计算机的角度出发，无法认出两者的先后，所以这里我们要加以人工干预，通过对文章的内容、文章的结构、文章的形式的观察人工拼接，得出结果。
改进后的图片排序见表7，复原图片见图10。
表7.人工干预
168-100-076-062-142-030-0
升级会员 