刘悦婷,　张燕

( 兰州文理学院 电子信息工程学院， 甘肃 兰州 730000 )



CMSFLA-SVM算法在人脸识别中的应用

刘悦婷,张燕

( 兰州文理学院 电子信息工程学院， 甘肃 兰州 730000 )

摘要：针对蛙跳算法(shuffled frog leaping algorithm，SFLA)易陷入局部最优，且求解精度较低的问题，提出一种交叉变异的蛙跳算法(crossover and mutation shuffled frog leaping algorithm，CMSFLA).该算法在全局搜索中，青蛙个体依适应度值而选择不同概率分别进行交叉和变异操作.将改进的蛙跳算法CMSFLA训练支持向量机(support vectors machines，SVM)，并将其用于人脸识别中.ORL和CAS-PEAL-R1人脸库仿真实验结果表明，与ASFLA-SVM和KSFLA-SVM方法相比，CMSFLA-SVM算法对人脸识别率更高，速度更快，且在训练样本不足时，其识别效果仍能保持良好. 支持向量机； 蛙跳算法； 交叉； 变异； 人脸识别； 最优解 TP391

文献标识码：A

0引言

人脸识别是生物识别领域的重要研究方向.在人脸识别技术中，各种人脸特征选择、特征提取方法和分类器的选择是决定识别效果的关键，目前常用的人脸识别分类器有最近邻距离法、人工神经网络法和支持向量机技术(SVM)[1].最近邻距离分类器是最基本的分类法，被广泛应用于各领域，但该方法在训练样本较多时会产生很高的错误率；人工神经网络分类器虽可解决非线性问题，但其依据风险最小化原则，易出现“过学习”现象，导致泛化能力较差；支持向量机技术基于结构风险化原理，具有数学表达式简洁和泛化能力良好的优点，在解决分类、非线性和高维模式识别问题中表现出良好的特性.

一般SVM训练方法是将问题分解为许多子问题，然后再对子问题逐一优化，但该方法运算结果只有一个次优解，并且分类速度较低[2].近年来，许多学者提出用仿生优化算法训练SVM，以提高最优解的质量及求解速度，例如：文献[3]采用遗传算法优化了SVM参数，文献[4]提出了用粒子群算法(particle swarm optimization，PSO)训练SVM.这些算法虽然在一定程度上提高了SVM的分类效果，但训练样本数较多且维数较高时其效果仍不理想.为此，有学者用蛙跳算法(SFLA)训练SVM[5]，但由于基本SFLA算法在全局搜索中，青蛙个体只是进行混合后再分组，与上下代的信息传递较少；因此，本文引入了交叉变异的蛙跳算法(CMSFLA)，该算法能够依据适应度而选择不同的概率来分别进行交叉和变异操作，既可以继承上一代的良好信息，又可以小概率变异，从而提高种群的多样性，便于种群找到最优解.本文用CMSFLA训练SVM，将其用于人脸识别中，并对其仿真结果进行了验证和对比.

1支持向量机

支持向量机是模式识别的主流分类器，对非线性、高维数的小样本人脸识别问题有很好的分类效果.其在结构风险最小化的基础上，先构造最优超平面，使分类误差达到最小，再通过适当的核函数将非线性数据变换到高维空间，从而获得最优分类面[6].

给定训练样本(xi，yi) (i=1,2,…,n)， x∈Rd， yi∈{+1,-1}， 满足

yi[(wxi)+b]-1≥0， i=1,2,…,n.

(1)

(2)

满足约束条件

(3)

0≤ai≤C ， i=1,2,…,n,

(4)

其中C为线性不可分样本的分类错误惩罚参数， ai为每个训练样本的Lagrange乘子， k(xi,xj)为核函数.

求解以上二次规划问题，可从训练样本中得到对应ai≠0的向量，即支持向量，由它们决定最优分类面：

(5)

式中s为支持向量集.

2基本蛙跳算法

2003年，MuzaffarEusuff等提出了群体智能优化算法——蛙跳算法(SFLA)[7].该算法结合了模因算法和粒子群算法的优点，具有寻优能力强和易于实现的优点，已被成功应用于资源网络优化问题、聚类问题、流水调度问题和考试安排等领域[7].

