一種簡化的ＳＩＦＴ圖像特征點提取算法

摘 要：針對目前尺度不變的圖像特征點提取算法計算量較大，算法較復雜的問題，提出一種簡化的SIFT圖像特征點提取算法。此算法通過改變金字塔尺度空間的結構實現對SIFT特征點提取過程的簡化，通過改變特征點描述子的結構實現對特征向量計算的簡化，從而在保證算法魯棒性的同時減少了計算量并增強了實時性。實驗證明了該算法的有效性。

關鍵詞：特征點提取；圖像匹配；尺度不變特征變換算法

中圖分類號：TP391 文獻標志碼：A

文章編號：1001-3695(2008)07-2213-03



Simplified SIFT feature point detecting method

GAO Jian， HUANG Xin-han， PENG Gang， WANG Min， WU Zu-yu



(Dept. of Control Science Engineering， Huazhong University of Science Technology， Wuhan 430074， China)



Abstract:The scale-invariant image feature point detecting methods are always complex and need large computation. In order to solve the problem， this paper proposed a feature point detecting method which was a simplification of the SIFT method. The method changed the pyramid frame in image scale space to simplify the SIFT feature point detecting process and changed the descriptor configuration to simplify the eigenvector computation. It could ensure the performance and decrease the computation at the same time. The experimental results have proved its validity.

Key words：feature point detection; image matching; SIFT(scale invariant feature transform) method

圖像特征在圖像處理中具有非常重要的意義。目前，幾何特征、彩色特征、紋理特征和特征點在目標識別、運動估計和立體匹配等領域中均已得到了一定程度的應用。在實際應用中，圖像經常會發生變化，提取具有較強魯棒性的圖像特征就顯得尤為重要。尺度不變的特征點對移動、旋轉、噪聲、縮放、遮擋等圖像變換均具有較強的適應能力。因而近年來，尺度不變的特征點提取算法及其應用成為了圖像處理領域中的一個研究熱點。

Harris角點檢測算法^[1]是一種經典的圖像特征點提取算法。雖然Harris角點對圖像平移、圖像旋轉和圖像噪聲均具有較強的魯棒性，但是它卻無法適應圖像的尺度變化，這也在一定程度上限制了它的應用。隨著圖像尺度空間理論的發展，近年來一些具有尺度不變特性的特征點提取算法被提了出來。這其中包括Harris-Laplacian算法^[2]、基于相位的局部特征點提取算法^[3]、Patch-Duplets算法^[4]、Laplacian算法和SIFT算法^[5]。前三種都是基于Harris角點并且擴展到了尺度空間以適應圖像的尺度變化。這類算法魯棒性較強，但是計算較復雜，實時性較差。與之相比，后兩種算法對大噪聲情況適應能力較差，但是算法相對簡單，實時性較好。

SIFT算法^[5]是Lowe提出的一種比較奇特的特征點提取算法。它選擇高斯殘差在尺度空間上的極值點為特征點，并計算特征點局部鄰域內的梯度方向直方圖為描述子。這種算法將圖像金字塔結構引入尺度空間以減少計算量，同時針對128維的特征向量空間，使用了BBF算法加快搜索過程，取得了較好的效果。SIFT算法已經在圖像匹配^[5]、全景拼接^[6]和視覺導航^[7]等領域得到成功應用。為了更好地適應實時性要求較高的場合，本文提出一種簡化的SIFT算法，它可以在一定程度上減少計算量、縮短計算時間。

1 特征點的提取

整個圖像特征點提取算法可以分為特征點的提取和特征點描述與匹配。其中，如何提取魯棒性較強的特征點是整個算法的基礎。

1．1 特征點的魯棒性

在實際的特征點提取算法中，微分算子可以實現對圖像的位移不變；數字圖像處理中微分的差分表示可以在一定程度上適應圖像的亮度改變；具有各向同性的微分算子可以適應圖像的旋轉變化；對圖像進行高斯卷積則可以增強抵抗噪聲干擾的能力；要適應圖像尺度的變化就需要在圖像的尺度空間中計算規格化導數。

如圖1所示，圖像的尺度空間是這幅圖像在不同解析度下的表示。一幅圖像I(X)在不同解析度下的表示可以利用高斯核G(t)的卷積來實現：L(X;t)=G(t)*I(X) （t為高斯方差）。圖像的尺度大小一般用高斯標準差σ（σ=t1/2）來表示。Lindeberg在文獻[8]中對圖像尺度空間理論進行了詳細的論述，并將γ規格化導數操作引入尺度空間。他指出當γ=1時，規格化后的導數具有尺度不變性。也就是圖像中某一點的σdxdL(X;t)的值不會因尺度的改變而變化。在實際的尺度不變特征點提取中，先通過圖像與一系列按指數分布的σ值（σ=knσ0，σ0為起始尺度）的高斯核卷積生成尺度空間，再對各層圖像各個像素求得相應規格化的各向同性的導數的函數值。在尺度空間局部鄰域中取得極值的像素點被選為特征點。這樣就保證了所提取特征點對圖像變化的魯棒性。

