徐健　常志國(guó)　趙小強(qiáng)

摘 要：綜述了字典學(xué)習(xí)算法的主要研究方向之一，即以圖像分類為目標(biāo)的稀疏表示字典學(xué)習(xí)算法。從空間變換法和類別指示法兩個(gè)角度，分析各種算法的優(yōu)缺點(diǎn)，并對(duì)相應(yīng)的實(shí)驗(yàn)結(jié)果進(jìn)行比較?？偨Y(jié)了利用這類算法進(jìn)行圖像分類時(shí)所面臨的其他一些關(guān)鍵問題，如模式識(shí)別中的旋轉(zhuǎn)不變性和計(jì)算速度等。依據(jù)目前已有的技術(shù)和應(yīng)用需求，探尋該領(lǐng)域未來的研究方向。

關(guān)鍵詞：圖像分類；稀疏表示；字典訓(xùn)練；原子

中圖分類號(hào)：TN391?34 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1004?373X（2013）02?0022?04

信號(hào)稀疏分解方法被廣泛的應(yīng)用于圖像處理的各個(gè)領(lǐng)域。但是與具有完美數(shù)學(xué)形式的信號(hào)分解算法，如離散傅里葉變換（Discrete Fourier Transform，DFT）[1]、離散小波變換（Discrete Wavelet Transform，DWT）[2]和傳統(tǒng)的主成分分析法（Principle Component Analysis，PCA）不同，近年來許多人提出的信號(hào)稀疏分解算法不再要求稀疏表示矩陣為正交完備基底[3?4]。非正交過完備的表示矩陣被人們稱為字典。稀疏表示矩陣可以由機(jī)器學(xué)習(xí)算法產(chǎn)生，這類算法稱為字典學(xué)習(xí)算法。人們已經(jīng)證明了當(dāng)使用非正交過完備字典對(duì)信號(hào)進(jìn)行稀疏表示時(shí)，能夠最稀疏表示一個(gè)樣本的字典系數(shù)是惟一的[5]。

1959年David Hubel和Toresten Wiesel通過對(duì)貓的視覺條紋皮層簡(jiǎn)單細(xì)胞感受野的研究得出一個(gè)結(jié)論：主視皮層V1區(qū)神經(jīng)元的感受野能對(duì)視覺感知信息產(chǎn)生一種“稀疏表示”，證明了稀疏表示符合視覺感知特性[6]。1993年Mallat等首次提出了應(yīng)用過完備冗余原子庫(kù)對(duì)信號(hào)進(jìn)行稀疏分解的思想，并引入了匹配追蹤算法，為非正交過完備字典的應(yīng)用提供了理論基礎(chǔ)[7?8]。自2009年以來，過完備冗余字典的稀疏表示方法成為圖像處理領(lǐng)域和模式識(shí)別領(lǐng)域的研究熱點(diǎn)，被廣泛應(yīng)用于解決計(jì)算機(jī)視覺方面的問題，如圖像去噪、圖像修補(bǔ)、圖像超分辨率放大和圖像分類等[9?11]。從目前的研究現(xiàn)狀來看，這類字典學(xué)習(xí)算法已經(jīng)成為一個(gè)研究熱點(diǎn)，專為圖像分類而設(shè)計(jì)的字典學(xué)習(xí)算法就有幾十種。人們希望通過稀疏字典學(xué)習(xí)算法真正揭示人類視覺特性和圖像語(yǔ)義之間的關(guān)系。本文將這些字典學(xué)習(xí)算法的研究思路總結(jié)為兩大類，并根據(jù)目前的研究提出該領(lǐng)域未來可能的發(fā)展方向。

1 圖像分類

圖像分割、圖像識(shí)別等問題都可以歸為圖像分類問題。在利用稀疏表示進(jìn)行的圖像分類研究中，如何設(shè)計(jì)對(duì)特征提取有效的字典和投影是決定算法性能最關(guān)鍵的因素[3]。

傳統(tǒng)的基于逼近的稀疏表示字典訓(xùn)練模型為：

式中：[X]為訓(xùn)練樣本矩陣，每列代表一個(gè)訓(xùn)練樣本；[D]為待訓(xùn)練的字典；[A]為表示系數(shù)；[ai]是組成[A]矩陣的列向量；[?F]表示矩陣的F范數(shù)；[?0]表示向量的0范數(shù)。該字典訓(xùn)練模型的意義是在滿足[ai]的0范數(shù)約束情況下能達(dá)到殘差最小。為了完成圖像分類任務(wù)，人們?cè)谠撃Ｐ偷幕A(chǔ)上思考出許多改進(jìn)方案。

