馮玉朋,曾慶喜,，馬 杉，方 嘯

(1.南京航空航天大學無人駕駛車輛研究中心，江蘇南京 210016；2. 吉林大學汽車仿真與控制國家重點實驗室，吉林長春 130012；3. 奇瑞汽車前瞻技術研究院，安徽蕪湖 241000)

無人駕駛車輛基于角點和斑點的特征提取算法

馮玉朋1,2,曾慶喜1,2,3，馬 杉1,2，方 嘯3

(1.南京航空航天大學無人駕駛車輛研究中心，江蘇南京 210016；2. 吉林大學汽車仿真與控制國家重點實驗室，吉林長春 130012；3. 奇瑞汽車前瞻技術研究院，安徽蕪湖 241000)

針對運行在計算資源有限的車載嵌入式系統(tǒng)中的視覺里程計算法實時性較差的問題，提出一種基于Harris和SIFT相結合的圖像匹配方法——Harris-SIFT算法。在介紹了SIFT算法的基礎上，給出了Harris-SIFT算法的原理：使用Harris算法提取圖像中的角點作為特征候選點，再利用SIFT算法在Harris的特征候選點中進行特征點提取。通過實例用Matlab軟件對算法進行了仿真，并對算法的復雜度及各種性能進行了分析。結果表明，所提出的方法在特征檢測模塊中降低了算法的運算量、提高了特征點提取速度。Harris-SIFT算法可用于實時視覺里程計系統(tǒng)中，進而可使視覺里程計在車載嵌入式導航系統(tǒng)上得到廣泛的應用。

車輛工程；無人駕駛車輛；特征提?。籗IFT；Harris；RANSAC

精準的自定位對于無人駕駛車輛導航系統(tǒng)是至關重要的，是確保無人駕駛車輛完成自主行為的前提。近年來，基于視覺方法設計的里程計逐漸成為智能車輛定位的重要選擇。相對于傳統(tǒng)的車載傳感器，視覺傳感器具有成本低、體積小等優(yōu)點，且視覺傳感器可以提供豐富的感知信息，既可以滿足車輛的自定位要求，又能夠同時為其他重要的任務提供信息，如目標檢測、避障等。

圖像匹配是視覺里程計的關鍵技術之一，是將同一場景的不同時間、不同角度、不同設備等拍攝的圖片進行匹配的過程。對于行駛在未知區(qū)域中的無人駕駛車輛而言，圖像匹配在實現(xiàn)無人駕駛車輛位姿預測方面有著廣泛的應用價值。目前，一般采用的匹配方法包括基于區(qū)域匹配的方法和基于特征匹配的方法[1]?；趨^(qū)域的匹配方法[2-6]是從待匹配圖像的灰度值出發(fā)，通過計算兩幅圖像的灰度相關性來作為圖像匹配的標準，其局限性在于受灰度級分布和窗口形狀的影響；而基于特征的圖像匹配是通過提取2幅圖像重疊區(qū)域的穩(wěn)定特征來進行匹配的，該方法匹配速度快，具有較高的穩(wěn)定性和魯棒性，是圖像匹配較常用的一種方法。

