基于爬山搜索的高斯模糊不變SIFT算子

付　波　張　敏　趙熙臨　李超順

1(湖北工業大學電氣與電子工程學院　湖北 武漢 430068)2(華中科技大學水電與數字化工程學院　湖北 武漢 430074)

?

基于爬山搜索的高斯模糊不變SIFT算子

付波1張敏1趙熙臨1李超順2

1(湖北工業大學電氣與電子工程學院湖北 武漢 430068)2(華中科技大學水電與數字化工程學院湖北 武漢 430074)

摘要針對SIFT算子對于高斯模糊環境下的特征匹配困難，提出基于目標圖像形變空間重采樣的高斯模糊不變SIFT算子GI-SIFT(Gaussian Invariant SIFT)。首先構建清晰目標的高斯模糊模型，重采樣模型參數重建目標圖像完備形變空間；其次，引入降采樣與爬山法，構建目標圖像的降采樣形變空間，在降采樣空間中以大采樣步長快速搜索當前峰值，對峰值鄰域進行曲線擬合，快速找到最優匹配。實驗結果表明，所提算法不僅對高斯模糊目標能較好匹配，同時較大提升了目標的特征匹配效率。

關鍵詞尺度不變特征變換形變空間重采樣高斯模糊降采樣爬山法特征匹配

0引言

高斯模糊形變常見于圖像復原領域中[1,2]，由于其點擴展函數較難檢測，故特征提取與辨識較為困難。SIFT算子[3,4]信息量豐富，獨特性好且可擴展性強，具有旋轉、尺度、亮度變化等不變性，并對于視角變化、仿射變換、噪聲有一定的穩定性[5]，廣泛應用于各類圖像工程領域。例如運動目標跟蹤與檢測[6,7]、雷達影像配準[8]、紅外目標跟蹤[9]、手背靜脈識別[10]等。

目前，多畸不變SIFT分為兩類。一類關注關鍵點局部區域特征模型與描述，如Harris-Affine[11]、MSER[12]、Hassian-Affine[13]等。劉向增等[14]針對大角度旋轉提出基于改進奇異值分解的仿射不變SIFT；Wang等[15]認為SIFT仿射不變性弱的原因在于DoG對關鍵點的關注區域是圓形，提出用MSER算子代替DoG算子；Zhao等[16]預估目標翻轉類型，使翻轉區域標準化，構建F-SIFT算子；Zhou等[17]提出基于采樣的局部描述子SLD，使圓形區域隨視點變化變成橢圓型區域，提升仿射穩定性。

關鍵點描述算子通過局部不變性統計特征反映目標的全局不變性，對現實場景中的變形目標匹配能力較弱。Morel等提出另一類基于形變空間重采樣的ASIFT(AffineScaleInvariantFeatureTransform)算子[18]。通過重采樣逼近仿射形變空間以尋找目標圖像的可能投影，大大提高算法的匹配準確度。但由于重構空間計算量較大，限制其應用，需要新的手段提高重構空間匹配效率。

1高斯模糊環境下的SIFT特征匹配

1.1SIFT算法

SIFT特征算法主要包括三個步驟：

1) 特征點檢測

(1) 在DoG尺度空間中對檢測點及其相鄰26個點比較，確保在尺度空間和二維空間檢測到極值點。DoG空間由不同尺度圖像高斯差分函數卷積得：

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))×I(x,y)

=L(x,y,kσ)-L(x,y,σ)

(1)

式中，G為二維高斯核函數；L為圖像的高斯尺度空間。DoG空間由高斯金字塔相鄰兩層相減得到；I(x,y)為圖像(x,y)位置處的像素值，其中G為:

(2)

式中τ為高斯分布標準差，即尺度空間因子。

(2)DoG空間中檢測到的候選極值點并不一定是真正的極值點，一般進行三維二次函數擬合，精確確定關鍵點的位置和尺度；引入2×2Hessian矩陣，剔除不穩定邊緣響應點；最后使用圖像梯度方法為每個極值點求取穩定方向，即對每個極值點的鄰域內像素的梯度和方向特征采集，使用36柱直方圖統計。直方圖峰值代表該極值點處鄰域梯度主方向，并將大于主方向峰值80%的方向作為輔方向。至此，檢測出的含有位置、尺度和方向的極值點即是SIFT特征點。

2) 特征點描述

SIFT一般采用128維特征向量對每個特征點描述，即在關鍵點周圍4×4窗口內計算8個方向的梯度信息，然后對該向量歸一化處理。

