萬源 張景會 陳治平 孟曉靜

摘 要：針對稀疏編碼模型在字典基的選擇時忽略了群效應，且歐氏距離不能有效度量特征與字典基之間距離的問題，提出基于彈性網(wǎng)和直方圖相交的非負局部稀疏編碼方法（EH-NLSC）。首先，在優(yōu)化函數(shù)中引入彈性網(wǎng)模型，消除字典基選擇數(shù)目的限制，能夠選擇多組相關特征而排除冗余特征，提高了編碼的判別性和有效性。然后，在局部性約束中引入直方圖相交，重新定義特征與字典基之間的距離，確保相似的特征可以共享其局部的基。最后采用多類線性支持向量機進行分類。在4個公共數(shù)據(jù)集上的實驗結果表明，與局部線性約束的編碼算法（LLC）和基于非負彈性網(wǎng)的稀疏編碼算法（NENSC）相比，EH-NLSC的分類準確率分別平均提升了10個百分點和9個百分點，充分體現(xiàn)了其在圖像表示和分類中的有效性。

關鍵詞：稀疏編碼;彈性網(wǎng)模型;局部性;直方圖相交;圖像分類

中圖分類號： TP391.4

文獻標志碼：A

文章編號：1001-9081（2019）03-0706-06

Abstract： To solve the problems that group effect is neglected when selecting dictionary bases in sparse coding models， and distance between a features and a dictionary base can not be effectively measured by Euclidean distance， Non-negative Local Sparse Coding algorithm based on Elastic net and Histogram intersection （EH-NLSC） was proposed. Firstly， with elastic-net model introduced in the optimization function to remove the restriction on selected number of dictionary bases， multiple groups of correlation features were selected and redundant features were eliminated， improving the discriminability and effectiveness of the coding. Then， histogram intersection was introduced in the locality constraint of the coding， and the distance between the feature and the dictionary base was redefined to ensure that similar features share their local bases. Finally， multi-class linear Support Vector Machine （SVM） was adopted to realize image classification. The experimental results on four public datasets show that compared with LLC （Locality-constrained Linear Coding for image classification） and NENSC （Non-negative Elastic Net Sparse Coding）， the classification accuracy of EH-NLSC is increased by 10 percentage points and 9 percentage points respectively on average， proving its effectiveness in image representation and classification.

Key words： sparse coding; elastic net model; locality; histogram intersection; image classification

0 引言

圖像分類是計算機視覺領域的一個重要研究方向，廣泛應用于生物特征識別、網(wǎng)絡圖像檢索和機器人視覺等領域，其關鍵在于如何提取特征對圖像有效表示。稀疏編碼是圖像特征表示的有效方法?？紤]到詞袋（Bag of Words， BoW）模型[1]和空間金字塔匹配（Spatial Pyramid Matching， SPM）模型[2]容易造成量化誤差，Yang等[3]結合SPM模型提出利用稀疏編碼的空間金字塔的圖像分類算法（Spatial Pyramid Matching using Sparse Coding， ScSPM），在圖像的不同尺度上進行稀疏編碼，取得了較好的分類效果。在稀疏編碼模型中，由于1范數(shù)在字典基選擇時只考慮稀疏性而忽略了群體效應，Zou等[4]提出一種新的正則化方法，將彈性網(wǎng)作為正則項和變量選擇方法。Zhang等[5]提出判別式彈性網(wǎng)正則化線性回歸（Elastic-Net regularized Linear Regression， ENLR ），引入魯棒彈性網(wǎng)絡正則化方法，以提高學習投影矩陣的緊湊性和有效性。張勇等[6]在目標函數(shù)中引入2范數(shù)正則項，提出基于非負彈性網(wǎng)的稀疏編碼算法（Non-negative Elastic Net Sparse Coding， NENSC），提高了編碼的判別性和有效性。Shen等[7]建議在字典原子選擇時使用彈性網(wǎng)作為正則項，提出彈性網(wǎng)正則項的字典學習算法（Elastic Net regularized Dictionary Learning， ENDL），這不僅得益于類似1范數(shù)的稀疏性，而且還鼓勵分組效應，有助于改善圖像表示的分類效果。Yu等[8]發(fā)現(xiàn)相比于稀疏性，局部性更重要，并且局部性必然推導出稀疏性，但反之未必。Wang等[9]將局部性約束引入到稀疏編碼中來代替稀疏性約束，提出局部線性約束的編碼算法（Locality-constrained Linear Coding for image classification， LLC），極大地提高了圖像的分類性能。但是該方法對近鄰數(shù)k很敏感，導致編碼過程極不穩(wěn)定，因此劉培娜等[10]在優(yōu)化問題中引入非負性約束，提出非負LLC算法。在表示特征與碼本之間的距離時，歐氏距離應用最多，然而尺度不變特征變換（Scale-Invariant Feature Transform， SIFT）特征是局部圖像塊梯度方向直方圖的統(tǒng)計量，Wu等[11]已經(jīng)證明直方圖相交在具有直方圖特征的學習任務中比歐氏距離更有效，提出一種超越歐氏距離的度量方法——直方圖相交相似性度量方法來創(chuàng)建有效的可視化碼本。為了解決這個問題，Chen等[12]提出了一種改進的LLC算法用于場景圖像分類，稱為基于直方圖相交的局部約束線性編碼（Locality-constrained Linear Coding based on Histogram Intersection， HILLC）。

