Transcript tracking - University of Washington

Electrical Engineering
Information Processing Lab
Object Tracking, Trajectory Analysis
and Event Detection in Intelligent
Video Systems
Student: Hsu-Yung Cheng
Advisor: Jenq-Neng Hwang, Professor
Department of Electrical Engineering
University of Washington
1
Electrical Engineering
Information Processing Lab
Outlines
Motivation
 Object Tracking
 Trajectory Analysis
 Event Detection
 Conclusions and Future Work

2
Electrical Engineering
Information Processing Lab
Motivation

Advantage of Video-based systems
Being able to capture a large variety of information
 Relatively inexpensive
 Easier to install, operate, and maintain


Applications
Security surveillance
 Home care surveillance
 Intelligent transportation systems
There is an urgent need for intelligent video systems
to replace human operators to monitor the areas under
surveillance.


3
Electrical Engineering
Information Processing Lab
System Modules for Intelligent Event
Detection Systems
4
Electrical Engineering
Information Processing Lab
Challenges for Robust Tracking
Segmentation errors
 Change of lighting conditions
 Shadows
 Occlusion

5
Electrical Engineering
Information Processing Lab
Inter-Object Occlusion
6
Electrical Engineering
Information Processing Lab
Initial Occlusion
7
Electrical Engineering
Information Processing Lab
Background Occlusion
8
Electrical Engineering
Information Processing Lab
Proposed Tracking Mechanism
Image
Frames
Background
Estimation
and Updating
Current
Frame
Background
Image
Moving
Object
Segmentation
Tracking Result
for Previous Frame
Tracking
List
Construction
Measurement
Candidate List
Prediction
Constructing
measurement
candidate List
for Each Target
Data
Association
and Update
Tracking Result
for Current Frame
9
Electrical Engineering
Information Processing Lab
Background Estimation and Updating








Based on Gaussian mixture models [Stauffer 1999]
Model the recent history of each pixel by a mixture of K
Gaussian distributions.
Every pixel value is checked among the existing K Gaussian
distributions for a match.
Update the weights for the K distributions and the parameters
of the matched distribution
The kth Gaussian is ranked by wk /  k (  k   k 2 I )
The top-ranked Gaussians are selected as the background models.
Pixel values that belong to background models are accumulated
and averaged as the background image.
The background image is updated for every certain interval of
time.
10
Electrical Engineering
Information Processing Lab
Moving Object Segmentation


Based on background subtraction
Fourth order moment
[S. Colonnese et al. Proc. of SPIE 2003]
d

( 4)
1
( x, y ) 
N
4
ˆ
(
diff
_
img
(
s
,
t
)

m
)

d
( s , t ) ( x , y )
Thresholding
1, if  d ( 4 ) ( x, y )  
S ( x, y )  
( 4)
0
,
if

( x, y )  
d

11
Electrical Engineering
Information Processing Lab
Kalman Filter

Kalman filters are modeled on a Markov chain
built on linear operators perturbed by Gaussian
noises.
 At time k, each target has state
xk
xk  Fk xk 1  wk , where wk ~ (0, Qk )
and observation (measurement)
yk  H k xk  vk
yk
, where vk ~ (0, Rk )
Kalman, R. E. "A New Approach to Linear Filtering and Prediction Problems,“
Transactions of the ASME - Journal of Basic Engineering Vol. 82: pp. 35-45, 1960.
12
Electrical Engineering
Information Processing Lab
Kalman Filter Phases
Predict
Updated
State
Estimate
Predicted State xˆk k 1
xˆk |k
Observed
yk
Measurements
xk  yk  [uk vk uk vk ]T
Update
1
0
Fk  
0

0
0
1
0
0
1
0
1
0
0
1
0

1
1
0
Hk  
0

0
0
1
0
0
0
0
1
0
0
0
0

1
13
Electrical Engineering
Information Processing Lab
Kalman Filter Phases
Predict Phase
Update Phase
• Updated State Estimate
• Predicted State
xˆk k 1  Fk xˆk 1 k 1
xˆk |k  xˆk |k 1  K k ~
yk
• Updated Estimate Covariance
Pk |k  ( I  K k H k ) Pk |k 1
• Predicted Estimate
Covariance
• Kalman Gain
K k  Pk |k 1H k Sk
T
1
Pk k 1  Fk Pk 1 k 1Fk  Qk • Innovation Covariance
T
Sk  H k Pk |k 1H k  Rk
T
• Innovation (Measurement) Residual
~
yk  yk  H k xˆk |k 1
14
Electrical Engineering
Information Processing Lab
Constructing Measurement
Candidate List
15
Electrical Engineering
Information Processing Lab
Searching for measurement
candidate representation points
• Search for q1 and q2 in the two n x n
windows centered around p1 and p2,
respectively.
q1  arg max Area(O(q)  Sc )
q1 ( x , y )
q2  arg max Area(O(q)  Sc )
q2 ( x , y )
• Compute the dissimilarities
between the target object and
the potential measurement
candidates.
16
Electrical Engineering
Information Processing Lab
Data Association


To associate measurements with targets when
performing updates
Nearest Neighbor Data Association
For all the measurement in the validation gate of a
target, select the nearest measurement.
1
[ yk  H k xk ]T S k [ yk  H k xk ]   2


Probabilistic Data Association (PDA)
Joint Probabilistic Data Association (JPDA)
17
Electrical Engineering
Information Processing Lab
Probabilistic Data Association
 j  P{X j | Y k }
