正交流形保持投影方法

張 偉，夏利民，羅大庸

(中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410075)

特征提取是模式識別領(lǐng)域中一個重要的研究方向，人們已經(jīng)提出了很多特征提取方法，其中最經(jīng)典的一種就是主分量分析(PCA)[1]。它是尋找使均方誤差最小的線性最優(yōu)變換矩陣，并且最優(yōu)矩陣由樣本方差的最大特征向量(叫做主分量)組成。PCA的目標(biāo)是盡可能地保留樣本的方差信息。但用PCA進(jìn)行特征降維時，經(jīng)常無法保留數(shù)據(jù)中的非線性結(jié)構(gòu)，而這些非線性特性對于物體的識別是非常重要的。最近，提出了一種新的特征提取方法，即保局投影(LPP)[2-3]，它具有較強(qiáng)的流形學(xué)習(xí)能力，當(dāng)數(shù)據(jù)存在非線性結(jié)構(gòu)時，該方法能很好地保留圖像的非線性特征。LPP的目標(biāo)是盡可能地保留數(shù)據(jù)的局部流形結(jié)構(gòu)，它通過使近鄰樣本之間的歐幾里德距離最小來尋找最優(yōu)投影方向。然而，LPP存在一些缺陷：非正交變換；沒有利用數(shù)據(jù)非近鄰信息，因此，在投影過程不一定能保持?jǐn)?shù)據(jù)全局流形結(jié)構(gòu)。針對這些問題，人們已提出了一些改進(jìn)的算法[4-14]，如Yang等[4]提出了非局保留投影(NLPP)，尋找使非近鄰樣本的歐幾里德距離最大的最優(yōu)投影方向，這種方法有效地利用了數(shù)據(jù)的非近鄰信息，但只適合非近鄰特性起主導(dǎo)作用的情況；韋佳等[5]利用全局信息、局部信息正、負(fù)約束信息提出了基于局部與全局保持的半監(jiān)督維數(shù)約減方法。Cai等[6]在特征值求解過程中增加了正交約束，提出了正交局部保持投影方法(OLPP)，但該方法計算相當(dāng)復(fù)雜。李瑞東等[7-8]利用Schur分解，提出了基于Schur分解的正交鑒別局部保持投影方法。Zhu等[9]利用投影基向量變換，提出了正交局部保持投影方法。本文作者針對LPP的缺陷，提出一種正交流形結(jié)構(gòu)保持投影方法(OMPP)，在 LPP目標(biāo)函數(shù)中引入非近鄰信息，與保局投影相比，改進(jìn)后的方法能更好地保持?jǐn)?shù)據(jù)的局部流形結(jié)構(gòu)和全局結(jié)構(gòu)；采用格拉姆-施密特正交化過程(Gram-Schmidt orthogonalization)[14]獲得正交投影向量，解決了保局投影非正交問題。在ORL和Yale人臉數(shù)據(jù)庫上進(jìn)行實驗，實驗結(jié)果驗證了該算法的有效性。

1 保局投影LPP

LPP算法本質(zhì)上是一種線性降維方法，根據(jù)最近鄰圖來建立映射，設(shè)在高維歐式空間 Rn中有數(shù)據(jù)集X={x1, x2, …, xN}，尋求一個投影矩陣A，將這些數(shù)據(jù)映射到一個相對低維的特征空間 Rd(d≤n)中。數(shù)據(jù)集在Rd中的表述為Y={y1, y2, …, yN}，且Y=ATX。

LPP算法的目的是在特征降維的同時，保持樣本固有的局部流形結(jié)構(gòu)不變。LPP的準(zhǔn)則函數(shù)為：

在下列約束條件下，使目標(biāo)函數(shù)J1最小的A就為LPP的投影矩陣A：

可證明，目標(biāo)函數(shù)J1極小化問題就是下面的廣義特征值求解問題：

即方程(2)前 d個最小的特征值對應(yīng)的特征向量 a1,a2, …, ad組成矩陣A。

很顯然，經(jīng)過保局投影，高維空間距離很近的 2個點的低維投影點之間的距離也應(yīng)該很近，即保局投影能有效地保持樣本固有的局部流形結(jié)構(gòu)不變。但是LPP存在下列問題：

(1) LPP不能保證在投影過程中保持?jǐn)?shù)據(jù)全局流形結(jié)構(gòu)，因為沒用考慮數(shù)據(jù)非近鄰信息。

(2) LPP不是正交變換。因為 ( XDnXT)-1XLnXT不一定是對稱的，所以，特征向量a1, a2, …, ad不一定正交。

為了有利于數(shù)據(jù)的分類，希望數(shù)據(jù)集經(jīng)過投影后，高維空間相鄰的點在低維空間也接近，而非鄰近點在低維空間應(yīng)該盡量散開；同時，希望消除數(shù)據(jù)各分量之間的相關(guān)性，因此，要求投影變換是正交投影。而這些是保局投影無法保證的。為此，作者提出了改進(jìn)的保局投影，即正交流形保持投影。

2 正交流形保持投影

