Tracking of Multiple Closely Spaced Extended Targets Based on Prediction-Driven Measurement Sub-Partitioning Algorithm

Abstract

For multiple extended target tracking, the accuracy of measurement partitioning directly affects the target tracking performance, so the existing partitioning algorithms tend to use as many partitions as possible to obtain accurate estimates of target number and states. Unfortunately, this may create an intolerable computational burden. What is worse is that the measurement partitioning problem of closely spaced targets is still challenging and difficult to solve well. In view of this, a prediction-driven measurement sub-partitioning (PMS) algorithm is first proposed, in which target predictions are fully utilized to determine the clustering centers for obtaining accurate partitioning results. Due to its concise mathematical forms and favorable properties, redundant measurement partitions can be eliminated so that the computational burden is largely reduced. More importantly, the unreasonable target predictions may be marked and replaced by PMS for solving the so-called cardinality underestimation problem without adding extra measurement partitions. PMS is simple to implement, and based on it, an effective multiple closely spaced extended target tracking approach is easily obtained. Simulation results verify the benefit of what we proposed—it has a much faster tracking speed without degrading the performance compared with other approaches, especially in a closely spaced target tracking scenario.

1. Introduction

Target tracking techniques have been studied extensively with fruitful results and widely developed in both military and civil fields [1,2,3,4,5,6,7,8,9,10]. In traditional tracking applications, it is generally assumed that at most one measurement can be received by sensors per time and the target is modeled as a single point mass. However, with the increased resolution of modern sensors, multiple measurements may be originated from different unknown sources on a target. In this case, a target should be regarded as extended if its extension is much larger than the sensor resolution. Recently, multiple extended target tracking [11,12,13,14,15,16] has been attracting attention. However, it is still a complicated problem because there are unknown and uncertain associations between targets and measurements. Especially for multiple closely spaced extended target tracking (MCETT), extended targets may have parallel or crossed tracks (such as decoys and re-entry vehicles in ballistic missiles, and groups of airplanes with close tracks in radar surveillance). It is more difficult to judge the associations between these closely spaced targets and their measurements, respectively.

The random finite set (RFS) [17] and the finite set statistics (FISST) [18] have been developed over decades. They are widely applied to deal with the tracking of multiple targets with unknown and time-varying number in noise and clutter environments, because the uncertain associations between targets and measurements can be avoided. In [19,20], the probability hypothesis density (PHD) filter was proposed. It was evolved into the extended target PHD (ET-PHD) filter [21] by assuming that the number of measurements obeys the Poisson distribution and measurements are distributed around the target based on an inhomogeneous spatial Poisson point process [22]. In recent years, many multiple extended target tracking approaches based on the ET-PHD filter and its variants have been proposed [23,24,25,26], e.g., the extended target Gaussian mixture PHD filter [27], the extended target gamma GIW-PHD (ET-GGIW-PHD) filter [28,29,30] based on the random matrix approach [31,32,33], and the ET-GM-PHD filter based on random hypersurface model [34,35,36].

In the ET-PHD filter framework, the measurement partitioning is indispensable. It divides the set of measurements into several non-empty subsets and aims at obtaining the partitions that are closest to the true partition. The multiple extended target tracking performance is affected by measurement partitioning to a large extent because the partitioning results are directly utilized to update the predicted target state. Especially for MCETT, the dense distribution of measurements may bring difficulty to the accurate measurement partitioning and even cause the cardinality underestimation problem. To deal with this problem, the traditional partitioning algorithms usually require all possible partitions. However, the number of possible partitions grows very fast with the increasing total number of measurements, which creates a heavy computational burden. Furthermore, a large number of partitions are still unreasonable and should be eliminated.

To partition the measurements more effectively, a distance partitioning algorithm was proposed to make relatively accurate partitions by decreasing the distance threshold empirically. However, this approach may not be well applied for tracking closely spaced extended targets because it is very likely to cause an underestimation in the extended target number. Furthermore, there are still unreasonable and redundant measurement partitions, which are adverse to reducing a heavy computational burden. In [37], the prediction partitioning algorithm and EM partition algorithm were proposed for tracking elliptical targets. The former directly treats the predicted mean of the GIW component as the centroid of the ellipsoid target and uses the extension estimation to put the measurements belonging to the corresponding component into the same subset. However, it may not handle well the tracking of extended targets with different sizes. To deal with this problem, the EM partition algorithm was proposed to obtain the better measurement partitions in which the Gaussian mixtures are initialized with the predicted GIW components. Due to the utilization of predictive information, these two algorithms can improve the tracking performance and save computational time.

Although the predictive information is promising to be utilized for achieving better performance, its accuracy is closely related to the predicted target number and state. Especially for the tracking of multiple closely spaced extended targets, obtaining accurate partitioning results is difficult when the target number is underestimated. Moreover, it is very likely to gain non-information subsets in missed detection environment, which directly leads to the instable estimate performance of target number and state. To deal with this problem, the distance partitioning algorithm was extended with sub-partitioning and proposed in [27]. It uses the K-means++ clustering [38,39,40] to repartition the inaccurate subsets. Unfortunately, it may not possibly guarantee the accuracy of repartitioning results. The main reason lies in the loss function of K-means++, which is likely to cause an unreasonable repartition of subsets and degrades the tracking performance. Overall, the main difficulties of measurement partitioning for MCETT are summarized as follows.

(i) How does one maintain the accuracy of the indispensable measurement partitioning results in clutters and missed detection environment without sacrificing the tracking performance?

(ii) How does one achieve high tracking performances in MCETT approaches, i.e., obtain relatively accurate partitions when tracking closely spaced extended targets in practical scenarios (e.g., tracks crossed or paralleled)?

This paper is motivated by these problems and proposes a prediction-driven measurement sub-partitioning (PMS) algorithm for tracking multiple closely spaced extended targets. The predictive information is utilized to determine possible clustering centers. Moreover, unreasonable target predictions (whose corresponding subset may contain measurements from more than one target when the target number is underestimated) are replaced by alternative points to obtain relatively accurate partition results when targets are spatially close. This proposed partitioning strategy fully considers the spatial distribution characteristics for the clustering center and target predictions, which help obtain the clustering centers close to the true target centers. Thus, PMS handles well the tracking of closely spaced extended targets and seems promising. To reduce the computational complexity, the range of partition numbers is narrowed to eliminate unreasonable and redundant partitions. Note that the proposed algorithm considers all possible changes in the number of targets at each time step and reduces the number of partitions as reasonably as possible. Due to its concise mathematical forms and favorable properties (modifying target predictions and reducing partition number), an approach to multiple extended target tracking is proposed. Compared with other existing approaches based on different measurement partitioning algorithms, the innovative aspects of this work are summarized as follows.

(i) In PMS, target predictions are explicitly considered and fully utilized to improve the accuracy of measurement partitioning, which facilitate the performance improvement of multiple closely spaced extended targets tracking.

(ii) Due to the concise mathematical forms and favorable properties of PMS, redundant measurement partitions can be eliminated so that the computational burden is largely reduced.

(iii) When extended targets are spatially close, PMS seems more promising because the unreasonable target predictions can be marked and replaced by alternative points. It solves the so-called cardinality underestimation problem without adding extra measurement partitions.

(iv) The proposed MCETT approach based on PMS fits well with the tracking of spawned and newborn targets in the clutter and missed detection environments.

This paper is organized as follows. Section 2 first elaborates and analyzes the existing problems of the typical measurement partitioning algorithms in multiple extended target tracking. Section 3 proposes a fast and robust prediction-driven algorithm (i.e., PMS) to partition the measurements set accurately for improving the target tracking performance. In Section 4, a multiple extended target tracking approach based on PMS is proposed for tracking closely spaced extended targets. Section 5 presents simulation results and demonstrates the effectiveness of what we proposed. Section 6 further discusses and compares the proposed algorithm with existing measurement partitioning algorithms. The last section concludes this paper.

2. The Measurement Partitioning Problem

An integral part of the update equation requires the partitions of the measurement set, i.e., the set of measurements needs to be partitioned into different partitions at each time step and each partition contains several subsets with the measurements understood to be originated from the same target or clutter. For MCETT in noise and clutter environments, the result of measurement partitioning would greatly affect the stability of subsequent tracking algorithm and the estimation accuracy of both the target state and number.

