一種具有實(shí)時性的SIFT特征提取算法

李鶴宇，王 青

(北京航空航天大學(xué)自動化科學(xué)與電氣工程學(xué)院，北京 100191)

一種具有實(shí)時性的SIFT特征提取算法

李鶴宇，王 青

(北京航空航天大學(xué)自動化科學(xué)與電氣工程學(xué)院，北京 100191)

針對尺度不變特征變換(SIFT)算法實(shí)時性差和在生成灰度圖時信息丟失的問題，提出一種對比度增強(qiáng)和使用DAISY描述符的SIFT特征提取算法。首先，通過彩色圖和原始灰度圖計算像素的顏色調(diào)整值和曝光調(diào)整值，根據(jù)調(diào)整值與原灰度級獲得對比度增強(qiáng)的灰度圖。其次，使用改進(jìn)后的灰度圖提取SIFT特征點(diǎn)，并根據(jù)鄰域灰度級計算不同高斯核和方向下的卷積方向圖。最終，由特征點(diǎn)和采樣點(diǎn)不同方向的偏導(dǎo)數(shù)值獲得DAISY描述符，該描述符結(jié)構(gòu)簡單，便于計算。對由標(biāo)準(zhǔn)圖像數(shù)據(jù)集提取的特征點(diǎn)使用K近鄰(KNN)算法進(jìn)行匹配，以評價在不同變化下算法的準(zhǔn)確率。試驗(yàn)結(jié)果表明，該算法能夠獲得更多的特征點(diǎn)，并且在保證準(zhǔn)確率的同時降低描述符生成部分和特征匹配部分的時間。

尺度不變特征變換(SIFT)；圖像匹配；對比度增強(qiáng)；DAISY描述符

0 引 言

圖像匹配算法是遙感技術(shù)、飛行器景象導(dǎo)航、目標(biāo)特征跟蹤問題、空間探測器位姿估計的基礎(chǔ)，廣泛應(yīng)用于航天領(lǐng)域[1-5]。Ma等[6]針對遙感圖強(qiáng)度不同時匹配點(diǎn)對較少的問題，定義了一種新的梯度，并將特征點(diǎn)的尺度、方向等信息引入到匹配算法中。陳方等[7]提出一種景象匹配輔助導(dǎo)航算法，對尺度不變特征變換(Scale-invariant feature transform,SIFT)特征點(diǎn)檢測和匹配進(jìn)行優(yōu)化，以獲取航向和位置偏差信息。Toshihiko等[8]針對小天體著陸問題，將彈坑、巖石等灰度變化明顯的區(qū)域作為陸標(biāo)，并利用圖像匹配技術(shù)對其進(jìn)行跟蹤。孫小煒等[9]采用基于目標(biāo)灰度特征的粒子濾波方法抑制圖像匹配的漂移，實(shí)現(xiàn)對非剛性變形目標(biāo)的穩(wěn)定跟蹤。郝剛濤等[10]針對故障衛(wèi)星繞本體最大慣量軸慢轉(zhuǎn)時信息缺失的問題，使用基于特征匹配的即時定位與地圖構(gòu)建(Simutaneous localization and mapping,SLAM)系統(tǒng)測量相對位置。

由Lowe[11]提出的SIFT算法，對不同視角變換和外界環(huán)境干擾具有較強(qiáng)的魯棒性。但是，SIFT使用灰度圖進(jìn)行處理，丟失部分彩色圖信息，并且為了獲得較好的性能，算法復(fù)雜，不能達(dá)到實(shí)時性。針對上述問題，學(xué)者們進(jìn)行了多方面的研究。Zhao等[12]利用灰度級分布，進(jìn)行不同程度的曝光調(diào)整，達(dá)到增強(qiáng)對比度的效果；Abdelhakim等[13]提出一種Colored SIFT算法，新生成的描述包含顏色信息，并對集合變化具有較強(qiáng)的魯棒性；Kwon等[14]根據(jù)物體的表面反射特性計算不變色值，根據(jù)該值檢測圖像局部特征并生成描述符。Lee等[15]減小SIFT中高斯濾波器的標(biāo)準(zhǔn)偏差并簡化高斯金字塔的構(gòu)建以降低算法復(fù)雜度；Yao等[16]通過下采樣替代上采樣保存插值運(yùn)算，并減少尺度空間的組數(shù)和每組的層數(shù)。

