基于字典學(xué)習(xí)的非線性降維方法

鄭思龍　　李元祥　　魏憲　　彭希帥

基于字典學(xué)習(xí)的非線性降維方法

鄭思龍1李元祥1魏憲2彭希帥1

目前，眾多的數(shù)據(jù)降維（Dimensionality reduction，DR）方法（如經(jīng)典的PCA（Principle component analysis），ISOMAP（Isometric mapping））能夠使降維后的數(shù)據(jù)保留原始信號(hào)的重要特征，但是從降維后的數(shù)據(jù)中很好地恢復(fù)出原始信號(hào)仍舊是一個(gè)挑戰(zhàn).近年來，稀疏表示（Sparse representation，SR）在信號(hào)重構(gòu)研究中受到廣泛關(guān)注，信號(hào)可以利用過完備字典中少數(shù)原子的線性組合來描述.本文提出一種基于字典學(xué)習(xí)的非線性降維方法.從高維輸入信號(hào)到低維特征的降維過程中，期望一些重要的幾何特征（內(nèi)積、距離和夾角）得以保留，同時(shí)又能夠從低維數(shù)據(jù)中恢復(fù)出原始信號(hào).為達(dá)此目的，本文采用CDL（Concentrated dictionary learning）算法訓(xùn)練一個(gè)字典對(duì)（高維字典D和低維字典P），使高維原始信號(hào)的能量能夠聚集于低維子空間中.字典D用來獲取稀疏表示系數(shù)，字典P是D的直接降維采樣，CDL算法能夠保證P聚集D中的大部分能量.這樣，信號(hào)的降維與恢復(fù)問題就轉(zhuǎn)變?yōu)樽值鋵?duì)的訓(xùn)練問題，信號(hào)的降維即為從D到P的能量保留過程.實(shí)驗(yàn)表明: CDL可在RIP（Restricted isomery property）條件的限制之外具有一定的信號(hào)重建能力，能在更低的維度條件下恢復(fù)圖像，優(yōu)于傳統(tǒng)的壓縮感知方法.此外，在噪聲較大的情況下，CDL圖像壓縮效果優(yōu)于JPEG2000.

數(shù)據(jù)降維，稀疏表示，壓縮感知，字典學(xué)習(xí)

引用格式鄭思龍，李元祥，魏憲，彭希帥.基于字典學(xué)習(xí)的非線性降維方法.自動(dòng)化學(xué)報(bào)，2016，42（7）:1065-1076

觀測空間中的數(shù)據(jù)達(dá)到上千維甚至上萬維時(shí)，巨大的數(shù)據(jù)計(jì)算量對(duì)計(jì)算系統(tǒng)來說是一個(gè)挑戰(zhàn).對(duì)圖像、音頻、視頻和網(wǎng)絡(luò)搜索來說，通過降低數(shù)據(jù)維度來提高處理速度顯得尤為重要.

為解決“維數(shù)災(zāi)難”問題，許多文獻(xiàn)假設(shè)數(shù)據(jù)具有低維的固有屬性（例如：低秩、稀疏性、低維流形），然后根據(jù)這些假設(shè)建立各種不同的模型.一個(gè)簡單有效的假設(shè)是：觀測數(shù)據(jù)落在一個(gè)低維流形子空間中.基于這樣的假設(shè)，利用PCA（Principlecomponent analysis）、LDA（Linear discriminant analysis）、ICA（Independent component analysis）、LPP（Locality preserving projection）等不同的線性降維算法，對(duì)高維空間做線性投影處理，以得到數(shù)據(jù)所在的子空間［1］.另一方面，非線性降維算法（例如ISOMAP（Isometric mapping）、LLE （Locally linear embedding））在降維處理中，可保留數(shù)據(jù)的非線性幾何結(jié)構(gòu)［1］.

上述兩類算法側(cè)重于挖掘和發(fā)現(xiàn)原始數(shù)據(jù)在低維空間中的內(nèi)在屬性，而對(duì)數(shù)據(jù)的恢復(fù)能力仍有待改進(jìn).壓縮感知（Compressed sensing，CS）算法的出現(xiàn)，使得我們能從更低的采樣信號(hào)中（低于奈奎斯特采樣率）較好地恢復(fù)原始信號(hào)［2］.

CS在減少觀測次數(shù)來表示一個(gè)有限維向量x∈Rm的同時(shí)，更加注重于原始信號(hào)x的稀疏性.假設(shè)y=Φx，其中Φ∈Rd×m，d?m是觀測到的信號(hào)，由于觀測矩陣Φ的行數(shù)小于列數(shù)，通過觀測信號(hào)y來獲取原始信號(hào)x是不適定的反問題.但是如果信號(hào)x在給定的字典D下足夠稀疏，那么在一定的條件下，只要維數(shù)d不低于某個(gè)限定值，觀測信號(hào)y可以唯一重構(gòu)x［3-4］.求解原始信號(hào)x在字典D下的稀疏表示α的過程可表述為

我們認(rèn)為x=Dα+ε，其中ε是高斯白噪聲，α 是x在D下的稀疏表示.大多數(shù)圖像、語音等自然信號(hào)，在某些字典下都有很好的稀疏性.

