一种基于分块小波的人脸识别算法

杨淑平，易国栋，袁修贵，刘再明

(中南大学 数学与统计学院，湖南 长沙，410083)

摘要：提出一种基于分块小波的人脸识别新算法。在充分考虑提取局部特征，又克服小样本问题的基础上，提出分块小波的概念。首先，对小波分解后的低频子图进行分块，提取局部特征，从而降低图像维数并除去冗余噪声；将其先后进行PCA和LDA变换，得到组合特征向量；最后，根据KNN的快速分类能力及SVM在少数类别分类上的优势，提出KNN+SVM融合分类器对组合特征向量进行分类识别。研究结果表明：该方法识别率高，识别速度快，具有一定的实用价值。

关键词：分块小波变换；PCA+LDA；KNN；支持向量机；分类器组合

中图分类号：O235          文献标志码：A         文章编号：1672-7207(2013)05-1902-08

A face recognition algorithm based on blocking wavelet transforms

YANG Shuping, YI Guodong, YUAN Xiugui, LIU Zaiming

(School of Mathematics and Statistics, Central South University, Changsha 410083, China)

Abstract: A new face recognition based on the blocking wavelet transforms was proposed. To fully extract local features, and overcome the small sample size problem, the concept of block wavelet was presented. First the local characteristics of the face were extracted by the blocking methods after wavelet decomposition of low frequency sub-band. The dimensions were reduced and the redundancy noise was eliminated. After that, the PCA and LDA transformations were taken to obtain the combine eigenvectors. Finally, taking advantage of the fast classification ability of the KNN and the high recognition rate of SVM on a few category classifications, a new blend classifier named KNN+SVM was constructed to recognize the combined eigenvectors. The results show that the new method has high recognition rate, fast identifying speed, and practical value.

Key words: blocking wavelet transform; PCA+LDA; KNN; SVM; classifications combination

基于统计特征的人脸识别方法由于具有识别率高的优点，在模式识别领域得到广泛应用和研究^[1]。其方法主要有基于Kirby-Sirovich(K-L)变换的主成分分析法(principal component analysis, PCA)、基于Fisher准则的线性鉴别分析(linear discriminant analysis, LDA)以及后来发展起来的独立元分析方法(independant component analysis, ICA)和核线性判别方法(kernel-based discriminant analysis, KDA)。K-L变换^[2]是由Kirby和Sirovich提出来的，它能够消除原向量中各分量之间的相关性，且能使原始能量主要集中在变换后向量的前几个分量中。受此理论的启发，Turk和Pentland^[3]于1991年将其应用到人脸识别领域，提出了基于PCA的人脸识别方法。他们将变换后所得到的最大几个特征值所对应的特征向量来表示原有图像，这样，保留了原始图像的主要信息，去除了次要信息，又达到降低图像维数的目的。该算法的识别过程是将人脸图像映射到由上述特征脸张成的子空间上，然后，比较其与已知人脸在特征空间中的位置来达到识别的目的。线性鉴别分析^[4](LDA)的基本思想是选择使得Fisher准则函数达到极值的向量作为最佳投影方向，从而使得样本在该方向上投影后，达到最大类间离散度和最小类内离散度。在人脸图像的多尺度分割基础上，张健等^[5]提出了具有较高识别率的多尺度LDA人脸识别方法。以上各种方法仅适用于类内散布矩阵非奇异(可逆)的情形，但在实际应用中存在大量典型的小样本问题，如在人脸图像识别问题中，类内散布矩阵经常是奇异的。已有实验证明PCA和LDA的结合往往既能克服LDA的小样本问题，又能保证有较高的识别率。而以往的研究大多仅考虑对图像进行小波变换提取其双低频子图像，以进行相应处理，虽达到了降维的目的，但没考虑人脸局部特征对识别起到很重要的作用。为此，本文作者在充分考虑提取局部特征，又克服小样本问题的基础上，提出一种基于分块小波的新算法，从组合特征的提取和融合分类器的角度出发，试图进一步提高统计特征识别方法的识别率和识别速度。

1  基于分块小波的组合特征提取

1.1  小波变换的特点

