稀疏表示的圖像分類研究綜述

周　近

(江蘇第二師范學院，江蘇 南京　210013)

稀疏表示的圖像分類研究綜述

周近

(江蘇第二師范學院，江蘇 南京210013)

良好的特征提取方法能減輕后續(xù)圖像分類與識別的工作量。針對具體的分類問題提出了不同的特征提取方法，并在圖像分類和識別任務上取得了較好的效果。然而，已有的基于傳統(tǒng)方法的特征提取存在一些明顯不足，即隨著視覺任務規(guī)模的增大，直接利用這些傳統(tǒng)方法進行特征分類，效果并不理想。提出的特征表達方法，在圖像最基本特征基礎上進行矢量量化、稀疏編碼或其它表達以形成一幅圖像最后的特征。著重介紹基于稀疏表示的特征分類算法并對其進行分析，最后探討存在的問題和今后研究的方向。

稀疏表示；圖像分類；稀疏編碼；特征編碼

圖像的分類作為計算機視覺領域的重要組成部分，能夠有效地對圖像的內容進行分析，獲取圖像中的關鍵信息，并給出正確的判斷，對現(xiàn)實的工作生活及社會的發(fā)展具有重要的意義[1]。圖像分類包括圖像的預處理、圖像特征的提取、特征的降維及特征的選擇、分類器的設計等步驟。其中，視覺特征的提取是最基礎的工作也是最關鍵的步驟，它能有效地減輕對后續(xù)環(huán)節(jié)的依賴性，同時也制約著整個系統(tǒng)的性能表現(xiàn)。因此，針對具體的視覺問題或一系列的視覺任務，如何有效地提取特征是計算機視覺領域的一個熱點和難點。

特征提取[2]是一個綜合性的研究課題，涉及到圖像處理、模式識別、機器學習、生物學等領域的知識。其中，特征表達是指在最基本的特征基礎上進行統(tǒng)計(矢量量化)、編碼或其它方法以形成一幅圖像最后的特征，通常情況下會比原始的基本特征具有更好的性能；而特征學習是指從大量的圖像樣本數據中采用不同規(guī)模的網絡結構以及各種學習規(guī)則來學習出特征，具有方法上的統(tǒng)一性，即針對不同類型的輸入圖像，可以采用同樣的結構進行特征提取，不再需要人工設計特征。

近年來，稀疏編碼理論已經成為信號分析處理、計算機視覺分析、模式識別與控制等國內外學術界的重點研究方向。它作為一種降維方法，有效性高于一般算法，因此，稀疏編碼常被應用于圖像特征提取。根據國內外的相關研究，基于稀疏編碼的圖像特征提取框架可以分為特征提取(Feature Extraction)[3]、詞典學習(Dictionary Learning)[4]、特征編碼(Feature Coding)[5]和特征匯總(Feature Pooling)[5]這幾個步驟。其中，特征編碼是基于視覺詞典D(D=[d1,d2,…,dm]∈Rd×m，式中d與特征的維度相同，是視覺單詞的個數)，在滿足特定性質的條件下一般設定的性質包括致密性、稀疏性或統(tǒng)計獨立性,將圖片的n個高維的局部特(Local Feature)征轉換為編碼C=[c1,c2,…,cm]∈Rm×n。不同的編碼技術具有不同的規(guī)則和性質，因而對同一個局部特征會產生不同的編碼。近來，出現(xiàn)很多基于改進詞袋模型(Bag of Words, BoW)[6]的新方法，它們不僅能夠更加精確地表示圖像而且能夠提高這些方法的分類能力。圖像雖然在圖像分類方面取得了顯著的進展，但是在如何對一幅圖像的局部特征進行編碼方面仍然有很大的提升空間。近年來各種不同的編碼方法可以分成3類：

1)基于重構(Reconstruction)的編碼方式：稀疏編碼(Sparse Coding, SCSPM)[7]、局部約束線性編碼(Locality-constrained Linear Coding, LLC)[8]、局部約束稀疏自編碼器(Locality-constrained Sparse Auto-Encoder, LSAE)[9]、局部約束和空間規(guī)范的編碼(Locality-Constrained and Spatially Regularized Coding, LCSRC)[10]、低秩稀疏編碼(Low-Rank Sparse Coding, LRSC)[11]；

2)基于配置(Assignment)的編碼方式：硬分配編碼(Hard-assignment Coding, HC)[6]、軟分配編碼(Soft-assignment Coding, SaC)[12]、局部軟分配編碼(Localized Soft-assignment Coding, LSC)[13]；

3)基于顯著性(Salient)的編碼方式：顯著編碼(Salient Coding, SC)[14]、組顯著編碼(Group Salient Coding, GSC)[15]。

下面對常見的幾類編碼做詳細的介紹。

1　幾種特征編碼方法