2.1　初始群体的生成

随机生成具有F只青蛙的初始群体(X1,X2,…,XF)， 第i只表示为Xi=(xi1,xi2,…,xi D)， 其中D为解的维数.初始群体生成后，将青蛙按照适应度值进行降序排列，然后再将青蛙群平均分配到m个子群，每个子群有n只，满足F=m×n.

2.2　局部搜索

子群t次搜索后，最优适应度和最差适应度的青蛙分别表示为Xb(t)、Xw(t)， 群体最优适应度的青蛙表示为Xg(t).每个子群进行局部搜索后对子群中的Xw(t)进行更新操作，更新策略为：

Di=rand()·(Xb-Xw);

(6)

Xw=Xw(当前位置)+Di, -Dmax≤Di≤Dmax,

(7)

式中Di是分量i上移动的距离，rand()是0到1的随机数， Dmax为青蛙允许运动的最大距离.

进行更新后，若得到的解Xw优于原来的解Xw(当前位置)，则用它取代原种群的解；否则用Xg取代Xb， 重复执行式(6)和(7)；若仍无改进，则随机产生新解取代原来的Xw.

2.3　全局搜索

综合青蛙各子群的局部模因信息有利于信息在全局中交流，可使算法向最优解的方向继续搜索[8-9].当所有子群迭代结束后，将所有子群混合，依适应度值降序排列，再平均划分为子群，继续进行局部搜索，直到满足混合迭代次数，算法停止.

3交叉变异的蛙跳算法训练支持向量机(CMSFLA-SVM)

3.1　交叉变异的蛙跳算法(CMSFLA)

为了便于种群找到最优解，本文借鉴了遗传算法中交叉和变异的思想，其中交叉概率和变异概率的取值是决定算法收敛性能的关键.交叉概率过大，新个体产生的速度越快，但会破坏适应度值优的个体；交叉概率过小，搜索过程缓慢，可导致算法停止.变异概率过大，算法会变成纯粹的随机搜索；变异概率过小，则很难产生新个体.因此，本文提出交叉概率和变异概率的大小随着适应度值改变的自适应交叉和变异策略，如式(8)、(9)所示：

(8)

(9)

式中Pc为交叉概率，Pm为变异概率，f为交叉两个体中较大的适应度，f′为变异个体的适应度，fmax为种群中最大适应度，favg为种群中平均适应度，k1和k2分别为常数.当种群中各个体的适应度值趋向一致或趋于局部最小时，分别增大交叉概率和变异概率；而当种群中各个体的适应度值分散时，分别减小交叉概率和变异概率.

3.2　CMSFLA算法训练SVM

SVM的训练即为解决二次规划问题，求解最优的、不为零、非负的训练样本点Lagrange乘子ai， 从而求出权值w和b以获取分类面.

Lagrange乘子ai=(a1,a2,…,an)是一个n维向量，因此二次规划问题(式(2))可用CMSFLA算法求解.本文用动态反向学习法初始化群体，并引入交叉变异概率来提高最优解的质量，获取最优ai， 提高SVM的训练速度和性能.采用CMSFLA算法训练SVM的步骤为：

步骤1初始化参数:青蛙群总数F， 子群数m， 子群内青蛙数n， 子群内搜索次数Ne， 混合迭代次数N， 变异和交叉概率中的常数k1和k2；

步骤2按照CMSFLA方法初始化青蛙群，使每个青蛙产生一个满足约束条件(3)和(4)的ai值；

步骤3用式(2)计算每个青蛙个体的目标函数值，依目标函数值对青蛙群体降序排列，分为m个子群；

步骤4确定局部搜索的Xb、Xw及全局最优Xg.按式(6)、(7)进行更新，直到设定的子群内搜索次数达到Ne，将更新后的各子群混合，按式(8)、(9)选择概率值进行交叉和变异操作后取代初始群体；

步骤5若所有青蛙的全局最优值满足库恩-塔克(Kuhn-Tucker)条件或达到混合迭代次数N， 则迭代终止，输出结果，否则返回步骤3.其中Kuhn-Tucker条件为:

(10)

4仿真实验