Tola等[17-18]提出DAISY描述符，由于其對稱性的結(jié)構(gòu)和較快的運(yùn)算速度，得到了廣泛的關(guān)注。學(xué)者多將其應(yīng)用于基于密集選取的局部特征提取。Huang等[19]將DAISY描述符與樹狀結(jié)構(gòu)相結(jié)合，通過計算匹配成本來避免局部最優(yōu)結(jié)果。Velardo等[20]利用DAISY描述符提取面部特征，并使用遞歸網(wǎng)格算法實(shí)現(xiàn)匹配。

本文提出一種基于對比度增強(qiáng)和DAISY描述符的SIFT特征提取算法，以增強(qiáng)顏色魯棒性并降低運(yùn)算時間。

1 SIFT算法流程

1.1 彩色圖轉(zhuǎn)化為灰度圖

將RGB模式的彩色圖轉(zhuǎn)化為灰度圖Gray的方式：

Gray=0.299R+0.587G+0.114B

(1)

式中：R、G、B分別代表像素點(diǎn)紅、綠、藍(lán)三個通道。

1.2 構(gòu)建高斯差分金字塔

高斯尺度圖像L(σ)由初始圖像I和高斯函數(shù)G(σ)卷積得到，根據(jù)卷積的可分離性，通過L(σ1)求取L(σ2)：

(2)

圖1 尺度空間構(gòu)建Fig.1 The construction of scale space

改變高斯核σ的值，獲得不同尺度下的高斯卷積圖像，構(gòu)成高斯金字塔的第0組，組內(nèi)圖層按高斯核從低到高排列，通過下采樣得到下一組的第1層圖像。以此類推，獲得高斯金字塔，其中每一層圖像的尺度為：

(3)

式中：o表示組數(shù)，O表示總組數(shù)，r表示層數(shù)，s設(shè)為3。通過高斯金字塔組內(nèi)相鄰層灰度的差值獲得高斯差分金字塔(Difference of Gaussian, DOG)，如圖1所示。

1.3 特征點(diǎn)檢測

對DOG組內(nèi)除邊界層外的點(diǎn)，對比8鄰域點(diǎn)和相鄰圖層各9個點(diǎn)，得到局部極值點(diǎn)，并使用泰勒級數(shù)展開式擬合函數(shù)：

(4)

通過使式(4)右側(cè)等于0，得到亞像素級別的特征點(diǎn)坐標(biāo)。為了獲得穩(wěn)定的特征點(diǎn)，還需要去除灰度級較小的極值點(diǎn)和在邊緣處的極值點(diǎn)。

1.4 主方向計算

為每一個特征點(diǎn)分配一個主方向，以便實(shí)現(xiàn)旋轉(zhuǎn)不變性。在以特征點(diǎn)為中心，3×1.5σ的鄰域范圍內(nèi)，統(tǒng)計像素點(diǎn)梯度方向和幅值，用直方圖表示統(tǒng)計結(jié)果，峰值所對應(yīng)的角度作為特征點(diǎn)的方向，如圖2所示。至此獲得圖像的亞像素級特征點(diǎn)坐標(biāo)和對應(yīng)的方向。

圖2 特征點(diǎn)主方向選取示意圖Fig.2 Illustration of the feature point main direction selection

1.5 描述符生成

根據(jù)主方向?qū)μ卣鼽c(diǎn)的鄰域進(jìn)行旋轉(zhuǎn)，以特征點(diǎn)為中心，將矩形鄰域范圍內(nèi)的像素點(diǎn)分為4×4個區(qū)域，對360°進(jìn)行8等分，統(tǒng)計每個區(qū)域內(nèi)所有點(diǎn)的梯度幅值和方向，生成128維的描述子。

2 本文算法

本文引入對比度增強(qiáng)算法，并使用DAISY描述符替代原有的SIFT描述符。算法流程圖如下：

圖3 本文算法流程圖Fig.3 The flow chart of the proposed algorithm

2.1 對比度增強(qiáng)算法

