Transcript Tutorial - faculty.ucmerced.edu

2009 京都
Tutorial – Part 3
Tracking Using Classification
and Online Learning
Björn Stenger
28 Sep 2009
Copyright 2008, Toshiba Corporation.
1
Roadmap
Online Random Forest
Adaptive Trees
Multi-Classifier Boosting
Combining off-line & on-line
Multiple Instance Learning
On-line Boosting
Ensemble Tracking
Online Feature Selection
Tracking by classification
Tracking by optimization
2
Tracking by Optimization
[Comaniciu et al. 00]
Example: Mean shift tracking
Given: target location in frame t,
color distribution
In frame t+1:
Minimize distance
p candidate distribution
q target distribution
y location
Mean shift: iterative optimization
Finds local optimum
Extension: downweight by
background
3
[Avidan 01]
Support Vector Tracking
Combines SVM classifier with optical flow-based tracking
Input:
- Initial guess x of object location in frame t
- SVM classifier (trained on ~10,000 example images)
Algorithm:
Maximize SVM classification score
SVM eqn
Motion eqn (1st order Taylor)
Results in this task:
Use first order Taylor approximation, obtain linear system
Prior knowledge of classifier is used in tracking process, no online update!
4
Online Selection of Discriminative Features
[Collins et al. 03]
Select features that best discriminate between object and
background
Feature pool:
Discriminative score:
measure separability (variance ratio) of fg/bg
Total variance
should be large
Within class variance
should be small
7
On-line Feature Selection (2)
Input image:
Feature ranking according to
variance ratio
[Collins et al. 03]
Combining estimates
Mean
shift
Mean
shift
Mean
shift
Median
New location
8
Ensemble Tracking
[Avidan 05]
Use classifiers to distinguish object from background
Image
Feature space
foreground
First location is provided
manually
All pixels are training data
labeled {+1,-1}
background
11-dimensional feature vector
8 orientation histogram of 5x5 nhood
3 RGB values
9
Ensemble Tracking
Feature space
[Avidan 05]
Confidence map
Mean shift
foreground
background
Train T (=5) weak linear
classifiers h:
Combine into strong
Classifier with AdaBoost
Find the mode
using mean shift
Build confidence map from
classifier margins
Scale positive margin to [0,1]
10
Ensemble Tracking Update
[Avidan 05]
For each new frame Ij
Test examples xi using strong classifier H(x)
Run mean shift on confidence map
Obtain new pixel labels y
Keep K (=4) best (lowest error) weak classifiers
Update their weights
h1 h2 h3 h4 h5
Train T-K (=1) new weak classifiers
11
AdaBoost (recap)
Feature space
[Freund, Schapire 97]
Input
- Set of labeled training samples
- Weight distribution over samples
Algorithm
for n=1 to N // number of weak classifiers
- train a weak classifier using samples and
weight distribution
- calculate error
- calculate classifier weight
- update sample weights
end
Result
[slide credit H. Grabner]
13
From Off-line to On-line Boosting
[Oza, Russel 01]
Off-line
On-line
Input
- set of labeled training samples
Input
- ONE labeled training sample
- weight distribution over samples
- strong classifier to update
- initial sample importance
Algorithm
For n=1 to N
End
Algorithm
For n=1 to N
- train a weak classifier using samples and
weight distribution
- update weak classifier using samples
and importance
- calculate error
- update error estimate
- calculate confidence
- update confidence
- update weight distribution
- update importance
End
[slide credit H. Grabner]
15
Online Boosting
Feature space
[Oza, Russell 01]
Input
- ONE labeled training sample
- strong classifier
Algorithm
- initial sample importance
for n=1 to N // number of weak classifiers
- update weak classifier using sample and
importance
- update error estimate
- update classifier weight
- update sample importance
end
Result
[slide credit H. Grabner]
16
Priming can help
[Oza 01]
Batch learning on first 200 points, then online
19
Online Boosting for Feature Selection
Combination of simple features
[Grabner, Bischof 06]
Each feature corresponds to a
weak classifier
20
Selectors
[Grabner, Bischof 06]
A selector chooses one feature/classifier from pool.
Classifier pool
Selectors can be seen as classifiers
Idea: Perform boosting on selectors, not
the features directly.
21
Online Feature Selection
[Grabner, Bischof 06]
For each training sample
Global classifier pool
one
sample
Init
importance
Estimate
errors
Estimate
errors
Select best
weak
classifier
Update
weight
Estimate
importance
Select best
weak
classifier
Update
weight
Estimate
errors
Estimate
importance
Select best
weak
classifier
Update
weight
Current strong classifier
22
Tracking Principle
[Grabner, Bischof 06]
[slide credit H. Grabner]
23
Adaptive Tracking
[Grabner, Bischof 06]
24
Limitations
[Grabner, Bischof 06]
25
Multiple Instance Learning (MIL)
[Keeler et al. 90,
Dietterich et al. 97,
Viola et al. 05]
 Precisely labeled data is expensive
