中国大学生在线首页 设为首页 在线投稿 实名注册指南
官方微博

基于旅行商规划模型的碎纸片拼接复原问题研究-国防科学技术大学

我要评论(0) 字号:T T 2013年11月12日 来源:全国大学生数学建模竞赛组委会

【导读】2013高教社杯全国大学生数学建模竞赛优秀论文选登 声明:未经全国大学生数学建模竞赛组委会书面许可,不得转载。

 

基于旅行商规划模型的碎纸片拼接复原问题研究-国防科学技术大学B379_1B1802.rar

 

所属学校:国防科学技术大学;     

参赛队员:1. 向航,2. 王帆,3.郭树璇;

基于旅行商规划模型的碎纸片拼接复原问题研究

 

摘要

本文分别针对RSSTD(Reconstruction of Strip Shredded Text Document)、RCCSTD(Reconstruction of cross-cut Shredded Text Document)和Two-Sides RCCSTD三种类型的碎纸片拼接复原问题进行了建模与求解算法设计。首先我们对于RSSTD问题,建立了基于二值匹配度的TSP模型,并将其转化为线性规划模型,利用贪心策略复原了该问题的中文和英文碎片;然后对于RCCSTD问题,由于中英文字的差别,我们分别建立了基于改进误差评估的汉字拼接模型和基于文字基线的误差评估的英文字拼接模型,并利用误差评估匹配算法,复原了该问题的中文和英文碎片;随后我们针对正反两面的RCCSTD问题,利用基线的概念将正反两面分行,转化为RCCSTD问题,并复原了该问题的英文碎片。最后,我们对模型的算法和结果进行了检验和分析。

◎问题一:我们针对仅纵切的情况,首先将图像进行数字化处理,转换为了二值图像,然后得到各图像的边缘,并计算所有碎片与其他碎片边缘的匹配程度。然后,根据两两碎片之间的匹配程度建立了TSP模型,并将其划归为线性规划模型。最终,我们根据左边距的信息确定了左边第一碎片,随后设计了基于匹配度的贪心算法从左向右得到了所有碎片的拼接复原结果。结果表明我们的方法对于中英文两种情况适用性均较好,且该过程不需要人工干预。

◎问题二:我们针对既纵切又横切的情况,由于中英文的差异性,我们在进行分行聚类时应采用不同的标准。首先根据左右边距的信息确定了左边和右边的碎片,随后分别利用基于改进误差评估的汉字拼接模型和基于文字基线的误差评估模型,将剩余的碎片进行分行聚类,然后再利用基于误差评估的行内匹配算法对行内进行了拼接,最终利用行间匹配算法对行间的碎片进行了再拼接,最终得到了拼接复原结果。对于拼接过程中可能出现误判的情况,我们利用GUI编写了人机交互的人工干预界面,用人的直觉判断提高匹配的成功率和完整性。

◎问题三:我们针对正反两面的情况,首先根据正反基线信息,分别确定了左右两边的碎片,然后利用基线差值将其两两聚类,聚类以后其正反方向也一并确定,随后我们将其与剩余碎片进行分行聚类,最终又利用行内匹配和行间匹配算法得到了最终拼接复原结果。其中,对于可能出现的误判情况,我们同样在匹配算法中使用了基于GUI的人机交互干预方式,利用人的直觉提高了结果的可靠性和完整性。

关键字:碎片复原、TSP、误差评估匹配、基线误差、人工干预 

[责任编辑:刘宇宏]
分享到:
复制链接 打印

查看心情排行你看到此篇文章的感受是:


  • 支持

  • 高兴

  • 震惊

  • 愤怒

  • 无聊

  • 无奈

  • 谎言

  • 枪稿

  • 不解

  • 标题党
查看网友评论网友评论( 网友评论仅供其表达个人看法,并不表明本站同意其观点或证实其描述。)
用户名: 快速登录

推荐活动