余沁茹,盧桂馥,李 華

(1 蕪湖職業(yè)技術(shù)學(xué)院, 安徽 蕪湖 241000; 2 安徽工程大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 蕪湖 241009)

在圖像處理過程中,圖像本身的表示形式是影響處理結(jié)果的關(guān)鍵因素。稀疏表示已被證明是一種極有效的圖像表示算法[1]。近年來,為了實(shí)現(xiàn)稀疏表示,研究人員已經(jīng)開發(fā)出例如稀疏主成分分析(PCA)[2]、稀疏非負(fù)矩陣分解(NMF)[3]等多種算法。作為稀疏表示最典型的方法之一,稀疏編碼(spares coding,SC)在機(jī)器學(xué)習(xí)、信號處理和神經(jīng)科學(xué)[4-7]等領(lǐng)域中得到了廣泛的關(guān)注。

SC是利用過完備字典來線性表示圖像的編碼過程,其中的非零元素只占所有元素的極小部分,體現(xiàn)了編碼的稀疏性。SC具有眾多優(yōu)點(diǎn),如:稀疏表示時其每個數(shù)據(jù)點(diǎn)都表示為少量基本矢量的線性組合,表示方式更簡潔;編碼狀的稀疏表示可以允許數(shù)據(jù)快速檢索等。SC算法目前已被應(yīng)用于如圖像恢復(fù)[8]、信號分類[9]、人臉識別[10]和圖像分類[11-12]等多個領(lǐng)域中。

近年來,研究人員針對SC的部分缺點(diǎn)提出了改進(jìn)算法。對于SC計(jì)算復(fù)雜度過高的問題,文獻(xiàn)[10]提出了一種迭代的軟閾值方法,該方法在負(fù)梯度方向上取Barzilai-Borwein步長,然后將軟閾值算子應(yīng)用于結(jié)果,提升了SC的計(jì)算速率。 Lee等[13]提出了一種特征符號搜索方法,將不可微L1范數(shù)問題簡化為L1正則化最小二乘問題,從而加快了優(yōu)化過程。在傳統(tǒng)方法中,SC的字典選擇也是影響算法效果的一個關(guān)鍵因素,然而其字典一般是從標(biāo)準(zhǔn)庫中選擇的[14],甚至是從隨機(jī)矩陣[15]中生成的。因此,有些學(xué)者試圖通過為稀疏編碼設(shè)計(jì)一個更合適的字典來提升SC的性能。Aharon 等[16]提出的K-SVD方法不同于之前利用標(biāo)準(zhǔn)庫獲得數(shù)據(jù)稀疏表示的算法,該算法使用正交匹配追蹤算法(orthogonal matching pursuit, OMP)或基追蹤算法(basis pursuit, BP),作為其學(xué)習(xí)詞典迭代過程的一部分。還有些學(xué)者致力于將稀疏編碼與經(jīng)典機(jī)器學(xué)習(xí)方法相結(jié)合以提出新的理論框架。文獻(xiàn)[17]將線性判別分析(linear discriminant analysis, LDA)與稀疏表示相結(jié)合提出了稀疏主成分判別分析的方法(sparse linear discriminant analysis,SDA),該方法可以通過重建特性、辨別力和稀疏性來進(jìn)行分類。文獻(xiàn)[11]提出了一種新的判別方法,稱為監(jiān)督字典學(xué)習(xí)算法(supervised dictionary learning,SDL),有效地利用圖像分類任務(wù)中相應(yīng)的稀疏信號分解去學(xué)習(xí)共享字典和判別模型。

