INTRODUCTION

With the rapid development of autopilot technology, intelligent security technology and intelligent robot technology, target tracking technology based on machine vision has gradually entered people’s daily life. Vision-based detection technology has played an important role in modern industrial production.

Recently years, many experts and scholars have been studying target tracking and obtained obtain some achievements on research. The existing target tracking techniques include appearance model [1], mean shift [2], Kalman filter [3], particle filter and their extended algorithm [4]. In addition, traditional methods such as background difference, inter-frame difference, sparse representation, compressed perception [5, 6] were widely used in the target tracking. Although these methods can be used to tracking the dynamic object, they failed to address the issues of significant measurement noise, which can reduce real-time and accuracy, especially in the dynamic unstructured complex background. Therefore, the target tracking technology in dynamic and complex background is still a problem to be solved in the field of machine vision.

In the process of continuous target tracking in complex background based on traditional particle filter [7], it often occurs that the loss of particle efficiency and diversity caused by sample dilution, because of the constraints of dynamic unstructured complex background, including: the change of light environment, the similar moving targets with the same moving state in the background, changes in the appearance and scale characteristics of the targets, being blocked of the target, and the noise caused by the characteristics of optical imaging sensors.

Under the case of fast moving object tracking in dynamic unstructured complex background, for the purpose of solving the problem of particle degradation above, not only should a large number of particles be used to describe the posteriori probability distribution of the state, but the random prediction for the state of the target object is necessary. This will lead to a significant increase in compute and algorithm complexity [8].

In view of the above-mentioned problem, this paper makes an important improvement to the traditional particle filter algorithm. Aimed at obtaining an efficient sparse particle distribution and better simulate the real moving state of the target, Gaussian clustering algorithm based on maximum fuzzy entropy was used to classify the particle set [9]. At the same time, adaptive resampling was adopted to improve the accuracy and robustness of particle filter tracking algorithm.

PARTICLE FILTER (PF)

Particle filter algorithm comes from the idea of Monte Carlo simulation, which replaces the System state variables by discrete sampling pots (particle). By means of modifying the original distribution according to the weight and position of particles, it approximates to the real posterior probability density function. Moreover, it use the sample mean take place of the integral operation, and get the best estimation of the system state variables.

Compared with other filtering methods, particle filter has the unique characteristics of non-parametric, which is not limited by system’s transition model and prior probability distribution. Therefore, it has more extensive modeling performance by contrast with Gaussian model and Kalman model.

State equation of dynamic system has the following form:

$$X(k) = f(X(k - 1),W(k)),$$
((1))
$$Z(k) = h(X(k),V(k)),$$
((2))

where \(X(k)\) denotes the system state variables in the moment k, and \(Z(k)\) is the measurement vector in the moment of k; \(p({{X}_{k}}\,|\,{{X}_{{k - 1}}})\) represents the state transfer model, \(p({{Z}_{k}}\,|\,{{X}_{k}})\) is state measurement model. Posterior probability of state is expressed as \(p({{X}_{{0:k}}}\,|\,{{Z}_{{1:k}}})\). The particle filter algorithm steps are as follows.

Step 1. The particle \(X_{0}^{{\left( i \right)}}\) is extracted from the state prior distribution \(p({{X}_{0}})\).

Where the state prior probability is denoted as p(X0).

Step 2. The weight of particle \(\omega _{k}^{{\left( i \right)}}\) is calculated by:

$$\omega _{k}^{{\left( i \right)}} = \omega _{{k - 1}}^{{\left( i \right)}}\frac{{p({{Z}_{k}}\,|\,X_{k}^{{\left( i \right)}})p(X_{k}^{{\left( i \right)}}\,|\,X_{{k - 1}}^{{\left( i \right)}})}}{{q(X_{k}^{{\left( i \right)}}\,|\,X_{{k - 1}}^{{\left( i \right)}},{{Z}_{{1:k}}})}},$$
((3))

where \(q({{X}_{{0:k}}}\,|\,{{Z}_{{1:k}}})\) represents sampling density of importance. \({{\tilde {w}}_{k}}(X_{{0:k}}^{{\left( i \right)}})\) denotes normalized weight:

$${{\tilde {w}}_{k}}(X_{{0:k}}^{{\left( i \right)}}) = \frac{{{{w}_{k}}(X_{{0:k}}^{{\left( i \right)}})}}{{\sum\limits_{i = 1}^N {{{w}_{k}}(X_{{0:k}}^{{\left( i \right)}})} }}.$$
((4))

Step 3. Importance resampling.

The particle set before resampling is \(\{ x_{{0:k}}^{{\left( i \right)}},w_{k}^{{\left( i \right)}}\} \)\(i = 1,2, \ldots ,N\). For the purpose of preventing the particle from degradation, new particle set is given by reproducing the particles which had larger weight, eliminating the smaller on the contrary.

Step 4. Prediction.

The resampled particles approximate a posterior distribution of the system state. According to the Monte Carlo method, the estimation of filter can be given:

$$\begin{gathered} {\text{E(}}{{g}_{k}}{\text{(}}{{X}_{{0:k}}}{\text{))}} = \int {{{g}_{k}}({{X}_{{0:k}}})p({{X}_{{0:k}}}\,|\,{{Z}_{{1:k}}})d{{X}_{{0:k}}}} \\ \approx \;\frac{1}{N}\mathop \sum \limits_{i = 1}^N \,{{g}_{k}}(X_{{0:k}}^{{\left( i \right)}}). \\ \end{gathered} $$
((5))

PF TRACKING ALGORITHM BASED ON FUSION GAUSSIAN CLUSTERING

The problem of target detection and tracking in dynamic background is in urgent need of solution. Therefore, what we need to consider when designing the algorithm is the disturbance of environmental factors and self-factors to dynamic target. While the algorithm has the necessary robustness, it should also take into account the necessary real-time performance. In a word, the dependence of the target model on the amount of data and computation should be considered for the target detection and tracking scheme when using traditional particle filter algorithm.

In this paper, Gaussian clustering is introduced into particle filter, considering the rationality of spatial particle distribution, the particle is optimized by clustering algorithm before updating. By substituting the centroid of class for the original particles, it not only reduces the number of particles and computation, but also smoothes the weight of the particles in the cluster. In this way, the problem of particle depletion and poor diversity can be solved effectively. Moreover, in multi-target tracking, Gaussian clustering can be used to divide the received observations into some classes first, so that later prediction proceeded smoothly and efficiently.

3.1 Maximum Fuzzy Entropy Gaussian Clustering Algorithm

Take multitarget tracking as example, there are \(C({{c}_{j}}\), \(j = 1,2, \ldots ,c)\) sample goals, where \(({{x}_{1}},{{x}_{2}}, \ldots ,{{x}_{m}})\) is the observations in the n-dimensional space, clustering fuzzy membership is calculated by:

$${{\mu }_{{ij}}} = 1,\quad \forall {{\mu }_{{ij}}} \in [0,1],$$
((6))

where cj are cluster center, μij denotes the probability that xi is subordinate to cj. \(d({{x}_{i}},{{c}_{j}})\) represents the Euclidean distance between xi and cj

$$E = \mathop \sum \limits_{i = 1}^m \,\mathop \sum \limits_{j = 1}^c \,{{\mu }_{{ij}}}\;\centerdot \;d{{({{x}_{i}},{{c}_{j}})}^{2}}.$$
((7))

According to Shannon entropy theory, the relationship between data points and cluster centers can be described by the membership relationship of the maximum entropy. Therefore, the entropy value of membership is calculated by equation as follows:

$$H = H({{\mu }_{{ij}}}) = - \mathop \sum \limits_{i = 1}^m \,\mathop \sum \limits_{j = 1}^c \,{{\mu }_{{ij}}}\ln {{\mu }_{{ij}}}.$$
((8))

In accordance with the restrictions above, optimization objective function can be defined as:

$$\begin{gathered} J(U,C) = H({{\mu }_{{ij}}}) - \mathop \sum \limits_{i = 1}^m \,\sigma \,\mathop \sum \limits_{j = 1}^c \,{{\mu }_{{ij}}}d{{({{x}_{i}},{{c}_{j}})}^{2}} \\ + \;\mathop \sum \limits_{i = 1}^m \,{\lambda }\left( {\mathop \sum \limits_{j = 1}^c - 1} \right), \\ \end{gathered} $$
((9))

where σ and λ denote the Lagrange multiplier, the minimal deviation estimation of μij can be calculated as:

$$\begin{gathered} {{\mu }_{{ij}}} = \frac{{\exp \left( { - \frac{{d{{{({{x}_{i}},{{c}_{j}})}}^{2}}}}{{2{{\sigma }^{2}}}}} \right)}}{{\sum\limits_{j = 1}^c {\exp \left( { - \frac{{d{{{({{x}_{i}},{{c}_{j}})}}^{2}}}}{{2{{\sigma }^{2}}}}} \right)} }}, \\ i \in [1,{{m}_{k}}],\quad j \in [1,c]. \\ \end{gathered} $$
((10))

Figure 1 shows the process of Gaussian cluster based on maximum fuzzy entropy.

Fig. 1.
figure 1

Gaussian clustering based on maximum fuzzy entropy.

Full size image

3.2 Adaptive Resampling Particle Filtering Algorithm

In order to track the target object effectively in the dynamic unstructured complex background, a large number of particle resources are needed when designing target tracking model based on the PF algorithm. However, in general, the spatial distribution of particles present stacking, which leads to redundancy of effective information to some extent. These redundant data not only affect the accuracy of the results, but also cause great waste to the system resources. Therefore, in this paper, an adaptive resampling method has been proposed to realize the secondary sampling in PF algorithm.

