Simultaneous Clustering and Tracking Unknown Number of Objects
Katsuhiko Ishiguro, Takeshi Yamada and Naonori Ueda
NTT Communication Science Laboratories
Kyoto, 619-0237, Japan{ishiguro, yamada, ueda}@cslab.kecl.ntt.co.jp

Abstract
In this paper, we present a novel on-line probabilistic
generative model that simultaneously deals with both theclustering and the tracking of an unknown number of moving objects. The proposed model assumes that i) time series
data are composed of a time-varying number of objects andthat ii) each object is governed by a mixture of an unknown
number of different patterns of dynamics. The problem oflearning patterns of dynamics is formulated as the clustering of tracked objects based on a nonparametric Bayesianmodel with conjugate priors, and this clustering in turn improves the tracking. We present a particle ﬁlter for posterior estimation of simultaneous clustering and tracking.
Through experiments with synthetic and real movie data, we
conﬁrmed that the proposed model successfully learned thehidden cluster patterns and obtained better tracking results
than conventional models without clustering.

Figure 1. Example of system input and output. Left ﬁgure shows
snapshot of a movie given to system as input. Right ﬁgure shows
output snapshot obtained from the system, where different coloredrectangles represent targets’ ID and positions and the numbers on
the rectangles denote dynamics pattern indices.

each target object to use multiple different patterns of dynamics. However, to construct such a model we need tosolve the following new problems: i) we do not know thenumber of patterns in the time series data, and ii) we do notknow the speciﬁcation of each dynamics. The ﬁrst problem
can be understood as time series clustering [9, 10, 12], andthe second is the estimation of the model parameters [2, 3].
If we know these patterns of dynamics in advance, thenwe can apply a conventional tracking algorithm. However,identifying these patterns is difﬁcult without ﬁrst segregating mixed indistinguishable target objects into target-wisetrajectory data with a tracking algorithm. Unfortunately
these algorithms assume that time series data are segregatedby objects. It is a chicken-and-egg problem.
This paper proposes a probabilistic generative model thatsimultaneously enables both clustering patterns of dynamics and the tracking of unknown numbers of objects. We
assume that time series data are generated from the hidden trajectories of target objects, each of which is governedby an unknown number of different dynamics parameters.
We incorporate the Dirichlet Process Mixture (DPM) to aprobabilistic multi-target tracking model to perform clustering and estimate an unknown number of Kalman ﬁlter
parameters, and this clustering in turn improves tracking
accuracies. A Particle ﬁlter approach is employed to makeon-line (incremental) inferences of latent variables and hid-

1. Introduction
Tracking multiple objects in movie images is an important task [6, 8]. Tracking algorithms compute ﬁlteredsmooth trajectories of objects from scenes, by ﬁtting statespace dynamics models such as Kalman ﬁlters to the observations. Tracking anonymous data such as maneuver tracking on radar (i.e., we cannot directly distinguish objects
from observations) [7, 11] is challenging and is mainly formalized in statistical and probabilistic manners and applied
to many types of time series data including movie data.
If many target objects are moving in a scene, it is natural to assume multiple different dynamics based on theircharacteristics. Many existing multi-target tracking models,
however, fail to address the problem of estimating multiple
patterns of dynamics in tracking problems. They assume
that whole trajectories of different objects can be modeledby a single general dynamics model, even though obviously
target-wise tuning of dynamics provides better prediction
and understanding of time series data.
We consider a multi-target tracking model that allows
1

978-1-4244-2243-2/08/$25.00 ©2008 IEEEden states. Experiments using synthetic and real-world data
show the effectiveness of the proposed model comparedwith conventional models.

2. Generative Models
Figure 2 shows the graphical models of those previously
studied in the literature and our new proposal. These graphical models represent dependencies between random variables and explain how the data are generated from the process characterized by these variables. In our model, data
to be generated include hidden state x(t), which is a realvalued vector consisting of the actual coordinates of the
tracked object, and observation y(t), which is a sensed signal that is possibly collapsed by observation noises.

