基于遗传优化的快速人脸特征提取方法

摘要：在人脸识别过程中，从检测到辨认往往需要进行大量的数据运算和存储，为有效利用硬件资源，通过分析遗传算法的理念并引入到人脸识别过程中，利用遗传特性寻找最相近的人脸特征，与目前常见方法进行性能对比，证明了遗传算法在不降低准确率的前提可以大幅减少运算时间。

关键词：人脸识别；遗传算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2013）12-2857-03

人脸识别技术以其非接触采集特性和良好的用户体验成为生物识别领域一个重要分支。尤其自上世纪90年代以来，研究该领域的各国学者针对不同的用户环境开发出很多识别技术[1]，如基于几何特征的方法，基于模板匹配的方法，基于代数特征的方法，基于神经网络的方法，基于支持向量机的方法等等。这些方法中采用频率较高的特征提取技术有主成分分析（PCA）[2]、小波分析（Gabor变换、Mallat算法）、线性判别分析（LDA）[3]等，在这些基础方法上还发展出来了KPCA[4]、二维Gabor小波变换、FSLDA以及多种技术的组合等众多方法，近几年还出现了三维人脸建模技术[5]。无论哪种方法都需要高效的计算和存储平台作硬件支撑。

如果能够在保证识别效果的基础上有效降低存储和计算量，使这一技术推广到常见的便携移动设备上，如利用智能手机进行银行转帐时，使用SIM+人脸鉴定的双重保险，将会给人们带来更加安全便捷的数字化服务。为与人脸识别过程相结合，在分析了遗传算法的基本过程和要素后，给出遗传算法在应用于人脸识别时的一种适应度评价方式和三个重要算子，通过实验分析，证实此方法效果明显。

1 基于遗传算法（GA）的人脸特征提取

遗传算法是Holland教授[6]于1975年提出的一种模拟生物体进化的抽象算法，具有“生成+检测”的特性。它利用编码空间代替问题参数空间，以适应函数作为评价依据，以编码群体为进化基础，并对群体中的个体进行遗传操作来实现选择和遗传机制，形成循环迭代，由群体中个体的不断进化逐渐接近问题的最优解。遗传算法的整个进化过程操作是随机的，但它所显现的特性并非完全随机，它在搜索过程中它能有效利用历史信息推测下一代，得到期望性能有所提高的寻优点集。

一般的遗传算法包含五大要素[7]：

1）参数编码（二进制编码、序列编码、树编码、自适应编码、大字符集等）；

2）初始群体的敲定；

3）适应度函数的设计；

4）遗传操作的设计（遗传算子：选择、交叉、变异）；

5）控制参数的设定。

其中遗传算子的作用就是模拟生物系统中“适者生存”，淘汰不能适应的染色体，把更有益的信息遗传到子代。

在生物模拟系统中，DNA由遗传的染色体构成，染色体在遗传算法中表示为比特序列。其中每个染色体用n位来表示。在执行遗传算法的第一步就是对各类中的每个个体进行编码，即编排单个个体的比特序列。在这里，对染色体的编码是通过获取个体的十进制值后转化为二进制编码来实现的，它是由0和1组成的序列。例如，对于已知的单个个体由8位（n=8）来表示时，则它的染色体为：X=x8， x7， x6， x5， x4， x3， x2， x1。

对群体中个体的染色体进行操作的三个算子：选择、交叉、变异。

选择算子，作用就是选择适应值较好的个体以生成交配池。这里采用轮盘赌（roulette whell）的方法来实现，以保证每个父代都有同等的概率Ps被选择。

交叉算子，在GA中模仿了自然界有性繁殖的基因重组过程，目的是将原有的优良基因遗传给子代。交叉操作一般分为三步：

从交配池中随机抽取出一对要交配的个体。

根据位串长度L，对要交配的一对个体进行长度[1，L-1]的位置交叉；

根据设定的交叉概率Pc（0 < Pc ≤ 1）实施交叉操作。从而生成一对新的个体。这里实验采用单点交叉的方式，设定Pc=0.6。

设在交配池中随机抽取一对个体：S1=a1，a2，a3，...，aL，S2=b1，b2，b3，...，bL，随机抽取交叉位x∈{1，2，...，L-1}，此处以L=5，X=3为例对两个个体右侧部分染色体位串进行交换，得到两个新个体S1’= a1，a2， b3，b4，b5，S2’=b1，b2， a3，a4，a5 。

变异算子，模拟的是自然界生物体进化中染色体某位基因发生突变的现象。在GA中，通过设定变异概率Pm随机反转某位的二进制字符值来实现。即，产生一个随机数P，若P

GA（后面提及的GA都是限定遗传算法在人脸识别中的应用）工作流程如下：

迭代开始： [t=0]

初始化： [P（0）={a（0）1，a（0）2，...，a（0）n}]

适应性评价：[P0={f（a（0）1），f（a（0）2），...，f（a（0）n）}]

