《九江学院b钟玥铧简欣官桃红》由会员分享,可在线阅读,更多相关《九江学院b钟玥铧简欣官桃红(44页珍藏版)》请在金锄头文库上搜索。
1、2013高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则(以下简称为“竞赛章程和参赛规则”,可从全国大学生数学建模竞赛网站下载)。我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。我们知道,抄袭别人的成果是违反竞赛章程和参赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺,严格遵守竞赛章程和参赛规则,以保证竞赛的公正、公平性。如有违反竞赛章程和参赛
2、规则的行为,我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公开展示(包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等)。我们参赛选择的题号是(从A/B/C/D中选择一项填写): B 我们的参赛报名号为(如果赛区设置报名号的话): 所属学校(请填写完整的全名): 九江学院 参赛队员 (打印并签名) :1. 钟玥铧 2. 简欣 3. 官桃红 指导教师或指导教师组负责人 (打印并签名): 教练组 (论文纸质版与电子版中的以上信息必须一致,只是电子版中无需签名。以上内容请仔细核对,提交后将不再允许做任何修改。如填写错误,论文可能被取消评奖资格。)
3、日期: 2013 年 09 月 15 日赛区评阅编号(由赛区组委会评阅前进行编号):2013高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号(由赛区组委会评阅前进行编号):赛区评阅记录(可供赛区评阅时使用):评阅人评分备注全国统一编号(由赛区组委会送交全国前编号):全国评阅编号(由全国组委会评阅前进行编号):题目:B参赛队员:钟玥铧 简欣 官桃红 指导教师:教练组 单位: 九江学院碎纸片的拼接复原摘要本文主要运用了Matlab中的imread和imshow命令对碎片进行处理,可以得到一个关于各碎片的灰度值的矩阵,通过提取各矩阵的边缘列和行,利用最小二乘法和相关系数得到了各个问题的数
4、学模型,并用程序把附件中的碎片进行了复原。对问题一,利用每张碎片边缘灰度值的向量列,建立了最小二乘模型,利用向量与向量的二范数最小实现了对碎片的排序。具体做法如下:按每张碎纸片的边缘列灰度值的不同,找出原图型的第一张,将其固定,将每一张碎纸片左右两边的像素点的灰度值分别标号为依次增加的奇数和偶数。然后,将第一张的偶数号和剩余的奇数号的灰度值用范数进行比较,找出原图形的第二张碎纸片。将第一张与第二张碎纸片固定,用上述同样的方法,找出余下的所有碎纸片在原图形的位置。对问题二,利用每张碎片边缘灰度值的向量列和灰度值向量行,建立了最小二乘数学模型,实现了各个碎片的排序。首先利于问题一的方法,分别找出四
5、周边缘的碎纸片并排序,将其固定。然后,依次找出第二行,第二列的碎纸片区域。这里,我们既考虑了行向量与行向量范数也考虑了列向量与列向量范数,利用范数最小确定了碎片的排序。这样提高了碎纸片拼接复原的准确率,进而提高效率,我们也给出了人工干预的时间节点和方法。对问题三,利用每张碎片边缘灰度值向量列和灰度向量行,利用相关系数最大建立了拼接的数学模型,并编程实现了附件五的拼接。【关键词】 像素灰度值 最小二乘原理 相关系数 MATLAB建模1问题重述 随着计算机技术的发展,碎纸片的自动拼接复原技术是图像处理一个较为典型的应用。特别是在司法物证复原、历史文献修复以及军事情报获取等领域起着重要的作用。碎纸片
6、的自动拼接复原技术大大提高了拼接复原效率,在拼接的过程中,我们要解决的问题有:问题一:对于给定的仅纵切的且来自同一页印刷文字文件的碎纸片,如何建立碎纸片拼接复原模型和算法,并且对附件1,附件2中给出的中、英文各一页文件的碎片数据进行拼接复原。问题二:在碎纸片纵切又横切的情形下,设计设计碎纸片拼接复原模型和算法,并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。问题三:在双面打印文件的 情况下,如附件5给出的是一页英文印刷文字双面打印文件的碎片数据,设计相应的碎纸片拼接复原模型与算法。(注:如果复原过程中需要人工干预,写出干预方式及干预的时间节点且复原结果以图片形式及表格形式表
7、达。针对附件1、附件2、附件3、附件4、附件5,所得图形和表格均在附录中。)2模型的假设与符号的约定2.1模型的假设与说明(1)在切割规格正常的情况下,排除误差,假设每个碎纸片都是规则的;(2)每个给定规格和切割方式(仅纵切,仅横切,纵切又横切)的碎纸片的整体是完整的,无残缺;(3)假设每个给定的碎片文件的文字不存在变异(文字自身不存在畸形);(4)碎纸片文件在拼接复原过程中,两纸片区域之间无重叠,无缝隙。2.2符号的约定与说明符号含义表示第张碎纸片,表示碎纸片左右两端的灰度值向量,也表示它所在的碎片的边表示向量的二范数表示一个矩阵在问题三中,表示碎片i的第j列,也表示碎片i的第j边j=1,表
8、示最左(列)边,j=end表示最右(列)边在问题三中,表示碎片i的第j行,也表示碎片i的第j边j=1,表示最上面的(列)边,j=end表示最下面的(列)边3问题的分析3.1问题一的分析针对问题一,我们需要解决的问题是对给定的来自同一页印刷文字文件的规则碎纸片(仅纵切)附件1和附件2建立一个使其拼接复原的模型和算法。由于该碎纸片是规则的,所以我们运用聚类分割方法,利用相邻两图像之间的像素灰度值的范数最小,来实现碎纸片的拼接复原。先将每个图像的像素灰度值置于矩阵中,此外,我们可由每页纸张的最左端部分为空白,从而可知其的像素灰度值均为255(在unit8类型下),即此时的向量,从而可以确定这张碎纸片
9、位于纸张的最左端。由于这张纸片的第一张的上端也为空白,所以其灰度值亦为255,从而我们可以找出第一张碎纸片。然后利用灰度值,运用范数最小值计算,找出这张碎纸片的位置。将的位置固定后,再将依次与剩下的进行范数比较,找出最小的即为其相邻的纸片。依次类推,依据循环语句将纸片进行拼接复原。3.2问题二的分析针对问题二,我们需要解决的问题是对给定的来自同一页印刷文字文件的规则碎纸片(横切且纵切)附件3和附件4建立碎纸片拼接复原和算法。运用的方法如同问题一中的聚类分割方法。首先,将每个图像的灰度值置于一个矩阵中,由于左上端第一张碎纸片最左端和最上端的部分空白,从而可知其灰度值为255,我们可以先找出左上端
10、的第一张碎纸片。利用问题一中同样的方法,找出所有这一行和这一列的碎纸片(即和),将它们按原图形固定。此时,算出所有已固定碎纸片最右端和的最下端的灰度值,计算剩余没有固定的碎纸片的灰度值,用范数最小值进行匹配。此时需要注意的是剩余的碎纸片拼接复原需要进行两个量的比较(即它的左端和上端需要和已固定右端和下端的灰度值进行匹配)。依次类推,可找出所有碎纸片的位置,从而完成碎纸片的拼接复原。3.3问题三的分析针对问题三,我们需要解决的问题是对给定的来自同一页印刷双面文字文件的规则碎纸片(横切且纵切)附件5建立碎纸片拼接复原和算法。每个图像的灰度值对应一个矩阵。运用相关系数,任取一边,找出相关系数最大的另
11、一边与其拼接。依次类推,可把整张图片复原完成。运用相关系数的过程中,不需考虑正反面问题。4模型的建立与求解4.1问题一的求解概念:灰度值灰度也可以认为是亮度,简单说就是色彩的深浅程度。范数实轴上任意两点距离用两点差的绝对值相关系数,用来刻画之间线性相关的密切程度。模型的建立与求解: 1 数据的处理将每个图像的灰度值依次置于矩阵中,且为一个1980行72列的矩阵,即, 又由于相邻两像素点之间的距离最近,相似度最高,分别提取矩阵中的第一列和最后一列,记为,即和,并将其转换成double类型即,在将其置于一个新的矩阵中,即2 建立拼接模型(1)确定文件的最左端碎片:根据图像最边缘点为空白的特点,利用
12、与之间的关系来判断。若,则该图像位于最左端。(2)拼接复原纸片:确定好最左边纸片后,按下面的方法进行拼接:Step1 令,对,对任意的,求,使 ,拼接与,Step2 令,T=T1, 转step1程序见附录的程序1.附件1的复原结果列成表格如下:表一12345678910111213141516171819008014012015003010002016001004005009013018011007017000006附件1的复原的图片见附录1附件2的复原结果列成表格如下:表二123456789101112131415161718190030060020070150180110000050010
13、09013010008012014017016004附件2的复原的图片见附录2注:第一问由于数据较大,特征明显,以上的程序效果好,不需要人工干预。4.2问题二的求解1 取每个碎纸片的最左端、最右端、最上端及最下端的灰度值在Matlab中运用imread命令得到图片灰度值矩阵,用表示。每个碎纸片的最左端、最右端的灰度值,即取出每个碎纸片所对应的灰度值矩阵的第一列和最后一列。在Matlab中可用如下程序取出:当中为奇数时表示的向量为矩阵的第一列,即为碎纸片的最左端,同理为偶数时表示碎纸片的最右端。同理,所有碎纸片的最上端及最下端的灰度值,即取出每个碎纸片所对应的灰度值矩阵的第一行和最后一行。即为:当中为奇数时表示的向量为矩阵的第一行,即为碎纸片的最上端,同理为偶数时表示碎纸片的最下端。 2 建立拼接模型(1) 确定文件的最左端碎片:根据图像最边缘点为空白的特点,利用与之间的关系来判断。若,则该图像位于最左端。(2) 确定文件的最右端碎片:若,则该图像位于最左端。(3) 确定文件的最上端碎片:若,则该图像位于最上端。(4) 确定文件的最下端碎片:若,则该图像位于最下端。(5