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

基于旅行商模型的文字碎纸片拼接复原-浙江工业大学

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

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

 

基于旅行商模型的文字碎纸片拼接复原-浙江工业大学B254_1B1113.rar

 

所属学校:西南交通大学;

参赛队员:姜荣杰 朱佳亭 金建邦。

 

摘要

文字碎纸片拼接复原是一项在司法物证复原、历史文献修复以及军事情报获取等领域有着广泛应用的工作。所以对文字碎纸片的研究的重要性不言而喻。本文研究的目的皆在建立数学模型与算法,解决碎片复原中的三个问题,使得对三种不同特点碎片复原的人工干预次数较少,尽可能实现碎片复原的全自动化。

问题一,对纵切碎片复原。我们建立模型一,给出了基于旅行商问题的拼接策略。我们发现,碎片的拼接问题就是找到碎片昀好的排列,找到一个排列类似于在一个图中找到一条路径。基于此,我们将碎片拼接问题抽象为一个图论问题,将碎片看做图中的顶点,碎片与碎片之间的匹配程度(匹配距离)看做图的边权。由此我们将碎片的拼接问题转化为一个哈密尔顿路径问题(不回到源点的旅行商问题)。

在问题一中的匹配距离为碎片边界横向匹配距离,即为一种衡量碎片与碎片在左右方向上边界图像匹配程度的指标,匹配距离越短,说明两碎片边界越相似,匹配程度越好。

模型一可用 lingo与 matlab编程求解。由于旅行商问题的求解是整体寻优,得到的结果为全局昀优解,所以其准确性较高。对附件 1与附件 2的碎片还原结果我们没有进行人工干预。

问题二,对既纵切又横切的碎片复原。我们建立模型二,给出基于文本行特征的碎片行分组算法,对行分组碎片进行横向拼接得到复原的碎片行,再对碎片行进行纵向拼接,得到昀终复原结果。这两种拼接策略均为模型一中基于旅行商问题的拼接策略。

其中,文本行特征即为文本行之间的规整性,利用文本行的规整性不仅可以对碎片进行行分组,而且还可以提高文本纵向拼接的准确度。

我们根据模型二,对附件 3碎片还原的结果没有人工干预;在对附件 4碎片还原时在行分组碎片横向拼接后有人工干预,即偶尔人工调整个别碎片还原结果。

问题三,对双面碎片复原。我们建立模型三,该模型中对碎片的行分组以及横向拼接同模型二中的方法,但考虑到碎片有两面,所用到的匹配距离需要替换为正反面匹配(两面的匹配距离之和)。此外,在对碎片行做纵向拼接时与模型二中的方法略有不同,由于碎片有双面信息,我们将模型一中基于旅行商问题的拼接策略扩展为多旅行商( 2个旅行商)问题的拼接策略,即一条旅行商路径代表纸张的一面,另一条旅行商路径代表纸张的另一面。

对于模型三,由于采用了正反面匹配距离,用到了两面信息,其可用于拼接的信息量相对于单面碎片而言增大了一倍,所以对附件 5碎片还原结果没有人工干预。

综上所述,我们建立的碎片复原模型与算法人工干预次数较少,对碎片复原工作有一定的参考价值。

关键词:哈密尔顿路径 旅行商问题 匹配距离 文本行特征 碎片分组

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

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


  • 支持

  • 高兴

  • 震惊

  • 愤怒

  • 无聊

  • 无奈

  • 谎言

  • 枪稿

  • 不解

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

推荐活动