基于實時局部特征描述的自然路標提取與匹配

劉天衡+石朝俠+王一璞

摘 要： 針對戶外場景路標匹配中所需的局部特征抽取和匹配技術(shù)進行研究，提出了基于曲率的特征抽取和二進制特征描述相結(jié)合的方法。算法利用基于曲率算法的特征分布較合理的特性，克服了傳統(tǒng)特征分布不均的問題，且通過二進制描述算法解決了特征匹配的實時性問題，最后通過實驗對比了不同算法的有效性和實時性。結(jié)果表明，該算法能夠在保證實時性的同時提取出有效的均勻特征點。

關(guān)鍵詞： 特征匹配； 特征抽取； 路標匹配； 曲率算法

中圖分類號： TN911.73?34 文獻標識碼： A 文章編號： 1004?373X（2015）15?0008?04

Extraction and matching of natural road sign

based on real?time local features description

LIU Tianheng1， SHI Chaoxia1， WANG Yipu2

（1. School of Computer Science and Engineering， Nanjing University of Science and Technology， Nanjing 210094， China；

2. School of Computer Science and Technology， Harbin University of Science and Technology， Harbin 150080， China）

Abstract： Local features extraction and matching techniques required in outdoor scene road sign matching are studied. The method in combination with curvature based feature extraction and binary feature description is proposed. The algorithm takes the advantage of reasonable features distribution in curvature algorithm to overcome the problems of traditional features uneven distribution. The real?time problem of feature matching is resolved by binary description algorithm. The validity and real?time performance of different algorithms are compared by experiments. The experimental results show that the proposed algorithm can extract even features effectively while guaranteeing real?time performance.

Keywords： feature matching； feature extraction； road sign matching； curvature algorithm

0 引 言

定位是移動機器人最基本的功能之一，最早的定位研究成果主要是通過機器人的內(nèi)部傳感器，如碼表、慣性儀等設(shè)施實現(xiàn)定位，但由于打滑、地面崎嶇不平等原因造成的誤差累積常常會導(dǎo)致定位結(jié)果不精確，不宜長時間單獨導(dǎo)航。如果通過GPS定位或者利用我國的北斗導(dǎo)航系統(tǒng)定位，在有遮擋區(qū)域等信號不好的地方定位系統(tǒng)將失效，因此，人們開始逐漸采用外部傳感器來輔助定位，比如紅外和視覺傳感器[1?2]。

視覺傳感器因其豐富的環(huán)境信息如視覺、紋理、形狀等備受關(guān)注，而且由計算機視覺理論可知，通過視覺系統(tǒng)便可準確識別出目標并判斷出自身位姿。目前許多現(xiàn)存的方法中，大多采用人工設(shè)置路標，然后在機器人移動過程中對事先設(shè)定的人工路標進行匹配實現(xiàn)定位。但是隨著研究工作的不斷進展，人們逐漸將移動機器人的應(yīng)用場景從室內(nèi)轉(zhuǎn)到了室外，此時許多特定情況下，人工設(shè)置路標是不現(xiàn)實的，所以自然路標就成為在戶外條件下的首選方法。所謂自然特征就是指環(huán)境中已有的、非人工設(shè)置的、能夠用以標識不同環(huán)境場景的特征對象。相對于室內(nèi)大多結(jié)構(gòu)化的環(huán)境，室外復(fù)雜的非結(jié)構(gòu)化環(huán)境對移動機器人的定位和導(dǎo)航帶來了相當大的挑戰(zhàn)，同時，相對于室內(nèi)，室外不斷變化的光照條件和氣候環(huán)境也是研究中的一大挑戰(zhàn)。

基于視覺的自然路標需要提取其不變點，之后利用特征點匹配的方法判斷和識別路標，從而實現(xiàn)移動機器人的定位。與GPS定位方法不同，基于特征的定位方法首先將原始的采樣數(shù)據(jù)轉(zhuǎn)換為相應(yīng)的局部特征，在只需少量存儲空間的情況下保存豐富而精確的環(huán)境信息。這類方法通常具有較好的魯棒性，能滿足相對復(fù)雜的應(yīng)用，但在道路兩旁有植被分布時，大多數(shù)特征點都集中于道路兩旁的樹木，而且提取的特征較為相似，這對后期的特征匹配和機器人定位帶來了較大的影響。因此，如何剔除植被對自然路標提取的影響，將特征點盡可能均勻地分布到場景的建筑物中去，成為自然路標提取中的一大難題 [3]。

