haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

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

发布时间:2013-09-18 16:30:46  

2013高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》(以下简称为“竞赛章程和参赛规则”,可从全国大学生数学建模竞赛网站下载)。

我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题。 我们知道,抄袭别人的成果是违反竞赛章程和参赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

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

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

我们参赛选择的题号是:B

我们的参赛报名号为:所属学校:四川大学

参赛队员:1.

2.

3.

指导教师或指导教师组负责人 :

日期: 年 月 日

赛区评阅编号:

2013高教社杯全国大学生数学建模竞赛

编 号 专 用 页

赛区评阅编号:

全国统一编号:

全国评阅编号:

碎纸片的复原与拼接问题的建模求解

摘要

碎纸片的拼接复原问题可以建立计算机模型来进行求解,其中需要利用matlab编写程序。可以考虑由于图片的纹理是由灰度分布在空间位置上反复出现而形成的,因而在图像空间中相隔某距离的两象素之间会存在一定的灰度关系,即图像中灰度的空间相关特性。灰度共生矩阵就是一种通过研究灰度的空间相关特性来描述纹理的常用方法。 [1]所以可以通过matlab产生灰度矩阵进行图片四周边缘灰度特征的量化,从而提取到可以比较的特征数据,对图像数据进行标准化处理(灰度二值),通过产生相关系数矩阵,在每一列中寻找最接近1且不低于阀值的数据,实现数据的匹配,即将相关系数认为是匹配度的指标,最后编制matlab图片自动拼接程序解决拼图问题。

第一问是对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),所以可以匹配的信息是图片的左右两边标准化后的灰度值向量(ai,bi)所产生的相关系数矩阵M19?19。先通过编制循环语句产生所有图片的灰度值矩阵并只提取每个矩阵的第一列和最后一列的灰度值向量(ai,bi)作为特征数据,然后利用matlab产生ai与bj的相关系数m(ai,bj)为向量的方差,cov为两向量间的协

方差,易知|m(ai,bj)|<=1,且可知m(ai,bj)越接近1,则线形相关度越大,ai与bi的数据接近程度越高,匹配的可能性越大。可以通过算法得到与i相关的系数向量后,取得最大值Mj=max{m(ai,bj)|j取除i以外的1~19},观察数据并设定阀值,判断Mj是否大于阀值,进而判断是否匹配成功,同理也可得到与j相关的系数矩阵Mi= max{m(ai,bj)|i取除j以外的1~19},最后利用matlab语句实现图片的最终拼接。

第二问对于碎纸机既纵切又横切的情形,求解这个问题可以借鉴第一问的思路,需要提取左右边和上下边缘的灰度值向量(ai,bj,ci, di),利用第一问的方法通过左右边灰度值的匹配和字间距k0与最短像素距D(ai,bj)的判别进行图片行的

左右拼接,得到所有的行图,之后通过所有行的上下灰度值向量(ei, fi),计算出相关系数n(ci,dj),然后循环得出所有的行图,得到相关系数矩阵N11?11,得到与i相关的系数向量后,取得最大值Nj=max{n(ai,bj)|j取除i以外的1~11},遇到多组满足阀值的数据时,通过行间距β或者人工干预,确定最佳行匹配,得到与j相关的系数向量后,判断Ni是否大于阀值,取得最大值Ni= max{n(ai,bj)|i取除j以外的1~11},处理方法同上,进而实现全图的拼接。

第三问只需要将图片正反两面提取的特征数据进行捆绑,可以通过第二问的法进行改进,并且添加筛选条件,即两图对应的反面也相关系数也很接近1时才认定配成功,拼接的结果见建模结果。

关键词:拼接复原 灰度二值向量 阀值 相关系数矩阵 循环语句 matlab

1

一、问题的重述

破碎文件的拼接具有现实的重要意义,传统上,拼接复原工作需由人工完成。准确率较高,但效率很低。尤其是在碎片数量巨大,人工拼接很难在短时间内完成任务,所以寻找计算机拼接技术的算法成为一个重要的课题。所求问题如下

(1)对于给定的来自同一页印刷文字文件进行破碎处理,但仅纵切,请建立碎纸片拼接复原模型和算法,并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。其中需要人工干预的地方注明需要的时间节点和方式。

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

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

二、背景与问题的分析

这个问题的背景是纸片在不同粉碎方式的条件下求拼图的解法,基于方式的不同,问题中给了两种方式纵切和纵横切,对象有两个内容只有单面的纸和双面的纸。

纵观全局,三个问题的处理方法上都必须通过数据的预处理,这里是将图形数据转化为其灰度值的数据矩阵,实现量化,再通过图像数据标准化,即产生黑白二值向量(标准处理后的灰度值),计算相关系数矩阵,提取相关的拼图特征,由于切纸方法只有纵横,所以形状特征不考虑,只考虑图片周围的灰度值即可。