In the framework of the ET-PHD filter, all possible partitions of the measurement set are needed in the measurement pseudo-likelihood, which makes the whole filtering computationally challenging with the increase of the partitions’ number [27]. However, there are many unsuitable subsets in a large part of the partitions, contributing little to the tracking performance. Only several partitions contain the most likely subsets. Thus, these partitions can be used to approximate the whole partitions.

2.1. The Measurement Partitioning Algorithm Based on Distance

A distance-based measurement partitioning algorithm (i.e., so-called distance partitioning) was proposed. It utilizes the statistical properties of distances between measurements obtained from the same target to reduce the number of partitions. However, the computational burden still grows rapidly in many cases when the number of targets increases. Furthermore, the distance-based underlying mechanism that measurements generated from the same target are close to each other will no longer applicable to the spatially close target tracking scenario. In this case, all the measurements are densely distributed in the same region once targets make a cross with each other. One clustering of the measurements may be generated from more than one extended target. However, distance partitioning is very likely to mistreat this clustering from one target, causing a cardinality error in the following filtering. In this point, the sub-partitioning algorithm was proposed on the basis of distance partitioning to better handle the estimated problem of cardinality.

The sub-partitioning is an augmentation of distance partitioning, which repartitions the subsets containing measurements from multiple targets by distance partitioning. It uses K-means++ clustering to repartition the subset $W_j^i$ into $N_x^j$ smaller subsets if the maximum likelihood (ML) estimation about the number of targets for each subset is larger than 1. These smaller subsets are added to the list of partitions, which are considered and utilized by the ET-PHD filter framework. However, this sub-partitioning strategy only focuses on improving the estimation performance of target number without considering the heavy computational burden, which is not good for real-time target tracking. Moreover, the cardinality error still exists, especially in the tracking scenario where four or more targets are being crossed. This is mainly because the loss function of the K-means++ clustering causes inaccurate repartitioning. These inaccurate repartitioning results will not contribute much to the target tracking due to the lower likelihood obtained by these partitions compared with one obtained by the relatively accurate partitions.

2.2. The Target Measurement Partitioning Algorithm Based on Target Predictions

In addition to the distance-based measurement partitioning algorithms, predicted components are used to partition the measurement set in the prediction partition and EM partition in the random matrix framework of extended target tracking [37]. In prediction partition, the predicted mean of the GIW component is treated as the centroid of the elliptic target. The extension estimate ${\widehat{X}}_{k+1\left|k\right.}^{\left(j\right)}$ (i.e., a symmetric positive definite matrix used to represent the elliptical shape of jth elliptic extended target) of the component is used to accurately partition the measurements, i.e., the measurements satisfying ${\left(z_k^{\left(i\right)}-m_{k+1\left|k\right.}^{\left(j\right),d}\right)}^T{\left({\widehat{X}}_{k+1\left|k\right.}^{\left(j\right)}\right)}^{-1}\left(z_k^{\left(i\right)}-m_{k+1\left|k\right.}^{\left(j\right),d}\right)<{\mathsf{\Delta }}_d\left(p\right)$ are put into the same subset, where $m_{k+1\left|k\right.}^{\left(j\right),d}$ denotes the first d components of the predicted mean of jth GIW component, $z_k^{\left(i\right)}$ is the ith measurement at time k, ${\mathsf{\Delta }}_d\left(p\right)$ is determined according to the inverse ${\chi }^2$ distribution with d degree of freedom, and p is the probability and equal to 0.99. For other measurements that are not included in any subsets of the predicted components, each of them is treated as an individual subset. However, the use of extension estimate limits the application of prediction partition to the tracking of extended targets with different shapes. It is also difficult to track ellipsoid targets with different sizes.

To better partition the measurements when elliptic targets have different sizes and a diverse number of measurements, EM partition was proposed based on the Expectation Maximization algorithm for Gaussian mixtures. The predicted components are used to initialize the Gaussian mixtures. Both of the above algorithms only generate one accurate partition for the subsequent filtering, which can achieve good tracking performances when the target predictions are accurate in some cases. However, they are sensitive to the target predictions. When the target prediction is erroneous (i.e., the discrepancy between the predicted mean of the GIW component and the true target centroid is considerable), this partition is very likely to contain the non-information subsets, which directly causes the degradation of the target tracking performance. Thus, the alternative partitions should be considered to guarantee the stability of target tracking.

Another problem of these partition algorithms is that they cannot handle well the measurement partitioning for tracking closely spaced extended targets in missed detection environments, which is very likely to cause the underestimation of the target number. Moreover, once the target number is underestimated, it further makes the target predictions erroneous, inevitably making the subsequent partition results unreasonable. Worst of all, only one partition is used in the partitioning algorithms. These subsets can directly influence the tracing performance and cause poor estimate performance of target number and state.

To sum up, the key to achieving good tracking performance is to obtain the partitions that are closest to the true partition, and the number of partitions is the main factor affecting the averaged computation time. As for the distance-based measurement partitioning algorithms, there is still a large part of partitions that contain unreasonable subsets, which contributes little to tracking performance and leads to a heavy computational burden. In contrast, the measurement partitioning algorithms based on predictions aim to obtain one relatively accurate partition by utilizing predictive information, which greatly reduces the partition number. However, the accuracy of this partition can not be guaranteed, making the target tracking performance unstable. Both of these measurement partitioning algorithms cannot handle well the tracking scenario where extended targets are spatially close to each other. It is very likely to cause an underestimation of target number.

From the above comparison of the existing measurement partitioning algorithm, it can be concluded that fast tracking multiple targets without a loss of tracking performance is still a challenge for tracking multiple extended targets (especially for closed spaced extended targets). In order to partition the measurement set accurately and quickly when extended targets of interest are spatially close, a more general prediction-driven measurement sub-partitioning algorithm (i.e., PMS) is proposed in this paper. The detailed procedures of the proposed PMS are in the next section.

3. Prediction-Driven Measurement Sub-Partitioning

To effectively approximate all possible partitions, several reasonable partitions are considered to achieve stable and accurate target tracking performance. The partition number is determined according to the possible changes of the target number. Suppose that the number of extended targets at time step $k-1$ is $J_{k-1}$, the number of newborn targets is $J_{\gamma ,k}$, and the number of spawned targets from the same existing target is $J_{\beta ,k}$, then the range of target number K is

$$J_{k-1}\le K\le J_{k-1}+J_{\beta ,k}\times J_{k-1}+J_{\gamma ,k},$$

(1)

As the measurements are needed to be partitioned into several subsets, we set the number of subsets in a partition as the possible target number. To obtain different partitions, we use different possible target number for measurement partitioning. As shown in Equation (1), there are $J_{\beta ,k}\times J_{k-1}+J_{\gamma ,k}+1$ different integers in the closed interval. Correspondingly, there are $J_{\beta ,k}\times J_{k-1}+J_{\gamma ,k}+1$ different partitions of the measurements. Here, $J_{\beta ,k}$ and $J_{\gamma ,k}$ are approximated by 1 and $J_{k-1}$, respectively. That is, there are $J_{k-1}$ newborn targets and one target spawned from the same target. Thus, the partition number $N_p$ is reduced to

$$N_p=2\times J_{k-1}+1.$$

(2)

As mentioned above, every possible target (e.g., the existing target, the spawned target, or the newborn target) has the corresponding subset in the partition. Considering the unknown positions of the spawned and newborn targets, their possible clustering centers are determined by the initial center selection strategy of K-means++ clustering. To make sure each partition contains the most likely subsets, the predicted position of the existing target is used to obtain the possible clustering center of the existing target at the current time step, i.e., the measurement close to the predicted mean is treated as the possible center. It is clear that the number of subsets for the existing targets is determined by one of the existing targets and the accuracy of the partitioning results is closely related to the target predictions. However, in the typical target tracking scenario with spatially close targets, the target number is very likely to be underestimated, causing the same cardinality underestimation problem to the target predictions. It would directly influence the precision of the partition results. What is worse is that the wrong number of target predictions is hard to correct, which makes accurate measurement partitions unavailable for the subsequent filtering. This phenomenon no doubt degrades the MCETT performance and lasts for some time.

