一種改進的基于SIFT特征的快速匹配算法

唐紅梅，張 恒，高金雍，王 霞，韓力英

(河北工業大學，天津 300401)

責任編輯:時 雯

圖像匹配就是通過對圖像內容、特征、結構、紋理及灰度等對應關系、相似性和一致性進行分析，尋求相同圖像目標的方法。目前，圖像匹配技術被廣泛應用于醫學、生物、軍事、遙感和航空航天等領域，是圖像處理應用中不可或缺的技術。

基于SIFT(Scale Invariant Feature Transform)的匹配算法［1］是一種穩定的特征匹配算法。SIFT特征是圖像的局部特征，對旋轉、尺度縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩定性，具有良好的獨特性、多量性及可擴展性。該算法在同類特征匹配算法中速度較快，但對于某些實時性要求較高的場合(如汽車匹配導航)，則無法滿足要求。

由于SIFT匹配算法復雜度高，尤其生成的特征向量是128維，使得算法效率受到影響。針對效率上的不足，不少國內外研究學者做了不同的改進，這些改進主要集中在以下幾個方面:在對SIFT描述簡化上，如Mikolajczyk提出的GLOH(Gradient Location and Orientation Histogram)［2］及劉力等提出的 SSIFT 算法［3］;在降低 SIFT 向量維數上，如 Ke提出的 PCA－SIFT［4］，馬莉、韓燮將 PCASIFT技術應用在圖像匹配中［5］，趙啟兵等提出為同心圓環劃分特征點鄰域的改進算法［6］;在尺度空間簡化構造上，如張羽等提出的基于DoM空間的SIFT改進算法［7］，呂冀等基于Zoser金字塔的改進算法［8］;在與其他算法結合上，如鄭永斌等的SIFT和旋轉不變LBP相結合的匹配算法［9］。然而這些算法在提高算法效率的同時，造成了算法精度和魯棒性的下降。

本文提出了一種改進的基于SIFT特征的快速匹配算法，改進算法首先使用D2OG算子［10］的過零檢測來生成特征向量，并針對此時可能導致匹配精度下降的問題，使用改進的RANSAC(Random Sample Consensus)算法對匹配點對進行二次消除錯配。改進算法用過零點檢測極值點代替經典算法的局部極值點檢測，在保證了精度的同時，提高了SIFT匹配算法的實時性。

1 基于SIFT的匹配算法原理

SIFT匹配算法主要有3個步驟:特征點的檢測;特征向量的生成;特征向量的匹配。

1.1 特征點的檢測

高斯核被證明為唯一的可以用來產生尺度空間的線性卷積核。特征點檢測是在高斯差分尺度空間DOG(Difference of Gaussian)上進行的，DOG是由不同尺度高斯核與圖像卷積構造圖像的尺度空間函數相鄰層相減得到，即

如圖1所示，為了得到局部極值點，每組除底層和頂層的圖像，其他同組圖像的每個像素點都要進行檢測，具體做法是每個待檢測像素點跟同層相鄰的8個像素點及其上一層和下一層相鄰的各9個像素點總共26個像素點相比較，若其比較結果都大于或都小于這26個像素點，則該點被看作一個空間局部極值點，并記錄該點所在的位置和尺度。對檢測到的初始極值點進行三維二次函數曲線擬合以及一個2×2的Hessian矩陣來去除低對比度以及邊緣響應點，以精確極值點的位置和尺度。利用鄰域像素梯度方向分布統計特性作為每一個特征點指定方向參數，以確保算子的旋轉不變性。至此提取的特征點具有位置、尺度、方向三個參數，且具有尺度和旋轉不變性。

圖1 DOG金字塔的構造及局部極值點檢測

1.2 特征向量的生成

用特征描述符對特征點進行描述，增加特征點的穩定性與獨特性，使其對亮度、視角等變化保持不變，最終形成128維的特征向量。

1.3 特征向量的匹配

算法采用優先k－d樹近似的BBF(Best Bin First)搜索算法快速搜索每個特征點的最近鄰與次近鄰，并計算它們的比值進行匹配，最后利用RANSAC算法消除錯配。

2 改進的SIFT特征匹配算法

在特征點檢測的過程中，LOG與DOG的構造占據80%左右的時間，簡化金字塔結構、簡化特征點檢測方法，可以有效減少檢測時間，提高算法運行速度。文獻［10］結合幾何學理論，提出了基于D2OG的特征點檢測算子。然而該算法在提高速度的同時，匹配精度有所下降，為此本文先用D2OG進行極值點檢測，然后采用改進的RANSAC算法來確保匹配的精度。這樣在保證算法精度的同時達到了提高算法速度的目的。

2.1 基于D2OG的過零檢測

2.1.1 D2OG過零檢測的理論依據

