Multitarget tracking is the main purpose of many video surveillance applications. Recently, multitarget tracking based on the particle filter method has achieved robust results by using the data association process. However, this method requires many calculations and it is inadequate for real time applications, because the number of associations exponentially increases with the number of measurements and targets. In this paper, to reduce the computational cost of the data association process, we propose a novel multitarget tracking method that excludes particle samples in the overlapped predictive region between the target to track and marginal targets. Moreover, to resolve the occlusion problem, we define an occlusion mode with the normal dynamic mode. When the targets are occluded, the mode is switched to the occlusion mode and the samples are propagated by Gaussian noise without the sampling process of the particle filter. Experimental results demonstrate the robustness of the proposed multitarget tracking method even in occlusion.
1. Introduction
T
he main goal of visual tracking for video surveillance is to track the position of multiple moving targets. For example, trajectories of multiple targets are useful for analyzing traffic on roads, consumer flow in department stores, sport events, and so on. The Kalman filter
[1
,
2]
or particle filter
[3
,
4
,
5]
are widely used for tracking objects. The Kalman filter supports an effective method by estimating a target state according to the time sequence. However, the target state is limited to the linear Gaussian model. The particle filter achieves superior performance in complicated environments. It is possible to apply the particle filter to the nonlinear and nonGaussian models. However, the traditional particle filter is not adequate to independently track multiple targets, since the samples are centralized to the modal with the highest likelihood according to the importance sampling.
Joint Probabilistic Data Association Filter (JPDAF)
[6]
, based on the data association technique, is a useful method for multitarget tracking. This method can independently track multiple targets by evaluating the association probabilities between measurements and targets. The particle filterbased data association methods
[7
,
8]
, modified from JPDAF based on the Kalman filter, are robust in tracking multiple targets with nonlinear property. However, these techniques are originally developed for radar data, and they require modification to apply to the visual tracking problem. There are many methods to track objects including the color histogram method
[9
,
10]
, which is an extended version of the color histogram method
[9]
, kernel particle filter
[11]
, boosted particle filter
[12]
, and detector confidence particle filter
[13]
, and these methods combine feature detection and tracking for the video sequence.
Despite these efforts, there are some problems in visual tracking based on the data association technique: 1) The tracking results cannot keep the identification of each target after occlusion, because of the lack of clarity of mutual exclusion of each target; and 2) the data association process of JPDAF is too complicated to apply to visual tracking in realtime.
In this paper, we propose the disjoint particle filter (DPF) for multitarget tracking. The proposed method assumes that each measurement cannot be identified by the feature of observed data, but is only disjointed by the spatial information. DPF is faster than JPDAF, which considers every association probability between the targets and measurements, since the proposed method updates weights by only comparing the predictive target probabilities with those of marginal targets. However, the proposed approach is weak in accuracy under occlusion, because we use the spatial information of samples with propagation to evaluate the predictive target probability. To solve these problems, we use a dynamic mode which can overcome the occlusion problem. When occlusions occur, the mode is changed into the occlusion mode, and the samples are propagated by Gaussian random noise. This method enables the filter to keep track of a target even under temporary occlusion.
This paper is organized as follows. In Section 2, we explain the general particle filter for visual tracking. In Section 3, we present the prediction and the update process of the proposed DPF, and how to change a filter state in dynamic mode. Experimental results are presented in Section 4, which show speedups for real time tracking and robustness in occlusion. The conclusions are presented in Section 5.
2. Visual Tracking using the Particle Filter
The particle filter is also known as the Condensation algorithm
[12]
, and has become famous in the visionbased tracking area. When the state of a tracked object is described by the vector
x
^{k}
, while the vector
Z
^{k}
denotes all the observations up to time
k
, to track a target of interest via the particle filter, the posterior probability density function
p
(
x
^{k}

Z
^{k}
), known as the filtering distribution, should be calculated at each time step
k
. It can be calculated by twostep recursion in Bayesian sequential estimation;
1) Prediction step:
2) Update step:
Because the integrals of the optimal Bayesian solution are intractable, the discrete sums of weighted samples drawn from the posterior distribution are used in the particle filter algorithm. However, it is often difficult to directly sample from the true posterior density; and thus, the particles are sampled from a known proposal distribution.
In order to explain the details of the particle filter, let {
x
^{i,k}
,
w^{i,k}
}
^{N}_{i}
_{1}
denote a weighted set of samples, where {
x
^{i,k}
,
i
=0,...,
N
} is a set of support points with associated weights {
w^{i,k}
,
i
=0,...,
N
} and
x
^{k}
={
x
^{j}
,
j
=1,...,
k
} is the set of all states up to time step
k
. The samples are repeatedly generated from the proposal distribution, and the new importance weights are updated by:
{
w^{i,k}
,
i
=0,...,
N
} and x
^{k}
={x
^{j}
,
j
=1,...,
k
} is the set of all states up to time step
k
. The samples are repeatedly generated from the proposal distribution, and the new importance weights are updated by:
where,
and
q
is the proposal density function, where new samples are generated from that distribution.
For successful tracking in the particle filter, which particular proposal distribution is used is important. In this paper, we use the state evolution model
p
(
x
^{k}

x
^{k}
^{1}
) as a proposal distribution for simple implementation as in
[14]
. So, the weights of samples are only dependent on the likelihood of measurements.
However, in this simplicity of using only the likelihood for object tracking, there is a critical disadvantage for tracking multiple targets.
Fig. 1
shows a problem that is created by tracking two targets with two simple particle filters. The particle samples, which independently track each of the two targets, are centralized into the left target, after overlapping at d) of the 30
^{th}
frame as shown in
Fig. 1
. This problem occurs when the samples are driven to one target with higher likelihood on the neighboring two targets. Recently, many strategies have been proposed to solve the problem associated with multitarget tracking. The key idea of the literature is to estimate each object’s position separately, and the measurements should be assigned to each target. Therefore, data association has been introduced to relate each target to its associated measures. Among the various methods, the Joint Probabilistic Data Association Filter (JPDAF) algorithm
[8]
is taken into account as one of the most attractive approaches.
An example of tracking two targets using two particle filters
3. Disjoint Particle Filter
One of the shortcomings of the data association method
[8]
is that the computational complexity exponentially increases as the numbers of targets and measurements are increased. Therefore, the objectives of our proposed DPF are reducing the computational complexity and tracking each target efficiently.
 3.1 Prediction