式(1)中R、G、B三個通道的系數(shù)根據(jù)人眼對三種顏色敏感度確定，由于三者系數(shù)不同，會出現(xiàn)不同顏色產(chǎn)生相同灰度級的現(xiàn)象，影響算法最終效果。此外，彩色圖每個像素點(diǎn)包含三個信息通道，灰度圖采用單通道模式，轉(zhuǎn)化為灰度圖時會有信息丟失現(xiàn)象，影響算法效果。因此本文算法通過計算顏色調(diào)整和曝光調(diào)整兩個量，對灰度圖的初始值進(jìn)行調(diào)整，增加對比度，保留更多的局部梯度信息。

2.1.1 顏色調(diào)整

將RGB模式的圖像轉(zhuǎn)化為YCbCr模式：

(5)

式中：Y、Cb、Cr分別代表灰度、紅色色度和藍(lán)色色度通道。統(tǒng)計Cb通道和Cr通道的平均值，用mb和mr表示。每個像素點(diǎn)的顏色調(diào)整Yci根據(jù)該點(diǎn)Cbi通道和Cri通道的相對大小、mb和mr的相對大小確定，并得到調(diào)整后的中間值P。

YCi=ksgn(mr-mb)×sgn(Cri-Cbi)×

(6)

P=Y+YC

(7)

式中：k的值取為3，α的值取為0.15。

2.1.2 曝光調(diào)整

灰度圖的信息主要由平均灰度級和局部對比度構(gòu)成。平均灰度級約等于127.5[12]時，能夠獲得較好的全局信息，因此灰度級接近127.5的像素點(diǎn)進(jìn)行較大的調(diào)整；圖像不同范圍的灰度級均勻分布時能夠保留較多的局部對比度，因此灰度級遠(yuǎn)離127.5像素點(diǎn)進(jìn)行較小的曝光調(diào)整：

YEi=(128-mP)exp[-(i-0.5)2/2σ2]

(8)

式中：將σ的值設(shè)定為0.25時。最終獲得調(diào)整后的灰度圖T：

T=Y+YC+YE

(9)

2.2 描述符生成

通過SIFT獲得特征點(diǎn)位置和主方向后，算法將DAISY描述符應(yīng)用于稀疏選取，達(dá)到提升計算效率的目的。

DAISY描述符計算灰度圖多個方向和尺度下的卷積方向圖，根據(jù)特征點(diǎn)和采樣點(diǎn)處的不同方向的偏導(dǎo)數(shù)生成描述符。首先，計算原始圖像I在不同方向的偏導(dǎo)數(shù)[17-18]：

(10)

(a)+=max(a,0)

(11)

式(10)中：等號右側(cè)表示計算圖像I每個點(diǎn)o方向的偏導(dǎo)數(shù)值，當(dāng)像素點(diǎn)偏導(dǎo)數(shù)值小于零時，取為0。由這些值組成的新矩陣稱為方向圖，記為Go，共計算8個方向的方向圖，相鄰方向間隔45°。

其次,對方向圖進(jìn)行不同尺度的卷積計算：

(12)

最后,以特征點(diǎn)為圓心，在卷積方向圖M層同心圓上分別獲得N個均勻分布的采樣點(diǎn)，同心圓的半徑分別為R1,…,RM，同一圓上采樣點(diǎn)對應(yīng)卷積方向圖的高斯核相同，高斯核大小與同心圓半徑成正比，其結(jié)構(gòu)如圖4所示。

圖4 DAISY描述符結(jié)構(gòu)Fig.4 The structure of DAISY operator

根據(jù)特征點(diǎn)和采樣點(diǎn)的偏導(dǎo)數(shù)值獲得描述符，如下所示：D(u,v) =

(13)

DAISY描述符采用圓形網(wǎng)格結(jié)構(gòu)，具有更好的定位屬性[20]。此外，在計算卷積方向圖時，由于高斯卷積函數(shù)具有可分離性，可以降低計算量。因此該算子具有較好的性能，并能提高計算效率。

3 仿真校驗(yàn)