針對文獻[9-12]在字典基的選擇時只考慮了稀疏性而忽略了群體效應，及文獻[9-10]在局部性約束中利用歐氏距離不能有效地度量特征與字典基的距離的問題，本文提出基于彈性網(wǎng)和直方圖相交的非負局部稀疏編碼（Non-negative Local Sparse Coding based on Elastic net and Histogram intersection， EH-NLSC）模型。在編碼模型中引入了彈性網(wǎng)作為正則項，可以得到類似于1范數(shù)約束的稀疏性，而且鼓勵分組效應，提高編碼的判別性和有效性;并在優(yōu)化函數(shù)中引入局部性約束和非負性約束，有效利用特征之間的局部信息，改善編碼的不穩(wěn)定性并保持相似編碼的一致性，并且通過引入直方圖相交，重新定義特征向量與字典元素之間的距離。實驗表明，相比于其他現(xiàn)有算法，EH-NLSC的分類性能更高。

1 相關工作

1.1 稀疏編碼

由于向量量化方法很容易導致量化誤差，并且K-means方法可能會使語義信息丟失，因此Yang等結合SPM提出了基于SPM的稀疏編碼方法（ScSPM）。其核心問題是學習M空間中的超完備（即M≥D，基向量的個數(shù)遠大于維數(shù)）字典U，并選取其中盡可能少的基向量來表示原始的特征向量。稀疏編碼具體的優(yōu)化模型如下：

1.2 局部約束線性編碼

Yu等指出局部性比稀疏性更重要，因為局部性可以推出稀疏性，但稀疏性不能推出局部性。Wang等指出局部非零系數(shù)通常被分配給編碼特征附近的基。因此，LLC方法用字典中的許多基來表示特征描述子，相似的特征通過共享它們的局部的基來獲得相似的編碼，從而提高了稀疏編碼的不穩(wěn)定性。局部約束線性編碼具體的優(yōu)化問題如下：

1.3 彈性網(wǎng)模型

2 本文方法

