您现在的位置:首页 > >

基于多约束条件的中文碎片拼接复原算法设计

发布时间:

基于多约束条件的中文碎片拼接复原算法设计 摘 要:文章对纵横切中文碎纸片的拼接复原问题进行了分析,对碎片图像 进行数字化处理,采用灰度相似性比较的方法,利用循环遍历的思想匹配碎片; 接着对图像进行二值化降噪处理,去除干扰元素,考虑到传统匹配算法下存在多 种匹配、错误匹配、重复匹配的问题,设计基于多种约束条件的中文碎片拼接算 法; 最后利用编程实现得到完整的复原图形,该算法提高了碎片拼接复原效率和 精准度。 关键词:碎片复原;相似性比较;多约束;匹配模型 传统破碎文件的拼接复原工作需由人工完成,效率很低。随着计算机技 术的发展,人们试图开发碎纸片的自动拼接技术,以提高拼接复原效率。本文对 2013 高教社杯全国大学生数学建模竞赛 B 题中提出的碎纸片拼接复原问题进行 研究,主要研究纵横切中文碎纸片的拼接复原问题。 1 灰度值的相似性比较 1.1 提取边缘灰度值 ①在得到所有图像的灰度值矩阵后,提取每组矩阵左边缘的灰度值,根据左 边缘的灰度值的特点,判断该图像是否为第一张图片,若左边缘灰度值均为 255 (全白) ,则表示该列无文字信息,即可确定复原的第一张图片。 ②提取第一张图像灰度值矩阵的右边缘灰度值, 并与其他图像的左边缘灰度 值作相似性比较,确定与之匹配的图像。 1.2 欧氏距离比较矩阵边缘灰度值相似性 欧氏距离(Euclid Distance)也称欧几里得距离,是一个通常采用的距离定 义, 它是在维空间中两个点之间的真实距离。在二维空间中的欧氏距离则为两点 之间的直线段距离,其表达如下: d=■ 在确定灰度值相似性时, 根据欧氏距离最短的准则, 对于一张分辨率为 m× n 的数字图像,用欧氏距离法确定出的的表达式为: d=■ 其中 i=1,2……19,且 i≠k,k 表示要匹配的图片序号。 1.3 循环遍历搜索 根据欧氏距离最小原则的相似性比较,匹配出与第一张图片相匹配的图像, 然后将该图像作为待匹配的图像,寻找下一张与之匹配的图像,利用循环遍历搜 索的方法,得到匹配顺序。最后按照匹配顺序,绘制复原图像。 2 算法设计与模型求解 2.1 图像二值化降噪处理 由于每张图片都存在着噪点这些干扰因素, 所以接下来运用二值化的方法对 图片进行降噪处理, 为了改善图像上的显示效果,需要人为的选取适当的阈值以 便得到更合理的二值化图像。 具体算法步骤如下 ①计算机编程读取 BMP 图片灰度值; ②选取适当的阈值; ③判断该像素点是否为噪点。 若是, 则视为背景色像素, 否则视为文本内容; ④根据背景色与文本内容确定出文本内容边界; ⑤重复步骤 3,直到识别出清晰图像; ⑥重置灰度; ⑦存储 BMP 灰度数据。 在得到每一行首张图像的基础上,采用问题一的算法,比较灰度值矩阵的相 似性,找出水*方向上与第一张图像相匹配的碎片,然后利用循环遍历搜索法, 找出与上一张匹配的碎片。 理论上能够搜索出每一行的所有匹配图像, 但程序运行中会出现多种情况而 导致程序停止运行,不能匹配出一行的图像。出现有以下情况:匹配过程中出现 多张碎片能够与上一张匹配、图像的错误匹配、图像的重复匹配。 2.2 图像黑白间隔化——条件 1 为了减少 “出现多张碎片能够与上一张匹配 ”和“图像的错误匹配 ”情况发生 的概率,采用将碎片图像黑白间隔化的方法,使图像的匹配精度更高。 具体实现方法如下: ①对各个图像矩阵进行二值化处理,使矩阵中的值只包含 0 和 1; ②对于有 72× 180 个像素点的图像,从矩阵上边缘开始搜索,判断是否出现 文字信息(即该行中出现 0) ; ③若出现文字信息,则将该行的值全部赋予 0,即全黑化; ④重复的步骤,是含有文字信息的行均变成全黑; ⑤搜索出 180 个像素点后,图像即呈现出黑白间隔化。 例如, 将附件 3 中序号 049 和 054 碎片拼接后作黑白间隔化处理过程如下图 1 所示。 特别地, 对于某些碎片图像有较大一部分空白的情况,根据我国文字分段常 识,可以判断出这些空白区域是可以有文字的,但可能由于分段原因,使得这一 部分看起来没有文字。若空白区域有文字信息,则碎片的匹配准确率更高。对于 这种情况,处理方法如下: 根据该碎片中已有文字的行间距计算空白区域中可有文字的位置, 行间距值 d 为上一行文字的下边缘与下一行文字的上边缘的高度差,即为 d=ai-aj 则空白区域中文字可占用的位置为 s=az+d 其中,ai、aj、az 分别为文字图像的矩阵各个位置的行向量。 利用 matlab 编程得到该情况黑白间隔化图像如下图 2 所示: 2.3 重复匹配的限制——条件 2 为了消除“图像重复匹配”的现象,采用数据结构中设置哨兵的方法,使图像 的匹配准确度更高。 ①在图像匹配过程中,为了避免重复匹配,需要加入一些限制,使结果更优 化。在匹配过程中,系统每次从 209 个图像中查找与上一张图片相匹配的图像, 每次搜索过程中,将要匹配的图片序号存入数组中,可看做压入堆栈。 r(j)=n 其中 j 为下标,n 为图片序号。 ②另外设置一个哨兵存放每个图片匹配其它图片的可能值,该值越小,匹配 率越高。当一张图片匹配完成时,该图片便不再与其它图片匹配,此时便可以设 置哨兵。b(r)=inf 其中 r、b 均为为数组。 ③在以后的搜索最优匹配图片过程中,读取哨兵信息,根据最优匹配方法, 所有已经匹配过的图片便不会再和其它图片匹配,从而达到避免重复匹配的目 的。 2.4 基于文字特征的汉字匹配——条件 3 当用 matlab 编程时,在算法已经满足上述三个条件下,仍然有部分碎片不 能正确拼接,例如下列情况(如图 3 所示) 。 很显然, 右边的图像拼接结果才是正确的拼接结果,但是根据前三个条件得 到的左边的结果也是合理的, 说明在算法满足前三个条件时无法确定出唯一的碎 片拼接图像。进一步分析其文字的特征,找出解决的办法如下图 4 所示。 ①按条件 1 所给步骤将两个图像中可能会拼接的文字黑白间隔化; ②设左边碎片


热文推荐
猜你喜欢
友情链接: 医学资料大全 农林牧渔 幼儿教育心得 小学教育 中学 高中 职业教育 成人教育 大学资料 求职职场 职场文档 总结汇报