2013高教杯数模竞赛B题四川大学22组答案.docx

2013高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。 我们参赛选择的题号是:B 我们的参赛报名号为：022 所属学校：四川大学 参赛队员：1. 2. 3. 指导教师或指导教师组负责人 ： 日期： 年 月 日 赛区评阅编号： 2013高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号： 赛区评阅记录： 评 阅 人 评 分 备 注 全国统一编号： 全国评阅编号： PAGE \* MERGEFORMAT 6 碎纸片的复原与拼接问题的建模求解 摘要 碎纸片的拼接复原问题可以建立计算机模型来进行求解，其中需要利用matlab编写程序。可以考虑由于图片的纹理是由灰度分布在空间位置上反复出现而形成的，因而在图像空间中相隔某距离的两象素之间会存在一定的灰度关系，即图像中灰度的空间相关特性。灰度共生矩阵就是一种通过研究灰度的空间相关特性来描述纹理的常用方法。 [1]所以可以通过matlab产生灰度矩阵进行图片四周边缘灰度特征的量化，从而提取到可以比较的特征数据，对图像数据进行标准化处理（灰度二值），通过产生相关系数矩阵，在每一列中寻找最接近1且不低于阀值的数据，实现数据的匹配，即将相关系数认为是匹配度的指标，最后编制matlab图片自动拼接程序解决拼图问题。 第一问是对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），所以可以匹配的信息是图片的左右两边标准化后的灰度值向量（ai,bi）所产生的相关系数矩阵M19*19。先通过编制循环语句产生所有图片的灰度值矩阵并只提取每个矩阵的第一列和最后一列的灰度值向量（ai,bi）作为特征数据，然后利用matlab产生ai与bj的相关系数m（ai,bj)=cov(ai，bj)Dai*D(bj),D为向量的方差，cov为两向量间的协方差，易知|m（ai,bj)|=1,且可知m（ai,bj）越接近1 第二问对于碎纸机既纵切又横切的情形，求解这个问题可以借鉴第一问的思路，需要提取左右边和上下边缘的灰度值向量（ai,bj，ci, di)，利用第一问的方法通过左右边灰度值的匹配和字间距k0与最短像素距D(ai,bj)的判别进行图片行的左右拼接，得到所有的行图，之后通过所有行的上下灰度值向量（ei, fi），计算出相关系数n（ci,dj)，然后循环得出所有的行图，得到相关系数矩阵N11*11，得到与i相关的系数向量后，取得最大值Nj=max{n（ai,bj) 第三问只需要将图片正反两面提取的特征数据进行捆绑，可以通过第二问的法进行改进，并且添加筛选条件，即两图对应的反面也相关系数也很接近1时才认定配成功，拼接的结果见建模结果。 关键词：拼接复原 灰度二值向量 阀值 相关系数矩阵 循环语句 matlab 一、问题的重述 破碎文件的拼接具有现实的重要意义，传统上，拼接复原工作需由人工完成。准确率较高，但效率很低。尤其是在碎片数量巨大，人工拼接很难在短时间内完成任务，所以寻找计算机拼接技术的算法成为一个重要的课题。所求问题如下 （1）对于给定的来自同一页印刷文字文件进行破碎处理，但仅纵切，请建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。其中需要人工干预的地方注明需要的时间节点和方式。 （2）对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 （3） 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