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

史 瑩 萬 源 陳曉麗

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

?

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

史 瑩 萬 源 陳曉麗

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

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

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

0 引 言

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

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

1 相關工作

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

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

1.1 向量量化

(1)

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

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

1.2 稀疏編碼(SC)

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

(2)

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

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

(3)

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

(4)

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

2 基于平均區域劃分的Laplacian稀疏編碼

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

圖1 LSCARD算法的整體框架

2.1 Laplacian稀疏編碼

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

(5)

(6)

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

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

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

(7)

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

(8)

(9)

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

算法具體步驟如下：

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

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

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

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

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

(10)

step5 檢查最優化條件：

2.2 利用ARD進行最大值融合

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

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

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

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

step 2 利用算法1求解特征的稀疏編碼系數，得到每一個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具備快速、低復雜度等優點，因此，本文采用多類線性SVM分類器。

3 實驗仿真

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

3.1 圖像數據集

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

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

圖2 Scene-15數據集中部分圖片

3.2 實驗設置

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

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

3.3 實驗步驟

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

3.4 實驗結果與分析

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

表2 Corel-10數據集上的分類結果 %

表3 Scene-15數據集上的分類結果 %

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

3.5 復雜度分析

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

4 結 語

針對SC方法中不穩定和金字塔匹配的劃分方法無法使得融合后的特征很稀疏這兩個問題，本文提出LSCARD的圖像分類方法。由于Laplacian正則化能降低由字典的超完備性造成稀疏編碼對局部特征的敏感性，并保留了相似特征編碼的一致性，使得對局部特征的表達更具魯棒性。同時由于使用ARD對圖像進行劃分，結合最大值融合，能使融合后的特征更稀疏并帶有空間信息。因此，在圖像表示階段，通過利用特征之間的依賴性和稀疏性可以更準確地模擬圖像。在三個標準圖像數據集上的實驗結果也表明本文的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]. 計算機應用與軟件, 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技術實現[M].2版.北京: 電子工業出版社, 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] 傅鵬, 孫權森, 紀則軒, 等. 一種遙感圖像信噪比評估和度量準則[J]. 測繪學報, 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] 周確. 基于區域劃分和字典學習的圖像去噪方法[D]. 西安: 西安電子科技大學, 2013.

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

[12] 張光勝, 李長春, 鄒友峰. 基于自適應分塊馬爾可夫隨機場(MRF)模型的SAR圖像變化檢測研究[J].科學技術與工程,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].上海交通大學學報,2012,46(9):1406-1410.

[15] 姜宇恒. 基于區域劃分的極化SAR圖像分類方法研究[D]. 西安: 西安電子科技大學, 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。國家自然科學基金項目(81271513,91324201)。史瑩，碩士生，主研領域：圖像處理與模式識別。萬源，副教授。陳曉麗，碩士生。

TP391.4

A

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