式（1）所表達(dá)的稀疏編碼框架具有很強(qiáng)的魯棒重建能力，并且在數(shù)據(jù)壓縮、超分辨率重建、去噪、分類等領(lǐng)域成功應(yīng)用.一方面，任務(wù)驅(qū)動(dòng)的數(shù)據(jù)降維方法認(rèn)為特定的任務(wù)（如圖像識(shí)別、數(shù)據(jù)可視化等）需要特定的降維方法將數(shù)據(jù)從高維降至低維，因此提取的特征也不一樣.文獻(xiàn)［5-7］認(rèn)為在稀疏域中，信號(hào)的幾何關(guān)系是一種有效的結(jié)構(gòu)信息.文獻(xiàn)［5］通過字典學(xué)習(xí)，得到原始信號(hào)的稀疏表示系數(shù)α，利用α的幾何結(jié)構(gòu)信息，建立一個(gè)通用有效的框架來解決不同任務(wù)的字典學(xué)習(xí)問題.類似地，文獻(xiàn)［6］依據(jù)α的幾何結(jié)構(gòu)信息，直接利用PCA作用于稀疏系數(shù)α上，實(shí)現(xiàn)數(shù)據(jù)降維.文獻(xiàn)［7］有針對(duì)性地保留稀疏域中信號(hào)間的內(nèi)積關(guān)系，通過學(xué)習(xí)得到原始信號(hào)到降維信號(hào)的線性投影來完成數(shù)據(jù)降維.另一方面，數(shù)據(jù)驅(qū)動(dòng)的數(shù)據(jù)降維方法采用將CS框架與高斯隨機(jī)投影結(jié)合的框架.文獻(xiàn)［8］利用高斯隨機(jī)矩陣將原始特征映射到觀測空間，證明在低維空間中并沒有發(fā)生重大的信息丟失，并給出結(jié)論：低維空間的特征保留了原始信號(hào)的主要信息.類似地，文獻(xiàn)［9-12］假設(shè)信號(hào)是在一個(gè)嵌入高維空間的低維流形中，因此在降維的過程中，一些重要的幾何信息（例如：角度、距離）得以保留.文獻(xiàn)［13］認(rèn)為通過學(xué)習(xí)得到的觀測矩陣比隨機(jī)投影更加有效.上述基于CS框架的方法都必須服從RIP（Restricted isometry property）條件，這對(duì)于數(shù)據(jù)降維中的可視化（2D或者3D）來說是不適合的.而且，雖然文獻(xiàn)［9-12，14］給出了將CS框架搭建在流形上的理論分析，但是實(shí)際可行的算法很少.

上述工作都是基于一個(gè)先驗(yàn)給定的字典D，不需要學(xué)習(xí)字典.更進(jìn)一步的研究認(rèn)為：在采樣和重建的過程中不需要知道字典D的先驗(yàn)知識(shí)，而是從訓(xùn)練樣本中學(xué)習(xí)字典（本文稱為“在數(shù)據(jù)降維中的字典學(xué)習(xí)方法”）.盲壓縮感知是這個(gè)框架下一個(gè)典型的例子，在嚴(yán)格的條件下，字典D可以通過低維的觀測值訓(xùn)練學(xué)習(xí)而來［15-16］.文獻(xiàn)［17-20］認(rèn)為高維信號(hào)X與低維信號(hào)Y之間，在字典Dx和Dy下共同享有稀疏表示系數(shù).字典對(duì)Dx和Dy是分別對(duì)應(yīng)高維數(shù)據(jù)x和降維數(shù)據(jù)y的高維字典和低維字典，是從數(shù)據(jù)降維過程中學(xué)習(xí)而來的.

本文結(jié)合降維算法中保留數(shù)據(jù)結(jié)構(gòu)特征和CS算法中數(shù)據(jù)恢復(fù)能力的優(yōu)點(diǎn)，提出聚能量字典學(xué)習(xí)（Concentrated dictionary learning，CDL）算法. CDL算法既能夠在CS中RIP下界的維數(shù)限制之外具有一定的信號(hào)重建能力，又結(jié)合了流形的特點(diǎn)，在降維后的空間中保留原始信號(hào)中的特征（例如：內(nèi)積、距離、夾角）［21］.并且，利用訓(xùn)練得到的字典，仿照CS算法設(shè)計(jì)算法框架.為驗(yàn)證算法的有效性，將CDL與CS+K-SVD（K-means-singular value decomposition）［22-23］等算法進(jìn)行數(shù)據(jù)恢復(fù)對(duì)比實(shí)驗(yàn)，結(jié)果表明本文算法相比傳統(tǒng)算法有明顯的提升.同時(shí)，進(jìn)行了圖像數(shù)據(jù)的3維觀測性實(shí)驗(yàn)，本文算法表現(xiàn)良好.在噪聲污染嚴(yán)重的圖像壓縮實(shí)驗(yàn)中，本文算法相對(duì)于JPEG2000，也具有一定程度的優(yōu)勢.

其余章節(jié)安排如下：第1節(jié)回顧C(jī)S算法及KSVD字典訓(xùn)練算法.第2節(jié)闡述本文字典學(xué)習(xí)算法推導(dǎo)及思路，對(duì)于內(nèi)積、距離、夾角特征推導(dǎo)出字典對(duì)D和P的具體形式.第3節(jié)進(jìn)行圖像重構(gòu)、3D可視化和圖像壓縮的對(duì)比實(shí)驗(yàn).最后，總結(jié)全文，討論本文算法的應(yīng)用拓展性.

1　CS及字典學(xué)習(xí)回顧

本文算法基于CS算法框架，下面對(duì)CS算法框架進(jìn)行簡要的回顧.CS算法框架如圖1所示，X為原始信號(hào)，Y是觀測值，Φ是觀測矩陣，α是稀疏表示系數(shù)，D是字典.典型的CS算法選取Φ為高斯隨機(jī)矩陣，Φ：Rm→Rd，d?m，y=Φx；字典D由標(biāo)準(zhǔn)正交基組成，如小波基、離散余弦變換（Discrete cosine transform，DCT）字典）.