以上研究都在克服原始稀疏編碼的不同缺點(diǎn),但是都沒有考慮到數(shù)據(jù)中潛在的幾何結(jié)構(gòu)。Kavukcuoglu等[18]提出了幾種稀疏編碼方法的變體,這些算法通過增加一些稀疏編碼系數(shù)的附加約束來捕獲數(shù)據(jù)中的結(jié)構(gòu),即它們可以通過添加額外的空間一致約束來學(xué)習(xí),以獲得局部不變的稀疏表示。Gao等[19]首次提出了使用流形學(xué)習(xí)算法學(xué)習(xí)數(shù)據(jù)幾何結(jié)構(gòu)的方法,但未明確提出詳細(xì)的優(yōu)化方案,所提方法的性能僅在圖像分類任務(wù)上進(jìn)行了評估。Zheng等[20]在文獻(xiàn)[19]的基礎(chǔ)上提出了一種新的算法,稱為圖正則化稀疏編碼(graph regularization sparse coding,GraphSC),該算法明確考慮了數(shù)據(jù)的局部幾何結(jié)構(gòu)。 GraphSC通過構(gòu)建一個近鄰圖來編碼數(shù)據(jù)中的幾何信息,并使用譜圖理論中的圖拉普拉斯算子作為光滑算子來保留局部流形結(jié)構(gòu)。與傳統(tǒng)的SC算法相比,GraphSC具有更強(qiáng)大的分類能力。基于文獻(xiàn)[20]的研究,Gao等[21]基于直方圖交點(diǎn)的度構(gòu)建相似度圖,利用超圖捕獲樣本之間的高階關(guān)系,進(jìn)一步提升了GraphSC的性能。此后,Sha等[22]提出將低秩表示[23](low-rank representation, LRR)引入圖正則化的處理過程,并就此提出了低秩正則化稀疏編碼算法(low-rank regularized spares coding,LogSC)。由于添加了低秩約束,LogSC在部分任務(wù)中獲得了較GraphSC更優(yōu)秀的性能。

然而,GraphSC及其改進(jìn)方法中的拉普拉斯圖都是預(yù)先定義且固定不變的,并不會參與之后對于字典與稀疏編碼的學(xué)習(xí)過程,而預(yù)先定義的拉普拉斯圖往往不是最合適的。針對這個問題,我們對GraphSC算法進(jìn)行了改進(jìn),提出了自適應(yīng)正則化稀疏編碼(graph regularization sparse coding with adaptive neighbour,GraphSCAN)算法。我們假設(shè)數(shù)據(jù)指向較小的距離代表更可能成為鄰居,因此 GraphSCAN可以從自適應(yīng)性分解的結(jié)果中學(xué)習(xí)局部流形結(jié)構(gòu),并重新構(gòu)造以保留精煉的局部結(jié)構(gòu),根據(jù)每個數(shù)據(jù)點(diǎn)的本地連通性選擇自適應(yīng)近鄰(adaptive neighbor, AN)以獲得相似度圖,然后將ANs正則化約束合并到GraphSC中。GraphSCAN將圖的構(gòu)建和稀疏編碼納入到統(tǒng)一框架中,使得內(nèi)部局部結(jié)構(gòu)學(xué)習(xí)的過程和圖稀疏編碼的過程同時進(jìn)行,并最終提高了GraphSC的性能。

1 相關(guān)工作

1.1 稀疏編碼(SC)

SC的目的是對于給定的一個數(shù)據(jù)矩陣,找到一組捕獲高級語義的基礎(chǔ)向量(即字典),并輸出數(shù)據(jù)的稀疏表示。

給定一個數(shù)據(jù)矩陣X∈[x1,x2,…,xn]∈Rn×m,X的每一列都是樣本矢量。令A(yù)=[a1,a2,…,ak]∈Rn×k為字典矩陣,其中ai表示字典中的基礎(chǔ)向量。令E=[e1,e2,…,em]∈Rk×m為系數(shù)矩陣,其中每一列都是數(shù)據(jù)點(diǎn)的稀疏表示。每個數(shù)據(jù)點(diǎn)都可以表示為字典中基向量的稀疏線性組合。

稀疏編碼的目標(biāo)函數(shù)定義如下:

(1)

