Adaboost 原理与应用 迄今见过最好的 ppt课件

AdaBoost ItsApplications 主講人 虞台文 Outline OverviewTheAdaBoostAlgorithmHowandwhyAdaBoostworks AdaBoostforFaceDetection AdaBoost ItsApplications Overview Introduction AdaBoost Adaptive Alearningalgorithm Buildingastrongclassifieralotofweakerones Boosting AdaBoostConcept weakclassifiers slightlybetterthanrandom strongclassifier WeakerClassifiers weakclassifiers slightlybetterthanrandom strongclassifier EachweakclassifierlearnsbyconsideringonesimplefeatureTmostbeneficialfeaturesforclassificationshouldbeselectedHowtodefinefeatures selectbeneficialfeatures trainweakclassifiers manage weight trainingsamples associateweighttoeachweakclassifier TheStrongClassifiers weakclassifiers slightlybetterthanrandom strongclassifier Howgoodthestrongonewillbe AdaBoost ItsApplications TheAdaBoostAlgorithm TheAdaBoostAlgorithm Given Initialization For FindclassifierwhichminimizeserrorwrtDt i e Weightclassifier Updatedistribution TheAdaBoostAlgorithm Given Initialization For FindclassifierwhichminimizeserrorwrtDt i e Weightclassifier Updatedistribution Outputfinalclassifier Boostingillustration WeakClassifier1 Boostingillustration WeightsIncreased Boostingillustration WeakClassifier2 Boostingillustration WeightsIncreased Boostingillustration WeakClassifier3 Boostingillustration Finalclassifierisacombinationofweakclassifiers AdaBoost ItsApplications HowandwhyAdaBoostworks TheAdaBoostAlgorithm Given Initialization For FindclassifierwhichminimizeserrorwrtDt i e Weightclassifier Updatedistribution Outputfinalclassifier WhatgoaltheAdaBoostwantstoreach TheAdaBoostAlgorithm Given Initialization For FindclassifierwhichminimizeserrorwrtDt i e Weightclassifier Updatedistribution Outputfinalclassifier WhatgoaltheAdaBoostwantstoreach Goal Minimizeexponentialloss Finalclassifier Goal Minimizeexponentialloss Finalclassifier MaximizethemarginyH x Goal Finalclassifier Minimize Define with Then Finalclassifier Minimize Define with Then Set 0 Finalclassifier Minimize Define with Then 0 with Finalclassifier Minimize Define Then 0 with Finalclassifier Minimize Define Then 0 with Finalclassifier Minimize Define Then with Finalclassifier Minimize Define Then with Finalclassifier Minimize Define Then maximizedwhen with Finalclassifier Minimize Define Then Attimet with Finalclassifier Minimize Define Then Attimet Attime1 Attimet 1 AdaBoost ItsApplications AdaBoostforFaceDetection TheTaskofFaceDetection ManyslidesadaptedfromP Viola BasicIdea Slideawindowacrossimageandevaluateafacemodelateverylocation Challenges Slideawindowacrossimageandevaluateafacemodelateverylocation Slidingwindowdetectormustevaluatetensofthousandsoflocation scalecombinations Facesarerare 0 10perimageForcomputationalefficiency weshouldtrytospendaslittletimeaspossibleonthenon facewindowsAmegapixelimagehas 106pixelsandacomparablenumberofcandidatefacelocationsToavoidhavingafalsepositiveineveryimageimage ourfalsepositiveratehastobelessthan10 6 TheViola JonesFaceDetector Aseminalapproachtoreal timeobjectdetectionTrainingisslow butdetectionisveryfastKeyideasIntegralimagesforfastfeatureevaluationBoostingforfeatureselectionAttentionalcascadeforfastrejectionofnon facewindows P ViolaandM Jones Rapidobjectdetectionusingaboostedcascadeofsimplefeatures CVPR2001 P ViolaandM Jones Robustreal timefacedetection IJCV57 2 2004 ImageFeatures Rectanglefilters ImageFeatures Rectanglefilters SizeofFeatureSpace Howmanynumberofpossiblerectanglefeaturesfora24x24detectionregion Rectanglefilters A B C D FeatureSelection Howmanynumberofpossiblerectanglefeaturesfora24x24detectionregion A B C D Whatfeaturesaregoodforfacedetection FeatureSelection Howmanynumberofpossiblerectanglefeaturesfora24x24detectionregion A B C D Canwecreateagoodclassifierusingjustasmallsubsetofallpossiblefeatures Howtoselectsuchasubset Integralimages Theintegralimagecomputesavalueateachpixel x y thatisthesumofthepixelvaluesaboveandtotheleftof x y inclusive x y ComputingtheIntegralImage Theintegralimagecomputesavalueateachpixel x y thatisthesumofthepixelvaluesaboveandtotheleftof x y inclusive Thiscanquicklybecomputedinonepassthroughtheimage x y ComputingSumwithinaRectangle D B C A Only3additionsarerequiredforanysizeofrectangle Scaling Integralimageenablesustoevaluateallrectanglesizesinconstanttime Therefore noimagescalingisnecessary Scaletherectangularfeaturesinstead 1 2 3 4 5 6 Boosting BoostingisaclassificationschemethatworksbycombiningweaklearnersintoamoreaccurateensembleclassifierAweaklearnerneedonlydobetterthanchanceTrainingconsistsofmultipleboostingroundsDuringeachboostinground weselectaweaklearnerthatdoeswellonexamplesthatwerehardforthepreviousweaklearners Hardness iscapturedbyweightsattachedtotrainingexamples Y FreundandR Schapire Ashortintroductiontoboosting JournalofJapaneseSocietyforArtificialIntelligence 14 5 771 780 September 1999 TheAdaBoostAlgorithm Given Initialization For FindclassifierwhichminimizeserrorwrtDt i e Weightclassifier Updatedistribution TheAdaBoostAlgorithm Given Initialization For FindclassifierwhichminimizeserrorwrtDt i e Weightclassifier Updatedistribution Outputfinalclassifier WeakLearnersforFaceDetection Given Initialization For FindclassifierwhichminimizeserrorwrtDt i e Weightclassifier Updatedistribution Outputfinalclassifier Whatbaselearnerisproperforfacedetection WeakLearnersforFaceDetection Boosting TrainingsetcontainsfaceandnonfaceexamplesInitially withequalweightForeachroundofboosting EvaluateeachrectanglefilteroneachexampleSelectbestthresholdforeachfilterSelectbestfilter thresholdcombinationReweightexamplesComputationalcomplexityoflearning O MNK Mrounds Nexamples Kfeatures FeaturesSelectedbyBoosting Firsttwofeaturesselectedbyboosting Thisfeaturecombinationcanyield100 detectionrateand50 falsepositiverate ROCCurvefor200 FeatureClassifier A200 featureclassifiercanyield95 detectionrateandafalsepositiverateof1in14084 Notgoodenough Tobepracticalforrealapplication thefalsepositiveratemustbecloserto1in1 000 000 AttentionalCascade Classifier3 Classifier2 Classifier1 IMAGESUB WINDOW T T Westartwithsimpleclassifierswhichrejectmanyofthenegativesub windowswhiledetectingalmostallpositivesub windowsPositiveresponsefromthefirstclassifiertriggerstheevaluationofasecond morecomplex classifier andsoonAnegativeoutcomeatanypointleadstotheimmediaterejectionofthesub window AttentionalCascade Classifier3 Classifier2 Classifier1 IMAGESUB WINDOW T T Chainclassifiersthatareprogressivelymorecomplexandhavelowerfalsepositiverates DetectionRateandFalsePositiveRateforChainedClassifiers Classifier3 Classifier2 Classifier1 IMAGESUB WINDOW T T ThedetectionrateandthefalsepositiverateofthecascadearefoundbymultiplyingtherespectiveratesoftheindividualstagesAdetectionrateof0 9andafalsepositiverateontheorderof10 6canbeachievedbya10 stagecascadeifeachstagehasadetectionrateof0 99 0 9910 0 9 andafalsepositiverateofabout0 30 0 310 6 10 6 TrainingtheCascade SettargetdetectionandfalsepositiveratesforeachstageKeepaddingfeaturestothecurrentstageuntilitstargetrateshavebeenmetNeedtolowerAdaBoostthresholdtomaximizedetection asopposedtominimizingtotalclassificationerror TestonavalidationsetIftheoverallfalsepositiverateisnotlowenough thenaddanotherstageUsefalsepositivesfromcurrentstageasthenegativetrainingexamplesforthenextstage TrainingtheCascade ROCCurvesCascadedClassifiertoMonlithicClassifier ROCCurvesCascadedClassifiertoMonlithicClassifier Thereislittledifferencebetweenthetwointermsofaccuracy Thereisabigdifferenceintermsofspeed Thecascadedclassifierisnearly10timesfastersinceitsfirststagethrowsoutmostnon facessothattheyareneverevaluatedbysubsequentstages TheImplementedSystem TrainingData5000facesAllfrontal rescaledto24x24pixels300millionnon faces9500non faceimagesFacesarenormalizedScale translationManyvariationsAcrossindividualsIlluminationPose StructureoftheDetectorCascade Combiningsuccessivelymorecomplexclassifiersincascade38stagesincludedatotalof6060features StructureoftheDetectorCascade RejectSub Window 1 2 3 4 5 6 7 8 38 Face F F F F F F F F F T T T T T T T T T AllSub Windows 2features reject50 non faces detect100 faces 10features reject80 non faces detect100 faces 25features 50features byalgorithm SpeedoftheFinalDetector Ona700MhzPentiumIIIprocessor thefacedetectorcanprocessa384 288pixelimageinabout 067seconds 15Hz15timesfasterthanpreviousdetectorofcomparableaccuracy Rowleyetal 1998 Averageof8fea