Clustering Trajectories

ImageLab
Modena
People Movement analysis: trajectories
•
Behavior analysis is a crucial tool for threat
assessment and in general scene understanding
•
Trajectory/path analysis is a first fundamental
step for behavior analysis in surveillance:
•
understanding critical and typical paths
•
identify deviations from “normality”
•
collect “occupancy” statistics
•
find suspicious behaviors
But also in other multimedia applications
•
Analyze similarities in videos
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Problem description
Given all the trajectories acquired by a video
surveillance system:
Which are the trajectories that
share some specific location
properties?
Which are the trajectories that
share some specific shape
properties?
Which are the most
frequent Behaviors?
Who did perform them?
people retrieval
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Literature on Trajectory analysis
Literature approaches on trajectory comparison can be classified:

Depending on the Feature (Point to Point vs Statistical):
Adopt a point-to-point comparison or exploit statistical data
representation

Depending on the Representation (Original vs
Transformed): Original feature space or provide a space
transformation

Depending on the Data Dimension (Complete vs
Selected): Use all the temporal data or select a subset
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Related Works
Point to
point
Basharat08
CVPR08
Hu06
PAMI06
Porikli04
CVPRWs04
Junejo04
ICPR04
Bashir03
ICIP03
Chen08
CVPR08
Ding08
VLD08
Shieh08
KDD08
Piotto09
TMM09
Calderara09
AVSS09
Picciarelli09
TCMS09
Feature
Statistical
Representation
Original
Transformed
Distance
Gaussian
x
x
Statistical
Gaussian
x
x
Statistical
HMM
x
x
HMM cross distance
x
x
Hausdorf
x
x
Sampling
x
PCA
PCA
Euclidean
Null Space
Projection
Eigen
decompositi
on
PCNSA(Principal
Component Null
Space analysis)
distance
LB_Keogh
SAX symbol
subspace
Breakpoints
quantization
symbol to symbol
DTW distance
symbol to symbol
Global
Alignment(GA)
distance
GA KL-divergence
pdf distance
SVM Learning
x
x
x
SAX
x
Breakpoints
ApproxWrapped
LinearGaussian
x
Dimension
Complete
Selected
MoAWLG
x
x
Subsampling
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
References:
(Basharat08) Basharat, A. Gritai, and M. Shah. Learning object motion patterns for anomaly detection and improved object detection. In Proc.
of IEEE Int’l Conference on Computer Vision and Pattern Recognition, 2008
(Porikli04) F. Porikli and T. Haga. Event detection by eigenvector decomposition using object and frame features. In Proc. Of Computer Vision
and Pattern Recognition (CVPR) Workshop,volume 7, pages 114–121, 2004.
(Hu06)W. Hu, X. Xiao, Z. Fu, D. Xie, T. Tan, and S. Maybank. A system for learning statistical motion patterns. IEEE Trans. on PAMI, 28(9):1450–
1464, September 2006.
(Junejo04) Junejo, O. Javed, and M. Shah, “Multi feature path modeling for video surveillance,” in Proc. of Int’l Conference on Pattern
Recognition, vol. 2, Aug. 2004, pp. 716– 719.
(Bashir03) F. I. Bashir, A. A. Khokhar, and D. Schonfeld, “Segmented trajectory based indexing and retrieval of video data,” in Proc. of IEEE Int’l
Conference on Image Processing, 2003, pp. 623–626.
(Chen08) X. Chen, D. Schonfeld, and A. Khokhar, “Robust null space representation and sampling for view invariant motion trajectory
analysis,” in Proc. of IEEE Int’l Conference on Computer Vision and Pattern Recognition, 2008.
(Ding08) H. Ding, G. Trajcevski, P. Scheuermann, X. Wang, and E. J. Keogh, “Querying and mining of time series data: experimental comparison
of representations and distance measures,” Proceedings of the VLDB Endowment, vol. 1, no. 2, pp. 1542–1552, 2008.
(Shieh08) Jin Shieh and Eamonn Keogh (2008). iSAX: Indexing and Mining Terabyte Sized Time Series. SIGKDD 2008.
(Piotto09) N. Piotto, N. Conci, and F. De Natale. Syntactic matching of trajectories for ambient intelligence applications. IEEE Transactions on
Multimedia, 11(7):1266–1275, Nov. 2009.
(Calderara09)S. Calderara, A. Prati, and R. Cucchiara. Learning people trajectories using semi-directional statistics. In Proceedings of IEEE
International Conference on Advanced Video and Signal Based Surveillance (IEEE AVSS 2009), Genova, Italy, Sept. 2009.
(Picciarelli08)Piciarelli, C.; Micheloni, C.; Foresti, G.L., "Trajectory-Based Anomalous Event Detection," Circuits and Systems for Video
Technology, IEEE Transactions on , vol.18, no.11, pp.1544-1554, Nov. 2008
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Available datasets of trajectories
Various time series (including trajectories):
http://www.cis.temple.edu/~latecki/TestData/TS_Koegh/
http://www.cs.ucr.edu/~eamonn/time_series_data/
Character Trajectories Data Set:
http://archive.ics.uci.edu/ml/datasets/Character+Trajectories
Pen-Based Recognition of Handwritten Digits Data Set:
http://archive.ics.uci.edu/ml/datasets/Pen-Based+Recognition+of+Handwritten+Digits
ETISEO project:
http://www-sop.inria.fr/orion/ETISEO/download.htm#video_data
Soccer player trajectories:
“T. D’Orazio, M.Leo, N. Mosca, P.Spagnolo, P.L.Mazzeo
A Semi-Automatic System for Ground Truth Generation of Soccer Video Sequences
In the Proceeding of the 6th IEEE International Conference on Advanced Video and Signal Surveillance,
Genoa, Italy September 2-4 2009”
Our own dataset:
More than 1000 trajectories of a video surveillance scenario (available at request)
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Trajectory analysis from two different perspectives
•
Trajectories are time series of data
•
Querying datasets of time series is a well studied data mining problem
which requires:
•
•
A similarity measure between two time series
•
A clustering technique to classify trajectories
In the database-related research the datasets are very large (VLDB) and
typically comprise reproducible phenomena (several repetitions of the
same class). Thus, similarity measure can be approximated but need
to be fast. Clustering can rely on very high number of samples of the
same class (simple 1NN clustering often suffices)
•
Viceversa, in video-surveillance research data availability is limited, very
diverse from time to time and full of noise. This lack of reproducibility
requires a precise measure, also at the cost of computational time. The
few data available per class also require more sophisticated clustering
approaches
•
Video surveillance scenarios also exhibit a high dinamicity which calls
for adaptive methods for classification
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Ding-Keogh 08 proposal
•The method proposed in (Ding-Keogh 08) perform the
comparison among time series in the original x-y data space.
Tj 

