基于条状碎纸片自动拼接

Size: px

Start display at page:

Download "基于条状碎纸片自动拼接"

谛昌
5 years ago
Views:

1 Modeling and Simulation 建模与仿真, 2013, 2, Published Online November 2013 ( Auto Stitching of Crapped Paper Based on Strips Dan Hang, Daqing Liao, Tingting Jiang, Ya Wang Air Force Logistics College, Xuzhou Received: Oct. 8 th, 2013; revised: Oct. 23 rd, 2013; accepted: Oct. 27 th, 2013 Copyright 2013 Dan Hang et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: By using the method of similarity matching, strip scraps of paper in messy order are jointed. According to the information on the left and the right column of each strip of paper images, we can calculate vector cosine. When vector value is closer to 1, the matching degree of the left and right columns on other images is higher. Then according to the maximum correlation principle, each strip of paper is spliced together, and the original text information of the image is restored. Through the MALAB programming algorithm, the effectiveness of the algorithm is verified through preliminary examples. Keywords: Stitching of Scrapped Paper; Correlation Analysis; Vector Angle Cosine 基于条状碎纸片自动拼接杭丹, 廖大庆, 蒋婷婷, 王娅空军勤务学院, 徐州 hazel-hang@sohu.com 收稿日期 :2013 年 10 月 8 日 ; 修回日期 :2013 年 10 月 23 日 ; 录用日期 :2013 年 10 月 27 日摘要 : 采用相似度匹配的方法, 对凌乱次序的条状碎纸片进行拼接根据每张条状碎纸图像的左右边列处的信息, 计算它与其他条状碎纸图像的左右边列的相关性即向量余弦值, 向量值越接近 1, 与其他图像左右列越匹配, 然后根据最大相关性的原则, 将各个条状碎纸拼接在一起, 得到的图像就是要恢复的原始文本信息通过 MALAB 编程实现算法, 并通过初步实例验证了算法的有效性关键词 : 碎纸片拼接 ; 相关性 ; 向量余弦值 1. 引言碎纸拼接, 是通过扫描和图像提取技术获取一组碎纸片的形状颜色等信息, 然后利用计算机通过特征匹配技术来识别相邻接的图像碎片, 进而重现整个物体的原貌碎片拼接技术的研究很有实用价值如, 考古研究中对破碎珍贵文物的修复, 司法物证复原历史文献修复以及军事情报获取等领域碎片拼接的方法根据特征可以分为基于色彩纹理材质轮廓等图像碎片拼接 ; 根据形状特征又可以分为规则图像碎片和不规则图像碎片的拼接 ; 根据空间特征还可分为二维图像碎片拼接和三维图像碎片拼接碎片拼接的主要工作流程可概括为以下三个步骤 : 1) 对图像碎片进行预处理, 即对物体碎片数字化, 得到碎片的数字图像 2) 图像碎片匹配, 通过匹配算法找到相互匹配的图像碎片 38 Open Access

