东北大学学报:自然科学版   2016, Vol. 37 Issue (2): 157-161   PDF (609 KB)    
基于投票策略的特征点提取
陈红1, 2, 吴成东1, 陈东岳1, 卢紫微1    
1.东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
2.鞍山师范学院 物理科学与技术学院, 辽宁 鞍山 114005
摘要:特征点提取算法中存在伪角点和定位不准确的问题,导致特征点匹配率低,并且影响图像配准精度和速度.针对这一问题,提出基于投票策略的特征点提取算法.算法通过选举人投票选举出最强特征性点集,有效去除伪角点.点集中的特征点满足多重准则,特征性强度高.依据坐标选举,保证了特征点定位的准确性.在发生相似变换、亮度变化和加噪的情况下对大量图像进行了特征点提取和匹配实验,并与传统的特征点提取方法进行比较.实验结果表明,该算法提取的特征点具有更好的有效性,算法具有较强的适应性和抗噪性.
关键词特征点提取     点匹配     投票策略     图像配准     伪角点    
Key Point Extraction Based on Voting Strategy
CHEN Hong1, 2, WU Cheng-dong1,CHEN Dong-yue1,LU Zi-wei1    
1. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. School of Physics Science and Technology, Anshan Normal University, Anshan 114005, China.
Corresponding author: CHEN Hong, E-mail: chenhongbuty@126.com
Abstract: False corners and inaccurate orientation in key point extraction algorithms will result in low matching rate and low image registration accuracy and speed. A new method is proposed to solve the problem. A set of strongest interest points is worked out in the algorithm to eliminate false corners. Interest points in the set have high characteristic strength and meet several criteria. The same coordinate is applied to ensure orientation accuracy. With similarity transformation, brightness change and noise, a series of images are tested with the new algorithm proposed and traditional algorithms, respectively. The results show that the new algorithm has better adaptability and anti-noise performance, and is more effective in feature points extraction.
Key words: key point extraction     point matching     voting strategy     image registration     false corner    

图像配准是将不同时间、不同传感器或不同视角获取的同一场景的两幅或者多幅图像,通过纠正几何形变,变换到同一坐标系下,实现同名点精确对准的过程.它是图像进行拼接、融合、比较等高级处理的基础.图像配准有多种分类方法[1],其中较常见的有基于灰度方法和基于特征方法.基于特征的配准方法是目前主要的研究方向.依据特征类型的不同,又产生了基于点、基于线和基于区域的方法.基于点特征的配准方法在配准速度、精度等方面优势较明显,是当前的主流研究方向.基于点特征的配准方法通常分为四步:特征点提取、特征点匹配、求解变换参数和图像变换及插值.

特征点是图像的极值点,又被称为兴趣点或者角点.特征点提取是一项关键且困难的工作,它是图像配准能够顺利进行的保证.现有的特征点提取方法遵循各自的提取准则,在旋转不变性、尺度不变性、抗噪性,以及适应性等方面不尽相同.提取的特征点集通常包含伪角点和定位不准确的特征点,而且数量巨大,将这样的点集直接匹配,会导致较长的匹配时间和较低的匹配率,以至于影响配准的精度和速度.

投票选举是生活中很常见的一种选举方法,属于社会选择理论,被广泛地应用于多种领域,如决策论、集成学习等,且取得了很大的成效.

本文将投票策略应用于待匹配特征点的选取,提出基于投票策略的特征点提取方法.文中主要介绍了该方法的基本思想和实现步骤,编程实现了算法,对大量图像进行了测试.结果表明,该方法提取的特征点具有更高的有效性,与传统算法进行比较,性能较好.

1 特征点提取方法

现有的特征点提取方法选取特征点的准则和特性各有异同.有的方法通过计算像素灰度变化最大值选取特征点,如Moravec,Harris和MinEigen,该类方法采用微分运算,对噪声较敏感[2, 3, 4].有的方法通过统计像素周围特定范围与该点灰度相同或不同的像素的个数选取特征点,如SUSAN和FAST,该类方法最大特点是速度快,抗噪性好[5, 6];有的方法利用尺度空间建立高斯金字塔选取特征点,如SIFT,SURF,该类方法有较好的尺度不变性,但算法复杂度高[7, 8];还有的算法通过SIFT,SURF和FAST检测特征点,利用邻域内点对的灰度大小关系生成二进制编码进行描述,如BRIEF,ORB和FREAK,该类方法的优点是速度快且旋转不变性较好[9, 10, 11].

本文测试算法性能时将Harris,FAST和MinEigen算法作为选举人,参与投票.

1.1 Harris角点提取

Harris算法[3]是Harris和Stephens于1988年提出的一种角点检测算子.算法利用自相关矩阵M来计算角点响应函数R,用下式表示:


式中:det(M)为矩阵的行列式,trace(M)为矩阵的迹;k的取值通常为0.04,自相关矩阵M定义为


式中:IxIy分别是点(x,y)水平和竖直方向的灰度梯度值;G(s)为高斯平滑模板,


当点(x,y)的响应值大于阈值时为角点.

1.2 FAST角点提取

FAST(features from accelerated segment test)算法[6]由Rosten 和Drummond于 2006年提出,在2010年进行完善.

该算法检测角点的标准是:以某点为圆心,如果周围的圆形模板上有足够多连续像素点比中心点灰度大或者小,那么中心点就是角点.FAST圆形模板示意图如图 1所示.

p点附近半径为3的圆环上的16个点,若其中有连续的12个点灰度值与p点的灰度值差别超过某一阈值,则可以认为p点为角点.

图 1 FAST圆形模板示意图 Fig. 1 Schematic of FAST round template
1.3 MinEigen算法

MinEigen(minimum eigenvalue algorithm)算法[4]由Shi和Tomasi于1994年提出.

算法首先对图像Image中的每一个像素点p(x,y)计算相关矩阵M


式中:IxIy分别为x,y方向的梯度;w(x,y)为窗函数,通常取高斯函数.

然后,对图像中的每一个点计算M的特征值λ1λ2,取min(λ1,λ2)得到图像对应的特征值.

最后依据给定的阈值λ,若min(λ1,λ2)>λ,认为该点为角点.

2 基于投票策略的特征点提取方法

投票是选举人使用自己选举权利的一种方式.利用投票方式选举出的代表符合多个投票人的意志和要求.本文通过多种算法投票的方式,选举出符合多准则的具有相同坐标的点作为特征点,这样的点具有高特征性强度和精准的定位.

2.1 算法基本思想

投票策略的很多优点使其应用于多种领域,但如果投票成员观点单一,投票意义会被削弱;如果投票成员中有效果差的,将会影响整体投票效果,使得投票的结果要比最好成员的性能差.本算法中参与投票成员的主要观点或准则虽然不尽相同,但都是以选取角点为唯一目的,而且在位置坐标的约束下,只有当多个投票成员都认为某一坐标的点为角点时,才认为该点为待匹配角点.投票结果会删除定位不准确的角点,使得投票的意义更强而不会被削弱.对于提取图像中特征点集的问题,衡量投票效果的标准在于定位精度及其有效性.本算法选取多个投票成员获得的具有相同坐标的点作为待匹配特征点,是保证定位精度的关键.该算法是以牺牲特征点的数量为代价的,特征点的数量一定会少于或等于各成员的特征点数量.在图像配准中,角点个数并非越多越好,为了提高运算速度,在保证数量充足的情况下往往需要减少角点个数,本算法能够得到数量足够的具有更高准确性的角点集.另外,通过投票方法淘汰了大量的伪角点,这将提高特征点匹配率及配准精度和速度.

2.2 算法实现步骤

1) 投票得到候选点集.选取N种特征提取方法V1,V2,…,VN作为选举人,对图像的各像素进行投票,得到N个候选点集P1,P2,…,PN.每个候选点的初始特征性强度即票数NOV记为1.

2) 唱票、计票得到候选点的特征性强度.对N组候选点进行比对,若点集P1中的点p也在点集P2中,则认为V2也投其一票,将该点NOV加1,依此类推,计算出p点特征性强度NOV.依此法,统计每个候选点的得票数NOV,max(NOV)为N.

3) 依据NOV分组.将NOV相同的候选点存储在同一点集中,得到N组特征性强度不同的特征点集F1,F2,…,FN.点集中点的NOV取值为II∈(1,N).点集中点的个数记为Gii=1,2,…,N.将FN称为最强点集,FN-1称为次强点集.

4) 确定特征点集F.设定特征点数量阈值K,若最强点集FN中点的个数GN大于或等于K,则FN为特征点集,否则将最强点集FN与次强点集FN-1中的GN+GN-1个点共同作为特征点集F.

3 实验结果与分析

本文的基于投票策略的特征点提取方法在Matlab环境下编程实现.选用Harris,FAST和MinEigen三种算法作为选举人.实验对多组不同类型、不同大小的图像进行了测试,实验结果表明,在图像平移、亮度变化以及加噪声的情况下,本文算法提取的特征点的有效性即匹配率都高于传统方法.实验中匹配率定义为,匹配点对的数量与两幅图像提取到的特征点中数量较小的数值的比值.

3.1 算法有效性

对256×256的Cameraman灰度图像和512×512的Airfield灰度图像进行平移,改变900×600的Office彩色图像的亮度,测试了各算法的匹配率,结果见表 1:1~3行分别为采用FAST,Harris和MinEigen算法提取到的特征点集的匹配率,特征点的NOV值为1;4~6行为使用两种特征提取方法投票获得的特征点集的匹配率,特征点的NOV值为2;最后一行为使用三种特征提取方法投票获得的特征点集的匹配率,特征点的NOV值为3.

