先撇开人脸检测问题，来看看直方图。

 

直方图Histogram，是一种常见的概率分布的非参数（区别于高斯分布，泊松分布等用参数表达概率密度的方法）表达方法。直方图可以看成概率密度分布的离散化表达方法。它的计算很简单，是一种投票的方法，就是每个样本往对应的小盒子(bin)里投一票。假设N个样本数据x量化为1～M之间的整数，那么Hist是M维数组，对应的直方图计算方法如下：

为了表示成概率分布，需要Hist数组和为1：

在这里sum(Hist)等于样本个数N。以上“投票+归一化”两个步骤，其实可以和成一步，即每个样本x[i]有一个对应的权重w[i]=1/N，投票的时候往小盒子里放的是权重：

 

 

这样得到数组Hist里的每个值都是一个0-1之间的小数，表示当x取这个值(数组对应的下标)时候的概率。

 

如果想改变一个概率分布取曲线的形状，比如，在训练的时候要强调x[i]=3的样本，一种办法是增加这种样本的个数，使Hist[3]变大，另一种方法是增加和它对应的样本的权重w[i]，让某些样本产生“一个顶俩”的效果，这两种方式都能起到改变概率分布的作用。

 

对人脸检测这类基于图像的目标检测方法，需要搜集大量样本进行离线的训练，样本要尽可能覆盖所有可能的情况，从而使所提取特征的概率分布具有代表性，当样本数趋向于无穷大的时候，概率分布就趋向于真实的分布情况。但通常在实际中，样本数总是有限的，这时就可以通过增加某些比较重要的样本的权重，来达到看起来是增加了某些样本数量的效果。

 

另外，直方图数组Hist的某个bin中的样本权重的改变，不应该仅仅影响当前的bin，也应该对周围相邻的bin造成影响。比如，在统计一个地区人群的身高分布的时候，如果只有一个样本x=1.65m，我们可以在Hist数组中对应1.6<=x<1.7这一个bin里投上一票，但是1.5<=x<1.6和1.7<=x<1.8两个bin的得票为0。其实不应该这样，根据身高应该是连续分布的这一假设，从样本x=1.65m可以安全地推断出世上也应该有身高1.59和1.71的人，这样左右两个相邻的bin的值就不应为0，应该也受到x=1.65m这个样本的影响，这种影响可以假设是服从高斯分布，即越远的bin受影响越小。这其实是另一种常见的概率密度估计的非参数方法，kernel density estimation(KDE)。我们的人脸检测应用由于样本足够多，所以没有考虑这一方法。也就是说，每个特征值在投票的时候，只对一个bin起作用，不影响相邻的那两个。

 

三.根据当前分类结果改变样本的权重并选择“好”的特征
对于人脸检测问题，我们希望两类（faces and nonfaces）模式特征的分布离得比较远，或者看起来分得比较开。举例来说，假设我们在所有样本上提取如下3种特征，此时feature pool尺寸是3，我们要从里面选2个最好的特征：

 

这个图表示的是3种计算特征的方法，用矢量表示分别是[2,5,5,16,4]，[2,5,5,12,4]，[3,5,5,5,7]。每个矢量中5个数的含义是：[特征种类，矩形左上角坐标的x，y，单个矩形的宽，高]；特征计算方法是白色矩形内的像素和减去黑色矩形内的像素和。其中第1个和第2个特征只在尺寸上有很小的差别，接下来的试验就是希望说明这两个特征的确是有很高的相关性的，在分类能力上是冗余的，而第3个特征和第1、2两个特征则基本上是不相关的。

 

我们先把这三个特征对于所有样本的概率分布（直方图的数组长度为64，也就是说特征值在所有可能的表达范围里量化为64级）画出来看看（蓝色曲线表示正样本，红色表示负样本）：

 

可以看出所有特征的两类分布都有很大的重叠，如前所述，‘好‘的特征是指两个曲线的'差别'比较大。表达概率分布曲线之间的“距离”的度量方法有很多，参考论文中的方法是先计算两条曲线对应bin的几何平均值，然后求和（见参考文献的公式(3)），用matlab语言表达是这样：Z(h) = 2*sum(sqrt(wp.*wn))，wp和wn是表示两类直方图的数组。 可以看出这个值越小说明两类的差别越大。当曲线wp和wn完全重合的时候，z值最大，表示这个特征完全不具有分类能力；当两条曲线完全不重叠时，z值最小，表示这个特征的分类能力最强，用一个阈值就能把两堆白菜分开来。我们要从有许多特征里选出那些‘好’的特征，就是选取使z达到最小的那个。

 

我们现有的3个特征的z分别是1.6586,1.7384,1.7627，也就是说第1个特征最好。那么次好的特征是哪个？是第2个z=1.7384吗？答案是否定的，因为第2个特征和第1个特征太象了，因为特征采样的空间位置决定了他俩拥有很相似的概率分布，它和第1个特征都是高度相关的。接下来介绍的AdaBoost方法，就是要去掉这种相关性的影响，从而选出真正的第二个‘好特征’。具体方法是通过改变样本的权重：减小可靠的样本的权重，增大难以区分的样本的权重，利用权重改变后的样本集合进行下一轮的特征选择。

 

