双目标精英策略的三维人脸表情特征筛选及识别

Foundation item: Supported by the Natural Science Foundation of Fujian Province(2012J01260)

双目标精英策略的三维人脸表情特征筛选及识别*

胡步发黄首宁

(福州大学 机械工程及自动化学院, 福建 福州 350116)

摘要：非支配遗传算法(NSGA-Ⅱ)对双目标的特征筛选可以取得很好的效果,但该算法在优化过程中会出现局部收敛和早熟问题.为此,文中提出了改进的NSGA-Ⅱ特征筛选算法:先对父代种群运行第1次精英策略,从中筛选出父代精英种群;然后将筛选后的父代精英种群与子代种群构成联合种群,并对联合种群运行第2次精英策略获得下一父代种群.在利用文中算法对三维人脸表情的候选特征进行筛选后,通过概率神经网络算法对筛选特征进行分类识别.结果表明,文中算法可以在很大程度上解决传统NSGA-Ⅱ的局部收敛和早熟问题,并能有效地提升表情识别的准确性.

关键词：非支配遗传算法；特征筛选；三维模型；表情识别；概率神经网络

收稿日期：2014-12-08

基金项目：* 福建省自然科学基金资助项目(2012J01260)

作者简介：胡步发(1963-),男,博士,副教授,主要从事机器视觉、图像处理与模式识别研究.E-mail: hubufa@21cn.com

文章编号：1000-565X(2015)05-0086-06

中图分类号：TP391.4

doi:10.3969/j.issn.1000-565X.2015.05.014

人脸表情识别主要由人脸表情的特征提取、筛选及分类识别组成.其中,人脸表情的特征筛选是为了从原人脸表情图像的特征集中筛选出尽量少的、但尽可能准确描述人脸表情的特征[1-2].特征筛选的过程是否合理、结果是否准确,直接影响到表情的分类识别.

目前,人脸表情特征筛选的主要方法有主成分分析(PCA)法[3-4]、信息熵法[5-9]和非支配遗传算法(NSGA-Ⅱ)[10].如Soyel等[3]运用PCA对人脸面部表情特征进行降维处理,然后运用双层概率神经网络(PNN)模型将处理后的特征进行分类识别,取得了较好的识别效果.Yun等[4]先提取三维人脸上的3D-Gabor特征,再利用PCA对提取后的特征进行降维处理,解决了改进的核典型性相关分析(IKCCA)算法中可能出现的“维数灾难”问题.Lajevardi等[5-6]通过计算各个特征的互信息熵值,并以互信息准则(MIQ)作为特征筛选的判据,获得了冗余度小、相关性高的表情特征.Kamil等[7-8]基于双层支持向量机人脸表情识别模型,对三维人脸上的83个特征点进行熵分析,筛选出符合Fisher准则的特征点,并提取这些点的强度值作为特征,解决了由模糊表情带来的错误识别问题.Jaganathan等[9]认为在实际中各个特征集合间的界限并不是十分清晰,不能采用常规的信息熵法来计算特征的熵值,进而提出了对不同特征集合的模糊熵阈值采用不同的筛选策略,完成了对不同种类特征的筛选工作.这些特征筛选方法均是以降低特征数量为目标，但实际上特征筛选是一个双目标控制的过程,在减少特征数量的同时还必须保证相同表情特征之间的相似程度要高而不同表情之间的差异度要大.传统的特征筛选方法在设计目标函数时,一般是将双目标问题融合在一起组成一个单目标函数,并根据不同目标增加目标函数的约束条件，但单纯地增加约束条件只可以使单目标函数取得最优解,并不会使该解成为双目标问题的最优解.因此,Soyel等[10]提出了应用于双目标特征筛选的NSGA-Ⅱ：首先将父代种群和该父代遗传变异获得的子代种群组成二倍联合种群；然后根据双目标函数构建个体之间的非支配关系,并按照非支配关系对个体进行分层；最后根据分层结果从二倍联合种群中挑选出下一父代种群.从二倍联合种群中挑选下一父代种群的过程,就是NSGA-Ⅱ的精英策略,其目的是保留各代大部分的精英个体,但在此过程中,联合种群规模要减少一半,算法在对联合种群进行非支配排序后,将联合种群中一些拥有优秀基因的普通个体排在联合种群的后半部分,并选取联合种群的前半部分个体作为下一父代种群,这样会使得下一父代种群中含有该优秀基因的个体数量较少.另外,从下一父代种群遗传变异获得下一子代种群的过程,实际上是一个“近亲繁殖”的过程,这样随着运行代数的不断增加,会使得数量较多的强势精英个体得以保留,而将数量较少的弱势精英个体排斥在父代种群之外,造成部分精英个体丢失.这将导致父代种群未达到算法迭代终止代数便因成熟度过高而失去种群多样性,造成算法迭代终止,失去在全局中搜寻最优解的能力,出现早熟和局部收敛现象,进而影响特征筛选和后续三维人脸表情识别的效果.