Consider the problem of tracking
T
targets. We use the same number of particle filters as targets.
X
^{k}
={(
x
_{1}
^{k}
,
π
_{1}
^{k}
),...,(
x
_{t}
^{k}
,
π_{t}
^{k}
)}, where
x
_{t}
^{k}
and
π_{t}
^{k}
denote the state vector of the
t
th particle filter and the confidence of the filter at time
k
, respectively. Confidence
π_{t}
^{k}
is an indicator that determines the mode of the particle filter. We assume that each measurement data is not identified. Our state vector,
x
_{t}
^{k}
, is simply the location,
x
_{t}^{k}
=[
x_{t}^{k}
,
y_{t}^{k}
]
^{T}
, which is the center of the rectangle with a predefined size for color histogram matching. The rectangle size is not related to the target size and appearance, because the rectangle region is just used for histogram matching. The size of a target is described by the distribution of samples, while the dynamics of the target are described by the simple linear model:
where,
G
denotes the Gaussian noise that is in charge of spreading the samples and the variation is determined according to the spreading degree of samples, which is adaptively set by a filter mode.
 3.2 Weight Update
As shown in
Fig. 1
, when two targets are overlapped, all samples are centralized into only one target due to the higher likelihood of that target. JPDAF, the data association based technique, is an efficient way of independently tracking targets by calculating the intersection of each other. However, the computation complexity is inappropriate for a realtime tracker, because the number of associations grows exponentially as the number of targets and the number of measurements increase. To improve the performance, we define the predictive target region (PTR) and propose a method to exclude the samples in the overlapped region at the resampling step.
The concept of mutual exclusion of disjoint particle filters
Fig. 2
shows the boundary of two overlapped PTRs for mutual exclusion at the particle sampling stage. If two particles are overlapped at the PTR, particles from different filters are depicted as dots or circles in
Fig. 2
, and are used separately for each particle filter. We can compute the PTR centers with x
_{t}^{i,k}
,
i
=1,2,...,
N
that are generated in the resampling process.
The distance of an
i^{th}
sample from the PTR center of the
t^{th}
target is defined by:
where,
S_{t}^{k}
is a covariance matrix of all the sample positions for the
t^{th}
target. We assume a predictive target distribution function for the
i^{th}
sample as the Gaussian distribution.
where, 
S_{t}^{k}
 is the determinant of