2.1. Conventional Models
First, we describe the simple multi-target tracking model
proposed by Särkkä et al. [11] in Fig. 2(a). Since we havemultiple targets, the hidden state of the ith target object isdenoted as xi (t). We represent this by depicting a “plate”
around xi (t). Analogously, this model produces multiple
observations ym (t) indexed by m. Nt and Mt are the number of objects and observations at time t, respectively.
When we have multiple target objects (hidden states) andobservations, we have to solve the correspondence between
targets and observations, since we don’t know which target
object generates which observation. This problem, whichis called data association, is essential to correctly estimate
the target-wise hidden state. This model introduces two
kinds of latent variables, c and j, to solve the data association problem. ci (t) represents the birth (addition) anddeath (deletion) of target object i and thus explains how
many target objects appear and disappear. With ci (t) = 1,
the ith object is alive (or visible in the scene) at time t, andci (t) = 0 means the target object is now outside the scene.
If a new target object is generated at time t, then new index î is produced and cî (t) = 1. jm (t) is the data association variable that associates ym (t) with its source target
xi (t). If jm (t) = i, then ith target object xi (t) generates
mth observation ym (t). For the inference of such latentvariables and hidden states, the Rao-Blackwellized Particle
ﬁlter is employed. Note that dynamics parameters ξ and ψ
are ﬁxed constants (depicted as squares) in this model. Thisimplies that the whole time series data are governed by one
ﬁxed dynamics. As discussed in the previous section, thisassumption is not always relevant.
The model illustrated in Fig. 2(b) [2] represents the situation where one target object produces its trajectory andemits observations while occasionally changing its dynamics. In contrast to the model proposed by Särkkä et al., wehave a set of parameters {ξk }, {ψk } indexed by k. x(t)(y(t)) is generated from the noise distribution parameter-

ized by ξk (ψk ). At each time step t, zt = k is sampled as anindex of the dynamics patterns, and corresponding dynamics parameters ξk and ψk are used to generate the hidden
states and the observations.
The novelty of their work lies in introducing the Dirichlet Process Mixture (DPM) to model these two noise distributions. DPM is a ﬂexible Bayesian nonparametric modelthat can be seen as an inﬁnite mixture of distributions. By
introducing DPM, the model can infer not only the speciﬁcation of dynamics parameters but also the number of
mixture components. Therefore, the system can track without explicitly specifying the number of mixture components(parameters) and their characteristics. As the inference algorithm the authors present a MCMC technique for off-line
inference and a Particle ﬁlter approach for on-line inference.
One major drawback of this model is that it cannot handle
time series data that consist of multiple objects. The timeseries must be segregated by the target objects in advancebecause the model cannot solve the data association problem.
To summarize, these two most recent models are not applicable to a time series that consists of the trajectories ofmultiple target objects that occasionally change their dynamics by switching between a pool of dynamics. In thenext subsection, we propose a new model that features theadvantages of both models.

2.2. Our Proposed ModelIn this subsection, we ﬁrst outline our proposed model
before discussing the details in a later section. Fig. 2(c) is
the graphical model of our proposed model that is designed
to represent the multi-target tracking data generated froma mixture of dynamics parameters. Following the multitarget tracking model (Fig. 2(a)), the hidden state of object
i is denoted as xi (t) and the mth observation is ym (t).
To generate xi (t), ﬁrst the model generates ci (t), which
denotes the birth (addition) and death (deletion) of target
objects as explained earlier. We model the process of target
additions and deletions by Bernoulli trials (Eq. (7)). We
can produce a time-varying number of object trajectories bycontrolling c(t). Next zi (t) is generated as an index of the
dynamics that governs the ith target at time t by following
Caron et al.’s model (Fig. 2(b)). Sampling zi (t) (Eq. (5))
is modeled by the Chinese Restaurant Process [1, 5] withconcentration parameter γ, combined with a Bernoulli trial
parametrized by π. CRP is a realization of DPM suitablefor clustering and can model multiple patterns (clusters) ofdynamics without ﬁxing the number of dynamics patterns.
For each pattern k, dynamics parameters ξk and ψk are
generated from base distribution G0 and H0 , respectively.
In our model, we use a Kalman ﬁlter as the state-spacemodel, and ξk and ψk are their normal distribution parameters. We assume that G0 and H0 are both Normal Inverse