式中:‖‖F(xiàn)表示矩陣的F范數(shù);f是度量的稀疏性函數(shù),其最直接的選擇是e的L0范數(shù)。然而,當(dāng)固定字典B時,系數(shù)e的極小化問題被證明是一個NP困難問題[24]。因此,可以轉(zhuǎn)而討論這個問題的近似或松弛。近似求解該問題有2種常用的方法,即匹配追蹤(matching pursuit,MP)[25]和基追蹤(basis pursuit, BP)[26]。MP以貪心的方式一次只尋找一個條目的解,而BP用L1范數(shù)代替L0范數(shù)對原問題進(jìn)行凸松弛。

因此,由文獻(xiàn)[13,26-27],可令f為f(ei)=‖ei‖1,此時目標(biāo)函數(shù)化為

(2)

由于(2)式中的目標(biāo)函數(shù)可能僅A或E是凸的,2個變量不能同時為凸。因此,可以通過固定一個變量、最小化另一個變量來迭代優(yōu)化目標(biāo)函數(shù)(2)。

1.2 圖正則化稀疏編碼(GraphSC)

GraphSC將拉普拉斯圖引入SC算法,并使用圖拉普拉斯正則項(xiàng)來保留數(shù)據(jù)局部流形結(jié)構(gòu)。

圖正則化目標(biāo)函數(shù)[20]可表示為

(3)

式中L是圖拉普拉斯矩陣,L=D-S。由(2)、(3)式可得GraphSC的目標(biāo)函數(shù)為

(4)

2 自適應(yīng)圖正則化稀疏編碼算法及其求解

利用數(shù)據(jù)的局部幾何結(jié)構(gòu),GraphSC算法提升了SC算法的計(jì)算能力。但GraphSC使用的拉普拉斯圖會在全局計(jì)算前預(yù)先定義且固定不變,并不參與之后對于字典與稀疏編碼的學(xué)習(xí)過程。我們提出自適應(yīng)方圖正則化稀疏編碼的算法(graph regularization sparse coding with adaptive neighbour,GraphSCAN)對GraphSC所存在的這個問題進(jìn)行了改進(jìn)。

2.1 GraphSCAN的算法模型

設(shè)輸入的原始數(shù)據(jù)集為X,X中的任意一數(shù)據(jù)點(diǎn)xi都有所有數(shù)據(jù)點(diǎn){x1,x2,…,xn}可以作為近鄰與之連接,連接的概率為sij?；跀?shù)據(jù)點(diǎn)間的歐幾里得距離構(gòu)造鄰域矩陣,距離越小則成為最近鄰的可能性越大。本文算法的求解形式如下:

(5)

(5)式第1項(xiàng)對原始數(shù)據(jù)集X求其字典及其稀疏編碼,其中矩陣X為原始數(shù)據(jù)集,A代表字典陣,E代表其稀疏陣。

(6)

式中γ是正則化參數(shù)。因此,可以將(6)式重新表示為

(7)

通過求解(7)式獲得的矩陣S∈Rn×n,可被視為相似度矩陣[29-30]。 可通過以下步驟來表示數(shù)據(jù)平滑度:

tr(ETDSE)-tr(ETWSE)=

tr(ETLSE)。

(8)

(5)式第3項(xiàng)是度量第一項(xiàng)中稀疏矩陣E稀疏度的函數(shù),設(shè)f(ei)=‖ei‖1作為度量函數(shù)。

(5)式第4項(xiàng)是局部圖拉普拉斯約束函數(shù),使用其增強(qiáng)傳統(tǒng)低秩表示模型的局部性和稀疏性。其中LS是Si的拉普拉斯矩陣,LS=DS-WS,tr( )表示矩陣的跡。

2.2 GraphSCAN的算法求解

本節(jié)提出求解GraphSCAN的更新算法,該算法通過固定其他變量更新一個變量的值來優(yōu)化目標(biāo),此過程重復(fù)直到收斂。

2.2.1 固定A、E更新S

觀察(5)式不難發(fā)現(xiàn),在固定A、E時更新S,最小化(5)式可等價(jià)于解決下式:

(9)

(10)

