单面英文碎纸片的拼接复原及算法实现

《单面英文碎纸片的拼接复原及算法实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第34卷第1期延安大学学报(自然科学版)Vol．34No．12015年3月JournalofYananUniversity(NaturalScienceEdition)Mar．2015DOI:10．13876/J．cnki．ydnse．2015．01．014单面英文碎纸片的拼接复原及算法实现金明娅，孙丹蕾，赵艳，窦霁虹(西北大学数学学院，陕西西安710127)摘要:先对碎片文件的边缘轮廓色彩灰度值及所包含内容的格式等进行特征分析，再通过定义差异度指数、高度差建立双目标0－1规划模型，运用聚类分析、MATLAB搜索算法和人工干预等相结合，实现单面文件既被横切也被纵切碎纸片的拼接复

2、原。关键词:差异度指数;0－1规划;MATLAB软件;聚类分析;高度差中图分类号:O242文献标识码:A文章编号:1004－602X(2015)01－0014－05无明显语法、词语和单词错误，证明复原图片正确。1问题分析2单面英文碎纸片拼接复原初步模型破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。随2.1提取信息:差异度指数着计算机技术的发展，人们试图开发碎纸片的自动我们用差异度指数来衡量任意块碎片右侧边缘［1］拼接技术，来提高拼接复原效率。与任意块碎片左侧边缘差异及任意块碎片下侧边缘［2］本文以2013年全国大学生数学建模竞赛B与任意块碎片

3、上侧边缘的差异。定义差异度指数Lij题为例，研究单面英文文件既被横切也被纵切的碎和Uij:Lij表示第i块碎片右侧和第j块碎片左侧的差纸片的拼接复原问题。异度，为第i块碎片右侧与第j块碎片左侧的对应灰要对建模B题附件4中的碎纸片进行拼接复度值之差的绝对值的累和。Uij表示第i块碎片下侧原，需建立碎纸片拼接复原模型和算法。由于209和第j块碎片上侧的差异度，为第i块碎片下侧与第j块英文碎片都有左侧、右侧和上侧、下侧，每块碎片块碎片上侧的对应灰度值之差的绝对值的累和。边缘灰度已知，需要同时考虑每块碎片左右侧与其公式如下:180他碎片的差异以及上下侧与其他碎片的差异，通过kkLi－

4、Lj，i=1，2，…，209，k=1该差异值可定义两个差异度指数，得到双目标0－1Lij={j=1，2，…，2009，i≠j规划模型，进而找到碎片的复原顺序。∞，i=j但由于决策变量较复杂，这种模型不易求解，因72kk而提出改进模型:先定义高度差H，运用聚类分析，k=1Ui－Uj，i=1，2，…，209，ij给定高度差阈值，按照高度不同将所有碎片分为23Uij={j=1，2，…，209，i≠j类，并建立双目标0－1规划模型。结合MATLAB∞，i=jk编程和人工干预，将23类碎片处理为11行碎片，再其中:Li表示第i块碎片右侧第k个特征点的k对碎片纵向复原，得到英文复原序号，

5、利用MATLAB灰度值;Lj表示第j块碎片右侧第k个特征点的灰k编程画出复原图片。最后人工检验英文复原图片中度值;Ui表示第i块碎片下侧第k个特征点的灰度收稿日期:2014-11-14作者简介:金明娅(1993—)，女，陕西安康人，西北大学数学学院2011级本科生。第1期单面英文碎纸片的拼接复原及算法实现15k值;Uj表示第j块碎片上侧第k个特征点的灰度值。碎片下侧和第j张碎片上侧的相连;以此模型可以kkkk说明:Li、Lj和Ui、Uj已知，将竞赛题附件4中得到所有碎片的连接方式。所有碎片数据带入MATLAB软件可得到每块碎片3英文碎片拼接复原改进模型的左侧、右侧和上侧、下侧灰

6、度值;从而得到两个差异度矩阵如下:由于建立的初步模型决策变量较复杂，且两个LL…L差异度矩阵较大，用程序实现较困难，因此在此提出é1，11，21，209ù［3］êú改进模型，只使用一种决策变量，具体建模过程L2，1L2，2…L2，209êú，如下:ê…………úêú3.1提取信息:差异度指数和高度差ëL209，1L209，2…L209，209û定义差异度指数Lij，与初步模型定义相同，但éU1，1U1，2…U1，209ùêú改进模型中不再使用差异度指数Uij，定义高度差U2，1U2，2…U2，209êú。Hij，表示第i块碎片第一行文字中心到第i碎片上ê…………úêú侧边缘的高度

7、Hi与第j块碎片第一行文字中心到ëU209，1U209，2…U209，209û第j碎片上侧边缘的高度Hj之间的差值。公式如2.2英文碎纸片拼接复原模型下:以第j块碎片左侧与第i块碎片右侧的差异度Hi－Hj，i=1，2，…，209，最小和第j块碎片上侧与第i块碎片下侧的差异度H=ij{j=1，2，…，209，i≠j最小为双目标函数，以第i块碎片右侧与第j块碎片0，i=j左侧是否相连为决策变量αij(αij≥0)和第i块碎片3.2英文碎纸片拼接复原模型下侧与第j块碎片上侧是否相连为决策变量βij