基于稀疏結構的圖像特征匹配算法①

包曉安, 詹秀娟, 張俊為, 王 強, 胡玲玲, 桂江生

(浙江理工大學 信息學院,杭州 310018)

圖像匹配是目標跟蹤、圖像檢索和圖像全景拼接等多個應用領域中重要的組成部分[1-4]. 目前匹配算法主要是基于圖像特征學習的,該類方法對于復雜環境的圖像匹配仍能保持較好的穩定性,已逐漸成為圖像匹配研究的主流方向.

SIFT算法[5]是公認性能最好的特征匹配算法之一,適用于圖像的尺度、旋轉變換、光線強弱變化等各種復雜情況下. 但是算法的復雜度較高,影響特征點的檢測速度和匹配速度. 快速魯棒特征(SURF)算法[6]是對SIFT的改進,該算法采用海森矩陣,使特征點的檢測速度提高幾倍,但降低了匹配準確率. PCA-SIFT算法[7],其思想是用主元分析法[8]代替SIFT算法中直方圖方法,提高算法運行的速度,但匹配數目較少. 近年來也產生了一些性能較好的算法,如Xu等[9]是將局部輪廓信息和全局信息融合,并結合改進的DTW技術,通過計算全局最佳匹配路徑,能夠實現局部匹配. Chen等[10]通過基礎矩陣計算特征點極線,并通過極線約束剔除錯誤匹配. Ren等[11]是將彩色信息和灰度信息疊加,形成改進的SURF特征描述子,并采用雙向搜索策略實現特征匹配.

特征匹配時,無論是最佳路徑的選擇,還是采用雙向搜索策略,都會有效提高匹配正確率. 但是多數匹配算法是對圖像進行全局特征點檢測,而且特征匹配時使用全局搜索策略,也會影響算法運行速度. 針對上述問題,提出一種基于稀疏結構的圖像特征匹配(Sparse Structure Matching,SSM)算法. 通過分析每個像素點的稀疏度值,篩選出稀疏度高的像素點所在的區域,作為結構稀疏度區域,縮小特征點的提取范圍,加快特征點檢測的速度,并通過最佳描述子的選擇實現特征匹配.

1 SSM算法

SSM算法是在特征點提取之前,通過稀疏度值的高低篩選出結構區域,然后對結構區域進行特征提取,這樣就避免了在全局進行特征點提取,減少了一些不穩點特征點的數量,這就使特征點生成過程,縮短特征點檢測時間,且采用最佳描述子匹配的準確率得到有效提高.

1.1 稀疏函數

在圖像中一個較小鄰域的灰度發生急劇的變化,其實體現的就是圖像的結構. 而灰度變換和空間變換對局部結構的影響較小[12]. 一般圖像的輪廓、圖形的拐角、交叉區域包含了圖像中大部分結構. 在圖像中,一個圖像塊與其鄰域中的其余圖像塊之間一般存在一定的聯系.

如圖1所示,其中,圖像塊用實線框區域表示,其鄰域用虛線框區域表示. 圖中A位于圖像中平滑區域,其鄰域內有較多的相似圖像塊[13]. 而位于圖像中結構區域的B,其鄰域范圍內有很少的相似圖像塊.

Xu等[14]根據圖像中圖像塊和它鄰域內其它圖像塊之間的一個相似度,來定義圖像稀疏結構的概念. 對圖像全局進行圖像塊的劃分,假設將圖像中某一像素點m為中心的鄰域窗口記為N(m),其大小為25×25.以該像素點為中心的圖像塊記為ψm,其大小為7×7,ψmi是其鄰域窗口中以mi為中心的鄰域塊,領域窗口N(m)中所有的mi的集合記為Ns(m),即：

圖1 不同區域的圖像塊及其鄰域

直方圖能夠反映圖像的灰度分布,以直方圖計算相似度,復雜度低. 梯度信息反映了相鄰像素之間的相對變化、連接緊密程度以及圖像的方向特征,所以引用文獻[15]中的梯度信息相似性度量,將梯度信息與直方圖相似性度量結合,增加衡量圖像塊位于結構區域的可信度,計算圖像塊的直方圖,則不同圖像塊直方圖之間的相似性定義為：

