基于改進(jìn)SIFT描述子的快速匹配算法*

錢冬云

（浙江工貿(mào)職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院，浙江溫州325003）

基于改進(jìn)SIFT描述子的快速匹配算法*

錢冬云

（浙江工貿(mào)職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院，浙江溫州325003）

針對尺度不變特征變換（SIFT）算法中存在描述子維度高、特征點信息冗余和配準(zhǔn)運算量大等問題，提出一種改進(jìn)的ECF-SIFT（eightcircles features）算法。該算法通過高斯差分金字塔，確定特征點，并以環(huán)繞特征點的8個圓環(huán)為鄰域構(gòu)造64維的特征描述子，采用最近鄰與次近鄰之比對描述子進(jìn)行匹配，最后用RANSAC算法對匹配點進(jìn)行校正和消除誤匹配。實驗結(jié)果表明，在尺度縮放、尺度和旋轉(zhuǎn)組合、視角變化、模糊變化和光照變化等條件下，ECF-SIFT算法的性能保持不變，并壓縮了匹配時間，提高了匹配的準(zhǔn)確率，算法的整體性能優(yōu)于SIFT和SURF算法。

尺度不變特征變換；特征提?。惶卣髅枋鲎?；RANSAC算法；圖像配準(zhǔn)；算法效率

0　引言

圖像配準(zhǔn)是計算機(jī)視覺和數(shù)字圖像處理的重要組成部分。目前，圖像配準(zhǔn)已經(jīng)被廣泛應(yīng)用于目標(biāo)識別、目標(biāo)跟蹤、圖像組合和三維重建等許多領(lǐng)域。圖像配準(zhǔn)的方法以灰度相關(guān)匹配和特征點的匹配兩類為主。在灰度相關(guān)匹配方面，Moravec［1］提出角點特征，通過灰度自相關(guān)函數(shù)來考慮一個像素與其鄰域像素的相似性，但是Moravec角點對圖像間的亮度、尺度縮放等變化較為敏感，且計算復(fù)雜，不具備旋轉(zhuǎn)不變性，抗噪聲能力差等很多局限性［2］。目前大部分學(xué)者主要研究特征點的匹配算法。哥倫比亞大學(xué)的LOWEDG.［3］提出基于尺度不變特征的SIFT（scale invariant feature transform）算法。目前，SIFT算法被認(rèn)為是最穩(wěn)定的圖像配準(zhǔn)算法之一。SIFT算法使用128維的描述子，包含了豐富的信息量，使得SIFT算法對圖像的旋轉(zhuǎn)、尺度縮放和光照變化等都具有很好的魯棒性。當(dāng)圖像尺寸較大，檢測到特征點數(shù)目龐大時，使用128維的描述子，將出現(xiàn)配準(zhǔn)計算時間長，占用系統(tǒng)資源過多，且實時性較差等問題。因此，很多學(xué)者在SIFT算法的基礎(chǔ)上，提出了許多的改進(jìn)算法。KE Y提出PCA-SIFT算法［4］，在歸一化的梯度場中應(yīng)用主成分分析（Principal Component Analysis，PCA）算法，將描述子進(jìn)行降維處理，提高了算法的穩(wěn)定性，但是實時性和魯棒性有待提高；Bay［5］沿著LOWE的思路，提出了SUFT（Speeded-Up Robust Features）局部特征，SUFT描述子采用積分圖像，在矩形區(qū)域內(nèi)，利用Haar小波響應(yīng)，來統(tǒng)計特征矢量，最終形成64維描述子，避免在特征矢量生成時對圖像的重復(fù)計算，大幅度提高了匹配速度，但是其魯棒性有待進(jìn)一步提高；Mikolajczyk等［6］利用在環(huán)形區(qū)域內(nèi)，利用對數(shù)極坐標(biāo)同心圓GLOH（Gradient Location-Orientation Histogram），構(gòu)建272維的特征矢量，然后采用PCA技術(shù)進(jìn)行降維處理，降成128維，雖然提高算法的魯棒性，但是計算復(fù)雜度大大提高，其運算效率較差；朱利成等［7］提出基于卡爾波曼濾波的改進(jìn)的SIFT特征點匹配算法。由于卡爾波曼濾波的狀態(tài)估算，造成運算效率低，實時性差。

