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

2013年数学建模(B题)碎纸片的拼接复原模型

发布时间:2013-11-17 10:57:37  

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

承 诺 书

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

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

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

我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公开展示(包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等)。 我们参赛选择的题号是(从A/B/C/D中选择一项填写): B 我们的参赛报名号为(如果赛区设置报名号的话): 所属学校(请填写完整的全名): 参赛队员 (打印并签名) :1. 2. 3. 指导教师或指导教师组负责人 (打印并签名): (论文纸质版与电子版中的以上信息必须一致,只是电子版中无需签名。以上内容请仔细核对,提交后将不再允许做任何修改。如填写错误,论文可能被取消评奖资格。)

日期: 2013 年 9 月 10 日

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

1

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

编 号 专 用 页

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

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

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

碎纸片的拼接复原模型

摘 要:

件图片数值化处理并建立矩阵;然后根据图像页边距特点定位最左边和最右边的碎片;按照每张碎片中的文字部分所在位置,提取同一行碎片,利用互相关函数

??

jk

?f

T?1

j

(t)fk(t)

?

?f

T?1

j

(t)fk(t)

?1??jk?1)

横向拼合。

在第一问中,附件一、二仅作横向相关性比较即可;在第二、三问中,需要提取同一行碎片横向拼接,并将横向拼合完整的碎片进行竖向拼合,经过人工干预得到结果。

最终结果见附录。

关键词:拼接复原;互相关;矩阵;数值化;人工干预

3

一、问题重述

在司法物证复原、历史文献修复以及军事情报获取等领域的破碎文件的拼接上,传统的拼接复原工作需由人工完成,准确率较高,但效率很低。尤其是当碎片数量巨大时,人工拼接很难在短时间内完成任务。随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率。我们需要用算法分别设计出附件1至附件5的拼接方法及拼接结果。

二、模型假设

1.

2.

3.

4.

5.

忽略实际拼接中边缘的整齐性; 不需要考虑实际拼接中破碎文件大小是否一致; 忽略碎片边缘的损耗,认为拼接后是完整的图片; 在模型的建立过程中重视算法与建模思想,淡化程序的编写; 文字的行间距一定。

三、符号说明

?jk 互相关系数(?1??jk?1)

fj(t) 相关像素数组1

fk(t) 相关像素数组2

Pi 图像像素值矩阵

Qi 处理后图像像素值矩阵

amn,bmn 矩阵元素

四、问题的分析

1. 已知条件的分析

第一,对碎片尺寸和数量的分析。

附件1和附件2的图片尺寸均为72?1980,碎片数量均为19;附件3、附件4和附件5的图片尺寸均为72?180,碎片数量均为11?19。由于纵列有11个,像素值180,总值11?180?1980,因此,所有拼接后的图像尺寸一致,均为1368?1980。

第二,对碎片边界的分析。

对于附件1、2,所有碎片上行和下行像素值为白。其中,一张碎片位于最左端,最左列像素值均为白;一张碎片位于最右端,最右列像素值均为白。

对于附件3、4、5,拼接后图像四边像素值为白,碎片也存在边像素值全为白的情况,因此需要分类讨论。

4

切割线为长度完全相等的直线,因此切割线两边应有很大的相似度,灰度值相似。

第三,对碎片正反性的分析。

附件5存在正反面情况,同一块用a、b,但根据题意分析,我们无法确定碎片的正反,即a可能是正面,也可能是反面。因此拼合时,应当注意统一序号在同一平面出现的单一性,例如,000a在设定正面出现以后,000b一定在反面。

第四,对碎片像素白色行的分析

对于中文,同一行的所有碎片文字是横向对齐的,因此白色开始的位置是一样的。因此可以提取出同一行的碎片。

2. 拼接方法的分析

由于碎片是长方形,有四条边,因此边的拼接有优先顺序。由于长边特征较为明显,采样点多,因此优先横向拼接,然后纵向拼接。当电脑拼接无法完成时,采取人工干预。

五、模型的分析与求解

1. 方法的确立

根据对问题的分析,我们得知此问题需要计算离散序列之间的相关性,因此我们需要使用互相关系数计算和矩阵的计算。

2. 模型的建立

1. 1图像数字化

由于电脑中图像的大小是由像素数量表示,而每个像素点均由一个数值表示,因此利用matlab读取灰度图像的像素值,第n副图用矩阵表示为:

?a11a12…a1n???aa…a21222n?(0?a?255)Pi???…………???aa…amn??m1m2

在第一问中,n=72,m=1980;

在第二问、第三问中,n=72,m=180。

1. 2数据预处理

由于互相关函数需要比较正负范围相等的数组,因此我们将Pn的每个数值减去

amaxaa,使amn在 [-max,max]范围内,即 222

??127.5?127.5??127.5?127.5?Am?n??……???127.5?127.5…?127.5??…?127.5? ?……?…?127.5?

5

?a11?127.5a12?127.5?

a?127.5a22?127.5

Qi?Pi?A??21

?……?

?am1?127.5am2?127.5

?b11b12?bb22??21

