史 瑩 萬 源 陳曉麗

(武漢理工大學(xué)理學(xué)院 湖北 武漢 430070)

?

基于平均區(qū)域劃分的Laplacian稀疏編碼的圖像分類

史 瑩 萬 源 陳曉麗

(武漢理工大學(xué)理學(xué)院 湖北 武漢 430070)

針對稀疏編碼方法中編碼過程不穩(wěn)定和金字塔匹配的劃分方法無法使得融合后的特征很稀疏這兩個問題，提出基于平均區(qū)域劃分的Laplacian稀疏編碼LSCARD(Laplacian sparse coding based on average region division)的圖像分類方法。首先，對原始圖像進行局部不變特征轉(zhuǎn)化(SIFT)特征提?。蝗缓?，在稀疏編碼方法中加入Laplacian正則化對局部特征進行編碼，使相似的特征具有相似的碼字；再利用平均區(qū)域劃分以及最大值融合將編碼后的特征向量進行融合；最后，采用多類SVM分類器對圖像進行分類。在幾個標準圖像數(shù)據(jù)集上的實驗結(jié)果表明，LSCARD算法具有更高的分類精度。

稀疏編碼 Laplacian正則化 平均區(qū)域劃分 最大值融合

0 引 言

圖像分類是計算機視覺領(lǐng)域中一個重要的研究問題，其關(guān)鍵在于提取合適的特征表示圖像。目前應(yīng)用得最廣泛的是利用局部特征，如SIFT[1]特征來表示圖像。對于SIFT特征的改進，涂秋潔等[2]提出基于PCA-SIFT特征與貝葉斯決策的圖像分類算法。而圖像表示最原始的算法是詞袋BoW(bag of words)[3]模型，為解決缺少特征點的空間關(guān)系信息的問題，Lazebnik等[4]提出利用空間金字塔匹配SPM(spatial pyramid matching)對圖像進行分類。由于BoW模型中的C-means方法導(dǎo)致語義信息的丟失從而造成量化誤差，Yang等[5]提出了基于稀疏編碼的空間金字塔匹配(ScSPM)圖像分類算法。該算法在圖像的不同尺度上進行稀疏編碼，并利用多類線性SVM分類器[6]對表示圖像的特征向量進行分類。然而，ScSPM對特征的變化很敏感，因此Gao等[7]引入圖Laplacian算子提出基于Laplacian的ScSPM(LScSPM或LSC)算法，改善了編碼的不穩(wěn)定性。另外，由于金字塔匹配的劃分方法無法使融合后的特征向量很稀疏，許多學(xué)者在圖像區(qū)域劃分的改進和應(yīng)用方面做了相關(guān)的研究。例如在圖像去噪領(lǐng)域中，傅鵬等[8]將圖像的平均區(qū)域劃分ARD(average region division)方法應(yīng)用在噪聲估計中，提出一種遙感圖像信噪比評估和度量準則。Liu等[9]提出對于盲目去噪的單圖像噪聲水平估計。由于稀疏表示理論為圖像去噪方法帶來了新思路，將其與冗余字典結(jié)合，周確[10]提出基于區(qū)域劃分和字典學(xué)習(xí)的圖像去噪方法。在圖像檢索方面，張旭等[11]利用一種結(jié)合SIFT和Harris特性的尺度空間興趣點檢測(IPDSH)和空間區(qū)域劃分的方法對圖像進行檢索，有效提高了圖像的檢索準確率。另外，對于合成孔徑雷達(SAR)圖像，張光勝等[12]將圖像劃分成尺寸變化的子圖像塊，并與馬爾可夫隨機場模型(MRF)結(jié)合，對SAR圖像實現(xiàn)變化檢測。Kazuhiro等[13]利用圖像特征的空間域和頻域，并將圖像劃分成單獨的幾個圖像塊，從而改善圖像的檢索效率。對于圖像分類的應(yīng)用，唐峰等[14]提出基于改進稀疏編碼模型的圖像分類算法，利用ARD方法和隨機森林多分類器，提高了圖像分類的性能。姜宇恒[15]提出基于區(qū)域劃分的極化SAR圖像分類算法研究，并取得了較好的分類效果。