以上這些方法都能在一定程度上減小重構誤差，但仍然存在以下幾個不足： 1）編碼模型中的1范數(shù)只考慮了稀疏性，忽略了群體效應，圖像特征不能找到與同一類圖像對應的字典基;2）特征之間缺乏局部性和非負性約束，相似的特征可能會被編碼成不同的碼字;3）利用歐氏距離來計算特征描述子和字典之間的距離不夠有效?；谝陨?個問題，本文提出基于彈性網(wǎng)和直方圖相交的非負局部稀疏編碼模型。首先，針對第1個問題，將彈性網(wǎng)模型應用到稀疏編碼中，即在編碼模型中添加2范數(shù)，將有效且相關的特征一起選出來，充分考慮了字典基選擇時的群體效應，有助于消除字典中所選原子數(shù)的限制，保留判別性特征并消除冗余特征（如圖1：與SC相比，EH-NLSC選擇多個相關的基，虛線箭頭為去除的冗余特征），有效提高了編碼的有效性;然后，引入局部性和非負性，確保相似特征共享局部的基（如圖1：xi，xj共享局部的基），改善編碼的不穩(wěn)定性;最后，通過引入直方圖相交，重新定義特征向量與字典基之間的距離，使得圖像表示更準確有效。再利用空間金字塔匹配SPM將圖像劃分為L0、L1和L2三層，并對每層的空間金字塔區(qū)域進行最大值融合（Max Pooling， MP），將三層分別得到的編碼連接起來，得到圖像的最終特征表示。最后利用支持向量機（Support Vector Machine， SVM）進行訓練和分類。

圖1為本文提出的EH-NLSC模型的框架，其中，在學習字典和編碼階段，圖中給出了傳統(tǒng)的稀疏編碼（Sparse Coding， SC）方法與本文的EH-NLSC的對比，虛線框為傳統(tǒng)的稀疏編碼方法，實線框為本文學習字典和稀疏編碼的核心內(nèi)容。

2.1 EH-NLSC模型

本文結合彈性網(wǎng)模型，將2范數(shù)引入到稀疏編碼的目標函數(shù)中，并在優(yōu)化問題中的添加局部性約束，將非負性添加到優(yōu)化問題的約束條件中，最終形成EH-NLSC，即為圖1中實線框內(nèi)的核心內(nèi)容。具體的優(yōu)化問題如下所示：

2.2 EH-NLSC算法的求解

對于式（4），由于同時優(yōu)化目標函數(shù)中的U和V，該問題是非凸的，這樣很難找到一個全局最小值，但當分別優(yōu)化U或V是凸的，交替優(yōu)化U和V就會存在全局最優(yōu)解。

首先，固定X和V，優(yōu)化非負字典U，優(yōu)化問題轉化為：

3 實驗結果及分析

本章設計了兩組仿真實驗來驗證EH-NLSC算法的性能和效果，其中3.1節(jié)給出實驗所用數(shù)據(jù)集和實驗設置，實驗設置包括本文所對比的方法以及參數(shù)設置;3.2節(jié)介紹本文的兩組實驗設計內(nèi)容及結果分析。

3.1 實驗數(shù)據(jù)集和實驗設置

本文選擇4個數(shù)據(jù)集對EH-NLSC方法進行驗證，分別為Corel-10、Scene-15、Caltech-101、Caltech-256，表1給出了所選數(shù)據(jù)集的信息。

為了驗證本文方法的有效性，將本文方法與以下幾種方法進行對比分析：

1） ScSPM。利用稀疏編碼的空間金字塔匹配的圖像分類算法[3]，在圖像的不同尺度上進行稀疏編碼，并結合空間金字塔匹配方法進行圖像表示。

2） LLC。利用局部約束將每個特征描述符投影到其局部坐標系中，并通過最大池融合投影坐標以生成最終表示[9]。

3） ENDL。使用彈性網(wǎng)作為正則項來選擇特征編碼中的原子，這不僅可以得到類似于1范數(shù)的稀疏性，而且還鼓勵群體效應，有助于改善圖像表示[7]。

4） NENSC。利用非負稀疏編碼算法和彈性網(wǎng)模型，在稀疏編碼優(yōu)化模型中引入2范數(shù)作為正則項，增加編碼系數(shù)的非負性約束[6]。

5） LScSPM。LScSPM（ScSPM based on Laplacian）[14]利用局部特征之間的依賴關系，使用Laplacian矩陣較好地刻畫局部特征的相似性;此外，將拉普拉斯矩陣合并到稀疏編碼的目標函數(shù)中，以保持編碼的一致性。

