纸片分割还原技术

《纸片分割还原技术》由会员分享，可在线阅读，更多相关《纸片分割还原技术（21页珍藏版）》请在文档大全上搜索。

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

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

3、日期： 2013 年 9 月 16 日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：碎纸片的拼接复原摘要随着电脑的发展，很多问题都可以利用计算机完成，从前，破碎文件的复原，主要是利用人力完成，虽说准确率高，但效率太低，本文根据具体问题，利用计算机复原算法，文件的复原效率得到了很大的提高。针对问题一，由于对应的碎纸，仅是进行了纵切，所以可以利用最小二乘法对两片纸的

4、左右进行匹配，选取匹配程度最大的边，进而复原碎纸，由于碎纸纵向较长，所以匹配非常明显，不需要人工干预，即可完成匹配。附件1、附件2的匹配结果如下：附件18141215310216145913181171706附件23627151811051913108121417164针对问题二，由于对应的碎纸，即有横切又有纵切，所以边界带有信息较少，本文为了较好的同时解决汉字与英文的关系，所以必须经过有效地取舍，并提高匹配精度。随机的取出一个碎片，逐个对其四周进行匹配，依次类推，将大量碎块，合成少量大块，再利用人为干预的方式完成拼合。针对问题三，这时纸片为正反打印，所以增加了匹配的难度，但由于，可同时利用反

5、面进行双重校正，提高了匹配精度，所以，主要利用问题二的解决方式，解决了双面打印纸复原的问题。总之，本文利用高精度的匹配，并充分利用已知的方法，有效地将大量碎片的复原，转化成大块的图形拼合问题，极大地提高了拼图效率。这种做法，可扩展到很多图像拼合问题中去。关键词：匹配 高精度 最小二乘法 图像拼合 文字识别一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上，拼接复原工作需由人工完成，准确率较高，但效率很低。特别是当碎片数量巨大，人工拼接很难在短时间内完成任务。随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率。本文基于此，

6、对给定的碎纸机的破碎纸片进行电脑拼接，同时，在适当的时机进行人工干预，这样既能效率很高，同时又不降低准确率。下面为本文要完成内容：1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。2. 对于碎纸机既纵切又横切的情形，请设计碎纸片拼接复原模型和算法，并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预，请写出干预方式及干预的时间节点。3. 上述所给碎片数据均为单面打印文件，从现实情形出发

7、，还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法，并就附件5的碎片数据给出拼接复原结果。二、问题分析问题一的分析在问题一中，由于碎纸机对纸的纵切具有边界的规整性，所以对碎纸的拼接，主要利用文字的匹配。一般地，文字的匹配，当然首先要对文字识别，但考虑到本题的特征，考虑文字识别将是非常复杂的，现只需考察边界的匹配性即可。因为每条碎纸都是从一页纸上切下的，所以必然会将汉字或字母的笔画割裂，所以文字对应的像素在匹配的两片纸上，笔画一定是连续的。为了匹配的方便，同时由于印刷纸张的特殊性质，首先可利用边界的空

8、白寻找到纸张的最左与最右的小块。由于可匹配的两边，笔画是连续的，即两边对应位置的像素是相近的，也就是说，可用对应位置的像素之差的平方和来表示相似程度，也就是最小二乘法1，和数越小，相似程度越大。问题二的分析在问题二中，纸张被碎纸机，即横切又纵切，所以每块都变得很小，此时，边界较小，特别是，出现了大量的白边的小块，这样必然导致要加入一些人为的干预。此时若像问题一的方法直接匹配，会发现有大量匹配度较高，而且相近的边，这样就使得判断异常艰难。这里，若边界像素较小，即便匹配率较高，也是未必匹配成功，所以必须进行有效的取舍。首先考虑边界像素较大的小块，且将匹配率提高到一个较高的范围。这样才能有效的找到匹

9、配小块。基于此，随机取出一小块，从其上、下、左、右四个方向进行匹配，若有匹配成功项，则将其组合，并且从组合块出发，还是对其各边向四个方向匹配，依次类推，直到所有无法匹配为止。再从剩下的里边随机取一小块，依上述方法进行。这样可得到若干个不规则大块，这时利用人工干预的方式进行拼合即可。此问题中，若利用汉字的字宽进行匹配，势必对英文的匹配造成影响，所以为了两者兼顾，对字宽不予考虑。问题三的分析在问题三中，由于正反面的印刷，使得要匹配的面增加了一倍，则必然增加的判断的难度。但此时也增加了一些匹配条件，即若两块在一面的匹配程度较大，同时翻转过来也具有较高的匹配程度，则匹配成功。所以此题利用问题二的方式，

10、进行双面匹配。这样可以得到若干个不规则大块，最后，利用人工干预的方式进行拼合即可。三、模型假设1.假设碎纸片边缘是整齐的；2.假设拼图人员是认识拼图文章的。四、符号说明 符号含义附件1或2的第个阶的矩阵中的元素的第1列与第72列组成的边界矩阵第块右面与第块的左面匹配函数附件3或4的第个阶的矩阵第块右面与第块的左面匹配函数第块上面与第块的下面匹配函数五、模型的建立与求解5.1问题一对于附件1的图片，利用MATLAB2将碎片读入，得到19个阶的灰度矩阵，由于灰度矩阵的元素为，不容易处理，所以对上述矩阵进行二值化，得到19个汉字的阶的矩阵。记为： （1）取出各边得： （2）这时第块右面与第块的左面匹

11、配函数为： （3）其中越小，匹配程度就越大。利用Matlab进行编程计算（见附录f1.m），首先找到处在左边界的纸条，再向右方进行匹配，得到： 表1：附件1的排序8141215310216145913181171706得到图片：图1：附件1的文章同理，利用上面程序对附件2进行处理，得到：表2：附件2的排序3627151811051913108121417164得到图片：图2：附件2的文章5.2问题二 对于附件3的图片，利用MATLAB将碎片读入，得到209个阶的灰度矩阵，由于灰度矩阵的元素为，不容易处理，所以对上述矩阵进行二值化，得到209个汉字的阶的矩阵。记为： （4）这时第块右面与第块的左