移動機器人視覺圖像特征提取與匹配算法

摘 要:針對移動機器人導航過程中視覺圖像處理速度慢以及特征點提取與匹配實時性和準確性差等特點，提出了一種基于SIFT特征提取算法與KD樹搜索匹配算法相結合的新方法，通過對候選特征點進行多次模糊處理，使其分布在高斯差分圖像的灰度輪廓線邊緣，利用SIFT特征提取算法找到滿足極限約束的極值點;通過KD樹最鄰近點搜索和匹配算法使處理后的特征點與原始圖像進行特征匹配，快速找出匹配正確的特征點。實驗證明，該方法對環境光照、視野角度頻繁變化的環境具有較強的魯棒性，能夠滿足移動機器人自主導航過程中對視頻圖像處理的實時性和準確性要求。

關鍵詞:比例尺度不變; 特征提取; 特征匹配; K維樹

中圖分類號:TP24文獻標志碼:A

文章編號:1001-3695(2009)09-3526-04

doi:10.3969/j.issn.1001-3695.2009.09.093

Robust image feature extracting and matching algorithm for mobile robots vision

YANG Jing-dong1，2， YANG Jing-hui3， HONG Bing-rong2

(1. School of Optical-Electrical Computer Engineering， University of Shanghai for Science Technology， Shanghai 200093， China; 2. College of Computer Science Technology， Harbin Institute of Technology， Harbin 150001， China; 3. School of Business Management， Shanghai Second Polytechnic University， Shanghai 201209， China)

Abstract:According to the real-time and accuracy requirement to process image during navigation for mobile robots， this paper proposed a new feature extracting algorithm， SIFT algorithm， which combined the searching and matching algorithm， KD tree. Firstly， fuzzed the feature images many times， so that distributed those extracted features around gray outline of Gaussian difference image. Then the global best points， which satisfied extreme constraints， were obtained based on SIFT algorithm. Finally， the exact matching features could be found by using matching algorithm based on KD tree quickly. It is validated that the algorithm is strongly robust to the environment change from the experiments， such as illumination and angle of view， and is able to meet the requirements of real-time and veracity in the process of navigation for mobile robots.

Key words:scale invariant feature transform(SIFT); feature extracting; feature matching; KD tree

移動機器人視覺的研究主要集中在目標識別、定位以及跟蹤等方面。在上述研究內容中，視覺圖像的特征提取和匹配是它們的前提與基礎，特征點匹配結果的優劣直接影響著后續的處理過程。在移動機器人自主導航過程中，圖像特征點匹配算法不僅要能夠適應機器人工作環境、光照、視野角度等因素帶來的圖像采集質量的變化，還應該滿足視覺信號處理實時性的基本要求，實現視覺圖像特征點的比例尺度不變的自動提取。最早提出特征點提取方法的是Moravec[1]，后來Harris等人[2]進行了改進，提出了Harris角點檢測方法，但是此方法只能對一幅圖像按照固定的比例提取特征點，當兩幅圖比例發生較大變化時就無法進行匹配。Crowley等人[3]最早開始對比例不變特征進行研究，后來Lowe等人[4，5]提出了一種圖像比例不變特征提取方法SIFT，該方法通過對圖像進行不同程度的模糊與縮放，產生具有不同比例的圖像，然后從這些圖像中分別提取特征。這些提取的特征對圖像比例尺度、視野角度以及光照強度等具有較好的不變性，因此常用于移動機器人自主導航過程中提取圖像特征。

提取圖像特征后需要與地圖中路標圖像特征進行對比來確定移動機器人當前位姿，這就是圖像特征匹配的過程。圖像特征匹配算法中較為傳統的方法是鏈表式匹配方法，這種方法費時且運算復雜性較高。因此本文采用一種最鄰近點匹配的方法，通過對比例空間中提取極值點構建一個樹型結構，然后用這個樹型結構完成不同比例圖像之間的匹配。這種方法可以有效地降低計算復雜度。

1 SIFT特征提取算法

