基于L1-范數的二維線性判別分析

陳思寶陳道然 羅 斌

(安徽大學計算機科學與技術學院 合肥 230601)

(安徽省工業圖像處理與分析重點實驗室 合肥 230039)

基于L1-范數的二維線性判別分析

陳思寶*陳道然 羅 斌

(安徽大學計算機科學與技術學院 合肥 230601)

(安徽省工業圖像處理與分析重點實驗室 合肥 230039)

為了避免圖像數據向量化后的維數災難問題，以及增強對野值(outliers)及噪聲的魯棒性，該文提出一種基于L1-范數的2維線性判別分析(L1-norm-based Two-Dimensional Linear Discriminant Analysis, 2DLDA-L1)降維方法。它充分利用L1-范數對野值及噪聲的強魯棒性，并且直接在圖像矩陣上進行投影降維。該文還提出一種快速迭代優化算法，并給出了其單調收斂到局部最優的證明。在多個圖像數據庫上的實驗驗證了該方法的魯棒性與高效性。

圖像處理；L1-范數；2維線性判別分析；線性投影；降維

1 引言

在模式識別和圖像處理領域，由于所處理的圖像維數特別高，而訓練樣本數量又非常有限，經常導致“維數災難”問題[1]。此外，在高維空間中存在著測度的“集中現象”，為了克服這些問題并且使得后續的數據表示或分類更加穩健，對高維數據進行降維就成了一個非常重要的步驟。

眾所周知，最為經典的線性投影降維方法通常將高維訓練數據用向量形式進行表示，再進行線性投影降維和特征提取，其中基于向量的1維線性投影降維方法主要有主成分分析(Principal Component Analysis, PCA)[2,3]，線性判別分析(Fisher Linear Discriminant Analysis, FisherLDA)[1,2], PCA+LDA[4]等。然而，1維方法通常將圖像數據拉直成向量形式，其維數通常非常高，但訓練數據又非常有限，這通常導致矩陣計算的不穩定，出現矩陣奇異問題。針對1維方法所遇到的問題，許多學者又提出了直接基于圖像矩陣的線性投影降維方法，即2維線性投影降維方法。經典的2維方法有2維主成分分析(Two-Dimensional PCA, 2DPCA)[5,6]和2維線性判別分析(Two-Dimensional LDA, 2DLDA)[7?9]。然而，這些1維的和2維的線性投影降維方法都基于L2-范數來計算相應的目標函數。當訓練數據中存在野值或噪聲時，計算所得到的投影方向會嚴重受到這些野值或噪聲的影響。

最近，一些文獻中出現了基于L1-范數[10?16]的線性投影降維方法，諸如：基于L1-范數的PCA (L1-norm based PCA, PCA-L1)[12]、基于旋轉不變L1-范數的LDA(Rotational invariant L1-norm based LDA, LDA-R1)[13]、基于L1-范數的LDA(L1-norm based LDA, LDA-L1)[14,15]及基于L1-范數的2DPCA(L1-norm based 2DPCA, 2DPCAL1)[16]。這些基于L1-范數的線性投影降維方法均對野值及噪聲表現出了很強的魯棒性。但是，PCA-L1, LDA-R1和LDA-L1都把圖像數據進行了向量化預處理，并沒有充分利用圖像數據固有的矩陣形式，破壞了圖像數據原有的空間結構關系。2DPCA-L1著重利用圖像數據矩陣來提取低維特征，但它沒有充分利用訓練數據中的類別信息以提高投影方向的判別性能。

本文提出的2DLDA-L1線性投影降維方法不僅充分利用L1-范數對野值及噪聲的強魯棒性，而且直接對圖像數據矩陣進行線性投影，減少了圖像數據空間的信息丟失，并且避免了圖像向量化后的高維矩陣的龐雜計算及解的不穩定性。相比于以前的方法對野值及噪聲具有更強的魯棒性，并且在分類識別的性能上取得了顯著提升。