小波是具有局部时频性和多分辨率特性的滤波器。小波变换示意图见图1。人脸图像经过1次二维小波分解后得到如图1(b)所示的4部分(L_L，L_H，H_L和H_H)。其中：L _L为水平方向和垂直方向低通滤波后的小波系数，该系数基本包含了原有图像的信息，而且在此区域中消除了随机信息和冗余信息；L_H包含了人脸水平方向低频和垂直方向的高通滤波后的小波系数；H_L包含了人脸水平方向高频和垂直方向的低频小波系数；H_H为水平方向和垂直方向都经过高通滤波后的小波系数。若对L_L重复分解，则可得到更高一级的分解图像。

图1  小波变换示意图

Fig.1  Diagrams of wavelet transformation

尽管可用基于任何方向的单一小波子图进行人脸识别，但是，由于它们所包含的信息不同，基于不同方向小波子图识别方法的识别率也不同^[6]。低频子图由于包含原图像的主要能量，且对表情变化不敏感，所以，它的识别率最高。水平方向子图和垂直方向子图包含了较多的轮廓信息，这些信息也可用于识别，故也有较高的识别率。而对角线方向子图主要包含一些冗余信息，所以，识别率最低^[7]。故本文利用低频子图进行研究，未使用其他3个方向的小波子图。

1.2  小波基和分解层数的确定

目前，常用的几种小波分别是Haar小波、Daubechies(DbN)小波系、Biorthogonal(BiorNr.Nd)小波系、Coiflet(CoifN)小波系、SymletsA(SymN)小波系。由于它们具有不同性质，在人脸识别中不同小波基对识别效果有较大影响，故选择正确的小波函数是小波变换应用效果的关键。然而，在实际选择时并没有很好的理论指导。一般是对于不同的人脸库，通过多次试验比较选择最好的小波基。为了得到应用于ORL人脸库上人脸识别最好的小波基，本文从时间和识别率2方面考虑，比较不同小波基的应用效果。对于这5类常用小波，在每类中选取几个有代表性的小波，然后，用这些不同类型的小波进行2层分解获得最低频子图进行识别。实验表明：一方面，各类小波基随着分解层数N增大，识别时间会显著增加，然而，识别率并不会提高；另一方面，各小波系类都有在识别率较高及识别时间上较短的小波基，并且这些小波基相互之间的差异并不显著，见表1。从表1可以看出：若选择Rbio1.3小波基且图像大小为112×92时，识别率最高，但是时间最长。综合考虑这2种不同大小图像，显然，Coif1在识别率和识别时间上效理想，而且显得更加稳定，故在后面的实验中选取的小波基为Coif1。

表1  不同小波基的识别性能

Table 1  Performance of different wavelet

分解层数与被分解图像的大小相关：若分解层数过多，则会丢到太多信息，造成图像失真；若层数太少，一方面达不到降维目的，另一方面也会留下过多冗余信息，从而影响后面的识别。ORL人脸库中有图片内容相同但大小不一(28×23和112×92)的2个人脸库。这2种图片在不同分解层数情况下的识别率如表2所示。

表2  不同分解层数的识别率比较

Table 2  Recognition rate of different decomposition levels constructed                %

从表2可知：不同大小的图像所对应的最佳分解层数不相同，对于大小为28×23的图像分解2次能达到最好的效果，而大小为112×92的图像则需要分解3次才能到达最好的效果，而且图像大小为112×92时识别效果更好，所以，本文统一采用大小为112×92的图像，小波分解级数为3。

1.3  确定分块小波系数

设给定小波子图I大小为，将I分成的区域(称n为分块长度)。记大小为的子区域为

，则其小波系数均值可由如下表达式求出：

；1＜a＜n；1＜b＜n      

从而，由组成的新矩阵W即为分块小波系数：

由不同的分块得到每子块包含人脸的局部信息不一样。划分2×2区域时，人脸被分为上、下、左、右4块(见图2(a))，人眼眉毛额头被分在一起。而划分4×4区域时(见图2(b))，额头被分得更细，脸颊和嘴巴也被区分，这样，当人脸局部有遮挡或因光照等原因对人脸造成一定的影响时也不会太大地影响识别效果。

图2  图片分块后的效果

Fig.2  Effects after subdivision of pictures

