2013年建模竞赛试卷碎纸片的拼接复原

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

2、书籍、期刊和其他进行正式或非正式等）。参赛选择的题号是（从 A/B/C/D 中选择一项填写）：B 的参赛报名号为（如果赛区设置报名号的话）：08060 所属学校（请填写完整的全名）：哈尔滨工程大学 参赛队员 (打印并签名) ：1.2.3.支(打印并签名)：指导教师或指导教师组（纸质版与中的以上信息必须一致，只是中无需签名。以上内容可能被取消评奖资格。）请仔细核对，提交后将不再允许做任何修改。如填写错误，日期： 2013 年 9 月 16日赛区评阅（由赛区评阅前进行）：2013 高教社杯大学生数学建模竞赛页赛区评阅（由赛区评阅前进行）：赛区评阅（可供赛区评阅时使用）：（由赛区送交前）：评阅（由评

3、阅前进行）：评阅人评分备注碎纸片的拼接复原摘要本文了碎纸片如何复原。根据对碎纸片拼接复原进行建模分析，通过利用灰度矩阵以及图像匹配技术来实现图像融合、图像校正、图像镶嵌以及目标识别与，应用在图像识别以及图像重建中。如何自动提取稳定可靠的特征，提高匹配准确度是实 现图像匹配的重要环节，基于像素的方法直接比较两幅图像之间像素的灰度值，认为相同部分的像素灰度差值应该相等，如果相等超过一定比值他俩就拼接在一起。这种方法简单直观。基于此，针对问题提出以下解决方案：问题一：根据题中所给要求以及附件 1、2 中的碎纸片图像，利用图像矩阵化的将图像的像素点的灰度值利用矩阵表示出来，并且进行二值化处理，使得黑色

4、对应生成的矩阵中 0 是表示黑色，255 代表白色。忽略中间灰度过渡阶段，并且对图片像素点的灰度值做近似处理：当 x150 时，x=0。然后利用算法进行拼接，当匹配度达到 90%以上时两张纸片就是拼接在一起的。问题二：由于附件三、四中给的碎纸片横切纵切而得，故要对问题一的处理方法就要改进，有可能会切到行间，使得很多边缘的像素点的灰度值都是 255，则给问题的解决带来了很大的。故采用分治的算法与极度空间取值方法 ，首先人工干预找进行拼接，拼成的 11到边角碎纸片然后利用问题一的思路进行边缘匹配，以行为个横条，然后将这 11 个横条拼接成整张。问题三：纸片是两面的，并且是由横切纵切而得。依然采用灰

5、度矩阵的模型与二值化，分治算法，为了提高复原的准确度，引入变量“准确度” ，用于表示碎片边缘像素点匹配的概率，验证拼接是否正确。不正确的话则进行分工干预，达到最优复原效果。：灰度矩阵二值化像素点匹配度一、 问题重述1.1 问题背景破碎文件的拼接在司法物证复原、历史文献修复以及军事获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。还可以将此技术用于历史等领域，因此对于此技术的研究就有了重要意义。1.2 需要解决还原1. 对于给定的来

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

7、附件的碎片数据给出拼接复原结果，结果表达要求同二、问题分析拼接碎片前需对碎片内图像进行二值化处理，一般利用 sobel 梯度算子或其他梯度算子对碎片图像进行处理，以获取字边界，进而获取碎片内文字行方向、高度、间距等文字行征，梯度大于给定阈值的点取黑色，否则取白色，为提高分析的准确性，假设未碎纸张的文字行方向沿水平方向，文字为汉字，汉字与汉字之间有间隔，汉字宽度与高比值 133。这意味着每个文字图像与其他文字图像之间空白点，文字图像宽度与高度的比值在 133 之间，如果碎内有西文单词，应将英文单词图像拆分成类汉字图像，即将文单词图像分割成宽度与高度近似的类汉字图像，同样如汉字图像之间靠得非常紧密

8、，以至于行内汉字之间黑点互邻接，需删除汉字图像之问过多黑点。问题一：对这类边缘相似的碎纸片的拼接，理想的计算机拼接过程应与人工拼接过程类似，即拼接时不但要考虑待拼接碎纸片边缘是否匹配，还要判断碎片内的字迹断线或碎片内的文字内容是否，然而由于理论和技术的限制，让计算机具备类似人那种识别碎片边缘的字迹断线、以及理解碎片内文字图像含义的智能几乎不太可能。、图像数字化：利用灰度共生矩阵表示图像。、图像预处理：利用图像二值化黑色为 0，白色为 255，忽略中间灰度时，x=255;当过渡阶段，并且对像素点的灰度值做近似处理：当时，x=0。那么生成的矩阵在匹配过程中就简便了很多。（3）、图像拼接：利用表示的