本文其余部分的結構安排如下：第2節先提出2DLDA-L1最優投影方向的目標優化函數，然后給出一種優化迭代方法，最后給出多重投影方向的完整2DLDA-L1算法并分析算法的復雜度；第3節在多個圖像數據庫上實驗驗證所提出的2DLDA-L1算法的判別性能及魯棒性能，并給出相應的實驗結果及分析；第4節為結束語。

2 基于L1-范數的2維線性判別分析(2DLDA-L1)

2.1 2DLDA-L1最優投影方向

采用w(t+1)=w(t)+γg(w(t ))來更新2DLDAL1最優投影向量w(t)，其中

γ＞0為學習步長，g(w(t))的獲得見文獻[14]。循環交替計算式(2)的符號函數及式(3)的梯度公式來求解2DLDA-L1最優投影向量w。在迭代過程中，若目標函數J(w(t+1))停止增長，則終止循環。否則，更新式(2)并繼續循環，直到找到滿足條件的投影向量w。

可以證明：在每次循環計算式(2)與式(3)后，式(1)中的目標函數J(w(t+1))都保持非降。另外，J函數存在上界(當目標函數J 在分母約束恒為 1 時，根據文獻[17，18]中的定理，可知其上界為圖像類間離散度矩陣的最大特征值)，因此，循環計算式(2)與式(3)的迭代過程逐漸收斂。然而，通過迭代算法所求的投影向量w可使目標函數J達到局部最優，但并不能保證J達到全局最優。由于篇幅有限，此處略去詳細證明，具體證明方法可以參考文獻[14]。

2.2 2DLDA-L1多個投影方向擴展

前面所述的迭代優化求解方法僅計算2DLDAL1的一個最優投影方向，這不利于實際應用，故需要擴展到求取多個投影方向。設已得到第1個最優投影軸為w1，我們在w1的正交補空間中尋求第2個最優投影軸w2，即在w1的正交補空間中最大化式(1)。w1的正交補空間為Is?w1，其中Is表示一個s維的單位矩陣。故存在一個向量b1∈Rs，使w2=(Is?w1)b1。代入w2到式(1)中，得

同樣，由2.1節的迭代算法可解出b1。再根據公式w2=(Is?w1)b1，便可得到第2個投影軸w2，并歸一化

設已獲得l個最優投影軸w1w2…wl，則第l+1個最優投影軸wl+1可在正交向量w1w2…wl的正交補空間中尋求，其中w1w2…wl的正交補空間為

Is?Wl，投影矩陣Wl=[w1w2…wl]。同樣存在一個向量bl∈Rs，使wl+1=(Is?Wl)bl，則bl可迭代優化由新數據矩陣A=(Is?Wl)計算的式(1)來求出。注意到

2.3 2DLDA-L1計算復雜度分析

對于含有c個類別共n個(m×s)大小的圖片訓練數據集，所提出的2DLDA-L1最耗時的是兩重循環內部的步驟2(3)計算符號函數與(4)計算梯度方向，它們的計算復雜度分別為O((cm+nm)s)和O(2(cm+nm)s)。因此，若欲每次內循環迭代t次，共提取q個投影方向軸，則整個2DLDA-L1的計算復雜度為O((cm+nm)stq)。在相同的數據集上，與之相對應的2DLDA的計算復雜度為O((n+c)ms2+s3)。LDA-L1的計算復雜度為O((c+n)mstq)，最耗時的是兩重循環內部的計算符號函數與計算梯度方向。LDA-R1的計算復雜度為O((n+c)m2s2tq2)，最耗時的是其中的特征值分解。LDA的計算復雜度為O((n+c)m2s2+m3s3)，最耗時的是求解廣義特征向量。

表1 基于L1-范數的2維線性判別分析(2DLDA-L1)

3 實驗結果及分析

