Target‐tracking algorithm based on improved probabilistic data association

Abstract

When tracking a single manoeuvring target in clutter environment, when the number of effective measurements within the detection threshold is small, it usually has a greater and more obvious impact on target‐tracking results. If the observation data error is large at this time, the tracking position and speed error will be larger. To solve this problem, a target‐tracking algorithm based on improved probabilistic data association is proposed in this paper. By dynamically adjusting the detection threshold, the effective quantity within the detection threshold of each frame is basically stable. Simulation results show that the improved algorithm is more accurate in location and speed than the traditional probabilistic data association method and Kalman filter, and the availability and effectiveness of the algorithm are verified.

INTRODUCTION

Target tracking refers to obtaining the motion state data of the target with the help of detectors or perceptions [1], including state vector data such as position and speed, so as to estimate the motion state or related parameters of the target at the next moment. When there are multiple observed targets, the corresponding target of the obtained motion state data needs to be determined [2]. In the 1950s, the research on target tracking started. Since the successful development and use of Doppler radar in the 1960s, the research on target-tracking technology has been rapidly developed [3]. Initially, target-tracking technology was mainly used in the military. With the continuous progress and development of science and technology, target-tracking technology is indispensable to many military and civil application scenarios such as aerial early warning, battlefield surveillance, ocean monitoring, robotics, traffic control and so on. Target-tracking technology is a comprehensive application of high technology, its research areas in artificial intelligence, pattern recognition, computer vision, project control and multiple disciplines such as mathematics, although in recent years the breakthrough progress has been made in every field of research, but with it, and also had the new change to the requirement of target tracking, for example in the real-time and accuracy requirements more stringent, etc. Therefore, the research on target tracking has been one of the hot topics in the world.

Target-tracking technology is one of the most important contents of radar field of research, for example, using the theory of parameter estimation to obtain motion parameters such as position, velocity and acceleration, preprocessing, selecting and tracking the moving target, estimating the shape and related physical properties of the target, a series of requirements are inseparable from the support of target-tracking technology [4]. In the early stage, the target tracking mainly used analog computing devices for data processing, so the data-processing process was often very slow; it was difficult to meet the real-time requirements. At present, modern radar usually uses digital computers to complete data processing, timeliness has been greatly improved. According to the representation and similarity measurement of moving objects, moving object-tracking algorithms can be divided into four categories: active contour-based tracking, feature-based tracking, region-based tracking and model-based tracking. The accuracy and robustness of the tracking algorithms largely depend on the representation of the moving target and the definition of similarity measure, the real-time performance of the tracking algorithm depends on the matching search strategy and filtering prediction algorithm. The active contour model proposed by Kass et al., namely Snake model [5], is a deformable curve defined in the image domain. By minimizing its energy function, the dynamic contour gradually adjusts its shape to be consistent with the target contour, which is also called Snake curve. The feature matching-based tracking method does not focus on the whole feature of the moving target, but only uses some salient features of the target image to track [6]. It is assumed that the moving object can be represented by a unique feature set and it is considered that the moving object is tracked if the corresponding feature set is found. In addition to using a single feature to track, multiple feature information can be fused together as a tracking feature. The region-driven tracking algorithm uses the template containing the target, which can be obtained through image segmentation or artificially determined in advance [7]. The template is usually a rectangle slightly larger than the target, or it can be irregular shape. In the sequence of images, the target is tracked by the correlation algorithm. The advantage of this algorithm is that when the target is not blocked, the tracking accuracy is very high and the tracking is very stable. But its disadvantage is time-consuming, especially when the search area is large. Besides, the algorithm is adapted to the certain situation that the target deformation is not large, and there could not be too much occlusion; otherwise, the decrease in the correlation accuracy will cause the loss of the target. In recent years, more attention has been paid to region-based tracking methods on how to deal with template changes, which are caused by posture changes of moving targets. If the posture changes of moving targets can be predicted correctly, stable tracking can be achieved. Model-based tracking is to build a model of the tracked target through certain prior knowledge, and then update the model in real time by matching the tracking target. Accurate building of the motion model is the key to the success of model matching. This method is not easy to be affected by the observation angle, and has strong robustness, high precision of model matching and tracking, and is suitable for various motion changes of manoeuvring targets with strong anti-interference ability. For rigid target, its motion state transformation is mainly translation, rotation and so on, so the method can be used to achieve target tracking. However, it is not only rigid bodies but also non-rigid bodies that are tracked in practical applications. It is not easy to obtain the exact geometric model of the target. Due to the complexity of calculation and analysis and the slow operation speed, the updating of the model is complicated and the real-time performance is poor.