采用SIFT方法提取的特征稱為SIFT特征。SIFT 特征是一種點特征，它是連續三幅高斯差分圖像中處于圖像邊緣附近的極值點。高斯差分圖像中的極值點是灰度值比它周圍像素點都大或者都小的像素點，即在圖像進行高斯模糊后變化最劇烈的像素點，因此這些從極值點中選取出來的SFIT特征點具有很好的穩定性。處理過程如圖1所示。

SIFT方法通過在對圖像作多次比例變換，獲得所有圖像集合中比例空間中的極值點，并用這些極值點構建一個樹型結構，然后用這個樹型結構完成不同比例圖像之間的匹配，從這些圖像中分別提取特征。該算法可分為比例尺度空間檢測、特征點定位、特征向量方向確定及特征描述器表述等過程[6]。特征描述器分布如圖2所示。

特征提取過程如下所示:

輸入:具有比例空間極值點的原始圖像

輸出:提取具有比例尺度不變特征的SIFT特征點

a)定義比例空間L和高斯差分函數D:L(x，y，δ)=G(x，y，δ)*I(x，y)。其中*表示卷積運算，且滿足

G(x，y，δ)=1/(2πδ2)e-(x2+y2)/2δ2

D(x，y，δ)=(G(x，y，kδ)-G(x，y，δ))*I(x，y)=L(x，y，kδ)-L(x，y，δ)

/*特征點提取*/

b)用拉普拉斯高斯算子表示高斯差分算子，依次產生高斯差分圖像，提取D0G(Kδ)中與周圍D0G(δ)和D0G(2δ)中26個候選特征點相比灰度值都大或都小的候選特征點作為特征點:

G(x，y，kδ)-G(x，y，δ)≈(k-1)δ22G|k∈{1，2，…，N}

/*特征點定位*/

c)對比例空間函數D(X)利用Taylor二項式展開:D(X)=D+(DT/X)X+1/2XT(2D/X2)X。 其中X=(x，y，б)T是對采樣點的偏移量對D(X)求偏導并令其為零得到極值點相對于采樣點的偏移量:x′=2D-1D/x2x

d)篩選特征點:IF x′>0.5，重新對別的像素點進行插值計算:D(x′)D+1/2(DT/X)X。滿足D(x′)<0.03的所有極值點都將被刪除

/*確定特征點的梯度和方向*/

e)對高斯模糊圖像L(x，y)周圍像素點灰度差值計算:

m(x，y)=(L(x+1，y)-L(x-1，y))2+(L(x，y+1)-L(x，y-1))2

θ(x，y)=tan-1(L(x+1，y)-L(x-1，y))/(L(x，y+1)-L(x，y-1))

/*描述特征點描述器的特性*/

f)特征點描述器的特征:

(a)使用高斯權值函數為每個采樣點的梯度大小賦予權值。

(b)分配到某個等級的采樣點梯度值乘以1-d個權值:m(x，y)*(1-d)。其中d為采樣點到等級中心的等級跨度距離。

(c)特征描述器的空間向量表示。采用4×4維直方圖，每個直方圖8個等級，每個特征點需要用4×4×8=128個元素的特征向量來描述。

(d)歸一化特征向量以減少光強的變化。

(e)每個像素值、梯度值歸一化以減小對比度的變化;每個像素值都加上一個常數以減小亮度的變化;設定單位特征向量的閾值φ≤0.2，歸一化其余的梯度值以降低大梯度的影響。

2 基于K維樹的特征匹配

SIFT特征匹配是對特征描述器進行比較，如果兩個特征描述器的差別小于設定數值，那么就稱這兩個特征相互匹配。通過特征匹配可以找到特征與特征之間的對應關系。特征點匹配的形式描述如下:

設一個K維空間的定義域和值域分別為R和D，E為K維空間R×D中采樣點的集合，d為目標點向量。其中di為向量d的第I維元素。一個簡單費時的算法是，依次計算E中所有點與目標點d之間的距離，從而找到與d最鄰近的點即鏈表式搜索法。這種算法的時間復雜度為O(N)，N為E中點的數目。最常用、最方便的方法是最鄰近法。最鄰近點的形式化描述如下:設d的最鄰近點d′，則滿足

d″∈E，|dd′|≤|dd″|，|dd′|=∑ki=1(di-d′)2