3) 特征點匹配

兩個SIFT描述子匹配一般采用歐氏距離法，Lowe針對128維特征向量維數較高的問題，對傳統k-d樹進行了改進。如果最近距離與次近距離的比值小于某個閾值，則認定這是一對匹配點。

1.2ASIFT算法

ASIFT算子構建待匹配圖像仿射形變空間，來模擬目標在不同參數的變形。其指出對于任意因視角變化引起的仿射變換，均可得到正定仿射變換矩陣A并且通過奇異值分解變換為：

(3)其中，λ>0表示尺度變化，φ為相機方位旋轉角度，Ф∈[0,π)，θ=arcos(1/t)，t≥1。Rφ與RΦ為相機方位對應的旋轉矩陣。

圖1為ASIFT仿射形變空間采樣規則，SIFT算子具有旋轉與尺度不變性，故只需對圖1中t與Φ采樣，以模擬所有可能的仿射形變。仿射形變空間構建完成后，空間中所有采樣圖像均與待匹配圖像進行SIFT特征匹配。記錄最優匹配結果。

圖1　t與Φ的采樣規則

1.3高斯模糊環境下的SIFT特征匹配

圖像的高斯模糊可通過以下模型實現：

(4)

其中，m、n為二維模板矩陣大小，σ為高斯正態分布標準差，同時也代表模糊半徑。

二維高斯函數圖像表現為從其中心點開始呈正態分布的同心圓，且離中心越遠的像素點權重越小，故二維模板矩陣的大小必須取適當值才能盡量減小計算量，同時保證模糊效果。一般模板矩陣大小取邊長為(1+2×3σ)的方陣，即(6σ+1)×(6σ+1)，簡化計算的同時，也將三個參數m、n、σ減少至一個參數σ。

在高斯模糊環境下，待匹配圖像相對于清晰圖像來說已十分“平滑”，對高斯模糊目標辨識不利。如圖2所示，高斯模糊圖像與清晰目標成功配117對，模糊圖像自身匹配成功245對，因此有必要提高SIFT算子在高斯模糊環境下的適應能力。

圖2　高斯模糊環境下SIFT算子匹配效果對比

2基于形變空間重采樣的高斯模糊目標特征匹配

2.1形變空間重采樣基本原理

設清晰目標S與待匹配圖像T在變換F下匹配建模，首先構造S的形變空間S′：

S′=F{α1,α2,…,αn|S}

(5)

其中，A={α1,α2,…,αn}為模型參數集，n是模型參數個數。對模型參數αi離散化：

αi→{αi1,αi2,…,αim}

(6)

其中，m為重采樣點數，由n維離散化模型參數{αij}(i=1,2,…,n,j=1,2,…,m)實現對形變空間的采樣，構成重采樣空間D逼近原始形變空間S′：

D→S′={D1,D2,…,Dp}

(7)

其中，p=mn,再由Di與T的匹配點數排序得：

D={Df1,Df2,…,Dfp}

(8)

其中，f1…fp是SIFT特征匹配點數從大到小排序，確定最優模型參數組合Af1。該過程實際上是一個優化過程，目標函數：

(9)

約束條件：

S′=F{α1,α2,…,αn|S}αi=Ri

(10)

其中，Ri是形變參數空間。

2.2高斯模糊目標特征匹配步驟

GI-SIFT算法流程如圖3所示。

圖3　形變空間重采樣算法流程

1) 構造清晰目標S的高斯模糊形變空間S′；

2) 設離散模糊參數為σ,構建參數空間Σ={σ1,σ2,…,σm}，進而由Σ構建S的高斯模糊重采樣空間D={D1,D2,…,Dm}逼近原始形變空間S′，Di為S與高斯模糊核函數F卷積后的圖像；

3) 將待匹配圖像T與采樣空間D匹配，獲得目標匹配點數空間P={N1,N2,…,Nm}；

4) 空間P中最大匹配點數Nmax對應的樣本D*即為所求目標，同時確定T對應的參數σ*。

3基于降采樣與爬山法的重采樣空間遍歷優化

單純的重采樣空間遍歷算法，例如ASIFT中所采用的將待匹配圖像T與重采樣空間D中的所有樣本一一匹配。雖然能準確搜尋最大匹配，但計算量過大，如圖4所示。

圖4　σ=5的待匹配圖像與不同分辨率下的重采樣空間匹配結果