Although there are a lot of research results, it is still difficult to achieve real-time and accurate tracking under complex conditions. In this paper, a target-tracking algorithm based on improved probabilistic data association is proposed. By dynamically adjusting the detection threshold, the effective quantity within the detection threshold of each frame is basically stable.

DATA ASSOCIATION

When using the radar to track the target, in the single target and clutter environment, there is only one dot in the relative tracking gate of the target, and only the target tracking is involved. However, under the condition of multiple targets or single target with clutter, multiple point marks on a single target related door or single point trace into multiple waves in the intersection area of the door would appear [8]. In this case, it is difficult to continuously track the target directly, so data association needs to be involved [9]. Data association is the process to establish the relationship between radar data measured at one time and data measured at other times, so as to judge whether the data comes from the same target. In other words, the uncertain observation is associated with the track, and the measured data from the sensor is matched with the known or determined track. Data association is the key technology of information fusion [10], which is applied to track initiation, centralize and distribute target tracking.

Classical data association algorithms include nearest-neighbour algorithm [11, 12], probabilistic data association algorithm (PDA) [13], joint probabilistic data association algorithm (JPDA) [14] and so on. The first step of the nearest-neighbour algorithm is to set up a tracking gate, and the echoes obtained by the initial screening of the tracking gate become candidate echoes, so as to limit the number of echoes participating in the correlation discrimination. Tracking gate refers to a sub-space of the tracking space; the centre is located in the prediction location of the tracked target. The size of the tracking door should be able to receive the correct echo with a certain probability, and the measurement falling into the tracking door is the candidate echo. If there is only one measurement falling into a relative wave, then this measurement can be directly used to track updates. However, if more than one echo fall within the relevant tracking gate of the tracked target, the echo with the smallest statistical distance should be taken as the target echo. The advantage of the nearest-neighbour method is that it is easy to calculate, but the disadvantage is that the candidate echo which is the closest to the target's predicted position may not be the real echo of the target in multi-echo environment. Therefore, this method is only suitable for tracking non-manoeuvring targets in sparse echo environment. Both PDA and JPDA calculate the correct probability of different measurements coming from the target at the current moment in the first step. Then these probabilities are weighed to obtain an estimate of the target's state. The difference is that PDA is a suboptimal filtering method, which only decomposes new measurements. PDA is mainly used to solve single target-tracking problem in clutter environment. JPDA is mainly aimed at dense target environment, so it is necessary to consider the calculation of interconnection probability in the case of multiple tracks competing with the same measurement. The PDA algorithm cannot accurately calculate the effect of common echo on track update in the intersection area of multiple targets associated gates, so the tracking performance of PDA is not ideal when the echo is dense. The JPDA algorithm uses the point traces in the current scanning cycle within the tracking threshold, takes the probability that the point traces in the tracking come from the target as the weight, calculates the correlation probability between the point traces and the corresponding track, and uses the correlation probability to sum the current point traces to complete the track correction. In the actual calculation, the weights are obtained by finding out the combined set of all possible point traces and track, and calculating the probability of point traces and track-associated set. The difference between JPDA and PDA is that the calculation of probability of probability interconnection is different, so the complexity and calculation amount of the JPDA algorithm are higher than the PDA algorithm [15]. PDA and JPDA are similar in process which is divided into two parts: joint event generation and association probability calculation. JPDA filter is basically similar to PDA [16] filter except the calculation of association probability. JPDA calculates probabilities as joint probabilities because measurements can come from multiple targets.