为了寻找最合适的划分准则，进行了几种不同图像大小、不同分解级数下各种分块的人脸识别率对比实验，结果见图3~6(其中，能量比例为PCA方法中取的前r个特征值所占能量)。从图3~6可以看出：当分块长度为2时，其识别率基本保持在96%以上；而分块越细，到分块长度为8时，其识别率会有所下降，所以，分块不是越细越好，而应该是以2和4为最好。

图3  子图大小为32×32时进行2层小波分解的人脸识别率

Fig.3  Face recognition rate of wavelet decomposition to 2 level about 32×32 of wavelet subband

图4  子图大小为 32×32时进行做3层小波分解的人脸识别率

Fig.4  Face recognition rate of wavelet decomposition to 3 level about 32×32 of wavelet subband

图5  子图大小为 64×64 时进行2层小波分解的人脸识别率

Fig.5  Face recognition rate of wavelet decomposition to 2 level about 64×64 of wavelet subband

图6  子图大小为 64×64时进行3层小波分解的人脸识别率

Fig.6  Face recognition rate of wavelet decomposition to 3 level about 64×64 of wavelet subband

但从表3可以看出：分块长度为2时的识别时间比不分块(分块长度为1)的识别时间要高很多，而分块为4和8时，在子图相对较大时，识别时间由所减小；但当子图为32×32时，子块长度为2，4和8的识别时间基本没什么变化。所以，本文采用子块长度为2进行划分。

表3  不同分块长度识别时间比较

Table 3  Comparison of recognization time for different blocking lengths      ms

1.4  组合特征的提取

小波变换能够将图像的主要信息集中到双低频段，而将一些边缘的、次要的信息集中到高频段。随着分解层数的增加，变换后能得到更多的信息。由于小波变换能很好地处理降维与保留图像主要信息之间关系^[8-10]，故是目前最常用的图像降维方法之一。进一步地，分块小波既能钝化人脸突出局部信息，又能实现快速降维的效果。孙鑫等^[11]提出了分块PCA的人脸识别，先将人脸分成几块，再对各个子块利用PCA提取特征。类似的，谢永华等^[12]提出对人脸分块子图分别进行小波变换，得到不同子块的高频和低频小波系数，然后用于特征识别。但是，这样会增加小波变换的次数，增大问题的复杂程度。为此，本文先对待识别图像进行小波变换，然后对小波子图进行分块处理^[13]。

设给定M个样本行向量(i=1, 2, …, M)以及L个类别ω_i (i=1, 2, …, L)，不妨设M_k表示属于类别ω_k的样本数目。

首先利用主成分分析法在投影方向提取特征向量。协方差矩阵从给定的样本集中进行估计：

其中：。令为协方差矩阵S的前r个最大特征值对应的特征列向量组成的矩阵。主成分分析法就是将上述r个特征向量作为基向量，将原始空间的样本向量Y投影到上述特征向量所张成空间中。不妨设Y在上述特征空间中的投影向量为F，则

为PCA特征向量。

上述PCA特征提取方法是针对所有给定样本而言的，样本的所属类别信息并没有纳入算法中。

另一方面，LDA方法采用了使得样本能够正确分类识别的先验知识，即寻找最优投影方向，使得投影后向量的类间离散度矩阵和类内离散度矩阵的比率最大化。这些投影方向被用于对给定的样本向量提取特征，从而有助于提高识别率。

给定样本向量的类间离散矩阵定义为

类内离散度矩阵定义为

其中：，为所有样本向量的均值向量；，为第k个类别的均值向量。线性

判别分析试图寻找L-1个方向向量v使得如下关系式最大化：

由Rayleigh商的知识可知，使得式(7)中J最大化的向量v是如下常见的特征问题：

记是由式(8)的最大特征值对应的特征列向量组成的矩阵。同样，设Y在上述特征空间中的投影向量为，则

为LDA特征向量。

1.5  分类器融合

获得人脸的特征向量后，将特征向量输入到分类器中进行识别，常见的有K-近邻方法(K-nearest neighbor，简称KNN)、神经网络和支持向量机等。本文结合KNN的快速分类能力及支持向量机在解决小样本问题上的优势^[14]，提出一种新的KNN-SVM方法。

KNN是一种简洁而有效的非参数分类方法，是最简单的机器学习算法。该算法核心最早由Cover和Hart^[15]提出，用于解决文本分类问题。该方法的思路是：若1个样本在特征空间中的K个最相似(即特征空间中最邻近)样本中大多数属于某一个类别，则该样本也属于这个类别。