可通過逐個求解的方式求解(10)式,此時(10)式等價(jià)于

(11)

(12)

設(shè)ζ和η≥0為拉格朗日乘子,則(12)式的拉格朗日函數(shù)為

(13)

根據(jù)KKT條件[31],滿足sij≥0,最優(yōu)解可以定義為

(14)

(15)

(16)

結(jié)合(15)和(16)式,可得

(17)

為了獲得具有k個非零值的最優(yōu)si,可以將γi設(shè)置為

(18)

為了便于計(jì)算,可以將整體γ設(shè)置為γ1,γ2,…,γn的均值,即

(19)

通過取γi的平均值,所有si的平均非零元素應(yīng)為k。我們不直接搜索正則化參數(shù)γ,而是搜索近鄰數(shù)k。因?yàn)閗是一個整數(shù),并且其值是有限的(即0≤k≤n),所以參數(shù)搜索會更加容易。

2.2.2 固定S、A更新E

在固定S、A時更新E,求解(5)式即等同于求解下式:

λtr(ETLSE)。

(20)

(21)

拉普拉斯正則項(xiàng)tr(ETLSE)可寫為

(22)

結(jié)合(21)、(22)式可重寫如下:

(23)

在更新ei時,其他向量{ej}j=1是固定的,因此可得

(24)

定義

(25)

(26)

2.2.3 固定S、E更新A

在固定S、E時更新A,最小化(4)等同于求解下式:

s.t.‖ai‖2≤c,i=1,2,…k。

(29)

使用拉格朗日對偶法對(29)式進(jìn)行求解。令ε=[ε1,ε2,…,εk]為與不等式約束相關(guān)聯(lián)的拉格朗日乘數(shù),則拉格朗日對偶函數(shù)為

g(ε)=infBL(A,ε)=

(30)

令Λ為k×k的對角矩陣,其對角線數(shù)Λii=λi。那么L(A,ε)可寫作

tr(ATAΛ)-ctr(Λ)=

tr(XTX)-2tr(ATAΛ)+tr(ETATAE)+

tr(ATAΛ)-ctr(Λ)。

(31)

令(31)式的一階導(dǎo)數(shù)等于零即可獲得最佳解A*,即

A*EET-XET+A*Λ=0。

(32)

這時,有

A*=XET(EET+Λ)-1。

(33)

將(33)式代入(31)式可得

g(ε)=tr(XTX)-2tr(XET(EET+Λ)-1EXT)-

ctr(Λ)+tr((EET+Λ)-1EXTXET)=

tr(XTX)-tr(XET(EET+Λ)-1EXT)-

ctr(Λ)。

(34)

由此可得拉格朗日對偶函數(shù)

s.t.εi≥0,i=1,2,…,k。

(35)

(35)式可以通過牛頓法或共軛梯度來求解。令Λ*為最優(yōu)解,那么最優(yōu)A*=XET(EET+Λ)-1。由于不能保證EET+Λ可逆,因此本文算法使用偽逆代替直接求逆。

至此,GraphSCAN的算法步驟可總結(jié)如下。

3 實(shí)驗(yàn)

我們在2個圖像數(shù)據(jù)集(CMU-PIE數(shù)據(jù)庫和COIL20圖像數(shù)據(jù)庫)上進(jìn)行聚類實(shí)驗(yàn)。實(shí)驗(yàn)中以聚類準(zhǔn)確率(accuracy, ACC)、標(biāo)準(zhǔn)互信息率(normalized mutual info, NMI)2個指標(biāo)作為評價(jià)標(biāo)準(zhǔn),實(shí)驗(yàn)環(huán)境為Intel(R) Core(TM) i7-1065G7 1.50 GHz CPU,16 GiB DDR3內(nèi)存,MATLAB 2019b。

3.1 實(shí)驗(yàn)步驟

為了進(jìn)一步評估所提出方法的性能,我們對GraphSCAN與一些經(jīng)典算法和最新算法進(jìn)行了對比實(shí)驗(yàn)。

