Statistical Template-Based Object Detection
A Statistical Method for 3D Object Detection Applied to Faces and Cars
Henry Schneiderman and Takeo Kanade
Rapid Object Detection using a Boosted Cascade of Simple Features
Back to recognition
Cascade for Fast Detection
Examples
Yes Stage 1 H1(x) > t1?
Stage 2 …
H2(x) > t2?
Yes
Stage N
HN(x) > tN?
Pห้องสมุดไป่ตู้ss
No
No
No
Reject
Reject
Reject
• Choose threshold for low false negative rate • Fast classifiers early in cascade • Slow classifiers later, but most examples don’t get
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
• Schneiderman-Kanade (2019-2000,2019) : ~1150
– Careful feature engineering, excellent results, cascade
• Viola-Jones (2019, 2019) : ~4400
– Haar-like features, Adaboost as feature selection, very fast, easy to implement
Integral Images
• “Haar-like features”
– Differences of sums of intensity – Millions, computed at various positions and scales
within detection window
-1 +1
• How to make it fast • How to deal with different viewpoints • Implementation details
– Window size – Aspect ratio – Translation/scale step size – Non-maxima suppression
Training multiple viewpoints
Train new detector for each viewpoint.
Testing
1) Processing:
a) Lighting correction (optional) b) Compute wavelet coefficients, quantize
• Margin maximization (Schapire et al. 2019)
– Ratch and Warmuth 2019 do this more explicitly
Adaboost: Margin Maximizer
Test error Train error
margin
Interpretations of Adaboost
Goal: Detect all instances of objects
Influential Works in Detection
• Sung-Poggio (1994, 2019) : ~1260
– Basic idea of statistical template detection (I think), bootstrapping to get “face-like” negative examples, multiple whole-face prototypes (in 1994)
• 17 types of parts • Discretize wavelet coefficient to 3 values • E.g., part with 8 coefficients has 3^8 = 6561
values
Part Likelihood
• Class-conditional likelihood ratio
• Adaboost tunes weights discriminatively
Training
1) Create training data
a) Get positive and negative patches b) Pre-process (optional), compute wavelet
2) Slide window over each position/scale (2 pixels, 21/4 scale)
a) Compute part values b) Lookup likelihood ratios c) Sum over parts d) Threshold
3) Use faster classifier to prune patches (cascade)… more on this later
• Rosset Zhu Hastie 2019
– Early stopping is form of L1-regularization
– In many cases, converges to “L1-optimal” separating hyperplane
– “An interesting fundamental similarity between boosting and kernel support vector machines emerges, as both can be described as methods for regularized optimization in high-dimensional predictor space, utilizing a computational trick to make the calculation practical, and converging to margin-maximizing solutions.”
• Reweight
Sidebar: Adaboost
Adaboost
Adaboost
“RealBoost”
Important special case: ht partitions input space:
alphat
Figure from Friedman et al. 2019
Adaboost: Immune to Overfitting?
– Excellent template/parts-based blend
Sliding window detection
What the Detector Sees
Statistical Template
• Object model = log linear model of parts at fixed positions
Test error Train error
Interpretations of Adaboost
• Additive logistic regression (Friedman et al. 2000)
– LogitBoost from Collins et al. 2019 does this more explicitly
coefficients, discretize c) Compute parts values
2) Learn statistics
a) Compute ratios of histograms by counting for positive and negative examples
b) Reweight examples using Adaboost, recount, etc. More on this later
there
Viola-Jones details
• 38 stages with 1, 10, 25, 50 … features
Two-rectangle features
Three-rectangle features
Etc.
Integral Images
• ii = cumsum(cumsum(Im, 1), 2)
x, y ii(x,y) = Sum of the values in the grey region
How to compute B-A? How to compute A+D-B-C?
Paul Viola and Michael Jones
Presenter: Derek Hoiem CS 598, Spring 2009 Feb 24, 2009
Some slides/figures from /~efros/courses/AP06/presentations/Schneiderman-Kanade%20Viola-Jones%20presentation.ppt