1、2013 高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： B 我们的参赛报名号为（如果
2、赛区设置报名号的话）： 所属学校（请填写完整的全名）： 重庆邮电大学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2013 年 9 月 13 日赛区评阅编号（由赛区组委会评阅前进行编号）：2013 高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1碎纸片的拼接复原摘要本文研究的是碎纸片的拼接复原问题。由于人工做残片复原虽然准确度高，但有着效率低的缺点，仅由计算
3、机处理复原，会由于各类条件的限制造成误差与错误，所以为了解决题目中给定的碎纸片复原问题，我们采用人机结合的方法建立碎纸片的计算机复原模型解决残片复原问题， 并把计算机通过算法复原的结果优劣情况作为评价复原模型好坏的标准，通过人工后期的处理得到最佳结果。面对题目中给出的 BMP 格式的黑白文字图片，我们使用 matlab 软件的图像处理功能把图像转化为矩阵形式，矩阵中的元素表示图中该位置像素的灰度值，再对元素进行二值化处理得到新的矩阵。题目每一个附件中的碎纸片均为来自同一页的文件，所以不需考虑残片中含有未知纸张的残片以及残片中不会含有公共部分。鉴于残片形状分为“长条形”与“小长方形” ，残片内容
4、分为中文、英文，纸张的打印类型分为“单面型” 、 “双面型” ，所以我们根据残片的类型对矩阵做不同处理。针对问题一中给出的“长条形”碎纸片：对图片转化后的矩阵进行边缘检测，发现每一张图片的两短边在一定范围内全是白色，而仅有 2 张图片的长边在一定范围内全是白色，说明我们需要对长边进行拼接，一边包含全白的长边是原文件纸张的两端。由于考虑到模型应用的推广，我们在此问中的模型包含了图片倒置的情况（仅在问题一中考虑倒置情况，鉴于问题二、三中数据量的增多，二三问不再考虑倒置情况） ，对图片的长边及矩阵中的第一列和最后一列与其他矩阵的第一列和最后一列进行边缘匹配，根据边缘匹配度来确定图片复原，最后若发现拼
5、接效果有偏差，在进行人工操作。针对问题二中的“小长方形”碎纸片：由于数据量变多，盲目使用问题一中的方法不能保证准确度，所以这里要进一步约束使当前图片与少量图片进行匹配。观察两种文字的特点，我们可以发现中英文在位置上均有一定的特性，我们利用这种特性将有相同位置特性的碎纸片归类为一组，在问题一方法的基础上做少许修改后代入有相同位置特性的一组碎纸片中，根据边缘匹配度将他们连接、检查并做人工处理可得拼接后的横行纸片，再将横行纸片的长边用同样的方法做边缘匹配可将行与行之间拼接起来，再做人工调整得到最优结果。通过模型的建立求解过程可以发现中英文在本问题的求解方法中有着一定的不同，英文需要更多地人工判断处理
6、。针对问题三考虑到双面问题以及问题二中英文碎纸片的情况，我们把碎纸片两面匹配度之和作为判断碎纸片是否连接的评价标准，在问题一方法的基础上，在计算机每一步的匹配结果加以人工选择与判断，这样再次处理得到的结果，可以得到同问题二中一样的横行碎纸片，在根据新的横行碎纸片的两面边缘匹配度之和进行同样的操作处理可以将原纸张拼接复原。关键词： 残片复原 matlab 图像处理 二值化 边缘匹配度 倒置情况 位置特性 2人工处理一 问题重述B 题 碎纸片的拼接复原破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当
7、碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切） ，建立碎纸片拼接复原模型和算法，并针对附件 1、附件 2 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】 ） 。 2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件 3、附件4 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，
8、请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件 5 给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件 5 的碎片数据给出拼接复原结果，结果表达要求同上。【数据文件说明】（1 ） 每一附件为同一页纸的碎片数据。（2 ） 附件 1、附件 2 为纵切碎片数据，每页纸被切为 19 条碎片。（3 ） 附件 3、附件 4 为纵横切碎片数据，每页纸被切为 1119 个碎片。（4 ） 附件 5 为纵横切碎片数据，每页纸被切为 1119 个碎片，
9、每个碎片有正反两面。该附件中每一碎片对应两个文件，共有 21119 个文件，例如，第一个碎片的两面分别对应文件000a、000b。【结果表达格式说明】复原图片放入附录中，表格表达格式如下：(1) 附件 1、附件 2 的结果：将碎片序号按复原后顺序填入 119 的表格；(2) 附件 3、附件 4 的结果：将碎片序号按复原后顺序填入 1119 的表格；3(3) 附件 5 的结果：将碎片序号按复原后顺序填入两个 1119 的表格；(4) 不能确定复原位置的碎片，可不填入上述表格，单独列表。二、模型假设假设题目中的碎纸图片与真实文件纸张大小、颜色、边缘情况相同。假设题目中的碎纸照片边缘完整，不存在破损
10、。假设所有碎纸片的扫描情况相同。假设人工干预后可以得到正确结果。假设原文件纸张的内容具有意义。三、符号说明符号 符号意义iA编号为 的图片的灰度矩阵iiB编号为 的图片经二值化处理后的矩阵iC编号为 的图片的二维边缘矩阵i、 、 、D 边缘匹配度矩阵iE编号为 i 的图片在此处理后的二值化矩阵F边缘匹配度之和矩阵*其他未提及的符号会在文章中说明。四、问题分析4.1 问题一的分析4.11 中文碎纸片的复原分析问题 1、2、3 附件 1、2、3、4、5 中的碎纸片均为一份纸张撕裂所得，所以碎纸片中不会存在含有相同信息的公共部分，这里进行强调，下面不再重述。附件 1 中所给的图片为5扫描原纸张碎片后
11、得到的 BMP 格式的图片，图片像素均为 ，使用1matlab 中的 iamread 函数可以做出图片的灰度矩阵 ，举例如9807 iA下（由于该像素图片转换后为 的矩阵，论文中无法放置，所以仅简单举例说198072明，论文中若还出现庞大的矩阵，同本说明）：42501iA矩阵的中元素表示该位置图片的灰度，255 表示为白，0 为黑，图片中信息为黑白文字信息，但由于文字信息会存在阴影，所以矩阵中出现了介于 0-255 的元素。为了方便应用，并查阅相关资料所得，可以对于本题中的黑白图片做2二值化处理，可将上面例子中的 转化为如下的矩阵：iA01iB其中白色用 0 值表示，非白色用 1 表示。将附件
12、 1 中的 19 张图片做如上处理得到各自的二值化后的矩阵 Bi，矩阵均为的矩阵，这里我们分别将每张图片的 Bi矩阵第 1 列和第 72 列提取出来做一新9872的二维边缘矩阵 Ci，它是 的矩阵。通过对所有图片矩阵的分析可以发现 C6、C 89802矩阵中均有一列为 0，所以可以认为编号为 006 和 008 的图片为原完整文件的一端，在做题过程中无需考虑会存在其他白边与白边拼接的情况。两张图片匹配的原则可以根据下面的图 1、图 2 来表示。图 1.图片未倒置 图 2.图片倒置如图 1，当图片未出现倒置情况时，即题目中的图片均是正常摆放，将左边矩阵的第二列元素与右边矩阵的第一列元素进行两两匹
13、配。记录元素相同的个数，个数除以1980 为左边矩阵第二列对右边矩阵第一列的边缘匹配度，记为： 1980ijD元 素 相 同 的 数 量将所有碎纸片的二值化矩阵做如上匹配可依次选取与其匹配的碎纸片。图 1 中左边矩阵第一列与右边矩阵第二列匹配的原则与上述相同，不再重述。5如图 2，当图片出现倒置情况时，正常情况下应是左边矩阵的第二列元素与右边矩阵的第一列元素进行两两匹配，若倒置后，则应该是左边矩阵的第二列元素与右边矩阵的第二列元素倒置顺序进行比较，同样记录相同元素的个数并计算匹配度。图 2 中左边矩阵第一列元素与右边矩阵第一列元素的匹配原则与上述相同，不再重述。综合图一图二我们可以做出 4 个
14、边缘匹配度的矩阵，即未倒置时矩阵第一列与其他矩阵第二列的边缘匹配度、未倒置时矩阵第二列与其他矩阵第一列的边缘匹配度、倒置时矩阵第一列与其他矩阵第一列的边缘匹配度、倒置时矩阵第二列与其他矩阵第二列的边缘匹配度。由于（未）倒置时矩阵第一列与其他矩阵第二列匹配在思想上同（未）倒置时矩阵第二列与其他矩阵第一列匹配相同，所以这里只需考虑其中一种情况即可。任选其中一例说明，由于碎纸片倒置情况未知，需要考虑未倒置时的情况与倒置式的情况，未倒置时矩阵第一列与其他矩阵第二列的边缘匹配度矩阵第一行最大值与倒置时矩阵第一列与其他矩阵第一列的边缘匹配度第一行的最大值进行比较，选取匹配度大的作为拼接的纸片，即编号为 0
15、00 的碎纸片要与该纸片拼接。以此类推把 19 张碎纸片拼接完成后做人工处理。4.1.2 英文碎纸片的复原分析将附件 2 的 19 张图片做 4.11 中处理得到二值化后的矩阵 Bi，矩阵均为的矩阵，这里我们分别将每张图片的 Bi矩阵第 1 列和第 72 列提取出来做一新19807的二维边缘矩阵 Ci，它是 的矩阵。通过对所有图片矩阵的分析可以发现 C3 、 C419802矩阵中均有一列为 0，所以可以认为编号为 003 和 004 的图片为原完整文件的一端，在做题过程中无需考虑会存在其他白边与白边拼接的情况。做如上判断后解题过程同 4.11。4.2 问题二的分析4.21 中文碎纸片的分析此问
16、中同 4.1 的图片处理方法，也需要将 209 张碎纸片进行同样的图像处理转化为灰度矩阵后进行二值化处理得到处理后的矩阵。根据结果知此问中的图片转化后的矩阵为 的矩阵，列数由第一问中的 1980 变为 180，虽然数量变少，但是图片数量7280由 19 张变为了 209 张。若同样使用 4.1 中的边缘匹配的方法，一张碎纸片对应其他208 张碎纸片的边缘匹配相同的像素点有 208 种情况，变化范围为 0-180，可知若直接采用 4.1 中的方法得到的结果可能出现多个相同或无法判断的情况，所以这里我们先考虑附件 3 中碎纸片的特性。观察下面的图 3 可以发现，通过查阅资料分析2基于文字特征的文档
17、碎纸片半自6动拼接，每一行的绝大多数中文文字均可认为拥有同一上界、同一下界（图 3 最右端出现了“一”字，但是同行还存在其他文字，可以认为同一行文字有同一上界与同一下界） ，我们可以根据这一特性使用软件将3匹配度高及位置相同的碎纸片归类为一组。方法为：搜索每一张碎纸片转化后二值化矩阵 的每一行，若矩阵该行中存在数值iC1，则将该行全部赋值为 1，若这一行元素全为 0，则将该行全部赋值为 0，其中 1 表示本行存在灰度小于 255 的像素，0 表示不存在灰度小于 255 的像素，这样将 209 张碎纸片做出4新的二值化矩阵 ，之后同 4.1 的分析取边缘做边缘匹配得修改后的6边缘iE匹配度矩阵
18、，匹配度高则说明碎纸片的文字信息处于同一水平位置，见下图图 4，D之后再人工干预，得到较优的结果。图 3.处理的图片图 4.再次处理后的图片得到很多组有相同位置的的碎纸片后，在每一组内采用 4.1 的中的边缘匹配方法，这里为了防止出现两白边匹配造成碎纸片连接混乱的现象，要加以限制。方法为：若在组内做边缘匹配出现匹配度为 1 的情况，则暂时不连接此碎纸片，从剩余的碎纸片出发做边缘匹配与其他碎纸片连接，直到组内所有碎纸片均已覆盖。7这样再通过一定的人工干预可以得到拼接复原后的的 11 横行碎纸片，在同样使用4.1 的边缘匹配方法，7将得到的 11 行的碎纸条的长边进行边缘匹配做出 的匹1配度矩阵后
19、找最大匹配度作为连接的碎纸条，同样为了防止出现两白边匹配造成碎纸片连接混乱的现象，要加以限制。方法为：若在组内做边缘匹配出现匹配度为 1 的情况，则暂时不连接此碎纸片，从剩余的碎纸片出发做边缘匹配与其他碎纸片连接，直到 11 张拼接后的碎纸片均已覆盖。最后加以人工处理，得到完整的原文件。4.2.2 英文碎纸片的分析同 4.2.1 中的分析相同，通过观察我们可以发现碎纸片的英文在位置上也有一定的规则可循。如下图图 5。图 5.演示的图片可以发现英文字母的主要的部分拥有同一上界和同一下界，但是跟中文不同，英文中会出现一些“y” 、 “b”之类的字母，为了同样使用 4.2.1 中的方法我们通过观察附
20、件 4 中图片的像素情况，将图片中每一行中黑色像素数少于 13 的及字母的次要部分转变为二值化矩阵中的 0，将每一行中黑色像素大于等于 13 的及字母的主要部分转化为二值化矩阵中的 1，这样得到的新的二值化矩阵 ，可认为图像转变为图 6 的方式，iE同样使用 4.2.1 中的分析方法将新的二值化矩阵做边缘匹配，匹配度高的可以认为两碎纸片在原纸张中位于同一行，把匹配度高于 0.9 的元素分为一组后，对每一组进行边缘匹配。由于考虑到英文字符的情况，在 4.1 的基础上，我们对于组内图片原始二值化矩阵的边缘匹配度矩阵 每一行的搜索，在这里我们若矩阵的任意一行中出现匹配度大于D0.9 的元素个数超过
21、2 个，我们加以人工干预，根据文章的格式、内容选择应该连接的碎纸片，其他过程与 4.1 相同，区别仅为本文中需要对软件执行过程进行人工干预，其他相同的步骤不在重述。8图 6.演示图片4.3 问题三的分析本问在问题二英文碎纸片的基础上还需要考虑纸片是否处于同一面，虽然数据量增加了一倍，但是判断碎纸片是否连接的标准由一面增加到了两面。本不对应的两张碎纸片一面的拼接复原情况好而令一面复原情况也好的情况只是个别的案例，所以可以将碎纸片两面边缘匹配度之和作为评判两张是否匹配的标准建立边缘匹配度之和矩阵，在这里可以先认为匹配度之和高于 1.9 的情况为匹配结果优秀。若仅将匹配度之F和作为评判标准，基于 4
22、.2.2 中的求解过程，英文碎纸片的纯计算机复原结果较差，所以还需要在计算机匹配碎纸片的过程中每一步都要进行人工干预判断、选择。以纸片 000 与 001 为例，匹配方式可能为：01ab ： ： 01ab ： ：为了找出碎纸片如何对应，则将的边缘匹配度相加得到边缘匹配度之和，将的边缘匹配度相加得边缘缘匹配度之和，两者的和做出比较。若仅有一个大于等于 1.9，则计算机输出该匹配度，人工判断是否碎纸片是否匹配；若两者均大于等于1.9，计算机把两个匹配度之和输出，人工选择判断碎纸片应是否匹配与如何匹配；若两者均小于 1.9，则计算输出最大者，人工判断碎纸片是否匹配。若出现计算机给出的结果人工判断后发现匹配错误，则记录当前匹配成功的碎纸片信息并在剩下的碎纸片中重新开始计算机匹配与人工判断。上述的结果可以得到一些在同一横行的碎纸片的拼接，再次根据这些新的碎纸片的边缘匹配度之和的情况通过上述人机结合的方法拼出 11 张横行的碎纸片，剩下的就是应该如何把 11 张横行的碎纸片拼接成完整的一份纸张，这里将 11 张横行碎纸片的上下长边进行两两匹配，以两面边缘匹配度之和的方法按照上述的方法将 11 横行的碎纸片拼接完毕。五、模型的建立与求解
