《碎纸片的拼接复原论文1.doc》由会员分享，可在线阅读，更多相关《碎纸片的拼接复原论文1.doc（32页珍藏版）》请在三一办公上搜索。
1、高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题.我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性.如有违反竞赛章程和参赛规则的行
2、为，我们将受到严肃处理.我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）.我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（即电子文件名）： B0813 所属学校（请填写完整的全名）： 广西师范大学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期2013年 9 月16日赛区评阅编号（由赛区组委会评阅前进行编号）：高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛
3、区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：纸片的拼接复原摘要 碎纸自动拼接复原技术现今可以归结到计算机视觉和模式识别领域内的问题，它在司法物证复原、历史文献修复等重要领域都起着重要的作用.本文主要分析了文字的拼接技术，通过研究碎纸片内的像素矩阵和文字行特征特点，提出了基于文字图形的半自动拼接算法.对于问题1中的这种单面的仅纵向切碎的文字文件，通过Matlab程序分析附件中每个碎片的像素矩阵，确定拼接的第一个碎片（自左向右拼接），再根据两列像素矩阵的像素绝对差的和来确定相邻碎片的编号，从而得到完整的拼接方案.例如文字文件
4、的拼接结果如下表所示：顺序12345678910111213141516171819编号008014012015003010002016001004005009013018016001004005009对于问题2中既纵切又横切的碎纸片，在问题一的基础上，充分考虑横向匹配和纵向匹配的要求，运用Matlab程序筛选最左列碎片成分，经过适当的人工干预根据文字行特征将所剩碎片进行行分类，大大提高拼接效率，得到意想的效果.例如文字文件的拼接结果如下表所示：顺序12345678910111213141516171819编号003006002007015018011000005001009013010008
5、012014017016004对于问题3，在前两问的基础上，建立筛选附件5碎片图的优化模型，通过Matlab编程，使用附件给的418张碎纸片图，将最终复原图划分为11个碎片横条区域，降低了拼接复原难度以及所需时间.最终复原结果见附录.最后，分析了所建立模型的优缺点以及推广，评价了文字碎纸片的拼接和复原实际情况. 关键词 文字图形碎片 半自动拼接 像素灰度 MATLAB程序 一 问题的重述碎纸自动拼接复原技术是计算机视觉和模式识别领域内的问题.它在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统意义上的拼接复原工作需由人工完成，准确率较高，但效率非常低，特别是当碎片数量巨大
6、时，人工拼接很难在短时间内完成任务.随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率.本文主要讨论：首先，对于给定的来自同一页单面印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，同时对题目中的附件1和附件2给出的中、英文各一页文件的碎片数据进行拼接复原.其次，对于同样是单面印刷文件既纵切又横切的情形，在第一问的基础上设计出碎纸片拼接复原模型和算法，对附件3和附件4给出的中、英文各一页文件的碎片数据进行拼接复原.最后，联系现实中的情况，对还有可能出现双面打印文件的碎纸片进行拼接复原.在前两问的基础上，设计出相应的碎纸片拼接复原模型与算法，并附件5中
7、双面打印文件的碎片数据给出拼接复原结果.在上述复原过程中，由于计算机的识别可能会出现偏差，那么就需要在拼接过程中进行必要的人工干预，在适当的时候我们会用干预的方式给出复原过程.并最终以图片形式及表格形式完成给出复原结果.具体结果在附件中给出.二 问题的分析破碎文件的复原，最直接及最精确的就是人工拼接，但是当碎片的数量巨大时，人工方式就显得效率低下，所以就考虑把破碎文件运用计算机技术来帮助人们进行破碎文件的复原，让计算机在这个过程中发挥主要作用，但是用计算机处理，又不是百分之一百完美，因此在适当的时候也需要进行人工干预.本文运用碎纸片的自动拼接技术，对每个附件给出的碎片文字材料进行分析，尽可能减
8、少人工干预，本文给出的图像数据均为形状、大小一样的规则长四边形，由于形状的一致性，所以在拼接时如果只考虑利用碎片的边界特征，直接拼接，显然效果不理想.考虑到使用计算机的拼接过程应该与人工拼接过程是相类似的，即拼接时不但考虑碎片边缘是否匹配，还要判断碎片内的字迹断线和文字内容是否匹配.然而根据现在已有的技术，实现计算机智能识字是几乎不可能的.但是我们可以获取图片所提供的像素信息，将其转化为矩阵，根据图像的像素矩阵值进行碎片拼接，用计算机去运行处理数据，可以想象其拼接效率无疑比单纯利用边界特征的方法好很多.以下是对各问题的详细分析： 针对问题1，对附件1和附件2提供的数据，每页纸被切为19条碎片，
9、对于这种单面的仅纵向切碎的文字文件，我们仅考虑碎片左右两侧的拼接.首先，在转换中发现，像素图片矩阵的值是介于0到255之间的一个像素矩阵，随着像素矩阵值的增加，我们发现随着像素矩阵数值的增大，所代表的区域越来越浅，最后255这个数值，代表了白色区域.其次，对于问题1中的附件1和附件2图片，由于仅纵向切碎的文字文件，仅考虑碎片左右两侧的拼接.需运用Matlab程序分别对附件1和附件2中的19个碎片计算其像素矩阵，将每个附件中19条图像转换成19个的像素矩阵，筛选出每个像素矩阵的第一列像素矩阵值，然后运用Excel软件统计各列像素值等于255的个数，可以粗略的认为所含255个数最多的列所对应的碎片
10、则是拼接顺序中的左边第一条（如果有必要进行人工干预，但是本文第一问没有进行人工干预）.接下来从左边开始选取第二条碎片，关于第二条待匹配的碎片，用先确定的第一条像素矩阵的最后一列，对其进行数值求和，然后将剩下的18个像素矩阵中的第一列和最后一列矩阵进行分别求和.将首先确定的最左边第一条矩阵中的最后一列矩阵与求出的18个像素矩阵中的第一列矩阵分别进行做差，然后将差值取绝对值，这样就可以得出，如果差值越小，其重叠的相似度也应该相对越高.这样可筛选得出相似度较高的碎片，即与第一个碎片相匹配，该碎片位于拼接顺序的第二条，确定第二条后，再用第二条的最右边矩阵并以此类推，逐一从左到右查询碎片，直到碎纸片的复
11、原结果.针对问题2，在问题1的基础上，继续对所给的附件3和附件4进行分析.针对附件3和附件4的特点，附件3和附件4给出了碎片既横切又纵切的中英文图像，那么在拼接时就有两方面的考虑，既要满足横向匹配，又要满足纵向匹配.那么我们就考虑在问题解决中可以分为两步进行，首先考虑横向拼接，一旦横向拼接完成了，纵向拼接自然相对就好解决了.根据碎片像素矩阵特征和行距特征将其分类，再结合问题1的方法将各类碎片进行匹配，即可得到11个碎片横条.接着考虑纵向拼接，使用Matlab程序对得到的新的横条碎片进行像素分析，比较像素矩阵中第一行数据中255的个数，个数最多的碎片即是原文件的第一行，依次类推，同样的方法即可知
12、道具体的排列顺序，从而得到碎纸片复原的结果.针对问题3，在问题1和问题2的基础上，继续对所给的附件5进行分析.实际生活中存在很多双面打印的文件，这些双面文件的碎纸片混合在了一起，当对其进行拼接复原时，首先要判断同一面的文字碎片，然后再进行拼接.附件5给出了碎片既横切又纵切的英文文字图像，那么在拼接时依旧有两方面的考虑，既要满足横向匹配，又要满足纵向匹配.首先考虑横向拼接，转换得到180x72的像素矩阵，这些是介于0到255之间的一个像素矩阵，随着图片的增加，相应的增多转换得到的像素矩阵，在问题2的基础上继续进行检验所给的碎纸片图，运用Matlab读取了418张碎片图后，将每张碎片转换得的像素矩
13、阵的第一列以及最后一列各自取出，通过程序进行验证，可以算出匹配度高的相邻碎片，此时进行一次人工干预，拼接出位于同一行的碎片横条；接着考虑纵向拼接，运用Matlab程序对得到的新的横条碎片进行像素分析的提取，配准各个横条的像素矩阵的第一行与最后一行的相关度，综合分析碎纸片上英文之间的行距，进而确定拼接的碎片横条位于哪一行，得到最终的复原结果.综上所述，以上三个问题的解决流程可用下面的流程图表示：图2 问题解决流程图三 模型假设准备与符号说明3.1 模型的假设 1、 假设碎纸机把一页印刷文字文件碎成形状规则，大小一样的碎片，看做形状、大小相同的长方形.2、 在碎纸过程中，只考虑文字被切开，不考虑文
14、字笔画的丢失、碎片添加的任何痕迹等.3、 假设文档碎片的文字的方向已经确定（按照阅读标准确定，从左向左右，自上而下），不考虑碎片图像的旋转问题.4、 图片在复原的过程中，不考虑图片像素的改变，只考虑碎片相对应的固定像素值的匹配问题.3.2 模型准备不规则几何文档碎纸片计算机拼接的方法一般利用碎片边缘的尖角特征、尖点特征、面积特征等一些几何特征，搜索与之匹配的相邻碎纸片进行拼接，这种基于边界的几何特征的拼接方法并不适用于边缘的形状相似的碎纸片.对于这类边缘相似的碎纸片的拼接问题，理想的计算机拼接的过程与人工拼接的过程类似，即拼接时不仅要考虑拼接碎纸片的边缘是否匹配，还要判断碎纸片内的文字字迹断线
15、或文字内容是否匹配，但是由于理论和技术的限制，让计算机具备类似于人的的那种识别碎纸片边缘字迹断线、以及理解碎纸片内文字图像的含义的智能几乎是不太可能的.但是利用现在已有的技术，完全可以获取到碎纸片文字所在行的几何特征信息，如文字行的行高及间距等信息.如果利用这些信息进行碎纸片拼接，其拼接的效率就比单纯利用边界的几何特征方法更好.根据本文题设要求，经考虑分析，本文采取转换矩阵数组元素拼接的技术对破碎的文字文档进行拼接复原.由于计算机数字分析图像能力方面的存在一定的缺陷，让计算机对碎纸片进行完全意义上的自动化拼接页几乎是不太可能，为保证其拼接的准确性，需要在拼接的过程中加入一定的人工干扰过程.一般
16、来说，先利用计算机搜索出于目标碎纸片相匹配的未拼接碎纸片，并根据匹配的程度按顺序到得待选的碎纸片，然后人为地进一步分析结果进行舍弃或拼接待选碎纸片3.一页文字文件的碎片拼接复原相当于全景图的生成技术，而相邻图像的配准及拼接是该技术的关键.图像的拼技术一般分为基于图像特征的方法和基于图像灰度的方法.特征提取的方法通常涉及大量的几何与图像形态学的计算，计算量大，没有一般的模型可遵循，但需要针对不同的应用场景来选择各自适合的特征， 所提取的图像特征包括更高层的语义信息，基于特征的方法具有尺度不变性和放射不变形.然而基于图像灰度的拼接方法简单简单易行，并且其数字统计模型以及收敛速度、定位精度等均具有定
17、量的分析和研究结果，此类方法得到了广泛的应用.本文中的文字图像中文字区域的文字结构相对单一，并可能出现相同或相似的字符，因此文字容易出现匹配出现误差.对于文字左右拼接的情况，可以对图片中划分的每行文字进行分析处理，通过提取文字图片的边缘像素矩阵，得到文字出现在图片边缘的那一行高，进一步对一行行的文字拼接复原，这也有利于获取更精确的配准结果.基于文字的图像灰度的方法不需要提取文字图像的相应的特征，只以两幅图像相连接部分对应的像素灰度的相似性准则来寻找图像的匹配位置.待匹配的图像，首先求出图像中最左边一列的像素矩阵值之和，和最右边一列像素矩阵之和。然后定义其相连接的区域的相似度可由像对应的像素灰度
18、平方差之和来衡量，其计算文字图片像素与和所搜索的文字图片像素灰度值的距离4：该方法称为差和法其中分别代表图像各个像素的灰度值，代表各个像素的坐标.其值最小者所对应的位置为最佳的匹配位置.不过，为了减少计算的工作量和评价标准，这里我们定义对应像素的灰度的绝对值之差然后求和去代替原来的像素灰度平方差之和，其计算文字图片像素与和所搜索的文字图片像素灰度值的距离：3.3符号说明相对应的像素绝对差值像素矩阵的像素值第个碎片最后一列与第个碎片第一列的图像矩阵值和的差的绝对值（）点对的欧氏距离和欧式距离和代价误差函数给定的初始值四 模型的建立和求解4.1 问题1的模型与求解对于问题1的解决，主要有以下四个步
19、骤：步骤1 确定像素矩阵运用Matlab程序分别对附件1和附件2中所给出的19张碎片图像进行像素矩阵计算，每个图都对应得到一个的像素矩阵.步骤2 确定左边第一列碎片通过Matlab程序筛选出每个像素矩阵的第一列像素值，运用Excel软件统计各列像素值等于255的个数.运算的结果如下图：图1 附件1碎片最左边像素为255的个数其中横坐标为碎纸片的编号，纵坐标是像素为255的个数。从上表的结果中，筛选出第一列的像素值为255的个数最多的是编号为008的图片，说明编号为008的图片是附件1中碎纸片复原的拼接顺序中位于左边的第1张图片.同理，得到附件2中每个图片的像素矩阵的第一列的像素值为255的个数
20、最多的是编号为003的图片，说明编号为003的图片是附件2中碎纸片复原的拼接顺序中位于左边的第1张图片.步骤3 确定碎片顺序对于本题中出现的形状、大小一样的相邻两块碎片拼接，只需考虑两块碎片灰度的绝对差值3.因此可运用Matlab程序建立以下模型：对于待匹配的图像，像素矩阵像素的像素值，表示行数，为列数，其连接区域的相似度可由相对应的像素灰度绝对差值来衡量，即计算第1张图片的图像矩阵的最后一列的像素值与待匹配图片的图像矩阵的第一列的像素值的绝对差值的总和，计算公式如下：下面先对附件1进行讨论，可通过Matlab程序进行计算得到它们相对应的像素差的绝对值，如下表的结果：表1 附件1碎片008与其
21、他碎片的相素差的绝对值表碎片编号0000010020030040059718111096511688912411210711478601碎片编号006007009010011012111883989831113941015939290198493碎片编号01301401501601701811944627544841251124681162686740根据表1中的数据进行比较，可筛选出与碎片008相对应的像素绝对差值最小的碎片014，即编号为014的碎片能与编号为008的碎片相互匹配重叠，作为拼接顺序的第2张图片.依次类推，按照相同的方法，在Matlab程序依次筛选出位于拼接顺序的第3张图片，
22、第4张图片，第19张图片，从而得到附件1的拼接复原文件（见本文附件一），拼接顺序如下表所示：表2 附件1文件的拼接顺序顺序12345678910111213141516171819编号008014012015003010002016001004005009013018016001004005009同理，计算附件2的第1张图片的图像矩阵的最后一列的像素值与待匹配图片的图像矩阵的第一列的像素值的绝对差值的总和，结果如下表：表3 附件2碎片003与其他碎片的相位差绝对值表碎片编号000001002004005006669776386970269781179226925277碎片编号007008009
23、010011012768838218572522784226580877712碎片编号013014015016017018776588899271768767487462863442从表3的结果可以看出，附件2中得到与碎片003的像素绝对差值最小的碎片编号为006，即编号为006的碎片能与编号为003的碎片相互匹配重叠，作为拼接顺序的第2张图片.以此类推，在Matlab程序依次筛选出位于拼接顺序的第3张图片，第4张图片，第19张图片，从而得到附件2的拼接复原文件（见本文附件二），拼接顺序如下表所示：表4 附件2文件的复原拼接结果顺序12345678910111213141516171819编号
24、0030060020070150180110000050010090130100080120140170160044.2 问题2模型与求解运用Matlab程序对附件3给出的209个碎片图像进行像素矩阵计算，其中每个图像得到一个的矩阵，刷选出209个碎片图像中每个像素矩阵的第一列像素矩阵和最后一列像素矩阵，即2个的像素矩阵.然后对得到209个第一列像素矩阵和最后一列像素矩阵进行列求和.把上述的求和结果转换成一个的矩阵：其中第个碎片最后一列图像矩阵值和与第个碎片第一列的图像矩阵值和的差的绝对值为矩阵中的元素（），比较筛选出矩阵中的第行所有元素的最小的一个，则说明第个碎片的左边与第个碎片的右边相匹配
25、，这样就完成了附件3的横向拼接顺序，得到11个新的横条碎片.接着进行纵向拼接，使用Matlab程序分别对得到的所有新的横条碎片进行像素矩阵计算，筛选出11个碎片图像中每个像素矩阵的第一的像素矩阵.用Excel软件统计各个新横条的像素矩阵中第一行数据中255的个数，得到个数最对的碎片是按如下表的顺寻拼接的横条，即该序列的横条位于纵向拼接顺序的第一个.部分行拼接结果如图2、图3所示：图2 附件3横向拼接复原图（1）图3 附件3横向拼接复原图（2）最后，在对所得新的11个横条处理的问题上，主要有像素矩阵分析法或者直接采用人工干预.由于只有11个横条，并且根据汉字的笔画特征，本文采取用人工干预的方式，
26、对11个横条进行干预，逐一确定，最终得到到附件3的拼接复原结果（见本文附件三、附件四）：表5 附件3部分拼接复原结果顺序12345613141516171819编号049054065143186002011022129028091188141顺序20212223242532333435363738编号061019078067069099163072006177020052036顺序编号顺序172173174175176177184185186187188189190编号071156083132200017170205085152165027060顺序1911921931941951962032
27、04205206207208209编号089146102154114040117004101113194119123同理，运用Matlab程序对附件4中给出的209个横纵交切的英文碎片进行像素矩阵计算.参照附件3同样的思路，首先得到横向拼接顺序的11个新的横条碎片，然后再通过纵向拼接顺序干预逐一得到附件4的复原图，附件4的拼接复原结果如下（详见本文附件五、附件六）：表6 附件4拼接复原结果顺序12345613141516171819编号191075011154190184149032204065039067147顺序20212223242532333435363738编号20124817019
28、6198094101026100006017028146顺序编号顺序172173174175176177184185186187188189190编号171042066205010157056035016009183152044顺序191192193194195196203204205206207208209编号0810771282001310520720121771240001021154.3 问题三的模型求解：区域的边缘为图像中灰度变化不剧烈的地方，变化不剧烈含有丰富的信息.因此考虑建立图像灰度模型，利用边缘的灰度像素变化，描述了图像中所包含的文字的有无，留白的区域.在对图片处理时，边缘处
29、理的好坏直接影响图像处理的结果.对于边界的追踪，我们利用像素矩阵中白色像素点255的变化来进行追踪，通过转化为像素矩阵的方式将边缘点连接起来，构成一列矩阵.MSAC（M-estinmator Sample Consenous）是Torr和Zisserman提出应用与图像几何的形状来估计12,13.其思想是在两幅图像所有匹配点对的样本中随机采样，在样本中寻找符合采样的所有点对中，通过反复迭代使得到的点对的欧氏距离和代价最小化，使之小于设定的初始值或超过迭代次数，最终得到的点对为所求的正确匹配点对.计算方法如下：首先计算点对的欧氏距离和，其中表示点对的距离函数，其和代价为：其中误差函数满足： 这里
30、给定的值，因此当给定比较大时，得到的地情况会相对多，那么计算得到的点对必然会包含外点，其中内点是我们所要找的点.参考这里的MASC算法，我们将提取的像素矩阵中的每一个元素看做一个个的点，用求绝对差的算法匹配点对，后期运用欧式距离进行检验匹配度.基于上述讨论，本题可由以下步骤完成：步骤一运用Matlab程序对附件5给出的418个碎片图像进行像素矩阵转换计算，其中每个图像得到一个的矩阵，提取出418个碎片图像所得每个像素矩阵的第一列像素矩阵和最后一列像素矩阵，即均为的像素矩阵.步骤二对得到418个第一列像素矩阵和最后一列像素矩阵分别进行列求和，然后分别存放在矩阵D和Dt中，接下来用Dt的每一项依次
31、减去D的每一项之后并求绝对值，得到一个矩阵M.步骤三用MSAC算法的思想，用matlab编程可以算出每一行（列）的最小值，并且反馈出最小值所在的行数，此时我们认为左右像素矩阵的欧式距离最小即为匹配度较高的左右相邻碎纸片.这样可以粗略得到关于文字行的关系，比较后初步得出部分用于拼接复原文件其中一面的180张碎纸片.运算结果部分如下表：表7 运算结果表45503369304363641049368534003040184415324144945900406024543881397160277638762776296214937593531081349858238651128553671285445
32、329842250113825723596410899364155151011551418727181984872230645900140490498070478618663872240316695571991392483021743264533483348322557865210603744590023538100712128153837292314547203921042401624179627452954641201146413721106221878441631548549683989594770559472092412352420904236528947559658033563296
33、335623829139335014347771313322234375939417593185533244058373642043160088537874206245902062367622071473361449412442801170322904374829042834136563148195335854869817557769160250891603422489156256737530345900457558784899503716155037701768150226141180403676015443834596477175647773922082942405426204497815
34、098944796519714681197137672298156445218863990732897164618537512901375119875182161328106435422689776467853151350131512587111838472870641092843520181039889722458897315946285362647450403928370503403242475128607512177432433977508936553834542316222524346931959469310454241158227083641826524852054226571094
35、25710281441217532871853步骤四运用Matlab程序对418个碎片图像的像素矩阵进行统计判断，得出每个图像的第一列的白色边缘像素值255，然后统计分析各个图像的白色边缘区域大小，匹配出位于行首和行末的碎纸片.但是由于计算结果存在误差，此时需要通过人工干预进行区分判断，将筛选出的左右相邻碎纸片，运用行距分类以及组词成句的方法干预拼接成一碎片横条.例如其中的一行的排列结果如下图4、图5所示：图4 附件5部分行拼接图（1）图5 附件5部分行拼接图（2）步骤五通过上述步骤，初步拼接出11个碎片横条，输出成图片，然后用Matlab读取这11张图的像素矩阵，运用同样的思路分析配准像素矩
36、阵的第一行与最后一行，匹配度较高的应为相邻行，进而得出最终复原图像（见本文附件七、附件八），部分排列顺序如下表所示：表8 附件5其中一面部分拼接顺序顺序12345613141516171819编号078b111b125a140a155a150a029a189b081b164b020a047a136b顺序20212223242532333435363738编号089a010b036a076b178a044a079a014a059a060b147a152a005a顺序编号顺序172173174175176177184185186187188189190编号023b133a048a051b095a160b118a101a015b205a082b145a009b顺序191192193194195196203204205206207208209编号099a043a096b109a123a006a100b106b055b103a112a196a054b观察以上所拼接出来的原文件，匹配程度是相当吻合的.七 模型的评价与推广7.1 模型的评价1、 基于图像灰度值的相关方法简单易行，且其数学统计模型、定位精度、收敛速度、误差估计等都有定量的分析及研究结果，此类方法可以进行推广普