xk , j , y k , j
k  1...np

•The comparison is performed directly on the original points
sequences using dynamic programming and the Dynamic
Time Warping
• Inexact matching such as DTW are required to account for
different lengths in time series and for temporal shifts
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
(Ding08) Point-to-point Complete Original
•DTW algorithm
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
(Ding08) Point-to-point Complete Original
• Each point is compared using the Euclidean distance.
•Each dimension, namely x and y sequences are compared
separately
•The final distance is the weighted average of the
contributions of single dimensions.
•The Method is effective when comparing similar
sequences hence suitable when a large dataset is
available, thus suitable for querying VLDB
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Gullo09
Francesco Gullo, Giovanni Ponti, Andrea Tagarelli, Sergio Greco, A time
series representation model for accurate and fast similarity detection,
Pages 2998-3014, Pattern Recognition, vol. 42, 11, Nov. 2009
• Proposing a new representation of time series based on DSA (Derivative
time series Segment Approximation) as dimensionality reduction method
and DTW as similarity measure
• Clustering based on UPGMA (Unweighted Pair Group Method using
arithmetic Averages) and classification on KNN
• Comparison with several similarity measures (DTW, DDTW, LCSS, EDR,
etc.) and with several dimensionality reduction methods (SAX, DWT, FWT,
etc.). Comparison on 7 public datasets using F-measure
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Gaussian Model for spatial analysis
x
nj
, yn j