?……?

?bm1bm2

…a1n?127.5?…a2n?127.5??

?……

?

…amn?127.5?

…b1n?…b2n??(?127.5?b?127.5) ……?

?

…bmn?

1. 3相关性的计算

由于碎片大小完全一致,切割线完全竖直且交界处长度完全相等,并且切割线无损,图像可以完全拼接,因此相邻两个图形交接处相似。由于图像已经数字化处理,因此可以由边界相应像素数值的相关性来确定两张图是否相邻。对于相关性的计算,我们使用互相关函数。互相关函数公式为:

?jk?

?f

T?1

j

(t)fk(t)

?

?f

T?1

j

(t)fk(t)

?1??jk?1)

公式中,分子表示的是两组离散数值的相似程度,分母则起到归一化作用,相邻两边的数组分别为序列fj(t)、fk(t)。

当?jk?1时,两组数相似程度最大,即两张图片最有可能相邻; 当?jk??1时,两组数相似程度最小,即两张图片不相邻。 根据这个公式,即可算出两个图边缘的相关度。 1. 4图像的拼接 1. 4. 1 第一问

附件一:

首先,根据图像页边距白边特点定位最左边为白色的碎片,

?a11?255???a?255?(0?a?255),将i=1,2,??19分别带入计算,Pi的第一列列向量为?21?…???a?255?m1??a11?255?

??a?25521??0,因此,最左边碎片为014。 仅当i=15时,??…???a?255?m1?

然后,令fj(t)?bj72fk(t)?bj1,将014矩阵数据带入fj(t)中分别计算?ijk,当取

6

得取?max时,i-1即为相邻碎片。同理,即可拼接整幅图。结果见附录。

1980?1?fj(t)f1k(t)??i?11980?1?fj(t)f2k(t)?? i?2??…

?1980?1?fj(t)fik(t)?i?19?ijk

同理可得附件二结果。

Matlab 附件一 拼接图

1. 4. 2 第二问

首先,确定最左边碎片。因为碎片存在非左边仍有白边的情况,例如附件4的图002.bmp,如下图所示。(由于底色是白色与文档背景相同,进行了对比度降低处理。) 7

附件4-002.bmp

因此,需要提取多组行向量,根据是否均为0确定最左碎片,同理可确定最右碎片。左碎片满足条件如下:

?a11?255??a12?255??a1r?255???????a?255a?255a?255?21???22??…=?2r??0 ?…??…??…???????a?255a?255a?255?m1??m2??mr?

式中,r的大小由实际图像左边缘白边像素数量决定。在附件3中,r取15时,满足条件的碎片数量为11。

利用同一行碎片文字垂直位置相同的特点,根据最左边碎片的文字的垂直位置特点,确定图像所在行。

同第二问,分别计算同一行序列的互相关系数,取最大值拼合。然而,这样只能拼接出11个横行碎片,用互相关函数拼接部分碎片后,最后用人工干预完成白边部分的拼合。结果如附件所示。

1. 4. 3 第三问

由于是两面混合,首先忽视两面性,认为所有碎片是在同一平面上,进行整体拼接,则图像应该为22?19个碎片,在进行最左边和最右边计算时会出现22个碎片。

然后根据第二问方法,进行横向碎片的拼接,纵向碎片的拼接。最后进行人工干预。由于图像是由两面组成的,因此两张图片的对称点(第n列和第20-n列对称)数字相同字母不同,例如199b在一个面的第4行、第19列,那么199a就在另一面的第4行、第1列。因此正反两面的对应行所在位置一致,可以人工将图拼合完整。效果如如下,结果见附件。

8

Matlab 附件五 拼接图

六、模型评价

模型优点:

1、模型具有坚实可靠的数学基础,经过实践数据分析证明,互相关函数在本题中应用的可行性,简化了对模型问题的分析;

2、模型能较好的优化人工干预次数。

模型缺点:

1、附件3、4、5在拼接时没有完全脱离人工干预;

2、在实际推算中,模型会产生较大的运算量;

3、模型在现实生活中的应用有待优化,因为现实中很少有完全规则的文字碎片。

9

参考文献:

[1]屈婉玲等编,离散数学,北京:高等教育出版社 ,2008

[2]同济大学数学系编,工程数学——线性代数 同济第五版,北京:高等教育出版社 ,2007

[3](美)奥本海姆等著 刘树棠译,信号与系统(第二版),北京:电子工业出版社 2013

[4]张志涌等编著,精通MATLAB R2011a,北京:北京航空航天大学出版社 ,2011

[5](美)穆尔 著,高会生,刘童娜,李聪聪 译,MATLAB实用教程(第二版),北京:电子工业出版社 ,2010

[6](美)莫勒(Moler,C.B)著 喻文健译,MATLAB数值计算,北京:机械工业出版社, 2006

[7](美)冈萨雷斯(Gonzalez.R.C.)等著 阮秋琦等译,数字图像处理(MATLAB版),北京:电子工业出版社 ,2005

[8](美)冈萨雷斯等著 阮秋琦译,数字图像处理的MATLAB实现(第2版),北京:清华大学出版社 ,2013

