賈 琪，王曉丹，周來恩，翟夕陽

(空軍工程大學 防空反導學院，陜西 西安 710051)

一種改進的特征點方向分配算法

賈 琪，王曉丹，周來恩，翟夕陽

(空軍工程大學 防空反導學院，陜西 西安 710051)

現(xiàn)有特征點方向分配算法易受噪聲干擾，在光照、仿射變換時準確性有待提高。針對以上不足，在SIFT算法基礎上，提出了一種改進的特征點方向分配算法。該算法以特征點為中心，在0°～360°的范圍內固定角度間隔，等距采樣若干局部區(qū)域的圓形圖像小塊，計算各圓形圖像小塊質心相對圓心的偏移值。根據(jù)統(tǒng)計學原理以及實驗驗證表明，低偏移值區(qū)域易受噪聲干擾且對特征點主方向的確定沒有影響。據(jù)此，改進算法排除低偏移值局部區(qū)域，計算剩余局部區(qū)域像素梯度的幅度與幅角，利用方向直方圖給特征點分配主方向。結果表明，相比SIFT算法，改進算法在主方向分配時運行速度更快，同時準確性更高。此外，在特征點匹配實驗中，對視角變換的數(shù)據(jù)集圖像，改進算法的準確率與現(xiàn)有算法基本持平；在噪聲干擾的數(shù)據(jù)集圖像中，改進算法的準確率提升了17%。

特征點；方向分配；SIFT；梯度

1 概 述

圖像點特征是圖像的一種重要局部特征，它是計算機視覺、模式識別中重要的信息來源[1-2]?，F(xiàn)有特征點描述算法中，特征點方向分配的重要性常被忽略[3-4]。特征點方向是指給定一個參考方向，可任意選擇，當特征點局部圖像發(fā)生旋轉變換時，給定的參考方向同旋轉變換方向保持一致，且對噪聲及復雜背景變換等干擾具有魯棒性。習慣上，將參考方向稱為特征點的主方向。

目前，應用最廣泛的當屬SIFT算法[5]中的梯度方向分配算法，利用特征點局部區(qū)域的梯度分布特性，給特征點分配一個或多個主方向，取得了非常好的效果，但也存在一些不足。經(jīng)統(tǒng)計分析可知，特征點主方向僅由部分局部區(qū)域的梯度決定。SIFT算法計算整個局部區(qū)域的梯度值，然后進行統(tǒng)計分析確定主方向，時間復雜度高，且易受外界干擾。DIFT算法[6]對特征點局部區(qū)域進行DCT變換，多次旋轉局部圖像，根據(jù)DCT域系數(shù)的比值確定主方向。HIPS算法[7]中提出一種高效的方向分配算法，以特征點為中心，僅計算特征點16個圓形鄰域像素的梯度值，以抗干擾能力減弱為代價提升效率。SURF[8]、KAZE[9]中計算特征點局部區(qū)域的Harr小波特征，以特征點為中心滑動張角為π/3的扇形區(qū)域，取扇形區(qū)域內Harr小波特征總和值最大的方向為主方向，算法中計算Harr小波特征與特征值總和均需要時間開銷，而離散化扇形旋轉角度降低了算法準確性。Gauglitz等[10]提出了CoM(Center-of-Mass)和HoI(Histogram-of-Intensities)方向分配算法。CoM算法將特征點圓形局部區(qū)域視為有質量的點，計算質心，主方向取特征點至質心的方向。實驗結果表明，質心距特征點較近時，主方向易受噪聲干擾，準確性不佳。HoI算法同樣選取特征點圓形局部區(qū)域，但以特征點為基準計算梯度的幅值、幅角，期間不使用雙線性插值。相比SIFT算法，HoI算法將運行時間降低了一個數(shù)量級，代價是降低了算法準確性。

隨著計算性能的提升，基于機器學習的特征點方向分配算法[11-12]也逐漸被提出。算法以不同角度旋轉樣本圖像獲取足夠多的訓練集數(shù)據(jù)，通過有監(jiān)督學習訓練模型，性能相比手工設計的主方向分配算法有進一步的提升，但也存在一些不足，如模型難以學習多種復雜變換共存的訓練集數(shù)據(jù)，當圖像存在多種復雜變換時，基于機器學習的特征點方向分配算法性能下降明顯，算法魯棒性有待提升，等等。為此，需要設計一種簡單易行，能對干擾具有強魯棒性，同時準確性高的方向分配算法。