基于特征的圖像匹配方法主要分為特征檢測與匹配2個關鍵步驟，這2個步驟的好壞將直接影響圖像匹配的結果。特征檢測算法可以分為2類：一類是角點檢測，提取角點的方法有很多[7-9]，如Harris角點[10]、Shi-Tomasi角點等；另一類是利用圖像的灰度進行檢測，如基于高斯濾波的高斯差、基于拉普拉斯變換的特征點檢測等。在這些特征檢測算子中，Harris角點檢測算法簡單且不受旋轉、光照、噪聲的影響，具有較好的檢測效果[11]，但其不具有尺度不變性，可能會導致匹配結果不準確[12]。而特征匹配最常用的是SIFT算子[13]，它是目前研究中最為穩(wěn)定的特征匹配算子，具有尺度、旋轉不變性，對光照變化穩(wěn)定性較高，但是算法中有大量的卷積運算及直方圖統(tǒng)計，運算復雜，難以滿足系統(tǒng)對實時性的要求。為了減少算法計算量，提高圖像匹配速度，文獻[14]提出了PCA-SIFT方法利用主成分分析把高維的特征向量進行降維，但計算量并沒有明顯地減少。BAY等[15]和郭曉冉等[16]提出了SURF方法，該方法利用積分代替卷積運算，通過統(tǒng)計特征點鄰域的Haar小波特征來生成64維的特征描述子，大幅提高了圖像匹配的速率，但是仍具有較大的計算量。也有很多研究考慮到Harris角點檢測和SIFT算法兩者的優(yōu)缺點，將兩種方法相結合去實現(xiàn)圖像匹配。如許佳佳等[17-18]采用多尺度Harris算子檢測角點特征，使用SIFT特征描述方法進行特征描述與匹配；文獻[19—20]利用Harris角點和Harris亞像素角點與SIFT算法相結合，實現(xiàn)特征點的快速匹配，但直接對Harris角點進行SIFT描述符描述，會造成很多錯誤的匹配；呂恒利等[21]通過Harris算法對SIFT特征點進行過濾，先進行Harris角點檢測和SIFT特征提取，然后選取Harris角點鄰域內的SIFT特征點，郭曉冉等[16]提出了一種利用Harris算法對SIFT算法進行自適應化改進的具有魯棒性的特征點提取算法。以上兩種方法提高了特征點的穩(wěn)定性，卻增加了算法的計算量。

本文結合Harris算法和SIFT算法各自的優(yōu)缺點，提出一種利用Harris算法來簡化SIFT算法的具有魯棒性的特征點檢測與匹配算法。首先利用Harris算法將圖像中的角點檢測出來，然后只對角點鄰域進行SIFT特征提取，從而實現(xiàn)圖像的精確匹配。

1 SIFT算法

SIFT是1999年David G Lowe提出的一種特征描述算法，在2004年Lowe在大量的研究基礎上，對該算法做了更為全面的總結，正式提出一種基于尺度空間的局部特征描述符——SIFT(尺度不變特征變換)。SIFT算子具有尺度不變性、旋轉不變性，對光照的變化、仿射變換、噪聲等具有魯棒性，已成為視覺領域最常用的描述符。算法步驟為構建尺度空間—尺度空間極值點檢測—特征點精確定位—確定關鍵點方向參數(shù)—生成特征描述子。

1.1 構建尺度空間

SIFT算法是基于尺度空間來對圖像進行處理的，其目的是模擬圖像數(shù)據(jù)的多尺度特征。該算法是利用高斯核與原圖像進行卷積，通過高斯卷積核中參數(shù)σ的變化，獲得多尺度空間下的圖像，實現(xiàn)了圖像的尺度變換。

二維圖像的尺度空間定義：

(1)

(2)

式中：L(x,y,σ)為圖像的尺度空間；G(x,y,σ)為尺度可變高斯函數(shù)；*為卷積運算符；I(x,y)為圖像函數(shù)；σ為尺度空間因子。

當完成高斯金字塔的建立后，按照式(3)建立DoG金字塔，即將高斯金字塔中相鄰尺度的圖像相減即可得到DoG金字塔：

(3)

圖1 尺度空間極值檢測Fig.1 Scale space extrema detection

1.2 尺度空間極值點檢測

在DoG尺度空間檢測極值點時，需要把每一個采樣點與其鄰域及上下層中的26點進行比較，如圖1所示。當采樣點的像素均大于或小于這26個點時，該點為極值點。

1.3 特征點精確定位

通過上一步檢測出的極值點中包括一些低對比度點和不穩(wěn)定的邊緣響應點，所以需要進一步進行篩選。通過擬合三維二次函數(shù)可以去除低對比度點，一般采用的是D(x,y,σ)的泰勒展開式。但是高斯差函數(shù)在邊緣部分會有相對較大的變化，這些不穩(wěn)定的極值點需要剔除，極值點的主曲率通過一個2×2的Hessian矩陣H求出：

(4)

然后根據(jù)該矩陣的跡與其行列式之間的關系來去除不穩(wěn)定的邊緣響應點。

根據(jù)關鍵點周圍鄰域像素點的梯度方向為每一個關鍵點指定方向參數(shù)，使算子具有旋轉不變性。關鍵點(x,y)處梯度的模值和方向如下：