TARGET-TRACKING MODEL BASED ON IMPROVED PROBABILISTIC DATA ASSOCIATION

Tracking model

A common time-varying system model is established, in which the state transition equation is as follows: 1 $$$\begin{equation}{\;}{X_k} = \;A{X_{k - 1}} + B{\mu _k} + {\omega _k}\end{equation}$$$2 $$$\begin{equation}{\omega _k}\sim N\left( {0,Q} \right)\end{equation}$$$where $${X_k}$$ represents the state at the moment k, A represents the state transition matrix, describing the state transition relationship of two adjacent frames, B represents the control matrix, and together with the control vector $${\mu _k}$$, describes the input control in the state transition process, $${\omega _k}$$ follows the Gaussian distribution, and Q represents the process noise covariance.

The measurement equation is as follows: 3 $$$\begin{equation}{}{Z_k} = H{X_k} + {\upsilon _k}\end{equation}$$$4 $$$\begin{equation}{\upsilon _k}\sim N\left( {0,R} \right)\end{equation}$$$where $${Z_k}$$represents the measurement of this frame, H represents the measurement matrix, describing the mapping relationship between the target state and the measurement space; $${\upsilon _k}$$ follows a Gaussian distribution, and R represents the covariance of measured noise and describes the influence degree of noise in the mapping process.

Generally, $$X_{k - 1}^ + $$ represents a posterior state estimation, that is, the optimal state estimation of the $$( {k - 1} )$$th frame has been obtained and is the optimal result obtained by the fusion of the previous $$( {k - 1} )$$th frame. $$X_{k - 1}^ - $$ represents the prior state estimation of the $$( {k - 1} )$$th frame. Since $${Z_k}$$ is not measured by the fusion of this frame, ‘–’ represents the lack of this frame information.

PDA is to calculate a probability $${\beta _{i( k )}}$$ for each valid measurement that passes the detection threshold of the k th frame, and combine its innovation to calculate a new most measurement, which is usually a virtual measurement. 5 $$$\begin{equation}{\beta _i}\left( k \right) = \frac{{{e_i}}}{{b + \mathop \sum \nolimits_{j = 1}^{{m_k}} {e_i}}}\;\;i\; = \;1,2 \ldots ,{m_k}\end{equation}$$$6 $$$\begin{equation}{e_i} \buildrel \Delta \over = exp\left\{ { - \frac{1}{2}v_i^{\prime}\left( k \right){S^{ - 1}}\left( k \right){\upsilon _i}\left( k \right)} \right\}\end{equation}$$$7 $$$\begin{eqnarray} b &\buildrel \Delta \over =& \;\frac{{\lambda {{\left| {2\pi S\left( k \right)} \right|}^{\frac{1}{2}}}\left( {1 - {P_D}{P_G}} \right)}}{{{P_D}}} \nonumber \\ &=& {\left| {2\pi } \right|^{\frac{1}{2}}}\;{\gamma ^{ - \frac{{{n_z}}}{2}}}\frac{{\lambda {V_k}\left( {1 - {P_D}{P_G}} \right)/{P_D}}}{{{c_n}}} \end{eqnarray}$$$where $$S( k )$$ represents the innovation covariance; $${P_D}$$ represents the detection probability of the target, which is determined by the sensor performance and is a known value; $${P_G}$$ represents the probability of the target appearing in the detection gate, which is related to the design form of the detection gate. $${V_k}$$ represents the equivalent innovation vector.

Design of dynamic detection gate

Due to the continuity of target movement and radar-tracking process, in a similar period of time, there is little difference in the measured number of passing detection threshold, and there is a certain correlation between the target motion states determined in two adjacent frames. On this basis, dynamic detection gate is designed and designed.

