田亚娜，童 莹，曹雪虹

(1.南京邮电大学 通信与信息工程学院，江苏 南京 210003；2.南京工程学院 通信工程学院，江苏 南京 211167)

1 概 述

随着信息技术的发展，高维数据的问题普遍存在，尤其是在许多模式识别和数据挖掘运用中，比如人脸图像识别和生物基因数据分析等。在高维数据的分析和学习中，数据降维有着非常重要的作用。数据降维不仅使得数据便于存储和计算，而且能够去除数据冗余信息，找到高维数据的低维表示以利于分析。目前，已有许多种数据降维方法成功运用到模式识别、图像处理等领域。

在现有的数据降维方法中，主成分分析(PCA)[1]和线性判别分析(LDA)[2]都是在图像数据满足高斯分布的假设条件下，计算图像的全局欧式结构来进行降维分析，没有分析局部结构特征。在实际运用中，很多人脸数据并不满足高斯分布，而且高维数据的局部结构特征对表示图像和图像分类判别是非常重要的。后来，流形学习成了研究热点，通过学习高维空间中样本的局部邻域结构，从高维空间中找到低维流形以实现维数约简。最有代表性的流形学习算法有拉普拉斯特征映射(LE)[3]、局部线性映射(LLE)[4]和局部保持投影(LPP)[5]等。LE是用一个无向加权图来描述一个流形图，在保持图的局部邻接关系的情况下，从高维空间降到低维表示空间；LLE是寻找每个样本的局部近邻点并计算样本的重建权值矩阵，通过保留嵌入在高维原始数据中的低维局部线性结构关系进行降维；LPP是构建高维空间中各样本的远近亲疏关系图，在降维投影时保持这种关系图不变来分析数据的局部结构特征。尽管这些算法的实现方法不一样，但它们的实现原理都可以统一到图形嵌入框架[6]。也就是说，它们的区别在于图结构的构造不同和边权重的计算不同。图结构的不同构造方法是不同降维算法的重点。LPP邻接图通过映射使得高维空间中邻域范围内的点在低维空间中尽可能近，同时使得其他不在邻域内的点通过映射在低维空间中尽可能远。而这些算法都非常依赖于参数的选择，需要人工选择邻域大小参数和边权重参数。

近年来，基于稀疏表示的方法在人脸识别中得到广泛应用。Wright等[7]提出将稀疏表示用在图像分类中，并且得到了很好的分类结果。文献[8-9]中认为稀疏表示能够很好地表征数据的局部结构关系。基于稀疏表示的概念，乔立山运用稀疏表示系数构建一种新的图结构，提出稀疏保留投影(SPP)算法[10]。算法实现过程中，稀疏表示系数是通过最小化L1范数求得，因此这种邻接图又叫L1图，L1图的构建过程继承了稀疏重构的优点，同时解决了人工参数选择的问题。文献[11-13]也相继提出基于稀疏表示方法构建L1图进行人脸识别。文献[14]在最小化L1正则化目标函数中引入了类别信息再结合稀疏重构误差来分析投影矩阵。文献[15]提出了一种判别稀疏邻域保持嵌入算法，通过结合SPP和最大边缘准则进行投影，提高了人脸识别率。

在稀疏保留投影算法获得重构关系时，既没有利用不同类样本的类别信息，也没有充分考虑同类样本间的相似问题。文中提出一种新的有监督的判别稀疏保留投影方法(DSPP)。首先利用样本系数与类内样本的平均系数之差来重新定义类内离散度，在获得稀疏重构关系时，对每个训练样本仅利用和样本同类别的其余样本来线性表示，同时添加类内散度约束项以减小每个类的表示系数的变化。这样得到的稀疏表示系数具有更好的判别能力，能够保留不同类样本之间具有判别性的结构信息，然后再通过最小化重构误差准则，保留投影获取有效的人脸特征信息来提高分类识别能力。

在人脸识别过程中，对原图像直接分类判别能够得到一定的识别率，可是受光照、表情、姿态等的变化会对人脸图像的识别造成不利影响。为克服这些因素的影响，提取有效的表征人脸信息的特征也是至关重要的。梯度方向直方图(histograms of oriented gradients,HOG)算子[16-17]是通过局部梯度大小和边缘信息将图像局部特征化，是一种局部信息描述算子。HOG特征具有很好的鲁棒性，能够很好地表征人脸的特征。文中在HOG算子提取图像特征的基础上，用DSPP方法降维处理再进行分类判别，并通过实验对其进行验证。

2 HOG特征提取

