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

2、要求。 關鍵詞:比例尺度不變; 特征提取; 特征匹配; ?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 & Co

3、mputer 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) Ab

4、stract: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 tha

5、t 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.

6、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(SIF

7、T); feature extracting; feature matching; KD tree 移動機器人視覺的研究主要集中在目標識別、定位以及跟蹤等方面。在上述研究內容中,視覺圖像的特征提取和匹配是它們的前提與基礎,特征點匹配結果的優(yōu)劣直接影響著后續(xù)的處理過程。在移動機器人自主導航過程中,圖像特征點匹配算法不僅要能夠適應機器人工作環(huán)境、光照、視野角度等因素帶來的圖像采集質量的變化,還應該滿足視覺信號處理實時性的基本要求,實現(xiàn)視覺圖像特征點的比例尺度不變的自動提取。最早提出特征點提取方法的是Moravec1,后來Harris等人2進行了改進,提出了Harris角點檢測方法,但是此方法只能對

8、一幅圖像按照固定的比例提取特征點,當兩幅圖比例發(fā)生較大變化時就無法進行匹配。Crowley等人3最早開始對比例不變特征進行研究,后來Lowe等人4,5提出了一種圖像比例不變特征提取方法SIFT,該方法通過對圖像進行不同程度的模糊與縮放,產生具有不同比例的圖像,然后從這些圖像中分別提取特征。這些提取的特征對圖像比例尺度、視野角度以及光照強度等具有較好的不變性,因此常用于移動機器人自主導航過程中提取圖像特征。 提取圖像特征后需要與地圖中路標圖像特征進行對比來確定移動機器人當前位姿,這就是圖像特征匹配的過程。圖像特征匹配算法中較為傳統(tǒng)的方法是鏈表式匹配方法,這種方法費時且運算復雜性較高。因此本文采用

9、一種最鄰近點匹配的方法,通過對比例空間中提取極值點構建一個樹型結構,然后用這個樹型結構完成不同比例圖像之間的匹配。這種方法可以有效地降低計算復雜度。 1 SIFT特征提取算法 采用SIFT方法提取的特征稱為SIFT特征。SIFT 特征是一種點特征,它是連續(xù)三幅高斯差分圖像中處于圖像邊緣附近的極值點。高斯差分圖像中的極值點是灰度值比它周圍像素點都大或者都小的像素點,即在圖像進行高斯模糊后變化最劇烈的像素點,因此這些從極值點中選取出來的SFIT特征點具有很好的穩(wěn)定性。處理過程如圖1所示。 SIFT方法通過在對圖像作多次比例變換,獲得所有圖像集合中比例空間中的極值點,并用這些極值點構建一個樹型結構,

10、然后用這個樹型結構完成不同比例圖像之間的匹配,從這些圖像中分別提取特征。該算法可分為比例尺度空間檢測、特征點定位、特征向量方向確定及特征描述器表述等過程6。特征描述器分布如圖2所示。 特征提取過程如下所示: 輸入:具有比例空間極值點的原始圖像 輸出:提取具有比例尺度不變特征的SIFT特征點 a)定義比例空間?L?和高斯差分函數(shù)?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,)? /*特征點提

11、取*/ b)用拉普拉斯高斯算子表示高斯差分算子,依次產生高斯差分圖像,提取?D?0G(K)中與周圍D?0G()和D?0G(2)中26個候選特征點相比灰度值都大或都小的候選特征點作為特征點: G(x,y,k)-G(x,y,)(k-1)?2?2G|k1,2,N? /*特征點定位*/ c)對比例空間函數(shù)?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?

12、>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)使用高斯權值函數(shù)為每個采樣點的梯度大小賦予權值。 (b)分配到某個等級的采樣點梯度值乘以1

13、-?d?個權值:?m(x,y)*(1-d)。其中d?為采樣點到等級中心的等級跨度距離。 (c)特征描述器的空間向量表示。采用4×4維直方圖,每個直方圖8個等級,每個特征點需要用4×4×8=128個元素的特征向量來描述。 (d)歸一化特征向量以減少光強的變化。 (e)每個像素值、梯度值歸一化以減小對比度的變化;每個像素值都加上一個常數(shù)以減小亮度的變化;設定單位特征向量的閾值?0.2?,歸一化其余的梯度值以降低大梯度的影響。 2 基于K維樹的特征匹配 SIFT特征匹配是對特征描述器進行比較,如果兩個特征描述器的差別小于設定數(shù)值,那么就稱這兩個特征相互匹配。通過特征匹配