Sequence of 2D spatial coordinates
Tj 
 x2 , y2 
 x1 , y1 
 x
1, j
, y1, j  ,  x2, j , y2, j  ,

, xn j , j , yn j , j
Advantages of using spatial
coordinates:
•Embodies additional information about
velocity and acceleration
• Some paths are more common then
other depending on their position on the
scene
•Represent partially the reaction of people
to the structure of the scenario
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy

ImageLab
Modena
Gaussian Model for spatial analysis
Due to the uncertainties on the measure of points
coordinates we choose a Gaussian model to model
every point location
Bivariate Gaussian
Centered on point coordinate
having fixed variance.
N i , k  N ( x, y |  i , k ,  )
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Mapping Gaussians to Symbols
• A single trajectory is modeled as a sequence of point
Coordinates:
Tj 
 x
1, j
, y1, j  ,  x2, j , y2, j  ,

, xn j , j , yn j , j

• On each point a Spatial Gaussian pdf is fitted.
• Trajectory model is then represented as a sequence of
symbols .
T j  S1, j ,S 2, j ...., S n, j

Where Si , j  N ( x, y | i , j , )
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Clustering Trajectories
Positional Gaussian Clustering
Frequent and anomalous behaviors can be obtained by
clustering trajectories:
According to positions and detect the
most frequent activity zones
(Gaussian model)
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
On-line Trajectories Classification
•
Additionally trajectories can be classified
on-line and anomalous paths detected.
Normal
Clusters
Abnormal
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Morris-Trivedi survey on trajectory analysis
B. Morris and M. Trivedi, “A survey of vision-based trajectory learning and
analysis for surveillance,” IEEE Transactions on Circuits and Systems for
Video Technology, vol. 18, no. 8, pp. 1114–1127, Aug. 2008.
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Morris-Trivedi survey on trajectory analysis
B. Morris and M. Trivedi, “A survey of vision-based trajectory learning and
analysis for surveillance,” IEEE Transactions on Circuits and Systems for
Video Technology, vol. 18, no. 8, pp. 1114–1127, Aug. 2008.
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Morris-Trivedi survey on trajectory analysis
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Trajectory shape analysis
Trajectory shape analysis for “abnormal behavior” recognition in video surveillance.
Different context than VLDB: few and noisy data, high degree of variability,
tracking errors
Trajectory Shape similarity; invariant to space shifts
Not only space-based or time-based similarity
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Trajectory Shape Analysis by angles
x
nj
, yn j

Sequence of 2D spatial coordinates
Tj 
 x
1, j
, y1, j  ,  x2, j , y2, j  ,

, xn j , j , yn j , j
Sequence of 1D angles

T j  1, j , 2, j ,
,n j , j

 x2 , y2 
Advantages of using angles:
 x1 , y1 
• more compact representation
• invariant to spatial translations (both
i 1
i
local and global), thus describing
trajectory shape
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy

ImageLab
Modena
Imagelab Proposal
1.
Trajectory description with angle sequence
2.
Statistical representation with a Mixture of Von Mises
Distributions (MovM)

T j  1, j , 2, j ,
,n j , j

A. Prati, S. Calderara, R.
Cucchiara, "Using
Circular Statistics for
Trajectory Analysis"
in Proceedings of
CVPR 2008
Definition of EM
algorithm for MovM
3.
4.
5.
Coding with a sequence of selected vM pdf identifiers
Code Alignment
Using Dynamic
programming
Clustering with k-medoids
Definition of
Bhattacharyya
distance fon vM
and on-line EM
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Training set and on-line classification

T j  1, j ,  2, j ,
,n j , j

MovM(Tj)
EM for MoVM
<S={S1j..Snjj},MovM(Tj)>
Coding with
MAP
Alignement
Clustering
with Br
distance
Trajectory
repository
Trajectory
clusters
repository
Surveillance
system