1．2 尺度空間結構分析

對于數字圖像而言，其在xy空間上的采樣已經確定。特征點提取算法所能改變的是尺度空間中在尺度方向上的采樣。在尺度上的采樣頻率和采樣深度對所提取特征點的魯棒性又具有較大影響。采樣間隔越短，采樣深度越深，特征點對應于圖像尺度變化的魯棒性就越強。但算法的計算量也會相應增加。

如前所述，尺度空間是由一系列的高斯卷積形成的，并且尺度系數越大，高斯卷積模板就越大，所需要的計算時間也就越長。在實際計算中，每層尺度圖像并不是直接通過原始圖像的高斯卷積生成，而是由下一層圖像的高斯卷積獲得，也就是L(X;t2)=G(t2-t1)* L(X;t1)。另一方面，也可以根據高斯卷積的性質，將二維卷積化為一維卷積來計算。但是尺度空間的生成依然需要大量的計算時間和存儲量。因而，尺度上的采樣間隔和采樣深度均會受到實時性要求的限制。



為了減少計算量和存儲量，SIFT算法將圖像金字塔引入尺度空間，采用了一種如圖2所示的金字塔結構^[5]：整個結構分為高斯金字塔和高斯殘差金字塔兩個部分。由高斯金字塔求高斯殘差，由高斯殘差金字塔提取特征點。金字塔分為多級，一級分為多層，每層之間的σ值相差k倍。如果每級有r層圖像需要提取特征點，則高斯殘差金字塔各級需要計算r+2層。由于高斯殘差金字塔由對應相鄰的高斯金字塔中的兩層相減獲得，高斯金字塔需要計算r+3層。此外，高斯金字塔每級取第r+1層（標準差對應krσ0）通過抽樣獲得上一級的第一層，再由高斯卷積獲得各層圖像。采用這種結構時，特征點只是在每級的中間r層中產生。每級的底層和頂層并不提取特征點，只是分別用于尺度方向上下層的極值比較中。



為了進一步減少計算量，本文采用了一種簡化的SIFT金字塔結構。如圖3所示，與簡化前相比，簡化后的SIFT金字塔每級的頂層被刪除。在這種結構中，每級的底層依然不提取特征點，只是用于與第二層規格化導數的極值比較中。由于缺少了原SIFT金字塔的頂層，簡化前的每級的最頂上兩層的極值比較就無法直接進行。考慮到上一級第一層是由本級第r+1層抽樣獲得，簡化后的結構用上一級的第一、第二層的對應像素的比較代替簡化前的結構中最頂上兩層間的對應像素比較，從而在每一級上減少了一次高斯卷積過程。

筆者在文獻[9]中已經分析了金字塔結構對特征點魯棒性的影響。從連續圖像的角度來看，金字塔結構并沒有改變規格化導數函數原有的位移不變性、各向同性和尺度不變性。但數字圖像中采樣過程不可避免地要發生混疊現象。金字塔結構中的抽樣操作和一些近似處理也會對特征點的魯棒性產生進一步的影響。在同樣標準差和同樣分層的情況下，采用金字塔結構所提取的特征點的魯棒性會差于采用原尺度空間結構，采用簡化后的結構會差于簡化前的結構，但是卻可以通過增加非完整金字塔結構的級數和層數來縮小這個差距。

1．3 特征點提取

簡化算法對特征點的提取可以分為四步：a)利用高斯卷積構建簡化后的高斯金字塔；b)計算高斯殘差金字塔；c)在高斯殘差金字塔中選擇局部鄰域（包括同層的八鄰域點、上層對應的九個像素點和下層對應的九個像素點）內取得極值并大于閾值的像素點為特征點；d)確定特征點的位置、尺度和方向。其中特征點的尺度為對應尺度空間圖像層的尺度大小，特征點方向角度的計算依照SIFT的計算方法進行。

2 特征向量的計算與匹配

在提取特征點并確定其位置、尺度和方向后，需要利用描述子計算特征點的特征向量，以進行特征點的匹配。對于遮擋等現象，局部特征比全局特征具有更強的適應能力。因而，對特征點的描述主要采用局部特性。在文獻[10]對多種描述子進行了實驗對比，得出基于SIFT的一類描述子具有最佳性能的結論。



