164 2009，45（12） Computer Engineering and Applications 计算机工程与应用 支持向量机和遗传算法的人脸识别方法 汪世义 1，2，陶 亮 1，王华彬 1 WANG Shi-yi1，2，TAO Liang1，WANG Hua-bin1 1.安徽大学 智能计算与信号处理教育部重点实验室，合肥 230039 2.巢湖学院 计算机系，安徽 巢湖 238000 1.Ministry of Education Key Laboratory of Intelligence Computing and Signal Processing，Anhui University，Hefei 230039，China 2.Computer Department of Chaohu College，Chaohu，Anhui 238000，China E-mail：E200701001@ahu.edu.cn WANG Shi-yi，TAO Liang，WANG Hua-bin.Face recognition based on Support Vector Machine and Genetic Algorithm. Computer Engineering and Applications，2009，45（12）：164-166. Abstract：Support Vector Machine （SVM） is an effective learning tool for small size samples.The SVM is considered as a good classifier with high generalization performance with no need to add a priori knowledge.However，the performance of SVM is in－ fluenced greatly by the scale parameter σ2 and the penalty parameter C，therefore，Genetic Algorithm （GA） to improve SVM in selecting these parameters based on face recognition is presented in this paper.Firstly，features from human face images are extracted by combining the 2 -D wavelet decomposition technique with the grayscale integral projection technique，and then，the optimized SVM to recognize is applied.The experimental results show that the proposed approach is efficient in face recognition. Key words：Support Vector Machines（SVM）；Genetic Algorithm（GA）；face recognition 摘 要：支持向量机是一种基于小样本学习的有效工具，作为分类器被认为具有很高的推广性能，无需先验知识。但是参数的选取 与支持向量机的识别性能是相关的，核函数参数 σ2 和惩罚因子 C 对支持向量机识别性能会产生很大的影响。针对支持向量机在 人脸识别问题中的应用，提出了一种基于遗传算法（GA）的参数选择优化方法。利用笔者曾提出的基于小波分解和积分投影的人 脸特征提取算法对人脸图像进行特征参数提取，然后利用优化的支持向量机进行识别。实验结果表明，该方法是有效的。 关键词：支持向量机；遗传算法；人脸识别 DOI：10.3778/j.issn.1002-8331.2009.12.053 文章编号：1002－8331（2009）12-0164-03 文献标识码：A 中图分类号：TP391.41 1 引言 人脸识别是模式识别研究领域的一个重要研究方向，属于 生物识别的研究领域。基于人脸识别的自动身份认证具有重要 的理论意义和应用价值，早在 20 世纪六七十年代就引起了研 究者的强烈兴趣，尤其是近十年来，由于各方面对人脸自动识 别系统的迫切需要，对人脸自动识别方法的研究越来越成为当 前模式识别和人工智能领域的一个研究热点[1-2]。 支持向量机（Support Vector Machine，SVM）是由 AT&T 贝 尔实验室的 Vapnik 及其研究小组于 20 世纪 90 年代中期在统 计学习理论的基础上提出的一种新的模式识别方法，在解决小 样本、非线性及高维模式识别问题中表现出许多特有的优势， 并能够推广应用到函数拟合等其它机器学习问题中，因此近年 来 SVM 的研究受到越来越多的重视[3-4]。人脸识别问题本质上 属于小样本、非线性模式识别问题，因此，把分类性能卓越的 SVM 作为人脸特征分类器是一种合理的自然选择。但作为分 类器的支持向量机，其泛化性能取决于核函数及其参数的选 择，但目前对核函数及其参数的选择仍是经验性的或实验性 的，在理论上尚无直接选择法[5]。为了能够自动地获取最佳的 SVM 参数，提出了基于遗传算法的 SVM 参数选取方法，并将 该方法应用于人脸识别，实验结果表明，该方法取得了比较好 的效果。 2 支持向量机 2.1 支持向量机基本原理 支持向量机的基本思想是：首先通过将输入样本空间非线 性变换到另一个空间（特征空间），然后在这个新的空间中求取 基金项目：国家自然科学基金（the National Natural Science Foundation of China under Grant No.60572128）；安徽省人才发展基金（the Talent Development Foundation of Anhui Province under Grant No.2005Z029）；安徽大学创新团队项目基金（Anhui University Program for Creative Teams）；安徽省高校省级自然科学研究计划项目（the Provincial Natural Scientific Fund from the Bureau of Education of An－ hui Province No.KJ2008B38ZC）；巢湖学院自然科学基金资助项目（the Natural Scientific Fund from Chaohu College No.XLY-200713）。 作者简介：汪世义（1974-），男，博士研究生，讲师，研究方向为模式识别、机器学习，网络安全；陶亮（1963-），男，博士，教授，博士生导师，研究方向 为数字信号与图像处理、模式识别；王华彬，男，博士研究生，研究方向为数字信号与图像处理、模式识别。 收稿日期：2009-01-09 修回日期：2009-02-13 