上述的研究中，遇到的第一個問題就是稀疏編碼SC(sparse coding)在編碼過程中極其不穩(wěn)定，相似特征之間的多種組合方式會導(dǎo)致相似的特征可能會被編成不同的碼字。而第二個問題是圖像區(qū)域劃分中金字塔匹配方法運用使得融合后的特征無法很稀疏。因此，為了解決第一個問題，由于Laplacian正則化可以提取圖像的空間幾何信息來保持相似特征之間編碼的一致性，從而改善編碼的不穩(wěn)定性，因此本文首先在SC的優(yōu)化問題中引入Laplacian正則化。針對第二個問題，從上述的研究成果中可以看出，圖像的ARD憑借其操作簡單、快速等優(yōu)點應(yīng)用得最廣泛。因此，本文將LSC方法結(jié)合圖像的ARD，提出一種基于ARD的Laplacian稀疏編碼的圖像分類算法，即LSCARD。該方法利用Laplacian正則化提取更多的圖像空間幾何信息并保持特征空間中特征的依賴關(guān)系和相似信息，而圖像的ARD使得區(qū)域融合后的特征向量盡可能稀疏并具備空間信息，因此可得到較低的重構(gòu)誤差和較好的分類性能。

1 相關(guān)工作

對于圖像分類來說，局部特征的適當編碼不僅可以簡潔準確地模擬圖像，而且還可以提高圖像分類的效率。因此，在這節(jié)中將回顧兩種典型的編碼方法：向量量化和稀疏編碼。

相關(guān)符號說明：X=[x1,x2,…,xn]∈Rd×n為輸入的SIFT特征矩陣，A=[a1,a2,…,ak]∈Rd×k代表字典(或碼本)，S=[s1,s2,…,sn]∈Rk×n為相應(yīng)的編碼。

1.1 向量量化

(1)

其中，S∈Rk×n為聚類指標矩陣即X的編碼集；‖·‖2和‖·‖1分別代表l2-范數(shù)和l1-范數(shù)；Card(si)=1代表si的僅一個元素非零；si≥0表示向量si的所有元素非負；所有這些約束條件加起來表示向量si中有且僅有一個元素的值為1。

對于式(1)的簡單解法是對于每一個局部特征xi搜索其最近鄰，并給相應(yīng)的指標標記為1，其他的標記為0。

1.2 稀疏編碼(SC)

由于VQ方法很容易導(dǎo)致量化誤差，并且C-means方法可能會使語義信息丟失，因此Yang等[5]提出了基于SPM的稀疏編碼方法(ScSPM)即SC。其核心問題是學(xué)習(xí)k空間中的超完備(即k?d，基向量的個數(shù)遠大于維數(shù))字典A，并選取其中盡可能少的基向量來表示原始的特征向量。該方法利用空間金字塔劃分方法進行稀疏編碼，它首先訓(xùn)練用于稀疏編碼的基向量，再利用得到的基向量和對圖像進行空間劃分方法，將不同金字塔層次得到的向量直接相連構(gòu)成一個向量，從而利用此向量表示圖像的特征。因此，圖像中的每個特征都是由字典中的多個基向量表示，減少特征點的量化誤差，從而能更準確地描述一幅圖像的特點。具體優(yōu)化問題如下：

(2)

其中，S∈Rk×n為相應(yīng)的稀疏編碼；λ為正則化參數(shù)，用來平衡重構(gòu)誤差和編碼的稀疏性；aj為矩陣A的第j個列向量。

對于式(2)的通常解法是交替固定A(或S)從而優(yōu)化S(或A)，直到目標函數(shù)的值達到指定的極值即可。首先固定X和A，則優(yōu)化問題可以轉(zhuǎn)化為通過優(yōu)化每一個編碼系數(shù)si來解決。即：

(3)

針對式(3)，可以通過特征符號搜索算法[16]來求解。固定X和S，則相應(yīng)地將優(yōu)化問題轉(zhuǎn)化為二次約束的最小平方問題。即：

(4)

利用共軛梯度法或Lagrange對偶方法[16]可得出式(4)的解。

2 基于平均區(qū)域劃分的Laplacian稀疏編碼

雖然傳統(tǒng)的LSC方法能提取圖像的空間幾何信息，保留相似特征編碼的一致性和穩(wěn)定性，但該方法在劃分圖像時利用的是金字塔匹配，由于金字塔的第一層和第二層劃分的局域數(shù)量較小，使得融合后的向量無法達到很稀疏，并且缺乏空間信息。而ARD是將一幅圖像平均劃分為大小相等的方塊，利用最大值融合方法能使融合后的每一個圖像的特征向量都盡可能達到稀疏并保留空間信息，因此本文結(jié)合ARD和最大值融合提出LSCARD的圖像分類方法。LSCARD方法的整體框架如圖1所示。

圖1 LSCARD算法的整體框架

2.1 Laplacian稀疏編碼

