LDA算法及其在人脸识别中的应用

Computer Engineering andApplications计算机 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 与应用 20 1 0，46(1 9) 1 89 LDA算法及其在人脸识别中的应用 谢永林 XIE Yong—lin 宁波大红鹰学院 软件学院，浙江 宁波 315000 College of Software，Ningbo Dahongying University，Ningbo，Zhejiang 3 1 5000，China E—mail：michealx@sina．com XIE Yong-fin．LDA algorithm and its application to face recognition．Computer Engineering and Applications，2010，46 (19)：189。192． Abstract：Linear Discriminant Analysis(LDA)is a linear feature extracting method using Fisher’S criterion in face recogni— tion．The main challenge of LDA is that its transformation matrix can not be computed directly；consequently，the discriminant vectors become very complicated，for the cases when the number of training samples is less than the dimensionality of the feature space．In this paper，a new LDA method is proposed using a modified Fisher’S criterion．Experiments are conducted US— ing ORL face database to present the superior performance of the proposed method，particularly for the cases when the ntlm- ber of training samples is smal1． Key words：human face recognition；linear feature extraction；Linear Discriminant Analysis(LDA) 摘 要：线性特征提取在人脸识别中的应用非常广泛，LDA是其主要方法之一，它基 于Fishers0别准则，然而，当人脸训练样本数 小于人脸样本向量的维数时，变换矩阵将无法直接得到，因此线性判别分析过程失效。采用 了一种改进的基 于Fisher准则的 LDA方法，针对小样本问题提 出了一种有效地解决类内散布矩阵奇异的方法，而且用ORL人脸数据进行了实验验证。实验证明 该方法在正确识别率方面 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 现突出。 关键词：人脸识别；线性特征提取；线性判别分析(LDA) DOI：10．3778~．issn．1002—8331．2010．19．055 文章编号：1002—833l(2010)19 0189 04 文献标识码：A 巾图分类号：TP391．4l 1 引言 人脸识别近些年已成为计算机视觉和模式识别等领域中 的热门课题，它有着广阔的应用前景，特征提取是人脸识别的 一 个重要过程 ，是人脸识别中的核心步骤，是人脸识别技术的 关键。人脸特征提取的方法不同，识别率、机器的存储量、机 器的运算时间等也不同，也就是说特征提取在人脸识别系统 中占据很重要的位置。不同识别方法有着对应不同特征提取 的策略。主要介绍基于Fisher判别分析的LDA方法。它可以 大幅降低原来模式空间的维数，使投影后样本向量类间散布 最大和类内散布最小 ，然而 ，当人脸的样本数小于人脸样本向 量的维数时，这时类内散布矩阵是奇异的，变换矩阵不能直接 得到，因此线性判别分析过程失效 ，采用了一种改进的基于 Fisher准则的LDA方法来解决这个问题，针对小样本问题，该 方法很好地解决了类内散布矩阵奇异的问题，而且实验证明 该方法在正确识别率方面表现较好。 值的向量作为最佳投影方向，从而使得样本在该方向上投影 后，达到最大的类间离散度和最小的类内离散度u 。 可以考虑把d维空间的样本投影到一条直线上，形成一维 空间，即把维数压缩到一维。这在数学上总是容易办到的。 然而 ，即使样本在 d维空间里形成若干紧凑的相互分得开的集 群，若把他们投影到一条任意的直线上，也可能使几类样本混 在一起而变得无法识别。但在一般情况下，总可以找到某个 方向，使在这个方向的直线上，样本的投影能分开得最好，问题 是如何根据实际情况找到这条最好的、最易于分类的投影线。 这就是Fisher线．『生判别法所要解决的基本问题(见图1) 。 2 Fisher线性判别分析的基本原理 关于线性判别分析的研究应追溯到Fisher在1936年发表 。 的经典论文。其基本思想是选择使得Fisher准则函数达到极 作者简介：谢永林(1979．)，男，讲师，主要研究方向：模式识别。 收稿日期：2009．02—26 修回日期：2009—04．16 图1 Fisher线性判别的基本原理 Computer Engineering andApplications计算机工程与应用 首先 ，讨论从d维空问到一维空间的一般数学变换方 法。假设有一集合 包含Ⅳ个 维样本x ， ，⋯，XN其中Ⅳ1 个属于∞ 类的样本记为子集而，Ⅳ2个属于∞：类的样本记为 。 若对 的分量作线性组合可得标量 Y =¨ ' X ，n=1，2，⋯，Ⅳ (1) 这样便得到Ⅳ个一维样本Y 组成的集合，并可分为两个子 集 和 ：。从几何上看，如 l Il=1，则每个 是相对应 到 方向为"'的直线上的投影。实际上，w的绝对值是无关紧要 的，它仅使Y¨乘上一个比例因子，重要的是选择 的方向。 的 方向不同，将使样本投影后的可分离程度不同，从而直接影响 识别效果。因此，前述所谓寻找最好投影方向的问题，在数学 上就是寻找最好的变换 的问题。 在定义Fisher判别准则之前，先定义几个必要的基本参量。 2．1 在d维 空间 (1)各类样本均值向量J，l m = 1∑ ，f=1，2 (2) ’ij ∈ (2)样本类内离散度矩阵 总类内离散矩阵 ’∑(X--m (X--ttt ) ， 1，2 (3) · ’ · s SI+s2 (4 (3)样本类间离散度矩阵 ～ ：)( 一埘：) (5) 其中 ，是对称半正定矩阵，而且当Ⅳ>d时通常是非奇异的。 也是对称半正定矩阵，在两类条件下，它的秩最大等于l。 2．2 在一维y空间 (1)各类样本均值n3． 历 ∑Y’f_1，2 (6) 一 iY ∈ (2)样本类内离散度 和总类内离散度 宴 =∑( 一廊 ) ， 1，2 (7) + (8) 现在来定义Fisher准则函数。希望投影后，在一维y空间 里各类样本尽可能分得开些，即希望两类均值埔l-rh，越大越 好；同时希望各类样本内部尽量密集。即希望类内离散度越 小越好。因此，可以定义Fisher判别准则为 ： )= (9) 显然应该寻找使 (，-，)的分子尽可能大，而分母尽可能 小，也就是使 (H，值尽可能大的 作为投影方向。但是式(9) 的 (，．，)并不是显含 ，因此必须设法将 ( )变成 的显函 数。由式(6)可推出 疏 专善 专 ． voTx =WT (1O) 这样式(9)的分子便成为： (廊1一廊2) 1一WTJ，l2 (肌1一 2)(肌1一In2) W=W S6 (11) 现在再来考察 f¨，)的分母与 ，¨的关系： = Z(y—m ) =∑ ( —w m ) = w f∑( — ，)( —m )Tl~V=wTs ，．， (12) j 因此 + = T( 1+ 2 w=wTS w 可得： ( )= WTS bw 下面求使 )取最大值时的 。 (’．，)是广义Rayleigh 商，可以用Lagrange乘子法求得： S6¨， =2S (13) 其中H， 就是 (’．，)的极值解。因为S 非奇异，式(13)两边左乘 S -1 ，可得 ： Sw-1SbW =2W (14) 解式(14)为求一般矩阵 -1Sb的特征值问题，通过计算可以 得到： w =手 -1( 一J，l：) (15) 忽略比例因子RI2，得： w = (J，l 一J，l2) (16) 僦是使Fisher~lJ}lJ准则函数 (’．，)取极大值时的解，也就是d 维空间到一维y空间的最好投影方向，有了 ，就可以把d维样 本 投影到一维，这实际上是多维空间到一维空间的一种映 射。这样，就将 维分类问题转化为一维分类问题了。只要再 确定一个阈值，便可做出识别决策。 ，当然也很容易把这种方 法推广到多维情况。这就是Fisher线性判别的原理。 3 LDA算法人脸识别系统的应用 利用MATLAB语言实现了基于LDA算法的人脸识别系 统，其基本过程包括：导入系统训练样本集和测试样本集、 Fisher最优判别向量的计算、将测试样本与各类训练样本投影 到特征子空间，以及分类识别。 3．1 导入系统训练样本集和测试样本集 实验采用的是英国剑桥大学Olivetti研究所制作的ORL (Olivetti Research Laboratory)人脸数据库。该数据库包括 4O个不同人、每人l0幅图像，一共400幅。每幅原始图像256 个灰度级，分辨率为 112x92。ORL人脸图像是在不同时间、 不同视角、各种表情(闭眼／睁眼、微笑／吃惊／生气／愤怒／高兴) 和不同脸部细节(戴眼镜／没戴眼镜、有胡子／没胡子、不同发 型)的条件下拍摄的。数据库中部分人脸图像如图2所示。 冒 圈 冒 圈 一 一 or1002 or1003 or1004 orlOll or1012 ■ 一 ■ 一 一 ■ 图2 ORL人脸数据库中部分人脸图像 为了提高运算速度、降低图像维数，采用了19x15的分辨 率。向系统中导入图像数据时，每类训练样本个数可以自行 设定为1～1O个，而测试样本则可以随机指定。 谢永林：LDA算法及其在人脸识别中的应用 2010，46(19) l91 3．2 Fisher最优判别向量的计算 首先根据导入的训练样本数据分别计算它的总体散布矩 阵 、类内散布矩阵S 类问散布矩阵S。和类平均矩阵S 。假 设w ，W：，⋯，W 是 个已知类别集合， ={Xi}， 1，2，⋯，Ⅳ是 维 训 练 样 本 集 合 ，每 个 样 本 _属 于 一 个 类 w，，即 ∈ w ，， 1，2，⋯，Ⅳ， =1，2，⋯，m,w 的先验概率为P(w )，则 P(wf) } ⋯ S =∑p(w )(埘 一 。)(删 -mo) (18) = + =E{( —m。)( — 。) } (19) 其中， 为任一训练样本 ，m 为所有训练样本平均向量 ， m。=E{ }。然后再根据Fisher判别准则公式，计算最优判别 向量： Fisher判别准则公式： ) (20) 改进的Fisher判别准则 ： (21) 讨论公式(21)：假设R是n维空间集合，Vx∈R，f(x1 0， g(x)>-0，f(x)+g( )>0， ( )=f(x)lg(x)，h2( )=_厂( )／ (f(x)+g( ))，如果向 ( )在 ( )有最大值，那么 ( )在 。 也有最大值；而且在求解最优分类向量过程中Fisher判别函 数可以被式(21)代替，还有如果 是一个非奇异的正矩阵，假 设hx=0，则x'Ax=0，因此 假 设S，是 一个 奇 异 矩阵 ， (o)={xlS，x=O， }， (o)为 (o)的互补空间，则最优 分类向量妒可以通过公式(21)计算出来。 (1)计算第一个判别向量妒。 根据 max{ ( 。)} l∈ (o) 【22) ll：1 Ngd~gzNNs． (0)：{St ∈ }，假设 是矩阵 (0)的维 数，则 (1)当 =n，则 就等于矩阵 S 的最大特征值对应的单 位特征向量。 (2)当1< 。< ，则假设： (0)= an{ 1， 2，⋯， }，其中 ， 2，⋯ ， 为正交 单位 向量 ，那么 = + ：+⋯+ ． ． = Plz ，其中， P1 ( ， 2，．．．， ) (23) z =( ， ⋯．， ) (24) 舳 麟 煳 恫 艟 。 (2)计算第f个判别向量 ， fI矍设： (0) Span{a1，口2，⋯，an-n} (25) t 其 中 ，a ，a ，⋯，n 是 正 交 单 位 向 量 ，假 设 是 被 span{~1，p2，⋯，妒f_】}分割的子空间， =span{~l， 2，⋯ 『_】，Ⅱl， 口2，⋯ ，an - n }，而且向量妒1， 2，⋯， 和口l，口2，⋯， 都已经 ] ~i n n, 被计算出来 ，根据代数原理 ，可以构造 出 的互补空间 ， =span{ ， ：，⋯， ⋯}，其中 ， z，⋯，I-i+1是正交单位 矩阵。很显然，求最优判别向量问题与以下公式求最大值问 题是等效的。 ( )=max{ ( )} ∈ (26) If=1 其中， 是 中的一个单位向量，对于V ∈ ， 都可以被表示 成以下公式： 。_ + ∥2+⋯+ 。． +1 ．一 + (27) 假设 = P ，z (28) 其 中，Pi=( ， ：⋯．， ，z∞=( ， ，⋯， ． 一 + )若 fz“ 以I-i+1) = z(i)~fs e z(~／lle z(~ll： = z(OTpT S p Z(i) ( 。)=max{~(Z )} (30) 容易证明P P 是正定义矩阵，因此，P ，P 是非奇异 的，假设 是矩阵 ： 最大特征值对应的特征向量，则第 ” P S P 行·判别向量 舶计算公式如下： 3-3 将测试样本与各类训练样本投影到特征子空间 通 过 以 上 计 算 得 到 最 优 判 别 向 量 空 间 ， = ( ， ，⋯ ，)，其中r= 一1，则任一测试样本投影到特征子 空间的向量为Y= ，每类训练样本平均向量投影到特征子 空间的向量为J' = m 。 3．4 分类识别 采用欧氏距离进行分类 ，计算测试人脸的投影特征与各 类平均人脸投影特征的欧氏距离，将测试人脸样本判为与类 平均人脸的投影特征欧氏距离最小的类所对应的类别。 4 实验结果分析 为了对改进的LDA算法在人脸识别系统的正确识别率 作分析，用MATLAB语言实现了基于PCA(Principal Compo． nent Analysis)算法的人脸识别系统，而且改进的LDA人脸识 别系统和PCA人脸识别系统的训练样本和测试样本都采用了 ORL人脸数据库，该数据库包括了40个不同的人，每个人有 192 2010，46(19) ComputerEngineeringandApplications计算机工程与应用 10幅不同的正面图像，一共有400幅人脸图像。在实验过程 中，针对系统的训练过程，PCA与改进的LDA人脸识别系统 分别从每个人中随机抽取5、6、7、8、9个样本做训练，并对这5 种训练的结果做人脸识别的测试，其中基于改进的LDA算法 的识别系统得到的正确识别率如表1所示。 表1 改进的LDA算法识别率 训练样本 5 6 7 8 9 LDA方法 89．5 92 95 96 97．5 而且从图3、4可以了解到 ： (1)当系统训练样本数从5到9逐步增大的时候，LDA人 脸识别系统的正确识别率也是逐步增大的，这说明在设计人 脸识别系统时，训练样本数越大系统的正确识别率就越好，即 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 训练样本的数量要大于每个样本空间的维数。但这一点 在实际应用时很难做到。 (2)在系统训练样本数相等的情况下，基于LDA算法的 人脸识别系统的正确识别率要比基于PCA算法的人脸识别系 统的正确识别率要高。因为虽然使用PCA方法和LDA方法 都能大大降低原始特征空间的维数，然而，PCA方法得到的特 征是最佳描述特征而不是最佳分类特征，所以在正确识别率 方面LDA方法要比PCA方法优越，但LDA方法则存在类内 散布矩阵总为奇异阵而使求解变得很困难等缺点。 5 结论 对近年来模式识别领域中线性特征提取的主要方法，即 LDA方法进行了较为深入的讨论。对它所基于的Fisher判别 准则做了详细的介绍，介绍了一种改进的LDA算法，对该方 法的有效性，用ORL人脸数据进行了实验验证。结果表明，该 方法基本可行，文中完成的系统也具有较高的识别率，但仍然 摹 锝 磊 O0 98 96 94 92 90 88 86 84 10O 95 龉 9O 85 8O 6 7 8 9 样本数 LDA方法的正确识别率 5 6 7 8 9 样本数／个 图4 PCA与LDA的实验结果比较图 需要进一步完善。 参考文献： ⋯1 边肇祺，张学工．模式识别[M】．2版．北京：清华大学出版社，2007： 87—91．223．226． [2]Sirovich L，Kirby M．Low—demensional procedure for character- ization of human faces[J]．Journal of the Optical Society of America，1987，4(3)：519—524． 【3]Belhumeur P N，Hespanha J P，Kriegman D J．Eigenfaces vs．fish— erfaces：Recognition using class specific linear projection[J]． IEEE Transactions on Pattern Analysis and Machine Intelli— gence，1997，19(7)：711-720． [4】张宇萍．基于Fisher准则的二次线性特征提取[J]．西安工业大学学 报，2007，27(5)：460—463． (上接 169页) [3]3 曹欧 ，孙晓鹏，薛钢，等．三角形Bezier网上的插值曲面[J】．鞍山钢铁 学院学报，2000(8)：206—210． [4】冯裕强，雷保珍 ，王爱玲．三角网格上Bezier曲面光滑构造研究[J】． 山西机械，2000(6)：19—21． [5】张于浩．空间结构的自由曲面插值技术[J]．深圳土木与建筑，2007 (9)：25—29． 【6]罗玉堂，姜昱明．法向量约束下的蝶形细分曲面方法[J]．微电子学 与计算机 ，2006(6)：156—159． (7】Lin Hong-Wei，Tai Chiew-Lan，Wang Guo-Jin．A mesh reconslruction algorithm driven by an intrinsic property of a point cloud[J]． Computer-Aided Design，2004：1—9． [8】Kumar G S，Kaim P K，Dhande S G．Curve and surface recon- struction from points：an approach based on self-organizing maps[J]．Applied Soft Computing．2004：55—66． [9]Yoon M，Lee Yunjin，Lee Seungyong．Surface and normal ensem- bles for surface reconstruction[J]．Computer-Aided Design，2007： 408 420． (上接172页) [4]Liu Chaochtm，Dai Daoqing，Yah Hong．Local discriminant wave— let packet coordinates for face recongnicition[J]．Learning Re- search，2007，8：1165—1l95． [5]Watson A B，Yang G Y，Solomon J A．Visibility of wavelet quan— tization noise[J]．IEEE Transactions on Image Processing，1997，6 (8)：1164。1175． [6】张旭，张贵仓．一种基于小波包分解的自适应水印算法[J]．计算机 辅助设计与图形图像学报 ，2007，19(7)：931．934． [7]张翼，陈丽萍，唐向宏．基于小波变换和奇异值分解的图像水印算 法[J1．杭州电子科技大学学报，2007，27(2)：37．40．