針對SIFT算法的128維特征向量表示的計算的復(fù)雜缺陷，本文提出ECF-SIFT（eight circles features，ECF）算法，通過高斯差分金字塔，以近似R=3σ的半徑，環(huán)繞特征點，劃分8個同心圓，構(gòu)成8個子環(huán)，然后計算每個子環(huán)內(nèi)的各元素在8個方向的梯度值累加，構(gòu)成64維的特征描述子，采用最近鄰與次近鄰之比來對64維描述子進(jìn)行匹配，最后用RANSAC算法對匹配點進(jìn)行校正和消除錯誤匹配。ECF-SIFT算法降低特征描述子的維度，降低特征點冗余和配準(zhǔn)的計算復(fù)雜度，提高了配準(zhǔn)的效率。

1　 SIFT算法

ECF-SIFT算法是一種基于SIFT算法的改進(jìn)圖像配準(zhǔn)算法。由LOWED.G在1999年提出SIFT算法，并與2004年進(jìn)行完善。SIFT算法是目前應(yīng)用最廣的特征檢測圖像匹配方法之一。SIFT算法主要包含幾個步驟：（1）構(gòu)建尺度空間；（2）確定關(guān)鍵點；（3）檢測特征點；（4）描述特征點，構(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)。

對于特征點的檢測，主要通過所在尺度空間所相鄰的兩個高斯尺度空間上的圖像相減，然后得到一個DoG（Difference of Gaussions）的響應(yīng)值圖像D（x，y，σ）。

其中，k為相鄰尺度空間倍數(shù)，如圖1所示。

圖1　高斯差分金字塔的生成

1.2關(guān)鍵點提取

關(guān)鍵點是由DoG空間的局部極值點。在同一組內(nèi)，通過與DoG相鄰兩層的圖像之間進(jìn)行比較，得到初步的關(guān)鍵點，如圖2所示。對于每個檢測點，要與同尺度的圍繞檢測點的8個相鄰點比較，還需與上下相鄰尺度對應(yīng)的9個點相比較，即與（8+9*2）共26個點比較，所以保證在尺度空間和二維的圖像空間都檢測到極值點。

圖2　DoG空間極值檢測

1.3特征點檢測

特征點檢測主要目的要剔除低對比度點和不穩(wěn)定的邊緣相應(yīng)點，以增強(qiáng)匹配的穩(wěn)定性。利用三維二次函數(shù)擬合，確定關(guān)鍵點的位置和尺度，同時去掉對比度低的關(guān)鍵點和不穩(wěn)定的邊緣點。對空間尺度函數(shù)（7）求導(dǎo)，并令其為0，得到精確的位置X?如式（8）和（9）。

在高斯空間中設(shè)定閾值去除對比度低的關(guān)鍵點，若|D（X?）|≥0.03，則該保留特征點，否則剔除。由于運算DoG算子會產(chǎn)生較強(qiáng)的邊緣響應(yīng)，對于不穩(wěn)定的邊緣點，可依據(jù)高斯差分算子的極值理論。一個橫跨邊緣的高斯差分算子有較大的主曲率，而垂直邊緣方向的高斯差分算子有較小的主曲率。主曲率通過一個2×2的Hessian矩陣求出，如式（10）所示。

其中，X的值（x，y，σ）T包含特征點的位置和尺度信息的向量。由于D的主曲率和Hessian矩陣H的特征值成正比，所以可將式簡化成為判斷不等式。其中，令α為最大特征值，β為最小特征值，則：

令α=γβ，則：

若式（14）成立，判斷為邊緣關(guān)鍵點，需剔除。

1.4特征點描述

1.4.1確定特征點的主方向

使用有限差分法，以關(guān)鍵點為中心，用radius為半徑的鄰域像素的梯度方向分為每個關(guān)鍵點的特征方向信息，梯度值m（x，y）和梯度方向（x，y），計算表達(dá)式分別為式（15）和式（16）。

通過直方圖統(tǒng)計關(guān)鍵點的鄰域像素梯度方向。將直方圖中的峰值表示該關(guān)鍵點的方向。

1.4.2特征點描述

以特征點為中心取8×8鄰域為采樣窗口來描述特征點。計算各塊內(nèi)的梯度直方圖，生成向量描述符。在4×4為采樣窗口的鄰域內(nèi)，計算每個領(lǐng)域的8個方向的梯度方向直方圖，然后累加每個梯度方向值，形成一個種子點，每個特征點就用4×4×8= 128維向量來表征，最后對特征向量歸一化消除光照的影響。