Weakly labeled data is easier to collect
 Algorithm for allowing ambiguity in training data:
Get bag of (data, label) pairs
 Bag is positive if one or more of its members is positive.
26
Multiple Instance Learning
Supervised learning
training input
Classifier
[Babenko et al. 09]
MIL training input
MIL
Classifier
27
Online MIL Boost
[Babenko et al. 09]
 At time t get more training data
1 Update all candidate classifiers
2 Pick best K in a greedy fashion
pool of
weak classifier candidates
28
Online MIL Boost
[Babenko et al. 09]
Frame t
Frame t+1
Get data (bags)
Update all classifiers
in pool
Greedily add best K to
strong classifier
29
Tracking Results
[Babenko et al. 09]
30
On-line / Off-line Spectrum
Tracking
Object/Background classifier
On-line update
Tracking
with prior
Adaptive
detector
Example strategies:
 Run detector in tandem to verify
[Williams et al. 03]
 Include generative model
[Woodley et al. 06][Grabner et al. 07]
 Integrate tracker and detector
[Okuma et al. 04][Li et al. 07]
Detection
General object/any background detector
Fixed training set
c/f Template Update Problem [Matthews et al. 04]
31
Semi-supervised
[Grabner et al. 08]
Use labeled data as prior
Estimate labels & sample importance for unlabeled data
32
Tracking Results
[Grabner et al. 08]
33
Beyond Semi-Supervised
[Stalder et al. 09]
“too inflexible”
Recognizer
Object specific
“Adaptive prior”
Updated by:
pos: Tracked samples
validated by detector
neg: Background
during detection
35
Results
[Stalder et al. 09]
36
Task: Tracking a Fist
38
Learning to Track with Multiple Observers
[Stenger et al. 09]
Idea: Learn optimal combination of observers (trackers) in an off-line
training stage.
Each tracker can be fixed or adaptive.
Given: labeled training data, object detector
Optimal tracker
for task at hand
Observation
Models
Off-line training
of observer
combinations
Labeled
Training
Data
39
Input: Set of observers
[Stenger et al. 09]
Each returns a location estimate & confidence value
Single
template
[NCC]
[SAD]
Normalized cross-correlation
Sum of absolute differences
Local
features
[BOF]
[KLT]
[FF]
[RT]
[MS]
[C]
[M]
[CM]
[OB]
[LDA]
[BLDA]
[OFS]
Block-based optical flow
Kanade-Lucas-Tomasi
Flocks of features
Randomized templates
Color-based mean shift
Color probability
Motion probability
Color and motion probability
On-line boosting
Linear Discriminant Analysis (LDA)
Boosted LDA
On-line feature selection
Histogram
On-line
classifiers
40
Combination Schemes
[Stenger et al. 09]
Find good combinations of observers automatically by
evaluating all pairs/triplets (using 2 different schemes).
1)
2)
41
How to Measure Performance?
[Stenger et al. 09]
Run each tracker on all frames (don’t stop after first failure)
Measure position error
Loss of track when error above threshold
Re-init with detector
42
Results on Hand Data
[Stenger et al. 09]
Pairs of
observers
Single observers
44
Tracking Results
[Stenger et al. 09]
45
Face Tracking Results
[Stenger et al. 09]
46
[Kim et al. 09]
Multi-Classifier Boosting
 Simultaneously learn image clusters and classifiers
AdaBoost
Multi-class boosting with gating function
47
Online Multi-Class Boosting
[Kim et al. 09]
 Handles multiple poses: take maximum classifier response
48
And now
Trees
49
Online Adaptive Decision Trees
[Basak 04]
Sigmoidal soft partitioning function at each node
Activation value at node i
hyperplane
 Complete binary trees, tree structure is maintained, each class = subset of