對算法進(jìn)行仿真，并與文獻(xiàn)[12]算法進(jìn)行比對，以驗(yàn)證算法的特性。仿真硬件開發(fā)平臺為：處理器為Intel(R) Core(TM) i5-5200U CPU @ 2.20G Hz，內(nèi)存8.00 GB；軟件開發(fā)平臺為Windows 10操作系統(tǒng)、Microsoft Visual Studio Professional 2013、OpenCV 2.4.9。試驗(yàn)使用牛津大學(xué)機(jī)器人實(shí)驗(yàn)室的圖像數(shù)據(jù)集[21]，仿真采用其中的仿射變化圖集、亮度變化圖集、清晰度變化圖集，并通過實(shí)測圖模擬旋轉(zhuǎn)變化，每組包含5張圖像，其中組內(nèi)圖像變化程度依次增加。仿真計算圖像平均灰度、圖像特征點(diǎn)個數(shù)和匹配正確率三個量，以衡量本文算法的性能。

統(tǒng)計原始灰度圖和對比度增強(qiáng)灰度圖像素點(diǎn)的平均灰度級，并計算SIFT算法特征點(diǎn)的數(shù)量，每組圖像的灰度平均值如表1所示。從表1可以看出，加入對比度增強(qiáng)算法后的平均灰度級接近127.5，保留更多的局部信息，從而提取更多的特征點(diǎn)。此外，特征點(diǎn)增加的數(shù)量與平均灰度級的變化量有關(guān)，亮度變化圖集和旋轉(zhuǎn)變化圖集經(jīng)過對比度增強(qiáng)算法，平均灰度級獲得較大的調(diào)整，特征點(diǎn)數(shù)量分別增加26.2%、41.3%。

表1 特征點(diǎn)提取數(shù)量

在每個圖集中，以第一張圖像作為基準(zhǔn)，使用K最近鄰(K-nearest neighbor,KNN)算法[22]與后四張圖像進(jìn)行匹配，統(tǒng)計匹配時間和正確率。原算法和本文算法對每組第1、2幅圖像的匹配結(jié)果如圖5、圖6所示。兩種算法對特征點(diǎn)進(jìn)行匹配所需要的時間和正確率分別如表2～9所示。

圖5 原算法匹配結(jié)果Fig.5 The matching result of the original algorithm

圖6 本文算法匹配結(jié)果Fig.6 The matching result of the proposed algorithm

匹配結(jié)果匹配數(shù)量正確匹配正確率描述符生成/s特征匹配/s圖1圖291587395．4%7．5917．588圖1圖331927285．2%7．5328．668圖1圖4552240．0%7．8788．01圖1圖537718．9%7．6898．523

表3 本文算法仿射變化圖集匹配準(zhǔn)確率及時間

表4 原算法亮度變化圖集匹配準(zhǔn)確率及時間

表5 本文算法亮度變化圖集匹配準(zhǔn)確率及時間

表6 原算法清晰度變化圖集匹配準(zhǔn)確率及時間

表7 本文算法清晰度變化圖集匹配準(zhǔn)確率及時間

表8 原算法旋轉(zhuǎn)變化圖集匹配準(zhǔn)確率及時間

表9 本文算法清晰度變化圖集匹配準(zhǔn)確率及時間

通過對比表2～9的數(shù)據(jù)可以發(fā)現(xiàn)，對于仿射變化、亮度變化和旋轉(zhuǎn)變化，改進(jìn)后的算法在描述符生成和特征匹配部分都能明顯提高計算效率，對于清晰度變化，除后兩組的描述符生成時間外，改進(jìn)后算法的運(yùn)行時間小于原算法對應(yīng)部分。原算法的匹配準(zhǔn)確率隨著變化程度的加強(qiáng)而降低，而改進(jìn)后的算法在較大的清晰度變化下，仍能獲得較高的匹配正確率，對于其它三種變化，改進(jìn)后的算法和原算法的匹配正確率相近，沒有出現(xiàn)明顯的差異。因此，改進(jìn)后的算法能夠在保證匹配正確率的同時降低運(yùn)算時間。

4 結(jié) 論