The purpose of resampling is to prevent the weight of particles from concentrating too much on a few particles, which results in the reduction of the effectiveness of other particles and the phenomenon of particle depletion in the process of target tracking. In order to obtain an efficient sparse particle distribution, on the basis of the first resampling, the particles have been optimized. In addition, without losing the particle efficiency, the effective information is aggregated and redundant data is eliminated. Next, the particles are resampled for the second time, the use of optimized and streamlined data will improve the real-time, effectiveness, robustness and accuracy greatly in the target tracking calculation.

At the same time, owing to the introduction of adaptive resampling, the computation of the algorithm is greatly increased. Therefore, the gradient method is considered to improve the speed of the algorithm and optimize the algorithm without losing the tracking quality [10].

4. EXPERIMENTS AND ANALYSIS

4.1 Analysis Based on Simulation

Taking single target tracking as an example, five algorithms are simulated and analyzed in this paper. Supposing there is a probe point and a dynamic target in the space. The equation of state of the system can be expressed as:

$$X(k + 1) = \varnothing X(k) + \Gamma w(k),$$
((11))
$$Z(k) = HX(k) + {v}(k),$$
((12))
$$X(k) = [{{x}_{p}}(k),{{y}_{p}}(k)],$$
((13))
$$Z(k)\, = \,\sqrt {{{{({{x}_{p}}(k) - \,{{x}_{p}}(0))}}^{2}}\, + {{{({{y}_{p}}(k) - \,{{y}_{p}}(0))}}^{2}}} + {v}(k).$$
((14))

Figure 2 shows the results of simulating and tracking based on five algorithms. With the number of samples increasing, the depletion and the poor diversity of particles exacerbated. As we can see, the effect of traditional particle filtering decreased sharply as samples increase. In addition, it is obvious that the problem above can be solved with the proposed algorithm. At the same time, in order to explain the accuracy of the algorithm persuasively, the particle filter algorithm based on Mean-shift is used to compare with the proposed algorithm. Although the introduction of Mean-shift improves the tracking performance to some extent, it doesn’t work as well as the proposed algorithm. Finally, in order to illustrate the practicability of proposed algorithm in target tracking, it is compared with other target tracking algorithms including PDA (probabilistic data association) and FCM-PDA (Fuzzy c-means-PDA) [11]. It can be seen from Fig. 2 that both the proposed algorithm and PDA have high tracking accuracy while FCM-PDA has a certain loss of precision.

Fig. 2.
figure 2

(Color online) Tracking effect of five algorithms.

Full size image

Table 1 lists the prediction error of five kinds of algorithm. It can be concluded that the proposed algorithm deal with particle depletion effectively, which has high accuracy in dynamic tracking.

Table 1. Prediction error of five algorithms
Full size table

On the basis of comparing the tracking accuracy, in order to illustrate the feasibility of the algorithm in target tracking, the computational time of the five algorithms is also compared in this paper. As can be seen from Fig. 3, the proposed algorithm not only has high tracking accuracy, but also can reduce the computational complexity by using the gradient method. Although the accuracy of PDA algorithm is high, its computation is most complex. FCM-PDA can reduce the complexity of calculation, but its accuracy is still difficult to guarantee.

Fig. 3.
figure 3

(Color online) Computation time of five algorithms.

Full size image

According to the simulation analysis above, it can be concluded that the proposed algorithm can solve the particle depletion problem, improve the tracking accuracy and calculation speed effectively.

4.2 Analysis Based on Experiments

In order to verify the effectiveness of this algorithm, soccer goalie robot system designed by the research is used in this paper. In the course of experiment, the proposed algorithm in this paper is used to track the soccer in flight. Based on the tracking results of the algorithm, the goalkeeper robot can predict the space coordinates of the soccer, then control the baffle motion to the corresponding position and block the ball out.

Figure 4 shows the effect of soccer target tracking based on improved PF algorithm. The PF algorithm based on the maximum fuzzy entropy Gaussian clustering not only can reduce the redundant information of particles, but solve the problem of particle depletion. In addition, it promotes the tracking accuracy and real-time performance of the algorithm, which is suitable for the target tracking of fast-moving objects.

Fig. 4.
figure 4

(Color online) Tracking effect based on improved PF algorithm.

Full size image

Figure 5 shows the soccer gatekeeper controlling the movement of the baffle to the position of the football, then blocking the football out according to the particle filter algorithm. It can be seen from the figure that the algorithm can track fast-moving football efficiently, stably and accurately.

Fig. 5.
figure 5

(Color online) The process of robot blocking the football.

Full size image

CONCLUSIONS

In order to solve the problem of particle depletion and poor diversity in dynamic target tracking, this paper introduce the Gaussian clustering into particle filter. Dividing the particles into several sets based on maximum fuzzy entropy Gaussian clustering algorithm, it can overcome the particle depletion effectively. At the same time, the application efficiency and calculating speed of particles can be further improved by adaptive repeated sampling. The experimental results show that the accuracy, efficiency and robustness of the algorithm have been promoted greatly by the improved PF algorithm.