2023年12月7日发(作者：茅台学院期末数学试卷)
2013高教社杯全国大学生数学建模竞赛
承 诺 书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B
我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）： 重庆邮电大学
参赛队员 (打印并签名) ：1.
2.
3.
指导教师或指导教师组负责人 (打印并签名)：
日期： 2013 年 9 月 13 日
赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛
编 号 专 用 页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
评
阅
人
评
分
备
注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原
摘要
本文研究的是碎纸片的拼接复原问题。由于人工做残片复原虽然准确度高，但有着效率低的缺点，仅由计算机处理复原，会由于各类条件的限制造成误差与错误，所以为了解决题目中给定的碎纸片复原问题，我们采用人机结合的方法建立碎纸片的计算机复原模型解决残片复原问题， 并把计算机通过算法复原的结果优劣情况作为评价复原模型好坏的标准，通过人工后期的处理得到最佳结果。
面对题目中给出的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) 不能确定复原位置的碎片，可不填入上述表格，单独列表。 二、模型假设
①假设题目中的碎纸图片与真实文件纸张大小、颜色、边缘情况相同。
②假设题目中的碎纸照片边缘完整，不存在破损。
③假设所有碎纸片的扫描情况相同。
④假设人工干预后可以得到正确结果。
⑤假设原文件纸张的内容具有意义。
三、符号说明
符号
D、D\'、D\'\'、D\'\'\'
符号意义
编号为i的图片的灰度矩阵
编号为i的图片经二值化处理后的矩阵
编号为i的图片的二维边缘矩阵
边缘匹配度矩阵
编号为i的图片在此处理后的二值化矩阵
边缘匹配度之和矩阵
*其他未提及的符号会在文章中说明。
四、问题分析
4.1问题一的分析
4.1．1 中文碎纸片的复原分析
问题1、2、3附件1、2、3、4、5中的碎纸片均为一份纸张撕裂所得，所以碎纸片附件1中所给的图片为[5]扫描原纸张碎片后得到的BMP格式的图片，图片像素均为中不会存在含有相同信息的公共部分，这里进行强调，下面不再重述。
198072，使用[1]matlab中的iamread函数可以做出图片的灰度矩阵Ai，举例如下（由于该像素图片转换后为198072的矩阵，论文中无法放置，所以仅简单举例说明，论文中若还出现庞大的矩阵，同本说明）：
矩阵的中元素表示该位置图片的灰度，255表示为白，0为黑，图片中信息为黑白文字信息，但由于文字信息会存在阴影，所以矩阵中出现了介于0-255的元素。为了方便应用，并查阅相关资料所得，可以对于本题中的黑白图片做[2]二值化处理，可将上面例子中的Ai转化为如下的矩阵：
其中白色用0值表示，非白色用1表示。
将附件1中的19张图片做如上处理得到各自的二值化后的矩阵Bi，矩阵均为198072的矩阵，这里我们分别将每张图片的Bi矩阵第1列和第72列提取出来做一新的二维边缘矩阵Ci，它是19802的矩阵。通过对所有图片矩阵的分析可以发现C6、C8矩阵中均有一列为0，所以可以认为编号为006和008的图片为原完整文件的一端，在做题过程中无需考虑会存在其他白边与白边拼接的情况。
两张图片匹配的原则可以根据下面的图1、图2来表示。
如图1，当图片未出现倒置情况时，即题目中的图片均是正常摆放，将左边矩阵的第二列元素与右边矩阵的第一列元素进行两两匹配。记录元素相同的个数，个数除以1980为左边矩阵第二列对右边矩阵第一列的边缘匹配度，记为：
将所有碎纸片的二值化矩阵做如上匹配可依次选取与其匹配的碎纸片。
图1中左边矩阵第一列与右边矩阵第二列匹配的原则与上述相同，不再重述。
如图2，当图片出现倒置情况时，正常情况下应是左边矩阵的第二列元素与右边矩 图1.图片未倒置 图2.图片倒置
阵的第一列元素进行两两匹配，若倒置后，则应该是左边矩阵的第二列元素与右边矩阵的第二列元素倒置顺序进行比较，同样记录相同元素的个数并计算匹配度。
图2中左边矩阵第一列元素与右边矩阵第一列元素的匹配原则与上述相同，不再重综合图一图二我们可以做出4个边缘匹配度的矩阵，即未倒置时矩阵第一列与其他述。
矩阵第二列的边缘匹配度、未倒置时矩阵第二列与其他矩阵第一列的边缘匹配度、倒置时矩阵第一列与其他矩阵第一列的边缘匹配度、倒置时矩阵第二列与其他矩阵第二列的边缘匹配度。由于（未）倒置时矩阵第一列与其他矩阵第二列匹配在思想上同（未）倒置时矩阵第二列与其他矩阵第一列匹配相同，所以这里只需考虑其中一种情况即可。
任选其中一例说明，由于碎纸片倒置情况未知，需要考虑未倒置时的情况与倒置式的情况，未倒置时矩阵第一列与其他矩阵第二列的边缘匹配度矩阵第一行最大值与倒置时矩阵第一列与其他矩阵第一列的边缘匹配度第一行的最大值进行比较，选取匹配度大的作为拼接的纸片，即编号为000的碎纸片要与该纸片拼接。以此类推把19张碎纸片拼接完成后做人工处理。
将附件2的19张图片做4.11中处理得到二值化后的矩阵Bi，矩阵均为198072的矩阵，这里我们分别将每张图片的Bi矩阵第1列和第72列提取出来做一新的二维边缘矩阵Ci，它是19802的矩阵。通过对所有图片矩阵的分析可以发现C3 、C4矩阵中均有一列为0，所以可以认为编号为003和004的图片为原完整文件的一端，在做题过程中
无需考虑会存在其他白边与白边拼接的情况。
做如上判断后解题过程同4.11。
4.2问题二的分析
4.2．1中文碎纸片的分析
此问中同4.1的图片处理方法，也需要将209张碎纸片进行同样的图像处理转化为灰度矩阵后进行二值化处理得到处理后的矩阵。根据结果知此问中的图片转化后的矩阵为72180的矩阵，列数由第一问中的1980变为180，虽然数量变少，但是图片数量由19张变为了209张。若同样使用4.1中的边缘匹配的方法，一张碎纸片对应其他208张碎纸片的边缘匹配相同的像素点有208种情况，变化范围为0-180，可知若直接采用4.1中的方法得到的结果可能出现多个相同或无法判断的情况，所以这里我们先考虑附件3中碎纸片的特性。
观察下面的图3可以发现，通过查阅资料分析[2]基于文字特征的文档碎纸片半自动拼接，每一行的绝大多数中文文字均可认为拥有同一上界、同一下界（图3最右端出现了“一”字，但是同行还存在其他文字，可以认为同一行文字有同一上界与同一下界），我们可以根据这一特性使用软件将[3]匹配度高及位置相同的碎纸片归类为一组。方法为：搜索每一张碎纸片转化后二值化矩阵Ci的每一行，若矩阵该行中存在数值1，则将该行全部赋值为1，若这一行元素全为0，则将该行全部赋值为0，其中1表示本行存在灰度小于255的像素，0表示不存在灰度小于255的像素，这样将209张碎纸片做出[4]新的二值化矩阵Ei，之后同4.1的分析取边缘做边缘匹配得修改后的[6]边缘匹配度矩阵D，匹配度高则说明碎纸片的文字信息处于同一水平位置，见下图图4，之后再人工干预，得到较优的结果。
图3.处理的图片
图4.再次处理后的图片
得到很多组有相同位置的的碎纸片后，在每一组内采用4.1的中的边缘匹配方法，这里为了防止出现两白边匹配造成碎纸片连接混乱的现象，要加以限制。方法为：若在组内做边缘匹配出现匹配度为1的情况，则暂时不连接此碎纸片，从剩余的碎纸片出发做边缘匹配与其他碎纸片连接，直到组内所有碎纸片均已覆盖。
这样再通过一定的人工干预可以得到拼接复原后的的11横行碎纸片，在同样使用4.1的边缘匹配方法，[7]将得到的11行的碎纸条的长边进行边缘匹配做出1111的匹配度矩阵后找最大匹配度作为连接的碎纸条，同样为了防止出现两白边匹配造成碎纸片连接混乱的现象，要加以限制。方法为：若在组内做边缘匹配出现匹配度为1的情况，则暂时不连接此碎纸片，从剩余的碎纸片出发做边缘匹配与其他碎纸片连接，直到11张拼接后的碎纸片均已覆盖。最后加以人工处理，得到完整的原文件。
图5.演示的图片
可以发现英文字母的主要的部分拥有同一上界和同一下界，但是跟中文不同，英文中会出现一些“y”、“b”Ei
由于考虑到英文字符的情况，在4.1的基础上，我们对于组内图片原始二值化矩阵的边缘匹配度矩阵D每一行的搜索，在这里我们若矩阵的任意一行中出现匹配度大于0.9的元素个数超过2个，我们加以人工干预，根据文章的格式、内容选择应该连接的碎纸片，其他过程与4.1相同，区别仅为本文中需要对软件执行过程进行人工干预，其他相同的步骤不在重述。
图6.演示图片
4.3问题三的分析
本问在问题二英文碎纸片的基础上还需要考虑纸片是否处于同一面，虽然数据量增加了一倍，但是判断碎纸片是否连接的标准由一面增加到了两面。本不对应的两张碎纸片一面的拼接复原情况好而令一面复原情况也好的情况只是个别的案例，所以可以将碎纸片两面边缘匹配度之和作为评判两张是否匹配的标准建立边缘匹配度之和矩阵F
以纸片000与001为例，匹配方式可能为：
为了找出碎纸片如何对应，则将①②的边缘匹配度相加得到边缘匹配度之和，将③④的边缘匹配度相加得边缘缘匹配度之和，两者的和做出比较。若仅有一个大于等于1.9，则计算机输出该匹配度，人工判断是否碎纸片是否匹配；若两者均大于等于1.9，计算机把两个匹配度之和输出，人工选择判断碎纸片应是否匹配与如何匹配；若两者均小于1.9，则计算输出最大者，人工判断碎纸片是否匹配。
若出现计算机给出的结果人工判断后发现匹配错误，则记录当前匹配成功的碎纸片上述的结果可以得到一些在同一横行的碎纸片的拼接，再次根据这些新的碎纸片的信息并在剩下的碎纸片中重新开始计算机匹配与人工判断。
边缘匹配度之和的情况通过上述人机结合的方法拼出11张横行的碎纸片，剩下的就是应该如何把11张横行的碎纸片拼接成完整的一份纸张，这里将11张横行碎纸片的上下长边进行两两匹配，以两面边缘匹配度之和的方法按照上述的方法将11横行的碎纸片拼接完毕。
五、模型的建立与求解
5.1问题一的模型建立与求解
5.1.1 中文碎纸片的拼接复原
’’’’’’’’’1919的矩阵D、矩阵D、矩阵D、矩阵D（这里仅做出D与D，其他两个矩阵仅在下面的说明中会提及，但不会使用），元素Dij为碎纸片图像未倒置时矩阵i的第二列与矩阵j第一列的边缘匹配度，元素Dij’为碎纸片图像倒置时矩阵i的第二列与矩阵j的第二列的边缘匹配度，元素Dij’为碎纸片图像倒置时矩阵i的第一列与矩阵j第一列的边缘匹配度，元素Dij’’为碎纸片图像未倒置时矩阵i的第一列与矩阵j第二列的边缘匹配度。
对于得到的两个矩阵D、D\'，从i=0即第0行（为方便说明）开始，找到这一行\'maxD0中最大的匹配度maxD0、，两者进行大小比较： 1） 若maxD0大于等于maxD0\'，把maxD0所处列数赋值为新的i，找到这一行中的最maxDi\'，两者进行大小比较，重复上述过程直到i重新变为0。若大匹配度maxDi、i经过19次后返回0，则可以认为所有的碎纸片已拼接在一起，仅需把两个空白端分开后再做人工调整，则可得到结果；若i少于19次变化后变为0，则认为部分碎纸片未拼在一起，要把剩余的纸片拼接在一起后做人工调整。
2） 若maxD0小于maxD0\'，把maxD0\'所处的列数赋值为新的i，找到矩阵D\'\'、Dij\'\'\'这maxDi\'\'\'，两者进行大小比较，其他过程与上述分析类一行中的最大匹配度maxD\'\'i、似，不再进行说明，重复上述过程直到i重新变为0。若i经过19次后返回0，则可以认为所有的碎纸片已拼接在一起，仅需把两个空白端分开后再做人工调整，则可得到结果；若i少于19次变化后变为0，则认为部分碎纸片未拼在一起，要把剩余的纸片拼接在一起后做人工调整。
根据所得两个矩阵D、D\'的情况，发现任意一行的maxD0大于maxD0\'，可以一定程度说明碎纸片中不存在倒置的情况，仅按上述maxD0大于等于maxD0\'的情况做分析即可。
该方法可以用图7的matlab软件编程流程图来表示。可以看出由于问题一中的数据量较小，为了方便我们仅对计算机的编程结果进行人工干预，而不对过程做人工干预。 i=0
否
maxDi>=maxDi’?
是
maxDi’’>=maxDi’’’?
记录i并重新赋值i
记录i并重新赋值i
否
i=0是
本次搜索结束，记录i并记录搜索次数n并重新赋值i开始新的搜索
……
……
i经过19次变化（若重新进行了搜索，此处为19-n是
结束并输出结果
人工处理
图7.流程图
得到的结果见表1：
表1.计算机拼图位置表格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（）函数，得到人机结合后的复原图片。
表2.修改后的拼图位置表格2 008 014 012 015 003 010 002 016 001 004 005 009 013 018 011 007 001 000 006
5.1.2 英文碎纸片的拼接复原
表3.计算机拼图位置表格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。
表4.修改后的拼图位置表格4
003 006 002 007 015 018 011 000 005 001 009 013 010 008 012 014 017 016 004
5.2 问题二模型的建立与求解
5.2．1 中文碎纸片复原的模型建立与求解
搜索每一张碎纸片转化后二值化矩阵Ci的每一行，若存在黑色即矩阵该行中存在数值1，则将该行全部赋值为1，若这一行不存在黑即此行元素全为0，则将该行全部赋值为0，这样将209张碎纸片做出新的二值化矩阵Ei，之后同5.1的求解过程做边缘匹配，做出矩阵大小为209209边缘匹配度矩阵D（由于矩阵太大，在论文中不作出），元素Dij为处理后的碎纸片边缘二值化矩阵i的第二列与处理后的碎纸片边缘二值化矩阵j第一列的边缘匹配度，匹配度高则说明碎纸片的文字信息处于同一水平位置。在矩阵D中每一行选取匹配度大于0.9的元素，进行统计分组，可得结果如下表表5.
表5.分组情况
序碎纸片编号
号
1 0 7 45 53 68 126 137 138 158 174 175 208
2 1 18 23 26 30 41 50 62 76 86 87 100
120 142 147 168 179 191 195
3 2 11 22 28 49 54 57 65 91 95 118 129 141
143 178 186 188 190 192
4 3 12 31 39 51 73 82 107 115 128 134 135
159 160 169 176 199 203
5 4 40 101 108 113 114 117 119 123 140 146 151
154 155 185 194 207
6 5 10 29 37 44 48 55 59 64 75 92 98
104 111 171 172 180 201 206
7 6 19 20 36 52 61 63 67 69 72 78 79 96
99 116 131 162 163 177 8
9
10
11
12
13
14
15
16
17
18
19
20
8 9 25 74 105
182 13
15??? 17 ?33????80????83???132???133???156???198???200???202
16 21 66 106 109 110 139 145 150 157 173 181
184 187 197 204
24 35 38 46 81 88 103 122 130 148 161 167
189 193
27 60 85 152 165 170 205
32 56 70 93 153 166 196
34 42 43 47 58 77 84 90 94 97 112 121
124 127 136 144 149 164 183
14
71
89
102
125
可以看出在取匹配度为0.9及以上时，分出了20个组，其中组内元素最多的为19，组内元素最少的为1。而最后的结果应该为11行，我们需要对这些组中的元素进行合并后得到11行，所以我们要先考虑元素数量为19的组，再考虑其他元素数多的组，对组内图片进行5.1中的边缘匹配，匹配后的结果在与元素数少的组做匹配与人工处理。
以序号2的组为例，该组包含19个元素，对于组内的19个元素的原始二值化矩阵进行上述中的边缘匹配，通过结果观察本题模型第一步确定模型的的可行性，其他的组的处理情况相同，不再重述。结果如下，见表6。
序号
2
表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。
序号
2 168-100-076-062-142-030-041-023-147-191-050-179-120-086-195-026-001-087-018
图10
通过结果可以发现拼接程度较好，所以也验证了本问题中碎纸片拼接复原模型的可行性。
其他组做相同处理，这样可得到拼接好的11横行的碎纸条，对11横行的碎纸条的长边进行边缘匹配，建立新的边缘匹配矩阵，方法同上，做出结果如下，见表9。
表9
一
014 128 003 159 082 199 135 012 073 160 203 169 134 039 031 051 107 115 176
094 034 084 183 090 047 121 042 124 144 077 112 149 097 136 164 127 058 043
二
125 013 182 109 197 016 184 110 187 066 106 150 021 173 157 181 204 139 145
029 064 111 201 005 092 180 048 037 075 055 044 206 010 104 098 172 171 059
007 208 138 158 126 068 175 045 174 000 137 053 056 093 153 070 166 032 196
三
049 054 065 143 186 002 057 192 178 118 190 095 011 022 129 028 091 188 141
061 019 078 067 069 099 162 096 131 079 063 116 163 072 006 177 020 052 036
四
168 100 076 062 142 030 041 023 147 191 050 179 120 086 195 026 001 087 018
038 148 046 161 024 035 081 189 122 103 130 193 088 167 025 008 009 105 074
五
089 146 102 154 114 040 151 207 155 140 185 108 117 004 101 113 194 119 123
六
071 156 083 132 200 017 080 033 202 198 015 133 170 205 085 152 165 027 060
表7. 人工干预
分组
以上做出的表格把一些横行碎纸片拼接在一起，未能拼接的原因是由于拼接后的横行碎纸片两端都存在白边，计算机无法做出顺序的判断，所以我们要根据文字内容、规格、形式等因素人工将它们结合起来，人机结合后的原文件以下面的表格10。
表10.附件3的复原
049 054 065 143 186 002 057 192 178 118 190 095 011 022 129 028 091 188 141
061 019 078 067 069 099 162 096 131 079 063 116 163 072 006 177 020 052 036
168 100 076 062 142 030 041 023 147 191 050 179 120 086 195 026 001 087 018
038 148 046 161 024 035 081 189 122 103 130 193 088 167 025 008 009 105 074
071 156 083 132 200 017 080 033 202 198 015 133 170 205 085 152 165 027 060
014 128 003 159 082 199 135 012 073 160 203 169 134 039 031 051 107 115 176
094 034 084 183 090 047 121 042 124 144 077 112 149 097 136 164 127 058 043 125 013 182 109 197 016 184 110 187 066 106 150 021 173 157 181 204 139 145
029 064 111 201 005 092 180 048 037 075 055 044 206 010 104 098 172 171 059
007 208 138 158 126 068 175 045 174 000 137 053 056 093 153 070 166 032 196
089 146 102 154 114 040 151 207 155 140 185 108 117 004 101 113 194 119 123
观察发现拼接复原后结果较好。
5.2．2英文碎纸片复原的模型建立与求解
搜索每一张碎纸片转化后二值化矩阵Ci的每一行，若存在黑色像素数量大于等于13即矩阵该行中数值1的数量大于等于13，则将该行全部赋值为1，若这一行黑色像素数量小于13，则将该行全部赋值为0，这样将209张碎纸片做出新的二值化矩阵Ei，之后同5.1的求解过程做边缘匹配，做出矩阵大小为209209边缘匹配度矩阵D（由于矩阵太大，在论文中不作出），元素Dij为处理后的碎纸片边缘二值化矩阵i的第二列与处理后的碎纸片边缘二值化矩阵j第一列的边缘匹配度，匹配度高则说明碎纸片的文字信息处于同一水平位置。同样在矩阵D中每一行选取匹配度大于0.9的元素，进行统计分组。
图11 开
始
对二值化矩阵Ei做边缘匹配
选取每一个元素对应匹配度大于0.9的元素存于一组中，即将对应的图片归为一组
对于每一组内图片做5.1中的边缘匹配
当前碎纸片对应其他碎纸片的匹配度为0.9以上的碎纸片张数大于等于2张
是
人工干预选择碎纸片并判断
重复判断过程多次直到结束
人工干预处理结果
图12.流程图
否
计算机给出最大的结果后人工判通过上述步骤可一把相同行的纸片先拼接好，得到新的11张横行碎纸片，这里拼接11张碎纸片的方法同5.2.1，不再重述，得到的结果见下表11。
表11.附件4的复原
191
201
75
148
11
170
154
196
190
198
184
94
2
113
104
164
180
78
64
103
106
91
4
80
149
101
32
26
204
100
65
6
39
17
67
28
147
146 86
19
159
51
194
139
107
93
1
29
141
129
40
88
63
158
121
138
186
126
153
98
105
53
24
155
38
117
114
123
150
176
120
5
182
175
59
151
85
58
22
50
92
57
160
30
202
187
37
71
97
46
165
203
127
82
31
20 41 108 116 136 73
7
60
49
14
36 207 135 15 76 43 199 45 173 79 161 179 143
208 21
70 84
61 119 33 142 168 62 169 54 192 133 118 189 162 197 112
68 174 137 195 8 47 172 156 96
3
18
48
23 99 122 90 185 109
13 110 25
16 9
27 178 132 181 95
171 42
81
69 167 163 166 188 111 144 206 130 34
56
72
35 66 205 10 157 74 145 83 134 55
89
183 152 44
0 102 115 77 128 200 131 52 125 140 193 87 12 177 124
5.3问题三模型的建立与求解
本问我们可以先将所有的图片用matlab的图像处理得到灰度矩阵后二值化处理得到每一个图像的二值化矩阵，通过对图片的观察与对矩阵的判断，编号为i的碎纸片a面右端（或左端）与b面左端（或右端）边缘全是白色的图片一共有22张，考虑到所有的碎纸片应被拼接为11行，而左右个两端，乘以2就是22，所以136、005、143、083、090、013、035、172、105、009、054、078、089、186、199、088、114、146、165、003、023、099这22张碎纸片应是原文件纸张的两端。为了方便可以将可以选择这22张碎纸片作为开端匹配对应的纸片。
以纸片000与001为例，匹配方式可能为：
为了找出碎纸片如何对应，则将①②的边缘匹配度相加得到边缘匹配度之和，将③④的边缘匹配度相加得边缘缘匹配度之和，两者的和做出比较。若仅有一个大于等于1.9，则计算机输出该匹配度，人工判断是否碎纸片是否匹配；若两者均大于等于1.9，计算机把两个匹配度之和输出，人工选择判断碎纸片应是否匹配与如何匹配；若两者均小于1.9，则计算输出最大者，人工判断碎纸片是否匹配。综上先建立边缘匹配度之和矩阵F，然后按照上面的匹配原则开始匹配。
若出现计算机给出的结果人工判断后发现匹配错误，则记录当前匹配成功的碎纸片该过程可以用下面的流程图图13来表示。
信息并在剩下的碎纸片中重新开始计算机匹配与人工判断。 开始
数据初始化
（边缘匹配度矩阵）
找出当前节点所有较优最佳匹配个数为三个或是
人工干预节点选择最佳算法自动选择最佳匹配
最佳匹配个数在两个或以下
是否还有待添加节点
否
输出结果，进行最后调
图13.流程图
根据上面的流程图17，以009碎纸片为例（它是22个边缘碎纸片之一）作为起始的图片，进行拼接，拼接结果如下：
附件5的还原后的表格见下表12、表13。
表12
78b
89a
186b
199b
88b
114a
146a
165b
111b
10b
153a
11b
107a
184b
171b
195a
125a
36a
84b
161a
149b
179b
31a
128a
140a
76b
42b
169b
180a
116b
201a
157a
155a
178a
30a
194b
37b
207a
50a
168a
150a
44a
38a
173b
191a
58a
190b
46a
183b
25b
121a
206b
65b
158a
92b
67a
174b
192a
98a
156a
115b
197a
19b
63b
110a
124b
94b
34a
166b
154b
16b
75b
66a
22a
61b
181b
1b
28b
177b
167a
108a
120b
137b
198b
151b
12a
53b
117b
18b
144a
45a
87a
170b
17b
202a
8b
29a
79a
138a
132b
41a
102b
21b
68b
189b
14a
56b
93a
70b
64b
130a
188a
81b
59a
131b
72b
139b
208a
163a
127a
164b
60b
187b
175a
2a
142a
193b
40a
20a
147a
86b
97a
162b
57a
73b
182b
47a
152a
200b
39b
203b
24a
159a
122a
136b
5a
143b
83a
90a
13a
35a
172a 3b
23b
99a
7b
133a
43a
85b
48a
96b
148b
51b
109a
77a
95a
123a
4a
160b
6a
69a
119a
104a
32a
33b
134a
74b
71b
113a
126b
52a
26b
176a
62a
49b
185a
129b
91a
0b
118b
106b
80b
101a
100b
27a
15b
55b
135b
205a
103a
141a
82b
112a
204b
145a
196b
105a
9b
54b
表13
136a
5b
143a
83b
90b
13b
35b
172b
105b
9a
54a
47b
152b
200a
39a
203a
24b
159b
122b
204a
145b
196a
20b
147b
86a
97b
162a
57b
73a
182a
141b
82a
112b
164a
60a
187a
175b
2b
142b
193a
40b
135a
205b
103b
81a
59b
131a
72a
139a
208b
163b
127b
27b
15a
55a
189a
14b
56a
93b
70a
64a
130b
188b
80a
101b
100a
29b
79b
138b
132a
41b
102a
21a
68a
0a
118a
106a
18a
144b
45b
87b
170a
17a
202b
8a
185b
129a
91b
108b
120a
137a
198a
151a
12b
53a
117a
176b
62b
49a
66b
22b
61a
181a
1a
28a
177a
167b
126a
52b
26a
110b
124a
94a
34b
166a
154a
16a
75a
74a
71a
113b
174a
192b
98b
156b
115a
197b
19a
63a
32b
33a
134b
183a
25a
121b
206a
65a
158b
92a
67b
69b
119b
104b
150b
44b
38b
173a
191b
58b
190a
46b
4b
160a
6b
155b
178b
30b
194a
37a
207b
50b
168b
77b
95b
123b
140b
76a
42a
169a
180b
116a
201b
157b
148a
51a
109b
125b
36b
84a
161b
149a
179a
31b
128b
85a
48b
96a
111a
10a
153b
11a
107b
184a
171a
195b
7a
133b
43b
78a
89b
186a
199a
88a
114b
146b
165a
3a
23a
99b
六、模型评价与推广
6.1模型的优点
通过对复原后图片的验证结果可以认为本论文中的碎纸片复原拼接模型对于本题有很高的可行性。对于中、英文两种情况，论文中按照从问题一到问题三、中文到英文的顺序依次改进模型。发现了中文需要人工干预较少，英文需要人工干预较多的规律，说明不同语言有各自的特性。
对于计算机错误匹配的结果，论文中在问题二与问题三种给出了详细的人工干预的时机与方法，通过模型说明不需要人工干预是不可能的。从问题一到问题三、中文到英文由于难度的增加依次将模型进行改进，给出了严谨的说明过程，可认为模型对该类问题有很好的可用性。
6.2模型的缺点
论文中的模型仅适合规则碎纸片黑白信息的复原问题，不能解决不规则碎纸片的复原与非黑白信息的复原。人工干预占总过程时间的比例相对较高(35%)，对于数据量大的碎纸片复原问题，人工干预可能会花掉大部分时间。
如果问题二、三同问题一考虑图片倒置与否的问题，则会大大增加计算机编程的实现难度与人工干预的时间与精力，所以对于图像倒置与否的问题，本模型只给出了判别方法，而要真正通过人机结合实现难度大，只能先进行图片倒置与否的处理，在人工进行接下来的操作，这使模型的推广受到了限制。
6.3模型的推广
该模型适用于规则碎纸片的拼接复原问题。问题一中还给出了未知图片倒置情况时的碎纸片拼接复原方法，对于一些不熟悉的语言和符号信息，我们不知碎纸片的倒置情况，问题一给出了很好地解释。 根据中英文的复原结果，可以认为本论文中的模型很好的适用于该类问题的解决。同样对于未知的语言与符号信息，依据问题二三的模型，只需要做出问题一中的倒置情况的判断后，就可以按照本文的求解复原图片。
对于规则的残片，如考古挖出的规则的文物、规则的钞票残片等残片复原问题，只需将它们用照片照好转化为灰度矩阵，对颜色进行一定的处理后即可将本模型用于它们的复原。
七、参考文献
[1] 刘保柱，MATLAB7.0从入门到精通，北京：人民邮电出版社，2010年。
[2] 罗智中，基于文字特征的文档碎纸片半自动拼接，计算机工程与应用，37,207-210,2012。
[3] 牛刚，基于特征像素统计的图像相关匹配算法，，2013年9月13日。
[4] 卓金武，MATLAB在数学建模中的应用，北京：北京航空航天大学出版社，2011。
[5] 章毓晋，图像处理，北京，清华大学出版社，2012年。
[6] 姜启源,谢金星,叶俊,数学模型,北京：高等教育出版社，2008。
[7] 楼顺天,matlab程序设计语言,西安：高等教育出版社，2008。
八、附录
复原图片
附件1复原图片
附件2的复原图片
附件3的复原图片
附件4的复原图片
附件5的复原图片（正面）
附件5的复原图片（反面）
附录matlab代码
%%%%%%%%%%%%%%%%%%%%%%匹配度%%%%%%%%%%%%%%%%%%%%%%%%%
function ResultLine=sortTeam(R,R2L)
Indexs=R;
Result=zeros(length(R));
for i=1:length(R)
for m=1:length(R)
PercentCom(i,m)=R2L(R(i),R(m));
end
end
PercentCom;
flag=zeros(1,length(R));
Root=1;
ResultLine=[1];
for i=1:length(R)
[result,index]=max(PercentCom(Root,:)); flag(Root)=1;
PercentCom(Root,:)=0;
PercentCom(:,Root)=0;
flag(index)=1;
ResultLine=[ResultLine index];
Root=index;
if sum(flag(:)==1)==length(R)
break;
end
end
for i=1:length(R)
ResultLine(i)=R(ResultLine(i));
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%第一问的算法流程%%%%%%%%%%%%%
a{1}=imread(\'C:UsersAero?\');
a{2}=imread(\'C:UsersAero?\');
a{3}=imread(\'C:UsersAero?\');
a{4}=imread(\'C:UsersAero?\');
a{5}=imread(\'C:UsersAero?\');
a{6}=imread(\'C:UsersAero?\');
a{7}=imread(\'C:UsersAero?\');
a{8}=imread(\'C:UsersAero?\');
a{9}=imread(\'C:UsersAero?\');
a{10}=imread(\'C:UsersAero?\');
a{11}=imread(\'C:UsersAero?\');
a{12}=imread(\'C:UsersAero?\');
a{13}=imread(\'C:UsersAero?\');
a{14}=imread(\'C:UsersAero?\');
a{15}=imread(\'C:UsersAero?\');
a{16}=imread(\'C:UsersAero?\');
a{17}=imread(\'C:UsersAero?\');
a{18}=imread(\'C:UsersAero?\');
a{19}=imread(\'C:UsersAero?\');
%取边缘
for?i=1:19
???demo=[];
???demo(:,1)=a{i}(:,1);
???demo(:,2)=a{i}(:,length(a{i}(1,:)));
???T{i}=demo;
end
%二值化
for?i=1:19
????Com=[];
???for?m=1:2
??????for?n=1:1980
??????????if?T{i}(n,m)==255
??????????????Com(n,m)=0;
??????????else
??????????????Com(n,m)=1;
??????????end
??????end
???end
???C{i}=Com;
end
Left=[];
for?i=1:19
????Left=[Left,C{i}(:,1)];
end
Right=[];
for?i=1:19
???Right=[Right,C{i}(:,2)];?
end
LeftCov=[];
for?i=1:19
???LeftCov=[LeftCov,C{i}(:,1)];?
end
for?i=1:19
???for?m=1:1980
??????demo(1981-m,i)=LeftCov(m,i);
???end
end
LeftCov=demo;
RightCov=[];
for?i=1:19
???RightCov=[RightCov,C{i}(:,2)];?
end
for?i=1:19
???for?m=1:1980
??????demo(1981-m,i)=RightCov(m,i); ???end
end
RightCov=demo;
%PercentL2LC
%for?i=1:19
?%??for?m=i:19
??%?????PercentL2LC(i,m)=SingleCompare(Left(:,i),LeftCov(:,m));
???%end
%end
%PercentL2R
%for?i=1:19
???%for?m=i:19
??????%?PercentL2R(i,m)=SingleCompare(Left(:,i),Right(:,m));
??%?end
%end
%PercentR2L
for?i=1:19
???for?m=1:19
???????PercentR2L(i,m)=SingleCompare(Right(:,i),Left(:,m));
???end
end
%PercentR2RC
for?i=1:19
???for?m=1:19
???????PercentR2RC(i,m)=SingleCompare(Right(:,i),RightCov(:,m));
???end
end
%PercentLC2L
for?i=1:19
????for?m=1:19
????????PercentLC2L(i,m)=SingleCompare(LeftCov(:,i),Left(:,m));
????end
end
%PercentLC2RC
for?i=1:19
????for?m=1:19
????????PercentLC2RC(i,m)=SingleCompare(LeftCov(:,i),RightCov(:,m)); ????end
end
%PercentL2LC;
%PercentL2R;
%PercentR2L;
%PercentR2RC;
??????PercentR2L;
??????PercentR2RC;
??????PercentLC2L;
??????PercentLC2RC;?
for?i=1:19
??????PercentR2L(i,i)=0;
??????PercentR2RC(i,i)=0;
??????PercentLC2L(i,i)=0;
??????PercentLC2RC(i,i)=0;
end
%从R2L下手
Sample{1}=PercentR2L;
Sample{2}=PercentR2RC;
Sample{3}=PercentLC2L;
Sample{4}=PercentLC2RC;
flag=zeros(1,19);
flagCov=zeros(1,19);
flagCov(1)=1;
i=1;
step=1;
Path(1)=1;
Num=2;
for?s=1:500
????if?step==1
???????[result1,index1]=max(Sample{1}(i,:));
???????[result2,index2]=max(Sample{2}(i,:));
???????if?result1>=result2
???????????disp(\'r1>r2\')
???????????pause
??????????Path(Num)=index1;
??????????flagCov(index1)=1;
??????????Sample{1}(i,:)=0; ??????????i=index1;
??????????step=1;
??????????Num=Num+1;
???????else
????????????disp(\'r1 ????????????pause ??????????Path(Num)=index2; ??????????flagCov(index2)=1; ??????????Sample{2}(i,:)=0; ??????????i=index2; ??????????step=0; ??????????Num=Num+1; ???????end ????else ????????[result3,index3]=max(Sample{3}(i,:)); ????????[result4,index4]=max(Sample{4}(i,:)); ????????if?result3>=result4 ?????????????disp(\'r3>r4\') ?????????????pause ????????????Path(Num)=index3; ????????????flagCov(index3)=1; ????????????Sample{3}(i,:)=0; ????????????i=index3; ????????????step=1; ????????????Num=Num+1; ????????else ?????????????disp(\'r3 ?????????????pause ????????????Path(Num)=index4; ????????????flagCov(index4)=1; ????????????Sample{4}(i,:)=0; ????????????i=index4; ????????????step=0; ????????????Num=Num+1; ????????end ????end ???? ????if?sum(flagCov(:)==1)==19 ????????break; ????end end s flagCov Path %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%第二问中文%%%%%%%%%%%%%%%%%%%%%%%%% %第二问中文 for?i=1:208 ????????str=?strcat(\'C:UsersAero?FantasiaDesktopCompetitionB1T3\',fullname(i),?\'.bmp\'); ????????b{i}=?imread?(str);???? end a{1}=imread(\'C:UsersAero?\'); for?i=1:208 ???a{i+1}=b{i};? end Top=zeros(1,209); for?i=1:209 ????if?sum(a{i}(1,:)==255)==72 ????????Top(i)=0; ????else ????????Top(i)=1; ????end end Area=zeros(180,209); for?i=1:209 ????for?m=1:180 ???????if?find(a{i}(m,:)<255) ???????????Area(m,i)=1; ???????end ????end end for?i=1:209 ???for?m=1:209 ???????Similarity(i,m)=SingleCompare2(Area(:,i),Area(:,m)); ???end end for?i=1:209 ???Similarity(i,i)=0; end ninty=zeros(1,209); nintyfive=zeros(1,209); eightyfive=zeros(1,209); for?i=1:209 ????countN=0; ????countF=0; ???for?m=1:209 ???????if?Similarity(i,m)>0.9 ???????????countN=countN+1; ???????elseif?Similarity(i,m)>0.95 ???????????countF=countF+1; ???????end ???end ??? ???ninty(i)=countN; ???nintyfive(i)=countF; ??? end for?i=1:209 ????countF=0; ???for?m=1:209 ???????if?Similarity(i,m)>=0.95 ???????????countF=countF+1; ???????end ???end ???nintyfive(i)=countF; end ???? for?i=1:209 ????countF=0; ???for?m=1:209 ???????if?Similarity(i,m)<=0.9&&Similarity(i,m)>=0.85 ???????????countF=countF+1; ???????end ???end ???eightyfive(i)=countF; end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%第二问英文%%%%%%%%%%%%%%%%% for?i=1:208 ????????str=?strcat(\'C:UsersAero?FantasiaDesktopCompetitionB1T4\',fullname(i),?\'.bmp\'); ????????b{i}=?imread?(str);???? end a{1}=imread(\'C:UsersAero?\'); for?i=1:208 ???a{i+1}=b{i};? end %边缘矩阵 Left=zeros(180,209); Right=zeros(180,209); for?i=1:208 ????Left(:,i)=a{i}(:,1); ????Right(:,i)=a{i}(:,length(a{1}(1,:))); end %边缘二值化 for?i=1:209 ???for?m=1:180 ???????if?Left(m,i)==255 ???????????Left(m,i)=0; ???????else ???????????Left(m,i)=1; ???????end ???????if?Right(m,i)==255 ???????????Right(m,i)=0; ???????else ???????????Right(m,i)=1; ???????end ???end end %匹配度矩阵 PercentR2L=zeros(209,209); for?i=1:209 ???for?m=1:209 ???????PercentR2L(i,m)=SingleCompareCom(Right(:,i),Left(:,m)); ???end end for?i=1:209 ???PercentR2L(i,i)=0;? end PercentCopy=PercentR2L; Army=1; Path=[]; flag=zeros(1,209); for?i=1:300 ????Num=1; ????if?sum(PercentR2L(i,:))~=0 ????????Root=i;? ????????Path(Army,Num)=Root; ??????for?m=1:18 ????????[result,index]=max(PercentR2L(Root,:)); ????????Path(Army,Num+1)=index; ????????Num=Num+1; ????????flag(1,Root)=1; ????????flag(1,index)=1; ????????PercentR2L(Root,:)=0; ????????PercentR2L(:,Root)=0; ????????Root=index; ??????end ??????PercentR2L(index,:)=0; ??????PercentR2L(:,index)=0; ??????Army=Army+1; ????end ????if?sum(flag(:))==209 ????????break; ????end end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
更多推荐
纸片,匹配,矩阵,复原
发布评论