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

雙目標精英策略的三維人臉表情特征篩選及識別*

胡步發(fā)黃首寧

(福州大學 機械工程及自動化學院, 福建 福州 350116)

摘要：非支配遺傳算法(NSGA-Ⅱ)對雙目標的特征篩選可以取得很好的效果,但該算法在優(yōu)化過程中會出現(xiàn)局部收斂和早熟問題.為此,文中提出了改進的NSGA-Ⅱ特征篩選算法:先對父代種群運行第1次精英策略,從中篩選出父代精英種群;然后將篩選后的父代精英種群與子代種群構成聯(lián)合種群,并對聯(lián)合種群運行第2次精英策略獲得下一父代種群.在利用文中算法對三維人臉表情的候選特征進行篩選后,通過概率神經(jīng)網(wǎng)絡算法對篩選特征進行分類識別.結果表明,文中算法可以在很大程度上解決傳統(tǒng)NSGA-Ⅱ的局部收斂和早熟問題,并能有效地提升表情識別的準確性.

關鍵詞：非支配遺傳算法；特征篩選；三維模型；表情識別；概率神經(jīng)網(wǎng)絡

收稿日期：2014-12-08

基金項目：* 福建省自然科學基金資助項目(2012J01260)

作者簡介：胡步發(fā)(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對人臉面部表情特征進行降維處理,然后運用雙層概率神經(jīng)網(wǎng)絡(PNN)模型將處理后的特征進行分類識別,取得了較好的識別效果.Yun等[4]先提取三維人臉上的3D-Gabor特征,再利用PCA對提取后的特征進行降維處理,解決了改進的核典型性相關分析(IKCCA)算法中可能出現(xiàn)的“維數(shù)災難”問題.Lajevardi等[5-6]通過計算各個特征的互信息熵值,并以互信息準則(MIQ)作為特征篩選的判據(jù),獲得了冗余度小、相關性高的表情特征.Kamil等[7-8]基于雙層支持向量機人臉表情識別模型,對三維人臉上的83個特征點進行熵分析,篩選出符合Fisher準則的特征點,并提取這些點的強度值作為特征,解決了由模糊表情帶來的錯誤識別問題.Jaganathan等[9]認為在實際中各個特征集合間的界限并不是十分清晰,不能采用常規(guī)的信息熵法來計算特征的熵值,進而提出了對不同特征集合的模糊熵閾值采用不同的篩選策略,完成了對不同種類特征的篩選工作.這些特征篩選方法均是以降低特征數(shù)量為目標，但實際上特征篩選是一個雙目標控制的過程,在減少特征數(shù)量的同時還必須保證相同表情特征之間的相似程度要高而不同表情之間的差異度要大.傳統(tǒng)的特征篩選方法在設計目標函數(shù)時,一般是將雙目標問題融合在一起組成一個單目標函數(shù),并根據(jù)不同目標增加目標函數(shù)的約束條件，但單純地增加約束條件只可以使單目標函數(shù)取得最優(yōu)解,并不會使該解成為雙目標問題的最優(yōu)解.因此,Soyel等[10]提出了應用于雙目標特征篩選的NSGA-Ⅱ：首先將父代種群和該父代遺傳變異獲得的子代種群組成二倍聯(lián)合種群；然后根據(jù)雙目標函數(shù)構建個體之間的非支配關系,并按照非支配關系對個體進行分層；最后根據(jù)分層結果從二倍聯(lián)合種群中挑選出下一父代種群.從二倍聯(lián)合種群中挑選下一父代種群的過程,就是NSGA-Ⅱ的精英策略,其目的是保留各代大部分的精英個體,但在此過程中,聯(lián)合種群規(guī)模要減少一半,算法在對聯(lián)合種群進行非支配排序后,將聯(lián)合種群中一些擁有優(yōu)秀基因的普通個體排在聯(lián)合種群的后半部分,并選取聯(lián)合種群的前半部分個體作為下一父代種群,這樣會使得下一父代種群中含有該優(yōu)秀基因的個體數(shù)量較少.另外,從下一父代種群遺傳變異獲得下一子代種群的過程,實際上是一個“近親繁殖”的過程,這樣隨著運行代數(shù)的不斷增加,會使得數(shù)量較多的強勢精英個體得以保留,而將數(shù)量較少的弱勢精英個體排斥在父代種群之外,造成部分精英個體丟失.這將導致父代種群未達到算法迭代終止代數(shù)便因成熟度過高而失去種群多樣性,造成算法迭代終止,失去在全局中搜尋最優(yōu)解的能力,出現(xiàn)早熟和局部收斂現(xiàn)象,進而影響特征篩選和后續(xù)三維人臉表情識別的效果.

針對NSGA-Ⅱ存在的問題,文中提出了改進的NSGA-Ⅱ特征篩選算法,以增加含有優(yōu)秀基因的普通個體入選下一父代種群的數(shù)量.首先將父代種群進行遺傳變異操作生成子代種群,然后在原算法的基礎上增加從父代種群挑選父代精英種群的過程,并用該父代精英種群代替原父代種群與子代種群構成聯(lián)合種群,最后根據(jù)雙目標函數(shù)構建個體之間的非支配關系,并按照非支配關系對聯(lián)合種群中的個體進行分層,選出下一父代種群.

1特征篩選方法

人臉表情是由肌肉動作來實現(xiàn)的,不同的表情動作會使得面部不同的特征點發(fā)生不同程度的移動.因此,采用面部特征點間的歐幾里德距離作為圖像的低層視覺特征,可以清晰準確地描述不同表情下人臉各部分特征的變化.文中采用BU-3DFE人臉表情數(shù)據(jù)庫提供的三維人臉表情模型,由該模型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)