表 1 各算法匹配率及NOV Table 1 Matching rate and NOV of various algorithms

表 1可以看出,使用投票策略得到的特征点强度为2的特征点集的匹配率明显高于特征点强度为1的匹配率,特征点强度为3的特征点集的匹配率明显高于特征点强度为2的匹配率.结果表明,通过本文算法可以获得特征性较强的特征点集;点集的特征性强度越高,则匹配率越高,算法提取出的特征点的有效性越好.

3.2 特征点的数量

表 2为三组图像正确匹配点对数.NOV为3的最强点集的点对数分别为17,103和14,基本能够满足图像配准等高级处理的要求.

表 2 各算法匹配点对数 Table 2 Number of matching pairs of various algorithms

在Cameraman和Office图像中,若需要更多的匹配点对,可以增选NOV=2的次强点集作为特征点集,总点对数分别为98和63.算法可依据设定的阈值K自动选取点集种类.

3.3 算法抗噪性

表 3为对Cameraman加0.01椒盐噪声后,采用Harris和MinEigen投票选举出的特征点个数、匹配点对数和匹配率统计.

表 3 加噪声后各算法匹配点对数和匹配率 Table 3 Matching rate and pairs of various algorithms with added noise

表 3可见,对图像加噪以后,采用本文算法提取特征点的匹配点对数为45,数量适中可以满足配准等处理的要求,匹配率为60.8%,高于Harris和MinEigen的52.7%和35.7%.实验结果表明,本文算法具有较强的抗噪性.

3.4 特征点提取与匹配效果

图 2是分别采用MinEigen方法和本文方法进行特征点提取和特征点匹配的结果图.

比较图 2a图 2d图 2b图 2e可见,采用本文方法提取到的最强点集中不存在伪角点,特征点定位准确,分布合理,数量适中.

比较图 2c图 2f可见,MinEigen方法存在明显的误匹配,而本文方法的匹配结果满足一对一,无误匹配.

图 2 不同算法对比结果图 Fig. 2 Comparison of different algorithms(a),(d)—在参考图像中提取特征点; (b),(e)—在待配准图像中提取特征点; (c),(f)—特征点匹配.
4 结 语

本文介绍了基于投票策略特征点提取方法的基本思想、实现步骤,对算法性能进行了测试.初步实验结果表明,该算法能够提取出特征性强度较高的最强点集和次强点集;点集中的特征点不包含伪角点,定位准确,特征点的有效性较强.算法能够在多种情况下获得较好的效果,具有较强的适应性和抗噪能力.虽然本文算法在投票选取特征点时会消耗一定的时间,但使用这样有效性高、数量适中且定位精准的特征点进行配准,会有效地减少特征点匹配和寻优的时间,同时提高配准精度.

参考文献
[1] Zitová B,Flusser J.Image registration methods:a survey [J].Image and Vision Computing,2003,21(11):977-1000.(1)
[2] Moravec H.Rover visual obstacle avoidance[C]// Proceedings of the Seventh International Joint Conference on Artificial Intelligence.Vancouver:Springer-Verlag,1981:785-790.(1)
[3] Harris C,Stephens M J.A combined corner and edge detector[C] // Allvey Vision Conference.Sydney:University of Sydney,1988:147-152.(2)
[4] Shi J,Tomasi C.Good features to track[C] // Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Los Alamitos:IEEE,1994:593-600.(2)
[5] Smith S M,Brady J M.SUSAN—a new approach to low level image processing[J].Journal of Vision,1997,23(1):45-78.(1)
[6] Rosten E,Drummond T.Machine learning for high-speed corner detection[C] // European Conference on Computer Vision.Graz:Springer-Verlag,2006:430-443.(2)
[7] Lowe D G.Distinctive image features from scale-invariant key points[J].International Journal of Computer Vision,2004,60(2):91-110.(1)
[8] Herbert B,Andreas E,Tinne T.SURF:speeded up robust features [J].Computer Vision and Image Understanding,2008,110 (3):346-359.(1)
[9] Calonder M,Lepetit V,Strecha C.BRIEF:binary robust independent elementary features[C] // 11th European Conference on Computer Vision (ECCV).Heidelberg:Springer-Verlag,2010:402-411.(1)
[10] Ethan R,Vincent R,Kurt K.ORB:an efficient alternative to SIFT or SURF[C]// 13th International Conference on Computer Vision(ICCV).Piscataway:IEEE,2011:1673-1678.(1)
[11] Alahi A.FREAK:fast retina keypoint[C]// IEEE Conference on Computer Vision and Pattern Recognition (CVPR).Washington D C:IEEE Computer Society,2012:510-517.(1)