為了驗證本文所提出的2DLDA-L1方法的魯棒性及最終識別性能，本文選擇在3個常用的人臉圖像數據庫(PIE[19], AR[20]及ORL[21])上進行先降維后分類識別的對比實驗。在實驗中，我們選擇4種對比方法，分別是LDA, LDA-R1, LDA-L1和2DLDA。為了保證實驗結果的公平與合理性，同類實驗中的參數設置均一致。為簡化實驗，我們僅采用最近鄰分類器進行分類識別。

3.1 PIE人臉數據庫

圖1 J(w(t))隨著迭代次數t的變化趨勢

PIE人臉數據庫提供了不同姿態、光照、表情條件下68位志愿者的40000多幅不同的圖像，每一幅圖像都是在嚴格控制的條件下采集的。本文在其中一個子集共17000幅圖像上進行測試，即隨機提取出68人每人24幅圖像作為PIE子庫。所有的人臉圖像都被縮放到32×32大小，量化到256級灰度。

3.1.1 目標函數的迭代收斂性 2.1節中提到了目標函數J(w(t))是非降的并逐漸收斂到局部最優。在這一部分，我們驗證2DLDA-L1的目標函數J(w(t))的局部最優化，并與迭代次數t之間的關系。實驗結果如圖1所示。

圖1表明，在提取投影向量的過程中，隨著迭代次數的逐漸增加，目標函數J(w(t))逐漸遞增并達到局部最大。

3.1.2 步長參數γ的影響

為了驗證梯度法w(t+1)=w(t)+γg(w(t ))中更新步長參數γ的影響，我們從集合{0.01,0.05,0.1,0.5, 1,5,10,50,100,500,1000}中選擇不同的γ值測試其對收斂性及識別率的影響。實驗結果如圖2所示。

圖2 步長參數γ的影響

圖2(a)和2(b)充分說明γ不僅影響算法的收斂速度而且還影響算法的識別性能。由于2DLDA-L1中的目標函數并不是全局嚴格凸的，一個固定的γ值易使迭代算法中的目標函數局部最優化，因此在運行實驗時，我們隨機選擇不同的γ值來優化目標函數，并選取使得目標函數達到最大的參數。

3.2 AR人臉數據庫

AR人臉數據庫由西班牙巴塞羅那計算機視覺中心建立，包括3120幅圖像，共120個人，每人26幅圖像，采集環境中的攝像機參數、光照環境、攝像機距離等都受到嚴格控制。所有人臉圖像都被縮放到32×32大小，量化到256級灰度。

3.2.1 投影軸數q對識別率的影響 線性投影降維是處理高維數據的一個重要步驟。為了驗證不同的投影軸數對識別率的影響，本節依次選擇1,2,…,20個投影軸數進行測試。實驗結果如圖3所示。

圖3表明，隨著投影軸數的逐漸增加，各種方法的識別率都會達到一個飽和值。但是，當投影軸數相同時，2DLDA-L1方法的識別率比其它方法的識別率高。

圖3 識別率隨著不同投影軸數q的變化趨勢

3.2.2 噪聲的影響 為了驗證2DLDA-L1對噪聲的魯棒性，本節在加有高斯噪聲或椒鹽噪聲的人臉圖像上進行對比分類識別實驗。圖4(a)和圖4(b)分別為加入高斯噪聲和椒鹽噪聲后的圖像示例，圖像加入高斯噪聲的方差或椒鹽噪聲的密度從小到大依次為0.0001, 0.0005, 0.001,0.005, 0.01, 0.05, 0.1。實驗結果如圖5所示。

圖4 加入噪聲示例

圖5表明，隨著噪聲方差或密度的逐漸增加，各種方法的識別率逐漸降低。但是2DLDA-L1的識別率一直最高，這說明2DLDA-L1具有更好的魯棒性。

3.3 ORL人臉數據庫

ORL數據庫是一個最為常用的人臉數據庫，它由40個人，每個人10幅92×112的灰度人臉正面圖像組成，每張人臉圖像都有姿態、表情和面部飾物的變化。所有的人臉圖像都被縮放到32×32大小，量化到256級灰度。

