《全国大学生数学建模大赛B优秀论文.doc》由会员分享，可在线阅读，更多相关《全国大学生数学建模大赛B优秀论文.doc（16页珍藏版）》请在三一办公上搜索。
1、2013高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛
2、规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 本10队 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填写错误，论文可能被取消评奖资格。） 日期： 2013 年 9 月
3、16 日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）： 碎 纸 片 的 拼 接 复 原 摘要 破碎文件的拼接在历史文献修复和军事情报获取等领域中都发挥着重要作用，由于撕裂、切碎、污染或自然衰老等原因，原始文件的信息可能会丢失。尽管用手或某些化学过程，可能将一些原始文件恢复，但是基于图像技术的文件恢复是一种非侵入性的和高效率的方法，所以它被普遍采用。传统上，拼接复
4、原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。 本文中针对问题1，读入附件所给出的图片，用自定义阈值法实现图像的二值化，得出碎纸片的匹配矩阵，根据欧氏距离计算图片之间重叠部分的相似度，再利用matlab软件进行该算法相关计算，得到碎纸片的拼接顺序，复原破碎图片。针对问题2，读入附件所给出的图片，用自定义阈值法实现图像的二值化，得出碎纸片拼接的匹配矩阵，任取一碎片并判断：（1）若被判断为图像左（右）边缘的碎片，则从该碎片右（左）边缘开始进行拼接，计算与其他碎片之间重叠部
5、分的相似度，再利用matlab软件进行矩阵的相关计算，得到碎纸片的拼接顺序，把块状复原拼接成条状。（2）若为图像中间部分的碎片，则分别从左右两个方向进行拼接。再按问题1的方法，计算这排列好的11行碎纸条重叠部分的相似度，即用matlab软件进行此算法的相关计算，得到碎纸片的拼接顺序，复原破碎图片，问题2的相似度的计算与问题1一样，用求欧式距离的方法。针对问题3，读入附件所给出的图片，用自定义阈值法实现图像的二值化，得出碎纸片拼接的匹配矩阵，任取一碎片再进行如同问题2中拼接，即求最小欧式距离的方法，发现满足此条件的候选被拼接的碎片不唯一，则我们再用相关系数法求得该系数最接近1的碎片是我们的最佳选
6、择，最后用matlab软件进行这个算法实现的相关计算，得到碎纸片的拼接顺序，复原破碎图片。关键词： 图像碎片拼接 二值化法 欧氏距离 相似度 人工干预 相关系数 1.问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。1.1破碎纸片为同一页印刷文字文件的碎纸机仅纵切得到的，建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如
7、果复原过程需要人工干预，则写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。1. 2破碎纸片为碎纸机既纵切又横切的得到，建立碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，则写出干预方式及干预的时间节点。复原结果表达要求同上。1. 3从现实情形出发，破碎纸片为双面打印文件的碎纸片，建立碎纸片拼接复原模型。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。 2.问题分析 此题针对破碎文件的拼接，在问题1中，对给定的来自同一页印刷文字的碎纸机破碎纸片（仅
8、纵切），建立碎纸片，拼接复原模型和算法。问题2中，来自同一页印刷文字的碎纸机破碎纸片（纵横切），建立碎纸片拼接复原模型和算法。问题3中，从现实情形出发，针对双面打印文件的碎纸片拼接复原问题的解决。设计相应的碎纸片拼接复原模型与算法。问题1：针对此题，读入附件所给的灰度图，用自定义阈值法实现图像的二值化。对于每一个碎纸片的灰度矩阵进行二值化处理。计算匹配矩阵，得出碎纸片拼接的匹配矩阵，找一张碎片的右边分别于其他碎片的左边进行匹配，直到找到相匹配的碎片为止，再把找到的碎片左边与其他碎片的右边进行匹配，直到找到相匹配的碎片为止，依次循环下去，直到拼接完成。问题2：针对此题，读入附件所给的灰度图，用自
9、定义阈值法实现图像的二值化。对于每一个碎纸片的灰度矩阵进行二值化处理。计算匹配矩阵，得出碎纸片拼接的匹配矩阵， 这时我们需要判断碎片是左边缘还是右边缘，还是上下边缘，中心边缘，从而进行拼接，先拼行再拼列，从左往右拼，最后复原破碎图片。问题3：读入附件所给出的图片，用自定义阈值法实现图像的二值化，得出碎纸片拼接的匹配矩阵，任取一碎片再进行如同问题2中拼接，即求最小欧式距离的方法，发现满足此条件的候选被拼接的碎片不唯一，则我们再用相关系数法求得该系数最接近1的碎片是我们的最佳选择，最后用matlab软件进行这个算法实现的相关计算，得到碎纸片的拼接顺序，复原破碎图片。 3.模型假设3.1假设所研究碎
10、纸片规则且形状大小完全相同。3.2假设所研究碎纸片为平滑的。3.3假设所研究碎纸片文字方向一致。4.变量说明i表示碎纸片灰度矩阵行数j表示碎纸片灰度矩阵列数P表示碎纸片灰度矩阵P表示二值化灰度矩阵D表示欧式距离表示改点的灰度值表示灰度矩阵第j列的k维坐标表示灰度矩阵第1列的k维坐标表示灰度矩阵第j列的k维坐标表示被选碎纸片第j列的i个指标所组成的向量表示匹配碎纸片第1列的i个指标所组成的向量C（X,Y）表示相关系数,X,Y表示两个向量5.模型的建立与求解问题一：碎纸片灰度矩阵的行列： i=1980 j=72.碎纸片灰度矩阵类型： 二值化处理后的灰度矩阵： 处理后的灰度矩阵第j列为： 处理后的灰
11、度矩阵第1列为： 运用欧氏距离得到相似度： D=D值越小，表明这两个碎纸片相似度越高，从而可以进行拼接，依次类推可得结果。 1、将附件1中所有图片进行预处理得到灰色矩阵，再将各个矩阵的第一列和最后一列拿出，构成新的72*2的列矩阵，对此进行初始编号。 2、用其中一个列矩阵的第二列与其他18个列矩阵的第一列做欧氏距离，在这十八个距离中，取最小值作为与它相似度最高的矩阵；再将取得最小值的列距阵的第二列与其他17个列矩阵的第一列做欧氏距离，在这十八个距离中，取最小值作为与它相似度最高的矩阵；依次循环直到拼接完成。matlab编程如下：imname = dir(.*.bmp);%读入文件夹下的全部图像
12、im_num = length(imname);% 文件夹中图像的个数ininum = 0;for s = 1:im_num Img = imread(imname(s).name,bmp); if norm(double(Img(:,1) - 255) 0.0001 ininum = s; endendindex = 1:ininum-1,ininum+1:im_num;Img1 = imread(imname(ininum).name,bmp);%读入第一幅图像height1,width1 = size(Img1);%得到图像的尺寸xunxu = zeros(1,im_num); %存储最
13、终序列号xunxu(1) = ininum;result = Img1;for a = 2:im_num error = zeros(1,length(index); for tt=1:length(index) Img2 = imread(imname(index(tt).name,bmp);%读入第一幅图像 height2,width2 = size(Img2);%得到图像的尺寸 error(tt) = norm(double(Img1(:,end)-Img2(:,1),2); end tm,tn=min(error); temp = imread(imname(index(tn).nam
14、e,bmp); result = result,temp; Img1 = imread(imname(index(tn).name,bmp);xunxu(a) = index(tn); index = index(1:tn-1),index(tn+1:end); end% result = uint8(result);% xunxu附件1的输出结果如表1 8 14 12 15 3 10 2 16 1 4 5 9 13 18 11 7 17 0 6得到拼接图1： 附件2输出结果表2： 3 6 2 7 15 18 11 0 5 1 9 13 10 8 12 14 17 16 4得到拼接图2：问题二
15、：图像拼接技术主要有以下三个步骤：图像预处理、图像配准、图像融合与边界平滑。空白的碎片通常出现在边界或分离的多个列的文档。最左边的分解特点是左边附近没有纹理或右边界有纹理，反之亦然，是最右边的边界。很明显,这两种类型的碎片可以方便验证通过检查直方图的垂直预测(即沿分解方向)。因此,他们首先,他们作为始端和终端，再建立如问题一的模型进行拼接，即求最小欧式距离的方法，用matlab软件进行此算法的相关计算，得到碎纸片的拼接顺序，复原破碎图片。1 2 1图是具有左边缘特征的图，2图具有右边缘特征的图 具体算法步骤 ： 1、将附件3中所有图片进行预处理得到灰色矩阵，再将各个矩阵的第一列和最后一列拿出，
16、构成新的列矩阵，对此进行初始编号。2、任取一列矩阵并判断是左边缘图还是右边缘图，若为左边缘图则从该碎片第二列开始与其他的列矩阵的第一列做欧氏距离，在这209个距离中，取最小值作为与它相似度最高的矩阵；再将取得最小值的列距阵与其他的列矩阵的第一列做欧氏距离，一次循环到该行拼接完成，直到把行都拼接完，再用问题1的方法拼接完成；若为右边缘图则从该碎片第一列开始与其他的列矩阵的第二列做欧氏距离，在这209个距离中，取最小值作它相似度最高的矩阵，将取得最小值的列距阵的第一列与其他的列矩阵的第二列做欧氏距离，一次循环到该列拼接完成，直到把列都拼接完；再用问题1的方法拼接完成。matlab编程如下：func
17、tion judgelinespaceam=cell(1,209);dd=zeros(2,209); for i=1:209 if i10 & i101) ImgName = D:B30, num2str(i-1), .bmp; am1,i = imread(ImgName, bmp); else ImgName = D:B3, num2str(i-1), .bmp; am1,i = imread(ImgName, bmp); end endend for k=1:209 flag=0; for i=1:180 for j=1:72 if am1,k(i,j) =255 flag=1; bre
18、ak; end end if flag=1; dd(1,k)=i-1; break; end end end for k=1:209 flag=0; for i=180:-1:1 for j=1:72 if am1,k(i,j) =255 flag=1; break; end end if flag=1; dd(2,k)=180-i; break; end end enddd输出函数如下：function re = mat2pic(mat) imname = dir(.*.bmp); im_num = length(imname);Img = imread(imname(1).name,bmp
19、);height,width = size(Img); r,c = size(mat)re = zeros(r*height,c*width,uint8);for tr = 1:r for ts = 1:c Img = imread(imname(mat(tr,ts).name,bmp);re(tr-1)*height+1:tr*height,(ts-1)*width+1:ts*width)=Img; endendimshow(re);附件3的输出结果如表3049 054 065 143 186 002 057 192 178 118 190 095 011 022 129 028 091 1
20、88 141 061 019 078 067 069 099 162 096 131 079 063 116 163 072 006 177 120 052 036168 100 076 062 142 030 041 023 147 050 179 191 120 086 195 026 001 087 018038 148 046 161 024 035 081 189 122 103 130 193 088 167 025 008 009 105 074071 156 083 132 200 017 080 073 202 198 015 133 170 205 085 152 165
21、027 060014 128 003 159 082 199 012 073 160 135 203 169 134 039 031 051 107 115 176094 034 084 183 077 090 047 121 042 124 144 112 149 097 136 164 127 058 045125 013 182 109 197 016 184 110 187 066 106 150 021 175 157 181 204 139 145029 064 111 201 005 092 180 048 037 075 055 044 206 010 104 098 172
22、171 059007 208 138 158 126 068 175 045 174 000 137 053 056 093 155 070 166 052 196 089 146 102 154 114 040 151 207 155 140 185 108 117 004 101 113 194 119 123得到拼接图3：得到拼接图4：问题三：先建立如问题二的模型，即求最小欧式距离的方法，发现满足此条件的候选被拼接的碎片不唯一。基于区域的配准方法是从待拼接图像的灰度值出发，对待配准图像中一块区域与参考图像中的相同尺寸的区域使用最小二乘法或者其它数学方法计算其灰度值的差异，对此差异比较后来
23、判断待拼接图像重叠区域的相似程度，由此得到待拼接图像重叠区域的范围和位置，从而实现图像拼接，而本文用计算两块区域的对应像素点灰度值的相关系数，相关系数越接近于1，则两块图像的匹配程度越高。该方法的拼接效果要好一些，成功率有所提高.附件5的输出结果如表56.模型的推广与改进该模型把规则且形状大小完全相同破碎纸片复原拼接，而且程序简单容易操作，建模过程用到的图像拼接技术具有一般性，容易做出推广，但是在碎片数量庞大时，我们需要用水平投影和垂直投影的方法将图片进行聚类，然后分类后再进行拼接，这样会减少计算机的运行时间，空间，也就同时提高了拼接效率。7.参考文献1罗智中，基于文字特征的文档碎纸片半自动拼
24、接，计算机工程与应用，05期：2012。2王磊，莫玉龙，戚飞虎，基于Canny 理论的边缘提取改善方法J，中国图象图形学报，03期：191-195，1996。3陶波，于志伟，郑筱祥，图像的自动拼接J，中国生物医学工程学报，04期：29-35，1997。4刘金根，吴志鹏，一种基于特征区域分割的图像拼接算法J，西安电子科技大学报，06期：768-771，2002。5周鹏，谭勇，徐守时，基于角点检测图像配准的一种新算法J，中国科学技术大学学报，04期：455-461，2002。6朱延娟，周来水,二维非规则碎片的匹配算法J，计算机工程，24期:7-9，20077罗智中.基于线段扫描的碎纸片边界检测算法
25、研究J，仪器仪表学报，02期：289-294，2011。8De Smet P.Semi-automatic Forensic reconstruction of ripped-up documentsC.International Conference on Document Analysis and Recognition，10th，703-707，2009。9 Biswas A, Bhowmick P, Bhattacharya B, Reconstruction of torn documents using contour maps，In International conferenc
26、e on image processing,3th：517520，2005。10 Brassil J，Tracing the source of a shredded document，Revised papers from the 5th international workshop on information hiding 387399，2003。11Brown M, & Seales W， Image restoration of arbitrarily warped documents，IEEE Transactions on Pattern Analysis and Machine
27、 Intelligence, 10th：12951306，2004。12Kuhn H，The Hungarian method for the assignment problem， Naval Research Logistics,1th：721，2005。13 Zhu L, Zhou Z, Zhang J, & Hu D，A partial curve matching method for automatic reassembly of 2D fragments，Lecture Notes in Control and Information Sciences,10th： 345-645，2006。14 Wolfson H, Schonberg E, Kalvin A, & Lamdan Y，Solving jigsaw puzzles by computer，Annals of Operations Research,1th：5164，1988。15 Zhu L, Zhou Z, & Hu D， Globally consistent reconstruction of ripped-up Documents，IEEE Transactions on Pattern Analysis and Machine Intelligence, 1th：113，2008。
