Journal of Image and Signal Processing
Vol.06 No.03(2017), Article ID:21489,13 pages
10.12677/JISP.2017.63018

A Feature-Vector Based Multi-Resolution Image Matching Method

Chao Liu*, Feng Qian, Wensong Liu

The 28th Research Institute of China Electronics Technology Group Corporation, Nanjing Jiangsu

Received: Jul. 7th, 2017; accepted: Jul. 23rd, 2017; published: Jul. 26th, 2017

ABSTRACT

Aiming at the matching problem of images with different or unknown resolutions, a feature-vector based matching method for multi-resolution images was proposed. Firstly, by comparing the key-point feature-vectors of object image with reference image, a point which satisfies matching rules can be taken as the same key-point of the two images, and then they can be matched by the geometry relation of multiple key-points. By a matching test for images with different resolutions, it can be concluded that the proposed method shows better performance for images with key- points which differ from each other obviously.

Keywords:Resolution, Feature-Vector, Image Matching

基于特征矢量的不同分辨率图像匹配方法

刘超*,钱丰,刘文松

中国电子科技集团公司第二十八研究所,江苏 南京

收稿日期:2017年7月7日;录用日期:2017年7月23日;发布日期:2017年7月26日

摘 要

针对分辨率不同或者分辨率未知情况下进行图像匹配比较困难的问题,提出一种基于特征矢量的图像匹配方法。该方法对模板图像与待匹配图像的特征点的特征矢量组进行比对,将满足匹配规则的特征点判为两幅图像中相同位置的同一特征点,然后根据多个识别特征点之间的几何关系进行图像匹配。通过对不同分辨率图像的匹配实验,表明该方法在图像特征点差异性较大时具有比较好的匹配效果。

关键词 :分辨率,特征矢量,图像匹配

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

图像匹配是模式识别、图像分析等领域的重要基础性研究课题,其主要目标是通过一定的匹配算法实现两幅或多幅图像之间的同名点识别。根据提取图像特征的层次,图像匹配算法主要分为三大类 [1] :直接利用像素值的匹配算法;利用边缘、角点等低层次图像特点的匹配算法;利用标示符、特征点之间相关性等高层次特征的匹配算法。其中,基于像素值匹配的方法对图像间的变化很敏感;基于高层次特征匹配的方法虽然对这些扰动不敏感,但需要提取和识别特征,而这一直是图像匹配中的主要难点之一。

基于特征的图像匹配是目前应用最广泛的一类方法,其核心是寻找特征点或者特征点之间的相互关系。在图像中,角点是一类特殊的特征点,角点被定义为方向变化非常快的地方。围绕角点检测问题,Zuniga等提出了基于梯度方向速率变化的方法 [2] ;Smith等提出了一种称为SUSAN算子的简单、准确的角点检测方法 [3] ;Rosten等利用机器学习显著改善了SUSAN算子的角点检测性能 [4] 。在完成特征点或者特征点间相互关系的检测识别后,研究学者进一步针对如何利用这些检测识别结果来实现图像匹配开展了大量深入研究。Gregory等提出一种利用Hausdorff距离实现图像匹配的方法 [5] ,这种方法通过计算相似度而不是图像点的精确对应来实现匹配,所以具有更好的抗干扰性;Lowe提出一种基于SIFT(尺度不变特征转换)的匹配算法 [6] ,这种算法基于每个兴趣点的局部区域的图像梯度,具有较强的鲁棒性。

目前,大部分的匹配算法都是基于图像分辨率相同这一隐含前提,并未考虑分辨率不同或者分辨率未知的情况。为此,本文提出一种基于特征矢量的不同分辨率图像匹配方法。该方法首先从模板图像和待匹配图像中分别提取特征点,然后根据特征点的性质形成特征矢量,再根据各自特征矢量间的几何关系相似性实现最终的图像匹配。

2. 相关工作

特征提取在基于特征的图像匹配中是最重要的过程。角点是图像中比较特殊的一类特征,如何提取并有效表示图像中的角点,便成为首要的任务。本文采用SUSAN算子进行角点检测,该算法具有简单、角点定位精度高、运算速度快等各种优点,但与其它现有角点检测方法一样,只能实现角点定位而不能提取其角度。为此,可通过Radon变换将平面图像中的直线映射到参数平面来实现角度提取。由于同一物体的放大或缩小,在几何关系上表现为比例关系,基于同一物体的这种比例关系即可实现图像的匹配。

2.1. SUSAN角点检测

