噪聲條件下對稀疏表示分類器的優化

陳浩

（上海海事大學信息工程學院，上海 201306）

0 引言

信號的稀疏表示在最近幾年引起了廣泛的興趣，并在許多應用中顯示出強大的特性，特別是在壓縮和去燥方面。通過觀察可以發現，大多數的自然信號可以適當的稀疏表示。稀疏信號表示的應用可以在諸如圖像去噪[1]、恢復[2]、視覺跟蹤[3]，檢測[4]和分類[5]。Wright等人[6]通過研究提出了一種基于稀疏表示的分類方法（Sparse Representation Classification）。其基本思想是將測試樣本的稀疏表示作為所有訓練樣本（超完備字典）的（稀疏）線性組合學習，其中產生最低重構誤差的類的特定字典決定了測試樣本的類標簽。SRC也積極應用于各種分類問題，包括車輛分類、多模態生物特征、數字識別、語音識別、高光譜圖像分類。

稀疏表示最稀疏的解決方案可以通過利用L0范數最小化來解決，已經證明L0范數最小化問題是解決線性優化問題，也是NP難問題。然而，文獻[7]已經證明獲得的解決方案由L0范數最小化可以等價于求解L1范數的最小化。SRC在人臉識別和魯棒性方面表現非常好，雖然SRC已經極大地影響人臉識別領域并且被廣泛地使用和研究，但還有一些未解決的問題。例如，它不能完美地解決人臉姿態變化、照明條件和面部表情等因素的影響。而且SRC算法通常是迭代求解最小化問題，因此耗時很長。目前已經有人提出很多方法改進SRC算法來獲得更好的性能。例如，鄧等人[8]提出了一個擴展的SRC，該方案是應用了一個內部變體字典來表示訓練樣本和測試樣本之間的差異。He等人[9]提出了一個兩階段測試樣本稀疏表示方法來提高數據集的健壯性和算法的效率。所有的這些方法仍然忽略了一個非常重要的事實，那就是訓練樣本仍不能精確地表示測試樣本且噪聲不能直接丟棄。傳統的SRC方法都是假設每個測試樣本可以用訓練樣本線性地表示。這個假設很難避免噪聲問題，并且在樣本的個數大于訓練樣本個數時，不能精確地表示測試樣本。

基于上述描述，我們提出利用局部線性編碼的方法和在迭代降噪處理的過程中考慮類依賴的特性，構建一個能夠揭示數據局部結構和樣本之間類依賴關系的方法，來提升在噪聲條件下SRC的分類效果。我們的假設是通過選擇訓練樣本的子集作為局部字典，并用其線性表示測試樣本，能夠很好地提高SRC算法的時間復雜度，也有過濾部分噪聲的效果。

1 相關研究

假設有n個訓練樣本，用向量的形式表示為X=[x1,x2,x3,…,xn]，其中總共有C類，每個類別有m個樣本。所有的測試樣本用y表示，在操作之前應該將所有樣本歸一化為長度為1的單位列向量。

1.1 SRC

當談到基于L1范數優化的表示分類方法時，稀疏表示（SRC）是最具有代表性的方法。它是使用訓練樣本確定一個線性組合來表示測試樣本y。因此，SRC可以大致用下面的式子來表示：

其中y是歸一化之后的測試樣本，xi的系數表示為ai(i=1,2,…,n)。為了便于描述我們可以按下列的方式重寫（1）式。

可以使用L1范數來求解α的最小化問題：

或者：

或者：

我們利用拉格朗日算法來求解式（5），其中α是訓練樣本矩陣X的系數。λ作為拉格朗日乘子。ξ是一個小的實數。

1.2 迭代降噪處理

據研究所知，式（2）不能準確地表示真實情況下訓練樣本和測試樣本之間的關系，我們可以確定的是來自任何主體的臉部圖像都有不可預知的組成部分和表示噪聲。這里迭代處理NMFIRC的主要原理是：迭代計算線性組合系數的表示解和表示噪聲，直到它收斂，然后利用確定的“最優”表示解決方案來分類。對于（1）式中的si可以表示噪聲，也可以用下面的式子表示：

其中si表示噪聲向量，同樣地可以用基于L1范數的優化問題來求解α。如下所示：

這里假設樣本數據已經做了歸一化處理，D表示處理之后的數據。首先設y′=y-si我們可以通過如下式子來求解α的值：

該式子等價于求解：

并計算然后設則目標函數可以表示為：

同樣地，我們可以通過以下式子求解：

反復執行（8）（10）兩步更新si，直到最大迭代次數為止。

2 提出的相關方法