根據平面幾何學理論，原函數的極值點就是該函數一階導數等于零的點。由此可見，經典算法在DOG金字塔中檢測的局部極值點對應于DOG函數的一階導數的過零點。

對DOG進行一次差分運算得到D2OG函數，即

式中，D2(x，y，σ)為高斯二階差分函數。

由于

則

且 kσ － σ ≠0 ，故可知:D2(x，y，σ)=0?=0可見，D2OG函數的過零點就是DOG函數一階導數為零的點，也就是DOG的局部極值點。

2.1.2 D2OG 特征檢測過程

D2OG金字塔構建如圖2所示。

圖2 D2OG金字塔構造過程

同DOG構建相同，每一組的DOG相鄰層相減得到一層D2OG圖像，該層的尺度為DOG層中減數的尺度。可見，D2OG金字塔擁有相同的組數，但每組層數比DOG少一層。

在D2OG每層中檢測零點時需要設一個閾值T，對每一層的絕對值與T進行比較，小于等于T的像素點作為特征點，記錄該點的信息(x，y，σ)。閾值T的選擇是關鍵，過大或過小都可能會影響匹配的精度，還會帶來程序運行時間的增加。考慮算法精度和速度兩個因素，T在［200，500］內可實現較好的折中。精確定位時，為了獲得亞像素級精度，需要將D2OG中檢測到的特征點映射回DOG空間中。

采用改進算法構造金字塔時，每組可減少一層高斯濾波圖像，構建幾組就可以減少幾層，前面提到，在特征檢測環節，金字塔的構造占據80%的時間，因此改進算法簡化了金字塔的構造。另外，D2OG算子的二維平面檢測在算法復雜度上也低于經典算法的三維空間局部檢測。因此，理論上改進算法實時性高于經典算法。

2.2 改進的RANSAC算法

當提供的特征點數目較少時，RANSAC性能可能有所降低。由于受本文D2OG中閾值T的選取影響，特征點數目少于經典算法從而生成的匹配點對數目減少，而匹配點對數目的減少可能導致匹配中存在誤匹配對，導致的匹配精度降低。

針對以上問題，采用改進的RANSAC算法進行特征點對提純，消除誤匹配對，從而提高匹配精度。改進算法的具體步驟如下:

1)在n個數據點集中隨機抽取4對特征點對，并將其設為初始內點集合，計算出變換矩陣H。將集合外的n－4個點看作外點，依次計算經過H變換后到對應匹配點的距離，小于閾值距離，則將當前點納入內點集合。記錄在此H下的內點數量。

2)重復步驟1)操作k次，選擇具有內點數量最多的集合并將該集合的內點作為估計的初始值，再使用RANSAC算法將新求出的內點集合與原來的內點集合并集為新的內點集合。

3)選取兩次內點并集后內點數量最多的集合作為最佳集合，將該集合下的變換矩陣作為最佳估計的變換矩陣。

改進的RANSAC算法對提取的匹配點進一步檢驗并消除誤匹配點對，以消耗小部分時間為代價，保證了匹配的精度。

下文通過實驗對經典算法與改進算法的性能進行比較，以驗證上述思路。

3 實驗結果與分析

在進行實驗之前，為了表述方便，將經典算法稱為SIFT，將基于D2OG檢測算子的 SIFT匹配算法稱為DSIFT，并將繼續加入改進RANSAC算法后的改進算法稱為DRSIFT。所有的程序實驗都是以VC++6.0為平臺，在操作系統為Windows7，主頻為Inter(R)Core(TM)2 Duo CPU T6600 2.2 GHz，內存為4 Gbyte的PC機上完成。實驗所用圖像均由筆者使用手機數碼相機實際拍攝。

3.1 程序流程圖

改進算法程序流程圖如圖3所示。

圖3 改進算法流程圖

3.2 基于D2OG算子的閾值選取

基于D2OG檢測算子在過零點檢測過程中引入閾值T，閾值大小的選取是檢測的關鍵。閾值過大會引入錯誤的特征點并增加算法運行時間;閾值過小，會漏掉部分正確的特征點，影響匹配精度。下面以一張大小為371×352的圖像為實驗對象，為了選取合適的閾值，實驗以經典算法作對比，分別在T=200，T=400，T=500時統計極值點數及運行時間，如圖4所示。

圖4 不同閾值下的DRSIFT與SIFT極值點檢測對比

實驗數據如表1所示，分析表1數據可以發現:閾值T的選取決定了極值點的數目和運行時間。閾值為500時，引入錯誤特征點，同時增加運行時間;閾值為200時，檢測的極值點數目很少，特征點是從極值點中得到的，因此，不能提供足夠的極值點會影響后期的匹配工作，影響匹配精度。由此可見，閾值選取由小到大，匹配精度是先升后降的過程。本文在綜合考慮算法的精度和速度兩個因素后，認為T=400時可實現較好的折中。