在解決圖像分類問題的過程中，根據(jù)對(duì)稀疏表示特征的利用方式不同，利用稀疏表示進(jìn)行圖像分類的方案可以分為2類：

（1）設(shè)計(jì)字典把圖像變化到有利于分類的空間上，把稀疏系數(shù)放入傳統(tǒng)分類器進(jìn)行分類，稱之為空間變換法。

（2）設(shè)計(jì)字典原子與語(yǔ)義直接對(duì)應(yīng)， 利用稀疏系數(shù)大小所表示出的樣本屬性進(jìn)行分類。稱之為類別指示法。

式（1）所示的問題是雙變量?jī)?yōu)化問題，因此在迭代過程中大多使用固定一個(gè)變量?jī)?yōu)化另一個(gè)變量的交替優(yōu)化算法[4]。本文后續(xù)所綜述的算法，凡是涉及字典學(xué)習(xí)算法的雙變量?jī)?yōu)化問題，均使用交替迭代的優(yōu)化算法進(jìn)行，本文后續(xù)的內(nèi)容只描述字典訓(xùn)練模型，不再贅述優(yōu)化算法。

2 空間變換法

當(dāng)樣本本身不易分類時(shí)，可以利用稀疏表示字典將其變換到易于分類的空間上去。為了讓這個(gè)空間有利于分類，需要在式（1）所示的字典訓(xùn)練模型的基礎(chǔ)上加入一些約束。

文獻(xiàn)[12]建立字典訓(xùn)練模型時(shí)，針對(duì)每個(gè)類訓(xùn)練一個(gè)字典。該算法的字典訓(xùn)練模型為式（2）。

[minDjNj=1i=1…Nl∈SiCλiR*xl，DjNj=1+λγR*xl，Di，yj=R*xl，Dj，Cλiy1，y2，…，yN=logj=1Ne-λyj-yi，R*x，D=x-Da*x，D22，a*x，D=argminα∈?kx-Da22，s.t. a0L] （2）

式中：[xl]是第[l]個(gè)訓(xùn)練樣本；[Dj]是第[j]個(gè)類別對(duì)應(yīng)的字典；[L]是稀疏度。式（2）中在減少稀疏殘差的基礎(chǔ)上，將優(yōu)化目標(biāo)變成殘差之間大小關(guān)系，其中的[Cλi]使用了logistic函數(shù)，保證了這些字典在對(duì)自己所對(duì)應(yīng)類別的樣本進(jìn)行稀疏表示時(shí)殘差比較小，在對(duì)其他類別的樣本進(jìn)行稀疏表示時(shí)殘差比較大。該算法本質(zhì)是將樣本矢量[x]映射為高維矢量[a]，然后使用K近鄰算法判斷類別。

但是由于logistic函數(shù)的運(yùn)算量較大，該算法在考慮迭代算法時(shí)需要進(jìn)行二階泰勒近似以降低運(yùn)算復(fù)雜度。并且該算法針對(duì)每個(gè)類別都要訓(xùn)練一個(gè)字典。在分類時(shí)，樣本需要在所有的字典下根據(jù)稀疏度約束進(jìn)行稀疏表示，對(duì)比其殘差才能確定類別。因此算法復(fù)雜度較高。為了降低分類時(shí)算法的復(fù)雜度，文獻(xiàn)[13]提出了只用一個(gè)字典就能區(qū)分多個(gè)類別的字典訓(xùn)練模型，如式（3）所示：

[minD，θ（i=1mμCS*xi，D，θ，-yi-S*xi，D，θ，yi+1-μS*xi，D，θ，yi）+λ2θ22，Sai，xi，D，θ，yi=Cyifxi，ai，θ+λ0xi-Dai22+λ1ai1，yi=R*xi，DCx=log1+e-x，fx，a，θ=wTa+b或fx，a，θ=xTWa+b，θ=W∈Rn×k，b∈R] （3）