3.3.1 不同訓練集大小對識別率的影響 為了驗證不同的訓練集大小對識別率的影響，每類中前k(k=2, 3,…,7)幅圖像作為訓練集，余下的作為測試集。實驗效果如圖6所示。

圖6表明，同等條件下，隨著訓練樣本數目的增多，各種方法的識別率逐漸增高，而2DLDA-L1的識別率一直最高，這充分說明2DLDA-L1方法的高效性。

3.3.2 部分缺失遮擋的影響 本節對人臉圖像設置不同比例的缺失或遮擋，以驗證所提出的2DLDA-L1的魯棒性。設置圖像缺失或遮擋的百分比分別為5%, 10%,15%,20%,25%,30%,35%,40%,45%,50%。圖7(a)為不同比例塊隨機缺失示例，圖7(b)為不同比例塊隨機遮擋示例。實驗結果如圖8所示。

圖8表明，隨著圖像隨機缺失或遮擋的百分比逐漸增加，2DLDA算法的識別率有很大的波動而其它算法的識別率整體趨勢都在逐漸下降。然而，當有相同比例的缺失或遮擋時，2DLDA-L1方法的識別率比其它算法的識別率高，這說明2DLDA-L1具有更強的魯棒性。

4 結束語

圖5 噪聲對識別率的影響

圖6 識別率隨著不同訓練集大小的變化趨勢

圖7 圖像隨機子塊缺失遮擋示例

圖8 不同比例缺失遮擋對識別率的影響

本文在LDA, LDA-L1和2DLDA方法的基礎上，提出基于L1-范數的2維線性判別分析(2DLDAL1)。該方法充分利用L1-范數對野值及噪聲的強魯棒性，并且直接在圖像數據矩陣上進行線性投影降維，減少了圖像數據空間的信息丟失以及避免了向量化圖像數據出現的維數災難。提出了一個單調優化迭代算法來求解其最優投影矩陣，并給出了其單調收斂到局部最優的證明。在多個圖像數據庫上的實驗結果表明，本文提出的2DLDA-L1對野值及噪聲具有強魯棒性，并且比其它方法具有更好的判別性能。注意到，本文方法僅僅是收斂到局部最優。在后續的工作中，我們將繼續深入研究如何找到全局最優。

[1] Duda R, Hart P, and Stork D. Pattern Classification[M]. Second edition, New York: John Wiley & Sons, 2001: 2-5.

[2] Chan L, Salleh S, Ting C, et al.. Face identification and verification using PCA and LDA[C]. International Malaysia, 2008: 1-6.

[3] Rujirakul K, So-In C, Arnonkijpanich B, et al.. PFP-PCA: parallel fixed point PCA face recognition[C]. 2013 4th International Conference on Intelligent Systems, Modelling Symposium on Information Technology, Kuala Lumpur, and Simulation, Bangkok, 2013: 29-31.

[4] Belhumeur P, Hespanha J, and Kriegman D. Eigenfaces vs. fisherfaces: recognition using class specific linear projection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(7): 711-720.

[5] Yang Jian, Zhang D, Frangi A, et al.. Two-dimensional PCA: a new approach to appearance-based face representation and recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(1): 131-137.

[6] Wang Shi-min, Ye Ji-hua, and Ying De-quan. Research of 2DPCA principal component uncertainty in face recognition[C]. 2013 8th International Conference on Computer Science & Education, Colombo, Sri Lanka, 2013: 159-162.

[7] Li Ming and Yuan Bao-zong. A novel statistical linear discriminant analysis for image matrix: two-dimensional 527-532.

[8] Mahanta M and Plataniotis K. Ranking 2DLDA features based on fisher discriminance[C]. IEEE International Conference on Acoustic, Speech and Signal Processing, Fisherfaces[J]. Pattern Recognition Letters, 2005, 26(5): Florence, Italy, 2014: 4-9.

[9] Wang Bin-bin, Hao Xin-jie, Chen Li-sheng, et al.. Face recognition based on the feature fusion of 2DLDA and LBP[C]. 2013 Fourth International Conference on Information, Intelligence, Systems and Applications, Piraeus, Greece, 2013: 10-12.