CS通過正交匹配追蹤算法 （Orthogonalmatching pursuit，OMP）［4，24-25］解決如式（2）的最優(yōu)化問題得到稀疏系數(shù)α，最后由字典D恢復(fù)原始信號(hào)x：x=Dα.

其中，ε∈R+.在此過程中，低維觀測值y∈Rd的維數(shù)d受到一定條件的限制：d>O（Cslog（k/s）），其中，C為常數(shù)，C∈（0，1），s是稀疏系數(shù)的稀疏性，k是字典的原子的個(gè)數(shù)，這種限制被稱為RIP條件［3-4］.一旦采樣信號(hào)y的維數(shù)低于d，那么就無法從y中恢復(fù)原始信號(hào)x，或者恢復(fù)的效果很差.例如，如果需要同時(shí)將數(shù)據(jù)可視化（二維或三維）和信號(hào)恢復(fù)作為目標(biāo)，那么傳統(tǒng)的CS算法遠(yuǎn)遠(yuǎn)滿足不了實(shí)際需求.

圖1CS算法示意圖Fig.1　CS algorithm schematic

在CS算法框架中所用到的字典往往是給定的正交基字典.不同于給定字典的思路，K-SVD算法提供了很好的字典學(xué)習(xí)方法［22-23］.從訓(xùn)練集中訓(xùn)練學(xué)習(xí)得到的字典比給定的正交基字典表現(xiàn)更加出色，通過字典D能夠得到最佳的稀疏系數(shù).它的優(yōu)勢主要表現(xiàn)在：

1）靈活性：能夠與任何的匹配追蹤算法相結(jié)合，確保所選的匹配追蹤算法能夠適合于所要求的時(shí)間限制；

2）有效性：K-SVD算法復(fù)雜度低，具有高效性和快速收斂性，更新字典原子和稀疏表示系數(shù)是同時(shí)進(jìn)行的.

2CDL算法

以CS框架為基礎(chǔ)，利用K-SVD字典算法的優(yōu)點(diǎn)，本文提出基于字典學(xué)習(xí)的信號(hào)降維和重建算法.該算法可在RIP條件的限制之外具有一定的信號(hào)重建能力，即能夠從較低維的觀測值中恢復(fù)出原始信號(hào).

原始信號(hào)x可看作是高維稀疏系數(shù)α通過字典D，在低維子空間中的一種表現(xiàn)形式.不同于觀測矩陣Φ的做法，本文直接將稀疏系數(shù)α通過映射函數(shù)P（α，y）投影到另一低維子空間y中，如式（3）所示.那么信號(hào)x與y之間的映射關(guān)系F（x，y）就可以通過稀疏系數(shù)α搭建橋梁，建立模型.理論證明該做法具有保留幾何結(jié)構(gòu)特性的作用［21］.

為了得到映射函數(shù)P（α，y），可簡單地認(rèn)為α到y(tǒng)的投影是通過一個(gè)矩陣P來實(shí)現(xiàn)的.而矩陣P是通過字典D獲取的.那么式（3）可以轉(zhuǎn)為如下表達(dá)形式：

假設(shè)已知P與D的關(guān)系，那么x到y(tǒng)的映射函數(shù)F（x，y）也就確定下來.在本文中，僅考慮x和y之間的關(guān)系有：內(nèi)積、距離、夾角.那么x到y(tǒng)的降維算法就轉(zhuǎn)換為字典D到P的函數(shù)關(guān)系，如式（5）所示.維空

設(shè)間X 中R=m［x 的1，xn2，個(gè)···輸，x入n］信∈號(hào).R給m×定n字表典示D高，α=［α1，α2，···，αn］∈.Rk×n是X在字典（Dx，y下），的n個(gè)稀疏表示系數(shù)給定映射函數(shù) F Y=［y1，y2，···，yn］∈Rd是低維空間中的特征.那么通過稀疏系數(shù)α搭建的橋梁，（X，Y）可以表示為如下形式：

其中，噪聲ε1∈Rm，ε2∈Rd.

2.1內(nèi)積關(guān)系

當(dāng)期望X內(nèi)部xi與xj之間的內(nèi)積關(guān)系能在Y中保留下來時(shí)，定義將式（6）帶入其中，得到關(guān)于P的最優(yōu)化問題：

為了解決上述最優(yōu)化問題，定義核函數(shù)：

那么f2（xi，xj；yi，yj）的表示如下：

假設(shè)（xi，xj）和（yi，yj）內(nèi)部相互獨(dú)立，那么：

其中，σ1，σ2為ε1，ε2的方差，由式（11），式（7）最終轉(zhuǎn)化為求解下式：

2.2距離關(guān)系

同樣地，若期望在Y中保留X 內(nèi)部xi與 xj之間的距離關(guān)系，定義寫成如下形式：

同樣地，將式（6）帶入式（13）得到一個(gè)關(guān)于P的最優(yōu)化問題：

上式中第二部分h2（xi；yi）推導(dǎo)如下：

可以看出，得到的結(jié)果與內(nèi)積關(guān)系式（12）相同.

2.3夾角關(guān)系

定義X和Y內(nèi)部的夾角關(guān)系為

事實(shí)上，在處理數(shù)據(jù)集時(shí)，常常將數(shù)據(jù)集歸一化，即：||xi||2=1.可以看出夾角關(guān)系與內(nèi)積關(guān)系是相似的.