文中以降低特征數(shù)量和最大化Fisher值[12]作為目標,以增加同種表情特征之間的聚合度和不同種表情間的差異性.

1.1Fisher準則

令ni表示第i類樣本,c表示類別數(shù)量,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的兩個參數(shù)np和Sp,其中np為種群中支配個體p的個體數(shù)量,Sp為種群中被個體p支配的個體集合,算法的主要步驟如下:

(1)找到種群中所有np=0的個體,并保存到當前集合F1中；

(2)遍歷Si(即F1中個體i所支配的個體集合)中的每個個體k,執(zhí)行nk=nk-1(因為支配個體k的個體p已被存入非支配個體集合F1),如果nk=0則將個體k保存在集合F2中；

(3)將F1中個體作為第1層非支配個體,F2作為當前集合,重復上述操作直到整個種群被分級完成.

1.3擁擠度計算

從聯(lián)合種群中篩選出下一父代種群的過程中,先對聯(lián)合種群進行快速非支配排序,再將聯(lián)合種群中的個體按照非支配關系分好層級.由于每一代父代種群的規(guī)模是不變的,而聯(lián)合種群的規(guī)模大于父代種群的規(guī)模,因此需要對聯(lián)合種群中可以放入下一父代種群的最后一級非支配層的個體進行擁擠度排序.

設種群中的個體數(shù)為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精英策略的排序規(guī)則

聯(lián)合種群在經(jīng)過快速非支配排序和擁擠度的計算后,種群中每個個體i都得到兩個屬性值:非支配序irank和擁擠度值I[i]d.當irankI[j]d時,表示個體i比j更優(yōu)秀,記為ij.也就是說,如果兩個個體i和j所在的非支配層不同,則選取非支配序較小的個體作為下一父代個體,否則選取周圍擁擠度值較大的個體作為下一父代個體.擁擠度的比較只對同一非支配層的個體有效.

1.5改進的NSGA-Ⅱ算法

改進的NSGA-Ⅱ算法共運行兩次精英策略.首先對父代種群運行第1次精英策略,篩選出父代精英種群；然后將父代精英種群與子代種群組合成聯(lián)合種群,并對聯(lián)合種群運行第2次精英策略,獲得下一父代種群.改進NSGA-Ⅱ的步驟如下:

(1)由式(2)獲得候選特征,并以這些特征的組合作為父代個體,構成父代種群.

(2)復制父代種群中所有的個體,形成完全相同的兩份父代種群.

(3)對其中一份父代種群運行第1次精英策略,分別計算每個個體的Fisher值和擁擠度,按照Fisher值和個體中的特征數(shù)量對種群中所有的個體進行快速非支配排序,并結合擁擠度選取排名靠前的個體作為父代精英種群(其大小由父代種群的精英比獲得).

(4)另一份父代種群經(jīng)過交叉、變異后生成子代種群.

(5)將步驟(2)獲得的父代精英種群和步驟(4)獲得的子代種群組合成聯(lián)合種群,對聯(lián)合種群運行第2次精英策略,構造下一父代種群,其中各個父代種群的大小始終與初始父代種群相同.