(5)

(6)

圖2 關鍵點周圍16×16區(qū)域Fig.2 16×16 area around keypoints

其中L所用的尺度是每個關鍵點各自所在的尺度。在實際計算時，在以關鍵點為中心的鄰域窗口內采樣，并用直方圖統(tǒng)計鄰域像素的梯度方向。梯度直方圖的范圍是0～360°，其中每45°一個柱，總共8個柱，或者每10°一個柱，總共36個柱。直方圖的峰值則代表了該關鍵點處鄰域梯度的主方向，作為該關鍵點的方向。

1.4 生成特征描述子

以關鍵點為中心選取一個16×16大小的區(qū)域，如圖2所示，然后把這個區(qū)域分成4×4個大小為4×4的小區(qū)域，每個小區(qū)域內計算加權梯度直方圖，每個子區(qū)域直方圖分為8方向，最后得到4×4×8=128維的向量，作為該點的SIFT描述子。

2 Harris-SIFT算法

2.1 研究背景

如何提高視覺里程計特征提取與匹配算法的效率，降低算法計算復雜度，是視覺里程計系統(tǒng)中急需解決的一個問題，也是利用視覺里程計進行實時定位的關鍵問題。在特征檢測、提取和匹配過程中涉及到的大量的像素運算和高維的向量運算，是造成算法消耗時間長和效率較低的原因。

圖3 算法流程圖Fig.3 Flow chart of the algorithm

在現(xiàn)有的特征提取算法中，SIFT特征算法是視覺里程計研究中最為常用的一種特征提取與描述算法。通過該算法提取的特征不會因為兩幅圖像的尺度不同、視角不同或是旋轉關系而發(fā)生變化，同時對光照的變化、仿射變換、噪聲等不敏感。SIFT特征提取算法是在多尺度空間下對圖像進行特征提取，其尺度空間是利用二維高斯核函數(shù)與圖像進行卷積構建的，并且在關鍵點分配主方向和生成128維的特征描述子時有大量的直方圖運算，故SIFT特征算法計算量比較大，消耗時間比較長。Harris算法利用圖像的灰度變化來判斷角點，沒有那么大的運算量，并且?guī)缀蹩梢詸z測到所有的角點，但角點匹配困難，出錯率較高。為了提高視覺里程計的實時性，就必須降低算法計算復雜度，提高特征點提取速度，在保證各種性能的前提下，盡量減少算法的計算量?；趦煞N算法的特點，本文提出了一種基于SIFT和Harris深度融合的特征提取算法。

2.2 算法基本原理

首先，利用Harris算法把圖像中的角點檢測出來，然后，在Harris角點鄰域內進行SIFT特征點提取，這些特征點將同時具有Harris角點和SIFT特征點的共同特征。利用SIFT描述子的特征描述方法對提取的特征點進行描述。該算法流程圖如圖3所示，具體實現(xiàn)步驟如下。

步驟1：首先在采集的圖像序列中提取Harris角點作為候選特征點。

Harris算法是以Moravec算法為基礎的，其原理是以目標像素點為中心的窗口向任意方向移動，計算移動前后的灰度變化來判斷像素點是否為角點。若在該像素點處，水平和垂直2個方向的變化均較大，則該像素點屬于角點。計算公式如式(7)所示。

(7)

式中：w(x,y)=exp(-(x2+y2)/(2σ2)),為窗口函數(shù)，Ix,Iy分別為圖像在x,y方向上的偏導數(shù)。

則圖像I在(x,y)處的局部自相關函數(shù)為

(8)

Harris角點的響應函數(shù)R定義為

(9)

式中：det(M)為矩陣M的行列式，tr(M)為矩陣M的跡，k=[0.04，0.06]。采用8領域非最大值抑制(即尋找局部最大值，將非極大值點所對應的灰度值置為0)來選擇那些響應度夠大的點，這些點即為角點。

