碎纸片的拼接复原论文

2013高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题.我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性.如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理.我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）.我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（即电子文件名）：B0813所属学校（请填写完整的全名）：广西师范大学参赛队员(打印并签名)：1.杨凯2.周志恒3.陈锦丽指导教师或指导教师组负责人(打印并签名)：日期2013年9月16日赛区评阅编号（由赛区组委会评阅前进行编号）：2013高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1纸片的拼接复原摘要碎纸自动拼接复原技术现今可以归结到计算机视觉和模式识别领域内的问题，它在司法物证复原、历史文献修复等重要领域都起着重要的作用.本文主要分析了文字的拼接技术，通过研究碎纸片内的像素矩阵和文字行特征特点，提出了基于文字图形的半自动拼接算法.对于问题1中的这种单面的仅纵向切碎的文字文件，通过Matlab程序分析附件中每个碎片的像素矩阵，确定拼接的第一个碎片（自左向右拼接），再根据两列像素矩阵的像素绝对差的和来确定相邻碎片的编号，从而得到完整的拼接方案.例如文字文件的拼接结果如下表所示：顺序12345678910111213141516171819编号008014012015003010002016001004005009013018016001004005009对于问题2中既纵切又横切的碎纸片，在问题一的基础上，充分考虑横向匹配和纵向匹配的要求，运用Matlab程序筛选最左列碎片成分，经过适当的人工干预根据文字行特征将所剩碎片进行行分类，大大提高拼接效率，得到意想的效果.例如文字文件的拼接结果如下表所示：顺序12345678910111213141516171819编号003006002007015018011000005001009013010008012014017016004对于问题3，在前两问的基础上，建立筛选附件5碎片图的优化模型，通过Matlab编程，使用附件给的418张碎纸片图，将最终复原图划分为11个碎片横条区域，降低了拼接复原难度以及所需时间.最终复原结果见附录.最后，分析了所建立模型的优缺点以及推广，评价了文字碎纸片的拼接和复原实际情况.关键词文字图形碎片半自动拼接像素灰度MATLAB程序2一问题的重述碎纸自动拼接复原技术是计算机视觉和模式识别领域内的问题.它在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统意义上的拼接复原工作需由人工完成，准确率较高，但效率非常低，特别是当碎片数量巨大时，人工拼接很难在短时间内完成任务.随着计算机技术的发展，人们试图开发碎纸片的自动拼接技术，以提高拼接复原效率.本文主要讨论：首先，对于给定的来自同一页单面印刷文字文件的碎纸机破碎纸片（仅纵切），建立碎纸片拼接复原模型和算法，同时对题目中的附件1和附件2给出的中、英文各一页文件的碎片数据进行拼接复原.其次，对于同样是单面印刷文件既纵切又横切的情形，在第一问的基础上设计出碎纸片拼接复原模型和算法，对附件3和附件4给出的中、英文各一页文件的碎片数据进行拼接复原.最后，联系现实中的情况，对还有可能出现双面打印文件的碎纸片进行拼接复原.在前两问的基础上，设计出相应的碎纸片拼接复原模型与算法，并附件5中双面打印文件的碎片数据给出拼接复原结果.在上述复原过程中，由于计算机的识别可能会出现偏差，那么就需要在拼接过程中进行必要的人工干预，在适当的时候我们会用干预的方式给出复原过程.并最终以图片形式及表格形式完成给出复原结果.具体结果在附件中给出.二问题的分析破碎文件的复原，最直接及最精确的就是人工拼接，但是当碎片的数量巨大时，人工方式就显得效率低下，所以就考虑把破碎文件运用计算机技术来帮助人们进行破碎文件的复原，让计算机在这个过程中发挥主要作用，但是用计算机处理，又不是百分之一百完美，因此在适当的时候也需要进行人工干预.本文运用碎纸片的自动拼接技术，对每个附件给出的碎片文字材料进行分析，尽可能减少人工干预，本文给出的图像数据均为形状、大小一样的规则长四边形，由于形状的一致性，所以在拼接时如果只考虑利用碎片的边界特征，直接拼接，显然效果不理想.考虑到使用计算机的拼接过程应该与人工拼接过程是相类似的，即拼接时不但考虑碎片边缘是否匹配，还要判断碎片内的字迹断线和文字内容是否匹配.然而根据现在已有的技术，实现计算机智能识字是几乎不可能的.但是我们可以获取图片所提供的像素信息，将其转化为矩阵，根据图像的像素矩阵值进行碎片拼接，用计算机去运行处理数3据，可以想象其拼接效率无疑比单纯利用边界特征的方法好很多.以下是对各问题的详细分析：针对问题1，对附件1和附件2提供的数据，每页纸被切为19条碎片，对于这种单面的仅纵向切碎的文字文件，我们仅考虑碎片左右两侧的拼接.首先，在转换中发现，像素图片矩阵的值是介于0到255之间的一个像素矩阵，随着像素矩阵值的增加，我们发现随着像素矩阵数值的增大，所代表的区域越来越浅，最后255这个数值，代表了白色区域.其次，对于问题1中的附件1和附件2图片，由于仅纵向切碎的文字文件，仅考虑碎片左右两侧的拼接.需运用Matlab程序分别对附件1和附件2中的19个碎片计算其像素矩阵，将每个附件中19条图像转换成19个198072的像素矩阵，筛选出每个像素矩阵的第一列像素矩阵值，然后运用Excel软件统计各列像素值等于255的个数，可以粗略的认为所含255个数最多的列所对应的碎片则是拼接顺序中的左边第一条（如果有必要进行人工干预，但是本文第一问没有进行人工干预）.接下来从左边开始选取第二条碎片，关于第二条待匹配的碎片，用先确定的第一条像素矩阵的最后一列，对其进行数值求和，然后将剩下的18个像素矩阵中的第一列和最后一列矩阵进行分别求和.将首先确定的最左边第一条矩阵中的最后一列矩阵与求出的18个像素矩阵中的第一列矩阵分别进行做差，然后将差值取绝对值，这样就可以得出，如果差值越小，其重叠的相似度也应该相对越高.这样可筛选得出相似度较高的碎片，即与第一个碎片相匹配，该碎片位于拼接顺序的第二条，确定第二条后，再用第二条的最右边矩阵并以此类推，逐一从左到右查询碎片，直到碎纸片的复原结果.针对问题2，在问题1的基础上，继续对所给的附件3和附件4进行分析.针对附件3和附件4的特点，附件3和附件4给出了碎片既横切又纵切的中英文图像，那么在拼接时就有两方面的考虑，既要满足横向匹配，又要满足纵向匹配.那么我们就考虑在问题解决中可以分为两步进行，首先考虑横向拼接，一旦横向拼接完成了，纵向拼接自然相对就好解决了.根据碎片像素矩阵特征和行距特征将其分类，再结合问题1的方法将各类碎片进行匹配，即可得到11个碎片横条.接着考虑纵向拼接，使用Matlab程序对得到的新的横条碎片进行像素分析，比较像素矩阵中第一行数据中255的个数，个数最多的碎片即是原文件的第一行，依次类推，同样的方法即可知道具体的排列顺序，从而得到碎纸片复原的结果.针对问题3，在问题1和问题2的基础上，继续对所给的附件5进行分析.实际生活中存在很多双面打印的文件，这些双面文件的碎纸片混合在了一起，当对其进行拼接复原时，首先要判断同一面的文字碎片，然后再进行拼接.附件5给出了碎片既横切又纵切的英文文字图像，那么在拼接时依旧有两方面的考虑，既要满足横向匹配，又要满足4纵向匹配.首先考虑横向拼接，转换得到180x72的像素矩阵，这些是介于0到255之间的一个像素矩阵，随着图片的增加，相应的增多转换得到的像素矩阵，在问题2的基础上继续进行检验所给的碎纸片图，运用Matlab读取了418张碎片图后，将每张碎片转换得的像素矩阵的第一列以及最后一列各自取出，通过程序进行验证，可以算出匹配度高的相邻碎片，此时进行一次人工干预，拼接出位于同一行的碎片横条；接着考虑纵向拼接，运用Matlab程序对得到的新的横条碎片进行像素分析的提取，配准各个横条的像素矩阵的第一行与最后一行的相关度，综合分析碎纸片上英文之间的行距，进而确定拼接的碎片横条位于哪一行，得到最终的复原结果.综上所述，以上三个问题的解决流程可用下面的流程图表示：图2问题解决流程图碎纸片转换像素矩阵提取首列尾列筛选碎纸片左右配准提取首行尾行人工干预碎片横条筛选确定行位置人工干预复原图排序三模型假设准备与符号说明3.1模型的假设1、假设碎纸机把一页印刷文字文件碎成形状规则，大小一样的碎片，看做形状、大小相同的长方形.2、在碎纸过程中，只考虑文字被切开，不考虑文字笔画的丢失、碎片添加的任何痕迹等.3、假设文档碎片的文字的方向已经确定（按照阅读标准确定，从左向左右，自上而下），不考虑碎片图像的旋转问题.4、图片在复原的过程中，不考虑图片像素的改变，只考虑碎片相对应的固定像素值的匹配问题.53.2模型准备不规则几何文档碎纸片计算机拼接的方法一般利用碎片边缘的尖角特征、尖点特征、面积特征等一些几何特征，搜索与之匹配的相邻碎纸片进行拼接，这种基于边界的几何特征的拼接方法并不适用于边缘的形状相似的碎纸片.对于这类边缘相似的碎纸片的拼接问题，理想的计算机拼接的过程与人工拼接的过程类似，即拼接时不仅要考虑拼接碎纸片的边缘是否匹配，还要判断碎纸片内的文字字迹断线或文字内容是否匹配，但是由于理论和技术的限制，让计算机具备类似于人的的那种识别碎纸片边缘字迹断线、以及理解碎纸片内文字图像的含义的智能几乎是不太可能的.但是利用现在已有的技术，完全可以获取到碎纸片文字所在行的几何特征信息，如文字行的行高及间距等信息.如果利用这些信息进行碎纸片拼接，其拼接的效率就比单纯利用边界的几何特征方法更好.根据本文题设要求，经考虑分析，本文采取转换矩阵数组元素拼接的技术对破碎的文字文档进行拼接复原.由于计算机数字分析图像能力方面的存在一定的缺陷，让计算机对碎纸片进行完全意义上的自动化拼接页几乎是不太可能，为保证其拼接的准确性，需要在拼接的过程中加入一定的人工干扰过程.一般来说，先利用计算机搜索出于目标碎纸片相匹配的未拼接碎纸片，并根据匹配的程度按顺序到得待选的碎纸片，然后人为地进一步分析结果进行舍弃或拼接待选碎纸片[3].一页文字文件的碎片拼接复原相当于全景图的生成技术，而相邻图像的配准及拼接是该技术的关键.图像的拼技术一般分为基于图像特征的方法和基于图像灰度的方法.特征提取的方法通常涉及大量的几何与图像形态学的计算，计算量大，没有一般的模型可遵循，但需要针对不同的应用场景来选择各自适合的特征，所提取的图像特征包括更高层的语义信息，基于特征的方法具有尺度不变性和放射不变形.然而基于图像灰度的拼接方法简单简单易行，并且其数字统计模型以及收敛速度、定位精度等均具有定量的分析和研究结果，此类方法得到了广泛的应用.本文中的文字图像中文字区域的文字结构相对单一，并可能出现相同或相似的字符，因此文字容易出现匹配出现误差.对于文字左右拼接的情况，可以对图片中划分的每行文字进行分析处理，通过提取文字图片的边缘像素矩阵，得到文字出现在图片边缘的那一行高，进一步对一行行的文字拼接复