1、第卷第期200 年 月.,200Vol. ,No.中國圖象圖形學(xué)報(bào)Journal of Image and Graphics一種快速多尺度特征點(diǎn)匹配算法邵 巍1）朱圣英1）陳靈芝2）1）（哈爾濱工業(yè)大學(xué)深空探測基礎(chǔ)研究中心 ，哈爾濱150080）2）（青島科技大學(xué)自動化與電子工程學(xué)院，青島266042）摘要為了快速穩(wěn)定地進(jìn)行多尺度特征點(diǎn)的跟蹤，提岀了一種快速多尺度特征點(diǎn)的提取算法。該算法首先利用 快速局部窗口極值搜索算法提取岀不同尺度空間的特征點(diǎn)的局部極值，然后對特征描述符進(jìn)行小波變換后，再利 用最近鄰算法對特征點(diǎn)進(jìn)行匹配。實(shí)驗(yàn)結(jié)果表明，該算法的計(jì)算速度快于SIFT算法和MOPS算法，穩(wěn)定性強(qiáng)

2、于傳統(tǒng)的Harris算法，可以用于實(shí)時(shí)圖像配準(zhǔn)及目標(biāo)跟蹤3002關(guān)鍵詞特征點(diǎn)提取特征點(diǎn)匹配多尺度變換MOPS SIFT Harris角點(diǎn)中圖法分類號：TP391.41 文獻(xiàn)標(biāo)識碼: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引言基于尺度空間的特征點(diǎn)提取算法是利用圖像 的特征不變描述符對不同尺度空間

5、的特征點(diǎn)進(jìn)行 描述。Schmid和Mohr最早利用高斯微分算子對 傳統(tǒng)的Harris算法進(jìn)行改進(jìn)，形成了旋轉(zhuǎn)不變 的特征描述2。Lowe對此算法進(jìn)行了改進(jìn)，在不同尺度空間進(jìn)行特征點(diǎn)的提取，形成了 SIFT（scale-invariant feature transform）算法 。 SIFT算法對圖像的旋轉(zhuǎn)、縮放及光照影響都具有 一定的魯棒性。Brown 等人提出了MOPS（multi-scale oriented patches）算法，進(jìn)行不 同尺度上Harris特征點(diǎn)的提取，并利用窗口搜索 算法對特征點(diǎn)的局部極值進(jìn)行提取。由于SIFT算法和MOPS算法對特征點(diǎn)的提取一般都采用窮 舉算法搜索

6、，計(jì)算量較大，因而在圖像實(shí)時(shí)處理 中的應(yīng)用受到限制。本文利用快速局部窗口搜索 算法進(jìn)行多尺度特征點(diǎn)局部極值的提取，從而提 高了特征點(diǎn)提取的速度。基金項(xiàng)目：國家自然科學(xué)基金（60874094）收稿日期：2008-02-29; 改回日期：2008-12-12E-mail:greatshao第一作者簡介：邵巍（1980-），男，博士研究生。主要研究工作是基于圖像信息的深空探測器自主導(dǎo)航。中國圖象圖形學(xué)報(bào)第卷=-7 2 I b max W,H2多尺度Harris特征點(diǎn)提取局部最大值,即計(jì)算 y =max4j(i=0,n-w),則進(jìn)行多尺度Harris特征點(diǎn)提取時(shí)，要對灰度 圖像I x,y先利用高斯平滑