1)k-means:最常用的基于歐式距離的聚類算法[32]。

2)主成分分析(principal component analysis,PCA):經(jīng)典的降維方法[33]。

3)SC:經(jīng)典SC算法 。

4)GraphSC:圖正則化的SC[20]。

5)LogSC:最新的基于拉普拉斯圖正則化的SC[22]。

實(shí)驗(yàn)中所用對比算法的參數(shù)已結(jié)合原論文進(jìn)行了調(diào)節(jié),使得其性能達(dá)到最優(yōu)。

3.2 圖像聚類實(shí)驗(yàn)

3.2.1 CMU-PIE數(shù)據(jù)集上的測試

我們首先在CMU-PIE數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn), CMU-PIE人臉數(shù)據(jù)庫包含68個人總共41 368張人臉圖像。每個圖像的大小為32×32,每個像素256個灰度級,每個圖像都由1 024維矢量表示。

我們進(jìn)行的聚類實(shí)驗(yàn)的簇?cái)?shù)C范圍為4～68。對于除68以外的每個簇,對不同隨機(jī)選擇的簇進(jìn)行20次測試運(yùn)行,并通過對20個測試取平均值來獲得最終的性能得分。對于每個測試,首先應(yīng)用比較算法中的每個算法,學(xué)習(xí)數(shù)據(jù)的新表示形式,然后在新的表示空間中應(yīng)用k-means。我們用不同的初始化將k-means在原數(shù)據(jù)集上重復(fù)50次,并記錄關(guān)于k-means目標(biāo)函數(shù)的最佳結(jié)果。PCA投影降維后,維數(shù)為64。對于SC、GraphSC、LogSC、GraphSCAN算法,基向量維度設(shè)為128。

實(shí)驗(yàn)結(jié)果如表1所示,本文GraphSCAN算法基本優(yōu)于其他算法(表中加粗?jǐn)?shù)據(jù))。GraphSCAN的ACC和NMI均值分別為86.28%和94. 41%,明顯高于現(xiàn)有優(yōu)秀算法LogSC在PIE數(shù)據(jù)集上的表現(xiàn)。同時,基于圖的SC算法結(jié)果均優(yōu)于標(biāo)準(zhǔn)SC算法。這說明結(jié)合圖的SC可以獲得更好的性能,且通過自適應(yīng)鄰居獲得相似度圖的方法比僅使用k-NN進(jìn)行構(gòu)造的圖算法獲得的結(jié)果精度更高。由于局部流形結(jié)構(gòu)的學(xué)習(xí)和稀疏編碼是同時進(jìn)行的,即從編碼的結(jié)果中自適應(yīng)地學(xué)習(xí)內(nèi)在局部結(jié)構(gòu),并且重新構(gòu)造因子以保留數(shù)據(jù)的精煉局部結(jié)構(gòu)。因此,可以更好探索數(shù)據(jù)內(nèi)在局部結(jié)構(gòu)。通過為每個數(shù)據(jù)點(diǎn)選擇自適應(yīng)和最佳鄰居,該方法可以提高一般情況下的聚類性能。

表1 CMU-PIE數(shù)據(jù)集的聚類結(jié)果Tab.1 Clustering results of CMU-PIE data set 單位:%

3.2.2 COIL20數(shù)據(jù)集上的測試

我們在COIL20數(shù)據(jù)集上也進(jìn)行了實(shí)驗(yàn), COIL20圖像庫包含20個對象1 440張32×32的灰度圖像(每個對象72個圖像),每個圖像由1 024維向量表示。實(shí)驗(yàn)設(shè)置與CMU-PIE數(shù)據(jù)集上的實(shí)驗(yàn)基本相同,但限制于數(shù)據(jù)集大小,此處以2～20的簇?cái)?shù)進(jìn)行20次實(shí)驗(yàn),通過對20個測試取平均值來獲得最終的性能得分。對于此數(shù)據(jù)集,PCA降維后的維數(shù)為175;對于SC、GraphSC、GraphSCAN算法,基向量維度設(shè)為256。

