Object Category Detection: Sliding WindowsGoal: Detect all instances of objectsInfluential Works in DetectionSliding window detectionWhat the Detector SeesStatistical TemplateDesign challengesSchneiderman and KanadeSchneiderman and KanadeParts modelParts: groups of wavelet coefficientsPart LikelihoodTrainingTraining multiple viewpointsTestingResults: facesResults: carsResults: faces todayViola and JonesIntegral ImagesIntegral ImagesAdaboost as feature selectionAdaboostAdaboostAdaboost: Immune to Overfitting?Interpretations of AdaboostAdaboost: Margin MaximizerCascade for Fast DetectionViola-Jones detailsViola Jones ResultsSchneiderman later resultsSpeed: frontal face detectorOcclusions?Strengths and Weaknesses of Statistical Template ApproachSK vs. VJThings to rememberObject Category Detection: Sliding WindowsComputer VisionCS 543 / ECE 549 University of IllinoisDerek Hoiem03/18/10Goal: Detect all instances of objectsInfluential Works in Detection• Sung-Poggio (1994, 1998) : ~1450 citations– Basic idea of statistical template detection (I think), bootstrapping to get “face-like” negative examples, multiple whole-face prototypes (in 1994)• Rowley-Baluja-Kanade (1996-1998) : ~2900– “Parts” at fixed position, non-maxima suppression, simple cascade, rotation, pretty good accuracy, fast• Schneiderman-Kanade (1998-2000,2004) : ~1250– Careful feature engineering, excellent results, cascade• Viola-Jones (2001, 2004) : ~6500– Haar-like features, Adaboost as feature selection, hyper-cascade, very fast, easy to implement• Dalal-Triggs (2005) : 1025– Careful feature engineering, excellent results, HOG feature, online code• Felzenszwalb-McAllester-Ramanan (2008)? 105 citations– Excellent template/parts-based blendSliding window detectionWhat the Detector SeesStatistical Template• Object model = log linear model of parts at fixed positions+3+2 -2-1 -2.5 = -0.5+4+1+0.5 +3+0.5= 10.5> 7.5?> 7.5?Non-objectObjectDesign challenges• Part design– How to model appearance– Which “parts” to include– How to set part likelihoods• How to make it fast• How to deal with different viewpoints• Implementation details– Window size– Aspect ratio– Translation/scale step size– Non-maxima suppressionSchneiderman and KanadeSchneiderman and Kanade. A Statistical Method for 3D Object Detection. (2000)Schneiderman and KanadeDecision function:Parts model• Part = group of wavelet coefficients that are statistically dependentParts: groups of wavelet coefficients• Fixed parts within/across subbands• 17 types of “parts” that can appear at each position• Discretize wavelet coefficient to 3 values• E.g., part with 8 coefficients has 3^8 = 6561 valuesPart Likelihood• Class-conditional likelihood ratio• Estimate P(part|object) and P(part | non-object) by counting over examples• Adaboost tunes weights discriminatively)()&()|(objectcountobjectpartcountobjectpartP =Training1) Create training dataa) Get positive and negative patchesb) Pre-process (optional), compute wavelet coefficients, discretizec) Compute parts values2) Learn statisticsa) Compute ratios of histograms by counting for positive and negative examplesb) Reweight examples using Adaboost, recount, etc. 3) Get more negative examples (bootstrapping)Training multiple viewpointsTrain new detector for each viewpoint.Testing1) Processing:a) Lighting correction (optional)b) Compute wavelet coefficients, quantize2) Slide window over each position/scale (2 pixels, 21/4scale) a) Compute part valuesb) Lookup likelihood ratiosc) Sum over partsd) Threshold3) Use faster classifier to prune patches (cascade…more on this later)4) Non-maximum suppressionResults: faces208 images with 441 faces, 347 in profileResults: carsResults: faces todayhttp://demo.pittpatt.com/Viola and JonesFast detection through two mechanismsViola and Jones. Rapid Object Detection using a Boosted Cascade of Simple Features (2001).Integral Images• “Haar-like features”– Differences of sums of intensity– Thousands, computed at various positions and scales within detection windowTwo-rectangle features Three-rectangle features Etc.-1 +1Integral Images• ii = cumsum(cumsum(Im, 1), 2)x, yii(x,y) = Sum of the values in the grey regionHow to compute A+D-B-C?How to compute B-A?Adaboost as feature selection• Create a large pool of parts (180K)• “Weak learner” = feature + threshold + parity• Choose weak learner that minimizes error on the weighted training set• ReweightAdaboostAdaboost“RealBoost”Figure from Friedman et al. 1999Important special case: htpartitions input space: alphatAdaboost: Immune to Overfitting?Test errorTrain errorInterpretations of Adaboost• Additive logistic regression (Friedman et al. 2000)– LogitBoost from Collins et al. 2002 does this more explicitly• Margin maximization (Schapire et al. 1998)– Ratch and Warmuth 2002 do this more explicitlyAdaboost: Margin MaximizermarginTest errorTrain errorCascade for Fast DetectionExamplesStage 1H1(x) > t1?RejectNoYesStage 2H2(x) > t2?Stage NHN(x) > tN?Yes…PassRejectNoRejectNo• Choose threshold for low false negative rate• Fast classifiers early in cascade• Slow classifiers later, but most examples don’t get thereViola-Jones details• 38 stages with 1, 10, 25, 50 … features– 6061 total used out of 180K candidates– 10 features evaluated on average• Examples– 4916 positive examples– 10000 negative examples collected after each stage• Scanning– Scale detector rather than image– Scale steps = 1.25, Translation 1.0*s to 1.5*s• Non-max suppression: average coordinates of overlapping boxes• Train 3 classifiers and take voteViola Jones ResultsMIT + CMU face datasetSchneiderman later resultsViola-Jones 2001Roth et al. 1999Schneiderman-Kanade 2000Schneiderman 2004Speed: frontal face detector• Schneiderman-Kanade (2000): 5 seconds• Viola-Jones (2001): 15 fpsOcclusions?• A problem• Objects occluded by > 50% considered “don’t care”• PASCAL VOC changed thisStrengths and Weaknesses of Statistical Template ApproachStrengths• Works very well for non-deformable objects: faces, cars, upright pedestrians• Fast detectionWeaknesses• Not so well for highly deformable objects• Not robust to occlusion• Requires lots of training dataSK vs. VJSchneiderman-Kanade• Wavelet features• Log linear model via boosted histogram ratios• Bootstrap training• Two-stage cascade• NMS: Remove overlapping weak boxes•