第一问的求解可通过只提取图片灰度值矩阵的首尾列向量并且计算相关系数矩阵M19?19作为其特征,图片匹配的过程是特征数据匹配的过程,可以通过matlab编写循环语句进行匹配编号,最后实现全图的拼接。

第二问的求解和第一问类似,只不过还需要提取处理后的首尾上下边的灰度值向量并且计算相关系数矩阵N11?11作为特征数据,图片匹配的过程可以通过循环算法先进行每行的匹配,达到阀值的话,认为可能匹配,遇到可能匹配的向量组不止一对时(诸如切到白边状况),可以通过判断行间距和人工干预的方法实现正确匹配。

第三问的求解可以在第二问的基础上,利用第二问单面全图拼接的算法,进行特征数据的捆绑,一对数据(如图片A某面和B某面特征数据)的匹配同时需要满足相应的另一对数据(A的另一面和B的另一面的特征数据)的匹配程度。所以增加了筛选条件,同时减少了人工干预,提高了匹配准确度。

2

三、问题的假设

1,切碎纸片的过程相对温和,对于切开处两侧相对保真,对于灰度值的提取不会有很大影响

2,在碎纸图片的照片摄取时保持了原状,像素相对保真

3,应用软件matlab在提取灰度值时相对精确

4,图像拼接时,干预者有正常的图像辨别能力

5,附件中原图片碎片完整即无丢失

符号的说明

(ai,bi)?i图的左右两侧的灰度值向量组 (ci,di)…i图的上下两侧灰度值向量组 Cov…协方差

D()…方差

m(ai,bj)=cov(ai,bj)/ …两向量的相关系数

n(ci,dj)=cov(ci,dj)/ …两向量的相关系数

pi ?i图的特征数据向量

L?已经拼好的某行图片

(ek,fk)?L上下两侧的灰度值向量组

k0?字间距

D2(ai,bj)…i图左边与j图右边的最短像素距

z…第一问阀值

α...第二问阀值

五,建模与求解

数据预处理:

通过matlab程序进行图片灰度值矩阵的提取,然后通过图像数据标准化处理,即转化为黑白图的灰度二值,第一问的数据只需要提取(ai,bi),即i图片标准化的灰度值最左列和最右列,第二问的数据需要提取图片四边的标准灰度值矩阵最左右和上下灰度值向量(ai,bi,ci,di),同时还需要通过程序提取字符间距k0,拼接边的像素最短距D(ai,bj)以及行间距β,两问都可以通过excel进行相关系数

矩阵行和列最大值的提取,进而分析相关系数矩阵的行列最大值来确定阀值z和α。

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

模型:Mj=max{m(ai,bj)|j=0...18且i≠j}

3

Mi=max{m(ai,bj)|i=0...18且i≠j} m(ai,bj)=cov(ai,bj)/ z=0.75设为阀值

算法:定义pi= ai,bi 定义为i图标准化灰度二值矩阵的最左和最右列向量 , m(ai,bj)表示ai和bj的相关系数,z设为阀值

1,初始化数据i=0,j=0 Mi=0,Mj=0

2,判断i<=18,是,进入4

否,进入3

3,输出pi的先后排列,结束

4,循环j=0...18且i≠j,计算m(ai,bj), 求出Mj=max{m(ai,bj)|j=0...18且i≠j},进入5 5,Mj>z,是,则进入6

否,进入7

6,pj= aj,bj 排在pi= ai,bi 左边,i=i+1,进入2 7,pi= ai,bi 列在全文第一列,进入8 8,循环j=0..18,i≠j,求出Mi=max{m(aj,bi)|j=0...18且i≠j},进入9 9,pj= aj,bj 排在pi= ai,bi 右边,i=i+1,进入2 根据上述算法,设计流程图如下:

4

编写的matlab程序见附件

运行程序并处理后的求解结果为:

整个过程没有用到人工干预,且计算机运行产生的排序和相关图片资料如下, 附件1的前三行

5

附件2的前三行

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

模型:max{m(ai,bj)|j=0...18且i≠j}

max{m(ai,bj)|i=0...18且i≠j}

p??=(mi,ni), mi=(ai,bi), ni=(ci,di)

m(ai,bj)=cov(ai,bj)/

n(ci,dj)=cov(ci,dj)/

阀值:α=0.77

算法2.1(抽出每行文字):

1,初始化i=0,j=0

2,判断i<=208,否,则进入3,是,进入4

3,因为a,b之间匹配即可建立关系,所以当提取关系到两端不能再次提取时,即可得到一个序列,也即是一完整的行,依次输出不相关的行,并进行编号L1,L2?L11