針對SIFT算法結(jié)構(gòu)復(fù)雜、存在信息丟失的問題，本文提出一種改進(jìn)的SIFT特征匹配算法。首先，根據(jù)彩色圖計算像素點(diǎn)的顏色調(diào)整、曝光調(diào)整，獲得對比度增強(qiáng)的灰度圖，以保留更多的信息。其次，使用SIFT算法獲得特征點(diǎn)坐標(biāo)和主方向。最后，利用DAISY描述符中心對稱的結(jié)構(gòu)和易于實(shí)現(xiàn)旋轉(zhuǎn)計算的特點(diǎn)，通過特征點(diǎn)和采樣點(diǎn)在卷積方向圖中的梯度值，獲得特征向量。仿真結(jié)果表明，對比度增強(qiáng)的灰度圖能夠提取更多的特征點(diǎn)，本文算法能夠?qū)Σ煌瑘D像變化保持魯棒性，維持較高的匹配準(zhǔn)確率，并有效降低描述符生成和特征點(diǎn)匹配部分的計算時間。下一步的研究重點(diǎn)是對特征提取部分進(jìn)行簡化，簡化高斯金字塔的構(gòu)建步驟，以進(jìn)一步提高運(yùn)算速度。

[1] 劉玉, 王敬東, 李鵬. 一種基于SIFT和KLT相結(jié)合的特征點(diǎn)跟蹤方法研究[J]. 宇航學(xué)報, 2011, 32(7):1618-1625. [Liu Yu, Wang Jing-dong, Li Peng. A feature point tracking method based on the combination of SIFT algorithm and KLT matching algorithm[J]. Journal of Astronautics, 2011, 32(7):1618-1625.]

[2] 龔俊斌, 張大志, 楊雪梅,等. 抗旋轉(zhuǎn)和縮放的SAR與可見光圖像自動配準(zhǔn)算法[J]. 宇航學(xué)報, 2011, 32(6):1350-1358. [Gong Jun-bin, Zhang Da-zhi, Yang Xue-mei, et al. Automatic registration algorithm for SAR and optical image with rotation and scale invariability[J]. Journal of Astronautics, 2011, 32(6):1350-1358.]

[3] 王紅梅, 李言俊, 張科. 一種基于Contourlet變換的圖像匹配算法[J]. 宇航學(xué)報, 2008, 29(5):1643-1647. [Wang Hong-mei,Li Yan-jun,Zhang Ke.An image matching algorithm based on contourlet transform[J]. Journal of Astronautics, 2008, 29(5):1643-1647.]

[4] 張科, 王紅梅, 李言俊. 一種基于可操縱金字塔的魯棒圖像匹配算法[J]. 宇航學(xué)報, 2005, 26(6):717-721. [Zhang Ke, Wang Hong-mei, Li Yan-jun. A robust steerable pyramid-based image matching algorithm[J]. Journal of Astronautics, 2005, 26(6):717-721.]

[5] 李瑩, 葉培建, 彭兢,等. 火星探測出艙機(jī)構(gòu)的識別定位與坡度測量[J]. 宇航學(xué)報, 2016, 37(2):169-174. [Li Ying, Ye Pei-jian, Peng Jing, et al. Egress mechanism recognition and slope measurement for Mars exploration[J]. Journal of Astronautics, 2016, 37(2):169-174.]

[6] Ma W P, Wen Z L, Wu Y, et al. Remote sensing image registr-ation with modified SIFT and enhanced feature matching[J]. IEEE Geoscience & Remote Sensing Letters, 2016(99):1-5.

[7] 陳方, 熊智, 許允喜,等. 慣性組合導(dǎo)航系統(tǒng)中的快速景象匹配算法研究[J]. 宇航學(xué)報, 2009, 30(6):2308-2316. [Chen Fang, Xiong Zhi, Xu Yun-xi, et al. Research on the fast scene matchin algorithm in the inertial integrated navigation system[J]. Journal of Astronautics, 2009, 30(6):2308-2316.]

[8] Toshihiko M, Tatsuaki H, Keiken N. Optical guidance for autonomous landing of spacecraft[J]. IEEE Transaction on Aerospace and Electronic Systems, 1999, 35(2):459-473.

[9] 孫小煒, 李言俊, 陳義. 一種新的紅外目標(biāo)跟蹤方法[J]. 宇航學(xué)報, 2008, 29(5):1637-1642. [Sun Xiao-wei, Li Yan-jun, Chen Yi. A novel infrared object tracking method[J]. Journal of Astronautics, 2008, 29(5):1637-1642.]

