Particle Filter Object Tracking Algorithm Based on Sparse Representation and Nonlinear Resampling

Zheyi Fan, Shuqin Weng, Jiao Jiang, Yixuan Zhu and Zhiwen Liu

(School of Information and Electronics, Beijing Institute of Technology, Beijing 100081, China)

As an active research topic in the field of image processing and computer vision, video real-time object tracking[1]is important in establishing spatial and temporal coherent relationships of object motion states between consecutive frames. Yet it is still challenging to guarantee the stability and accuracy of tracking in complex real-world scenarios due to occlusion, illumination changes and abrupt motion[2-3]. Abrupt motions of objects, such as uncertain and fast motions, fast and high dynamic changing directions range, are ubiquitous in the scenes like sport events as well as in low frame rate videos, so tracking these kinds of objects have attracted wide attention.

However, most traditional tracking methods cannot accurately track objects with abrupt motions due to their smooth motion assumptions. Therefore, some novel methods have been proposed to handle the abrupt motion tracking. On the one hand, Kwon et al.[4]combined the Wang-Landau sampling with Markov Chain Monte Carlo (MCMC) to propose the WLMC-based tracking. Nguyen et al.[5]utilized sparse estimates of motion direction derived from local features to generate particles by MCMC, which can effectively reduce the search space and handle abrupt motions. Zhou et al.[6]proposed an adaptive stochastic approximation Monte Carlo sampling to solve the problem of abrupt motion tracking.

On the other hand, considering that particle-filtering based tracking methods[7]can be effectively applied to estimate the object motion states of nonlinear and non-Gaussian system, researchers have proposed abrupt motion tracking algorithms based on the particle filter (PF) method[8-10]. Su et al.[8]detect the regions with visual saliency as the global proposal distribution and then sample particles from it to avoid suffering from local maxima. Morimitsu et al.[9]combined frame description with attributed relational graphs with PF, to track multiple objects with abrupt motions in structured sports videos. These PF-based methods can handle abrupt motions, however, most of them cause the problem of particle diversity impoverishment.The traditional resampling process of PF duplicates particles with large weights and removes those with small weights, which leaves many repetitive particles in the sample set. Thus, the posteriori distribution of object states cannot be accurately represented by these samples. Aiming at this problem, Choi et al.[10]retained the diversity of particles through resampling particles based on the Gaussian distribution.

To better handle the problem of abrupt motions and particle diversity impoverishment in existing object tracking algorithms, an improved PF object tracking algorithm based on sparse representation and nonlinear resampling is proposed. First, considering the fact that particle weights are sparse when object moves abruptly, the sparse representation is used to compute particle weights, which can reconstruct the object of interest effectively and further predict the potential object region more accurately. Then, a nonlinear resampling process based on the nonlinear sorting strategy is proposed to reserve more kinds of valid particles, so the problem of particle diversity impoverishment can be alleviated.

1 PF Tracking Method

Based on Monte Carlo importance sampling, PF uses Bayesian estimation as the main framework to express a posteriori probability of object state. The core of PF tracking method is applying the empirical conditional probability distribution of state system to generate a set of weighted discrete particles. The weights and locations of particles are updated in each frame to estimate the object state by minimum variance. Assume xkand zkrespectively denote the object state and observation result of thekth frame. The tracking process includes the prediction and update stages.

In the prediction stage, the current object state can be predicted by previous observation results

(1)

In the update stage, a posteriori distribution can be updated by the current observation result

(2)

wherep(xk-1|z1:k-1) is the posteriori density of framek-1,p(xk|xk-1) is the transition model,p(zk|xk) is the observation model, andp(zk|z1:k-1) is a normalization constant.

(3)

(4)

2 Proposed Tracking Method

2.1 Motion model

As a basic element of PF tracking, the motion model describes the transition process between consecutive frames. The random motion model can effectively capture the motion state of object, whose motion features are difficult to be accurately gained, thereby making it suitable for abrupt motions. The definition of the random motion model is

Xk=Xk-1+Rk+Uk

(5)

where Xkis the predicted state of the interested object at timek, Ukis white Gaussian noise with zero mean, Rkis the spread radius of particles, which is proportional to the mean value of the object states changing in the previoustframes

(6)

whereCis a scaling factor.

The object is usually denoted by a rectangle, whose state can be defined as

X=(x,vx,y,vy)T

(7)

where (x,y) is the coordinate of object region center; (vx,vy) denotes the velocity of object in thexandydirections, respectively.

2.2 Observation model

The observation model describes the object appearance. A suitable observation can effectively differentiate the object from the background, which is crucial to the tracking accuracy. The color feature can be easily calculated and is insensitive to the changes of image sizes and viewing angles, so we adopt blocked color histogram[11]as the observation model. The object region is firstly partitioned into 4 sub-regions in HSV color space, and then the color histogram is extracted from each sub-region. Finally, all 4 histograms are concatenated to form a 512-bins color feature.