實(shí)驗(yàn)結(jié)果如表2所示,GraphSCAN的ACC和NMI均值分別為88.07%和87.63%。與LogSC相比,GraphSCAN的性能略有提升,且二者都優(yōu)于同樣基于圖的GraphSC算法。這說明將圖優(yōu)化的概念引入使用圖方法的GraphSC中,可以提高原有算法的性能。

表2 COIL20數(shù)據(jù)集的聚類結(jié)果Tab.2 Clustering results of COIL20 data set

結(jié)合對PIE數(shù)據(jù)集進(jìn)行的聚類實(shí)驗(yàn)結(jié)果可以看出,通過將自適應(yīng)拉普拉斯圖構(gòu)建的概念引入帶有幾何信息編碼的稀疏表示中,可以有效提高學(xué)習(xí)性能。

3.3 參數(shù)選擇實(shí)驗(yàn)

觀察目標(biāo)函數(shù)(5)可以看出,GraphSCAN中包含了α、β、λ3個參數(shù)。根據(jù)文獻(xiàn)[20,28]中實(shí)驗(yàn)不難發(fā)現(xiàn),雖然α、β取值會影響實(shí)驗(yàn)結(jié)果,但是由于其取值范圍較小,且因其改變而影響的實(shí)驗(yàn)結(jié)果誤差不大,故此處僅討論對算法中參數(shù)取值范圍及實(shí)驗(yàn)結(jié)果影響較大的參數(shù)λ的選擇。

考慮到實(shí)驗(yàn)數(shù)據(jù)集包含的數(shù)據(jù)量,這里選擇COIL20以及CEU-PIE 2個數(shù)據(jù)集及PCA、SC、GraphSC、GraphSCAN 4種算法進(jìn)行了實(shí)驗(yàn)。所有實(shí)驗(yàn)均使用ACC、NMI指標(biāo)作為算法評價(jià)標(biāo)準(zhǔn)。為了公平地比較所有方法,所有算法都在不同的參數(shù)設(shè)置下進(jìn)行,且在每個參數(shù)設(shè)置下,均會獨(dú)立重復(fù)實(shí)驗(yàn)20次。所有方法的迭代次數(shù)都根據(jù)經(jīng)驗(yàn)設(shè)置為50,GraphSCAN中α、β兩個參數(shù)粗略取值為α=λ、β=0.3進(jìn)行實(shí)驗(yàn)(更好的參數(shù)調(diào)整可以給本文算法帶來更優(yōu)秀的性能)。聚類的數(shù)量設(shè)置為真實(shí)類的數(shù)量。

試驗(yàn)結(jié)果如圖1所示?？梢钥闯?在CEU-PIE數(shù)據(jù)集上當(dāng)λ取到0.1時以及在COIL20數(shù)據(jù)集上當(dāng)λ取到1時可獲得較好的結(jié)果,其結(jié)果顯示GraphSCAN與GraphSC算法取到λ最優(yōu)值過程中指標(biāo)變化趨勢相差較小。以上結(jié)果表明,實(shí)際對算法影響較大的部分為SC之前進(jìn)行的圖構(gòu)造過程。

圖1 各算法中參數(shù)λ對性能的影響Fig.1 The influence of parameter λ on different algorithms

4 結(jié)語

為優(yōu)化GraphSC算法,本文將自適應(yīng)拉普拉斯圖構(gòu)建的方法引入GraphSC中,提出了自適應(yīng)圖正則化稀疏編碼算法GraphSCAN。該算法通過使用自適應(yīng)方法定義構(gòu)建合適的局部拉普拉斯圖,再使用構(gòu)建好的圖參與SC的運(yùn)算,圖的構(gòu)建與稀疏編碼的運(yùn)算同時迭代進(jìn)行。本文在2個圖像數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn),并與相關(guān)算法進(jìn)行了比較分析,驗(yàn)證了GraphSCAN的有效性。