To improve the robustness of the proposed measurement partitioning algorithm based on target prediction, a new repartition strategy is proposed in this paper to correct the unreasonable clustering centers obtained by target prediction. First of all, the unreasonable target prediction can be found through its partitioning results. According to the above clustering centers of existing targets, an initial partition $P_1={\left\{W^{\left(i\right)}\right\}}_{i=1}^{J_{k-1}}$ is obtained by clustering, where $W^{\left(i\right)}$ denotes the ith subset in the initial partition $P_1$. By comparing the expected number $\lambda$ of measurements from the same target with the measured number $\left|W^{\left(i\right)}\right|$ of each subset, the unreasonable subsets and their corresponding target predictions can be found. For each subset in $P_1$, if the condition $\frac{\left|W^{\left(i\right)}\right|}{\lambda }\ge 2$ is satisfied, this means it wrongly contains measurements of more than one target due to its clustering center. The corresponding target prediction of this clustering center is considered unreasonable. Second, the corresponding correct target number of each unreasonable subset can be roughly estimated by $\frac{\left|W^{\left(i\right)}\right|}{\lambda }$. To correct the unreasonable target prediction, the unreasonable target prediction should be replaced by alternative points, the number of which is the estimated correct target number.

At last, based on geometry, the locations of alternative points can be determined by the spatial distribution of the target prediction and measurements. Through analyzing the distribution of the measurements and target prediction, the prediction $x_{k\left|k-1\right.}^{\left(i\right)}$ corresponding to $i^{th}$ unreasonable subset $W^{\left(i\right)}$ can be approximated as the geometrical center of a polygon composed of real clusters’ centers. It can be seen in Figure a, which represents the spatial distribution of four true clusters of measurements that are observed from four crossed extended targets. Target number underestimation occurs in this tracking scenario with tracks-crossed, i.e., these measurements from four targets are mistakenly put into one subset according to the clustering center calculated by the target prediction. From Figure 1a, the target prediction can be treated as the geometrical center of the polygon composed of these true target centers. Thus, the alternative points can be roughly approximated by the vertices of polygons, as shown in Figure 1b.

According to the above analysis of the spatial distribution of the measurements and $x_{k\left|k-1\right.}^{\left(i\right)}$, we consider replacing the predicted target state $x_{k\left|k-1\right.}^{\left(i\right)}$ with reasonable alternative points (e.g., the vertices of a regular polygon) based on the geometry thought. Thus, the position ($p_{j,x},p_{j,y}$) of alternative point can be calculated as follows,

$$\begin{array}{c}{p}_{j,x}=x_{k\left|k-1,x\right.}^{\left(i\right)}+TH\times cos(\theta -\frac{2\pi \left(j-1\right)}{n_i})\hfill \\ p_{j,y}=x_{k\left|k-1,y\right.}^{\left(i\right)}+TH\times sin(\theta -\frac{2\pi \left(j-1\right)}{n_i})\hfill \end{array}$$

(3)

where $\theta =arctan\left(\frac{p_{1,y}-x_{k\left|k-1\right.,y}^{\left(i\right)}}{p_{1,x}-x_{k\left|k-1x\right.}^{\left(i\right)}}\right)$ is the angle between the X-axis and the line passing through $p_1$ and $x_{k\left|k-1\right.}^{\left(i\right)},$$TH$ is the distance between $x_{k\left|k-1\right.}^{\left(i\right)}$ and the first alternative point which is decided according to the distribution of the distances between $x_{k\left|k-1\right.}^{\left(i\right)}$ and the measurements, and $j=2,\cdots ,n_i$. As the number of polygon vertices, $n_i$ is the expected target number of the underestimated subsets.

The above strategy is more reliable and effective than the existing measurement partitioning algorithm (e.g., sub-partitioning algorithm) for repartitioning unreasonable subsets. Take Figure 2 as an example. There is a measurement set consists of $N_{z,k}=31$ measurements (originated from three closely spaced targets). From Figure 2a, we can see that sub-partitioning cannot partition the measurements into three relatively accurate subsets, which unreasonably treats the distant measurement as an individual subset. Compared with sub-partitioning, our method successfully divides the set of densely distributed measurements into three subsets (as shown in Figure 2b), which has more accurate measurements partitioning results and fits well with the tracking of extended targets with tracks-crossed.

After getting the clustering centers (including the alternative points of the unreasonable target predictions), a new partition can be obtained by K-means++ clustering, i.e., put the measurements closet to the above position into the same subset. Suppose that $X_{S,k|k-1}={\left\{x_{k\left|k-1\right.}^{\left(i\right)}\right\}}_{i=1}^{J_{k-1}}$ is the predictions of existing targets, $Z_k$ is the measurement set at time k, $N_{z,k}$ is the number of the observed measurements, and $J_{k-1}$ is the estimated number of targets at time $k-1$. The whole procedure of the proposed algorithm is detailed as follows.

Step 1. The lower and upper threshold of target number is calculated as $K_L=J_{k-1}$ and $K_U=J_{k-1}+J_{\beta ,k}\times J_{k-1}+J_{\gamma ,k}$, respectively. For each K value, there is an individual partition containing K subsets. Here, $J_{\beta ,k}$ and $J_{\gamma ,k}$ are approximated by 1 and $J_{k-1}$, respectively.

Step 2. Judge whether the underestimation problem exists in the subsets of the first partition by using $\frac{N_{z,k}}{\lambda }-J_{k-1}$. If $\frac{N_{z,k}}{\lambda }-J_{k-1}\ge 1$, it means that the number of targets has been underestimated at the previous time $k-1$, where $\lambda$ is the expected number of observed measurements from each target and equal to the Poisson rate.

Step 3. For each K value, the initial clustering centers $C^{J_{k-1}}=\left\{c_1,\cdots ,c_{J_{k-1}}\right\}$ are obtained by the predicted positions of survival targets, and the initial partition $P_1={\left\{W^{\left(i\right)}\right\}}_{i=1}^{J_{k-1}}$ is gained by $C^{J_{k-1}}$, where $W^{\left(i\right)}$ is the ith subset. For each subset $W^{\left(i\right)}\in P_1$, $\frac{\left|W^{\left(i\right)}\right|}{\lambda }\ge 2$ is used to find the underestimated subset and corresponding predicted state $x_{k\left|k-1\right.}^{\left(i\right)}$, where $\left|W^{\left(i\right)}\right|$ is the number of observed measurements in ith subset. Round $\frac{\left|W^{\left(i\right)}\right|}{\lambda }$ up to the nearest whole number $n_i$, and let $n_i$ as the number of the alternative points of the predicted state $x_{k\left|k-1\right.}^{\left(i\right)}$. In this case, the predicted state $x_{k\left|k-1\right.}^{\left(i\right)}$ needs to be replaced by $n_i$ alternative points $P^{n_i}={\left\{p_j\right\}}_{j=1}^{n_i}$. This strategy may help us to obtain the alternative initial clustering centers $C_{{}^{n_i}}^i={\left\{c_j^i\right\}}_{j=1}^{n_i}$, where $c_j^i$ is determined according to $p_j$.

Step 4. Calculate the distance between each measurement and the predicted state $x_{k\left|k-1\right.}^{\left(i\right)}$, and sort them from smallest to largest. Afterward, the one in the middle is selected as the first alternative initial clustering center $c_1^i$. The distance between $c_1^i$ and $x_{k\left|k-1\right.}^{\left(i\right)}$ is denoted by $TH$. Let $c_1^i$ be the first alternative point $p_1$. The other $n_i-1$ alternative points $P^{n_i-1}=\left\{p_2,p_3,\cdots ,p_{n_i}\right\}$ can be considered as the vertexes of a regular polygon, and their locations are calculated by Equation (3). Then, all alternative points $P^{n_i}=\left\{p_1,,,P^{n_i-1}\right\}$ are obtained to replace the corresponding predicted state $x_{k\left|k-1\right.}^{\left(i\right)}$.

Step 5. Compute K-means clustering centers $C_{{}^{n_i-1}}^i={\left\{c_j^i\right\}}_{j=2}^{n_i}$ with alternative points $P^{n_i-1}$. Then, the alternative initial clustering center set $C_{{}^{n_i}}^i=\left\{c_{{}_1}^i,C_{{}^{n_i-1}}^i\right\}$ is obtained to replace the corresponding clustering center gained by $x_{k\left|k-1\right.}^{\left(i\right)}$ in $C^{J_{k-1}}$.

