2013建模碎片拼接

1、2013高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。如有违反竞赛章程和参赛

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

3、月16日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：论文题目（三号，黑体，居中）摘要（一级标题、四号，黑体，居中）（小四号，宋体）我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队

4、外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。关键词：数学建模；交通；拼接一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题：1. 对于给定的来自同一页印刷文字文件的碎纸

5、机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达（见【结果表达格式说明】）。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。3. 上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文

6、件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、问题分析历史文物及近现代名人作品的毁坏造成了人类文明历史上的无数遗憾，重要证据的粉碎给破案增加了无数困难，另外还有许多文件的破碎毁坏也造成许多无法弥补的损失，因此图像碎片复原的技术研究是一个具有重大意义的课题。对于问题一，由题目可得文字文件碎片均为规则长方形，且为图片，因此可以利用图片边缘灰度相似性对比进行图片拼接还原。首先对文件图像进行像素量化转化，因为该文字图像为黑白图像，因此可对附件文字图像灰度值进行二值化，白色记为0，其他颜色记为1。取其中一张图片的左边缘灰度二值表依次与

7、其他图片右边缘灰度二值表进行比较，对应位置相似度误差最小的可相互拼接，其中有的图片有一侧灰度二值表全部为零，根据对比判断其为整幅图片边界,根据得出的排列顺序，利用灰度值反向导出整幅图。对于问题二，由问题一可得图片拼接方法是边缘灰度相似性比较，基于此种算法对问题二碎片进行拼接，可先将完整图片的左右两边分别含有的图片挑出，但是由于图片又被横向剪切平均分成11份，因此边缘相似度可比较范围只有问题一的，相似性小，拼接正确率较低，需增加约束条件。因为同为一行拼接的图片的每行文字的行间距位置固定且相同，所以可根据每行图片字的行间距相同，进行分行挑选。然后根据边缘灰度相似比对及相应的人工干预，得出正确的每行

8、拼接结果，以及整幅图片的拼接结果。三、模型假设1.所有文件碎片保存完好2.全部碎片保存完整，没有破损及污渍。3.全部碎片切割整齐，不出现斜歪现象。四、符号说明1.：碎片总数2.:图片左边缘与图片右边缘相似度误差3.：图片左边缘与所有图片右边缘相似度误差的最小值4.：图像的灰度矩阵5.：图像灰度二值化矩阵五、模型的建立与求解一般来讲，图像碎片复原的主要工作流程可以概括为以下三个步骤:(1)对碎片进行预处理，即将物体碎片数字化，得到碎片的数字图像，并进行特征检测提取等一系列图像预处理过程。(2)图像碎片匹配，通过各种匹配算法找出相互匹配的图像碎片。(3)图像碎片的拼合，将上一步中找到的相互匹配的图

9、像碎片拼合在一起得到最终的正确结果。对于问题一基于图像边缘灰度相似性的图像拼接算法思路：首先对图像进行预处理，进行像素量化转化，然后进行灰度值二值化，然后利用边缘灰度相似性进行比对，依次进行左右两边缘相似性的比对，对相似度误差大小进行比较，误差越小即相似度最大的为拼接对象。算法描述：算法输入：各个需要进行拼接的图像算法输出：拼接完成的完整图片步骤一：对图像进行对应像素转化，并对得到的灰度值进行二值化转化；步骤二：抽取碎片图像，并将其左边缘灰度二值表依次与所有碎片图像的右边缘灰度二值表进行相似性比较，并记录相似度误差。步骤三：比较相似度误差大小，找出相似度误差最小的即为碎片图像的拼接对象。步骤四

10、：重复步骤二、三，直到所有碎片图像都得到所对应的拼接对象。步骤五：进行人工干预，将对应图片进行拼接，找出完整图片的拼接序号，利用matlab导出完整图像。模型建立.1碎片预处理一般图像特征包含纹理特征、颜色特征和形状特征，题中给出图片为文字文件且为规则长方形，因此首先将图像碎片进行像素灰度处理，得出图像碎片的的灰度值矩阵记为，文字图像为黑白图片，对图片进行灰度值二值化处理，白色记为0，其他颜色全部为1，因此可以得出图像灰度值二值化后的矩阵，此后所使用的灰度值都是二值化后的灰度值。.2碎片匹配基于边缘灰度相似性进行匹配，将个图片的左右边缘灰度值依次选出重新组成两个矩阵，分别为左边缘矩阵，右边缘矩