在KNN算法中，所选择的邻居都是已经正确分类的对象。设有N个样本分布到C个类为，每类有N_i个样本(i=1, 2, …, C)。在全部样布找出K个最近距离的近邻。K个近邻分布于C个类中数目用k_i表示。K近邻的判断函数为

; i=1, 2, …, C           

若，则决策为。这里可以使用的样本距离有欧氏距离、曼哈顿距离、明考斯基距离和范数等。

支持向量机(support vector machine, SVM)的基本思想是：将1个非线性可分样本输入向量，经非线性变换后映射到另一个高维空间中，再在变换后的空间中寻找1个最优的分界面超平面，使其推广能力最强^[16]。设线性可分样本集(x_i, y_i) (i=1, …, n, )，可以被超平面分开。通过求解1个约束极值问题，可以得到1个最优分类超平面，则最优分类判别函数可以表示为

式中： 和为约束极值问题最优解。

对于非线性可分问题，可以通过核函数将输入向量x映射到1个高维空间中进行分类运算。此时，最优分类判别函数式(4)变为

常用的核函数有许多种，主要有多项式函数、径向基函数、双曲正切函数。

支持向量是从2个分类问题发展而来，而人脸识别是多类分类问题。对于这种多类分类问题，尽管可以将多类分类问题分解为多个2类分类问题^[17-18]：一对多分类和一对一分类以及决策树。但是，由于需要构造多个分类器，这样会造成计算复杂及分类重叠的情况。为此，本文利用KNN快速分类的能力，提出一种新的分类器融合方法即KNN+SVM方法。

算法思路为：首先对人脸图像用前面提到的方法，基于分块小波的组合特征向量提取方法提取特征向量，然后用KNN对训练样本过滤，在剩下的类别中再用SVM进行分类识别，最后得到识别结果，算法流程图见图7。

图7  KNN+SVM算法流程图

Fig.7  Basic process of KNN+SVM algorithm

1.6  算法步骤

LDA充分利用了类别归属信息，得到的特征向量很好地强调了不同人脸之间的差异，并且弱化了同一人脸由于不同光照、姿态及表情所产生的变化，所以，应用于人脸识别能取得很好的效果，但是，推广能力较差。而PCA既能降低数据维数，又能使得式(8)中S_W非奇异，保证了LDA的推广能力，因此，本文提出了基于分块小波系数的PCA+LDA特征提取方法。该算法步骤如下：

Step 1 对待识别图像进行小波变换，提取双低频子图I；

Step 2 在I上应用式(2)得到分块小波系数W；

Step 3 对分块小波系数W增强处理；

Step 4 对增强后的重构图像进行PCA变换，得到PCA特征向量F；

Step 5 对PCA特征向量F利用式(9)进行LDA变换，得到LDA特征向量；

Step 6 对提取到的特征向量采用KNN和支持向量机相结合的组合分类器进行分类识别。

2  实验结果与讨论

在ORL和YALE人脸库上进行实验对比，对2个都进行2组对比实验。每组实验随机选择5个图像作为训练样本，剩下的5个图像用于测试，对不同分块长度和分解层数进行了10次重复实验。第1组是将小波子图的线性变换为32×32，实验结果见表4；第2组变换为64×64，实验结果见表5。

从表4和表5可以看出：对于2种大小不同的图像，基于分块小波的识别性能都比未分块小波的好。对于图像大小为32×32的图像，当分解级数为2级、分块长度为2个像素时，识别率最高，为96.80%；对于图像大小为64×64的图像，当分解级数为3、分块长度为4个像素时，识别率最高，为96.75%。而且这2种方式的识别速度都较高，识别时间分别为7.30 ms和9.60 ms。而不进行分块处理(对应的就是表4和表5中第1行的数据)时最高识别率是96.70%，识别时间分别为19.57 ms和138.60 ms。可见：进行分块处理不但能提高识别率，而且识别速度至少提高2倍以上。

表4  小波子图大小为32×32的识别率和识别时间

Table 4  Recognition rate and time to 32×32 of wavelet subband

表5  小波子图大小为64×64的识别率和识别时间

Table 5  Recognition rate and time to 64×64 of wavelet subband

