正交流形保持投影方法

張 偉，夏利民，羅大庸

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

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

1 保局投影LPP

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

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

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

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

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

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

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

(2) LPP不是正交變換。因?yàn)?( XDnXT)-1XLnXT不一定是對(duì)稱(chēng)的，所以，特征向量a1, a2, …, ad不一定正交。

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

2 正交流形保持投影

2.1 流形保持投影

對(duì)于非鄰近點(diǎn)，定義：

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

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

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

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

2.2 正交流形保持投影

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

2.2.1 第1個(gè)正交特征向量a1

2.2.2 第2個(gè)正交特征向量a2

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果

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

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

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

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

圖1 ORL人臉庫(kù)中部分人臉?lè)鶊D像Fig.1 Sample images in ORL database

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

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

圖2 Yale人臉庫(kù)中部分人臉?lè)鶊D像Fig.2 Sample images in Yale database

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

4 結(jié)束語(yǔ)

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

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

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

[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é)報(bào), 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] 李瑞東, 余黨軍, 陳偕雄. 一種新的正交保局投影人臉識(shí)別方法[J]. 科技通報(bào), 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]. 中國(guó)圖像圖形學(xué)報(bào), 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]. 模式識(shí)別與人工智能, 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.