HOG算子[17]通过计算图像局部区域的梯度，并统计分布在不同方向的梯度幅值，得到梯度方向直方图来构成HOG特征。图像的局部外观和形状通过局部梯度和边缘信息得到很好的表征和描述。HOG特征具有对方向、尺度、光照的不敏感性，对图像区域的小变化保持不变性。HOG算子提取图像特征的过程如下：

(1)遍历图像的所有像素点，并计算各个像素点的梯度幅值和梯度方向，捕获图像边缘信息，弱化光照的干扰。

(2)将图像均匀划分为2×2像素的单元(cell)并对每个单元的梯度方向进行统计。将[0,π]分为9个区间，平均每20°为一个区间(bin)，这样每个单元获得一个9维的梯度方向直方图。

(3)把相邻的2×2个不重叠的cell组合成一个网格(block)，将每个block块内的4个cell的直方图拼接，经过L2-norm标准化处理，得到一个block块的梯度直方图。

(4)将一张图像划分的所有block块的梯度直方图进行拼接，统计得到整个图像的HOG特征。

对于大小为32×32的一幅图像，可划分为64(8×8)个block块，得到的HOG特征维数为2 304(8×8×4×9)。HOG算子有良好的局部特性，对于光照等变化的影响具有鲁棒性，是提取图像特征的有效算子。

3 稀疏保留投影(sparsity preserving projections，SPP)

不同于LLE[4]、LPP[5]等流形学习方法，SPP[10]是利用稀疏表示的原理构建样本之间的重构关系图，再通过最小化重构误差准则进行最优化投影，使得高维空间中样本之间的重构关系在低维空间中保持不变。

受稀疏表示的启发，每个图像样本可以由其余样本稀疏表示，样本之间的关系可以通过稀疏系数来表示。许多研究[18-19]表明，通过求解L1范数最小化可以得到最优稀疏表示系数。图结构有效地表征数据之间的相互关系，用得到的稀疏系数构建的邻接图叫做L1图，用L1图结构来表示样本图像之间的关系。假设有n个训练样本，样本集记为X=[x1,x2,…,xn]，X∈Rm×n，通过求L1范数最小化问题构建邻接图ζ={X,W}来表示样本之间的相互关系。对任一训练样本xi：

(1)

其中，Xi=[x1,…,xi-1,xi+1,…,xn]∈Rm×(n-1)表示除xi以外的其余训练样本构成的矩阵；wi=[wi1,…,wij,…,win]T∈Rn-1表示系数向量；wij表示训练样本xj对重构xi的稀疏表示系数值，系数值越大表示对应样本和重构样本越相似。再依次求得每个训练样本的稀疏表示系数向量，得到W=[w1,…,wi,…,wn]，也就构建完成L1邻接图。

由得到的L1邻接图，根据最小化重构误差准则，通过最优化目标函数得到一个线性投影，使得样本之间的重构关系在降维前后保持不变，其目标函数是：

(2)

X(W+WT-WTW)XTp=λXXTp

(3)

将训练样本和测试样本分别在投影矩阵上进行投影降维，然后再进行分类识别。SPP算法利用L1范数最小化问题分析样本之间的稀疏重构关系，既没有人工参数选择，也具有很好的鲁棒性和适应性，在人脸识别中得到明确的验证和运用。

4 判别稀疏保留投影(discriminant sparse preserving projection，DSPP)

稀疏保留投影算法在构建图结构时用其余所有的训练样本线性表示某一个样本，保留高维空间中数据的稀疏重构关系，没有利用不同样本的类别信息，也没有充分考虑同类样本之间的相似性。为了提高SPP算法的分类识别性，文中提出了一种判别稀疏保留投影算法(DSPP)。该算法利用样本的标签信息同时添加类内散度约束项，获得样本的稀疏重构关系，通过构建新的具有判别性的邻接图结构来保留样本之间的相互关系，再由最小化重构误差得到最优线性投影，从而提取更有效的人脸信息进行分类识别。

4.1 构建邻接图

(4)

其中，xi为任意一个训练样本；X为由除xi以外并且和xi有相同类别的训练样本组成的矩阵；si为X训练样本集对样本xi的线性表示系数；λ为大于零的参数。

有研究[20]表明，L1范数的稀疏约束在基于稀疏表示的人脸识别中没有起到至关重要的作用，这里用F范数替代L1范数对系数进行正则化约束。Γ是与xi有相同类别的所有样本的平均表示系数，最小化目的是使相同类别的样本的表示系数接近它们的平均值，以减小每类的系数向量的变化，使每类类内散度最小化。

式(4)变形化简得到：

(5)

式(5)对si求偏导，并令偏导式右边等于0，整理可得到最优si：

