一种快速多尺度特征点匹配算法概要

1、第卷第期200 年 月.,200Vol. ,No.中国图象图形学报Journal of Image and Graphics一种快速多尺度特征点匹配算法邵 巍1）朱圣英1）陈灵芝2）1）（哈尔滨工业大学深空探测基础研究中心 ，哈尔滨150080）2）（青岛科技大学自动化与电子工程学院，青岛266042）摘要为了快速稳定地进行多尺度特征点的跟踪，提岀了一种快速多尺度特征点的提取算法。该算法首先利用 快速局部窗口极值搜索算法提取岀不同尺度空间的特征点的局部极值，然后对特征描述符进行小波变换后，再利 用最近邻算法对特征点进行匹配。实验结果表明，该算法的计算速度快于SIFT算法和MOPS算法，稳定性强

2、于传统的Harris算法，可以用于实时图像配准及目标跟踪3002关键词特征点提取特征点匹配多尺度变换MOPS SIFT Harris角点中图法分类号：TP391.41 文献标识码:AA Fast Multi-Scale Feature Matching AlgorithmSHAO Wei, ZHU Sheng-ying, CHEN Ling-zhi(Deep Space Explorati on Research Center, Harbi n In stitute of Tech no logy, Harbin 150008)Abstract This paper presents a Mu

3、lti-Scale feature extraction algorithm, which computes maximum of the features in moving windows using fast algorithm and gets the matching features using nearest neighbor matching algorithm that indexes features based on their low frequency Haar wavelet coefficients. The experimental results show t

4、hat this algorithm is faster than the SIFT and MOPS, and has more stability than Harris algorithm. The algorithm can be used in image registration and target tracking.Keywords feature extraction; feature matching; multi-scale transform; MOPS; SIFT; Harris corner1引言基于尺度空间的特征点提取算法是利用图像 的特征不变描述符对不同尺度空间

5、的特征点进行 描述。Schmid和Mohr最早利用高斯微分算子对 传统的Harris算法进行改进，形成了旋转不变 的特征描述2。Lowe对此算法进行了改进，在不同尺度空间进行特征点的提取，形成了 SIFT（scale-invariant feature transform）算法 。 SIFT算法对图像的旋转、缩放及光照影响都具有 一定的鲁棒性。Brown 等人提出了MOPS（multi-scale oriented patches）算法，进行不 同尺度上Harris特征点的提取，并利用窗口搜索 算法对特征点的局部极值进行提取。由于SIFT算法和MOPS算法对特征点的提取一般都采用穷 举算法搜索

6、，计算量较大，因而在图像实时处理 中的应用受到限制。本文利用快速局部窗口搜索 算法进行多尺度特征点局部极值的提取，从而提 高了特征点提取的速度。基金项目：国家自然科学基金（60874094）收稿日期：2008-02-29; 改回日期：2008-12-12E-mail:greatshao第一作者简介：邵巍（1980-），男，博士研究生。主要研究工作是基于图像信息的深空探测器自主导航。中国图象图形学报第卷=-7 2 I b max W,H2多尺度Harris特征点提取局部最大值,即计算 y =max4j(i=0,n-w),则进行多尺度Harris特征点提取时，要对灰度 图像I x,y先利用高斯平滑