T j  1, j ,  2, j ,
,n j , j
On-line EM
for MoVM
Normal/
abnormal
Classification
with Br
distance

Coding with
MAP
Alignement
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Von Mises distribution
• When the variables represent angles, Gaussians or
MoGs are inappropriate.
• Example: two observations at 1° and 359°.
Modeling these data with a univariate Gaussian
distribution is incorrect. In fact, if we select the
origin at 0°    180   179
if we select the origin at 180°    0   1
• Von Mises distribution is more suitable to treat
periodic variables, being circularly defined
V ( |  0 , m) 
1
e m cos( 0 )
2 I 0 (m)
I0 = modified zero-order Bessel function of the first
kind
1
I0  m  
2
2
m cos
e
d

0
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Mixture of von Mises and Mixture of Gaussians (MoG)
• MovM:
MoG:
K
p ( x )   k   x | μ k , Σ k 
K
p ( )   kV  |  0,k , mk 
k 1
k 1
1.4
1.2
m 1
0.8
0   2
0.6
1.2
9
0  
5
0  
1
m 1
1
0.3
 
0.5
0.6
 1
 
0.4
0.2
0
  0.5
0.8
m 1
0.4
9
 
5
  0.3
2
0.2
0
1
1  0.2
2
3
2  0.5
4
5
3  0.3
6
7
0
0
1
2
1  0.2
3
4
2  0.5
5
6
3  0.3
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
7
ImageLab
Modena
Modelling a single trajectory
1)A single trajectory is modeled as a sequence of
angles:
T j  1, j , 2, j , , n , j 
j
2) A specifically defined EM algorithm is used:
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
EM for MovM distribution
• MovM:
• Likelihood of complete data set:
• Expected value of the log likelihood:
• E-step: estimate of the responsabilities:
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
EM for MovM distribution
• M-step: maximizing wrt  k :
• M-step: maximizing wrt 0,k :
• M-step: maximizing wrt
mk
:
function zeros found by inverted numerically
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Mapping angles to symbols
2) A single trajectory is modeled as a sequence of angles
• and after having defined the MoVM
• as a sequence of symbols:


T j  1, j , 2, j ,

, n j , j  T j  S1, j , S2, j ,
, Sn j , j

Si , j  arg max p i , j | 0,r , mr 
r 1,
,K
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Distance for sequences
• We transform a comparison between two
sequences of either angles or coordinates in the
comparison between two sequences of symbols,
with each symbol corresponding to the proper
probability distribution
• However, due to acquisition noise, uncertainty and
spatial/temporal shifts, exact matching between
sequences is unsuitable for computing similarity
• We use global alignment between two sequences,
basing the distance as a cost of the best alignment
of the symbols
• Dynamic programming techniques are used to
speed up the process.
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Global alignment
• Global vs local alignment
• Using global alignment instead of local
one is preferable because the former
preserves both global and local shape
characteristics
• Dynamic programming is used to reduce
computational time to O (ni · nj), where
ni and nj are the lengths of the two
sequences.
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Inexact matching
• Since the symbols we are comparing correspond to
pdf, match/mismatch should be proportional to the
distance between the two corresponding pdfs
• Need to evaluate distance between two pdfs:
Angular: Von Mises Distributions V ( |  0,a , ma ) V ( | 0,b , mb )
• Bhattacharyya distance bw pdfs (closed
form)

1
d B  1  
I0
 I 0 (ma ) I 0 (mb )



ma2  mb2  2ma mb cos (0,a  0,b ) 

