李 勇，梁志貞，夏士雄

LI Yong,LIANG Zhizhen,XIA Shixiong

中國礦業(yè)大學 計算機科學與技術(shù)學院，江蘇 徐州 221116

School of Computer Science and Technology,China University of Mining and Technology,Xuzhou,Jiangsu 221116,China

1 引言

在大規(guī)模的數(shù)據(jù)分析問題中，高維的特征向量會造成高維協(xié)方差矩陣奇異性問題，從而使問題的解決變得困難，因此降維是非常重要的。要求它在不降低性能表現(xiàn)的前提下，通過降低特征向量的維數(shù)來簡化問題。主成分分析（PCA）[1]就是一種常用的降維方法，它常用一組向量來最大限度地表示所給的數(shù)據(jù)。這些向量組成了一個低維的線性子空間，通過這個子空間，可以有效地獲取原始輸入空間中的數(shù)據(jù)的內(nèi)在結(jié)構(gòu)。

由于PCA是基于圖像向量的方法，所以它在降低特征維數(shù)時，比不上直接基于兩維圖像矩陣的方法方便。1993年Liu等人提出利用數(shù)字圖像矩陣直接構(gòu)造圖像散布矩陣，并在此基礎(chǔ)上進行鑒別分析的新方法[2]；2003年Yang改進了Liu的方法[3]，得到一種具有統(tǒng)計不相關(guān)性的圖像投影鑒別分析方法；2004年Yang等人[4]將文獻[3]的方法用于圖像重構(gòu)，取得了很好的效果。

由于在PCA和2DPCA[4]中的目標函數(shù)都運用了L2范數(shù)，所以異常值的出現(xiàn)會因L2范數(shù)的使用而被擴大，所以這種方法對異常值較敏感。為了減輕這個問題的影響并且取得更好的穩(wěn)定性，許多人做了相關(guān)的研究[5-9]，在文獻[7]中，改進了以往的L1-PCA算法，并取得了不錯的效果。在文獻[8]中，改進了基于L2范數(shù)的傳統(tǒng)的2DPCA，提出了基于L1范數(shù)的2DPCA（2DPCA-L1）方法。

本文對2DPCA-L1方法進行了改進和推廣，提出了基于L1范數(shù)且受Lp范數(shù)約束的2DPCA方法（2DPCA-Lp），其主要思路是直接對圖像矩陣進行操作，目標函數(shù)仍采用L1范數(shù)，而在求投影向量時，使用Lp范數(shù)進行約束。其特點為：它通過引入?yún)?shù)p控制投影向量的稀疏性，從而用不同的p值來處理不同的情況，提高識別率和魯棒性。

2 2DPCA與2DPCA-L1

這章簡要介紹了2DPCA和2DPCA-L1這兩種方法。它們都是直接處理圖像數(shù)據(jù)的方法。

2.1 2DPCA方法

2DPCA是圖像矩陣的子空間學習方法。與PCA相比，2DPCA能夠獲取更多的子空間信息，從而有利于圖像的分類或者重建。如果設(shè)列投影向量x∈?n，2DPCA的思想是將m×n的圖像矩陣A通過線性變換Y=Ax投影到x上，從而可以得到圖像 A的特征投影向量Y∈?m×1。設(shè)訓練樣本為 A1，A2，…，AN∈?m×n，其圖像的總體散布矩陣C定義為：

在2DPCA中，需要找到一組最優(yōu)投影矩陣U=[x1，x2，…，xd]∈?n×d，使得準則函數(shù)最大化：

此時，各個圖像矩陣在U上投影后所得特征向量的總體散布的程度最大。最優(yōu)投影向量組 x1，x2，…，xd為C的d個最大特征值所對應的標準正交的特征向量。

2.2 2DPCA-L1

在2DPCA-L1方法中，設(shè)列向量 x∈?n×1為第一個主成分向量。對于N個訓練樣本圖像，Ai∈?m×n，i=1，2，…，N，其對應的特征Yi∈?m為：

其中 Aij∈?1×n為 Ai的第 j行。

2DPCA-L1是在低維特征空間中，找到向量x使得如下函數(shù)取得最大值：

其中 ‖·‖1和 ‖·‖2分別表示 L1 范數(shù)和 L2 范數(shù)。注意到利用這個方法只能得到一個投影向量，為了取得多個投影向量，文獻[8]中的作者利用了貪婪算法。

3 2DPCA-Lp方法

3.1 模型及算法

