張鵬，付希凱，葛國棟，賁晛燁

山東大學 信息科學與工程學院，山東 濟南 250100

二維線性大間距判別分析及其在步態(tài)識別中的應用

張鵬，付希凱，葛國棟，賁晛燁

山東大學 信息科學與工程學院，山東 濟南 250100

提出一種二維線性大間距判別分析（Two dimensional linear maximum margin discriminant analysis,2DLMMDA）的投影算法。該算法一方面采用了有效且穩(wěn)定的大間距優(yōu)化準則，引入了Laplacian矩陣，保持了特征矩陣的流形結構，且優(yōu)化域為Laplacian類間散度與Laplacian類內散度之差，能克服Fisher準則帶來的小樣本問題；另一方面，采用了具有監(jiān)督信息的判別分析，大大地提高了識別率。為了驗證所提出的算法對特征提取的有效性，選擇最近鄰分類器進行特征分類，最后通過在CASIA(B)步態(tài)庫上實驗。實驗結果表明，文中提出的算法具有更高的識別率和識別速度。

特征提??；二維線性大間距判別分析；拉普拉斯矩陣；步態(tài)識別

在計算機視覺和模式識別領域，降維技術一直是眾多研究者熱衷的焦點[1]。數據的高維性給數據處理帶來了很大的難度，對硬件設備有很高的要求[2]。自一個多世紀前K. Pearson提出主成分分析（principle component analysis，PCA）[3]方法后，幾十年來數據采集和存儲能力得到快速提高，大數據處理漸漸走向日常應用，行之有效的特征提取技術也越來越迫切。近幾十年來，經典的降維技術，例如PCA、獨立成分分析（independent component analysis，ICA）[4-5]、線性判別分析（linear discriminant analysis，LDA）[6]受到了嚴重的挑戰(zhàn)，已經不能繼續(xù)滿足日常應用中對大數據處理的有效性和可靠性要求。在這種嚴峻的形勢下，研究者對于2D數據進一步研究，為了保持二維數據的完整性，提高執(zhí)行效率和準確率，Yang 首先提出了直接處理二維矩陣的方法替代經典算法中將矩陣轉化為一維向量來處理圖像矩陣的方法。繼二維主成分分析(Two dimensional principle component analysis，2DPCA)[7]之后相繼提出了二維線性獨立判別分析（Two dimensional linear discriminant analysis, 2DLDA）[8-9]、二維局部保留投影（Two dimensional locality preserving projects，2DLPP）[10]以及二維大間距算法[11]等算法，大大提高了運算的效率。

研究表明，PCA是一種無監(jiān)督的降維技術[3]。2DPCA對PCA進行了改進，將二維圖像矩陣直接進行投影，而不是把二維矩陣先初始化為向量，大大提高了識別的準確率，然而二者都是無監(jiān)督方式，分類可靠性還有很大的局限性。而2DLDA算法用樣本的標號信息作為監(jiān)督矩陣指導降維，取得了更好的分類效果。然而2DLDA采用Fisher判別準則最大化類間散度和類內散度之商，需要計算類內散布矩陣的逆，而小樣本將導致奇異的類內散度矩陣，因此2DLDA帶來了小樣本問題（small sample size, SSS）[12]。

近幾年來，LPP[13]用于降維備受研究者親睞，它是一種基于流形假設提出的流形學習方法的線性算法[14]，通過保持數據的局部性的Laplacian矩陣來實現(xiàn)降維，在步態(tài)識別領域取得了不錯的效果。類似PCA改進到2DPCA的過程，2DLPP被提出，對圖像矩陣直接投影，而不是將其轉化成向量。2DLPP保留了LPP的優(yōu)點，不僅能解決奇異矩陣導致的小樣本問題，并且不需要PCA進行預處理，保留了二維圖像數據的結構信息，獲得了更好的識別率。2DLPP可以解決一般性的特征值問題，但也帶來了一系列的問題。首先，2DLPP涉及到相似矩陣，相同的相似矩陣值與LPP內部流形結構矛盾，且高維訓練樣本處理起來非常麻煩，容易造成維數災難，對物理設備有更高的要求；其次，需要引入大量的系數用于圖像處理和識別，稀系數的優(yōu)化選取有很大的難度。