2.3 Weights calculation based on sparse representation

The core idea of the sparse representation classification (SRC) method is to reach the sparsest representation of the coefficient matrix when the reconstruction error is minimum. Since this method can reduce the importance of feature choice and is robust to occlusion, it has been widely applied in pattern recognition. Object tracking can be considered as a binary classification problem, which recognizes object region from background and then tracks the interested object by classification approach.

In the PF tracking framework, a weighted particle set is used to approximate a posteriori distribution of the object state. When the object moves abruptly, only a few particles close to the object have relatively large weights, while the weights of others are roughly zeros, as shown in Fig. 1. Thus, considering the fact that the particle weights have sparsity under the situation of abrupt motions, the observation model can be represented by the linear combination of the features of all particles, and the coefficients can be calculated by constrainedl1norm minimization.

Fig.1 Particle weights for a single object with abrupt motion

Assuming that M denotes the observation model extracted from the object template at initial frame, yi(i=1,2,…,N) denotes the feature extracted from theith particle region, when the background is invariant as the object moves abruptly, only a few particles match the object and other particle weights vanish. So the object model can be described by the linear representation of all particle feature vectors, namely

M=ω1y1+ω2y2+ω3y3+…+ωNyN

(8)

whereω=(ω1,ω2,ω3,…,ωN)Tis the weight vector, andNis the number of particles.

Transform Eq.(8) to al1norm problem and set each element value of the weight vector between 0 and 1. The optimization problem can then be described as

(9)

whereεis the error term, which is a user-defined small positive-valued parameter.

2.4 Nonlinear resampling

The resampling process can effectively solve the problem of particle degradation by duplicating the particles with large weights and removing the ones carrying small weights. However, the traditional resampling method duplicates or removes particles depending on their weights only, resulting in many repetitive particles in the sample set and causing particle diversity impoverishment. This can reduce the kinds of particles to a great extent and seriously influence the representation ability of object state probability distribution when the object moves abruptly. Aiming at this problem, this paper proposes an improved resampling algorithm based on a nonlinear sorting strategy. The details are as follows.

② The sorted indices of each particle are mapped to the reservation probability through a nonlinear function. And then the reservation probability is normalized by

(10)

(11)

③ The duplicated number of each particle is determined by its corresponding reservation probability and the number of all particles, namely

(12)

The proposed resampling algorithm based on the nonlinear sorting strategy allocates the reservation probability to each particle depending on its corresponding weight and avoids the situation where most particle reservation probabilities are approximately zero. The validity and diversity of particles are guaranteed.

2.5 Tracking algorithm

A robust tracking algorithm for the object with abrupt motions is proposed in this paper. The main procedures are summarized as follows.

Step1Initialization

② The motion model of object is established by Eq.(5).

③ The observation model of the initial object region is established by extracting its color features.

Step2Object tracking

① The new particle set in thetth frame is predicted by Eq.(5).

② The color features of particle regions are extracted and the corresponding weight of each particle is calculated by Eq.(9).

③ The weights are normalized by

(13)

④ The motion state of the tracked object is estimated by

(14)

⑤ Particles are resampled based on our proposed algorithm in section 2.4.

⑥t=t+1, turn to ①.

3 Experiments and Analysis

In this section, two experiments are described to prove the effectiveness of the proposed method. First, a single moving point tracking program is designed to compare the proposed nonlinear resampling with other resampling algorithms. Then, the tracking experiments are conducted on videos containing objects with different kinds of abrupt motions, and the tracking results are compared with other approaches. All experimented are performed by MATLAB R2014a on a 3.10 GHz Intel Core computer with 4 GB of RAM.

3.1 Performance of the nonlinear resampling

First, we design a tracking program based on a one-dimensional system to compare the proposed nonlinear resampling with some typical resampling methods, like residual resampling, multinomial resampling, systematic resampling, Gaussian distribution[10]resampling and partial systematic[12]resampling. The number of particles isN=500 and the state vector is

(15)

(16)

wherex0～N(0,5),nk～N(0,10) andvk～N(0,1) are white Gaussian noises. The tracking errors are compared in Fig.2. Since our resampling strategy effectively ensures the diversity of particles during the tracking process, it can obtain better tracking results with smaller errors than other methods.

Fig.2 Comparisons of the tracking errors with different resampling methods

The root mean square error (RMSE) is calculated to quantitatively evaluate the performance of each resampling method. The RMSE results obtained by 6 kinds of resampling strategies are listed in Tab.1. The results demonstrate that our nonlinear resampling has the smallest RMSE value.

3.2 Video object tracking results

Tracking experiments are conducted on several videos including various abrupt motions, such as low frame rate videos, sudden dynamic changes and multi-cameras switching. The tracking results are compared among the traditional PF, WLMC[4]and our proposed method. The number of particles isN=500 and the observation model is blocked color histogram feature.

Tab.1 RMSE results of 6 resampling methods