這種基于K維樹(KD)[7，8]的最鄰近點搜索算法可以在地圖創建中處理大量的特征點匹配運算，具有較高的匹配效率，將時間復雜度降低到O(log2N)。

2.1 K維樹的建立

K維樹是一種存儲K維空間點集的數據結構，它是一棵二元樹，每個節點的描述如表1所示。其中:d表示該節點存儲的空間點向量;s值為I，劃分超平面是指經過點d且垂直于第I維方向面;left代表所有位于劃分平面左子空間的點，right代表所有位于劃分平面右子空間的點。當且僅當一個點的第I維元素小于(大于)d的第I維元素時，這個點才位于劃分平面左(右)子空間。如果一個節點沒有子節點，那么就不需要劃分超平面。

為了說明K維樹劃分的過程，這里舉例說明。圖3 (a)表示了一棵二維空間(k=2)的K維樹，它由(2，5)，(3，8)，(6，3)，(8，9)四個點向量構成。根節點(2，5)在第2維上將空間劃分為兩個子空間，點(3，8)位于右子空間，因為其第2維元素8大于點(2，5)的第2維元素5。同理，點(6，3)位于左子空間，點(8，9)位于右子空間。再看點(3，8)，根據其第1維繼續劃分兩個子空間，點(8，9)位于點(3，8)的右子空間，因為其第1維元素8大于點(3，8)第1維元素3。圖3 (b)表示這棵K維樹對2維空間的劃分結果。

2.2 基于K維樹的最鄰近點搜索

K維樹建立起來后借助于一個簡單例子描述基于K維樹的最鄰近點搜索算法。如圖3(c)所示，目標點用X標記，其所在區域的葉節點為點4。從根節點進行初步搜索將找到點4，作為當前與目標點最鄰近的點。本例中點4不是最鄰近點。距離目標點更近的點一定位于以X為圓心、以X與點4之間為半徑的圓內。于是回溯到當前節點(點4)的父節點(點2)，然后判斷父節點的另外一棵子樹中是否有距目標點更鄰近點的可能點。這在本例中是不可能的，因為圖中的圓沒有與父節點的另外一個子空間(圖中陰影區域)相交，在這種情況下，直接回溯到K維樹的更上一層，否則需要遞歸搜索父節點的另外一個子空間。搜索過程回溯到點1，這時需要搜索點1的另外一個子空間(圖中上半部分)，因為圖中的圓與該子空間有相交。進而參考點3，其右子空間(圖中右上角區域)與圓相交，故搜索點3的右子空間，最終找到了該子空間的葉節點(點5)。由于沒有其他區域與圓相交，點5就是與目標點最鄰近的點。

后面給出了基于K維樹的最鄰近點搜索算法描述，該算法采用深度優先啟發式搜索策略。其中定義了一種數據結構，叫做超矩形(hyper-rectangle)，用來描述K維空間采樣點集合所占據的空間范圍。判斷一個超矩形hr是否與以目標點Ptarget為中心且半徑為r超球體相交，首先需要找到hr中最接近target的點P。P由下式計算:

Pi=hr_miniif targeti≤hr_mini

targetiif hr_mini

hr_maxiif targeti≥hr_maxi

其中:Pt與Ptarget分別表示點P與target在第I維上的取值;hr_mini和hr_maxi分別表示超矩形在第I維上的最小值和最大值。當|P-Ptarget|

輸入:CCD當前K維樹的根節點kd，目標點target，K維樹所占用的超矩形hr，最鄰近點與目標點之間的最大距離max_dist;

輸出:目標點的最鄰近點nearest， 目標點與最鄰近點之間的距離distance。

a)令s=kd.s， pivot=kd.d;

b)將hr劃分為兩個子超矩形，分別記為lhr與rhr，劃分面經過pivot且垂直于第s維的方向;

c)target_in_left = targets≤pivots;

d)如果target_in_left為真，那么

nearer_kd=kd.left， nearer_hr=lhr

further_kd=kd.right， further_hr=rhr

e)如果target_in_left為假，那么

nearer_kd=kd.right，nearer_hr=rhr