Step 6. Repeat Steps 3–5 until finishing selecting the alternative initial clustering centers $C^{under}={\left\{C_{n_i}^i\right\}}_{i=1}^N$ in all the underestimated subsets, where N is the number of the underestimated subsets. These centers are included into $C^{J_{k-1}}$. Other $K-J_{k-1}$ measurements are selected as $C^{K-J_{k-1}}=\left\{c_{J_{k-1}+1},c_{J_{k-1}+2},\cdots ,c_K\right\}$, which satisfy the selection probability $\frac{D{\left(z_k^{\left(i\right)}\right)}^2}{\sum _{z_k\in Z_k}D{\left(z_k\right)}^2}$, where $D\left(x\right)$ is the shortest distance from a measurement $z_k^{\left(i\right)}$ to the closest initial center.

Step 7. $J_{k-1}$ is changed to be $J_{k-1}^{*}=J_{k-1}-N+\sum _{i=1}^N{n}_i$, where N is the number of the underestimated subsets and $n_i$ is the expected target number of the ith subset. Accordingly, the lower bound is $K_L$$=J_{k-1}^{*}=J_{k-1}-N+\sum _{i=1}^N{n}_i$ and the upper bound is $K_U=J_{k-1}^{*}+J_{\beta ,k}\times J_{k-1}^{*}+J_{\gamma ,k}.$

Step 8. $C^{K-J_{k-1}}$ and $C^K$ are merged into $C^K=C^{K-J_{k-1}}\cup C^{J_{k-1}}$ as the whole clustering center set. Compute K-means clustering to get the final measurement partitioning results. The pseudocode of the proposed method is given in Algorithm 1.

Algorithm 1 Prediction-driven measurement sub-partitioning algorithm.

Input:$Z_k$: the set of measurements; $N_{z,k}$: the number of measurements; $X_{S,k|k-1}$: predictions for existing targets; $J_{k-1}$: the number of targets at time $k-1$; $\lambda$: the expected number of measurements from one target; $f_{pre}\left(X,Z\right)$: a function using target predictions to obtain clustering centers; $f_{initialP}\left(K,C,Z\right)$: K-means clustering function with only one iteration; $f_{alter}\left(n,c,Z\right)$: a function to compute alternative clustering centers; $f_K\left(K,,,Z\right)$: K-means++’s initial clustering center selection function; $f_P\left(K,C,Z\right)$: K-means clustering function;

Output: partitions ${\left\{P_K\right\}}_{K=K_L}^{K_U}$

1: $K_L=J_{k-1}$, $K_U=J_{k-1}+J_{\beta ,k}\times J_{k-1}+J_{\gamma ,k}$; 2: Obtain $C^{J_{k-1}}:$${\left\{c_i\right\}}_{i=1}^{J_{k-1}}=f_{pre}\left(X_{S,k\left|k-1\right.},Z_k\right)$; 3: if$N_{z,k}/\phantom{N_{z,k}\lambda }\lambda -J_{k-1}\ge 1$then 4:     First partitioning: ${\left\{W^{\left(i\right)}\right\}}_{i=1}^{J_{k-1}}=f_{initialP}\left(J_{k-1},C^{J_{k-1}},Z_k\right)$; 5:     $J_{k-1}^{*}=J_{k-1}$; 6:     for $i=1:J_{k-1}$ do 7:         if $\frac{\left|W^{\left(i\right)}\right|}{\lambda }$ then 8:            $n_i\leftarrow \mathrm{ROUND}\left(\frac{\left|W^{\left(i\right)}\right|}{\lambda }\right)$; 9:             Find alternative centers: $C_{n_i}^i=f_{alter}\left(n_i,c_i,Z_k\right)$; 10:            Delete the center $c_i$ in $C^{J_{k-1}}$ 11:            Augment the new centers: $C^{J_{k-1}}=C^{J_{k-1}}\cup C_{n_i}^i$; 12:            $J_{k-1}^{*}=J_{k-1}^{*}-1+n_i$; 13:         end if 14:     end for 15:     $K_L=J_{k-1}^{*}$,$K_U=J_{k-1}^{*}+J_{\beta ,k}\times J_{k-1}^{*}+J_{\gamma ,k}$; 16: end if 17: while$K_L\le K\le K_U$do 18:     Obtain $C^{K-J_{k-1}}$: ${\left\{c_i\right\}}_{i=J_{k-1}^{*}+1}^K=f_K\left(K-J_{k-1},,,Z_k\right)$; 19:     Obtain the whole clustering center set $C^K$: $C^K=C^{J_{k-1}}\cup C^{K-J_{k-1}}$; 20:     Measurements partitioning: $P_K={\left\{W^{\left(i\right)}\right\}}_{i=1}^K=f_P\left(K,C^K,Z_k\right)$; 21:     $K=K+1$; 22: end while

Remark 1.

The above algorithm flexibly utilizes predictions of existing targets to obtain more accurate measurement partitioning results. Moreover, the unreasonable target predictions are replaced by more reasonable alternative points, which fits well in the tracking scenarios with extended targets spatially close (e.g., targets with tracks-crossed) when the number of targets is underestimated. Note that this strategy aims to make the use of target predictions more robust, which does not add extra partitions to improve the accuracy of partitions. Due to its concise mathematical forms and favorable properties, PMS can be easily integrated into the framework of ET-PHD filter, achieving higher tracking performance.

4. A Target Tracking Approach Based on Prediction-Driven Measurement Sub-Partitioning

As mentioned above, the proposed prediction-driven measurement sub-partitioning algorithm can be integrated into various filters to track multiple extended targets due to its concise mathematical forms and favorable properties. Thus, a multiple extended target tracking approach based on PMS is proposed.

Based on the assumption of the measurement model that measurements are distributed around a target reference point approximately, the target state vector $x_k^{\left(i\right)}={[m_k^{\left(i\right)},x_k^{*}]}^{\mathrm{T}}$ consists of only the target position $m_k^{\left(i\right)}$ and velocity $x_k^{*}$ without any parameter of target’s size and shape. Note that this is the basic structure of the target state vector, in which the parameters for spatial extent can be included according to other models of target extension. It makes our approach easily extended to other filters for tracking extended targets with the complicated spatial extent.

To deal with the tracking scenario with clutters and unknown associates between measurements and targets, measurements and target states are modeled as random finite sets (RFS), respectively, i.e., $X_{k-1}={\left\{x_{k-1}^{\left(i\right)}\right\}}_{i=1}^{N_{x,k-1}}$, $Z_k={\left\{z_k^{\left(i\right)}\right\}}_{i=1}^{N_{z,k}}$. $N_{x,k-1}$ is the number of targets estimated at time $k-1$ and $N_{z,k}$ is the number of measurements obtained at time k. The corresponding dynamic model of each target state in the $X_{k-1}$ and the measurement model of each measurement in $Z_k$ are assumed as follows,

$$x_k^{\left(i\right)}=F_{k-1}{x}_{k-1}^{\left(i\right)}+w_{k-1}$$

(4)

$$z_k^{\left(i\right)}=H_k{x}_{k-1}^{\left(i\right)}+e_k$$

(5)

where $F_{k-1}$ is the state transition matrix, $w_{k-1}$ is the independent Gaussian white noise with the covariance $Q_{k-1}$, $H_k$ is the measurement matrix, and $e_k$ is Gaussian white noise with the covariance $R_k$.

The proposed extended target tracking approach includes the prediction, measurement partitioning, and update, which are detailed as follows.

4.1. Prediction

The predicted intensity $D_{k\left|k-1\right.}\left(x\right)$, which contains the intensity for newly born targets, spawned targets and existing targets, can be given as follows,

$$D_{k\left|k-1\right.}\left(x\right)=\sum _{j=1}^{J_{k\left|k-1\right.}}{\omega }_{k\left|k-1\right.}^{\left(j\right)}\mathcal{N}\left(x;m_{k\left|k-1\right.}^{\left(j\right)},P_{k\left|k-1\right.}^{\left(j\right)}\right)$$

(6)

where $J_{k\left|k-1\right.}$ is the predicted number of Gaussian components, ${\omega }_{k\left|k-1\right.}^{\left(j\right)}$ is the predicted weight of the Gaussian component, $m_{k\left|k-1\right.}^{\left(j\right)}$ is the predicted mean of the Gaussian component, and $P_{k\left|k-1\right.}^{\left(j\right)}$ is the predicted covariance of the Gaussian component.