步態(tài)識別具有易采集、不易偽裝、采集設備要求低等優(yōu)點，是最具有潛力的生物特征之一[15]。隨著生物特征識別技術的迅速發(fā)展，對步態(tài)識別的研究出現(xiàn)了很多成果[16]。步態(tài)能量圖[17]是近年來提出的一種有效的步態(tài)識別方法，它受輪廓噪聲影響小，結合空間降維技術[18]可有效地提取步態(tài)能量特征。

鑒于2DLDA解決分類問題的有效性，文中提出了一種二維線性大間距判別分析的特征提取算法。該算法不僅引入了Laplacian矩陣，保持了數據之間的流形結構，而且優(yōu)化類間散度與類內散度之差，克服了小樣本問題。同時，它采用判別分析，可以獲得更高的識別性能。通過在中科院CASIA（B）步態(tài)庫上實驗，實驗結果證明本文的方法魯棒性強，具有更高的識別率和識別速度。

1 二維線性大間距判別分析

設矩陣x表示一幅大小為m×n的圖像，U表示一個大小為m×m′( m′≤m)的行投影矩陣，y為提取的特征矩陣，圖像x經過線性變換投影得到：

因此，圖像大小由原來的m×n，變?yōu)閙′×n，實現(xiàn)了降維的目的，其中最佳投影矩陣U可以根據特征矩陣y的Laplacian散度情況來確定，表示如下

式中：LΨb表示類間Laplacian散度矩陣；LΨw表示類內Laplacian散度矩陣；LΨt表示總體Laplacian散度矩陣；tr(?)表示表達式的跡，式（2）取得最大值的物理意義是：找到一個最佳的投影矩陣U，使得投影后所得特征向量的列間Laplacian類間距最大化。在特征空間中，上述間距越大，就代表不同類中的樣本距離間隔越遠，而同類中的樣本間距就會越近。即優(yōu)化目標式（3）最大

相應地，令yi表示特征xi投影后的特征矩陣，則特征提取后構成的矩陣為

為了保持步態(tài)圖像的內在非線性流形結構，在散度矩陣中引入Laplacian矩陣的高斯相似性[19]：

圖像集X的總體Laplacian散度定義如下：

對投影矩陣強加正交性約束，則最優(yōu)U通過求解如下的優(yōu)化問題獲得：

通過（10）、（13）兩式得到基于Laplacian矩陣的二維線性大間距判別分析是將大小為m×n目標圖像矩陣xi同時在投影矩陣Um×m′和Vm′×n上進行投影，得到一個m×n的矩陣zi，如式（14）所示。

2 分類識別

給定一個測試圖像xtest,由式（16）可得該測試圖像的特征矩陣ztest

文中采用最近鄰分類器驗證所提出算法的特征提取的有效性，通過計算訓練樣本和測試樣本特征值之間的歐氏距離進行分類，如式（18）：

式中d(ztest,zi)為測試圖像的特征值矩陣與訓練樣本集中各樣本的特征矩陣之間的歐氏距離。當測試樣本與樣本庫中的某一個樣本之間有最小的歐氏距離時，則認為該測試樣本與步態(tài)樣本庫中的相應樣本匹配。如果該測試樣本與樣本庫中相應的樣本屬于同一類，則認為是匹配正確的，否則，認為該測試樣本與樣本庫中相應步態(tài)樣本是匹配錯誤的。

3 實驗結果

CASIA（B）步態(tài)庫是中國科學院自動化研究所于2005年1月建立的一個步態(tài)輪廓數據庫，它是一個多視角的步態(tài)庫，在幀頻25幀/s攝像機下獲得。庫中共包括124個人，每個人有3種行走條件（其中正常行走拍攝6次、背包情況下拍攝2次、穿著外套拍攝2次），每個人在3種條件下都按照11個視角（0?，18?，36?，…，180?）進行采集。