2.4理論推導(dǎo)

從內(nèi)積、距離、夾角關(guān)系中可看出，需要解決如下問題：

將上式重寫為

通過求解式（17）得到的特征Y的維數(shù)可以比CS算法更低，因此該算法框架可在CS算法的RIP限制之外具有恢復(fù)信號(hào)的能力［25］.

由式（18），可認(rèn)為字典P是字典D的PCA降維，不妨假設(shè)：

當(dāng)字典維數(shù)較低時(shí)，DCT及K-SVD字典在降維后，無法保留較多的主成分.因此，本文通過訓(xùn)練字典，使得能量聚集于較低的維度內(nèi)（見圖4），保留較多的主成分，以滿足式（19）的需求.

文獻(xiàn)［25］中提到D與P是具有如下條件的矩陣：

且

式（21）說明，奇異值分解中的Θ總能量是保持不變的，如果Θ中靠后的（m-d）個(gè)奇異值越小，那么前d個(gè)奇異值越大.因此，為了使字典D前d維聚集更多的能量，應(yīng)滿足下述條件：

1）原始信號(hào)X在字典D下表示系數(shù)足夠稀疏；

2）給定正整數(shù)q，當(dāng)d＜q時(shí)，D的奇異值分

解：D=UΘVT中，關(guān)于奇異值Θ有：

其中，Θd是奇異值Θ取前d行d列，td是設(shè)定的主成分閾值.

3）為了保證D的滿秩性，要求奇異值Θ后m-d個(gè)奇異值很小卻非零.

當(dāng)D滿足上述條件時(shí)，字典P可以保留字典D中較多的主成分.設(shè)D的奇異值分解為

式（19）中，取A=Ud，則有：

式（25）中，如果能夠保證Θd足夠大，即：

2.5字典訓(xùn)練

通過上述分析，明確訓(xùn)練字典D的兩個(gè)目標(biāo)：

1）字典D要使得測試圖像在該字典下的表示系數(shù)足夠稀疏.

為了達(dá)到上述目標(biāo)，利用式（25）的性質(zhì)，令：

其中

令

更新奇異值分解：D=UΘVT中Θ：

令

將上述更新過程寫作：

輸入.訓(xùn)練圖集X，迭代次數(shù)T.

輸出.訓(xùn)練好的字典D、P.

初始化.從訓(xùn)練圖集中隨機(jī)選取16×16的圖像塊，并將每個(gè)小塊排列成列向量形式xi（256×1），令X=［x1，x2，···，xn］.初始化DCT字典D.

第一階段.稀疏編碼

1）稀疏編碼

對(duì)每一個(gè)xi，利用匹配追蹤算法得到稀疏表示系數(shù)αi［24-25］：

α←minα12||X-Dα||22+λ||α||1其中，

第α二=階［α 段1.，α字2，典···，α更n］新∈Rk×n. DDD

2）對(duì)DTD作奇異值分解：DTD=uΛvT；

5）仿照K-SVD 字典學(xué)習(xí)算法［22-23］，將Ek限定在wk集合中，得到

6）對(duì)EkR做奇異值分解做如下更新=?（1，1）n1；

第三階段.字典 PPP 計(jì)算

8）根據(jù)式（23）字典D的奇異值分解得到Ud，則字典

2.6訓(xùn)練結(jié)果

圖3所示的CDL字典是利用自然圖像（如圖2所示）訓(xùn)練得到的，見第3.1節(jié)描述.根據(jù)式（23）字典D的奇異值分解得到Ud（d=16），令即可得到對(duì)應(yīng)的低維字典.字典P如圖3（b）所示.

CDL字典能夠?qū)⒅鞒煞旨杏谳^低的維數(shù)中，具有能量聚集的作用，如圖4所示.當(dāng)選取90%主成分（td=0.9）時(shí)，CDL字典的能量集中于前16維，而K-SVD字典則需要148維，DCT字典需要207維.當(dāng)字典的維數(shù)降得較低時(shí)，DCT，K-SVD字典在降維后，無法保留較多的主成分.

圖2 自然圖像示例Fig.2　Natural image examples

圖3 由CDL算法訓(xùn)練得到的字典對(duì)Fig.3　Coupled dictionaries trained by CDL

圖4　不同字典奇異值的分布（當(dāng)選取90%主成分（td=0.9）時(shí)，圖中的點(diǎn)代表所需的字典維數(shù).DCT字典: 207，K-SVD字典:148，CDL字典:16）Fig.4　Distribution of singular values from different dictionaries（When selecting 90%component of dictionaries（td=0.9），the dots represent the required dimensions for different dictionaries.DCT:207，K-SVD: 148，CDL:16）

3　實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文算法的有效性，分別從圖像重構(gòu)與數(shù)據(jù)可視化、RIP條件驗(yàn)證和圖像壓縮三個(gè)方面進(jìn)行實(shí)驗(yàn)和分析.實(shí)驗(yàn)中的圖像包括：自然圖像、USPS手寫數(shù)字和PIE人臉圖像.

3.1圖像重構(gòu)和3D可視化

本文的對(duì)比算法有：CS+K-SVD、PCA、LPP［1］.低維空間的維數(shù)分別為：d=8，16，32，64.CS+KSVD算法中，降維采樣矩陣分別用高斯隨機(jī)陣（GAU）和主成分分析（PCA）.重構(gòu)圖像的質(zhì)量評(píng)價(jià)用峰值信噪比（Peak signal to noise ratio，PNSR）表示.