該算法借助了支持向量機(jī)（Support Vector Machine，SVM）思想，試圖將線性分類器和字典[D]均作為訓(xùn)練對(duì)象。優(yōu)化目標(biāo)兼顧正確判決的[S*]和錯(cuò)誤判決[S*]之差及稀疏表示殘差，并加入了線性分類器（或雙線性分類器）的條件。通過理論分析，得出該算法在研究分類框架時(shí)兼顧了泛化能力，這樣就避免了過擬合現(xiàn)象，并且提高了該算法的魯棒性。但是該算法沒有解決線性組合系數(shù)[μ]如何選取的問題。而且，盡管分類時(shí)算法復(fù)雜度降低了，分類器訓(xùn)練的過程算法復(fù)雜度仍然很高。無法針對(duì)維數(shù)較高的樣本進(jìn)行訓(xùn)練。

文獻(xiàn)[14]提出了一種圖像分類算法，其主要思路是在優(yōu)化稀疏表示殘差的同時(shí)降低字典間的相關(guān)性。其字典訓(xùn)練模型如式（4）所示：

[minDi，AiXi-DiAi2F+ηj≠iDTjDi，ai0

式中：[Xi]為第[i]類樣本；[Di]是對(duì)應(yīng)第[i]類樣本的字典[Ai]是表示系數(shù)，[η]是拉格朗日參數(shù)。該字典訓(xùn)練方法不但考慮了在固定稀疏度情況下的稀疏表示殘差，還把字典間的相關(guān)性作為約束條件。

實(shí)際上，如圖1所示，假設(shè)[Dj∈Rmj×nj]是固定的，[dkjnjk=1]是[Dj]中的原子。那么訓(xùn)練得到的[Di]，如果和[Dj]互不相交的話，那么[Di]的所有原子只能位于[Dj]的正交補(bǔ)[Φ]上。如果[Dj]是過完備且列滿秩的字典，理論上[Di]不可能和[Dj]完全正交。因此它們之間一定存在不正交的原子。為了提高字典間的正交性，每個(gè)字典盡量都不占用更大的空間。這一點(diǎn)可以通過降低字典維數(shù)來得到。由于相關(guān)性的要求，每個(gè)類別的字典的訓(xùn)練過程都被限制在與其他字典盡量不相關(guān)的狹小空間內(nèi)尋找原子，而這些狹小空間未必能夠以較小殘差對(duì)該類樣本進(jìn)行稀疏表示。因此相關(guān)性降低和稀疏表示殘差是一對(duì)矛盾。較小的相關(guān)性必然帶來較大的殘差，而較小的殘差會(huì)導(dǎo)致相關(guān)性增強(qiáng)。

圖1 字典間相關(guān)性的三維示意圖

因此對(duì)這類字典進(jìn)行訓(xùn)練的迭代算法必須要平衡相關(guān)性和殘差之間的矛盾。并且該算法沒有解決在同時(shí)優(yōu)化字典和系數(shù)2個(gè)變量時(shí)如何選取最優(yōu)步長(zhǎng)的問題。不合適的步長(zhǎng)將會(huì)導(dǎo)致2個(gè)變量不能同時(shí)收斂。

[minW∈Rm×p，D∈DEy，xlog1+e-yxTWα*x，D+v2W2F] （5）

隨后文獻(xiàn)[15]中對(duì)前面提出的算法做出了改進(jìn)，提出了如式（5）描述的字典訓(xùn)練模型。

該算法對(duì)logistic函數(shù)的運(yùn)算結(jié)果的均值作為優(yōu)化目標(biāo)，并且使用雙線性函數(shù)訓(xùn)練分類器提高了算法的泛化能力。盡管雙線性函數(shù)的參數(shù)眾多導(dǎo)致訓(xùn)練復(fù)雜度提高，但是卻為分類器提供了更多靈活性，避免了過擬合現(xiàn)象。但是該算法僅僅在手寫數(shù)字識(shí)別等問題上進(jìn)行了測(cè)試。對(duì)于更加大型或復(fù)雜問題的實(shí)驗(yàn)仍然有待進(jìn)一步研究。上述幾種算法都針對(duì)MNIST和USPS手寫數(shù)字識(shí)別進(jìn)行了實(shí)驗(yàn)，每個(gè)文章中算法的最佳實(shí)驗(yàn)結(jié)果如表1所示。REC是使用式（1）所示的字典訓(xùn)練模型訓(xùn)練字典得到的分類錯(cuò)誤率。A是文獻(xiàn)[13]的最佳實(shí)驗(yàn)結(jié)果。B是文獻(xiàn)[14]的實(shí)驗(yàn)結(jié)果。C是文獻(xiàn)[15]提出的算法在無監(jiān)督學(xué)習(xí)過程中的實(shí)驗(yàn)結(jié)果。D是文獻(xiàn)[15]提出的算法在有監(jiān)督學(xué)習(xí)過程中的實(shí)驗(yàn)結(jié)果。K?NN是K近鄰算法分類的實(shí)驗(yàn)結(jié)果（其中K為10）。SVM?Gauss是SVM算法在使用高斯核函數(shù)時(shí)的實(shí)驗(yàn)結(jié)果[16]。

文獻(xiàn)[12?15]都是將稀疏表示系數(shù)作為特征進(jìn)行圖像分類，其本質(zhì)是將圖像映射到便于分類的空間上去，然后運(yùn)用傳統(tǒng)的分類算法（如K近鄰，SVM算法）進(jìn)行分類。由于稀疏表示本身對(duì)于噪聲具有魯棒性。因此，運(yùn)用該方法的分類算法有較低的錯(cuò)誤率。

表該算法首先對(duì)圖像進(jìn)行極坐標(biāo)映射。假設(shè)[a，b]是圖像本身的坐標(biāo)，則通過式（6）將其映射為[ξ，η]。然后再通過Rapid變換將其變?yōu)槠揭撇蛔兲卣?。最后將變換過的具有平移不變性的圖像作為訓(xùn)練樣本進(jìn)行字典學(xué)習(xí)。這樣學(xué)習(xí)得到的字典可以提取到圖像的平移和旋轉(zhuǎn)不變的特征。由于目前存在的字典學(xué)習(xí)算法都采用雙變量迭代更新的方法，且迭代步驟中都存在奇異值分解等運(yùn)算規(guī)模較大的步驟，因此大多數(shù)都是利用低于100維的數(shù)據(jù)進(jìn)行字典學(xué)習(xí)[20?21]。當(dāng)遇到了較大圖像的字典學(xué)習(xí)問題，都采用將數(shù)據(jù)分割成小塊分別處理[10]。為了加快字典學(xué)習(xí)速度，文獻(xiàn)[22]提出了使用GPU并行技術(shù)來解決較大圖像的分類識(shí)別問題。利用GPU技術(shù)來提高各種圖像處理算法的速度將是未來圖像處理發(fā)展的趨勢(shì)。