2　 ECF-SIFT算法的64維描述子的生成

ECF-SIFT算法在SIFT算法的基礎(chǔ)改進(jìn)特征點的描述子生成方式，采用64維描述子描述特征點；在特征點匹配時，增加使用RANSAC算法消除誤匹配點，提高配準(zhǔn)率。

由于圓環(huán)具有旋轉(zhuǎn)不變特性，因此ECF-SIFT算法利用圓環(huán)作為鄰域來構(gòu)建描述子，雖然省略了旋轉(zhuǎn)處理步驟，但自動具有旋轉(zhuǎn)不變特征。LOWE認(rèn)為在實際應(yīng)用中，采用3σ為半徑的鄰域的綜合效果最佳［1］，所以，ECF-SIFT算法采用與SIFT算法相同的鄰域進(jìn)行采樣。以特征點為中心，以radius為半徑，由式（17）得到，分別畫出8個同心圓，如圖3所示。在圖中以不同的顏色表示最里層圓和7個圓環(huán)，將鄰域劃分為8個子域，使得特征描述子具有旋轉(zhuǎn)不變特性。

其中，σoctave為特征點所在的組內(nèi)尺度。其中，當(dāng)n的值取1，繪制第1個圓；當(dāng)n的值取2，繪制第2個圓；以此類推，構(gòu)建8個同心圓，得到1個圓V［1］和7個圓環(huán)V［i］（i=2，3，4，5，5，6，7，8）來表達(dá)。

圖3　ECF-SIFT算法的特征描述子的示意圖

設(shè)特征點（x，y）在V［i］（i=1，2，3，4，5，6，7，8）子區(qū)域內(nèi)中像素點的個數(shù)為nrρ，然后統(tǒng)計在每個子環(huán)內(nèi)，對每個像素點在8個梯度方向的直方圖定義為式（18），計算其梯度值和梯度方向，然后對每個梯度幅值乘以權(quán)重參數(shù)，生成直方圖。

權(quán)重weight的計算如式（19）。

其中，xk和yk分別表示該像素點與特征點的列距離和行距離。

由式（18），按照i=1，2，3，4，5，6，7，8的順序，計算所有子域V［i］對于的統(tǒng)計直方圖組成一個特征向量Hi，其中的，同時將特征向量進(jìn)行歸一化處理，使得特征描述子對圖像光照保持不變的特征，將特征向量組合（8×8）在一起構(gòu)成特征描述子64維的描述子。

3　 ECF-SIFT特征點匹配

在匹配階段，對兩幅圖像中同一特征點的對應(yīng)位置進(jìn)行匹配。本文采用歐式距離作為相似性度量函數(shù)，即根據(jù)最近鄰域（Nearest Neighbor，NN）法來確定兩個相匹配的特征點，選擇可靠性高的匹配點對計算幾何約束模型，進(jìn)行精確匹配。由于旋轉(zhuǎn)、光照、圖像縮放和尺度變化等因素的影響，仍會存在部分的誤匹配點，所以利用RANSAC算法消除誤匹配。

Fischler和Bolles最先提出RANSAC（Random Sample Consensus）算法［8］。RANSAC算法中根據(jù)一組包含異常數(shù)據(jù)Outliers（偏離正常范圍較遠(yuǎn)、無法適應(yīng)數(shù)學(xué)模型的數(shù)據(jù)）的樣本數(shù)據(jù)集，計算出數(shù)據(jù)的數(shù)據(jù)模型參數(shù)，得到有效的樣本數(shù)據(jù)Inliers（可被模型描述的數(shù)據(jù)）的算法。本文使用RANSAC算法的基本思想描述如下。

（1）考慮一個最小的勢為n抽樣集模型和一個樣本集P。集合P的樣本數(shù)要求#（P）＞n。從匹配得到的結(jié)果集為樣本數(shù)據(jù)集P，從P中隨機(jī)選取4（n的值取4）對特征匹配對，構(gòu)成P的一個子集S，由式（20）和（21）得到相應(yīng)的變化模型參數(shù)矩陣H。

（2）計算剩余的特征點（P-4）對，經(jīng)過變化矩陣的坐標(biāo)值與它的匹配點之間的距離。

若小于設(shè)定的閾值T，則認(rèn)為是內(nèi)點，否則為外點。

（3）內(nèi)點構(gòu)成的集合S’為S的一致集。若一致集S中匹配點數(shù)目大于4，則使用最小二乘法重新計算新的模型H’，重新抽取4組，重復(fù)（1）到（3）步驟。