同樣，設(shè)第 i幅圖像 Ai∈?m×n，其對應的特征向量Bi∈?m×1：

其中，Aij∈?1×n為圖像 Ai的第 j行。

2DPCA-Lp的優(yōu)化問題是在低維特征空間中尋求投影向量x使得下式取得最大值，即

下面，首先給出算法求解式（6）。類似于文獻[8]中的算法，給出算法1來求解式（6）。

算法1 2DPCA-Lp

（1）初始化：選擇任意的 x(0)，令 x(0)←x(0)/‖x(0)‖p，t=0。

（2）極性檢測：對于所有的 i∈{1，2，…，N}，j∈{1，2，…，m}，當 Aijx(t)＜0，pij(t)=-1，否則 pij(t)=1。

（4）收斂檢查：

①如果 x(t)≠x(t-1)，執(zhí)行（2）。

②否則，令x*=x(t)并結(jié)束算法。

為了分析算法，首先介紹了霍爾德不等式[10]。當 p，q∈(1，∞)，且1/p+1/q=1時，在 n 維歐式空間中，對于所有的(x1，x2，…，xn)，(y1，y2，…，yn)∈?n，有如下不等式成立：

等號成立當且僅當|xk|p與|yk|p成比例時成立。

既然該算法是一種迭代方法，下面給出定理1來表明算法1的局部收斂性。

定理1由算法1得到的向量收斂于局部最大值。

證明 首先，由算法1的（2）和（3）得到：

3.2 選取多個關(guān)聯(lián)特征（k＞1）

注意到通過式（6）只能取得一個最佳投影向量x。但是在實際情況下，僅僅利用一個投影向量是不合適的，往往經(jīng)常需要多個投影向量，為了取得多個投影向量，采用類似獻[8]中的貪婪算法，描述如下：

在文獻[8]中，由于在約束集中采用了L2范數(shù)，容易證得取得的xt與xt-1是正交的。而本文的方法采用Lp范數(shù)，所以通常所取得的xt與xt-1并不正交。注意到2DPCA-Lp方法僅僅取得局部最優(yōu)值。很顯然當 p=2時，本文的方法就退化為2DPCA-L1方法。另外，由于采用多次賦給不同初始的值來選取目標函數(shù)的最大值，所以使得該方法取得全局最大值的可能性就較大。

圖1 在ORL數(shù)據(jù)集上性能的比較

4 實驗結(jié)果與分析

4.1 ORL數(shù)據(jù)庫

ORL人臉數(shù)據(jù)庫由40個人、每人10幅，分辨率為112×92的人臉圖像組成，這樣總共400幅圖像。樣本包含著不同姿態(tài)，不同光照和不同面部細節(jié)的人臉圖像。首先測試了2DPCA-Lp，PCA，2DPCA方法在ORL人臉數(shù)據(jù)庫中的性能。對于2DPCA-Lp方法在求訓練樣本的特征時，需要先把訓練樣本中值化。令p={1.1，1.2，…，2.0}，其中當p=2.0時，2DPCA-Lp方法就退化成2DPCA-L1方法[8]。對于每類樣本，隨機選取其中的20%作為訓練集，80%作為測試集進行交叉驗證實驗，提取特征數(shù)量為20至40并采用最小距離分類器進行分類，部分實驗結(jié)果如圖1所示。表1也列出了每種方法的最好性能以及取得最好性能所對應的提取特征數(shù)量。另外，在實驗的圖像上加入了8×8的遮擋塊，從而進一步測試這幾種方法在遮擋情況下的性能，實驗結(jié)果如圖2所示，各種方法的最佳識別率如表1所示。

表1 ORL上的最優(yōu)分類率及對應的提取特征數(shù)量

從圖1可以看出，p=1.2時識別率比其他方法都要高，所以在圖像沒有遮擋的條件下，本文的方法要優(yōu)于其他幾種方法。

圖2 在ORL上加入8×8的遮擋后性能的比較

圖3 在UMIST上性能的比較

從圖2很明顯地看出，當p=1.6時2DPCA-Lp方法取得最佳性能，并且比 PCA，2DPCA，2DPCA-L1（p=2.0）的性能好。

從表1可以看出，當取得最大正確分類率時，p=1.6～2.0等方法對應的提取特征數(shù)量較小，而p=1.1～1.5等方法對應的提取特征數(shù)量較大。這是因為當p較小時，得到的投影向量較稀有，因此需要更多的投影向量來進行識別以達到最大分類率。