9、矩阵编写算法，利用阈值分割法，使得两张纸片的相对像素点达到 1800 以上就自动拼接。问题二：由于此问题涉及到横切，有可能会切到行间，很多边缘的像素点的灰度值都是 255，则给问题的解决带来了很大的。故采用分治的算法，首先以为进行拼接，拼成的 11 个横条，然后将这 11 个横条拼接成整张行 在 出，的算法 问题三：。实际问题中边角纸片最容易辨别，基于此手动将 4 个边角的碎纸片找利用问题一的，将碎纸片矩阵化，利用阈值分割法以及图像二值化开始进行匹配。此问题中的碎片来自两个面，并由横切和纵切获得，复原难度较大。采用模型一、二中的算法，在此不作详细介绍。可以考虑从纸的一面入手，当一面成功后，另一

10、面自然也就拼接成功，由此可降低问题的难度。拼接三、模型建立与求解3.1 模型一3.1.1 模型假设1、假设纸张边缘光滑，在过程中边缘没有纸屑的损坏与掉落。2、假设纸张边缘规则，如题中所给的边缘都是直线型。3、假设两张纸片相邻一侧边缘的像素点灰度值相同的数目达到 1800 时，就认为这两张纸是拼接在一起的。3.1.2 符号说明V:调整后的颜色值V：调整前的颜色值X:灰度值k：对某个元素的期望值a：输入范围上界值 d：输入范围下界值3.1.3 模型的建立3.1.3.1 碎纸片（仅纵切 19 个碎片）拼接的算法模型一：灰度矩阵模型协方差矩阵的相似行向量.最后,根据一维 DP 匹配计算相似行向量与被匹

11、配协方差矩阵标准行向量之间的匹配距离,度量出两个匹配制片和被匹配制片的相似度。假设 X 是以 n 个标量随量组成的列向量，并且k 是其第 k 个元素的期望值，即，k= E(xk)，协方差矩阵然后被定义为： =E矩阵中的第(i,j)个元素是 xi 与 xj 的协方差。这个概念是对于标量随差的一般化推广量方4. 对于英语碎纸片，当候可以进行人工干预，把以后，很容易发现文章的左右部分颠倒了，这时复原。5.复原的结果：附件一排列号：见附录，顺序如下附件二排列号：3.1.3.2 碎纸片（仅纵切 19 个碎片）拼接的算法优化在之前的算法实现之后，发现会有重复的拼接。因为最左边和最右边都是白色的，在矩阵中的

12、元素都是 255，所以又会进入到循环中。图 2 优化前003006002007015018011000005001009013010008012014017016004008014012015003010002016001004005009013018011007017000006通过的算法，能够完整地拼接复原碎纸片，但仍存在以下缺陷：一是在拼接结果中重复拼接了很多使用过的被拼接的可能。；二是边沿碎纸片空白边沿一端仍然存在对于问题一，由于每张碎纸片只能使用一次，因此，每当找到一对匹配的时，的标记。两张对应的灰度矩阵的（1,1）的灰度设为 50，作为已使用过的在下次匹配前判断两张常拼接。是否有此

13、标记，有则跳过拼接过程执行下一次循环，反之正对于问题二，主要是对边沿纸片的判定。如果某张纸片是边沿纸片，那么采用了扫描灰度矩阵边沿一列的灰度值，并求和，与全白色的情况作比较。若相等，则认为是边沿碎纸条，反之则不是。对于边沿碎纸条，则优化后的效果如下图所示：其在边沿拼接其它碎纸条。图 3 优化后3.2 模型二3.2.1 模型假设1、假设纸张边缘光滑，在过程中边缘没有纸屑的损坏与掉落。2、假设纸张边缘规则，如题中所给的边缘都是直线型。3、假设两张纸片相邻一侧边缘的像素点灰度值相同的数目达到 170 时，就认为这两张纸是拼接在一起的。3.2.2 符号说明:正态分布的标准差：方差I(x,y )：待处理