Spatial: Gaussians Distributions N ( x, y |  a ,k ,  a ) N ( x, y | b ,m ,  b )
• Bhattacharyya distance bw pdfs (  a  b)
1
d B  (  a  b )T  1 (  a  b )
8
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Sequence similarity
where cB is the Bhattacharyya
coefficient
• The best alignment is then converted in
a distance and used for clustering and
testing
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Comparison of alignment techniques
• When the sequences
are characterized by different lengths, DTW
tries to stretch the two sequences in order to find the optimal
time warping path with the consequence of eventually adding
additional matches.
• Global alignment (based on Needleman-Wunsch algorithm), on
the other hand, simply adds gaps to align the sequences
leading to the advantage of being more susceptible to slight
time series’ changes by controlling the gap cost value
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Comparison of alignment techniques
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Clustering trajectories
•
•
•
The distance is used to cluster the trajectories in the training
set either according their shape or they location
k-medoids algorithm: prototype of the cluster is the element
that minimizes the sum of intra-class distances
To compute the best number of k clusters, iterative kmedoids:
•
initialization: i = 0, k(0) = Nt (cardinality training set);
each trajectory is chosen as medoid) of the cluster
•
Step 1: Run k-medoids algorithm with k(i) clusters
•
Step 2: If there are two medoids with a similarity
greater than a threshold Th, merge them and set k(i+1)
= k(i)−1. Increment i and go back to step 1.
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Experimental Result
•
We report results on a corpus of 3000 trajectories with
an average length of 100 points
•
We compare our method with the baseline off-line
time sequence comparison method of [Keog02]
Method
Classification
Accuracy
Normal Abnormal
Accuracy
Online VM + GA
96%
97%
Gaussian + Online
GA
93%
97%
[Keog02] on complete
trajectory
85%
87%
E. Keogh., “Exact indexing
of dynamic time warping,” in
28th International
Conference on Very Large
Data Bases. Hong Kong,
2002, pp. 406–417
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Comparison between VS and VLDB approaches
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Comparison between VS and VLDB approaches
•
Results on synthetic dataset
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Comparison between VS and VLDB approaches
•
Results on real dataset
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Adding the speed
Pure trajectory shape is not sufficiently always discriminative in
surveillance scenarios:

the same path covered by a walk or by a run has a different
meaning in terms of behavior
Add the speed to the shape description to provide a more
complete analysis of the trajectory.
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Trajectory encoding
•
•
•
For each couple of subsequent
point the angle θ and the velocity
vector module ρ are computed
For each couple of parameters
(θi, ρi) the encoding is performed
using a polar scheme
Velocity module is used to
choose the ring and the direction
is used to choose the sector
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Alignment score for trajectory comparison
After the polar encoding a trajectory Ti is then represented as a sequence of literals
S={si,1,si,2,si,3…}
We define a suitable score to compare people trajectories given two simbols sp,i and sq,j and
the corresponding codes ca1,b1 and ca2,b2
The matching score λi,j is finally normalized to 1 and the similarity metric ξi,j is computed
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Experiments
We log for training 88 trajectories from the multicamera system at
our campus during ordinary working days
We collect 121 trajectories for testing purposes being labeled
manually by an expert as belonging to one of the 12 clusters
previously computed
The classification rate is 74%. Most of errors are due to two main
factors:


First: lack of data in the training set
Second: inherent difficulties for the expert to answer the
question “Which is the most similar trajectory in the direction
and the velocity domain? ”
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Experiments
Error example:
S. Calderara, R. Cucchiara, A. Prati, "A Dynamic Programming
Technique for Classifying Trajectories" in Proceedings of IEEE
International Conference on Image Analysis and Processing (IEEE
ICIAP 2007), Modena, Italy, pp. 137-142, Sept. 10-14, 2007
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Trajectory modeling
Use of semi-directional statistics to jointly model
linear (speed) and circular (direction) data
Estimation of precision m in Von Mises pdf is
troublesome
Using a approximated wrapped Gaussian pdf is
preferable:


Similar treatment of its linear counterpart
a linear approximation of the variance parameter even
for circular variables: Gaussian MLE to compute the
joint multivariate covariance matrix
1
AWG ( |  0 ,  ) 
e
2 
  0  mod 2 

2
2 2
46
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Checking independence
since directions and speed are dependent:
K
p  , v   MoAWLG  X | π, μ, Σ     k AWLG  X | k ,  k 
k 1
AWLG  X |  ,   
 
X  
v 
  ,

 v,
1
2 
e

1
 X   T 1  X   
2
  ,v 
 v,v 
  0  mod 2 
X   

