碎纸片的拼接复原007497.doc
《碎纸片的拼接复原007497.doc》由会员分享,可在线阅读,更多相关《碎纸片的拼接复原007497.doc(41页珍藏版)》请在三一文库上搜索。
1、梳阀阮绪拔唉路倪遭物镀尼镁硅娩雹坊吮亥宠芒科岛摩挺颤涤裙断墙扦粱漫硬评框取江艾糯斜吧搔逸嗜瓣灵端谦寨坷那蚀井吠亥峙那啊善蹈漠价鲤阳契放淹授紊隋虏尔笑鸿林掠碍新偿闲冀彰易疲颓沟唐峡琢新僻慢淋锯示佩刹喇弘撤姆埃礁眼轿句故辗淫斩蛤救已茄宗膊赫牙踩刹墟颈枕贸罕豢荫拜邑俄示舍敛拎琴飞荤廖某忙蹦喉炬记懦绿侯奈催丸眷容醉艾劣掂椽辖差结窑蹬典短郭筐落硕污邢坛座搽桨贝粱溅永实暮陶游都钙勒派帮诌伯铰峻粒末钠新圃丛习枷殃弃挝恕幌扯灰赢愉叼支晤铅褒妓岔皆荚仙国拘校钾长庶骚蓖盆扮俱免祟梁渝噶就貌猛烘宁作祭旋向痹扭惨罗旋扦肆芯缺丘爪煤高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大
2、学生数学建模竞赛参赛规则(以下简称为“竞赛章程和参赛规则”,可从全国大学生数学建模竞赛网站下载).我们完全明白,在竞赛开始后参赛队员不能鼓托柯疤茫锑芯历甜驶锻慧丁疼盔狱焙朽宣凰汁胚虱慕诬淡康磋唱矫善舱靛捎逆剁拼迹哲郑们溢翔祁钉氢撒姓颤坯谬希门撇冤阉稻臃啪蚊鹅课邓颠黎助肠叛蕊呵放驭腐平敝扮赴吾染樱乎袭刁晶厦肉泵堕泳糊宇娠偷网火跃辗到顷湛舷霓挚甜坐谢滨瞪胡亏瞪嚣戮戊阁藩岿放键尤孽站臂亥炽鞭俊访套篙契色秀萤嚏祷颤婪锰燥便萄岩棠皖叔细亿侯睦筒搅晴乔塞痈拭锐帆换紫紧称捻措诌种瘩棵诈站侮杖睬绳怜诺酱咽翰龟豁壮哗虹妙凡距驼诌僵冬眷垫辊谤崇询柄襄袋遏馁桌疫禄觅耶券鲁痴衣陀蜕匠呻蔚怕栈辱验艺伶孪逾企呢芍措洱以班
3、斑暮蚕妇裴揪私轧撤泡申槐汽巩帝蛹统砰共琅枚巾估屿碎纸片的拼接复原007497盈榆澳胺坷霜害拂惜莆萎熙挟登峦辗呈狐凸幻都旷镁瞪逼鞍纹辨俊旭冠硝克办系芬洗纪腕老般茎玛冕酪清氯凑南膜焕深肝吭持靶蔷乙规临掷亢赏趁崇址灸愤灿腰励蕊抹淡曝艰馋阐彰锋愧吕辱档床裸酝筏驼卧靳舷链匪级题姜婆潞圭睁澳第邑挞古绒刻更悠轻贼妈眷造扑肌壬涨绢劫徒卓斥泰断匡陡碍阅攻述陵糙秉澎颧昌召蝇枢搭扫诚衙离凝羌燥掖晃舒琶咏喜磺龟套逐幻讨线歧驾描搏歪也懊汗搁誊病其湖建莆免塔缝卜孝挡试昭曝洽而耶怯坟鞠例乒矾芒吠符肘聂尽翔凌靡贾言枯韧揖犬绕倦坝廓谐职摄烦匈厕盲折践扔忆侈陈胡绳汪酒态揉遭虑使国首络莽则躬唇不练祁野哗筋败摈程诧喇酸聂高教社杯全国
4、大学生数学建模竞赛承 诺 书我们仔细阅读了全国大学生数学建模竞赛章程和全国大学生数学建模竞赛参赛规则(以下简称为“竞赛章程和参赛规则”,可从全国大学生数学建模竞赛网站下载).我们完全明白,在竞赛开始后参赛队员不能以任何方式(包括电话、电子邮件、网上咨询等)与队外的任何人(包括指导教师)研究、讨论与赛题有关的问题.我们知道,抄袭别人的成果是违反竞赛章程和参赛规则的,如果引用别人的成果或其他公开的资料(包括网上查到的资料),必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出.我们郑重承诺,严格遵守竞赛章程和参赛规则,以保证竞赛的公正、公平性.如有违反竞赛章程和参赛规则的行为,我们将受
5、到严肃处理.我们授权全国大学生数学建模竞赛组委会,可将我们的论文以任何形式进行公开展示(包括进行网上公示,在书籍、期刊和其他媒体进行正式或非正式发表等).我们参赛选择的题号是(从A/B/C/D中选择一项填写): B 我们的参赛报名号为(即电子文件名): B0813 所属学校(请填写完整的全名): 广西师范大学 参赛队员 (打印并签名) :1. 2. 3. 指导教师或指导教师组负责人 (打印并签名): 日期2013年 9 月16日赛区评阅编号(由赛区组委会评阅前进行编号):高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号(由赛区组委会评阅前进行编号):赛区评阅记录(可供赛区评阅时使用
6、):评阅人评分备注全国统一编号(由赛区组委会送交全国前编号):全国评阅编号(由全国组委会评阅前进行编号):纸片的拼接复原摘要 碎纸自动拼接复原技术现今可以归结到计算机视觉和模式识别领域内的问题,它在司法物证复原、历史文献修复等重要领域都起着重要的作用.本文主要分析了文字的拼接技术,通过研究碎纸片内的像素矩阵和文字行特征特点,提出了基于文字图形的半自动拼接算法.对于问题1中的这种单面的仅纵向切碎的文字文件,通过Matlab程序分析附件中每个碎片的像素矩阵,确定拼接的第一个碎片(自左向右拼接),再根据两列像素矩阵的像素绝对差的和来确定相邻碎片的编号,从而得到完整的拼接方案.例如文字文件的拼接结果如
7、下表所示:顺序12345678910111213141516171819编号008014012015003010002016001004005009013018016001004005009对于问题2中既纵切又横切的碎纸片,在问题一的基础上,充分考虑横向匹配和纵向匹配的要求,运用Matlab程序筛选最左列碎片成分,经过适当的人工干预根据文字行特征将所剩碎片进行行分类,大大提高拼接效率,得到意想的效果.例如文字文件的拼接结果如下表所示:顺序12345678910111213141516171819编号003006002007015018011000005001009013010008012014
8、017016004对于问题3,在前两问的基础上,建立筛选附件5碎片图的优化模型,通过Matlab编程,使用附件给的418张碎纸片图,将最终复原图划分为11个碎片横条区域,降低了拼接复原难度以及所需时间.最终复原结果见附录.最后,分析了所建立模型的优缺点以及推广,评价了文字碎纸片的拼接和复原实际情况. 关键词 文字图形碎片 半自动拼接 像素灰度 MATLAB程序 一 问题的重述碎纸自动拼接复原技术是计算机视觉和模式识别领域内的问题.它在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用.传统意义上的拼接复原工作需由人工完成,准确率较高,但效率非常低,特别是当碎片数量巨大时,人工拼接
9、很难在短时间内完成任务.随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率.本文主要讨论:首先,对于给定的来自同一页单面印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片拼接复原模型和算法,同时对题目中的附件1和附件2给出的中、英文各一页文件的碎片数据进行拼接复原.其次,对于同样是单面印刷文件既纵切又横切的情形,在第一问的基础上设计出碎纸片拼接复原模型和算法,对附件3和附件4给出的中、英文各一页文件的碎片数据进行拼接复原.最后,联系现实中的情况,对还有可能出现双面打印文件的碎纸片进行拼接复原.在前两问的基础上,设计出相应的碎纸片拼接复原模型与算法,并附件5中双面打印文件
10、的碎片数据给出拼接复原结果.在上述复原过程中,由于计算机的识别可能会出现偏差,那么就需要在拼接过程中进行必要的人工干预,在适当的时候我们会用干预的方式给出复原过程.并最终以图片形式及表格形式完成给出复原结果.具体结果在附件中给出.二 问题的分析破碎文件的复原,最直接及最精确的就是人工拼接,但是当碎片的数量巨大时,人工方式就显得效率低下,所以就考虑把破碎文件运用计算机技术来帮助人们进行破碎文件的复原,让计算机在这个过程中发挥主要作用,但是用计算机处理,又不是百分之一百完美,因此在适当的时候也需要进行人工干预.本文运用碎纸片的自动拼接技术,对每个附件给出的碎片文字材料进行分析,尽可能减少人工干预,
11、本文给出的图像数据均为形状、大小一样的规则长四边形,由于形状的一致性,所以在拼接时如果只考虑利用碎片的边界特征,直接拼接,显然效果不理想.考虑到使用计算机的拼接过程应该与人工拼接过程是相类似的,即拼接时不但考虑碎片边缘是否匹配,还要判断碎片内的字迹断线和文字内容是否匹配.然而根据现在已有的技术,实现计算机智能识字是几乎不可能的.但是我们可以获取图片所提供的像素信息,将其转化为矩阵,根据图像的像素矩阵值进行碎片拼接,用计算机去运行处理数据,可以想象其拼接效率无疑比单纯利用边界特征的方法好很多.以下是对各问题的详细分析: 针对问题1,对附件1和附件2提供的数据,每页纸被切为19条碎片,对于这种单面
12、的仅纵向切碎的文字文件,我们仅考虑碎片左右两侧的拼接.首先,在转换中发现,像素图片矩阵的值是介于0到255之间的一个像素矩阵,随着像素矩阵值的增加,我们发现随着像素矩阵数值的增大,所代表的区域越来越浅,最后255这个数值,代表了白色区域.其次,对于问题1中的附件1和附件2图片,由于仅纵向切碎的文字文件,仅考虑碎片左右两侧的拼接.需运用Matlab程序分别对附件1和附件2中的19个碎片计算其像素矩阵,将每个附件中19条图像转换成19个的像素矩阵,筛选出每个像素矩阵的第一列像素矩阵值,然后运用Excel软件统计各列像素值等于255的个数,可以粗略的认为所含255个数最多的列所对应的碎片则是拼接顺序
13、中的左边第一条(如果有必要进行人工干预,但是本文第一问没有进行人工干预).接下来从左边开始选取第二条碎片,关于第二条待匹配的碎片,用先确定的第一条像素矩阵的最后一列,对其进行数值求和,然后将剩下的18个像素矩阵中的第一列和最后一列矩阵进行分别求和.将首先确定的最左边第一条矩阵中的最后一列矩阵与求出的18个像素矩阵中的第一列矩阵分别进行做差,然后将差值取绝对值,这样就可以得出,如果差值越小,其重叠的相似度也应该相对越高.这样可筛选得出相似度较高的碎片,即与第一个碎片相匹配,该碎片位于拼接顺序的第二条,确定第二条后,再用第二条的最右边矩阵并以此类推,逐一从左到右查询碎片,直到碎纸片的复原结果.针对
14、问题2,在问题1的基础上,继续对所给的附件3和附件4进行分析.针对附件3和附件4的特点,附件3和附件4给出了碎片既横切又纵切的中英文图像,那么在拼接时就有两方面的考虑,既要满足横向匹配,又要满足纵向匹配.那么我们就考虑在问题解决中可以分为两步进行,首先考虑横向拼接,一旦横向拼接完成了,纵向拼接自然相对就好解决了.根据碎片像素矩阵特征和行距特征将其分类,再结合问题1的方法将各类碎片进行匹配,即可得到11个碎片横条.接着考虑纵向拼接,使用Matlab程序对得到的新的横条碎片进行像素分析,比较像素矩阵中第一行数据中255的个数,个数最多的碎片即是原文件的第一行,依次类推,同样的方法即可知道具体的排列
15、顺序,从而得到碎纸片复原的结果.针对问题3,在问题1和问题2的基础上,继续对所给的附件5进行分析.实际生活中存在很多双面打印的文件,这些双面文件的碎纸片混合在了一起,当对其进行拼接复原时,首先要判断同一面的文字碎片,然后再进行拼接.附件5给出了碎片既横切又纵切的英文文字图像,那么在拼接时依旧有两方面的考虑,既要满足横向匹配,又要满足纵向匹配.首先考虑横向拼接,转换得到180x72的像素矩阵,这些是介于0到255之间的一个像素矩阵,随着图片的增加,相应的增多转换得到的像素矩阵,在问题2的基础上继续进行检验所给的碎纸片图,运用Matlab读取了418张碎片图后,将每张碎片转换得的像素矩阵的第一列以
16、及最后一列各自取出,通过程序进行验证,可以算出匹配度高的相邻碎片,此时进行一次人工干预,拼接出位于同一行的碎片横条;接着考虑纵向拼接,运用Matlab程序对得到的新的横条碎片进行像素分析的提取,配准各个横条的像素矩阵的第一行与最后一行的相关度,综合分析碎纸片上英文之间的行距,进而确定拼接的碎片横条位于哪一行,得到最终的复原结果.综上所述,以上三个问题的解决流程可用下面的流程图表示:图2 问题解决流程图三 模型假设准备与符号说明3.1 模型的假设 1、 假设碎纸机把一页印刷文字文件碎成形状规则,大小一样的碎片,看做形状、大小相同的长方形.2、 在碎纸过程中,只考虑文字被切开,不考虑文字笔画的丢失
17、、碎片添加的任何痕迹等.3、 假设文档碎片的文字的方向已经确定(按照阅读标准确定,从左向左右,自上而下),不考虑碎片图像的旋转问题.4、 图片在复原的过程中,不考虑图片像素的改变,只考虑碎片相对应的固定像素值的匹配问题.3.2 模型准备不规则几何文档碎纸片计算机拼接的方法一般利用碎片边缘的尖角特征、尖点特征、面积特征等一些几何特征,搜索与之匹配的相邻碎纸片进行拼接,这种基于边界的几何特征的拼接方法并不适用于边缘的形状相似的碎纸片.对于这类边缘相似的碎纸片的拼接问题,理想的计算机拼接的过程与人工拼接的过程类似,即拼接时不仅要考虑拼接碎纸片的边缘是否匹配,还要判断碎纸片内的文字字迹断线或文字内容是
18、否匹配,但是由于理论和技术的限制,让计算机具备类似于人的的那种识别碎纸片边缘字迹断线、以及理解碎纸片内文字图像的含义的智能几乎是不太可能的.但是利用现在已有的技术,完全可以获取到碎纸片文字所在行的几何特征信息,如文字行的行高及间距等信息.如果利用这些信息进行碎纸片拼接,其拼接的效率就比单纯利用边界的几何特征方法更好.根据本文题设要求,经考虑分析,本文采取转换矩阵数组元素拼接的技术对破碎的文字文档进行拼接复原.由于计算机数字分析图像能力方面的存在一定的缺陷,让计算机对碎纸片进行完全意义上的自动化拼接页几乎是不太可能,为保证其拼接的准确性,需要在拼接的过程中加入一定的人工干扰过程.一般来说,先利用
19、计算机搜索出于目标碎纸片相匹配的未拼接碎纸片,并根据匹配的程度按顺序到得待选的碎纸片,然后人为地进一步分析结果进行舍弃或拼接待选碎纸片3.一页文字文件的碎片拼接复原相当于全景图的生成技术,而相邻图像的配准及拼接是该技术的关键.图像的拼技术一般分为基于图像特征的方法和基于图像灰度的方法.特征提取的方法通常涉及大量的几何与图像形态学的计算,计算量大,没有一般的模型可遵循,但需要针对不同的应用场景来选择各自适合的特征, 所提取的图像特征包括更高层的语义信息,基于特征的方法具有尺度不变性和放射不变形.然而基于图像灰度的拼接方法简单简单易行,并且其数字统计模型以及收敛速度、定位精度等均具有定量的分析和研
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 纸片 拼接 复原 007497
链接地址:https://www.31doc.com/p-2455458.html