表1 DRSIFT閾值T的選取及與經典算法的比較

3.3 改進算法的綜合性能比較

為了檢驗改進算法的匹配性能，本文將SIFT，DSIFT和DRSIFT進行比較。實驗使用的圖片包括不同尺度縮放圖片、不同的旋轉圖片、不同視角變化的圖片以及添加了噪聲和光照等復雜變化的圖片。為了較全面地驗證算法的性能，實驗以特征點數、特征點檢測時間、匹配點對數、錯配點對數、正確匹配率以及運行總時間6個方面對SIFT，DSIFT和DRSIFT進行比較。其中，特征點數是指基準圖像的特征點數目;特征點檢測時間是基準圖像特征點檢測所消耗的時間;匹配點對數是SIFT與DSIFT經過RANSAC算法以及DRSIFT經過改進RANSAC算法后保留的匹配點對數。

實驗匹配效果如圖5～8，其中線段端點分別是基準圖像與待匹配圖像對應的匹配點。

實驗數據如表2所示，算法中的參數均為Lowe原文中推薦的參數。DISFT與DRSIFT選取的閾值為T=400。

分析實驗數據可以發現:在不同幾何變換或光學畸變下，DRSIFT算法特征點檢測時間要低于SIFT算法，可見，D2OG算子實時性優于DOG算子。DRSIFT算法總運行時間低于SIFT算法，可見DRSIFT算法復雜度低于SIFT算法，速度更快。DRSIFT算法正確匹配率與SIFT算法相當，DRSIFT算法匹配點對數少于SIFT算法，錯誤匹配點對數少于SIFT算法，可見采用改進的RANSAC算法在進行二次估計時消除了部分誤匹配。DRSIFT算法與DSIFT算法總運行時間相差不大，可見改進RANSAC算法運行時間與初始匹配點對數有關并且時間消耗很少，以犧牲小部分時間為代價，提高了匹配精度。

表2 SIFT，DSIFT和DRSIFT性能比較

由此可以得出DRSIFT算法的優點在于:在基本保持高精度、幾何形變、光照等不變性的基礎上，降低算法的復雜度和時間代價，提高了算法的運行速度。

與SIFT經典算法相比，DRSIFT算法的缺點在于:盡管引入改進RANSAC算法提高匹配精度，但當DRSIFT算法在圖像輪廓邊界信息較少或存在復雜畸變時，匹配精度與經典算法相比仍然有所下降。

4 結論

本文提出了一種改進的基于SIFT特征的快速匹配算法。改進算法通過簡化金字塔結構、降低特征檢測算子復雜度，二次篩選匹配點對，在保證算法高精度的同時提高了算法的速度。改進算法適用于圖像信息較豐富且對實時性有一定要求的場合。改進算法的缺點在于匹配點對數目相對較少，限制了算法處理的圖像類型(如邊緣輪廓較少的圖像)。因此，如何提高匹配點對數目以及在匹配點對數目較少的情況下如何進行更準確的參數估計是需要進一步學習研究的問題。

［1］LOWE D G.Distinctive image from scale－invariant keypoint［J］.International Journal of Omputer Vision，2004，60(2):20.

［2］MIKOLAJCZYK K，SCHMID C.A performance evaluation of local descriptors［J］.IEEE Trans.Pattern Analysis and Machine Intelligence，2005，27(10):1615－1630.

［3］劉力，彭復員，趙坤，等.采用簡化SIFT算法實現快速推向匹配［J］.紅外與激光工程，2008，37(1):186－189.

［4］KE Y ，SUKTHANKAR R.PCA－sift:A more distinctive representation for local image descriptors［C］//Proc.CVRP 2004.［S.l.］:IEEE Press，2004:506－513.

［5］馬莉，韓燮.主成分分析法(PCA)在SIFT匹配算法中的應用［J］.電視技術，2012，36(1):129－132.

［6］趙啟兵，王養柱，胡永浩.基于改進SIFT算法的無人機遙感影像匹配［J］.光電與控制，2012，19(3):36－39.

［7］張羽，朱丹，王玉良.一種改進的快速SIFT特征匹配算法［J］.微計算機信息，2008，24(33):226－228.

［8］呂冀，高洪民，汪渤，等.圖像制導的目標匹配算法與系統設計［J］.彈箭與制導學報，2009，29(5):43－45.

［9］鄭永斌，黃新生，豐松江.SIFT和旋轉不變LBP相結合的圖像匹配算法［J］.計算機輔助設計與圖形學學報，2010，22(2):286－292.

［10］曹娟，李興瑋，林偉廷，等.SIFT特征匹配算法改進研究［J］.系統仿真學學報，2010，22(11):2760－2763