此外，本文还比较了不同特征提取方法的人脸识别性能，见表6。从表6可以看出：2个人脸数据库由于人脸特征不同，ORL人脸库中每个对象人脸部分的表情和细节均只有细微变化，例如笑或不笑、脸部正面或者侧面、眼睛睁着或闭着、眼镜戴或不戴等，人脸空间姿态也稍有变化，其深度和平面旋转可达20°，人脸尺寸变化也不超过10%；而YALE人脸库则受光照、表情变化、配饰的影响较大，所以，采用同样的方法识别，其识别率和识别时间又一定差别。总体上看，线性鉴别分析(LDA)比特征脸方法(PCA)要好，因为前者充分利用了类别信息；而结合小波变换和PCA+LDA的方法比前两者要好，在识别率上提高了1%~2%，但识别时间上没有减少，本文所提出的分块小波+PCA+LDA特征提取方法识别率最高，且识别时间大大降低。

表6  各种方法实验结果对比

Table 6  Comparison of different methods

由于KNN不需监督，分类效率较高，SVM对于少数类别分类有很好效果，所以，有研究者将这2种方法结合起来进行分类^[15]。目前，大多数结合方法都是先判断样本和支持向量机的距离，若该距离大于某个阈值，则将其输入到SVM分类器，否则，就输入到KNN分类器^[16]。这种结合方法已经广泛应用于文本、网页分类和人脸识别的研究中，并取得了较好效果。但是，这种结合方法还是从支持向量机出发，需要构造最优超平面，所以，还是会带来计算复杂的问题。为此，本文提出了先用KNN过滤、简化问题规模、再用SVM分类的融合分类器方法。实验表明：采用此方法识别率比KNN的高，时间效率相当。

为了找出3种分类器的各自特点，以更好地应用分类器，最后对这3种分类器进行2组试验：第1组实验直接利用3种分类器对原始图像经1层小波分解后得到的双低频小波特征向量进行分类识别；第2组实验首先用本文提出的分块小波+PCA+LDA组合特征提取法得到新的组合特征向量后，再用3种分类器进行分类识别。不同分类器的比较见表7。

(1) 在第1组实验中，SVM分类器与其他分类器相比，其识别率最高，说明它非常适合处理双低频小波系数特征向量。另外，由于SVM识别每张图像花费时间太长，故时效性较差。

(2) KNN是一个适应性很强的分类器，无论是否使用PCA+LDA特征提取，其识别率都较高。由于其具有识别时间很短的优点，因而在人脸识别中得到了广泛应用。

(3) KNN +SVM融合分类器对特征向量的识别效果具有选择性，该方法不适合处理双低频小波系数。但经PCA+LDA特征提取后，其识别率显著比其他分类器的高，且平均识别时间与KNN的相近。

表7  不同分类器的比较

Table 7  Comparison of different classifiers

3  结论

(1) 在对原始图像进行小波变换后，对其低频子图像进行了分块运算，给出了一种新的小波系数即分块小波系数；结合主成分分析法和线性鉴别分析法得到了基于分块小波系数的组合特征向量。该方法充分利用了不同方法的特点，克服了不同方法带来的差异，得到了比单独是一种方法更好的效果。

(2) KNN +SVM融合分类器对经PCA+LDA处理后的组合特征特征向量识别率与其他分类器相比显著增大，且识别速度很快，具有实时处理的能力。

(3) 本文提出的方法不仅识别率比传统方法的要高，且识别速度快，在实时识别系统中具有一定实用价值。

参考文献：

[1] 刘琦, 韩其睿. 人脸识别技术综述[J]. 仪器仪表用户, 2008, 15(5): 1-2.

LIU Qi, HAN Qirui. Summary of the face recognition[J]. Electronic Instrumentation Consumer, 2008, 15(5): 1-2.

[2] Kirby M, Sirovich L. Application of the Karhunen-Loeve procedure for the characterization of human faces[J]. IEEE Transaction on Pattern Analysis and Mechine Intelligence, 1990, 12(1): 103-108.

[3] Turk M, Pentland A. Eigenfaces for recognition[J]. Journal of Cognitive Neuroscience, 1991, 3(1): 71-86.

