1、碎纸片的拼接复原算法及MATLAB实现2013高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛
2、的公正、公平性。如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 楚雄师范学院 参赛队员 (打印并签名) ：1. 陈志明 2. 施明杰 3. 阮秀婷 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容请仔细核对，提交后将不再允许做任何修改。如填
3、写错误，论文可能被取消评奖资格。） 日期： 3013 年 9 月 16 日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原算法及MATLAB实现摘要：对于只有纵切的情形，文章通过比较当前待拼碎片与剩余碎片的信噪比psnr1,3,4的值来确定两碎片是否为邻接碎片；拼接算法首先连续调用右拼函数直到拼接到原图右边界，然后连续调用左拼函数直到拼接到原图左边
4、界，从而得到整幅复原图像；对于单面纵横交错切的情形，文章对首先采用纵切拼接算法将碎片拼接成多幅横条图片，然后将各横条图片矩阵转置2，再次采用纵切拼接算法拼接；两种情形的拼接，都存在人为参与；实验证明，我们的算法对纵切情形是有效的，对纵横切情况是可行的。关键字：纵切；单面纵横交错切；双面纵横交错切；信噪比；左拼函数；右拼函数；矩阵转；Matlab5编程一、问题描述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的
5、自动拼接技术，以提高拼接复原效率。请讨论以下问题：（1）对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。（2）对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。（3）上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印文件的
6、碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果，结果表达要求同上。二、拼接中存在的几个主要问题及解决方案为了将碎片拼接成一幅完整的图片，需要解决的问题有以下几个方面：（1）如何判断两个碎片是否为相邻碎片？（2）如何控制两两拼接的循环执行直至拼接完成？（3）如何判断碎片是否为边界碎片？（4）如果碎片的某个边界刚好完全是空白，则将其判断为原图的边界还是相邻文字的空隙？（5） 对于既有纵切又有横切的单面图片，如何拼接？（6） 对于对于既有纵切又有横切的双面图片，如何拼接？ 针对上述问题，
7、我们给出以下解决方案：1问题（1）的解决方案为了减少计算量和便于处理，我们将原灰度图像转换成二值图像，此转换不影响文字类图片的质量，也不会影响拼接效果。一般而言，相邻碎片的边缘都具有很强的相似性，我们通过判断碎片矩阵的对应边界列的相似程度来确定两矩阵存储的碎片是否为相邻碎片。为了确定两列向量的相似程度，我们利用其信噪比值psnr来衡量，psnr的值越大，说明两者的相似程度越高。在拼接过程中可能会存在这种现象：也许存在多幅待拼碎片与已拼图片的信噪比相同，为了从中选择一幅正确的碎片作为当前碎片的邻接碎片，我们可以人为介入从语义上进行判断。也有可能待拼碎片与已拼图片的信噪比大，但是并不是已拼图片的邻
8、接图片，反而次小信噪比的碎片是邻接碎片。这是因为用信噪比去衡量邻接碎片边缘的相似度也存在概率性误差。对于以上两种情况，我们都需要在程序运行期间进行人工干预，即程序在拼接时需要与用户进行交互。思想如下：拼接函数f2()和f3()拼接时都会将当前已拼图片与所有待拼碎片的信噪比进行求解，并将所得信噪比序列存入一维数组中，然后通过排序函数paixu2()进行自小而大的排序，然后通过循环控制，从已排序数组的最后一个元素逐个向前尝试，每尝试一次都要与用户交互，用户根据图片语义判断拼接正确与否，如果正确，则给出YES的输入，程序终止拼接；如果否，则给出NO的输入，程序继续尝试剩余碎片，直到找到正确邻接碎片为
9、止。实验证明，用该种方法对单纯纵切碎片的情况非常有效。2问题（2）的解决方案在拼接的过程中，需要考虑如下几种情况： 如果选取的第一幅碎片刚好是原图的左侧边缘碎片，则只需要在其右侧进行拼接，直到完毕。 如果选取的第一幅碎片刚好是原图的右侧边缘碎片，则只需要在其左侧进行拼接，直到拼接完毕。 如果选取的第一幅碎片刚好是原图的内部某一碎片，则既要进行右侧拼接，又要进行左侧拼接。针对以上三种情况，我们编写了两个拼接函数，其中函数f2()实现两碎片的右侧拼接，函数f3()实现两碎片的左侧拼接。通过反复调用两函数实现整幅图的拼接。为了确定是选择函数f2()还是函数f3()，依照以下思路进行：从所有碎片中首先
10、选择一个碎片，判断其是否为右侧边缘碎片，如果否，则对其进行右侧拼接，则反复调用右拼函数f2()，直到右边缘，然后再调用左拼函数f3()进行左拼，直到左边缘；如果是，则直接调用左拼函数f3()进行左拼，直到左边缘。3问题（3）的解决方案在拼接过程中需要判断是否已经拼接到原图的边缘，为了解决该问题，我们在设计函数f2()和f3()时，分别用它们的返回值的一个分量来标志是否调用成功。如果函数按psnr的逆序试了所有剩余碎片都未能找到合适的碎片，说明当前待拼图片是边界图片， 此时返回值分量flag的值为0，否则返回1。4问题（4）的解决方案对于此种情况可以不做特殊处理，只需要调用拼接函数f2()或f3
11、()进行拼接。如果刚好是边界，而剩余碎片个数为n，则人机交互n次才能判断该图片为边界碎片，而且人为根据语义做出判断时，也浪费了很多精力。为了避免该情况发生，我们将边界完全为空白的情况处理为边界。也可以在程序中直接把该处理对应的代码去掉，其余代码不需做任何改动，不足是增加了人工干预次数。当然，我们假定，在纵切时没有刚好完全切在空白处的情况，否则程序会给出错误的结果。程序实现时，具体处理方法如下：以f2()为例，首先测试碎片矩阵的大小，如果该碎片矩阵的右侧边界分量各元素值的和与碎片的行数之差小于一个阀值，我们就认为该碎片为边缘碎片，停止拼接。因为碎片已被处理为二值图像，在二值图像中，白色像素值为1
12、，黑色像素值为0，而边缘通常是纯白的，在考虑有极少杂色的情况下，我们给了一个阀值。左侧边缘判定方法一样。5问题（5）的解决方案对于既有纵切又有横切的图片，我们按如下思想进行拼接：利用纵切图片的拼接思想首先将碎片拼接成多个横条图片，然后将每个横条图片的矩阵进行转置，最后再次利用纵切拼接思想对横条图片进行拼接，拼接完毕后，将得到的最终矩阵进行转置，最终得到整幅图片。在实现过程中，存在以下细节需要处理：整个过程中需要多次调用纵切拼接函数将碎片拼接成多个横条图片，所以，需要在每次成功拼接一个横条图片时将当前已参与拼接的碎片从剩余碎片中分离出来，这就需要用到分离函数ff()。6问题（6）的解决方案 单面
13、纵横切的算法和思想完全可以拓展到双面纵横切的情形，区别在于：在将所有碎片拼接成横条形图片后，再进行横条拼接时要产生两幅图像。为了能生成两幅图像，需要在单面纵横切拼接算法的基础上做以下处理：在拼接过程中要将参与拼接的图片与剩余图片分离出来；从一个图片开始拼起，如果遇到两个边界都已经找到了，说明第一个图片已经拼接完毕，然后再将剩余碎片拼接成另一面图像。因时间关系，我们未能编程实现。三、Matlab编程实现拼接算法中的几个功能模块及调用关系整个问题解决方案的实现代码分成以下几个功能模块：（1）read1()函数：将待处理碎片集附件1读入一个三维矩阵中，程序中设置的默认读取路径是d:盘根目录，所以，需
14、要把待拼碎片文件夹放在该路径下。（2）read2()函数：将待处理碎片集附件2读入一个三维矩阵中，其余同上。（3）read3()函数：将待处理碎片集附件3读入一个三维矩阵中，其余同上。（4）read4()函数：将待处理碎片集附件4读入一个三维矩阵中，其余同上。（5）f2()函数：按右拼方法实现两个单面纵切碎片的拼接。（6）f3()函数：按左拼方法实现两个单面纵切碎片的拼接。（7）paixu2()函数：实现psnr序列的排序。（8）psnr()函数：求解两个碎片矩阵的边界列向量的信噪比值。（9）pinjie1()函数：实现对附件1单面纵切图片的拼接。（10）pinjie2()函数：实现对附件2单
15、面纵切图片的拼接。（11）pinjie3()函数：实现对附件3单面纵横交错切所得碎片的拼接。（12）pinjie4()函数：实现对附件4单面纵横交错切所得碎片的拼接。（13）ff()函数：对于单面纵横交错切的情形，将参与拼成横条图片的碎片从当前碎片集合中筛掉。上述几个函数之间的调用关系是： 对只有纵切的情形，直接调用pinjie1()函数、pinjie2()函数进行拼接即可。拼接函数pinjie1()函数、pinjie2()函数，首先通过read1()或read2()将纵切碎片读入三维矩阵，然后通过反复调用f2()和f3()实现整副图的拼接。而f2()和f3()实现拼接时需要判断当前待拼碎片与
16、剩余碎片相应边界列向量的信噪比值psnr，并且存入一维数组中，并进行paixu()函数排序。所以，f2()和f3()需要调用psnr()和paixu2()函数。然后在窗口出入pinjie1代码和pinjie2代码进行结果运算。对既有纵切又有横切的情形，直接调用pinjie3()函数、pinjie4()函数即可。该拼接函数是在pinjie1()函数、pinjie2()函数的基础上添加了循环控制，并通过调用ff()函数将已拼碎片与剩余图片进行分离，从而将所有碎片拼成多个条形图片，并通过调用pinjie5()函数将条形图片拼成最终的原图。四、实验结果及分析对只有纵切的情形，直接调用pinjie1()
17、函数和pinjie2()函数分别对附件1和附件2进行拼接即可。拼接函数pinjie1()和pinjie2()在执行过程中，首先分别通过read1()和read2()将纵切碎片读入三维矩阵，然后通过反复调用f2()和f3()实现整副图的拼接。实验结果如附录2中图1和图2所示。结果表明，我们的方法是高效且可行的。对于纵横切的情形，首先在Matlab中对函数read3()和read4()进行调用，从而将附件3和附件4中的碎片读入到三维矩阵中，然后调用函数pinjie3()和pinjie4()分别对两组碎片进行拼接，由于时间关系，程序只拼接出部分横切图片如图3所示。利用psnr作为判断邻接碎片的标准，
18、衡量其好坏，主要是看每成功拼接一次尝试的次数。附件1在拼接过程中人工干预输入yes和no拼接次数的统计表如附录4所示，由附录表中的数据可以得出准确率：，即拼接效果很好。附件2在拼接过程人工干预输入yes和no拼接次数的统计表如附录5所示，由附录的表中的数据可以得出准确率：，即拼接效果很好。五、提高效率的新想法用信噪比psnr作为衡量邻接碎片的标准对多数情况是有效的，判断一到两次就可以确定邻接图片，但对少数情况并不乐观，这样就导致整体算法的效率不高。为了节约拼接时间，可以在原算法的基础上做如下两种改进：（1）在原有算法的基础上做如下调整：在进行横向拼接时，不采用完全拼接，比如，对一条横条图片进行
19、拼接时，在拼的过程中，发现在寻找已拼图片的邻接碎片时总是要进行多次判断，此时，可以通过阀门控制判断次数，比如将最大阀门设为10，则相邻碎片进行拼接时，如果判断10次还未找到其相邻图片，则停止拼接，然后转向另一侧拼接。将每次拼接好的横向图片存在在不同矩阵中，然后再对这些拼接好的大小不等（但是具有相同宽度）的横向图片进行二次拼接，得到完整的横向切片。然后再对这些完整的横向切片按前述的思想进行纵向拼接得到完整的整幅图片。（2）左拼函数和右拼函数判断相邻碎片时是单纯使用信噪比，对少数情况效率较低，此时可以结合均方差一起使用，首先设定一个阀门，比如设为10，如果在使用信噪比进行10次判断时仍然未找到已知
20、图片的邻接碎片，在接下来的搜索中，采用均方差进行搜索。由于时间紧迫，未能来得及编程实现。六、小结本文通过比较当前待拼碎片与剩余碎片的信噪比值来确定两碎片是否为相邻碎片。首先要考虑碎片被切的方向，若只是单一的纵向切，则可以直接拼接；若既有纵切又有横切，则只能先考虑同一方向上的拼接，待完成一个方向的拼接再进行另一方向上的拼接，只能逐步完成拼接过程。文章利用Matlab编写程序，经过检测得到了很好的拼接效果。参考文献1 沈连丰，叶芝慧.信息论与编码.科学出版社，2004年9月.2 王向东，戎海武，数学实验.北京：高等教育出版社，2004年5月.3 王学伟，王春韵，张玉叶.点击图像信噪比计算方法.第1
21、7卷第1期，2010年1月.4陈桂明，张明照，戚红雨.应用Matlab语言处理数字信号与数字图像.科学出版社，2000年. 5刘宏友，彭峰.MATLAB6.x符号运算及其应用.机械工业出版社，2003年2月. 附录1：相关程序代码（1）read1()函数代码function a=read1()a(1,:,:)=dither(imread(d:附件1000.bmp);a(2,:,:)=dither(imread(d:附件1001.bmp);a(3,:,:)=dither(imread(d:附件1002.bmp);a(4,:,:)=dither(imread(d:附件1003.bmp);a(5,:
22、,:)=dither(imread(d:附件1004.bmp);a(6,:,:)=dither(imread(d:附件1005.bmp);a(7,:,:)=dither(imread(d:附件1006.bmp);a(8,:,:)=dither(imread(d:附件1007.bmp);a(9,:,:)=dither(imread(d:附件1008.bmp);a(10,:,:)=dither(imread(d:附件1009.bmp);a(11,:,:)=dither(imread(d:附件1010.bmp);a(12,:,:)=dither(imread(d:附件1011.bmp);a(13,:
23、,:)=dither(imread(d:附件1012.bmp);a(14,:,:)=dither(imread(d:附件1013.bmp);a(15,:,:)=dither(imread(d:附件1014.bmp);a(16,:,:)=dither(imread(d:附件1015.bmp);a(17,:,:)=dither(imread(d:附件1016.bmp);a(18,:,:)=dither(imread(d:附件1017.bmp);a(19,:,:)=dither(imread(d:附件1018.bmp);（2）read2()函数代码function a=read2()a(1,:,:)
24、=dither(imread(d:附件2000.bmp);a(2,:,:)=dither(imread(d:附件2001.bmp);a(3,:,:)=dither(imread(d:附件2002.bmp);a(4,:,:)=dither(imread(d:附件2003.bmp);a(5,:,:)=dither(imread(d:附件2004.bmp);a(6,:,:)=dither(imread(d:附件2005.bmp);a(7,:,:)=dither(imread(d:附件2006.bmp);a(8,:,:)=dither(imread(d:附件2007.bmp);a(9,:,:)=dit
25、her(imread(d:附件2008.bmp);a(10,:,:)=dither(imread(d:附件2009.bmp);a(11,:,:)=dither(imread(d:附件2010.bmp);a(12,:,:)=dither(imread(d:附件2011.bmp);a(13,:,:)=dither(imread(d:附件2012.bmp);a(14,:,:)=dither(imread(d:附件2013.bmp);a(15,:,:)=dither(imread(d:附件2014.bmp);a(16,:,:)=dither(imread(d:附件2015.bmp);a(17,:,:)
26、=dither(imread(d:附件2016.bmp);a(18,:,:)=dither(imread(d:附件2017.bmp);a(19,:,:)=dither(imread(d:附件2018.bmp);（3）read3()函数代码function a=read3()a(1,:,:)=dither(imread(d:附件3000.bmp);a(2,:,:)=dither(imread(d:附件3001.bmp);a(3,:,:)=dither(imread(d:附件3002.bmp);a(4,:,:)=dither(imread(d:附件3003.bmp);a(5,:,:)=dither
27、(imread(d:附件3004.bmp);a(6,:,:)=dither(imread(d:附件3005.bmp);a(7,:,:)=dither(imread(d:附件3006.bmp);a(8,:,:)=dither(imread(d:附件3007.bmp);a(9,:,:)=dither(imread(d:附件3008.bmp);a(10,:,:)=dither(imread(d:附件3009.bmp);a(11,:,:)=dither(imread(d:附件3010.bmp);a(12,:,:)=dither(imread(d:附件3011.bmp);a(13,:,:)=dither
28、(imread(d:附件3012.bmp);a(14,:,:)=dither(imread(d:附件3013.bmp);a(15,:,:)=dither(imread(d:附件3014.bmp);a(16,:,:)=dither(imread(d:附件3015.bmp);a(17,:,:)=dither(imread(d:附件3016.bmp);a(18,:,:)=dither(imread(d:附件3017.bmp);a(19,:,:)=dither(imread(d:附件3018.bmp);a(20,:,:)=dither(imread(d:附件3019.bmp);a(21,:,:)=di
29、ther(imread(d:附件3020.bmp);a(22,:,:)=dither(imread(d:附件3021.bmp);a(23,:,:)=dither(imread(d:附件3022.bmp);a(24,:,:)=dither(imread(d:附件3023.bmp);a(25,:,:)=dither(imread(d:附件3024.bmp);a(26,:,:)=dither(imread(d:附件3025.bmp);a(27,:,:)=dither(imread(d:附件3026.bmp);a(28,:,:)=dither(imread(d:附件3027.bmp);a(29,:,:
30、)=dither(imread(d:附件3028.bmp);a(30,:,:)=dither(imread(d:附件3029.bmp);a(31,:,:)=dither(imread(d:附件3030.bmp);a(32,:,:)=dither(imread(d:附件3031.bmp);a(33,:,:)=dither(imread(d:附件3032.bmp);a(34,:,:)=dither(imread(d:附件3033.bmp);a(35,:,:)=dither(imread(d:附件3034.bmp);a(36,:,:)=dither(imread(d:附件3035.bmp);a(37,:,:)=dither(imread(d:附件3036.bmp);a(38,:,:)=dither(imread(d:附件3037.bmp);a(39,:,:)=dither(imr