11、阵。将左边缘矩阵中任一列灰度值与右边缘矩阵中的每列灰度值依次进行相似性对比，则图片左边缘与图片右边缘灰度值差值的绝对值之和为，：左边缘矩阵中列向量的序号也指图片序号，（）：右边缘矩阵中列向量的序号也指图片序号，（）：左边缘矩阵中第行第列这个像素点所对应的灰度值：右边缘矩阵中第行第列这个像素点所对应的灰度值比较该列左边缘灰度值分别与每列右边缘灰度值差值的大小，得到最小的，即说明图片左边与图片右边相匹配，可进行拼接。依据上述匹配算法得出所有碎片的拼接.3碎片拼接依据图片匹配得出的匹配顺序，进行人工干预，将所有图片进行拼接，并进行修正，找出整幅图的左右边，得出完整图片的拼接顺序，通过matlab编程

12、实现灰度值向图片的转化，导出完整图片。模型求解.1汉字图片拼接通过matlab编程，分别得出19个汉字碎片图像的各个灰度值矩阵，及其进行灰度值二值化后的矩阵，将19个汉字碎片图像左右边缘灰度值、，组成新的矩阵分别为左边缘矩阵，右边缘矩阵，并将每个图片左边缘灰度值与右边缘灰度值进行相似性对比，得出相邻两个图片的拼接组合，如下表：表1 汉字图片左右边缘拼接组合x0123456789101112131415161718y1716101514011653181498122713注：“x”“y”代表图片序号，图片x左边拼接图片y右边。经过人工干预得到的完整排序见下表：表2 完整汉字图片拼接顺序81412

13、15310216145913181171706最终拼得的完整图片见附录一图一，各种matlab程序见附录二程序。.2英文碎片拼接英文碎片拼接过程与汉字一样，最后得到的碎片左右边缘拼接图片组合见下表：表3 英文图片左右边缘拼接组合x0123456789101112131415161718y1156416032101131889127171415注：“x”“y”代表图片序号，图片x左边拼接图片y右边。经过人工干预得到的最终完整图片序号见下表：表4 完整英文图片拼接顺序3627151811051913108121417164拼接完整的英文文件图片见附录一图二。问题二算法算法描述：输入：全部碎片图像输

14、出：完整图片图像步骤一：首先将图片进行像素灰度值转化，再将灰度值二值化，白色为0，其他全部为1；步骤二：依据边缘灰度值相似，同为整幅图左右边界的图片它们的边缘灰度在相应范围内完全相同，因此可从全部碎片图像中确定页边图片；步骤三：取左页边图片的其中一张，依据所给拼接标准，在理想误差范围内确定可与该边界图片进行同行拼接的所有图片；步骤四：剔除已挑选出的同行图片；步骤五：选取第二张左页边图片，重复步骤三、四，直到所有左页边图片所匹配的同行图片完全选出；步骤六：对同行图片自动拼接结果进行人工干预检验。若是有错，进行人工调整，得出每行图片的正确拼接顺序；步骤七：根据上下边缘的灰度相似性，进行图片的上下自

15、动拼接，通过matlab导出拼接的完整图像。进行人工干预检验，若有错，进行调整再次进行上下拼接得出正确拼接结果，通过matlab导出完整图像。汉字图片拼接.1模型的建立1）碎片预处理将图片全部导入matlab中进行像素转化，得每张图像灰度值矩阵 ，然后将图片灰度值进行二值化处理，白色记为0，其他颜色记为1，得到新的灰度值矩阵，此后所使用的灰度值都是二值化后的灰度值。2）碎片匹配根据问题一可知完整图片拼接是以11行19列的形式排列的，基于边缘灰度相似性比较，将所有图片左边缘灰度值进行比较，同为页面左边界的图片左边缘灰度值在一定范围内完全相同，因此可得出同为页面左边界的11张图片，同样方法可得出同

16、为页面右边界的11张图片。首先观察这11张图片各自的特征，可发现图片089与其余10张图片相比较特殊，因此先将除图片086外的10张图片根据其灰度值表确定字行间距及对应位置和右边缘灰度值。依次将10张图片与剩余非边界图片进行相似度比对，比对标准如下：；：左页边图片序号；：除左页边图片外的图片序号；：左页边图片的行间距宽度；：除左页边图片外的图片的行间距宽度：图片右边缘灰度与图片右边缘灰度对比误差Q：图片右边缘灰度与图片右边缘灰度对比误差最小值由matlab编程可得出11行图片的整行拼接序列。3）碎片拼接由于自动拼接图片存在误差，因此对每行自动拼接图片进行人工干预，得到正确拼接顺序。依据边缘灰度

17、相似性对11行图片进行上下拼接，由最终拼接结果，通过matlab编程导出完整图像。进行人工干预检验，若有错则进行调整再次上下拼接并导出正确图像。.2模型求解根据建立的模型，通过matlab编程可得出初次进行成行拼接的结果如下表：表6 人工干预后整行图片再次拼接结果720813815812668175451740137535693153701663219614128315982199135127316020316913439315110711517629641112015921804837755544206101049817217159381484616124358118912210313019