圖4中，待匹配圖像T的高斯模糊參數σ0=5，其表示在不同分辨率條件下，模糊圖像與清晰目標的N-σ曲線。圖中降采樣下的曲線1在匹配點數上遠遠少于原分辨率下的曲線2，但兩條曲線的變化趨勢卻是相同的。N-σ曲線均可看作一幅單峰波形圖，說明降采樣方法在減少計算量的同時，并不會影響N-σ曲線的走勢。

3.1圖像降采樣

降采樣常用于圖像特征提取類算法，如SIFT算法DoG圖像金字塔的構建采用2×2降采樣，但參數過大的降采樣會導致圖片出現嚴重的失真。必須選擇合適的參數，在保證N-σ曲線趨勢不變的同時，減少單幅圖像匹配計算量。本文采用3×3的降采樣。

3.2爬山搜索

將3×3降采樣后的待匹配圖像Ts與重采樣空間Ds中任意一幅圖像進行匹配。通過對高斯模糊參數σ的擾動，判斷擾動前后匹配點數N的變化情況，按照使匹配點數N增加的原則在重采樣空間中搜索與Ts的最大匹配。該方法思路簡單，且易實現。

如圖4所示的N-σ曲線，用爬山法能輕易地找出當前曲線的峰值點，但該點可能與真實峰值點有所偏差。本文通過構建N-σ曲線，快速搜索曲線峰值點區域，然后采用局部曲線擬合確定峰值P點。該方法兼具搜索效率高與精確度高的優點。

3.3算法實現

基于降采樣與爬山法的重采樣空間遍歷優化算法流程如圖5所示。

圖5　基于圖像降采樣及爬山法的改進算法流程圖

算法實現步驟如下：

1) 以采樣步長Δ重構清晰目標S的重采樣空間Da，對待匹配圖像T，Da進行3×3降采樣，得到Ts、Das，將Ts與空間Das中樣本的匹配點數N定義為樣本模糊參數σ的函數：N=f(σ)；

2) 理論上來說，高斯模糊參數σ可以趨近于無窮大，但課題組經過大量實驗后發現，當模糊參數σ>8以后，肉眼已難以分辨目標形態，不具備辨識價值，因此本文設置采樣參數范圍上限閾值σend≤8；

3) 降采樣條件下，在步長Δ采樣重構空間Das內搜索峰值，令σ0=σend/2，得到匹配點數N0=f(σ0)，對σ0擾動，設σ1=σ0+Δ，則N1=f(σ1)，匹配點數增量：

ΔN1=N1-N0=f(σ0+Δ)-f(σ0)

(11)

(1) 若ΔN1>0，說明峰值點在σ0右邊，繼續增加σ，直到σk+1=σk+Δ，如果：

ΔNk+1=Nk+1-Nk=f(σk+1)-f(σk)<0

(12)

則Nk為對應步長Δ下的N-σ曲線峰值；

(2) 若ΔN1<0，說明峰值點在σ0左邊，重定義σ1=σ0-Δ，持續減少σ，直到σk+1=σk-Δ，如果：

ΔNk+1=Nk+1-Nk=f(σk+1)-f(σk)<0

(13)

則Nk為對應步長Δ下的N-σ曲線峰值；

4) 此時回到原分辨率，在峰值點Nk對應的σk周圍半徑為ε的鄰域進行曲線擬合，求得擬合最優參數(Nmax、σmax)。

4實驗結果及分析