7、函数卷积形成图像 金字塔。金字塔的最底层R(x y(x,y、更高层的金字塔表示为Pl x,y 二R x,y : g. x, yRi x, y 二 R sx,sy其中，I表示金字塔的层数，g._x, y表示标准差 为匚的高斯平滑窗口，s为采样间隔，一般取 2。第I层坐标x, y处的Harris特征点检测矩阵可以 表示为HI (X, y 尸陷R(X, y 詹R X, y 碍g*x, y) 其中，I ；3表示在尺度 二上的梯度，即x,y 八 f x,y _gc x, y参考文献4将积分尺度口和微分尺度 6的值分 别取为1.5和1.0，并利用矩阵 H特征值(!, 9) 的调和平均检测函数皿来检测特征点

8、，即fHM x,y匚嚳亠 trH i (x, y)入+為当fHM大于某个阈值(一般取为10)，该点即为特 征点。3局部区域快速特征点选取算法由于特征点匹配的速度与特征点的个数直接 相关，同时由于底层金字塔提取的Harris特征点主要集中在物体的边缘和角点处，分布很不均匀； 若只将整幅图像中第皿最大的多个特征点提取出 来以减少特征点的个数，则可能使得这些特征点 仅局限在某个局部区域，不利于重合区域较小的 图像间的匹配。因此，本文在不同尺度金字塔图 像的一定半径范围内选取匚皿的局部极值，并通过控制采样窗口的大小来控制特征点的提取个 数。其中半径r的选取公式可选择如下：其中，W、Hl分别表示金字塔第

9、I层图像的宽度和高度。3.1特征点局部极值的快速算法在传统的Harris算法中，若某个像素对应的fHM值在周围3X 3的邻域中是最大值，则该像素即为特征点。这里将邻域范围扩大到w x w窗口范围内来选取特征点，这就将特征点选取转化为 在WX H的图像中对大小为 wx w的窗口中进行 局部极值搜索的问题，若中心元素为极值，则判 定该点为特征点。一般采用穷举法来进行搜索， 根据条件概率计算，平均要进行1 1w W 1 H w 1 k ( k =12)次比较，计算量较大。本文利用形态学滤波中的极 大值滤波的思想5-7,采用改进的HGW(Herk-Gil-Werman)算法，并将最大值滤波的求取 过程

10、转化为2维窗口内局部极值的求取，以加快 运算速度。具体步骤如下：(1) 设图像的像素用矩阵 X表示，先将图像扩充 到 X - IX A ,其中 A 为 H (w _mod(W,w)的全零矩阵(mod表示取余运算)，这样可以将X均 分为宽度为w的多个子矩阵。(2) 将2维窗口内极值的计算分解为水平、垂直2次1维窗口极值的计算：max '.f x k, y I J = max max.f x k,y I ”订(7)-w k w. w_w _w _k _w-w-r_w记X某一行的元素为 xc ,，xn,考虑1维数组的用序列Xw亠X2w丄X3w,将该行元素分为多个小 数组，数组中间元素的下标记

11、为t。对于包括xt的每个小数组，定义如下序列元素&和Qk (k=0,w-1):& =&(t人亠必丄)=max(&亠人丄)(幼Q =Qk t i；=max 人，人.“，人 =max Qk 亠人 k该步骤对每个小数组需要2(w-1)次比较。这里采用如下的改进算法来提高Rk和Qk的计算速度：w+1w wmod 2I'2 2(9)应元素相减，若某元素的对应值为0,则表示该值为wX w窗口的局部最大值，即在其周围wX w 窗口的元素中没有比它更大的元素。由于分别进先计算Qk (k=0,q-1)和R t 1 (k=q，w),需要 进行q-1+w-q=w-1次比较；然

12、后比较 Qq .和R, t 1，由于Qk是非递减数列，Rq t 1是非 递增数列，若Rq_Qq丄，则Rq丄& Rq ； 最后计算Qq,Qp丄，需要比较w _q次。同理， 若Rq <Qq1，则无须计算Qq，Qw丄，只要比较口-1 次，即可计算R ,，Rq 1。因此计算Rk和Qk平均 共需要进行w 1 |T max w-q,q1 =1.5w wmod2 / 2次 比较。(3) 合并该行元素的 &和Qk，即可得到以下窗口 最大值的函数：tk 二maxxj 上，,为，刍 心丄二max &,Q上丄(10)考虑到Rw 2 _Rw_1 R1 及 Qw _2 Q w 1 _Q1

13、，右 R _Qw丄丄，则对所有的k .i有0 _ R _Sw丄丄，因此不需比较 k -i的情 况。同理，当R兰Sw丄4时，则不需比较kvi的情 况。利用二叉树搜索的原理，该步骤对每个元素 进行搜索的次数为lb w -1 / w。这样就可将 X的每个元素用对应1维窗口的最大值tk代替，得 到矩阵Y。综合步骤运算平均到每个元素的比较 次数为.5 Jb (w(wmod2)(11)w2w若对矩阵Y进行列元素的1维局部极值求取，重 复步骤(1), (2)即可得到2维窗口局部极值的分布 矩阵Y ,即Y表示在某元素半径范围内的最大值 的分布情况。原始图像及对底层金字塔进行局部(a)原始图像(b)底层金字塔局

14、部最大值图1原始图像及局部最大值分布图Fig.1 Original image and local maximum distributing将Y中的扩充矩阵去掉，并将其与X矩阵对行了一次水平方向和垂直方向的局部极值的求 取，所以总共的比较次数为3 十2 |lb(w_1(wmod 2)(12)常规算法、HGW算法及改进的 HGW算法 每元素的比较次数如图 2所示。由图2可以看出， 随着窗口的增大，改进的 HGW算法的单个元素 的比较次数趋向于 3，比较次数少于另外两种算 法。窗口越大，该算法的优势越明显。图2几种算法平均计算次数的比较Fig.2 Average number of compari

15、sons of differentalgorithms3.2特征点方向确定由于传统的Harris特征点检测方法提取的特 征点不带有方向信息，因此对于图像的旋转容易 产生误匹配。采用SIFT算法的思想，利用特征点邻域像素的梯度方向分布特征为每个特征点指 定方向。对L层上的特征点邻域内的坐标 (x,y)处 的方向计算如下：V x, y =actanL x,y 1 -L x,y-1L x 1,y -L x-1,y(13)若用直方图统计邻域像素加权梯度方向的值，则 其峰值即为该特征点的方向。3.3特征点描述符及特征点匹配结合MOPS算法，用特征点周围的8X 8大小的像素的标准化灰度值来对特征点进行描述

16、。 再进行Haar小波变换，即形成 64维的特征描述 向量。特征点描述符形成后，采用次近邻算法 (2-NN)8对不同图像间提取的特征点进行匹配，具体步骤可参考 MOPS算法中的匹配过程。4实验结果及不同算法性能比较为对比不同算法的特征点提取、匹配效果， 对本文算法、SIFT算法及Harris算法进行了对比 实验。运行环境为 PD820(2.8GHz)，编程环境为 V结合Opencv,采集图像的分辨率为640 x480。图中圆的半径大小代表特征点所在的尺度， 圆圈内部短线表示特征点的方向。从特征点提取 的结果(图3)看，Harris算法提取的特征点更集 中在边缘和角点处，而用本文提出的快速MOP

17、S算法提取的特征点分布比SIFT和Harris的特征点分布更为均匀。由于快速MOPS算法是在运算 速度上对MOPS算法的改进，而提取特征点的结 果是一致的，在此不再分开讨论。(a)快速MOPS算法提取结果(b) SIFT算法提取结果(c)Harris算法提取结果图3 快速MOPS, SIFT, Harris提取特征点分布图Fig.3 Features extracted by fast MOPS,SIFT and Harris图4 利用快速MOPS进行匹配的结果Fig.4 Features matching using fast MOPS表1几种算法的比较Tab. 1 Compare of t

18、hese algorithms算法平均运行时间(s)正确匹配的特征点个数错误匹配的特征点个数SIFT6.6223317MOPS1.7119610快速MOPS1.3619610Harris0.92s211116通过表1的比较可以看7出，Harris算法运 行速度最快，但该算法对于图像的旋转、缩放的 稳定性不高，误匹配率较高，不适用于旋转和缩放变化较大的图像间的匹配。SIFT算法用128维描述符对特征点进行描述，稳定性更好，但运算 最慢，不利于实时计算。而MOPS算法是两种算 法的折中，利用快速MOPS算法可以进一步提高 MOPS算法的运行速度，基本上可以满足实时处 理的要求。图4是利用快速MOP

19、S算法对两幅图像进行 特征点匹配的结果。从图上可以看出，虽然两幅 图像内的物体存在缩放与旋转变化，但利用快速 MOPS算法依然可以使得正确匹配的特征点达到 90%左右。通过多次实验测试，对于旋转缩放情 况不是很大的情况，利用快速MOPS算法是稳定 可靠的，大多数情况都可以使得正确匹配的特征 点的比率大于50%，这样就可以通过 RANSAC(random sample consensus) 9等算法去除 误匹配的特征点。同时，由于采用该算法的特征 点分布比较均匀，对于特征跟踪来说，就减小了 由于运动物体某一部分受遮挡而不能连续跟踪所 造成的影响。由于对每层金字塔上的特征点提取， 采用的是Harr

20、is角点算法，对于大角度的旋转情 况，其准确匹配的特征点个数要少于SIFT。因此，可以根据相机、物体运动的不同性质和特征跟踪 对稳定性和实时性的要求，来选择不同的特征匹 配算法。同时，可以根据不同的需要，通过变化 式(6)改变半径大小来控制特征点提取的个数及 分散程度，以进一步提高运算速度。5结论本文提出了一种利用局部极值的快速求法来 提高特征点提取速度的算法。通过比较实验分析 了几种特征点提取算法的优缺点，验证了该算法 的有效性。今后的研究主要集中在以下几个方面： (1)该算法运行时所占内存的要大于传统算法，进一步提高算法的快速性、减少内存消耗是下一步 研究的重点。同时也需研究窗口半径对匹配

21、效果 的影响，通过选取合适的窗口半径，以使其适应 于多种图像间平移、旋转及缩放变换。将该算法灵活运用到 SIFT，SURF等多种特征 点局部极值的求取过程，以拓展该算法的应用范 围。考虑将随机采样策略应用到局部极值的求取 问题中，虽然不能保证全部局部极值的求取，但 可进一步提高该算法的快速性。参考文献(References)Harris C G, Stephens M J. A combined corner and edge detectorA. In: Proceedings Fourth Alvey Vision Conference©, Manchester, UK, 198

22、8:147-151.2 Schmid C, Mohr R. Local grayvalue invariants for image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(5):530-535.3 Lowe D. Distinctive image features from scale-invariant keypointsJ. International Journal of Computer Vision, 2004, 60(2):91-110.4 Brown

23、 M, Szeliski R, Winder S. Multi-image matching using multi-scale oriented patchesA. In: Proceeding of IEEE Computer Society Conference on Computer Vision and PatternC, San Diego, CA, USA, 2005: 510-517.5 Van Herk M. A fast algorithm for local minimum and maximum filterson rectangular and octagonal kernelsJ. Pattern Recognition Letters, 1992, 13(7):517-521.6 Joseph G Michael W. Efficient dilation, erosion, opening, and closing algorithmsJ. IEEE Transactions on Pattern Analysis and Machine Intelligence,1993, 15(