18、388167258910574495465143186257192178118190951122129289118814161197867699916296131796311616372617720523671156831322001780332021981513317020585152165276089146102154114401512071551401851081174101113194119123943484183904712142124144771121499713616412758431251318210919716184110187661061502117315718120413

19、9145168100766214230412314719150179120861952618718表7 成行图片自动上下拼接结果49546514318625719217811819095112212928911881416119786769991629613179631161637261772052367115683132200178033202198151331702058515216527601681007662142304123147191501791208619526187183814846161243581189122103130193881672589105741412831598

20、21991351273160203169134393151107115176943484183904712142124144771121499713616412758432964111201592180483775554420610104981721715972081381581266817545174013753569315370166321961251318210919716184110187661061502117315718120413914589146102154114401512071551401851081174101113194119123表8 人工干预后完整图片拼接结果495

21、465143186257192178118190951122129289118814161197867699916296131796311616372617720523616810076621423041231471915017912086195261871838148461612435811891221031301938816725891057471156831322001780332021981513317020585152165276014128315982199135127316020316913439315110711517694348418390471214212414477112

22、1499713616412758431251318210919716184110187661061502117315718120413914529641112015921804837755544206101049817217159720813815812668175451740137535693153701663219689146102154114401512071551401851081174101113194119123本问所需程序见附录二，最终所得完整图片见附录一英文文件拼接英文文件拼接与中文类似，建立模型相同，用同样方法对图片进行预处理，用边缘灰度相似性分别找出完整图像左右边界的图片。

23、英文四线格特点：三格等宽；英文书写特点：任一字母不论大小写书写时中间格均上下顶格占用。因此可根据左边界11张图片中每行英文字母中间格的位置与宽度对剩余图片进行分类拼接匹配。匹配标准：1）整行拼接的图片，每行英文字母中间格所处位置与宽度完全相同，绝对误差为0；2）整行拼接的图片，两图片拼接处边缘灰度相似性最高。同时满足以上条件才能对图片进行成行拼接。注意：成行拼接过程中，每个图片只可归于一行进行拼接。拼接过程中，计算机并不能将图片完全正确拼接，因此需要进行人工干预，本次拼接过程中人工干预两次，分别为：1）将每行图片进行匹配拼接后，整行图片拼接顺序有错误，需要人工干预进行调整，得出正确排列顺序。2

24、）整行图片正确拼接后，上下边缘拼接过程中，出现排列错误，因此需要人工干预调整出正确的上下拼接顺序。最终完整图片拼接结果见下表：表9 附件四英文碎片19175111541901842104180641064149322046539671472011481701961989411316478103918010126100617281468651107294015818698241171505595892303746127191949314188121126105155114176182151225720271165821591391129631381535338123120175855016018

25、79720331204110811613673362071351576431994517379161179143208217496111933142168621695419213311818916219711270846014681741371958471721569623991229018510913218195691671631661881111442063130341311025271781714266205101577414583134551856351691831524481771282001315212514019387894872121771240102115Matlab程序见附

26、录二，最终所得完整图片见附录一。问题三算法模型的建立模型求解89a10b36a76b178a44a25b192a124b22a120b144a79a14a59a60b147a152a5a78b111b125a140a155a150a183b174b110a66a108a18b29a189b81b164b20a47a136b186b153a84b42b30a38a121a98a94b61b137b45a138a56b131b187b86b200b143b199b11b161a169b194b173b206b156a34a181b198b87a132b93a72b175a97a39b83a88b1

27、07a149b180a37b191a65b115b166b1b151b170b41a70b139b2a162b203b90a114a184b179b116b 207a58a158a197a154b28b12a17b102b64b208a142a57a24a13a146a171b31a201a50a190b92b19b16b177b53b202a21b130a163a193b73b159a35a165b195a128a157a168a46a67a63b75b167a117b8b68b188a127a40a182b122a172a3b7b85b148b77a4a69a32a74b126b176a1

28、85a0b80b27a135b141a204b105a23b133a48a51b95a160b119a33b71b52a62a129b118b101a15b205a82b145a9b99a43a96b109a123a6a104a134a113a26b49b91a106b100b55b103a112a196b54b5b152b147b60a59b14b79b144b120a22b124a192b25a44b178b76a36b10a89b136a47b20b164a81a189a29b18a108b66b110b174a183a150b155b140b125b111a78a143a200a86a

29、187a131a56a138b45b137a61a94a98b121b38b30b42a84a153b186a83b39a97b175b72a93b132a87b198a181a34b156b206a173a194a169a161b11a199a90b203b162a2b139a70a41b170a151a1a166a115a65a191b37a180b149a107b88a13b24b57b142b208b64a102a17a12b28a154a197b158b58b207b116a179a184a114b35b159b73a193a163b130b21a202b53a177a16a19a9