2.1 流形保持投影

對于非鄰近點，定義：

要使非鄰近點的低維投影能夠盡量散開，則要求下列目標(biāo)函數(shù)應(yīng)最大：

要使投影后鄰近點的低維投影點很近，當(dāng)非鄰近點的低維投影點離得很遠(yuǎn)時，應(yīng)保持?jǐn)?shù)據(jù)的局部流形結(jié)構(gòu)和全局結(jié)構(gòu)不變，則要求目標(biāo)函數(shù)J最小。這種投影稱為流形保持投影。

若XLfXT是非奇異的，則求目標(biāo)函數(shù)最小的問題轉(zhuǎn)化為求下列廣義特征值問題：

方程(6)前 d個最小的特征值對應(yīng)的特征向量 a1,a2, …, ad組成投影矩陣A=(a1, a2, …, ad)。

2.2 正交流形保持投影

由于a1, a2, …, ad為非正交向量，下面利用格拉姆-施密特正交化過程求方程(6)前 d個最小的特征值對應(yīng)的正交特征向量a1, a2, …, ad。

2.2.1 第1個正交特征向量a1

2.2.2 第2個正交特征向量a2

由于特征矢量a2滿足=0和S-1Sa=λa，fn因此，a2必定在與第1個特征向量a1垂直的(n-1)維子空間Sn-1上，所以，應(yīng)該在Sn-1上尋找=λa最小特征值對應(yīng)的特征向量作為a2。

將矩陣Sn，Sf轉(zhuǎn)化成Sn-1空間的矩陣：

2.2.3 第i個正交特征矢量ai(i =3, 4, …，d)

將矩陣Sn和Sf轉(zhuǎn)化成空間的矩陣：

即特征向量a1, a2, …, ad是正交的。因此，A是正交投影矩陣，投影變換Y=ATX是正交投影。

3 實驗與結(jié)果

為說明本文作者方法的有效性，在ORL和Yale 2種人臉數(shù)據(jù)庫上進(jìn)行實驗，并與PCA，LPP，NLPP和OLPP等方法進(jìn)行比較。

實驗1在ORL標(biāo)準(zhǔn)人臉庫上進(jìn)行，此人臉庫由40人、每人10幅圖像組成，圖像有112×92個像素。這些圖像拍攝于不同時期，圖像的特點是：(1) 表情不一，如：憤怒、 厭惡、 恐懼、高興、平靜、 悲傷、驚訝、眼睛睜與閉；(2) 臉部姿態(tài)不一，人臉深度旋轉(zhuǎn)和平面旋轉(zhuǎn)可達(dá)20°；(3) 佩戴物不一，如戴眼鏡與不戴眼鏡；(4) 人臉的尺度變化多達(dá)10%。圖1所示是ORL人臉庫中部分人臉圖像。實驗中，以每個人的前5幅圖像作為訓(xùn)練樣本，后5幅作為測試樣本，訓(xùn)練樣本和測試樣本總數(shù)均為200。

首先對圖像進(jìn)行預(yù)處理，將圖像剪輯、歸一成為64×64像素。然后分別采用PCA，LPP，NLPP和OLPP及文中方法(OMPP)提取人臉特征；最后，用余弦距離來衡量樣本之間的相似程度，采用最近鄰分類器進(jìn)行人臉識別。表1給出了這幾種方法的最高識別率及對應(yīng)特征維數(shù)。

實驗2在Yale人臉庫上進(jìn)行。此人臉庫由15人、每人11幅圖像組成，圖像像素為100×100。這些圖像是在不同表情和光照條件下拍攝的。圖 2所示是Yale人臉庫中部分人臉圖像。實驗中，以每人的前6幅圖像作為訓(xùn)練樣本，后5幅作為測試樣本，訓(xùn)練樣本數(shù)為66，測試樣本數(shù)為55。首先將圖像剪輯、歸一成為64×64像素。表2所示是PCA，LPP，NLPP，OLPP和OMPP方法加余弦距離下的最近鄰分類器的最高識別率及對應(yīng)特征維數(shù)。

圖1 ORL人臉庫中部分人臉幅圖像Fig.1 Sample images in ORL database

表1 在ORL人臉庫上5種方法的識別結(jié)果Table1 Recognition results of five methods on ORL database

以上實驗結(jié)果表明：OMPP方法的識別率與其他幾種方法相比有明顯提高，并且OMPP方法減少了表情、姿態(tài)、光照等因素對人臉識別的影響。其中PCA識別率最低，這是由于人臉圖像存在大量的非線性結(jié)構(gòu)，而這些非線性結(jié)構(gòu)對于人臉識別十分重要。當(dāng)使用PCA變換時，這些非線性結(jié)構(gòu)經(jīng)常無法保留，導(dǎo)致識別降低；LPP只考慮了數(shù)據(jù)的近鄰信息，不能保持?jǐn)?shù)據(jù)的全局流形結(jié)構(gòu)，當(dāng)使用LPP降維時，對于比較相似的人臉就可能難以分開；而NLPP只考慮了數(shù)據(jù)的非近鄰信息，沒有考慮近鄰信息，因此，對于同一個人，當(dāng)其表情、姿態(tài)或者光照發(fā)生較大變化時，采用NLPP很可能出現(xiàn)誤識；OLPP利用了局部與全局信息，因此，識別率得到提高。作者提出的OMPP方法由于同時考慮了數(shù)據(jù)的近鄰信息和非近鄰信息，有效地保持了數(shù)據(jù)的局部流形結(jié)構(gòu)和全局流形結(jié)構(gòu)，使得識別率有了明顯提高；同時，由于所得到的基向量具有正交性，消除了數(shù)據(jù)各分量之間的相關(guān)性，使得特征維數(shù)有了明顯減少。

