一种改进的AdaBoost算法_ADAdaBoost_图文

1、第30卷第1期2007年1月计算机学报C HIN ESE J OU RNAL OF COM PU TERSJan.2007一种改进的Ada Boost 算法AD Ada Boost李闯丁晓青吴佑寿(清华大学电子工程系北京100084A R evised Ada Boost Algorithm AD Ada BoostL I Chuang DIN G Xiao 2Qing WU Y ou 2Shou(Depart ment of Elect ronic Engineering ,Tsinghua Universit y ,Bei j ing 100084Abstract Object detec

2、tion is one of t he mo st pop ular and important issues in t he domain of com 2p uter vision.AdaBoo st algorit hm based on cascade st ruct ure can solve t he p roblem effectively ,however it has it s own shortcoming.This paper p ropo ses a revised type of AdaBoost algorit hm ,AD AdaBoo st.AD AdaBoo

3、st adopt s a new met hod to acquire parameters.The weighted parame 2ters of weak classifiers are determined not o nly by t he error rates ,but also by t heir abilities to recognize t he positive samples.The algorit hm can decrease t he classifiers false alarm rates in t he low false rejection rate e

4、nd ,so it is more adaptive to t he object detection based on cascade struc 2t ure.The experiment result s p rove t he imp rovement achieved by t he new algorit hm.K eyw ords AD AdaBoost ;object detection ;cascade structure ;weak classifier ;weighted parameter1引言目标检测问题是计算机视觉领域最普遍和关键的问题之一.在很多情况下,人们往往只

5、关心观测信号中某些特定的目标,比如雷达信号中敌方飞机的信号;观测图像中的文字或者人脸等等.因此寻找准确快速的目标检测算法一直受到研究者们的广泛关注.在目标检测问题中,代表目标信号的正样本和代表背景信号的负样本在概率分布上是极度不均衡的,两者在重要性上也存在差异,这使得目标检测问题可以被看作是一个非对称的两类分类问题.由于问题的非对称性,在设计分类器时,整体的分类错误率不再是决定性的指标,必须对正负样本的分类错误率分别加以考虑.另外,在对分类器进行学习的过程中,容易得到足够的代表检测目标的正训练样本,但却难以得到能代表各种背景信号的足够的负样本集合,负样本的匮乏增加了分类器学习和训练的困难.针对

6、目标检测问题的特点,研究者们采用了多种学习算法进行了尝试.Papageorgiou采用基于冗余小波特征的支持向量机(SVM来构建检测算法1.Schneiderman提出了一个基于多尺度小波变换的贝叶斯分类器来进行检测2.Rowley在人脸检测系统中使用的是神经网络的方法3.Viola和Jones则提出了一个基于级联结构的AdaBoost分类器4,级联结构由多级分类器组成,每一级的分类器都采用AdaBoo st算法进行训练.对比其它的算法,Viola和Jones所提出的基于级联结构的AdaBoo st算法在解决实际应用问题时更为有效.该算法在人脸检测的研究中被广泛地加以采用,取得了很好的结果.该

7、算法通过AdaBoost学习算法将多个弱分类器集成得到一个强分类器,具备很强的泛化能力,保证了算法的稳定性.同时,由于采取了级联结构,大多数的负样本都在前面比较简单的级次中被滤除,提高了检测的速度.级联结构还提供了方便的采集负训练样本的方法,将前面级次中误识的负样本作为下一个级次分类器的负训练样本.正因为基于级联结构的AdaBoo st算法的这些特点符合目标检测问题的要求,所以在实践中取得了成功.Viola等在人脸检测中采用了传统的AdaBoo st 算法,其训练过程中参数的选择准则是训练集错误率上界的最小化.但是,错误率上界的最小化并不能保证错误率的最小化.因而,AdaBoo st分类器实际

8、上并不是最小错误率的分类器.因此,仍然有可能对其进行改进,以获得更好的错误率性能.更重要的是,传统的AdaBoost算法是基于对称的两类分类问题的,正样本的错误率FR R和负样本的错误率FA R在训练过程中处于平等的地位,而在目标检测问题通常采用的级联结构中,这样的假设不再成立.对于一个具有5个级次的级联结构分类器来说,如果每一级的FR R和FA R均为10%,那么最后整体级联结构的FR R和FA R分别为41%(1-01950141和01001%(0115= 0100001.显然,FR R这么高的分类器是无法满足检测要求的.在级联结构中,要达到整体分类器对FR R的要求,每一级的分类器必须具

9、有很低的FR R,而FA R的目标则通过增加级数来实现.为了在保证FR R的前提下使用较少的级数获得理想的FA R,就要使得每级的分类器在低FR R的条件下,FA R 尽可能地小,而不再是像传统的AdaBoost算法那样追求错误率上界的最小化.优化目标的变化使得传统AdaBoo st的参数选择方案不再那么有效.为此,本文在AdaBoost的基础上提出了一种新的算法AD(Adaptive to DetectionAdaBoo st.这种算法比传统的AdaBoo st算法更适合于目标检测问题中所使用的级联结构.AD AdaBoo st采用了新的弱分类器加权参数的求解算法,使得分类器在给定的低FR

10、R前提下对应的FA R有明显降低,从而改进目标检测算法的性能.本文首先在第2节中对传统的基于级联结构的AdaBoost分类器进行简单的介绍;然后,在第3节介绍新的算法AD AdaBoo st,并且对它所取得的性能改善加以分析;最后是算法的实验结果和结论.2基于级联结构的Ada Boost分类器Viola提出的级联结构的分类器是指一组串行的分类器.在对待识样本进行分类时,只有被前面一级的分类器判决为正的样本才被送入后面的分类器继续处理,反之则被认为是负样本直接输出.最后,只有那些被每一级的分类器都判决为正的样本才作为正样本输出.级联结构的示意图如图1所示 .图1级联结构的示意图在级联结构中,前面

11、几级的分类器相对来说结构比较简单,使用的特征数也较少,但具有很高的检测率,同时能够尽可能地滤除那些与目标差异较大的负样本.后面级次的分类器则使用更多的特征和更复杂的结构,从而可以区分那些与目标相似的负样本.在实际的目标检测问题中,由于待检测的正样本通常在整体样本中只占很小的比例,大部分的样本在级联结构前端的分类器就会被滤除,只有少量的样本需要通过所有级的分类器,因而级联结构大大地降低了运算复杂度.在级联结构的分类器中,Viola和Jones采用AdaBoost算法来对每一级的分类器进行训练.Ada2401计算机学报2007年Boo st算法的基本思想是将多个弱分类器集成成为一个强分类器.在训练

12、过程中,每个训练样本被赋予一个初始权值,当一个弱分类器训练完成后,根据其在训练集上的分类结果对所有的样本权值进行调整,使得下一次训练的弱分类器更关注那些被识别错误的样本.最后的强分类器的判决结果是所有弱分类器的判决结果的加权和.Viola4和Tu5分别在人脸检测和文字检测中采用基于级联结构的AdaBoost分类器,取得了较好的结果,证明了基于级联结构的AdaBoo st分类器在解决目标检测问题时是有效的.但是该算法仍然具有改进的空间,后来的研究者也在其基础上提出了很多新的修正.当采用级联结构的AdaBoo st分类器解决目标检测问题时,要满足最后整个系统对FR R的要求,每级的分类器都要具有很

13、低的FR R.一般来说,在前面几级的分类器中,要达到接近于0的FR R(即接近100%的检测率,在后面级次的分类器中,由于正负样本较难区分,所以对FR R的要求相应地下降.此时,级联结构中每级分类器判决阈值的选取不再是像传统的两类分类问题那样选取对应最小错误率处的阈值,而是要调整到与符合要求的FR R 相对应.在这种情况下,基于最小错误率上界的传统AdaBoo st算法以及求解的加权参数,在低FR R端并不一定能够获得好的性能.为了解决这个问题,研究者们提出了一些改进的算法.AdaCo st6和Cost2Sensitive AdaBoost7采取类似的思路对样本权值的更新过程进行改进.在分类器

14、进行训练时,每次权值更新的过程中都偏重于提高正样本的权值,这样使得每个弱分类器对正样本更加重视,从而改善低FR R端的性能.但是,这类算法的参数训练过程仍然是基于最小错误率上界的,所以得到的改进相对有限.3一种新的Ada Boost算法AD Ada Boost本文提出了一种新的AdaBoost算法AD AdaBoo st,它在判决阈值调整到对应低FR R一端时能够获得比传统AdaBoo st算法更好的性能,因而更加适用于目标检测问题中通常采用的级联结构分类器.下文首先对算法的流程进行介绍,然后对它取得的改进进行分析.311AD Ada Boost算法流程新算法的流程为:1.给定标定的训练样本集

15、:(x1,y1,(x2,y2, (x m,y m,其中,x iX,y iY=-1,+1.2.对样本权值进行初始化:D1(i=1/m;3.循环t=1,2,T:t=h t(x iy iD t(i以及识别正确的正样本的权值和p t=y i=1,h t(x i=1D t(i.t=12ln1-tt+ke p t,k为一个常数,其取值满足在本次循环中,令最小错误率的上界下降.D t+1(i=D t(iZ te-t,h t(x i=y iet,h t(x iy i=D t(ie(-t y i h t(x iZ t,其中,Z t是归一化因子,即Z t=iD t(ie(-t y i h t(x i.4.最后的强

16、分类器为H(x=signTt=1t h t(x-T h,其中,T h是满足FR R要求的判决阈值.新的算法采用了与传统AdaBoost算法不同的加权参数的求解公式:t=12ln1-tt+ke p t(1其中,k为常数,p t=y i=1,h t(x i=1D t(i.显然,p t是第t次循环的弱分类器中所有被识别正确的正样本的权值和,它能够代表弱分类器h t 对正样本的识别能力.而ke p t是p t的增函数,这样求得的新的加权参数,在错误率t相同的情况下,那些对正样本识别能力更强的弱分类器具有更大的权值.下文的理论分析和实验结果可以证明,采用上述参数求解方法的AD AdaBoost,应用到目

17、标检测问题中能够得到性能上的改进.5011期李闯等:一种改进的AdaBoost算法AD AdaBoost312对AD Ada Boost 的分析AdaCo st 6,Asymmet ric AdaBoo st 8等算法通过改变样本权值的更新过程来使训练算法更适应目标检测问题的要求,而本文提出的新算法则通过改变弱分类器加权参数的求解方式来实现这一点.本节对AD AdaBoo st 在性能上得到改进的原因加以分析.前文已经指出,在目标检测所采用的级联结构中,为了满足FR R 的要求,要对判决阈值进行调整.如图2所示,阈值不再是对应最小错误率处的A 点,而是要调整到B 点,即min H (x i (

18、y i 满足y i =1附近.分布在B 点附近的正样本,其H (x i 值较小的原因是早期选取的加权参数较大的弱分类器对它们的识别能力比较差,虽然它们的样本权值因此得到提升,后面的弱分类器对它们的识别能力比较强,但是由于后面的弱分类器对应的加权参数通常都很小,所以最后的加权和H (x i 比较小 .图2阈值调整的示意图而采用了AD AdaBoo st 后,从式(1可以看出,弱分类器的加权参数不但与错误率有关,还与其对正样本的识别能力有关.在实际训练过程中,虽然后面循环中的弱分类器通常错误率都很高,接近50%,但是其中有的弱分类器仍然具有很强的对正样本的识别能力.这样,这些弱分类器的权值就比传统

19、AdaBoost 算法中的权值有很大的提高.此时再考察H (x i 值较小的那些正样本,上文已经提到,循环早期权值较高的弱分类器对它们的识别能力较差.而采用新的算法后,后期对正样本识别能力强的弱分类器由于权值上升比较大,并且对此类样本更容易识别正确,因而能够有效地弥补前面的弱分类器的不足,提高最后的加权和H (x i .如果与此同时,负样本的加权和H (x i 并不上升,或者上升的幅度较小,那么AD AdaBoost 就可以在相同的FR R 要求下获得更小的FA R.下文证明AD AdaBoost 确实能够通过改善样本H (x i 值的分布来改进分类器在训练集上的性能.令f (p t =k e

20、 pt .则新算法中样本x i 对应的加权和H (x i 为H (x i =tt h t(x i =t12ln 1-tt+f (p t h t (x i =t12ln 1-tth t (x i +tf (p th t(x i(2式(2最右端的前一项仍然保持了传统Ada 2Boo st 算法的形式,因而主要考察后一项.令H (x i =tf (p th t(x i,对于那些正样本:y i =1H(x i =y i =1tf (p th t(x i=ty i =1f (p th t(x i=tf (p ty i =1h t(x i(3令N p 为训练集中正样本的数量,N n 为训练集中负样本的数量

21、,C t 为第t 次循环中正样本的权值和.即C t =y i =1D t(i .那么可以得到在第t 次循环中,识别正确的正样本数量约为N pp tC t,则y i =1h t (x i =N p p tC t1+N p -N pp tC t(-1=N p 2p tC t-1(4将式(4代入式(3可以得到y i =1H(x i =tf (p ty i =1h t(x i=2N ptf (p t p tC t-015(5对于那些负样本,同公式(3类似,可以求得y i =-1H(x i =tf (p ty i =-1h t(x i(6已知第t 个弱分类器的错误率为t =h t (x i y iDt(

22、i ,即第t 个弱分类器识别错误的样本总数约为(N p +N n t ,其中识别错误的正样本数前文已经给出,为N p -N pp tC t,则识别错误的负样本数为601计算机学报2007年(N p +N n t -N p -N p p tC t,因此,识别正确的负样本数为 N n -(N p +N n t -N p -N pp tC t.则y i =-1h t (x i =N n -(N p +N n t -N p - N p p tC t (-1+(N p +N n t -N p -N pp t C t1=2(N p +N n t -N p -N pp tC t-N n .在弱分类器的训练过

23、程中,能够保证每个弱分类器的错误率是小于015的,即t 015,那么根据上式可以得出y i =-1h t(x i2(N p +N n 015-N p -N p p tC t-N n =2N pp tC t-015(7综合式(5,(6和式(7,所以有y i =-1H(x i =tf (p ty i =-1h t(x i2N p tf (p t p tC t -015=y i =1H(x i (8通过上述分析以及式(8可以看出 ,AD Ada 2Boo st 对比传统的AdaBoost 算法,正样本和负样本的H (x i 分布向两侧拉伸.这样,在固定FR R 的要求下,就能够获得更低的FA R .

24、图3给出了图像中的文字检测问题中分别采用传统的AdaBoost 算法和新算法时H (x i 分布的对比.可以看到用实线表示的新算法的H (x i 分布对比传统的AdaBoost 算法(用虚线表示有明显的改善,因而在符合FR R 要求的阈值T h 处具有更低的FA R .图3新旧算法H (x i 分布的对比313常数k 值的选取本小节将对新的参数求解公式(1中常数k 值的选取加以讨论.从312节中的分析来看,较大的k 值对应的H (x i 分布的拉伸效果更明显,但是这并不说明k 值越大对性能的改进越有利.k 值过大会使得参数求解公式(1中的前一项重要性下降,从而使得分类器丧失对负样本的识别能力.

25、Freund 和Schapire 在文献9中已经证明,AdaBoost 算法最小错误率的上边界为Tt =1Z t .新的算法没有改变样本权值的更新过程,所以最小错误率的上边界仍然是T t =1Z t.那么在考虑新算法中k 的取值时,仍然要保证此时每个弱分类器对应的Z t 1,即在AD Ada 2Boo st 中,循环中每加入一个新的弱分类器还能保持最小错误率上边界Tt =1Z t 的下降.参考训练过程,能够得到Z t =(1-t e -t +t e t=(1-t e -12ln1-tt+f (p t +t e12ln1-tt+f (p t =(1-t t (e-f (p t +e f(p t1

26、,即e -f (p t +e f(p t1(1-t t(9当f (p t =k e pt 时,k 的取值要满足在所有弱分类器中不等式(9成立.一般的,在训练完成某级弱分类器h t 后,对其对应的Z t 进行验证,满足Z t 1的弱分类器才会被加入.当取k =1/120时,对应的错误率t 01494的弱分类器都可以满足Z t 1.4实验结果自然景物图像中的文字检测问题是一个典型的目标检测问题,基于该问题对本文所提出的AD AdaBoost 算法进行了实验.在检测过程中,采用1616的移动窗口在不同尺度上对图像进行扫描,以确定文字的位置.对每个扫描窗口,使用AdaBoo st 分类器来对其是否是文

27、字进行判决,分类器的训练算法分别是本文提出的新算法AD AdaBoost 和传统的AdaBoo st 算法.因为文字不像人脸那样具有相似的内部结构,所以分类所使用的特征是与人脸检测不同的直方图特征.实验分别在训练集和测试集上进行.正样本是从自然景物图像中的文字区域截取的,负样本则是7011期李闯等:一种改进的AdaBoost 算法AD AdaBoost108 计 算 机 学 报 2007 年 从非文字区域中随机获取的 . 训练集包括 10000 个 正样本和 10000 个负样本 , 测试集则包括 10000 个 正样本和 20000 个负样本 . 训练采用的特征是从 8784 维直方图特征库

28、中 选取的 . 对于级联结构的第一级 ,选用 100 维特征各 自在 AD AdaBoo st 和传统的 AdaBoo st 算法下训练 分类器 . 图 4 给出了分别采用两种算法在训练集和 测试集上对应的 ROC 曲线 ,可以看出 , 在高检测率 端 ,即 FR R 较低的一端 , 新算法的 FA R 性能得到 了改善 . 为了体现 AD AdaBoo st 在低 FR R 端 FA R 的下降 ,图中的 ROC 曲线截取的是对应高检测率 即 FR R 较小的部分 . 图 4 ROC 曲线 ,为级联结构的第一级分类器确定阈值 , 使其满足在训练集上的 FR R 为 01 1 %. 此时 ,

29、表 1 给出 了 分 类 器 在 训 练 集 和 测 试 集 上 的 FR R 和 FA R . 可以看出 , 与传统的 AdaBoo st 算法对比 ,AD AdaBoo st 在训练集上具有更低的 FA R , 其在测试 集上的 FR R 和 FA R 也有不同程度的改善 . 要 32 级才能够满足同样的要求. 基于 AD AdaBoo st 的级联结构分类器由于具有较少的级数 , 其运算速 度更快 ,泛化能力也更强 . 在对自然景物图像中的文字进行检测的应用系 统中 ,首先采用基于 AD AdaBoo st 的级联结构分类 器对扫描窗口进行判决 , 然后对判决结果进行合并 等操作以实现对

30、文字区域的检测定位 . 图 5 给出了 检测的过程和结果 . 表1 新旧算法在训练集 FRR = 01 1 %时的实验结果对比 算法 训练集 测试集 FR R ( % FA R ( % FR R ( % FA R ( % 出的 AD AdaBoo st 算法对比传统的 AdaBoo st 算法 具有更好的性能 . 当采用 AD AdaBoo st 对图像中文 字检测所使用的级联结构分类器进行训练时 ,22 级 的分类器即可满足检测问题对 FR R 和 FA R 的要 求 . 而若采用传统的 AdaBoo st 算法进行训练 ,则需 根据本文 31 2 节中对阈值调整的阐述和图 4 的 AD A

31、daBoost AdaBoost 上述的实验结果说明了 , 在低 FR R 端 , 本文提 01 10 01 10 461 51 521 38 01 82 01 90 651 20 701 45 图 5 5 结 论 基于级联结构的 AdaBoo st 分类器是解决目标 1期 李 闯等 : 一种改进的 AdaBoo st 算法 AD AdaBoo st 2 109 检测问题的有效途径之一 . 但是 , 传统的 AdaBoo st 算法是针对对称的两类分类问题的 , 其优化目标是 错误率上界的最小化 ; 而目标检测是一个非对称的 两类分类问题 ,在采用级联结构时 ,其对分类器的要 求是在低 FR

32、R 端 FA R 尽可能地小 . 因此 , 传统的 AdaBoo st 算法仍需进一步改进才能更适应目标检 测问题 . 本文提出了一种新的 AdaBoo st 算法 AD AdaBoo st . 该算法采用了更为有效的参数求解方 法 ,即弱分类器的加权参数不但与错误率有关 ,还与 其对正样本的识别能力有关 . AD AdaBoo st 能够通 过改善样本 H ( x i 值的分布有效地降低低 FR R 端 的 FA R ,使其更适用于目标检测问题的要求 . 实验结果证明了新算法对比传统算法所取得的 性能改进 . 本文采用新算法训练基于级联结构的分 类器并将其应用到自然景物图像中的文字检测 ,

33、取 得了较好的结果 . 参 考 1 ject detection applied to faces and cars/ / Proceedings of t he tion. U SA , 2000 : 7462751 Press , 2002 : 131121318 3 4 5 6 7 8 文 献 9 Papageorgiou C P , Oren M , Poggio T. A general f ramework ference on Co mp uter Vision. Bombay , India , 1998 : 5552562 for object detection/ / Pr

34、oceedings of t he 6t h International Con2 L I Chuang , born in 1975 , Ph. D. candidate. His research interest s include pattern recognition and comp uter vision. Background This wo rk is suppo rted by t he National Nat ural Science Fo undation of China under grant No1 60472002 ( research on statisti

35、cal based comp uter vision t heories , met hods and appli2 cations . This o bjective of t his wo rk is to imp rove t he well2known machine learning algo rit hm , AdaBoo st , which is widely used in comp uter visio n applicatio ns. AdaBoo st has low comp uta2 tio n complexity , simple st ruct ure as

36、well as st ro ng generali2 zatio n ability. However , t here is still a lot of works need to be done to imp rove t he AdaBoo st algo rit hm , especially in some special applicatio ns. AdaBoo st algo rit hm is pop ular in t he research of object detectio n and has got many p romising result s. But so

37、 me fea2 t ures of Na ve AdaBoo st are not adaptive to t he object detec2 tio n p ro blems. The reason is t hat Na ve AdaBoo st interest in t he minimal error rate , but not t he false alarm rate at low false rejectio n rate end , which is much more impo rtant in t he object detetion. There are very

38、 few effort s to solve t he p rob2 lem in mo st current research works. This app roach p ropo ses a revised type of AdaBoo st algo2 rit hm , AD AdaBoo st . Compared wit h t he Na ve AdaBoo st , AD AdaBoo st adopt s a different met hod to co mp ute t he weighted parameters of t he weak classifiers. T

39、hus t he algo2 rit hm can get lower false alarm rates at t he low false rejectio n rate end , so it has st ro nger classification abilities t han t he Na ve AdaBoo st facing t he o bject detection p roblems. The experiment result s of text detection in images p rove t he im2 p rovement achieved by t

40、 he given algorit hm. This algorit hm can be used in many o bject detectio n ap 2 plications , such as face detectio n , text detectio n , vehicle de2 tection , etc. It will imp rove t he performance of many co m2 p uter vision systems. DING Xiao2 Qing , born in 1939 , p rofesso r , Ph. D. su2 pervi

41、so r. Her research interests include intelligent information p rocessing of images and documents , pattern recognition , im2 age processing and optical character recognition , etc. WU You2Shou , born in 1925 , p rofessor , Ph. D. super2 visor , member of Chinese Academy of Engineering. His re2 search interest s include digital communication , digital signal p rocessing and pattern recognitio n , etc. detection. IEEE Transactions on Pattern Analysis and Ma2 chine Intelligence , 1998 , 20 (1 : 22238