1Active learning for visual objectrecognitionWritten byYotam Abramson and Yoav FreundPresented byBen LaxtonOutline• Motivation and procedure• How this works: adaboost and feature details• Why this works: boosting the margin fordiscriminative classifiers• How well this works: results2MotivationObservations:- Machine learning methods are preferred forvisual object detection.- Most, if not all, require large amounts of handlabeled training data- It is hard for people to identify ‘hard’ instancesfor trainingMotivationHow much data is required?-Most require on the order of thousands of labeledpositive examples-Viola-Jones used 4916 labeled faces for training49163MotivationHow much data is required?-Most require on the order of thousands of labeledpositive examples-Viola-Jones used 4916 labeled faces for training4916 * 10(sec)MotivationHow much data is required?-Most require on the order of thousands of labeledpositive examples-Viola-Jones used 4916 labeled faces for training4916 * 10(sec) = 14 hours4Motivation• ‘Hard examples providemore information than‘easy’ ones• How do we identify ‘hard’examples?– Interaction betweenclassifier and humanoperator.Motivation• ‘Hard examples providemore information than‘easy’ ones• How do we identify ‘hard’examples?– Interaction betweenclassifier and humanoperator.5Motivation• ‘Hard examples providemore information than‘easy’ ones• How do we identify ‘hard’examples?– Interaction betweenclassifier and humanoperator.Motivation• ‘Hard examples providemore information than‘easy’ ones• How do we identify ‘hard’examples?– Interaction betweenclassifier and humanoperator.• We will see that the notionof margin provides a niceframework for selectingthese ‘hard’ examples‘Easy’ values to classify‘Hard’ examples provide the most new information6Procedure• SEVILLE (Semi automatic Visual Learning)provides an intuitive framework to achieve thesegoals• Combines adaboost detectors (similar to Viola-Jones) with human interaction in an iterativefashion• Can be used as a good labeling framework ingeneralProcedure• First, play inputimages and manuallycollect a small numberof positive andnegative examples• Train a classifier onthese examples7Procedure• Upon running theclassifier, SEVILLEdisplays exampleswithin the margins• Label all of theseexamples and re-traina classifierProcedure• Continue this processon new frames.• The resulting classifiershould converge tooptimal8Outline• Motivation and procedure• How this works: adaboost and feature details• Why this works: boosting the margin fordiscriminative classifiers• How well this works: resultsSEVILLE Implementation• Structured after the detector developed byViola and Jones• Uses Adaboost to boost weak classifiers• Additional idea of intensity-invariant, fast,single pixel-based detectors9Adaboost• Boosting methods produce accurate or ‘strong’classifiers by combining many ‘weak’ classifiersin a principled framework.• Adaboost is one algorithm for doing this:– Training error approaches 0 exponentially in thenumber of rounds.– Probabilistic upper bound for generalization error– Tends not to overfitAdaboost• The weak requirement:h3(x1,y1,w1), … (xn,yn,wn)h4(x1,y1,w1), … (xn,yn,wn)h5(x1,y1,w1), … (xn,yn,wn)h6(x1,y1,w1), … (xn,yn,wn)h7(x1,y1,w1), … (xn,yn,wn)h8(x1,y1,w1), … (xn,yn,wn)h9(x1,y1,w1), … (xn,yn,wn)hT(x1,y1,w1), … (xn,yn,wn)weak learnerh1 (x1,y1,1/n), … (xn,yn,1/n)Sign[ ]h1α1+h2α2+hTαΤ+Strong Rule:Slide Figure Borrowed from Yoav Freund’s Into to Boosting Presentation10Adaboost• Intuitively Adaboost hones in on the ‘best’ simplefeatures.• This is important since there is a huge number offeatures:– For haar-like features used by Viola and Jones, with awindow size of 24x24, there are 45,396 possibilities.Adaboost• Given example images (x1,y1) , … , (xn,yn) where yi = 0, 1 for negative and positive examples respectively. • Initialize weights w1,i = 1/(2m), 1/(2l) for training example i, where m and l are the number of negatives and positives respectively. For t = 1 … T 1) Normalize weights so that wt is a distribution 2) For each feature j train a classifier hj and evaluate its error εj with respect to wt. 3) Chose the classifier hj with lowest error. 4) Update weights according to: βε−=+1,,1itititww where ei = 0 is xi is classified correctly, 1 otherwise, and εεβ−=1ttt • The final strong classifier is: ≥=∑ ∑= =otherwisexxhTtTtttth021)(1)(1 1αα, where )1log(βαtt=11Viola-Jones• The work by Viola and Jones extends the basicadaboost classifier in the following ways:– Rediscovery of the integral image representation forfast feature calculations– Use of haar-like feature basis as weak classifiers– Introduction of a cascaded classifierViola-Jones: Integral imageDef: The integral image at location (x,y), is the sum ofthe pixel values above and to the left of (x,y),inclusive.Using the following two recurrences, where i(x,y) isthe pixel value of original image at the given locationand s(x,y) is the cumulative column sum, we cancalculate the integral image representation of theimage in a single pass.(x,y)s(x,y) = s(x,y-1) + i(x,y)ii(x,y) = ii(x-1,y) + s(x,y)(0,0)xyTaken from Gyozo Gidofalvi’s presentation on Viola-Jones12Viola-Jones: Simple featuresUsing the integral image representationone can compute the value of anyrectangular sum in constant time.For example the integral sum insiderectangle D we can compute as:ii(4) + ii(1) – ii(2) – ii(3)As a result two-, three-, and four-rectangular features can becomputed with 6, 8 and 9 array references respectively.Taken from Gyozo Gidofalvi’s presentation on Viola-JonesViola-Jones: Simple Features• Resulting simplefeatures offer someinsight into what theclassifier is looking atFirst discriminative featureSecond discriminative feature13Viola-Jones: Cascaded Classifier• Using a cascaded classifier can improve therunning time substantially– Discard ‘easier’ examples early on and focus attentionon ‘harder’ ones.– Takes the form of a degenerate decision tree:All examplesRejectAccept…Adaboost: Cascaded Classifier• Detection and false-positive rates can now bebroken down on a per-level basis:– e.g. To get a 10-stage cascaded classifier with adetection rate of 90% and false positive