针对NSGA-Ⅱ存在的问题,文中提出了改进的NSGA-Ⅱ特征筛选算法,以增加含有优秀基因的普通个体入选下一父代种群的数量.首先将父代种群进行遗传变异操作生成子代种群,然后在原算法的基础上增加从父代种群挑选父代精英种群的过程,并用该父代精英种群代替原父代种群与子代种群构成联合种群,最后根据双目标函数构建个体之间的非支配关系,并按照非支配关系对联合种群中的个体进行分层,选出下一父代种群.

1特征筛选方法

人脸表情是由肌肉动作来实现的,不同的表情动作会使得面部不同的特征点发生不同程度的移动.因此,采用面部特征点间的欧几里德距离作为图像的低层视觉特征,可以清晰准确地描述不同表情下人脸各部分特征的变化.文中采用BU-3DFE人脸表情数据库提供的三维人脸表情模型,由该模型83个手工标定特征点间的欧几里德距离[11]作为低层视觉特征.其中,手工标定特征点如图1所示.

图1　不同人脸表情模型的83个特征点分布

Fig.1Distribution of 83 feature mark points of different facial expression models

设βi表示三维人脸上的特征点,则两两特征点间的欧几里德距离(即特征Δi,j)可表示为

(1)

式中,ω为两眼外眼角点间的欧几里德距离.

第k(k∈{1,2…,N})个三维人脸表情模型的候选特征Vk表示为

(2)

文中以降低特征数量和最大化Fisher值[12]作为目标,以增加同种表情特征之间的聚合度和不同种表情间的差异性.

1.1Fisher准则

令ni表示第i类样本,c表示类别数量,mi表示第i类样本的平均向量,m表示所有类别样本的平均向量,SB表示类间散布矩阵,SW表示类内散布矩阵,xij表示第i类的第j个特征向量(i=1,2,…,c;j=1,2,…,ni),则有

(3)

(4)

(5)

1.2快速非支配排序

快速非支配排序算法由Deb等[13]提出,假设种群为P,则该算法需要计算种群P中个体p的两个参数np和Sp,其中np为种群中支配个体p的个体数量,Sp为种群中被个体p支配的个体集合,算法的主要步骤如下:

(1)找到种群中所有np=0的个体,并保存到当前集合F1中；

(2)遍历Si(即F1中个体i所支配的个体集合)中的每个个体k,执行nk=nk-1(因为支配个体k的个体p已被存入非支配个体集合F1),如果nk=0则将个体k保存在集合F2中；

(3)将F1中个体作为第1层非支配个体,F2作为当前集合,重复上述操作直到整个种群被分级完成.

1.3拥挤度计算

从联合种群中筛选出下一父代种群的过程中,先对联合种群进行快速非支配排序,再将联合种群中的个体按照非支配关系分好层级.由于每一代父代种群的规模是不变的,而联合种群的规模大于父代种群的规模,因此需要对联合种群中可以放入下一父代种群的最后一级非支配层的个体进行拥挤度排序.

设种群中的个体数为l,拥挤度I[i]d[13]的计算过程如下：

(1)初始化种群中的个体拥挤度值,即对于每个个体i,I[i]d=0；

(2)设个体拥挤度的边界为I[1]d=I[l]d=∞,计算个体i(i=2,3,…,l-1)的拥挤度值

(6)

1.4精英策略的排序规则

联合种群在经过快速非支配排序和拥挤度的计算后,种群中每个个体i都得到两个属性值:非支配序irank和拥挤度值I[i]d.当irankI[j]d时,表示个体i比j更优秀,记为ij.也就是说,如果两个个体i和j所在的非支配层不同,则选取非支配序较小的个体作为下一父代个体,否则选取周围拥挤度值较大的个体作为下一父代个体.拥挤度的比较只对同一非支配层的个体有效.

1.5改进的NSGA-Ⅱ算法

