馮開平，賴思淵

(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006)

0 引言

人臉表情識(shí)別主要涉及圖像處理與模式識(shí)別兩個(gè)方面，在教育、游戲[1]、醫(yī)學(xué)[2]、動(dòng)畫[3-4]等領(lǐng)域都有著廣泛應(yīng)用。表情識(shí)別過程分為特征提取與分類識(shí)別兩部分，常用的特征提取算法有PCA[5]、LBP[6]以及Gabor小波變換[7]。好的分類模型能夠提高表情識(shí)別準(zhǔn)確性，降低計(jì)算復(fù)雜度。常用于表情識(shí)別的分類方法有K最近鄰(KNN)、支持向量機(jī)(SVM)[8]、神經(jīng)網(wǎng)絡(luò)(NN)[9-10]、分類樹(CT)[11]與稀疏表示(SP)[12-13]等。Qite Wang等[14]提出一種基于PCA與KNN的表情識(shí)別方法，并用于在車聯(lián)網(wǎng)中識(shí)別路怒癥、疲勞駕駛與酒后駕駛狀態(tài)。卷積神經(jīng)網(wǎng)絡(luò)[15]雖然分類準(zhǔn)確率高，但需要大量參數(shù)，而且當(dāng)數(shù)據(jù)出現(xiàn)部分缺失時(shí)容易發(fā)生錯(cuò)誤。分類樹計(jì)算復(fù)雜度不高，能夠處理一定的數(shù)據(jù)缺失，但對(duì)于噪聲數(shù)據(jù)比較敏感，容易導(dǎo)致過擬合。針對(duì)SVM計(jì)算量大以及KNN分類精度不高問題，王小虎等[16]提出一種組合FSVM與KNN的方法，通過區(qū)分度函數(shù)判斷輸入樣本的區(qū)分程度，然后自適應(yīng)地選擇分類器；Zineb等[17]提出一種基于一維隱馬爾可夫模型的方法，首先通過小波變換提取特征，然后通過線性判別分析法降低數(shù)據(jù)冗余度，從而減少計(jì)算量。

本文在分析上述方法后，提出一種結(jié)合加權(quán)KNN和RF[18]的分類器。首先通過人臉對(duì)齊方法SDM[19]將訓(xùn)練樣本的人臉特征點(diǎn)提取出來，生成一張平均特征點(diǎn)分布圖，然后計(jì)算測(cè)試樣本與平均人臉特征點(diǎn)之間的距離，最后根據(jù)距離選擇分類器，利用加權(quán)KNN算法對(duì)表現(xiàn)程度弱的樣本進(jìn)行分類，其余樣本交由RF處理。實(shí)驗(yàn)結(jié)果證明，該方法具有一定可行性，在改善分類效果的同時(shí)，能夠減少KNN算法的計(jì)算量。

1 相關(guān)算法描述

1.1 加權(quán)KNN算法基本原理

KNN算法是一種簡(jiǎn)單、容易實(shí)現(xiàn)的分類方法，尤其適用于多分類問題。其基本原理是給定訓(xùn)練集T，其中的每個(gè)樣本都有一個(gè)類別，輸入一個(gè)沒有分類的測(cè)試數(shù)據(jù)，遍歷所有樣本，計(jì)算測(cè)試數(shù)據(jù)與樣本之間的距離，然后選取距離最近的k個(gè)樣本，將k個(gè)樣本中出現(xiàn)最多的類別作為測(cè)試數(shù)據(jù)類別。雖然KNN算法易于理解，但當(dāng)訓(xùn)練集中的樣本類別不均勻時(shí)，如一個(gè)類的樣本較多，而其它類別樣本過少，則容易使分類結(jié)果受到影響。另外當(dāng)訓(xùn)練集過大時(shí)，計(jì)算量也會(huì)比較大，從而降低了分類效率，不適合直接用于表情識(shí)別。針對(duì)上述情況，可以采取加權(quán)方式改善表情識(shí)別的分類效果。