7、函數(shù)卷積形成圖像 金字塔。金字塔的最底層R(x y(x,y、更高層的金字塔表示為Pl x,y 二R x,y : g. x, yRi x, y 二 R sx,sy其中，I表示金字塔的層數(shù)，g._x, y表示標(biāo)準(zhǔn)差 為匚的高斯平滑窗口，s為采樣間隔，一般取 2。第I層坐標(biāo)x, y處的Harris特征點(diǎn)檢測矩陣可以 表示為HI (X, y 尸陷R(X, y 詹R X, y 礙g*x, y) 其中，I ；3表示在尺度 二上的梯度，即x,y 八 f x,y _gc x, y參考文獻(xiàn)4將積分尺度口和微分尺度 6的值分 別取為1.5和1.0，并利用矩陣 H特征值(!, 9) 的調(diào)和平均檢測函數(shù)皿來檢測特征點(diǎn)

8、，即fHM x,y匚嚳亠 trH i (x, y)入+為當(dāng)fHM大于某個閾值(一般取為10)，該點(diǎn)即為特 征點(diǎn)。3局部區(qū)域快速特征點(diǎn)選取算法由于特征點(diǎn)匹配的速度與特征點(diǎn)的個數(shù)直接 相關(guān)，同時(shí)由于底層金字塔提取的Harris特征點(diǎn)主要集中在物體的邊緣和角點(diǎn)處，分布很不均勻； 若只將整幅圖像中第皿最大的多個特征點(diǎn)提取出 來以減少特征點(diǎn)的個數(shù)，則可能使得這些特征點(diǎn) 僅局限在某個局部區(qū)域，不利于重合區(qū)域較小的 圖像間的匹配。因此，本文在不同尺度金字塔圖 像的一定半徑范圍內(nèi)選取匚皿的局部極值，并通過控制采樣窗口的大小來控制特征點(diǎn)的提取個 數(shù)。其中半徑r的選取公式可選擇如下：其中，W、Hl分別表示金字塔第

9、I層圖像的寬度和高度。3.1特征點(diǎn)局部極值的快速算法在傳統(tǒng)的Harris算法中，若某個像素對應(yīng)的fHM值在周圍3X 3的鄰域中是最大值，則該像素即為特征點(diǎn)。這里將鄰域范圍擴(kuò)大到w x w窗口范圍內(nèi)來選取特征點(diǎn)，這就將特征點(diǎn)選取轉(zhuǎn)化為 在WX H的圖像中對大小為 wx w的窗口中進(jìn)行 局部極值搜索的問題，若中心元素為極值，則判 定該點(diǎn)為特征點(diǎn)。一般采用窮舉法來進(jìn)行搜索， 根據(jù)條件概率計(jì)算，平均要進(jìn)行1 1w W 1 H w 1 k ( k =12)次比較，計(jì)算量較大。本文利用形態(tài)學(xué)濾波中的極 大值濾波的思想5-7,采用改進(jìn)的HGW(Herk-Gil-Werman)算法，并將最大值濾波的求取 過程

10、轉(zhuǎn)化為2維窗口內(nèi)局部極值的求取，以加快 運(yùn)算速度。具體步驟如下：(1) 設(shè)圖像的像素用矩陣 X表示，先將圖像擴(kuò)充 到 X - IX A ,其中 A 為 H (w _mod(W,w)的全零矩陣(mod表示取余運(yùn)算)，這樣可以將X均 分為寬度為w的多個子矩陣。(2) 將2維窗口內(nèi)極值的計(jì)算分解為水平、垂直2次1維窗口極值的計(jì)算：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維數(shù)組的用序列Xw亠X2w丄X3w,將該行元素分為多個小 數(shù)組，數(shù)組中間元素的下標(biāo)記

11、為t。對于包括xt的每個小數(shù)組，定義如下序列元素&和Qk (k=0,w-1):& =&(t人亠必丄)=max(&亠人丄)(幼Q =Qk t i；=max 人，人.“，人 =max Qk 亠人 k該步驟對每個小數(shù)組需要2(w-1)次比較。這里采用如下的改進(jìn)算法來提高Rk和Qk的計(jì)算速度：w+1w wmod 2I'2 2(9)應(yīng)元素相減，若某元素的對應(yīng)值為0,則表示該值為wX w窗口的局部最大值，即在其周圍wX w 窗口的元素中沒有比它更大的元素。由于分別進(jìn)先計(jì)算Qk (k=0,q-1)和R t 1 (k=q，w),需要 進(jìn)行q-1+w-q=w-1次比較；然

12、后比較 Qq .和R, t 1，由于Qk是非遞減數(shù)列，Rq t 1是非 遞增數(shù)列，若Rq_Qq丄，則Rq丄& Rq ； 最后計(jì)算Qq,Qp丄，需要比較w _q次。同理， 若Rq <Qq1，則無須計(jì)算Qq，Qw丄，只要比較口-1 次，即可計(jì)算R ,，Rq 1。因此計(jì)算Rk和Qk平均 共需要進(jìn)行w 1 |T max w-q,q1 =1.5w wmod2 / 2次 比較。(3) 合并該行元素的 &和Qk，即可得到以下窗口 最大值的函數(shù)：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的情 況。同理，當(dāng)R蘭Sw丄4時(shí)，則不需比較kvi的情 況。利用二叉樹搜索的原理，該步驟對每個元素 進(jìn)行搜索的次數(shù)為lb w -1 / w。這樣就可將 X的每個元素用對應(yīng)1維窗口的最大值tk代替，得 到矩陣Y。綜合步驟運(yùn)算平均到每個元素的比較 次數(shù)為.5 Jb (w(wmod2)(11)w2w若對矩陣Y進(jìn)行列元素的1維局部極值求取，重 復(fù)步驟(1), (2)即可得到2維窗口局部極值的分布 矩陣Y ,即Y表示在某元素半徑范圍內(nèi)的最大值 的分布情況。原始圖像及對底層金字塔進(jìn)行局部(a)原始圖像(b)底層金字塔局

14、部最大值圖1原始圖像及局部最大值分布圖Fig.1 Original image and local maximum distributing將Y中的擴(kuò)充矩陣去掉，并將其與X矩陣對行了一次水平方向和垂直方向的局部極值的求 取，所以總共的比較次數(shù)為3 十2 |lb(w_1(wmod 2)(12)常規(guī)算法、HGW算法及改進(jìn)的 HGW算法 每元素的比較次數(shù)如圖 2所示。由圖2可以看出， 隨著窗口的增大，改進(jìn)的 HGW算法的單個元素 的比較次數(shù)趨向于 3，比較次數(shù)少于另外兩種算 法。窗口越大，該算法的優(yōu)勢越明顯。圖2幾種算法平均計(jì)算次數(shù)的比較Fig.2 Average number of compari

15、sons of differentalgorithms3.2特征點(diǎn)方向確定由于傳統(tǒng)的Harris特征點(diǎn)檢測方法提取的特 征點(diǎn)不帶有方向信息，因此對于圖像的旋轉(zhuǎn)容易 產(chǎn)生誤匹配。采用SIFT算法的思想，利用特征點(diǎn)鄰域像素的梯度方向分布特征為每個特征點(diǎn)指 定方向。對L層上的特征點(diǎn)鄰域內(nèi)的坐標(biāo) (x,y)處 的方向計(jì)算如下：V x, y =actanL x,y 1 -L x,y-1L x 1,y -L x-1,y(13)若用直方圖統(tǒng)計(jì)鄰域像素加權(quán)梯度方向的值，則 其峰值即為該特征點(diǎn)的方向。3.3特征點(diǎn)描述符及特征點(diǎn)匹配結(jié)合MOPS算法，用特征點(diǎn)周圍的8X 8大小的像素的標(biāo)準(zhǔn)化灰度值來對特征點(diǎn)進(jìn)行描述

16、。 再進(jìn)行Haar小波變換，即形成 64維的特征描述 向量。特征點(diǎn)描述符形成后，采用次近鄰算法 (2-NN)8對不同圖像間提取的特征點(diǎn)進(jìn)行匹配，具體步驟可參考 MOPS算法中的匹配過程。4實(shí)驗(yàn)結(jié)果及不同算法性能比較為對比不同算法的特征點(diǎn)提取、匹配效果， 對本文算法、SIFT算法及Harris算法進(jìn)行了對比 實(shí)驗(yàn)。運(yùn)行環(huán)境為 PD820(2.8GHz)，編程環(huán)境為 V結(jié)合Opencv,采集圖像的分辨率為640 x480。圖中圓的半徑大小代表特征點(diǎn)所在的尺度， 圓圈內(nèi)部短線表示特征點(diǎn)的方向。從特征點(diǎn)提取 的結(jié)果(圖3)看，Harris算法提取的特征點(diǎn)更集 中在邊緣和角點(diǎn)處，而用本文提出的快速M(fèi)OP

17、S算法提取的特征點(diǎn)分布比SIFT和Harris的特征點(diǎn)分布更為均勻。由于快速M(fèi)OPS算法是在運(yùn)算 速度上對MOPS算法的改進(jìn)，而提取特征點(diǎn)的結(jié) 果是一致的，在此不再分開討論。(a)快速M(fèi)OPS算法提取結(jié)果(b) SIFT算法提取結(jié)果(c)Harris算法提取結(jié)果圖3 快速M(fèi)OPS, SIFT, Harris提取特征點(diǎn)分布圖Fig.3 Features extracted by fast MOPS,SIFT and Harris圖4 利用快速M(fèi)OPS進(jìn)行匹配的結(jié)果Fig.4 Features matching using fast MOPS表1幾種算法的比較Tab. 1 Compare of t

18、hese algorithms算法平均運(yùn)行時(shí)間(s)正確匹配的特征點(diǎn)個數(shù)錯誤匹配的特征點(diǎn)個數(shù)SIFT6.6223317MOPS1.7119610快速M(fèi)OPS1.3619610Harris0.92s211116通過表1的比較可以看7出，Harris算法運(yùn) 行速度最快，但該算法對于圖像的旋轉(zhuǎn)、縮放的 穩(wěn)定性不高，誤匹配率較高，不適用于旋轉(zhuǎn)和縮放變化較大的圖像間的匹配。SIFT算法用128維描述符對特征點(diǎn)進(jìn)行描述，穩(wěn)定性更好，但運(yùn)算 最慢，不利于實(shí)時(shí)計(jì)算。而MOPS算法是兩種算 法的折中，利用快速M(fèi)OPS算法可以進(jìn)一步提高 MOPS算法的運(yùn)行速度，基本上可以滿足實(shí)時(shí)處 理的要求。圖4是利用快速M(fèi)OP

19、S算法對兩幅圖像進(jìn)行 特征點(diǎn)匹配的結(jié)果。從圖上可以看出，雖然兩幅 圖像內(nèi)的物體存在縮放與旋轉(zhuǎn)變化，但利用快速 MOPS算法依然可以使得正確匹配的特征點(diǎn)達(dá)到 90%左右。通過多次實(shí)驗(yàn)測試，對于旋轉(zhuǎn)縮放情 況不是很大的情況，利用快速M(fèi)OPS算法是穩(wěn)定 可靠的，大多數(shù)情況都可以使得正確匹配的特征 點(diǎn)的比率大于50%，這樣就可以通過 RANSAC(random sample consensus) 9等算法去除 誤匹配的特征點(diǎn)。同時(shí)，由于采用該算法的特征 點(diǎn)分布比較均勻，對于特征跟蹤來說，就減小了 由于運(yùn)動物體某一部分受遮擋而不能連續(xù)跟蹤所 造成的影響。由于對每層金字塔上的特征點(diǎn)提取， 采用的是Harr

20、is角點(diǎn)算法，對于大角度的旋轉(zhuǎn)情 況，其準(zhǔn)確匹配的特征點(diǎn)個數(shù)要少于SIFT。因此，可以根據(jù)相機(jī)、物體運(yùn)動的不同性質(zhì)和特征跟蹤 對穩(wěn)定性和實(shí)時(shí)性的要求，來選擇不同的特征匹 配算法。同時(shí)，可以根據(jù)不同的需要，通過變化 式(6)改變半徑大小來控制特征點(diǎn)提取的個數(shù)及 分散程度，以進(jìn)一步提高運(yùn)算速度。5結(jié)論本文提出了一種利用局部極值的快速求法來 提高特征點(diǎn)提取速度的算法。通過比較實(shí)驗(yàn)分析 了幾種特征點(diǎn)提取算法的優(yōu)缺點(diǎn)，驗(yàn)證了該算法 的有效性。今后的研究主要集中在以下幾個方面： (1)該算法運(yùn)行時(shí)所占內(nèi)存的要大于傳統(tǒng)算法，進(jìn)一步提高算法的快速性、減少內(nèi)存消耗是下一步 研究的重點(diǎn)。同時(shí)也需研究窗口半徑對匹配

21、效果 的影響，通過選取合適的窗口半徑，以使其適應(yīng) 于多種圖像間平移、旋轉(zhuǎn)及縮放變換。將該算法靈活運(yùn)用到 SIFT，SURF等多種特征 點(diǎn)局部極值的求取過程，以拓展該算法的應(yīng)用范 圍。考慮將隨機(jī)采樣策略應(yīng)用到局部極值的求取 問題中，雖然不能保證全部局部極值的求取，但 可進(jìn)一步提高該算法的快速性。參考文獻(xiàn)(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(