基于粒子群優化的圖像自適應尺度空間劃分方法研究

徐久成，王煜堯，董 婉

1(河南師范大學 計算機與信息工程學院，河南 新鄉 453007)

2(河南省高校計算智能與數據挖掘工程技術研究中心，河南 新鄉 453007)

1 引 言

近年來，人工智能在理論研究和實際應用方面都取得了很大的進展，其中，圖像識別是人工智能發展進程中的重要組成部分.在圖像識別的過程中，如何從原始的圖像中提取有鑒別力的描述子，對于圖像識別的結果起著至關重要的作用.特征匹配則是檢測提取特征的一種有效的方法，其應用領域包括共同分割[1,2]，圖像匹配[3,4]，目標探測[5,6]，圖像配準[7,8]等許多方面.特征匹配結果的優劣依賴于是否提取到精確的圖像局部特征和健壯的特征描述.

從20世紀80年代開始，人們已經開始進行簡單的圖像領域研究.但是由于計算機硬件的限制，當時的圖像領域研究只能采用一些特征點的對應關系做射影幾何，選擇一些線條作形狀的分析，Harris角點探測子[9]就屬于其中有關圖像特征的研究成果.到了90年代末本世紀初，隨著計算機硬件的革新，大批高效的圖像描述子提取方法被提出，其中包括Lowe提出的SIFT特征檢測和局部描述子[10]，其通過收集梯度直方圖來得到最終的圖像描述.直至今日，仍有大批的學者[11-15]采用機器學習的方法來建立基于SIFT描述子的更加豐富的局部特征描述.

除了SIFT圖像特征描述子，一些實值描述子[16-18]也相繼被提出.Wang等人利用圖像(塊)整體的亮度順序信息將圖像塊分割為若干個局部子區域，提出了用來刻畫圖像局部亮度順序信息的LIOP特征描述子[17].Hauagge和Snavely提出了基于圖像對稱性的SYMD圖像特征描述子[18]，該描述子在識別具有對稱性質的圖像時具有很好的性能.除了這些實值描述子，許多二進制描述子[19-21]也不斷被提出.其中，Rublee等人在BRISK[19]的基礎上，提出了更加快速的二進制ORB描述子[20]，其具有旋轉不變性和抗噪的優點.另外，還有一些利用學習算法的特征提取方法，但是他們的有效性經常嚴重依賴訓練的數據集.例如，Trzcinski等提出的BinBoost方法[22]，采用一種類似AdaBoost的方法，在梯度域內使用正負patch對來訓練生成的二進制描述子，在patch數據集[23]上經常優于很多方法，但是在其它的一些圖像匹配數據集上它的性能就不好，相同的結論同樣被許多學者所證實[15-21].基于CNN生成的特征描述子[24-26]，雖然取得了很好的效果，但是卻生成了將近有4000維的描述子.

最近，學者們發現，相比指定每一個特征一個探測尺度并在每一個特定的尺度上提取特征描述子的描述子提取方法[10，16，20，22]，融合多個采樣尺度的描述子[13-15]能夠獲得更加有效的特征描述.Hassner等人使用低維線性空間來近似代替一組在多尺度提取的SLS特征描述子[13].Dong等人提出了DSP-SIFT特征描述子[14]，同樣通過采樣尺度空間，而不是在采樣尺度上的描述子上執行pooling.Yang等人提出了ASV-SIFT特征描述子[15]，通過不同尺度間的差異來測量特征尺度間的穩定性.然而，這些基于多個采樣尺度空間的特征描述子提取方法在尺度空間的范圍以及分布上依靠經驗，缺少了靈活性.例如，在Hassner提出的SLS特征描述子提取方法[13]中，他們主觀地在0.5到12的區間內線性等分為20個尺度；在Dong提出的DSP-SIFT特征描述子提取方法[14]中，他們主觀地1/6到3/4的區間內線性等分為15個尺度；在Yang提出的ASV-SIFT特征描述子提取方法[15]中，他們主觀地1/6到3的區間內線性等分為若干個尺度.因此，本文提出一種自適應的尺度空間劃分方法(PSO-ASV)，采用基本的粒子群算法，自適應地找尋到最佳的尺度劃分方案.

2 相關工作

2.1 SIFT 描述子

尺度不變特征轉換(Scale-Invariant Feature Transform，SIFT)[10]是一種有效的用來探測與描述圖像中局部特征的算法，其在空間尺度中尋找極值點，然后提取出相關的位置、尺度和旋轉不變量.SIFT圖像特征描述子的提取主要分為兩步：特征點的探測和描述子的生成.

圖像I(x，y)通過與實現尺度變換的高斯函數G(x，y，σ)[27]的卷積運算，進而構建尺度空間L(x，y，σ) ：

L(x，y，σ)=G(x，y，σ)*I(x，y)