[4] LU Guifu, ZOU Jian, WANG Yong. Incremental complete LDA for face recognition[J]. Pattern Recognition, 2012, 45(7): 2510-2521.

[5] 张健, 肖迪. 基于多尺度自适应LDA的人脸识别方法[J]. 计算机工程与设计, 2012, 33(1): 332-335.

ZHANG Jian, XIAO Di. Face recognition method based on multi-scale adaptive LDA[J]. Computer Engineering and Design, 2012, 33(1): 332-335.

[6] 翟俊海, 翟梦尧, 王华超. 基于小波变换和2DPCA的人脸识别[J]. 河北大学学报: 自然科学版, 2010, 30(5): 574-579.

DI Junhai, DI Mengyao, WANG Huachao. Face recognition based on wavelet transforms and 2DPCA[J]. Journal of Hebei University: Natural Science Edition, 2010, 30(5): 574-579.

[7] Zhao W, Chellappa R, Phillips P, et al. Face recognition: A literature survey[J]. Association for Computing Machinery Computing Surveys, 2003, 35(4): 399-458.

[8] Mandal T. A new approach to face recognition using curvelet transformation[D]. Canada: University of Windsor. Department of Electrical and Computer Engineering, 2008: 30-62.

[9] Belhumeour P N, Hespanha J P, Kriegman D J. Eigenfaces vs fisherfaces: Using class specific linear projection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997, 19(7): 711-720.

[10] 王科俊, 邹国锋, 阎涛. 基于全局与局部特征的单样本人脸识别[J]. 中南大学学报: 自然科学版, 2011, 42(增1): 760-764.

WANG Kejun, ZOU Guofeng, YAN Tao. Integration of global and local feature for single sample face recognition[J]. Journal of Central South University: Science and Technology, 2011, 42(S1): 760-764.

[11] 孙鑫, 刘兵, 刘本永. 基于分块PCA的人脸识别[J]. 计算机工程与应用, 2005, 41(2): 80-82.

SUN Xing, LIU Bing, LIU Benyong. Face recognition based on block-PCA[J]. Computer Engineering and Application, 2005, 41(2): 80-82.

[12] 谢永华, 陈伏兵, 张生亮, 等. 基于分块小波变换与奇异值阈值压缩的人脸特征提取与识别算法[J]. 计算机应用与软件, 2008, 25(1): 30-32.

XIE Yonghua, CHEN Fubing, ZHANG Shengliang, et al. Feature extraction and recognition of human face based on intersected transformation and SVD threshold compression[J]. Computer Application and Software, 2008, 25(1): 30-32.

[13] 付瑶, 刘志镜, 谷明坡. 基于小波分析的人脸特征提取方法[J]. 计算机工程与科学, 2002, 24(6): 52-54.

FU Yao, LIU Zhijing, GU Mingpo. Face feature extraction using wavelet analysis[J]. Computer Engineering and Science, 2002, 24(6): 52-54.

[14] 陈振洲, 李磊, 姚正安. 基于SVM的特征加权KNN算法[J]. 中山大学学报: 自然科学版, 2005, 44(1): 17-20.

CHEN Zhenzhou, LI Lei, YAO Zhengan. Feature-weighted K-Nearest neighbor algorithm with SVM[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2005, 44(1): 17-20.

[15] Cover T, Hart P. Nearest neighbor pattern classification[J]. Information Theory, 1967, 13(1): 21-27.

[16] HAO Zhang, Berg A C, Maire M, et al. SVM-KNN: Discriminative nearest neighbor classification for visual category recognition[C]//Computer Vision and Pattern Recognition IEEE Computer Society Conference. New York, 2006: 2126-2136.

[17] Cotes C, Vapnic V. Support vector network[J]. Machine Learning, 1995, 20(1): 1-25.

[18] Schwenker F. Hierarchical Support Vector Machines for Multi-class Pattern Recognition[C]//Proceedings of the 4th International Conference on Knowledge-based Intelligent Engineering Systems & Allied Technologies. UK: University of Brighton, 2000: 561-565.

(编辑  陈灿华)

收稿日期：2012-07-22；修回日期：2012-10-08

基金项目：国家自然科学基金资助项目(61173119)

通信作者：袁修贵(1964-)，男，湖北蓟春人，教授，从事最优化算法研究；电话：13974870869；E-mail: xgyuan@sina.com