6） Lap-NMF-SPM。Lap-NMF-SPM（NMF and graph Laplacian based on Spatial Pyramid Matching）[15]使用非負矩陣分解來約束碼本和相應的編碼系數(shù)的非負性，利用圖拉普拉斯正則化方法保持局部和相似特征之間的依賴性。

7） HILLC。使用直方圖相交來描述特征向量與碼本之間的距離。對于每個特征向量，搜索K最近鄰（K-Nearest Neighbor， KNN）來構造一個局部碼本[12]。

在特征提取階段，利用16×16的滑動窗口，步長為8進行SIFT特征提取，每個局部特征描述子均為128維，即D=128;在字典訓練階段，固定字典的大小為M=1024，然后對于4個數(shù)據(jù)集，選取不同的訓練樣本和測試樣本。對于Corel-10和Scene-15兩個數(shù)據(jù)集，從每類中分別隨機選擇50和100幅圖像作為訓練樣本，剩余的作為測試樣本。而對于Caltech-10和Caltech-256數(shù)據(jù)集，從每類分別隨機選擇15、30和15、30、45、60幅圖像作為訓練樣本，剩余的作為測試樣本。關于優(yōu)化問題中涉及的參數(shù)λ、 β以及σ，分別設置 λ∈[0.1，0.4]， β∈[0.1，0.4]，σ=100。

3.2 實驗設計及結果分析

3.2.1 實驗1：三種方法所得字典比較

首先，對SC、LSC以及本文方法EH-NLSC訓練所得到的字典圖予以顯示，如圖2所示。為了提高字典的表示能力，必須保證字典原子能夠合理地遍布于潛在的子空間，并且原始的訓練樣本具有大量的冗余信息和噪聲干擾，因此需要采用精簡且具有區(qū)分度的字典來提高識別精度。由灰度圖可以看出，本文方法EH-NLSC學習到的字典具有更多的可判別屬性，其中灰色像素反映圖像中原始特征的更多特性，比如EH-NLSC方法學習到的字典具有更好的局部性、非負性、帶通性和方向性（圖2（a）、（b）來自文獻[16]）。

為了更好地說明本文算法的有效性，選取Yale數(shù)據(jù)集[17]對圖像進行重建，隨機選取部分圖像。在訓練階段，利用EH-NLSC算法交替優(yōu)化目標函數(shù)，得到完備字典U和稀疏編碼矩陣V;在測試階段，對于新的單幅輸入圖像，利用訓練得到的字典U及式（12）計算其稀疏系數(shù)vi;在重建階段，利用完備字典U和稀疏系數(shù)vi對圖像進行重建。如圖3所示，從圖像的視覺效果來看，重建的圖像比較清晰，但得到的結果局部細節(jié)邊緣模糊，這是由于在EH-NLSC優(yōu)化函數(shù)中添加了局部性約束，使得圖像的重建系數(shù)是稀疏的，同時在圖像重建時也造成圖像信息的損失，因此重建圖像的部分局部細節(jié)模糊。

3.2.2 實驗2：不同方法平均分類準確率比較

表2，3分別為EH-NLSC算法與ScSPM、LLC、ENDL、HILLSC和NENSC五種方法在Scene-15，Caltech-101兩個數(shù)據(jù)集上的分類效果;表4，5分別為EH-NLSC算法與ScSPM、LLC、LScSPM和Lap-NMF-SPM四種方法在Corel-10和Caltech-256數(shù)據(jù)集上的分類效果。

從表2的結果可以看出，本文的EH-NLSC算法取得了更好的效果。與LLC方法相比，EH-NLS的分類準確率提高了10個百分點，與HILLSC方法相比，分類準確率提高了5.5個百分點，原因是對Scene-15場景分類，每個局部圖像塊包含豐富的紋理和輪廓，雖然這三種方法都可以對特征進行局部約束，但是在本文方法中，通過使用彈性網(wǎng)模型作為正則項，在稀疏編碼的優(yōu)化函數(shù)中引入2范數(shù)，鼓勵字典基選擇時的群體效應，將高度相關且判別性很高的特征一起選出來，也將冗余特征去除掉，有效控制了特征描述子的敏感性。另外，EH-NLSC與HILLSC均優(yōu)于LLC，由于在局部性約束中通過引入直方圖相交來代替原來的特征向量與碼本之間的歐氏距離，與SIFT特征是基于直方圖的統(tǒng)計量保持一致，因此取得較好的分類效果。