定義bi∈Rd是字典中的視詞(基)，這里d代表局部特征的維度；矩陣MatrixB=[b1,b2,…,bn]代表字典或者說是視詞的集合，n代表視詞的個數;xi∈Rd是一幅圖像的第i個特征;zi∈Rn是xi的編碼，其中zij是bj的系數。

1.1硬分配編碼(Hard-assignmentCoding,HC)

對于一個局部特征xi有且僅有一個非零系數，根據預先設定好的距離尋找到離它最近的視詞(基)來給它編碼。該距離一般采用歐氏距離：

(1)

在視覺字典固定的情況下，硬分配編碼方法使用只含有1個非零元素的向量來表示1個特征，不可避免地會產生很大的量化誤差。而且在分類時若直接采用線性分類器，結果往往很差；而若采用非線性支持向量機，計算復雜度就會很高。

硬分配編碼方法會導致兩個問題:視覺單詞的不確定性和視覺單詞的合理性。視覺單詞的不確定性是指圖像局部特征到兩個或幾個視覺單詞的距離都很近,要從這兩個或幾個視覺單詞中選出一個“正確的”，硬分配編碼方法只選擇能最好表達局部特征的一個視覺單詞,而忽略其他候選視覺單詞的相關性；視覺單詞的合理性是指圖像局部特征到視覺詞典中所有視覺單詞的距離都很遠,但仍然要從這些不合理的候選者中選出一個去代表它。硬分配編碼方法給出了對于每個局部特征視覺詞典中最合適的單詞,但是忽略了這個所謂“最合適”的視覺單詞很可能并不真正代表局部特征。

1.2軟分配編碼(Soft-assignment Coding,SaC)

該方法的第j個編碼系數代表了局部特征xi和第j個視詞之間的匹配程度，α是平滑系數，同時定義有n個視詞用來計算zij：

(2)

該方法通過稍微降低表示的稀疏性，來達到高表示的性能的目的，雖然計算速度會降低，但是分類的準確性有較大的提升。

1.3局部軟分配編碼(Localized Soft-assignment Coding,LSC)

該方法基本思想是采用局部特征在字典中的k個近鄰視詞來更新Soft-assignment Coding：

(3)

實驗證明，該方法在分類問題上取得了非常好的效果，但是它并沒有真正解決視詞的合理性問題，有可能這k個視詞與局部特征之間的距離都很遠(都不相似)，而經過正則化之后變成了噪聲，從而影響編碼效果。

1.4稀疏編碼(Sparse Coding,SCSPM)

該方法使用稀疏集合和字典中基向量的線性組合來表示局部特征xi，在求解系數向量zi時，加入了l1范數的正則項：

(4)

該方法重建性能好，稀疏特征更加線性可分。實驗結果表明對較大的字典，該方法表現(xiàn)出更好的性能，與前面提到的向量化方法相比，該方法造成的量化損失較小。稀疏性是由正則項控制的，以保證學習到的表達能捕捉到局部特征的顯著模式。但是為了保證稀疏性，它非常有可能對相似的局部特征選擇完全不同的視詞，導致編碼之間的相關性較弱。

1.5局部約束線性編碼(Locality-constrainedLinearCoding,LLC)

和上面說的SCSPM方法不同，該方法考慮更多的是局部性而不是稀疏性，這就造成了相關系數小的基向量遠離xi，用一個局部約束項來代替SCSPM中的稀疏約束項，編碼zi的計算就變成了解決以下正則化的最小二乘問題：

(5)

其中，

di=exp(dist(xi,B)/δ,dist(xi,B))=

(dist(xi,b1),dist(xi,b2),…,dist(xi,bn))T

(6)

dist(xi,bj)定義為xi和bj之間的l2距離，δ是一個正的參數，用于調整局部性適配器的權重衰退速度。上式中第1項限制了重建損失，第2項保證了相似的局部特征可以獲得相似的編碼。該方法提出后，在圖像分類中取得了非常好的效果，它的優(yōu)勢在于：具有良好的重建性能，具有局部的光滑性，編碼具有解析解(不需要迭代)。

1.6拉普拉斯稀疏編碼(LaplacianSparseCoding,LScSPM)

這是第一種對稀疏編碼一致性進行改進的方法，它考慮了數據庫中相似的局部特征應該具有相似的稀疏編碼。該算法通過在LASSO問題中加入圖嵌入的正則項來實現(xiàn)，字典的學習和稀疏編碼的求解可以通過交替迭代得到：

(7)

這里L是拉普拉斯矩陣，它在編碼時考慮了局部特征之間的關系，i為樣本數目。由于數據庫中的特征非常多，當構建拉普拉斯矩陣和學習稀疏編碼同時進行時計算上是不可行的，所以產生了一些具有啟發(fā)性的措施來改善計算復雜度。