Usually, the elliptic tracking gates are used to filter the measurements falling into the current track prediction position. There will be many measurements $$Z_k^1$$ passing the detection threshold in the k th frame, and the measurement that passes the ellipse tracking gate is called effective measurement, namely 8 $$$\begin{equation}{[ {{Z_k} - {Z_{k|k - 1}}} ]^T}S{\left( k \right)^{ - 1}}[ {{Z_k} - {Z_{k|k - 1}}} ] \le \gamma \end{equation}$$$where $${Z_{{\mathrm{k}}|{\mathrm{k}} - 1}}$$ is priori measurement estimations, γ is gate of wave, $${Z_{{\mathrm{k}}|{\mathrm{k}} - 1}}$$ and S(k) are determined by Kalman filtering, gamma probability $${P_G}$$ determined according to the set of tracking gate, when the target area is a two-dimensional plane, 9 $$$\begin{equation}{\;}{P_G} = \;1 - exp\left( { - \gamma /2} \right)\end{equation}$$$

According to statistics, the probability P_G of a two-dimensional measurement falling into a gate is shown in Table 1.

TABLE 1 Probability P_G with different γ.

γ	1	4	9	16	25
$$g{\;} = \sqrt \gamma {\;}$$	1	2	3	4	5
$${P_G}$$	0.393	0.865	0.989	0.9997	1.0

For the k th frame, the initial detection gate is the same as the $$( {k - 1} )$$th frame; then the number of effective measurements passing the detection threshold is calculated. The threshold 1 is set for the difference in the effective measured quantity between two frames. If the difference of the effective measurements between two frames does not exceed the set threshold, the detection threshold of the k th frame is the same as the $$( {k - 1} )$$th frame. If the threshold is exceeded, the detection threshold is appropriately adjusted according to the characteristics of target motion state. That is, when the effective measurement of the detection threshold passing the $$( {k - 1} )$$th frame is smaller than the $$( {k - 1} )$$th frame and exceeds the threshold, the detection threshold is enlarged to a certain extent according to the set proportion and the motion state of the target in the previous frame. When the effective measurement of the $$( {k - 1} )$$th frame passing the detection threshold is larger than the $$( {k - 1} )$$th frame and exceeds the threshold, the detection threshold is reduced proportionally so as to realize the dynamic change of the detection gate.

Suppose that the numbers of effective measurements passing the detection threshold of $$( {k - 1} )$$th frame and k th frame are $${n_{k - 1}}$$ and $${n_k}$$ respectively, if 10 $$$\begin{equation}\left| {{n_{k - 1}} - {n_k}} \right| > f\end{equation}$$$

Then 11 $$$\begin{equation}\;{\gamma _k} = \;\alpha \frac{{{n_{k - 1}}}}{{{n_k}}}{\gamma _{k - 1}}\end{equation}$$$where α represents the dynamic detection coefficient and $$\alpha > 0$$.

It can be seen from the algorithm steps that the dynamic detection gate improves the algorithm performance by affecting the screening range of the effective measurement and has no influence on the subsequent calculation of the algorithm, which is equivalent to preprocessing the effective measurement before data association, without increasing the complexity of the algorithm on the premise of improving the accuracy of the algorithm. In addition, the dynamic detection gate can also be combined with other algorithms, which has good mobility.

SIMULATION AND RESULT ANALYSIS

Simulation

Suppose the tracked target is moving uniformly in the plane, and the discretized system equation and the target equation of state are as follows: 12 $$$\begin{equation}X\;\left( {k + 1} \right) = \;F\left( k \right)X\left( k \right)\end{equation}$$$13 $$$\begin{equation}X = [ {x\;\dot x\;y\;\dot y} ]\end{equation}$$$

The state transition matrix is as follows: 14 $$$\begin{equation}F\left( k \right) = \left[ { \def\eqcellsep{&}\begin{array}{@{}*{4}{c}@{}} 1&\quad T&\quad 0&\quad 0\\ 0&\quad 1&\quad 0&\quad 0\\ 0&\quad 0&\quad 1&\quad T\\ 0&\quad 0&\quad 0&\quad 1 \end{array} } \right]\;\end{equation}$$$in which $$T{\;} = {\;}1{\mathrm{s}}$$. The initial state is $$X( 0 ) = [ {200{\mathrm{m\;}}0{\mathrm{m}}/ {\mathrm{s\;}}104{\mathrm{m\;}} - 15{\mathrm{m}}/{\mathrm{s}}} ]$$.