further_kd=kd.left，further_hr=lhr

f)遞歸調用:

nearestNeighbor(nearer_kd，target，nearer_hr，max_dist)

g)max_dist=min(max_dist，distance)

h)如果further_hr某部分與target之間小于max_dist，那么

i)如果pivot到target的距離小于dist，那么

nearest=pivot， distance = d(Ppivot -Ptarget)2， max_dist=dist

j)遞歸調用:

nearestNeighbor(further_kd，target，further_hr，max_dist)

返回值存放在temp_nearest和temp_dist

k)如果temp_dist

nearest=temp_nearest，distance = temp_dist

2.3 基于K維樹的SIFT特征匹配算法

SIFT特征匹配是對特征點描述器(128維特征向量)進行匹配。SIFT特征點之間距離用其之間的歐幾里德距離來表示。本文采用上述基于K維樹最鄰近法實現SIFT特征匹配。首先，將已經觀測到的所有SIFT特征點建立一棵K維樹;然后，對當前觀測到的每個特征點kp用基于K維樹的最鄰近點搜索算法找到最臨近點kp1和次鄰近點kp2。如果|kpkp1|越小而|kpkp2|越大，那么kp和kp1匹配質量越好，搜索條件滿足下式:

|kpkp1|/|kpkp2|<λ

則認為kp與kp1匹配，其中λ為常量，λ∈(0，1)。這樣就排除了一些誤差較大的特征點對。為此，對表3中的算法進行了修改，使其輸出為最鄰近點kp1和次鄰近點kp2，并將修改后的算法命名為nearestNeighbor2。基于K維樹的SIFT特征匹配算法描述如下:

輸入:根據已經觀測到的信息創建的KD_Tree kd， 當前的觀測特征點序列kp_dist;

輸出:特征點的匹配對序列match_list。

a)設定max_dist，將match_list置空;

b)計算kd的超矩形;

c)對于kp_list中的每一個特征點kp:

調用函數nearestNeighbor2(kd，kp，hr，max_dist)

返回最臨近點kp1和次臨近點kp2;

d)|kpkp1|/|kpkp2|<λ，將匹配對(kp1， kp2)加入到match_list中。

3 基于SIFT特征提取與匹配實驗分析

本文利用移動機器人Pioneer3-DX平臺在室內環境下進行了多次SIFT特征提取與匹配實驗。視覺系統包括一個圖像采集卡、嵌入式計算機。單目攝像頭Logitech QuickCam Pro 3000/4000 Web cameras，像素范圍320×240，開發軟件Visual Studio.NET 2003。

1)對圖像比例尺度變化匹配的魯棒性 SIFT主要特點是具有比例不變特性。此方法是通過獲得特征在比例空間中比例的變化，修正特征描述器，保持比例特征描述器的一致性。理論上比例尺度與距離物體的距離成反比關系。為了驗證SIFT比例不變性進行如下實驗:如圖4所示，圖4(a)(b)分別是距離目標5 m處和4 m處拍攝的圖像，匹配特征點數為217個;(c)(d)分別是距離目標8 m處和6.5 m處拍攝的圖像，匹配特征點數為112個。

圖5(a)顯示的是SIFT特征比例變化的對比圖，通過描點、擬合的辦法測得遠近特征點的比值為1.2，理論比值為5.0/4.0=1.25，比值不能完全吻合，這是由于同一圖像的特征點可能是從不同模糊程度高斯模糊圖像中提取的，即使在同一高斯模糊圖像內的兩個特征點都會有不同的比例，這種比例尺度變化中的微小誤差是合理的，但基本可以滿足比例尺度與距離成反比的關系。

圖5(b)數據曲線統計的是隨著攝像機與物體距離的變化，基于K維樹的SIFT特征匹配算法(SIFT-KD)和傳統SIFT匹配算法(SIFT)特征點的正確匹配率(正確匹配的特征點數/特征點總數)變化情況。由于每一時刻的光強頻率不同，開始時的正確匹配率并不是100%，但是SIFT-KD算法的正確匹配率要遠高于SIFT算法的匹配率，分別為75%和54%。隨著攝像頭向前方移動，進入視野的特征點數降低，這兩種算法的特征點正確匹配率也都逐漸降低，當向前移動大約1.8 m時傳統算法的正確匹配率為0，而SIFT-KD算法仍然可以匹配數據庫中的特征圖像。整個過程中兩種算法正確匹配率均值分別為17.49%和10.78%。因此SIFT-KD算法的正確匹配率要較傳統匹配算法有較大的提高。

