最新-碎纸片的拼接复原问题大学生数学建模全国一等奖论文精品.pdf
《最新-碎纸片的拼接复原问题大学生数学建模全国一等奖论文精品.pdf》由会员分享,可在线阅读,更多相关《最新-碎纸片的拼接复原问题大学生数学建模全国一等奖论文精品.pdf(6页珍藏版)》请在三一文库上搜索。
1、碎纸片的拼接复原问题 摘要 为解决碎纸片的拼接复原问题,我们通过定义差异度指数、高度差,建立0-1 规划 模型,使用聚类分析、 MATLAB 搜索算法和人工干预等相结合,得到了所有附件复原序号 和复原图片。 针对问题一,首先提取附件1、2 中所有碎片左侧和右侧边缘灰度,通过任意列碎 片右侧和任意列碎片左侧的边缘灰度差值可以定义差异度指数,从而得到差异度特征矩 阵,然后建立 0-1 规划模型,以第 i 张碎片右侧与第 j 张碎片左侧差异度最小为目标函 数,以第 i 张碎片右侧与第 j 张碎片左侧是否相连为决策变量,以每张碎片右侧一定与 某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条
2、件。算法为先提取 任意张碎片边缘灰度值,得到差异度矩阵,带入规划模型中,通过LINGO软件找到中英 文碎片的拼接方法,得到复原序号如表一、表二,从而得到出中文与英文复原图片。 表一: 中文碎片的复原序号 008 014 012 015 003 010 002 016 001 004 005 009 013 018 011 007 017 000 006 表二:英文碎片的复原序号 003 006 002 007 015 018 011 000 005 001 009 013 010 008 012 014 017 016 004 检验中英文碎片拼接复原顺序准确性,利用MATLAB 搜索算法,可以
3、得到中英文碎 片拼接方法。结果表明两种方法得出的中英文复原顺序相同,复原图片相同,同时人工 检验中英文复原图片中无明显语法、单词错误,证明复原图片准确。 针对问题二,由于每张碎片有左侧、右侧和上侧、下侧,与问题一相同,可以定义 两个差异度指数,建立双目标0-1 规划模型。但由于差异度矩阵过大,决策变量复杂, 我们又建立了改进的简化模型,定义高度差,运用聚类分析方法,按照高度不同将所有 碎片分为 18 类,然后再以第 j 块碎片左侧与第 i 块碎片右侧的差异度最小为目标函数, 以第 i 块碎片右侧与第 j 块碎片左侧是否相连为决策变量,以每块碎片右侧一定与某块 碎片左侧相连、每块碎片左侧一定与某
4、块碎片右侧相连,满足高度差阈值为约束条件, 建立单目标 0-1 规划模型。算法为先提取任意块碎片边缘灰度值和高度,得到差异度矩 阵,编程将中文碎片按高度分为18 类,人工干预分为 11 行,再利用问题一中碎片纵向 复原方法,得到中文复原序号,画出中文复原图片。(英文复原模型相似,仅高度差阈 值不同) 针对问题三,对于双面英文碎片的复原问题,我们提出了单词残缺程度的定义,定 量的描述了英文碎片的特征信息,构成了算法的核心内容,运用编程和人工干预将碎纸 片分为 11 类,每类 19 个碎片,在此基础上利用前两问所建的0-1 规划模型,再加上双 面的一些约束条件,得到双面英文复原序号,并绘出英文双面
5、复原图片。 关键词: 差异度指数; 0-1 规划; LINGO软件;聚类分析;高度差;残缺程度; 一、问题重述 破碎文件的拼接在司法物证复原、历史文献修复以及军事情报获取等领域都有着重 要的应用。传统上,拼接复原工作需由人工完成,准确率较高,但效率很低。特别是当 碎片数量巨大,人工拼接很难在短时间内完成任务。随着计算机技术的发展,人们试图 开发碎纸片的自动拼接技术,以提高拼接复原效率。请讨论以下问题: 1. 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立碎纸片 拼接复原模型和算法,并针对附件1、附件 2 给出的中、英文各一页文件的碎片数据进 行拼接复原。如果复原过程需要人工干
6、预,请写出干预方式及干预的时间节点。复原结 果以图片形式及表格形式表达。 2. 对于碎纸机既纵切又横切的情形, 请设计碎纸片拼接复原模型和算法,并针对附 件 3、附件 4 给出的中、英文各一页文件的碎片数据进行拼接复原。如果复原过程需要 人工干预,请写出干预方式及干预的时间节点。复原结果表达要求同上。 3. 上述所给碎片数据均为单面打印文件,从现实情形出发, 还可能有双面打印文件 的碎纸片拼接复原问题需要解决。附件 5 给出的是一页英文印刷文字双面打印文件的碎 片数据。请尝试设计相应的碎纸片拼接复原模型与算法,并就附件5 的碎片数据给出拼 接复原结果,结果表达要求同上。 二、模型假设 1.假设
7、每个碎纸片上的字和字母都没有发生扭曲。 2.假设每个碎纸片的形状和大小完全相同。 3.假设每个碎纸片上灰度值的提取都是完全正确的值不等于255 的都是黑点 三、符号说明 符号符号的含义 ij C差异度指数,表示第i张碎片右侧和第j张碎片左侧的差异度; ik C 表示第i张碎片右侧第k 个特征点的灰度值; ij x 决策变量,当 ij x =0 时,表示第 i 张碎片右侧和第 j 张碎片左侧的不相连; ij x =1 时,表示第i张碎片右侧和第 j 张碎片左侧的相连; ij S 表示第 j 列碎片左侧与差异度最小的第i 列碎纸片右侧相连; ij L 表示第i块碎片右侧和第 j 块碎片左侧的差异度
8、; ij U表示第i块碎片下侧和第j块碎片上侧的差异度; ik L表示第i块碎片右侧第k 个特征点的灰度值; ik U表示第i块碎片下侧第k 个特征点的灰度值; ijij =0 时,表示第i张碎片右侧和第j张碎片左侧的不相连; ij =1 时,表示第i张碎片右侧和第j张碎片左侧的相连; ij ij =0 时,表示第 i 张碎片下侧和第 j 张碎片上侧的不相连; ij =1 时,表示第i张碎片下侧和第 j 张碎片上侧的相连; ij H 高度差表示第i 块碎片第一行文字中心到第i 碎片上侧边缘的高度 i H与第 j 块碎片第一行文字 中心到第 j 碎片上侧边缘的高度 j H 之间的差值; 四、问题
9、一分析与模型建立、求解 4.1 问题一的分析 问题一要求对于给定的来自同一页印刷文字文件的碎纸机破碎纸片(仅纵切),建立 碎纸片拼接复原模型和算法,并针对附件1、附件 2 给出的中、英文各一页文件的碎片 数据进行拼接复原。参考文献1 ,由于每列中文和英文碎片都有左侧和右侧,需要考 虑每一列碎片的左侧和右侧与其他列的左侧和右侧差异,每列碎片边缘灰度已知,通过 任意列碎片右侧和任意列碎片左侧的差异值可以定义差异度指数(同一列碎片的左侧与 右侧的差异度定义为无穷大) ,从而得到差异度特征矩阵。 然后可以通过 0-1 规划模型,以第 j 张碎片左侧与第 i 张碎片右侧的差异度最小为 目标函数,以第 i
10、 张碎片右侧与第 j 张碎片左侧是否相连为决策变量,以每张碎片右侧 一定与某张碎片左侧相连、每张碎片左侧一定与某张碎片右侧相连为约束条件(复原图 片最左侧一定与最右侧的差异度最小),找到中文和英文碎片的拼接复原顺序,MATLAB 编程得到复原序号,从而得到出中文与英文复原图片。 为了检验中文与英文碎片拼接复原顺序是否正确,建立了MATLAB 搜索算法模型, 可以得到中文与英文碎片拼接方法,MATLAB 软件可以直接画出中文与英文复原图片。结 果表明两种方法得出的中文与英文复原顺序相同,复原图片相同。同时人工检验出中文 与英文复原图片中无明显语法、词语和单词错误,证明复原图片正确。 4.2 问题
11、一的碎纸片拼接复原模型建立 先提取碎纸片边缘差异信息,再进行图片拼接复原,具体步骤如下: (1)提取信息:差异度指数 用差异度指数来衡量任意列右侧边缘与任意列左侧边缘差异。 定义差异度指数 ij C,表示第 i 张碎片右侧和第j 张碎片左侧的差异度,为第i 张碎 片右侧与第 j 张碎片左侧的对应灰度值之差的绝对值的累和。公式如下: 时,当 时,当 ji jijiCC C k jkik ij 19.2, 1,19,.,2, 1, 1980 1 (1) 其中: ik C表示第 i 张碎片右侧第 k 个特征点的灰度值 jk C表示第 j 张碎片右侧第 k 个特征点的灰度值 说明: ik C和 jk
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最新 纸片 拼接 复原 问题 大学生 数学 建模 全国 一等奖 论文 精品
链接地址:https://www.31doc.com/p-5578396.html