868编号碎纸片的拼接复原算法及MATLAB实现

《868编号碎纸片的拼接复原算法及MATLAB实现》由会员分享，可在线阅读，更多相关《868编号碎纸片的拼接复原算法及MATLAB实现（36页珍藏版）》请在金锄头文库上搜索。

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

2、赛章程和参赛规则，以保证竞赛的公正、公平性。如有 违反竞赛章程和参赛规则的行为，我们将受到严肃处理。 我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展 示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等） 。 我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 楚雄师范学院 参赛队员 (打印并签名) ：1. 陈志明 2. 施明杰 3. 阮秀婷 指导教师或指导教师组负责人 (打印并签名)： （论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。以上内容

3、请仔细核对， 提交后将不再允许做任何修改。 如填写错误， 论文可能被取消评奖资格。） 日期： 3013 年 9 月 16 日 赛区评阅编号（由赛区组委会评阅前进行编号）： 2013 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 编编 号号 专专 用用 页页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 1 碎纸片的拼接复原算法及 MATLAB 实现碎纸片的拼接复原算法及 MATLAB 实现 摘要：摘要：对于只有纵切的情形，

4、文章通过比较当前待拼碎片与剩余碎片的信噪比 psnr1,3,4的值来确定两碎片是否为邻接碎片；拼接算法首先连续调用右拼函数直到拼接 到原图右边界， 然后连续调用左拼函数直到拼接到原图左边界， 从而得到整幅复原图像 ； 对于单面纵横交错切的情形，文章对首先采用纵切拼接算法将碎片拼接成多幅横条图 片，然后将各横条图片矩阵转置2，再次采用纵切拼接算法拼接；两种情形的拼接，都 存在人为参与；实验证明，我们的算法对纵切情形是有效的，对纵横切情况是可行的。 关键字：关键字：纵切；单面纵横交错切；双面纵横交错切；信噪比；左拼函数；右拼函数； 矩阵转；Matlab5编程 2 一、问题描述一、问题描述 破碎文件

5、的拼接在司法物证复原、 历史文献修复以及军事情报获取等领域都有着重 要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当 碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图 开发碎纸片的自动拼接技术，以提高拼接复原效率。请讨论以下问题： （1）对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切） ，建立碎纸 片拼接复原模型和算法，并针对附件 1、附件 2 给出的中、英文各一页文件的碎片数据 进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。复原 结果以图片形式及表格形式表达。 （2）对于碎纸机既纵切又横切的情形，请设

6、计碎纸片拼接复原模型和算法，并针 对附件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程 需要人工干预，请写出干预方式及干预的时间节点。复原结果表达要求同上。 （3）上述所给碎片数据均为单面打印文件，从现实情形出发，还可能有双面打印 文件的碎纸片拼接复原问题需要解决。 附件 5 给出的是一页英文印刷文字双面打印文件 的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件 5 的碎片数据给 出拼接复原结果，结果表达要求同上。 二、拼接中存在的几个主要问题及解决方案二、拼接中存在的几个主要问题及解决方案 为了将碎片拼接成一幅完整的图片，需要解决的问题有以下几个方

7、面： （1） 如何判断两个碎片是否为相邻碎片？ （2） 如何控制两两拼接的循环执行直至拼接完成？ （3） 如何判断碎片是否为边界碎片？ （4） 如果碎片的某个边界刚好完全是空白， 则将其判断为原图的边界还是相邻文字的 空隙？ （5） 对于既有纵切又有横切的单面图片，如何拼接？ （6） 对于对于既有纵切又有横切的双面图片，如何拼接？ 针对上述问题，我们给出以下解决方案： 1问题（1）的解决方案1问题（1）的解决方案 为了减少计算量和便于处理，我们将原灰度图像转换成二值图像，此转换不影响文 字类图片的质量，也不会影响拼接效果。 一般而言，相邻碎片的边缘都具有很强的相似性，我们通过判断碎片矩阵的对应

8、边 界列的相似程度来确定两矩阵存储的碎片是否为相邻碎片。 为了确定两列向量的相似程 度，我们利用其信噪比值 psnr 来衡量，psnr 的值越大，说明两者的相似程度越高。在 拼接过程中可能会存在这种现象：也许存在多幅待拼碎片与已拼图片的信噪比相同，为 了从中选择一幅正确的碎片作为当前碎片的邻接碎片， 我们可以人为介入从语义上进行 3 判断。也有可能待拼碎片与已拼图片的信噪比大，但是并不是已拼图片的邻接图片，反 而次小信噪比的碎片是邻接碎片。 这是因为用信噪比去衡量邻接碎片边缘的相似度也存 在概率性误差。对于以上两种情况，我们都需要在程序运行期间进行人工干预，即程序 在拼接时需要与用户进行交互。

9、思想如下：拼接函数 f2()和 f3()拼接时都会将当前已 拼图片与所有待拼碎片的信噪比进行求解，并将所得信噪比序列存入一维数组中，然后 通过排序函数 paixu2()进行自小而大的排序， 然后通过循环控制， 从已排序数组的最后 一个元素逐个向前尝试，每尝试一次都要与用户交互，用户根据图片语义判断拼接正确 与否，如果正确，则给出YES的输入，程序终止拼接 ； 如果否，则给出NO的输入， 程序继续尝试剩余碎片，直到找到正确邻接碎片为止。实验证明，用该种方法对单纯纵 切碎片的情况非常有效。 2问题（2）的解决方案2问题（2）的解决方案 在拼接的过程中，需要考虑如下几种情况： 如果选取的第一幅碎片刚

