2013全国大学生数学建模比赛B题_答案.doc

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为纵横切碎片数据，每页纸被切为1119个碎片。（4） 附件5为纵横切碎片数据，每页纸被切为1119个碎片，每个碎片有正反两面。该附件中每一碎片对应两个文件，共有21119个文件，例如，第一个碎片的两面分别对应文件000a、000b。【结果表达格式说明】复原图片放入附录中，表格表达格式如下：(1) 附件1、附件2的结果：将碎片序号按复原后顺序填入119的表格；(2) 附件3、附件4的结果：将碎片序号按复原后顺序填入1119的表格；(3) 附件5的结果：将碎片序号按复原后顺序填入两个1119的表格；(4) 不能确定复原位置的碎片，可不填入上述表格，单独列表。二、模型假设假设题目中的碎纸图片与真实文件纸张大小、颜色、边缘情况相同。假设题目中的碎纸照片边缘完整，不存在破损。假设所有碎纸片的扫描情况相同。假设人工干预后可以得到正确结果。假设原文件纸张的内容具有意义。三、符号说明符号符号意义编号为的图片的灰度矩阵编号为的图片经二值化处理后的矩阵编号为的图片的二维边缘矩阵、边缘匹配度矩阵编号为i的图片在此处理后的二值化矩阵边缘匹配度之和矩阵*其他未提及的符号会在文章中说明。四、问题分析4.1问题一的分析4.11 中文碎纸片的复原分析问题1、2、3附件1、2、3、4、5中的碎纸片均为一份纸张撕裂所得，所以碎纸片中不会存在含有相同信息的公共部分，这里进行强调，下面不再重述。附件1中所给的图片为5扫描原纸张碎片后得到的BMP格式的图片，图片像素均为，使用1matlab中的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，矩阵均为的矩阵，这里我们分别将每张图片的Bi矩阵第1列和第72列提取出来做一新的二维边缘矩阵Ci，它是的矩阵。通过对所有图片矩阵的分析可以发现C3 、C4矩阵中均有一列为0，所以可以认为编号为003和004的图片为原完整文件的一端，在做题过程中无需考虑会存在其他白边与白边拼接的情况。做如上判断后解题过程同4.11。4.2问题二的分析4.21中文碎纸片的分析此问中同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。若i经过19次后返回0，则可以认为所有的碎纸片已拼接在一起，仅需把两个空白端分开后再做人工调整，则可得到结果；若i少于19次变化后变为0，则认为部分碎纸片未拼在一起，要把剩余的纸片拼接在一起后做人工调整。根据所得两个矩阵、的情况，发现任意一行的大于，可以一定程度说明碎纸片中不存在倒置的情况，仅按上述大于等于的情况做分析即可。 该方法可以用图7的matlab软件编程流程图来表示。可以看出由于问题一中的数据量较小，为了方便我们仅对计算机的编程结果进行人工干预，而不对过程做人工干预。i=0 maxDi=maxDi?记录i并重新赋值i是i=0?否i经过19次变化（若重新进行了搜索，此处为19-n次）是结束并输出结果人工处理是本次搜索结束，记录i并记录搜索次数n并重新赋值i开始新的搜索记录i并重新赋值i否maxDi=maxDi?图7.流程图得到的结果见表1： 表1.计算机拼图位置表格1000006008014012015003010002016001004005009013018011007001根据表种情况可已发现碎纸片006和碎纸片008连接在一起，发生这种情况的原因是两白边边缘匹配度为1.0，所以他们匹配在了一起，根据实际情况，可以判定碎纸片008为正常放置情况下原纸张的左端，所以重新指定表格，以碎纸片008作为纸片的开端，表格见表2，在使用matlab中的imshow（）函数，得到人机结合后的复原图片。 表2.修改后的拼图位置表格20080140120150030100020160010040050090130180110070010000065.1.2 英文碎纸片的拼接复原根据4.1.1与4.1.2的分析，模型建立求解同5.1.1。使用计算求解的结果见表3。 表3.计算机拼图位置表格3000005001009013010008012014017016004003006002007015018011根据表种情况可已发现碎纸片003和碎纸片004连接在一起，发生这种情况的原因是两白边边缘匹配度为1.0，所以他们匹配在了一起，根据实际情况，可以判定碎纸片003为正常放置情况下原纸张的左端，所以重新指定表格，以碎纸片003作为纸片的开端，表格见表3，在使用matlab中的imshow（）函数，人机结合后的复原图片见图片5。 表4.修改后的拼图位置表格40030060020070150180110000050010090130100080120140170160045.2 问题二模型的建立与求解5.21 中文碎纸片复原的模型建立与求解搜索每一张碎纸片转化后二值化矩阵的每一行，若存在黑色即矩阵该行中存在数值1，则将该行全部赋值为1，若这一行不存在黑即此行元素全为0，则将该行全部赋值为0，这样将209张碎纸片做出新的二值化矩阵，之后同5.1的求解过程做边缘匹配，做出矩阵大小为边缘匹配度矩阵（由于矩阵太大，在论文中不作出），元素为处理后的碎纸片边缘二值化矩阵i的第二列与处理后的碎纸片边缘二值化矩阵j第一列的边缘匹配度，匹配度高则说明碎纸片的文字信息处于同一水平位置。在矩阵中每一行选取匹配度大于0.9的元素，进行统计分组，可得结果如下表表5. 表5.分组情况序号碎纸片编号10 7 45 53 68 126 137 138 158 174 175 20821 18 23 26 30 41 50 62 76 86 87 100 120 142 147 168 179 191 19532 11 22 28 49 54 57 65 91 95 118 129 141 143 178 186 188 190 19243 12 31 39 51 73 82 107 115 128 134 135 159 160 169 176 199 20354 40 101 108 113 114 117 119 123 140 146 151 154 155 185 194 20765 10 29 37 44 48 55 59 64 75 92 98 104 111 171 172 180 201 20676 19 20 36 52 61 63 67 69 72 78 79 96 99 116 131 162 163 17788 9 25 74 1059182 131015 17 3380831321331561982002021116 21 66 106 109 110 139 145 150 157 173 181 184 187 197 2041224 35 38 46 81 88 103 122 130 148 161 167 189 1931327 60 85 152 165 170 2051432 56 70 93 153 166 1961534 42 43 47 58 77 84 90 94 97 112 121 124 127 136 144 149 164 1831614177118891910220125可以看出在取匹配度为0.9及以上时，分出了20个组，其中组内元素最多的为19，组内元素最少的为1。而最后的结果应该为11行，我们需要对这些组中的元素进行合并后得到11行，所以我们要先考虑元素数量为19的组，再考虑其他元素数多的组，对组内图片进行5.1中的边缘匹配，匹配后的结果在与元素数少的组做匹配与人工处理。以序号2的组为例，该组包含19个元素，对于组内的19个元素的原始二值化矩阵进行上述中的边缘匹配，通过结果观察本题模型第一步确定模型的的可行性，其他的组的处理情况相同，不再重述。结果如下，见表6。表6.内部分组序号分组2062-142-030-041-023-147-191-050-179-120-086-195-026-001-087-018168-100-076分别复原得到图片，观察下面的图8、图9。 图8 图9对于第二问中文碎纸片的复原问题，通过上面的结果发现匹配结果较好，对于中文的碎纸片的拼接复原即使过程中未加入人工干预也可以得到较优的结果。可以发现该组中文字的位置符合我们的想象，及同一行中的文字拥有同一上界和同一下界，在这一组中matlab软件很好的将碎纸片拼接出来，思考为什么会出现上面图9图10两者不能匹配在一起的原因。可以发现拼接复原后的图8、图9左右两侧均存在白边，仅从计算机的角度出发，无法认出两者的先后，所以这里我们要加以人工干预，通过对文章的内容、文章的结构、文章的形式的观察人工拼接，得出结果。改进后的图片排序见表7，复原图片见图10。 表7. 人工干预序号分组2168-100-076-062-142-030-041-023-147-191-050-179-120-086-195-026-001-087-018 图10通过结果可以发现拼接程度较好，所以也验证了本问题中碎纸片拼接复原模型的可行性。其他组做相同处理，这样可得到拼接好的11横行的碎纸条，对11横行的碎纸条的长边进行边缘匹配，建立新的边缘匹配矩阵，方法同上，做出结果如下，见表9。 表9一014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043二125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196三049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036四168100076062142030041023147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074五089146102154114040151207155140185108117004101113194119123六071156083132200017080033202198015133170205085152165027060以上做出的表格把一些横行碎纸片拼接在一起，未能拼接的原因是由于拼接后的横行碎纸片两端都存在白边，计算机无法做出顺序的判断，所以我们要根据文字内容、规格、形式等因素人工将它们结合起来，人机结合后的原文件以下面的表格10。 表10.附件3的复原049054065143186002057192178118190095011022129028091188141061019078067069099162096131079063116163072006177020052036168100076062142030041023147191050179120086195026001087018038148046161024035081189122103130193088167025008009105074071156083132200017080033202198015133170205085152165027060014128003159082199135012073160203169134039031051107115176094034084183090047121042124144077112149097136164127058043125013182109197016184110187066106150021173157181204139145029064111201005092180048037075055044206010104098172171059007208138158126068175045174000137053056093153070166032196089146102154114040151207155140185108117004101113194119123观察发现拼接复原后结果较好。5.22英文碎纸片复原的模型建立与求解搜索每一张碎纸片转化后二值化矩阵的每一行，若存在黑色像素数量大于等于13即矩阵该行中数值1的数量大于等于13，则将该行全部赋值为1，若这一行黑色像素数量小于13，则将该行全部赋值为0，这样将209张碎纸片做出新的二值化矩阵，之后同5.1的求解过程做边缘匹配，做出矩阵大小为边缘匹配度矩阵（由于矩阵太大，在论文中不作出），元素为处理后的碎纸片边缘二值化矩阵i的第二列与处理后的碎纸片边缘二值化矩阵j第一列的边缘匹配度，匹配度高则说明碎纸片的文字信息处于同一水平位置。同样在矩阵中每一行选取匹配度大于0.9的元素，进行统计分组。在这里需要强调的是，若分完组后的组内元素进行5.2.1中的边缘匹配进行残片复原，小组成员发现结果十分的不理想，任举一例，见下图11。图11根据图12可以发现对于本文中的英文残纸片的文字信息主要内容处于相同水平位置，文字信息处于同一水平位置，结合5.2.1可以认为首先判断文字信息未知的方法是正确的。但是组内英文碎纸片的拼接复原程度结果差，图中部分碎纸片得到了复原，而大部分却进行了错误的拼接。对比5.2.1的中文复原结果，可以认为英文相对中文会有一定的特殊性。分析产生问题的原因，由于碎纸片的连接是按照组内图片两两边缘匹配的的大小来决定的，发生如图的情况说明：实际的对应的碎纸片的边缘匹配度一般在0.9以上，英文碎纸片实际对应的碎纸片的边缘匹配度会出现比其他碎纸片的边缘匹配对小的情况。面对这种问题，我们需要对检测边缘匹配度的程序的过程进行人工干预，方法为：其他图片对当前图片的边缘匹配度若出现两个及两个以上大于0.9的匹配度，则进行人工干预，根据文章的内容、格式等进行人工拼接复原，其他步骤同5.2.1。对于本文中对于英文碎纸片的拼接复原问题可用下面图12的流程图表示。开 始对灰度矩阵进行5.2.2中的二值化处理对二值化矩阵Ei做边缘匹配选取每一个元素对应匹配度大于0.9的元素存于一组中，即将对应的图片归为一组对于每一组内图片做5.1中的边缘匹配当前碎纸片对应其他碎纸片的匹配度为0.9以上的碎纸片张数大于等于2张人工干预选择碎纸片并判断是重复判断过程多次直到结束否人工干预处理结果计算机给出最大的结果后人工判断 图12.流程图通过上述步骤可一把相同行的纸片先拼接好，得到新的11张横行碎纸片，这里拼接11张碎纸片的方法同5.2.1，不再重述，得到的结果见下表11。 表11.附件4的复原19175111541901842104180641064149322046539671472011481701961989411316478103918010126100617281468651107294015818698241171505595892303746127191949314188121126105155114176182151225720271165821591391129631381535338123120175855016018797203312041108116136733620713515764319945173791611791432082174961119331421686216954192133118189162197112708460146817413719584717215696239912290185109132181956916716316618811114420631303413110252717817142662051015774145831345518563516918315244817712820013152125140193878948721217712401021155.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，则计算输出最大者，人工判断碎纸片是否匹配。综上先建立边缘匹配度之和矩阵，然后按照上面的匹配原则开始匹配。若出现计算机给出的结果人工判断后发现匹配错误，则记录当前匹配成功的碎纸片信息并在剩下的碎纸片中重新开始计算机匹配与人工判断。该过程可以用下面的流程图图13来表示。 开始数据初始化（边缘匹配度矩阵）找出当前节点所有较优匹配最佳匹配个数为三个或以上最佳匹配个数在两个或以下人工干预节点选择最佳匹配算法自动选择最佳匹配是否还有待添加节点输出结果，进行最后调整否是 图13.流程图根据上面的流程图17，以009碎纸片为例（它是22个边缘碎纸片之一）作为起始的图片，进行拼接，拼接结果如下：该题中人工干预占了总过程的35%，按上面的原则做出一些拼接好的碎纸片后，按照5.2.2中的方法，可以将碎纸片拼接成为11横行的碎纸片，然后继续使用本问题三中的方法将11横行的碎纸片拼接完成并做人工判断与人工处理。附件5的还原后的表格见下表12、表13。表1278b111b125a140a155a150a183b174b110a66a108a18b29a189b81b164b20a47a136b89a10b36a76b178a44a25b192a124b22a120b144a79a14a59a60b147a152a5a186b153a84b42b30a38a121a98a94b61b137b45a138a56b131b187b86b200b143b199b11b161a169b194b173b206b156a34a181b198b87a132b93a72b175a97a39b83a88b107