2 3) 图像碎片的拼接合并, 将相互匹配碎片拼接在一起得到最终的复原图其中, 最重要的就是第二步图像碎片匹配图像碎片匹配是图像碎片拼接的核心问题近些年国内很多学者对这一问题进行了大量研究, 提出了许多新的算法 [1-7], 使得这一领域研究有了长足的进步本文采用相似度匹配的方法, 对凌乱次序的条状碎纸片进行拼接, 根据每张条状碎纸图像的左右边列处的信息, 计算它与其他条状碎纸图像的左右边列的相关性即向量余弦值, 向量值越接近 1, 与其他图像左右列越匹配, 根据最大相关性的原则, 将各个条状碎纸拼接在一起, 得到的图像就是要恢复的原始文本信息最后通过 MALAB 编程实现算法, 并利用附件 1, 附件 2 提供碎片验证了算法的有效性, 实现碎片拼接为初始图像 2. 基本假设 1) 在纸张切割处有油墨覆盖的部位没有受损断裂, 附着在纸上的油墨没有被扯开, 在断裂处也没有出现丢失油墨的情况 2) 在图像预处理阶段对图像进行过几何畸变校正和噪声点的抑制处理, 让条状碎片不存在明显的几何畸变以及毛刺边缘等问题, 确保结果的可信度 3. 变量说明 Bian_R 每张纸带图中右列信息 Bian_L 每张纸带图中右列信息 m 碎片个数 i 第 i 个碎片 ;j 除 i 之外所有碎片 B 结构元素 4. 模型的建立和求解 4.1. 图像拼接算法图像拼接的质量, 主要依赖图像的配准程度, 因此图像的配准是拼接算法的核心和关键根据图像匹配方法的不同仁阔, 一般可以将图像拼接算法分为以下两个类型 : 1) 基于区域相关的拼接算法这是最为传统和最普遍的算法基于区域的配准方法是从待拼接图像的灰度值出发, 对待配准图像中一块区域与参考图像中的相同尺寸的区域使用最小二乘法或者其它数学方法计算其灰度值的差异, 对此差异比较后来判断待拼接图像重叠区域的相似程度, 由此得到待拼接图像重叠区域的范围和位置, 从而实现图像拼接也可以通过 FFT 变换将图像由时域变换到频域, 然后再进行配准对位移量比较大的图像, 可以先校正图像的旋转, 然后建立两幅图像之间的映射关系当以两块区域像素点灰度值的差别作为判别标准时, 最简单的一种方法是直接把各点灰度的差值累计起来这种办法效果不是很好, 常常由于亮度对比度的变化及其它原因导致拼接失败另一种方法是计算两块区域的对应像素点灰度值的相关系数, 相关系数越大, 则两块图像的匹配程度越高该方法的拼接效果要好一些, 成功率有所提高 2) 基于特征相关的拼接算法基于特征的配准方法不是直接利用图像的像素值, 而是通过像素导出图像的特征, 然后以图像特征为标准, 对图像重叠部分的对应特征区域进行搜索匹配, 该类拼接算法有比较高的健壮性和鲁棒性基于特征的配准方法有两个过程 : 特征抽取和特征配准首先从两幅图像中提取灰度变化明显的点线区域等特征形成特征集冈然后在两幅图像对应的特征集中利用特征匹配算法尽可能地将存在对应关系的特征对选择出来一系列的图像分割技术都被用到特征的抽取和边界检测上如 canny 算子拉普拉斯高斯算子区域生长抽取出来的空间特征有闭合的边界开边界交叉线以及其他特征特征匹配的算法有 : 交叉相关距离变换动态编程结构匹配链码相关等算法 4.2. 算法本文采用相似度匹配的方法, 考虑碎片的边缘匹配情况, 根据每张条状碎纸图像的左右边列处的信息, 计算它与其他条状碎纸图像的左右边列的相关性, 根据最大相关性的原则, 将各个条状碎纸拼接在一起, 得到的图像就是要恢复的原始文本信息对于碎纸片左右的相关性, 我们用向量余弦值衡量向量值越接近 1, 与其他图像左右列越匹配向量余弦值多维空间中有方向的线段如果两个向量的方向 Open Access 39

3 一致, 即夹角接近零, 那么这两个向量就相近而要确定两个向量方向是否一致, 这就要用到余弦定理计算向量的夹角了余弦定理对我们每个人都不陌生, 它描述了三角形中任何一个夹角和三个边的关系, 换句话说, 给定三角形的三条边, 我们可以用余弦定理求出三角形各个角的角度假定三角形的三条边为 a,b 和 c, 对应的三个角为 A,B 和 C, 那么角 A 的余弦 b c a cos A 2bc 如果我们将三角形的两边 b 和 c 看成是两个向量, 那么上述公式等价于 bc, cos A bc 其中分母表示两个向量 b 和 c 的长度, 分子表示两个向量的内积举个具体的例子, 假如提取碎纸片左边 Bian_L 和右边 Bian_R 对应向量分别是 x1,x2,,x64000 和 y1,y2,,y64000, 那么它们夹角的余弦等于, cos xy xy x y x x x y y y 当两条边向量夹角的余弦等于一时, 这两条边文字情况信息完全重复 ; 当夹角的余弦接近于一时, 两条边文字信息相似, 从而可以归成一类 ; 夹角的余弦越小, 两条边文字信息越不相关, 如图 1 和算法下面给出本文算法的步骤 : 1. 首先通过 MATLAB 软件确定图像位置, 再调用 MATLAB 软件里的 imread 函数读取图像数据 ( 即颜色值 ) 2. 用 MATLAB 软件里的 im2double 函数把图像的数据类型转换成双精度浮点类型 3. 提取图像左边缘数据 4. 提取图像右边缘数据 5. 计算不同图像左右边相似度向量余弦值 6. 计算余弦值接近 1 的程度 7. 找相邻图像边最相似 8. 对图片进行排序 9. 拼接图像匹配碎片 4.3. 碎片复原实例 (MATLAB 编程实现 ) 算法流程图 ( 图 3) [8] : 为了初步验证算法的有效性, 下面给出两个实例 : 例 1: 附件 1 给出的碎片有 18 个, 如 :( 仅列举几个个碎片, 具体见附件 1) ( 图 4) 通过 MATLAB 程序复原碎片得到的 18 个条形碎片的排列顺序 (MATLAB 编程实现 ): 表 1 下图 5 即为附件 1 原文件的复原图图 1 这是一份中文文件例 2: 附件 2 给出的碎片有 18 个, 如图 6:( 仅列举几个碎片, 具体见附件 2) 通过 MATLAB 程序复原碎片得到的 18 个条形碎片的排列顺序 (MATLAB 编程实现 ): 见表 2 X Y Figure 1. Vector similarity 图 1. 两向量相似 X Y Figure 2. Vector independent 图 2. 两向量无关 Table 1. Fragment sequence of recovery 表 1. 复原碎片排列顺序 Table 2. Fragment sequence of recovery 表 2. 复原碎片排列顺序 Open Access

