基于改进蚁群算法的多模态情感识别研究

解迎刚，王志良，杨溢，邵彦娟

(北京科技大学 计算机与通信工程学院，北京，100083)

摘要：本文研究是从基于图像分析、生理信号融合的情感感知入手，利用生理信号检测传感器获得某类情感信号，同时获取通过视频图像分析得到的情感状态，将情感结果与情感机理相关内容对应起来，并将多模态融合的情感感知识别问题抽取为一个组合优化模型，使用优化问题中常用的蚁群算法进行特征选择，找出最适合实际情景交互状态下的情感识别算法，实现高兴、惊奇、厌恶、悲伤、愤怒和恐惧6种基本情绪的情感识别。研究结果表明：用改进的蚁群算法优化组合识别模型，可以有效而快速地求得问题的最优解或近似最优解。

关键词：情感识别；蚁群算法；蚁群系统

中图分类号：TP9          文献标志码：A         文章编号：1672-7207(2011)S1-0137-05

Research of emotion recognition based on improved ant colony algorithm

XIE Ying-gang, WANG Zhi-liang, YANG Yi, SHAO Yan-juan

(School of Computer and Communication Engineering, University of Science & Technology Beijing,

Beijing 100083, China)

Abstract: Physiological signal detection sensor signals are used to obtain certain types of emotion, while a video image analysis accesses to the emotional state of the mechanism of emotion and emotion-related content results are corresponded. Colony optimization algorithm uses emotion recognition to achieve pleasure, surprise, disgust, sadness, anger and fear of six basic emotions. The results show that the ant colony algorithm with a combination of improved recognition model can effectively and quickly obtain the optimal solution or near optimal solution.

Key words: emotion recognition; colony algorithm; colony system

计算机情感识别是情感计算的一个关键问题,已逐步成为人机交互领域的热点和发展方向。情感识别的研究内容包括面部表情、语音、姿势、文本和生理信号^[1]等方面。在当前各类情感识别研究中，针对单一类型特定条件的情感识别研究较多，融合多种情感识别方式实现多模态情感感知识别的研究很少，而且单一类型特定条件的情感识别在实际情景中应用稳定度差、识别率低的问题都会涌现。为此，Picard与Hudlicka就人工情绪与情感计算具有挑战性的6个问题进行了批评与反批评的论述^[2]。AAAI04，SCI04和HCI04等国际会议的人工情绪专题研讨会希望心理学家、生理学家和信息科学家一起就人工情绪的理论与方法进行深入研讨^[3]。本文研究是从基于图像分析、生理信号融合的情感感知入手，利用生理信号检测传感器获得某类情感信号，同时获取通过视频图像分析得到的情感状态，将情感结果与情感机理相关内容对应起来，并将多模态融合的情感感知识别问题抽取为一个组合优化模型，使用优化问题中常用的蚁群算法进行特征选择， 同时改进信息素的更新方式、客户点选择策略，以提高算法的收敛速度和全局搜索能力。找出最适合实际情景交互状态下的情感识别算法，实现高兴、惊奇、厌恶、悲伤、愤怒和恐惧6种基本情绪的情感识别。

1  蚁群算法应用

蚁群算法是受人们对自然界中真实蚁群集体行为研究成果的启发而在近年来提出的一种基于种群的模拟进化算法，属于随机搜索算法，由Dorigo等首先提出^[3-4]。蚁群算法可用来解决各种不同的组合优化问题，特别适合于在离散优化问题的解空间进行多点非确定性搜索，如旅行商问题(TSP)、二次分配问题(QAP)、作业安排调度问题(JSP)等等；此外，在通信网络负载问题和水科学^[5]等应用研究中也被广泛应用。它具有通用性和鲁棒性，是基于总体优化的方   法^[6]。