10、好是原图的左侧边缘碎片，则只需要在其右侧进行拼 接，直到完毕。 如果选取的第一幅碎片刚好是原图的右侧边缘碎片，则只需要在其左侧进行拼 接，直到拼接完毕。 如果选取的第一幅碎片刚好是原图的内部某一碎片， 则既要进行右侧拼接， 又要 进行左侧拼接。 针对以上三种情况， 我们编写了两个拼接函数， 其中函数 f2()实现两碎片的右侧拼 接，函数 f3()实现两碎片的左侧拼接。通过反复调用两函数实现整幅图的拼接。为了确 定是选择函数 f2()还是函数 f3()，依照以下思路进行： 从所有碎片中首先选择一个碎片，判断其是否为右侧边缘碎片，如果否，则对其进 行右侧拼接，则反复调用右拼函数 f2()，直到右边

11、缘，然后再调用左拼函数 f3()进行 左拼，直到左边缘；如果是，则直接调用左拼函数 f3()进行左拼，直到左边缘。 3问题（3）的解决方案3问题（3）的解决方案 在拼接过程中需要判断是否已经拼接到原图的边缘，为了解决该问题，我们在设计 函数 f2()和 f3()时，分别用它们的返回值的一个分量来标志是否调用成功。如果函数 按 psnr 的逆序试了所有剩余碎片都未能找到合适的碎片，说明当前待拼图片是边界图 片， 此时返回值分量 flag 的值为 0，否则返回 1。 4问题（4）的解决方案4问题（4）的解决方案 对于此种情况可以不做特殊处理，只需要调用拼接函数 f2()或 f3()进行拼接。如 果

12、刚好是边界，而剩余碎片个数为 n，则人机交互 n 次才能判断该图片为边界碎片，而 且人为根据语义做出判断时，也浪费了很多精力。为了避免该情况发生，我们将边界完 全为空白的情况处理为边界。也可以在程序中直接把该处理对应的代码去掉，其余代码 4 不需做任何改动，不足是增加了人工干预次数。当然，我们假定，在纵切时没有刚好完 全切在空白处的情况，否则程序会给出错误的结果。程序实现时，具体处理方法如下： 以 f2()为例， 首先测试碎片矩阵的大小， 如果该碎片矩阵的右侧边界分量各元素值的和 与碎片的行数之差小于一个阀值，我们就认为该碎片为边缘碎片，停止拼接。因为碎片 已被处理为二值图像，在二值图像中，白

13、色像素值为 1，黑色像素值为 0，而边缘通常 是纯白的，在考虑有极少杂色的情况下，我们给了一个阀值。左侧边缘判定方法一样。 5问题（5）的解决方案5问题（5）的解决方案 对于既有纵切又有横切的图片，我们按如下思想进行拼接：利用纵切图片的拼接思 想首先将碎片拼接成多个横条图片，然后将每个横条图片的矩阵进行转置，最后再次利 用纵切拼接思想对横条图片进行拼接，拼接完毕后，将得到的最终矩阵进行转置，最终 得到整幅图片。在实现过程中，存在以下细节需要处理： 整个过程中需要多次调用纵切拼接函数将碎片拼接成多个横条图片，所以，需要在每次 成功拼接一个横条图片时将当前已参与拼接的碎片从剩余碎片中分离出来， 这

14、就需要用 到分离函数 ff()。 6问题（6）的解决方案6问题（6）的解决方案 单面纵横切的算法和思想完全可以拓展到双面纵横切的情形，区别在于：在将所有 碎片拼接成横条形图片后，再进行横条拼接时要产生两幅图像。为了能生成两幅图像， 需要在单面纵横切拼接算法的基础上做以下处理：在拼接过程中要将参与拼接的图片与 剩余图片分离出来；从一个图片开始拼起，如果遇到两个边界都已经找到了，说明第一 个图片已经拼接完毕，然后再将剩余碎片拼接成另一面图像。因时间关系，我们未能编 程实现。 三、Matlab 编程实现拼接算法中的几个功能模块及调用关系三、Matlab 编程实现拼接算法中的几个功能模块及调用关系 整

15、个问题解决方案的实现代码分成以下几个功能模块： （1） read1()函数 ： 将待处理碎片集附件 1读入一个三维矩阵中，程序中设置的默 认读取路径是 d:盘根目录，所以，需要把待拼碎片文件夹放在该路径下。 （2） read2()函数：将待处理碎片集附件 2读入一个三维矩阵中，其余同上。 （3） read3()函数：将待处理碎片集附件 3读入一个三维矩阵中，其余同上。 （4） read4()函数：将待处理碎片集附件 4读入一个三维矩阵中，其余同上。 （5） f2()函数：按右拼方法实现两个单面纵切碎片的拼接。 （6） f3()函数：按左拼方法实现两个单面纵切碎片的拼接。 （7） paixu2(

16、)函数：实现 psnr 序列的排序。 （8） psnr()函数：求解两个碎片矩阵的边界列向量的信噪比值。 （9） pinjie1()函数：实现对附件 1 单面纵切图片的拼接。 （10）pinjie2()函数：实现对附件 2 单面纵切图片的拼接。 （11）pinjie3()函数：实现对附件 3 单面纵横交错切所得碎片的拼接。 5 （12）pinjie4()函数：实现对附件 4 单面纵横交错切所得碎片的拼接。 （13）ff()函数：对于单面纵横交错切的情形，将参与拼成横条图片的碎片从当前碎片 集合中筛掉。 上述几个函数之间的调用关系是： 对只有纵切的情形，直接调用 pinjie1()函数、pinjie2()函数