4,计算m(ai,bj),j=0..208 且j≠i,筛选B={m(ai,bj)>α|j≠i},判断B是否为空集,否,则进入5,是,则进入12

5,判断B中元素是否唯一,是,则进入6,否,则进入8

6,确定匹配成功,且pj在pi左侧,进入7

7,i=i+1,进入2

8,判断是否存在m(ai,bj)=1,是,则进入9,否,则进入11

6

9,判断是否D(ai,bj)=k0,是,则进入10,否,则进入12

10,如果只有一组,则匹配成功。否则,进行人工干预进行匹配。进入7 11,取max{(ai,bj)j=0,1?208且j≠i},进入6 12,pi为某行首位,进入13

13,计算max{m(aj,bi)|j=0,1?208且j≠i},所得元素即为成功匹配对,且pj在pi右侧,进入7。

根据上述算法设计流程图如下:

算法2.2(整行的拼接):利用算法1提取的L1,L2..L11 且定义Lk=(ek,fk)为第k行提取的上下特征数据向量,其中ek={ci|i是按照算法一排序的第k行灰度值向量},

7

fk={di|i是按照算法一排序的第k行灰度值向量},β为测得的行间距,s=1,2..11,t=1,2..11, m es,ft = cov(es,ft)/ st 1,初始化数据s=1,t=1

2,判断s<=11,否,则进入3,是,则进入4

3,输出L1..L11的排列顺序

4,计算C={m es,ft |t≠s,t=1..11}判断C中是否包含1,否,则进入5,是,则进入7

5,取出max{m es,ft |t≠s,t=1..11},实现Ls和Lt的匹配,且Ls位于Lt下侧,进入6

6,s=s+1,进入2

7,判断{m es,ft |t≠s,t=1..11且m es,ft =1}中,是否存在D2(s,t)=β,是,则进入8,否,则进入9

8,上述集合只有单元素(一对行)时,认定

Ls和Lt匹配,且Ls位于Lt下侧,多元素时(不止一对),进行人工干预,实现Ls和Lt匹配,且Ls位于Lt下侧,进入6

9,认定Ls为首行,进入10

10,取出max{m et,fs |t≠s,t=1..11},认定Ls和Lt匹配,且Ls位于Lt的上侧,进入6。

根据上述算法设计流程图如下

8

运行程序并处理后的求解结果为:

在进行算法2.1行拼接时,步骤10遇到了满足阀值和字间距,且不止一对的情况,这时运行程序并进行了人工干预,人工干预次数为5次,

算法2.2在步骤8中遇到了Ls与Lt的匹配值都满足完全匹配,D2(s,t)=β,且不止一对可匹配时,进行了人工干预,运行程序并进行了人工干预,人工干预次数为7次。

结果分析因为行向量特征向量维数的降低,可用信息量减少,再加上行间距较大,导致人工干预次数的显然增加。

附件3前三行图展示

9

附件4的前三行

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

10

模型:

max{m(ai,bj)|j=0...416且j≠i,i+1} 定义i和i+1为某图正反面 max{m(ai,bj)|i=0...416且i≠j,j+1} 定义j和j+1为某图正反面 p??=(mi,ni), mi=(ai,bi), ni=(ci,di) m(ai,bj)=cov(ai,bj)/

n(ci,dj)=cov(ci,dj)/

算法:

同算法2.1和2.2,只需要算法2.1的步骤4和10中 添加 筛选条件,两配对图片的反面特征数据是否匹配,两个都匹配认定匹配成功,在算法2.2中的 步骤8中添加 筛选条件两配对图片的反面特征数据是否匹配。

运行程序并处理后的求解结果为:

在进行算法1行拼接时,遇到了满足阀值和字间距,且不止一对,这时运行程序并进行了人工干预,人工干预次数为2次,

在遇到了Ls与Lt的匹配值都满足完全匹配,D2(s,t)=β,且不止可匹配一对时,进行了人工干预,运行程序并进行了人工干预,人工干预次数为3次。 因为多了一条筛选条件(提取的特征数据维数增加),使得匹配过程更加精确而且人工干预的次数明显降低了许多。

附件5前三行

11

六,模型的评价

这个模型的建立是通过图片的特征数据提取并产生相关系数矩阵进行匹配通过计算机模拟来实现的,优点是量化的特征(即灰度二值向量和相关系数向量)比较明显,且特征数据维数大,准确匹配的概率很高,结果的验证通过人为的阅读之后,得到的组合图的文字语句很符合语言逻辑,也很合理,所以这是一个很不错的模型。

模型的优点 :

1.程序通俗易懂,利用matlab进行数据处理相对精确和方便。