在特征提取階段，將人臉的68個(gè)特征點(diǎn)提取出來，如圖1所示。從圖中可以看出，不同特征點(diǎn)對(duì)于表情的貢獻(xiàn)度不同，如果同等對(duì)待每個(gè)特征點(diǎn)，則可能會(huì)對(duì)最后的分類結(jié)果造成影響，從而降低識(shí)別率。例如每個(gè)人的輪廓不同，因此可以認(rèn)為輪廓對(duì)表情的貢獻(xiàn)度較低，計(jì)算距離時(shí)可以刪除該部分特征點(diǎn)，降低數(shù)據(jù)維度，以達(dá)到減少計(jì)算量的目的。

圖1 不同表情特征點(diǎn)分布

用歐式距離計(jì)算兩個(gè)樣本之間的距離D：

(1)

其中，I為特征點(diǎn)集合，x、y、w、v分別為測(cè)試樣本與訓(xùn)練樣本的特征點(diǎn)坐標(biāo)。

最常見的加權(quán)方式是用距離D的倒數(shù)作為權(quán)重，權(quán)重W計(jì)算方式如下：

(2)

其中，C為一個(gè)常數(shù)，因?yàn)闇y(cè)試樣本有可能與訓(xùn)練樣本完全一樣或相當(dāng)接近，將導(dǎo)致權(quán)重趨于無窮大，因此在求距離倒數(shù)時(shí)需要額外加上一個(gè)常數(shù)。

距離倒數(shù)加權(quán)方法的優(yōu)點(diǎn)在于計(jì)算簡(jiǎn)單，但其對(duì)于較近的樣本會(huì)分配很大的權(quán)重，對(duì)稍遠(yuǎn)的樣本分配權(quán)重時(shí)則衰減很快。該加權(quán)方法在表情識(shí)別中效果一般，對(duì)噪聲數(shù)據(jù)變得較為敏感。

還有一種常用的加權(quán)方式是使用高斯函數(shù)加權(quán)，其公式如下：

(3)

其中，a為曲線高度，b為曲線中心線在橫軸的偏移，c為半峰寬度。當(dāng)a=1，b=0，c=0.5時(shí)，高斯函數(shù)的函數(shù)圖像如圖2所示。

圖2 高斯函數(shù)圖像

從圖2中可以看出，當(dāng)距離等于0時(shí)，權(quán)重獲得最大值1，隨著距離增加，權(quán)重逐漸減少，但是永遠(yuǎn)不等于0，因而能夠滿足實(shí)際應(yīng)用需要。實(shí)驗(yàn)結(jié)果證明，在本文中使用高斯函數(shù)加權(quán)時(shí)的分類效果優(yōu)于距離倒數(shù)加權(quán)。

首先對(duì)求得的樣本距離從小到大進(jìn)行排序，選擇距離最近的k個(gè)訓(xùn)練樣本進(jìn)行加權(quán)。設(shè)與第n個(gè)訓(xùn)練樣本屬于同類的概率為Pn，通過以下公式計(jì)算Pn：

(4)

其中，Wn為第n個(gè)樣本權(quán)重，分母為距離最近的k個(gè)樣本權(quán)重之和。

1.2 隨機(jī)森林基本原理

隨機(jī)森林是通過隨機(jī)構(gòu)建多棵決策樹對(duì)樣本進(jìn)行訓(xùn)練與預(yù)測(cè)的一種分類器，其中的每棵決策樹都按照如下規(guī)則生成：①設(shè)樣本集大小為N，對(duì)于隨機(jī)森林中的每棵決策樹，隨機(jī)有放回地從訓(xùn)練集中抽取N個(gè)樣本，作為決策樹的訓(xùn)練集；②設(shè)訓(xùn)練集中的每個(gè)樣本特征維度為M，隨機(jī)從M個(gè)特征中選擇m個(gè)特征子集，其中m<