[9](美)罗森著 袁崇义等译,离散数学及其应用,北京:机械工业出版社 ,2011

10

附录

附录一 模型结果

附件一效果图 附件二效果图

11

12

附件4结果:

13

14

附录三效果图 附录四效果图

附录五效果图1 附录五效果图2

15

附录二 部分源程序(由于源程序篇幅过长,打印不便,因此只附上部分程序) 使用软件:Matlab

I000=imread('000.bmp')

I001=imread('001.bmp')

I002=imread('002.bmp')

I003=imread('003.bmp')

I004=imread('004.bmp')

I005=imread('005.bmp')

I006=imread('006.bmp')

I007=imread('007.bmp')

I008=imread('008.bmp')

I009=imread('009.bmp')

I010=imread('010.bmp')

I011=imread('011.bmp')

I012=imread('012.bmp')

I013=imread('013.bmp')

I014=imread('014.bmp')

I015=imread('015.bmp')

I016=imread('016.bmp')

I017=imread('017.bmp')

I018=imread('018.bmp')

P=[I000,I001,I002,I003,I004,I005,I006,I007,I008,I009,I010,I011,I012,I013,I014,I015,I016,I017,I018]

% 最左计算函数

function F=borderright(x)

for j=1:1:19

y(j)=0

for i=1:1:1980

if(x(i,72*(j-1)+1)==255)

y(j)=y(j)+0

else

y(j)=y(j)+1

end

end

if(y(j)==0)

F=j

end

end

end

function d=split(x,y,m)

16

maxx=[0,0]

for j=1:1:19

z(j)=0

if((j~=(m(1)+1))&&(j~=(m(2)+1))&&(j~=(m(3)+1))&&(j~=(m(4)+1))&&(j~=(m(5)+1))&&(j~=(m(6)+1))&&(j~=(m(7)+1))&&(j~=(m(8)+1))&&(j~=(m(9)+1))&&(j~=(m(10)+1))&&(j~=(m(11)+1))&&(j~=(m(12)+1))&&(j~=(m(13)+1))&&(j~=(m(14)+1))&&(j~=(m(15)+1))&&(j~=(m(16)+1))&&(j~=(m(17)+1))&&(j~=(m(18)+1))&&(j~=(m(19)+1)))

for i=1:1:1980

if((x(i,72*y)<255)&&(x(i,72*(j-1)+1))<255)

z(j)=z(j)+1

else

z(j)=z(j)+0

end

end

else

z(j)=0

end

if(z(j)>maxx(1))

maxx=[z(j),j]

end

end

d=maxx(2)

end

function two(x,a,b)

for i=1:1:a

for j=1:1:b

if(x(i,j)<255)

x(i,j)=0

end

end

end

f3=0

f4=0

f5=0

f3=double(f3)

f4=double(f4)

f5=double(f5)

p=0

bai=0

17

HENG=[19,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1;

20,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 70,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 81,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 86,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 132,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 145,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 159,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 171,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1; 191,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1;

201,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1;] for k=1:1:11

a=HENG(k,1)

for i=2:1:19

for b=1:1:208

f3=0

f4=0

f5=0

for c=1:1:180

f1=Q(c+a*180,72)

f2=Q(c+b*180,1)

f3=f3+Q(c+a*180,72)*Q(c+b*180,1)

f4=f4+f1*f1

f5=f5+f2*f2

end

r(b)=f3/sqrt(f4*f5)

if r(b)>p

p=r(b)

h=b

end

r(b)=0

end

p=0

HENG(k,i)=h

a=h

for c=1:1:180

bai=bai+Q(c+a*180,72)

end

if ((bai==22950)&&(i==19))

msgbox('àTà2')

18

end

if ((bai==22950)&&(i<19))

msgbox('1t1t£?è?1¤?é?¤°é')

break

end

bai=0

end

end

f3=0

f4=0

f5=0

f3=double(f3)

f4=double(f4)

f5=double(f5)

p=0

bai=0

% 初始化数组

%

HENG=[49,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,141;

% 61,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,36; %

168,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,18;

% 38,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,74; % 71,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,60; %

14,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,176;

% 94,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,43; %

125,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,145; % 29,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,59; % 7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,196; %

89,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,123;] for k=1:1:11

a=HENG(k,19)

for i=18:-1:1

for b=1:1:208

f3=0

f4=0

f5=0

r(b)=0

19

if b~=105

for c=1:1:180

f1=Q(c+a*180,1)

f2=Q(c+b*180,72)

f3=f3+Q(c+a*180,1)*Q(c+b*180,72) f4=f4+f1*f1

f5=f5+f2*f2

end

r(b)=f3/sqrt(f4*f5)

if r(b)>p

p=r(b)

h=b

end

end

end

p=0

HENG(k,i)=h

a=h

for c=1:1:180

bai=bai+Q(c+a*180,1)

end

if (bai>22000)&&(i>1)

msgbox('1t1t£?è?1¤?é?¤°é') break

end

bai=0

end

end

20

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