The measurement equation is 15 $$$\begin{equation}z\;\left( k \right) = \;H\left( k \right)X\left( k \right) + W\left( k \right)\end{equation}$$$

And the measurement matrix is 16 $$$\begin{equation}H\;\left( k \right) = \left[ { \def\eqcellsep{&}\begin{array}{@{}*{4}{c}@{}} 1&\quad 0&\quad 0&\quad 0\\ 0&\quad 0&\quad 1&\quad 0 \end{array} } \right]\;\end{equation}$$$17 $$$\begin{equation}z\;\left( k \right) = \left[ { \def\eqcellsep{&}\begin{array}{@{}*{1}{c}@{}} {{z_1}\quad \left( k \right)}\\[3pt] {{z_2}\quad \left( k \right)} \end{array} } \right]\;\end{equation}$$$

The measured noise $$W( k )$$ is zero-mean Gaussian white noise with covariance matrix R, 18 $$$\begin{equation}{\;}{R_{11}} = {R_{22}}\; = \;200{m^2}\end{equation}$$$19 $$$\begin{equation}{\;}{R_{12}} = {R_{21}}\; = \;0\end{equation}$$$

For the two-dimensional measurement, the area of the confirmed region is as follows: 20 $$$\begin{equation}{\;}{A_v} = \;\pi \gamma {\left| {S\left( k \right)} \right|^{1/2}}\end{equation}$$$where $$S( k )$$ is the innovation covariance. Assuming the parameter $$\gamma \; = \;16$$, $$\alpha = 0.75$$ in Formula (11), the false measurements are uniformly generated in A square centred on the correct measurements. The square area is 21 $$$\begin{equation}A\; = \frac{{{n_c}}}{\lambda }\; \approx 10{A_v}\end{equation}$$$where λ is the number of false measurements per unit area and $${n_c}$$ is the total number of false measurements. The position of the ith false measurement is 22 $$$\begin{equation}{\;}{x_i} = \;a + \left( {b - a} \right)RND,\;{y_i} = \;c + \left( {d - c} \right)RND\end{equation}$$$

where RND stands for uniformly distributed random number, $${x_k},{y_k}$$ stand for real measurement positions. $$a,b,c,$$ and d stand for 23 $$$\begin{equation}a\; = {x_k}\; - q,\;b\; = {x_k}\; + q\end{equation}$$$24 $$$\begin{equation}c\; = {y_k}\; - q,\;d\; = {y_k}\; + q\end{equation}$$$25 $$$\begin{equation}q\; = \sqrt {10{A_v}} \;/2\end{equation}$$$

A large number of false measurements are generated in $$10{A_v}$$, and the false measurements falling into the region are approximately Poisson distribution, initialized by the two-point difference method, and clutter is introduced into the system at $$t = 10\;{\mathrm{s}}$$.

Result analysis

The Kalman filter, probabilistic data association and improved probabilistic data association proposed in this paper were used to track the target, and the simulation results are as follows,

As can be seen from the figures above, the tracking effect of the target tends to be good as time goes by, and the speed and position errors in the x and y directions gradually decrease. As the speed error in the x direction is slightly larger, the tracking position in the x direction fluctuates around the real position, as shown in Figures 1–4. According to the simulation results, the improved method is effective for single-target tracking in clutter environment. Further, it can be seen from the comparison between Figures 1 and 2 that the tracking track is closer to the real track after the dynamic detection gate is adopted, which indicates that the dynamic tracking gate can effectively improve the accuracy of target tracking. Besides, Figures 4a and 4b show that position error decreases obviously after the application of dynamic tracking door, especially in the x direction, the position and velocity errors of the improved PDA algorithm proposed in this paper for target tracking are significantly smaller than those of the PDA algorithm and the Kalman filter, and the estimation errors of the Kalman filter are smaller than those of the PDA algorithm, (d), (e) and (f) show significant optimizations in velocity errors.

[IMAGE OMITTED. SEE PDF]