步驟2：根據(jù)檢測到的角點的坐標選擇SIFT特征點的區(qū)域，建立局部的高斯金字塔和DoG金字塔。遍歷所有角點的坐標，若在一個角點的鄰域內出現(xiàn)另一個角點，則認為它們屬于同一區(qū)域，根據(jù)角點的分布情況將圖像進行分塊，將不含角點和面積較小(面積的大小根據(jù)在所建的DoG金字塔中檢測極值時的圖像層數(shù)s決定)的圖像塊去掉。然后利用式(1)—式(3)在選定的區(qū)域內建立局部的高斯金字塔和DoG金字塔。

步驟3：在每個角點的局部尺度空間檢測極值點。將每個角點與其圖像域和空間域相鄰的26個像素點進行比較，如圖1所示。在角點領域的DoG尺度空間中，如果一個點的像素值在本尺度以及上下兩尺度的26個領域像素點的像素值中是最值(最大或最小)時，則認為該像素點是它所在尺度下圖像的一個特征點。如果該角點領域的DoG尺度空間內存在特征點，則保留該尺度空間；否則，刪除該尺度空間。

步驟4：為特征點分配主方向。利用式(5)和式(6)計算特征點梯度的模值和方向，然后在以特征點為中心的鄰域窗口內采樣，并用直方圖統(tǒng)計鄰域像素的梯度方向來確定特征點的主方向。

步驟5：生成特征點描述子。因為角點特征本身具有旋轉不變性，所以直接以特征點為中心選取一個16×16大小的區(qū)域，然后在每個4×4的小區(qū)域內計算8方向的梯度信息，最后得到4×4×8=128維的向量，該向量作為該點的Harris-SIFT描述子。

3 仿真及分析

為了驗證算法的性能，對大量的實驗圖像進行了測試，實驗結果均較為理想。實驗是在PC機上實現(xiàn)的，硬件環(huán)境為Intel Core i5，內存4G，軟件開發(fā)環(huán)境為Windows 7操作系統(tǒng)，Matlab 2012b版。實驗所用的3組匹配圖像分別取自不同的場景，如圖4所示。第1組圖像大小為720×480；第2組圖像大小為640×480；第3組圖像大小為1 280×960。

圖4 待匹配圖像Fig.4 Images to be matched

首先，通過實驗對比來驗證本文方法在特征點檢測時間上相較于現(xiàn)有算法的優(yōu)勢。分別利用Harris角點檢測算法、SIFT算法、PCA-SIFT算法、SURF算法以及Harris-SIFT算法對圖4中的3組圖像進行特征點提取，單個特征點檢測時間如表1所示。由表1可知，由于Harris算法不需要構建尺度空間和卷積運算，采用Harris算法檢測特征點具有明顯的時間優(yōu)勢；SIFT算法的運行時間最長；PCA-SIFT算法的特征提取模塊與SIFT算法一樣，所以其單個特征點檢測所用時間和得到的特征點的數(shù)量與SIFT算法相同；而在SURF算法中，通過積分代替SIFT算法中的微分計算，減少了算法的計算量；Harris-SIFT算法特征檢測時間相對SIFT算法有明顯的減少。這是因為Harris-SIFT算法不需要在整幅圖像中進行特征點檢測，而只需要在Harris角點鄰域中進行檢測，所需要計算的像素點的數(shù)量大大減少，節(jié)省了一部分計算時間。

表1 單個特征點檢測時間

然后，在上述實驗環(huán)境下分別利用SIFT算法、PCA-SIFT算法、SURF算法和Harris-SIFT算法對圖4中3組實驗圖像進行特征點提取與匹配，其提取特征點的數(shù)量以及匹配對數(shù)見表2和表3。通過對比表2、表3中的數(shù)據(jù)可知，采用本文方法所獲得的特征點的數(shù)量比SIFT算法、PCA-SIFT算法和SURF算法得到的特征點數(shù)量要少，但也節(jié)省了匹配過程中所消耗的時間?；贖arris-SIFT的視覺里程計位姿估計模塊基礎矩陣的求解一般至少需要7對匹配點，這是由于可能存在誤匹配點對，且匹配點對的坐標受噪聲干擾也有誤差。本文方法獲得的正確匹配的特征點對的數(shù)量相比于其他3種算法來說較少，但足以通過由其獲得的匹配點對計算得到攝像機的位姿。

表2 5種算法提取特征的數(shù)量統(tǒng)計

