AdaBoost算法及应用

ADABOOST&ITSAPPLICATIONSOUTLINEOverviewTheAdaBoostAlgorithmHowandwhyAdaBoostworks?AdaBoostforFaceDetectionADABOOST&ITSAPPLICATIONSOverviewINTRODUCTIONAdaBoostAdaptiveAlearningalgorithmBuildingastrongclassifieralotofweakeronesBoostingADABOOSTCONCEPT1{1}),1(hx...weakclassifiersslightlybetterthanrandom1()()TttTthxHxsign2{1}),1(hx{1(}),1ThxstrongclassifierWEAKERCLASSIFIERS1{1}),1(hx...weakclassifiersslightlybetterthanrandom1()()TttTthxHxsign2{1}),1(hx{1(}),1Thxstrongclassifier训练一个弱分类器（特征f）就是在当前权重分布的情况下，确定f的最优阈值以及不等号的方向，使得这个弱分类器（特征f）对所有训练样本的分类误差最低。1()(,,,)0pfxphxfp其他THESTRONGCLASSIFIERS1{1}),1(hx...weakclassifiersslightlybetterthanrandom1()()TttTthxHxsign2{1}),1(hx{1(}),1ThxstrongclassifierADABOOST&ITSAPPLICATIONSTheAdaBoostAlgorithmTHEADABOOSTALGORITHMGiven:11where(,),,(,),{1,1}mmiixyxyxXyInitialization:11(),1,,mDiimFor:1,,tT•FindclassifierwhichminimizeserrorwrtDt,i.e.,:{1,1}thX1whereargmin()[()]jmtjjtijiihhDiyhx:probabilitydistributionof'sattime()tiDixt•Weightclassifier:11ln2ttt•Updatedistribution:1()exp[()],isfornormalizati()onttititttDiyhxDiZZminimizeweightederrorforminimizeexponentiallossGiveerrorclassifiedpatternsmorechanceforlearning.THEADABOOSTALGORITHMGiven:11where(,),,(,),{1,1}mmiixyxyxXyInitialization:11(),1,,mDiimFor:1,,tT•FindclassifierwhichminimizeserrorwrtDt,i.e.,:{1,1}thX1whereargmin()[()]jmtjjtijiihhDiyhx•Weightclassifier:11ln2ttt•Updatedistribution:1()exp[()],isfornormalizati()onttititttDiyhxDiZZOutputfinalclassifier:1()()TtttsignHxhxBOOSTINGILLUSTRATIONWeakClassifier1BOOSTINGILLUSTRATIONWeightsIncreasedBOOSTINGILLUSTRATIONWeakClassifier2BOOSTINGILLUSTRATIONWeightsIncreasedBOOSTINGILLUSTRATIONWeakClassifier3BOOSTINGILLUSTRATIONFinalclassifierisacombinationofweakclassifiersADABOOST&ITSAPPLICATIONSAdaBoostforFaceDetectionTHETASKOFFACEDETECTIONManyslidesadaptedfromP.ViolaTHEVIOLA/JONESFACEDETECTOR2001年，Viola和Jones利用类Haar特征构造弱分类器，使用AdaBoost算法把弱分类器组合成强分类器，采用Cascade结构把强分类器串联组合成级联分类器，实现了准实时的人脸检测。P.ViolaandM.Jones.Rapidobjectdetectionusingaboostedcascadeofsimplefeatures.CVPR2001.P.ViolaandM.Jones.Robustreal-timefacedetection.IJCV57(2),2004.HARR-LIKEFEATURESFeatureValue(Pixelinwhitearea)(Pixelinblackarea)Rectanglefilters将任意一个矩形放到人脸区域上，然后将白色区域的像素和减去黑色区域的像素和，得到的值我们暂且称之为人脸特征值。IMAGEFEATURESFeatureValue(Pixelinwhitearea)(Pixelinblackarea)RectanglefiltersTHEVIOLA/JONESFACEDETECTORAsimpleexample2×2imageHaarfeaturetemplateADABOOST在人脸检测中的应用…计算特征值发挥出每个Haar特征的最好效果特征值排序穷举找到最佳阈值1类-1类or-1类1类考虑方向-1类1类+1-1标记1-111分布0.150.350.250.25结果-1-111错误率0.15标记11-11分布0.150.250.350.25结果11-1-1错误率0.25标记-1111分布0.350.150.250.25结果-1111错误率0特征1特征3特征2最终选定特征3及其阈值构成弱分类器排序排序排序“好中取最好”THEADABOOSTALGORITHMGiven:11where(,),,(,),{1,1}mmiixyxyxXyInitialization:11(),1,,mDiimFor:1,,tT•FindclassifierwhichminimizeserrorwrtDt,i.e.,:{1,1}thX1whereargmin()[()]jmtjjtijiihhDiyhx•Weightclassifier:11ln2ttt•Updatedistribution:1()exp[()],isfornormalizati()onttititttDiyhxDiZZOutputfinalclassifier:1()()TtttsignHxhxATTENTIONALCASCADE单独一个AdaBoost分类器即使很强，在误检率和检测时间上根本满足不了真正的实时人脸检测系统的需要。采用级联检测策略能很好地解决这个问题。Adaboost算法引入了一种瀑布型的分类器---级联分类器。在级联分类器中，每一个待检测窗口只有通过了当前层的强分类器（AdaBoost分类器）才能进入下一层。这样大量的待检测窗口只需要最初几层简单的判断就可以被迅速淘汰，使得平均检测成本大大降低。多层级联结构中，每一层的强分类器都是由AdaBoost算法训练来的。Classifier3Classifier2Classifier1IMAGESUB-WINDOWTTFACETNON-FACEFFNON-FACEFNON-FACEATTENTIONALCASCADEChainclassifiersthatareprogressivelymorecomplexandhavelowerfalsepositiveratesClassifier3Classifier2Classifier1IMAGESUB-WINDOWTTFACETNON-FACEFFNON-FACEFNON-FACE0100050%FalsePos%DetectionROCCurveDETECTIONRATEANDFALSEPOSITIVERATEFORCHAINEDCLASSIFIERSThedetectionrateandthefalsepositiverateofthecascadearefoundbymultiplyingtherespectiveratesoftheindividualstagesAdetectionrateof0.9andafalsepositiverateontheorderof106canbeachievedbya10-stagecascadeifeachstagehasadetectionrateof0.99(0.9910≈0.9)andafalsepositiverateofabout0.30(0.310≈6106)Classifier3Classifier2Classifier1IMAGESUB-WINDOWTTFACETNON-FACEFFNON-FACEFNON-FACE11,fd22,fd33,fd11,KiKiiiFfDd,FDSTRUCTUREOFTHEDETECTORCASCADENoden就是当前面n-1节点都不能正确分类样本时，用它来正确分类这些“顽固”分子，如果Noden也不能完全解决这个问题，再把问题甩给Noden+1。这就要求越“后面”的节点越复杂，越“聪明”—T越大.RejectSub-Window12345678NFaceFFFFFFFFFTTTTTTTTTAllSub-WindowsSTRUCTUREOFTHEDETECTORCASCADERejectSub-Window1234567838FaceFFFFFFFFFTTTTTTTTTAllSub-Windows2features,reject50%non-faces,detect100%faces10features,reject80%non-faces,detect100%faces25features50featuresbyalgorithmOUTPUTOFFACEDETECTORONTESTIMAGESOTHERDETECTIONTASKSFacialFeatureLocalizationMalevs.femaleProfileDetectionOTHERDETECTIONTASKSFacialFeatureLocalizationProfileDetectionOTHERDETECTIONTASKSMalevs.FemaleCONCLUSIONSThankyou