基于蚁群算法在解决TSP问题^[7]上的特点，将这个过程映射到特征选择的问题上。特征选择可以看成是蚂蚁觅食中寻找最优路径的过程，每个特征相当于蚂蚁觅食时要经过的节点，每个特征有2种标记状态：0或1。0代表该特征没被选中，1代表被选中, 其余的依此类推。这些节点的标记状态1和0组成蚂蚁的觅食路径, 路径(选择的特征子集)的质量按照适应度函数进行评价, 适应度函数值越大，说明路径质量越好(特征子集质量越好)。蚁群间通过残留在每个特征节点上的信息素进行合作，最终寻找到较优的觅食路径(对应较优的特征子集)。将特征选择问题抽象成蚂蚁觅食时寻找最优路径的过程, 运用蚁群优化算法解 决^[8-9]。

2  基于蚁群算法的多模态情感识别的数学模型

多模态情感感知及情感识别见图1。本文通过实验的方法获取原始数据,这些数据包括多人在6种(包括平静、愤怒、恐惧、高兴、悲伤、惊奇)情感状态下检测的2种生理信号及其对应的面部表情图像，计算出每种生理信号的统计值作为原始特征供本文的特征选择, 统计量有均值、中值、方差、一阶差分、二阶差分、最小值、最大值等，每类生理信号选取特征值32个，面部表情图像数据中每种表情8 幅图像，首先采用手动方法剪切背景；然后，为了减少光照的影响，对每幅图像进行了灰度均衡和去噪处理(归一化)，消除了光照对图像的整体影响以及孤立噪声点的干扰，利用积分投影的方法提取面部表情区域(眉区、眼区和嘴巴区域)，最终对每幅表情图像选取24个特征值参与运算。

图1  多模态情感感知及情感识别

Fig.1  Multi-mode perception and emotional recognition emotion

(1) 符号定义以下几种符号：L为特征点总数；q_i为特征点i的权重量纲，i=1, 2, …, L；d _ij为从特征点相近度量纲，i=0, 1, …, L；j=0, 1, …, L；K为情感状态目标；Q_k为情感状态k的匹配度，k=1, 2, …, K；D_k为情感状态转移量纲；n_k为情感分析节点；R_k为情感状态同特征值关联集合。当n_k=0时，R_k=；当  n_k≠0时，

，k=1, 2, …, K  (1)

(2) 约束条件：

① 每个情感状态节点上的情感信息匹配度不超过节点状态值：

≤Q_k，n_k≠0             (2)

② 每次情感状态转移节点值之和不超过特征值的情感状态的匹配度之和：

≤D_k，n_k≠0       (3)

③ 情感匹配评价遍布所有特征点：

0≤n_k≤L

               (4)

(3) 优化目标。根据本文中描述的多模态情感感知信息进行情感识别的优化目标，列出优化目标的数学形式：

               (5)

3  蚁群算法的改进

遗传算法的操作算子是遗传算法的核心内容，将复制、交叉、变异这些遗传算子引入蚁群算法中，以提高算法的收敛速度和全局搜索能力^[10]。

3.1  复制

遗传算法中，复制的主要思想是认为父代中的优质个体可能更接近全局最优解，应该在子代中继承并继续进化。复制操作使得父代中优质的个体能够在子代中得以保存，避免交叉变异等操作导致优质个体在种群中丢失。在蚁群算法中，在每一代搜索完成后，将当前父代中最优的解复制到子代中，使得最优的个体能在子代中继续积累信息素，这样能加快算法的收敛速度^[11]。

3.2  交叉

交叉操作是遗传算法中增加种群多样性，防止算法早熟、停滞的操作。在蚁群算法中引入交叉操    作，可以有效地扩大搜索空间，避免算法陷入局部最优解^[12-13]。

在蚁群算法每一代搜索完成之后，将其中的最优解和次优解进行编码交叉操作，交叉规则如下：

(1) 假设2组编码分别是S1和S2，首先随机生成交叉段的长度和交叉段起始位置；

(2) 找出S1和S2中的交叉段，假设S1：P₁|P₂|P₃，S2：Q₁|Q₂|Q₃，P₂和Q₂分别是S1和S2的交叉段；将Q₂插入S1中，位于P₂前面，这样形成新的编码S3：P₁|Q₂|P₂|P₃；