改进的NSGA-Ⅱ算法共运行两次精英策略.首先对父代种群运行第1次精英策略,筛选出父代精英种群；然后将父代精英种群与子代种群组合成联合种群,并对联合种群运行第2次精英策略,获得下一父代种群.改进NSGA-Ⅱ的步骤如下:

(1)由式(2)获得候选特征,并以这些特征的组合作为父代个体,构成父代种群.

(2)复制父代种群中所有的个体,形成完全相同的两份父代种群.

(3)对其中一份父代种群运行第1次精英策略,分别计算每个个体的Fisher值和拥挤度,按照Fisher值和个体中的特征数量对种群中所有的个体进行快速非支配排序,并结合拥挤度选取排名靠前的个体作为父代精英种群(其大小由父代种群的精英比获得).

(4)另一份父代种群经过交叉、变异后生成子代种群.

(5)将步骤(2)获得的父代精英种群和步骤(4)获得的子代种群组合成联合种群,对联合种群运行第2次精英策略,构造下一父代种群,其中各个父代种群的大小始终与初始父代种群相同.

(6)若运行代数大于最大代数,则算法结束,否则返回步骤(2)直到达到终止条件为止.

2三维人脸表情识别

文中采用PNN[3,14]进行三维人脸表情识别.PNN由3层构成:①输入层,它由R个神经元组成,主要是将输入变量送入到隐含层;②隐含层,它采用径向基函数计算输入特征向量和训练集中各模式的匹配关系,其神经元数目和训练样本数相同;③竞争输出层,根据贝叶斯规则[15]估计未知向量Γ属于所有可能类别c的概率,而类别ci的概率密度函数采用Parzen窗函数密度估计的方法[16]确定.PNN的输出神经元是一种竞争神经元,每个竞争神经元对应输出一种数据类型,即分类模式,输出神经元的个数等于所有模式的种类数.神经元中概率密度最大的对应输出为1,其他的输出为0,从而实现对特征向量的分类识别.

PNN方法的优点在于结构简单、学习速度快、收敛性好,对先验知识利用率高,对于复杂繁琐的分类,只要有充足的训练样本,都可以获得较好的分类结果.

3实验及结果分析

文中采用Matlab软件和三维人脸表情数据库BU_3DFE在Intel(R)Core(TM)i5 CPU 3.2GHz、4GB内存的电脑上进行实验.BU_3DFE包含100个人的人脸表情图像,其中56%为女性、44%为男性,每个人有6种基本表情和1种中性表情.另外,除中性表情外,6种基本表情分别包含4个层次的表情变化强度模型.因此,每个人有25个人脸模型,数据库中有2500个人脸表情模型.

文中实验选取60个对象,其中男女各占50%,并选取每个对象每种最强表情的人脸表情图像(除中性表情外).采用十折交叉验证方法进行实验,即将数据集分成10份,轮流将其中9份作为训练集,1份作为测试集,并取10次实验结果的平均值作为最终实验结果.

3.1父代精英种群规模的确定

表1精英比和计算结果之间的关系

Table 1Relationship between the elite ratio and the calculation results

精英比ξ均值ξ方差0.00.20.40.60.81.00.1760.4520.6050.5240.2620.2070.0120.0560.0230.0370.0260.021

3.2三维人脸表情特征筛选

文中实验将数据集分成训练集(包含54个个体、378个人脸表情图像)和测试集(包含6个个体、42个人脸表情图像),利用改进的NSGA-Ⅱ算法筛选出最优的特征组合并验证该改进算法的有效性.首先,根据最大化Fisher值和最小化特征数目,利用改进的NSGA-Ⅱ算法获得筛选特征组合,如图2(a)所示.可以看出,在特征组合数为25时,平均Fisher值曲线较为平缓,各种特征组合的候选解逐渐收敛到该曲线,并且出现最大的Fisher值(9.66).因此,选取Fisher值为9.66、筛选特征组合数为25的特征集合作为筛选特征组合.

图2两种算法的特征筛选结果

Fig.2Feature selection results of two algorithms

采用传统NSGA-Ⅱ算法获得的特征筛选结果如图2(b)所示.可以看出,由传统NSGA-Ⅱ算法获得的特征筛选结果中,各个候选解在特征组合为23时开始收敛到平均Fisher值曲线,并且出现最大的Fisher值为8.86.

从图2可知,文中改进NSGA-Ⅱ算法的平均Fisher值曲线整体上较传统NSGA-Ⅱ算法高,说明改进NSGA-Ⅱ算法获得的候选解在整体上优于传统NSGA-Ⅱ算法.