1）自然圖像重構(gòu)

自然圖像集包括13張圖片［19］，尺寸為256×256或者512×512，如圖2所示.訓(xùn)練時(shí)，隨機(jī)選取圖集中的圖像塊13 000個(gè)（16×16）.分別用K-SVD算法和本文CDL算法訓(xùn)練字典.測試用的圖像分別為：Lena（512×512）、Boat（512×512），測試結(jié)果如圖5、圖6所示.由表1和表2可看出，CDL重構(gòu)效果明顯優(yōu)于其他算法，比CS+K-SVD（GAU）高出3 dB以上.

表1　Lena圖像重構(gòu)對(duì)比Table 1　Comparison of reconstructed Lena images

表2　Boat圖像重構(gòu)對(duì)比Table 2　Comparison of reconstructed Boat images

2）手寫數(shù)字重構(gòu)和3D可視化

手寫數(shù)字圖片來自USPS庫1，包含9298個(gè)圖片（16×16）.選取其中每類數(shù)字的一半做訓(xùn)練，分別降至8，16，32和64維，利用訓(xùn)練得到的CDL字典對(duì)剩余的一半數(shù)字做重構(gòu)測試.如圖7及表3所示，給出d=16時(shí)各種方法的重構(gòu)結(jié)果，并統(tǒng)計(jì)出不同方法恢復(fù)結(jié)果的平均PSNR值.表4統(tǒng)計(jì)不同維數(shù)下各方法重構(gòu)的PSNR平均值，可看出CDL的重構(gòu)效果優(yōu)于其他算法.

1http：//www.cad.zju.edu.cn/home/dengcai/Data/data.html

圖5Lena圖像重構(gòu)對(duì)比（原始圖像、CS+K-SVD（GAU）、CS+K-SVD（PCA）、PCA、LPP、CDL，d=16）Fig.5 Reconstructed images of Lena（Original image，CS+K-SVD（GAU），CS+K-SVD（PCA），PCA，LPP，CDL，d=16）

圖6Boat圖像重構(gòu)對(duì)比（原始圖像、CS+K-SVD（GAU）、CS+K-SVD（PCA）、PCA、LPP、CDL，d=32）Fig.6 Reconstructed images of Boat（Original image，CS+K-SVD（GAU），CS+K-SVD（PCA），PCA，LPP，CDL，d=32）

圖7　USPS手寫數(shù)字重構(gòu)對(duì)比（從上到下:原始圖像、CS+K-SVD（GAU）、CS+K-SVD（PCA）、PCA、CDL，d=16）Fig.7　Reconstructed images of USPS（From top to bottom:original image，CS+K-SVD（GAU），CS+K-SVD （PCA），PCA，CDL，d=16）

同時(shí)，在USPS中取3類數(shù)據(jù)（數(shù)字0、3、4），共3229個(gè).利用CDL、CS+PCA［6］和PCA算法降至3維后，給出3維平面上的數(shù)據(jù)分布，如圖8所示.圖8給出的3D可視化結(jié)果表明，通過CDL降維后的數(shù)據(jù)可分性很強(qiáng)，而CS+PCA由于受到RIP條件的限制，導(dǎo)致算法失效，具體分析見第3.2 節(jié).在圖像重構(gòu)方面，CDL仍然能夠?qū)⒔抵?維后的數(shù)據(jù)恢復(fù)，如圖9所示.

圖8　USPS手寫數(shù)字三類樣本（0、3、4）可視化結(jié)果（d=3）Fig.8　The visualization results of USPS（0，3，4）（d=3）

表3　USPS手寫數(shù)字重構(gòu)對(duì)比（d=16）Table 3　Comparison of reconstructed USPS（d=16）

表4　USPS手寫數(shù)字重構(gòu)對(duì)比（d=8、16、32、64）Table 4　Comparison of reconstructed USPS （d=8，16，32，64）

圖9　USPS手寫數(shù)字三類樣本（0、3、4）圖像重構(gòu)對(duì)比（從上到下:原始圖像、CDL、CS+K-SVD（GAU））Fig.9　Reconstructed images of USPS（0，3，4）（From top to bottom:original image，CDL，CS+K-SVD（GAU））

圖10　PIE人臉圖像重構(gòu)對(duì)比（從上到下:原始圖像、CS+K-SVD（GAU）、CS+K-SVD （PCA）、PCA、CDL，d=16）Fig.10　Reconstructed images of PIE（From top to bottom:original image，CS+K-SVD（GAU），CS+K-SVD （PCA），PCA，CDL，d=16）

3）人臉重構(gòu)

人臉圖像來自PIE庫1（16×16）.選取其中的10類樣本1700個(gè)圖片，一半用于訓(xùn)練字典，另一半用于測試，分別計(jì)算將數(shù)據(jù)降至8、16、32和64維時(shí)的PSNR值，并統(tǒng)計(jì)不同方法的PSNR平均值（如圖10和表5所示）.從表5可看出在PIE上CDL也優(yōu)于其他算法.

另外，文獻(xiàn)［6］中提到：CS+PCA在滿足RIP條件的情況下可以得到很好的降維效果，可以用于數(shù)據(jù)可視化和數(shù)據(jù)分類.針對(duì)上述PIE庫，用本文中的字典P和直接對(duì)α做PCA降維的方法得到降維數(shù)據(jù)（d=64），本文算法可以有效恢復(fù)圖像；而文獻(xiàn)［6］采用CS+PCA方法，則無法恢復(fù)出原始數(shù)據(jù)（如圖11所示）.

