全国大学生数学建模比赛B题 答案.docx
《全国大学生数学建模比赛B题 答案.docx》由会员分享，可在线阅读，更多相关《全国大学生数学建模比赛B题 答案.docx（51页珍藏版）》请在冰点文库上搜索。
全国大学生数学建模比赛B题答案
2021高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规那么.
我们完全明白，在竞赛开场后参赛队员不能以任何方式〔包括、电子邮件、网上咨询等〕与队外的任何人〔包括指导老师〕研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违背竞赛规那么的,假如引用别人的成果或其他公开的资料〔包括网上查到的资料〕，必须按照规定的参考文献的表述方式在正文引用途和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规那么，以保证竞赛的公正、公平性。
如有违背竞赛规那么的行为，我们将受到严肃处理。
我们参赛选择的题号是〔从A/B/C/D中选择一项填写〕：
B
我们的参赛报名号为〔假如赛区设置报名号的话〕：
所属学校〔请填写完好的全名〕：
重庆邮电大学
参赛队员（打印并签名）：
1.
2.
3.
指导老师或指导老师组负责人（打印并签名）：
日期：
2021年9月13日
赛区评阅编号〔由赛区组委会评阅前进展编号〕：
2021高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号〔由赛区组委会评阅前进展编号〕：
赛区评阅记录〔可供赛区评阅时使用〕：
评
阅
人
评
分
备
注
全国统一编号〔由赛区组委会送交全国前编号〕：
全国评阅编号〔由全国组委会评阅前进展编号〕：
碎纸片的拼接复原
摘要
本文研究的是碎纸片的拼接复原问题。
由于人工做残片复原虽然准确度高，但有着效率低的缺点，仅由计算机处理复原，会由于各类条件的限制造成误差与错误，所以为理解决题目中给定的碎纸片复原问题，我们采用人机结合的方法建立碎纸片的计算机复原模型解决残片复原问题，并把计算机通过算法复原的结果优劣情况作为评价复原模型好坏的标准，通过人工后期的处理得到最正确结果。
面对题目中给出的BMP格式的黑白文字图片，我们使用matlab软件的图像处理功能把图像转化为矩阵形式，矩阵中的元素表示图中该位置像素的灰度值，再对元素进展二值化处理得到新的矩阵。
题目每一个附件中的碎纸片均为来自同一页的文件，所以不需考虑残片中含有未知纸张的残片以及残片中不会含有公共局部。
鉴于残片形状分为“长条形〞与“小长方形〞，残片内容分为中文、英文，纸张的打印类型分为“单面型〞、“双面型〞，所以我们根据残片的类型对矩阵做不同处理。
针对问题一中给出的“长条形〞碎纸片：
对图片转化后的矩阵进展边缘检测，发现每一张图片的两短边在一定范围内全是白色，而仅有2张图片的长边在一定范围内全是白色，说明我们需要对长边进展拼接，一边包含全白的长边是原文件纸张的两端。
由于考虑到模型应用的推广，我们在此问中的模型包含了图片倒置的情况〔仅在问题一中考虑倒置情况，鉴于问题二、三中数据量的增多，二三问不再考虑倒置情况〕，对图片的长边及矩阵中的第一列和最后一列与其他矩阵的第一列和最后一列进展边缘匹配，根据边缘匹配度来确定图片复原，最后假设发现拼接效果有偏向，在进展人工操作。
针对问题二中的“小长方形〞碎纸片：
由于数据量变多，盲目使用问题一中的方法不能保证准确度，所以这里要进一步约束使当前图片与少量图片进展匹配。
观察两种文字的特点，我们可以发现中英文在位置上均有一定的特性，我们利用这种特性将有一样位置特性的碎纸片归类为一组，在问题一方法的根底上做少许修改后代入有一样位置特性的一组碎纸片中，根据边缘匹配度将他们连接、检查并做人工处理可得拼接后的横行纸片，再将横行纸片的长边用同样的方法做边缘匹配可将行与行之间拼接起来，再做人工调整得到最优结果。
通过模型的建立求解过程可以发现中英文在本问题的求解方法中有着一定的不同，英文需要更多地人工判断处理。
针对问题三考虑到双面问题以及问题二中英文碎纸片的情况，我们把碎纸片两面匹配度之和作为判断碎纸片是否连接的评价标准，在问题一方法的根底上，在计算机每一步的匹配结果加以人工选择与判断，这样再次处理得到的结果，可以得到同问题二中一样的横行碎纸片，在根据新的横行碎纸片的两面边缘匹配度之和进展同样的操作处理可以将原纸张拼接复原。
关键词：
残片复原matlab图像处理二值化边缘匹配度倒置情况位置特性人工处理
一问题重述
B题碎纸片的拼接复原
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。
传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。
特别是当碎片数量宏大，人工拼接很难在短时间内完成任务。
随着计算机技术的开展，人们试图开发碎纸片的自动拼接技术，以进步拼接复原效率。
请讨论以下问题：
1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片〔仅纵切〕，建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进展拼接复原。
假如复原过程需要人工干预，请写出干预方式及干预的时间节点。
复原结果以图片形式及表格形式表达〔见【结果表达格式说明】〕。
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×19的表格；
（3）附件5的结果：
将碎片序号按复原后顺序填入两个11×19的表格；
（4）不能确定复原位置的碎片，可不填入上述表格，单独列表。
二、模型假设
①假设题目中的碎纸图片与真实文件纸张大小、颜色、边缘情况一样。
②假设题目中的碎纸照片边缘完好，不存在破损。
③假设所有碎纸片的扫描情况一样。
④假设人工干预后可以得到正确结果。
⑤假设原文件纸张的内容具有意义。
三、符号说明
符号
符号意义
编号为
的图片的灰度矩阵
编号为
的图片经二值化处理后的矩阵
编号为
的图片的二维边缘矩阵
、
、
、
边缘匹配度矩阵
编号为i的图片在此处理后的二值化矩阵
边缘匹配度之和矩阵
*其他未提及的符号会在文章中说明。
四、问题分析
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，当图片未出现倒置情况时，即题目中的图片均是正常摆放，将左边矩阵的第二列元素与右边矩阵的第一列元素进展两两匹配。
记录元素一样的个数，个数除以1980为左边矩阵第二列对右边矩阵第一列的边缘匹配度，记为：
将所有碎纸片的二值化矩阵做如上匹配可依次选取与其匹配的碎纸片。
图1中左边矩阵第一列与右边矩阵第二列匹配的原那么与上述一样，不再重述。
如图2，当图片出现倒置情况时，正常情况下应是左边矩阵的第二列元素与右边矩阵的第一列元素进展两两匹配，假设倒置后，那么应该是左边矩阵的第二列元素与右边矩阵的第二列元素倒置顺序进展比拟，同样记录一样元素的个数并计算匹配度。
图2中左边矩阵第一列元素与右边矩阵第一列元素的匹配原那么与上述一样，不再重述。
综合图一图二我们可以做出4个边缘匹配度的矩阵，即未倒置时矩阵第一列与其他矩阵第二列的边缘匹配度、未倒置时矩阵第二列与其他矩阵第一列的边缘匹配度、倒置时矩阵第一列与其他矩阵第一列的边缘匹配度、倒置时矩阵第二列与其他矩阵第二列的边缘匹配度。
由于〔未〕倒置时矩阵第一列与其他矩阵第二列匹配在思想上同〔未〕倒置时矩阵第二列与其他矩阵第一列匹配一样，所以这里只需考虑其中一种情况即可。
任选其中一例说明，由于碎纸片倒置情况未知，需要考虑未倒置时的情况与倒置式的情况，未倒置时矩阵第一列与其他矩阵第二列的边缘匹配度矩阵第一行最大值与倒置时矩阵第一列与其他矩阵第一列的边缘匹配度第一行的最大值进展比拟，选取匹配度大的作为拼接的纸片，即编号为000的碎纸片要与该纸片拼接。
以此类推把19张碎纸片拼接完成后做人工处理。
i，矩阵均为
的矩阵，这里我们分别将每张图片的Bi矩阵第1列和第72列提取出来做一新的二维边缘矩阵Ci，它是
的矩阵。
通过对所有图片矩阵的分析可以发现C3、C4矩阵中均有一列为0，所以可以认为编号为003和004的图片为原完好文件的一端，在做题过程中
无需考虑会存在其他白边与白边拼接的情况。
做如上判断后解题过程同4.11。
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，之后再人工干预，得到较优的结果。
得到很多组有一样位置的的碎纸片后，在每一组内采用4.1的中的边缘匹配方法，这里为了防止出现两白边匹配造成碎纸片连接混乱的现象，要加以限制。
方法为：
假设在组内做边缘匹配出现匹配度为1的情况，那么暂时不连接此碎纸片，从剩余的碎纸片出发做边缘匹配与其他碎纸片连接，直到组内所有碎纸片均已覆盖。
这样再通过一定的人工干预可以得到拼接复原后的的11横行碎纸片，在同样使用4.1的边缘匹配方法，[7]将得到的11行的碎纸条的长边进展边缘匹配做出
的匹配度矩阵后找最大匹配度作为连接的碎纸条，同样为了防止出现两白边匹配造成碎纸片连接混乱的现象，要加以限制。
方法为：
假设在组内做边缘匹配出现匹配度为1的情况，那么暂时不连接此碎纸片，从剩余的碎纸片出发做边缘匹配与其他碎纸片连接，直到11张拼接后的碎纸片均已覆盖。
最后加以人工处理，得到完好的原文件。
同4.2.1中的分析一样，通过观察我们可以发现碎纸片的英文在位置上也有一定的规那么可循。
如下列图图5。
可以发现英文字母的主要的局部拥有同一上界和同一下界，但是跟中文不同，英文中会出现一些“y〞、“b〞之类的字母，为了同样使用4.2.1中的方法我们通过观察附件4中图片的像素情况，将图片中每一行中黑色像素数少于13的及字母的次要局部转变为二值化矩阵中的0，将每一行中黑色像素大于等于13的及字母的主要局部转化为二值化矩阵中的1，这样得到的新的二值化矩阵
，可认为图像转变为图6的方式，同样使用4.2.1中的分析方法将新的二值化矩阵做边缘匹配，匹配度高的可以认为两碎纸片在原纸张中位于同一行，把匹配度高于0.9的元素分为一组后，对每一组进展边缘匹配。
由于考虑到英文字符的情况，在4.1的根底上，我们对于组内图片原始二值化矩阵的边缘匹配度矩阵
每一行的搜索，在这里我们假设矩阵的任意一行中出现匹配度大于0.9的元素个数超过2个，我们加以人工干预，根据文章的格式、内容选择应该连接的碎纸片，其他过程与4.1一样，区别仅为本文中需要对软件执行过程进展人工干预，其他一样的步骤不在重述。
本问在问题二英文碎纸片的根底上还需要考虑纸片是否处于同一面，虽然数据量增加了一倍，但是判断碎纸片是否连接的标准由一面增加到了两面。
本不对应的两张碎纸片一面的拼接复原情况好而令一面复原情况也好的情况只是个别的案例，所以可以将碎纸片两面边缘匹配度之和作为评判两张是否匹配的标准建立边缘匹配度之和矩阵
，在这里可以先认为匹配度之和高于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。
假设i经过19次后返回0，那么可以认为所有的碎纸片已拼接在一起，仅需把两个空白端分开后再做人工调整，那么可得到结果；假设i少于19次变化后变为0，那么认为局部碎纸片未拼在一起，要把剩余的纸片拼接在一起后做人工调整。
根据所得两个矩阵
、
的情况，发现任意一行的
大于
，可以一定程度说明碎纸片中不存在倒置的情况，仅按上述
大于等于
的情况做分析即可。
该方法可以用图7的matlab软件编程流程图来表示。
可以看出由于问题一中的数据量较小，为了方便我们仅对计算机的编程结果进展人工干预，而不对过程做人工干预。
得到的结果见表1：
000
006
008
014
012
015
003
010
002
016
001
004
005
009
013
018
011
007
001
根据表种情况可已发现碎纸片006和碎纸片008连接在一起，发生这种情况的原因是两白边边缘匹配度为1.0，所以他们匹配在了一起，根据实际情况，可以断定碎纸片008为正常放置情况下原纸张的左端，所以重新指定表格，以碎纸片008作为纸片的开端，表格见表2，在使用matlab中的imshow〔〕函数，得到人机结合后的复原图片。
008
014
012
015
003
010
002
016
001
004
005
009
013
018
011
007
001
000
006
5.1.2英文碎纸片的拼接复原
根据4.1.1与4.1.2的分析，模型建立求解同5.1.1。
使用计算求解的结果见表3。
000
005
001
009
013
010
008
012
014
017
016
004
003
006
002
007
015
018
011
根据表种情况可已发现碎纸片003和碎纸片004连接在一起，发生这种情况的原因是两白边边缘匹配度为1.0，所以他们匹配在了一起，根据实际情况，可以断定碎纸片003为正常放置情况下原纸张的左端，所以重新指定表格，以碎纸片003作为纸片的开端，表格见表3，在使用matlab中的imshow〔〕函数，人机结合后的复原图片见图片5。
003
006
002
007
015
018
011
000
005
001
009
013
010
008
012
014
017
016
004
5.2问题二模型的建立与求解
5.2．1中文碎纸片复原的模型建立与求解
搜索每一张碎纸片转化后二值化矩阵
的每一行，假设存在黑色即矩阵该行中存在数值1，那么将该行全部赋值为1，假设这一行不存在黑即此行元素全为0，那么将该行全部赋值为0，这样将209张碎纸片做出新的二值化矩阵
，之后同5.1的求解过程做边缘匹配，做出矩阵大小为
边缘匹配度矩阵
〔由于矩阵太大，在论文中不作出〕，元素
为处理后的碎纸片边缘二值化矩阵i的第二列与处理后的碎纸片边缘二值化矩阵j第一列的边缘匹配度，匹配度高那么说明碎纸片的文字信息处于同一程度位置。
在矩阵
中每一行选取匹配度大于0.9的元素，进展统计分组，可得结果如下表表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
14
17
71
18
89
19
102
20
125
可以看出在取匹配度为0.9及以上时，分出了20个组，其中组内元素最多的为19，组内元素最少的为1。
而最后的结果应该为11行，我们需要对这些组中的元素进展合并后得到11行，所以我们要先考虑元素数量为19的组，再考虑其他元素数多的组，对组内图片进展5.1中的边缘匹配，匹配后的结果在与元素数少的组做匹配与人工处理。
以序号2的组为例，该组包含19个元素，对于组内的19个元
升级会员 