(7)

其中,Pt为第t代种群集合.则第t代种群的熵可定义为

(8)

图3两种算法的各代种群成熟度曲线

Fig.3Each generation population maturity curves of two algorithms

图3中,成熟度值为1代表种群不是特别成熟,成熟度值为0代表种群较为成熟.显然,在29代之前,两种算法的种群成熟度保持在一个较高的值,种群成熟度低,保持较高的多样性,未发生早熟现象.在第29代之后,传统NSGA-Ⅱ算法的各代种群成熟度开始下降,且随着算法运行代数的增加,种群成熟程度越来越高,种群的多样性也随之降低;而改进NSGA-Ⅱ算法的成熟度仍然保持在一个较高的位置,下降幅度较小.这说明改进NSGA-Ⅱ算法可以有效地减缓各代种群成熟的速度,使各代种群拥有较高的多样性,改善传统NSGA-Ⅱ算法出现的早熟问题.

另外,如图3所示,当成熟度达到0.1(即虚线与点线的交点处)时,传统NSGA-Ⅱ算法达到迭代终止条件,可认为种群足够成熟,终止迭代.即认为在第43代时算法已筛选出最优的特征组合,失去了在全局搜索其他可能存在的最优解的能力,发生了局部收敛现象.改进NSGA-Ⅱ算法的成熟度整体上高于传统NSGA-Ⅱ算法的成熟度,即在整体上降低了各代种群的成熟度,避免了在100代之前发生因成熟度过高而导致的局部收敛问题,使算法具有全局搜索最优解的能力,避免了传统NSGA-Ⅱ算法的局部收敛问题.

3.3三维人脸表情识别对比实验

文中算法对各三维人脸表情的识别结果如表2所示.

表2文中算法的三维人脸表情识别结果

Table 23D facial expression recognition results of the proposed algorithm

表情识别结果/个中性愤怒厌恶恐惧高兴悲伤惊讶中性52736000370愤怒22517000610厌恶00529304100恐惧370049601156高兴00670504290悲伤495501504810惊讶00028500522

文中算法与传统NSGA-Ⅱ[10]对三维人脸表情的平均识别结果如表3所示.

表3两种算法的三维人脸表情识别结果比较

Table 3Comparison of 3D facial expression recognition results between two algorithms

算法筛选特征数量Fisher值识别率/%NSGA-Ⅱ算法[10]238.8681.43文中算法259.6685.16

从表3可以看出,文中算法的筛选特征数、Fisher值及识别率均高于NSGA-Ⅱ算法.文中算法的筛选特征数高于NSGA-Ⅱ算法的原因是,NSGA-Ⅱ算法的种群出现早熟和局部收敛问题,使得种群中含有优秀基因的普通个体发生丢失,导致传统NSGA-Ⅱ算法获得的23个筛选特征不能准确地描述三维人脸的各种表情,从优化算法上来看就是没有获得最优解,这影响了后面表情识别的准确性.上述实验结果表明,改进算法不仅可以有效改善NSGA-Ⅱ算法中出现的早熟和局部收敛问题,而且获得的特征筛选组合可以更为准确地描述人脸表情,将改进算法获得的特征组合应用到三维人脸表情识别中,可以显著增加识别的准确率.

另外,文中算法与其他相关的特征筛选算法相比,也取得了很好的人脸表情识别效果,结果如表4所示.

表4几种算法的表情识别结果比较

Table 4Comparison of expression recognition results among several algorithms

算法特征提取方式特征筛选方法分类器人脸数据库识别率/%文献[4]3D-GaborPCAKCCABU-3DFE84.32文献[5]GaborMIQLDABU-3DFE81.52文献[10]几何距离NSGA-ⅡPNNBU-3DFE81.43文中算法几何距离改进NSGA-ⅡPNNBU-3DFE85.16

4结论

文中对NSGA-Ⅱ算法的局部收敛和早熟问题进行了分析,并对其精英策略进行了改进,增加了联合种群中含有优秀基因的普通个体入选下一父代种群的数量,改善了原算法收敛到非最优解和种群过早失去多样性的问题.文中提出的改进NSGA-Ⅱ算法主要是针对特征筛选中出现的双目标问题进行优化,获得双目标问题最优解.实际上,三维人脸表情的特征筛选结果还受到其他目标函数的影响.今后将进一步研究多目标函数的特征筛选方法,并将其应用到三维人脸表情识别中.