(3) 在S3中，删除P₁，P₂和P₃中与Q₂重复的编码，形成交叉编码S3；

(4) 对S2采用同样的方法，生成新的编码S4；

(5) 比较S1，S2，S3和S4的结果，选出最优的2组编码并保存。

3.3  变异

变异操作也是增加种群多样性的一种进化手段。适度的变异既能保持种群内个体的多样化，又能提高算法的效率^[14]。

在蚁群算法中，在完成交叉操作后，对种群中最优个体进行变异操作，操作方法为：

(1) 随机生成变异次数N；

(2) 随机生成2个不同的自然数n₁，n₂＞1(第1位不变，保证编码以物流中心为起点)；

(3 )在最优个体的编码S中，将第n₁位和第n₂位的编码对调；

(4) 重复(2)和(3)N次，生成新的编码S′；

(5) 比较S和S′的结果，保存较优解。

3.4  改进后蚁群算法流程图

结合改进后的蚁群算法，可以得到基于改进后蚁群算法优化问题的算法流程图，见图2。

图2  蚁群算法流程图

Fig.2  Ant colony algorithm flow chart

3.5  实验与计算

以下为本次研究中应用的改进算法的部分代码：

int ACSAnt::Choose()

{   int nextNote = -1;

    double q = rand()/(double)RAND_MAX; //如果q <= q0，按先验知识，否则则按概率转移，

    if (q <= qzero)

    {   double probability = -1.0; //转移到下一节点的概率

        for(int i = 0; i < N; i++)

     { if (1 == allowed[i]) //去掉禁忌表中已走过的节点，从剩下节点中选择最大概率的可行节点

            { double prob = antColony->Transition (cururentNote, i);

                if (prob  > probability)

                {   nextNote = i;

                    probability = prob;

                }    }

        } }   else

    { double p = rand()/(double)RAND_MAX; //生成一个随机数, 用来判断落在哪个区间段

        double sum = 0.0;

        double probability = 0.0; //概率的区间点, p落在哪个区间段, 则该点是转移的方向

         for(int i = 0; i < N; i++)

        {    if (1 == allowed[i])

            {   sum += antColony->Transition (cururentNote, i);

            }    }

        for(int j = 0; j < N; j++)

        {    if (1 == allowed[j] && sum > 0)

            {   probability += antColony-> Transition(cururentNote, j)/sum;

                if (probability >= p || (p > 0.9999 && probability > 0.9999))

                {  nextNote = j;   break;

                }  }     }  }

    return nextNote;   }

采用经过改进的蚁群算法先对生理信号识别后的同组图像进行识别，在进行多组优化，进行降维与分类，得到综合下来可以达到86.5%的识别率，与生理信号的情感识别和面部图像的情感相比均明显提高。3种方式得到的识别率比较如图3所示。

图3   3类方法识别效果的比较

Fig.3  Three methods of recognition effect comparison

4  结论

(1) 从基于图像分析、生理信号融合的情感感知入手，利用生理信号检测传感器获得某类情感信号，同时获取通过视频图像分析得到的情感状态，将情感结果与情感机理相关内容对应起来，并将多模态融合的情感感知识别问题抽取为一个组合优化模型，使用优化问题中常用的蚁群算法进行特征选择。仿真结果表明：在识别率和特征降维方面均达到了较好的效果。

(2) 针对蚁群算法容易陷入局部最优的不足，下一步的工作是利用蚁群算法较好的鲁棒性，与其他的智能优化算法相结合，并与其他算法的结果相结合，统计分析各种情感的最优特征组合，以达到更好的识别效果。

参考文献：

[1] XIE Lun, WANG Zhi-liang. Emotional gait generation for a humanoid robot[J]. International Journal of Automation and Computing, 2010(1): 64-69.