在SIFT算法的基礎上融合CoM算法，文中提出了一種改進的特征點方向分配算法，即在確定特征點主方向之前，通過一定策略排除特征點周圍對主方向生成沒有影響且易受干擾的局部區(qū)域，提升主方向分配的魯棒性與準確性，并通過實驗對該方法進行驗證。

2 改進的特征點方向分配算法

2.1SIFT中特征點方向分配算法

SIFT，全稱是尺度不變特征變換，是圖像匹配時提取特征點的一種算法，同時也是計算機視覺中的一種局部特征描述子，能夠很好地解決出現(xiàn)平移、光照、視角、旋轉等變化的多幅圖片之間的匹配問題。算法過程分為四步：尺度空間極值點檢測、特征點定位、特征點方向分配、特征點描述。

SIFT中特征點方向分配算法的步驟為：首先，假定某個特征點所在尺度為σ，計算以該特征點為圓心，4.5σ為半徑的圓形鄰域內高斯圖像的幅值和幅角，計算方法如下：

m(x,y)=

(1)

(2)

其中，m(x,y)表示圖像梯度的幅值；θ(x,y)表示圖像梯度的幅角；L表示關鍵點所在的尺度。

然后，對特征點鄰域內像素點的梯度方向和幅值進行直方圖統(tǒng)計。統(tǒng)計方法為在梯度方向0°～360°的范圍劃分36個區(qū)間，每個區(qū)間10°作為直方圖的橫軸，采用高斯加權將梯度幅值的累加作為直方圖的縱軸，高斯加權是為了保證離中心越近的像素點梯度信息越重要。

最后，根據(jù)直方圖統(tǒng)計結果，取峰值位置的橫軸方向為特征點主方向，為了增強算法的魯棒性，當存在有峰值80%能量以上的梯度方向，則分配給特征點作為輔方向。

特征點方向分配作為中間環(huán)節(jié)，其準確性對特征點描述具有較大影響。首先選取Oxford數(shù)據(jù)集中旋轉、尺度變換的boat圖片集，利用SIFT算法提取特征點并存儲。隨機選取300個特征點，將選取特征點的主方向以3°為步長遞增，在0°～360°范圍共生成120個主方向不同位置相同的特征點。最后，隨機抽取100個特征點進行特征描述，以原特征點描述向量為基準，計算旋轉不同角度的特征描述誤差2-范數(shù)，取平均值為最終結果，結果如圖1所示。其中，橫坐標的正、負代表相對主方向逆、順時針的角度差值。

圖1 不同主方向偏差角度下特征點的描述誤差2-范數(shù)

由圖1可知，當特征點主方向旋轉3°時，描述誤差的2-范數(shù)增加57.64，且隨著旋轉角度的增加急劇上升。由此可見，描述子中特征點方向分配的準確性對特征點描述具有較大影響。此外，文獻[13]從圖像旋轉變換一致性的角度提出了一種特征點主方向修正算法，根據(jù)圖像在旋轉變換中各特征點主方向變換角度相等，通過分析SIFT、SURF中方向分配算法確定的各特征點主方向，估計圖像的旋轉角度，然后對分配的特征點主方向進行修正，在特征點匹配實驗中取得了較好的效果，進一步證實了以上觀點。

2.2CoM方向分配算法

CoM，全稱是基于質心的方向分配算法，對特征點的微小移位及局部噪聲干擾具有一定的魯棒性。算法過程分為三步：特征點局部區(qū)域采樣、局部區(qū)域質心計算、特征點主方向確定。

首先，采樣半徑為R的特征點圓形局部區(qū)域，R的取值直接影響算法的性能與效率。通過大量的對比實驗，表明R為10.5時，性能與效率具有較好的折中比。

然后，計算特征點局部區(qū)域的質心，通過對比采用不同加權函數(shù)的算法，得到采用二次方程權函數(shù)能較好地平衡局部區(qū)域邊緣與中心對結果取值的貢獻，使計算結果更加平滑。二次方程權函數(shù)如下：

w(r)=1-(r/rmax)2

(3)

最后，將特征點至質心的方向作為主方向分配給特征點，CoM分配主方向給特征點的方法如圖2所示。

圖2 CoM算法特征點的主方向分配

2.3改進算法主要步驟

2.3.1 特征點局部區(qū)域采樣

特征點局部區(qū)域采樣分為兩步：特征點局部區(qū)域劃分和圓形圖像小塊采樣。

對于特征點局部區(qū)域劃分，方法是在0°～360°的范圍內，以固定角度間隔θ劃分特征點所在區(qū)域，以θ取90°為例，劃分方法如圖3(a)所示。