圖2 Yale人臉庫中部分人臉幅圖像Fig.2 Sample images in Yale database

表2 在Yale人臉庫上5種方法的識別結(jié)果Table2 Recognition results of five methods on ORL database

4 結(jié)束語

(1) 保局投影是一種非常有效的特征提取方法，針對LPP存在的缺陷，本文作者提出了正交流形保持投影方法。

(2) 在保局投影目標(biāo)函數(shù)中引入數(shù)據(jù)的非近鄰信息，有效地保持了數(shù)據(jù)的局部流形結(jié)構(gòu)和全局流形結(jié)構(gòu)；采用格拉姆-施密特正交化過程獲取正交投影基向量，解決了保局投影非正交問題。

(3) 在ORL和Yale人臉數(shù)據(jù)庫上進(jìn)行實驗，實驗結(jié)果驗證了該方法的有效性。

[1] Turk M, Pentland A P. Eigenfaces for recognition[J]. Journal of Cognitive Neuroscience, 1991, 3(1): 71-86.

[2] He X F, Niyogi P. Locality preserving projections[C]//Proceedings of 17th Annual Conference on Neural Information Processing Systems. Cambridge: MIT Press, 2003: 585-591.

[3] He X F, Yan S C, Hu Y X, et al. Face recognition using laplacianfaces[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(3): 328-340.

[4] YANG Jian, ZHANG David, YANG Jing-yu. Non-locality preserving projection and its application to palmprint recognition[C]// Proceedings of 9th International Conference on Control, Automation, Robotics and Vision. Piscataway: IEEE,2006: 1-4.

[5] 韋佳, 彭宏. 基于局部與全局保持的半監(jiān)督雄數(shù)約減方法[J].軟件學(xué)報, 2008, 19(11): 2833-2842.

WEI Jia, PENG Hong. Local and global preserving based semisupervised dimemsionality reduction[J]. Journal of Software,2008, 19(11): 2833-2842.

[6] Cai D, He F X, Han J W, et al. Orthogonal laplacianfaces for face recognition[J]. IEEE Transactions Image Process, 2006,15(11): 3608-3614.

[7] 李瑞東, 余黨軍, 陳偕雄. 一種新的正交保局投影人臉識別方法[J]. 科技通報, 2007, 23(5): 702-704.

LI Rui-dong, YU Dang-jun, CHEN Xie-xiong. A new alternative formulation of orthogonal LPP with application to face recognition[J]. Bulletin of Science and Technology, 2007, 23(5):702-704.

[8] 林宇生, 鄭宇杰, 楊靜宇. 一種基于Schur分解的正交鑒別局部保持投影方法[J]. 中國圖像圖形學(xué)報, 2009, 14(4):701-706.

LIN Yu-sheng, ZHENG Yu-jie, YANG Jing-yu. An orthogonal discriminant locality preserve projections with schur decomposition[J]. Journal of Image and Graphics, 2009, 14(4):701-706.

[9] Zhu L, Zhu S A. Face recognition based on orthogonal discriminant locality preserving projections[J]. Nurocomputing,2007, 70(7/9): 1543-1546.

[10] Shao J D, Gang R, Jong M L. Generalized orthogonal locality preserving projections for nonlinear fault detection and diagnosis[J]. Chemometrics and Intelligent Laboratory Systems,2009, 96(1): 75-83.

[11] 肖永良, 夏利民. 基于改進(jìn)的保局投影視頻特征提取[J]. 模式識別與人工智能, 2010, 23(3): 396-401.

XIAO Yong-liang, XIA Li-min. Video feature extraction based on improved locality preserving projections[J]. Pattern Recognition and Artificial Intelligence, 2010, 23(3): 396-401.

[12] He X F, Yan S C, Hu Y X, et al. Learning a locality preserving subspace for visual recognition[C]// Proceedings of 9th International Conference on Computer Vision. Los Alamitos:IEEE Comput Soc, 2003: 385-392.

[13] CHENG Jian, LIU Qing-shan, LU Han-qing, et al. Supervised kernel locality preserving projections for face recognition[J].Nurocomputing, 2005, 67(8): 443-449.

[14] Liu K, Cheng Y Q, Yang J Y. A generalized optimal set of discriminant vectors[J]. Pattern Recognition, 1992, 25(1):731-739.