Pb

Pb

Pd

γ

π

c (t)

c (t-1)

Pd

γ

i

π

i

c (t-1)c (t)iz (t-1)z (t)z (t-1)z (t)x (t-1)x (t)x(t-1)x (t)x (t-1)

x (t)

i

i

i

i

i

i

i

i = 1, ..., Nt

i = 1, ..., Nt

ξ

G0

ξ

H0

ψ

y (t-1)m

j (t-1)

ξ

ψ

H0

ψ

k

y (t-1)y (t)ky (t-1)y (t)j (t-1)

j (t)

m

j (t)

m

k

k = 1, ...,

k = 1, ...,

y (t)

m

k

G0

m

m

m = 1, ..., Mtmm

m = 1, ..., Mt

(a)

(b)

(c)

Figure 2. Graphical models of three generative models described in this paper. Circle nodes represent random variables, and squares denote
ﬁxed parameters. White nodes are latent variables, and shaded nodes are observables. Rectangles (“plates”) denote replication, with theindex given in rectangle’s bottom. (a): model proposed in [11], (b): model proposed in [2] and (c): proposed model.

Wishart distributions (NIW) with parameters θξ and θψ respectively. Now we generate each of the latent variables
required to produce xi (t). The hidden state of ith object
xi (t) is produced if the object is in scene (ci (t) = 1), andthe generation process is governed by ξk that is designatedby zi (t) = k.
To generate observation ym (t), we ﬁrst produce latent
data association variable jm (t) (Eq. (5)). As stated abovejm (t) holds the association information between xi (t) andym (t). If jm (t) = i then mth observation ym (t) is generated from ith target object xi (t) with target observation
parameter ψk . Iterating this process for all t, we have timeseries data consisting of multiple target trajectories, each ofwhich is governed by multiple different dynamics.

3. Inference
In this section, we discuss the on-line clusteringand dynamics parameter learning schemes and how toinfer them.
Note that we represent the whole setof the variables from time step 1 to t by capitals:
e.g. X(t) = {x(1), x(2), . . . , x(t)} and Y (t) ={y(1), y(2), . . . , y(t)}.

3.1. Posterior Estimation with Particle Filter
Our objective is to estimate posterior distributionp (x(t)|Yt ). We write the set of latent variables at time stept as φ(t) = {{ci (t)}, {jm (t)}, {zi (t)}, {ξk (t)}, {ψk (t)}},and Φ(t) = {φ(1), φ(2), . . . , φ(t)}.
Using these notations, we approximate the posteriorp (x(t)|Y (t)) with Particle ﬁlter technique as follows:p (x(t)|Y (t)) =S()∑
p x(t), Φ(t)(s) |Y (t) w(t)(s) , (1)s=1where S denotes the number of particles. Let q(·) be theproposal distribution that generates Φ(t)(s) as follows:φ(t)(s) ∼ q (φ(t)|Φ(t−1), Y (t)) .

(2)

For the choice of the proposal distribution, we may simply use p (φ(t)|Φ(t−1)) instead of q (φ(t)|Φ(t−1), Y (t)).
Each particle is weighted by w(t)(s) deﬁned by:)) (y(t)|φ(t)(s) p φ(t)(s) |Φ(t−1)).
w(t) = w(t−1)
q (φ(t)|Φ(t−1), Y (t))(3)()
For likelihood p y(t)|φ(t)(s) , we use Kalman likelihood, as in [11]. Because we model p (x(t), Φ(t)|Y (t))
by Kalman ﬁlter following previous researches [7,11], we can easily compute hidden state distributionp (x(t), Φ(t)|Y (t)) in Eq. (1), after obtaining the latentvariable samples.
Based on the generative model (Fig. 2(c)), we decom(s)

