- 1、本文档共23页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
2013年国赛B题讲评
2014年数学建模竞赛湖南赛区研讨会
2013B题“碎纸片拼接复原”评论
题 目
B题 碎纸片的拼接复原
破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重要的应用。传统上,拼接复原工作需由人工完成,准确率较高,但效率很低。特别是当碎片数量巨大,人工拼接很难在短时间内完成任务。随着计算机技术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率。请讨论以下问题:
1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片拼接复原模型和算法,并针对附件1、附件2给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预,请写出干预方式及干预的时间节点。复原结果以图片形式及表格形式表达。
题 目
2. 对于碎纸机既纵切又横切的情形,请设计碎纸片拼接复原模型和算法,并针对附件3、附件4给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要人工干预,请写出干预方式及干预的时间节点。复原结果表达要求同上。
3. 上述所给碎片数据均为单面打印文件,从现实情形出发,还可能有双面打印文件的碎纸片拼接复原问题需要解决。附件5给出的是一页英文印刷文字双面打印文件的碎片数据。请尝试设计相应的碎纸片拼接复原模型与算法,并就附件5的碎片数据给出拼接复原结果,结果表达要求同上。
目 录
命题背景
解题思路
评阅要点
存在问题
几点评价
命 题 背 景
有实际应用
难度适中
参考文献少
一篇参考文献:Reconstruction of shredded document based on image feature matching
解 题 思 路
第一步:分行
行距信息 :普遍做法,精度略差(尤其是英文),大约是80%左右,技术含量不足。
聚类算法:主流算法,技术含量较高,效果好。
图1:英文文本行特征—像素行和
解 题 思 路
第一步:分行——聚类算法
计算Ai 的行和,得到180维向量ri。定义合适的向量相似度,对ri(i = 1;2;: :: ; n)进行相似度计算,然后对所有碎片进行聚类,从而得到分行结果。
解 题 思 路
第一步:分行——聚类算法
几种相似性度量
欧氏距离倒数:
夹角余弦:
相关系数:
解 题 思 路
第一步:分行——聚类算法
相似度定义
欧式距离倒数
夹角余弦
相关系数
总正确率
91.39
91.39
92.34
1
89.47
89.47
89.47
2
84.21
89.47
89.47
3
94.74
94.74
94.74
4
84.21
78.95
84.21
5
100.00
100.00
100.00
6
94.74
94.74
94.74
7
94.74
94.74
94.74
8
84.21
89.47
89.47
9
94.74
94.74
94.74
10
84.21
78.95
84.21
11
100.00
100.00
100.00
解 题 思 路
第一步:分行——规划算法
假设每一组最左边一块可以识别出来,记为 ,其他198块碎片记为 ,相似度记为 ,则可以求解以下0-1线性规划求得分组结果:
s.t.
解 题 思 路
第二步:行内排序——距离定义
欧氏距离
夹角余弦
相关系数
解 题 思 路
第二步:行内排序——距离定义
考虑斜率的距离:
考虑像素阵列分布的距离:
解 题 思 路
第二步:行内排序——排序算法
贪心算法1:从左到右逐步拼接
贪心算法2:从右到左逐步拼接
贪心算法3:所有邻接距离中最小的两片拼接
图论+规划方法:按邻接距离定义有向权图,将最佳排序问题转化为TSP问题,再应用规划软件求解。
解 题 思 路
第二步:行内排序——排序算法
规划方法:定义两碎片i,j之间边缘(有向)距离为rij,并规定ri0=r18,j=∞,求解以下规划模型:
如果求解结果无子回路,则得到问题最优解。
解 题 思 路
第二步:行内排序——排序算法
您可能关注的文档
- 20120509老年健康管理规范-技术杜雪平.ppt
- 20122012年中考时政热点专题.ppt
- 20120718战略宣讲培训——CSST智慧新城建设分享已改.ppt
- 2012中考时政材料.PPT.ppt
- 20121105第10课:物业管理前期介入及案例分析.ppt
- 2012军事理论课总结.ppt
- 2011涂装车间安全工作回顾.ppt
- 2012九年级第二次月考试卷讲评.ppt
- 2012商事法律2.ppt
- 2012万科品牌及佛山发展介绍.ppt
- 2021-2022学年湖南省常德市安乡县四年级上学期期中语文真题及答案.pdf
- 2023-2024学年河南省南阳市社旗县四年级上学期期中数学真题及答案.pdf
- 2022-2023学年云南省曲靖市四年级下学期期末数学真题及答案.pdf
- 2021-2022学年河南省周口市鹿邑县二年级下册月考语文真题及答案.pdf
- 2018年河南焦作解放区教师招聘考试真题及答案.pdf
- 2019年江西公务员行测考试真题及答案-乡镇.pdf
- 2019中国石油报社应届高校毕业生招聘试题及答案解析.pdf
- 光大银行招聘应届毕业生能力素质测试笔试真题及答案.pdf
- 2024年广西百色教师招聘考试模拟题及答案.pdf
- 2021-2022学年浙江绍兴诸暨市五年级上册语文期末试卷及答案.pdf
文档评论(0)