[IMAGE OMITTED. SEE PDF]

[IMAGE OMITTED. SEE PDF]

[IMAGE OMITTED. SEE PDF]

The mean square errors of target position and velocity in x, y directions and space are shown in the following table:

Table 2 shows that the enhanced method's tracking accuracy is greater and its mean square error of spatial location and velocity is less than that of the traditional PDA algorithm and the Kalman filtering. This indicates that the dynamic detection gate is effective in screening effective measurements.

TABLE 2 The comparison of improved PDA, PDA and KALMAN mean square.

	Position	Speed
Type	Space	X direction	Y direction	X direction	Y direction
Improved PDA	70.1566	3.5071	70.0464	0.4629	6.0274
PDA	75.6882	16.0965	73.9086	1.5982	7.0364
Kalman	73.1058	4.7783	72.9494	0.7332	7.2584

CONCLUSION

The target-tracking algorithm based on improved PDA makes use of neighbourhood similarity and adjusts the detection threshold to some extent. The mean square error of single target tracking in a cluttered environment is less than that of the traditional PDA algorithm and Kalman filtering, and it has a greater tracking accuracy, according to simulation experiment and result analysis.

AUTHOR CONTRIBUTIONS

Jiaguo Zhang: Data curation. Xiaojie Huang: Writing–original draft.

CONFLICT OF INTEREST STATEMENT

The authors declare no conflicts of interest.

DATA AVAILABILITY STATEMENT

The data that support the findings of this study are available from the corresponding author upon reasonable request.

References

Ehrman, L.M.: Multitarget, multisensor tracking. IET Digital Library (2012)

Salmond, D.: Target tracking: Introduction and Kalman tracking filters. IEE Target Tracking: Algorithms and Applications (Ref. No. 2001/174). IET (2001)

Doppler Radar: John Wiley & Sons, Inc (2005)

Pan, Z., Liu, S., Fu, W.: A review of visual moving target tracking. Multimed. Tools. Appl. 76, 16989–17018 (2017)

Kass, M., Witkin, A., Terzopoulos, D.: Snakes: Active contour models. IJCV 1(4), 321–331 (1988)

Li, D., Wang, C., Deng, H., et al.: Motion planning algorithm of a multi‐joint snake‐like robot based on improved serpenoid curve. IEEE Access 8, 8346–8360 (2020)

Roonizi, A.K.: An efficient algorithm for maneuvering target tracking [tips & tricks]. IEEE Signal Process Mag. 38(1), 122–130 (2021)

Xiao, C., Li, Y., Jing, Y., et al.: Developing the fuzzy c‐means clustering algorithm based on maximum entropy for multitarget tracking in a cluttered environment. J. Appl. Remote Sens. 12(1), 1 (2018)

Bar‐Shalom, Y., Fortman, T.E.: Tracking and data association. J. Acoust. Soc. Am. 87(2), 918–919 (1990)

Zhang, L., Pan, Y., Wu, X., et al.: Information Fusion (2021)

Li, J.: An improved K‐nearest neighbor algorithm using tree structure and pruning technology. Intell. Autom. Soft Comput. 25(1), 35–48 (2019)

Zhao, Y.: An improved indoor positioning method based on nearest neighbor interpolation. Netw. Commun. Technol. 6(1), 1 (2021)

Valarmathi, J., Chaitra, T.C., Gupta, Y.: Multiple target tracking using KNN‐based classifier and probabilistic data association. In: International Conference on Automation, Signal Processing, Instrumentation and Control, pp. 271–281 (2021)

Zhao, S., Wang, Y., Wang, P., et al.: Adaptive non‐linear joint probabilistic data association for vehicle target tracking. IEEE Access 9, 14138–14147 (2021)

Luo, J., Wang, Z., Chen, Y., et al.: An improved unscented particle filter approach for multi‐sensor fusion target tracking. Sensors 20(23), 6842 (2020)

Liu, D., Zhao, Y., Gao, J., et al.: Kalman‐PDA approach using radial velocity. Syst. Eng. Electron. (10), 2195–2199 (2018)