2013 高教社 全国大学生数学建模获奖论文 碎纸片的拼接和复原

2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：S15076所属学校（请填写完整的全名）：河南理工大学参赛队员(打印并签名)：1.祝红祥2.程港3.王金强指导教师或指导教师组负责人(打印并签名)：（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。）日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1碎纸片的拼接复原摘要破碎文件的复原有着重要的意义以及实用价值。传统上，人们只能靠手工完成，效率十分低。当碎片数量过于庞大时，甚至无法完成。随着技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率，根据题意要求，我们需要研究的问题主要是关于规则碎片拼接问题。随着研究的深入，本问题分为三个大问题：首先对于单面文字纵切碎片进行复原，然后关于单面文字横纵切割碎片的复原，最后就是双面文字横纵切割碎片的复原。对于问题一，我们需要对单面文字纵切碎片进行复原。为此，我们建立了边缘最大相似度匹配模型来解决该问题。我们首先将图片读入Matlab软件生成相应的灰度值矩阵，考虑到纸片被切割后，左右碎片在切割线相应位置的灰度值接近相同，即左边碎片灰度值矩阵与右边灰度值矩阵在切割线附近数值接近。由此，我们借助Matlab软件的()2corr函数计算一碎片与其他所有碎片在切割线附近灰度值最大相似度来找到与之匹配的碎片，从而达到了良好的复原效果。对于问题二，我们需要对单面文字横纵切割碎片的复原。此问题增加了碎片的数量，为了简化算法，减少计算量，我们建立了横纵扫描模型。由于整张纸的左右边缘没有字迹（即该处的灰度值为255），我们扫描（读取）所有碎片的左侧附近灰度值，如果灰度值都等于255，那么该碎片就很有可能属于纸张左边缘。为了进一步确定，我们可以多扫描几列灰度值。确定左边缘碎片后，我们以其中某一碎片作为起点，应用问题一中我们所建的边缘最大相似度匹配模模型对其右边进行匹配，最终完成整行的复原得到一条状图形。同理，我们可以得到其他10张条状图形。此时，问题二最终就转化成了问题一，最终我们成功完成对图形复原的任务。对于问题三，我们要解决的就是双面文字横纵切割碎片的复原问题。该问题在前两问的基础上又进一步增加了问题难度，即碎片具有双面文字。在解决双面文字横纵切割碎片的复原问题中，我们借助了问题一和二中的模型。有了前两问的基础，在此问题上我们着重考虑了双面问题。我们先找到左边缘碎片，然后再以边缘碎片与其他碎片进行匹配最终得到11张条状图形，然后再对着11张图片进行匹配，在双面碎片匹配过程中，我们分别求出某一碎片与其他所有碎片两个面的边缘相似度，然后让最大边缘相似度对应碎片的面与这一碎片匹配，最终达到良好的复原效果。关键词：碎片复原；边缘最大相似度匹配模型；横纵扫描模型；Matlab2一、问题重述将破碎文件的拼接、复原，在司法获取物证、历史文献修复以及军事情报获取等领域都有着重要的作用。但是传统拼接技术落后，拼接复原工作都是由人工完成的，虽然提高了准确率，但效率很低。特别是当碎片数量较多时，人工拼接在短时间内基本不可能完成任务。随着科学技术技术的发展，人们将计算机技术引入，试图开发碎纸片的自动拼接技术，以提高拼接复原效率。在这样的背景下利用所学的知识讨论并解决以下问题：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、问题分析问题一针对破碎文件的拼接，附件1、附件2为纵切碎片数据，对给定的来自同一页印刷文字的碎纸机破碎纸片,每页纸被切为19条碎片（仅纵切），要求将纵切的只带进行拼接，并建立碎纸片拼接复原模型和算法。，附件一中给出了所要拼接的碎片，但不能直接使用拼接。我们利用MATLAB软件对图片进行处理，读入附件所给的灰度图，用适当的程序实现图像的数字化。对于每一个碎纸片的灰度矩阵进行数字化处理。得到了图片对应的数组矩阵。首先进行人工干预，将其中可以明显看出原来处于第一个和最后一个位置处的文件碎片，我们分别将这两个文件碎片放到原来它们所处的位置处，然后就有多种处理方法可以使用，如利用c语言程序编程，将举证数组配对，并用欧氏距离惊醒计算，找到最近距离输出结果；或运用matlab相似度函数()2corr，取出该碎片最后一列数组与剩余的碎片的第一列进行相似度对比，取其相似度最大的碎片，利用Matlab程序得出所要拼接的原图顺序。鉴于对原始数据量大的考虑，结我们选择后一种方法。计算匹配矩3阵，得出碎纸片拼接的匹配矩阵。找出复原图片的左右两张碎纸片，自左端开始，依次向右进行匹配拼接，直至与右端图片拼接完成。问题二，来自同一页印刷文字的碎纸机破碎纸片（纵横切），附件3、附件4为纵横切碎片数据，每页纸被切为11×19个碎片建立碎纸片拼接复原模型和算法。由于问题二与问题一相比较数据量明显增大所以要分阶段对题目分析，首先还是要对文件碎片进行数字化处理，但是我们无法直接从图片中找到参照碎片（即处于原文件边缘的碎片），所以我们就对所有碎片的左边界进行分析，分析它空白的宽度，从而可以找到处于原文件左侧的碎片，然后在以这些碎片为参照物，利用Matlab余碎片进行分析，可以求得几条矩阵条（行型文件碎片），这时数组矩阵的个数不减少了很多个，但是又没有了参照碎片。故我们只能从条形矩阵上找突破点了，我们可以想到一张纸上都有页眉，所以我们可以先选出那一个位于原图最上边位置的条形矩阵，最后再次引入()2corr函数，再条形矩阵排成一定的序列，然后按序列将纸片拼接的匹配矩，最终原件。问题三，由于日常生活中我们不仅仅只有单面打印的纸张，双面打印的纸张也很常见,，附件5为纵横切碎片数据，每页纸被切为11×19个碎片，每个碎片有正反两面。该附件中每一碎片对应两个文件，共有2×11×19个文件，例如，第一个碎片的两面分别对应文件000a、000b。所以本题要求对双面的纸张碎片进行拼接，并写出相应的算法。首先我们要明确双面打印的纸张它的每一面都有文字，拼接时必须考虑，对碎片进行数字化处理，然后得到了418个矩阵，我们接下来就要考虑参考碎片的选取问题，因为这里的碎片是双面的，所以在计算出的便捷参照碎片也将是原来的二倍，因此我们也直接引入所有的碎片面进行匹配，组ii后会得到行中碎片编码相同的情况，对此我们可以舍弃其中的一部分（因为重复的碎片有着不同的特征），剩下的那部分我们在利用Matlab程序对其进行关联度分析，并输出对应的碎片编码，用人工干涉的方法找出最上端的文件碎片条，然后由上端开始，依次向下进行匹配拼接，直至与最下端图片拼接完成。三、问题假设1.假设在文件撕碎时，对碎片上的文字影响较小；2.认为所有的文件碎片大小相等；3.假设英文和中文撕碎后拼接时方法是相同的；4.认为所有在原图边界处的碎片中文字和边都有一定的距离，且比其他的都大。4四、符号说明符号符号说明x表示文件碎片数字化后的矩阵元素k表示各个数字化的矩阵，其中hk表示h号图片矩阵的第一列，ik表示第i号图片矩阵的最后一列n表示数字化矩阵的行列数R表示两矩阵的相似度y表示条形矩阵，其中iy表示第i个条形矩阵五、模型的建立与求解5.1问题一的模型建立与求解对于问题一，依据题目给定的条件，我们先对附件一进行适当处理，根据文件碎片的像素将附件一种给定的图片转成数组矩阵的形式，图中没有文字的空白部分计为0，反之则取值在0到255之间，然后先对数据进行人工筛选，选出原图起始和结束位置的文件碎片，放置到对应位置。但是由于图片数字化后所得到的矩阵数量很大（198072），为了简化计算，我们采用相似度分析法：首先提取剩余文件碎片的边界数组运用Matlab软件中的()2corr函数来分析数组的相似度（这个函数的返回值在-1到1之间，0表示完全无关，1和-1表示完全相关。），得出一组相似度读数据，比较选出最合适的文件碎片按顺序排放。5算法过程图由于附录1给出的图片编号从000开始，我们这里将000计为pic1，以此类推。首先数字化后的矩阵：nnnnxxxxk1111人工干预选取出：255][]1[k和255][][nk两个矩阵将其放于开与结尾处提取边界数组：左端1niihxxk文件碎片数字化人工干预提取对象边界相似度比较选择匹配对象回复原图6右端nnnixxk1引入Matlab软件代入相似度函数()2corr并循环比较，并输出R绝对值最大的i的值再令ih;19,2,1i最终本文利用数学软件Matlab，得到如下的匹配序列及匹配矩阵即复原后的文件碎片的顺序改回原编码如表1、表2所示（图片见附录）008014012015003010002016001004005009013018011007017000006表1表示附件一复原后的排列顺序003006002007015018011000005001009013010008012014017016004表2表示附件二复原后的排列顺序5.2问题二的模型建立与求解5.2.1、模型的建立对于问题二来自同一页印刷文字的碎纸机破碎纸片（纵横切），建立碎纸片拼接复原模型和算法。要考虑到问题中的文件碎片相比问题一更加的复杂，所以在问题一的基础上进一步求解。步骤一：将文件碎片数字化处理，得到多组矩阵，利用Matlab软件算法将原文件中位于第一列的文件碎片筛选出了；步骤二：再次用问题一中的方法，对每一行的文件碎片进行相似度分析，找出每一行的文件碎片；步骤三：人工干涉，将11行文件碎片的首行找到，然后运用corr2（）函数进行关联度分析，找到碎片顺序，回复出原图。5.2.2、模型的求解将图片编码更改，令000记为pic1，以此类推。首先对文件碎片进行图像的处理，得到数组矩阵：nnnnxxxxk1111在这些矩阵中对255][]][[jik（;72,2,1;209,2,1ji）进行查找，7首次得到的是结果：8，15，30，39，50