式(2)中,H(m,mi)表示圖像塊ψm的直方圖和鄰域范圍中其余圖像塊ψmi的直方圖的相似度,h1i表示圖像塊ψm灰度級為i時的像元個數,h2i表示圖像塊ψmi灰度級為i時的像元個數,灰度級l=255. 兩圖像塊相似度越高,其直方圖越相似,那么H(m,mi)的值就越小.

如圖1中A的鄰域內圖像塊C和A比較相似,其直方圖之間的相似度較高; 而D則與A相差較大,其直方圖之間相似度較低,所以采用直方圖的方法能夠較好的衡量圖像塊之間的相似度.

圖像塊ψm與圖像塊ψmi之間的相似度定義為：

式 (3)中,d(Гm,Гmi)表示在梯度模值圖像中,以m與mi為中心的圖像塊間的距離,α=5,用來控制相似度的衰減程度.P(m)是歸一化系數,使

在求得圖像塊之間的相似度之后,圖像塊的稀疏度函數就可以定義為：

式(4)中,|Ns(m)|是集合中元素個數; |N(m)|表示鄰域窗口中元素的個數.

1.2 稀疏結構區域的標記

通過對圖像分析,由稀疏度函數求解出每個圖像塊的稀疏度值S(m),利用塊結構稀疏概念將圖像劃分為兩類[16]：一是包含大量結構信息的結構區域,稱為結構塊; 二是包含大量紋理信息或平滑區域的非結構區域,稱為非結構塊. 圖像中結構區域、非結構區域的結構稀疏度是不同的,結構區域的結構稀疏度值較高一般在0.7～1.0之間,而非結構區域的稀疏度值一般小于0.3.

在運算中,將閾值設置為0.7,這樣對于不同的圖像基本都可以篩選出它們的結構區域. 結構塊的稀疏度值都大于規定的閾值,則為稀疏結構區域,認定關系表述為：

式(5)中S(m)為圖像塊的稀疏度值,ξ=0.7為規定的閾值. 相反,非結構塊的稀疏度值都小于規定的閾值.在一般情況下,在一幅圖像中結構塊的數量遠少于非結構塊的個數,所以只對標記的結構塊進行特征提取,提取的特征穩定性好且能有效減少處理的區域.

圖2 稀疏結構區域的標記

計算每個像素的稀疏度值,通過定義的閾值,將稀疏度值高的區域篩選出來,進行標記,如圖2所示.

1.3 稀疏結構區域的SIFT特征提取

采用SIFT的方法對有標記的稀疏結構區域進行極值點檢測、關鍵點定位和方向分配. 極值點的檢測,如圖3(a),對圖像特征方向的定位,如圖3(b)所示.

1.4 最佳描述子選擇及特征匹配

通過關鍵點周圍區域梯度信息得到SIFT描述子.關鍵點及其周圍部分像素點都包含在描述子中,而圖像匹配的質量依賴于特征提取的描述子,因此如何找到最佳的描述子,是提高匹配準確率的一種方法. 描述子的有效性不僅取決于圖像內的外觀,而且取決于圖像間的變化,因此對于圖像匹配,最佳的描述子通常是圖像相關或者是區域相關[17].

圖3 極值點檢測及SIFT特征

特征匹配是通過在特征點鄰域內搜索多個描述子中的一個,該鄰域內所有的描述子就作為候選描述子.特征點之間距離可能相隔幾個像素,特別是對于鄰域內兩個相距最近的特征點,它們的描述子相似度較高,在對這兩點尋找對應匹配點時,導致錯誤匹配的概率就會增高. 在鄰域內的候選描述子中尋找一個描述子能使該特征點與其相距最近的特征點進行區分,這樣的描述子就是該特征點的最佳描述子. 將最佳描述子選擇問題轉化為構造圖的能量最小化問題.

(1) 構造圖