從上述實(shí)驗(yàn)可以看出，本文CDL算法的圖像重構(gòu)效果明顯優(yōu)于其他算法.

表5　PIE人臉圖像重構(gòu)對(duì)比（d=8、16、32、64）Table 5　Comparison of reconstructed PIE （d=8，16，32，64）

3.2RIP條件驗(yàn)證

另外，回顧第3.1節(jié)中CS+PCA［6］在USPS數(shù)據(jù)集上3D可視化的結(jié)果（如圖8所示），在實(shí)驗(yàn)中，k=784，s=10，RIP條件為：d>18.94.當(dāng)維數(shù)降至3維時(shí)不滿足RIP條件限制，其低維（3D）嵌入也喪失了原始數(shù)據(jù)的可分性結(jié)構(gòu).CS算法只有在嚴(yán)格的條件限制下具有一定的信息保持能力，詳見文獻(xiàn)［9］.

圖11PIE人臉圖像重構(gòu)對(duì)比（從上到下:原始圖像、CS+PCA、CDL）（d=64）Fig.11　Reconstructed images of PIE（From top to bottom:original image，CS+PCA，CDL）（d=64））

圖12　Lena圖像和Barara圖像重構(gòu)對(duì)比（d=4）Fig.12　Reconstructed images of Lena and Barara（d=4）

表6　USPS手寫數(shù)字三類樣本（0、3、4）圖像重構(gòu)對(duì)比Table 6　Comparison of reconstructed USPS（0，3，4）

利用USPS數(shù)字0、3、4做圖像重構(gòu)實(shí)驗(yàn)時(shí)，針對(duì)RIP條件，對(duì)比CDL和CS+K-SVD的性能.首先，分別用CDL和K-SVD訓(xùn)練字典，字典規(guī)格均為256×784，即k=784.實(shí)驗(yàn)中稀疏系數(shù)的稀疏性s=6，則RIP條件：d>12.7.CDL算法中利用字典P降維；CS算法中，降采樣矩陣為高斯隨機(jī)陣.實(shí)驗(yàn)中兩種算法同時(shí)對(duì)數(shù)據(jù)降至12維和3維，實(shí)驗(yàn)結(jié)果如圖9和表6所示.可以發(fā)現(xiàn)，當(dāng)d=12時(shí)，在RIP條件臨界值附近，CS+K-SVD算法依然有效，但是當(dāng)維數(shù)更低時(shí)（d=3?12），CS+K-SVD算法無法完成圖像重構(gòu)；而CDL在d=3仍然能夠恢復(fù)數(shù)據(jù).因此，CDL能夠在RIP條件限制之外仍具有較好的圖像重構(gòu)能力.

3.3圖像壓縮

從壓縮的角度出發(fā)，為了最大限度地減少數(shù)據(jù)量，在本文算法的基礎(chǔ)上，不重疊的取出測試圖像塊.實(shí)驗(yàn)中，仍然取圖像塊大小為16×16，并分別降維至64、32、16、8，即分別對(duì)應(yīng)壓縮比CR為 4、8、16和32.測試圖像為Lena（512×512），分別在無噪聲，添加方差為10、20、40的噪聲情況下（如圖13～圖16所示），進(jìn)行壓縮重建.CDL與JPEG2000進(jìn)行對(duì)比，用PSNR來評(píng)判解壓圖像質(zhì)量的優(yōu)劣，如表7～表10所示.

實(shí)驗(yàn)表明：1）無噪聲時(shí)，JPEG2000解壓效果優(yōu)于CDL.2）但在噪聲環(huán)境下，CR較低時(shí)，CDL優(yōu)于JPEG2000；隨著噪聲的增加，CDL相比JPEG2000的優(yōu)勢越明顯.由于在重構(gòu)的過程中，當(dāng)原始信號(hào)X通過字典D轉(zhuǎn)化為稀疏系數(shù)α表示時(shí)，此過程中存在一定去噪的功能，而Y在字典P轉(zhuǎn)化為α表示時(shí)，恢復(fù)過程同樣有一定的去噪功能.因此，本文CDL算法對(duì)噪聲具有很好的魯棒性.

表7　Lena圖像壓縮重建（無噪聲）Table 7　Comparison of reconstructed Lena（No noise）

圖13　Lena圖像壓縮重建（從左到右:原始圖像、JPEG2000（38.45dB）、CDL（30.56dB））（無噪聲，CR=16）Fig.13　Reconstructed images of Lena（From left to right:original image，JPEG2000（38.45dB），CDL（30.56dB））（No noise，CR=16）

圖14　Lena圖像壓縮重建（從左到右:原始圖像、加噪圖像（28.15dB）、JPEG2000（32.04dB）、CDL（30.24dB）（σ=10，CR=16））Fig.14　Reconstructed images of Lena（From left to right:original image，noisy image（28.15dB），JPEG2000 （32.04dB），CDL（30.24dB）（σ=10，CR=16））

圖15　Lena圖像壓縮重建（從左到右:原始圖像、加噪圖像（22.09dB）、JPEG2000（25.93dB）、CDL（29.34dB）（σ=20，CR=16）Fig.15　Reconstructed images of Lena（From left to right:original image，noisy image（22.09dB），JPEG2000 （25.93dB），CDL（29.34dB）（σ=20，CR=16））

圖16　Lena圖像壓縮重建（從左到右:原始圖像、加噪圖像（16.09dB）、JPEG2000（19.76dB）、CDL（26.96dB）（σ=40，CR=16））Fig.16　Reconstructed images of Lena（From left to right:original image，noisy image（16.09dB），JPEG2000 （19.76dB），CDL（26.96dB）（σ=40，CR=16））