S_{t}^{k}
. This is the predictive target distribution function by conversely estimating from the propagated samples.
Because the predictive target density of targets
x
_{1}
and
x
_{2}
are modeled according to the Gaussian distribution, it has the mean and standard deviation for the spatial region. The observation likelihood of the
i^{th}
sample is calculated via comparison between the histograms of the sample block and a template. Using the color histogram of the template
p
and the reference histogram of the target region
q
, we can calculate the observation likelihood
o_{t}^{i}
using the Bhattacharyya distance and Gaussian distribution
[9]
as follows:
where
and
m
is the number of bins in the two histograms
p
={
p^{u}
}
_{u=1...m}
and
q
={
q^{u}
}
_{u=1...m}
. The variance
σ_{t}^{k}
is calculated by the samples in each target. This approach can distinguish the target of interest from other targets by a simple comparison as shown in
Fig. 3
. Each particle has a weight assigned to it, which represents the probability of that particle being sampled from the probability density function. After a few iterations the particle set will contain many particles with weight close to zero and a few particles with high weights. In order to avoid this effect we resample the particles that new particle set likely contains multiple copies of particles with high weights whereas particles with low weights are likely to be discarded form the set as shown in
Fig.3
. The particles with higher weights (larger circles) are chosen with a higher probability, but the total number of samples stays the same.
The propagation of particle samples for multitarget tracking with the mutual exclusion constraint
Sample weights are updated by the observation likelihood, if the predictive target probability of the target being tracked is higher than the predictive target probability of other targets, as follows:
If the weight is updated for all particle samples in (9), the state vector of the
t^{th}
target can be estimated as follows:
 3.3 Dynamic Mode for Occlusion
Mode transition diagram for DPF
Fig. 4
shows the transition diagram of the DPF containing the dynamic mode. As defined in Section 2, the DPF has the filter confidence
π_{t}^{k}
for each target, and is computed by averaging the weight of all samples.
where
and α is the weight that adjusts the importance between the previous confidence
π_{t}^{k}
^{1}
and the average of current observations
ŵ_{t}^{k}
۰
π_{t}^{k}
represents the tracking confidence for the
t^{th}
target. If this value is high, then the tracking is stable in recent frames. If this value is low, then tracking is not stable up to recent frames. Each process in
Fig. 4
is described below.
1) Generation: If
π_{t}^{k}
of all particle filters are higher than the threshold
T
_{1}
, then a new particle filter is generated to track targets that are not chased. If there is no target remaining to be tracked, then the generated particle filter will be eliminated. The samples in the generated particle filter are uniformly distributed in the global region of the image at the initial time, and are then converged in one target by applying SIR (sampling importance resampling). In this process, if the
π_{t}^{k}
of the generated particle filter is higher than
T
_{1}
, then the status of the generated particle filter is changed into the tracking mode.
2) Tracking Mode: Targets are tracked by applying the SIR with (9). In this process, if the
is lower than
T
_{2}
, then it will be changed into the occlusion mode.
3) Occlusion Mode: This process is under the situation that most samples missed the target. In this step, instead of the SIR process, all samples are propagated by dynamics with the Gaussian noise, as described in (4). After particles are propagated by (4) and updated by (9), if
is higher than
T
_{2}
, then the mode will be changed into the tracking mode.
4) Elimination: If the filter confidence
π_{t}^{k}
is lower than
T
_{3}
, then the particle filter will be eliminated.
Our method has tracking and occlusion modes to distinguish between the cases of the lost target and temporary occlusion. If the average of all sample weights is lower than the threshold, then the mode changes into the occlusion mode and keeps tracking by the propagation of particles according to the dynamics of the Gaussian noise. Because the filter confidence is updated by the mean of weights of all the samples in the filter, as shown in (9), the filter confidence decreases in the occlusion mode. If the filter confidence is lower than the threshold, then the filter restarts the tracking for the new target by uniformly distributed samples.
Occluded target tracking using the dynamic mode
Fig. 5
shows tracking results of the target occluded by an obstacle using the dynamic mode. The images in the first row show that the red color denotes a target moving in a circular trajectory, the cyan line is a trace of the target, and the gray region is an artificially made obstacle. In the second row images, the cyan points mean the particle samples tracking a target, and the predictive target region (PTR) that occurs by particles is presented as a red ellipse.
As shown in
Fig. 5
, the moving direction of the target is changed from (a) the bottom of the 124
^{th}
frame to (b) the right of the 145
^{th}
frame. The particles are also propagated from horizontally to vertically, since all the samples are moving according to their dynamics in (4). This property makes it easy to track the target in occlusion mode. The particle filter with the tracking mode at (b) transfers into the occlusion mode at (c), because the target is lost due to the occlusion. Samples in the occlusion mode are diffused by keeping the previous dynamics, so that at (d) the target can be tracked at the appropriate location of the 166
^{th}
frame. The 174
^{th}
frame in (e) shows that the filter has changed back into the tracking mode.
4. Experiment
The experiments are performed on a PC with 2GB memory, 2.0 GHz QuadCore CPU, and the resolution of an input image is 640×480. To apply realtime surveillance systems, we compare the performance of the proposed method with that of JPDAF. In the second experiment, we test the multitarget tracking for soccer players that occlude each other.
 4.1 Pixel based Tracking