Note that the proposed PMS only uses the predicted intensity for existing targets. Given the initial intensity $D_{k-1}\left(x\right),$ the predicted intensity $D_{S,k\left|k-1\right.}\left(x\right)$ for existing targets can be calculated as follows,

$$D_{S,k\left|k-1\right.}\left(x\right)=p_S\left(x\right)\sum _{j=1}^{J_{k-1}}{\omega }_{k-1}^{\left(j\right)}\mathcal{N}\left(x;m_{S,k\left|k-1\right.}^{\left(j\right)},P_{S,k\left|k-1\right.}^{\left(j\right)}\right)$$

(7)

$$m_{S,k\left|k-1\right.}^{\left(j\right)}=F_{k-1}{m}_{k-1}^{\left(j\right)}$$

(8)

$$P_{S,k\left|k-1\right.}^{\left(j\right)}=Q_{k-1}+F_{k-1}{P}_{k-1}^{\left(j\right)}{F}_{k-1}^T$$

(9)

where $p_S\left(x\right)$ is the survival probability, $m_{S,k\left|k-1\right.}^{\left(j\right)}$ is the transition mean of the Gaussian component, $P_{S,k\left|k-1\right.}^{\left(j\right)}$ is the transition covariance of the Gaussian component, ${\omega }_{k-1}^{\left(j\right)}$ is the weight of the Gaussian component at time $k-1$, $m_{k-1}^{\left(j\right)}$ is the mean of the Gaussian component at time $k-1$, and $P_{k-1}^{\left(j\right)}$ is the covariance of the Gaussian component at time $k-1$.

4.2. Measurement Partitioning

The measurement partitioning is indispensable to MCETT and aims to make measurements (originated from the same target) divided into the same subset. As an integral part of ET-PHD filter, it would greatly affect the stability of the subsequent tracking algorithm and the estimation accuracy of both the target state and number. Besides, the computational burden of the measurements partitioning is also a key factor affecting the speed of multiple extended target tracking. Target predictions can be used to partition the measurements to obtain relatively accurate partitioning results. However, they are likely to cause measurements that are inaccurately divided when the cardinality underestimation problem occurs. There is a pressing need to modify it for improving the performance in the target number and state estimation.

Based on PMS, the measurement set can be partitioned as accurately as possible. The range of K value is also narrowed, i.e., the lower and upper bounds of the interval $\left[K_L,K_U\right]$ are set as $K_L=J_{k-1}$ and $K_U=J_{k-1}+J_{\beta ,k}\times J_{k-1}+J_{\gamma ,k}$, respectively. This strategy reduces the partition number and decreases the computational complexity greatly. Note that the predictive information is fully used to obtain the clustering centers. More importantly, the problem of underestimation in the target number is considered and solved explicitly. $\frac{N_{z,k}}{\lambda }-J_{k-1}\ge 1$ is presented to judge whether there is the underestimation of the target number, and $\frac{\left|W^{\left(i\right)}\right|}{\lambda }\ge 2$ is used to find the underestimated subset and corresponding predicted state if the condition is satisfied (i.e., the number of targets have been underestimated). In this way, $n_i$ alternative points of the predicted state can be found by introducing the Geometry of a regular polygon, which serves to determine the alternative initial centers of the underestimated subset. The whole procedures of PMS are detailed in Algorithm 1.

4.3. Update

As the accurate measurement partitioning results can be obtained by the PMS, the subsets of each partition is used to update each predicted Gaussian Mixture components. By using the measurement pseudo-likelihood function $L_{Z_k}\left(x\right)$, the update equation is given by

$$D_{k|k}\left(x\right)=L_{Z_k}\left(x\right)D_{k|k-1}\left(x\right)$$

(10)

$$\begin{array}{c}{L}_{Z_k}\left(x\right)=\underset{\mathrm{No}\mathrm{detections}\mathrm{of}\mathrm{the}\mathrm{target}}{\underbrace{1-(1-e^{-\gamma \left(x\right)})p_D\left(x\right)}}+\hfill \\ \underset{\mathrm{A}\mathrm{t}\mathrm{least}\mathrm{one}\mathrm{detection}\mathrm{of}\mathrm{the}\mathrm{target}}{\underbrace{{\displaystyle e^{-\gamma \left(x\right)}{p}_D\left(x\right)\times \sum _{P\angle Z_k}{\omega }_P\sum _{W\in P}\frac{\gamma {\left(x\right)}^{\left|W\right|}}{d_W}·\prod _{z_k\in W}\frac{{\varphi }_{z_k}\left(x\right)}{{\lambda }_k{c}_k\left(z_k\right)}}}}\hfill \end{array}$$

(11)

where $D_{k|k}\left(x\right)$ is the posterior intensity, $D_{k|k-1}\left(x\right)$ is the predicted intensity, $p_D\left(x\right)$ is the detection probability of target, $\gamma \left(x\right)$ is the expected number of measurements from the target, ${\varphi }_{z_k}\left(x\right)$ is the Gaussian likelihood function of the generate measurement for a single target, ${\lambda }_k$ is the mean of clutter measurements, and $c_k\left(z_k\right)$ is the spatial distribution of the clutter over the surveillance volume. Note that the non-negative coefficients ${\omega }_P$ and $d_W$ are defined for P and W, respectively. $P\angle Z_k$ denotes that there are P partitions, each of which is able to divides the measurement set $Z_k$ into several non-empty subsets, and $W\in P$ denotes that W is a subset in the partition P.

$L_{Z_k}\left(x\right)$ can be separated into two parts according to the situation of measurement detection. Thus, the above update equation can be evolved to a more clear form containing two aspects (i.e., the update in the case with no detection of targets and the update in the case with detection of targets), which are as follows,

$$D_{k|k}\left(x\right)=D_{k|k}^{ND}\left(x\right)+\sum _{P\angle Z_k}\sum _{W\in P}{D}_{k|k}^D(x,W)$$

(12)

where $D_{k|k}^{ND}\left(x\right)$ serves to the case of non-detected targets and $D_{k|k}^D(x,W)$ serves to the case of detected targets. In these cases, ${\omega }_{k\left|k\right.}^{\left(j\right)}$ is used to denote the updated weight of the Gaussian component, $m_{k\left|k\right.}^{\left(j\right)}$ is the updated mean of the Gaussian component, and $P_{k\left|k\right.}^{\left(j\right)}$ is the updated covariance of the Gaussian component.

The update for no detection case is given as follows,

$$D_{k|k}^{ND}\left(x\right)=\sum _{j=1}^{J_{k|k-1}}{\omega }_{k|k}^{\left(j\right)}\mathcal{N}(x;m_{k|k}^{\left(j\right)},P_{k|k}^{\left(j\right)})$$

(13)

$${\omega }_{k|k}^{\left(j\right)}=(1-(1-e^{-\gamma \left(j\right)}){p_D}^{\left(j\right)}){\omega }_{k|k-1}^{\left(j\right)}$$

(14)

$$m_{k|k}^{\left(j\right)}=m_{k|k-1}^{\left(j\right)},P_{k|k}^{\left(j\right)}=P_{k|k-1}^{\left(j\right)}$$

(15)

where $p_D\left(j\right)$ is the detection probability of target and $\gamma \left(j\right)$ is the expected number of measurements from the target.

The update for detected targets is

$$D_{k|k}^D(x,W)=\sum _{j=1}^{J_{k|k-1}}{\omega }_{k|k}^{\left(j\right)}\mathcal{N}(x;m_{k|k}^{\left(j\right)},P_{k|k}^{\left(j\right)})$$

(16)

$${\omega }_{k|k}^{\left(j\right)}={\omega }_P\frac{{\Gamma }^{\left(j\right)}{p_D}^{\left(j\right)}}{d_W}{\mathsf{\Phi }}_W^{\left(j\right)}{\omega }_{k|k-1}^{\left(j\right)}$$

(17)

$${\omega }_P=\frac{{\prod }_{W\in P}{d}_W}{{\sum }_{P^{\prime }\angle Z^{\prime }}{\prod }_{W^{\prime }\in P^{\prime }}{d_W}^{\prime }}$$

(18)

$$d_W={\delta }_{\left|W\right|,1}+\sum _{j=1}^{J_{k|k-1}}{\Gamma }^{\left(j\right)}{p_D}^{\left(j\right)}{\mathsf{\Phi }}_W^{\left(j\right)}{\omega }_{k|k-1}^{\left(j\right)}$$