2 加權(quán)KNN結(jié)合隨機(jī)森林算法

2.1 算法描述

加權(quán)KNN算法能夠有效識(shí)別表現(xiàn)力較弱的表情，但是如果樣本過多，則會(huì)導(dǎo)致KNN算法計(jì)算量增大，而隨機(jī)森林訓(xùn)練速度較快，能在不作特征選擇的前提下有效處理高維數(shù)據(jù)，并且對(duì)特征的重要性進(jìn)行排序。為了充分結(jié)合兩者的優(yōu)越性，提高人臉表情識(shí)別率與識(shí)別速度，同時(shí)降低計(jì)算復(fù)雜度，本文提出一種加權(quán)KNN與隨機(jī)森林相結(jié)合的分類器。該分類器將JAFEE表情數(shù)據(jù)庫(kù)中的語(yǔ)義程度評(píng)分作為樣本的一部分特征，通過判斷測(cè)試樣本是否屬于表現(xiàn)程度較弱的表情進(jìn)行分類器選擇，以充分發(fā)揮改進(jìn)KNN算法的優(yōu)勢(shì)，識(shí)別表現(xiàn)程度較弱的表情，同時(shí)利用魯棒性較好的隨機(jī)森林對(duì)其它表情進(jìn)行分類，算法基本流程如下：

(1)根據(jù)語(yǔ)義程度評(píng)分r對(duì)樣本從低到高進(jìn)行排序，為了防止樣本不均勻?qū)е碌姆诸惾毕?，需要保證加權(quán)KNN算法中樣本的平衡性，按比例從排序結(jié)果中抽取樣本，根據(jù)樣本的特征點(diǎn)分布，計(jì)算坐標(biāo)平均值，然后生成一張平均特征點(diǎn)分布圖，如圖3所示。

圖3 生成平均特征點(diǎn)分布

(2)按下列步驟隨機(jī)抽取樣本，訓(xùn)練d棵決策樹作為弱分類器：

計(jì)算每個(gè)特征點(diǎn)的基尼不純度(Gini impurity)，Gini值越大，則意味著分裂后的總體內(nèi)包含的類別越雜亂。對(duì)于樣本集S，Gini值計(jì)算公式如下：

(5)

其中，pk表示樣本集分類結(jié)果中第k個(gè)類別出現(xiàn)的概率。

為了選擇最好的特征進(jìn)行分裂，加強(qiáng)隨機(jī)森林中每棵決策樹的分類能力，從而使隨機(jī)森林獲得最佳分類效果，本文選擇最小基尼增益值GiniGain作為決策樹分裂方案。GiniGain計(jì)算公式如下：

(6)

其中，S1、S2為樣本集S的兩個(gè)樣本子集，n1、n2為兩個(gè)樣本子集的數(shù)量，N為樣本容量。

對(duì)于樣本S中的特征，計(jì)算任意可能的特征值組合的GiniGain，最后選擇GiniGain最小的特征值組合作為決策樹當(dāng)前節(jié)點(diǎn)的最優(yōu)分裂方案，并聯(lián)合訓(xùn)練出多棵決策樹作為隨機(jī)森林分類器。

(3)計(jì)算測(cè)試樣本與新生成特征分布圖的距離，當(dāng)距離小于閾值t時(shí)，認(rèn)為該測(cè)試樣本屬于表現(xiàn)程度較弱的一類，選擇加權(quán)KNN算法對(duì)其進(jìn)行分類；當(dāng)距離大于t時(shí)，選擇隨機(jī)森林進(jìn)行分類。當(dāng)選擇加權(quán)KNN算法進(jìn)行分類時(shí)，輸出分類結(jié)果。算法流程如圖4所示。

圖4 算法流程

2.2 分類器有效性驗(yàn)證