v

v
0


Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
State of the Art approaches
We choose to test our MoAWLG method against
two state of the art approaches:
•Point-to-point, Complete, Original: (DingKeogh08) (same as before, but with also speed)
•Point-to-point, Selected, Transformed: (Piotto09)
H. Ding, G. Trajcevski, P.
Scheuermann, X. Wang,
and E. J. Keogh,
“Querying and mining
of time series data:
experimental
comparison of
representations and
distance measures,”
Proceedings of the VLDB
Endowment, vol. 1, no.
2, pp. 1542–1552, 2008.
N. Piotto, N. Conci, and F. De
Natale. Syntactic
matching of trajectories
for ambient intelligence
applications. IEEE
Transactions on
Multimedia,
11(7):1266–1275, Nov.
2009.
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
(Piotto09) Point-to-point Selected Quantized
• The method proposed in (Piotto 09) perform the comparison
among selected quantize representations of the original
position-speed dataspace.
•Characteristic points of the sequences (breakpoints) are
extracted:
•Temporal Breakpoints: consecutive points in a small area
are represented by a single point associated with the time
interval the objects stays in its position
•Spatial Breakpoints: sudden(a) or slow
curvature changes(b) are selected
as representative points of the trajectory.
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
(Piotto09) Point-to-point Selected Quantized (2)
• Once the breakpoints B are computed two consecutive
breakpoints identifies a segment.
•Every segment is then associated to a symbol
Where :
S m  ( m , vm , tm )
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
(Piotto09) Point-to-point Selected Quantized (3)
• Every Symbols’ values are quantized and associated to literals:
•Directions are quantized not uniformly
•Speed and time are quantized in
fixed intervals
•Symbols’ sequences are aligned using
Global Alignment separately for every
dimension (direction,speed,time) and the
final similarity score is a weighted sum of
partial scores.
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Experimental comparison
• We compare our AWLG method with the approaches in (Ding08) and (Piotto09) on a dataset
of about 500 trajectories manually ground truthed and divided in clusters
•We perform 4 tests:
•T1 and T2: ordinary days acquired trajectories
•T3: Actor played straight trajectories
•T4: T3 Trajectories at different speeds.
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Experimental comparison
• Clustering accuracy was measured using the same K-medoids based clustering on distance
matrices computed with the different methods described
Test ID
Number of
Trajectories
(Ding08)
(Piotto09)
Our
Approach
T1
140
78%
73%
95%
T2
108
80%
87%
99%
T3
145
94%
86%
96%
T4
100
90%
80%
97%
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Conclusions
Trajectory analysis is one of the most powerful task to compare
movements of people
many and many different proposals
for large datasets of long trajectories typical data series
comparisons point to point and complete could be preferable
With smaller and noisy dataset statistical methods could be the
best ones
With MoG for spatial representation
With MoVM for shape representation only
With MoAWLG for shape and speed representation
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
Multiple camera and distributed tracking
Multi-camera
tracking with camera with
overlapping FOVs:
Distributed
Tracking with camera without
overlapping FOVs:
Use calibration
and 3D geometry
Improve with Probabilistic
Association
Search for similarity
Content based retrieval methods
Global descriptors: Histograms
texture.Medioni’s circular histograms,
Mixture of gaussians…
..
S. Calderara, R.Cucchiara,
A. Prati Multimedia
Surveillance: Content based
Retrieval with
Multicamera People Tracking
Proc of VSSN 2006
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy
ImageLab
Modena
For any other information
http://Imagelab.ing.unimore.it
Rita Cucchiara
Dipartimento di Ingegenria
dell’Informazione
+390592056136
[email protected]
Thanks to Imagelab
Andrea Prati, Roberto Vezzani, Costantino
Grana, Simone Calderara, Giovanni Gualdi,
Paolo Piccinini, Paolo Santinelli, Daniele
Borghesani, Davide Baltieri, Sara Chiossi,
Rudy Melli, Emanuele Perini, Giuliano
Pistoni..
Rita Cucchiara - Università di Modena e
Reggio Emilia, Italy