若給定待匹配圖像Ip和IQ,特征點分別是構造圖G,由頂點集v和邊集ε組成,表示為G(v,ε). 圖G中每個頂點在本文中即是對應于圖像Ip中的特征點Cp,頂點的數量|v|=Np. 如果在某一鄰域大小為K的區域中,Cj是距離Ci最近的鄰點,則連接它們對應的頂點vi和vj的邊為eij,且復合變量每個頂點與復合變量相關聯,該復合變量wi表示通過描述子di將特征點與特征點進行匹配,此時選擇的描述子di,即是最佳的描述子; 而特征點與特征點是在最佳描述子下的最佳匹配對.

(2) 尋找合理的圖的標號

式(6)表示特征點鄰域內描述子的評估功率取最小值,gi(wi)為鄰域內選擇的描述子的評估功率.

式(7)中,n是空間鄰域的個數,si是特征點索引,di是描述子索引. 其中,

式(8)中,Y是特征點的特征向量是在描述子di下,特征點之間的光度相異函數,dist是特征向量之間的歐式距離. 同理,是在描述子di下,特征點之間的光度相異函數.

(3) 最佳描述子及特征匹配

當式(6)的取值為最小時,則選擇的這個合理的標號為W=wi,故由可知,鄰域內選擇的描述子di,是的最佳描述子,該描述子下的特征點的匹配是最佳的匹配; 否則,該描述子就不屬于最佳描述子,這樣的描述子無法區分相鄰匹配點對故被舍去.

1.5 算法運行步驟

本文算法步驟如下：

步驟1. 分別將兩幅利用式(4)計算圖像塊的稀疏度值,用式(5)進行篩選,得到稀疏結構區域,對該區域進行標記;

步驟2. 構造尺度空間. 將待匹配圖像與高斯核函數卷積可得到待匹配圖像的尺度空間,為：

式(9)、(10)中,(x0,y0)是像素點的位置,σ決定圖像平滑程度. 將高斯尺度空間中相鄰兩層相減得到高斯差分金字塔,對其特征進行歸一化,可以得到明顯的差分圖像蘊含的特征,這些特征就是要提取的穩定特征.

步驟3. 采用經典SIFT算法對兩幅圖像中有標記的稀疏結構區域中進行極值點檢測和關鍵點定位.

步驟4. 統計關鍵點鄰域的梯度信息生成SIFT描述子.

步驟5. 利用式(7)計算描述子的評估功率,利用式(6)找到評估功率的最小值. 在最佳描述子下,將特征點進行匹配,對匹配的兩特征點進行連線,直到圖像Ip中所有特征點找到其在圖像IQ中的對應匹配點為止.

2 算法測試及結果分析

實驗運行環境為Matlab R2014b版本,Intel(R)Core(TM)i5-3210M 2.3 GHz 4 GB內存的PC機. 實驗5組圖像數據,分別為cat、flower、lena、build和street,圖像分辨率均為400 dpi.

2.1 匹配結果比較

為驗證本文算法的普適性,使用不同類型的圖像,將SSM算法與三種算法進行比較.

圖4是選擇5種圖像數據的特征匹配結果圖,圖中每根線代表一對特征匹配對,圖(a)、(b)、(c)和(d)分別表示SIFT、SURF、PCA-SIFT和SSM算法匹配結果. 從圖中可以看出,圖(d)相比于其它算法的匹配對個數較多.

圖4 SIFT、SURF、PCA-SIFT和SSM算法特征匹配結果

匹配結果數據用表1列出,可知cat圖像的匹配結果中,SSM方法的匹配對數是SIFT方法的2.1倍,是SURF方法的6.3倍,是PCA-SIFT方法的8.9倍.flower圖像的匹配結果中,SSM方法的匹配對數是SIFT方法的1.3倍,是SURF方法的1.7倍,是PCASIFT方法的2.0倍. lena圖像匹配結果中,SSM方法的匹配對數是SIFT方法的1.6倍,是SURF方法的1.9倍,是PCA-SIFT方法的2.5倍. build圖像的匹配結果中,SSM方法的匹配對數是SIFT方法的7.7倍,是SURF方法的7.0倍,是PCA-SIFT方法的9.2倍.street圖像的匹配結果中,SSM方法的匹配對數是SIFT方法的5.7倍,是SURF方法的6.6倍,是PCA-SIFT方法的7.5倍. 5組數據中,SSM方法的匹配對個數比其它三種方法高出1.3～9.2倍.