SUSAN角点检测方法是一种利用图像灰度信息进行角点检测的方法。该方法首先建立一个圆形模板,其中心点称为核点,把图像上落在模板内且与核点相同或相似的像素所构成的区域称为核值相似区(USAN)。如图1所示,SUSAN算子将圆形模板在整幅图像中移动,若模板内图像某点的灰度值与模板核点像素灰度值的差小于某个阈值,则认为两点是同值的。USAN区域包含了图像在该模板局部区域的

Figure 1. Diagram of SUSAN operator

图1. SUSAN算子示意图

结构信息,区域大小反映了图像局部特征的强度。当模板完全位于背景或目标内部时,模板中的USAN面积最大,如图中所示;当模板逐渐移动到边缘时,USAN面积逐渐减小,如图中所示;当模板移动到角点位置时,USAN面积到达最小,如图中所示。

USAN区域面积的计算公式如下:

(1)

式(1)中,为中心位于的模板区域,为模板内同值像素的判别函数,定义如下:

(2)

式(2)中,分别代表模板内任意点和模板中心点的灰度值,为灰度值门限。最后,角点的判别函数按公式(3)定义:

(3)

式(3)中,为非极大值抑制门限,SUSAN角点检测算法将的值设定为 (定义为USAN最大面积)的一半。

2.2. Radon变换

Radon变换定义 [7] :在任意空间域,一个维函数的Radon变换定义为维超平面的积分值。若考虑的特例,Radon变换是计算图像在某一指定角度射线方向上投影的变换。二维平面函数的Radon变换为:

(4)

式(4)中,为图像平面,为图像上点的灰度值;上的点在投影线

上的投影点到中心点的距离:

(5)

式(5)中为投影线与水平轴的夹角。映射关系如图2所示。

Radon变换将图像从灰度平面映射到参数平面,对图像函数求出各个值的投影,从而对图像全角度观察。若图像中存在直线,直线的法线方向投影最大,在参数平面处该直线会形成一个峰值,通过提取峰值对应的,可以得到图像平面中直线的斜率和偏移量。

2.3. 几何关系相似性

几何相似性定义:如果两个物体各点之间存在一一对应关系,使得对应点之间的距离之比对所有可能的点都不变(等于同一个常数),则称这两个物体是几何相似的。

对于几何相似的物体来说,它们的形状是一样的,只是在大小上是按比例缩放的。如图3所示的两个物体,在满足几何关系相似性的前提下,必然有如下式(6)成立:

(6)

3. 建立特征矢量

在未知图像分辨率时,首先以本文第2部分介绍的特征提取方法,分别提取模板图像与待匹配图像的角点信息,并各自形成特征矢量组;再从模板图像建立的特征矢量组中任选三个不同的特征矢量构建平面,用穷举法搜索待匹配图像建立的特征矢量空间,将与图形满足几何关系相似性的图形作为

Figure 2. Diagram of radon transformation

图2. Radon变换示意图

Figure 3. Diagram of geometric similarity

图3. 几何相似性示意图

一种匹配输出。特征矢量由多个矢量因子组成,每一项因子对应特征的某一方面信息,矢量因子空间相互正交,以保证用于表征所选取特征的特征信息具有唯一的可识别性。

3.1. 可测量角点及角点类型定义

角点可能由两条或者多条直线构成 [8] 。由两条直线构成的角点,其角度有唯一值,可以提供明确的角度信息;而由多条直线构成的角点,则具有更加明显的结构特点,可以提供角点的结构信息。但由多条直线构成的角点,在对其进行类型判定时会显著提升计算复杂度,所以本文着重研究X型、Y型和V型角点,并对角点定义准则如下:

准则1:以角点为起始点的边界必须不大于4条且不少于2条;

准则2:边界均需具有一定的长度;

准则3:边界上的像素点必须在近似直线段上;

准则4:X型角点必须是两条边界的交叉;

准则5:Y型角点必须是三条边界相接或两条成90˚夹角的边界相接。

3.2. 角点可测度判定

根据上述的角点及角点类型定义准则,指定如下角点可测性判定方法:

1) 针对准则1,以角点为中心作一个半径为的圆,圆上某一点为起始点,逆时针遍历灰度至起始点,记录圆周上灰度较大幅度稳定变化的次数,如果发生零次或一次跳变,则认为角点不满足准则1,该点为角度非可测角点;如果大于等于2次跳变,则该点可能为角度可测性角点,如图4所示。

2) 针对准则2,只需将(1)中的圆半径设置为合适的值,即可保证角点的两条边界都足够长。

