adaboost完整版解析

基于类haar特征的Adaboost算法主要内容:训练系统分为“训练部分”和“补充部分”，1-4为训练部分，5为补充部分。1、以样本集为输入，在给定的矩形特征原型下，计算并获得矩形特征集;2、以特征集为输入，根据给定的弱学习算法，确定阈值，将特征与弱分类器一一对应，获得弱分类器集;3、以弱分类器集为输入，在训练检出率和误判率限制下，使用AdaBoost算法挑选最优的弱分类器构成强分类器;4、以强分类器集为输入，将其组合为级联分类器;5、以非人脸图片集为输入，组合强分类器为临时的级联分类器，筛选并补充非人脸样本。1如何选取特征？---类haar特征1.1矩形特征•Viola和Jone将Adaboost应用于人脸检测，在保证检测率的同时，首次使得人脸检测达到了实时的速度。•为了保证Adaboost分类器的分类能力，其选择的弱分类器一般都应该尽可能的简单，通常都是一条简单的规则，对物体的某个特征进行简单判断。•在基于Adaboost的人脸检测系统中，每个弱分类器都是对图像一个特征值的判断，常用的特征是一种基于积分图计算的Haar-like特征。矩形特征•在Viola的方法中，使用矩形特征作为分类的依据，称为Haar特征，因为它是用一种类似Haar小波的方法来形成人脸特征的。典型的矩阵特征由2到4个矩形组成，分别对应于边界、细线/棒或者对角线特征，见下图。对应的矩形特征的特征值定义为白色矩形内的像素和减去黑色矩形内的像素和。•后来，Lienhart等人提出扩展的Haar-like特征下图所示，每个特征由2~3个矩形组成，分别检测边界、细线、中心特征等。•在确定了特征形式后，Harr-like特征的数量就取决于训练样本图像矩阵的大小。当人脸样本图像和非人脸样本图像的矩阵大小为24×24时(一般人脸检测的训练样本为24×24大小)，原始Harr-like特征库的四种特征的总数量就为162336个，见下表。•Adaboost算法通过从大量的haar特征中挑选出最优的特征，并将其转换成对应的弱分类器进行分类使用，从而达到对目标进行分类的目的。11y11x),(),(]1[*]1[tnsmnmtstynsxmm,n表示样本图像的宽和高比例，s,t表示haar矩形特征宽和高。公式表示样本图像逐渐缩小，得到的某一haar特征的总数假设训练或检测窗口大小为W*H个像素，w,h分别为特征原型的长、宽，所示四种特征原型对应的w/h分别为:2/1,1/2,3/1,2/2。1.2矩形特征的快速算法----积分图•利用矩形特征来计算选取人脸的特征有一种非常快速的算法，这种算法使用了一种间接的图像表示方法，称之为积分图（如图6（a））。在一张积分图上，点i(x,y)的积分值ii(x,y)是原图像上该点的上方和左方所有点的亮度值的和。即：其中ii(x,y)为积分图，i(x,y)为原始图像，如下图所示。x,y表示图像的像素坐标。上式表示对（x,y）左上角像素求和。'''',(,)(,)xxyyiixyixy•有了积分图，矩形特征值就可以通过很少的计算量得到。任意一个矩形内的像素和可以由积分图上对应的四点得到。如图6（b）:矩形框A、B、C、D内的像素和分别为A、B、C、D，即1处的积分值为A，2点处的积分值为A+B，3点处的积分值为A+C，4点处的积分值为A+B+C+D，如果求D区域内的像素值的和，则D＝4+1-(2+3)，其实就是利用了D的四个顶点处的积分值就可以求得D。由此可见，矩形特征的特征值的计算，只于此特征的端点的积分图有关，而与图像的坐标值无关。所以积分图的引入，大大提高了检测速度。这也就是Viola方法速度非常快的根本原因。2、弱分类器及其选取•一个弱分类器h(x,f,p,q)由一个特征f，阈值q和指示不等号方向的p组成：•训练一个弱分类器（特征f）就是在当前权重分布的情况下，确定f的最优阈值，使得这个弱分类器（特征f）对所有训练样本的分类误差最低。1()(,,,)0pfxphxfp其他•选取一个最佳弱分类器就是选择那个对所有训练样本的分类误差在所有弱分类器中最低的那个弱分类器（特征）。•对于每个特征f，计算所有训练样本的特征值，并将其排序。通过扫描一遍排好序的特征值，可以为这个特征确定一个最优的阈值，从而训练成一个弱分类器。具体来说，对排好序的表中的每个元素，计算下面四个值：1)全部人脸样本的权重的和；2)全部非人脸样本的权重的和；3)在此元素之前的人脸样本的权重的和；4)在此元素之前的非人脸样本的权重的和；TTSS•这样，当选取当前元素的特征值和它前面的一个特征值之间的数作为阈值时，所得到的弱分类器就在当前元素处把样本分开——也就是说这个阈值对应的弱分类器将当前元素前的所有元素分类为人脸（或非人脸），而把当前元素后（含）的所有元素分类为非人脸（或人脸）。•可以认为这个阈值所带来的分类误差为:于是，通过把这个排序的表扫描从头到尾扫描一遍就可以为弱分类器选择使分类误差最小的阈值（最优阈值），也就是为这个特征选取了一个最佳弱分类器。对于所有特征，应用以上寻找阈值的方法，就得到了所有特征对应的弱分类器，组成一个弱分类器集，作为训练的输入。jF1jFmin((),())STSSTS3、Adaboost算法基本原理•强分类器：如果一个学习算法通过一组样本的学习后，能够达到理想的识别率，则称它为强分类器。•弱分类器：如果一个学习算法的识别率仅好于随机的猜测，则称其为弱分类器。通常，针对一个具体的识别问题，我们很难找到一个理想的强分类器，但是弱分类器一般都会很多，基于这种现象，Freund和Schapire提出了Adaboosting算法：通过一定的算法可以将一组弱分类器提升为一个强分类器。Adaboost算法分析对于boosting算法，存在两个问题：1.如何调整训练集，使得在训练集上训练的弱分类器得以进行；2.如何将训练得到的各个弱分类器联合起来形成强分类器。针对以上两个问题，AdaBoost算法进行了调整：1.使用加权后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在比较难分的训练数据样本上；2.将弱分类器联合起来，使用加权的投票机制代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。3.1Adaboost算法的具体描述如下：输入：一组训练集：，其中为样本描述，为样本标识，；其中0，1分别表示正例子和反例。在人脸检测中，可以定义0为非人脸，1为人脸。初始化：初始样本权值设为(可能会导致证样本比例很小，所以常用正m个，负n个，则正的权重为1/2m,负的权重1/2n,使得正负比例分别为1/2)。对，(T为循环数，即找到T个弱分类器)循环执行下面的步骤：1.归一化权重：11(,),...,(,)nnxyxyixiy(0,1)iy1,1jwn1,2,...,tT,,,1titintjjwqw2.对每个特征f，训练一个弱分类器；计算所有特征的弱分类器的加权错误率3.（在所有特征中）选取具有最小错误率的最佳弱分类器。4.按照这个最佳弱分类器，调整权重：，其中表示被正确分类，表示被错误分类。(,)hxf|(,)|fiiiqhxfy()thxmin|(,)||(,)|ffiiitiiiqhxfyqhxfy()(,)tthxhxf11,,ietititww0ieix1ieix1ttt5.最后的强分类器为：其中。注：（另一种方法：不用循环，而是用识别率与误识别率是否达到来进行循环）在每一次循环完之后，运用5判断已经得到的弱分类器的加权后判断的识别率与误识别率是否在预定范围内，若在：停止循环，直接；不在：继续。1111()()20TTttttthxCx其他1logtt强分类器的构成•经过T次迭代后，获得了T个最佳弱分类器，可以按照下面的方式组合成一个强分类器：•其中。•那么，这个强分类器对待一幅待检测图像时，相当于让所有弱分类器投票，再对投票结果按照弱分类器的错误率加权求和，将投票加权求和的结果与平均投票结果比较得出最终的结果。12(),...,()hxhx1111()()20TTttttthxCx其他1logtt算法流程图：算法流程图：adaboost它把一些比较弱的分类方法合在一起，组合出新的很强的分类方法。例如在下图中需要一些线段把红色的球和深蓝色的球分开，然如仅果仅用一条线的话，是分不开的。例子：使用Adaboost算法来进行划分的话，先画出一条错误率最小的线段如图a，但左下角的深蓝色的球被错划分到红色区域，因此加重被错误划分的球的权重，再下一次划分的时候，将更加考虑那些权重大的球，如图c，最终得到一个准确的划分，如下图所示。4、级联分类器•利用训练过程得到的弱分类器，使用上式将部分弱分类器组合得到若干强分类器，各强分类器对目标都有较强的检测能力。如果将多个强分类器级联在一起，那么能够通过各级强分类器检测的对象是人脸的可能性也最大。根据这一原理，Adaboost算法引入了一种瀑布型的分类器---级联分类器。级联分类器的检测示意图如下图：（分类器误识别率不断降低。确定不是证样本的排除，不确定的到下一个分类器中）•级联分类器将若干个强分类器分级串联在一起，强分类器一级比一级复杂，一级比一级严格。检测中非目标图像会在前端被排除掉，只有目标图像才能通过各级强分类器的检测。此外，由于非目标图像会被级联分类器的前几级迅速排除掉，从而加快了Adaboost算法的检测速度。5、补充负样本•一级训练结束后，应用级联分类器于负样本，将分类错误的负样本留下，再补充新的负样本，作为下一级训练的负样本。三个问题详解：1、强分类器为什么是级联的？3、强分类器的公式,权重的选取？1、强分类器为什么是级联的？每一级训练都会产生一个强分类器，同时产生一组特征，而且，随着训练级数的增加，特征数也会随着增加。例如第一级训练结束后，会产生15个特征，第六级就会产生50个特征。如果只用第六级的分类器进行特征识别，由于特征数较多，运行起来会很慢。这时，将各级的分类器级联起来，容易判断的特征会再第一级分类器中被判断出来，将其踢出样本集，这样留下的样本数会越来越少，速度就会愈来愈快。3、强分类器的公式,权重的选取一共m个样本，Y={-1，+1}，-1代表负样本错误率：|(,)|fiiiqhxfy假设的权重：ttt1ln21从1到M循环,样本权重：iitiittttyxheyxheZiDiDtt)(if)(if)()(1最后强分类器：TtttxhxH1)(sign)(下面解释为什么要首先证明adaboost最终强分类器的的错误率上限是：iitiittttyxheyxheZiDiDtt)(if)(if)()(1由于：通过迭代公式，一直迭代到D1=1/m。公式变为：txtxttyheyheZmitttt1)(D1t将上述公式整合成一个公式，如下：（h与y相等，乘积为1，不等，乘积为-1）为了使得adaboost算法精确，就要使错误率最小，就是使最小，而()exp(())tttitiiZDiyhx是的函数，又因为h的值域是{-1,1}，所以只要另一个参数最小。（在原始的AdaBoost算法中采用贪婪算法，每次的都是最小的保证收敛到满意的结果。）tth、求偏导数，令其为0。其中A是h=y的集合，就有以下式子：0)()(tithyittthyxDZtti