表3顯示了本文方法EH-NLSC和幾種方法在Caltech-101數(shù)據(jù)集上的性能比較。

同樣地，EH-NLSC方法的分類準確率比其他幾種方法效果都要好，首先相比于ScSPM、ENDL和NENSC，本文方法在優(yōu)化問題中引入局部性約束，確保相似的特征共享其局部的基，使得編碼過程更加穩(wěn)定。另外，添加對字典和編碼的非負性約束，使優(yōu)化問題只涉及加法運算，從而保留更多的有效特征。相比于LLC方法，EH-NLSC在計算特征描述子與碼本之間的距離時，利用的是直方圖相交相似性度量，因此可以更好地保留局部信息;同時在稀疏編碼模型中引入了彈性網(wǎng)正則項，鼓勵分組效應，選擇具有判別信息的特征，更加有利于特征表示。

為了充分證明EH-NLSC方法在圖像分類中的有效性，本文在Corel-10和Caltech-256數(shù)據(jù)集上設計了另外一組實驗，對比方法為ScSPM、LLC、LScSPM和Lap-NMF-SPM。對比結果如表4和表5，從實驗結果可以看出，EH-NLSC方法在兩個數(shù)據(jù)集上的分類準確率均優(yōu)于其他方法，尤其優(yōu)于ScSPM。ScSPM、LScSPM和Lap-NMF-SPM這三種方法，由于局部信息的缺失，導致圖像的特性不能被準確且有效地表示出來。由于EH-NLSC在優(yōu)化函數(shù)中引入了局部性約束，確保相似的特征具有相似的編碼，保留更多局部信息。與LLC方法相比，EH-NLSC算法的分類準確率提升了6個百分點，這是因為LLC雖然考慮到了局部性約束，但是在衡量特征向量和碼本之間的相似性時用的是歐氏距離，而SIFT特征本是直方圖統(tǒng)計的結果，因此利用直方圖相交代替歐氏距離更為準確。另外，EH-NLSC將彈性網(wǎng)模型用作正則項，使得具有判別信息的特征均被選出，并且將多余無關的特征去除，有效提高了圖像表示的準確性。

3.2.3 實驗3：參數(shù)靈敏度分析

本實驗研究了不同的參數(shù)設置在4個標準數(shù)據(jù)集上對分類效果的影響，將λ和β分別設為0.1，0.15，0.2，0.25，0.3，0.35，0.4，其分類結果變化如圖4所示。從圖4中可以看出：在Scene-15和Corel-10兩個數(shù)據(jù)集上，當λ=0.3，β=0.2時，分類效果達到最優(yōu);而在Caltech-101和Caltech-256數(shù)據(jù)集上，λ=0.3， β=0.1時效果最佳。

4 結語

本文提出一種新的稀疏編碼框架，稱為基于彈性網(wǎng)和直方圖相交的非負局部稀疏編碼，并將其與空間金字塔和最大池融合相結合來獲得用于圖像分類的編碼模型。通過將彈性網(wǎng)引入到稀疏編碼模型中，本文的EH-NLSC在保持稀疏性的基礎上，鼓勵分組效應，可以有效地選擇判別性特征，并將冗余特征去除，因此EH-NLSC比普通稀疏編碼方法具有更好的鑒別能力。另外，在圖像分類中，局部性約束已經(jīng)被證明是非常重要的，本文利用局部性約束編碼，使得相似的特征共享局部的基，并保持相似特征具有相似編碼。并通過引入直方圖相交重新定義特征向量與字典元素之間的距離，與通過直方圖統(tǒng)計的特征保持一致。已經(jīng)評估了所提方法在幾個公共數(shù)據(jù)集上的分類效果，實驗證明了EH-NLSC算法的有效性。

參考文獻 （References）