（4）在完成指定的抽取次數(shù)后，如果查找一致集算法失效，則選取在抽取后得到的最大一致集內(nèi)判斷內(nèi)外點，最后算法結(jié)束得到最終結(jié)果。

4　實驗與結(jié)果分析

為了驗證ECF-SIFT算法使用描述子的有效性，將ECF-SIFT算法與傳統(tǒng)的SIFT算法、SURF算法性能對比實驗。實驗仿真平臺的硬件環(huán)境為：Intel（R）Core（TM）i5-337U CPU@1.80GHz，內(nèi)存為4.0GB；軟件Windows7操作系統(tǒng)，實驗所采用的圖片來自Mikolajczyk05標(biāo)準(zhǔn)數(shù)據(jù)集（http://www.robots.ox.ac.uk/～vgg/research/affine/）及實拍圖像。

實驗采用圖像數(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算法實驗匹配效果如圖4-圖8所示，從圖中可以看出ECF-SIFT算法在尺度縮放、尺度和旋轉(zhuǎn)組合、視角變化和模糊變化和光照變化等都有較好的配準(zhǔn)效果。

圖4　尺度縮放

圖5　尺度和旋轉(zhuǎn)組合

圖6　視角變化

圖7　模糊變化

圖8　光照變化

現(xiàn)采用平均匹配時間和平均匹配準(zhǔn)確率來驗證算法性能，圖9和圖10所示為性能實驗的結(jié)果。對于時間曲線圖來說，曲線與坐標(biāo)軸之間的面積應(yīng)當(dāng)越小，效果越理想。從圖9看出，ECF-SIFT算法在配準(zhǔn)平均時間與SIFT算法相比約提升了75%左右；ECF-SIFT算法與SURF算法相比提升約45%。由于ECF-SIFT算法采用64維描述子，降低描述子生成的復(fù)雜度和冗余性，減少特征點的數(shù)目，縮短特征點配準(zhǔn)的時間，實現(xiàn)了整體算法的快速匹配。匹配準(zhǔn)確率的定義為正確匹配點數(shù)與所有匹配數(shù)之比。對于匹配準(zhǔn)確率曲線圖來說，曲線與坐標(biāo)軸之間的面積應(yīng)當(dāng)越大，效果越理想。由圖10得ECF-SIFT算法匹配準(zhǔn)確性超過SIFT算法和SURF算法。從總體曲線構(gòu)成的面積，ECF-SIFT算法與SIFT算法的準(zhǔn)確率在同一級別上。由于SIFT算法采用128維描述子，而ECF-SIFT算法采用64維描述子。SIFT算法描述子包含大量冗余信息，雖然匹配正確率略有提升，但是匹配計算時間過長。從總體而言，ECF-SIFT算法超過傳統(tǒng)的SIFT算法和SURF算法。

圖9　平均匹配時間對比

圖10　平均匹配準(zhǔn)確率對比

5　結(jié)束語

本文提出的ECF-SIFT算法降低描述子的生成復(fù)雜度，提高了算法的穩(wěn)定性；并對特征向量進(jìn)行歸一化處理，消除光照的敏感性；使用RANSAC算法消除誤匹配點，提高了配準(zhǔn)的準(zhǔn)確率，增強(qiáng)算法的魯棒性。實驗結(jié)果表明，ECF-SIFT算法對圖像處理的旋轉(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］畢國玲，趙建，續(xù)志軍，等.基于角點和局部特征描述子的快速匹配算法［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)匹配和識別［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é)報:自然科學(xué)版，2012，38（6）:747-751.

［11］劉輝，申海龍.一種基于改進(jìn)SIFT算法的圖像配準(zhǔn)方法［J］.微電子學(xué)與計算機(jī)，2014（01）:38-42.

［12］?？?，郝向陽，劉松林.一種改進(jìn)的SIFT特征提取算法［J］.測繪科學(xué)技術(shù)學(xué)報，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é)校訪問學(xué)者教師專業(yè)發(fā)展項目（FX2014177）；2014年度全國教育信息技術(shù)研究規(guī)劃項目（146231964）；2014年度溫州市科技計劃項目（R20140090）

錢冬云，碩士，浙江工貿(mào)職業(yè)技術(shù)學(xué)院副教授，主要研究方向：圖像分析、模式識別。