[10] Pang Yan-wei, Li Xue-long, and Yuan Yuan. Robust tensor analysis with L1-norm[J]. IEEE Transactions on Circuits Syst ems for Video Techology, 2010, 20(2): 172-178.

[11] Zheng Wen-ming, Lin Zhou-chen, and Wang Hai-xian. L1-norm kernel discriminant analysis via Bayes error bound optimization for robust feature extraction[J]. IEEE Transactions on Neural Networks and Learning Systems, 2014, 25(4): 793-805.

[12] Kwak N. Principal component analysis based on L1-norm maximization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(9): 1672-1680.

[13] Li Xi, Hu Wei-ming, Wang Han-zi, et al.. Linear discriminant analysis using rotational invariant L1 norm[J]. Neurocomputing, 2010, 73(13): 2571-2579.

[14] Wang Hai-xian, Lu Xue-song, Hu Zi-lan, et al.. Fisher discriminant analysis with L1-norm[J]. IEEE Transactions on Cybernetics, 2013, 44(6): 828-842.

[15] Zhong Fu-jin and Zhang Jia-shu. Linear discriminant analysis based on L1-norm maximization[J]. IEEE Transactions on Image Processing, 2013, 22(8): 3018-3027.

[16] Li Xue-long, Pang Yan-wei, and Yuan Yuan. L1-norm-based 2DPCA[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2010, 40(4): 1170-1175.

[17] Wang Hai-xian, Tang Qin, and Zheng Wen-ming. L1-normbased common spatial patterns[J]. IEEE Transactions on Biomedical Engineering, 2012, 59(3): 653-662.

[18] Jenatton R, Obozinski G, and Bach F. Structured sparse principal component analysis[C]. International Conference on Artificial Intelligence and Statistics, Paris, France, 2009: 1-8.

[19] Gross R, Matthews I, Cohn J, et al.. Multi-PIE[C]. 8th IEEE International Conference on Automatic Face & Gesture Recognition, Amsterdam, The Netherland, 2008: 1-8.

[20] Martinez A and Benavente R. The AR face database[R]. CVC Technical Report 24, Barcelona, Spain, 1998.

[21] Samaria F and Harter A. Parameterisation of a stochastic model for human face identification[C]. Proceedings of the Second IEEE Workshop on Applications of Computer Vision, Sarasota, USA, 1994, 138-142.

陳思寶： 男，1979年生，副教授，碩士生導師，研究方向為圖像處理與模式識別.

陳道然： 女，1989年生，碩士生，研究方向為圖像處理與模式識別.

羅 斌： 男，1963年生，教授，博士生導師，研究方向為計算機視覺與模式識別.

L1-norm Based Two-dimensional Linear Discriminant Analysis

Chen Si-bao Chen Dao-ran Luo Bin
(School of Computer Science and Technology, Anhui University, Hefei 230601, China)
(Key Laboratory for Industrial Image Processing and Analysis of Anhui Province, Hefei 230039, China)

To overcome the curse of dimensionality caused by vectorization of image matrices, and to increase robustness to outliers, L1-norm based Two-Dimensional Linear Discriminant Analysis (2DLDA-L1) is proposed for dimensionality reduction. It makes full use of strong robustness of L1-norm to outliers and noises. Furthermore, it performs dimensionality reduction directly on image matrices. A rapid iterative optimization algorithm, with its proof of monotonic convergence to local optimum, is given. Experiments on several public image databases verify the robustness and the effectiveness of the proposed method.

Image processing; L1-norm; Two-Dimensional Linear Discriminant Analysis (2DLDA); Linear projection; Dimensionality reduction

TP391.4

： A

：1009-5896(2015)06-1372-06

10.11999/JEIT141093

2014-08-18收到，2015-02-04改回

國家自然科學基金(61202228)和安徽省高校自然科學研究重點項目(KJ2012A004)資助課題

*通信作者：陳思寶 sbchen@ahu.edu.cn