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.
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 so-called 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 anti-occlusion ability of tracking system. Luo et al. (2011) took advantage of log-likelihood 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 eight-connected component after binaryzation of difference frame. After corrosions, the motion information Im 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 Ih in H channel is obtained |
| • | To calculate zero-order moment of moving target based on motion information and color probability distribution. The first-order of x and y is defined as: |
| (1) |
| (2) |
| (3) |
| • | The centroid position of searching window is defined as: |
| (4) |
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 first-order X(1) = (x(1) (1), x(1) (2),..., x(1) (n)), then:
| (5) |
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:
| (6) |
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:
| (7) |
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 non-Gauss 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 (x0, y0) |
| • | The particles set (xmk-1, ymk-1) 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 wmk-1 of each particle. The probability density function of particles observation is defined as: |
| (8) |
| (9) |
where, k-1 represents the number of current frame and m = 1,2,…,N denotes the particle number
| • | After an AND process between motion information lm and color probability distribution ln, consecutive non-zero 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 {(xmk, ymk) is reshuffled at random. Probability density function of observation value of particles after evolution is defined as: |
| (10) |
And the particles weight wmk after the resampling is defined as:
| (11) |
| • | Through a weighted sum of particles, the target center (x0new, y0new) of particles in the next frame will thus be evaluated as: |
| (12) |
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 real-time 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(a-b): | 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(a-b): | 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(a-b): | 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 multi-target 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(a-b): | 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(a-c): | 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(a-c): | 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 time-varying 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).