第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