[1] SIVIC J， ZISSERMAN A. Video Google： a text retrieval approach to object matching in videos [C] // ICCV '03： Proceedings of the 9th International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2003， 2： 1470-1477.

[2] LAZEBNIK S， SCHMID C， PONCE J. Beyond bags of features： spatial pyramid matching for recognizing natural scene categories [C]// CVPR '06： Proceedings of the 2006 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE， 2006： 2169-2178.

[3] YANG J C， YU K， GONG Y H， et al. Linear spatial pyramid matching using sparse coding for image classification [C]// CVPR '09： Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE， 2009： 1794-1801.

[4] ZOU H， HASTIE T. Regularization and variable selection via the elastic net [J]. Journal of the Royal Statistical Society， 2005， 67（2）： 301-320.

[5] ZHANG Z， LAI Z H， XU Y， et al. Discriminative elastic-net regularized linear regression [J]. IEEE Transactions on Image Processing， 2017， 26（3）： 1466-1481.

[6] 張勇，張陽陽，程洪，等.基于非負彈性網(wǎng)稀疏編碼算法的圖像分類方法[J].計算機工程，2017，43（7）：239-243.（ZHNAG Y， ZHANG Y Y， CHENG H， et al. Image classification method based on non-negative elastic net sparse coding algorithm[J]. Computer Engineering， 2017， 43（7）： 239-243.）

[7] SHEN B， LIU B D， WANG Q F. Elastic net regularized dictionary learning for image classification [J]. Multimedia Tools and Applications， 2016， 75（15）： 8861-8874.

[8] YU K， ZHANG T， GONG Y. Nonlinear learning using local coordinate coding [C]// Proceedings of the 2009 Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009， 31： 927-936

YU K， ZHANG T， GONG Y. Nonlinear learning using local coordinate coding [EB/OL]. [2018-06-12]. http：//www.doc88.com/p-6971813767934.html.

[9] WANG J， YANG J， YU K， et al. Locality-constrained linear coding for image classification [C]// CVPR '10： Proceedings of the 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway， NJ： IEEE， 2010： 3360-3367.

[10] 劉培娜，劉國軍，郭茂組，等.非負局部約束線性編碼圖像分類算法[J].自動化學報，2015，41（7）：1235-1243.（LIU P N， LIU G J， GUO M Z， et al. Image classification based on non-negative locality constrained linear coding[J]. Acta Automatica Sinica， 2015， 41（7）： 1235-1243.）

[11] WU J， REHG J M. Beyond the Euclidean distance： creating effective visual codebooks using the Histogram intersection kernel [C]// ICCV '09： Proceedings of the 2009 IEEE 12th International Conference on Computer Vision. Piscataway， NJ： IEEE， 2009： 630-637.

[12] CHEN H， XIE K， WANG H， et al. Scene image classification using locality-constrained linear coding based on histogram intersection [J]. Multimedia Tools and Applications， 2018，77（3）：4081-4092.

[13] LEE H， BATTLE A， RAINA R， et al. Efficient sparse coding algorithms [C]// NIPS '06： Proceedings of the 19th International Conference on Neural Information Processing Systems. Cambridge， MA： MIT Press， 2006： 801-808.

[14] GAO S， TSANG I W-H， CHIA L-T， et al. Local features are not lonely-Laplacian sparse coding for image classification [C]// CVPR '10： Proceedings of the 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2010： 3555-3561.

[15] HAN H， LIU S， GAN L. Non-negativity and dependence constrained sparse coding for image classification [J]. Journal of Visual Communication and Image Representation. 2015， 26（C）： 247-254.

[16] 史瑩.基于Laplacian稀疏編碼的圖像分類研究[D].武漢：武漢理工大學，2016：30-31.（SHI Y. Image classification based on Laplacian sparse coding[D].Wuhan： Wuhan University of Technology， 2016：30-31.）

[17] CAI D. Four face databases in matlab format [DB/OL]. [2018-03-29]. http：//www.cad.zju.edu.cn/home/ dengcai/Data/FaceData.htm.