錢冬云
(浙江工貿(mào)職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院,浙江溫州325003)
基于改進(jìn)SIFT描述子的快速匹配算法*
錢冬云
(浙江工貿(mào)職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院,浙江溫州325003)
針對(duì)尺度不變特征變換(SIFT)算法中存在描述子維度高、特征點(diǎn)信息冗余和配準(zhǔn)運(yùn)算量大等問(wèn)題,提出一種改進(jìn)的ECF-SIFT(eightcircles features)算法。該算法通過(guò)高斯差分金字塔,確定特征點(diǎn),并以環(huán)繞特征點(diǎn)的8個(gè)圓環(huán)為鄰域構(gòu)造64維的特征描述子,采用最近鄰與次近鄰之比對(duì)描述子進(jìn)行匹配,最后用RANSAC算法對(duì)匹配點(diǎn)進(jìn)行校正和消除誤匹配。實(shí)驗(yàn)結(jié)果表明,在尺度縮放、尺度和旋轉(zhuǎn)組合、視角變化、模糊變化和光照變化等條件下,ECF-SIFT算法的性能保持不變,并壓縮了匹配時(shí)間,提高了匹配的準(zhǔn)確率,算法的整體性能優(yōu)于SIFT和SURF算法。
尺度不變特征變換;特征提??;特征描述子;RANSAC算法;圖像配準(zhǔn);算法效率
圖像配準(zhǔn)是計(jì)算機(jī)視覺(jué)和數(shù)字圖像處理的重要組成部分。目前,圖像配準(zhǔn)已經(jīng)被廣泛應(yīng)用于目標(biāo)識(shí)別、目標(biāo)跟蹤、圖像組合和三維重建等許多領(lǐng)域。圖像配準(zhǔn)的方法以灰度相關(guān)匹配和特征點(diǎn)的匹配兩類為主。在灰度相關(guān)匹配方面,Moravec[1]提出角點(diǎn)特征,通過(guò)灰度自相關(guān)函數(shù)來(lái)考慮一個(gè)像素與其鄰域像素的相似性,但是Moravec角點(diǎn)對(duì)圖像間的亮度、尺度縮放等變化較為敏感,且計(jì)算復(fù)雜,不具備旋轉(zhuǎn)不變性,抗噪聲能力差等很多局限性[2]。目前大部分學(xué)者主要研究特征點(diǎn)的匹配算法。哥倫比亞大學(xué)的LOWEDG.[3]提出基于尺度不變特征的SIFT(scale invariant feature transform)算法。目前,SIFT算法被認(rèn)為是最穩(wěn)定的圖像配準(zhǔn)算法之一。SIFT算法使用128維的描述子,包含了豐富的信息量,使得SIFT算法對(duì)圖像的旋轉(zhuǎn)、尺度縮放和光照變化等都具有很好的魯棒性。當(dāng)圖像尺寸較大,檢測(cè)到特征點(diǎn)數(shù)目龐大時(shí),使用128維的描述子,將出現(xiàn)配準(zhǔn)計(jì)算時(shí)間長(zhǎng),占用系統(tǒng)資源過(guò)多,且實(shí)時(shí)性較差等問(wèn)題。因此,很多學(xué)者在SIFT算法的基礎(chǔ)上,提出了許多的改進(jìn)算法。KE Y提出PCA-SIFT算法[4],在歸一化的梯度場(chǎng)中應(yīng)用主成分分析(Principal Component Analysis,PCA)算法,將描述子進(jìn)行降維處理,提高了算法的穩(wěn)定性,但是實(shí)時(shí)性和魯棒性有待提高;Bay[5]沿著LOWE的思路,提出了SUFT(Speeded-Up Robust Features)局部特征,SUFT描述子采用積分圖像,在矩形區(qū)域內(nèi),利用Haar小波響應(yīng),來(lái)統(tǒng)計(jì)特征矢量,最終形成64維描述子,避免在特征矢量生成時(shí)對(duì)圖像的重復(fù)計(jì)算,大幅度提高了匹配速度,但是其魯棒性有待進(jìn)一步提高;Mikolajczyk等[6]利用在環(huán)形區(qū)域內(nèi),利用對(duì)數(shù)極坐標(biāo)同心圓GLOH(Gradient Location-Orientation Histogram),構(gòu)建272維的特征矢量,然后采用PCA技術(shù)進(jìn)行降維處理,降成128維,雖然提高算法的魯棒性,但是計(jì)算復(fù)雜度大大提高,其運(yùn)算效率較差;朱利成等[7]提出基于卡爾波曼濾波的改進(jìn)的SIFT特征點(diǎn)匹配算法。由于卡爾波曼濾波的狀態(tài)估算,造成運(yùn)算效率低,實(shí)時(shí)性差。
針對(duì)SIFT算法的128維特征向量表示的計(jì)算的復(fù)雜缺陷,本文提出ECF-SIFT(eight circles features,ECF)算法,通過(guò)高斯差分金字塔,以近似R=3σ的半徑,環(huán)繞特征點(diǎn),劃分8個(gè)同心圓,構(gòu)成8個(gè)子環(huán),然后計(jì)算每個(gè)子環(huán)內(nèi)的各元素在8個(gè)方向的梯度值累加,構(gòu)成64維的特征描述子,采用最近鄰與次近鄰之比來(lái)對(duì)64維描述子進(jìn)行匹配,最后用RANSAC算法對(duì)匹配點(diǎn)進(jìn)行校正和消除錯(cuò)誤匹配。ECF-SIFT算法降低特征描述子的維度,降低特征點(diǎn)冗余和配準(zhǔn)的計(jì)算復(fù)雜度,提高了配準(zhǔn)的效率。
ECF-SIFT算法是一種基于SIFT算法的改進(jìn)圖像配準(zhǔn)算法。由LOWED.G在1999年提出SIFT算法,并與2004年進(jìn)行完善。SIFT算法是目前應(yīng)用最廣的特征檢測(cè)圖像匹配方法之一。SIFT算法主要包含幾個(gè)步驟:(1)構(gòu)建尺度空間;(2)確定關(guān)鍵點(diǎn);(3)檢測(cè)特征點(diǎn);(4)描述特征點(diǎn),構(gòu)成特征向量;(5)匹配特征向量。
1.1構(gòu)建尺度空間
一幅二維圖像的尺度空間L(x,y,σ)函數(shù)表示,如式(1)所示,由不變尺度的高斯函數(shù)G(x,y,σ)與圖像的I(x,y)卷積產(chǎn)生的函數(shù)表示。
其中,G(x,y,σ)是尺度可變的高斯函數(shù);I(x,y)表示為輸入圖像,表示在x和y方向上進(jìn)行卷積操作;σ為尺度因子;G(x,y,σ)的值如式(2)。
LOWE還給出了各尺度空間的σ的變化值,如式(3)。
其中,σ∈R+,o∈Z,s∈N。σ0是基準(zhǔn)層尺度,o為組(Octave)的坐標(biāo),s為層(Level)坐標(biāo)。
對(duì)于特征點(diǎn)的檢測(cè),主要通過(guò)所在尺度空間所相鄰的兩個(gè)高斯尺度空間上的圖像相減,然后得到一個(gè)DoG(Difference of Gaussions)的響應(yīng)值圖像D(x,y,σ)。
其中,k為相鄰尺度空間倍數(shù),如圖1所示。
圖1 高斯差分金字塔的生成
1.2關(guān)鍵點(diǎn)提取
關(guān)鍵點(diǎn)是由DoG空間的局部極值點(diǎn)。在同一組內(nèi),通過(guò)與DoG相鄰兩層的圖像之間進(jìn)行比較,得到初步的關(guān)鍵點(diǎn),如圖2所示。對(duì)于每個(gè)檢測(cè)點(diǎn),要與同尺度的圍繞檢測(cè)點(diǎn)的8個(gè)相鄰點(diǎn)比較,還需與上下相鄰尺度對(duì)應(yīng)的9個(gè)點(diǎn)相比較,即與(8+9*2)共26個(gè)點(diǎn)比較,所以保證在尺度空間和二維的圖像空間都檢測(cè)到極值點(diǎn)。
圖2 DoG空間極值檢測(cè)
1.3特征點(diǎn)檢測(cè)
特征點(diǎn)檢測(cè)主要目的要剔除低對(duì)比度點(diǎn)和不穩(wěn)定的邊緣相應(yīng)點(diǎn),以增強(qiáng)匹配的穩(wěn)定性。利用三維二次函數(shù)擬合,確定關(guān)鍵點(diǎn)的位置和尺度,同時(shí)去掉對(duì)比度低的關(guān)鍵點(diǎn)和不穩(wěn)定的邊緣點(diǎn)。對(duì)空間尺度函數(shù)(7)求導(dǎo),并令其為0,得到精確的位置X?如式(8)和(9)。
在高斯空間中設(shè)定閾值去除對(duì)比度低的關(guān)鍵點(diǎn),若|D(X?)|≥0.03,則該保留特征點(diǎn),否則剔除。由于運(yùn)算DoG算子會(huì)產(chǎn)生較強(qiáng)的邊緣響應(yīng),對(duì)于不穩(wěn)定的邊緣點(diǎn),可依據(jù)高斯差分算子的極值理論。一個(gè)橫跨邊緣的高斯差分算子有較大的主曲率,而垂直邊緣方向的高斯差分算子有較小的主曲率。主曲率通過(guò)一個(gè)2×2的Hessian矩陣求出,如式(10)所示。
其中,X的值(x,y,σ)T包含特征點(diǎn)的位置和尺度信息的向量。由于D的主曲率和Hessian矩陣H的特征值成正比,所以可將式簡(jiǎn)化成為判斷不等式。其中,令α為最大特征值,β為最小特征值,則:
令α=γβ,則:
若式(14)成立,判斷為邊緣關(guān)鍵點(diǎn),需剔除。
1.4特征點(diǎn)描述
1.4.1確定特征點(diǎn)的主方向
使用有限差分法,以關(guān)鍵點(diǎn)為中心,用radius為半徑的鄰域像素的梯度方向分為每個(gè)關(guān)鍵點(diǎn)的特征方向信息,梯度值m(x,y)和梯度方向(x,y),計(jì)算表達(dá)式分別為式(15)和式(16)。
通過(guò)直方圖統(tǒng)計(jì)關(guān)鍵點(diǎn)的鄰域像素梯度方向。將直方圖中的峰值表示該關(guān)鍵點(diǎn)的方向。
1.4.2特征點(diǎn)描述
以特征點(diǎn)為中心取8×8鄰域?yàn)椴蓸哟翱趤?lái)描述特征點(diǎn)。計(jì)算各塊內(nèi)的梯度直方圖,生成向量描述符。在4×4為采樣窗口的鄰域內(nèi),計(jì)算每個(gè)領(lǐng)域的8個(gè)方向的梯度方向直方圖,然后累加每個(gè)梯度方向值,形成一個(gè)種子點(diǎn),每個(gè)特征點(diǎn)就用4×4×8= 128維向量來(lái)表征,最后對(duì)特征向量歸一化消除光照的影響。
ECF-SIFT算法在SIFT算法的基礎(chǔ)改進(jìn)特征點(diǎn)的描述子生成方式,采用64維描述子描述特征點(diǎn);在特征點(diǎn)匹配時(shí),增加使用RANSAC算法消除誤匹配點(diǎn),提高配準(zhǔn)率。
由于圓環(huán)具有旋轉(zhuǎn)不變特性,因此ECF-SIFT算法利用圓環(huán)作為鄰域來(lái)構(gòu)建描述子,雖然省略了旋轉(zhuǎn)處理步驟,但自動(dòng)具有旋轉(zhuǎn)不變特征。LOWE認(rèn)為在實(shí)際應(yīng)用中,采用3σ為半徑的鄰域的綜合效果最佳[1],所以,ECF-SIFT算法采用與SIFT算法相同的鄰域進(jìn)行采樣。以特征點(diǎn)為中心,以radius為半徑,由式(17)得到,分別畫出8個(gè)同心圓,如圖3所示。在圖中以不同的顏色表示最里層圓和7個(gè)圓環(huán),將鄰域劃分為8個(gè)子域,使得特征描述子具有旋轉(zhuǎn)不變特性。
其中,σoctave為特征點(diǎn)所在的組內(nèi)尺度。其中,當(dāng)n的值取1,繪制第1個(gè)圓;當(dāng)n的值取2,繪制第2個(gè)圓;以此類推,構(gòu)建8個(gè)同心圓,得到1個(gè)圓V[1]和7個(gè)圓環(huán)V[i](i=2,3,4,5,5,6,7,8)來(lái)表達(dá)。
圖3 ECF-SIFT算法的特征描述子的示意圖
設(shè)特征點(diǎn)(x,y)在V[i](i=1,2,3,4,5,6,7,8)子區(qū)域內(nèi)中像素點(diǎn)的個(gè)數(shù)為nrρ,然后統(tǒng)計(jì)在每個(gè)子環(huán)內(nèi),對(duì)每個(gè)像素點(diǎn)在8個(gè)梯度方向的直方圖定義為式(18),計(jì)算其梯度值和梯度方向,然后對(duì)每個(gè)梯度幅值乘以權(quán)重參數(shù),生成直方圖。
權(quán)重weight的計(jì)算如式(19)。
其中,xk和yk分別表示該像素點(diǎn)與特征點(diǎn)的列距離和行距離。
由式(18),按照i=1,2,3,4,5,6,7,8的順序,計(jì)算所有子域V[i]對(duì)于的統(tǒng)計(jì)直方圖組成一個(gè)特征向量Hi,其中的,同時(shí)將特征向量進(jìn)行歸一化處理,使得特征描述子對(duì)圖像光照保持不變的特征,將特征向量組合(8×8)在一起構(gòu)成特征描述子64維的描述子。
在匹配階段,對(duì)兩幅圖像中同一特征點(diǎn)的對(duì)應(yīng)位置進(jìn)行匹配。本文采用歐式距離作為相似性度量函數(shù),即根據(jù)最近鄰域(Nearest Neighbor,NN)法來(lái)確定兩個(gè)相匹配的特征點(diǎn),選擇可靠性高的匹配點(diǎn)對(duì)計(jì)算幾何約束模型,進(jìn)行精確匹配。由于旋轉(zhuǎn)、光照、圖像縮放和尺度變化等因素的影響,仍會(huì)存在部分的誤匹配點(diǎn),所以利用RANSAC算法消除誤匹配。
Fischler和Bolles最先提出RANSAC(Random Sample Consensus)算法[8]。RANSAC算法中根據(jù)一組包含異常數(shù)據(jù)Outliers(偏離正常范圍較遠(yuǎn)、無(wú)法適應(yīng)數(shù)學(xué)模型的數(shù)據(jù))的樣本數(shù)據(jù)集,計(jì)算出數(shù)據(jù)的數(shù)據(jù)模型參數(shù),得到有效的樣本數(shù)據(jù)Inliers(可被模型描述的數(shù)據(jù))的算法。本文使用RANSAC算法的基本思想描述如下。
(1)考慮一個(gè)最小的勢(shì)為n抽樣集模型和一個(gè)樣本集P。集合P的樣本數(shù)要求#(P)>n。從匹配得到的結(jié)果集為樣本數(shù)據(jù)集P,從P中隨機(jī)選取4(n的值取4)對(duì)特征匹配對(duì),構(gòu)成P的一個(gè)子集S,由式(20)和(21)得到相應(yīng)的變化模型參數(shù)矩陣H。
(2)計(jì)算剩余的特征點(diǎn)(P-4)對(duì),經(jīng)過(guò)變化矩陣的坐標(biāo)值與它的匹配點(diǎn)之間的距離。
若小于設(shè)定的閾值T,則認(rèn)為是內(nèi)點(diǎn),否則為外點(diǎn)。
(3)內(nèi)點(diǎn)構(gòu)成的集合S’為S的一致集。若一致集S中匹配點(diǎn)數(shù)目大于4,則使用最小二乘法重新計(jì)算新的模型H’,重新抽取4組,重復(fù)(1)到(3)步驟。
(4)在完成指定的抽取次數(shù)后,如果查找一致集算法失效,則選取在抽取后得到的最大一致集內(nèi)判斷內(nèi)外點(diǎn),最后算法結(jié)束得到最終結(jié)果。
為了驗(yàn)證ECF-SIFT算法使用描述子的有效性,將ECF-SIFT算法與傳統(tǒng)的SIFT算法、SURF算法性能對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)仿真平臺(tái)的硬件環(huán)境為:Intel(R)Core(TM)i5-337U CPU@1.80GHz,內(nèi)存為4.0GB;軟件Windows7操作系統(tǒng),實(shí)驗(yàn)所采用的圖片來(lái)自Mikolajczyk05標(biāo)準(zhǔn)數(shù)據(jù)集(http://www.robots.ox.ac.uk/~vgg/research/affine/)及實(shí)拍圖像。
實(shí)驗(yàn)采用圖像數(shù)據(jù)如圖4到圖8的5組圖像所示。其中,圖4為一組尺度縮放圖,左側(cè)的圖片大小為384×256,右側(cè)的圖片大小為320×213;圖5為一組尺度和旋轉(zhuǎn)組合圖片,圖片大小均為850× 680;圖6為一組視角變化圖片,左側(cè)的圖片為1000×700,右側(cè)的圖片大小為880×680;圖7為模糊變化的圖片,圖片大小均為1000×700;圖8為一組光照變化圖片,圖片大小均為900×600。ECF-SIFT算法實(shí)驗(yàn)匹配效果如圖4-圖8所示,從圖中可以看出ECF-SIFT算法在尺度縮放、尺度和旋轉(zhuǎn)組合、視角變化和模糊變化和光照變化等都有較好的配準(zhǔn)效果。
圖4 尺度縮放
圖5 尺度和旋轉(zhuǎn)組合
圖6 視角變化
圖7 模糊變化
圖8 光照變化
現(xiàn)采用平均匹配時(shí)間和平均匹配準(zhǔn)確率來(lái)驗(yàn)證算法性能,圖9和圖10所示為性能實(shí)驗(yàn)的結(jié)果。對(duì)于時(shí)間曲線圖來(lái)說(shuō),曲線與坐標(biāo)軸之間的面積應(yīng)當(dāng)越小,效果越理想。從圖9看出,ECF-SIFT算法在配準(zhǔn)平均時(shí)間與SIFT算法相比約提升了75%左右;ECF-SIFT算法與SURF算法相比提升約45%。由于ECF-SIFT算法采用64維描述子,降低描述子生成的復(fù)雜度和冗余性,減少特征點(diǎn)的數(shù)目,縮短特征點(diǎn)配準(zhǔn)的時(shí)間,實(shí)現(xiàn)了整體算法的快速匹配。匹配準(zhǔn)確率的定義為正確匹配點(diǎn)數(shù)與所有匹配數(shù)之比。對(duì)于匹配準(zhǔn)確率曲線圖來(lái)說(shuō),曲線與坐標(biāo)軸之間的面積應(yīng)當(dāng)越大,效果越理想。由圖10得ECF-SIFT算法匹配準(zhǔn)確性超過(guò)SIFT算法和SURF算法。從總體曲線構(gòu)成的面積,ECF-SIFT算法與SIFT算法的準(zhǔn)確率在同一級(jí)別上。由于SIFT算法采用128維描述子,而ECF-SIFT算法采用64維描述子。SIFT算法描述子包含大量冗余信息,雖然匹配正確率略有提升,但是匹配計(jì)算時(shí)間過(guò)長(zhǎng)。從總體而言,ECF-SIFT算法超過(guò)傳統(tǒng)的SIFT算法和SURF算法。
圖9 平均匹配時(shí)間對(duì)比
圖10 平均匹配準(zhǔn)確率對(duì)比
本文提出的ECF-SIFT算法降低描述子的生成復(fù)雜度,提高了算法的穩(wěn)定性;并對(duì)特征向量進(jìn)行歸一化處理,消除光照的敏感性;使用RANSAC算法消除誤匹配點(diǎn),提高了配準(zhǔn)的準(zhǔn)確率,增強(qiáng)算法的魯棒性。實(shí)驗(yàn)結(jié)果表明,ECF-SIFT算法對(duì)圖像處理的旋轉(zhuǎn)、尺度縮放、光照、模糊、視角變化具有很強(qiáng)的魯棒性,并且提高了圖像配準(zhǔn)的準(zhǔn)確度、快速性。因此,ECF-SIFT算法能廣泛地應(yīng)用在模式匹配領(lǐng)域。
[1]Moravec H P.TOWARDSAUTOMATIC VISUAL BBSTACLE AVOIDANCE[C]//International Conference on Artificial Intelligence(5th:1977:Massachusetts InstituteofTechnology).1977.
[2]畢國(guó)玲,趙建,續(xù)志軍,等.基于角點(diǎn)和局部特征描述子的快速匹配算法[J].光電工程,2014,41(9):63-68.
[3]Lowe D G.Object recognition from local scale-invariant features[C]//Computer vision,1999.The proceedingsof the seventh IEEE international conferenceon.Ieee,1999,2:1150-1157.
[4]Lowe DG.Distinctive image features from scale-invariantkeypoints[J].International journalof computer vision,2004,60(2):91-110.
[5]Ke Y,Sukthankar R.PCA-SIFT:Amore distinctive representation for local image descriptors[C]//Computer Vision and Pattern Recognition,2004.CVPR 2004.Proceedingsof the2004 IEEEComputer Society Conferenceon.IEEE,2004,2:II-506-II-513 Vol.2.
[6]Bay H,Tuytelaars T,Van Gool L.Surf:Speeded up robust features[M]//Computer Vision-ECCV 2006.Springer Berlin Heidelberg,2006:404-417.
[7]Mikolajczyk K,Schmid C.An affine invariant interest point detector[M]//Computer Vision—ECCV 2002.Springer Berlin Heidelberg,2002:128-142.
[8]朱利成,姚明海.基于SIFT算法的目標(biāo)匹配和識(shí)別[J].機(jī)電工程,2009,26(12):73-74.
[9]Fischler M A,Bolles R C.Random sample consensus:a paradigm formodel fitting with applications to image analysis and automated cartography[J].Communicationsof the ACM,1981,24(6):381-395.
[10]常青,張斌,邵金玲.基于SIFT和RANSAC的特征圖像匹配方法[J].華東理工大學(xué)學(xué)報(bào):自然科學(xué)版,2012,38(6):747-751.
[11]劉輝,申海龍.一種基于改進(jìn)SIFT算法的圖像配準(zhǔn)方法[J].微電子學(xué)與計(jì)算機(jī),2014(01):38-42.
[12]??ィ孪蜿?yáng),劉松林.一種改進(jìn)的SIFT特征提取算法[J].測(cè)繪科學(xué)技術(shù)學(xué)報(bào),2014(02):173-176.
(責(zé)任編輯:潘修強(qiáng))
A FastMatching Algorithm Based on Im proved SIFT Feature Descriptor
QIAN Dong-yun
(Collegeof Information and Communications,Zhejiang Industry&Trade VocationalCollege,Wenzhou,325003,China)
An eight-circle-feature based scale invariant feature transform(ECF-SIFT)algorithm was developed to hurdle the problemsof the redundant feature point,large computation,and thehigh dimensionality of the scale invariant feature transform(SIFT)algorithm.The feature pointswere firstly determ ined by the difference of Gaussian.By utilizing eight concentric circlesaround the feature points,the 64-dimensional feature descriptors were created.The ratio of the first and the second closest distance was used to match the 64-dimesional vectors.Finally,thematching pointswere corrected by the RANSAC method to further remove the false matching.The ECF-SIFT algorithm demonstrated the invariance ofmatching performance for rotation,scale scaling,the changes of illum ination changes and smaller viewpoint,aswell as the blur,which is superior to the SIFT algorithm and SURF algorithm w ith the higherefficiency and betteraccuracy in imagematching.
scale invariant feature transform;feature extraction;feature descriptor;RANSAC algorithm;imagesmatching;algorithm efficiency
TP391.41
A
1672-0105(2015)03-0051-06
10.3969/j.issn.1672-0105.2015.03.012
2015-02-27
2014年度浙江省高等學(xué)校訪問(wèn)學(xué)者教師專業(yè)發(fā)展項(xiàng)目(FX2014177);2014年度全國(guó)教育信息技術(shù)研究規(guī)劃項(xiàng)目(146231964);2014年度溫州市科技計(jì)劃項(xiàng)目(R20140090)
錢冬云,碩士,浙江工貿(mào)職業(yè)技術(shù)學(xué)院副教授,主要研究方向:圖像分析、模式識(shí)別。
浙江工貿(mào)職業(yè)技術(shù)學(xué)院學(xué)報(bào)2015年3期