The experiment is performed by increasing the number of targets from one to nine with N=2000 for each target, with
T
_{1}
=0.9,
T
_{2}
=0.7,
T
_{3}
=0.1, and
α
=0.9, in (11). For the initialization of the particle filter, we manually select the starting values of the state vector
x _{k}
, and the number of particle filters increases from one to the number of targets. The samples in the generated particle filter are uniformly distributed in an image at the initial time then converged in one target by applying the importance resampling. After the particles of a filter are converged to a target, a new particle filter is generated according to the scenario in Section 3.3.
Multitarget tracking for realtime application
Fig. 6
shows the tracking result of billiard ball targets from the reference colors. By using the histogram matching technique described in (8), the particle filter can provide a fine matching result based on various feature vectors. We use the similarity of Cr and Cb in the YCrCb color space as the likelihood instead of the histogram matching, for fair comparison between the data association technique and the proposed technique.
Fig. 6
shows the 12
^{th}
frame starting with one particle filter, and from 38
^{th}
to 116
^{th}
frames there are four particle filters in tracking mode.
Comparison of the processing time with DPF and JPDAPF
Fig. 7
shows the average processing time of one frame for the particle filter based on JPDAF
[9]
and the proposed DPF. In JPDAFPF, we increase the number of targets and the number of measurements equally. Targets are likely to be tracked in realtime until up to five in both methods, even when using 2,000 samples for each target. However, since the processing time of JPDAFPF exponentially increases according to the number of targets and the number of measurements, it is inappropriate for a realtime tracker. The computational cost of the proposed method is efficient for realtime tracking, because the processing time is only linearly increased.
 4.2 Blockbased Tracking