汪世义，陶 亮，王华彬：支持向量机和遗传算法的人脸识别方法 2009，45（12） 165 样本的最优线性分类面（使两类样本的分类间隔最大），而这种 非线性变换是通过定义适当的内积函数（或称为核函数）实现 的。上述那些与最优分类面最近的两类样本被称为支持向量 （Support Vector，SV）。设两类线性可分学习（训练）样本集为 度下降法存在对初始值要求高，容易陷入局部最优值的问题。 本文采用遗传算法对 SVM 参数优选进行了研究，为支持 向量机参数优选提供一种新的方法，并把它应用到人脸识别系 统中。 ，yi } N i=1 i ，x {xi ∈R i d ，y ∈{+1，-1}是其类别标记。 最优分类面函数设为： g（xi ）= n Σα j=1 op i yi K（xi ，xj ）+b op ，i=1，2，…，n （1） op 为分类阈值，k（xi 其中 b ）是一内积函数。这里选下列径向 基函数作为内积函数，由此得到的支持向量机是一种径向基函 ，xj 数分类器： K（x，xi ）=exp - ‖x-xi ‖ 22 2 2 （2） σ 最优分类面函数是通过下列函数 Q（a）的最优化解 a …，n 来确定的。 op i ，i=1，2， Q（a）=- Min a n Σai +0.5 i=1 n Σ 1 Σai aj yi yj k（xi n 1 ） ，xj （3） Subject to Σyi ai =0，c≥ai ≥0，i=1，2，…，n n i=1 ，a2 ，…，an ] T ，C 为某一正常数。这是一个不等式约束 其中 a=[a1 下的二次函数极值问题，存在唯一解，最优化的过程实际上是 使分类间隔最大。 根据 Kühn-Tucker 条件，Q（a）的最优化解中，多数 a 为 op i i sv op （记为 a 0，取值不为 0 的 a 成立的那些样本即为支持向量：x 全体样本中很少的一部分，即 s 远小于 n。 ，i=1，2，…，s）所对应的能使式（4） ，i=1，2，…，s，它们通常只是 sv i i （ yi Σa op j yi k（xi ，xj ）+b op）-1=0 （4） n j=1 于是，只要代入上式任一支持向量 x 即可求出分类阈值 b op ： sv i 及对应的类别标记 y sv ， i n s sv op op b =y i - Σa j k（x 最后得到支持向量机的最优分类函数为： j yj k（x Σa ）=y ，xj i - j y j=1 j=1 sv sv sv sv i sv i ） sv ，x j s f（x）=sign{g（x）}=sign 2 Σα 上式中 sign（·）为符号函数。 2.2 参数对 SVM 性能的影响 l y l=1 sv sv sv l〈x，x l 〉+b op 2 （5） （6） 在 SVM 算法中，参数 C、σ 2 对支持向量机的性能有着十分 重要的影响[6-7]。参数 C 是经验风险和置信范围的裁决；参数 σ 影响数据在高维空间中分布的复杂度。在基于 SVM 的人脸识 别系统[5]应用中也表明，惩罚系数 C 和核函数参数 σ 2 对分类结 果的影响均很大，只有选择合适的模型参数，SVM 的优越性才 能更好地发挥出来。 2 随着 SVM 在模式识别领域的广泛应用，各种对参数选择 进行优化的方法层出不穷，文献[8]提出了一种以原空间中样本 到分类面的最短代数距离最大为准则的 SVM 参数优化方法； 文献[9]提出采用梯度下降法进行参数优选，但是同时也指出梯 3 基于遗传算法的支持向量机参数选择 遗传算法（Genetic Algorithm）利用生物遗传学的观点，结 合适者生存和随机信息交换的思想，通过自然选择、交叉、变异 等作用机制，实现种群的进化。在寻优过程中，遗传算法在解空 间随机产生多个起始点并同时开始搜索，由适应度函数来指导 搜索方向，是一种能够在复杂搜索空间快速寻求全局优化解的 搜索技术。在基本遗传算法中，每个分类器的基本表达是一个 二进制位串，称为染色体。 3.1 编码方式 遗传算法主要是对群体中的个体施加操作从而完成优化 的，它只能处理以基因编码形式表示的个体。在使用遗传算法 时需把优化问题解的参数形式转换成基因编码的表示形式。本 文是文献[5]的后继工作，根据惩罚因子 C 和高斯核参数 σ 2 可 能的取值范围，选取整数 C∈[1，100 000]，σ C 和 σ 参数组可用 24 位二进制串表示。 3.2 初始种群与适应度函数设计 2 可分别用 14 位和 10 位的二进制串表示，这样 C 和 σ ∈[0.001，1]，于是， 2 2 由上述可知，C 和 σ 2 参数组可用一个随机产生的 24 位二 进制串表示一个个体，多个个体组成种群，种群的规模就是指 种群中个体的数目。其中种群数目过大将会增加 GA 的运算时 间，且使种群形态过于分散，实验中群体规模取为 30，进化代 数为 30。 根据具体应用中实验的情况，设计适应度函数 f（σ 2 ，C）=1/inaccuracy （7） 其中，inaccuracy 是 SVM 在训练样本集上的错分率，可见当 SVM 在测试样本集上的分类错误率越低，对应于该组参数的 染色体适应度函数值越大。 3.3 基于遗传算法的 SVM 参数优化算法 （1）初始代数 GEN=0（GEN 表示进化的代数），GENmax 表 示最大进化代数，初始化优化目标的最大值 fmax。 （2）确定变量 C 和 σ 应 24 位二进制串编码。 2 的取值范围，然后进行编码，文中对 （3）种群初始化：在各变量取值范围之内，随机生成规模为 POPnumber 的初始种群 Rgen，其中单个初始染色体记作 Xk， k=1，2，…，POPnumber。文中 POPnumber 值取 30。 （4）确定适应度函数值。以参数 σ 2 和 C 为基础，运用 SVM 算法对样本进行分类。然后利用式（7）计算适应度函数值。 （5）按适应度值进行排序。对各染色体 Xk 进行解码，并依 据适应度值对染色体进行排序。 （6）遗传操作： ①选择：根据各个个体的适应度值，采用随机遍历抽样方 法从上一代群体中选择出一些优良的个体遗传到下一代群 体中； ②交叉操作：将群体内的各个个体随机搭配成对，对每一 个个体，以某个交叉概率交换它们之间的部分染色体（即互换 

166 2009，45（12） Computer Engineering and Applications 计算机工程与应用 图 1 ORL 人脸图像库中 1 人的 10 张脸像及其归一化标准脸像 串中部分代码）； ③变异操作：在群体中随机地选择一个个体，对于选中的 个体以变异概率 P，改变字符串中某位上的字符的值，以得到 新的个体。 （7）程序终止条件：当前群体的个体最优值达到优化目标 的最大值 fmax 或进化代数达到 GENmax，则终止，得到最优的 惩罚系数 C 和核函数参数 σ 2 ，带入 SVM 对测试样本数据进行 训练以获得最优分类面；否则令 GEN=GEN+1，转到（4）。 4 实验 不同的人脸特征提取法对人脸识别的性能有很大影响，本 文应用文献[10]中提出的人眼定位算法可以有效地实现复杂背 景下人眼的定位，然后再利用文献[11]中提到的归一化算法和 基于小波分解的人脸特征提取方法来提取人脸特征，最后可以 得到维数为 352×1 的向量，作为下面实验中的人脸特征向量。 4.1 人脸图像库和实验设计 剑桥大学 ORL 人脸图像库是国际上人脸识别领域常用的 人脸图像库，该图像库由 40 人的准正面灰度脸像组成，所有图 像的精度为 112×92，像素灰度级 256，每人有 10 张不同的脸 像，该图像库共有 400 张人脸图像。图 1 给出了其中 1 人的 10 张脸像及其归一化标准脸像。 从 ORL 人脸图像库中随机选出 20 个人，人脸图像库中 20 个人每人 10 张脸像分成两组，一组作为训练集，一组作为 测试集。训练集脸像选择应有代表性，尽量包括有不同表情变 化、不同脸部朝向、不同光照的脸像。在每类（人）中选择 5 张脸 像作为训练用，其余 5 张用作测试，20 个类中训练集和测试集 各有 100 张脸像；然后交换训练集与测试集，重新进行一次实 验，这样在实验中就可以得到两组数据。 用遗传算法搜索最优的支持向量机参数，随机产生初始代 群体，群体规模为 30，最大进化代数为 30。然后利用优化参数 的支持向量机进行分类测试，本实验用的 PC 机配置为 Pen－ tium4 2.4 GHz 的 CPU、512 M 的内存，软件环境为 XP 操作系 统，Visual C++6.0。 4.2 实验分析与比较 实验 1 径向基核函数中不同的 σ 2参数值下 SVM 分类性能。 测试前用训练集样本训练一个两分类支持向量机，这样每 一两分类支持向量机可分出一个用户。表 1 为不同的参数值下 SVM 分类性能比较，由表 1 可看出，不同的 σ 2 值对 SVM 分类 =0.08 时，SVM 分类错误率最小，性能最好。 精度是有影响的，当 σ 2 实验 2 基于 GA 的 SVM 参数的选取与优化。 遗传算法参数选择：初始交叉概率取值 0.85，初始变异 概率取值 0.025，初始种群数为 30，最大进化代数 30，C∈ 表 1 径向基核函数中不同的 σ2 参数值下 SVM 分类性能 σ2 0.06 0.07 0.08 0.09 0.10 0.11 第一次错分类个数 第二次错分类个数 平均错分类个数 平均错误率/（%） 4 6 5 5 3 4 3.5 3.5 2 3 2.5 2.5 3 3 3 3 4 4 4 4 5 6 5.5 5.5 [1，100 000]，σ 2 ∈[0.001，1]。 从表 2 可以看出：SVM 的分类正确率随着迭代次数的增 加而逐步得到提高，同时适应度函数值也逐步变大，而且逐步 收敛到稳定值。 表 2 SVM 参数选取结果和识别率 迭代次数 σ2 C 识别准确率 适应度函数值 1 5 10 15 20 25 30 0.050 1 67 252 0.933 1 0.090 0 66 408 0.973 1 0.090 9 94 936 0.988 5 14.947 6 37.174 7 85.956 5 0.077 3 94 688 0.993 5 153.846 1 0.077 3 94 688 0.993 5 153.846 1 0.077 3 98 016 0.994 2 172.413 8 0.077 3 98 016 0.994 2 172.413 8 5 结语 本文研究了支持向量机在人脸识别系统中的应用，提出了 一种基于遗传算法的参数选取优化方法。针对 ORL 人脸图像 库，利用基于小波分解的人脸特征提取方法来提取人脸特征， 然后确定合适的遗传算法适应度函数，并利用遗传算法对支持 向量机的参数进行优化选取，利用优化参数的 SVM 进行人脸 识别。实验结果表明，所提出的基于遗传算法的 SVM 参数优化 方法的识别率较好，是一种行之有效的方法。后继的工作主要 是研究更好的参数编码方式，提高所提出的算法的性能和求解 精确度。 参考文献： [1] Shih Pei-chung，Liu Cheng-jun.Face detection using discriminating feature analysis and support vector machine[J].Pattern Recognition， 2006，39：260-276. [2] 余慧海，申金媛，刘润杰.基于 ICA 和 NFL 与 NN 联合分类器的人 脸识别[J].计算机工程与应用，2008，44（26）：183-185. [3] Huang C，Lee Y，Lin D.Model selection for support vector ma － chines via uniform design[J].Comput Stat Data An，2007，52（1）： 335-346. [4] Bao Y，Liu Z.A fast grid search method in support vector regres－ sion forecasting time series[C]//LNCS 4224：Intelligent Data Engineer－ ing and Automated Learning，IDEAL 2006，2006，42（24）：504-511. （下转 232 页） 

232 2009，45（12） Computer Engineering and Applications 计算机工程与应用 （a） （c） （b） 图 9 大尺寸零件的处理效果 （a）复杂度适中数据；（b）内部结构简单数据；（c）多内孔的复杂数据 三个处理过程，最终完成文本标注的定位。该方法快速、有效， 对应的软件系统在工程实践中表现良好。 但是该方法仅仅是一种可行性解决方案，在以后的工作 中，如何得到一种既能得到美观的填充位置又能满足工程应用 的时效要求的“最优解”，是很有研究价值和应用价值的。 参考文献： [1] 李波，吴琼玉，刘东华，等.快速的复联通区域扫描线图形填充新方 法[J].国防科技大学学报，2003，4：68-71. [2] Bevington P R，Robinson D K.Data reduction and error analysis the physical sciences [M].2nd ed.Boston：WCB/McGraw -Hill， for 1992. [3] Chan T S，Yip R K K.Line detection algorithm [C]//Proceedings the 13th International Conference on Pattern Recognition，Vien－ of na，1996：126-130. [4] Draper N R，Smith H.Applied regression analysis [M].3rd ed.New York：John Wiley & Sons，1998. [5] 章毓晋.图像分割[M].北京：科学出版社，2001. [6] 任明武，杨静宇，张涵.一种新的基于链码描述的轮廓填充算法[J]. 中国图象图形学报，2001，6（4）：348-352. [7] 王耀南，李树涛，毛建旭.计算机图像处理与识别技术[M].北京：高 等教育出版社，2001. [8] 李桂清，李陶深.扫描线种子填充算法的问题及改进[J].广西大学学 报，1998，23（3）. [9] 顾国庆，许彦冰.数字图像区域标定的方法[J].上海理工大学学报， 2001，23（4）：295-299. [10] 吴章文，杨代伦.区域填充极点判别算法[J].计算机辅助设计与图 形学学报，2003，15（8）：979-983. （上接 166 页） [5] 陶亮.基于人脸识别的身份认证方法研究[D].中国科学技术大学， 2003. [6] Agrawal R K，Bala R.A hybrid approach for selection of relevant features for micro array datasets[J].Computer and Information Sci － ence and Engineering，2007，1（4）：196-202. [7] 于青，赵辉.基于 GA 的 ε-支持向量机参数优化研究[J].计算机工程 与应用，2008，44（15）：139-141. 微型计算机系统，2008，28（1）：102-105. [9] Chappelle O，Vapnik V，Bousquet O.Choosing multiple parameters for support vector machines[J].Machine Learning，2002，46（1）：131- 160. [10] 陶亮，庄镇泉.复杂背景下人眼自动定位[J].计算机辅助设计与图 形学学报，2003，15（1）：38-42. [11] 陶亮，庄镇泉.基于小波分解和支持向量机的正面人脸识别方法[J]. [8] 肇莹，刘红星，高敦堂.支持向量机参数优化的一种新方法[J].小型 电路与系统学报，2003，8（6）：107-112. （上接 207 页） 表 3 分析结果的比较 雷达信号类型 频率固定型 频率捷变型 频率跳变型 每组脉冲数 实际类型数目 分析类型数目 漏分选数目 误分选数目 总分选准确率/（%） 100 100 100 0 0 100 100 99 1 0 99.67 100 100 100 0 0 因为动态聚类法对聚类中心进行了修正，所以分选识别率 有了明显的提高。 4 结束语 本文给出了一种基于动态聚类分析的雷达信号载频模式 识别方法，通过仿真分析可以看出，该算法原理简单、易于实 现、运算量小，在实现信号分类的同时还能够识别载频模式信 息，是一种有效的雷达信号分析识别工具。同时该算法使用方 便，满足雷达对抗侦察的实际需求，易于在雷达侦察数字接收 机上高速实现。 参考文献： [1] 罗景青.雷达对抗原理[M].北京：解放军出版社，2003. [2] Poosala V，Ioannidis Y E.Improved histograms for selectivity esti－ mation of range predicates[C]//Proceedings of ACMSIG-MOD Con－ ference，1996：294-305. [3] 陶荣辉.基于直方图和小波网络的雷达信号识别方法[J].电波科学 学报，2005，20（6）：784-788. [4] 孙即祥.现代模式识别[M].长沙：国防科技大学出版社，2002. [5] 张万军.聚类方法在雷达信号分选中的应用[J].雷达科学与技术， 2004，2（4）：219-223.