2)對仿射角度變化匹配的魯棒性 如圖6(a)(b)所示，圖中的兩幅圖像分別是利用SIFT-KD算法在原始位置以及垂直偏轉20°的圖像相互匹配的情況。其中匹配特征點總數為244個，正確匹配特征點為201個，正確匹配率為82.38%。圖6(d)~(f)分別為圖6 (c)經過水平旋轉一定角度后與自身特征匹配的情況。正確匹配率分別為85.34%、78.95%、82.12%。從圖6中各種情況中可以清楚看到，對不同的垂直或水平旋轉以及仿射角度變化，SIFT-KD算法均能正確匹配。

圖7(a)數據曲線圖顯示了利用傳統SIFT特征匹配算法與SIFT-KD算法對具有不同仿射角度視覺圖像的匹配情況。統計數據中可以看到，當仿射角為0時并非能夠完全匹配數據庫中的圖像。這是由于每一時刻光線頻率的變化不同，地圖庫中的原始圖像與實時生成的圖像會具有不同的特征點分布。因此在無仿射角時，正確匹配率也并非100%。當仿射角度逐漸增加時，進入視野的原始圖像中的特征點數逐漸減少，匹配率開始明顯下降，但是傳統SIFT算法匹配率還是遠低于SIFT-KD算法，當仿射角增加到60°時，傳統匹配算法已經不能正確匹配原始圖像，而SIFT-KD算法仍能達到20%的正確匹配率。整個過程SIFT-KD算法正確匹配率均值為33.73%，而傳統算法為22.88%。由此可見，SIFT-KD算法提高了特征點正確匹配率，視野角度由原來的60°變成75°，對圖像仿射變化的魯棒性增強了，更加適合于視野角度經常變化的機器人導航環境。

3)對部分圖像被遮擋匹配的魯棒性 表2給出了傳統SIFT匹配算法和SIFT-KD算法特征點正確匹配率對比數據。表2統計了兩種算法在夜間室內日光燈照情況下部分圖像遮擋時正確匹配率的對比情況。從表中可以看到，對于部分圖像被物體遮擋時傳統SIFT匹配算法識別率很低，當被遮擋部分超過65%時，幾乎無法識別物體;而對于SIFT-KD，可以在遮擋范圍為25%~85%的圖像匹配，其部分圖像遮擋情況下識別率遠遠高于傳統算法。因此SIFT-KD算法可以將從不同角度實時拍攝的圖像與地圖庫中圖像進行特征匹配，更適合于移動機器人導航過程中環境變化的隨機性要求。

4)對外界光線變化匹配的魯棒性 表3給出了在不同光照強度下兩種算法對同一幅原始圖像的特征點匹配率對比情況。表中分別給出了在黃昏室內(10 LUX)、正常室內(60 LUX)、室內日光燈(100 LUX)、室內強日光(300 LUX)、室內陽光(600 LUX)、室內陽光和日光(800 LUX)，以及室內正午陽光加日光(1 000 LUX)光強下，特征點正確匹配情況。

可以看出，SIFT-KD算法正確匹配的光強變化范圍很廣，并且當光線變化時正確匹配率變化較為平穩，在一般光照情況下正確匹配率均能達到75%以上，較為適合移動機器人在未知室內環境下的自由導航過程。而傳統算法的匹配率較低，正確匹配的光線強度范圍較小，當外界光線發生變化時，匹配成功率變化波動較大，呈跳躍式波動趨勢，通常光照情況下的正確匹配率只有40%左右，不適合移動機器人在大范圍光照變化下的自由導航過程。由此可見，針對移動機器人在環境光強劇烈變化的環境下，SIFT-KD算法的正確匹配率比傳統算法明顯提高，對光照變化的魯棒性增強，更適合于環境光線變化的機器人導航過程。

