论文0913.pdf

2013 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 承承 诺诺 书书 我们仔细阅读了 全国大学生数学建模竞赛章程 和 全国大学生数学建模竞赛参 赛规则 以下简称为 竞赛章程和参赛规则 可从全国大学生数学建模竞赛网站下载 我们完全明白 在竞赛开始后参赛队员不能以任何方式 包括电话 电子邮件 网 上咨询等 与队外的任何人 包括指导教师 研究 讨论与赛题有关的问题 我们知道 抄袭别人的成果是违反竞赛章程和参赛规则的 如果引用别人的成果或 其他公开的资料 包括网上查到的资料 必须按照规定的参考文献的表述方式在正文 引用处和参考文献中明确列出 我们郑重承诺 严格遵守竞赛章程和参赛规则 以保证竞赛的公正 公平性 如有 违反竞赛章程和参赛规则的行为 我们将受到严肃处理 我们授权全国大学生数学建模竞赛组委会 可将我们的论文以任何形式进行公开展 示 包括进行网上公示 在书籍 期刊和其他媒体进行正式或非正式发表等 我们参赛选择的题号是 从 A B C D 中选择一项填写 B 我们的参赛报名号为 如果赛区设置报名号的话 J0420 所属学校 请填写完整的全名 西安电子科技大学 参赛队员 打印并签名 1 汤敬浩 2 陈柯宇 3 张 珊 指导教师或指导教师组负责人 打印并签名 教练组 日期 2013 年 09 月 15 日 赛区评阅编号 由赛区组委会评阅前进行编号 2013 高教社杯全国大学生数学建模竞赛高教社杯全国大学生数学建模竞赛 编编 号号 专专 用用 页页 赛区评阅编号 由赛区组委会评阅前进行编号 赛区评阅记录 可供赛区评阅时使用 评 阅 人 评 分 备 注 全国统一编号 由赛区组委会送交全国前编号 全国评阅编号 由全国组委会评阅前进行编号 1 碎纸片的拼接复原 摘 要 本文针对单面纵切 横纵切和双面横纵切三种情况下碎纸片拼接复原的问题 建立 边缘特征匹配模型 采用模拟退火算法 给出拼接后的复原结果图及序号表 针对问题一 建立纵切图像拼接中的边缘特征匹配模型 即模型一 首先 提取了 碎纸片图像的边缘像素点矩阵 根据汉字和英文的结构特点 在边缘像素点矩阵中合理 地选取了边缘特征点 然后 构造了匹配值公式 并以 19 条碎纸片排列顺序为决策变 量 构造了匹配值目标函数 最后 采用模拟退火算法求解 人工将开头碎纸片置首 得到了汉字和英文的碎纸片序号排列表 分别见文中表 2 表 4 复原结果图分别见附 录 1 图 6 图 8 针对问题二 对模型一进行改进得到模型二 首先 基于图像中文字高度的特征计 算出图像间的相似度 筛选出每行的图像序号 筛选过程中需要人工干预 其次 对每 行的图像采用模型一和模拟退火算法求解 人工将每行图像的开头碎纸片置首后 得到 了每行拼接好的图像 然后 通过对行间距的控制 实现每行图像的上下拼接 最后得 到了汉字和英文的碎纸片序号排列表 分别见文中表 6 表 7 复原结果图分别见附录 1 图 9 图 10 针对问题三 对模型二进行改进得到模型三 首先 分析得到每组图像两面的文字 高度是一致的 单面即可表达双面的高度特征 因此我们仅采用一面进行相似度筛选 筛选出每行的图像序号 筛选过程中需要人工干预 其次 对每行的正反面图像采用模 型一和模拟退火算法求解 人工将每行图像的开头碎纸片置首后 得到了每行拼接好的 图像 然后 仍然通过对行间距的控制 实现了每行图像的上下拼接 最后得到了碎纸 片序号排列表 见文中表 9 表 10 复原结果图见附录 1 图 11 12 最后 对模型的优缺点进行了评价 并给出模型的推广 关键词 数字图像处理 图像拼接 边缘特征 模拟退火 图像相似度 2 1 问题重述 1 1 问题背景 破碎文件的拼接复原在司法物证复原 历史文献修复以及军事情报获取等领域都有 着重要的应用 传统上 拼接复原工作需由人工完成 准确率较高 但效率很低 特别 是当碎片数量巨大 人工拼接很难在短时间内完成任务 随着计算机技术的发展 人们 试图开发碎纸片的自动拼接技术 以提高拼接复原效率 1 2 问题要求 数据文件说明 1 纵切碎片数据 每页纸被切为 19 条碎片 横切碎片数据 每页纸被切为 11 条碎片 2 正反两面数据 两面分别对应文件 000a 000b 3 附件 1 2 为纵切数据 附件 3 4 为横纵切数据 附件 5 为横纵切 双面数据 结果表达格式 1 复原得到的图像放入附录中 2 碎片排列序号放在表格中 放在论文结果中 1 3 问题提出 问题一 对于给定的来自同一页印刷文字文件的碎纸机破碎纸片 仅纵切 建立碎 纸片拼接复原模型和算法 并针对附件 1 附件 2 给出的中 英文各一页文件的碎片数 据进行拼接复原 如果复原过程需要人工干预 请写出干预方式及干预的时间节点 问题二 对于碎纸机既纵切又横切的情形 请设计碎纸片拼接复原模型和算法 并 针对附件 3 附件 4 给出的中 英文各一页文件的碎片数据进行拼接复原 如果复原过 程需要人工干预 请写出干预方式及干预的时间节点 问题三 上述所给碎片数据均为单面打印文件 从现实情形出发 还可能有双面打 印文件的碎纸片拼接复原问题需要解决 附件 5 给出的是一页英文印刷文字双面打印文 件的碎片数据 请尝试设计相应的碎纸片拼接复原模型与算法 并就附件 5 的碎片数据 给出拼接复原结果 2 问题分析 碎纸片的拼接复原过程 需要考虑文字类型 行间距等多种因素的影响 为了建立 合理的模型和算法 求解复原图像 问题分析如下 首先 为了便于计算机对图像信息进行处理 对碎纸片图像进行数字化处理 对于问题一 为了研究图像边缘的拼接问题 应先提取图像左右两侧的边缘信息 通过图像之间的边缘信息关系来确定图像之间是否匹配 由于汉字和英文的结构特点不 同 还需要对于不同的字体进行不同的边缘信息分析 最终制定了汉字 英文两种匹配 值 问题二在问题一的基础上增加了横切的图像 为了使模型一适用性较高 我们研究 了图像之间的相似度 用以反映图像中文字所处高度的相似程度 通过相似度分析可以 得到属于同一行的图像序号 这样问题二的求解转化成了问题一的求解 但将每行图像 复原后 还需要将图像上下拼接 因此除了提取左右两侧的边缘信息 还需要考虑上下 的边缘 分析发现上下边缘无法用问题一中的匹配值匹配 因此我们另外加入了对 行 3 间距 的考虑 问题三在问题二的基础上增加了正反两面的情况 但对于我们的模型和制定的匹配 值 可通过模拟退火算法自动排除图像之间为反面的情况 因此沿用问题二的模型与算 法 此外 我们发现对于每组图像的正反面 图像中文字所处的高度是完全一致的 因 此 在进行图像之间的相似度分析时 可只选择其中一面进行相似度分析 3 模型假设 1 假设忽略图像噪声的干扰 2 假设忽略图像在文本截取时极小部分信息的丢失 4 符号说明 符号 符号说明 Match 两张图像的匹配值 r 相似度 R 相似度矩阵 D 行间距接受度 注 其它未注明符号均在文中有详细解释 5 模型建立与求解 5 1 模型准备 为了便于计算机对图像信息进行处理 对碎纸片图像进行数字化处理 图像数字化 是将连续色调的图像经采样量化后转换成数字信息的过程 其主要过程是 首先 对图 像每个像素点的信息进行采集 然后 将采集到的信息进行量化 对于黑白图来说 常 用的量化指标是灰度值 即将黑色定义为 0 白色定义为 255 0 255 之间的值为黑色与 白色之间的渐变色 最后 将量化后的灰度值以像素点矩阵的形式存储 以方便计算机 处理 Matlab 软件的图像工具箱提供了便捷的图像数字化处理的函数 imread 函数 运 用此函数对题目中提供的碎纸片图像进行数字化处理 结果为 仅纵切的碎纸片图像生 成 1980 72 的像素点矩阵 横纵切的碎纸片图像生成 180 72 的像素点矩阵 5 2 问题一 5 2 1 纵切图像拼接中边缘特征匹配模型 模型一 对于题目中给出的纵切碎纸片图像拼接问题 需要考虑的第一个问题是 直接根据 图像的像素点矩阵拼接碎纸片并不可行 其复杂度等同于直接利用图像的几何特征拼接 提取合理的特征点尤为重要 另一个问题是 图像特征点提取后 当两个图像满足何种 关系时可以认定为可拼接 故匹配值的制定尤为重要 1 边缘特征点 所谓边缘特征点 在本文中指的是针对不同的文字种类对图像边缘信息提取的特征 4 点 选取题目中给出的汉字和英文两种文字种类作为模型建立的基础 考虑到在纵切图 像的拼接过程中 图像左右边缘的匹配程度即可作为是否可拼接的依据 首先 提取图 像左右边缘的像素点矩阵 称之为边缘像素点矩阵 根据这一思想 分别提取汉字和英文的边缘像素点矩阵 汉字和英文两种文字种类 的像素点矩阵均为 1980 72 的矩阵 均提取像素点矩阵的第 1 列和第 72 列作为边缘像 素点矩阵 边缘信息提取后 边缘特征点的提取则是因字体类型而异的 对题目中的汉字类型 和英文类型特征点提取方式如下 1 汉字特征点 根据汉字的结构特点 1 汉字的平均笔画为 10 75 画 结构较复杂 每个汉字在同 一高度笔画相似程度很低 可通过选取图像右边缘中未收笔的笔画作为特征点 与需拼 接图像的左边缘等高度的边缘像素点匹配 达到选出拼接图像的目的 未收笔的笔画是指只有部分 未完成的笔画 在图像中显示为黑色未变灰 对应边 缘像素点矩阵 该点像素值为 0 因此 汉字边缘特征点即为图像右边缘像素点矩阵中为 0 的像素点 2 英文特征点 相较汉字的结构特点 英文字体结构较为简单 若采用与汉字相同的特征点 会出 现如下情况 图 1 英文字母拼接中出行的问题 即字母 c e 拼接中 虽然拼接结果不正确 但 e 能够和 c 中的边缘特征点进行拼接 考虑到还有很多字母间在拼接中存在上述状况 因此 不采用与汉字相同的特征点 选取方式 而采用将边缘所有像素点作为特征点的方式 根据这种思想 在两张图像拼 接中 不仅考虑了左侧图像右边缘的匹配程度 还同时考虑了右侧图像的左边缘的匹配 程度 对于英文这种结构简单的文字类型较为适合 因此 英文边缘特征点即为图像左 右边缘的所有像素点 2 匹配值 所谓匹配值 在本文中指的是两张图像需拼接的边缘特征点灰度值的绝对值距离之 和 当匹配值较小时 说明两张图像色调变化缓和 可拼接度高 根据匹配值的概念 其通用公式可表达为 ii Matchleftright 1 其中 Match 为两张图像匹配值 lefti为拼接后右侧图像的左边缘中第 i 个特征点的灰度 值 righti为拼接后左侧图像的右边缘中第 i 个特征点的灰度值 两种文字类型结构特点的不同以及特征点选取的方式不同 致使其匹配值计算也不 尽相同 在匹配值通用公式下 两种文字类型的匹配值具体计算方式如下 1 汉字类型 根据汉字笔画大全 2 收录的所有汉字笔画 汉字笔画的走势一般有上扬 水平和下 降三种情况 具体形式如下 5 图 2 汉字笔画走势情况 对于情况一 设该特征点高度为 h 即边缘像素点矩阵的行数 若某特征点属于该 匹配情况 那么拼接后 左侧图像右侧边缘高为 h 的像素点应与右侧图像左侧边缘高位 h 1 的像素点匹配 此时 匹配值计算公式应为 1hh matchleftright 同理可得 情况二匹配值计算公式为 hh matchleftright 情况三匹配值计算公式应为 1hh matchleftright 事实上 图像拼接中某特征点匹配情况是未知的 根据匹配值的概念 匹配值越小 则匹配程度越高 则某特征点应属于三种情况下匹配值最小的的匹配情况 因此 汉字类型匹配值计算公式为 11 min hhhhhh i matchleftrightleftrightleftright 2 其中 h 为第 i 个边缘特征点的高度 2 英文类型 相较汉字类型 英文类型并无典型的笔画走势 且英文类型的边缘特征点为左 右 边缘所有的像素点 并无需要特殊考虑的情况 利用匹配值的通用公式 1 即可 在实际求解过程中 需要对 19 条碎纸片的排列顺序进行决策 使得拼接完成后的 图像拼接处匹配值之和越小越好 设向量 1231819 Yy yyyy 为决策向量 表示 19 条碎纸片的排列方案 目标函数 如下 min MMatch Y 3 其中 函数 Match 返回的是输入为 Y 时 拼接完成后的图像拼接处匹配值 5 2 2 算法描述 为了求得上述目标函数的最小值 采用了模拟退火算法 该算法是源于对热力学中 固体退火过程的模拟 在某一给定初温下 通过缓慢下降温度参数 使算法能够在多项 式时间内给出一个近似最优解 且搜索效率较高 模拟退火算法基本步骤如下 Step1 随机生成初始解 yi 令初始温度 T T0 计算目标函数 M yi Step2 根据 yi进行扰动产生一个新解 yj 其中为了使得满足拼接过程中 单个和多个拼 接块的移动 采用了以下三种扰动产生一个新解的方式 分别为 1 二变换 随机产生 1 19 中的两个数 ind1 和 ind2 将 ind1 和 ind2 在解中对应位置的值互换 2 三变换 随机产生 1 19 中的三个数 ind1 ind2 和 ind3 ind1 在解中对应位置的值换到 ind3 在解中对应位置 ind3 在解中对应位置的值换到 ind2 在解中对应位置 ind2 在解中对 应位置的值换到 ind1 在解中对应位置 6 3 块变换 随机产生 1 19 中的三个数 ind1 ind2 和 ind3 将 ind1 和 ind2 在解中对应位置之间 的值换到 ind3 在解中对应位置之后 其中 ind1 ind2 31 2indind ind 否则重新产生 新的随机数 Step3 计算 ji MM yM y 根据 Metropolis 接受准则选择是否接受新解 Metropolis 准则 3 为以新解与当前解的目标函数差定义接受概率 P 即 10 exp0 M P M T 4 Step4 检查是否达到迭代次数 如果不是 转入 Step2 Step5 检查是否满足终止条件 如果不是 转入 Step2 否则程序结束 返回最优解 5 2 3 模型求解 对于上面建立的纵切图像拼接中边缘特征匹配模型 我们利用了方便 实用的 Matlab 图像处理工具箱分别对汉字和英文两种文字类型进行了求解 对于汉字类型 首先 按照汉字类型边缘特征点选取规则 将边缘灰度值 0 进行了 筛选 然后根据汉字类型匹配值的计算方法求得了两图像拼接时的匹配值 最后根据目 标函数利用 Matlab 软件进行求解 得到了 19 个碎片序号的排列如下表 表 1 人工干预前汉字图像复原结果 编号 1 2 3 4 5 6 7 8 9 10 序号 003 010 029 016 001 004 005 009 013 018 编号 11 12 13 14 15 16 17 18 19 序号 011 007 017 000 006 008 014 012 015 汉字复原图见附录 1 图 5 由图 1 很容易发现 该复原图有偏差 这主要是由于开头和结尾未固定 因此我们 人工干预将开头的图像 008 置首 由此得到了正确的 19 个碎片序号的排列顺序 如下 表 表 2 人工干预后汉字图像复原结果 编号 1 2 3 4 5 6 7 8 9 10 序号 008 014 012 015 003 010 029 016 001 004 编号 11 12 13 14 15 16 17 18 19 序号 005 009 013 018 011 007 017 000 006 汉字正确复原图见附录 1 图 6 对于英文类型 首先 根据英文类型匹配值的计算方法得到两图像拼接时的匹配值 然后根据目标函数利用 Matlab 软件进行求解 得到了 19 个碎片序号的排列如下表 表 3 人工干预前英文图像复原结果 编号 1 2 3 4 5 6 7 8 9 10 序号 014 017 016 004 003 006 002 007 015 018 编号 11 12 13 14 15 16 17 18 19 序号 011 000 005 001 009 013 010 008 012 英文复原图见附录 1 图 7 由图 1 很容易发现 该复原图有偏差 这主要是由于开头和结尾未固定 因此我们 7 人工干预将开头的图像 003 置首 由此得到了正确的 19 个碎片序号的排列顺序 如下 表 表 4 人工干预后英文图像复原结果 编号 1 2 3 4 5 6 7 8 9 10 序号 003 006 002 007 015 018 011 000 005 001 编号 11 12 13 14 15 16 17 18 19 序号 009 013 010 008 012 014 017 016 004 英文正确复原图见附录 1 图 8 5 2 4 结果分析 根据模型求解中的结果 分析得到人工干预主要出现在计算机拼接完成后 对开头 碎纸片置首这个过程 出现该现象的原因很有可能是 计算机拼接时只考虑匹配值的最 优 无法考虑到文章内容相关问题 而对于手工拼接工作者来说 很容易就会发现计算 机拼接出来的图像文章内容是读不通的 很快能调整出正确的拼接结果 因此 模型一 不仅快速的解决了该问题 也减轻了手工拼接工作者的工作量 5 3 问题二 5 3 1 横纵切图像拼接中边缘特征匹配模型 模型二 1 模型一适用性分析 模型一在纵切图像拼接中有较好的适用性 但当图像中含有纵切 横切图像时 需 要考虑的因素除了左右边缘的匹配值 还有上下边缘的匹配值 观察图像的左右边缘 与问题一中的左右边缘情况相似 在问题二左右边缘拼接时 可延用模型一 观察图像的上下边缘 容易发现其中空白的比例较大 这使得模型一中 匹配值的计算方法出现了较大的误差 这种计算方法会主动增加空白之间的拼接 但事 实情况并不是如此 空白只是文章中的行间的空白 即行间距 因此 对于问题二中横纵切图像拼接的问题中 需要考虑的第一个问题是 模型一 可以解决同一行中 19 个碎纸片的拼接 不在同一行则无法解决 如何将经横切后处在 同一行的 19 个碎纸片筛选出来 另一个问题是 11 行碎纸片拼接完成后 利用行间距 这个指标拼接出完整的复原图 2 横纵切图像拼接中边缘特征匹配 1 相似度筛选 相似度筛选是指通过图像间的相似度筛选出属于同一类的图像集合 在本文中是指 通过图像间的相似度筛选出属于同一行的 19 个碎纸片 这是基于问题二中所给中英文 图像中 不同图像中每一行文字对应的高度不同 致使其不可能拼接在复原图中的同一 行上 首先给出任意两图像间相似度的计算方法 步骤如下 1 无关信息弱化处理 考虑到我们是根据不同图像中每行文字对应的高度不同筛选出同一行图像 只需计 算图像中每行文字高度的相似度 通过对图像像素点二维矩阵每行所有元素求和 得到 该图像的一维矩阵 该矩阵可有效的说明该图像中每行文字所处的高度 巧妙地忽略文 字信息不同对相似度的影响 称之为高度信息矩阵 因此 构造高度信息矩阵可去除无关信息的干扰 提高相似度的可信度 2 相似度计算 Matlab 中有直接计算图像相似度的函数 corr2 其原理如下 8 首先 对任意两图像的高度信息矩阵 A B 作如下操作 A B AAmean BBmean 5 其中 meanA 和 meanB分别表示 A B 矩阵的平均值 然后 得到相似度 r 其计算公式如下 T TT sum A B r sum A Asum B B 6 其中 sum 函数返回的是矩阵中所有元素的和 AT表示矩阵 A 的转置 最后 根据公式 6 便可得到对于中英文 209 张图像的相似度矩阵 为 111209 2091209 209 rr R rr 其中 rij表示第 i 张图像与第 j 张图像的相似度 3 相似度筛选 根据相似度矩阵 按如下过程筛选出处于同一行的图像 Step1 从第一张图像开始 找出与该图像相似度最高的 18 张图像 对这 19 张图像利用 模型一求解 Step2 如果 19 张图像不能拼接出正确图像 则人工干预加入剩余图像中相似度较高的 图像 转入 Step1 如果可拼接 则转入 Step3 Step3 在相似度矩阵中删除已拼接的图像的相似度信息 查找下一张图像的分类情况 如果矩阵为空则拼接完成 得到每行的图像后 还需要对图像进行上下拼接 我们引入了行间距控制 2 行间距控制 考虑到行间距是一个相对固定的值 在像素点矩阵中约为 27 行 因此我们将拼接 后的行间距 ver 作为行与行之间拼接的指标 当 ver 规定阈值 本文设定为 2 行 内时 接受这两张图像可拼接 接受度 D 表示为 125 29 0 ver D else 7 5 3 2 模型求解 对于上述建立的模型二 首先 利用 Matlab 软件求出相似度矩阵 然后 对相似度 筛选过程进行求解 以英文序号为 000 图像为例 演示筛选的过程 如下 找出与 000 相似度较高 25 张图像 具体信息如下表 表 5 英文 000 图像筛选结果 图像序号 与图像 000 的相似度 000 1 131 0 991495 072 0 988669 048 0 985181 193 0 984996 115 0 984819 052 0 984745 9 081 0 984712 089 0 984368 077 0 984292 124 0 984031 087 0 983488 012 0 983348 177 0 98309 140 0 981274 102 0 98122 200 0 979275 125 0 979042 128 0 974672 031 0 949296 085 0 94718 187 0 946041 001 0 944866 063 0 931933 203 0 931101 找出其中最高的 18 张图像 利用模型一求解 发现这 19 张图像属于同一行 同理 分别求得汉字与英文 11 条碎纸片拼接后的序号排列见附录 1 表 10 表 11 最后 根据行间距阈值的控制 分别得到汉字与英文已拼接完成 11 条碎纸片拼接 顺序 具体排序见下表 表 6 问题二人工干预后汉字复原结果 049 054 065 143 186 002 057 192 178 118 190 095 011 022 129 028 091 188 141 061 019 078 067 069 099 162 096 131 079 063 116 163 072 006 177 020 052 036 168 100 076 062 142 030 041 023 147 191 050 179 120 086 195 026 001 087 018 038 148 046 161 024 035 081 189 122 103 130 193 088 167 025 008 009 105 074 071 156 083 132 200 017 080 033 202 198 015 133 170 205 085 152 165 027 060 014 128 003 159 082 199 135 012 073 160 203 169 134 039 031 051 107 115 176 094 034 084 183 090 047 121 042 124 144 077 112 149 097 136 164 127 058 043 125 013 182 109 197 016 184 110 187 066 106 150 021 173 157 181 204 139 145 029 064 111 201 005 092 180 048 037 075 055 044 206 010 104 098 172 171 059 007 208 138 158 126 068 175 045 174 000 137 053 056 093 153 070 166 032 196 089 146 102 154 114 040 151 207 155 140 185 108 117 004 101 113 194 119 123 10 表 7 问题二人工干预后英文复原结果 208 021 007 049 061 119 033 142 168 062 169 054 192 133 118 189 162 197 112 081 077 128 200 131 052 125 140 193 087 089 048 072 012 177 124 000 102 115 159 139 001 129 063 138 153 053 038 123 120 175 085 050 160 187 097 203 031 020 041 108 116 136 073 036 207 135 015 076 043 199 045 173 079 161 179 143 201 148 170 196 198 094 113 164 078 103 091 080 101 026 100 006 017 028 146 086 051 107 029 040 158 186 098 024 117 150 005 059 058 092 030 037 046 127 171 042 066 205 010 157 074 145 083 134 055 018 056 035 016 009 183 152 044 019 194 093 141 088 121 126 105 155 114 176 182 151 022 057 202 071 165 082 132 181 095 069 167 163 166 188 111 144 206 003 130 034 013 110 025 027 178 070 084 060 014 068 174 137 195 008 047 172 156 096 023 099 122 090 185 109 191 075 011 154 190 184 002 104 180 064 106 004 149 032 204 065 039 067 147 正确复原图见附录 1 图 9 图 10 5 3 3 结果分析 与问题一中的模型一比较 人工干预的过程增加了 即在筛选过程中可能要加入人 工干预 但在算法实际运行中 汉字几乎不需要人工干预 英文则只需 7 8 次人工干预 在一定程度上 也较快速地解决了该问题 减轻了手工拼接工作者的工作量 5 4 问题三 5 4 1 双面横纵切图像拼接中边缘特征匹配模型 模型三 1 模型二适用性分析 模型二在单面横纵切图像拼接的问题中有较好的适用性 相似度筛选能较好的筛选 出属于同一类的图像 其筛选的依据主要为图像间文字高度的相似度 而且之前对于汉 字 英文的结构分析出的匹配值公式 可通过模拟退火算法自动排除图像之间为反面的 情况 因此 正反面图像的拼接得到了处理 2 双面横纵切图像拼接中边缘特征匹配模型 对于双面横纵切的图像来说 由于正反两面图像中每行文字的高度特征是一致的 单面即可表达双面的高度特征 因此 模型二中的筛选原则同样适用于双面情况下的同 一类图像的筛选 由上述分析 单面即可表达双面的高度特征 所以在进行相似度筛选前 每个图像 正反面中只选取一面进行筛选 本文中选取的序号为 a 的图像进行筛选 5 4 2 模型求解 对于上述建立的模型三 首先 利用 Matlab 软件求解相似度矩阵 根据相似度矩阵 选出属于同一类的图像 以序号为 000a 为例 演示筛选的过程 如下 11 找出与 000a 相似度较高 25 张图像 具体信息如下表 表 8 双面 000a 图像筛选结果 图像序号 与图像 000a 的相似度 030a 0 986265 032a 0 98473 176a 0 984506 027a 0 983344 105a 0 982977 121a 0 981978 077a 0 981421 138a 0 981284 004a 0 979972 153a 0 979284 098a 0 978257 185a 0 97797 141a 0 976846 038a 0 975762 007a 0 973389 074a 0 970246 069a 0 96781 148a 0 966987 045a 0 962483 003a 0 961407 085a 0 959455 126a 0 923813 204a 0 923093 135a 0 922607 200a 0 918412 找出其中最高的 18 张图像 利用模型一求解 发现不属于同一类图像 需要进行 人工干预 作出筛选个数与相似度的曲线 如下图 图 3 筛选个数与相似度的曲线 在第一个相似度下降较快的点 即筛选个数为 21 时 我们人工干预添加新增的两 个图像 利用模型一求解 发现依旧不属于同一个类 进行第二次人工干预 在第二个 相似度下降较快的点 即筛选个数为 38 时 我们人工干预添加新增的 17 张图像 利用 0 8 0 82 0 84 0 86 0 88 0 9 0 92 0 94 0 96 0 98 1 1357911 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 12 模型一求解 发现其中 19 个属于同一行 取出这 19 个中的 000a 和为未分类 19 个中的 187a 如下图 图 4 碎纸片图像 发现它们的高度特征很相似 我们猜想筛选出的 38 张图为高度特征相似的两行 所以 对剩余的 19 张图像利用模型一验证 发现他们确实属于同一行 同理得到了剩余 9 行的拼接结果 然后 根据行间距阈值的控制 得到已拼接完成 11 条碎纸片拼接顺序 正 反面的 排序见下表 表 9 问题三正面复原结果 078b 111b 125a 140a 155a 150a 183b 174b 110a 066a 108a 018b 029a 189b 081b 164b 020a 047a 136b 089a 010b 036a 076b 178a 044a 025b 192a 124b 022a 120b 144a 079a 014a 059a 060b 147a 152a 005a 186b 153a 084b 042b 030a 038a 121a 098a 094b 061b 137b 045a 138a 056b 131b 187b 086b 200b 143b 199b 011b 161a 169b 194b 173b 206b 156a 034a 181b 198b 087a 132b 093a 072b 175a 097a 039b 083a 088b 107a 149b 180a 037b 191a 065b 115b 166b 001b 151b 170b 041a 070b 139b 002a 162b 203b 090a 114a 184b 179b 116b 207a 058a 158a 197a 154b 028b 012a 017b 102b 064b 208a 142a 057a 024a 013a 146a 171b 031a 201a 050a 190b 092b 019b 016b 177b 053b 202a 021b 130a 163a 193b 073b 159a 035a 165b 195a 128a 157a 168a 046a 067a 063b 075b 167a 117b 008b 068b 188a 127a 040a 182b 122a 172a 003b 007b 085b 148b 077a 004a 069a 032a 074b 126b 176a 185a 000b 080b 027a 135b 141a 204b 105a 023b 133a 048a 051b 095a 160b 119a 033b 071b 052a 062a 129b 118b 101a 015b 205a 082b 145a 009b 099a 043a 096b 109a 123a 006a 104a 134a 113a 026b 049b 091a 106b 100b 055b 103a 112a 196b 054b 13 表 10 问题三反面复原结果 136a 047b 020b 164a 081a 189a 029b 018a 108b 066b 110b 174a 183a 150b 155b 140b 125b 111a 078a 005b 152b 147b 060a 059b 014b 079b 144b 120a 022b 124a 192b 025a 044b 178b 076a 036b 010a 089b 143a 200a 086a 187a 131a 056a 138b 045b 137a 061a 094a 098b 121b 038b 030b 042a 084a 153b 186a 083b 039a 097b 175b 072a 093b 132a 087b 198a 181a 034b 156b 206a 173a 194a 169a 161b 011a 199a 090b 203a 162a 002b 139a 070a 041b 170a 151a 001a 166a 115a 065a 191b 037a 180b 149a 107b 088a 013b 024b 057b 142b 208b 064a 102a 017a 012b 028a 154a 197b 158b 058b 207b 116a 179a 184a 114b 035b 159b 073a 193a 163b 130b 021a 202b 053a 177a 016a 019a 092a 190a 050b 201b 031b 171a 146b 172b 122b 182a 040b 127b 188b 068a 008a 117a 167b 075a 063a 067b 046b 168b 157b 128b 195b 165a 105b 204a 141b 135a 027b 080a 000a 185b 176b 126a 074a 032b 069b 004b 077b 148a 085a 007a 003a 009a 145b 082a 205b 015a 101b 118a 129a 062b 052b 071a 033a 119b 160a 095b 051a 048b 133b 023a 054a 196a 112b 103b 055a 100a 106a 091b 049a 026a 113b 134b 104b 006b 123b 109b 096a 043b 099b 正确复原图见附录 1 图 11 图 12 5 4 3 结果分析 与问题二中的模型二比较 相似度筛选过程中人工干预次数增加了 这只要是由于 问题三中高度特征相似的行较多 6 模型推广与评价 本文针对碎纸片图像复原问题建立了三个模型 分别解决了仅纵切碎纸片拼接复原 横纵切碎纸片拼接复原和双面横纵切碎纸片拼接复原三个问题 在一定人工干预下 得 到满意的结果 对各模型具体分析如下 模型一 主要是解决了仅纵切碎纸片拼接复原的问题 在解决过程中 首先 提出 了边缘特征点和匹配值等概念 然后 分别对汉字和英文两种文字类型进行了讨论 给 出不同的边缘特征点提取方案 和匹配值计算方法 最后利用模拟退火算法求解了最优 拼接方案 由以上分析可知 此模型最大的优点为对于不同文字类型进行分类考虑 且模拟退 火算法能够较快得到最优解 精度也较高 主要缺点是仅考虑了纵切时的拼接情况 不 能较好的适应问题二 三中横纵切和双面的拼接问题 模型二 三 主要是解决加入横切情况后碎纸片拼接复原的问题 在解决过程中 提出了筛选和行间距等概念 分别解决了行元素选择和行拼接的问题 模型的主要优点是 精确筛选规则得到了很好的结果 使得模拟退火算法得到最优 解的精确度 行间距在解决行拼接问题中达到了快速准确的效果 主要缺点是 虽然能 较好的适应题目中给出的碎纸片拼接复原的问题 在解决手写碎纸片拼接中 由于手写 文字的每一行不一定在同一水平线上 行间距不固定 受到了较大的限制 本文中建立的模型一 二和三均为解决碎纸片拼接复原的模型 能够广泛地应用于 很多领域中 比如在医学领域中 通过图像拼接技术提高图像的精确度 在遥感领域中 14 通过利用图像拼接技术可以对一组有重叠区域遥感图像进行拼接 得到完整的遥感图像 方便进一步遥感图像分析 4 7 文献参考 1 百度文库 2 汉字特点与结构 年 9 月 15 日 2 百度文库 汉字笔画大全 年 9 月 15 日 3 卓金武 MATLAB 在数学建模中的应用 北京 北京航空航天大学出版社 2011 4 李新 葛晓燕 基于 SIFT 的低空遥感图像拼接 制造业自动化 35 3 2013 8 附录 附录 1 15 图 5 人工干预前汉字复原结果 16 图 6 人工干预后汉字复原结果 17 图 7 人工干预前英文复原结果 18 图 8 人工干预后英文复原结果 19 表 11 问题二人工干预前汉字复原结果 007 208 138 158 126 068 175 045 174 000 137