(19)

where the coefficient ${\Gamma }^{\left(j\right)}$ and ${\mathsf{\Phi }}_W^{\left(j\right)}$ are

$${\Gamma }^{\left(j\right)}=e^{-\gamma \left(j\right)}{\left({\gamma }^{\left(j\right)}\right)}^{\left|W\right|},{\mathsf{\Phi }}_W^{\left(j\right)}={{\varphi }_W}^{\left(j\right)}\prod _{z_k\in W}\frac{1}{{\lambda }_k{c}_k\left(z_k\right)}$$

(20)

${\delta }_{\left|W\right|,1}$ is the Kronecker delta and the coefficient ${\varphi }_W^{\left(j\right)}$ is

$${{\varphi }_W}^{\left(j\right)}=\mathcal{N}\left(z_W\right|H_K{m}_{k|k-1}^{\left(j\right)},R_K+H_K{P}_{k|k-1}^{\left(j\right)}{H}_K^{\mathrm{T}})$$

(21)

$$H_K=\underset{\left|W\right|\mathrm{times}}{\underbrace{{\left[H_k^{\mathrm{T}},H_k^{\mathrm{T}},\cdots ,H_k^{\mathrm{T}}\right]}^{\mathrm{T}}}}$$

(22)

$$R_K=\mathrm{BLKdiag}\underset{\left|W\right|\mathrm{times}}{\underbrace{\left(R_k,R_k,\cdots ,R_k\right)}}$$

(23)

Here, the standard Kalman filter is used to obtain the mean $m_{k\left|k\right.}^{\left(j\right)}$ and covariance $P_{k|k}^{\left(j\right)}$ of the Gaussian components.

$$m_{k\left|k\right.}^{\left(j\right)}=m_{k|k-1}^{\left(j\right)}+{\mathrm{K}}_k^{\left(j\right)}\left(\right[\begin{array}{c}{z}_1\hfill \\ ⋮\hfill \\ z_{\left|W\right|}\hfill \end{array}]-H_K{m}_{k|k-1}^{\left(j\right)})$$

(24)

$$P_{k|k}^{\left(j\right)}=(\mathrm{I}-{\mathrm{K}}_k^{\left(j\right)}{H}_K)P_{k|k-1}^{\left(j\right)}$$

(25)

$${\mathrm{K}}_k^{\left(j\right)}=P_{k|k-1}^{\left(j\right)}{H}_K^{\mathrm{T}}{(R_K+H_K{P}_{k|k-1}^{\left(j\right)}{H}_K^{\mathrm{T}})}^{-1}$$

(26)

where $K_k^{\left(j\right)}$ denotes the matrix of Kalman filter gain.

To sum up, the proposed multiple close-spaced extended target tracking approach is summarized as follows.

Step 1. Calculate the predicted intensity:

$$m_{k-1}^{\left(j\right)}\to m_{k\left|k-1\right.}^{\left(j\right)},P_{k-1}^{\left(j\right)}\to P_{k\left|k-1\right.}^{\left(j\right)},{\omega }_{k-1}^{\left(j\right)}\to {\omega }_{k\left|k-1\right.}^{\left(j\right)}$$

(27)

Step 2. Determine the range of K value:

$$J_{k-1}+J_{\beta ,k}\times J_{k-1}+J_{\gamma ,k}\to K_U$$

(28)

$$J_{k-1}\to K_L$$

(29)

Step 3. Select the initial clustering centers $C^{J_{k-1}}$ by using the predictive information and obtain the first partition $P_1$ based on the above centers:

$$m_{S,k\left|k-1\right.}^{\left(j\right)}\to c_j\in C^{J_{k-1}}$$

(30)

$$Z_k\to P_1={\left\{W^{\left(i\right)}\right\}}_{i=1}^{J_{k-1}}$$

(31)

Step 4. Partition measurements: If $\frac{N_{z,k}}{\lambda }-J_{k-1}\ge 1$, it implies that the target number has been underestimated. Then, execute PMS to find the alternative initial centers of the estimated subsets in $P_1$, which contributes to more accurate partitioning results when extended targets cross each other.

$$\mathrm{PMS}\to P=\left\{P_1,P_2,\cdots \right\}$$

(32)

If this judgment condition is not satisfied, PMS directly uses the predictions of existing targets to obtain the clustering centers and partition the measurement set.

Step 5. Update the predicted intensity:

$$m_{k\left|k-1\right.}^{\left(j\right)}\to m_{k\left|k\right.}^{\left(j\right)},P_{k\left|k-1\right.}^{\left(j\right)}\to P_{k\left|k\right.}^{\left(j\right)},{\omega }_{k\left|k-1\right.}^{\left(j\right)}\to {\omega }_{k\left|k\right.}^{\left(j\right)}$$

(33)

5. Simulation Results and Performance Evaluation

In this section, the effectiveness of the proposed MCETT approach based on prediction-driven measurement sub-partitioning (PMS) for tracking of closely spaced targets is illustrated by comparing the proposed MCETT approach with the existing MCETT approaches based on different measurements partitioning strategies:

(1)

PP: The MCETT approach using the measurement partitioning of the work in [37].

(2)

SP: The MCETT approach using the measurement partitioning of the work in [27].

(3)

DP: The MCETT approach using the distance-based partitioning.

To better illustrate the tracking performance of multiple extended targets, a typical simulation scenario is considered: (A) Tracking of extended targets with typical tracks, which contains the crossing targets, spawned targets, and newborn targets. To further illustrate the tracking performance of closely spaced targets, two more specific simulation scenarios of MCETT are considered: (B) Tracking of extended targets with paralleled tracks; (C) Tracking of extended targets with crossed tracks. In each simulation scenario, there is a stationary sensor platform and multiple moving extended targets and approaches are initialized with the same target state and number without further information. Moreover, there are clutter measurements distributed randomly, and the measurements of each target may be not detected by the sensor at per time step. Both of these bring great difficulties to accurately track multiple extended targets.

We calculate the performance in the computational burden, target number estimation, and optimal sub-pattern assignment (OSPA) distance [41]. Note that the OSPA distance is chosen as the measure to evaluate the tracking performance. The computation time and partition number of measurements are jointly used to reflect the computational burden of the algorithm in simulations. The computational complexities for these approaches are compared in the CPU running time and simulations are implemented by MATLAB on Intel(R) Core(TM) i3-2130, 3.40 GHz, and 4 GB RAM. The detailed discussions and analysis are as follows.

5.1. Performance Evaluation in Tracking of Extended Targets with Typical Tracks

Scenario A is a typical tracking scenario with clutter and missed detection. It contains the tracking of crossed targets, newborn targets, and spawned targets. The true tracks and measurements are illustrated in Figure 3. Both of two targets were born at $k=1$ s and died at $k=100$ s. They are crossed at $k=50$ s. At $k=67$ s, there is a target newborn and a target spawned from the existing target. Especially when a new target is spawned from the existing target, the locations of these two targets are very close. It is another typical form of tracking closely spaced targets.

In this scenario, the surveillance area is $\left[-10001000\right]\times \left[-10001000\right]$. The target state contains the position and velocity, i.e., $X_k={\left[x_k,y_k,{\dot{x}}_k,{\dot{y}}_k\right]}^{\mathrm{T}}$, where $\left(x_k,y_k\right)$ and $\left({\dot{x}}_k,{\dot{y}}_k\right)$ are the position and velocity in the two-dimensional Cartesian coordinate system, respectively. It is assumed that each target generates measurements with the Poisson distribution (the Poisson rate is ${\gamma }^{\left(i\right)}=10,\forall i$). The clutter measurements are also generated with $\lambda =10$ at each time step. The observed measurement is denoted as $z_k^{\left(j\right)}={\left[x_k^{\left(j\right)},y_k^{\left(j\right)}\right]}^{\mathrm{T}}$. The probability of detection and survival are set to $p_S=0.99$ and $p_D=0.99$, respectively.

Each extended target is supposed to perform a nearly constant velocity motion model with the sampling interval $T=1$ s, and the dynamic and measurements models are as follows,

$$f_{k\left|k-1\right.}\left(x_k\left|x_{k-1}\right.\right)=\mathcal{N}(x_k;F{x}_k,Q)$$

