第6卷第1期 智能系统学报 Vol.6 No.1 2011年2月 CAAI Transactions on Intelligent Systems Feb.2011 doi:10.3969/j.issn.16734785.2011.01.008 核方法的对比研究及在步态识别中的应用 贲晛烨，王科俊2，刘海洋1 (1.哈尔滨工业大学交通科学与工程学院，黑龙江哈尔滨150090：2.哈尔滨工程大学自动化学院，黑龙江哈尔滨 150001) 摘要：为了提高步态识别问题的识别性能，将“核技巧”应用到步态识别上，对核二维线性判别分析提出新的解决 方案，在自建的HEU(B)步态数据库上，应用核主成分分析、核线性判别分析、核二维主成分分析与核二维线性判别 分析进行特征提取作对比实验研究.实验结果显示：“核技巧”用于矩阵特征比向量更有效；核二维主成分分析对于 单训练样本较核主成分分析更为有效；核二维线性判别分析在测试识别时间上有优势。 关键词：步态识别：核主成分分析：核线性判别分析：核二维主成分分析：核二维线性判别分析 中图分类号：TP391.41文献标识码：A文章编号：16734785(2011)01-006305 A comparative study on kernel methods and their applications to gait recognition BEN Xianye',WANG Kejun2,LIU Haiyang (1.School of Transportation Science and Engineering,Harbin Institute of Technology,Harbin 150090,China;2.College of Automa- tion,Harbin Engineering University,Harbin 150001,China) Abstract:A kernel trick was applied to gait recognition in order to improve recognition performance.A novel solu- tion was proposed for kerel two dimensional linear discriminant analysis.Feature extraction,which makes use of kernel principal component analysis(KPCA),kernel linear discriminant analysis(KLDA),kernel two dimension- al principal component analysis(K2DPCA),and kernel two dimensional linear discriminant analysis(K2DLDA), was performed for contrasting experiments in HEU(B)'s locally built gait database.The experimental results dem- onstrate that a kemel trick applied to a matrix form is more efficient than in vector form.K2DPCA outperforms KP- CA significantly with a single sample per person,and K2DLDA has the advantage of less time spent on recognition testing. Keywords:gait recognition;kernel principal component analysis (KPCA);kernel linear discriminant analysis (KLDA);kemnel two dimensional principal component analysis(K2DPCA);kernel two dimensional linear dis- criminant analysis (K2DLDA) 在政府部门、军队的涉密场所等，必须严格掌握外广大科研工作者的研究热情 人员进出的情况，大多数时间还需要识别远处活动 步态特征的选择和提取是步态识别工作的重 人员的身份.此时，人脸、虹膜、指纹等生物特征，以 点.步态识别问题从机器视觉的角度来分类大致分 及证件、密码等信息特征不再适用，而步态作为有效 为基于模型23]和非模型46方法.非模型的方法可 的生物特征能够用低分辨率设备从远距离进行身份 以利用统计模式识别方法进行特征提取：主成分分 识别，具有非接触、不唐突的明显优势.步态识别在 析(principal component analysis,PCA)结合线性判 门禁系统、安全监控、人机交互、医疗诊断等领域具 别分析(linear discriminant analysis,LDA)[],核主 有广泛的应用前景和经济价值口，因此激发了国内 成分分析(kernel PCA,KPCA)[],核线性判别分析 (kernel LDA,KLDA)I91,二维主成分分析(wodi- mensional PCA,2DPCA)Io.在人脸识别研究领 收稿日期：2010-0909. 基金项目：国家“863”计划资助项目(2008AA01Z148) 域，二维线性判别分析（two dimensional LDA, 通信作者：贲明烨.E-mail:benxianyeye(@163.corm. 2DLDA)[2I、核二维主成分分析(kernel2DPCA
·64 智能系统学报 第6卷 K2DPCA)B)都取得了较好的识别效果.为了提高 可分的模式在特征空间F中可能变得线性可分 步态识别的识别率，缩短步态识别的耗时，本文将 2.1基于向量的核方法 “核技巧”应用在步态识别问题上，提出了核二维线 样本x,i=1,2,…,M(x:eR"),由空间R映 性判别分析(kernel2DLDA,K2DLDA)作为新的解 射到一个高维空间F:F={(x),i=1,2,…,M} 决方案，4种核方法（包括KPCA、KLDA、K2DPCA、 具有更高的维数.假定映射后的样本向量已被中心 K2DLDA)在自建的有一定俯角的步态数据库(HEU 化，即 (B))上实验，进行步态的特征提取，并与它们相应 Ax)=0, (1) 的线性方法做对比，验证了“核技巧”应用在步态识 别问题上识别性能大大优于其对应的线性方法，而 2.1.1核主成分分析(KPCA) 且K2DLDA在识别时耗时短. KPCA相当于在特征空间F上执行经典的 PCA.在F空间的样本协方差矩阵为 1步态图像预处理 采用文献[14]的步态预处理方法，视频中的单 c=) 帧图像灰度化（如图1(a)),中值法估计的背景图 因此，在F空间上运用PCA,即解方程v=Cy中的 像（如图1(b),背景减除法提取人的侧影（如图1 特征值入和特征向量.根据再生核理论，在F空间 (c)),二值化以及数学形态学处理（如图1(d),居 中，对于任意入≠0对应的是由{中(x:),i=1,2, 中归一到64×64像素大小（如图1(e)),采用侧影 …,M}张成，因而存在系数a,(i=1,2,…,M),有 的宽高比对步态的周期进行分析后，通过对一个步 ,=龙a. 态周期图像的简单加权平均生成步态能量图(gait M energ罗image,GEI)(如图1(f)).对于给定的二值步 ∑a,(x)=C∑a,(x). (2) 态周期图像序列B(x,y),GEI的定义如下： 由于式(2)需要计算中(x:)很麻烦，在这里通 G,）=N名B 过构造内积来回避计算(·)映射问题，即 式中：N是完整步态周期序列的长度；t代表时间；x、 A,)·三a()= y代表二维图像平面横纵坐标。 M )Cga）. (3) 式中：(·)表示内积，k=1,2,…,M. 记一个M×M的核矩阵K中的每一个元素 K=K(xx)=(x)·(),由式(3)得 (a)灰度化 (b)背景重建 Mλa=Ka. 由于(y,)=8g,i,j=1,2,…,n(n≤M),可推导 出特征向量a的正交归一化条件为Mλ(a:,4)= δg,因此可以得出特征向量α的惟一解.于是，对于 (c)背景减除 (d)提取日标人休 任意输入的样本x,可求它在F中的第k个主成分， 即它在特征向量方向上的投影： ye=(k·(x)=】 (()()= (e)标准化 (O GEI M k 图1步态图像预处理 Fig.1 Gait images preprocessing 注意：若式(1)的假设条件不成立，所以前面所述的 K应修正为K,即 2“核技巧”方法 飞g=[(x)-1/M∑(x)]· “核技巧”最早应用于支持向量机(SVM),是通过 M 一个非线性变换中，使输入数据在原始空间R“线性不 [(x)-1/M∑(x)]=
第1期 贲明烨，等：核方法的对比研究及在步态识别中的应用 ·65 K-1VwgK-1wgK+VwAAK 特征值对应的特征向量，P:=q:(i=1,2,…,d)是 式(5)的解， 2.1.2核线性判别分析(KLDA) 对于任意输入的样本A投影到P1卫2，…，Pa,得到 KLDA相当于在特征空间F上执行经典的 Y=D(A)R. LDA,即最优的投影向量w为 2.2.2核二维线性判别分析(K2DLDA) IwCw I WoR arg max 借鉴KLDA方法，定义最优投影矩阵Wp为 ”Iw'Cpw| IWΦS.W 式中：CB为样本在F上的类间散布矩阵；Cg为 Wom arg max wpS WI' 样本在F上的类内散布矩阵， 式中：Sg为样本在F上的类间散布矩阵；Sm为 2.2基于矩阵的核方法 样本在F'上的类内散布矩阵 直接针对图像矩阵运算的线性方法，不能提取 在解决KLDA的小样本问题上，一种较简单的 图像像素间的高阶统计信息，但通过“核技巧”图像 解决策略是在样本上先施加KPCA,使样本数M大 矩阵像素间的高阶相关信息可被获取. 于特征维数，再施加LDA;因此K2DLDA同样采用 2.2.1核二维主成分分析(K2DPCA) 类似的策略，先施加K2DPCA,再在该核空间F'上 考虑M个训练样本图像A:(i=1,2,…,M), 施加二维线性判别分析(2DLDA). A:∈Rmx(前述的样本x:是A:的向量化形式).定 义图像矩阵A,的核映射为 3实验 Φ(A:)=[(A)T…(An)T]T 考虑到视频监控场景的摄像头通常是有一定俯 式中A为A:的第=1,2，…，m)行向量.在特征 角的，我们建立了一个包含20人的数据库 空间F上定义协方差矩阵为 (HEU(B)),每个人3个视角(0°、30°、-45)，每个 ((4)-)r(A) 视角2个序列.在有一定光照和复杂背景下拍摄，共 120个序列.实验条件为：摄像机与人体行走方向相 式中-点4). 对，摆放有一定俯角；区域只有一个目标，无遮挡；监 控范围为15~25m.如图2(a)所示为HEU(B)步态 仍然假定映射后的样本向量已被中心化，即 数据的环境，如图2(b)所示为HEU(B)的步态视频 亚=0，那么 图像. M sΣ∑4)'b(4)鱼D'D, (4) 省 式中：D=[中(A)T…中(A)T中(A)T… (AR)]. 30 -45--C K2DPCA的最优投影轴p使式(5)最大 (a)步态数据的环境 J(p)=trace(p'Sp)=p'p. (5) 式(5)等价于求解方程p=Φp问题.若采用传 统KPCA的分析方法，K2DPCA中的p相当于存在 mM个样本去张成F',即p∈pan{(A),i=1,2, …,M,j=1,2,…,m.这样导致计算量剧增，为了 解决这一问题，张道强等人[)]使用M个样本近似 )步态视频图像 表示核空间： 图2EU(B)步态数据库 =[(A)T(A2)T…(Aw)T]T. Fig.2 HEU(B)gait database 式中：中(A:)为样本A:的m行向量的均值.则式 将步态视频序列经过步态图像预处理的一系列 (5)的等价形式为 操作后，核函数选择为高斯核函数：K(x,y)= 入Kmq=KKq: (6) exp(Ix-y‖2/2σ2)，其中核宽度σ选择为训练样 式中：K。=,K=,Kn∈RxM,KeRa× 本的标准差，将KPCA、KLDA、K2DPCA、K2DLDA等 设R=[q192…qa]∈RMx4为式(6)的前d个最大 “核技巧”方法，应用于步态识别的特征提取阶段. 将每个序列的第1个样本作为训练集，第2个样本
66 智能系统学报 第6卷 作为测试集，识别阶段采用最近邻分类器(NN), 出，核方法(K2DPCA、K2DLDA)的训练时间是线性 在AMD Sempron(tm）Processor2500+ 方法(2DPCA、2DLDA)的30倍左右，而K2DPCA、 1.54GHz,512MB的P℃机环境下实验，表1和表2 K2DLDA、2DPCA和2DLDA4种方法的识别时间基 分别给出基于向量形式的特征提取方法的实验测试 本相当，K2DLDA较2DLDA的测试识别时间有一定 识别率结果和计算时间.表格中“一”表示无数据， 的优势，也是有可取之处的， 因为单视角(0°、30°或-45°)下均为单样本训练情 表3基于矩阵形式的特征提取方法的识别率 况，那么类内的散布矩阵不存在，因此KLDA、LDA Table 3 Recognition rates of feature extraction methods 失效.由表1可以看出：单视角下，KPCA方法的识 based on matrix form 号 别率高于P℃A;当混合视角下的样本一起训练时， 视角 K2DPCA K2DLDA 2DPCA 2DLDA KLDA、LDA等方法生效，除3个视角混合下，应用 0° 80.0 75.0 KLDA方法的识别率略低于LDA方法的识别率，其 30° 90.0 80.0 他核方法的识别率都远远高于它对应的线性方法. -45° 85.0 75.0 由表2可以看出，核方法识别率高，但付出的代价是 0°+30° 87.5 82.5 77.5 85 训练时间增长，大约是线性方法训练时间的4倍；但 0°+(-45°) 87.5 87.5 82.5 90 30°+(-45°) 90.0 90.0 85.0 92.5 是核方法和线性方法的测试时间差异不是很大，核 0°+30°+(-45°) 90.0 90.0 85.0 86.7 方法的测试时间长一些，是因为经KPCA、KLDA降 表4基于矩阵形式的特征提取方法的运算时间 得的维数略高于PCA、LDA方法，而且KPCA、KLDA Table 4 Operation time of feature extraction methods 都要求取测试样本的核函数.基于向量的核方法一 based on matrix form 旦训练好，它的识别性能（包括识别精度、识别耗 算法 训练时间/s 测试识别时间/s 时)大大优于线性方法 K2DPCA 662.460 0.359 表1基于向量形式的特征提取方法的识别率 K2DLDA 954.240 0.265 Table 1 Recognition rates of feature extraction methods 2DPCA 2.140 0.094 based on vector form % 2DLDA 2.469 0.797 视角 KPCA KLDA PCA LDA 总体来说，核方法(KPCA、KLDA、K2DPCA和 0° 75.0 65.0 K2DLDA)主要是由于从低维空间映射到高维空间 30° 85.0 75.0 的核映射耗费了时间.K2DPCA识别率高于KPCA -45° 85.0 55.0 的，这是因为K2DPCA的本质是KPCA以行为单元 0°+30° 77.5 82.5 75.0 80.0 的分段线性化的特殊情况；而且由式(4)可以看出， 0°+(-45°) 87.5 85.0 65.0 82.5 K2DPCA对单样本（单个视角0°、30°或-45°）识别 30°+(-45) 80.0 87.5 75.0 80.0 0°+30°+(-45°) 83.3 81.3 62.5 81.7 时，将样本数扩充到原来的64倍，这样在核空间中 表2 基于向量形式的特征提取方法的运算时间 的图像协方差矩阵较KPCA更准确. Table 2 Operation time of feature extraction methods 4结束语 based on vector form 算法 测试识别时间/a 本文建立一个有一定俯角的小型的包含3个视 训练时间/min KPCA 75.561 2.734 角的步态数据库(HEU(B),并将“核技巧”应用于 KLDA 92.846 2.968 步态识别问题上，核方法(KPCA、K2DPCA、KLDA、 PCA 15.961 1.250 K2DLDA)的识别性能远远优于线性方法(PCA、 LDA 21.915 1.485 LDA、2DPCA、2DLDA).对提出新的解决方案 下面对基于矩阵的核方法进行研究，表3和表 K2DLDA,核方法用于矩阵比向量上更有效， 4分别给出其特征提取方法实验的测试识别率结果 K2DPCA的性能优于KPCA,而且对于单训练样本 和计算时间.由表3可以看出，K2DPCA的识别率高 下的识别问题更为有效，因为K2DPCA对样本数目 于2DPCA;K2DLDA方法的识别率与单独使用 进行了扩充，扩充到原来的行数倍.K2DLDA在小样 K2DPCA和2DLDA相当，这是由于样本数有限，体 本数据库上的识别率与K2DPCA、2DLDA基本相 现不出来K2DLDA方法的优越性，由表4可以看 当，但是在测试识别的时间上有优势，K2DLDA方法
第1期 贲明烨，等：核方法的对比研究及在步态识别中的应用 67… 的优越性有待于通过增加样本做进一步研究： WANG Kejun,BEN Xianye,LIU Lili,et al.Gait recogni- tion using information fusion of energy[J].Joural of Hua- 参考文献： zhong University of Science and Technology:Nature Sei- [1]王科俊，侯本博.步态识别综述[J].中国图象图形学报， ence Edition,2009,37(5):14-17. 2007,12(7):1152-1160. [12]LIANG Zhizheng,LI Youfu,SHI Pengfei.A note on two- WANG Kejun,HOU Benbo.A survey of gait recognition dimensional linear discriminant analysis[J].Pattem Rec- [J].Journal of Image and Graphics,2007,12(7):1152- 0 gnition Letters,2008,29(16):2122-2128. 1160. [13 ]ZHANG Daoqiang,CHEN Songcan,ZHOU Zhihua.Rec- [2]WAGG D K,NIXON M S.On automated model-based ex- ognizing face or object from a single image:linear vs.ker- traction and analysis of gait[C]//Proceedings of the Sixth nel methods on 2D pattems[C]//Proceedings of the Joint IEEE International Conference on Automatic Face and Ges- IAPR International Workshops on Structural and Syntactic ture Recognition.Seoul,Korea,2004:11-16. Pattern Recognition and Statistical Techniques in Pattern [3]RONG Z,CHRISTIAN V,DIMITRIS M.Human gait rec- Recognition.Hong Kong,China,2006:889-897. ognition at sagittal plane[J].Image and Vision Computing, [14]王科俊，贲晛烨，刘丽丽.基于Fan-Beam映射的步态识 2007,25(3):321-330. 别算法[J].哈尔滨工业大学学报，2008,40（增刊1）： [4]LEE S,LIU Y,COLLINS R.Shape variation-based frieze 151-155. pattem for robust gait recognition[C]//Proceedings of IEEE WANG Kejun,BEN Xianye,LIU Lili.Gait recognition Conference on Computer Vision and Pattern Recognition. based on fan-beam projection[J].Joumal of Harbin Insti- Minneapolis,USA,2007:1-8. tute of Technology,2008,40(Supl.1):151-155. [5]LAM T H W,LEE R S T,ZHANG D.Human gait recogni- tion by the fusion of motion and static spatio-temporal tem- 作者简介： plates J].Pattern Recognition,2007,40 (9):2563- 贲原烨，女，1983年生，博士后.主 2573. 要研究方向为智能交通系统、模式识 [6]LU Haiping,PLATANIOTIS K N,VENETSANOPOULOS A 别、生物特征识别.申请国家发明专利5 N.MPCA:multilinear principal component analysis of ten- 项，其中1项已授权.发表学术论文26 sor objects[J].Neural Networks,2008,19(1):18-39. 篇，其中被SCL、EI检索14篇. [7]HUANG P S.Automatic gait recognition via statistical ap- proaches for extended template features[J].IEEE Transac- tions on Systems,Man,and Cybernetics-Part B:Cyber 王科俊，男，1962年生，教授、博士 netics8,2001,31(5):818-823. 生导师、博士，哈尔滨工程大学自动化 [8]WU Jianning,WANG Jue,LIU Li.Feature extraction via 学院副院长，模式识别与智能系统学科 KPCA for classification of gait patterns[J].Human Move- 带头人.主要研究方向为模糊混沌神经 ment Science,2007,26(3）:393-411. 网络、自适应逆控制理论、可拓控制、网 [9]NI Jian,LIANG Libo.A new method based on KFDA and 络智能控制、模式识别、多模态生物特 SVM for gait identification[C]//Interational Workshop on 征识别、联脱机指纹考试身份鉴别系统、微小型机器人系统 Intelligent Systems and Applications(ISA 2009).Wuhan, 等.完成科研项目20余项，目前在研项目10余项.曾获得部 China,2009:1-3. 级科技进步二等奖2项、三等奖3项，省高校科学技术一等 [10]王科俊，贲明烨.基于广义主成分分析的步态识别算法 奖1项、二等奖1项.发表学术论文180余篇，出版学术专著 研究[J].哈尔滨工程大学学报，2009,30(9)：28-34. 3部、国防教材1部，主审教材2部. WANG Kejun,BEN Xianye.Research on gait recognition 刘海洋，男，1986年生，硕士研究 based on generalized principal component analysis[J]. 生，主要研究方向为智能交通系统： Journal of Harbin Engineering University,2009,30(9): 28-34. [11]王科俊，贲睨烨，刘丽丽，等.基于能量的信息融合步态 识别[J].华中科技大学学报：自然科学版，2009,37 (5):14-17