目前已有的局部特征匹配算法主要有Harris，SIFT，SURF，ORB等[4?5]，SIFT（Scale?invariant Feature Transform）算法由David Lowe在1999年提出，2004年完善總結(jié)。因其具有良好的尺度旋轉(zhuǎn)不變性而受到廣泛關(guān)注，但由于其運算速度較慢，影響了其在實時應(yīng)用中的應(yīng)用。Herbert Bay針對SIFT算法提出了改進的SURF算法[6?7]，在速度上提升了一個量級，但是在一些實時應(yīng)用中此速度依舊不夠。直到2011年Willowgarage提出了ORB算法[8?9]，可以滿足大多數(shù)實時性應(yīng)用。但是，ORB算法提取的特征點，在戶外應(yīng)用中，特征點分布都不夠均勻，故本文采用基于曲率的算法來實現(xiàn)較均勻的特征點提取[10]。

1 基于曲率的特征點抽取

基于曲率的特征點抽取方法計算簡單，提取出來的特征點具有旋轉(zhuǎn)不變性，對噪聲和亮度變化也都具有良好的魯棒性，且特征點分布均勻，更重要的是可以提取定量的特征點。該方法主要通過灰度變化來判斷是否是角點，當圖像中某一點沿任意方向的微小偏移都會產(chǎn)生灰度的大量變化，則該點被認為是角點。設(shè)[Ix]為水平方向灰度的變化，[Iy]為豎直方向的灰度變化，那么角點就是[Ix，][Iy]變化都很大的點，而邊緣則是[Ix，][Iy]中只有一個變化較大的點。設(shè)[w（x，y）]是以[（x，y）]為中心的一個滑塊，當其在任意方向滑動[[u，v]]時，產(chǎn)生灰度變化[E（u，v）]的計算方法如下：

[E（u，v）=x，yw（x，y）I（x+u，y+v）-I（x，y）2] （1）

而后根據(jù)泰勒級數(shù)計算出一階到[n]階的偏導(dǎo)數(shù)，最終可以得到一個矩陣公式：

[M=w（x，y）I2xIxIyIxIyI2y] （2）

再根據(jù)矩陣的特征值[λ1，λ2]判斷是否為角點，但實際操作中一般計算出角點響應(yīng)值如下：

[R=det M-k（trace M）2] （3）

式中：[k]為系數(shù)值，一般取0.04～0.06，通過[R]來判斷是否為角點，[R]若為對應(yīng)的鄰域的極大值就是角點所在位置。

鄰域設(shè)置為[3×3]和[8×8]時基于曲率的特征點提取的效果圖，如圖1所示。

圖1 基于曲率的特征抽取

原本的基于曲率的特征點提取算法，判斷一個點是否為特征點的依據(jù)是判斷計算出的[R]是否在鄰域內(nèi)最大，若最大則為特征點。而這里因為一個點的不確定性主要取決于較小的那個特征值，若采用行列式的特征值來判斷是否為特征點的話，只需較小的一個特征值數(shù)值大于預(yù)先設(shè)置的閾值，則該點便可以被認為是一個強角點[11]，即此時：

[R=λ1， λ1<λ2λ2， λ2<λ1] （4）

若[R]大于預(yù)先給定閾值即為強角點，由于該算法對發(fā)現(xiàn)特征值的要求較低，可以抽取到一些不是特別明顯的特征點，若實際應(yīng)用中需要特征點均勻分布時，適當提高該算法的運算鄰域，即可獲得相對其他算法而言分布更加均勻的角點分布圖，效果如圖2所示。

圖2 改進的曲率特征提取效果圖

圖2（a）和圖2（b）分別為極大值抑制區(qū)域為[3×3]和[8×8]的情況，可以發(fā)現(xiàn)當極大值抑制區(qū)擴大為[8×8]時，特征分布已相當均勻。

2 具有旋轉(zhuǎn)不變性的二進制特征描述

二進制字符串描述符，相對其他算法減少了描述符的維度，從而減少了描述和匹配的時間。該算法首先對圖像進行高斯濾波以降低噪聲的影響，后在圖像中選擇一個局部塊[p，]大小為[S×S]像素，定義一個[τ]測試如下：

[τ（p；u，v）=1， p（u）

式中：[u，][v]是形如[（x，y）]的二維坐標對；[p（u），p（v）]是所在點的亮度。

由若干個[τ]測試的結(jié)果組成字符串：

[f（p）=1≤i≤n2i-1τ（p；x，y）] （6）

式中：[n]可以取128，256，512等，這里取512，其需要[5128=64 ]B的存儲空間。如何有效地選取特征點對接下來的運用影響很大，經(jīng)實驗證明，采用服從[125S2]的高斯分布，特征向量具有較好的分辨率，同時采用Hamming距離代替?zhèn)鹘y(tǒng)的歐式距離判斷是否匹配，匹配時只需按位進行異或操作，大大縮短了特征匹配的時間。

BRIEF運算簡單且所占內(nèi)存較小，比較適用于一些實時應(yīng)用，但該算法同樣也存在一些缺點：易受噪聲影響，未考慮特征方向，不具備旋轉(zhuǎn)不變性，不具備尺度不變性。