leaves, label leaf nodes beforehand
 For each training sample, adapt decision hyperplanes at all inner nodes via
gradient descent on error measure (leaf node activation)
50
Adaptive Vocabulary Forests
[Yeh et al. 07]
 Application: Efficient indexing, leafs represent visual words
 Batch learning: hierarchical k-means, cf. [Nister and Stewenius 06]
[slide credit T. Yeh]
51
Incremental Building of Vocabulary Tree
[Yeh et al. 07]
52
Tree Growing by Splitting Leaf Nodes
[Yeh et al. 07]
53
Tree Adaptation with Re-Clustering
Identify affected
neighborhood
Remove exisiting
boundaries
[Yeh et al. 07]
Re-Cluster points
54
Accuracy drops when Adaptation is stopped
[Yeh et al. 07]
Recent accuracy
T=100
R(j) = 1
if top ranked
retrieved image
belongs to same
group
55
Tree Pruning
[Yeh et al. 07]
 Limit the number of
leaf nodes
 Keep record of
inactivity period at
each node, if limit
reached, remove
nodes with leastrecently used access
 Allows for
restructuring of heavily
populated areas
56
On-line Random Forests
[Saffari et al. 09]
Input: New training example
Random forest
…
For each tree t
Update tree t with
k times
Estimate Out-of-bag error
P(Discard tree t and insert new one) =
end
57
Leaf Update and Split
Current leaf node
[Saffari et al. 09]
Set of random split functions
class k
Compute gain of each potential split function
Split node when
1) Number of samples in node > threshold 1
2) Gain of best split > threshold 2
58
Results
Convergence of on-line RF classification
to batch solution on USPS data set
[Saffari et al. 09]
Tracking error of online RF
compared to online boosting
59
Conclusions
 On-line versions exist for Boosting and Random Forests
 Experimentally good convergence results (but few
theoretical guarantees)
 Useful for Tracking via Classification
 A lot of code has been made available online by authors
 Detection – Tracking Spectrum
 Adaptation vs. Drift