表1 SIFT、SURF、PCA-SIFT和SSM算法匹配對個數數據統計

為了直觀表明SSM方法的優越性,畫出了四種算法得到的特征點匹配對數的柱狀圖,如圖5. 可以看出,對于任意一組圖像數據,SSM算法的匹配對數都比其它三種算法多出1.3倍以上. 選擇的圖像包括：單個對象、自然景物、建筑物和室外復雜場景,采用SSM算法,匹配效果都得到提高,足以說明SSM算法的普適性.

圖5 特征匹配對個數對比圖

2.2 匹配速率

為了準確評估SSM算法性能,分別對圖像在亮度、旋轉、尺度、加椒鹽噪聲和仿射變換等復雜情況下進行對比試驗,性能分析中選擇lena圖像作為試驗對象.

將SSM算法與SIFT、PCA-SIFT、SURF三種方法,在特征檢測時間和特征匹配時間進行比較. 算法運行時間對比,如圖6所示,由圖(a)可以看出,對于不同的圖像變換,由于SURF通過海森矩陣定位興趣點,所以檢測耗時最短; 而SSM算法是在稀疏結構區域進行特征點檢測,有效的縮小了檢測范圍,但是在尋找稀疏結構區域時也會增加計算復雜度,雖然在檢測速度上優于PCA-SIFT算法和SIFT算法,但是仍然沒有SURF算法檢測速度快. 由圖(b)可知,SSM算法匹配時間最短,SIFT算法耗時最長. 因為本文方法不是對圖像進行全局尋找匹配點,而是在稀疏結構區域進行全局搜索,這樣就會大大減少搜索區域,節省很多時間.而其它三種算法均是對圖像進行全局的特征點搜索,每搜索一個特征點,都要進行一次步驟5,要將所有特征點一一匹配也是一個浩大的工程. 所以本文算法在匹配速度上是優于其它三種算法的.

圖6 算法運行時間對比圖

2.3 匹配準確率

為了直觀反應算法的匹配效果,定義了匹配準確率函數P.P越大說明錯誤匹配對越少,算法的匹配效果越好. 假設圖像Ip和圖像IQ進行特征匹配時,匹配總數為f,其中錯誤匹配數為f1,那么匹配準確率可以定義為：

由表2可以看出,在圖像亮度變換的情況下,SSM算法的匹配準確率為91.5%,比其它三種算法高6.1%～13.2%,而SIFT準確率略低. 在圖像旋轉變換情況下,SSM算法的匹配準確率為98.3%,比其它三種算法高12.3%～34.6%,SIFT準確率還是相對較高,而旋轉變換對SURF和PCA-SIFT的影響較大. 在圖像尺度變換的情況下,SSM算法的匹配準確率為98.6%,比其它三種算法高8.5%～19.4%,SURF和PCA-SIFT的匹配準確率相對較低,而SIFT的匹配準確率是圖像幾種變換下最高的,SIFT具有較好的尺度不變性. 在圖像加噪聲的情況下,SSM算法的匹配準確率為97.8%,比其它三種算法高11.1%～36.1%,而噪聲對SIFT的影響較大. 在仿射變換下,SSM算法的匹配準確率為90.2%,比其它三種算法高9.9%～15.8%. 由于SSM算法特征點穩定性較好,且采用最佳描述子下進行特征匹配,所以受圖像外界影響較小. 因此在圖像進行復雜變換時,SSM算法在匹配準確率上比其它三種算法更具有優勢.

表2 4種算法匹配準確率統計表(單位：%)

3 結論

