李 勇，梁志貞，夏士雄

LI Yong,LIANG Zhizhen,XIA Shixiong

中國礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州 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ǔ)上進(jìn)行鑒別分析的新方法[2]；2003年Yang改進(jìn)了Liu的方法[3]，得到一種具有統(tǒng)計(jì)不相關(guān)性的圖像投影鑒別分析方法；2004年Yang等人[4]將文獻(xiàn)[3]的方法用于圖像重構(gòu)，取得了很好的效果。

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

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

2 2DPCA與2DPCA-L1

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

2.1 2DPCA方法

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

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

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

2.2 2DPCA-L1

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

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

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

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

3 2DPCA-Lp方法

3.1 模型及算法

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

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

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

下面，首先給出算法求解式（6）。類似于文獻(xiàn)[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}，當(dāng) Aijx(t)＜0，pij(t)=-1，否則 pij(t)=1。

（4）收斂檢查：

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

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

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

等號成立當(dāng)且僅當(dāng)|xk|p與|yk|p成比例時成立。

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 在UMIST上性能的比較

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

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

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

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

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

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

表2 UMIST上的最優(yōu)分類率及對應(yīng)的提取特征數(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%。當(dāng)無遮擋時p=1.4取得最優(yōu)分類率，當(dāng)有遮擋時p=1.7取得最優(yōu)分類率。實(shí)驗(yàn)結(jié)果表明通過選擇合適的參數(shù)p，本文方法優(yōu)于其他方法。

5 結(jié)束語

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

[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)計(jì)不相關(guān)性的圖像投影鑒別分析及人臉識別[J].計(jì)算機(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]郭志強(qiáng)，楊杰.雙向壓縮二維特征抽取人臉識別新方法[J].計(jì)算機(jī)科學(xué)，2009，36（11）：296-299.

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