60
References
Avidan, S.,
Support Vector Tracking,
IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR),
Hawaii, 2001.
Comaniciu, D., Ramesh, V., Meer P.,
Real-Time Tracking of Non-Rigid Objects using Mean Shift,
IEEE Conf. Computer Vision and Pattern Recognition, Hilton Head Island, South Carolina, Vol. 2, 142-149,
2000.
Avidan, S.,
Support Vector Tracking ,
IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), Vol. 26(8), pp. 1064-1072, 2004.
T. G. Dietterich and R. H. Lathrop and T. Lozano-Perez,
Solving the multiple instance problem with axis-parallel rectangles.
Artificial Intelligence 89 31-71, 1997.
Avidan, S.,
Ensemble Tracking,
IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), Vol. 29(2), pp 261-271,
2007.
Avidan, S.,
Ensemble Tracking,
IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), San
Diego, USA, 2005.
Babenko, B., Yang, M.-H., Belongie, S.,
Visual Tracking with Online Multiple Instance Learning,
Proc. CVPR 2009.
Basak, J.,
Online adaptive decision trees,
Neural Computation, v.16 n.9, p.1959-1981, September 2004.
Collins, R. T., Liu, Y., Leordeanu, M.,
On-Line Selection of Discriminative Tracking Features,
IEEE Transaction on Pattern Analysis and Machine Intelligence (PAMI), Vol 27(10), October
2005, pp.1631-1643.
Freund, Y. , Schapire, R. E. ,
A decision-theoretic generalization of on-line learning and an application to boosting.
Journal of Computer and System Sciences, 55(1):119–139, August 1997.
H. Grabner, C. Leistner, and H. Bischof,
Semi-supervised On-line Boosting for Robust Tracking.
In Proceedings European Conference on Computer Vision (ECCV), 2008.
H. Grabner, P. M. Roth, H. Bischof,
Eigenboosting: Combining Discriminative and Generative Information,
IEEE Conference on Computer Vision and Pattern Recognition, 2007.
H. Grabner, M. Grabner, and H. Bischof,
Real-time Tracking via On-line Boosting,
In Proceedings British Machine Vision Conference (BMVC), volume 1, pages 47-56, 2006.
H. Grabner, and H. Bischof,
On-line Boosting and Vision,
In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), volume 1, pages 260-267,
2006.
J. D. Keeler , D. E. Rumelhart , W.-K. Leow,
Integrated segmentation and recognition of hand-printed numerals,
Proc. 1990 NIPS 3, p.557-563, October 1990, Denver, Colorado, USA.
Collins, R. T., Liu, Y.,
On-Line Selection of Discriminative Tracking Features,
Proceedings of the 2003 International Conference of Computer Vision (ICCV '03), October,
2003, pp. 346 - 352.
T.-K. Kim and R. Cipolla,
MCBoost: Multiple Classifier Boosting for Perceptual Co-clustering of Images and Visual Features,
In Advances in Neural Information Processing Systems (NIPS), Vancouver, Canada, Dec. 2008.
Comaniciu, D., Ramesh, V., Meer, P.,
Kernel-Based Object Tracking,
IEEE Trans. Pattern Analysis Machine Intell., Vol. 25, No. 5, 564-575, 2003.
T-K. Kim, T. Woodley, B. Stenger, R. Cipolla,
Online Multiple Classifier Boosting for Object Tracking,
CUED/F-INFENG/TR631, Department of Engineering, University of Cambridge, June 2009.
61
References & Code
Y. Li, H. Ai, S. Lao, M. Kawade,
Tracking in Low Frame Rate Video: A Cascade Particle Filter with Discriminative Observers of
Different Lifespans,
Proc. CVPR, 2007.
I. Matthews, T. Ishikawa, and S. Baker,
The template update problem.
In Proc. BMVC, 2003
I. Matthews, T. Ishikawa, and S. Baker,
The Template Update Problem,
IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 26, No. 6, June, 2004, pp. 810
- 815.
K. Okuma, A. Taleghani, N. De Freitas, J. Little, D. G. Lowe,
A Boosted Particle Filter: Multitarget Detection and Tracking ,
European Conference on Computer Vision(ECCV), May 2004.
Oza, N.C.,
Online Ensemble Learning,
Ph.D. thesis, University of California, Berkeley.
Oza, N.C. and Russell, S.,
Online Bagging and Boosting.
In Eighth Int. Workshop on Artificial Intelligence and Statistics, pp. 105–112, Key West, FL, USA,
January 2001.
Oza, N.C. and Russell, S.,
Experimental Comparisons of Online and Batch Versions of Bagging and Boosting,
The Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San
Francisco, California, 2001.
Saffari, A., Leistner C., Santner J., Godec M., Bischof H.,
On-line Random Forests,
3rd IEEE ICCV Workshop on On-line Computer Vision, 2009.
P. A. Viola and J. Platt and C. Zhang,
Multiple instance boosting for object detection,
Proceedings of NIPS 2005.
O. Williams, A. Blake, and R. Cipolla,
Sparse Bayesian Regression for Efficient Visual Tracking,
in IEEE Transactions on Pattern Analysis and Machine Intelligence, IEEE Computer Society, August 2005.
O. Williams, A. Blake, and R. Cipolla,
A Sparse Probabilistic Learning Algorithm for Real-Time Tracking,
in Proceedings of the Ninth IEEE International Conference on Computer Vision, October 2003.
T. Woodley, B. Stenger, R. Cipolla,
Tracking Using Online Feature Selection and a Local Generative Model,
Proc. BMVC, Warwick, September 2007.
T. Yeh, J. Lee, and T. Darrell,
Adaptive Vocabulary Forests for Dynamic Indexing and Category Learning.
Proc. ICCV 2007.
Code:
Severin Stalder, Helmut Grabner
Online Boosting, Semi-supervised Online Boosting, Beyond Semi-Supervised Online Boosting
http://www.vision.ee.ethz.ch/boostingTrackers/index.htm
Boris Babenko
MIL Track
http://vision.ucsd.edu/~bbabenko/project_miltrack.shtml
Amir Saffari
http://www.ymer.org/amir/software/online-random-forests/
S. Stalder, H. Grabner, and L. Van Gool,
Beyond Semi-Supervised Tracking: Tracking Should Be as Simple as Detection, but not Simpler than
Recognition.
In Proceedings ICCV’09 WS on On-line Learning for Computer Vision, 2009.
B. Stenger, T. Woodley, R. Cipolla,
Learning to Track With Multiple Observers.
Proc. CVPR, Miami, June 2009.
62