当前位置: 代码迷 >> 综合 >> adaboost(转自:http://blog.scien…
  详细解决方案

adaboost(转自:http://blog.scien…

热度:1   发布时间:2024-01-06 02:54:36.0
先撇开人脸检测问题,来看看直方图。
一.用带权重的样本统计直方图
直方图Histogram,是一种常见的概率分布的非参数(区别于高斯分布,泊松分布等用参数表达概率密度的方法)表达方法。直方图可以看成概率密度分布的离散化表达方法。它的计算很简单,是一种投票的方法,就是每个样本往对应的小盒子(bin)里投一票。假设N个样本数据x量化为1~M之间的整数,那么Hist是M维数组,对应的直方图计算方法如下:

//initializing
for i=1:M
    Hist[i] = 0;
end
//voting
for  i = 1:N
    Hist[x[i]] += 1 ;
end
为了表示成概率分布,需要Hist数组和为1:
//normalize
for  j = 1:M
    Hist[j] = Hist[j]/sum(Hist) ; //sum(Hist) = Hist[1] + Hist[2] + ... + Hist[M];
end
在这里sum(Hist)等于样本个数N。以上“投票+归一化”两个步骤,其实可以和成一步,即每个样本x[i]有一个对应的权重w[i]=1/N,投票的时候往小盒子里放的是权重:
//initializing
for i=1:M
    Hist[i] = 0;
end
//voting
for  i = 1:N
    Hist[x[i]] += w[i] ;
end
这样得到数组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个最好的特征:
adaboost(转自:http://blog.sciencenet.cn/home.php?mod=space&uid=465130&do=blog&id=427078)

 
这个图表示的是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级)画出来看看(蓝色曲线表示正样本,红色表示负样本):
adaboost(转自:http://blog.sciencenet.cn/home.php?mod=space&uid=465130&do=blog&id=427078)

 
可以看出所有特征的两类分布都有很大的重叠,如前所述,‘好‘的特征是指两个曲线的'差别'比较大。表达概率分布曲线之间的“距离”的度量方法有很多,参考论文中的方法是先计算两条曲线对应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个特征的概率分布(直方图)变成下面的曲线了:
adaboost(转自:http://blog.sciencenet.cn/home.php?mod=space&uid=465130&do=blog&id=427078)

 
可以看出,特征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
  相关解决方案