匹配算法運行在IntelCore(TM)2 2.0GHz處理器上，編譯環境為VisualStudio2012。課題組在查閱大量文獻后發現，目前學術界并沒有專門針對高斯模糊形變的SIFT衍生算法，故在此采用標準SIFT算子與GI-SIFT作對比實驗。實驗采用程序來自RobHess維護的SIFT算法庫(http://robwhess.github.io/opensift/)。實驗分為高斯模糊環境下的特征匹配效果對比，采樣空間遍歷算法優化前后的計算效率對比以及實際應用效果對比。

4.1高斯模糊環境下目標特征匹配效果對比

圖6、圖7采用512×512分辨率的標準lena圖像，分別表示模糊參數σ為1、3的模糊圖像在三種算法下的匹配結果對比。(a)、(b)分別為SIFT、GI-SIFT對高斯模糊圖片的匹配結果，N為匹配點數。實驗結果顯示,本文提出的GI-SIFT，相比于SIFT在針對高斯模糊圖片的匹配點數上，有顯著提高。

圖6　模糊圖像(上)σ=1在經典SIFT算子與GI-SIFT算子的匹配效果

圖7　模糊圖像(上)σ=3在經典SIFT算子與GI-SIFT算子的匹配效果

同時，課題組采用華盛頓大學GroundtruthDatabase圖片庫進行實驗。該圖片庫包含24類圖片，課題組選取其中巴塞羅那、劍橋、哥倫比亞峽谷、格陵蘭等九類圖片，每類50張，分別進行隨機參數的高斯模糊形變，對兩種算法匹配點數均值統計如圖8所示。橫坐標代表圖像的類別，縱坐標代表匹配點數。從統計結果可以看出，對每一類圖片，GI-SIFT的平均匹配點數明顯高于SIFT。但由于每類圖片內容與模糊度的不同，GI-SIFT相對于SIFT的匹配點數提升幅度也不一樣，由64.4%到253.3%，平均提升幅度在117.5%左右，說明GI-SIFT對圖片的高斯模糊形變匹配效果提高了很多。

圖8　兩種算法匹配點數對比

4.2遍歷算法優化前后匹配運行時間對比

由于算法的設計思路不同，GI-SIFT在算法效率上與MSER、PCA-SIFT、Harris-Affine等算法并不具有可比性，因此此處只考慮GI-SIFT算法優化前后的時間對比。圖9是針對標準Lena圖片的高斯模糊特征匹配時間測試，其中鄰域半徑ε=1，步長Δ=1，σend=8，對目標圖像模糊參數σ每隔0.5進行一次時間采樣。

圖9　遍歷算法優化前后運行時間對比

實驗結果顯示，當待匹配圖像模糊參數在2以下時，匹配時間由優化前的400到750秒縮短至20秒左右；當模糊參數進一步增大時，優化算法所需時間還能夠進一步的降低；相對于優化前，GI-SIFT在特征匹配效率上有質的提升，且目標圖像的模糊度越小，效率提升越明顯。

4.3實際應用效果對比

圖10為SIFT與GI-SIFT在實際生活中的應用效果對比。測試圖片來自課題組所拍攝的日常照片，其中N為匹配點數。由于日常生活中所遇到的絕大多數圖片所受到的均為復合形變,因此并不能完全依照其受到的形變種類來進行絕對的分類。本文在采集實驗所用的實際生活照片時,也不可避免會受到光照、視角、焦距等各種因素的影響。但課題組已盡量對除高斯模糊以外的形變進行了限制,以期達到預期的實驗效果。 同時,考慮到目標物體被部分遮擋這一情況并不會影響高斯形變的處理效果,在采集實驗圖片時也加入了目標遮擋這一情況。

圖10　SIFT算子與GI-SIFT算子對于實際場景的高斯模糊特征匹配效果

由圖10可以看出，(a)、(b)中，待匹配圖片模糊度σ1=0.7，目標物體進行了90度的旋轉，SIFT算子匹配點數為218，但能明顯看出有較多錯誤匹配點，GI-SIFT的匹配點數為245，且錯誤匹配點數量沒有較大變化。(c)、(d)中，待匹配圖片模糊度σ2=1.3，目標物體有一部分被遮擋，SIFT算子的匹配點數為54，GI-SIFT卻能找出94個匹配點。(e)(f)中，待匹配圖片模糊度σ3=2.7，目標物體有輕微的仿射形變，SIFT算子只能找出5個匹配點，GI-SIFT的匹配點數為13。以上結果說明，本算法在實際應用中也具有較好的匹配效果，與前文實驗結果相符。

5結語

針對SIFT算子對高斯模糊環境下的特征匹配能力弱的問題，提出了一種基于圖像形變空間重采樣的改進算法。通過高斯模糊模型構建待識別目標的重采樣形變空間，在該空間內搜尋與待匹配圖像具有最大匹配的圖像采樣，較大提升了特征匹配能力。在此基礎上又提出了基于降采樣與爬山法的遍歷優化算法，在不影響匹配結果的情況下，顯著加快運算效率。

參考文獻

[1] 陳曦,汪彥剛,彭思龍.部分模糊核已知的混合模糊圖像復原算法[J].計算機輔助設計與圖形學學報,2010,22(2):272-278.

[2] 王芳,李誼,陸建峰,等.模糊圖像盲復原的魯棒自適應濾波算法[J].計算機輔助設計與圖形學學報,2014,26(3):457-464.

[3]LoweDG.Objectrecognitionfromlocalscale-invariantfeatures[C]//ProceedingsofInternationalConferenceonComputerVision.Kerkyra,Greece:IEEE,1999:1150-1157.

[4]LoweDG.Distinctiveimagefeaturesfromscale-invariantkeypoints[J].InternationalJournalofComputerVision,2004,60(2):91-110.

[5] 吳慧蘭,劉國棟,劉炳國,等.基于SIFT算法的圓心快速精確定位技術研究[J].光電子·激光,2008,19(11):1512-1515.

[6] 藺海峰,馬宇峰,宋濤.基于SIFT特征目標跟蹤算法研究[J].自動化學報,2010,36(8):1204-1208.

[7] 明安龍,馬華東.多攝像機之間基于區域SIFT描述子的目標匹配[J].計算機學報,2008,31(4):650-661.

[8] 陳爾學,李增元,田昕,等.尺度不變特征變換法在SAR影像匹配中的應用[J].自動化學報,2008,34(8):861-868.

[9] 鄭紅,鄭晨,閆秀生,等.基于SUKF與SIFT特征的紅外目標跟蹤算法研究[J].光電子·激光,2012,23(4):791-797.

[10] 王云新,劉鐵根,江俊峰,等.基于局部SIFT分析的手背靜脈識別[J].光電子·激光,2009,20(5):681-684.

[11]MikolajczykK,SchmidC.Scale&affineinvariantinterestpointdetectors[J].InternationalJournalofComputerVision,2004,60(1):63-86.

[12]ForssénPE,LoweDG.Shapedescriptorsformaximallystableextremalregions[C]//ProceedingsofThe11thInternationalConferenceonComputerVision.RiodeJaneiro,Brazil:IEEE,2007:601-614.

[13]RuanL,SridhaS,ClintonF.Hessian-Basedaffineadaptationofsalientlocalimagefeatures[J].JournalofMathematicalImagingandVision,2012,44(2):150-167.

[14] 劉向增,田錚,溫金環,等.基于仿射不變SIFT特征的SAR圖像配準[J].光電工程,2010,37(11):121-127.

[15]ZhupingWang,HuiyuMo,HanWang,etal.AnAffineInvariantFeatureDetectionMethodBasedonSIFTandMSER[C]//Proceedingsof2012 7thIEEEConferenceonIndustrialElectronicsandApplications(ICIEA).Singapore:IEEE,2012:69-72.

[16]WanleiZhao,ChongwahNgo.Flip-InvariantSIFTforCopyandObjectDetection[J].IEEETransactionsonImageProcessing,2013,22(3):980-991.

[17]WenZhou,ChunhengWang,BaihuaXiao,etal.SLD:ANovelRobustDescriptorforImageMatching[J].IEEESignalProcessingLetters,2014,21(3):339-342.

[18]MorelJM,YuG.ASIFT:anewframeworkforfullyaffineinvariantimagecomparison[J].SIAMJournalonImagingSciences,2009,2(2):438-469.

GAUSSIAN BLUR INVARIANT SIFT OPERATOR BASED ONHILL-CLIMBINGSEARCHING

Fu Bo1Zhang Min1Zhao Xilin1Li Chaoshun2

1(School of Electrical and Electronic Engineering,Hubei University of Technology,Wuhan 430068,Hubei,China)2(School of Hydropower and Information Engineering,Huazhong University of Science and Technology, Wuhan 430074,Hubei,China)

AbstractSIFT operator is difficult in feature matching in Gaussian blur environment. Aiming at this problem, we proposed a Gaussian blur invariant SIFT operator (GI-SIFT) which is based on resampling in deformation space of object image. First, we built the Gaussian blur model of the clear object and re-sampled the model parameters to reconstruct complete deformation space of the object image. Secondly, we introduced subsampling and hill climbing approaches to construct the subsampling deformation space of the object image, and rapidly searched the current peak value in subsampling space with large sampling step, and made curve fitting in peak neighbourhood to quickly find the optimal matching. Experimental results showed that the proposed algorithm can well match Gaussian blur object, at the same time it also greatly improves the efficiency of objects feature matching.

KeywordsScale invariant feature transform (SIFT)Resampling of deformation spaceGaussian blurSubsamplingHill-climbingFeature matching

收稿日期：2014-12-18。國家自然科學基金項目(61072130，5110 9088)；武漢市科技攻關計劃項目(2013012401010845)；湖北工業大學科研基金項目(BSQD12107)；廣東省工業攻關項目(2011B010100037)。付波，教授，主研領域：圖像處理。張敏，碩士生。趙熙臨，副教授。李超順，副教授。

中圖分類號TP391.4

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.045