AdaBoost算法及应用课件

1OverviewThe AdaBoost AlgorithmHow and why AdaBoost works?AdaBoost for Face Detection2Overview3AdaBoostAdaptiveA learning algorithmBuilding a strong classifier a lot of weaker onesBoosting4.weak classifiersslightly better than randomstrong classifier5.weak classifiersslightly better than randomstrong classifier 训练一个弱分类器（特征f）就是在当前权重分布的情况下，确定f 的最优阈值以及不等号的方向，使得这个弱分类器（特征f）对所有训练样本的分类误差最低。6.weak classifiersslightly better than randomstrong classifierHow good the strong one will be?7The AdaBoost Algorithm8Given:Initialization:For :Find classifier which minimizes error wrt Dt,i.e.,Weight classifier:Update distribution:9Given:Initialization:For :Find classifier which minimizes error wrt Dt,i.e.,Weight classifier:Update distribution:Output final classifier:10Weak Classifier 111WeightsIncreased12Weak Classifier 213WeightsIncreased14Weak Classifier 315Final classifier is a combination of weak classifiers16AdaBoost forFace Detection17Many slides adapted from P.Viola182001年，Viola和Jones利用类Haar特征构造弱分类器，使用AdaBoost算法把弱分类器组合成强分类器，采用Cascade结构把强分类器串联组合成级联分类器，实现了准实时的人脸检测。P.Viola and M.Jones.Rapid object detection using a boosted cascade of simple features.CVPR 2001.P.Viola and M.Jones.Robust real-time face detection.IJCV 57(2),2004.19Rectangle filters将任意一个矩形放到人脸区域上，然后将白色区域的像素和减去黑色区域的像素和，得到的值我们暂且称之为人脸特征值。20Rectangle filters21A simple example 22 imageHaar feature template22计算特征值计算特征值发挥出每个发挥出每个Haar特征的最好效果特征的最好效果特征值排序特征值排序穷举找到最佳阈值1类-1类or-1类1类考虑方向考虑方向-1类1类+1-123标记 1 -1 1 1 分布 0.15 0.35 0.25 0.25 结果 -1 -1 1 1 错误率 0.15标记 1 1 -1 1 分布 0.15 0.25 0.35 0.25 结果 1 1 -1 -1 错误率 0.25标记 -1 1 1 1 分布 0.35 0.15 0.25 0.25 结果 -1 1 1 1 错误率 0特征特征1特征特征3特征特征2最终选定特征最终选定特征3及其阈值构及其阈值构成弱分类器成弱分类器排序排序排序“好中取最好好中取最好”24Given:Initialization:For :Find classifier which minimizes error wrt Dt,i.e.,Weight classifier:Update distribution:Output final classifier:25单独一个AdaBoost分类器即使很强，在误检率和检测时间上根本满足不了真正的实时人脸检测系统的需要。采用级联检测策略能很好地解决这个问题。Adaboost算法引入了一种瀑布型的分类器-级联分类器。在级联分类器中，每一个待检测窗口只有通过了当前层的强分类器（AdaBoost分类器）才能进入下一层。这样大量的待检测窗口只需要最初几层简单的判断就可以被迅速淘汰，使得平均检测成本大大降低。多层级联结构中，每一层的强分类器都是由AdaBoost算法训练来的。Classifier 3Classifier 2Classifier 1IMAGESUB-WINDOWTTFACETNON-FACEFFNON-FACEFNON-FACE26Chain classifiers that are progressively more complex and have lower false positive ratesClassifier 3Classifier 2Classifier 1IMAGESUB-WINDOWTTFACETNON-FACEFFNON-FACEFNON-FACE0100050%False Pos%DetectionROC Curve27The detection rate and the false positive rate of the cascade are found by multiplying the respective rates of the individual stagesA detection rate of 0.9 and a false positive rate on the order of 10 6 can be achieved by a 10-stage cascade if each stage has a detection rate of 0.99(0.9910 0.9)and a false positive rate of about 0.30(0.310 6106)Classifier 3Classifier 2Classifier 1IMAGESUB-WINDOWTTFACETNON-FACEFFNON-FACEFNON-FACE28Node n就是当前面n-1节点都不能正确分类样本时，用它来正确分类这些“顽固”分子，如果Node n也不能完全解决这个问题，再把问题甩给Node n+1。这就要求越“后面”的节点越复杂，越“聪明”T越大.Reject Sub-Window12345678NFaceFFFFFFFFFTTTTTTTTTAll Sub-Windows29Reject Sub-Window1234567838FaceFFFFFFFFFTTTTTTTTTAll Sub-Windows2 features,reject 50%non-faces,detect 100%faces 10 features,reject 80%non-faces,detect 100%faces 25 features50 featuresby algorithm3031Facial Feature LocalizationMale vs.femalePro 32Facial Feature LocalizationPro 33Male vs.Female34p经常不断地学习,你就什么都知道。你知道得越多,你就越有力量pStudyConstantly,AndYouWillKnowEverything.TheMoreYouKnow,TheMorePowerfulYouWillBe写在最后35Thank You在别人的演说中思考，在自己的故事里成长Thinking In Other PeopleS Speeches，Growing Up In Your Own Story讲师：XXXXXX XX年XX月XX日36