表3 不同算法的特征點匹配對數(shù)

4 結 語

根據(jù)Harris算法和SIFT算法各自的特點，提出一種基于Harris角點和SIFT相結合的圖像匹配方法，先提取Harris角點，然后在角點中尋找具備SIFT特征的特征點，采用SIFT描述子對特征點進行描述，最后以少量特征點實現(xiàn)圖像的匹配。本算法同時具備2種算法的優(yōu)點，提高了特征點提取速度，并保持了良好的匹配效率，對于實時車載視覺里程計系統(tǒng)的開發(fā)具有一定的參考價值。未來可考慮融合其他傳感器，建立組合導航系統(tǒng)，進一步提高視覺里程計的性能。

/References：

[1] 李昱川，田錚，劉向增. SAR圖像多尺度配準的小波域最小割模型方法[J]. 電子學報，2010，38(9): 2122-2127. LI Yuchuan, TIAN Zheng, LIU Xiangzeng. A minimum-cut model method in wavelet domain for SAR image multiscale registration[J]. Acta Electronica Sinica, 2010，38(9): 2122-2127.

[2] ZHAI Bo, ZHENG Jin, LI Bo. Digital image stabilization based on adaptive motion filtering with feedback correction[J]. Journal of Multimedia Tools and Applications, 2016, 75(19): 12173-12200.

[3] SHUKLA D, JHA R K, OJHA A. Digital image stabilization using similarity transformation over constrained differential-radon warping vectors[J]. Journal of Signal Processing-Image Communication, 2016, 47: 115-130.

[4] YANG Weiping, ZHANG Zhilong, ZHANG Yan, et al. Real-time digital image stabilization based on regional field image gray projection[J]. Journal of Systems Engineering and Electronics, 2016, 27(1): 224-231.

[5] 張艷超，王芳，趙建，等. 投影特征峰匹配的快速電子穩(wěn)像[J]. 光學精密工程，2015, 23(6): 1768-1773. ZHANG Yanchao, WANG Fang, ZHAO Jian,et al. Fast digital image stabilization based on characteristic peak of projection matching[J]. Optics and Precision Engineering, 2015, 23(6): 1768-1773.

[6] KIR B, KURT M, URHAN O. Local binary pattern based fast digital image stabilization[J]. Journal of Signal Processing Letters, 2015, 22(3): 341-345.

[7] RASSEM T H, KHOO B E. Performance evaluation of new colour histogram-based interest point detectors[J]. Journal of Multimedia Tools and Applications, 2015, 74(24): 11357-11398.

[8] ZIOMEK A, OSZUST M. Evaluation of interest point detectors in presence of noise[J]. Journal of Intelligent Systems and Applications, 2016, 8(3): 26-33.

[9] LANG S R, LUERSSEN M H, POWERS D M W. Automated evaluation of interest point detectors[J]. Journal of Software Innovation, 2014, 2(1): 86-105.

[10]HARRIS C, STEPHENS M. A combined corner and edge detector[C]//Proc of 4th Alvey Vision Conference. [S.l.]: [s.n.], 1988：147-151.

[11]KARTHIK O S,VARUN D, RAMASANGU H. Localized Harris-FAST interest point detector[C]//India Conference.[S.l.]:IEEE, 2016.

[12]LOWE D U. Distinctive image features from scale-invariant keypoints[J]. Journal of Computer Vision, 2004, 60(2): 91-110.

[13]KE Y, SUKTHANKAR R. PCA-SIFT: A more distinctive representation for local image description[C]//Proc of IEEE Computer Vision and Pattern Recognition Conference.[S.l.]:[s.n.], 2004: 506-513.

[14]BAY H, TUYTELAARS T, VAN-GOOL L. SURF: Speeded-up robust features(SURF)[C]//Proc of European Conference on Computer Vision.[S.l.]:[s.n.], 2006: 404-417.

[15]BAY H, ESS A, TUYTELAARS T, et al. Speeded-up robust features(SURF)[J]. Journal of Computer Vision and Image Understanding, 2008, 110(3): 346-359.

