基于多尺度稀疏近邻图的近邻保持嵌入算法*

于 露

(长春财经学院 信息工程学院， 长春 130122)

人脸识别技术在自动控制领域具有广泛的应用.邹香玲[1]将人脸识别技术应用在智能监控系统中，并利用云计算对大规模认证系统进行了优化；高翔等[2]提出一种结合人眼检测和定位的人脸识别方法，并将其用于智能会议系统中；王文明等[3]提出了一种在具备全景图合成功能应用型机器人视觉中加装人脸识别功能的方法，该方法被成功用于多领域的机器人监控系统中；李定远等[4]将基于PCA算法下的人脸识别技术应用于身份验证环节，解决了液压控制系统运行时的身份验证问题.基于近邻图的流形学习降维算法[5-7]是解决模式识别任务中“维度灾难”的有效手段，这些通过拉普拉斯特征映射进行计算的流形学习降维算法有一个共性：在原始的高维空间上建立一个样本近邻图，使用近邻图来保持原始流形空间的局部特征，然后通过求解特征值将原始流形空间上的数据映射到低维空间.正是由于该共性，文献[5]中提出了图嵌入框架理论，很多现有的降维算法[6-9]都可归入到图嵌入框架之中.在图嵌入框架理论中，近邻图的作用是尽量保持样本之间的关系在降维前后不发生改变，因此，近邻图对于图嵌入降维算法来说起着至关重要的作用.文献[9]指出，近邻图是降维算法的核心，选择一个好的近邻图构建方法比选择一个好的降维算法更重要.近邻保持嵌入算法通过近邻图来保持降维前的局部流形结构，因此它是一个典型的基于近邻图流形学习降维算法.但NPE算法有如下两个不足：1)具有二维结构的数据样本或人脸图片被转化成了向量形式，这样构建的近邻图没有考虑原始人脸图片的二维结构信息且参数k指定困难；2)NPE算法对于存在遮挡的人脸图片鲁棒性不强，当人脸图片存在遮挡时NPE取得的识别率较低.本文提出了多尺度稀疏近邻图构造方法，并称使用该方法构造的近邻图为多尺度稀疏近邻图(multi-scale sparse neighbor graph，MSNG).对于每个待识别的人脸图片，近邻图构造方法都会建立一个九个尺度的图像金字塔，并且计算金字塔中每个尺度与其他图片对应的稀疏近邻.两个图片能否成为近邻将由两个图片金字塔之间稀疏近邻的个数决定.本文将该方法构造的近邻图(MSNG)与NPE算法结合，提出了基于多尺度稀疏近邻图的近邻保持嵌入算法(MSNG-NPE).与传统NPE算法相比，MSNG-NPE算法优势如下：

1) 稀疏表示算法对遮挡具有很强的鲁棒性.多尺度稀疏近邻图构造方法通过计算一张人脸图片在每个尺度上的稀疏近邻来确定人脸图片在近邻图中的近邻，这样构造出来的近邻图对于人脸的遮挡具有鲁棒性.

2) 对于每张人脸图片，都建立一个具有九尺度的高斯金字塔，通过计算金字塔中每个尺度图片的稀疏近邻来构建近邻图.

3) 原始的近邻图构造方法需要预先指定近邻参数k，而本文提出的近邻图构造方法不需要指定近邻参数.

1 相关算法

1.1 局部保持嵌入算法

设含有N个图片样本的人脸数据集为I={I1，I2，…，IN}，图片的尺寸为n×m.令X={x1，x2，…，xN}为数据集I中人脸图片的向量形式.NPE的近邻图可以表示为G={V，W}，其中，V为图G的顶点集合，即V对应着集合X；W为带权邻接矩阵，wij为两个样本xi和xj在近邻图中对应的顶点vi和vj之间邻接边上的权值.NPE算法描述如下：

1) 确定近邻.若xi是xj的k近邻之一，或者xj是xi的k近邻之一，则两个样本在图G中是邻接的.

2) 计算权重.通过最小化目标函数来计算邻接边上的权值，即

(1)

若Y={y1，y2，…，yN}是集合X在低维空间的数据映射，则映射关系为Y=αTX，其中，α为NPE的映射向量，其计算表达式为

XMXTα=λXXTα

(2)

式中，M=(I-W)T(I-W)，且I=diag(1，1，…，1).式(2)的解为α0，α1，…，αd-1，它们与特征值λ0≤λ1≤…≤λd-1相对应.

1.2 稀疏表示算法

若X={x1，x2，…，xN}表示数据集I中人脸图片的向量形式.对于一个新的样本Y，稀疏表示的目标是使用集合X中尽量少的样本来表示样本Y.若Y=Xs0，s0为系数向量，s0=[0，…，0，a1，a2，…，aj，0，…，0]T.稀疏表示的目标函数[10]为

(3)

式(3)是一个l1范数最小化问题，可以通过正交匹配(orthogonal matching pursuit，OMP)算法[11]来计算.

2 多尺度稀疏近邻图的近邻嵌入算法