14、的图像 G(x,y,)：均值，为 0*：卷积运算3.2.3 模型的建立与碎纸片（横、纵切 1119 个碎片）拼接算法的实现模型二：运用分治的算法，将问题分解为两部分进行。首先以行为进行拼接，拼成的 11 个横条，然后将这 11 个横条拼接成整张。1人工找出原图左侧一列的纸条，然后以以行为，运用问题一中的算法，完成每一行的拼接。由于一张碎纸条边缘一纵列的像素点总数较少，因此到 95%才将两张纸条进行拼接。拼接结果如下（任意一行）：设定当匹配率达2.利用边缘获取的方法，开始拼接列的纸片。当遇到在行间切开使得拼接错误时就人工干预，利用人的逻辑与判断能力选择正确的拼接方式。3. 在图像中常用的二维函数

15、定义如下：G(x,y,)=附件 3 排列号附件 4 排列号1911750111541901840021041800641060041490322040650390671472011481701961980941131640781030910801010261000060170281460860511070290401581860980241171500050590580920300370461270191940931410881211261051551141761821510220572020711650821591390011290631381530530381231201750850501

16、601870972033010200411081161360730362071350150760431990451730791611791432080210070490611190331421680621680541921331181891621971120490540651431860020571921781181900950110221290280911881410610190780670690991620961310790631161630720061770200520361681000760621420300410231471910501791200861950260010870180

17、381480461610240350811391221030250080091050740141280031590821990350120731602031691340390310511071151760940340841830900471210421241440771121490971361641270580431250131821091970161841101870661061500211731571812341391450290641111920050921800480370750550442060101040981781710590072081381581260681750451740

18、001370530560931530701660321960711560831322000170980332021980151331702050851521650270600891461021541140401512071551441851081170041011131941791233.3 模型三3.3.1 模型假设1、假设纸张边缘光滑，在过程中边缘没有纸屑的损坏与掉落。2、假设纸张边缘规则，如题中所给的边缘都是直线型。3、假设两张纸片相邻一侧边缘的像素点灰度值相同的数目达到 170 时，就认为这两张纸是拼接在一起的。3.3.2 符号说明：像素点匹配准确度temp：像素点匹配计数点3.3.3

19、 模型的建立碎纸片（正横、纵切 1119 个碎片）拼接算法实现对于模型三，依旧使用灰度矩阵算法，在此不作详细介绍。与模型一，二不同的是，模型三的碎纸片是两个面的。于是，首先分别拼接一个面。由于碎片是横切和纵切所得，横切的时候会切到段间或行间，由算法所得的拼接完的会有偏差，在此引入准确度 这个概念。碎片形成的矩阵的有 180 行，在程序中用变量 temp计算碎片边缘的像素点匹配的个数。于是准确度为：=/180再调用 Max 函数计算出 的最大值。当 最大时进行匹配。在拼接好一面后，另一面的碎片顺序已知。此时，算出这一面的所有 值。如若出现某个 值很小，则进行人工干预，在 小处的碎片进行重新拼接，

20、拼接后在计算 。如此循环往复，直至找的一种拼接结果，此时所有的 值都很大（90%以上）。至此，碎片拼接结束。附件 5 排列号070084060014068174137195008049172156096023099122090185109132181095069167163166188111144206002130034013110025027178171042066205010157074145083134055018056035016009183152044081077128200131052125140193087089048072012177124000102115四、模型的评价与改进

21、4.1 模型的评价4.1.1 模型的优点（1）在考虑每个碎纸片拼接问题时突出重点，大胆忽略次要问题更加明了，清楚；，使得所研究的所建模型常见模型或常见模型的改进，而且算法简单，易于理解和应用；算法简单，模型误差较小，具有较高的稳定性和较强的实用性；在拼接过程中136b47a20a164b81b189b29a18b108a66a110a174b183b150a155a140a125a111b78b5a152a147a60b59a14a79a144a120b22a124b192a25b44a178a76b36a10b89a143b200b86b187b131b56b138a45a137b61b94b98a121a38a30a42b84b153a186b83a39b97a175a72b93a132b87a198b181b34a156a206b137b194b169b161a11b199b90a203b162b2a139b70b41a170b151b1b166b115b65b191a37b180a149b107a88b13a24a57a142a208a64b