基于HOG-AP的人脸图像识别算法*

陈赛英，何建农

(福州大学 数学与计算机科学学院，福建 福州350108)

目前,图像目标识别算法已经广泛应用于各个领域，包括军事、交通、公安、医学、工业、遥感图像处理、摄影测量自动化等[1]。

针对图像目标识别国内外学者相继提出了多种方法,如粒子群优化算法和仿生模式识别法等,但这些方法具有局限性。粒子群优化算法主要是针对连续函数优化问题，但当自变量是整数时，例如生产调度、路由选择以及很多整数规划问题[2-3],则不能应用该算法来解决。仿生神经元网络是针对高维数据进行处理，它的计算量非常大，在实现时，需要对数据进行降维[4]。仿射传播AP(Affinity Propagation)算法具有简单、高效的优势，已经广泛应用于多种领域，例如设施选址、图像识别、图像分割等[5],但在应用中还存在一些问题，如缺乏判定最优聚类结果的指标以及收敛性能不够好。

图像目标识别的关键问题是选取图像的特征，用于识别的图像特征有颜色、纹理、形状、空间关系等，但是这些特征都存在一些缺点。颜色特征对图像或图像区域的方向、大小等变化不敏感，当图像的分辨率变化时，所计算出来的纹理可能会有较大偏差[6]。空间关系特征常对图像或目标的旋转、反转、尺度变化等比较敏感。而方向梯度直方图HOG(Histograms of Oriented Gradients)描述子具有如下的优点：可以描述局部的形状信息，不受平移、旋转和光照变化的影响，可以很好地表征图像局部像素点之间的关系[5,7-8]。

基于以上原因，本文对AP算法进行改进，提出了提取图像的HOG特征进行聚类识别的改进算法。

1 相关概念及算法

1.1 HOG

HOG描述子的主要思想是一幅图像中物体的表象和形状可以被像素强度梯度或边缘的方向分布很好地描述。其实现方法是,先将图像分成小的方格单元连通区域,然后采集方格单元中各像素点的梯度方向或边缘方向直方图,最后把这些直方图组合起来就可以构成特征描述子[7,9]。

1.2 收缩因子

[10]的研究表明,使用收缩因子可以有效保证算法收敛。收缩因子的公式为：

在数值实验中，φ取值为4.1，因此ρ=0.729。收缩因子可以调节收敛系数，以加速收敛过程。

1.3 指标

(1)Silhouette指标

样本t的Silhouette指标为:

其中，a(t)为聚类Cj中的样本t与类内所有其他样本的平均不相似度或距离；d(t,Ci)为样本 t到另一个类 Ci的所有样本的平均不相似度或距离，则:

(2)Hartigan指标

Hartigan指标适用于类数估计,其满足Ha≤10的最小类数作为最优的聚类个数:

在有效性指标中，Silhouette指标[11]具有性能好、简单易用、既能评价聚类结果的优良程度也能确定聚类个数的优势，所以得到广泛的应用，选择它对半监督仿射传播算法的运行进行监督和指导是合适的。但是Silhouette指标在聚类个数为1时没有定义,于是采用 Hartigan指标[11]进一步判断是否只有一个聚类。

1.4 AP算法

AP算法不需要事先指定聚类数目，在迭代过程中不断搜索合适的聚类中心，自动从数据点间寻找类中心的位置及个数。算法开始时把所有的数据点都作为潜在的聚类中心，通过数据点间的“信息传递”来实现聚类过程。与传统的K均值算法对初始聚类中心的选择的敏感性相比，AP算法是一种具有确定性的聚类算法，多次独立运行的聚类结果一般比较稳定[12]。

AP算法主要根据N个样本点之间的相似度进行聚类,这些相似度组成N×N的相似度矩阵S,如S(i,j)=‖xi-xj‖表示样本点i和样本点 j之间的相似度。AP算法通过迭代过程不断更新每一个点的责任值(Responsibility值)和有效值(Availability值)，直到自动产生若干个高质量的聚类中心，同时将其余的数据点分配到相应的类中[12]。

2 基于HOG的AP改进算法

AP算法存在两个问题：一是很难确定何时能够使算法产生最优的聚类结果，即没有一个判定最优聚类结果的指标；二是AP算法中收敛系数常作为固定参数在算法运行中保持不变，因此其收敛性能不好。针对AP算法存在的两个问题，本文提出基于HOG的AP改进算法。

2.1 算法的主要思想

首先提取图像的HOG特征向量；然后在AP算法基础上引入收缩因子调节收敛系数[10]，以加速AP算法的收敛过程，改善AP算法的收敛性能；最后将评价聚类质量的有效性指标嵌入算法的迭代过程，依据比较小的来产生各个聚类中心，其聚类目标是有效性指标所指示的最好聚类质量，因此能够监督并引导算法向着最好聚类质量的方向运行[13]。

2.2 算法的主要步骤

(1)计算HOG特征向量。本文计算HOG特征所使用的一些参数设置如下:没有Gamma校正等光照预处理；梯度计算采用简单的中心对称算子；没有图像平滑；采样窗口大小为 8×8,分为 4个 4×4像素的 cell；没有计算高斯加权范围；初始的方向角是0～180°,分为 9个块；L2-norm的block标准化方法；块与块之间没有重叠。

(2)算法初始化,将步骤(1)的 HOG特征向量作为输入，计算初始相似度矩阵 S(i,j)=-‖xi-xj‖;偏向参数 p=pm，pm=median(median(S))； 下 降 步 幅 为 step=pmin/10,pmin=max(max(S))，；收敛条件为聚类中心30次循环无变化、终止参数为最大循环次数Cy=1 000或者聚类中心300次循环无变化。