设含有N个图片样本的人脸数据集I={I1，I2，…，IN}，图片的尺寸为n×m.令X={x1，x2，…，xN}表示数据集I中人脸图片的向量形式.MSNG可以表示为MSNG={V，WMSNG}，与传统近邻图类似，V和WMSNG分别表示顶点集合和带权邻接矩阵.MSNG的构造过程如下：

1) 建立图像金字塔.对于一个人脸图片建立如图1所示的具有九个尺度图像金字塔.图像金字塔中图像的尺寸从原始尺寸(尺度1)到原始尺寸的20%(尺度9).

图1 九个尺度的图片金字塔Fig.1 Image pyramid with nine scales

3) 计算每个人脸图片Ii的近邻.设Nij表示图片Ij对应金字塔的所有尺度图片中成为了图片Ii对应的金字塔中图片的近邻，Nij描述了两个样本间的相似程度，即Nij的值越大，两个样本图片Ii和Ij就越相似.带权邻接矩阵WMSNG可以表示为

(4)

3 实验仿真

3.1 人脸遮挡鲁棒性实验

本节实验在AR人脸数据库上进行，AR人脸数据库含有来自126位志愿者的超过4 000张的人脸图片[12].部分AR数据库中的人脸上有遮挡物，例如墨镜或者围巾.本文建立了一个AR数据库的子集，该子集中含有50位男性志愿者，其中每个志愿者13张照片.在这13张照片中有6张照片是含有遮挡的.图2为本文AR数据库子集的人脸样本图片.

图2 AR数据库中的人脸样本图Fig.2 Face sample images in AR database

首先对比MSNG和传统近邻图构造方法在人脸上有遮挡情况下正确寻找近邻的能力.分别使用MSNG和传统的近邻图构造方法来寻找AR数据库中第2个志愿者的第5张照片的近邻.设置传统近邻图构造方法的近邻参数k=6，将MSNG计算出来的前6个近邻与传统近邻图计算出来的6个近邻进行比较，两种近邻图构造方法选择出来的人脸近邻如图3所示.

从图3a可以看出：人脸近邻1～4都属于第二个志愿者.尽管人脸图片2～4存在遮挡，但是MSNG还是正确将其作为人脸图片5的近邻.从图3b可以看出：传统的近邻图构造方法计算出来的6个近邻图片都不属于第二个志愿者.通过这个实验可以看出，在存在遮挡的情况下，传统的近邻图构造方法无法正确计算出每个样本的k近邻，从而导致所构造的近邻图质量不高，最终导致识别率低.

在AR数据库上进行人脸识别实验，Gm/Pn表示在一轮实验中每个志愿者选择m张图片用于训练，其余n张图片用于测试.对于每一轮实验，都随机产生50组Gm/Pn的数据，本轮最终的实验结果为这50组数据得到结果的平均值.表1对比了NPE算法和MSNG-NPE算法的平均识别率，NPE算法的近邻参数设置为Gm.

从表1中可以看出，由于遮挡干扰了近邻图的构建，NPE算法取得了很低的识别率，但是MSNG-NPE算法取得了较为满意的识别率.

3.2 人脸识别实验

本节在ORL和YALE数据库上进行人脸识别实验.YALE数据库中有11个志愿者，每人11张照片，总共有121张人脸图片[13]，YALE数据库中照片尺寸是100×100；ORL数据库中有40个志愿者，每人10张照片，共有400张人脸图片[14]，ORL数据库中照片的尺寸是112×92，设置传统近邻图构造方法的近邻参k=6.图4、5分别为ORL和YALE人脸库的样本照片，表2、3分别是在ORL和YALE人脸库上进行人脸识别的实验结果.

图3 志愿者2第5张照片的近邻比较Fig.3 Comparison in neighbors of No.5face image of No.2 volunteer

图4 ORL数据库中的人脸样本图Fig.4 Face sample images in ORL database

图5 YALE数据库中的人脸样本图Fig.5 Face sample images in YALE database

测试类型NPEMSNG-NPEG2/P861.5471.01G3/P770.4177.88G4/P677.3883.84G5/P582.3786.01G6/P485.2385.89G7/P388.0589.32

表3 YALE数据库上的平均识别率Tab.3 Average recognition accuracy in YALE database %

从表2、3中的实验结果可以看出：随着训练样本数量的增加，两个算法的平均识别率都逐渐提高；在ORL和YALE数据库上进行实验时，使用MSNG-NPE算法所取得的人脸识别率都超过了使用NPE算法进行人脸识别所取得的识别率.

4 结 论

本文提出了一种近邻图构造方法，方法对于每个人脸图片建立一个具有九个尺度的图片金字塔，并计算金字塔中每个尺度图片的稀疏近邻.用两个人脸图片金字塔之间成为稀疏近邻的个数来决定是否这两个人脸图片在最终的近邻图中可以成为近邻.之后，将MSNG与NPE算法结合，提出了MSNG-NPE算法，在几个著名人脸数据库上的实验结果显示，MSNG-NPE算法具有比传统的NPE算法更好的识别效果.