[2] CHANG Yun-tao, PENG Guo-xiong. Urban arterial road coordinate control based on genetic algorithm[J]. Journal of Traffic and Transportation Engineering, 2003, 3(2): 106-112.

[3] SHI Lin, WANG Zhi-liang, LI Zhi-gang. Affective model for intelligent virtual agent based on PFCM[J]. International Journal of Virtual Reality, 2008, 7(3): 49-52.

[4] 徐宁, 李春光, 张健. 几种现代优化算法的比较研究[J]. 系统工程与电子技术, 2002, 24(12): 101-104.
XU Ning, LI Chun-guang, ZHANG Jian. Studies on some modern optimization algorithms[J]. Systems Engineering and Electronics, 2002, 24(12): 101-104.

[5] 杨瑞臣, 云庆夏. 改进的蚁群算法在矿山物流配送路径优化中的研究[J]. 中国矿业, 2004, 28(6): 16-18.
YANG Rui-chen, YUN Qing-xia. Study of improved ant colony system in the routing optimization for physical distribution in mines[J]. China Molybdenum Industry, 2004, 28(6): 16-18.

[6] Zhang X Y, Wang Z L, Nagai M. Emotion and speech interaction of service robot based on artificial psychology[C]//The 6th World Congress on Intelligent Control and Automation. Dalian, China, 2006: 9174-9177.

[7] 马军建, 董增川, 王春霞. 蚁群算法研究进展[J]. 河海大学学报: 自然科学版, 2005, 33(2): 139-143.
MA Jun-jian, DONG Zeng-chuan, WANG Chun-xia. Advances in research of ant colony algorithm[J]. Journal of Hohai University: Natural Sciences, 2005, 33(2): 139-143.

[8] 张维泽, 林剑波. 基于改进蚁群算法的物流配送路径优化[J]. 浙江大学学报, 2008, 42(4): 575-581.
ZHANG Wei-ze, LIN Jian-bo. Based on improved ant colony optimization of logistics and distribution paths[J]. Journal of Zhejiang University, 2008, 42(4): 575-581.

[9] WANG Zhi-liang. Artificial psychology and artificial emotion[J]. Intelligent Systems Journal, 2006, 1(1): 38-43.

[10] 鲁舜, 刘光远. 用自适应蚁群算法的生理信号情感状态识别[J]. 计算机应用, 2009, 29(6): 146-149.
LU Shun, LIU Guang-yuan. Ant colony algorithm with adaptive emotional state recognition of physiological signals[J]. Computer Applications, 2009, 29(6): 146-149.

[11] XIE Lun. Study and realization of internet-assisted bidding system for construction project[C]//Proceedings of the 21st Chinese Control and Decision Conference. Guilin, China, 2009: 4440-4445.

[12] 解迎刚, 王志良. 人脸与眼部检测及其在情感识别中的应用[C]//第二十五届中国控制会议. 哈尔滨, 中国, 2006: 1942-1946.
XIE Ying-gang, WANG Zhi-liang. Face and eye detection of emotional identification[C]//The 25th Chinese Control Conference Proceedings. Harbin, China, 2006: 1942-1946.

[13] Lu X G, Wang Y H. Combining classifiers for face recognition[C]//Proceedings of the IEEE International Conference on Multimedia and Expo. Baltimore, USA, 2003, III: I3-I6.

[14] 詹士昌. 蚁群算法及其在连续性空间优化问题中的应用[J]. 杭州师范学院学报: 自然科学版, 2004, 13(5): 395-399.
ZHANG Shi-chang. The application of ant colony algorithm in the continuous space optimization problems[J]. Journal of Hangzhou Teachers College: Natural Science Edition, 2004, 13(5): 395-399.

(编辑 陈灿华)

收稿日期：2011-04-15；修回日期：2011-06-15

基金项目：国家高技术发展计划(“863”计划)项目(2007AA04Z218)

通信作者：解迎刚(1978-)，男，宁夏贺兰人，博士，讲师，从事人工心理相关研究；电话：13691117939；E-mail: yinggangxie@163.com