圖3 特征點局部區(qū)域采樣方法

對于圓形圖像小塊采樣，其方法是在特征點局部區(qū)域劃分范圍內，求解滿足式(4)要求的圓心坐標。其中，假設圓形圖像小塊半徑為R，(x,y)表示圓心坐標，(xp,yp)表示特征點坐標，θN表示第N個劃分區(qū)域中過特征點的二分線方向。

(4)

實驗表明，當N=4，R=3時，改進算法性能最佳。此時，以特征點為中心，局部區(qū)域如圖3(b)所示。

實驗中，為保證算法的準確性，去除靠近邊緣不能完整采樣的特征點，此類特征點約占總特征點數(shù)目的1%～3%，通常不穩(wěn)定，去除后對算法幾乎沒有影響。2.3.2 特征點主方向確定

在局部區(qū)域采樣的基礎上，特征點主方向確定分為三個步驟：帶權函數(shù)的質心計算、非低偏移值區(qū)域獲取、特征點主方向確定。

首先，帶權函數(shù)的質心計算方法借鑒CoM算法，為提升采樣效率，提出改進策略：對不同角度間隔和圖像小塊半徑的特征點需采樣的鄰域像素進行預處理，提前確定各像素相對特征點的偏移，省去中間計算過程。

其次，根據(jù)統(tǒng)計學原理并通過實驗驗證[10]，低偏移值區(qū)域易受噪聲干擾且對特征點主方向的確定沒有影響，改進算法排除了低偏移值區(qū)域，存儲剩余區(qū)域的像素值供下一步計算使用。排除低偏移值區(qū)域后，重疊部分的像素不重復計算。

最后，計算剩余區(qū)域梯度的幅值、幅角，確定特征點方向直方圖柱數(shù)，采用高斯加權將梯度幅值累加至對應方向的直方圖柱中，取峰值方向及大于峰值80%能量的方向作為主方向。計算過程中，根據(jù)方向直方圖柱數(shù)，對像素豎直、水平的幅值比建立幅角數(shù)組，簡化幅角計算為查表操作，提升算法效率。

綜上所述，假設改進算法參數(shù)θ=90°、R=3，其主要步驟如圖4所示。

圖4 改進算法主要步驟

改進的特征點方向分配算法流程為：

Step1：設有灰度圖像I，利用特征點提取算法得到其特征點集P，滿足(xp,yp)∈P；

Step2：分別采樣集合P中特征點局部區(qū)域，剔除不滿足要求的特征點，得到特征點局部區(qū)域集C與剩余特征點集P'。其中，特征點m(xp',yp')對應局部區(qū)域集合為Cm；

Step3：計算特征點局部區(qū)域集C的質心偏移值，去除低偏移值區(qū)域，得到C'；

Step4：利用改進策略，計算各特征點剩余局部區(qū)域集C'的梯度幅值與幅角，將計算得到的幅值與幅角分配到離散化的方向直方圖中；

Step5：對方向直方圖進行高斯平滑，解決因沒有仿射不變性而產(chǎn)生的特征點不穩(wěn)定的問題；

Step6：根據(jù)方向直方圖的結果，分別給P'中特征點分配一個或多個主方向。

3 實 驗

實驗采用Ubuntu 10.4系統(tǒng)環(huán)境，PC機配置為Inter (R) i7-4790 3.60 GHz處理器，內存為8 G。選取Oxford數(shù)據(jù)集，由8組每組6張的800×640像素圖片組成，包含對圖像視角、旋轉、噪聲、圖像壓縮、尺度和光照等的變換。改進算法參數(shù)設置在Matlab 2014a軟件環(huán)境下運行；特征點匹配實驗中，特征描述子構造使用加載OPENCV 2.9.1開源庫的VS 2010軟件環(huán)境。

3.1改進算法參數(shù)設置

改進算法中共有三個參數(shù)需要設置，分別是劃分角度間隔θ、圖像小塊半徑R、低偏移值閾值Thr。實驗采用控制變量法，依次確定各參數(shù)取值。

首先設R=4，Thr=0.7，從數(shù)據(jù)集圖像中隨機選取1 000個特征點，統(tǒng)計不同θ下改進算法分配單個特征點方向所需要的運行時間，給出SIFT算法所需要的時間以供參考，實驗結果如圖5所示。

圖5 運行時間

