基于文档结构特征的碎纸片拼接复原毕业论文模板(编辑修改稿)

基于文档结构特征的碎纸片拼接复原毕业论文模板(编辑修改稿)内容摘要：

行预处理，将图片上的信息处理成便于计算机识别的值，并依次对碎片进行相应的自动或半自动拼接复原．现有方法大多为针对手撕碎片的拼接复原，通过计算机识别其边缘轮廓进行拼接，但当碎片数量庞大且碎片边缘轮廓相似 或由碎纸机绞碎后的纸片时， 轮廓识别方法则变得不再可行． 本文结合笔画的连续性、光滑性等文字特点及 字高、字宽 、行间距等 文 档 结构特征 设计关于规则碎纸 片的高效率复原方法． 2 问题分析 二 值处 理匹 配 度 计算结 构 控 制校 正 匹 配 度拼 接准 确 性 检验纸 片复 原 图 1 碎片的拼接复原 碎片的拼接复原过程可由上述流程图表示：首先，对所给碎片进行二值化处理，将文字图像转化为便于计算机识别的 01 值； 接着 ， 根据文字特征 进行边缘像素点的匹配度计算；再由文字行间距、字间距、字高和字宽相似等 文档 特征 校正匹配度；然后，以碎片间的最大匹配度为目标建立优化模型；之后，设计 贪心算法 以 每次寻求最优解的思想，选择与碎片边缘匹配度最高的另一碎片进行拼接，在拼接过程中可对结果的准确性进行检验 (可配合人工 检验 )，若检验不通过，则找出错误拼接碎片重新拼接，最后，所有碎片拼接完成，得到文件的复原图． 边缘像素点匹配 （ 小四号黑体不加粗 ） （二级标题小四号黑体不加粗，段前断后不空行．） 由文字内部特征和书写习惯可知，文字文件为横向书写，每一文字的所有笔画均连续且外边缘像素点围成封闭图形．因此，通过构造匹配度函数，计算任意两碎片边缘的文字匹配度，便可清楚地反映出这两条碎片是否能够正确拼接． 匹配度的计算方法并不唯一，由笔画的连续性：若被切割的两张碎片边缘同一水平内江师范学院本科毕业论文 3 线上 的像素点灰度值相同，则两像素点可能相匹配，即可能同属于 文字的一个笔画，这样便可通过统计匹配像素点个数来刻画匹配度；由笔画的光滑性：同一笔画的外边缘像素点构成一个封闭的光滑曲线，因此可以连接碎片边缘任意两像素点，统计其中能构成圈，且内部有像素点填充的个数，以此来刻画碎片边缘的匹配度；综合笔画的连续性和光滑性： 若两碎片边缘 像素点斜率相同，则表示像素点走向一致，同属于一个笔画． 以下内容省略 „„ ． 3 数据预处理 （ 1） 读取灰度值 由于题目所给原始图片不便于计算机识别，在计算匹配度之前需要对图片进行预处理．本文在 ， 内存， 20xx 版本的硬件环境和 的软件环境下利用 Imread 命令将附件中的所有图片读取为灰度矩阵，矩阵中的值为 0~255 的数． （ 2） 二值化处理 对灰度矩阵进行二值化处理：即在灰度矩阵中将值大于 220 的像素点赋值为 1，小于 220 的像素点赋值为 0，则经二值化处理后的图片空白处像素点灰度值为 0，文字处像素点灰度值为 1. 4 基于像素点 覆盖 的匹配度计算方法 横一匹配 (1) 基本原理 根据文字笔画的连续性，对经过二值化处理后的任意两张碎片，可比较一张碎片左边缘（上边缘）与另一张碎片右边缘（下边缘）像素点的灰度值．若同一水平线上（同一垂直线上）的 灰度值相等，则认为像素点可能相匹配 [3]，即碎片边缘的像素点可能为同一笔画内的像素点，匹配过程见图 2． p = 0p = 0p = 0p = 1p = 0p = 1p = 1p = 1 图 2 横一匹配过程示意图 图 2 中， P 表示同一水平线上的像素点灰度值是否相匹配，其值为 1 代表像素点能内江师范学院本科毕业论文 4 匹配，值为 0 代表不能匹配． (2) 匹配度计算模型 由横一匹配原理，引入匹配度 P 来刻画碎片边缘之间的匹配程度，将待匹配的两张碎片边缘灰度值作差，相匹配的像素点坐标灰度差值为 0，不匹配的像素点坐标灰度差值绝对值为 1，则任意两张碎片的边缘匹配度 ijP 为： 1 (1 ( ) ( ) )mij i jkP E k E k   (1) (1)式中 ijP 为任意第 i 张碎片和第 j 张碎片的边缘匹配度， ()iEk为第 i 张碎片边缘的第 k 个像素点坐标灰度值． 针对左右拼接的情况，匹配度可进一步表示为： 1 (1 ( ) ( ) )mij ir jlkP E k E k   1 (1 ( ) ( ) )mji il jrkP E k E k   其中 ijP 表示第 i 张碎片的右边缘和第 j 张碎片的左边缘拼接的匹配度， ()irEk表示第i 张碎片右边缘第 k 个像素点坐标灰度值， ()jlEk表示第 j 张碎片左边缘第 k 个像素点坐标灰度值．类似地， jiP 表示第 j 张碎片右边缘和第 i 张碎片左边缘拼接的匹配度， ()ilEk表示第 i 张碎片左边缘第 k 个像素点坐标灰度值， ()jrEk表示第 j 张碎片右边缘第 k 个像素点坐标灰度值． 同理，上下边缘拼接的匹配度可表示为： 1 (1 ( ) ( ) )mij id jukQ E k E k   1 (1 ( ) ( ) )mji iu jdkQ E k E k   其中， ijQ 为碎片 i 下边缘与碎片 j 上边缘的匹配度， jiQ 为碎片 j 下边缘与碎片 i 上边缘的匹配度， u 代表上边缘， d 代表下边缘． 以下内容省略 „„ 方向场匹配 (1) 基本原理 由文字笔画的连续性可知笔画的外边缘轮廓线也是光滑的，为描述笔画外边缘轮廓线的光滑性，引入斜率的概念，若边缘上相匹配的像素点有相同的斜率（如图 3 中 b 若12kk ，表示有相同的斜率 ），则认为该组像素点属于同一笔画． 内江师范学院本科毕业论文 5 DCBA 图 3 方向场匹配过程示意图 在判断斜率是否相同之前首先应判断像素点是否匹配，如图 3 中像素点 A 分别与对应碎片的像素点 B C D、 、 的灰度值进行比较，只有在灰度值相同的情况下，才进一步计算两对应像素点的斜率，如在图 3 中仅判断 A 点斜率与 ,BC点的斜率是否相同． 以下内容省略 „„ 5 碎纸片拼接复原模型的建立 纵切碎片的单一横向拼接 建模思路 匹配度形象的反映了碎片拼接时的契合程度，因此可利用匹配度的高低表示碎片拼接复原的效果．哈密顿通路是经过图中所有顶点一次且仅一次的通路，而碎片的拼接复原过程就是根据起始碎片与其余各碎片的匹配度将其依次排列的过程，则以碎片为点，碎片之间的匹配度为边的权值，纵切碎片的拼接复原问题可转化为寻找该有向完全图的哈密顿通路问题． 始末碎片 根据书写或打印规律，纵切碎片的左右边缘有空白列，即灰度值全为 0．则可将左边缘灰度值全为 0 的碎片作为候选的起始碎片，右边缘灰度值全为 0 的碎片作为候选的末尾碎片，当根据灰度值全为 1 的原则选择始末碎片时，可分为两种情况： (1) 若边缘灰度值全为 0 的碎片恰为两片，则分别以这两片为始末碎片； (2) 若边缘灰度值全为 0 的碎片超过两片，则将始末碎片两两组合，并选出所有组合进行拼接复原，得到多个复原结果； 特别地，若纵切碎片的边缘无空白列，即无灰度值全为 0 的边缘，则选择左边缘与其他碎片边缘匹配度总和最低的碎片为起始碎片，选择右边缘与 其他碎片边缘匹配度总和最低的碎片为末尾碎片．若匹配度最低的碎片有两片以上，仍采取两两组合的方式． 模型建立 假设文件仅为完全纵向切割，以碎片为点，碎片之间的匹配度为边的权值建立有向a b 内江师范学院本科毕业论文 6 完全图 ( , )G V E ，如图 7 所示： DECBA 图 8 以碎片为顶点的有向完全图 其中 {1,2,...,。