本節將詳細的講解我們所提出的方法，不管是基于L1范數的稀疏表示分類算法（SRC）或者是基于L2范數的協作表示（CRC），這些方法都是假設每個測試樣本可以由訓練樣本線性表示，不過這個假設忽略了一個非常重要的事實，那就是測試樣本依然不能用訓練樣本精確的表示，例如噪聲不能直接被丟棄。因此，我們提出的假設是在選擇字典集時來表示測試樣本時，是否可以有選擇的丟棄部分噪聲數據，以達到更精確地線性表示組合。同時，傳統的SRC的一個限制是它不包含數據集的類標簽（先前）信息。它只使用類標簽信息在計算每個類的殘差時進行后處理，卻忽略了類之間歐幾里得距離的相關性。我們提出類依賴的KNN方法，將獲得的距離信息和傳統的分類信息統一起來，以達到更好的分類效果。

2.1 局部線性編碼設計

由LCC[10]可得，局部特征比稀疏性更為重要，局部必然會導致稀疏性，反之亦然。我們提出的方法通過選擇局部約束來達到更好的稀疏性。在流形學習中，局部線性被用來捕捉局部的幾何結構。例如，局部線性嵌入（LLE），使用局部鄰居線性重建每個數據，目的是捕捉自然的局部結構。我們首先在原始的訓練樣本中選擇它的K個最近鄰樣本，作為子集字典。解決以下式子來求解最優化問題：

其中樣本xi的K最近鄰居表示為：

λ＞0是平衡因子，通過循環迭代（8）（10）（11）式子以達到最優化的稀疏向量表，即為數據對象xi的最佳稀疏重構系數。該系數表示為：

我們可以通過圖1更直觀地表示。

2.2 類依賴KNN（cdKNN）

SRC分類算法主要是通過比較每類的殘差來確定測試樣本的類別，沒有考慮樣本的空間距離信息，在各種各樣的文獻中，例如SOMAP，局部線性嵌入，局部保留投影（LPP）和局部Fisher判別分析（LFDA），都是考慮了樣本之間的局部結構信息。研究表明，LFDA提供了一個很好的方法將數據投影到較低維的子空間。使得來自不同類的樣本被很好地分離，另外LFDA通過保留每各類的局部結構得到有效的組合實現了線性判別分析和LPP的性質。受到這些啟發，我們引入cd?KNN來捕獲樣本之間的局部結構，通過融合殘差信息和樣本之間的歐幾里得距離信息達到更優的分類效果。

2.3 基于局部線性編碼和融合局部結構信息的SRC優化算法

假設訓練數據集用表示，每個類別中的數據用表示，測試樣本為y∈Rd，則整個流程如下：

第一步：對所有的訓練樣本和測試樣本使用PCA方法，得到P∈Rd×p的投影矩陣，并通過計算D=PTX得到p維的數據集用D表示。

第二步：在降維后的數據集D之上選擇局部線性編碼樣本。主要是通過KNN算法選擇與測試樣本相近的K個樣本作為局部字典集。用XN(xi)表示。

第三步：對選擇的局部訓練樣本和測試樣本用如下方法進行歸一化，XN(xij)=XN(xij)/||XN(xij)||和y=y/||y||，并且用si=[0,0,....,0]T表示初始噪聲。

第四步：反復執行式子（9）（10）（11）直到最大迭代次數q為止，更新和的值。

第五步：計算每個類別的殘差，使用如下式子，即第i類的殘差：

其中XN(xij)是第i類，第j個訓練樣本。第i類的樣本個數為第二步選擇的k個最近鄰居，則是預先計算得到的最佳稀疏系數。

第六步：計算測試樣本y和第二步求得的樣本字典集中每個樣本XN(xij)的歐幾里得距離，即dij=D(y,XN(xij))。并求其平均距離作為第i類的距離。

第七步：求得以下式子即為測試樣本y的類別標簽。

圖1 即為提出的局部線性編碼的整個流程

3 實驗與結果分析

3.1 實驗數據集

在圖像識別領域，最常用的數據集有三個，分別是ORL人臉數據庫、PIE數據庫和AR數據庫。實驗中使用這三種人臉數據來驗證我們的想法。其中ORL數據庫包含40個類別，每類10個樣本的圖像。每幅圖像的面部表情和外部特種都各部相同。實驗數據是從每類中選擇5幅圖像作為訓練數據，共200幅，其他圖像作為測試數據。AR圖像數據主要在臉部表情上存在較大的變化，實驗中，選擇了20個類別，每類10幅圖像，其中選擇每類5幅作為訓練數據，5幅作為測試數據。PIE數據集的特點是每個人采集時的光照、表情和姿態都不一樣，同樣是選擇其中20個類別，每個類別21幅。實驗中每類選取17張作為訓練數據，4張作為測試數據。