4 碎条调入其余碎片左边缘转换双精度类型转换双精度类型 ( 取边缘带存入数组 ) 计算余弦值左边缘转换双精度类型程序筛选出的初始碎条循环左边缘转换双精度类型拼接后的不完整文档完整图 Figure 3. Flow chart 图 3. 流程图 Figure 4. Fragment legend 图 4. 碎片图示图 7 即为附件 2 原文件的复原图图 2 这是一份英文文件 5. 模型评价传统上, 拼接复原工作需由人工完成, 准确率较高, 但效率很低特别是当碎片数量巨大, 人工拼接很难在短时间内完成任务由于碎纸片的拼接复原技术的重要性, 目前世界上对它已经有了研究, 能够查阅到的文档碎片拼接技术主要使用曲线的特征来进行碎片拼接, 计算量非常巨大本文首先介绍了一些关于碎纸拼接的方法, 然后在详细研究了 MATLAB 软件的应用的基础上, 设计了碎纸片自动拼接复原的算法, 最后通过题目中的实例对本文提出的算法和方法进行验证, 通过拼接出来的图像可以证明本文的算法和方法是切实可行的但是可以看到, 文章主要解决的是对规则长条形状的碎纸片能够进行很好的拼接, 而对于非规则的碎片形状差异大的碎片等等情况, 还不能够进行顺利的拼 Open Access 41

5 Figure 5. Restored view 图 5. 复原图 Figure 6. Fragment legend 图 6. 碎片图示 42 Open Access

Figure 7. Restored view 图 7. 复原图接, 因此有待深入研究参考文献 (References) [1] 陶波, 于志伟, 郑筱祥 (1997) 图样的自动拼接. 中国生物医学工程学报, 4, 29-35. [2] 韩煜 (2008) 基于颜色和纹理特征的计算机自动拼图研究. 硕士论文, 首都师范大学, 北京.

6 Figure 7. Restored view 图 7. 复原图接, 因此有待深入研究参考文献 (References) [1] 陶波, 于志伟, 郑筱祥 (1997) 图样的自动拼接. 中国生物医学工程学报, 4, [2] 韩煜 (2008) 基于颜色和纹理特征的计算机自动拼图研究. 硕士论文, 首都师范大学, 北京. [3] 钟家强, 王润生 (2001) 基于边缘的图像配准改进算法. 计算机工程与学科, 6, [4] 罗智中 (2011) 基于线段扫描的碎纸片边界检测算法研究. 仪器仪表学报, 24, 7-9. [5] 刘金根, 吴志鹏 (2002) 一种基于特征区域分割的图像拼接算法. 西安电子科技大学学报, 6, [6] 贾海燕, 朱良家, 周宗潭, 胡德文 (2006) 一种碎纸自动拼接中的形状匹配方法. 计算机仿真, 23, [7] 吕科 (2003) 空间物体碎片的自动复原算法研究. 计算机应用, 4, [8] 苏金明, 张莲花, 刘波 (2005) MATLAB 高级编程. 电子工业出版社, 北京. Open Access 43

国学思想与大学数学

国学思想与大学数学 Pure Mathematics 理论数学, 2013, 3, 201-206 http://dx.doi.org/10.12677/pm.2013.33030 Published Online May 2013 (http://www.hanspub.org/journal/pm.html) Chinese Traditional Culture and College Mathematics