2013-全国数学建模竞赛b题优秀论文.pdfVIP

基于最小二乘法的碎纸片拼接复原数学模型 摘要 首先对图片进行灰度化处理,然后转化为 0-1 二值矩阵，利用矩阵行（列） 偏差函数，建立了基于最小二乘法的碎纸片拼接数学模型，并利用模型对图 片进行拼接复原。 针对问题一，当两个数字矩阵列向量的偏差函数最小时，对应两张图片 可以左右拼接。经计算，得到附件 1 的拼接结果为： 08,14,12,15,03,10,02,16,01,04,05,09,13,18,11,07,17,00,06。 附件 2 的拼接结果为: 03,06,02,07,15,18,11,00,05,01,09,13,10,08,12,14,17,16,04。 针对问题二，首先根据每张纸片内容的不同特性，对图片进行聚类分析， 将 209 张图片分为 11 类；对于每一类图片，按照问题一的模型与算法，即列 偏差函数最小则进行左右拼接,对于没有拼接到组合里的碎纸片进行人工干 预，我们得到了 11 组碎纸片拼接而成的图片；对于拼接好的 11 张图片，按照 问题一的模型与算法，即行偏差函数最小则进行上下拼接,对于没有拼接到 组合里的碎纸片进行人工干预。我们最终经计算，附件 3 的拼接结果见表 9， 1 附件 4 的拼接结果见表 10。 针对问题三，由于图片区分正反两面，在问题二的基础上，增加图片从 下到上的裁截距信息，然后进行两次聚类，从而将所有图片进行分类，利用 计算机自动拼接与人工干预相结合，对所有图片进行拼接复原。经计算，附 件 5 的拼接结果见表 14 和表 15 模型的优点是将图片分为具体的几类，大大的减少了工作量，缺点是 针对英文文章的误差比较大。 关键字 ：灰度处理，图像二值化，最小二乘法，聚类分析，碎纸片拼接 一、问题重述 碎纸片的拼接复原技术在司法鉴定、历史文献修复与研究、军事情 2 报获取以及故障分析等领域都有着广泛的应用。近年来，随着德国“斯塔西” 文件的恢复工程的公布，碎纸文件复原技术的研究引起了人们的广泛关注。 传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当 碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展， 人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。对于一页印刷 文档，针对不同的破碎方法，讨论下列三个问题： （1）将给定的一页印刷文字文件纵切，建立碎纸片拼接复原模型和算法， 并针对附件 1、附件 2 给出的中、英文各一页文件的碎片数据进行拼接复原。 （2）对于碎纸机既纵切又横切的情形，设计碎纸片拼接复原模型和算法， 并针对附件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。 （3）对于双面打印文档，研究如何进行碎纸片的拼接复原问题。附件 5 给出的是一页英文印刷文字双面打印文件的碎片数据。要求尝试设计相应 的碎纸片拼接复原模型与算法，并就附件 5 的碎片数据给出拼接复原结果。 二、模型的基本假设 （1） 待拼接的碎纸片来自同一页印刷文字文件。 （2） 待拼接复原的碎纸片是规整的矩形。 3 （3） 模型中的碎纸片长度、宽度和面积都相等。 （4） 附件中照片都是同标准拍摄。 三、符号说明 表 1 符号说明 符号 符号说明 Gray 灰度值 r 红色 g 绿色 b 蓝色 A, B 矩阵 D i 裁截距 (i= 1,2, , 209) ai 裁截文字长度