為了驗證2DLMMDA算法的識別效果，將2DLMMDA方法在CASIA(B)步態(tài)庫90?視角上的步態(tài)下進行了測試。PC機的配置為Intel(R) Core(TM)2 Duo CPU T5870 @2.00GHz，2.00GB內存的PC機上進行實驗。在正常行走狀態(tài)下，對每個樣本分別提取步態(tài)能量圖特征，大小歸一為64×64像素，如圖1所示為CASIA(B)庫中3個研究對象的步態(tài)序列能量圖。

圖1 CASIA（B）庫中提取的3個人的步態(tài)序列能量

圖2 不同特征維數下的識別率變化

在實驗中，首先從提取的步態(tài)序列庫中對每個人隨機選取3個樣本用于訓練，剩下的3個樣本用于測試算法的識別率和識別效率，為了保證算法的準確性，重復做10次實驗，取識別率和識別時間的平均值作為最終結果，為了驗證保留維數與識別率的關系，在圖2中給出了保留不同維數下的識別率曲線，并在表1中給出了2DLMMDA算法與其他方法在最高識別率、識別時間以及相應的保留維數的對比情況。

實驗結果表明，2DPCA，MMC這2種方法有較快的識別速度，但是識別率相對較低。這是由于2DPCA沒有引入監(jiān)督信息；而MMC雖然引入了監(jiān)督信息，但是優(yōu)化的是具有近鄰流形結構的Laplacian散度差，而且僅為單邊投影；2DLDA、2DLPP這2種方法雖然提高了識別率，但是也大大增加了計算負擔，這是由于它們直接對大數據進行處理，優(yōu)化Fisher域；而文中提出的2DLMMDA算法正好均衡了識別的有效性和魯棒性，在盡量少的識別時間內，取得更高的識別率。由圖2可知，在相同的特征維數的前提下，2DLMMDA總能取得最高的識別率，由表1可知，文中提出的2DLMMDA算法最高識別率96.51%，總的時間僅為18.63 s。

表1 2DLMMDA算法在CASIA（B）步態(tài)庫實驗結果及其與其他方法對比

4 結束語

文中提出了一種二維線性大間距判別分析的特征提取算法。該算法一方面在計算散度矩陣時引入了Laplacian矩陣，保持了數據間的流形結構，另一方面不再是優(yōu)化Fisher域，而是優(yōu)化類間Laplacian散度與類內Laplacian散度之差，克服了優(yōu)化Fisher域帶來的小樣本問題。同時，該算法還引入了帶有監(jiān)督信息的判別方法，大大地提高了識別率。通過與同類方法相比，文中的算法在不明顯增加識別時間消耗的基礎上，取得了最高的識別率。但是，步態(tài)能量圖結合二維線性大間距判別分析并沒有考慮各幀之間的關系，而步態(tài)序列各幀卻具有嚴格的時間順序。隨著多線性技術的發(fā)展，今后的工作是將步態(tài)序列在更高維空間中進行特征提取，將運用多線性技術將各幀之間的關系考慮進來，勢必會得到更好的識別效果。

致謝

感謝中科院自動化所為我們提供的CASIA(B)步態(tài)數據庫。

[1] CARREIRA-PERPINAN M A. A review of dimension reduction techniques[R]. Sheffield: University of Sheffield Tech. Rep CS-96-09, 1997: 1-69.

[2] FODOR I K. A survey of dimension reduction techniques[R]. Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, 2002: 1-18.

[3] ABDI H, WILLIAMS L J. Principal component analysis[J]. Wiley Interdisciplinary Reviews: Computational Statistics, 2010, 2(4): 433-459.

[4] HYV?RINEN A. Survey on independent component analysis[J]. Neural Computing Surveys, 1999, 2: 94-128.

[5] HYVARINEN A, KARHUNEN J, OJA E. Independent component analysis[J]. Studies in Informatics and Control, 2002, 11(2): 205-207.

[6] BELHUMEUR P N, HESPANHA J P, KRIENGMAN D J. Eigenfaces vs. Fisherfaces: recognition using class specific linear projection[J]. IEEE Trans Pattern anal Mach Intell, 1997(7): 711-720.