do {

选择： [P'（t）=s（P（t），Ps）]

交叉： [P''（t）=c（P'（t），Pc）]

变异： [P'''（t）=m（P''（t），Pm）]

生成新一代： [P（t+1）=P'''（t），t=t+1]

适应性评价： [P（t+1）={f（a（t+1）1），f（a（t+1）2），...，f（a（t+1）n）}]

} while（ [T（P（t））=true]）

2 应用示例

设有L类样本，定义：

训练集X={X1，X2，X3，...XL}

第i个类的子集Xi={x1（i）， x2（i），...， xNi（i）}

其中x1（i）， x2（i）为i类的第1和第2个训练样本个体（图像），Ni为第i类样本的训练样本总数。所有图像训练样本的总数量N=N1+N2+...NL

1）对所有图像转换为列矢量，即，把每个位置的染色体变为向量。每个向量代表一个个体，位数取决于染色体所代表图像的灰度级，即图像像素的编码。假设一个灰度级为256的图像，其染色体应为8位（28=256），如图1，为一个m×n像素的图像。

2） 每个类的初始种群从Ni中产生。因为交叉操作需成对进行，所以当Ni为奇数时，需要取一个测试图像进行配对交叉（仅对属于同一类的所有个体设置进行交叉操作，产生的新个体仍属于此类中）。

3） 对每个类中的所有个体设置一个适应度函数，这里采用欧氏距离来衡量。设测试用例为q，与xij（第i类中的第j个个体）的适应度函数为：[d（j）i=q-x（j）iq，（1≤j≤2Ni）]

4） 新生成的类中的每个个体Ni都将符合最低适应度函数。

5） 迭代递增+1。

6） 如果算法执行超过最大迭代数T，或者群体产生的个体已达到最高适应度值，则认为此测试用例属于该类。否则，转到步骤3。

为说明交叉操作，设有某类中一对将要配对的个体a和b，在第4比特位进行切割交叉，将产生两个新个体c和d，如图2：

3 实验分析

实验使用了剑桥ORL库（共有40人，每人10幅，每幅92×112像素的256灰度级图片），实验机器平台为清华同方X46H型号，使用[8]的方法与遗传算法进行比较，先后进行了10次实验，取平均值得到结果如表1和表2：

表1 识别率对比

[训练样本 Ni＼&GA识别率＼&PCA识别率＼&5＼&91.1%＼&90.0%＼&6＼&92.5%＼&91.7%＼&7＼&94.1%＼&93.3%＼&]

表2 运算时间对比

[训练样本Ni＼&GA耗时（s）＼&PCA＼&前期处理时间（s）＼&识别时间（s）＼&总时间（s）＼&5＼&12.0＼&119.6＼&5.6＼&125.2＼&6＼&13.4＼&125.8＼&5.7＼&131.5＼&7＼&15.3＼&129.3＼&5.8＼&135.1＼&]

从实验结果看，两种方法的识别率比较接近。首先，对比所用时间，两种方法在训练和识别同一组人脸时，在L=40，T<10，Pm<0.01，Pc=0.6的情况下，使用PCA方法的总耗时是GA的十倍。其次，对比存储空间，PCA方法在前期的预处理过程中，占用资源要比GA方法大很多。例如一幅92×112的图像，产生的协方差矩阵大小为10304×10304，如果协方差矩阵所表示的基本像素单元为8字节，那么6幅图像需要占用存储量6×10304^2×8b，相当于4.7GB的存储空间，要比普通的电脑全部内存还大；而GA即使在256灰度级图片上进行编码，存储6幅图像所占用空间为：92×112×6×8×2约966Kb，远远小于PCA。

4 总结

利用遗传算法良好的“生成+检测”特性来寻找优化问题的最优解，并在人脸识别中进行一次有效尝试，实验结果表明在不降低识别率的情况下，无论是计算时间还是所占在存储容量GA都要明显少于PCA。但本方法只适合在非固定用户群使用，这里使用单一的PCA降维方式进行实验对比只是为了更明显分析遗传算法的特点，并非反映PCA方法低效，相反，在固定用户群体的情况下，PCA只需进行一次前期训练即可完成以后的快速识别，这是GA所不能及的。相信在其他优化问题求解上，遗传算法会有更好的拓展空间。

参考文献：

[1] 王映辉.人脸识别：原理、方法与技术[M].北京：科学出版社，2010.

[2] Turk M， Pentland A. Eigenfaces for Recognition， Journal of Cognitive Neurosicence， 1991，3（1）：71-86.

[3] Zhao W， Krishnaswamy A， Chellappa R， et al. Discriminant Analysis of Principal Components for Face Recognition， Face Recognition： From Theory to Applications， H. Wechsler， P.J. Phillips， V. Bruce， F.F. Soulie， and T.S. Huang， eds.， Springer-Verlag， Berlin， 1998：73-85.

[4] Yang M Q， Ahuja N， Kriegman D.Face recognition using kernel eigenfaces. Proc.ICIP，1：37-40.

[5] Lee J， Moghaddam B， Pfister H， et al. Finding Optimal Views for 3D Face Shape Modeling， Proc. of the International Conference on Automatic Face and Gesture Recognition， FGR2004， 17-19 May 2004， Seoul， Korea， pp. 31-36.

[6] Holland J H. Outline for a logical theory of adaptive systems. Journal of the Association fo Computing Machinery， 1962，9（3）：297-314.

[7] 李敏强，寇纪淞，林丹，等. 遗传算法的基本理论与应用[M].北京：科学出版社，2002.

[8] Moon H， Phillips P J. Computational and Performance aspects of PCA-based Face Recognition Algorithms， Perception， 2001（30）：303-321.