碎纸片的拼接复原问题大学生数学建模(一等奖论文).pdf
《碎纸片的拼接复原问题大学生数学建模(一等奖论文).pdf》由会员分享,可在线阅读,更多相关《碎纸片的拼接复原问题大学生数学建模(一等奖论文).pdf(42页珍藏版)》请在咨信网上搜索。
1、碎纸片的拼接复原问题 摘要为解决碎纸片的拼接复原问题,我们通过定义差异度指数、高度差,建立0-1规划 模型,使用聚类分析、MATLAB搜索算法和人工干预等相结合,得到了所有附件复原序号 和复原图片。针对问题一,首先提取附件1、2中所有碎片左侧和右侧边缘灰度,通过任意列碎 片右侧和任意列碎片左侧的边缘灰度差值可以定义差异度指数,从而得到差异度特征矩 阵,然后建立0T规划模型,以第i张碎片右侧与第j张碎片左侧差异度最小为目标函 数,以第i张碎片右侧与第j张碎片左侧是否相连为决策变量,以每张碎片右侧一定与 某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件。算法为先提取 任意张碎片边缘灰
2、度值,得到差异度矩阵,带入规划模型中,通过LI NGO软件找到中英 文碎片的拼接方法,得到复原序号如表一、表二,从而得到出中文与英文复原图片。表一:中文碎片的复原序号008014012015003010002016001004005009013018011007017000006表二:英文碎片的复原序号003006002007015018011000005001009013010008012014017016004检验中英文碎片拼接复原顺序准确性,利用MATLAB搜索算法,可以得到中英文碎 片拼接方法。结果表明两种方法得出的中英文复原顺序相同,复原图片相同,同时人工 检验中英文复原图片中无明显
3、语法、单词错误,证明复原图片准确。针对问题二,由于每张碎片有左侧、右侧和上侧、下侧,与问题一相同,可以定义 两个差异度指数,建立双目标0-1规划模型。但由于差异度矩阵过大,决策变量复杂,我们又建立了改进的简化模型,定义高度差,运用聚类分析方法,按照高度不同将所有 碎片分为18类,然后再以第j块碎片左侧与第i块碎片右侧的差异度最小为目标函数,以第i块碎片右侧与第j块碎片左侧是否相连为决策变量,以每块碎片右侧一定与某块 碎片左侧相连、每块碎片左侧一定与某块碎片右侧相连,满足高度差阈值为约束条件,建立单目标0-1规划模型。算法为先提取任意块碎片边缘灰度值和高度,得到差异度矩 阵,编程将中文碎片按高度
4、分为18类,人工干预分为H行,再利用问题一中碎片纵向 复原方法,得到中文复原序号,画出中文复原图片。(英文复原模型相似,仅高度差阈 值不同)针对问题三,对于双面英文碎片的复原问题,我们提出了单词残缺程度的定义,定 量的描述了英文碎片的特征信息,构成了算法的核心内容,运用编程和人工干预将碎纸 片分为11类,每类19个碎片,在此基础上利用前两问所建的0-1规划模型,再加上双 面的一些约束条件,得到双面英文复原序号,并绘出英文双面复原图片。关键词:差异度指数;0-1规划;LI NGO软件;聚类分析;高度差;残缺程度;1一、问题重述破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着
5、重 要的应用。传统上,拼接复原工作需由人工完成,准确率较高,但效率很低。特别是当 碎片数量巨大,人工拼接很难在短时间内完成任务。随着计算机技术的发展,人们试图 开发碎纸片的自动拼接技术,以提高拼接复原效率。请讨论以下问题:1.对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片 拼接复原模型和算法,并针对附件1、附件2给出的中、英文各一页文件的碎片数据进 行拼接复原。如果复原过程需要人工干预,请写出干预方式及干预的时间节点。复原结 果以图片形式及表格形式表达。2.对于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法,并针对附 件3、附件4给出的中、英文各一页文件的碎片
6、数据进行拼接复原。如果复原过程需要 人工干预,请写出干预方式及干预的时间节点。复原结果表达要求同上。3.上述所给碎片数据均为单面打印文件,从现实情形出发,还可能有双面打印文件 的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎 片数据。请尝试设计相应的碎纸片拼接复原模型与算法,并就附件5的碎片数据给出拼 接复原结果,结果表达要求同上。二、模型假设1.假设每个碎纸片上的字和字母都没有发生扭曲。2.假设每个碎纸片的形状和大小完全相同。3.假设每个碎纸片上灰度值的提取都是完全正确的值不等于255的都是黑点三、符号说明符号符号的含义差异度指数,表示第i张碎片右侧和第/张碎片左
7、侧的差异度;Q表示第i张碎片右侧第k个特征点的灰度值;x.j决策变量,当x,7=o时,表示第i张碎片右侧和第j张碎片左侧的不相连;时,表示第i张碎片右侧和第j张碎片左侧的相连;Su表示第j列碎片左侧与差异度最小的第i列碎纸片右侧相连:Lij表示第i块碎片右侧和第j块碎片左侧的差异度;4表示第i块碎片下侧和第j块碎片上侧的差异度;稣表示第i块碎片右侧第k个特征点的灰度值;5k表示第i块碎片下侧第k个特征点的灰度值;%=o时,表示第i张碎片右侧和第j张碎片左侧的不相连;2%=i时,表示第i张碎片右侧和第j张碎片左侧的相连:AOu=o时,表示第i张碎片下侧和第j张碎片上侧的不相连:%=i时,表示第i
8、张碎片下侧和第j张碎片上侧的相连;高度差表示第i块碎片第一行文字中心到第i碎片上侧边缘的高度与第j块碎片第一行文字 中心到第j碎片上侧边缘的高度H j之间的差值;四、问题一分析与模型建立、求解4.1问题一的分析问题一要求对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立 碎纸片拼接复原模型和算法,并针对附件1、附件2给出的中、英文各一页文件的碎片 数据进行拼接复原。参考文献1,由于每列中文和英文碎片都有左侧和右侧,需要考 虑每一列碎片的左侧和右侧与其他列的左侧和右侧差异,每列碎片边缘灰度已知,通过 任意列碎片右侧和任意列碎片左侧的差异值可以定义差异度指数(同一列碎片的左侧与 右侧
9、的差异度定义为无穷大),从而得到差异度特征矩阵。然后可以通过0T规划模型,以第j张碎片左侧与第i张碎片右侧的差异度最小为 目标函数,以第i张碎片右侧与第j张碎片左侧是否相连为决策变量,以每张碎片右侧 一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件(复原图 片最左侧一定与最右侧的差异度最小),找到中文和英文碎片的拼接复原顺序,MATLAB 编程得到复原序号,从而得到出中文与英文复原图片。为了检验中文与英文碎片拼接复原顺序是否正确,建立了 MATLAB搜索算法模型,可以得到中文与英文碎片拼接方法,MATLAB软件可以直接画出中文与英文复原图片。结 果表明两种方法得出的中文与英
10、文复原顺序相同,复原图片相同。同时人工检验出中文 与英文复原图片中无明显语法、词语和单词错误,证明复原图片正确。4.2问题一的碎纸片拼接复原模型建立先提取碎纸片边缘差异信息,再进行图片拼接复原,具体步骤如下:(1)提取信息:差异度指数用差异度指数来衡量任意列右侧边缘与任意列左侧边缘差异。定义差异度指数表示第,张碎片右侧和第/张碎片左侧的差异度,为第i张碎 片右侧与第j张碎片左侧的对应灰度值之差的绝对值的累和。公式如下:”1980C=X-cjk1=U,-,19,j=1,2.19,当,制时()ij k=l8,当i=j时其中:品表示第i张碎片右侧第k个特征点的灰度值C用表示第j张碎片右侧第k个特征点
11、的灰度值3说明:品和C的值已知,将附件1和附件2中19张碎片数据带入MATLAB软件可以得到每张碎片的1980个灰度值;从而得到差异度矩阵如下:通过MATLAB编程计算出具体值如下:表一:附件一中文任意碎片差异度G差异度G1列左侧2列左侧3列左侧4列左侧5列左侧6列左侧7列左侧8列左侧9列左侧10列左侧j列左侧1列右侧I nf13094511610314144810094211195525661106097859491111182列右侧123423I nf12658912565233616100027112423119895935271116043列右侧127946114084I nf1050
12、351047459692812241490256827441016734列右侧10625312762995945I nf113330106911111305103203838871128105列右侧110732116398100076115677I nf22300118792105006575641040876列右侧120399113365105551124588114916I nf1226938746581403246507列右侧84410106346744681140798670949380I nf628100803698列右侧1116071132051091371369761023621
13、11309107605I nf846291129369列右侧971811109651168891241121071147860111188398983I nf11139410列右侧11148411862010928812147111806910447212446410150090152I nfi列右侧表二:附件二英文任意碎片差异度岫差异度G1列左侧2列左侧3列左侧4列左侧5列左侧6列左侧7列左侧8列左侧9列左侧10列左侧j列左侧1列右侧I nf8531082752765677956224368985428960089490897152列右侧68051I nf800855157474947102
14、845869457199767927183563列右侧5829562297I nf402266457988857778251982366511693244列右侧669776386970269I nf7811792269252777688382185725225列右侧3489739595546630I nf83053616754614357641507866列右侧5764919399767274548276087I nf790896994580753662107列右侧667477727719737517986301585575I nf7148774927804368列右侧702507458074
15、65457731809149252071274I nf75578707579列右侧6250663054701424022571430809388231068430I nf7577510列右侧689017092777477538548212397435887038446184145I nfi列右侧4(2)中文和英文碎纸片拼接复原模型以第j张碎片左侧与第i张碎片右侧的差异度最小为目标函数,以第i张碎片右侧 与第j张碎片左侧是否相连为决策变量,以每张碎片右侧一定与某张碎片左侧相连、每 张碎片左侧一定与某张碎片右侧相连为约束条件,建立0-1规划模型。19 19i=l j=2xu=1,J=1,2,.,1
16、9s.t X/=l,i=1,2,.,19=0或 1其中:勺为决策变量,%=0时,表示第,张碎片右侧和第j张碎片左侧的不相连;闯=1时,表示第,张碎片右侧和第j张碎片左侧的相连;4.3问题一中英文碎片拼接问题模型求解模型求解算法如下:(1)运用MATLAB编程提取19列中文和英文碎片左侧和右侧的灰度值,计算出差异 度指数,得到差异度矩阵,结果见表一和表二。(2)运用LI NGOH.0软件,将上述0-1规划问题的目标函数与约束条件带入LI NGO 软件中(附录一为中文碎片拼接复原LI NGO算法,附录二为英文碎片拼接复原LI NGO算 法),结果如表三和表四。(3)运用MATLAB编程(编程见附录
17、三)得到中文和英文碎片的复原序号,结果见 表五和表六,可以直接得到中文和英文复原图片,图片见附录四和五。表三:中文碎片连接方法决策变量为1X(2,5)X(l,7)X(3,17)X(4,ll)X(5,6)X(6,10)X(7,9)X(8,18)X(9,15)X(10,14)实际连接点01-0400-0602-1603-1004-0505-0906-0807-1708-1409-13决策变量为1X(ll,3)X(12,8)X(13,16)X(14,19)X(15,13)X(16,14)X(17,2)X(18,1)X(19,12)实际连接点10-0211-0712-1513-1814-1215-13
18、16-0117-0018-11表四:英文碎片连接方法决策变量为1X(l,6)X(2,10)X(3,8)X(4,7)X(5,4)X(6,2)X(7,3)X(8,16)XX(10,14)实际连接点00-0501-0902-0703-0604-0305-0106-0207-1508-1209-13决策变量为1X(ll,19)X(12,1)X(13,15)X(14,11)X(15,18)X(16,19)X(17,5)X(18,17)X(19,12)实际连接点10-1811-012-1413-1014-1715-1816-0417-1618-115得到连接方法以后,可以使用MATLAB编程(见附录三)得
19、到中文和英文碎片的复 原序号如下表:表五:中文碎片的复原序号008014012015003010002016001004005009013018011007017000006表六:英文碎片的复原序号003006002007015018011000005001009013010008012014017016004用MATLAB编程(附录四)可以直接拼接出中文和英文碎片复原图片,程序结果截图如图一:Current Fol det:E:mt b|g 四I m Edit or Mdin_PrQ.m x Workspacei 璃-|1T|+rr|x 噫啜 qi%此模块是程序的主要执行程序2%通过调用写好
20、的各个模块(子程序等)进行运算3%4%5%入数据并得到特征向量6%附件17 DATA1 TeZhenl _Lie TeZhenl _Hang=Dac8%附件29-DATA2 TeZhen2_Lie TeZhen2_Hang=Da(10%附件311-DATA3 TeZhen3_Lie TeZhen3_Hang=Da12%附件413-DATA4 TeZhen4_Lie TeZhen4_Hang=Dac14%附件澈特殊,所以需要使用新的行列函数15%附件516-DATA5_A DATA5.B TeZhen5_Lie_A TeZhe17 TeZhen5_Hang_B=DaoRuShuJu_AB(18%
21、当,I”他闺,桓父曹方日吃一画国画匾电I St ack:rName 上 回 DATA1 叵DATA2 叵1DATA3 叵|DATA4 叵1 DATA5_AFigure 1Efe Edit View I nsert Tool s Deskt op Window Hefc口目 H 4|Q|X 踮 W|131 国|El献上层搂婆诚下佬淮古汴“毕手指吴云,人与X天嗔送,虎断后夜松江月满维瑟衣巾莎塞范村里村上响澡车,牛衣古柳卖黄 II.海宗珠登一生王.活璘近帝战.脑脂券与匀淡,偏向脸边浅.小郑春 常漏记,二南依旧能诗 更右舶鱼先切绘,儿军结微知自古t fl从休务 B,何妨孤唱才吟天香云至作吞胡“出中人半
22、弊,帘外3?信深.双T年 BL饼限稳波后SI翠”舞用原“掌上身轻其态斜/理轻箓两凤,琴场 淡胡双冽为诋流解不归家.铤包门前过目“我劝离张妇去好,从来口己忘情“尘心消尽恒心平,江南与*北,W 处不耍行:用为PH:惟金案授就王,间时梦公南,旧恨前欺,心事也无融 里如带a丑由.s Am.-mat s,ixiwacra卜物.若再汨图一:复原图片程序结果截图中文与英文碎片复原的图片见附录四和五。复原过程不需要人工干预,可完全通过LI NGO软件和MATLAB编程实现。4.4中文和英文碎片拼接复原方法检验为了检验差异度指数和0-1规划模型得出的复原顺序和复原图片的准确性,利用 MATLAB搜索算法模型:S
23、,7=面吗,)给定时,,取 1,2,.,19。=1,2,.,19)(4)已通过MATLAB编程得到第i张碎片右侧和第j张碎片左侧的差异度.,见表一与 表二。对表一和表二按照列搜索,依次搜索找到与第j列碎片左侧相连的差异度最小的 第i列碎纸片右侧(即匹),即第i列碎纸片右侧与第j列碎片左侧相连,对于每一列 碎纸片需要搜索19次,共需要搜索361次,使用MATLAB搜索算法即可实现(编程见附 录三)可以得到中文和英文碎纸片的连接方式,如下表:表七:中文碎纸片连接方式6表八:英文碎纸片连接方式第i列右侧连接第j列左侧017-000016-001010-002015-003001-004004-005
24、000-006011-007000-006005-009第i列右侧连接第j列左侧003-010018-011014-012009-013008-014012-015002-016007-017013-018通过对比这两种模型得到的结果发现:中文和英文碎片连接方式完全相同,两种方 法得出的中文与英文复原顺序相同,复原图片相同。同时人工检验出中文与英文复原图 片中无明显语法、词语和单词错误,证明中文和英文复原图片正确。第i列右侧连接第j列左侧011-000005-001006-002000-003016-004000-005003-006010-008002-007001-009第i列右侧连接第j
25、列左侧013-010018-011008-012009-013012-014007-015017-016014-017015-0180T规划模型清晰明了,同时运算简单,运算速度快。MATLAB搜索算法搜索次数较 多,运算速度慢一些,但结果准确。所以我们使用0-1规划模型解决问题一,使用MATLAB 搜索算法检验结果。五、问题二分析与模型建立、求解5.1问题二的分析问题二要求对于碎纸机既纵切又横切的情形,建立碎纸片拼接复原模型和算法,并 针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。由于209块 中文和209块英文碎片都有左侧、右侧和上侧、下侧,与问题一相同,可以定义两个差
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 纸片 拼接 复原 问题 大学生 数学 建模 一等奖 论文
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【曲****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【曲****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。