2013全国大学生数学建模竞赛B题优秀论文

承 诺 书

我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》(以下简称为“竞赛章程和参赛规则”,可从全国大学生数学建模竞赛网站下载). 我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题.

我们知道,抄袭别人的成果是违反竞赛章程和参赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.

我们郑重承诺,严格遵守竞赛章程和参赛规则,以保证竞赛的公正、公平性.如有违反竞赛章程和参赛规则的行为,我们将受到严肃处理.

我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公开展示(包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等).

我们参赛选择的题号是(从A/B/C/D中选择一项填写): B 我们的参赛报名号为(如果赛区设置报名号的话 所属学校(请填写完整的全名): 中原工学院 参赛队员 (打印并签名) :1. 王新栋 指导教师或指导教师组负责人 (打印并签名): 建模指导组

(论文纸质版与电子版中的以上信息必须一致,只是电子版中无需签名.以上内容请仔

细核对,提交后将不再允许做任何修改.如填写错误,论文可能被取消评奖资格.)

日期: 2013 年 9 月 16日 赛区评阅编号(由赛区组委会评阅前进行编号):

编 号 专 用 页

赛区评阅编号(由赛区组委会评阅前进行编号):

全国统一编号(由赛区组委会送交全国前编号):

全国评阅编号(由全国组委会评阅前进行编号):

碎纸片的拼接复原

摘要

碎纸自动拼接技术是图像处理与模式识别领域中的一个较新但很典型的应用,它是通过扫描和图像提取技术获取一组碎纸片的特征信息,然后利用计算机进行相应的处理从而实现对这些碎纸品的全自动或半自动拼接还原.

本文首先运用MATLAB对图片做图像预处理,调用函数imshow使图片转化成矩阵形式并获取其数字矩阵形式的特征信息,通过分析数字信息(图片灰度),了解到只有图片边缘生成的数据信息可以更为方便的进行处理,通过计算不同两张图片边缘相似度,引入公式差异度量:

s xij yik

i 1

n

其值越小,相似度越大,便越是匹配,进而选择拼接.主要运用Matlab软件进行编程建立计算机图片自动拼接模型来解决此类问题.

对于问题一,采用计算机图片自动拼接模型(主要是MATLAB编程)来对边缘处理拼接,且只考虑边缘灰度,分析差异度量.对图片进行先右匹配到右边缘,再左匹配到左边缘,然后输出图像并观察以便进一步考虑是否需要人工干涉.

对于问题二,则在问题一的基础上使用灰度图像二值化模型进行数据处理,然后用计算机图片自动拼接模型对边缘处理拼接使得209块图片左右匹配到最大可能,拼得图片若干,再对拼成的若干图片进行人工干涉处理,最终得到复原图片.

对于问题三,引入正反两面差异度量

,,

s2 xij yik xic yid

则在问题二的基础上正反面同时进行边缘灰度分析,保证信息量的充分性,接下来具体处理方法同问题二.

关键词:MATLAB 图像预处理 计算机图片自动拼接模型 灰度图像二值化模型 相似度 差异度量

一、问题的重述

破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统上,拼接复原工作需由人工完成,但效率偏低,随着计算机的快速发展,运用计算机进行自动拼接碎纸片,既能提高拼接复原效率.又可以节省人力物力,讨论以下问题:

1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片拼接复原模型和算法,并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原.如果复原过程需要人工干预,请写出干预方式及干预的时间节点.复原结果以图片形式及表格形式表达.

2. 对于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法,并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原.如果复原过程需要人工干预,请写出干预方式及干预的时间节点.复原结果表达要求同上.

3. 上述所给碎片数据均为单面打印文件,从现实情形出发,还可能有双面打印文件的碎纸片拼接复原问题需要解决.附件5给出的是一页英文印刷文字双面打印文件的碎片数据.请尝试设计相应的碎纸片拼接复原模型与算法,并就附件5的碎片数据给出拼接复原结果,结果表达要求同上.

二、问题分析

据题目分析,碎纸片人工拼接劳功劳时,利用计算机可以高效率的实现碎纸片的自动拼接,对于已知的碎片如何可以在计算机中可操作,在此处利用MATLAB进行图像预处理,使得图片信息数据化,如此所得到的矩阵数据类型取值只为0到255,因不便于计算,进而建立函数模型求解.

1、针对问题一,对于附件1、2分析了解到碎纸片形状都是规则的矩形,因此对碎片只进行边缘纹理的相似度分析即可,进而根据相似度实现自动拼接.

2、针对问题二,对于附件3、4观察,碎纸片是由纵切横切双重作用所得,因而采用问题一的操作流程先把碎纸片还原成横条形式,然后人工干涉,把剩余的利用问题一的思想拼接在一起.

3、针对问题三,具体可知,碎片正反两面均有文字,且采用纵切横切双重作用,故正反两面均作考虑,若两片图片正面已经匹配拼接,则反面必然也能完美拼接.这样对于正反两面差异度量s2误差更小,所以采用正反两面差异度量可以使得匹配变得更加精确.

综合分析可知问题一二三在用计算机拼接过程中可能出现不能正常运行或出错情况,此时可以采用人工干涉,然后再进行图片匹配拼接.

三、模型的假设

1、假设需要人工干涉时,人工能正确解决图片拼接问题 2、假设相似度函数能够反映两碎片间的拟合程度 3、假设还原图边缘都有空白 4、假设切割没有边界损坏

四、符号说明

s:两图片相接边缘灰度的差异度量

s2:两图片正反两面相接边缘灰度的差异度量xij:一张图片数据化后矩阵的第i行第j列的元素yik:另一张图片数据化后矩阵的第i行第k列的元素

五、模型的建立与求解

图像碎片的匹配拼接是以实物碎片为参考依据进行的,建立描述实物的计算机图片自动拼接模型是图像碎片匹配拼接的关键技术之一,因此首先需要对实物碎片进行数字化处理,获得图像碎片的矩阵信息,先用MATLAB处理图片,调用函数imshow使图片转化矩阵形式(见附录7).

1. 问题一的模型建立与求解

根据题意,碎纸片数据化后,碎纸片的左右边缘即为矩阵的一列元素,建立计算机图片自动拼接模型.模型求解过程引入差异度量

s xi yi,

i 1

n

将所选图片与其他图片一一对s进行计算,取使其s最小的图片进行标记拼接. 求解过程:具体求解需考究两种情况,载入所有图片,运用MATLAB进行数据化处理,调用一张图片并进行标记,再对其数字矩阵最后一列元素进行分析判断边缘是否有空白:(边缘空白是指该图片矩阵某边缘灰度值为

255)

(1)若判断边缘为空白,则进行横向向左依次匹配、标记、拼接.

(2)若边缘非空白,则向右依次进行匹配、标记、拼接直至完成图片右向拼接,返回分析所选图片最左列的数据信息,向左依次匹配分析、标记、拼接. 计算机图片自动拼接模型具体流程简化图如下:

该模型就是通过MATLAB软件编程来实现图片的自动拼接复原.具体程序见附录1,运行此程序求得该模型解为:

中文图片(仅纵切)拼接复原的最终结果(表格形式)为:

英文图片(仅纵切)拼接复原的最终结果(表格形式)为:

中英文拼接复原的图片形式见附录2. 2. 问题二的模型建立求解

根据问题分析可得,碎纸片是由横切,纵切双重作用产生,首先在问题一所建立模型的基础上加用灰度图像二值化模型来进行求解.此模型主要是将图片数字信息中的灰度值介于0到255之间的数值转换成0或255.经MATLAB软件多次运行得知,此种模型使得后续人工干涉的介入率大大降低,而且将其数值转换成0要远比转换成255的图片匹配相似度更好,更优的降低了人工干涉的介入率.因此在此模型中将其灰度数值转换成0.

以下为此模型求解过程:

虚拟模拟拼接过程 模拟碎纸片(3×4)

要求:按顺序拼接

首先进行横向拼接如所选图片是

依次循环得到如下横条图片:

如若横向拼接中出现差错或所有横向拼接均已完成,则可进行人工干涉,然后将正确的横条图片进行纵向拼接结果如下图

模型的求解过程(程序代码)具体见附录3

当MATLAB程序代码运行所得拼接图像时,需要进行人工干涉,干涉方式主要有:若出现断边情况(即图片拼接虽然终止但非边界),则进行人工拼接直到正常边界终止;若没出现,则不需要人工拼接.然后将这些已正常终止的横条按问题一模型类似的进行矩阵上下匹配最终得到结果为:

中文图片(即纵切又横切)拼接复原的最终结果(表格形式)为:

英文文图片(即纵切又横切)拼接复原的最终结果(表格形式)为:

中英文拼接复原的图片形式见附录4. 3、问题三模型建立及求解过程

针对问题三的情况,碎片中不光出现纵切,横切,而且要考虑纸片的正反面数据.对于问题三,在问题二的模型基础上引入正反两面差异度量:

,,

s2 xij yik xic yid

很显然,若两片图片正面已经匹配拼接,则反面必然也能完美拼接.这样对于正反两面差异度量s2误差更小,所能体现的相似度更高,所以采用正反两面差异度量可以使

得匹配变得更加精确.简要流程图如下:

针对此模型,运用MATLAB编程求解得:(程序见附录5) 英文图片(即横切又纵切外加正反面)拼接复原结果(表格形式):

反面

英文图片(即横切又纵切外加正反面)拼接复原图见附录6.

六、模型的评价

碎纸自动拼接是计算机视觉和模式识别的一个基本问题,图像预处理和碎片匹配是其中的关键技术.本文主要研究了碎纸自动拼接中的图像预处理技术和灰度图像二值法,来解决碎纸片拼接与复原.

1、本文第一问利用了灰度分析法、碎片预处理,然后利用MATLAB软件编程,能够得到完整的碎纸片复原图,且不需要人工干涉,方法易懂.

2、第二问和第三问采用了问题一的方法,并使此方法得到了一定的升华,虽然需要一定的人工干涉,但结果还是令人满意的.对于更完善的方法,我们需要进行近一步研究.

3、我们运用MATLAB软件进行编程,从编程中我们构思了一系列的模型,使整篇文章更加充实,更加有新意.

七、模型的讨论

通过建立模型进行匹配拼接碎纸片的研究,以及讨论模型的优缺点,显然很好的实现了自动拼接,尽管需要必要时候的人工干涉,依然很好的验证的模型的可靠性和实用性,充分表明了所进行的碎纸片拼接复原技术研究的必要性.然而对于日常生活所出现的拼接复原现象,比如文物碎片,重要秘密文件的碎片,规则的矩形碎片基本上不会出现,碎片的形状一般是不规则的,并且颜色也是多种多样的,因此建立更完善的数学模行求解才会真正地应用到现实中的碎片拼接复原工作中.

现实中碎片形式如图

数学模型的建立需考究碎片的形状,颜色,纹理等综合信息,可以通过聚类分析形状,颜色,纹理等的综合影响,建立更为优化的相似度函数,对其相似匹配,进行拼接复原.然而,仅依靠计算机的全自动拼接完成碎片复原仍然难以实现,必须结合着类似于人工拼图游戏似的手工复原方法,才能将碎片拼接复原.为更智能的自动拼接复原进行如下优化讨论:

1、对于数学模型中的算法的优化

虽然文中所用算法在实验中取得了比较好的效果,但还需挖掘潜力,基于计算机视觉、图形学,并且结合了传统的仿真软件,达到高效和有效,进行进一步优化设计方案.因此,如何减少匹配的数量,提高效率,增加适应性,还是需要深入研究的.

2、对于软件程序的优化

虽然在本题编程中,系统可以满足要求,但是在实际应用中,通常会涉及对大量纸片数据进行管理和处理工作.目前,我们主要还是以实现功能为主,下一步必须优化程序结

构,改善用户界面,提高程序的交互能力.真正实现快速有效的计算机辅助碎纸片自动拼接复原系统.

3、数据库的进一步开发

在实际应用中,由于设备等条件的限制,一次处理往往不能完全完成匹配拼接的任务,因此必须开发更高效的数据库,以便充分利用每次拼接所得的过程图片.

八、 模型的应用与推广

碎纸片自动拼接技术是图像处理与模式识别领域中的一个较新但是很典型的应用,它是利用计算机进行处理从而实现对碎纸片的全自动或半自动拼接复原.此技术还可以在司法物证复原、历史文献、文物修复以及军事情报获取等领域都有着重要的应用.

九、 参考文献

[1]陈超,MATLAB应用实例精讲,北京:电子工业出版社,2011.

[2]张汗灵,MATLAB在图像处理中的应用,北京:清华大学出版社. [3]姜启源,数学模型(第三版),北京:高等教育出版社,2003.

[4]韩中庚,数学建模方法及其应用(第二版),北京:高等教育出版社. [5]郑忠俊 谢红兵,计算机辅助几何设计,上海:上海交通大学出版社.

附录

运用软件名称:MATLAB.

注意:每次调用MATLAB时首先在子菜单Current Folder下打开需解答题目所对应的附件文件夹.

附录1:

G.all=dir(fullfile('.\','*.bmp')); %读入所有该文件夹下的bmp图片 tem=size(G.all); G.size=tem(1); %图片总数

worked_num=0; %记录已处理数量

for i=1:G.size %标记对象i是否处理过 is_worked(i)=0; end

while worked_num<G.size for j=1:G.size %取未被处理过的一个对象作为左值(left) if is_worked(j)==0 %若未被处理过,标记,开始处理 is_worked(j)=1; worked_num=worked_num+1; left.mat=imread(G.all(j).name); %对象一的矩阵表示 break; end end while 1 tem=size(left.mat); left.height=tem(1); %对象一的行数(高) left.width=tem(2); %对象一的列数(宽) is_blank=1; %判断是否到达“边缘” for j=1:left.height if left.mat(j,left.width)~=255 is_blank=0; break; end end if is_blank==1 %若到达边缘,右匹配停止 break;

for j=1:G.size %选取右对象(right sum_difference(j)=0; %记录left与right图的差值 if is_worked(j)==1; %若right已被处理过,将差值置为无穷大 sum_difference(j)=inf; else %若right未被处理过 right.mat=imread(G.all(j).name); %记录right的矩阵信息 tem=size(right.mat); right.height=tem(1); right.width=tem(2); for t=1:right.height if left.mat(t,left.width)>right.mat(t,1) tem_dif=uint32(left.mat(t,left.width)-right.mat(t,1)); else tem_dif=uint32(right.mat(t,1)-left.mat(t,left.width)); end sum_difference(j)=sum_difference(j)+tem_dif; end end end %该循环用于记录left与其他所有right的差值 min_num=1; %最小值的编号 min_difference=inf; %最小差值 for j=1:G.size if sum_difference(j)<min_difference min_difference=sum_difference(j); min_num=j; end end left.mat=cat(2,left.mat,imread(G.all(min_num).name)); is_worked(min_num)=1; worked_num=worked_num+1; end

%以上右匹配1.0实现完成

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

right.mat=left.mat;

while 1

right.height=tem(1); %对象一的行数(高) right.width=tem(2); %对象一的列数(宽)

is_blank=1; %判断是否到达“边缘” for j=1:right.height if right.mat(j,1)~=255 is_blank=0; break; end end

if is_blank==1 %若到达边缘,右匹配停止 break; end

for j=1:G.size %选取右对象(right sum_difference(j)=0; %记录left与right图的差值 if is_worked(j)==1; %若right已被处理过,将差值置为无穷大 sum_difference(j)=inf; else %若right未被处理过 left.mat=imread(G.all(j).name); %记录right的矩阵信息 tem=size(left.mat); left.height=tem(1); left.width=tem(2); for t=1:right.height if left.mat(t,left.width)>right.mat(t,1) tem_dif=uint32(left.mat(t,left.width)-right.mat(t,1)); else tem_dif=uint32(right.mat(t,1)-left.mat(t,left.width)); end sum_difference(j)=sum_difference(j)+tem_dif; end end end

%该循环用于记录left与其他所有right的差值

min_num=1; %最小值的编号 min_difference=inf; %最小差值 for j=1:G.size if sum_difference(j)<min_difference min_difference=sum_difference(j); min_num=j; end end

本文来源：https://www.bwwdw.com/article/suai.html