为验证CMSFLA-SVM算法的有效性，实验分别采用ORL和CAS-PEAL-R1人脸库作为测试对象，编写Matlab程序，并与ASFLA-SVM[10]和KSFLA-SVM[11]算法进行比较.测试中，参数取值与文献[12]相同，种群中青蛙总数F=200，子群数m=20，子群内搜索总次数Ne=10，混合搜索总次数N=400，变异和交叉概率中的常数k1=0.5，k2=0.5.

4.1　ORL人脸库测试

ORL人脸库[13]由40人的人脸图像组成，其中每个人有10幅不同图像，该图像是每个人在不同时间、不同表情、不同光照及不同姿态下获取的，每幅图像为256级灰度、92×112像素，其中某人的10幅图像如图1所示.本实验选择40人的4种测试模式(对每个人)： 1) Sub1：前5幅测试，后5幅训练； 2) Sub2：后5幅测试，前5幅训练； 3) Sub3：图像名编号偶数的5幅测试，其余5幅训练； 4) Sub4：图像名编号奇数的5幅测试，其余5幅训练.

图1　ORL库中某人的10幅图像

测试结果如图2、图3所示.由图2可知，随特征维数的增加，3种方法的识别率都有所提高，但CMSFLA-SVM算法的识别率最高(97.5%)，比其他两种方法高0.5%~1.6%.因此，说明CMSFLA-SVM算法的识别性能优于ASFLA-SVM和KSFLA-SVM算法，同时也说明了CMSFLA算法训练SVM在人脸识别应用中的有效性.图3显示了在不同ORL训练组中应用不同的交叉变异概率获取的不同人脸识别性能.从图3可知，在Sub3和Sub4组中采用交叉变异概率提高了基本SFLA算法最优解的性能，用其训练SVM后，可明显提高人脸识别性能，这说明将交叉变异概率引入到SFLA算法中是有效的.表1显示了不同ORL训练组的人脸识别性能，实验使用的特征维数为40.由表1可知，平均识别1副人脸图像，KSFLA-SVM算法的识别时间为0.223 75s，识别率为96.275%；ASFLA-SVM算法的识别时间为0.203 75s，识别率为96.4%；CMSFLA-SVM算法的识别时间为0.199 75s，识别率为96.675%.这说明在SFLA算法的全局搜索中引入交叉变异概率可以提高最优解的精度，从而提高人脸识别率，因此CMSFLA-SVM算法的识别性能优于其他两种算法.

图2　3种方法的识别率随特征维数的变化

图3　CMSFLA-SVM算法的识别性能

表1　不同ORL训练组的人脸识别性能

4.2　CAS-PEAL-R1人脸库测试

CAS-PEAL-R1人脸数据库[13]是CAS-PEAL人脸库的共享版，包括人脸的正面子库和姿态子库共计1 040人的30 900幅图像，其中正面子库包括标准、表情、光照、饰物、背景、距离和时间等共计1 040人的9 060幅图像，姿态子库包括1 040人的21 840幅图像.本实验选取100人，每个人选取5幅表情(Open mouth、Frown、Close eyes、Smile and Surprise)和1副标准(Normal)共6幅，总共600幅人脸图像，每幅图像大小为360×480.所选其中某人的表情和标准的6幅测试图像如图4所示，佩戴饰物的6幅测试图像如图5所示.

图4　CAS-PEAL-R1库中表情和标准的人脸图像

图6　3种算法的识别率随特征维数的变化

用如图4所示每个人任意3幅图像作测试，其余3幅作训练，测试结果如图6所示.由图6可知，CMSFLA-SVM算法的识别率高于其他两种方法.当特征维数为5时，CMSFLA-SVM算法的识别率为93.8%；当特征维数为40时，CMSFLA-SVM算法的人脸识别率达到97.7%：因此，说明CMSFLA-SVM算法优于其他两种方法，并且CMSFLA-SVM算法对脸部表情变化具有很好的鲁棒性，说明用CMSFLA算法训练SVM效果良好.