1.7顯著編碼(Salient Coding,SC)

(8)

1.8組顯著編碼(Group Saliency Coding,GSC)

定義si(k)是fi(特征向量)根據group code的大小得到的編碼結果，φ(k)(fi)是經過改進的顯著性程度的描述函數

(9)

(10)

g(fi,k)是由距離fi最近的k個視詞組成的codewords，k是group-code尺寸的最大值。

GaSC的主要思想是考慮了fi的group-code和其他codewords之間的相對位置。對于不同的k，總能找到固定的k+1個近鄰codewords來給每個特征編碼，這k個最近的基放在group-codes中，其中，第k個codeword作為group-code中最具代表性的元素用以計算顯著性的程度。

1.9低秩稀疏編碼(Low-Rank Sparse Coding,LRSC)

定義X是由SIFT描述子組成的矩陣，每一列代表一個局部特征點，通常是128維的，D為字典，在沒有噪聲的情況下，局部特征xi可以由字典中的基線性表示，寫成矩陣的形式就是：X=DZ

(11)

1.10局部約束稀疏自編碼器(Locality-constrainedSparseAuto-Encoder,LSAE)

在基于字典的編碼方法中，當給定字典D后，往往需要求解一個優(yōu)化算法來獲得輸入x的碼字，其計算復雜度隨著字典規(guī)模增大而增大。另一方面，基于自動編碼器的編碼模式只需要簡單的內積運算和一個非線性變換就能獲取碼字，但其在編碼過程中丟失了近鄰性。因此把基于字典編碼中的近鄰性引入自動編碼器中，使得自動編碼器在快速獲取碼字的同時能充分利用近鄰性，使得相似的輸入能夠采用相似的基來編碼，從而使得最后的碼字具有相似的結構。該方法的優(yōu)點在于：

(1)相對于視覺領域的字典編碼來說，LSAE能夠快速學習字典，并且只需要簡單的前饋操作就能獲得碼字；

(2)相對于傳統(tǒng)的(稀疏)自動編碼器來說，LSAE在獲取碼字過程中充分利用了輸入與基之間的近鄰性，使得碼字更為魯棒；

(3)相對于LLC自動編碼器來說，其學習效率更高。

存在的問題是：當字典規(guī)模非常大時，有些基仍很難學習到有用的特征。

2　編碼方法討論

現(xiàn)階段的研究表明:給定一個字典，局部特征的編碼方法將顯著影響著分類性能。最早的方法是硬分配編碼(HC)，這種方法雖然簡單，但是它對于字典的選擇十分敏感，而且量化誤差較大，因此出現(xiàn)了一個更加魯棒的方案軟分配編碼方法(SC),它在提高分類性能的同時付出了一定的時間代價。為了改進軟分配和硬分配這兩種編碼方法，通過稀疏學習的技術在圖像局部特征編碼中引入了稀疏性[7]，但是稀疏編碼非常耗時而且常常導致編碼不穩(wěn)定，比如，具有相似描述子的局部特征會有不同編碼。為了消除這種不穩(wěn)定性，有人提出了另一種編碼方案[15]。這種體現(xiàn)局部性的編碼方法讓那些代表局部特征的視詞(字典中的基)和特征描述子之間盡可能地相似，這就需要從原來的字典中選擇和特征描述子最近鄰的幾個視詞作為特征字典，這樣圖像的描述子就可以用這些局部選擇出來的基來編碼。然而，在前面所提到的這些編碼方案中，每個特征的編碼都是相對獨立的。在拉普拉斯稀疏編碼(LScSPM)[16]方法中，在引入稀疏限制的同時還考慮了局部特征之間的全局相似性，但是這種方法在特征集合較大的時候計算量巨大，而且沒有結合相應特征的稀疏編碼和空間布局之間的關系?？臻g一致性要求在圖像中空間位置相近的點應該具有相似的稀疏編碼，并可以由相似的字典中的基來表示。鑒于這種思想又出現(xiàn)了低秩稀疏編碼(LRSC)，兼顧了稀疏性、局部性和空間一致性信息。顯著編碼(SaC) 的提出主要是為了解決局部約束線性編碼(LLC)在編碼過程中存在信息的丟失問題所進行的改進，組顯著編碼(GSaC)又對顯著編碼存在不能處理較大字典的問題進行了修改。

3　總結

研究結果表明：有效的特征表達方法能夠極大地改善視覺圖像分類和識別的性能，而分類的準確率很大程度上依賴特征編碼的具體方式。本文介紹了比較具有影響力的幾種特征編碼方法的原理、設計動機、優(yōu)越性以及存在的問題。通過總結歸納發(fā)現(xiàn)，這些方法仍然是基于淺層模型的特征描述方法，它們的特征表達能力是有限的。所以最近深度學習在圖像分類的任務中發(fā)揮了越來越重要的作用，主要因為它屬于更深一層的模型，抽象效果更好，具有較強的特征表達能力，能夠顯著地提高分類的準確率，是一個非常前沿的研究方向且具有廣泛的應用前景。