3) 针对准则3,将(2)中的圆半径三等分,得到半径。分别以为半径作圆,记录每个圆上灰度发生跳变的点:,则这些点与角点构成直线与水平方向的夹角。如果有任意两角度差近似相等,则表明该斜率对应的直线是角点的某一边。

Figure 4. Diagram of detectable Corner

图4. 可测度角点示意图

3.3. 角点边缘直线的提取

在进行Radon变换前,目前广泛采用的是先通过canny边缘提取方法得到二值化图像,再对此二值化图像进行Radon变换。这种计算方法简单、方便,但同时也带来以下两个问题:1) 弱边缘在边缘提取时信息丢失;2) 在边缘提取时对图像的边界进行细化、填充断点等操作,使得边缘的像素不在一条直线上,在Radon变换时该直线在参数平面峰值比较平坦,不利于局部极大值的提取。

具体运算时,可以在参数平面设置一个二维数组。开始时设置数组为0,让遍取上所有的可能值,并通过公式(5)计算,再将已经取整的值进行累加。如果对图像进行二值化,Radon变换的累加器。角点具有明显的梯度特征,对其边缘直线上的梯度值进行累加,会使累加结束后边缘直线上的梯度值比较大,从而在参数平面形成峰值。

3.4. 角度提取

本文将角点划分为X型、Y型和V型三种类型。而在将其设置为特征的特征因子作为匹配对比要素时,X型和Y型角点因为角度提取的复杂性,更多的是应用其结构信息;而V型角点,更多的应用其角度信息。根据Radon变换,角点的边界在Radon变换后,在参数平面上形成最亮的峰值点。本文着重介绍V型角点的角度提取,此时在参数平面上形成最亮的两个峰值点,如图5图6所示。

根据Radon变换原理,可知Radon变换能检测直线的斜率,是法线与轴的夹角,通过坐标几何关系得到直线与轴的夹角为:

(7)

Figure 5. An image with two lines

图5. 包含两条直线的图像

对应的直线与轴的夹角可以通过公式(7)求得。夹角在坐标平面中映射到参数平面后关系如图7所示,则V型角点的夹角角度为

3.5. 匹配算法实现流程

1) 对输入的模板图像和待匹配图像分别进行SUSAN角点检测,检测的角点总数分别为,初始化

2) 对SUSAN检测结果图扫描,扫描到一个角点,以该角点为中心,获取仅包含一个角点的子领域图像区域;

3) 将该角点进行角点角度可测量判定,如果满足可测量条件,转至(4),否则转至(8);

4) 将该角点进行角点类型判定,对符合判定准则的X型和Y型角点,建立该点的特征矢量 (或),转至(8);对符合V型判定准则的角点,建立特征矢量并转至(5);

5) 将该子领域图像中的每个点进行Radon变换;

6) 进行非极大值抑制后提取附件的所有峰值点,排序选取最大的两个峰值点;

7) 利用角点夹角计算公式得出夹角等于,将夹角值作为矢量因子填入该点的特征矢量

Figure 6. Image of line with Radon transformation

图6. 直线Radon变换后的图像

Figure 7. Angle mapping from to

图7. 夹角从平面映射到平面

8) 判断是否小于,若小于累加1,返回(2),否则继续;

9) 从模板图像的特征矢量组中任选三点构建平面三角形

10) 从待匹配图像的特征矢量组中任选三点构建平面三角形

11) 按式(6)计算的几何关系相似性,若满足转至(12),否则转至(10);

12) 输出模板图像与待匹配图像的像素分辨率比例关系,并定位模板图像。

4. 实验结果与分析

为了验证所提算法的图像匹配性能,根据上述算法原理和实现流程,构建验证平台和图像:

a) 待匹配图像:图8 (分辨率72 dpi,614 × 389像素);

b) 参考图像:图9 (分辨率72 dpi,344 × 346像素)、图10 (分辨率36 dpi,307 × 194像素)、图11 (分辨率24 dpi,205 × 129像素)、图12 (分辨率18 dpi,154 × 97像素)、图13 (分辨率9 dpi,77 × 49像素)。

为显示方便,将分辨率不同的图像展成相同大小,显然随着分辨率的降低,图像将更加模糊。

Figure 8. (72 dpi, 614 × 389)

图8. (72 dpi, 614 × 389)

Figure 9. (72 dpi, 344 × 346)

图9. (72 dpi, 344 × 346)

Figure 10. (36 dpi, 307 × 194)

图10. (36 dpi, 307 × 194)