針對傳統特征匹配算法特征點檢測耗時長和匹配準確率低的問題,本文提出一種基于稀疏結構的圖像特征匹配算法. 文中通過引入稀疏結構的概念,進而考慮到在稀疏結構區域提取特征點以縮小特征點的檢測范圍. 通過對實驗結果的分析,我們可以看出,本文提出的SSM算法與其它的算法相比,無論在特征點的檢測速度,還是在特征匹配速度,更或者是匹配準確率和算法普適性方面,都具有很好的優勢. 但是本文算法也存在一些不足,比如在計算稀疏度值、篩選出稀疏度高的像素點所在的區域上,比其它的算法稍顯復雜. 接下來的研究工作主要在兩個方面：一是考慮到該方法存在一定的錯誤匹配,如果與誤匹配剔除結合起來,會使算法性能更好. 二是將本文算法與目標跟蹤算法相結合.

1 常發亮,馬麗,喬誼正. 遮擋情況下基于特征相關匹配的目標跟蹤算法. 中國圖象圖形學報,2006,11(6)：877-882. [doi：10.11834/jig.200606147]

2 周燕,曾凡智. 基于二維壓縮感知和分層特征的圖像檢索算法. 電子學報,2016,44(2)：453-460.

3 曹世翔,江潔,張廣軍,等. 邊緣特征點的多分辨率圖像拼接. 計算機研究與發展,2011,48(9)：1788-1793.

4 鄭啟財,曾智勇,池燕玲. 改進的基于顏色和SIFT特征的圖像檢索方法. 計算機系統應用,2015,24(11)：129-133.[doi：10.3969/j.issn.1003-3254.2015.11.020]

5 Lowe DG. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision,2004,60(2)：91-110. [doi：10.1023/B：VISI.0000029664.99615.94]

6 Bay H,Tuytelaars T,Van Gool L. SURF：Speeded up robust features. In：Leonardis A,Bischof H,Pinz A,eds. Computer Vision-ECCV 2006. Berlin,Heidelberg：Springer,2006.404-417.

7 Ke Y,Sukthankar R. PCA-SIFT：A more distinctive representation for local image descriptors. Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington,DC,USA.2004. II-506-II-513.

8 黃煒,趙險峰,馮登國,等. 基于主成分分析進行特征融合的JPEG隱寫分析. 軟件學報,2012,23(7)：1869-1879.

9 徐貴力,趙妍,姜斌,等. 基于局部尺度特征描述和改進DTW技術的局部輪廓匹配算法. 電子學報,2016,44(1)：135-142.

10 陳潔,高志強,密保秀,等. 引入極線約束的SURF特征匹配算法. 中國圖象圖形學報,2016,21(8)：1048-1056. [doi：10.11834/jig.20160809]

11 任克強,胡夢云. 基于改進SURF算子的彩色圖像配準算法. 電子測量與儀器學報,2016,30(5)：748-756.

12 王海明. 基于稀疏結構和SIFT特征的SAR圖像配準研究[碩士學位論文]. 西安：西安電子科技大學,2014.

13 侯躍恩,李偉光,容愛瓊,等. 融合背景信息的分塊稀疏表示跟蹤算法. 華南理工大學學報(自然科學版),2013,41(8)：21-27.

14 Xu ZB,Sun J. Image inpainting by patch propagation using patch sparsity. IEEE Transactions on Image Processing,2010,19(5)：1153-1165. [doi：10.1109/TIP.2010.2042098]

15 李志丹,和紅杰,尹忠科,等. 結合顏色和梯度信息的稀疏圖像修復算法. 計算機研究與發展,2014,51(9)：2081-2093. [doi：10.7544/issn1000-1239.2014.20130071]

16 程妮. 一種基于結構稀疏度的圖像塊分類方法. 現代計算機,2016,(17)：71-74. [doi：10.3969/j.issn.1007-1423.2016.17.015]

17 Hu YT,Lin YY. Progressive feature matching with alternate descriptor selection and correspondence enrichment.Proceedings of 2016 IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas,NV,USA. 2016.346-354.