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

PAGE \* MERGEFORMAT 1 2013高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 重庆邮电大学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2013 年 9 月 13 日 赛区评阅编号（由赛区组委会评阅前进行编号）： 2013高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： PAGE \* MERGEFORMAT 1 碎纸片的拼接复原 摘要 本文研究的是碎纸片的拼接复原问题。由于人工做残片复原虽然准确度高，但有着效率低的缺点，仅由计算机处理复原，会由于各类条件的限制造成误差与错误，所以为了解决题目中给定的碎纸片复原问题，我们采用人机结合的方法建立碎纸片的计算机复原模型解决残片复原问题， 并把计算机通过算法复原的结果优劣情况作为评价复原模型好坏的标准，通过人工后期的处理得到最佳结果。 面对题目中给出的BMP格式的黑白文字图片，我们使用matlab软件的图像处理功能把图像转化为矩阵形式，矩阵中的元素表示图中该位置像素的灰度值，再对元素进行二值化处理得到新的矩阵。题目每一个附件中的碎纸片均为来自同一页的文件，所以不需考虑残片中含有未知纸张的残片以及残片中不会含有公共部分。鉴于残片形状分为“长条形”与“小长方形”，残片内容分为中文、英文，纸张的打印类型分为“单面型”、“双面型”，所以我们根据残片的类型对矩阵做不同处理。 针对问题一中给出的“长条形”碎纸片：对图片转化后的矩阵进行边缘检测，发现每一张图片的两短边在一定范围内全是白色，而仅有2张图片的长边在一定范围内全是白色，说明我们需要对长边进行拼接，一边包含全白的长边是原文件纸张的两端。由于考虑到模型应用的推广，我们在此问中的模型包含了图片倒置的情况（仅在问题一中考虑倒置情况，鉴于问题二、三中数据量的增多，二三问不再考虑倒置情况），对图片的长边及矩阵中的第一列和最后一列与其他矩阵的第一列和最后一列进行边缘匹配，根据边缘匹配度来确定图片复原，最后若发现拼接效果有偏差，在进行人工操作。 针对问题二中的“小长方形”碎纸片：由于数据量变多，盲目使用问题一中的方法不能保证准确度，所以这里要进一步约束使当前图片与少量图片进行匹配。观察两种文字的特点，我们可以发现中英文在位置上均有一定的特性，我们利用这种特性将有相同位置特性的碎纸片归类为一组，在问题一方法的基础上做少许修改后代入有相同位置特性的一组碎纸片中，根据边缘匹配度将他们连接、检查并做人工处理可得拼接后的横行纸片，再将横行纸片的长边用同样的方法做边缘匹配可将行与行之间拼接起来，再做人工调整得到最优结果。通过模型的建立求解过程可以发现中英文在本问题的求解方法中有着一定的不同，英文需要更多地人工判断处理。 针对问题三考虑到双面问题以及问题二中英文碎纸片的情况，我们把碎纸片两面匹配度之和作为判断碎纸片是否连接的评价标准，在问题一方法的基础上，在计算机每一步的匹配结果加以人工