(1)

其中，高斯函數G(x，y，σ)為：

(2)

在尺度空間采用高斯差分(DoG)函數探測到方向和尺度不變特性的特征點.通過對比度去除一些對比度較低的特征點，另外還去除一些不穩定的邊緣響應點.計算出探測到的特征點與其附近像素間的梯度方向分布特性，選取梯度值最大的方向為當前特征點的方向，使得提取的局部描述子具有旋轉不變的特性.采用梯度直方圖的方式，每一個特征點最終生成了一個128維的特征描述向量.梯度的計算如下：

m(x，y)=

(3)

θ(x，y)= tan-1((L(x，y+1)-L(x，y-1))/

(L(x+1，y)-L(x-1，y)))

(4)

其中，m(x，y)和θ(x，y)分別為在特征點(x，y)處梯度的模值和方向.

2.2 累積穩定性投票

累積穩定性投票(Accumulated stability voting，ASV)與SLS[13]，DSP-SIFT[14]類似，都是在多尺度空間上提取特征描述子.首先，在被探測尺度σ的近鄰尺度(λsσ，λlσ)范圍內線性等分地采樣ns個尺度.其中，λs表示最小尺度的縮放比例；λl表示最大尺度的縮放比例.

然后在每一個采樣的尺度的同一個特征點上提取一個SIFT描述子，并求出在兩個不同的尺度采樣的SIFT描述子的差的絕對值vi，j.vi，j用來度量尺度i和尺度j之間的每一個特征點之間的穩定性，表示為：

vi，j=xi-xj

(5)

其中，xi和xj是從i和j(1≤i，j≤ns)兩個不同的尺度提取的SIFT描述子，運算符 | · | 表示輸入向量的每一個元素的絕對值.由于在每一個尺度上的每一個特征點都對應一個128維的SIFT描述子，因此，尺度之間的穩定性可以另表示為：

(6)

hm=θt(vm|tm)

(7)

其中，θt為閾值函數，tm為選定的閾值.最后，對所有尺度對所得的二進制形式的穩定性hm執行pooling，得到度量穩定性的實值描述子C：

(8)

最終得到的描述子C即為ASV-SIFT.

3 基于PSO的自適應尺度劃分的描述子生成

近年來，實驗表明融合多個采樣尺度的描述子[13-15]能夠獲得更加有效的特征描述.尺度的劃分在此類方法中起到至關重要的作用，然而，如何進行尺度的劃分卻沒有一個準確的方法.在基于尺度空間的特征描述方法中，都采用主觀的經驗來進行較為合理的尺度劃分，并沒有一種高效的尺度劃分方法.因此，我們提取了一種基于粒子群算法[27]的自適應尺度劃分方法，并將其應用于ASV描述子提取方法中，最終得到高效的描述子提取方法(AD-ASV).

在基于多個采樣尺度的描述提取算法中，λs和λl分別表示最小尺度和最大尺度的縮放比例，兩者的取值直接影響著最終提取的描述子能否有準確的圖像描述，采用粒子群優化算法，來自適應地尋找到能夠準確描述圖像信息時λs和λl的值.

首先，隨機選取范圍為1到10的值作為λs和λl的初始值，同時作為粒子群算法的初始值.采用初始的λs和λl值作為初始的尺度劃分方式，通過ASV-SIFT方法計算出當下的適應值，然后對第i個粒子的速度和位置進行更新，更新方式如下：

vid=vid+c1r1(pid-xid)+c2r2(pgd-xgd)

(9)

xid=xid+vid

(10)

其中，vid和xid分別為粒子的速度和位置，pid和pgd分別是第i個粒子和整個粒子群迄今為止搜索到的最優位置，c1和c2是非負的學習因子，r1和r2是介于0和1之間的隨機數.

迭代中止條件根據粒子群當前搜索到的最優位置是否大于同等設置下的ASV的最優值.如果大于采用ASV得到的值，則終止迭代并返回當前搜索到的最優位置對應的λs和λl的值.完整的算法流程見算法1.

算法1. 基于PSO的自適應尺度劃分的描述子生成算法.

輸入：群體規模m，加速常數c1和c2，最大代數Gm

輸出：適應值mAP，最小尺度的縮放比例λs和最大尺度的縮放比例λl

Step1. 初始化一群群體規模為m的粒子，包括每個粒子初始位置xid和速度vid；

Step2. 采用ASV描述子提取方法，計算每個粒子的適應值mAP，即圖像特征點的匹配準確率；

Step3. 對每個粒子，如果它的適應值mAP大于它經歷過的最好位置pbest的適應值mAPpb，則將其作為當前的最好位置pbest并將其適應值更新為mAPpb；