参考文献：

[1]Venkatesh Yedatore V,Kassim Ashraf A,Yuan Jun,et al.On the simultaneous recognition of identity and expression from BU-3DFE datasets [J].Pattern Recognition Letters,2012,33(13):1785-1793.

[2]Sandbach Georgia,Zafeiriou Stefanos,Pantic Maja,et al.Static and dynamic 3D facial expression recognition:a comprehensive survey [J].Image and Vision Computing,2012,30(10):683-697.

[3]Soyel Hamit,Demirel Hasan.Optimal feature selection for 3D facial expression recognition using coarse-to-fine classification [J].Turkish Journal of Electrical Engineering and Computer Sciences,2010,18(6):1031-1040.

[4]Yun Tie,Guan Ling.Human emotional state recognition using real 3D visual features from Gabor library [J].Pattren Recognition,2013,46(2):529-538.

[5]Lajevardi Seyed Mehdi,Wu Hong Ren.Facial expression recognition in perceptual color space [J].IEEE Transactions on Image Processing,2012,21(8):3721-3733.

[6]Lajevardi Seyed Mehdi,Hussain Zahir M.Automatic facial expression recognition:feature extraction and selection [J].Signal,Image and Video Processing,2012,6(1):159-169.

[7]Kamil Yurtkan,Hasan Demirel.Feature selection for improved 3D facial expression recognition [J].Pattern Re-cognition Letters,2014,38:26-33.

[8]Kamil Yurtkan,Hasan Demirel.Entropy-based feature selection for improved 3D facial expression recognition [J].Signal,Image and Video Processing,2014,8(2):267-277.

[9]Jaganathan P,Kuppuchamy R.A threshold fuzzy entropy based feature selection for medical database classification [J].Computers in Biology and Medicine,2013,43(12):2222-2229.

[10]Soyel Hamit,Tekguc Umut,Demirel Hasan.Application of NSGA-Ⅱ to feature selection for facial expression recognition [J].Computers and Electrical Engineering,2011,37(6):1232-1240.

[11] Soyel Hamit,Demirel Hasan.Facial expression recognition using 3D facial feature distances[M].Image Analysis and Recognition.Berlin/Heidelberg:Springer,2007:831-838.

[12]Lu J C,Liu F L,Luo X Y.Selection of image features for steganalysis based on the Fisher criterion [J].Digital Investigation,2014,11(1):57-66.

[13]Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ [J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[14]Jing J F,Xu M M,Li P F,et al.Automatic classification of woven fabric structure based on texture feature and PNN [J].Fibers and Polymers,2014,15(5):1092-1098.

[15]Rau Christian.Bayes classifiers of three-dimensional rotations and the sphere with symmetries [J].Statistics and Probability Letters,2013,83(3):930-935.

[16]Nojun Kwak.Input feature selection by mutual information based on Parzen window [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(12):1667-1671.

[17]汪民乐,高晓光,刘刚.遗传算法早熟问题的定量分析及其预防策略 [J].系统工程与电子技术,2006,28(8):1249-1252.

Wang Min-le,Gao Xiao-guang,Liu Gang.Quantitive ana-lysis and prevention of genetic algorithm premature convergence [J].Systems Engineering and Electronics,2006,28(8):1249-1252.

Selection and Recognition of 3D Facial Expression Feature Based on

Bi-Objective Elitist Strategy

HuBu-faHuangShou-ning

(College of Mechanical Engineering and Automation,Fuzhou University,Fuzhou 350116,Fujian,China)

Abstract:Non-dominated sorting genetic algorithm Ⅱ(NSGA-Ⅱ) works effectively in selecting bi-objective features,but may result in local convergence and prematurity in the process of optimization.In order to solve this problem,an improved NSGA-Ⅱ feature selection algorithm is proposed.In this algorithm,firstly,the first elite strategy is operated to select the elite population from parent population. Secondly,the selected parent elite population is combined with the offspring population to form a combined population.Finally,the second elite strategy is executed to obtain the next parent population. After the selection of 3D face expression candidate features,the selected features are classified by means of probabilistic neural network. Experimental results show that the proposed algorithm improves the performance of NSGA-Ⅱ with local convergence and prematurity problems greatly and increases the accuracy of facial expression recognition effectively.

Key words: non-dominated sorting genetic algorithm;feature selection;three-dimension model;expression re-cognition;probabilistic neural network