如圖4所示，SIFT描述子由多個子區域組成，每個子區域分為16個采樣區。描述子在與特征點對應的尺度層圖像上計算特征向量，以特征點為中心，并旋轉其方向與特征點的方向一致。在劃分好各個子區域和采樣區之后，需要計算各采樣區的梯度幅值和梯度方向，從而形成每個子區域的八梯度方向的直方圖。直方圖中各向量的大小由對應梯度方向的采樣區的梯度幅值累加而成。為了消除直方圖中的邊界效應，首先確定與采樣區梯度方向相鄰的直方圖中的兩個方向向量，再根據梯度方向與這兩個方向向量中心值的偏離距離將采樣區的梯度幅值分散累加到這兩個方向向量中。這樣，每個子區域就形成了一個8維的特征向量。為了減少描述子偏移帶來的影響，各個采樣區的梯度幅值還需要進行方差為描述子一半寬度的高斯平滑，以突出靠近特征點采樣區所占的比重而減少遠離特征點采樣區所占的比重。同時，為了減少光照變化對梯度幅值的影響，特征向量還需要進行歸一化處理。圖4為2×2的結構形式。Lowe在文獻[5]中推薦使用4×4的結構形式，而對于4×4結構的描述子，就會形成一個128維的特征向量。



文獻[5]并沒有對采樣區的選取進行詳細的說明。如果選取單個像素點作為采樣區，那么采樣區和子區域的大小對于各層尺度層圖像都是固定的。這樣的描述子就不具有尺度不變的特性。要使描述子具有尺度不變性，其尺寸大小必須要與對應尺度成比例。所以采樣區的寬度也要與對應尺度成比例，并且對應不同尺度層圖像的描述子所包含的像素點的個數也不一樣。這樣，如何計算各采樣區的梯度幅值和梯度方向是需要解決的問題。

由以上分析可以看出，SIFT描述子中設置采樣區的方法顯得有點多余。本文簡化了計算過程，取消了采樣區的設置，而直接由子區域所包含像素點的梯度方向和梯度幅值來計算特征向量。為了保證尺度不變性，簡化后的SIFT描述子的寬度依然與對應尺度成比例。為了增加描述子的魯棒性，各像素點的梯度幅值也要與對應的高斯函數值相乘。高斯方差取描述子單個方向上所包含像素點個數的一半；再依據各像素點的梯度方向將處理后的梯度幅值統計到相應子區域的直方圖中，并對整個特征向量進行歸一化。簡化后的SIFT描述子計算上更簡單，計算量也有所減少，但是性能卻沒有下降。第3章的實驗結果將給出詳細的比較。

分別對兩幅圖像提取特征點并計算了各個特征點的特征向量之后，就可以進行特征點的匹配。兩幅圖像中兩個最相近的特征向量所對應的特征點組成一個匹配點對。SIFT特征向量的匹配采用的是歐式距離，并且通過計算與最相近的兩個特征向量的距離的比值來判斷是否匹配。這種方法可以取得比直接設置距離閾值更好的效果。匹配后的點對還是可能存在錯誤的匹配，這可以通過RANSAC算法作進一步的篩查。

3 實驗結果與分析

本文使用重復率^[5]來評價特征點檢測器的魯棒性。也就是先對原始圖像和其變形圖像分別計算特征點，求兩幅圖像中重復特征點的數量與這兩幅圖像分別提取的特征點數量的最小值的比值作為重復率。筆者預先知道圖像變形的相關系數，這樣就可以得到原始圖像中的像素點在變形圖像中的對應像素點。實際計算中，兩幅圖像提取的特征點是很難準確對應的。因此，當兩幅圖像中位置誤差小于1．5×2l（l為特征點所在的級數，最低級為0）個像素，尺度誤差小于21/2σ，方向角誤差小于15°的兩個特征點就被認為是對應重復特征點。對于描述子性能的評價，本文采用的是文獻[10]中所定義的匹配率和錯誤匹配率。匹配率是指通過描述子計算匹配成功的特征點對數量與前面所求得的重復特征點對數量的比值。錯誤匹配率則是錯誤匹配的點對數量與描述子計算匹配的總點對數量的比值。錯誤匹配的判斷依然采用以上計算重復率時確定的重復點對的標準。同時為了增加數據的可靠性，筆者選取了100幅實際場景圖像分別計算，再作統計求平均值作為最終實驗結果進行比較。