用如图5所示佩戴饰物的100人的人脸图像作为测试对象，取特征维数为60，训练样本不足时3种方法的平均识别率如表2所示.表2中“2”表示每个人作为训练样本有2幅图像，测试样本有其余4幅图像.由表2可知，当每个人的训练样本都为“4”时，CMSFLA-SVM算法的平均识别率达到了96.5%,说明当训练样本不足时，CMSFLA-SVM算法仍能提高佩戴饰物人脸图像的识别率.

表2　训练样本不足时3种方法的平均识别率

5结束语

本文用改进的蛙跳算法CMSFLA训练SVM，并将其用于人脸识别中，ORL和CAS-PEAL-R1人脸库实验仿真结果表明：CMSFLA-SVM方法比ASFLA-SVM和KSFLA-SVM方法识别率更高，速度更快，且在训练样本不足时仍能保持良好的识别效果.在优化人脸识别问题时，CMSFLA-SVM算法中各参数的设置仍较薄弱，今后将对此作进一步的研究.

参考文献：

[1]ZHAO W, Chellappa R, Philips P J, et al. Face recognition: a literature survey[J]. ACM Computing Surveys, 2003,35(4):399-458.

[2]聂会星，梁坤，徐枞巍.基于小波变换和支持向量机的人脸识别研究[J].合肥工业大学学报(自然科学版)，2011，34(2)：208-211.

[3]汪世义，陶亮，王华彬.支持向量机和遗传算法的人脸识别方法[J].计算机工程与应用，2009，45(12)：164-166.

[4]Tang Faming， Chen Mianyun， Wang Zhongdong. An improved approach to training support vectors machine[J]. Journal of Systems Engineering and Electronics, 2006，17(1):200-205.

[5]张潇丹，黄程韦，赵力，等.应用改进混合蛙跳算法的实用语音情感识别[J].声学学报，2014，51(2)：271-280.

[6]谢赛琴，沈福明，邱雪娜.基于支持向量机的人脸识别方法[J].计算机工程，2009，35(16)：186-188.

[7]Eusuff M M， Lansey K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. Journal of Water Sources Planning and Management, 2003，129(3):210-225.

[8]Elbeltagi E， Hegazy T， Grierson D. A modified shuffled frog-leaping optimization algorithm： application to project management[J]. Structure and Infrastructure Engineering, 2007，3(1):53-60.

[9]姜建国，张丽媛，苏仟.一种利用动态搜索策略的混合的蛙跳算法[J].西安电子科技大学学报(自然科学版)，2014，41(4)：66-71.

[10]葛宇，王学平，梁静.自适应混沌变异蛙跳算法[J].计算机应用研究，2011，28(3)：945-947.

[11]李辉.交叉变异蛙跳算法[J].鲁东大学学报(自然科学版)，2015，31(1)：16-20.

[12]Elbeltagi E， Hegazy T， Grierson D. Comparison among five evolutionary-based optimization algorithms[J]． Advanced Engineering Informatics， 2005，19(1)：43-53．

[13]田海军.基于支持向量机的人脸识别技术研究与实现[D].长沙：国防科学技术大学，2009.

Application of CMSFLA-SVM algorithm in face recognition

LIU Yueting,ZHANG Yan

(SchoolofElectronicsandInformationEngineering，LanzhouUniversityofArtsandScience，

Lanzhou730000，China)

Abstract：Because of shuffled frog leaping algorithm (SFLA) such as local optimal and low precision solution，a crossover and mutation shuffled frog leaping algorithm is presented. In the global search， each of frog individuals according to the fitness will choose different probability of crossover and mutation operations. A face recognition algorithm using CMSFLA to train SVM is proposed. The simulation results of experiments on the ORL and CAS-PEAL-R1 face database show that compared with ASFLA-SVM and KSFLA-SVM， CMSFLA-SVM has higher recognition rate and higher speed. In the lack of training samples， CMSFLA-SVM also has good recognition effect.

Keywords：support vectors machines (SVM)； shuffled frog leaping algorithm (SFLA)； crossover； mutation； face recognition； optimal solution

文章编号：1004-4353(2015)04-0337-06

作者简介：刘悦婷(1979—)，女，副教授，研究方向为电子、自动控制.

收稿日期：2015-11-03基金项目： 甘肃省高等学校科研项目(2015B-132)