第3卷第1期 智能系统学报 Vol.3№1 2008年2月 CAAI Transactions on Intelligent Systems Fcb.2008 基于C均值K近邻算法的面部表情识别 张一鸣，欧宗瑛，王虹 (大连理工大学机械工程学院，辽宁大连116023) 摘要：随着人工智能与模式识别技术的不断发展，面部表情识别在智能人机交互中发挥着越来越重要的作用.通 过对人的面部表情分类的研究，提出了一种使用C均值聚类、K近邻算法的面部表情分类方法.对参加训练的表情 图像先进行Gabor小波变换，然后使用Fisherface判别分析方法进行变换，求得特征空间.再将已进行Gabor变换的 标准表情图像投影到特征空间，进行C均值聚类得到子类表情模板.对于一幅待识别的表情图像，使用K近邻算法 与子类表情模板比较，将该表情图像分类.使用该方法，在公开的日本女人表情人脸库上实测达到了95.8%的识 别率. 关键词：面部表情识别；C均值聚类，K近邻；Gabor小波；Fisherface判别分析 中图分类号：TP391.41文献标识码：A文章编号：16734785(2008)01-005下05 Facial expression recognition based on G means and Knearest neighbor algorithms ZHANG Yi-ming,OU Zong-ying,WANG Hong (School of Mechanical Engineering,Dalian University of Technology,Dalian 116023,China) Abstract:With the rapid development of artificial intelligence and pattern recognition,facial expression rec- ognition plays an important role in intelligent humanmachine interaction.In this paper,a facial expression classification method is presented which uses a Gmeans and K-nearest neighbor algorithm as the basis of a- nalysis for the classification of facial expressions.First the images to be analyzed are transformed with Ga- bor wavelets,and then Fisherface discriminate analysis is performed to generate a feature space.Next,the images which were transformed with Gabor wavelets are projected into the feature space and Gmeans clus- tering performed on the projected images to generate subrexpression templates.Finally,the type of ex- pression is identified by comparing the input expression images with the sub-expression templates by using a K-nearest neighbor algorithm.Experiments on the public Japanese female facial expression database show that the method proposed in this paper can achieve a 95.8%recognition rate. Keywords facial expression recognition:Gmeans clustering;K-nearest neighbor:Gabor wavelet;fisher- face discriminant analysis 人的面部表情（高兴、厌恶、愤怒、惊讶等）是表 学者对表情识别的方法进行了研究.1978年Ekman 达人的情绪的主要方法，是人的内心世界的外在表 和Friesen开发了面部运动编码系统(facial action 现形式.表情属于肢体语言，它和自然语言一起传达 coding system),用以描述面部表情和人类的认知 信息，因此面部表情的识别作为生物特征识别中的 行为，被认为是表情识别与分析的里程碑.后来又出 一种，是人机交互中不可缺少的一部分」 现了光流(optic flow)法)、基于主成分分析法 鉴于表情识别的重要性与复杂性，国内外很多 (principal component analysis)5,、局部加权的 二维主成分分析算法(partially weighted two-di- 收稿日期：2007-02-10. 基金项目：大连理工大学与中科院沈阳自动化研究所联合探索基金 mensional,PCA)ll、线性判别分析(linear discrimi-- 资助项目(DU下SLA2006). nant analysis)lo、Gabor小波的方法r]、独立成份 通讯作者：欧宗瑛.上mail:ouzyg@dlut.edu.cn 分析7，别、局部特征分析o1、神经网络23]等多种方 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
第 3 卷第 1 期 智 能 系 统 学 报 Vol. 3 №. 1 2008 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2008 基于 C 均值 K 近邻算法的面部表情识别 张一鸣 ,欧宗瑛 ,王 虹 (大连理工大学 机械工程学院 ,辽宁 大连 116023) 摘 要 :随着人工智能与模式识别技术的不断发展 ,面部表情识别在智能人机交互中发挥着越来越重要的作用. 通 过对人的面部表情分类的研究 ,提出了一种使用 C 均值聚类、K近邻算法的面部表情分类方法. 对参加训练的表情 图像先进行 Gabor 小波变换 ,然后使用 Fisherface 判别分析方法进行变换 ,求得特征空间. 再将已进行 Gabor 变换的 标准表情图像投影到特征空间 ,进行 C 均值聚类得到子类表情模板. 对于一幅待识别的表情图像 ,使用 K近邻算法 与子类表情模板比较 ,将该表情图像分类. 使用该方法 ,在公开的日本女人表情人脸库上实测达到了 9518 %的识 别率. 关键词 :面部表情识别 ;C 均值聚类 ; K近邻 ; Gabor 小波 ; Fisherface 判别分析 中图分类号 : TP391141 文献标识码 :A 文章编号 :167324785 (2008) 0120057205 Facial expression recognition based on C2means and K2nearest neighbor algorithms ZHAN G Yi2ming , OU Zong2ying , WAN G Hong (School of Mechanical Engineering , Dalian University of Technology ,Dalian 116023 ,China) Abstract :Wit h t he rapid development of artificial intelligence and pattern recognition , facial expression rec2 ognition plays an important role in intelligent human2machine interaction. In this paper , a facial expression classification method is p resented which uses a C2means and K2nearest neighbor algorit hm as t he basis of a2 nalysis for the classification of facial expressions. First t he images to be analyzed are transformed with Ga2 bor wavelets , and t hen Fisherface discriminate analysis is performed to generate a feature space. Next , t he images which were transformed wit h Gabor wavelets are projected into t he feat ure space and C2means clus2 tering performed on t he p rojected images to generate sub2expression templates. Finally , t he type of ex2 pression is identified by comparing t he inp ut expression images with t he sub2expression templates by using a K2nearest neighbor algorit hm. Experiments on the p ublic J apanese female facial expression database show that t he method proposed in t his paper can achieve a 95. 8 % recognition rate. Keywords :facial expression recognition ; C2means clustering ; K2nearest neighbor ; Gabor wavelet ; fisher2 face discriminant analysis 收稿日期 :2007202210. 基金项目 :大连理工大学与中科院沈阳自动化研究所联合探索基金 资助项目(DU T2SIA 2006) . 通讯作者 :欧宗瑛. E2mail :ouzyg @dlut . edu. cn. 人的面部表情(高兴、厌恶、愤怒、惊讶等) 是表 达人的情绪的主要方法 ,是人的内心世界的外在表 现形式. 表情属于肢体语言 ,它和自然语言一起传达 信息 ,因此面部表情的识别作为生物特征识别中的 一种 ,是人机交互中不可缺少的一部分. 鉴于表情识别的重要性与复杂性 ,国内外很多 学者对表情识别的方法进行了研究. 1978 年 Ekman 和 Friesen [1 ]开发了面部运动编码系统(facial action coding system) ,用以描述面部表情和人类的认知 行为 ,被认为是表情识别与分析的里程碑. 后来又出 现了光流 (optic flow) 法[223 ] 、基于主成分分析法 (principal component analysis) [425 ,11 ] 、局部加权的 二维主成分分析算法 (partially weighted two2di2 mensional ,PCA) [6 ] 、线性判别分析 (linear discrimi2 nant analysis) [ 6 ] 、Gabor 小波的方法[729 ] 、独立成份 分析[7 ,9 ] 、局部特征分析[10 ] 、神经网络[12213 ]等多种方 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·58 智能系统学报 第3卷 法.综合考虑了以上算法，文中采用了Gabor小波 变换和Fisherface判别分析的方法进行特征提取，采 用了C均值聚类对标准的表情图像进行聚类，得到子 类表情模板.对待识别的表情图像使用了K近邻判 别方法进行了分类，该方法考虑到同一种表情可能有 很多种不同的表现形式，比如高兴，有的人是张开嘴 大笑，有的人是闭着嘴微笑，这就表明高兴这类表情 155d 还可以继续划分成多个子类，如果使用聚类的方法， 就可以使每种表情聚成更多的子类，这样，所得到的 表情模板才能更精确地代表该种表情的一种表现形 式.使用K近邻算法将待识别的图像与各个聚类中 0.8d 0.8d 心的表情模板进行比较，从而判别出该种表情与哪些 表情的哪些表现形式更加接近，进而将该种表情进行 图1面部表情图像的剪切比例示意图 分类.文中通过对公开的日本女人表情图像数据库 Fig I Schematic of cut proportion on UAFFE)的测试表明，与其他方法相比，使用了C均 expression image 值聚类与K近邻算法使识别率得到提高 对图像进行各种分析.二维Gabor小波变换描述了 图像1(W上给定一点x=(x,以附近区域的灰度特 1表情分类算法 征，这可以用一个卷积来定义！： 文中所使用的表情分类方法分为以下几个步 f(x)w(x-x)dx' (1) 骤：首先对表情图像进行几何与灰度预处理.几何预 Gabor核函数的定义为 处理是先找到图像中人眼的位置，经过旋转将两眼 调整到同一水平位置.再将该图像按照一定的比例 华( 0 exp 20 剪切下来，假设人两眼间的距离为d,剪切比例如图 1所示.为排除人相貌对表情识别的影响，所以将人 exp(ikjx)- exp 2 的额头与脸的外轮廓剪切掉.人表情的变化主要表 式中： 现在眉毛、眼睛和嘴角的变化上，图示的剪切方法能 krcos蚓 很好地保留表情的变化的表现，同时削减了部分相 k k=2π， kr sin中u 貌差异对表情的影响.最后将剪切下来的图像放缩 .0=2元 到统一大小，文中使用100×128像素大小的图像. 8 (3) 对于灰度预处理，文中使用了直方图均衡化，使图像 文中使用了5个频率，8个方向的Gabor核函 的对比度大大提高，灰度分布也趋于均匀.对图像进 数，即v=0,1,4,μ=1,2,8.对图像中的一个 行预处理之后，使用Gabor小波提取图像的频率特 点进行Gabor滤波，便得到40个Gabor系数.文中 征，然后使用Fisherface判别分析对图像进行训练， 对预处理后的图像使用网格结构均匀取点，每隔20 求得特征空间.文中使用模板匹配的方法分类表情， 个像素点取一个点（共30个点）进行Gabor滤波 表情模板是通过在特征空间对一些标准的表情图像 得到长度为1200 Gabor系数的向量J.即经过该滤 进行动态C均值聚类，将聚类中心作为表情模板而 波之后，将大小为128×100的灰度图像变换为 得到的.对于待识别的图像使用了K近邻算法，该算 1200维Gabor向量. 法与C均值聚类一起使用，达到了很好的识别效果. l.2 Fisherface判别分析 1.1表情图像的二维Gabor小波变换 灰度图像经过二维的Gabor小波变换得到了 文中使用Gabor小波来编码人脸图像.二维 Gabor向量，接下来使用主成分分析(PCA)与线性 Gabor滤波器是带通滤波器，在空间域和频率域均 判别分析(LDA)相结合的方法，即Fisherface法对 有较好的分辨能力，它在空间域有良好的方向选择 Gabor向量进行训练，得到投影空间.该方法先将 性，在频率域有良好的频率选择性.Gabor小波变换 Gabor向量通过PCA提取主成分信息并降维，然后 是具有最好的时-频局部化描述能力的窗函数.二 对降维后的图像应用LDA训练一个最佳分类器」 维Gabor小波变换是图像的多尺度表示和分析的 Fisherface方法既保留了原始向量的主成分信息， 有力工具，作为唯一能够取得空域和频域联合不确 又克服了直接使用LDA带来的大矩阵和类内散布 定关系下限的Gabor函数经常被用作小波基函数， 矩阵奇异的问题，且该方法的识别率比只使用PCA 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
法. 综合考虑了以上算法 ,文中采用了 Gabor 小波 变换和 Fisherface 判别分析的方法进行特征提取 ,采 用了 C均值聚类对标准的表情图像进行聚类 ,得到子 类表情模板. 对待识别的表情图像使用了 K近邻判 别方法进行了分类.该方法考虑到同一种表情可能有 很多种不同的表现形式 ,比如高兴 ,有的人是张开嘴 大笑 ,有的人是闭着嘴微笑 ,这就表明高兴这类表情 还可以继续划分成多个子类 ,如果使用聚类的方法 , 就可以使每种表情聚成更多的子类 ,这样 ,所得到的 表情模板才能更精确地代表该种表情的一种表现形 式.使用 K近邻算法将待识别的图像与各个聚类中 心的表情模板进行比较 ,从而判别出该种表情与哪些 表情的哪些表现形式更加接近 ,进而将该种表情进行 分类. 文中通过对公开的日本女人表情图像数据库 (JAFFE)的测试表明 ,与其他方法相比 ,使用了 C 均 值聚类与 K近邻算法使识别率得到提高. 1 表情分类算法 文中所使用的表情分类方法分为以下几个步 骤 :首先对表情图像进行几何与灰度预处理. 几何预 处理是先找到图像中人眼的位置 ,经过旋转将两眼 调整到同一水平位置. 再将该图像按照一定的比例 剪切下来 ,假设人两眼间的距离为 d ,剪切比例如图 1 所示. 为排除人相貌对表情识别的影响 ,所以将人 的额头与脸的外轮廓剪切掉. 人表情的变化主要表 现在眉毛、眼睛和嘴角的变化上 ,图示的剪切方法能 很好地保留表情的变化的表现 ,同时削减了部分相 貌差异对表情的影响. 最后将剪切下来的图像放缩 到统一大小 ,文中使用 100 ×128 像素大小的图像. 对于灰度预处理 ,文中使用了直方图均衡化 ,使图像 的对比度大大提高 ,灰度分布也趋于均匀. 对图像进 行预处理之后 ,使用 Gabor 小波提取图像的频率特 征 ,然后使用 Fisherface 判别分析对图像进行训练 , 求得特征空间. 文中使用模板匹配的方法分类表情 , 表情模板是通过在特征空间对一些标准的表情图像 进行动态 C 均值聚类 ,将聚类中心作为表情模板而 得到的. 对于待识别的图像使用了 K近邻算法 ,该算 法与 C均值聚类一起使用 ,达到了很好的识别效果. 111 表情图像的二维 Gabor 小波变换 文中使用 Gabor 小波来编码人脸图像. 二维 Gabor 滤波器是带通滤波器 ,在空间域和频率域均 有较好的分辨能力 ,它在空间域有良好的方向选择 性 ,在频率域有良好的频率选择性. Gabor 小波变换 是具有最好的时 - 频局部化描述能力的窗函数. 二 维 Gabor 小波变换是图像的多尺度表示和分析的 有力工具 ,作为唯一能够取得空域和频域联合不确 定关系下限的 Gabor 函数经常被用作小波基函数 , 图 1 面部表情图像的剪切比例示意图 Fig11 Schematic of cut proportion on expression image 对图像进行各种分析. 二维 Gabor 小波变换描述了 图像 I ( x) 上给定一点 x = ( x , y) 附近区域的灰度特 征 ,这可以用一个卷积来定义[13 ] : J j ( x) =∫I ( x′)Ψj ( x - x′) d 2 x′. (1) Gabor 核函数的定义为 Ψj ( x) = ‖kj ‖2 σ2 exp ‖kj ‖2 ‖x ‖2 2σ2 · exp ( ik j x) - exp - σ2 2 . (2) 式中 : kj = kjx kjy = kv cosφμ kv sinφμ , kv = 2 - v+2 2π, φμ = μ π 8 ,σ = 2π. (3) 文中使用了 5 个频率 ,8 个方向的 Gabor 核函 数 ,即 v = 0 ,1 , …,4 ,μ= 1 ,2 , …,8. 对图像中的一个 点进行 Gabor 滤波 ,便得到 40 个 Gabor 系数. 文中 对预处理后的图像使用网格结构均匀取点 ,每隔 20 个像素点取一个点 (共 30 个点) 进行 Gabor 滤波 , 得到长度为 1 200 Gabor 系数的向量 J . 即经过该滤 波之后 ,将大小为 128 ×100 的灰度图像变换为 1 200维 Gabor 向量. 112 Fisherface 判别分析 灰度图像经过二维的 Gabor 小波变换得到了 Gabor 向量 ,接下来使用主成分分析 (PCA) 与线性 判别分析(LDA) 相结合的方法 ,即 Fisherface 法对 Gabor 向量进行训练 ,得到投影空间. 该方法先将 Gabor 向量通过 PCA 提取主成分信息并降维 ,然后 对降维后的图像应用 LDA 训练一个最佳分类器. Fisherface 方法既保留了原始向量的主成分信息 , 又克服了直接使用 LDA 带来的大矩阵和类内散布 矩阵奇异的问题 ,且该方法的识别率比只使用 PCA · 85 · 智 能 系 统 学 报 第 3 卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第1期 张一鸣，等：基于C均值K近邻算法的面部表情识别 ·59· 的方法高 很多种表现方式，因此很难只使用一个表情模板来 对于已经过Gabor小波变换的表情图像训练 代表一种表情，也就是说每种表情还应再划分成多 集X,先将图像集进行分类，将同一种表情的图像归 个子类.聚类是在样本类别未知的情况下进行的无 为一类，记为X.文中要识别7种表情，所以i=1, 监督的学习方法.通过聚类分析，可以把相似的样本 2,,7.Fisherface的计算过程如下 聚成一类，不相似的样本分别聚在不同的类里.文中 首先，计算每一类的类内平均表情图像m,和 对表情模板使用了动态C均值聚类方法，将每种表 所有训练图像的总体平均表情图像m.然后，将每个 情聚成多个子表情类，取每类的质心作为标准的表 类内的表情图像减去自己类内的平均表情图像，得 情模板.C均值聚类算法过程如下： 到每个表情的差值表情：最后每一个类内平均表情 首先，确定聚类的类数C并选择C个代表点作 图像减去总体平均表情图像」 为最初的质心然后计算代表点之外的所有点到各 x∈X,X∈X, 个代表点的距离，按照最近邻的原则，将这些点进行 父=X-m,h:=m-m. 分类.至此完成第1次迭代.接下来再分别计算各个 再创建一个数据矩阵，即把所有中心化后的表 类的质心，然后计算所有点到各个质心的距离，按照 情图像按次序排列成一个表情数据矩阵.接下来求 最近邻法将所有点再一次进行分类.反复迭代，直到 解表情数据矩阵的正交向量：可以通过奇异值分解 算法收敛或达到预定义的最大迭代次数为止.该过 或者求解表情数据矩阵的协方差矩阵的方法得到正 程如图2所示 交基，也就是采用PCA方法得到一个表情子空间， 待聚类的表情样本 记为WCA.投影所有的中心化后的表情图像、中心 化后的类内平均表情图像及总体表情平均图像到表 确定类别数及初始聚类中心 情子空间」 X=Wea父，m=WCah, 计算各样本到质心的距离 m WicA m. (5) 计算第1类的类内散布矩阵S,和总的类内散 按照最近邻原则对各样本分类 布矩阵Sw.C为表情分类的类数，文中C=7 重新计算各聚类的质心 s.=(x-m (x-m.s.=25.(6) 类间散布矩阵Sa是所有类内表情平均图像在 算法已经收敛或 达到最大迭代次数 表情子空间的投影的加权协方差矩阵之和，权值N, 是该类表情的图像数 是 聚类完成 ∑N,(m-m(m-m 7) 求解类内散布矩阵Sm和类间散布矩阵Sa的 图2C均值聚类算法过程图 广义特征值V和特征向量A: Fig 2 Process of Gmeans clustering algorithm SEV ASwV (8 1.4K近邻分类 按照特征值的大小对特征向量从大到小排序， 该方法简单地说就是取未知样本x的k个近 保留最大的前C-1个特征向量，组合成最佳分类 邻，看这k个近邻中多数属于哪一类，就把x归为哪 空间WD.最后，组合PCA/LDA方法，得到最优的 一类5).具体说就是在N个已知样本中，找出x的 表情投影子空间Wr=WHD WPCA.对于后文表情模 k个近邻.设这N个样本中，来自4类的样本有N 板的计算和待识别的表情图像，都要在这个空间进 个，来自类的样本有N2个，…，来自4类的样本 行计算，即要投影到这个空间.对于任意一个向量 有N:个，若，：，…k分别是k个近邻中属于 x,在该空间的投影变换公式为 ,,4类的样本数，则定义判别函数为 Z WoPT x WELD WPCA (x-m). (9) g(W=k,i=1,2,…C (10) 式中：z是一个C-1维的向量，文中C=7,所以是6 决策规则为 维的向量.可见经过该变换后数据量大大减小，这样 若g(x=maxk, 11) 才能做到表情的实时识别 则决策x∈. 1.3C均值聚类 这就是K近邻法的基本原则.对一幅待识别的 因为表情因人而异，所以同一种表情往往会有 表情图像，文中先将该图像进行Gabor小波变换， 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved http://www.cnki.net
的方法高. 对于已经过 Gabor 小波变换的表情图像训练 集 X,先将图像集进行分类 ,将同一种表情的图像归 为一类 ,记为 Xi . 文中要识别 7 种表情 ,所以 i = 1 , 2 , …,7. Fisherface 的计算过程如下. 首先 ,计算每一类的类内平均表情图像 mi 和 所有训练图像的总体平均表情图像 m . 然后 ,将每个 类内的表情图像减去自己类内的平均表情图像 ,得 到每个表情的差值表情;最后每一个类内平均表情 图像减去总体平均表情图像. Πx ∈Xi , Xi ∈X, ^x = x - mi , m^ i = mi - m. (4) 再创建一个数据矩阵 ,即把所有中心化后的表 情图像按次序排列成一个表情数据矩阵. 接下来求 解表情数据矩阵的正交向量 :可以通过奇异值分解 或者求解表情数据矩阵的协方差矩阵的方法得到正 交基 ,也就是采用 PCA 方法得到一个表情子空间 , 记为 WPCA . 投影所有的中心化后的表情图像、中心 化后的类内平均表情图像及总体表情平均图像到表 情子空间. x = W T PCA ^x , mi = W T PCA m^ i , m = W T PCA m. (5) 计算第 i 类的类内散布矩阵 Si 和总的类内散 布矩阵 S W . C为表情分类的类数 ,文中 C = 7. Si = x∑∈Xi ( x - m) ( x - m) T , Sw = ∑ C i = 1 Si . (6) 类间散布矩阵 SB 是所有类内表情平均图像在 表情子空间的投影的加权协方差矩阵之和 ,权值 Ni 是该类表情的图像数. SB = ∑ C i =1 Ni ( mi - m) ( mi - m) T . (7) 求解类内散布矩阵 SW 和类间散布矩阵 S B 的 广义特征值 V 和特征向量Λ: SB V = ΛS W V . (8) 按照特征值的大小对特征向量从大到小排序 , 保留最大的前 C - 1 个特征向量 ,组合成最佳分类 空间 WFLD . 最后 ,组合 PCA/ LDA 方法 ,得到最优的 表情投影子空间 W T OPT = W T FLDW T PCA . 对于后文表情模 板的计算和待识别的表情图像 ,都要在这个空间进 行计算 ,即要投影到这个空间. 对于任意一个向量 x ,在该空间的投影变换公式为 z = W T OPT x = W T FLDW T PCA ( x - m) . (9) 式中 : z 是一个 C - 1 维的向量 ,文中 C = 7 ,所以是 6 维的向量. 可见经过该变换后数据量大大减小 ,这样 才能做到表情的实时识别. 113 C 均值聚类 因为表情因人而异 ,所以同一种表情往往会有 很多种表现方式 ,因此很难只使用一个表情模板来 代表一种表情 ,也就是说每种表情还应再划分成多 个子类. 聚类是在样本类别未知的情况下进行的无 监督的学习方法. 通过聚类分析 ,可以把相似的样本 聚成一类 ,不相似的样本分别聚在不同的类里. 文中 对表情模板使用了动态 C 均值聚类方法 ,将每种表 情聚成多个子表情类 ,取每类的质心作为标准的表 情模板. C 均值聚类算法过程如下 : 首先 ,确定聚类的类数 C 并选择 C 个代表点作 为最初的质心. 然后计算代表点之外的所有点到各 个代表点的距离 ,按照最近邻的原则 ,将这些点进行 分类. 至此完成第 1 次迭代. 接下来再分别计算各个 类的质心 ,然后计算所有点到各个质心的距离 ,按照 最近邻法将所有点再一次进行分类. 反复迭代 ,直到 算法收敛或达到预定义的最大迭代次数为止. 该过 程如图 2 所示. 图 2 C 均值聚类算法过程图 Fig12 Process of C2means clustering algorithm 114 K 近邻分类 该方法简单地说就是取未知样本 x 的 k 个近 邻 ,看这 k 个近邻中多数属于哪一类 ,就把 x 归为哪 一类[15 ] . 具体说就是在 N 个已知样本中 ,找出 x 的 k 个近邻. 设这 N 个样本中 ,来自ω1 类的样本有 N1 个 ,来自ω2 类的样本有 N2 个 , …,来自ωc 类的样本 有 Nc 个 ,若 k1 , k2 , …, kc 分别是 k 个近邻中属于 ω1 ,ω2 , …,ωc 类的样本数 ,则定义判别函数为 gi ( x) = ki , i = 1 ,2 , …, C. (10) 决策规则为 若 gj ( x) = max i k i , (11) 则决策 x ∈ωj . 这就是 K近邻法的基本原则. 对一幅待识别的 表情图像 ,文中先将该图像进行 Gabor 小波变换 , 第 1 期 张一鸣 ,等 :基于 C均值 K 近邻算法的面部表情识别 · 95 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·60 智能系统学报 第3卷 再利用式(9)投影到特征空间上，最后使用K近邻 本测试实验与Michael等1的测试方法相同 法与1.3中使用C均值聚类得到的表情模板进行 把数据库中的213张图像分成10部分，每次使用其 比较，以达到对该表情分类的目的.K近邻法与C 中的9部分训练，剩下的1部分测试.循环测试10 均值聚类方法联合使用，考虑了同种表情的表现多 次，然后对这10次取平均值，得出正确识别率，由于 样性，能够有效地提高表情的识别率 C均值算法的C取值和K近邻的K取值不同，识 1.5表情识别的整体流程 别率有所不同，实验结果见表1 表情识别的全部过程见图3.所有的图像首先 都要进行Gabor小波变换，然后对训练图像进行训 表1C均值K近邻算法的不同取值的实验结果 Table 1 Performance of Gmeans cluster and 练得到特征空间，标准的表情图像在该特征空间中 Knearest neighbor algorithm 进行C均值聚类得到表情模板，待识别的表情图像 在该特征空间中与表情模板匹配从而实现该幅表情 K 图像的分类 2 3 5 6 91.0 91.0 91.0 91.0 91.0 91.0 标准的表 参加练的 一幅待识别 情图像 表情图像 、的表情图像 2 91.3 91.3 91.7 91.9 91.9 91.9 Gabor小波变换 Gabor小波变换 Gabor小波变换 3 92.8 92.893.2 93.1 93.1 93.0 训练特征空间 4 95.2 95.2 95.5 95.8 95.3 95.3 特 5 94.2 94.2 94.3 94.4 94.4 特征空 94.3 C均值聚类 6 93.193.1 93.393.5 93.593.4 [表特模板匹配 由表1的实验数据可以看出，采用把每个表情 表情分类) 类分成多个子表情类的方法，由于充分利用了每种 表情类之间的差异信息，因此能够提高识别率，K 的取值对识别率影响不大，识别率主要取决于C的 图3表情识别的全部过程 取值，即每种表情聚成的子类个数.随着C的取值 Fig 3 Process of facial expression recognition 从1逐渐增大，识别率也随着提高，但是当C的取 2 测试实验 值超过某一个数值之后识别率又开始下降.这是因 为当聚类的数目很多时，每类的图像数目变少，聚类 测试实验使用了日本女人表情数据库(Japa 所形成的表情模板受到了人相貌的影响，影响了表 nese female facial expression JAFFE).该数据库包 情识别的准确率.从表1看出当C=4,K=4时，达 含了10个日本女人的213幅表情图像，每个人7种 到最高识别率95.8%.该识别率高于文献[16]92% 表情，包括高兴、生气、恐惧、厌恶、害怕、悲伤和中性 的识别率.此时输入的表情与被识别出的表情的混 表情，每个人的同一种表情图像有3~4幅.JAFFE 淆矩阵(confusion matrix)见表2. 的部分表情图像如图4所示，其表情依次为中性、生 气、厌恶恐惧、高兴、悲伤、惊讶 表2C=4,K=4时的混淆矩阵 Table 2 Confusion matrix when C=4 and K=4 0 高兴厌恶生气恐惧惊讶悲伤中性 高兴 31 0 0 0 0 0 0 厌恶 0 29 0 1 0 生气 0 0 28 0 0 1 0 恐惧 0 0 0 30 2 0 0 惊讶 0 0 2 28 0 0 悲伤 0 0 1 0 29 1 图4 JAFFE表情图像数据库中的表情样本 中性 0 0 0 0 0 0 29 Fig,4 Expression samples in JAFFE expression database I:识别输入(recognition input);O:识别输出(recogni- tion output) 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
再利用式(9) 投影到特征空间上 ,最后使用 K 近邻 法与 11 3 中使用 C 均值聚类得到的表情模板进行 比较 ,以达到对该表情分类的目的. K 近邻法与 C 均值聚类方法联合使用 ,考虑了同种表情的表现多 样性 ,能够有效地提高表情的识别率. 115 表情识别的整体流程 表情识别的全部过程见图 3. 所有的图像首先 都要进行 Gabor 小波变换 ,然后对训练图像进行训 练得到特征空间 ,标准的表情图像在该特征空间中 进行 C 均值聚类得到表情模板 ,待识别的表情图像 在该特征空间中与表情模板匹配从而实现该幅表情 图像的分类. 图 3 表情识别的全部过程 Fig13 Process of facial expression recognition 2 测试实验 测试实验使用了日本女人表情数据库 (J apa2 nese female facial expression ,J A FFE) . 该数据库包 含了 10 个日本女人的 213 幅表情图像 ,每个人 7 种 表情 ,包括高兴、生气、恐惧、厌恶、害怕、悲伤和中性 表情 ,每个人的同一种表情图像有 3～4 幅.J AFFE 的部分表情图像如图 4 所示 ,其表情依次为中性、生 气、厌恶、恐惧、高兴、悲伤、惊讶. 图 4 J AFFE 表情图像数据库中的表情样本 Fig14 Expression samples in J AFFE expression database 本测试实验与 Michael 等[ 16 ] 的测试方法相同 , 把数据库中的 213 张图像分成 10 部分 ,每次使用其 中的 9 部分训练 ,剩下的 1 部分测试. 循环测试 10 次 ,然后对这 10 次取平均值 ,得出正确识别率. 由于 C均值算法的 C 取值和 K 近邻的 K 取值不同 ,识 别率有所不同 ,实验结果见表 1. 表 1 C均值 K近邻算法的不同取值的实验结果 Table 1 Performance of C2means cluster and K2nearest neighbor algorithm C K 1 2 3 4 5 6 1 9110 9110 9110 9110 9110 9110 2 9113 9113 9117 9119 9119 9119 3 9218 9218 9312 9311 9311 9310 4 9512 9512 9515 9518 9513 9513 5 9412 9412 9413 9414 9414 9413 6 9311 9311 9313 9315 9315 9314 由表 1 的实验数据可以看出 ,采用把每个表情 类分成多个子表情类的方法 ,由于充分利用了每种 表情类之间的差异信息 ,因此能够提高识别率. K 的取值对识别率影响不大 ,识别率主要取决于 C 的 取值 ,即每种表情聚成的子类个数. 随着 C 的取值 从 1 逐渐增大 ,识别率也随着提高 ,但是当 C 的取 值超过某一个数值之后识别率又开始下降. 这是因 为当聚类的数目很多时 ,每类的图像数目变少 ,聚类 所形成的表情模板受到了人相貌的影响 ,影响了表 情识别的准确率. 从表 1 看出当 C = 4 , K = 4 时 ,达 到最高识别率 9518 % . 该识别率高于文献[ 16 ]92 % 的识别率. 此时输入的表情与被识别出的表情的混 淆矩阵(conf usion matrix) 见表 2. 表 2 C= 4 , K= 4 时的混淆矩阵 Table 2 Confusion matrix when C= 4 and K= 4 O I 高兴 厌恶 生气 恐惧 惊讶 悲伤 中性 高兴 31 0 0 0 0 0 0 厌恶 0 29 1 0 0 1 0 生气 0 0 28 0 0 1 0 恐惧 0 0 0 30 2 0 0 惊讶 0 0 0 2 28 0 0 悲伤 0 0 1 0 0 29 1 中性 0 0 0 0 0 0 29 I :识别输入 (recognition input) ; O:识别输出 ( recogni2 tion output) · 06 · 智 能 系 统 学 报 第 3 卷 © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第1期 张一鸣，等：基于C均值K近邻算法的面部表情识别 *61* 从表2可以看出，惊讶和恐惧不易区分，生气、 [10]PEN EV P S,A TICKJ J.Local feature analysis:a gen- 厌恶、悲伤3种表情也不易区分，高兴的识别率最 eral statistical theory for object representation [J].Net- 高.这是由于不同表情之间的差异不同造成的 work:Computation in Neural Systems,1996,7(3):477- 500. 3结束语 [11]CALDER A J,BURTON A M,MILL ER P,et al.A principal component analysis of facial expressions [J ] 文中通过Gabor小波变换提取面部表情信息， Vision Research,2001,41(9):11791208. 使用Fisherface判别分析的方法训练投影空间，对 [12]SEYEDARABI H,AGHAGOLZADEH A,KHAN- 于表情模板使用了C均值动态聚类的方法，将每种 MOHAMMADI S.Recognition of six basic facial ex- 表情聚成多个子表情类，最后使用K近邻法进行表 pressions by feature-points tracking using RBF neural 情识别.从实验结果来看，文中的方法由于考虑了每 network and fuzzy inference system [C]//Proceedings 种表情表现形式的多样性，将每种表情划分成多个 of 2004 IEEE International Conference on Multimedia 子类，识别率得到一定的提高.由于表情的多样性与 and Expo.Taipei,China,2004. 复杂性，表情识别的研究，仍然是模式识别领域的一 [13]MA L,KHORASANI K.Facial expression recognition 项重要的课题 using constructive feedforward neural networks [J]. IEEE Trans on SMC-Part B,2004,34(3):1588-1595. 参考文献： [14]LADES M JAN C.Distortion invariant object recogni- tion in the dynamic link architecture [J ]IEEE Trans [1]EKMAN P,FRIESEN W V.Facial action coding sys on Computer,1993,42(3):300311. tem:a technique for the measurement of facial movement [15]边肇祺，张学工.模式识别[M].北京：清华大学出版社， M].Palo Alto,CA:Consulting Psychologists Press, 2000. 1978. [16]L YONS MJ ,BUD YNEKJ ,A KAMA TSU S.Automat- [2]MASE K.Recognition of facial expression from optical ic classification of single facial images [J].IEEE Trans f1owU].IEICE Trans E,1991,74(10):3474-3483. on PAM1,1999,21(12):13571362 [3]YACOOB Y,DAVIS L.Recognizing human facial ex- 作者简介 pressions from long image sequences using optical flow 张一鸣，女，1981年生，硕士研究生，主要 [U].IEEE Trans on PAM1,1996,18(6):636642. 研究方向为模式识别 [4]COTTRELL G,METCALFE J.Face,gender and emo- tion recognition using Holons [Cl//Advances in Neural Information Processing Systems.Denver,USA,1990, 3:564-571. [5]PADGETT C,COTTRELL G.Representing face images for emotion classification C]//Advances in Neural In- 欧宗瑛，男，1936年生，教授，博士生导 formation Processing Systems.Cambridge:MIT Press, 师，主要研究方向为计算机辅助设计、计算机 1997. 图形学和图像处理.获教委和机械部科技三 [6]金一，阮秋琦.一种局部加权的二维主成分分析算法 等奖各一项，辽宁省科技一等奖一项.参与主 及其在人脸识别中的应用[J].智能系统学报，2007,2 编的机械设计手册和机电类规划教材分别获 (3):2529 1995全国科技图书二等奖和2002全国优秀 JIN Yi,RUAN Qiuqi.A part weighted two-dimensional 教材二等奖.发表的学术论文被SC1检索12 PCA for face recognition[J ]CAAI Transactions on In- 篇，被EI检索95篇 telligent Systems,2007,2(3):25-29. [7]DONA TO G,STEWART M B,HAGER J C,et al. 王虹，男，1964年生，博士研究生，主 Classifying facial actions [J ]IEEE Trans on PAMI. 要研究方向为模式识别、图像处理 199921(10):974-989. [8]DAU GMAN J G.Complete discrete 2D Gabor transform by neural networks for image analysis and compression [U].IEEE Trans on ASSP,1998,36(7):11691179. [9]BUCIU I,KOTROPOULOS C.ICA and Gabor represen- tation for facial expression recognition[C]//Proceedings of IEEE ICIP.Barcelona,Spain,2003. 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
从表 2 可以看出 ,惊讶和恐惧不易区分 ,生气、 厌恶、悲伤 3 种表情也不易区分 ,高兴的识别率最 高. 这是由于不同表情之间的差异不同造成的. 3 结束语 文中通过 Gabor 小波变换提取面部表情信息 , 使用 Fisherface 判别分析的方法训练投影空间 ,对 于表情模板使用了 C 均值动态聚类的方法 ,将每种 表情聚成多个子表情类 ,最后使用 K 近邻法进行表 情识别. 从实验结果来看 ,文中的方法由于考虑了每 种表情表现形式的多样性 ,将每种表情划分成多个 子类 ,识别率得到一定的提高. 由于表情的多样性与 复杂性 ,表情识别的研究 ,仍然是模式识别领域的一 项重要的课题. 参考文献 : [1 ] EKMAN P , FRIESEN W V. Facial action coding sys2 tem : a technique for the measurement of facial movement [ M ]. Palo Alto , CA : Consulting Psychologists Press , 1978. [2 ] MASE K. Recognition of facial expression from optical flow [J ]. IEICE Trans E ,1991 ,74 (10) :347423483. [3 ] YACOOB Y , DAVIS L. Recognizing human facial ex2 pressions from long image sequences using optical flow [J ]. IEEE Trans on PAMI ,1996 ,18 (6) :6362642. [4 ]CO TTRELL G,METCAL FE J. Face , gender and emo2 tion recognition using Holons [ C]/ / Advances in Neural Information Processing Systems. Denver , USA , 1990 , 3 : 5642571. [5 ] PAD GETT C , CO TTRELL G. Representing face images for emotion classification [ C]/ / Advances in Neural In2 formation Processing Systems. Cambridge : MIT Press , 1997. [6 ]金 一 , 阮秋琦. 一种局部加权的二维主成分分析算法 及其在人脸识别中的应用 [J ]. 智能系统学报 , 2007 , 2 (3) :25229. J IN Yi , RUAN Qiuqi. A part weighted two2dimensional PCA for face recognition [J ]. CAAI Transactions on In2 telligent Systems , 2007 ,2 (3) :25229. [7 ] DONA TO G, STEWART M B , HA GER J C , et al. Classifying facial actions [J ]. IEEE Trans on PAMI , 1999 , 21 (10) : 9742989. [8 ]DAU GMAN J G. Complete discrete 2D Gabor transform by neural networks for image analysis and compression [J ]. IEEE Trans on ASSP ,1998 , 36 (7) : 116921179. [ 9 ]BUCIU I , KO TROPOULOS C. ICA and Gabor represen2 tation for facial expression recognition[C]/ / Proceedings of IEEE ICIP. Barcelona , Spain , 2003. [10 ]PEN EV P S , A TICKJ J. Local feature analysis: a gen2 eral statistical theory for object representation [J ]. Net2 work : Computation in Neural Systems , 1996 ,7 (3) :4772 500. [11 ]CALDER A J , BURTON A M , MILL ER P , et al. A principal component analysis of facial expressions [J ]. Vision Research , 2001 ,41 (9) : 117921208. [12 ]SEYEDARABI H , A GHA GOL ZADEH A , KHAN 2 MO HAMMADI S. Recognition of six basic facial ex2 pressions by feature2points tracking using RBF neural network and fuzzy inference system [ C]/ / Proceedings of 2004 IEEE International Conference on Multimedia and Expo. Taipei , China , 2004. [13 ]MA L , KHORASANI K. Facial expression recognition using constructive feedforward neural networks [J ]. IEEE Trans on SMC2Part B ,2004 ,34 (3) :158821595. [14 ]LADES M ,J AN C. Distortion invariant object recogni2 tion in the dynamic link architecture [J ]. IEEE Trans on Computer ,1993 , 42 (3) :3002311. [15 ]边肇祺 ,张学工. 模式识别[ M]. 北京 :清华大学出版社 , 2000. [ 16 ]L YONS M J ,BUD YN EKJ ,A KAMA TSU S. Automat2 ic classification of single facial images [J ]. IEEE Trans on PAMI ,1999 ,21 (12) :135721362. 作者简介 : 张一鸣 ,女 ,1981 年生 ,硕士研究生 ,主要 研究方向为模式识别. 欧宗瑛 ,男 ,1936 年生 ,教授 ,博士生导 师 ,主要研究方向为计算机辅助设计、计算机 图形学和图像处理. 获教委和机械部科技三 等奖各一项 ,辽宁省科技一等奖一项. 参与主 编的机械设计手册和机电类规划教材分别获 1995 全国科技图书二等奖和 2002 全国优秀 教材二等奖. 发表的学术论文被 SCI 检索 12 篇 ,被 EI 检索 95 篇. 王 虹 ,男 ,1964 年生 ,博士研究生 ,主 要研究方向为模式识别、图像处理. 第 1 期 张一鸣 ,等 :基于 C均值 K 近邻算法的面部表情识别 · 16 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