(s) p

(

pose conditional distribution p (φ(t)|Φ(t−1)) as follows:p (φ(t)|Φ(t−1)) , p (c(t)|C(t−1), Pb , Pd )∏∏p (jm (t)|J(t−1))
p (zi (t)|Z(t−1), γ, π)
×
m

(4)
(5)

i

) (
)
∏ (
×
p ξk (t)|θkξ (t−1) p ψk (t)|θkψ (t−1)(6)

k3.2. “Birth and Death” Variable
The right term in Eq. (4) is the conditional prior of c(t),which denotes the birth (addition) and death (deletion) oftarget objects. With ci (t) = 1, the ith object is alive (or in
the scene) at time t, and ci (t) = 0 means the target object
is now outside the scene. In [11], the time evolution of
C is formalized as two-step Bernoulli trials: i) an existing
object with ci (t−1) = 1 disappears and ci (t) = 0 withprobability Pd , otherwise ci (t) = 1, ii) a new target object
is generated in the scene with probability Pb . We limit the
number of newly born objects at every time step to 1 (as in[11]), giving us the following:p (c(t)|C(t−1), Pb , Pd ) = Pd nd (1−Pd )ns Pb nb (1−Pb )1−nb ,(7)where ns denotes the number of surviving target objects, nd
is the number of that disappeared, and the (nb = {0, 1}) isthe number of newly born objects.

3.3. Data Association Variable
For data association variable J, p (jm (t) | J(t − 1)) inthe ﬁrst term of Eq. (5) is assumed as uniform among all
existing objects. Otherwise, if search space of J is large,
we can introduce a pseudo likelihood to the proposal to reject the outliers. In this experiment, we use the following
distribution for the proposal of j similar to [11]:q (jm (t) = i|J(t−1), ym (t))∝ p (ym (t)|x̂i (t)) p (jm (t) = i|J(t−1)) . (8)This equation incorporates observation likelihoods given a“representative” state vector x̂i (t), which is the average ofthe predictive distribution of xi (t).

3.4. Dynamics Cluster Index Variable
We adopt the Chinese Restaurant Process (CRP) [1] prior
to generate z(t) in the second term of Eq. (5). CRP is arealization of Dirichlet Process Mixture (DPM), which is afamily of nonparametric Bayes, and is a distribution overpartitions. We have a set of mixture components or clusters
indexed by k, and write the cluster index of ith sample aszi . The distribution over index of ith sample conditioned on

