2014全国大学生数学建模大赛

《2014全国大学生数学建模大赛》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、碎纸片的拼接复原摘要本文讨论了三种情况下的碎纸片复原问题。通过聚类分析、灰度匹配、人工干预的方法，借助MATLAB软件，建立三个数学模型，分别给出了三个问题的解决方案。针对问题一的情形，我们建立了边缘识别模型。首先，将图像像素映射成灰度矩阵，然后利用灰度矩阵边缘特征的相关匹配原理，用MATLAB软件提取每个矩阵的左右边缘信息，并对二值化的图像进行相似匹配。最后，利用迭代数列函数找出所求碎片的排列顺序，对附件1及附件2给出的碎片各拼接成一张完整图片。针对问题二的情形，建立了基于文字特征的模式识别模型。通过研究碎纸片内文字行特征，提出了基于碎片文字行特征的碎片拼接算法。如果碎片内的文

2、字行在碎片边缘断裂，那么与它相邻的碎纸片在边缘处一定有相同高度、相同间距的文字行或表格，因而可以很容易地从形状相似的多碎片中挑选出相邻碎片。其方案是先运用MATLAB软件对209个碎片进行聚类分析，共分成11类，然后利用问题一的方法对每一类的碎片进行拼接，最后对附件3及附件4给出的碎片各拼接成一张完整图片。针对问题三的情形，建立基于文字特征的双模式匹配模型。首先基于问题二，根据碎纸片内英文文字的行特征，进行两次边缘识别检索，分别检索出a面和b面，然后通过人工干预进行匹配，最终得出正反面碎纸片的排列顺序。为了检验所建立的模型对碎片拼接复原的效果，对模型进行了灵活性检验和误差分析，做

3、出了优缺点评价以及可行性建议。关键词：碎纸片拼接模式识别边缘匹配聚类分析一、问题重述11破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时

4、间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。2.对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3.上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。【数据文件说明】(1)每一附件为同一页纸的碎片数

5、据。(2)附件1、附件2为纵切碎片数据，每页纸被切为19条碎片。(3)附件3、附件4为纵横切碎片数据，每页纸被切为11×19个碎片。(4)附件5为纵横切碎片数据，每页纸被切为11×19个碎片，每个碎片有正反两面。该附件中每一碎片对应两个文件，共有2×11×19个文件，例如，第一个碎片的两面分别对应文件000a、000b。【结果表达格式说明】(5)复原图片放入附录中，表格表达格式如下：(6)附件1、附件2的结果：将碎片序号按复原后顺序填入1×19的表格；(7)附件3、附件4的结果：将碎片序号按复原后顺序填入11×19的表格；(8)附件5的结果：将碎片序号按复原后顺序填入两个11×1

6、9的表格；(9)不能确定复原位置的碎片，可不填入上述表格，单独列表。二、模型假设与符号说明2.1模型假设结合本题实际，为了保证模型求解的准确性和合理性，我们排除了未知因素的干扰，提出了以下三点假设：[1]碎纸机破碎纸片时对印刷文字无磨损；[2]假设纸张为完整的一张纸，且页边距部位零[3]人工干预不对所建立的模型或函数造成误差，也不会对碎纸片数据造成影响；[4]印刷文字规格均相同，不存在文件中出现不同种类文字的现象；2.2符合说明11A一维数组B一维数组数组B中的第J个元素第i块碎纸片的灰度矩阵第i块碎纸片灰度矩阵的首末两列对二值化处理后的矩阵最首列的末列K值三、问题分析与模型建立

7、3.1针对问题一建模3.1.1问题一分析当碎片数量巨大，人工拼接很难在短时间内完成任务，我们考虑利用计算机实现碎纸片的自动拼接或识别，将碎纸片数字化。通过MATLAB软件编程[1]可以很好地实现这样的转化。利用MATLAB将图像转换成灰度矩阵，再对灰度矩阵进行二值化的数据处理，这就是实现碎纸片利用计算机处理而得到拼接复原的基本思想，之后根据具体问题做出相应处理。3.1.2建立模型I第一步：将附件一中的图片利用MATLAB进行图像想数字的转化，将图片批量导入之后再分析附件一中的图片