2.图像灰度矩阵的预处理,产生只有黑白元素的灰度二值矩阵(即文中标准化后的灰度矩阵)使得特征数据更加精准。

3.模型的建立是通过分析多维向量值的相关系数矩阵进行的,能比较准确的进行匹配 。

4.该模型的适用性比较广泛,能够解决多种类似的问题,具有一定的理论价值和实践意义。

5.运用统计和计算机知识简化问题,这对于一些实际问题抽象简化成数学理论问题,具有一定的启发意义。

6.人工干预的过程在算法设计和实现中尽可能地减少了,所以具有了简易可行和准确性。

模型的改进方案:

1,增加像素点分格的精细程度,产生更高维的特征数据,这样可以使得 特征数据的匹配更加精确。

2,阀值在选取的时候,可以适度调节,是筛选目标减少,进而减少计算量。

七,参考文献

[1]

http://baike.baidu.com/link?url=GEdOCrRk1KcIOvLdiVES80x8dNNTW66FyuDoL0ZaxR1mlTfIA2THCWTls8TeEi6qfI56b98Tryr4Y6Od0SXjYa (百度百科)

附录:

12

13

14

附件1

15

附件2

16

附件3

17

附件4

18

附件5

问题一提取特征数据的程序:

%先将名为“000.bmp”的图片文件重命名为“019.bmp” for i=1:19

if i<10

img_name=strcat('00',num2str(i),'.bmp');

Ai=imread(img_name);

Li= Ai(:,1);

else

img_name=strcat('0',num2str(i),'.bmp');

Ai=imread(img_name);

Li= Ai(:,1);

end %取出第i幅图的灰度矩阵的第一列,将它赋给Li for j=1:19

if j<10

19

img_name=strcat('00',num2str(j),'.bmp');

Bj=imread(img_name);

Rj= Bj(:,72);

else

img_name=strcat('0',num2str(j),'.bmp');

Bj=imread(img_name);

Rj= Bj(:,72);

end %取出第j幅图的灰度矩阵的最后一列,将它赋给Rj

M(i,j)=corr2(Li,Rj); %计算Li和Rj的相关系数,使它成为矩阵M第i行第j列的元素

end

end

M %打印矩阵M

问题一拼图程序:

%-- 2013/9/15 16:11 --%

I1=imread('008.bmp');

I2=imread('014.bmp');

I3=imread('012.bmp');

I4=imread('015.bmp');

I5=imread('003.bmp');

I6=imread('010.bmp');

I7=imread('002.bmp');

I8=imread('016.bmp');

I9=imread('001.bmp');

I10=imread('004.bmp');

I11=imread('005.bmp');

I12=imread('009.bmp');

I13=imread('013.bmp');

I14=imread('018.bmp');

I15=imread('011.bmp');

I16=imread('007.bmp');

I17=imread('017.bmp');

I18=imread('000.bmp');

I19=imread('006.bmp');

I=[I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,I17,I18,I19]

20

;

imshow(I)

I1=imread('003.bmp');

I2=imread('006.bmp');

I3=imread('002.bmp');

I4=imread('007.bmp');

I5=imread('015.bmp');

I6=imread('018.bmp');

I7=imread('011.bmp');

I8=imread('000.bmp');

I9=imread('005.bmp');

I10=imread('001.bmp');

I11=imread('009.bmp');

I12=imread('013.bmp');

I13=imread('010.bmp');

I14=imread('008.bmp');

I15=imread('012.bmp');

I16=imread('014.bmp');

I17=imread('017.bmp');

I18=imread('016.bmp');

I19=imread('004.bmp');

I=[I1,I2,I3,I4,I5,I6,I7,I8,I9,I10,I11,I12,I13,I14,I15,I16,I17,I18,I19];

imshow(I)

问题二提取特征数据的matlab程序:

for i=1:209

if i<10

img_name=strcat('00',num2str(i),'.bmp');

Ai=imread(img_name);

Li= Ai(:,1);

elseif i<100

img_name=strcat('0',num2str(i),'.bmp');

Ai=imread(img_name);

Li= Ai(:,1);

21

else

img_name=strcat(num2str(i),'.bmp'); Ai=imread(img_name); Li= Ai(:,1); end for j=1:209 if j<10

img_name=strcat('00',num2str(j),'.bmp'); Bj=imread(img_name); Rj= Bj(:,72); elseif j<100

img_name=strcat('0',num2str(j),'.bmp'); Bj=imread(img_name); Rj= Bj(:,72); else

img_name=strcat(num2str(j),'.bmp'); Bj=imread(img_name); Rj= Bj(:,72); end

M(i,j)=corr2(Li,Rj); end end M

问题二,产生相关系数矩阵

22

23

24

25

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com