5)兩種算法特征點分布及匹配時間對比 圖8顯示的是傳統SIFT和SIFT-KD匹配算法圖像處理的對比結果。從圖8(b)中可以清楚地看到，傳統SIFT匹配的特征點分布較為均勻(圓圈大小代表比例尺度的變化)，對圖像灰度變化不敏感，與原始的圖8(a)匹配特征點數213對，正確匹配對數93對，正確匹配率只是43%，這樣提取的特征點受光照強度、野角度影響很大，當機器人視角稍有變化，圖像中梯度變化較小部分提取的特征點就會消失，很難保證圖像之間的匹配;而圖8(c)中采用 SIFT-KD算法對原始圖像匹配的特征點多數集中在灰度變化較為明顯的邊緣輪廓部位，邊界容易形成連線和封閉的區域，構成了不同層次和強度的邊緣梯度，并且正確匹配對數較多，201對特征點中正確匹配169對，正確匹配率接近84%，因此能較好地顯示出灰度邊緣輪廓，對光線和視野角度變化有很好的魯棒性。

從圖7(b)兩種算法匹配時間對比圖中可以清楚地看到，相同特征點數量情況下，SIFT-KD匹配算法的匹配時間要遠少于傳統SIFT匹配算法，匹配時間均值分別為85.062 5和120.437 5 ms。這是因為SIFT-KD算法雖然每一次迭代都需要追溯判斷當前節點父節點的匹配情況，但是從父節點搜索下一個子節點時不用遍歷搜索整個節點樹，縮短了整體匹配時間，提高了視頻圖像的實時處理速度，加之本實驗中采用圖像視頻采集卡，雙向傳輸速度可達到120 fps，提高了圖像數據的傳輸速度。因此，基于KD樹的SIFT特征提取與匹配算法能滿足室內環境下移動機器人自主導航的實時性要求。

4 結束語

本文對移動機器人自主導航過程中的視頻圖像提取SIFT特征點，該方法提取的特征具有對比例變化、光照強度、視野角度等因素變化具有較強的魯棒性。但考慮到匹配準確率的要求，只有匹配的特征點對多于8對時，才認為該圖像與地圖庫中的特征圖像完全匹配，否則在地圖庫中繼續尋找與該圖像匹配的地圖路標。本文對提取的特征點采用一種深度啟發性搜索匹配算法——最鄰近點搜索方法，該方法可以有效地減少特征搜索時間，降低運算復雜度，提高搜索效率。通過以上實驗也可以看出，該方法能夠滿足室內環境下移動機器人大范圍、長距離自主導航過程中的實時視頻圖像處理過程，提高導航的實時性。

參考文獻:

[1]MORAVEC H. Rover visual obstacle avoidance[C]// Proc of the 7th International Joint Conference on Artificial Intelligence.Pittsburgh: Carnegie Mellon University， 1981:785-790.

[2]HARRIS C， STEPHENS M. A combined corner and edge detector[C]// Proc of the 4th Alvey Vision Conference. Manchester， UK:[s.n]，1988:147-151.

[3]CROWLEY J L， PARKER A C. A representation for shape based on peaks and ridges in the difference of low-pass transform[J]. IEEE Trans on Pattern Analysis and Machine Intelligence， 1984，6(2):156-170.

[4]LOWE D G. Districtive image features from scale-invariant keypoints[J]. International Journal of Computer Vision， 2004， 60(2):91-110.

[5]MUTCH J， LOWE D G. Object class recognition and localization using sparse features with limited receptive fields[J]. International Journal of Computer Vision， 2008， 80(1): 45-57.

[6]LOWE D G. Object recognition from local scale-invariant features[C]// Proc of International Conference on Computer Vision.Wa-shington DC:IEEE Computer Society，1999:1150-1157.

[7]ARYA S， MOUNT D M， NETANYAHU N S， et al. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions[C]// Proc of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms. 1994:573-582.

[8]TAO Yu-fei， ZHANG Jun， PAPADIAS D， et al. An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces[J].IEEE Trans on Knowledge and Data Engineering， 2004， 10(16):1169-1184.