(34)

$$g_k\left(z_k\left|x_k\right.\right)=\mathcal{N}\left(z_k;H{x}_k,R\right)$$

(35)

where $N\left(x;m,P\right)$ is a Gaussian density with mean m and covariance P. Here, F is the state transition matrix, Q is the process noise covariance, H is the measurement matrix, and $R_k$ is the observation noise covariance. They have the following forms,

$$F=\left[\begin{array}{cccc}1& 0& T& 0\\ 0& 1& 0& T\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right],Q={\sigma }_W^2{\left[\begin{array}{c}\begin{array}{cccc}\frac{T^2}{2}& 0& T& 0\end{array}\hfill \\ \begin{array}{cccc}0& \frac{T^2}{2}& 0& T\end{array}\hfill \end{array}\right]}^{\mathrm{T}}$$

$$H=\left[\begin{array}{c}\begin{array}{cccc}1& 0& 0& 0\end{array}\hfill \\ \begin{array}{cccc}0& 1& 0& 0\end{array}\hfill \end{array}\right],R_k={\sigma }_e^2{\mathrm{I}}_2$$

where ${\sigma }_W=2$ m/s${}^2$ is the standard deviation of process noise and ${\sigma }_e=20$ m is the standard deviation of measurement noise. The birth intensity for the existing targets is

$$D_b\left(x\right)=0.1\mathcal{N}(x;m_b^{\left(1\right)},P_b)+0.1\mathcal{N}(x;m_b^{\left(2\right)},P_b)$$

(36)

where $m_b^{\left(1\right)}={[250,250,0,0]}^T$, $m_b^{\left(2\right)}={[-250,-250,0,0]}^T$, and $P_b=\mathrm{diag}\left([100,100,25,25]\right)$.

Figure 4 gives the comparison results of target number estimation. It can be seen that PMS has a more accurate estimation of target number than DP, PP and SP especially when a new target is spawned from the existing target at $k=67$ s. This is because PMS finds relatively accurate alternative points to replace unreasonable target predictions according to the geometry of a regular polygon, which facilitates partitioning the measurements more accurately to avoid the target number underestimation.

For further evaluating the tracking performance of PMS, we compare it with DP, PP, and SP by using the OSPA distance. As shown in Figure 5, PMS outperforms DP, especially when targets are spatially close (i.e., targets are crossed at $k=50$ s and a new target is spawned at $k=67$ s). Compared with SP, we can see that PMS has the better performance in estimation of the target number and state due to their higher precision of the measurements partitioning. This facilitates the accurate estimation of the target state and number in the subsequent filtering. It also demonstrates that PMS’s strategy of replacing unreasonable target predictions with alternative points is more reliable than the loss function of the K-means++ clustering, which is very likely to inaccurately repartition the subsets.

Specifically for PP, its tracking performance is much lower than others. This main reason is that missed detection is likely to bring unreasonable partitioning results of the measurement set, not to mention that only one partition is obtained according to target predictions, which affects the MCETT performance directly. Moreover, PP cannot handle well the tracking of crossed targets, newborn targets, and spawned targets due to the dependence of target predictions. Unlike PP, PMS fully considers the possible changes of target number to narrow the range of partition number and uses the predicted target state to determine the possible clustering centers, which guarantees the accurate partition of the measurement set to improve the performance of multiple extended target tracking greatly.

As predictions of the target state and number help PMS obtain the relatively accurate partitioning results, it can be seen that compared with DP, the predictive information is more reliable than the distance information (may contain the distance between clutters with each other) for measurements partitioning when lots of clutters exist in the surveillance area. To sum up, PMS is more reliable than DP, SP, and PP. It has the better tracking performance.

Figure 6 and Figure 7 give the partitioning number and computation time of four approaches, respectively. From the comparison results, we can see that the number of measurements partitioning increases as the number of extended targets increases. In other words, the greater the number of measurements partitioning is, the longer the computation time is. Thus, the number of measurements partitioning is the major determinant of the computational burden of different MCETT approaches. Compared with DP and SP, PMS spends less time because it does not need to partition the measurements as much as DP and SP do. This demonstrates that the proposed approach (i.e., PMS) is superior to existing approaches in measurements partitioning for real-time tracking of multiple extended targets. Although PP has the least partition number and computational time, its tracking performance is worse than other algorithms from Figure 5.

From Figure 4, Figure 5 and Figure 6, it can be concluded that our approach can handle well the tracking of existing targets, newborn targets, and spawned targets. It not only reduces the computational burden largely for practical tracking applications, but more importantly improves the MCETT performance greatly. Note that this subsection proves that the proposed measurement partitioning algorithm outperforms other existing ones in the typical tracking scenario (including the crossed targets, newborn targets, and spawned targets). For the tracking scenario with closely spaced targets, the tracking performance of the proposed MCETT approach based on PMS needs to be further evaluated in more specific tracking scenarios (i.e., subsections B and C), which is to be demonstrated later.

5.2. Performance Evaluation in Tracking of Extended Targets with Paralleled Tracks

PMS aims to deal with the measurement partitioning problem of closely spaced extended targets. Therefore, in this part, a multiple extended target tracking scenario (i.e., Scenario B) is designed to further evaluate the tracking performance of the proposed MCETT based on PMS. The true tracks (i.e., black solid lines) and measurements with clutter (i.e., black dots) are illustrated in Figure 8. The tracks of these targets are paralleled all the time, which is a typical scenario and brings a huge challenge for MCETT. Both of two extended targets were born at $k=1$ s and died at $k=100$ s. The targets’ birth intensity is

$$D_b\left(x\right)=0.1\mathcal{N}(x;m_b^{\left(1\right)},P_b)+0.1\mathcal{N}(x;m_b^{\left(2\right)},P_b)$$

(37)

where $m_b^{\left(1\right)}={[250,250,0,0]}^T$, $m_b^{\left(2\right)}={[250,180,0,0]}^T$, and $P_b=\mathrm{diag}\left([100,100,25,25]\right)$. The other simulation parameters are the same as those of the extended targets in Scenario A.

As is shown in Figure 9, PMS has much better performance than DP, SP, and PP in the target number estimation. Especially compared with PP, the estimate of the target number in PMS is more accurate. This is because PP directly fixes the predicted mean as the centroid of a target, which is likely to cause the non-information subsets. Unlike PP, PMS only uses the predicted mean of a target to find its possible centroid, which is more flexible and improves the accuracy of partition results. Besides, Figure 9 also implies that the strategy used in PMS is more effective than that of SP, in which K-means++ clustering is utilized to repartition the unreasonable subsets. Although SP can, to some extent, handle the partitioning problem in DP due to the dense distribution of measurements, the degradation of target number estimation performance still cannot be avoided, i.e., relatively accurate partitioning results are not available in some cases. This lies in the loss function of K-means++ clustering, which is very likely to obtain inaccurate repartitioning results. However, in PMS, the unreasonable target prediction is reasonably replaced by the alternative points so that measurements are divided into two subsets rather than one subset, which contributes to better target number estimation performance.

Figure 10 shows the OSPA distance of the compared approaches. In this figure, PMS has much better tracking performance than DP, SP, and PP. This reflects that the strategy of predicted position is more reliable than K-means++ in SP. This figure also illustrates that the predictive information (instead of the distance information) is more appropriate to be utilized for measurements partitioning, because the distance information is very likely to wrongly divide the measurements from more than one target into one subset in closely spaced target tracking.

The comparison of partitioning number is shown in Figure 11. Compared with DP and SP, PMS uses fewer partitions, which can greatly reduce the computational burden. Combined with the comparison results of the estimation performance of the target number and state in Figure 10, it can be seen that the tracking performance by PMS does not degrade due to the reduction of the partition number. This is because the strategy in PMS is useful to obtain relatively accurate partitioning results. Besides, from Figure 11, PP has the lowest number of partitioning, only one partition. However, its tracking performance is worse than PMS because PP may obtain non-information partitions, which undoubtedly causes an inaccurate estimation of target number and state. Thus, we conclude that the good tracking performance depends on the accurate measurements partitioning, instead of merely the number of partitions.

The computation time of these four algorithms is given in Figure 12. Combined with the partition number results from Figure 11, we can see that partition number is the main factor affecting the computational time. The computational time increases with the increase of partition number. Due to the lower partition number compared with DP and SP, PMS saves a lot of computational time, which is very significant for real-time target tracking. More importantly, from the above total figures, the tracking performance of PMS remains accurate, which is much better than DP, SP, and PP.