為了讓該算法具有旋轉(zhuǎn)不變性以減少移動機器人在抖動過程中畫面旋轉(zhuǎn)對匹配結(jié)果造成的影響，通過質(zhì)心算法計算出各關(guān)鍵點的方向，如下式所示：

[Mij=xyxiyjIx，y] （7）

得到特征點的方向為：

[cx=M10M00，cy=M01M00，θ=tan-1cycx] （8）

式中：[（x，y）]為檢測到興趣點的坐標，之后將獲得的[θ]以[2π30]的尺標將其量化。在位置[（xi，yi）]上對任意[n]個二進制特征集，定義一個[2×n]的矩陣：

[S=x1x2xny1y2yn] （9）

用之前得到的[θ]校正[S]得到[Sθ=SRθ，]其中：

[Rθ=cosθsinθ-sinθcosθ] （10）

根據(jù)得到的方向再提取描述子[g（p，θ）=f（p）（xiyi）∈Sθ]就具有旋轉(zhuǎn)不變性了。

3 實驗和結(jié)論

本實驗在Win7系統(tǒng)下，利用vs2010和opencv2.4.10實現(xiàn)了基于曲率算法的特征抽取與二進制特征描述方法。實驗硬件為AMD四核的A6?3420M APU 1.5 GHz，內(nèi)存4 GB，顯卡HD 7470M 1G。由于實現(xiàn)移動機器人定位所需的特征點對不多，故本文所有算法對每一幅圖像檢測到的特征點數(shù)設(shè)置上限為200，所使用圖片采用錄制視頻中相近幀截屏獲得，各算法實驗效果如圖3所示，實驗數(shù)據(jù)見表1。

圖3 特征匹配效果

表1 各算法實驗數(shù)據(jù)

[特征提取算法＼&正確匹配率 /%＼&匹配用時 /ms＼&快速角點檢測算法＼&86＼&68＼&SIFT＼&60＼&5 237＼&SURF＼&58＼&1 142＼&基于曲率的算法＼&75＼&152＼&改進基于曲率的均勻提?。?amp;77＼&143＼&]

從實驗結(jié)果來看，SIFT和SURF所獲得的特征點分布比較均勻，但是在速度上和其他算法相比，慢了很多，不適用于實時性應(yīng)用，速度最快的快速角點檢測算法檢測出的特征點分布較為集中，無法減少樹木等對特征匹配的影響。

基于曲率的算法在算法實時性和特征均勻分布特性方面得到了很好的權(quán)衡，改進的基于曲率的特征抽取方法，由于簡化了運算過程，在處理時間上更短；在正確匹配率方面，兩種方法相差不大，相對于原算法，本文算法分布更加均勻，減少了樹木等自然路標對特征匹配造成的影響。故本文提出的算法能滿足戶外條件下有效地提取特征點并進行匹配的要求，且具有較好的實時性和魯棒性。

注：本文通訊作者為石朝俠。

參考文獻

[1] 徐則中，莊燕濱.移動機器人定位方法對比研究[J].系統(tǒng)仿真學(xué)報，2009，21（7）：1891?1896.

[2] 張浩峰，趙春霞，王曉麗，等.面向室外自然環(huán)境的移動機器人視覺仿真系統(tǒng)[J].系統(tǒng)仿真學(xué)報，2006，18（3）：701?705.

[3] 王永明，王貴錦.圖像局部不變性特征與描述[M].北京：國防工業(yè)出版社，2010.

[4] LEUTENEGGER S， CHLI M， SIEGWART R Y. Brisk： binary robust invariant scalable keypoints [C]// Proceedings of 2011 IEEE International Conference on Computer Vision. [S.l.]： IEEE， 2011： 2548?2555.

[5] 廖婷婷.基于特征匹配的圖像檢索算法研究[D].廣州：華南理工大學(xué)，2012.

[6] BAY H， ESS A， TUYTELAARS T， et al. Surf： speeded up robust features [C]// Proceedings of 2006 IEEE International Conference on Computer Vision. [S.l.]： IEEE， 2006： 346?359.

[7] 張銳娟，張建奇，楊翠.基于SURF的圖像配準方法研究[J].紅外與激光工程，2009（1）：160?165.

[8] RUBLEE E， RABAUD V， KONOLIGE K， et al. ORB： an efficient alternative to SIFT or SURF [C]// Proceedings of 2011 IEEE International Conference on Computer Vision. [S.l.]： IEEE， 2011： 2564?2571.

[9] 許斌鋒.增強現(xiàn)實中ORB與KLT相結(jié)合的特征點跟蹤方法研究[D].南京：南京大學(xué)，2012.

[10] HARRIS C， STEPHENS M. A combined comer and edge detector [C]// Proceedings of 1988 the 4th IEEE Alvey Vision Conference. Manchester： IEEE， 1988： 147?151.

[11] SHI Jianbo， TOMASI C. Good features to track [C]// Procee?dings of 1994 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Champaign： IEEE， 1994： 593?600.