[7] YANG J, ZHANG D, FRANGI A F. Two-dimensional PCA: a new approach to appearance based face representation and recognition[J]. IEEE Trans Pattern anal Mach Intell, 2004, 26(1): 131-137.

[8] LI M, YUAN B Z. 2D-LDA: a statistical linear discriminant analysis for image matrix[J]. Pattern Recognition Letters, 2005, 26(5): 527-532.

[9] LI J, JANARDAN R, LI Q. Two-dimensional linear discriminant analysis[J]. Advances in Neural Information Processing Systems, 2004, 17: 1569-1576.

[10] CHEN S, ZHAO H, KONG M. 2DLPP: a two-dimensional of locality preserving projections[J]. Neuro Computing, 2007, 70(4/5/6): 912-921.

[11] LI H F, JIANG T, ZHANG K S. Efficient and robust feature extraction by maximum margin criterion[J]. IEEE Transactions on Neural Networks, 2006, 17(1): 157-165.

[12] RAUDYS S J, JAIN A K. Small sample size effects in statistical pattern recognition: recommendations for practitioners[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(3): 252-264.

[13] HE X F, NIYOGI P. Locality preserving projections[C]// Proceedings of the 16thConference on Neural Information Processing Systems. Cambridge, USA: MIT Press, 2003: 153-160.

[14] HE X F, YAN S C, NIYOGI P, et al. Face recognition using Laplacian faces[J]. IEEE Transaction on Pattern Analysis and Machine Intelligence, 2005, 27(3): 328-340.

[15] 賁晛燁，徐森，王科俊.基于Trace變換的步態(tài)識別算法研究[J]. 吉林大學學報: 工學版, 2012, 42(1): 156-160.

[16] 賁晛燁, 徐森, 王科俊. 行人步態(tài)的特征表達及識別綜述[J]. 模式識別與人工智能, 2012, 25(1): 71-81.

[17] HAN J, BHANU B. Individual recognition using gait energy image[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(2): 316-322.

[18] BEN Xianye, MENG Weixiao, WANG Ze, et al. Two linear subpattern dimensionality reduction algorithms[J]. Journal of Harbin Institute of Technology: New series, 2012, 19(5):47-53. [19] BELKIN M, NIYOGI P. Laplacian eigenmaps for dimensionality reduction and data representation[J]. Neural Computation, 2003, 15(6): 1373-1396.

[20] 詹宇斌, 殷建平, 劉新旺. 基于大間距準則和圖像矩陣雙向投影的人臉特征提取方法[J]. 自動化學報, 2010, 36(12): 1645-1654.

2D linear maximum margin discriminant analysis and its application to gait recognition

ZHANG Peng, FU Xikai, GE Guodong, BEN Xianye

School of Information Science and Engineering, Shandong University, Ji’nan 250100, China

In this paper, a novel projection algorithm named 2D linear maximum margin discriminant analysis is proposed. The efficient and stationary maximum margin optimization criterion was used in this algorithm, which introduces Laplacian matrix in order to maintain the manifold structure of the feature matrix, and the optimization criterion is the difference of the Laplacian inter-class scatter and Laplacian intra-class scatter. This algorithm can avoid the small sample size (SSS) problem brought by the Fisher criterion. The discriminant analysis is adopted, which has supervision information and greatly improves the recognition accuracy. In order to verify the efficiency of the proposed method for feature extraction, experiment with the nearest neighborhood (NN) classifier on the CASIA(B) database is conducted. The results show that the proposed method gains a higher recognition rate and faster speed.

feature extraction; two dimensional linear maximum margin discriminant analysis; Laplacian matrix; gait recognition

TP391.4

A

1009-671X（2014）01-0011-05

10.3969/j.issn.1009-671X.201306002

2013-06-03.

國家自然科學基金資助項目（61201370）；高等學校博士學科點專項科研基金資助項目(20120131120030）；中國博士后科學基金面上資助項目（2013M530321）；山東大學自主創(chuàng)新基金資助項目（2012GN043，2012DX007）.

張鵬（1990-）, 男, 碩士研究生;賁晛燁（1983-）, 女, 講師, 碩士生導師, 博士.

賁晛燁, E-mail: benxianyeye@163.com.