Fig.3 Tracking results of groundtruth (solid line), our algorithm (dotted line), the traditional PF (dash dot line) and WLMC (dashed line) on video sequences with various kinds of abrupt motions

The tracking results of each method are shown in Fig. 3. Fig. 3a and Fig. 3b are Face[13]and Animal scenarios for sudden dynamic changes. The tracked object in video Face is a human face that moves left and right rapidly, and the target in video Animal jumps fast between consecutive two frames. Fig. 3c is a Boxing sport event in which the camera switches 8 times. Fig. 3d is a low frame rate video of Tennis, constructed manually by keeping one in every 35 frames in this experiment, so a large shift of object position between adjacent frames exists. The tracking results reveal that our proposed method can predict and track the object of interest more successfully owing to the effectiveness of the proposed weight calculation method and nonlinear resampling. The traditional PF, by contrast, cannot accurately track the object due to its smooth motion assumption. Although WLMC searches the object in the whole state space, it is unstable throughout the tracking process and usually deviates to other wrong locations.

To quantitatively analyze the results of different methods mentioned above, success rate is used to evaluate the performance. If the center of the ground truth is in the estimated rectangle, the object is considered accurately tracked at that frame[6]. The success rate is represented by the ratio between the number of accurately tracked frames and the number of total frames, and is shown in Tab.2. Obviously, the object with abrupt motion is difficult to track successfully, so the success rates are relatively low. But our algorithm shows better tracking performance handling this challenge. Tab.3 shows the average run time of each algorithm for the test videos. The time cost of our algorithm is longer than the traditional PF method for the introduction of sparse representation. However, the WLMC needs longer time due to its global search strategy. Thus, our method can obtain better tracking results and has a relatively high efficiency.

Tab.2 Success rate of 3 methods on test videos %

Tab.3 Run time of 3 algorithms on test videos s

4 Conclusion

To track the objects with abrupt motions accurately, sparse representation is introduced to calculate the particle weights byl1norm minimization, which can reconstruct the interested object better. Moreover, a nonlinear resampling strategy is proposed to improve the traditional resampling process. This method gains the duplicated number of each particle depending on its corresponding reservation probability and the number of all particles in the set, so it effectively maintains the diversity of particles. Experiments show that the proposed resampling algorithm has improved performance compared to previous algorithms, and our tracking method is robust to abrupt motions.

[1] Li M, Fan Z Y, Liu Z W. An improved visual tracking algorithm based on particle filter[C]∥2013 IEEE International Conference of IEEE Region 10, Xi’an, Shaanxi, China, 2013:1-4.

[2] Cai Z W, Wen L Y, Lei Z, et al. Robust deformable and occluded object tracking with dynamic graph[J]. IEEE Transaction on Image Processing, 2014, 23(12): 5497-5509.

[3] Kwon J, Lee K M.Tracking by sampling and integrating multiple trackers[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(7): 1428-1441.

[4] Kwon J, Lee K M. Wang-Landau Monte Carlo-based tracking methods for abrupt motions[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013,35(4): 1011-1024.

[5] Nguyen T, Pridmore T P. Tracking using multiple linear searches and motion direction sampling[C]∥2014 22nd International Conference on Pattern Recognition, Stockholm, Sweden, 2014: 2191-2196.

[6] Zhou X, Lu Y. Abrupt motion tracking via adaptive stochastic approximation Monte Carlo sampling[C]∥2010 IEEE Conference on Computer Vision and Pattern Recognition,San Francisco, CA, USA, 2010: 1847-1854.

[7] Doucet A, Gordon N J. Sequential monte carlo methods in practice[M]. Berlin,Germany: Springer, 2001.

[8] Su Y, Zhao Q, Zhao L, et al. Abrupt motion tracking using a visual saliency embedded particle filter[J]. Pattern Recognition, 2014, 47(5): 1826-1834.

[9] Morimitsu H, Bloch I. Attributed graphs for tracking multiple objects in structured sports videos[C]∥Proceedings of the IEEE International Conference on Computer Vision Workshops, Santiago, Chile, 2015: 34-42.

[10] Choi H D, Ahn C K, Lim M T. Gaussian distribution resampling algorithm of particle filter[C]∥Proceedings of the International Conference on Control, Automation and Systems, Gwangju, Korea, 2013.

[11] Li Mo, Yin Licheng, Yan Tianyi.Particle filter tracking algorithm based on integral histogram and improved resampling[J]. Optics and Electronic Technology, 2013, 11(3): 45-48. (in Chinese)

[12] Yu J X, Liu W J, Tang Y L. Improved particle filter algorithms based on partial systematic resampling[C] ∥ 2010 IEEE International Conference on Intelligent Computing and Intelligent Systems, Xiamen, China, 2010: 483-487.

[13] Birchfield S. Elliptical head tracking using intensity gradients andcolor histograms[C] ∥1998 IEEE Computer Society Conferenceon Computer Vision and Pattern Recognition, Santa Barbara, CA, USA, 1998: 232-237.