Laplacian稀疏編碼方法最初是由Gao等[7]考慮到傳統(tǒng)的SC方法對特征變化很敏感，且相似的局部特征之間缺乏判別能力，因此引入Laplacian矩陣保留特征之間編碼的一致性，使得編碼過程不再獨立。相應(yīng)的優(yōu)化問題如下：

(5)

(6)

其中，k是兩個直方圖的維數(shù)(即字典的尺寸)，Him和Hjm分別表示特征xi和xj落入直方圖Hi和Hj的數(shù)量，即向量Hi和Hj的第m個元素。

對于式(5)來說，同時求解A和S是非凸的，但是固定A(或S)求S(或A)卻是凸的。一般的解法是：首先從所有局部特征中隨機選擇部分局部特征即模板特征來訓(xùn)練A和S。在交替更新A和S的過程中，分別采用共軛梯度法和特征符號搜索算法[16]。當有新的特征出現(xiàn)時，就可以得到對于新特征的稀疏編碼。

下面具體介紹利用特征符號搜索算法求編碼的步驟。首先固定特征X和字典A，優(yōu)化S。為了優(yōu)化S，我們逐個優(yōu)化si，固定所有剩下的sj(j≠i)。相應(yīng)的優(yōu)化問題如下：

(7)

接下來，利用算法1求解式(7)。算法中涉及的公式定義如下：

(8)

(9)

其中，矩陣S-i是去掉矩陣S的第i列的子矩陣，向量Li,-i是去掉Li第i項的子向量，E是單位矩陣。

算法具體步驟如下：

算法1 特征符號搜索算法求稀疏編碼

輸入：字典A，特征矩陣X的第i個特征，初始化編碼S，參數(shù)λ和β以及Laplacian矩陣L

輸出：第i個特征的稀疏編碼si

step 1 初始化si=0，θ=0，其中，θi∈{-1,0,1}表示系數(shù)的符號，activeset:={}。

其中，θm是θ的第m個分量。

(10)

step5 檢查最優(yōu)化條件：

2.2 利用ARD進行最大值融合

這節(jié)將介紹利用ARD對圖像進行劃分，由于ARD是對給定圖像平均劃分為多個區(qū)域，因此結(jié)合最大值融合方法可使融合后的特征向量盡可能稀疏，有效地克服了金字塔的不同尺度所劃分的局域數(shù)量較小并無法順暢地傳遞空間信息的缺點。在對圖像進行SIFT提取階段，若每個SIFT描述子是在p×p的像素塊上計算所得，則將每幅圖像I平均分成p(p=q×q)個方塊。因此，在對圖像進行LSC之后，可以利用ARD將這些稀疏特征進行最大值融合，從而得到圖像的最終表示。具體步驟如下：

輸入：圖像I，圖像劃分的區(qū)域數(shù)量p=q×q，字典A

輸出：融合后的特征向量z∈Rp×k，其中k為字典的個數(shù)

step 1 將圖像I平均地劃分成p個方塊，并提取每一個方塊中的SIFT特征。

step 2 利用算法1求解特征的稀疏編碼系數(shù)，得到每一個SIFT特征向量X∈R128×n的稀疏編碼S∈Rk×n。

step 3 采用最大值融合方法將每一個方塊中的所有稀疏編碼利用ARD進行融合，即：

vl=max{|s1l|,|s2l|,…,|snl|},l=1,2,…,k

(11)

其中，snl是稀疏編碼sn的第l個元素；而vl是向量v的第1個元素。而每一方塊的稀疏向量可用v=[v1,v2,…,vk]表示。

step 4 將表示該圖像中每一方塊的稀疏向量v按照這個方塊所在位置拼接成表示該幅圖像的稀疏向量z，即：z=[v11,…,v1k,…,vi1,…,vij,…,vik,…,vp1,…,vpk]

(12)

其中，vij是表示第i個方塊的稀疏特征向量的第j個元素。

得到圖像的最終表示之后，對于圖像分類，由于線性SVM具備快速、低復(fù)雜度等優(yōu)點，因此，本文采用多類線性SVM分類器。

3 實驗仿真

為了驗證本文LSCARD算法的有效性，分別在Corel-10[18]、Scene-15[19]和Caltech-101[20]三個標準數(shù)據(jù)集上進行仿真實驗。并將其與三種稀疏編碼方法的分類準確率進行比較。

3.1 圖像數(shù)據(jù)集

這節(jié)將介紹三個標準的圖像數(shù)據(jù)集，包括Corel-10、Scene-15和Caltech-101數(shù)據(jù)集。具體如表1所示。其中，Scene-15數(shù)據(jù)集的部分圖片如圖2所示。

