
Research Article


Object Tracking Based on Particle Filter with Improved Camshift 

Zhiyu Zhou,
Xiaolong Peng ,
Dichong Wu ,
Zefei Zhu ,
Chuanyu Wu
and
Jianwei Wu



ABSTRACT

Particle filter simulates posterior probability distribution
of tracking target through a collection of random particles. Whereas the interferences
of analogues occur frequently in a normal condition, random particles might
not be able to proximate target state that easily. This study presents an innovative
particle tracking method, with a combination of color and motion information
provided by improved Camshift. First, the centroid position of tracking target
is denoted by joint probability distribution of color histogram and motion information,
such that the stability of Camshift has been improved. Then, an improved Camshift
is introduced to optimize particles evolution. With analogue interferences,
grey prediction model initialized by Camshift is imposed to harvest proposal
distribution of optimized particle filter. Finally, in the sampling process,
particles are sampled hierarchically to denote exact target position on the
basis of the weights. Experimental tasks have demonstrated that the method performs
well under the condition of targets maneuvering, incomplete or complete occlusions.
Furthermore, it outperformed the previous with more robustness and computation
accuracy.





Received: July 18, 2013;
Accepted: October 04, 2013;
Published: February 01, 2014


INTRODUCTION
In these years, object tracking based on pattern matching and state estimation
has found extensive applications in computer vision. There are improved methods
with pattern matching and state estimation flourishing recently, e.g., the sophisticated
Meanshift and Camshift (Bradski, 1998). Thanks to these
methods, traditional tracking problem has been translated into a local matching
optimization problem. They performed rather smooth and facile in normal conditions,
however, a couple of limitations stand over there, rendering tracking paralyzed
in certain conditions, e.g., complete occlusions and drastic interferences.
Yun and Xiao (2011) utilized adaptive weight of target
color, shape and texture information, fusing them together into Camshift to
track the watercrafts. Nevertheless, it drops out tracking accuracy somewhat
in case of occlusions. Under the framework of Bayesian theory, tracking problem
has been turned into an approaching process of maximum a posteriori probability
of target state. In this case, sequential Monte Carlo method, otherwise the
socalled particle filter has become a ubiquitous tool, solving dozens of tracking
problems. Traditional particle filter displayed a relatively high accuracy in
rigid object tracking, particularly competent for object tracking of maneuvering
target, robot localization and state estimations. However, a couple of defects
stemming from its inherent property have found very knotty to get rid, e.g.,
particles degradation and high computation complexity. Niu
et al. (2010) constructed a target model of particles through the
invariant features of illumination, scale and affine transforms in Scale Invariant
Feature Transform (SIFT). In general, substantial rotation of moving target
has evil impacts on tracking robustness. Xia et al.
(2012) optimized particles propagation by a sampling process in high likelihood
region, such that the particles are prone to higher probability of state transition,
magnifying antiocclusion ability of tracking system. Luo
et al. (2011) took advantage of loglikelihood function, incorporating
the background information into target model to eliminate similar interferences
in background. In this sense, a least square method would be applying as well
to alleviate occlusions problem. Shi et al. (2012)
adopted Meanshift to improve particles propagation direction, tracking the vehicles
with particles under low altitude platform. Similarly, Wang
et al. (2009) put forth a tracking method using particle filter with
Camshift, the upgraded Mean Shift, in a way that particles degradation has been
overwhelmed somewhat. Although both of them employ color as the single feature,
similar color interference in background is harmful to system robustness. Li
et al. (2010) made full use of features constraint, such that the
majority of sampling particles had fallen on the target. With an attachment
of Meanshift to approach particles to local extrema, particles number won’t
entail so many like traditional particle filter. Nevertheless, this method disregards
the influence of illumination changes and drastic occlusions, both of which
have proved to be important influential factors that matter. At last, Sun
et al. (2010) combined color and motion features together to track
objects adaptively using an optimized Camshift based on particle filter.
Posterior probability distribution of target could be approximated by particle filter with random sample particles. Once the target gets occluded completely by similar objects, it is bound to cause a tracking failure. Given all merits and demerits mentioned above, this study presents an innovative method using color and motion information in pairs to determine the joint probability distribution of Camshift. Without occlusions, improved Camshift will serve alone to yield the particles proposal distribution. With occlusions, an initialized grey prediction model using improved Camshift is imposed instead to harvest proposal distribution. In summary, the proposal distribution will be selected adaptively for a stronger robustness. MATERIALS AND METHODS Improved camshift: Once video sequences get occluded by some background interferences, traditional Camshift would lose the tracking targets rapidly. As some categories of object inherited with distinct color and motion trajectory, it would thus be judicious to use color and motion cues to capture the visual appearance in targets. With an implement of improved Camshift, the outputting distribution would approach authentic motion more compactly. Following are the major computation stages of improved Camshift:
• 
To obtain background difference image by the subtraction of
current image and background image in current frame and label the image
in eightconnected component after binaryzation of difference frame. After
corrosions, the motion information I_{m }in image is known 
• 
To acquire color histogram in H channel of current image frame and extend
color range from 0 to 255. Counting up the color histogram of current frame,
statistic color probability distribution I_{h} in H channel is obtained 
• 
To calculate zeroorder moment of moving target based on motion information
and color probability distribution. The firstorder of x and y is defined
as: 
• 
The centroid position of searching window is defined as: 
After definite times of iteration, target centroid position would thus be denoted. Then a GM (1,1) model will be imposed in X and Y, respectively, to proceed the prediction. Suppose the initial sequence of target centroid X^{(0)} = (x^{(0)} (1), x^{(0)} (2),..., x^{(0)} (n)), the accumulative sequence of firstorder X^{(1)} = (x^{(1)} (1), x^{(1)} (2),..., x^{(1)} (n)), then:
is called the grey differential equation, also famed as grey prediction model
(Liu et al., 2004). Then, white differential equation
of grey prediction model is defined as:
Thus, the time response function of white and grey differential equation, which corresponds the initial value with the average value of x(1),..., x(n) would be: In a very identical way, another centroid y would be acquired likewise. Without occlusions, the particle filter distribution would be predicted by improved Camshift, meanwhile, the initial value of grey prediction model is deployed as the average value of x(1),..., x(n). In the environment of analogue occlusions, grey prediction model will be complemented instead to yield particles proposal distribution. Only a small amount of observation sample is required in grey prediction model, which could accommodate tracking to some extreme scenarios. In such cases, e.g., there are occlusions of outsiders emerging at times or the target of interest exhibits distinctive features too barren. Particle filter with improved camshift: Particle filter is an effective tracking algorithm based on Bayesian and Monte Carlo method, combating either the nonlinear or the nonGauss problem. One benefit of particle filter is that, it allows for information fusion of various cues in a principled manner. And there exists a large swarm of cues available to increase the reliability of the tracking. Nevertheless, it still entails the appropriate particles proposal distribution under the main framework. In this study, on the basis of distinctive environment, the Camshift and grey prediction model would pick up alternatively to evolve particles proposal distribution. In a way that particles would move to the direction of maximum posterior probability of target. The biggest sampling obstacle of particle filter is the particles degradation phenomenon. In this case, sampling would be concentrated on minor particles, yet these particles are not pragmatic enough to express the authentic posterior probability density. To suppress the particles degradation, this study presents a novel method called stratified resampling. The concrete implementation steps are listed as follows:
• 
To select target color template in image sequence of the first
frame and compute the target center (x_{0}, y_{0}) 
• 
The particles set (x^{m}_{k1}, y^{m}_{k1})
is engendered based on target’s center. A similarity comparison of
center position between current particles and the target would then be adopted,
in order to harvest the normalized weight w^{m}_{k1} of
each particle. The probability density function of particles observation
is defined as: 
where, k1 represents the number of current frame and m = 1,2,…,N denotes the particle number
• 
After an AND process between motion information l_{m}
and color probability distribution l_{n}, consecutive nonzero data
of one line would be obtained by a statistical value of pixels in each line.
Then, the threshold is to be set according to accumulated pixel values in
moving target region. In this way that the disturbing regional noise would
vanish and a nonzero or zero data block of available pixels would be substituted
for a renovation 
• 
When number of nonzero data block in detection region appears greater
than two, a decision of occlusions would be predicated. And then particles
prediction method is to be chosen based on the distance threshold T between
the target and analogue. Once the distance between two analogues is greater
than threshold T, the improved Camshift method would be then employed. Otherwise,
the mean value of initial sequences x(1),..., x(n) of grey prediction model
would be alterative choice to proceed the prediction instead 
• 
A stratified resampling strategy of predicted particles is applied to
harvest accumulated value of particle weights. Particles with larger weights
will then take replace of those with smaller weights and particles set {(x^{m}_{k},
y^{m}_{k}) is reshuffled at random. Probability density
function of observation value of particles after evolution is defined as: 
And the particles weight w^{m}_{k} after the resampling is defined as:
• 
Through a weighted sum of particles, the target center (x_{0}^{new},
y_{0}^{new}) of particles in the next frame will thus be
evaluated as: 
RESULTS AND DISCUSSION
Amongst all categories of particle filter, it makes sense that how many particles
should be picked up. On the one hand, number of particles is associated with
the precision of one system compactly. On the other hand, an inappropriate selection
of particles would otherwise aggrandize the computation complexity. In general,
the larger number of particles has been chosen, the more precision the system
will harvest. Whereas the realtime of system are restricted by particles number,
it is thus sagacious to seek a medium amount of particles. Almost recently,
a method called RANSAC has become a sleek tool in computer vision, molding a
galaxy of successful applications over extensive range. As a comparison of methods
in Yun and Xiao (2011) and Sun
et al. (2010), particles number is deployed as ten in this study.

Fig. 1(ab): 
Contrast results of Yun and this study with incomplete occlusions
(Frame 32, 72,112,122), (a) Tracking results with Yun’s method (Yun
and Xiao, 2011) and (b) Tracking results with improved method in this
study 
And particles selection woud be escorted by an implementation of RANSAC routine.
Tracking with incomplete occlusions: In literature (Yun
and Xiao, 2011), specific category of objects with distinctive features
has been considered. With mixed cues of color, shape and texture fused all together,
visual appearance of the tracking entities would be captured easily. However,
under a tracking condition of incomplete occlusions and similar color interferences,
they might yet be contaminated by the clutter of similar objects. Tracking results
with the method of Yun and Xiao (2011) are shown in
Fig. 1a. In this study, motion cue based on Camshift is to
be incorporated into particle filter. The instantaneous motion information carries
subtle aspects of video contents, which could render the needful aid as soon
as color features turn meager intermittently. Tracking results in this study
are shown in Fig. 1b. In this study, the motion trajectory
of tracking target has been shrunk into one little point. In this sense, centroid
of tracking target in either X, Y direction would denote the genuine motion
trajectory. Figure 2 shows the centroid contrast diagrams
in both X and Y direction with partial occlusions. As an intuitive cognition,
the error rate between tracking results and real outputs is lower than the rate
in Yun’s method. The average error rate of direction X and Y in this study
is 1.967 and 3.994 pixel. And the error in Yun’s method is 63.956 and 45.598
pixel. The method proposed in this study has proved able to perform with more
robustness under the incomplete occlusions of analogues.
Tracking with complete occlusions: In order to contrast discrepant interfering
effects of analogues, portions of similar parts in tracking objects are brought
into tracking context. In literature (Sun et al.,
2010), a joint probability distribution coined by pair of color histogram
and motion information is employed to track the moving target. Whereas centroid
of the target is vulnerable to analogues, might automatically shift itself to
one direction with higher joint probability. The centroid has moved toward opposite
direction of target since the 24th frame, as it is shown in Fig.
3a. The color cooperates with motion information perfectly, in a mutual
way that renders disappearance of the analogue interferences. At last, proposal
distribution of the particle filter would thus be generated with a grey prediction
model initialized by Camshift, Fig. 3b shows the tracking
results in this study. Tracking has approached to the authentic centroid of
target pretty close. As it can be seen from Fig. 4, the error
rate of tracking results in this study turns out even lower. The average error
rate of direction X and Y is 3.416 and 7.319 pixel, whereas Yun’s is 35.875
and 20.208 pixel. Experiment in this study has satisfactory results with parallel
stability and robustness, albeit under the interferences with complete occlusions.

Fig. 2(ab): 
Centroid contrast diagrams of Yun and this study with incomplete
occlusions, (a) Centroid contrast diagram in direction X and (b) Centroid
contrast diagram in direction Y 

Fig. 3(ab): 
Contrast results of Sun and this study with complete occlusions
(Frame 27, 51, 53, 58), (a) Tracking results with Sun’s method (Sun
et al., 2010) and (b) Tracking results with improved method in
this study 
Object tracking of maneuvering targets: Image sequences delivered by
IBM turn to be ideal to conduct the third experiment, which will be introduced
to demonstrate the tracking efficiency of maneuvering targets. Proceeding with
multitarget tracking task, tracking results in this study prevails over literature
(Sun et al., 2010) with great odds. As certain
class of objects appears susceptible to color and texture interferences, scenario
occurred in literature (Yun and Xiao, 2011) would thus
yield fairly discontented tracking consequence. Let alone the variations of
motion direction, more often, it turns out to be a direct reflection of motion
variations. Both Sun’s and the method in this study take motion information
into account. Targets could accommodate to certain conditions with scarce features
of color, texture or shapes. Figure 5 shows tracking results
of the maneuvering targets.

Fig. 4(ab): 
Centroid contrast diagrams of Sun and this study with complete
occlusions, (a) Centroid contrast diagram in direction X and (b) Centroid
contrast diagram in direction Y 

Fig. 5(ac): 
Contrast results of maneuvering targets of Yun, Sun and this
study (Frame 40, 115, 295, 405), (a) Tracking results of maneuvering targets
with Yun’s method (Yun and Xiao, 2011), (b)
Tracking results of maneuvering targets with Sun’s method (Sun
et al., 2010) and (c) Tracking results of maneuvering targets
with improved method in this study 

Fig. 6(ac): 
Contrast results of Yun, Sun and this study with occlusions
of branches (Frame 20, 50, 170, 200), (a) Tracking results with Yun’s
method with occlusions of branches (Yun and Xiao, 2011),
(b) Tracking results with Sun’s method with occlusions of branches
(Sun et al., 2010) and (c) Tracking results
with improved method in this study with occlusions of branches 
Tracking with occlusions of branches: In a natural environment, the context of interruptions would happen at times. As a practical example, portions of human body in occlusions of branches are taken out as comparisons. The reflection of sunshine, in addition of irregular variations of shape and texture of the branches, both of which would cause numerous mismatches in the process of tracking. As a tracking result of Yun, the target gets disappeared after 30th frame. The color and motion information are exploited in Sun’s method. As a consequence of observations, once a cluster of branches jump into the frame suddenly, the gross information would fluctuate sharply. As it is, it only lives up to 150 frames at climax. In this study, motion information provided by improved Camshift is integrated into particle filter, such that information starvation needn’t beware any more. The experimental results in Fig. 6 have demonstrated the fact that improved method in this study could survive of occlusions with complex outside interferences. The method in this study caters various drastic environments. It maintains a high tracking precision, disregarding the tracking condition of complete, incomplete occlusions, maneuvering tracking or some occlusions of branches. The innovative method improves the traditional particle filter, in a novel way eliminating the particle degradation. As it were, numerous particles would occupy the smaller weights, contributing little to the final posterior probability. Improved Camshift combines color and motion information together, prevailing over the traditional Camshift with single cue whose extremum easily converged into one local point. In a magic way that copes with any changes of environment, e.g., the color, illumination, motion or some unpredicted shape changes. The tracking results of Camshift are taken out to predict the particles distribution, rendering the particles evolution approach authentic posterior probability with more odds. And then, a grey prediction model called GM (1,1) wields modeling method, regarding the sample data as a timevarying grey unit, i.e., the grey process. White differential equation of grey prediction model would be obtained through accumulating and decreasing process. The particular merit of GM (1,1) is the little information requirement of itself, without any quota of the distribution of sample, having solved the uncertain issues of “small sample and poor information”. In the condition of analogue interferences, the method of grey prediction model initialized by Camshift to harvest proposal distribution of particle filter could accommodate the complex tracking conditions. It will, therefore, overcome the uncertain factor of target tracking as well as maintain a high continuous robustness. CONCLUSION For the traditional video tracking, the single cue of image has been explored as a ubiquitous routine. However, in realistic world, drastic illumination variations and complete occlusions of analogue interferences occur now and then. It entails a multiple collection of data to achieve a robust tracking. In this study, generic mechanisms are introduced for data fusion within particle filter. And a tracking strategy based on particle filter is developed with data fusion of color and motion information. Motion information is added by color histogram of the target, such that Camshift would be ameliorated by color histogram in H channel in current frame. Proceeding with the outputs of improves Camshift, the proposal distribution of particle filter and the grey prediction model would be predicated successively. Once the occlusions approach, grey prediction model is altered immediately to yield proposal distribution of particle filter. In this study, a couple of confirmatory tasks have been performed. Observations show that particles evolution does approach posterior density estimation of the target state more closely. It turns out that the method in this study yields comparative satisfying results, under any condition of interferences and complete, incomplete occlusions of analogue. ACKNOWLEDGMENT This study is supported by Zhejiang Provincial Natural Science Foundation of China (No. LY13F030013, R1110502).

REFERENCES 
1: Bradski, G.R., 1998. Computer vision face tracking as a component of a perceptual user interface. Proceedings of the IEEE Workshop on Applications of Computer Vision, October 1921, 1998, Princeton, NJ., USA., pp: 214219.
2: Li, H.T., P.L. Wu and L.F. Kong, 2010. Mean shiftbased and featurerestricted particle filter for maneuver targets tracking. Control Decision, 25: 149152. Direct Link 
3: Liu, S., Y. Dang and Z. Fang, 2004. Grey Theory and Applications. Science Press, Beijing, China, ISBN: 703013351X, pp: 126133.
4: Luo, T., J.Z. Wang and P.Y. Lu, 2011. An improved particle filter tracking algorithm with background information fusion. Trans. Beijing Inst. Technol., 31: 562566.
5: Niu, C.F., D.F. Chen and Y.S. Liu, 2010. Tacking object based on SIFT features and particle filter. Robot, 32: 241247.
6: Shi, H., T. Liu, M. Li and M.J. Shen, 2012. Meanshift optimization based particle filter tracking of vehicles in lowaltitude platform. J. Jilin Univ. (Sci. Edn.), 50: 535539.
7: Sun, H.G., J. Zhang, Y.T. Liu, Q. Bu and Y.N. Xie, 2010. Optimized particle filter tracking by camshift based on multifeature. OptoElectronic Eng., 37: 16, 31. Direct Link 
8: Wang, Z., X. Yang, Y. Xu and S. Yu, 2009. CamShift guided particle filter for visual tracking. Pattern Recognit. Lett., 30: 407413. CrossRef  Direct Link 
9: Xia, Y., X.J. Wu and H.Y. Wang, 2012. An antiocclusion method for object tracking based on adaptive particle filter. J. Optoelectronics Laser, 23: 22072214.
10: Yun, X. and G. Xiao, 2011. Camshift ship tracking algorithm based on multifeature adaptive fusion. OptoElectronic Eng., 38: 5258. Direct Link 