根据上一篇博客，Naive贝叶斯分类器的对数表达形式为：

ln(f(f1,...fn))  =   [ln(p( f1 | w+ )) - ln(p( f1 | w- )) ]  +  ....+  [ln(p( fn | w+ )) - ln(p( fn | w- )) ] ;

其中hp =[ln(p( f1 | w+ )) - ln(p( f1 | w- ))] 可以看成是特征f1的置信度曲线，它是曲线wp和wn的相同x坐标处的p值的比值的对数。也就是说，当我们计算得到一个样本的特征值，在这个曲线上查表，如果ln(p( f1 | w+ ))>ln(p( f1 | w- ))，表示样本更象人脸，置信度结果为正数；当ln(p( f1 | w+ ))<ln(p( f1 | w- ))，样本更象非人脸，置信度结果为负数；当ln(p( f1 | w+ ))=ln(p( f1 | w- ))置信度为0。

 

当我们选出一个特征后，可以根据每个样本的置信度hp决定如何改变它的权重，对于正样本假设它的权重为Dp ，权重改变方法为：Dp = Dp.*exp(-1*hp); 对于负样本，为Dn = Dn.*exp(1*hn)。

 

在我们的例子中，现在第一轮特征选择已经选出第1号特征z(1)=1.6586为最好特征，按照 [ln(p( f1 | w+ )) - ln(p( f1 | w- )) ] 得到每个样本的置信度值，改变样本权重后，上面3个特征的概率分布（直方图）变成下面的曲线了：

 

可以看出，特征1的两类样本曲线完全重合在一起，特征2则几乎重合在一起了，而特征3几乎没有任何变化。也就是说，特征1完全变成一个没用的特征了，而 权重的变化对特征3影响不大。这个第二轮特征选择过程，曲线间“距离”度量z重新计算后分别为 1.6586,1.6454, 1.4163，可见第二轮计算3号特征是最好的。第1个特征完全废掉了，第2个特征也几乎废了，就因为它和第1个特征太象了（高度冗余的）。

 

这种利用现有分类器（这里是指特征的置信度曲线）改变样本权重，再进行下一轮特征选取的训练方法，统称为AdaBoost(Adaptive Boosting)。这里的根据样本置信度改变权重的方式称为RealAdaboost。每个特征的置信度hp其实都可以看成一个分类器（比如hp大于一个阈值，则为人脸），只是这样的分类器的分类能力很低，称为弱分类器。训练过程，就是从feature pool中选取好的特征（弱分类器），组成最终的强分类器。

 

四.串联若干强分类器组成最终的分类器
上一篇博客提到，一个强分类器的最终形式是把若干特征的置信度相加：
 if ( SUM ( H(fj) ) >Th ) , j = 1, .. .., n， n个特征
    输出 face;          
else
     输出 nonface;

 

对于人脸检测系统特征个数可能达上千个，在进行实际的人脸检测的时候，一个照片要送到分类器中进行确认的图像块个数往往数以百万记，而其中真正包含人脸的往往很少，只有几十或几百个，也就是说，非人脸的先验概率远远大于人脸。这样就希望有一种机制，可以通过计算少量特征就快速地拒绝掉那些肯定不是人脸的样本。在训练的时候，我们发现仅仅使用最好的2个特征组合的强分类器，可以在保证几乎100%检测率的情况下，拒绝掉几乎50%的负样本。这样，最终的人脸检测系统，是由若干强分类器串联而成的，象一个向一边生长的二叉树，每个强分类器只负责把样本分成“非人脸”和“有可能是人脸”两类，对于后一类样本再送入到下一个强分类器。就象很多叠在一起的筛子一样，只有通过最下面一个筛子的样本才被判断为人脸。而论文中，这种机制称为cascade。

 

假设每个强分类器的检测率为99%，错检率为50%（拒绝掉50%的非人脸），假设我们有10级强分类器串联，最终的分类器的检测率为0.99^10=0.9044，错检率为0.50^10=9.7656e-004。实际训练的初始化阶段，每层强分类器要给定的参数是1检测率，2错检率或3样本个数中的某两个。

 

两类训练样本假设为5000和1万，每层检测率为99%，错检率为50%，程序自动选取了若干特征组成两层结构的分类器。由于每层都拒绝掉50%的负样本，第3层训练开始的时候，正样本还有4900，负样本只剩下2500，太少了。这时，要做一件事，就是利用现有的分类器做为人脸检测器，在不包含人脸的图像样本中搜集负样本（其实就是这个半成品人脸检测器的错检结果），作为下一层训练的负样本。这个重新采样搜集负样本的过程称为Bootstrapping，在数据挖掘和模式识别领域是常用的一个操作步骤。试验中看到的有趣的现象是，越是处在后面的强分类器的负样本越是看起来象人脸，也需要更多的弱特征组合才能得到一个不错的强分类器。

 

参考文章：

[1] Bo WU, Haizhou AI, Chang HUANG, Shihong LAO, Fast Rotation Invariant Multi-View Face Detection Based on Real Adaboost, In Proc. the 6th IEEE Conf. on Automatic Face and Gesture Recognition (FG 2004), Seoul, Korea, May 17-19, 2004. http://media.cs.tsinghua.edu.cn/~imagevision/publications.htm