si=XTX+(λ+1)-1(XTxi+Γ)

(6)

由计算得到si=[si1,…,sij,…,sini],j∈X，构建新的样本之间的邻接图关系ζ={X,W}，其中W=[w1,…,wi,…,wn]∈Rn×n，wi=[wi1,…,wij,…,win]T，wij定义为：

(7)

4.2 最优化投影

上述邻接关系图的构建过程中，不仅利用不同类样本的类别信息，而且充分考虑了同类样本集的相似性，通过计算稀疏表示系数很好地表示了样本之间的关系。

图结构矩阵W表示了高维空间中各样本之间的内在关系，为了在低维空间中最大限度地保留这种关系，类似SPP算法，通过最小化重构误差函数得到最优投影：

(8)

其中，P为投影矩阵；wi为样本xi的稀疏重构系数；约束项是为了防止退化解。

通过数学公式推导，可转化得到如下最优化问题：

s.t.PTXXTP=I

(9)

令Wβ=W+WT-WTW，为计算严谨，转换最小化问题为求解一个最大化问题。

(10)

求解最优解P即转化为求解广义特征值问题，XWβXTp=λXXTp，选取前d个最大特征值对应的特征向量构成投影矩阵，记为WDSPP=[p1,p2,…,pd]。将训练样本X在WDSPP上进行投影，得到一个d×n维矩阵，同样也将测试样本在WDSPP上进行投影，得到具有判别性的人脸信息后再进行分类识别。

5 实验仿真

为了验证算法的有效性，与其他算法(PCA[1]、LDA[2]、LPP[5]、LSDA[21]、SPP[10])进行比较。DSPP算法中，参数λ设置为0.05。文中采用Extended Yale B人脸库[22]和LFW人脸库[23]进行实验。所有实验采用稀疏表示分类方法进行分类识别，通过用训练样本集对测试样本进行稀疏表示，求出稀疏系数向量，根据系数向量对测试样本在每个类上进行重构，分别计算测试样本和每类的重构样本之间的残差，将测试样本判别为残差最小的类。

5.1 Extended Yale B库

Extended Yale B库包含38类人在光照条件变化的情况下获得的人脸照片，图像大小为192×168，每类人有大约64张，共2 414张正面对齐图像。选取有64张图像的人脸作为实验数据，共31类，共1 984张图像，并且每张图像大小裁剪调整为32×32大小，并进行归一化处理。图1为Extended Yale B人脸库中某类人的一些样本图像。

图1 Extended Yale B库的样本图像

实验包括两部分，分别是对人脸原图像的分类识别和基于原图像HOG特征的分类识别。在每类人的图像中随机选取10个样本进行训练，其余样本用于测试，重复进行10次，最后计算得到平均值和标准偏差。表1是对Extended Yale B库的人脸原图像在不同方法下的平均识别率和标准偏差；表2是在Extended Yale B库人脸图像HOG特征的基础上再利用不同方法降维的平均识别率和标准偏差。

表1 Extended Yale B库原图像的实验结果

表2 Extended Yale B库图像HOG特征的实验结果

从表1可以看出，文中提出的DSPP算法的识别率相比其他算法有很大提升，提高到89.10%，主要原因是DSPP算法实现过程中同时考虑了不同类的类别信息和相同类的离散度信息，在降维过程中更充分地保持了数据的内在结构和便于分类的结构信息，从而更好地提高了识别率。结合表1和表2可以看出，相比原图像的分类判别，基于人脸图像HOG特征的分类判别结果有明显提高，主要原因是HOG算子是具有鲁棒性的局部特征描述子，HOG特征很好地表征了图像的局部特征，提取了有效的人脸特征信息，从而取得了较高的识别率。

5.2 LFW库

LFW库包含5 749类人的13 233张人脸图像，图片大小为250×250，其中1 680类人有两张以上的图片，剩余的4 069类人只有一张图片。实验中，选取有20张以上(包括20张)图像的人脸作为实验数据，共62类，共3 023张图像。基于图论的视觉显著性算法对图像检测人脸区域，并调整图像大小为128×128，再进行归一化处理。图2为LFW人脸库中某类人的一些样本图像。

图2 LFW库的样本图像

实验包括两部分，分别是对人脸原图像的分类识别和基于原图像HOG特征的分类识别。实验过程中，对每类人的图片分别随机选取10个样本进行训练，其余样本用于测试，即有620个训练样本，2 403个测试样本，重复进行10次，最后以计算得到的平均值和标准偏差作为最后的识别结果进行分析。结果如表3和表4所示。