To sum up, PMS outperforms other approaches when tracking of extended targets with tracks-paralleled. Its computation burden is greatly reduced without the loss of tracking performance.

5.3. Performance Evaluation in Tracking of Extended Targets with Crossed Tracks

From the above analysis, it can be seen that using alternative points to replace the unreasonable target prediction is useful to obtain relatively accurate measurement partitioning results, which makes PMS effectively solve the cardinality underestimation problem of closely spaced targets. To further evaluate the tracking performance of MCETT approach using PMS, a multiple extended target tracking scenario (i.e., Scenario C) is designed, in which the tracks are crossed. Figure 13 shows the true trajectories of the extended targets with cluttered measurements in Scenario C. All extended targets were born at $k=1$ s and died at $k=100$ s. Roughly from $k=45$ s to $k=55$ s, all these targets are getting very spatially close and crossing from each other, which is another typical scenario for tracking of multiple extended targets. This scenario, in which the dense distribution of measurements bring huge difficulty for measurement partitioning, is suitable to test the proposed measurement partitioning algorithm, i.e., PMS. The birth intensity is

$$\begin{array}{c}{D}_b\left(x\right)=0.1\mathcal{N}(x;m_b^{\left(1\right)},P_b)+0.1\mathcal{N}(x;m_b^{\left(2\right)},P_b)+\hfill \\ 0.1\mathcal{N}(x;m_b^{\left(3\right)},P_b)+0.1\mathcal{N}(x;m_b^{\left(4\right)},P_b)+\hfill \\ 0.1\mathcal{N}(x;m_b^{\left(5\right)},P_b)+0.1\mathcal{N}(x;m_b^{\left(6\right)},P_b)\hfill \end{array}$$

(38)

where $m_b^{\left(1\right)}={[-500,250,0,0]}^{\mathrm{T}}$, $m_b^{\left(2\right)}={[250,500,0,0]}^{\mathrm{T}}$, $m_b^{\left(3\right)}={[250,-500,0,0]}^{\mathrm{T}}$, $m_b^{\left(4\right)}={[-500,-250,0,0]}^{\mathrm{T}}$, $m_b^{\left(5\right)}={[-50,450,0,0]}^{\mathrm{T}}$, $m_b^{\left(6\right)}={[450,50,0,0]}^{\mathrm{T}}$ and $P_b=\mathrm{diag}\left([100,100,25,25]\right)$. The other simulation parameters are the same as those of the extended targets in Scenario A.

In this scenario, PMS is less affected by the underestimated target number when tracking of extended targets with tracks crossed and outperforms other measurement partitioning algorithms (i.e., DP, SP, and PP). The target number estimation of four approaches is shown in Figure 14. It can be seen that PMS has a much better estimation performance of target number than PP and the other two approaches. Especially when targets are crossing, PMS uses the alternative points to replace the unreasonable target predictions, which can greatly avoid inaccurate measurement partitions, i.e., measurements are accurately divided into six subsets rather than one subset. Compared with DP and SP, which wrongly divide the measurements generated from more than one target into one subset when the measurements are densely distributed, this contributes to better performance in estimation of the target number.

The OSPA distance of the compared approaches is shown in Figure 15. From Figure 15, we can see that PMS has much better tracking performance than DP, SP, and PP. The main reason for this is that the tracking performance of the PMS is closely related to the target predictions. More importantly, the unreasonable target predictions are replaced by other suitable alternative points, which greatly improve the accuracy of measurement partitioning results. Besides, considering that the target prediction is calculated by the precious target estimation, the more accurate the target estimation is, the more reliable information the target states prediction provides. This facilitates more accurate partitions of the measurement set and more accurate target estimation. Accordingly, the MCETT performance of PMS will get better and better. Figure 15 also illustrates that PMS is more appropriate to be utilized for tracking of crossed targets. In this case, distance information falls to accurately divide the measurements because of the density distribution of measurements. Though SP works better than DP by using K-means++ clustering, the loss function of K-means++ clustering may lead to the unreasonable subsets, which makes the degradation of target tracking performance. Here, PMS uses the alternative points to replace the unreasonable target predictions and obtain more accurate partitions, which greatly improves the target tracking performance.

The comparison of partitioning number is shown in Figure 16. The partition number of PMS is much lower than that of DP and SP. From $k=45$ s to $k=55$ s, the partition number of DP and SP is a little lower than PMS because measurements are densely distributed making the number of distance thresholds reduced. However, combined with the comparison of tracking performance in Figure 15 , it can be seen that the partitions obtained according to these distance thresholds contribute little to the tracking performance. Unlike DP and SP, when targets are crossing, PMS still has almost the same number of measurement partitions as that at previous time steps. Moreover, these partitions obtained by PMS are more accurate than these of DP and SP (as seen in Figure 15). It means that PMS does not add computation time to achieve better tracking performance in this scenario. Because PMS only replaces the unreasonable target predictions in each partition by alternative points to obtain more reliable target centers, which does not increase the extra partitions. The analysis of PP and PMS is detailed in the above subsection.

Here, the computation time of four algorithms is given in Figure 17. Combined with Figure 16, we can see that the computation time decreases rapidly when the number of partitions decreases, which implies that the number of partitions can directly affect the tracking speed.

In summary, simulation results and performance evaluation demonstrate that our approach outperforms approaches in Scenarios A, B, and C. It can save much computational time because of the limited range of partitioning numbers. Besides, the strategy of using modified predictive information is proved to be more reliable for obtaining better tracking performance. In a word, the tracking approach based on PMS can successfully realize the adaptive tracking of multiple closely spaced extended targets.

6. Discussion

As shown in the above simulation results, the tracking performance of the distance-based measurement partitioning algorithms (e.g., SP and DP) is at the cost of computational burden. Compared with the distance-based measurement partitioning algorithms, the measurement partitioning algorithms based on target predictions have less computational burden for a complete target tracking cycle. This is because only one partition is used for measurement partitioning. However, these algorithms (e.g., PP) may not obtain stable and accurate target tracking performance in the missed detection scenarios due to the dependence of target predictions. Additionally, DP and PP are very likely to underestimate the target number when targets are crossed or parallel. Although SP has a specific strategy for repartitioning the unreasonable subsets, the accuracy of partitioning results needs to be further improved without a loss of computational burden.

Unlike PP, PMS deals well with the clutter and missed detection scenarios. Moreover, it obtains more accurate estimation performance of the target state and number compared with DP and SP, especially for tracking closely spaced targets. The main reason is that PMS only uses the predicted location of the survival target to obtain the most likely partitions, which facilitates eliminating the inaccurate partitions. More importantly, it fully considers and effectively solves the measurement partitioning problem that the predictive information is not suitable for partitioning the set of measurements in the tracking scenario with targets spatially close. Note that this modification of target predictions does not add extra partitions to achieve better tracking performance. With the limitation of partition number, PMS has a higher tracking speed than DP and SP to achieve accurate estimates of target number and state, which is significant for applications in a real-time target tracking scenario.

7. Conclusions

To improve the MCETT performance in the tracking scenario with spatially close targets and to reduce the computational burden, an effective prediction-driven measurement sub-partitioning algorithm (PMS) has been proposed in this paper. By utilizing the target predictions and considering the most likely partitions, PMS can obtain high partitioning accuracy without spending too much time. Moreover, to further improve the robustness of predicted information, the bias predictive information is fully discussed when the number of targets is underestimated in many practical tracking scenarios. More importantly, these target predictions are reasonably replaced by the alternative points with a correct number to repartition the inaccurate subsets, which is its major advantage over other existing approaches.

Due to the concise mathematical forms and favorable measurement partitioning strategies, PMS is simple to implement. This facilitates the derivation of an efficient MCETT approach in the framework of the ET-PHD filter and enables one to estimate the target number and state jointly with promising effectiveness. Furthermore, the cardinality underestimation in closely spaced extended target number may be avoided. Therefore, a large range of the measurement partitioning problems in MCETT can be handled. Simulation results demonstrate that our approach has much less computational time than other existing approaches without degrading tracking performance. In summary, our approach may pave the way for fast and accurate tracking of multiple extended targets in noise and clutter environments.