表8　Lena圖像壓縮重建（σ=10）Table 8　Comparison of reconstructed Lena（σ=10）

表9　Lena圖像壓縮重建（σ=20）Table 9　Comparison of reconstructed Lena（σ=20）

表10　Lena圖像壓縮重建（σ=40）Table 10　Comparison of reconstructed Lena（σ=40）

4　結(jié)束語

本文提出一種聚能量字典學(xué)習(xí)算法，應(yīng)用于圖像降維與恢復(fù).基于字典學(xué)習(xí)的理論，本文算法通過字典對(duì)（高維字典D和低維字典P），能夠在原始信號(hào)X到特征Y的降維過程中保留高維信號(hào)的本質(zhì)特征，并且能夠在RIP條件限制之外仍具有較好的信號(hào)重構(gòu)能力.在自然圖像、人臉圖像、手寫數(shù)字上的實(shí)驗(yàn)驗(yàn)證了本文算法的優(yōu)越性.

從X到Y(jié)降維的同時(shí)，因?yàn)閅中保留了X的幾何結(jié)構(gòu)特征，因此可以從Y中恢復(fù)出原始信號(hào)X.算法本身并不局限于內(nèi)積、距離、夾角等特征，只要能找到合適映射關(guān)系，可推導(dǎo)出不同的模型，以實(shí)現(xiàn)不同任務(wù)需求：如目標(biāo)識(shí)別、目標(biāo)跟蹤、視頻分析等.

References

1 Van der Maaten L J P，Postma E O，Van den Herik H J. Dimensionality reduction：a comparative review.Journal of Machine Learning Research，2009，10：66-71

2 Donoho D L.Compressed sensing.IEEE Transactions on Information Theory，2006，52（4）：1289-1306

3 Cand′es E J，Romberg J，Tao T.Robust uncertainty principles：exact signal reconstruction from highly incomplete frequency information.IEEE Transactions on Information Theory，2006，52（2）：489-509

4 Tropp J A，Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit.IEEE Transactions on Information Theory，2007，53（12）：4655-4666

5 Mairal J，Bach F，Ponce J.Task-driven dictionary learning.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（4）：791-804

6 Gao J B，Shi Q F，Caetano T S.Dimensionality reduction via compressive sensing.Pattern Recognition Letters，2012，33（9）：1163-1170

7 Gkioulekas I A，Zickler T.Dimensionality reduction using the sparse linear model.In：Proceedings of the 2011 Advances in Neural Information Processing Systems.Granada，Spain：Morgan Kaufmann，2011.271-279

8 Calderbank R，Jafarpour S，Schapire R.Compressed Learning：Universal Sparse Dimensionality Reduction and Learning in the Measurement Domain.Technical Report，Princeton University，USA，2009

9 Baraniuk R G，Wakin M B.Random projections of smooth manifolds.Foundations of Computational Mathematics，2009，9（1）：51-77

10 Hegde C，Wakin M B，Baraniuk R G.Random projections for manifold learning.In：Proceedings of the 2008 Advances in Neural Information Processing Systems.Vancouver，Canada：Morgan Kaufmann，2008.641-648

11 Chen M H，Silva J，Paisley J，Wang C P，Dunson D，Carin L.Compressive sensing on manifolds using a nonparametric mixture of factor analyzers：algorithm and performance bounds.IEEE Transactions on Signal Processing，2010，58（12）：6140-6155

12 Baraniuk R，Davenport M，DeVore R，Wakin M.A simple proof of the restricted isometry property for random matrices.Constructive Approximation，2008，28（3）：253-263

13 Weiss Y，Chang H S，F(xiàn)reeman W T.Learning compressed sensing.In：Proceedings of the 24th Annual Allerton Conference on Communications，Control and Computing.Illinois，USA：Citeseer，2007.535-541

14 Baraniuk R G，Cevher V，Duarte M F，Hegde C.Modelbased compressive sensing.IEEE Transactions on Information Theory，2010，56（4）：1982-2001

15 GleichmanS，EldarYC.Blindcompressedsensing. IEEE Transactions on Information Theory，2011，57（10）：6958-6975

16 Silva J，Chen M H，Eldar Y C，Sapiro G，Carin L.Blind compressed sensing over a structured union of subspaces. eprint arXiv：1103.2469，2011.

17 Zeyde R，Elad M，Protter M.On single image scale-up using sparse-representations.In：Proceedings of the 7th International Conference on Curves and Surfaces.Avignon，F(xiàn)rance：Springer，2012.711-730

18 Yang J C，Wang Z W，Lin Z，Cohen S，Huang T.Coupled dictionary training for image super-resolution.IEEE Transactions on Image Processing，2012，21（8）：3467-3478

19 Yang J C，Wright J，Huang T S，Ma Y.Image superresolution via sparse representation.IEEE Transactions on Image Processing，2010，19（11）：2861-2873

20 Adler A，Hel-Or Y，Elad M.A shrinkage learning approach for single image super-resolution with overcomplete representations.In：Proceedings of the 11th European Conference on Computer Vision.Heraklion，Crete，Greece：Springer，2010.622-635

21 Wei X，Kleinsteuber M，Shen H.Invertible nonlinear dimensionality reduction via joint dictionary learning.In：Proceedings of the 12th International Conference on Latent Variable Analysis and Signal Separation.Liberec，Czech Republic：Springer，2015.279-286