30、2a190a50b201b31b171a146b172b122b182a40b127b188b68a8a117a167b75a63a67b46b168b157b128b195b165a105b204a141b135a27b80a0a185b176b126a74a32b69b4b77b148a85a7a3a9a145b82a205b15a101b118a129a62b52b71a33a119b160a95b51a48b133b23a54a196a112b103b55a100a106a91b49a26a113b134b104b6b123b109b96a43b99b六、模型评价与推广6.1模型评价优

31、点：将碎片拼接问题进行数字化转化，提取图片特征，方便快捷，对所提取的特征进行一系列的数学分析，并通过相关软件进行分类匹配等过程，大大减少了工作时间，提高工作效率。缺点：模型建立简单，碎片特征提取相对较少，人工干预次数较多。6.2模型推广由以上建模求解过程可知，碎片拼接过程并不能完全实现自动化，同时需要进行若干次的人工干预以求得到最佳结果。本题模型对具有形状规则、色彩特征明显等可准确提取碎片特征的的理想化碎片进行拼接时是较为高效有用的，但是对于不规则具有其他不明显特征的碎片拼接就不适用，此时需要在此模型的基础上对算法等进行改进，以求得到最佳拼接结果。七、参考文献 1 汪冬华，多元统计分析与SPS

32、S应用，上海：华东理工大学出版社，2010.9。 2 杜杰，两种基于灰度的快速图像匹配算法，学位论文，2007.3。参考文献中网上资源的表述方式为：编号 作者，资源标题，网址，访问时间（年月日）。附录一 碎片还原图图一 附件一还原图图二 附件二还原图图三 附件三还原图图四 附件四还原图问题一：1.将图片转化成像素灰度值clcclearfor i=1:19 x(:,:,i)=imread('m',num2str(i),'.bmp');endfor j=1:19 a(:,j)=x(:,1,j);endfor k=1:19 b(:,k)=x(:,72,j);end2.

33、将灰度值二值化并进行图片相邻拼接clccleara=load('e:bisaidutuzuo1.txt')b=load('e:bisaidutuyou1.txt')n=0;% t21=zeros(1,2)for j=1:19 for i=1:1980 if a(i,j)<255 a(i,j)=1; else a(i,j)=0; end if b(i,j)<255 b(i,j)=1; else b(i,j)=0; end end end %灰度二值化处理 for j=1:19 for k=1:19 for i=1:1980 p=a(i,j)-b(i,k

34、); if p=0 n=n+1; end %比较计数 end %第一循环结束 t(k)=n n=0; %相似度 end %第二循环结束 t1=max(t); t21=find(t=t1); t2(j)=t21(1); if length(t21)>1 t3(j)=t21(2); end t=;end问题二程序clccleara1=dir('e:/bisai/tupian3');a11=struct2cell(a1)'k1=a11(:,1);for i=1:209a2=strcat('e:/bisai/tupian3/',k1(i+2,1);a3=c

35、ell2mat(a2);a4=imread(a3);z(1:180,i*72-71:72*i)=a4(:,:);x1(i,:)=sum(a4');endfor i=1:209 for j=1:180 if x1(i,j)=255*72 x1(i,j)=0; else x1(i,j)=1; end endendfor i=1:180 for j=1:15048 if z(i,j)<255 z(i,j)=1; else z(i,j)=0; end endendaa3=load('e:bisaia3.txt')aa4=load('e:bisaia4.txt

36、9;)n=1;pin(:,1)=aa3(:);n1=1; for p=1:18for i=1:11 hw=; for j=1:209 aa(:,1)=z(1:180,pin(i,n1)*72);biaozhun=x1(pin(i,n1),:); xx1=; hw1=1;hw=;for xx=2:180 if biaozhun(xx)=0&&biaozhun(xx-1)=1 hw(hw1)=xx; hw1=hw1+1;endif biaozhun(xx)=1&&biaozhun(xx-1)=0&&length(hw)>0 hw(hw1)=xx

37、-1; hw1=hw1+1;endendif length(hw)=2|length(hw)=3 if sum(x1(j,hw(1):hw(2)<5 if find(pin=j)>=1; else for jj=1:180 kk(jj)=aa(jj)-z(jj,j*72-71); end if n1<18 if find(aa4=j)>=1; else nn(n)=sum(kk'); nn1(n)=j; n=n+1; end end if n1=18 nn(n)=sum(kk'); nn1(n)=j; n=n+1; end end endendif length(hw)=4|length(hw)=5 if sum(x1(j,hw(1):hw(2)<