由于改進算法中，圖像小塊為對稱結構的圓形區(qū)域，因此當R增加1個像素時，特征點鄰域直徑增加4個像素。實驗結果表明，當θ為60°時，改進算法運行時間幾乎等同于SIFT算法；當θ為90°時，改進算法運行時間為SIFT算法的36%～51%；而當θ為30°時，改進算法運行時間超出SIFT。因為當θ增大時，改進算法處理圖像小塊的數(shù)目急劇增加，Thr一定時，改進算法可忽略梯度計算過程的低偏移值區(qū)域，算法運行時間趨向于SIFT的運行時間，而計算各圓形圖像小塊的偏移值需要部分運行時間。綜上所述，為保證算法性能，改進算法中取θ=90°。

接下來確定R的取值。從數(shù)據(jù)集圖像中隨機選取1 000個特征點，分別計算各特征點鄰域圖像小塊的偏移值。在R取3、4、5時，由實驗結果可知，當R取5時，由于圓形圖像小塊像素點較多，偏移均值太小且集中于0.4個像素以下；當R取4時，偏移均值總體偏小，質心趨向于特征點所在位置，此時偏移值均值為0.418 2個像素；當R取3時，偏移值均值為0.921 0個像素，偏移值分布較為理想，故改進算法中取R=3。

最后，Thr通過模擬環(huán)境下的實驗選取，方法是：從boat圖片集的img1圖像中隨機提取出500個特征點局部圖像并旋轉30°變換，從ubc、iguazu圖片集的img1、img3圖像中隨機提取出500個一致匹配特征點對，以SIFT、SURF、CoM算法作為參考，計算各算法分配主方向的準確性。對SIFT算法與改進算法，當一個特征點具有多個主方向時，取誤差較小的主方向為最終結果。期間做了大量的統(tǒng)計分析工作，由于篇幅有限，僅列出0.6～0.85之間取值的Thr，設置步長為0.5，縱軸取不同參數(shù)下角度偏差的平均值，實驗結果如圖6所示。

圖6 模擬環(huán)境下各算法方向分配誤差平均值

結果表明，當Thr=0.7時，改進算法穩(wěn)定性較好。因此，在改進算法中，設置θ=90°，R=3，Thr=0.7。

3.2實驗結果與分析

為進一步驗證改進算法的有效性，以特征點匹配為應用背景，對比分析不同特征描述子的性能。實驗中采用文獻[14]的錯誤率1-precision和召回率recall曲線來描述算法性能。

錯誤率=

(5)

(6)

實驗中選用指定閾值的特征性描述誤差2-范數(shù)作為匹配策略，當誤差值小于設定的閾值，則為匹配對，當匹配對所對應的特征點坐標誤差小于2個像素，則該匹配對為正確匹配，否則為錯誤匹配。而后通過變化閾值來取得1-precision與recall曲線。

特征描述算法通常對圖像的視角變化和噪聲干擾較為敏感。當視角變化較大時，對算法性能是一種挑戰(zhàn)。其中，視角變化圖像采用graf、wall圖片集，噪聲干擾圖像采用iguazu圖片集。

分別對SIFT[15]、SURF[8]、HOI[10]及改進算法進行求解，由于實驗集圖片較多，在此僅分析wall數(shù)據(jù)集的P1-P3(img1與img3圖像匹配，下同)特征點匹配結果與iguazu數(shù)據(jù)集P1-P2與P1-P3特征點匹配結果，并對各算法的1-precision與recall曲線作圖，結果如圖7所示。其他情況下各描述子的性能曲線排序規(guī)律與圖7中一致，不再另作描述。

圖7 特征點匹配實驗結果

對于視角變化，改進算法的性能與SIFT、SURF相比略有不足，實驗結果跟模擬實驗結果保持一致，其原因可能在于當視角變化時，特征點局部區(qū)域背景發(fā)生較大改變，改進算法排除低偏移值區(qū)域反而使主方向分配受到一定干擾，導致準確率略有下降。

對于噪聲干擾，改進算法表現(xiàn)出了較好的性能，在recall為0.85時，其準確率較SIFT算法提升了17%以上。其原因是改進算法通過排除低偏移區(qū)域，減少了噪聲干擾對特征點主方向分配的影響。同時，實驗結果也證實了特征點方向分配對特征描述具有顯著影響，對帶主方向分配的特征點描述算法，主方向分配的準確性將直接影響特征點匹配的準確性。

4 結束語