3.2 實驗結果分析

我們的算法主要是通過利用局部線性編碼的方式過濾掉部分噪音數據和融合具有類依賴特性的空間距離信息來提高分類精度。因此，實驗中，分別驗證這兩種方法對SRC分類效果的影響，并且最終與我們的算法效果作對比來驗證我們提出方法的有效性。表1顯示的是不同算法在三種數據集上的最優識別率。其中cdSRC算法的參數包括融合稀疏（p）即最優權重，LLC+SRC方法是選擇合適的局部字典集，參數為選擇字典集的個數（K），而我們的算法（cdLLCSRC）是包括的參數有：選擇局部編碼集的個數（K），融合空間距離信息的參數（p），和降噪過程中的迭代次數（t）。

表1 幾種算法最優識別率比較（%）

從實驗結果中可以看出：（1）在三種數據集上我們的算法和基本的SRC算法、有類依賴特性的SRC算法（cdSRC）、從LLC算法借鑒過來的LLCSRC算法相比較，都取得了更好的分類結果。（2）其中類依賴的SRC（cdSRC）算法在特定的條件下相比SRC算法有優異的結果；而根據LLE算法思想改進的SRC算法比SRC算法也有很好的表現。通過對比發現，我們的算法分類效果優異且得到了很大的提升，這充分證明臉表情、光照、角度的影響下，cdSRC和LLCSRC的表現不佳。主要是因為在含噪聲的圖像中，選取的圖像特征量的多少對分類效果有較大的影響。我們融合了LLC思想和類依賴的特性得到的cdLLCSRC算法卻在少量特征條件下得到了很好的分類效果。這也充分表明了我們算法的有效性。

圖2是各個算法在三種不同的數據集上的識別率表現，可以發現在人臉表情、光照、角度的影響下，cd?SRC和LLCSRC的表現不佳。主要是因為在含噪聲的圖像中，選取的圖像特征量的多少對分類效果有較大的影響。我們融合了LLC思想和類依賴的特性得到的cdLLCSRC算法卻在很少的特征條件下得到了很好的分類效果。這也充分證明了我們算法的有效性。

圖2

圖3

圖4

4 結語

本文提出了選擇局部編碼并融合歐幾里得距離信息來提升在噪聲條件下對人臉圖像的分類效果。實驗表明我們的方法在低維條件下也能取得很好的分類效果。當然，我們的算法涉及選擇局部編碼個數的參數K和權衡距離信息的平衡因子p。如何降低調參的復雜度，將是我們未來探索的方向。

[1]M.Elad,M.Aharon,Image Denoising Via Sparse and Redundant Representations Overlearned Dictionaries,IEEE Trans.Image Process，2006，15（12）：3736-3745.

[2]J.Mairal,M.Elad,G.Sapiro,Sparse Representation for Color Image Restoration,IEEE Trans.Image Process，2008，17（1）：53-69.

[3]T.Bai,Y.F.Li.Robust Visual Tracking with Structured Sparse Representation Appearance Model,Pattern Recognit，2012，45（6）：2390-2404.

[4]X.Zhu,J.Liu,J.Wang,C.Li,H.Lu.Sparse Representation for Robust Abnormality Detection in Crowded Scenes,Pattern Recognit，2014，47（5）：1791-1799.

[5]L.-C.Chen,J.-W.Hsieh,Y.Yan,D.-Y.Chen,Vehicle Make and Model Recognition Using Sparse Representation and Symmetrical Surfs,Pattern Recognit，2015，48（6）：1979-1998.

[6]J.A.Wright,A.Y.Yang,A.Ganesh,S.S.Sastry,Y.Ma.Robust Face Recognition Via Sparse Representation,IEEE Trans.Pattern Anal.Mach.Intell，2009，31（2）.

[7]K.Yu,T.Zhang,Y.Gong.Nonlinear Learning Using Local Coordinate Coding.Proc.of Nips'09,2009.

[8]W.Deng,J.Hu,J.Guo,Extended SRC:Undersea Mpled Face Recognition Via Intraclass Variant Dictionary,IEEE Trans.Pattern Anal.Mach.Intell，2012，34（9）：1864-1870.

[9]S.T.Roweis,L.K.Saul.Nonlinear Dimensionality Reduction by Locally Linear Embedding,Science，2000，290（5500）：2323-2326.

[10]E.Candes,T.Tao.Near-Optimal Signal Recoveryfrom Random Projections:Universal Encoding Strategie.