[1]LuD,WengQ.Asurveyofimageclassificationmethodsandtechniquesforimprovingclassificationperformance[J].InternationalJournalofRemoteSensing, 2007,28(5):823-870.

[2]NixonMS,AguadoAS.FeatureExtractionandImageProcessing[M].London:Elsevier,2008.

[3]YuN,QiuT,BiF,etal.ImageFeaturesExtractionandFusionBasedonJointSparseRepresentation[J].IEEEJournalofSelectedTopicsinSignalProcessing, 2011,5(5):1 074-1 081.

[4]YangM,ZhangL,FengX,etal.FisherDiscriminationDictionaryLearningforsparserepresentation[C]∥2011IEEEInternationalConferenceonComputerVision(ICCV),Piscataway:IEEE, 2011:543-550.

[5]GaoSH,TsangIWH,ChiaLT.SparseRepresentationWithKernels[J].IEEETransactionsonImageProcessing, 2013,22(2):423-434.

[6]LazebnikS,SchmidC,PonceJ.Beyondbagsoffeatures:spatialpyramidmatchingforrecognizingnaturalscenecategories[C]∥ComputerVisionandPatternRecognition,NewYork:IEEE, 2006:2 169-2 178.

[7]YangJ,YuK,GongY,etal.Linearspatialpyramidmatchingusingsparsecodingforimageclassification[C].ComputerVisionandPatternRecognition,NewYork:IEEE, 2009:1 794-1 801.

[8]WangJ,YangJ,YuK,etal.Locality-constrainedlinearcodingforimageclassification[C]∥ComputerVisionandPatternRecognition(CVPR),NewYork:IEEE, 2010:3 360-3 367.

[9]LuoW,YangJ,XuW,etal.Locality-constrainedSparseAuto-EncoderforImageClassification[J].IEEESignalProcessingLetters, 2015,22(8):1 070-1 073.

[10]ShabouA,BorgneHL.Locality-constrainedandspatiallyregularizedcodingforscenecategorization[C]∥ComputerVisionandPatternRecognition(CVPR),NewYork:IEEE, 2012:3 618-3 625.

[11]ZhangT,GhanemB,LiuS,etal.Low-RankSparseCodingforImageClassification[C]∥ComputerVision(ICCV),Piscataway:IEEE, 2013:281-288.

[12]GemertJCV,GeusebroekJ-M,VeenmanCJ,etal.KernelCodebooksforSceneCategorization[C]∥10thEuropeanConferenceonComputerVision,Heidelberg:springerVerlap, 2008:696-709.

[13]LiuL,WangL,LiuX.Indefenseofsoftassignmentcoding[C]∥ComputerVision(ICCV),Piscataway:IEEE, 2011:

2 486-2 493.

[14]HuangY,HuangK,YuY,etal.Salientcodingforimageclassification[C]∥ComputerVisionandPatternRecognition(CVPR),NewYork:IEEE, 2011:1 753-1 760.

[15]YuK,ZhangT,GongY.NonlinearLearningusingLocalCoordinateCoding[C]∥AdvancesinNeuralInformationProcessingSystems22 (NIPS2009),Vancourer:CurranAssociats, 2009:1-9.

[16]GaoS,TsangIW-H,ChiaL-T,etal.Localfeaturesarenotlonely-laplaciansparsecodingforimageclassification[C]∥ComputerVisionandPatternRecognition(CVPR),NewYork:IEEE, 2010:3 555-3 561.

(責任編輯：李華云)

Survey of Image Classification Based on Sparse Representation

ZHOU Jin

(Jiangsu Second Normal University, Nanjing Jiangsu210013, China)

Good feature extraction method can reduce the workload of subsequent image classification and recognition. Different feature extraction methods are proposed for the specific classification problem, and achieved good results in image classification and recognition tasks. However, there are some obvious shortcomings of the existing feature extraction based on the traditional method. With the increasing of the size of the visual task, direct use of these traditional methods for feature classification is not ideal. The feature expression method is proposed, which is based on the most basic features of the image, and the sparse encoding or other expressions are proposed to form a final image.Based on sparse representation and its analysis, this paper focused on the feature classification algorithm and finally discussed the existing problems and future research directions.

sparse representation; image classification; sparse coding; feature coding

10.16018/j.cnki.cn32-1650/n.201503011

2015-04-21

江蘇省高校自然科學研究(12KJD510006, 13KJD520004)資助

周近(1978-)，女，江蘇丹陽人，實驗師，主要研究方向為圖像處理與模式識別。

TP391.41

A

1671-5322(2015)03-0047-05