Step4. 對每個粒子，如果它的適應值mAP大于全局所經歷最好位置gbest的適應值mAPgb，則將其作為當前全局的最好位置gbest并將其適應值更新為mAPgb；

Step5. 根據公式(9)和公式(10)來更新粒子的速度和位置；

Step6. 如未找到一個優于在相同條件下ASV達到的mAP或未達到預設最大代數Gm，返回Step2；反之，則輸出當前的適應值mAP以及相應的λs和λl；

Step7. 算法結束.

4 實驗與結果

4.1 數據集

本文將在Oxford[28]和Fischer[24]兩個圖像匹配數據集上進行實驗來驗證所提算法的有效性.Oxford數據集包含模糊、壓縮、視角變化和光照等變換的40個圖像對；Fischer數據集彌補了Oxford數據集變換類型不足的缺陷，提供了包含模糊、縮放、旋轉、視角變化和非線性變換等變換更加多樣的400個圖像對.

4.2 實驗設置與分析

所有的實驗將在Ubuntu 12.04上進行，采用Matlab R2012a編程軟件.采用VLFeat工具箱[29]提取經典的描述子，例如SIFT描述子，LIOP描述子等.采用Mikolajczyk和Schmid的結果評價方法[30]，計算各個算法的匹配和實際匹配的交除并值(intersection-over-union，IoU)，如果超過50%，就認定該匹配是正確的.相比其它基于尺度空間的描述子提取方法，ASV方法由于獲得了更好的匹配結果，因此，本文提出的自適應尺度劃分方法將應用在ASV描述子提取方法上.

圖1 不同的描述子對應的平均準確率Fig. 1 Mean average precision of different descriptors

在不同的尺度劃分數目上比較本文所提PSO-ASV方法與多種相關方法的平均匹配準確率mAP.在Oxford數據集和Fischer數據集上的實驗結果如圖1所示.

表1 不同描述子的平均準確率比較Table 1 Comparison of mean average precision of different descriptors

從表1中可以看出，當尺度空間的劃分數目達到10時，本文所提的PSO-ASV方法都優于其它方法.其中，SIFT，RAW-PATCH，LIOP都不是基于尺度空間的特征描述子，DSP-SIFT，ASV-SIFT是基于尺度空間的特征描述子.為了能夠進一步驗證本文所提方法的有效性，本文在Oxford數據集上又做了一些對比實驗，在每個類型的圖像對中選擇變換最大的圖像對來繪制出P-R曲線來評價文中所提方法，實驗結果如圖2所示.

圖2 Oxford數據集的8個變換最大的圖像對的P-R曲線Fig. 2 P-R curves of eight extreme pairs in the Oxford dataset

從圖2可以看出，在多種圖像變換方式中，相比其它方法，PSO-ASV方法大都取得了較好的結果，只是在對于視角的變換的wall圖像對匹配中，效果不明顯.除此之外，本文分析了在不同的圖像變化強度下采用不同的特征描述子實現的特征點正確匹配數目，實驗結果如圖3所示.圖3實驗結果表明，PSO-ASV方法能夠在模糊、壓縮和光照變化等圖像變換中獲得很好的匹配結果，但是對于視角的變換，效果不明顯.

圖3 在Oxford數據集上，不同的描述子在不同的變換強度下的正確特征點匹配數量Fig. 3 Number of correct correspondences using different descriptors under different transformation magnitudes in the Oxford dataset

在圖4中，選取其它的基于尺度空間的描述子提取方法與PSO-ASV方法作head-to-head比較，畫布中的每一個點代表使用選擇的兩個特征描述子匹配的其中一個圖像對的平均準確率.從圖4中看到，相比SIFT、DSP-SIFT、ASV-SIFT和1M2M，PSO-ASV能夠取得更好的匹配結果，也說明本文方法獲取了更加精確的圖像描述.

圖4 PSO-SIFT分別與其它相關方法的head-to-head比較Fig. 4 Head-to-head comparisons between PSO-SIFT and other relative methods

5 總 結

本文提出了新的圖像尺度空間劃分方法，通過引入粒子群算法，根據描述子的提取方式及尺度空間劃分的數目自適應地劃分尺度空間.實驗結果表明，PSO-ASV方法能夠在任何尺度劃分數目和特征提取方法下，找到更優的圖像尺度劃分.雖然PSO-ASV提高了特征匹配的準確率，但是卻不可避免地增加了時間的消耗，因此，如何能夠更加高效地自適應找尋更優的圖像尺度劃分，是我們下一步研究的方向.

：

[1] Rubio J，Serrat J，López A，et al.Unsupervised co-segmentation through region matching [C] .Proc of the 25th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2012：749-756.

[2] Chen H，Lin Y，Chen B.Co-segmentation guided hough transform for robust feature matching [J].IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI)，2015，37(12)：2388-2401.