表3 LFW库的原图像的实验结果

表4 LFW库的图像HOG特征的实验结果

从表3可以看出，对LFW人脸库原图像分类判别，DSPP算法取得57.06%的识别率，比PCA、LDA、LPP、LSDA、SPP的识别结果分别提高22.74%、7.13%、8.31%、11.55%、18.82%，识别效果提高明显。

从表4可以看出，在LFW库人脸图像HOG特征的基础上，DSPP算法的识别率达到77.93%，比对人脸原图像识别结果提高20.87%，充分验证了该算法的可行性和有效性。

6 结束语

提出一种新的判别性稀疏保留投影算法，在构建数据间的稀疏重构关系时，同时考虑样本不同类的类别信息和相同类的类内散度信息，保持了数据具有判别性的内在结构信息，提高了人脸图像的识别率。鉴于HOG算子能够描述图像的局部特征，克服了图像对光照、姿态等变化的影响，具有很强的鲁棒性。所以该算法能够提取得到更有效的人脸特征信息，使得人脸识别效率有了进一步的提高。

[1] ABDI H,WILLIAMS L J.Principal component analysis[J].Wiley Interdisciplinary Reviews:Computational Statistics,2010,2(4):433-459.

[2] IZENMAN A J. Linear discriminant analysis[M]//Modern multivariate statistical techniques.New York:Springer,2013:237-280.

[3] BELKIN M,NIYOGI P.Laplacian eigenmaps for dimensionality reduction and data representation[J].Neural Computation,2003,15(6):1373-1396.

[4] ROWEIS S T,SAUL L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.

[5] HE X,YAN S,HU Y,et al.Face recognition using Laplacianfaces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(3):328-340.

[6] YAN S,XU D,ZHANG B,et al.Graph embedding and extensions:a general framework for dimensionality reduction[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(1):40-51.

[7] WRIGHT J,YANG A Y,GANESH A,et al.Robust face recognition via sparse representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(2):210-227.

[8] WRIGHT J,MA Y,MAIRAL J,et al.Sparse representation for computer vision and pattern recognition[J].Proceedings of the IEEE,2010,98(6):1031-1044.

[9] ELHAMIFAR E,VIDAL R.Sparse subspace clustering:algorithm,theory,and applications[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(11):2765-2781.

[10] QIAO L,CHEN S,TAN X.Sparsity preserving projections with applications to face recognition[J].Pattern Recognition,2010,43(1):331-341.

[11] YANG J,CHU D,ZHANG L,et al.Sparse representation classifier steered discriminative projection with applications to face recognition[J].IEEE Transactions on Neural Networks and Learning Systems,2013,24(7):1023-1035.

[12] 杜 春，孙即祥，周石琳，等．基于稀疏表示和非参数判别分析的降维算法[J]．国防科技大学学报，2013，35(2)：143-147.

[13] GAO Q,HUANG Y,ZHANG H,et al.Discriminative sparsity preserving projections for image recognition[J].Pattern Recognition,2015,48(8):2543-2553.

[14] ZANG F,ZHANG J.Discriminative learning by sparse representation for classification[J].Neurocomputing,2011,74(12):2176-2183.

[15] GUI J,SUN Z,JIA W,et al.Discriminant sparse neighborhood preserving embedding for face recognition[J].Pattern Recognition,2012,45(8):2884-2893.

[16] DALAL N,TRIGGS B.Histograms of oriented gradients for human detection[C]//IEEE computer society conference on computer vision and pattern recognition.[s.l.]:IEEE,2005:886-893.

[18] CHENG B,YANG J,YAN S,et al.Learning with l1-graph for image analysis[J].IEEE Transactions on Image Processing,2010,19(4):858-866.

[19] YANG Y,WANG Z,YANG J,et al.Data clustering by Laplacian regularized L1-graph[C]//Twenty-eighth AAAI conference on artificial intelligence.[s.l.]:[s.n.],2014:3148-3149.

[20] ZHANG L,YANG M,FENG X.Sparse representation or collaborative representation:which helps face recognition?[C]//2011 International conference on computer vision.[s.l.]:IEEE,2011:471-478.

[21] GAO Q,LIU J,CUI K,et al.Stable locality sensitive discriminant analysis for image recognition[J].Neural Networks,2014,54:49-56.

[22] LEE K C,HO J,KRIEGMAN D J.Acquiring linear subspaces for face recognition under variable lighting[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(5):684-698.

[23] HUANG G B,RAMESH M,BERG T,et al.Labeled faces in the wild:a database for studying face recognition in unconstrained environments[R].Amherst:University of Massachusetts,2007.