Figure 11. (24 dpi, 205 × 129)

图11. (24 dpi, 205 × 129)

Figure 12. (18 dpi, 154 × 97)

图12. (18 dpi, 154 × 97)

验证平台选用角点类型和角度值作为特征矢量的信息因子。对于信息比较复杂的图像,可以选用更多的信息因子来构建特征矢量,但信息因子的数量与计算量成几何倍增关系。实验结果如图14~19所示,分别为根据图8~13得出的几何匹配形状。

Figure 13. (9 dpi, 77 × 49)

图13. (9 dpi, 77 × 49)

Figure 14. (72 dpi, 614 × 389)

图14. (72 dpi, 614 × 389)

Figure 15. (72 dpi, 344 × 346)

图15. (72 dpi, 344 × 346)

Figure 16. (36 dpi, 307 × 194)

图16. (36 dpi, 307 × 194)

Figure 17. (24 dpi, 205 × 129)

图17. (24 dpi, 205 × 129)

Figure 18. (18 dpi, 154 × 97)

图18. (18 dpi, 154 × 97)

表1列出了通过计算得到的分辨率比例以及相对误差。通过实验证明,根据模板的特征信息建立特征图形后,待匹配图像能够从模板的特征矢量组中搜索匹配的特征矢量,从而在待匹配图像中建立与模板图像相对应的特征图形,成功实现定位。

为了对比本文所提匹配方法与其他方法的效果差异,选用Hausdorff距离下的图像匹配方法对图8~13进行对比性匹配实验。验证过程中仍采用canny算子将图像进行边缘检测并将其二值化处理;图8作为待匹配图像,以图9~13作为模板分别遍历图8,计算相应的Hausdorff距离,然后分别定位图9~13在图8中的位置,所得结果如图20(a)~(e)所示。图中的矩形框为模板图像在待匹配图像中的位置。此实验很明确的验证了,对于分辨率不同的两幅图像用Hausdorff法进行匹配的效果:在图像分辨率相差较大时,Hausdorff法的图像匹配效果较差,但随着分辨率的逐渐接近((e)中匹配图像分辨率差异最大,(d)次之,(a)最小),定位逐渐逼近准确位置。

Figure 19. (9 dpi, 77 × 49)

图19. (9 dpi, 77 × 49)

Figure 20. Results of Hausdorff based image matching

图20. Hausdorff匹配效果

表1. 分辨率比例以及相对误差

5. 结论

基于特征矢量的不同分辨率图像匹配方法利用图像之间特征的相对不变性,较好地实现了不同分辨率图像之间的匹配定位。通过实验与基于Hausdorff距离计算的图像匹配方法进行对比验证,结果表明所提方法对于不同分辨率的图像匹配具有更优的效果。

文章引用

刘 超,钱 丰,刘文松. 基于特征矢量的不同分辨率图像匹配方法
A Feature-Vector Based Multi-Resolution Image Matching Method[J]. 图像与信号处理, 2017, 06(03): 147-159. http://dx.doi.org/10.12677/JISP.2017.63018

参考文献 (References)

  1. 1. 章为川, 孔祥楠, 宋文. 图像的角点检测研究综述[J]. 电子学报, 2015, 43(11): 2315-2321.

  2. 2. Zuniga, O.A. and Haralick, R. (1983) Corner Detection Using the Facet Model. IEEE CVPR, 18, 30-37.

  3. 3. Smith, S.M. and Brady, M. (1997) A New Approach to Low Level Image Processing. International Journal of Computer Vision, 23, 45-78. https://doi.org/10.1023/A:1007963824710

  4. 4. Rosten, E. and Porter, R. (2010) A Machine Learning Approach to Corner Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32, 105-117. https://doi.org/10.1109/TPAMI.2008.275

  5. 5. Klanderman, G.A., Huttenlocher, D.P. and Rucklidge, W.J. (1993) Comparing Images Using the Hausdorff Distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15, 850-863.

  6. 6. Lowe, D.G. (2004) Distinctive Image Features from Scale-Invariant Keypoints. International Journal of Computer Vision, 60, 91-110. https://doi.org/10.1023/B:VISI.0000029664.99615.94

  7. 7. 陈至坤, 潘晓娣, 王福斌, 等. 基于Radon变换的图像轮廓提取方法研究[J]. 传感器与微系统, 2010, 29(2): 63-68.

  8. 8. 马婧, 徐守时, 陈克. 基于Radon变换的图像角点角度提取算法[J]. 光电工程, 2009, 36(2): 126-131.

期刊菜单