the indices z1:i−1 isp (zi = k|z1:i−1 ) ={mk
if k is an existing cluster with mk > 0
i−1+γ
,
γ
if k is a new cluster
i−1+γ

(9)

where mk denotes the size of the kth cluster. We write
this sampling procedure as zi ∼ CRP (γ). CPR favors asmall number of clusters that can be easily understood from
Eq. (9) and is consistent with the intuition of clustering. Estimating the posterior distribution of z(t) can be achieved
straightforwardly by combining the prior provided by CRP
and an appropriately selected data likelihood.
In our model, Eq. (9) is updated to obtain the best clustering estimate at every time step. Using Z(t−1) as priorinformation, we write the sampling of zi (t) as follows:p (zi (t) = k|Z(t−1), γ) ={ m (t−1)k|Z(t−1)|+γγ|Z(t−1)|+γ

if mk (t−1) > 0
if mk (t−1) = 0

,

(10)

where mk (t−1) is the total population size (the number ofi s.t. zi (t) = k) of kth cluster up to the time step t − 1, and|Z(t−1)| denotes the sum of total population among all theclusters up to the time step t − 1: i.e., it equals the sum ofmk (t−1) for all k.
In addition, we introduce another parameter π in orderto improve performance. We assume that the changes ofdynamics happen only occasionally and thus the target object switches its dynamics parameters with relatively small
probability π. Now we formulate the second term of Eq. (5)as follows:zi (t) ∼ CRP (Z(t−1), γ)

with probability πzi (t) = zi (t−1) with probability 1−π

(11)
(12)

3.5. Kalman Filter Parameters
In our model, we use linear Gaussian state-space models, namely Kalman ﬁlters, for the dynamics models. If thehidden state of ith object xi (t) and mth observation ym (t)are generated from the kth dynamics cluster (i.e. jm (t) = i
and zi (t) = k), we have the following state-space model
equations:xi (t) = f (xi (t−1), ξk (t)) ,ym (t) = h (xi (t), ψk (t)) ,ξk (t) = {q, Q}(13)ψk (t) = {r, R}.

(14)f and h are standard linear Gaussian models with normal
distribution noise. ξk (t) = {q, Q} is the mean and covariance matrix for the system model noise and ψk (t) = {r, R}
is for observation noise. To estimate these parameters, we
introduce Normal Inverse Wishart distribution (NIW) as a

Table 1. Tested methods and their characteristics

methodSingleIndividual
ClusteredEqs. (17), (18)
no
yes
yes

Eqs. (10), (11), (12)
no
no
yes

prior distribution of the parameters (c.f. [2]). We assign
NIW for each cluster, for the system noise and the observation noise, respectively. We parameterize the system noise
NIW and the observation noise NIW by θk = {θkξ , θkψ }.
ξk (t) and ψk (t) are sampled from the posterior distribution given the data up to time t−1 as current estimates of thetrue dynamics parameter ξk and ψk . The sampling distributions and their hyper parameters θk are also updated according to the data: θk (t−1) = {θkξ (t−1), θkψ (t−1)}. Components in Eq. (6) will be described as follows:()()
p ξk (t)|θkξ (t−1) = NIW ξk (t); θkξ (t−1)
(15)
(
)
(
)
p ψk (t)|θkψ (t−1) = NIW ψk (t); θkψ (t−1) . (16)Figure 3. Example of synthetic movie data. Left: snapshot of observations. Each point denotes one observation. Right: groundtruth data. Colored points are target objects, and white are noise
data.

Using sampled ξk (t) and ψk (t), we perform tracking.
For on-line estimation, we update hyper parameters θ toobtain better predictions of ξ and ψ after tracking. These
updates can be analytically performed because of the conjugacy:()()
NIW ξk ; θkξ (t) ∝ p (x(t)|ξk ) NIW ξk ; θkξ (t−1) .
(17) )()(
ψψ
NIW ψk ; θk (t) ∝ p (y(t)|ψk , x(t)) NIW ψk ; θk (t−1) .
(18)
Updated hyper parameters θ(t) will be used in Eqs.(15) and(16) in the next time step.

(Eqs. (17) and (18)), but without clustering on zi (t). Thismodel represents more complicated time series data thanthe ﬁrst model by modeling each target object with its own
dynamics parameters: state trajectories of multiple objects
are governed by the multiple patterns of dynamics.
Finally, the proposed model (Clustered) is tested, which
has clustered dynamics and hyper parameter adaptations.
Compared to the second model, this model assumes a number of patterns in dynamics shared among multiple objects
and also that the dynamics of an object may change temporarily.

4. Experiments
We tested the proposed model with both artiﬁcially generated data and real movie data.

4.1. Compared Models
We compared the proposed model with the other two
more restricted models with fewer latent variables and evaluated their effect. In experiments we compared the threemodels summarized in Table 1. The ﬁrst model (labeled
as Single in Table 1) is a baseline that closely resembles
Särkkä et al.’s model [11] in Fig. 2(a). This model does
not update the dynamics hyper parameters θξ (t) and θψ (t)in Eqs. (17) and (18), nor select and generate clusters with
CRP (Eqs. (10), (11) and (12)): all ξ(t) and ψ(t) are always
sampled from single default hyper parameters θ(0).
The second model (Individual) learns hyper parameter θ(t) incrementally as described in the previous section

Table 2. Noise parameters used in generation of synthetic data

I
II
III
IV

q
{3.0, 0.0}T{−3.0, 0.0}T{0.0, 3.0}T{0.0, −10.0}TQ
diag{1.0, 1.0}diag{1.5, 1.5}diag{0.5, 0.5}diag{1.0, 1.0}Rdiag{1.0, 3.0}diag{1.0, 2.0}diag{2.0, 2.0}diag{0.5, 3.5}

4.2. Synthetic Data Experiment
We consider tracking and clustering moving mass points
in a [0 : 200] × [0 : 200] virtual 2D space. The hidden statesof the target objects are the 2D real-valued vectors representing the coordinates of the objects. The observations arealso 2D real-valued vectors and the collapsed coordinatesof the mass points. The observations include outputs froma “noise target”, which is a false target. Each target object
obeys the following random walk model:xi (t) = xi (t−1) + v(t),yi (t) = xi (t) + w(t),v(t) ∼ N (q, Q)
w(t) ∼ N (r, R) .

(19)
(20)

where N (·) denotes the normal distribution. In this experiment, each object alters its dynamics by changing the noise
parameters selected among four patterns, which we present
in Table 2. In all patterns, r is the zero vector.
The initial hyper parameters of NIW distribution θ(0)are selected so that the average of ξk (t) and ψk (t) takes thefollowing values: q = 0, Q = diag{10.0, 10.0}, r = 0,

Table 3. Time step wise average of data log-likelihood for synthetic data and real movie data

π
0.1
0.2
0.5
1.0

MethodSingleIndividual
Clusteredsynthetic−115.22−107.85−96.68−96.37−103.66−110.31real 1−95.62−84.21−79.71−80.93−82.96−83.93

real 2−54.54−51.94−50.30−50.74−51.86−52.13eters.

4.3. Real Movie Data Experiment
Next we describe two experiments using two real movie
data. The task was to perform clustering and tracking
feature points emitted from pedestrians in movie frames
recorded by a common digital camera.

4
2

Y

0
-2

Figure 5. Snapshots from the movie data used in the real movie
data experiments. (a): used for the ﬁrst experiment. (b): used forthe second experiment.

Ground Truth
Clst 0 Size 27
Clst 1 Size 387
Clst 2 Size 420
Clst 3 Size 107
Clst 4 Size 68
Clst 5 Size 532
Clst 6 Size 26
Clst 7 Size 0

-4
-6
-8
-10
-4

-2

0

X

2

4

Figure 4. Plot of mean values of system noise distribution

R = diag{5.0, 5.0}. The length of the time series data is
300 steps. The number of particles is S = 300, and the CRP
concentration parameter is set to γ = 2. At every time step,a new object is born with the probability of Pb = 0.1. Eachexisting object (ci (t−1) = 1) is deleted based on Eq. (21)with λ = 0.1. Let tn be the last time step when at least
one observation ym exists such that jm (·) = i. Then theprobability of the object deletion Pd is deﬁned as follows:
Pd = 1−λet−tn .

(21)

Now we analyze the results. The averaged data likelihood at each time step is shown in the third column of Table 3. This value measures how likely the obtained latentvariables (namely, a model) generates the observed data.
The table shows that dynamics parameter estimation and its
clustering improve the log likelihood. This means our proposed model successfully ﬁnds better models and parameters through on-line tracking and clustering.
Next we present the distribution of q in Fig. 4 at the lasttime step (π = 0.2). q represents the averaged bias of thetarget velocities. The analyzed data has four patterns in q,
as discussed earlier. Each plot corresponds to a dynamics
cluster, and the number of “size” is the data size of eachcluster: how many times the objects selected this dynamics. Four dominant clusters acquire values nearly equal tothe designed ground truth. Namely, our model successfully
clustered the dynamics patterns and estimated their param-

The movie data of the ﬁrst real data experiment wasrecorded at a shopping mall corridor (Fig. 5 (a)). The camera was placed almost right above the pedestrians. The sizeof each frame is 320 × 240 pixels. Basically, pedestrians
move in vertical directions (upward or downward), and occasionally make turnarounds to enter shops.
Target feature points were extracted as follows. First,
the background subtraction was performed on all frames.
Second, pixels were binarized with thresholds to extract theforeground pixels. Then, we extracted the black-coloredpixels and performed mean shift clustering on them at eachframe. Finally, obtained means were used as the observed
feature points. On average, each pedestrian corresponds to
one to three feature points at each frame.
In this experiment we utilized a color model [8] for dataassociation prior (Eq. (5)) instead of uniform distribution.
We computed an 8-bit RGB histogram around the featurepoint. Data association prior was computed based on the
Bhattacharya coefﬁcient between the histogram around thefeature point and the object’s histogram obtained at the previous time step.
The state-space model is identical with the previous synthetic data experiment. The initial hyper parameters of
NIW distribution θ(0) are selected so that the average ofξk (t) and ψk (t) takes the following values: q = 0, Q =diag{20.0, 20.0}, r = 0 and R = diag{20.0, 20.0}. The
length of the time series data is 200 steps. 200 frames are
extracted from 1000 frames of 30 FPS-captured movie data.
The number of particles is S = 500, and CRP concentration parameter is set to γ = 0.1. The target birth probability
Pb = 0.1 and target death probability Pd is calculated by
Eq. (21) with λ = 0.1.
The second real movie data is a crowded walkway scene(Fig. 5 (b)). The size of each frame is 640 × 480 pixels.

8

4
Clst 0 Size 508
Clst 1 Size 1196

6

2

4

1

2

Height

Width

3

0
-1

0

-4

-3

-6

-3

-2

-1

0

1

2

3

4

-8

Upward-10

As in Fig. 5 (b), the viewpoint was set in lower angle ofelevation, and occlusions were observed frequently. We observe that there are roughly three patterns in the movementsof pedestrians: upward, downward and right-to-left movements. Each of three patterns may be divided into subpatterns, reﬂecting different crash avoidance behaviors in thecrowded area.
Target feature points were extracted by employing HoGbased human shape detector [4]. We processed all the captured frames with the detector program provided by the authors. Obtained coordinates of the possible human locations
are input to the tracking systems.
The state-space model is identical with the previous experiments. The initial hyper parameters of NIW distribution θ(0) are selected so that the average of ξk (t) and ψk (t)takes the following values: q = 0, Q = diag{25.0, 25.0},
r = 0 and R = diag{10.0, 10.0}. The length of the timeseries data is 300 steps that are extracted from 600 framesof 15 FPS-captured movie data. The number of particles
is S = 1000, and CRP concentration parameter is set toγ = 1.0. The target birth probability Pb = 0.1 and target
death probability Pd is calculated by Eq. (21) with λ = 0.1.
The two rightmost columns of Table 3 show the averaged
data likelihood for the real movie data experiments. As thesynthetic data experiment, our proposed model successfully
improved the data log likelihood.
Next we present the distribution of q in Fig. 6 for theﬁrst real movie data, and Fig. 7 for the second real movie
data, respectively (π = 0.1). Since these experiments aredone on real-world data, we do not have the ground truth of
the number and the speciﬁcations of the dynamics. For theﬁrst experiment (Fig. 6), we observe that the obtained two
dynamics clusters are well matched to the expected result.
For the second experiment (Fig. 7), the system generated
two clusters for each of three directions (upward, downward
and right-to-left). This result well matches to the expected
result: i.e. we have roughly three dynamics patterns and

-5

0

5

10

Width

HeightFigure 6. Plot of mean values of system noise distribution at thelast frame of the ﬁrst real movie data experiment

Clst 0 Size 540
Clst 1 Size 225
Clst 2 Size 96
Clst 3 Size 472
Clst 4 Size 259
Clst 5 Size 82
Clst 6 Size 1
Clst 7 Size 10

-2

-2

-4
-4

Downward

Right-to-Left

Figure 7. Plot of mean values of system noise distribution at thelast frame of the second real movie data experimenteach pattern is divided into smaller clusters so as to reﬂect
the complex behaviors.
Finally we present snapshots from the tracking resultsin Fig. 8 for the ﬁrst experiment and Fig. 9 for the second
real movie data experiment, respectively. In the ﬁgures, estimated object coordinates are denoted with rectangles. The
color of each rectangle denotes the target’s ID (i). Numberson the rectangles represent the indices of the pattern of dynamics (z) in Fig. 6 and Fig. 7. The results show that the
proposed model is able to identify hidden states of multiple
targets and estimate the unknown patterns of dynamics.

5. Conclusion
In this paper, we presented a novel on-line probabilistic generative model that simultaneously deals with boththe clustering and the tracking of multiple moving objects.
We assume that time series data are generated from an unknown number of hidden trajectories of target objects, eachof which is governed by an unknown number of different
dynamics parameters. Our model can infer the property ofa mixture model whose number of mixture components is
unknown through a nonparametric Bayes model with conjugate priors. The developed model can simultaneously learn
and infer the hidden states of each target object as wellas their patterns of dynamics and characteristics. Throughexperiments with synthetic and real movie data, we conﬁrmed that the proposed model successfully learned the hidden cluster patterns and obtained better tracking results thanconventional models without clustering.
In this paper, we modeled rather simple state-space
schemes. One possible extension of this work is to incorporate more complex models into the learning scheme, suchas object appearance or structure models.

frame #0

frame #100

frame # 0

frame # 160

frame #25

frame #125

frame # 40

frame # 200

frame #50

frame #150

frame # 80

frame # 240

frame #75

frame #175

frame # 120

frame # 280

Figure 8. Tracking results of the ﬁrst real movie experiment

References[1] D. Blackwell and J. B. MacQueen. Ferguson distributions
via Polya urn schemes. The Annals of Statistics, 1(2):353–
355, 1973. 2, 4
[2] F. Caron, M. Davy, A. Doucet, E. Duﬂos, and P. Vanheeghe.
Bayesian inference for linear dynamic models with Dirichlet
process mixtures. IEEE Trans. Signal Processing, 56(1):71–
84, 2008. 1, 2, 3, 5
[3] M. J. Cassidy and W. D. Penny. Bayesian nonstationary autoregressive models for biomedical signal analysis. IEEE
Trans. Biomedical Engineering, 49(10):1142–1152, 2002. 1[4] N. Dalal and B. Triggs. Histograms of oriented gradients forhuman detection. In Proc. CVPR, volume 2, pages 886–893,
2005. 7[5] C. Kemp, J. B. Tenenbaum, T. L. Grifﬁths, T. Yamada, andN. Ueda. Learning systems of concepts with an inﬁnite relational model. In Proc. AAAI, 2006. 2[6] Z. Khan, T. Balch, and F. Dellaert. A Rao-Blackwellized
particle ﬁlter for eigentracking. In Proc. CVPR, pages 980–

Figure 9. Tracking results of the second real movie experiment986, 2004. 1[7] Z. Khan, T. Balch, and F. Dellaert. MCMC data association and sparse factorization updating for real time multitarget tracking with merged and multiple measurements. IEEE
Trans. PAMI, 28(12):1960–1972, December 2006. 1, 3
[8] B. Leibe, N. Cornelis, K. Cornelis, and L. V. Gool. Dynamic
3D scene analysis from a moving vehicle. In Proc. CVPR,
2007. 1, 6
[9] T. W. Liao. Clustering of time series - a survey. Pattern
Recognition, 38(11):1857–1874, 2005. 1[10] M. Ramoni, P. Sebastiani, and P. Cohen. Bayesian clustering
by dynamics. Machine Learning, 47(1):91–121, 2002. 1[11] S. Särkkä, A. Vehtari, and J. Lampinen. Rao-Blackwellized
particle ﬁlter for multiple target tracking. Information Fusion, 8(1):2–15, 2007. 1, 2, 3, 4, 5[12] P. Smyth. Clustering sequences with hidden markov models.
In M. C. Mozer, M. I. Jordan, and T. Petsche, editors, Advances in Neural Information Processing Systems 9, pages
648–654. MIT Press, 1997. 1