5 結(jié) 論

從上述研究現(xiàn)狀來看，目前的用于分類識(shí)別的稀疏字典訓(xùn)練還缺乏字典參數(shù)與語(yǔ)義之間的關(guān)系的論證，因此下一步的研究應(yīng)當(dāng)關(guān)注如何從字典訓(xùn)練過程揭示圖像語(yǔ)義方面的問題。另外，稀疏表示的特征提取方法還處于起步階段。

上述文獻(xiàn)所涉及算法僅僅在小規(guī)模的較簡(jiǎn)單的分類問題上進(jìn)行了測(cè)試，還沒有觸及更加大型和復(fù)雜的問題。因此，對(duì)這類方法的應(yīng)用還有待進(jìn)一步開發(fā)。稀疏表示的字典訓(xùn)練往往涉及優(yōu)化問題，需要大量的樣本參與運(yùn)算，算法復(fù)雜度較高。盡管已經(jīng)有少部分研究人員利用GPU技術(shù)進(jìn)行仿真實(shí)驗(yàn)，但是如何專門為GPU設(shè)計(jì)迭代算法，充分發(fā)揮GPU的并行計(jì)算能力，也是該領(lǐng)域未來的發(fā)展方向。

隨著基于訓(xùn)練的字典模型理論的完善，信號(hào)處理將不再局限于以傳統(tǒng)的正交完備基為理論基礎(chǔ)。非正交過完備字典以其符合人眼感知機(jī)理、系數(shù)稀疏性、魯棒性和靈活性等優(yōu)勢(shì)將成為未來信號(hào)處理研究的主流。

參考文獻(xiàn)

[1] 季虎，夏勝平，郁文賢.快速傅里葉變換算法概述[J].現(xiàn)代電子技術(shù)，2001，24（8）：11?14.

[2] 周義明，張超，張化民.樣條小波的構(gòu)造方法及其應(yīng)用[J].現(xiàn)代電子技術(shù)，2009，32（8）：36?40.