14、可以找到特征與特征之間的對應關系。特征點匹配的形式描述如下: 設一個?K維空間的定義域和值域分別為R和D,E為K維空間R×D中采樣點的集合,d為目標點向量。其中d?i為向量d的第I維元素。一個簡單費時的算法是,依次計算E中所有點與目標點d之間的距離,從而找到與d最鄰近的點即鏈表式搜索法。這種算法的時間復雜度為O(N),N為E中點的數(shù)目。最常用、最方便的方法是最鄰近法。最鄰近點的形式化描述如下:設d的最鄰近點d?,則滿足 ?d?E,|dd|dd|,|dd|=ki=1(d?i-d)?2 這種基于?K?維樹(KD)7,8的最鄰近點搜索算法可以在地圖創(chuàng)建中處理大量的特征點匹配運算,具有較高的

15、匹配效率,將時間復雜度降低到?O?(log?2?N?)。 2.1 K維樹的建立 ?K維樹是一種存儲K維空間點集的數(shù)據結構,它是一棵二元樹,每個節(jié)點的描述如表1所示。其中:d表示該節(jié)點存儲的空間點向量;s值為I,劃分超平面是指經過點d且垂直于第I?維方向面;left代表所有位于劃分平面左子空間的點,right代表所有位于劃分平面右子空間的點。當且僅當一個點的第?I維元素小于(大于)d的第I?維元素時,這個點才位于劃分平面左(右)子空間。如果一個節(jié)點沒有子節(jié)點,那么就不需要劃分超平面。 為了說明?K?維樹劃分的過程,這里舉例說明。圖3 (a)表示了一棵二維空間(?k=2)的K?維樹,它由(2,5)

16、,(3,8),(6,3),(8,9)四個點向量構成。根節(jié)點(2,5)在第2維上將空間劃分為兩個子空間,點(3,8)位于右子空間,因為其第2維元素8大于點(2,5)的第2維元素5。同理,點(6,3)位于左子空間,點(8,9)位于右子空間。再看點(3,8),根據其第1維繼續(xù)劃分兩個子空間,點(8,9)位于點(3,8)的右子空間,因為其第1維元素8大于點(3,8)第1維元素3。圖3 (b)表示這棵?K?維樹對2維空間的劃分結果。 2.2 基于K維樹的最鄰近點搜索 ?K維樹建立起來后借助于一個簡單例子描述基于K?維樹的最鄰近點搜索算法。如圖3(c)所示,目標點用?X?標記,其所在區(qū)域的葉節(jié)點為點4。從

17、根節(jié)點進行初步搜索將找到點4,作為當前與目標點最鄰近的點。本例中點4不是最鄰近點。距離目標點更近的點一定位于以?X為圓心、以X?與點4之間為半徑的圓內。于是回溯到當前節(jié)點(點4)的父節(jié)點(點2),然后判斷父節(jié)點的另外一棵子樹中是否有距目標點更鄰近點的可能點。這在本例中是不可能的,因為圖中的圓沒有與父節(jié)點的另外一個子空間(圖中陰影區(qū)域)相交,在這種情況下,直接回溯到?K?維樹的更上一層,否則需要遞歸搜索父節(jié)點的另外一個子空間。搜索過程回溯到點1,這時需要搜索點1的另外一個子空間(圖中上半部分),因為圖中的圓與該子空間有相交。進而參考點3,其右子空間(圖中右上角區(qū)域)與圓相交,故搜索點3的右子空間

18、,最終找到了該子空間的葉節(jié)點(點5)。由于沒有其他區(qū)域與圓相交,點5就是與目標點最鄰近的點。 后面給出了基于?K?維樹的最鄰近點搜索算法描述,該算法采用深度優(yōu)先啟發(fā)式搜索策略。其中定義了一種數(shù)據結構,叫做超矩形(hyper-rectangle),用來描述?K?維空間采樣點集合所占據的空間范圍。判斷一個超矩形?hr是否與以目標點P?target?為中心且半徑為?r?超球體相交,首先需要找到?hr?中最接近target的點?P。P?由下式計算: ?P?i=hr?_min?i?if target?ihr?_min?i? target?i?if ?hr?_min?i?hr?_max?i?if targ

19、et?ihr?_max?i? 其中:?P?t與P?target?分別表示點?P?與?target?在第?I維上的取值;hr?_min?i?和?hr?_max?i?分別表示超矩形在第?I?維上的最小值和最大值。當|?P-P?target?|輸入:CCD當前?K?維樹的根節(jié)點kd,目標點target,?K?維樹所占用的超矩形?hr?,最鄰近點與目標點之間的最大距離max_dist; 輸出:目標點的最鄰近點nearest, 目標點與最鄰近點之間的距離distance。 a)令?s?=kd.?s?, pivot=kd.?d?; b)將?hr?劃分為兩個子超矩形,分別記為?lh?r?與?rh?r?,劃分

