碎纸片拼接数学模型教学教材.doc
《碎纸片拼接数学模型教学教材.doc》由会员分享,可在线阅读,更多相关《碎纸片拼接数学模型教学教材.doc(25页珍藏版)》请在咨信网上搜索。
1、碎纸片拼接数学模型精品资料碎纸片的拼接复原问题模型摘要本文研究的是碎纸片的拼接复原问题。针对碎纸不同的裁剪特点,我们运用相关性系数法、聚类分析法等建立不同的模型来解决不同裁剪特点和不同纸张的复原问题。针对问题一,我们利用图像数字化技术,借助MATLAB软件将题目中附件1,2所给的图片转化为灰度值矩阵,并作二值化处理,然后取出每个矩阵第一列和最后一列,采用相关系数分析的方法,计算每第一列和每最后一列相关系数,根据相关系数的大小确定相邻的图片,逐步确定各张图片的顺序,最后得到复原的图片。中文文档拼接的顺序为:8,14,12,15,3,10,2,16,1,4,5,9,13,18,11,7,17,0,
2、6,中文文档复原的结果见附录1;英文文档拼接的顺序为:3,6,2,7,15,18,11,0,5,1,9,13,10,8,12,14,17,16,4,英文文档复原结果见附录2。针对问题二,同样,在将图片二值化处理后,我们运用聚类分析法将纵横裁剪后的图片进行行分类,经过人工干预后,获得需要的矩阵尺寸,然后根据图片的特点运用图片的上下边界和左右边界进行二次匹配,直到找到大致正确的图片排序;同时在必要时,进行二次人工干预,直到获得正确的图片排序。关键词:碎纸片复原 图像数字化 相关性系数 聚类法 1 问题重述1.1 问题背景碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用
3、。然而,传统的拼接复原工作需由人工完成,准确率较高,但效率很低。特别是当碎片数量巨大,人工拼接很难在短时间内完成任务。随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率。本题即是通过一些模型算法开展对碎纸自动拼接技术的研究,具有重要的现实意义。1.2 要解决的问题问题一:对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片拼接复原模型和算法,并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预,要求写出干预方式及干预的时间节点。问题二:对于碎纸机既纵切又横切的情形,要求设计碎纸片拼接复原模型和算法,并针对附件3、
4、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预,请写出干预方式及干预的时间节点。问题三:附件5给出的是一页英文印刷文字双面打印文件的碎片数据。要求设计相应的碎纸片拼接复原模型与算法,并就附件5的碎片数据给出拼接复原结果。2 模型的假设及符号说明2.1 模型的假设(1)假设碎纸机在碎纸时不对碎片造成损坏,可以拼接复原成完整的一页文字;(2)假设各碎纸片大小相等且规则;(3)假设同一页中,文字的种类、行间距和段落分布情况是相同的。2.2 符号的说明3 问题分析针对问题一,要求对来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片拼接复原的模型和算法。附件1和
5、附件2的碎纸片是经过纵切而成,想要将图片进行还原,必须要在里面取出左右边缘的值,进而对碎纸图片的左右边缘进行匹配就可以还原图像。首先将图片进行图像化处理,获得图片的像素点灰度值矩阵,转化成计算机可以识别且量化的计算机语言,其次,取出每个灰度值矩阵的第一列和最后一列列向量形成新的矩阵,并对其进行二值化处理,最后计算矩阵两列的相关系数,相关性越高,说明这两块碎纸片匹配的概率就越大,最终得出图片复原的排列顺序,将碎纸片进行复原。针对问题二,附件3和附件4的碎纸图片是经过纵切和横切而成的,相对第一问而言,图片可以直接获取的信息就较少,如像素灰度矩阵变小;如果采取同第一问一样的方法,对图片的匹配而言准确
6、度大为降低,同时还会出现更多的重复匹配。所以要进行碎纸图片还原,首相应该对碎纸进行行分类或者列分类,这里我们选择行分类,同时根据碎纸片的特点,我们进行行内的左右边界匹配,以及对所得行模块进行相关性匹配,对于不能够找到最佳匹配的,我们进行人工干预,直到将整个图片进行复原。针对问题三,4 图片数据处理与分析 纵观整个题目,给出的附件均是一整幅图片的碎片集合。根据题目建模的相关要求,需要将图片转化为其像素点灰度矩阵,同时为了降低计算机的计算机的计算强度和为了整个题目的计算过程,我们将图片的像素点灰度矩阵归置为0-1矩阵,即图片的二值化过程。5 问题一的解答5.1 建模思路将图片导入MATLAB软件中
7、对图片进行预处理,以获得图片的像素点灰度值矩阵,进而转化成矩阵之间相关性计算问题。矩阵的计算过程如下:首先,在获得灰度值矩阵后,提取每个矩阵的第一列与最后一列分别得到两个分别是第一列与最后一列的矩阵;其次,把得到的新的灰度值矩阵做二值化处理;再次,利用矩阵两列的相关性系数判断其匹配程度;最后完成图片的拼接复原顺序和输出复原图片。5.2 模型建立(1)分别读取19张图片的19个像素点的灰度值矩阵,分别将每个矩阵的第一列取出获得新的矩阵;同时分别将每个矩阵的最后一列取出获得新的矩阵;根据像素的特点,我们以一半像素为分界点,分别将这两个矩阵进行二值化处理得到两个0-1值矩阵BF,BL,处理标准如下:
8、其中, ,两个0-1矩阵的规模为。(2)计算两个碎纸片对应0-1矩阵左右两边的相关系数,相关性越高表明这两块碎纸片匹配的概率就越大。相关性系数的计算如下:其中,为各个边缘列的灰度值, 表示灰度值的均方值。(3)在匹配过程中加入了阈值指标,当两个碎纸片0-1矩阵相关度大于指标时两碎片有匹配可能,当拼接或有多种可能时需加入人工干预人工筛选出与之最匹配的碎片。根据汉字的特点,定义阈值为0.7,说明当相关系数大于0.7时,两列数据有强相关性,即两碎片匹配几率较大。对于英文文章的拼接复原,考虑到英文字符的特点,我们将临界匹配阈值设定为0.6,即当相关性系数大于或等于0.6时,说明两列数据具有强相关性,即
9、两碎片匹配几率较大。本文从相关系数表中提取系数大于阈值的各边缘的相关系数:表1:汉字纸片的阈值设定汉字碎片阈值相关性无相关性弱相关强相关表2:英文纸片的阈值设定汉字碎片阈值相关性无相关性弱相关强相关5.3模型的求解及结果分析根据以上模型,运用MATLAB软件编程(源程序见附录3、4),得到图片的拼接复原顺序,见表1和表2。中文文档复原结果见附录1,英文文档复原结果见附录2。表1:中文文档的图片复原排序8141215310216145913181171706表2:英文文档的图片复原排序3627151811051913108121417164从中文、英文文档的复原结果可以看出,拼接后的图像字迹清晰
10、,内容完整,说明本题的模型和算法能有效地实现纵切文档图像的拼接复原。 6 问题二的解答6.1建模思路: 对于纵横切的情形,在增加横切之后,两图片边界处共同信息量大大减少,故需要更进一步地挖掘可用信息,如图片的四个边界信息。纵观整个问题,我们作如下考虑:(1)用问题一的方法对图像进行预处理,分别构建反映中、英文文档行特征的特征向量以及确定需要扫描像素行的行数; (2)通过分别建立特征匹配模型,左右边界匹配模型,上下边界匹配模型三个模型,完成单页打印横纵切纸片匹配模型的构建;(3)对模型进行求解,特别的,特征匹配模型求解后加入人工干预,最后复原出整个图片。6.2 模型建立6.2.1模型的准备(1)
11、对于图像的处理,同第一问一样,我们使用MATLAB软件读取每张图片的灰度值矩阵,并进行二值化处理,转化为0-1值矩阵。(2)构建中文特征灰度条向量(聚类分析)特征灰度条是指记录图片中文字的行方向信息的列向量,建造特征灰度条的方法为:对于预处理后的图像,建造一个与碎片的图像行数一致的列向量,对图像中像素行进行扫描,若此行中有像素值为 0 的点,则将列向量中相同行处的值设为 0,否则设为 1。图 000.bmp 的特征灰度条如图 1 所示 图1 000.bmp及其灰度条特征灰度条的列向量为: 便可得到每张碎纸片的特征灰度条。若某两张碎片的灰度条相似程度达到精度要求,则它们就具有相同的图像行特征,位
12、于原文件的同一行。(3)确定扫描像素行的行数扫描一幅图片的像素点,其自然的思路就是对第张图像的每一行进行扫描,得到每行的像素值。但在构造特征灰度条矩阵的时候,发现了一些特殊情况,如下图所示:图 特殊情况举例编号为008 和编号为 009的图片可以认为判断他们是左右相邻的,由于图片的下部是空白部分,在匹配过程中可能出现,重复匹配的情况,即原本不该归为一类的情况可能放在一起,为此我们根据图片与汉字的特点,我们在进行扫描时尽量扫描图片的三分之二的高度区域。这样可以减轻计算的复杂度,避免结果的冗余,提高结果的准确性。按照每张图片的像素矩阵尺寸,我们设定的扫描行数定为120行。6.2.2 建立横纵切纸片
13、匹配模型(1).聚类分析模型 将碎片与碎片进行特征比较,(),即求碎片的特征列向量和碎片的特征列向量对应元素差的绝对值,再求和,得到特征值考虑到每个汉字或英文字母结构的差异性,位于同一行文字的高度可能会出现微小的偏差,很难出现特征灰度条相同(即)的情况,若取作为判断原则,那么原本位于同一行的两张图片可能因为这微小的偏差而归于不同的行集合中。取一个合适小的置信区间,若,则认为碎片与碎片来源于文件的同一行。(2)建立左右边界匹配模型本问中的左右边界匹配模型相对于第一问中的边界匹配模型而言,差异性在于问题一中的边界匹配模型是19条纵向大长条,信息量大,而本问中是纵向小长条,信息量小。问题二中的左右边
14、界矩阵为;(3)建立上下边界匹配模型将第张图篇的上、下边界处的元素分别存于矩阵的第一行、第二行中。即上下边界匹配模型中第k行的上下边界矩阵为:故模型的构建如下:1、 上边界匹配模型的构建将第行的上边界与第()行的下边界进行上边界匹配,即求第行的边界矩阵的第一行与第行的边界矩阵的第二行对应列元素的差,再求差的绝对值的和将第行的上边界依次与其余的任意一行的下边界进行上边界匹配,得到个值:,通过比较,取这个值中的最小值,作为上边界匹配值。2、下边界匹配模型的构建将第行的下边界与第()行的上边界进行下边界匹配,即求第行的边界矩阵的第二行与第行的边界矩阵的第一列对应列元素的差,再求差的绝对值的和将第行的
15、下边界依次与其余的任意一行的上边界进行下边界匹配,得到个值:,通过比较,取这个值中的最小值,作为上边界匹配值。3、最佳边界匹配模型的建立取第行,先与任意一行()依次进行上匹配,求得,再与任意一行依次进行下匹配,取两者之间的最小值 对应的匹配方式即为第行与第行的最佳匹配方式。若,则说明第行上边接于第行的下边;,说明第行的下边与第行的上边相连。综上,我们构建的横纵切纸片匹配模型为:6.3 模型的求解(1)根据以上模型,运用MATLAB编程(源程序间附录),得到每行集合的碎片个数,附件3(中文)对应的15个行集合中碎片个数,如表所示:表4:15行中每行的碎片个数行集合的编号1234567891011
16、12131415碎图片的个数19191918151919193218161814由上表知道:包含19个碎图片行集合的个数有6个,编号分别为:1、2、3、6、7、8,这6个可以唯一对应原文件的6个图像行;行集合的包含的图片个数大于10且小于19的行的个数有5,分别的标号为:4、5、11、12、13,这些行集合包含于原文件图片组成的行。而行集合中元素个数小于10的行的个数有4个,行集合编号分别为:9、10、14、15。由于附件中的图片是1119个,所以需要将4个行集合中的图片分配到5个行集合中去。(2)此外还得到了每行所包含的图片编号,考虑到数据过多,仅列举其中三行,见表5。行集合的编号碎图片的编
17、号12(3) 人工干预结合附件3、4中1119规模的文件,在特征匹配模型求解完成后加入第一次人工干预,即将表5中4个行集合中的图片元素通过与对应的5个行集合的图片进行人工配对,来人为生成与原文件相同的11个行集合。具体的人工配对方法如下:a.按行集合编号的顺序选择9集合中的一个图片,通过文义匹配和边缘断线匹配的方法,将其与集合4、5、11、12、13中各抽取出一个图片共5张图片,进行依次比较,如果与某行集合中的那个图片匹配成功,就将这个图片存入该行集合中;b.循环进行a的步骤,直至将集合9、10、14、15中共计10个图片分别归于各自的行集合中。在最不利的情况下,需要匹配次,而在最有利的情况下
18、只需配对9次。可见,人工干预的复杂度不高,从而充分发挥了人工智能的准确度高的优点,而且很好的规避了人效率不高的缺点。+ + + + 通过人工干预,将未分配的图片归入对应的行中之后,利用左右边界匹配模型对附件三中每一行图片进行横向排序,使行内图片排列固定下来。附件3中的各类图片的排列顺序如表7:复原结果将已经得到的行内图片排列顺序以及行与行之间的排列顺序相结合,便可以得到各个碎图片在原文件中的位置,从而将原文件复原。附件3(中文)复原的图片排列顺序见表6,复原结果见附录。表7:附件3(中文)复原的图片排序4954651431862571921781181909511221292891188141
19、611978676999162961317963116163726177205236168100766214230412314719150179120861952618718381484616124358118912210313019388167258910574711568313220017803320219815133170205851521652760141283159821991351273160203169134393151107115176943484183904712142124144771121499713616412758431251318210919716184110187
20、6610615021173157181204139145296411120159218048377555442061010498172171597208138158126681754517401375356931537016632196891461021541144015120715514018510811741011131941191236.3 结果分析加入人工干预后,复原后的文件字迹清晰,内容完整,复原的效果良好。检验未加入人工干预计算机排序结果,本题中人工干预只选择图片的首序列,对图片的排列顺序没有任何影响,所以附件3(中文)的排序正确率为90.4%,附件4(英文)的排序正确率为65.1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 纸片 拼接 数学模型 教学 教材
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。