表1給出了幾種算法所提取特征點的在多種圖像變化條件下的魯棒性比較。SIFT表示σ0=21/2，k=21/2，m=2，高斯金字塔每級的層數p取0~4，j取0~3的SIFT特征點檢測器。SDet1表示簡化后的SIFT特征點檢測器，其σ0、k、m和j與SIFT相同，只是p取0~3。SDet2的算法與SDet1相同，只是k=21/4，p取0~5，j取0~4。表1中的第一列顯示了五種圖像變化條件；第二~四列分別顯示了在這五種變化條件下的SIFT、SDet1和SDet2提取特征點的重復率。從表中可以看出，對SIFT金字塔結構的簡化對照明改變和圖像噪聲條件下的重復率影響較小，對圖像旋轉條件下的重復率有所影響，而對尺度變化后的重復率影響比較明顯。但是可以通過增加金字塔的采樣頻率和采樣深度來縮小這個差距。SDet2就是在SDet1的基礎上增加了一級、每級增加了兩層。它在某些方面上的性能已經超越了SIFT。表2給出了三種特征點檢測器在Intel P4 3．0 GHz CPU的條件下計算一幅320×240像素圖像所需時間的平均值。從表中可以看出，簡化后的SIFT金字塔結構減少了計算量和計算時間，在實時性方面得到改善。

表2給出了SIFT描述子和簡化的SIFT描述子所計算的特征向量在多種圖像變化條件下的匹配魯棒性比較。其中，第一列顯示了五種圖像變化條件；第二三列分別顯示了SIFT描述子在這五種變化條件下的匹配率和錯誤匹配率；第四五列分別顯示了簡化的SIFT描述子在這五種變化條件下的匹配率和錯誤匹配率。從中可以看出簡化后的SIFT描述子與簡化前相比，在性能上并沒有明顯的差異。本文用計算1 000個特征點的特征向量所需要的計算時間來比較SIFT描述子在簡化前后的實時性能。SIFT描述子在簡化前計算1 000個特征點所需時間為339 ms，簡化后為267 ms。這也是在Intel P4 3.0 GHz CPU的條件下統計獲得。可以看出簡化后的SIFT描述子在實時性上有所改善。

圖5顯示了三種算法對兩幅圖像的特征點匹配結果。其中：(a)為SIFT算法匹配了101個點對，并由RANSAC算法剔除了9個錯誤匹配；(b)為SDet1+SDes算法匹配了91個點對。其中85個匹配正確，這個算法雖然匹配成功的特征點對比SIFT少，但是其在實時性上有所增強；(c)為SDet2+SDes算法匹配了124個點對，其中123個匹配正確，與前兩種算法相比，該算法檢測出的正確匹配點對最多。

4 結束語 

理論分析和實驗結果表明，本文所提出簡化的SIFT特征點提取算法可以在保證性能的同時提高算法的實時性。雖然改變SIFT金字塔結構帶來的誤差會影響所提取特征點的魯棒性，但是可以通過減少采樣間隔和增加采樣深度在一定程度上提高算法的性能。而對描述子結構的修改不僅沒有影響原有的性能，還簡化了計算過程。因而，這種簡化算法比較適合于立體視覺匹配等對算法實時性要求較高的圖像處理領域中。

參考文獻：

［1］ HARRIS C， STEPHENS M. A combined corner and edge detector[C]// Proc of the 4th Alvey Vision Conference. Manchester: [s.n.]， 1988: 147-151.

［2］MIKOLAJCZYK K， SCHMID C. Indexing based on scale invariant interest points[C]// Proc of the 8th International Conference on Computer Vision.Vancouver: [s.n.]， 2001: 525-531.

［3］CARNEIRO G， JEPSON A D. Multi-scale phase-based local features[C]// Proc ofIEEE Computer Society Conference on Computer Vision and Pattern Recognition. 2003: 736-743.

［4］JOHANSSON B，MOE A. Patch-duplets for object recognition and pose estimation[C]// Proc of the 2ndCanadian Conference on Computer and Robot Vision. 2005: 9-16.

［5］LOWE D G.Distinctive image features from scale invariant keypoints[J]. International Journal of Computer Vision， 2004， 60 (2): 91-110.

［6］BROWN M， LOWE D G.Recognising panoramas [C]// Proc of the 9th International Conference on Computer Vision. Nice: [s.n.]， 2003: 1218-1225.

［7］SE S， LOWE D G， LITTLE J J.Vision-based global localization and mapping for mobile robots[J]. IEEE Trans on Robotics， 2005，21 (3): 364-375.

［8］LINDEBERG T. Feature detection with automatic scale selection[J]. International Journal of Computer Vision， 1998， 30(2): 79-116.

［9］GAO Jian， HUANG Xin-han， PENG Gang， et al. A quick feature detecting method applied in robot vision[C]// Proc ofIEEE International Conference on Mechatronics and Automation. Haerbin: [s.n.]， 2007: 736-743.

［10］SCHMID C， MOHR R， BAUCKHAGE C. Comparing and evaluating interest points[C]// Proc of the 6th International Conference on Computer Vision.1998: 230-235.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”