表1 三個標準圖像數(shù)據(jù)集(張)

圖2 Scene-15數(shù)據(jù)集中部分圖片

3.2 實驗設(shè)置

對于ARD中的空間劃分粒度，本文選取4×4的粒度。在特征提取階段，利用16×16的窗口，步長為8提取圖像的SIFT特征。對于訓(xùn)練字典的過程，固定字典的尺寸為k=1 024。使用K最近鄰構(gòu)建相似W矩陣時，K=5。

針對LSC優(yōu)化問題中的目標函數(shù)，有兩個重要的參數(shù)λ和β。本文依照文獻[7]中的方法，對于不同的圖像數(shù)據(jù)集設(shè)置不同的值。例如，對于Corel-10和Scene-15數(shù)據(jù)集，λ=0.4,β=0.2；對于Caltech-101數(shù)據(jù)集，λ=0.3,β=0.1。

3.3 實驗步驟

首先，對于上述的三個標準圖像數(shù)據(jù)集，將每一個數(shù)據(jù)集隨機分成10份，并利用10-折交叉驗證來證明本文方法的有效性。然后，記錄基于10-折交叉驗證的LSCARD方法的平均分類準確率和標準差。最后，將本文方法與其他三種稀疏編碼方法進行比較并分析相應(yīng)的實驗結(jié)果。

3.4 實驗結(jié)果與分析

表2、3、4給出了LSCARD方法與一些知名的稀疏編碼方法包括ScSPM、LScSPM和SC-RF[14]在上述三個標準圖像數(shù)據(jù)集上的分類效果比較。

表2 Corel-10數(shù)據(jù)集上的分類結(jié)果 %

表3 Scene-15數(shù)據(jù)集上的分類結(jié)果 %

從上述這三個表可以看到，LSCARD方法在所有圖像數(shù)據(jù)集上的平均分類準確率都比其它三種編碼方法要高。具體地，對于ScSPM和LScSPM這兩種方法，由于其在進行圖像劃分時，利用的是金字塔匹配，這會造成金字塔的第一層和第二層因劃分的局域數(shù)量較小，使得融合后的特征無法很稀疏，并且缺乏空間信息。而LSCARD方法利用的是將圖像平均劃分為多個區(qū)域，這不僅使得融合后的特征盡可能稀疏，而且還具備空間信息，因此更能準確地表示圖像。對于SC-RF來說，由于其缺乏Laplacian正則化的使用，因此相似的編碼可能被編成不同的碼字。而LSCARD方法利用Laplacian算子能提取更多的空間幾何信息，保持編碼的一致性并使編碼過程不再獨立。因此，從整體上看，本文的LSCARD方法能顯著地提高圖像分類準確率。

3.5 復(fù)雜度分析

給定一幅圖像的局部特征數(shù)量為n，模板特征的數(shù)量為n1，字典的數(shù)量為k，則總的局部特征和模板特征之間相似度的計算的復(fù)雜度為O(n×n1)，特征符號搜索算法[16]的復(fù)雜度為O(n×k)，因此編碼階段的總復(fù)雜度為O(n×n1+n×k)=O(n×(n1+k))。針對編碼融合階段，空間金字塔劃分過程中涉及到金字塔的層數(shù)pLevels和直方圖的個數(shù)nBins，因此復(fù)雜度為O(2×n+pLevels×nBins)。而本文方法在融合階段利用的是平均區(qū)域劃分，假設(shè)一幅圖像的區(qū)域劃分數(shù)量為p，則該階段的復(fù)雜度為O(p×k)。因此，LSCARD方法的總復(fù)雜度為O(n×(n1×k)+p×k)，遠小于利用空間金字塔劃分進行特征融合的算法的復(fù)雜度。

4 結(jié) 語

針對SC方法中不穩(wěn)定和金字塔匹配的劃分方法無法使得融合后的特征很稀疏這兩個問題，本文提出LSCARD的圖像分類方法。由于Laplacian正則化能降低由字典的超完備性造成稀疏編碼對局部特征的敏感性，并保留了相似特征編碼的一致性，使得對局部特征的表達更具魯棒性。同時由于使用ARD對圖像進行劃分，結(jié)合最大值融合，能使融合后的特征更稀疏并帶有空間信息。因此，在圖像表示階段，通過利用特征之間的依賴性和稀疏性可以更準確地模擬圖像。在三個標準圖像數(shù)據(jù)集上的實驗結(jié)果也表明本文的LSCARD方法與已有的三種編碼算法相比有更好的性能。

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