Fig. 8
shows the tracking results using DPF for soccer players that occlude each other. In
Fig. 8
, the 130
^{th}
~200
^{th}
frames show two soccer players overlapping one another, and the DPF excludes particle samples in the two overlapped PTRs at the resampling step. Despite occlusion, the 236
^{th}
frame shows successful tracking of each player, because DPF can spatially distinguish the two targets in the occluded PTR by sample exclusion. This result shows that the proposed algorithm assures tracking accuracy as well as computational efficiency for realtime surveillance applications.
Tracking soccer players with occlusion
5. Conclusion
The disjoint particle filter intuitively and efficiently tracks multitarget by excluding particles in the overlapped tracking region between the tracking target and other objects. In the case of occlusion, DPF changes the tracking mode with the SIR process into the occlusion mode with Gaussian propagation, and tracking is stable despite the occlusion. In the experiment of tracking targets of billiards and soccer players, we show the robustness in tracking targets and the efficiency in computation. In future work, we will combine the DPF with textural features and it will be applied to realtime surveillance systems.
BIO
YoungJoon Chai received a BS degree in Information and Communication Engineering from Korea University of Technology and Education in 2003 and a MS degree in Advanced Imaging Engineering at ChungAng University, Seoul, Korea. Currently, he is working toward a PhD in Advanced Imaging Engineering at ChungAng University.
Hyunki Hong received his BS, MS, and PhD degrees in electronic engineering from ChungAng University, Seoul, Korea, in 1993, 1995, and 1998, respectively. From 1998 to 1999 he worked as a researcher in the Automatic Control Research Center, Seoul National University, Korea. From 2000 to 2014, he was a professor in the Department of Imaging Science and Arts, Graduate School of Advanced Imaging Science, Multimedia and Film at ChungAng University. Since 2014, he has been a professor in the School of Integrative Engineering, ChungAng University. His research interests include computer vision, augmented reality, and multimedia application.
TaeYong Kim received a BS degree in Electrical Engineering and MS degree in Communication Engineering from HanYang University, Seoul, Korea, in 1986 and 1988, respectively, and a PhD in Computer Science and Engineering from Pohang University of Science & Technology, Korea, in 1998. He has been a professor at the Graduate School of Advanced Imaging Science, Multimedia and Film, ChungAng University, Seoul, Korea since 2003. His research interests are in Computer Vision, Image Processing, and A.I.
BarShalom Y.
,
Li X.
,
Kirubarajan T.
2001
Estimation with Applications to Tracking and Navigation
J. Wiley and Sons
Article (CrossRef Link).
Kim J.Y.
,
Yi C.H.
,
Kim T.Y.
2010
“ROICentered Compression by Adaptive Quantization for Sports Video”
IEEE Transaction on Consumer Electronics
Article (CrossRef Link).
56
(2)
951 
956
DOI : 10.1109/TCE.2010.5506025
Arulampalam M. S.
,
Maskell S.
,
Gordon N.
,
Clapp T.
2002
“A tutorial on particle filters for online nonlinear/nonGaussian Bayesian tracking”
IEEE Transactions on Signal Processing
Article (CrossRef Link).
50
(2)
174 
188
DOI : 10.1109/78.978374
Chai YoungJoon
,
Shin SeungHo
,
Chang Kyusik
,
Kim TaeYong
2010
“Realtime user interface using particle filter with integral histogram”
IEEE Transaction on Consumer Electronics
Article (CrossRef Link).
56
(2)
510 
515
DOI : 10.1109/TCE.2010.5505963
BarShalom Y.
,
Blair W. D.
2000
MultitargetMultisensor Tracking: Applications and Advances, Vol. III.
Artech House
Norwood, MA
BarShalom Y.
,
Daum Fred
,
Huang Jim
2009
“The Probabilistic Data Association Filter”
IEEE Control Systems Magazine
Article (CrossRef Link).
29
(6)
82 
100
DOI : 10.1109/MCS.2009.934469
Ng W.
,
Li J.
,
Godsill S.
,
Vermaak J.
2005
“Tracking variable number of targets using sequential monte carlo methods”
in Proc. of IEEE Statistical Signal Processing Workshop
July 1720
Article (CrossRef Link).
1286 
1291
Gorji A.
,
Menhaj M. B.
,
Shiry S.
2009
Multiple Target Tracking for Mobile Robots Using the JPDAF Algorithm
Tools and Applications with Artificial Intelligence
Article (CrossRef Link).
51 
68
Jaward M.
,
Mihaylova L.
,
Canagarajah N.
,
Bull D.
2006
“Multiple object tracking using particle filters”
in Proc. of the AERO
Article (CrossRef Link).
Czyz J.
,
Ristic B.
,
Macq B.
2005
“A colorbased particle filter for joint detection and tracking of multiple objects”
in Proc. of the ICASSP
Article (CrossRef Link).
217 
220
Chang Cheng
,
Ansari R.
,
Khokhar A.
2005
“Multiple Object Tracking with Kernel Particle Filter”
in Proc. of the CVPR
June 2025
Article (CrossRef Link).
566 
573
Okuma K.
,
Taleghani A.
,
de Freitas N.
,
Little J. J.
,
Lowe D. G.
2004
“A boosted particle filter: Multitarget detection and tracking”
in Proc. ECCV
May 1114
Article (CrossRef Link).
28 
39
Breitenstein M. D.
,
Reichlin F.
,
Leibe B.
,
KollerMeier E.
,
Van Gool L.
2009
“Markovian trackingbydetection from a single, uncalibrated camera”
in Proc. IEEE Int. Workshop Performance Evaluation of Tracking and Surveillance
December 3
Article (CrossRef Link).
Chai YoungJoon
,
Park JinYong
,
Yoon KwangJin
,
Kim TaeYong
2011
“Multi Target Tracking Using Multiple Independent Particle Filters For Video Surveillance”
in Proc. of IEEE International Conference on Consumer Electronics
January 912
Article (CrossRef Link).
756 
757