[3] Chen H，Lin Y，Chen B.Robust feature matching with alternate hough and inverted hough transforms [C] .Proc of the 26th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2013：2762-2769.

[4] Yang T，Lin Y，Chuang Y.Accumulated stability voting：a robust descriptor from descriptors of multiple scales [C].Proc of the 29th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2016：327-335.

[5] Dalal N，Triggs B.Histograms of oriented gradients for human detection [C].Proc of the 18th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2005，1：886-893.

[6] Felzenszwalb P，Girshick R，McAllester D，et al.Object detection with discriminatively trained part-based models [J].IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI)，2010，32(9)：1627-1645.

[7] Liu C，Yuen J，Torralba A.SIFT flow：dense correspondence across scenes and its applications [J].IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI)，2011，33(5)：978-994.

[8] Hsu K，Lin Y，Chuang Y.Robust image alignment with multiple feature descriptors and matching-guided neighborhoods [C].Proc of the 28th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2015：1921-1930.

[9] Harris C，Stephens M.A combined corner and edge detector [C] .Proc of the 4th Alvey Vision Conference,Citeseer，1988：147-151.

[10] Lowe D.Distinctive image features from scale-invariant keypoints [J].International Journal of Computer Vision(IJCV)，2004，60(2)：91-110.

[11] Lazebnik S，Schmid C，Ponce J.Beyond bags of features：spatial pyramid matching for recognizing natural scene categories [C].Proc of the 19th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2006，2：2169-2178.

[12] Yang J，Yu K，Gong Y，et al.Linear spatial pyramid matching using sparse coding for image classification [C].Proc of the 22th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2009：1794-1801.

[13] Hassner T，Mayzels V，Zelnik-Manor L.On sifts and their scales [C].Proc of the 25th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2012：1522-1528.

[14] Dong J，Soatto S.Domain-size pooling in local descriptors：DSP-SIFT [C].Proc of the 28th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2015：5097-5106.

[15] Yang T，Lin Y，Chuang Y.Accumulated stability voting：a robust descriptor from descriptors of multiple scales [C] .Proc of the 29th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2016：327-335.

[16] Tola E，Lepetit V，Fua P.DAISY：an efficient dense descriptor applied to wide-baseline stereo [J].IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI)，2010，32(5)：815-830.

[17] Wang Z，Fan B，Wu F.Local intensity order pattern for feature description [C] .Proc of the 13th International Conference on Computer Vision(CVPR)，Piscataway，NJ：IEEE，2011：603-610.

[18] Hauagge D，Snavely N.Image matching using local symmetry features [C].Proc of the 25th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2012：206-213.

[19] Leutenegger S，Chli M，Siegwart R.BRISK：Binary robust invariant scalable keypoints [C].Proc of the 24th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2011：2548-2555.

[20] Rublee E，Rabaud V，Konolige K，et al.ORB：An efficient alternative to SIFT or SURF [C] .Proc of the 13th International Conference on Computer Vision(CVPR)，Piscataway，NJ：IEEE，2011：2564-2571.

[21] Balntas V，Tang L，Mikolajczyk K.BOLD-binary online learned descriptor for efficient image matching [C].Proc of the 28th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2015:2367-2375.

[22] Trzcinski T，Christoudias M，Fua P，et al.Boosting binary keypoint descriptors [C].Proc of the 26th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2013：2874-2881.

[23] Brown M，Hua G，Winder S.Discriminative learning of local image descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI)，2011，33(1)：43-57.

[24] Fischer P，Dosovitskiy A，Brox T.Descriptor matching with convolutional neural networks：a comparison to sift [J].ArXiv Preprint ArXiv：1405.5769，2014

[25] Han Xu-feng，Leung T，Jia Yang-qing，et al.MatchNet：unifying feature and metric learning for patch-based matching [C] .Proc of the 28th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2015：3279-3286.

[26] Zagoruyko S，Komodakis N.Learning to compare image patches via convolutional neural networks[C].Proc of the 28th IEEE Conference on Computer Vision and Pattern Recognition(CVPR)，Piscataway，NJ：IEEE，2015：4353-4361.

[27] Kennedy J，Eberhart R.Particle swarm optimization [C] .Proc of the IEEE International Conference on Neural Networks，Perth，Australia，1995：1942-1948.

[28] Hua G，Brown M，Winder S.Discriminant embedding for local image descriptors [C].Proc of the11th IEEE International Conference on Computer Vision(ICCV)，Piscataway，NJ：IEEE，2007：1-8.

[29] Vedaldi A，Fulkerson B.VLFeat-an open and portable library of computer vision algorithms [C].Proc of the 18th ACM International Conference on Multimedia，New York：ACM，2010：1469-1472.

[30] Mikolajczyk K，Schmid C.A performance evaluation of local descriptors [J].IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI)，2005，27(10)：1615-1630.