(3)A(i,j)、R(i,j)初始化为零矩阵，计算样本点间的Responsibility值:

其中，A(i,j)表示 j对于 i的 Availability值。

(4)计算样本点间的Availability值:

(5)Responsibility值和Availability值的更新：

其中，ρ是收缩因子，调节收敛系数λ，以加速AP算法的收敛过程。

(6)运行m次迭代过程，算法产生K1个候选的聚类中心，则给出K1个聚类并计算Silhouette指标值Sil1。

(7)以步幅step减小参数p为p=p+step，继续迭代过程，若产生的聚类数目下降收敛到某个类数K2，则计算K2个聚类的Sil2，同时计算所有指标值中的最大值Silmax，当 Sil2＜Silmax时，则统计 Silhouette指标值连续下降的次数Hc；否则，再用步幅step减小参数p，直到产生更小的类数 Ki。

(8)依此类推,若在迭代的某一步中检测到Hc＞K1/2(Sil连续下降表明最优结果已找到)或 K达到 2，则算法终止，将Silmax对应的聚类结果作为最优结果输出。若算法终止时Silmax对应的聚类个数K=2,则再计算Hartigan指标，判别K=1和K=2哪个更优。

(9)输出最优聚类数目和对应的聚类结果,算法终止。

3 算法性能分析

3.1 仿真实验

对于本文提出的改进算法,依次用ORL、BioID和YALE 3类图像分别进行实验，并与AP算法的实验结果进行比较。3类图像的示例图片如图1～图3所示。实验结果如表1所示。

图1 ORL人脸库示例图片

图2 BioID人脸库示例图片

图3 YALE人脸库示例图片

表1 实验结果

其中，ORL是提取ORL人脸数据库中的4类人的人脸图像的HOG特征得到的数据集，每类各10张，共40张。BioID是提取BioID人脸数据库中的4类人的人脸图像的HOG特征得到的数据集,每类40张,共160张。YALE是提取YALE人脸数据库中的5类人的人脸图像的HOG特征得到的数据集，每类各10张,共50张。

当聚类结果的错误率大于20%时，错误率指标可能不准确。因为计算错误率程序比较简单，不能处理复杂的情况，此时可以采用外部有效性指标FM(Fowlkes-Mallows)对聚类结果的质量进行评价[11]。FM计算公式为：

其中，C、C′是聚类中两个不同的类，C11表示在 C、C′上的同一类数据对的数量；C01表示在C′上但不在C上的同一类数据对的数量；C10表示在C上但不在C′上的同一类数据对的数量；C00表示不在C、C′上的同一类数据对的数量。FM值处于0与1之间，且越大表示一致性越好，当聚类结果与正确类标完全一致时，FM=1。

3.2 实验结果分析

从表1可以看出,在仿射传播算法中嵌入指标，使算法向最好聚类质量的方向运行，可得到更加接近正确类数的类数、提高FM值、降低错误率，可是时间却没有节省；而引入收缩因子之后，加速了AP算法的收敛过程，比单独嵌入指标，时间上明显减少。

本文首先提取图像的HOG特征向量，然后用基于HOG的AP改进算法对图像聚类进行识别。改进算法引入收缩因子调节收敛系数，加速了AP算法的收敛过程，改善了AP算法的收敛性能，并同时将评价聚类质量的有效性指标嵌入算法的迭代过程，使算法向最好聚类质量的方向运行。实验表明，本文算法对小类数样本具有较好的识别能力，不仅得到更接近正确类数的结果，较大幅度提高了FM值，还显著地降低了错误率，是一种有效的图像目标识别新算法。

参考文献

[1]盖光建.基于图像的特征信息提取与目标识别[D].哈尔滨：哈尔滨理工大学，2009.

[2]李太勇，吴江，朱波,等.一种基于距离度量的自适应粒子群优化算法[J].计算机科学，2010，37(10)：214-216.

[3]孙焱，和多田淳三，翁培奋.基于粒子群优化算法的行人识别与跟踪方法研究[J].计算机工程与设计，2011(3):988-990.

[4]王宪宝，陆飞，陈勇,等.仿生模式识别的算法实现与应用[J].浙江工业大学学报，2011，39(1)：71-74.

[5]赵健，唐洁，谢瑜.仿射传播算法在图像聚类应用中的实现与分析[J].计算机应用研究，2012，29(10)：3980-3982.

[6]何鹏，王福刚，王成琳.基于马尔科夫随机场的炉膛火焰图像分割[J].电子技术应用，2012,38（11）:133-135.

[7]DALAL N,TRIGGS B.Histograms of oriented gradients for human detection[C].IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Washington,2005,2:886-893.

[8]黄茜，刘军，彭啸,等.基于局部二元模式特征的行人检测[J].计算机工程与设计,2011(6):2119-2123.

[9]张璐，陈淑荣.基于ROI区域强分辨力 HOG特征的视频行人检测[J].微型机与应用，2013,32(7):46-49.

[10]DUECKD,FREY B J,JOJICN,et al.Constructing treatment portfolios using affinity propagation[C].Proceedings of International Conference on Research in Computational Molecular Biology(RECOMB),Singapore,Springer,2008:360-371.

[11]DUDOIT S,FRIDLYAND J.A prediction-based resampling method for estimating the number of clusters in a dataset[J].Genome Biology,2002,3(7):1-21.

[12]FREY B J,DUECK D.Clustering by passing messages between data points[J].Science,2007,315(5814):972-976.

[13]陈伟.基于网格的K-means算法与聚类有效性指标[D].天津：天津大学，2009.