針對特征點方向分配算法的準確性易受噪聲干擾的問題，提出一種改進的特征點方向分配算法。該算法采樣特征點所在局部區(qū)域的圓形圖像小塊，并計算各圓形圖像小塊的質心偏移值，通過排除易受噪聲干擾的低偏移值區(qū)域，減少噪聲干擾對算法的影響。實驗結果表明，該算法的時間復雜度低，對噪聲干擾、光照、壓縮變換等具有較強的魯棒性。但當特征點局部發(fā)生較大的旋轉、視角變化時，算法的性能略有下降，同時算法性能對參數(shù)取值較為敏感。因此，研究更加準確、通用的改進策略將是下一步努力的方向。

[1] 廖 斌.基于特征點的圖像配準技術研究[D].長沙:國防科學技術大學,2008.

[2] 張琳波,肖柏華,王 楓,等.圖像內容表示模型綜述[J].計算機科學,2013,40(7):1-8.

[3] Yi K M,Verdie Y,Fua P,et al.Learning to assign orientations to feature points[C]//IEEE conference on computer vision and pattern recognition.[s.l.]:IEEE,2016:107-116.

[4] Brown M,Szeliski R,Winder S.Multi-image matching using multi-scale oriented patches[C]//IEEE conference on computer vision and pattern recognition.[s.l.]:IEEE,2005:510-517.

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

[6] Wang Y ,Shi M,You S,et al.DCT inspired feature transform for image retrieval and reconstruction[J].IEEE Transactions on Image Processing,2016,25(9):4406-4420.

[7] Taylor S,Drummond T.Binary histogrammed intensity patches for efficient and robust matching[J].International Journal of Computer Vision,2011,94(2):241-265.

[8] Bay H.SURF:speeded up robust features[J].Computer Vision & Image Understanding,2006,110(3):404-417.

[9] Alcantarilla P F,Bartoli A,Davison A J.KAZE features[C]//ECCV.[s.l.]:[s.n.],2012:214-227.

[10] Gauglitz S,Turk M,H?llerer T.Improving keypoint orientation assignment[C]//British machine vision conference.[s.l.]:[s.n.],2011.

[11] Kavukcuoglu K,Ranzato M A,Fergus R,et al.Learning invariant features through topographic filter maps[C]//IEEE conference on computer vision and pattern recognition.[s.l.]:IEEE,2009:1605-1612.

[12] Roth S,Schmidt U.Learning rotation-aware features:from invariant priors to equivariant descriptors[C]//IEEE conference on computer vision and pattern recognition.[s.l.]:IEEE,2012:2050-2057.

[13] Goh K M,Abu-Bakar S A R,Mokji M M,et al.Implementation and application of orientation correction on SIFT and SURF matching[J].International Journal of Advances in Soft Computing & Its Applications,2013,5(3):1-16.

[14] Mikolajczyk K,Schmid C.A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2005,27(10):1615-1630.

[15] Vedaldi A,Fulkerson B.Vlfeat:an open and portable library of computer vision algorithms[C]//International conference on multimedia.[s.l.]:[s.n.],2010:1469-1472.

AnImprovedAlgorithmforAssigningOrientationstoFeaturePoints

JIA Qi，WANG Xiao-dan，ZHOU Lai-en，ZHAI Xi-yang

(Air and Missile Defense College,Air Force Engineering University,Xi’an 710051,China)

Existing feature point orientation assignment algorithm is easily disturbed by noise and its accuracy needs to be improved in illumination variation and affine transform.For this,an improved algorithm for assigning orientations of feature points is put forward based on SIFT.It fixes the interval in the range of 0～360 degrees with the feature points as the center,equidistant sampling of circular image blocks in several local area,calculating the offset value of the centroid for circular image blocks to center of that.According to the statistics theory and experimental verification,low offset value area is easily disturbed and has no effect on the determination of dominant orientation.Therefore it excludes the local area of low offset value,calculates the amplitude of the pixel gradient of the residual local area,and assigns the main direction to the feature points using the directional histogram.The results of experiments show that compared with SIFT algorithm,it has a relatively higher running speed and accuracy.In addition,during the feature point matching,its accuracy is basically identical with the existing algorithm in database with changeable viewpoint and improves by 17% in database with noise interference.

feature point;assigning orientations;SIFT;gradient

TP391.4

A

1673-629X(2017)10-0006-05

2016-11-30

2017-03-07 < class="emphasis_bold">網(wǎng)絡出版時間

時間：2017-07-19

國家自然科學基金資助項目(61273275,60975026)

賈 琪(1993-)，男，碩士，研究方向為智能信息處理及模式識別；王曉丹，教授，博士生導師，研究方向為智能機器處理、機器學習。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170719.1113.092.html

10.3969/j.issn.1673-629X.2017.10.002