[10] 郝剛濤, 杜小平, 宋建軍. 空間翻滾非合作目標(biāo)相對位姿估計的視覺SLAM方法[J]. 宇航學(xué)報, 2015, 36(6):706-714. [Hao Gang-tao, Du Xiao-ping, Song Jian-jun. Relative pose estimation of space tumbling non-cooperative target based on vision-only SLAM[J]. Journal of Astronautics, 2015, 36(6):706-714.]

[11] Lowe D G. Distinctive image features form scale invariant keypoints[J]. International Journal of Computer Vision, 2004,60(2): 91-110.

[12] Zhao Y, Zhai Y W, Dubois E, et al. Image matching algorithm based on SIFT using color and exposure information[J]. Journal of Systems Engineering and Electronics, 2016, 27(3):691-699.

[13] Abdelhakim A E, Farag A A. CSIFT: a SIFT descriptor with color invariant characteristics[C]. IEEE Conference on Computer Vision and Pattern Recognition,New York,USA,June 17-22,2006.

[14] Kwon O S, Ha Y H. Panoramic video using scale-invariant feature transform with embedded color-invariant values[J]. IEEE Transactions on Consumer Electronics, 2010, 56(2):792-798.

[15] Lee C, Rhee C E, Lee H J. Complexity reduction by modified scale-space construction in SIFT generation optimized for a mobile GPU[J]. IEEE Transactions on Circuits & Systems for Video Technology, 2016(99).

[16] Yao L F, Feng H, Zhu Y Q, et al. An architecture of optimised SIFT feature detection for an FPGA implementation of an image matcher[C]. International Conference on Field-Programmable Technology, Sydney,Australia,December 9-11,2010.

[17] Tola E, Lepetit V, Fua P. A fast local descriptor for dense matching[C]. IEEE Conference on Computer Vision and Pattern Recognition, Anchorage,USA,June 23-28,2008.

[18] Tola E, Lepetit V, Fua P. DAISY: an efficient dense descriptor applied to wide-baseline stereo[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2010, 32(5):815-830.

[19] Huang X S, Zhang J, Wu Q, et al. Dense correspondence using non-local DAISY forest[C]. International Conference on Digital Image Computing: Techniques and Applications (DICTA), Adelaide,Australia,November 23-25,2015.

[20] Velardo C, Dugelay J L. Face recognition with DAISY descriptors[C]. MM′10 and Sec′10, ACM SIGMM Multimedia and Security Workshop, Rome, Italy, September 9-10, 2010.

[21] Robotics Research Group. Affine covariant features[EB/OL].2007[2017].

[22] Cover T M, Hart P E. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory, 1967, 13(1)：21-27.

通信地址：北京航空航天大學(xué)自動化科學(xué)與電氣工程學(xué)院(100191)

電話：13161237733

E-mail:liheyu_umaa@163.com

A Real-Time SIFT Feature Extraction Algorithm

LI He-yu, WANG Qing

(1. School of Automation Science and Electrical Engineering, Beihang University, Beijing 100191, China)

In order to be implemented for real-time execution and use color information, an improved scale-invariant feature transform (SIFT) algorithm based on the contrast enhancement and DAISY descriptor is proposed in this paper. The color offset and the exposure offset of the pixel are calculated from the color image and the original grayscale image. The two offsets are added to the gray level to gain the contrast enhancing image according to which the SIFT feature points and the main directions are got. The DAISY descriptor of the feature point is obtained from the partial derivative values of the feature point and the sampling points with different directions. To evaluate the accuracy of the algorithm under different view changes, the feature points extracted from the standard image data sets are matched by the K-nearest neighbor (KNN) algorithm. The experimental results show that the algorithm can obtain more feature points. Furthermore, it guarantees the accuracy while reducing the time of the descriptor generating process and the feature matching process.

Scale-invariant feature transform (SIFT); Image matching; Contrast enhancement；DAISY descriptor

2017- 05- 03;

2017- 05-23

國家自然科學(xué)基金(61374012)

TP391

A

1000-1328(2017)08-0865-07

10.3873/j.issn.1000-1328.2017.08.011

李鶴宇(1993-)，男，碩士生，主要從事圖像處理、機(jī)器視覺的研究。