20、面經過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? 4)對外界光線變化匹配的魯棒性 表3給出了在不同光照強度下兩種算法對同一幅原始圖像的特征點匹配率對比情況。表中分別給出了在黃昏室內(10 LUX)、正常室內(60 LUX)、室內日光燈(100 LUX)、室內強日光(300 LUX)、室內陽光(600 LUX)、室內陽光和日光(

21、800 LUX),以及室內正午陽光加日光(1 000 LUX)光強下,特征點正確匹配情況。  可以看出,SIFT-KD算法正確匹配的光強變化范圍很廣,并且當光線變化時正確匹配率變化較為平穩(wěn),在一般光照情況下正確匹配率均能達到75%以上,較為適合移動機器人在未知室內環(huán)境下的自由導航過程。而傳統(tǒng)算法的匹配率較低,正確匹配的光線強度范圍較小,當外界光線發(fā)生變化時,匹配成功率變化波動較大,呈跳躍式波動趨勢,通常光照情況下的正確匹配率只有40%左右,不適合移動機器人在大范圍光照變化下的自由導航過程。由此可見,針對移動機器人在環(huán)境光強劇烈變化的環(huán)境下,SIFT-KD算法的正確匹配率比傳統(tǒng)算法明顯

22、提高,對光照變化的魯棒性增強,更適合于環(huán)境光線變化的機器人導航過程。 5)兩種算法特征點分布及匹配時間對比 圖8顯示的是傳統(tǒng)SIFT和SIFT-KD匹配算法圖像處理的對比結果。從圖8(b)中可以清楚地看到,傳統(tǒng)SIFT匹配的特征點分布較為均勻(圓圈大小代表比例尺度的變化),對圖像灰度變化不敏感,與原始的圖8(a)匹配特征點數(shù)213對,正確匹配對數(shù)93對,正確匹配率只是43%,這樣提取的特征點受光照強度、野角度影響很大,當機器人視角稍有變化,圖像中梯度變化較小部分提取的特征點就會消失,很難保證圖像之間的匹配;而圖8(c)中采用 SIFT-KD算法對原始圖像匹配的特征點多數(shù)集中在灰度變化較為明顯的

23、邊緣輪廓部位,邊界容易形成連線和封閉的區(qū)域,構成了不同層次和強度的邊緣梯度,并且正確匹配對數(shù)較多,201對特征點中正確匹配169對,正確匹配率接近84%,因此能較好地顯示出灰度邊緣輪廓,對光線和視野角度變化有很好的魯棒性。 從圖7(b)兩種算法匹配時間對比圖中可以清楚地看到,相同特征點數(shù)量情況下,SIFT-KD匹配算法的匹配時間要遠少于傳統(tǒng)SIFT匹配算法,匹配時間均值分別為85.062 5和120.437 5 ms。這是因為SIFT-KD算法雖然每一次迭代都需要追溯判斷當前節(jié)點父節(jié)點的匹配情況,但是從父節(jié)點搜索下一個子節(jié)點時不用遍歷搜索整個節(jié)點樹,縮短了整體匹配時間,提高了視頻圖像的實時處理

24、速度,加之本實驗中采用圖像視頻采集卡,雙向傳輸速度可達到120 fps,提高了圖像數(shù)據的傳輸速度。因此,基于KD樹的SIFT特征提取與匹配算法能滿足室內環(huán)境下移動機器人自主導航的實時性要求。 4 結束語 本文對移動機器人自主導航過程中的視頻圖像提取SIFT特征點,該方法提取的特征具有對比例變化、光照強度、視野角度等因素變化具有較強的魯棒性。但考慮到匹配準確率的要求,只有匹配的特征點對多于8對時,才認為該圖像與地圖庫中的特征圖像完全匹配,否則在地圖庫中繼續(xù)尋找與該圖像匹配的地圖路標。本文對提取的特征點采用一種深度啟發(fā)性搜索匹配算法最鄰近點搜索方法,該方法可以有效地減少特征搜索時間,降低運算復雜度

25、,提高搜索效率。通過以上實驗也可以看出,該方法能夠滿足室內環(huán)境下移動機器人大范圍、長距離自主導航過程中的實時視頻圖像處理過程,提高導航的實時性。 參考文獻: 1MORAVEC H. Rover visual obstacle avoidanceC/ Proc of the 7th International Joint Conference on Artificial Intelligence.Pittsburgh: Carnegie Mellon University, 1981:785-790. 2HARRIS C, STEPHENS M. A combined corner and ed

26、ge detectorC/ Proc of the 4th Alvey Vision Conference. Manchester, UK:s.n,1988:147-151. 3CROWLEY J L, PARKER A C. A representation for shape based on peaks and ridges in the difference of low-pass transformJ. IEEE Trans on Pattern Analysis and Machine Intelligence, 1984,6(2):156-170. 4LOWE D G. Districtive image features from scale-invariant keypointsJ. International Journal of Comput