遇到異常值的影響時，PCA，2DPCA，以及2DPCA-L1（p=2.0）的最高分類率都下降了，且2DPCA-Lp的下降率要大于其他方法。但是不管參數(shù)p怎樣，2DPCA-Lp方法在性能上仍然高于其他的方法。本文方法的主要優(yōu)點之一是當p取較小的值時，得到的投影可能是稀疏的。在求圖像的特征時，最佳投影向量的稀疏使得圖像中的異常值被濾去，進而使得異常值的影響降低。

4.2 UMIST數(shù)據(jù)庫

在UMIST人臉數(shù)據(jù)庫中繼續(xù)測試提出算法的性能。在UMIST人臉庫中，有20人，總共564幅圖像。實驗的方法與在ORL上的方法相同，部分實驗結(jié)果如圖3所示。

同樣，在UMIST的圖像上也加入8×8的塊遮擋，測試這幾種方法在有遮擋情況下的性能，部分實驗結(jié)果如圖4所示。各種方法的最佳識別率如表2所示。

表2 UMIST上的最優(yōu)分類率及對應的提取特征數(shù)量

圖4 在UMIST上加入8×8的遮擋后性能的比較

從圖3可以看出，在分類性能上PCA算法最差，2DPCA算法優(yōu)于PCA但又劣于2DPCA-L1，同時注意到2DPCA-Lp方法在p=1.3時性能最佳。

從圖4同樣可以發(fā)現(xiàn)2DPCA-Lp（p=1.5）比PCA，2DPCA，2DPCA-L1有更高的識別率和穩(wěn)定性。從表2可以看出在無遮擋時，2DPCA-Lp（p=1.1至1.9）在最高分類率上，與PCA，2DPCA，2DPCA-L1的相比，之差分別為4.42%，4.03%，3.44%。有遮擋時，分別為3.06%，2.58%，1.92%。當無遮擋時p=1.4取得最優(yōu)分類率，當有遮擋時p=1.7取得最優(yōu)分類率。實驗結(jié)果表明通過選擇合適的參數(shù)p，本文方法優(yōu)于其他方法。

5 結(jié)束語

本文首先介紹了PCA和2DPCA，然后提出了2DPCA-Lp。與2DPCA-L1相同的是，它在求最佳投影向量時的目標函數(shù)采用L1范數(shù)。不同的是它采用Lp范數(shù)進行約束，因此2DPCA-Lp是2DPCA-L1的一種推廣，也可以說2DPCA-Lp是2DPCA-L1的一般化。它通過引入?yún)?shù)p對投影向量進行約束，這樣可以選擇合適的參數(shù)p，從而取得最好的分類性能。同時通過實驗，表明2DPCA-Lp又比PCA，2DPCA，2DPCA-L1具有更高的識別率和魯棒性。此外，如果文中算法在其他數(shù)據(jù)庫中的性能不理想又如何進一步改進是今后的工作方向之一。

[1]Jolliffe I T.Principal component analysis[M].New York：Springer-Verlag，1986.

[2]Liu K，Cheng Y Q，Yang J Y，et al.Algebraic feature extraction for image recognition based on an optimal discriminant criterion[J].Pattern Recognition，1993，26（6）：903-911.

[3]楊鍵，楊靜字.具有統(tǒng)計不相關(guān)性的圖像投影鑒別分析及人臉識別[J].計算機研究與發(fā)展，2003，40（3）：447-452.

[4]Yang Jian，Zhang D，Yang Jing-yu.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.

[5]Baccini A，Besse P，F(xiàn)alguerolles A D.A L1-norm PCA and a heuristic approach[C]//Ordinal and Symbolic Data Analysis.Berlin：Springer，1996：359-368.

[6]KeQ，Kanade T.Robust subspace computation using L1 norm[R].Pittsburgh：Carnegie Mellon Univ，2003.

[7]Kwak N.Principal component analysis basedonL1-norm maximization[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30（9）：1672-1680.

[8]Li Xuelong，Pang Yanwei，Yuan Yuan.L1-norm-based 2DPCA[J].IEEE Transactions on Systems，Man，and Cybernetics-Part B：Cybernetics，2009，40（4）：1170-1175.

[9]郭志強，楊杰.雙向壓縮二維特征抽取人臉識別新方法[J].計算機科學，2009，36（11）：296-299.

[10]夏道行，吳卓人，嚴紹宗，等.實變函數(shù)論與泛函分析[M].北京：高等教育出版社，2010.