22 Aharon M，Elad M，Bruckstein A.K-SVD：an algorithm for designing overcomplete dictionaries for sparse representation.IEEE Transactions on Signal Processing，2006，54（11）：4311-4322

23 Elad M，Aharon M.Image denoising via sparse and redundant representations over learned dictionaries.IEEE Transactions on Image Processing，2006，15（12）：3736-3745

24 Pati Y C，Rezaiifar R，Krishnaprasad P S.Orthogonal matching pursuit：recursive function approximation with applications to wavelet decomposition.In：Proceedings of the 27th Asilomar Conference on Signals，Systems and Computers.Pacific Grove，USA：IEEE，1993.40-44

25 Tropp J A.Greed is good：algorithmic results for sparse approximation.IEEE Transactions on Information Theory，2004，50（10）：2231-2242

鄭思龍上海交通大學(xué)航空航天學(xué)院碩士研究生.主要研究方向?yàn)閳D像處理，計(jì)算機(jī)視覺與模式識(shí)別.

E-mail:zhengsilong@sjtu.edu.cn

（ZHENG Si-LongMaster student at the School of Aeronautics and Astronautics，Shanghai Jiao Tong University.His research interest covers image processing，computer vision，and pattern recognition.）

李元祥上海交通大學(xué)航空航天學(xué)院副教授.2001年獲得清華大學(xué)電子工程系博士學(xué)位.主要研究方向?yàn)檫b感圖像解譯，圖像識(shí)別，圖像重構(gòu)與評(píng)估，臺(tái)風(fēng)云圖信息提取與漢字信息處理.本文通信作者.E-mail:yuanxli@sjtu.edu.cn

（LI Yuan-XiangAssociate professor at the School of Aeronautics and Astronautics，Shanghai Jiao Tong University.He received his Ph.D.degree from the Department of Electronic Engineering，Tsinghua University in 2001.His research interest covers remote sensing image interpretation，image recognition，image reconstruction and evaluation，typhoon image information extraction，and Chinese information processing.Corresponding author of this paper.）

魏憲慕尼黑工業(yè)大學(xué)電氣與計(jì)算機(jī)工程系博士研究生.主要研究方向?yàn)閹缀蝺?yōu)化，數(shù)據(jù)表達(dá)與圖像處理.

E-mail:xianweich@gmail.com

（WEI XianPh.D.candidate in the Department of Electrical and Computer Engineering，Technische Univesitaet M¨unchen，Germany.His research interest covers geometry optimization，data representation，and image processing.）

彭希帥上海交通大學(xué)航空航天學(xué)院博士研究生.主要研究方向?yàn)閳D像處理，計(jì)算機(jī)視覺，機(jī)器學(xué)習(xí).

E-mail:xishuaipeng@sjtu.edu.cn

（PENG Xi-ShuaiPh.D.candidate at the School of Aeronautics and Astronautics，Shanghai Jiao Tong University.His research interest covers image processing，computer vision，and machine learning.）

Nonlinear Dimensionality Reduction Based on Dictionary Learning

ZHENG Si-Long1LI Yuan-Xiang1WEI Xian2PENG Xi-Shuai1

Most classic dimensionality reduction（DR）algorithms（such as principle component analysis（PCA）and isometric mapping（ISOMAP））focus on finding a low-dimensional embedding of original data，which are often not reversible.It is still challenging to make DR processes reversible in many applications.Sparse representation（SR）has shown its power on signal reconstruction and denoising.To tackle the problem of large scale dataset processing，this work focuses on developing a differentiable model for invertible DR based on SR.From high-dimensional input signal to the low-dimensional feature，we expect to preserve some important geometric features（such as inner product，distance and angle）such that the reliable reconstruction from the low dimensional space back to the original high dimensional space is possible.We employ the algorithm called concentrated dictionary learning（CDL）to train the high dimensional dictionary to concentrate the energy in its low dimensional subspace.Then we design a paired dictionaries:D and P，where D is used to obtain the sparse representation and P is a direct down-sampling of D.CDL can ensure P to capture the most energy of D.Then，the problem about signal reconstruction is transformed into how to train dictionaries D and P，so the process of input signal X to feature Y is transformed into the process of energy retention from D to P.Experimental results show that without the restrictions of linear projection using restricted isometry property（RIP），CDL can reconstruct the image at a lower dimensional space and outperform state-of-the-art DR methods（such as Gaussian random compressive sensing）.In addition，for noise-corrupted images，CDL can obtain better compression performance than JPEG2000.

Dimensionality reduction（DR），sparse representation（SR），compressed sensing（CS），dictionary learning CitationZheng Si-Long，Li Yuan-Xiang，Wei Xian，Peng Xi-Shuai.Nonlinear dimensionality reduction based on dictionary learning.Acta Automatica Sinica，2016，42（7）:1065-1076

10.16383/j.aas.2016.c150557

2015-09-02錄用日期2016-01-13
Manuscript received September 2，2015；accepted January 13，2016
國家自然科學(xué)基金（U1406404，61331015，41174164）資助
Supported by National Natural Science Foundation of China （U1406404，61331015，41174164）
本文責(zé)任編委胡清華
Recommended by Associate Editor HU Qing-Hua
1.上海交通大學(xué)航空航天學(xué)院上海200240中國2.慕尼黑工業(yè)大學(xué)電氣與計(jì)算機(jī)工程系慕尼黑D-80333德國
1.School of Aeronautics and Astronautics，Shanghai Jiao Tong University，Shanghai 200240，China2.Department of Electrical and Computer Engineering，Technische Universitaet M¨unchen，Munich D-80333，Germany