(6)若運行代數(shù)大于最大代數(shù),則算法結束,否則返回步驟(2)直到達到終止條件為止.

2三維人臉表情識別

文中采用PNN[3,14]進行三維人臉表情識別.PNN由3層構成:①輸入層,它由R個神經(jīng)元組成,主要是將輸入變量送入到隱含層;②隱含層,它采用徑向基函數(shù)計算輸入特征向量和訓練集中各模式的匹配關系,其神經(jīng)元數(shù)目和訓練樣本數(shù)相同;③競爭輸出層,根據(jù)貝葉斯規(guī)則[15]估計未知向量Γ屬于所有可能類別c的概率,而類別ci的概率密度函數(shù)采用Parzen窗函數(shù)密度估計的方法[16]確定.PNN的輸出神經(jīng)元是一種競爭神經(jīng)元,每個競爭神經(jīng)元對應輸出一種數(shù)據(jù)類型,即分類模式,輸出神經(jīng)元的個數(shù)等于所有模式的種類數(shù).神經(jīng)元中概率密度最大的對應輸出為1,其他的輸出為0,從而實現(xiàn)對特征向量的分類識別.

PNN方法的優(yōu)點在于結構簡單、學習速度快、收斂性好,對先驗知識利用率高,對于復雜繁瑣的分類,只要有充足的訓練樣本,都可以獲得較好的分類結果.

3實驗及結果分析

文中采用Matlab軟件和三維人臉表情數(shù)據(jù)庫BU_3DFE在Intel(R)Core(TM)i5 CPU 3.2GHz、4GB內存的電腦上進行實驗.BU_3DFE包含100個人的人臉表情圖像,其中56%為女性、44%為男性,每個人有6種基本表情和1種中性表情.另外,除中性表情外,6種基本表情分別包含4個層次的表情變化強度模型.因此,每個人有25個人臉模型,數(shù)據(jù)庫中有2500個人臉表情模型.

文中實驗選取60個對象,其中男女各占50%,并選取每個對象每種最強表情的人臉表情圖像(除中性表情外).采用十折交叉驗證方法進行實驗,即將數(shù)據(jù)集分成10份,輪流將其中9份作為訓練集,1份作為測試集,并取10次實驗結果的平均值作為最終實驗結果.

3.1父代精英種群規(guī)模的確定

表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三維人臉表情特征篩選

文中實驗將數(shù)據(jù)集分成訓練集(包含54個個體、378個人臉表情圖像)和測試集(包含6個個體、42個人臉表情圖像),利用改進的NSGA-Ⅱ算法篩選出最優(yōu)的特征組合并驗證該改進算法的有效性.首先,根據(jù)最大化Fisher值和最小化特征數(shù)目,利用改進的NSGA-Ⅱ算法獲得篩選特征組合,如圖2(a)所示.可以看出,在特征組合數(shù)為25時,平均Fisher值曲線較為平緩,各種特征組合的候選解逐漸收斂到該曲線,并且出現(xiàn)最大的Fisher值(9.66).因此,選取Fisher值為9.66、篩選特征組合數(shù)為25的特征集合作為篩選特征組合.

圖2兩種算法的特征篩選結果

Fig.2Feature selection results of two algorithms

采用傳統(tǒng)NSGA-Ⅱ算法獲得的特征篩選結果如圖2(b)所示.可以看出,由傳統(tǒng)NSGA-Ⅱ算法獲得的特征篩選結果中,各個候選解在特征組合為23時開始收斂到平均Fisher值曲線,并且出現(xiàn)最大的Fisher值為8.86.

從圖2可知,文中改進NSGA-Ⅱ算法的平均Fisher值曲線整體上較傳統(tǒng)NSGA-Ⅱ算法高,說明改進NSGA-Ⅱ算法獲得的候選解在整體上優(yōu)于傳統(tǒng)NSGA-Ⅱ算法.

(7)

其中,Pt為第t代種群集合.則第t代種群的熵可定義為

(8)

圖3兩種算法的各代種群成熟度曲線

Fig.3Each generation population maturity curves of two algorithms