2
y2
Consider a single target independently
of others
j
denotes the event that the j th
measurement belongs to that target.
1
x
y1
y3
3
Combined (Weighted) Innovation
m
m
j 1
j 1
~
yk    j ~
ykj    j ( ykj  H k xˆk|k 1 )
Y . Bar-Shalom and E. Tse, “Tracking in a cluttered environment
with probabilistic data association,” Automatica, vol. 11, pp. 451-460, Sept. 1975.
18
Electrical Engineering
Information Processing Lab
Modified PDA for
Video Object Tracking
• To handle video objects (regions), incorporate the
following factor when computing  j

Similarity j
 (1   )
m
 Similarity
i
i 1
OverlapArea j
m
 OverlapArea
i 1
i
0   1
• Similarity measure: cross correlation function
CR 
 ( A
mn
m
 A )( Bmn  B )
n
( ( Amn  A ) 2 )( ( Bmn  B ) 2 )
m
n
m
n
19
Electrical Engineering
Information Processing Lab
Experimental Videos
20
Electrical Engineering
Information Processing Lab
Vehicle Tracking Results 1
21
Electrical Engineering
Information Processing Lab
Vehicle Tracking Results 2
22
Electrical Engineering
Information Processing Lab
Human Tracking Results
23
Electrical Engineering
Information Processing Lab
Object Tracking Statistics
Video
Sequence 1
Sequence 2
Sequence 3
Sequence 4
Ground Truth
71
64
92
130
Object Detected
72
61
93
128
Miss
0
3
0
5
False Alarm
1
0
1
3
Correctly Detected
71
61
92
125
Correctly Tracked
70
58
92
120
Detection Precision
0.986
1.000
0.989
0.977
Detection Recall
1.000
0.953
1.000
0.962
Tracking Success Rate
0.986
0.951
1.000
0.960
Detection Precision 
Correctly Detected
Object Detected
Tracking Success Rate 
Detection Recall 
Correctly Detected
Ground Truth
Correctly Tracked
Correctly Detected
Occluded Object Tracking Success Rate: 0.855
24
Electrical Engineering
Information Processing Lab
Trajectory Analysis
Class 1
Class 2
Class 3
Class 5
Class 4
Class 6
25
Electrical Engineering
Information Processing Lab
Trajectory Smoothing
• Sample
the
trajectory
• Perform cubic
spline interpolation
26
Electrical Engineering
Information Processing Lab
Angle Feature Extraction
Relative Angle
Absolute Angle

v1  ( ~
xt  ~
xt k , ~
yt  ~
yt k )

v2  ( ~
xt k  ~
xt , ~
yt k  ~
yt )
 

v
v
 p  cos 1  1 2
 v1 v2




 vh  v2
 h  cos   
 vh v2




1
27
Electrical Engineering
Information Processing Lab
Hidden Markov Model
N
states Si , i=1,…, N
 Transition probability aij
 Initial probability pi
 Observation symbol probability bj(k)
 A complete model l=(A,B,P)
A={aij}
 B={bjk}


P={pi}
Sunny
P(walk) = 0.5
P(bike) = 0.4
P(bus) = 0.1
Cloudy
P(walk) = 0.4
P(bike) = 0.3
P(bus) = 0.3
Rainy
P(walk) = 0.2
P(bike) = 0.1
P(bus) = 0.7
28
Electrical Engineering
Information Processing Lab
Example of HMM
Observation sequence O = { walk, bike, bus, bus, bike, walk, … }
29
Electrical Engineering
Information Processing Lab
Three Problems in HMM

Given l, compute the probability that O is
generated by this model
How likely did O happen at this place?

Given l, find the most likely sequence of hidden
states that could have generated O
How did the weather change day-by-day?

forward-backward algorithm
Viterbi algorithm
Given a set of O, learn the most likely l
Train the parameters of the HMM
Baum-Welch algorithm
30
Electrical Engineering
Information Processing Lab
Left-to-right HMM for
Trajectory Classification
31
Electrical Engineering
Information Processing Lab
K-means Clustering of
Feature Points
32
Electrical Engineering
Information Processing Lab
Number of Training
and Test sequences
Video for both training and testing
Video for testing only
Trajectory
Class
Training
Trajectories
Testing
Objects
Testing
Trajectories
Class 1
12
64
307
Class 2
11
18
66
Class 3
13
27
27
Class 4
5
20
20
Class 5
8
26
32
Class 6
8
29
45
33
Electrical Engineering
Information Processing Lab
Trajectory Classification Statistics
C1
C2
C3
C4
C5
C6
Accuracy
Class 1
307
0
0
0
0
0
100%
Class 2
0
64
0
0
0
2
97.4%
Class 3
2
0
25
0
0
0
92.6%
Class 4
0
0
0
20
0
0
100%
Class 5
1
0
0
0
31
0
96.8%
Class 6
0
2
0
0
0
43
95.5%
34
Electrical Engineering
Information Processing Lab
Anomalous Trajectories
35
Electrical Engineering
Information Processing Lab
Event Detection

Type I Events





Type II Events

Based on trajectory classification results via HMM using angle features

Illegal U-turns or left turns
Anomalous trajectories


Simple rule-based decision logic
Entering a dangerous region
Stopping in the scene
Driving on the road shoulder
Type III Events

Based on trajectory classification results via HMM using speed features

Speed change
36
Electrical Engineering
Information Processing Lab
Conclusions and Future Works


Tracking

Kalman filtering for prediction

Modified PDA for data association
Basic Events
 Simple rule-based decision logic


HMM
Higher Level Events


Combining basic events
More flexible models
Trajectories
Intermediate
Events
Basic Events
Angle Features,
Speeds,
Positions,
Other Features
HMMs
High
Level
Events
Type II,
Type III
Events
HMMs
DBNs
Rule-based
Detection Logic
Type I
Events
37
Electrical Engineering
Information Processing Lab
38