將分類器用于測(cè)試樣本之前需要驗(yàn)證其有效性，以避免測(cè)試時(shí)出現(xiàn)過擬合現(xiàn)象。在KNN算法中，k的取值對(duì)分類效果有很大影響，若k值太小會(huì)造成過擬合現(xiàn)象，導(dǎo)致分類器分類錯(cuò)誤。因此，Ghosh[20]提出一種基于貝葉斯的方法選擇較優(yōu)的k值，但是計(jì)算比較復(fù)雜。本文采用十折交叉驗(yàn)證方法確定k值。

十折交叉驗(yàn)證是驗(yàn)證分類器泛化性能的一種方法，其基本思想是通過對(duì)訓(xùn)練集進(jìn)行分組，將其平均分為K個(gè)子集，每個(gè)子集分別作為一次測(cè)試集，其它K-1個(gè)子集作為訓(xùn)練集，從而得到K個(gè)分類模型，然后用K個(gè)模型分類準(zhǔn)確率的平均數(shù)評(píng)估分類器性能。通過十折交叉驗(yàn)證能夠?yàn)樗惴ㄟx擇一個(gè)較優(yōu)的參數(shù)k，以避免出現(xiàn)過擬合現(xiàn)象。

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)中采用JAFFE表情數(shù)據(jù)庫(kù)，表情庫(kù)中包含10個(gè)日本女性的7種不同表情，包括生氣、恐懼、厭惡、高興、驚訝、悲傷和中性，每人同種表情的圖像有3～4幅。實(shí)驗(yàn)中，從每種表情中隨機(jī)選取22～23幅共160幅圖像作為訓(xùn)練集，然后將160幅圖像平均分為10組進(jìn)行交叉驗(yàn)證，評(píng)估分類模型效果并且確定加權(quán)KNN算法中的參數(shù)k，每次測(cè)試時(shí)從剩下圖像中隨機(jī)選取20幅圖像作為測(cè)試集。為了對(duì)比分類效果，分別采用KNN、RF、SVM與本文方法對(duì)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。4種分類器表情識(shí)別率如表1所示。

表1 4種分類器表情識(shí)別率 單位/%

圖5為進(jìn)行十折交叉驗(yàn)證時(shí)不同加權(quán)方法的錯(cuò)誤率。從圖中可以看出，高斯函數(shù)加權(quán)的識(shí)別錯(cuò)誤率都低于倒數(shù)加權(quán)，因此認(rèn)為高斯函數(shù)加權(quán)的方式優(yōu)于倒數(shù)加權(quán)。同時(shí)隨著k值增加，錯(cuò)誤率趨于穩(wěn)定，當(dāng)k為6時(shí)錯(cuò)誤率最低，但是隨著k值繼續(xù)增加，噪聲越來越大，導(dǎo)致分類模型效果變差。

圖5 十折交叉驗(yàn)證錯(cuò)誤率

4 結(jié)語(yǔ)

本文提出的加權(quán)KNN結(jié)合隨機(jī)森林的分類器在表情識(shí)別領(lǐng)域優(yōu)于普通的KNN和SVM方法，其具有以下特點(diǎn)：①減少了訓(xùn)練模型參數(shù)，通過加權(quán)方法改善了KNN算法分類效果；②與隨機(jī)森林相結(jié)合，減少了KNN算法的計(jì)算量并且提高了隨機(jī)森林的可調(diào)控性，充分發(fā)揮了隨機(jī)森林魯棒性強(qiáng)、訓(xùn)練速度快的優(yōu)點(diǎn)，降低了計(jì)算復(fù)雜度。盡管通過在JAFFE表情庫(kù)中的實(shí)驗(yàn)證明了該算法的可行性與穩(wěn)定性，但若只考慮人臉特征點(diǎn)分布仍然不太嚴(yán)謹(jǐn)，因?yàn)槊總€(gè)人的臉型存在一定差異，因此下一步研究中需要考慮融合其它特征信息。