圖3中,成熟度值為1代表種群不是特別成熟,成熟度值為0代表種群較為成熟.顯然,在29代之前,兩種算法的種群成熟度保持在一個較高的值,種群成熟度低,保持較高的多樣性,未發(fā)生早熟現(xiàn)象.在第29代之后,傳統(tǒng)NSGA-Ⅱ算法的各代種群成熟度開始下降,且隨著算法運行代數(shù)的增加,種群成熟程度越來越高,種群的多樣性也隨之降低;而改進NSGA-Ⅱ算法的成熟度仍然保持在一個較高的位置,下降幅度較小.這說明改進NSGA-Ⅱ算法可以有效地減緩各代種群成熟的速度,使各代種群擁有較高的多樣性,改善傳統(tǒng)NSGA-Ⅱ算法出現(xiàn)的早熟問題.

另外,如圖3所示,當成熟度達到0.1(即虛線與點線的交點處)時,傳統(tǒng)NSGA-Ⅱ算法達到迭代終止條件,可認為種群足夠成熟,終止迭代.即認為在第43代時算法已篩選出最優(yōu)的特征組合,失去了在全局搜索其他可能存在的最優(yōu)解的能力,發(fā)生了局部收斂現(xiàn)象.改進NSGA-Ⅱ算法的成熟度整體上高于傳統(tǒng)NSGA-Ⅱ算法的成熟度,即在整體上降低了各代種群的成熟度,避免了在100代之前發(fā)生因成熟度過高而導致的局部收斂問題,使算法具有全局搜索最優(yōu)解的能力,避免了傳統(tǒng)NSGA-Ⅱ算法的局部收斂問題.

3.3三維人臉表情識別對比實驗

文中算法對各三維人臉表情的識別結果如表2所示.

表2文中算法的三維人臉表情識別結果

Table 23D facial expression recognition results of the proposed algorithm

表情識別結果/個中性憤怒厭惡恐懼高興悲傷驚訝中性52736000370憤怒22517000610厭惡00529304100恐懼370049601156高興00670504290悲傷495501504810驚訝00028500522

文中算法與傳統(tǒng)NSGA-Ⅱ[10]對三維人臉表情的平均識別結果如表3所示.

表3兩種算法的三維人臉表情識別結果比較

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

算法篩選特征數(shù)量Fisher值識別率/%NSGA-Ⅱ算法[10]238.8681.43文中算法259.6685.16

從表3可以看出,文中算法的篩選特征數(shù)、Fisher值及識別率均高于NSGA-Ⅱ算法.文中算法的篩選特征數(shù)高于NSGA-Ⅱ算法的原因是,NSGA-Ⅱ算法的種群出現(xiàn)早熟和局部收斂問題,使得種群中含有優(yōu)秀基因的普通個體發(fā)生丟失,導致傳統(tǒng)NSGA-Ⅱ算法獲得的23個篩選特征不能準確地描述三維人臉的各種表情,從優(yōu)化算法上來看就是沒有獲得最優(yōu)解,這影響了后面表情識別的準確性.上述實驗結果表明,改進算法不僅可以有效改善NSGA-Ⅱ算法中出現(xiàn)的早熟和局部收斂問題,而且獲得的特征篩選組合可以更為準確地描述人臉表情,將改進算法獲得的特征組合應用到三維人臉表情識別中,可以顯著增加識別的準確率.

另外,文中算法與其他相關的特征篩選算法相比,也取得了很好的人臉表情識別效果,結果如表4所示.

表4幾種算法的表情識別結果比較

Table 4Comparison of expression recognition results among several algorithms

算法特征提取方式特征篩選方法分類器人臉數(shù)據(jù)庫識別率/%文獻[4]3D-GaborPCAKCCABU-3DFE84.32文獻[5]GaborMIQLDABU-3DFE81.52文獻[10]幾何距離NSGA-ⅡPNNBU-3DFE81.43文中算法幾何距離改進NSGA-ⅡPNNBU-3DFE85.16

4結論

文中對NSGA-Ⅱ算法的局部收斂和早熟問題進行了分析,并對其精英策略進行了改進,增加了聯(lián)合種群中含有優(yōu)秀基因的普通個體入選下一父代種群的數(shù)量,改善了原算法收斂到非最優(yōu)解和種群過早失去多樣性的問題.文中提出的改進NSGA-Ⅱ算法主要是針對特征篩選中出現(xiàn)的雙目標問題進行優(yōu)化,獲得雙目標問題最優(yōu)解.實際上,三維人臉表情的特征篩選結果還受到其他目標函數(shù)的影響.今后將進一步研究多目標函數(shù)的特征篩選方法,并將其應用到三維人臉表情識別中.

參考文獻：

[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].系統(tǒng)工程與電子技術,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