[3] WRIGHT J， MA Y， MAIRAL J， et al. Sparse representation for computer vision and pattern recognition [J]. Proceedings of the IEEE， 2010， 98（6）： 1031?1044.

[4] AHARON Michal， ELAD Michael， BRUCKSTEIN Alfred. K?SVD： An algorithm for designing overcomplete dictionaries for sparse representation [J]. IEEE Transactions on Signal Processing， 2006， 54（11）： 4311?4322.

[5]AHARON M， ELAD M， BRUCKSTEIN A M. On the uniqueness of overcomplete dictionaries， and a practical way to retrieve them [J]. Linear algebra and its applications， 2006， 416（1）： 48?67.

[6] HUBEL D H， WIESEL T N. Receptive fields of single neurones in the cat's striate cortex [J]. The Journal of physiology， 1959， 148（3）： 574?591.

[7]王建英，尹忠科，張春梅.信號(hào)與圖像的稀疏分解及初步應(yīng)用[M].成都：西南交通大學(xué)出版社，2006.

[8] MALLAT S G， ZHANG Z. Matching pursuits with time?frequency dictionaries [J]. IEEE Transactions on Signal Processing， 1993， 41（12）： 3397?3415.

[9] XU Z， SUN J. Image inpainting by patch propagation using patch sparsity [J]. IEEE Transactions on Image Processing， 2010， 19（5）： 1153?1165.

[10] ELAD M， AHARON M. Image denoising via sparse and redundant representations over learned dictionaries [J]. IEEE Transactions on Image Processing， 2006， 15（12）： 3736?3745.

[11] ZHANG Hai?chao， ZHANG Yan?ning， HUANG THOMAS S. Efficient sparse representation based image super resolution via dual dictionary learning [C]// IEEE International Conference on Multimedia and Expo. Barcelona， Spain： IEEE， 2011： 1?6.

[12] MAIRAL J， BACH F， PONCE J， et al. Discriminative learned dictionaries for local image analysis [C]// IEEE Conference on Computer Vision and Pattern Recognition. Anchorage， Alaska， USA： IEEE， 2008： 1?8.

[13] MAIRAL J.， BACH F.， PONCE J.， et al. Supervised dictionary learning[C]//Annual Conference on Neural Information Processing Systems. Vancouver， BC， Canada： CNIPS， 2008： 1?6.

[14] RAMIREZ I， SPRECHMANN P， SAPIRO G. Classification and clustering via dictionary learning with structured incoherence and shared features [C]// IEEE Conference on Computer Vision and Pattern Recognition. San Francisco， CA， USA： IEEE， 2010： 3501?3508.

[15] MAIRAL J， BACH F， PONCE J. Task?driven dictionary learning [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2012， 34（4）： 791?804.

[16] LECUN Y， BOTTOU Y， BENGIO Y. Gradient?based learning applied to document recognition [J]. Proceedings of IEEE， 1998， 86（11）： 2278?2324.

[17] WRIGHT J， YANG A Y， GANESH A， et al. Robust face recognition via sparse representation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 31（2）： 210?227.

[18] YANG M， ZHANG L. Gabor feature based sparse representation for face recognition with Gabor occlusion dictionary [C]// Proceedings of the 11th European Conference on Computer Vision. Berlin： Springer?Verlag， 2010： 448?461.

[19] BAR L， SAPIRO G. Hierarchical dictionary learning for invariant classification [C]// Proceedings of 2010 IEEE International Conference on Acoustics， Speech， and Signal Processing. Dallas， TX， USA： IEEE， 2010： 3578?3581.

[20] MAIRAL J， BACH F， PONCE J， et al. Online dictionary learning for sparse coding [C]// Proceedings of Annual International Conference on Machine Learning. Montreal， QC， Canada： AICML， 2009： 689?696.

[21] ZOLTAN S， BARNABAS P， ANDRAS L. Online group?structured dictionary learning [C]// Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Colorado Springs， CO， USA： IEEE， 2011： 2865?2872.

[22] NAGESH P， GOWDA R， LI B. Fast GPU implementation of large scale dictionary and sparse representation based vision problems [C]// Proceedings of 2010 IEEE International Conference on Acoustics， Speech， and Signal Processing. Dallas， TX， USA： IEEE， 2010： 1570?1573.