[2] 涂秋潔, 王晅. 基于PCA-SIFT特征與貝葉斯決策的圖像分類算法[J]. 計算機應(yīng)用與軟件, 2016,33(6):215-219.

[3] Sivic J, Zisserman A. Video Google: A text retrieval approach to object matching in videos[C]//Proceedings of the International Conference on Computer Vision,2003,2:1470-1477.

[4] Lazebni S, Schmid C, Ponce J. Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 2006,2:2169-2178.

[5] Yang J C, Yu K, Gong Y H, et al. Linear spatial pyramid matching using sparse coding for image classification[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 2009:1794-1801.

[6] 楊淑瑩. 模式識別與智能計算—Matlab技術(shù)實現(xiàn)[M].2版.北京: 電子工業(yè)出版社, 2011:126-133.

[7] Gao S H, Tsang I W, Chia L-T, et al. Local features are not lonely-Laplacian sparse coding for image classification[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 2010:3555-3561.

[8] 傅鵬, 孫權(quán)森, 紀則軒, 等. 一種遙感圖像信噪比評估和度量準則[J]. 測繪學(xué)報, 2013,42(4):559-567.

[9] Liu X H, Tanaka M, Okutomi M. Single-image noise level estimation for blind denoising[J].IEEE Transcations on Image Processing, 2013,22(12):5226-5237.

[10] 周確. 基于區(qū)域劃分和字典學(xué)習(xí)的圖像去噪方法[D]. 西安: 西安電子科技大學(xué), 2013.

[11] 張旭, 郭寶龍, 孟繁節(jié), 等. 基于IPDSH興趣點空間區(qū)域劃分的圖像檢索[J].吉林大學(xué)學(xué)報(工學(xué)版),2013,43(5):1408-1414.

[12] 張光勝, 李長春, 鄒友峰. 基于自適應(yīng)分塊馬爾可夫隨機場(MRF)模型的SAR圖像變化檢測研究[J].科學(xué)技術(shù)與工程,2014,14(16):6-10.

[13] Kazuhiro K, Chen Q. Image retrieval using features in spatial and frequency domains based on block-division[C]//2015 International Conference on Computational Science and Computational Intelligence,2015:448-453.

[14] 唐峰, 孫錟鋒, 蔣興浩, 等. 基于改進稀疏編碼模型的圖像分類算法[J].上海交通大學(xué)學(xué)報,2012,46(9):1406-1410.

[15] 姜宇恒. 基于區(qū)域劃分的極化SAR圖像分類方法研究[D]. 西安: 西安電子科技大學(xué), 2014.

[16] Lee H, Battle A, Raina R, et al. Efficient sparse coding algorithms[C]//Advances in Neural Information Processing Systems,2006:801-808.

[17] Wu J X, Rehg J M. Beyond the Euclidean distance: Creating effective visual codebooks using the histogram intersection kernel[C]//Proceedings of IEEE 12th International Conference on Computer Vision, 2009:630-637.

[18] Lu Z W, Ip H H S. Image categorization with spatial mismatch kernels[C]//IEEE Conference on Computer Vision and Pattern Recognition, 2009:397-404.

[19] Li F F, Perona P. A Bayesian hierarchical model for learning natural scene categories[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2005,2:524-531.

[20] Li F F, Fergus R, Perona P. Learning generative visual models from few training examples: An incremental Bayesian approach tested on 101 object categories[J].Computer Vision and Image Understanding,2007,106(1):59-70.

IMAGE CLASSIFICATION BASED ON AVERAGE REGION PARTITIONING AND LAPLACIAN SPARSE CODING

Shi Ying Wan Yuan Chen Xiaoli

(SchoolofScience,WuhanUniversityofTechnology,Wuhan430070,Hubei,China)

For the sparse coding method, the coding process is unstable and the pyramid matching method can not make the fusion feature very sparse, an image classification method based on Laplacian sparse coding with average region partition is proposed. Firstly, local invariant feature transform (SIFT) feature extraction was applied to the original image. Then, Laplacian regularization was added to the sparse coding method to encode the local features so that the similar features have similar code words and the feature vectors were fused by average region partition and max pooling. Finally, multi-class SVM classifier was used to classify the images. Experimental results on several standard image datasets show that the algorithm has higher classification accuracy.

Sparse coding Laplacian regularization Average region division Maximum fusion

2016-07-14。國家自然科學(xué)基金項目(81271513,91324201)。史瑩，碩士生，主研領(lǐng)域：圖像處理與模式識別。萬源，副教授。陳曉麗，碩士生。

TP391.4

A

10.3969/j.issn.1000-386x.2017.07.027