[16]郭曉冉，崔少輝. 基于局部特征點匹配的圖像拼接算法[J]. 半導體光電，2014，35(1): 89-94. GUO Xiaoran, CUI Shaohui. Image mosaic approach using local feature points registration[J]. Journal of Semiconductor Optoelectronics, 2014, 35(1): 89-94.

[17]許佳佳，張葉，張赫. 基于改進Harris-SIFT算子的快速圖像配準算法[J]. 電子測量與儀器學報，2015，29(1): 48-54. XU Jiajia, ZHANG Ye, ZHANG He. Fast image registration algorithm based on improved Harris-SIFT descriptor[J]. Journal of Electronic Measurement and Instrumentation, 2015, 29(1): 48-54.

[18]許佳佳. 結合Harris與SIFT算子的圖像快速配準算法[J]. 中國光學，2015，8(4): 574-581. XU Jiajia. Fast image registration method based on Harris and SIFT algorithm[J]. Journal of Chinese Optics, 2015, 8(4): 574-581.

[19]HE H,CHEN X,LIU B,et al. A sub-Harris operator coupled with SIFT for fast images matching in low-altitude photogrammetry[J]. International Journal of Signal Processing, Image Processing and Pattern Recognition, 2014, 7(3): 395-406.

[20]SHARMA K, GOYAL A. Very high resolution image registration based on two step Harris-Laplace detector and SIFT descriptor[C]//International Conference on Computing.[S.l.]:[s.n.], 2013:1-5.

[21]呂恒利，尚振宏，劉輝，等. 基于Harris角點和SIFT算法的車輛圖像匹配[J]. 昆明理工大學學報(自然科學版)，2015，40(1): 49-54. LYU Hengli, SHANG Zhenhong, LIU Hui, et al. Vehicle image matching based on Harris corner and SIFT algorithm[J]. Journal of Kunming University of Science and Technology(Natural Science Edition), 2015, 40(1): 49-54.

A feature extraction algorithm based on corner and spots in self-driving vehicles

FENG Yupeng1,2, ZENG Qingxi1,2,3, MA Shan1,2, FANG Xiao3

(1.Self-driving Vehicle Research Center, Nanjing University of Aeronautics and Astronautics, Nanjing, Jiangsu 210016, China; 2. State Key Laboratory of Automotive Simulation and Control, Jilin University, Changchun, Jilin 130012, China;3.Prospective Technology Research Institute of Chery Automobile Company Limited, Wuhu, Anhui 241000, China)

To solve the poor real-time performance problem of the visual odometry based on embedded system with limited computing resources, an image matching method based on Harris and SIFT is proposed, namely the Harris-SIFT algorithm. On the basis of the review of SIFT algorithm, the principle of Harris-SIFT algorithm is provided. First, Harris algorithm is used to extract the corners of the image as candidate feature points, and scale invariant feature transform (SIFT) features are extracted from those candidate feature points. At last, through an example, the algorithm is simulated by Matlab, then the complexity and other performance of the algorithm are analyzed. The experimental results show that the proposed method reduces the computational complexity and improves the speed of feature extraction. Harris-SIFT algorithm can be used in the real-time vision odometer system, and will bring about a wide application of visual odometry in embedded navigation system.

vehicle engineering; self-driving vehicles; feature extraction; SIFT; Harris; RANSAC

1008-1542(2017)03-0237-07

10.7535/hbkd.2017yx03004

2017-02-28；

2017-04-10；責任編輯：馮 民

國家自然科學基金(51505221)；中國博士后科學基金(YBA16027)；國家重點實驗室開放基金；南京航空航天大學研究生創(chuàng)新基地(實驗室)開放基金(kfjj20160216)

馮玉朋(1992—)，男，安徽滁州人，碩士研究生，主要從事無人駕駛車輛視覺導航系統(tǒng)方面的研究。

曾慶喜博士。E-mail：cheliang@nuaa.com

TP391.4

A

馮玉朋，曾慶喜，馬 杉，等.無人駕駛車輛基于角點和斑點的特征提取算法[J].河北科技大學學報,2017,38(3):237-243. FENG Yupeng，ZENG Qingxi，MA Shan，et al.A feature extraction algorithm based on corner and spots in self-driving vehicles[J].Journal of Hebei University of Science and Technology,2017,38(3):237-243.