SUN Lili,CAO Yunhe,WU Wenhua,and LIU Yutao

1.National Laboratory of Radar Signal Processing,Xidian University,Xi’an 710071,China;2.Science and Technology on Communication Networks Laboratory,Shijiazhuang 050081,China

Abstract: Since the joint probabilistic data association (JPDA) algorithm results in calculation explosion with the increasing number of targets, a multi-target tracking algorithm based on Gaussian mixture model (GMM) clustering is proposed. The algorithm is used to cluster the measurements, and the association matrix between measurements and tracks is constructed by the posterior probability. Compared with the traditional data association algorithm, this algorithm has better tracking performance and less computational complexity. Simulation results demonstrate the effectiveness of the proposed algorithm.

Keywords: multiple-target tracking, Gaussian mixture model(GMM), data association, expectation maximization (EM) algorithm.

1.Introduction

Multi-target tracking technology has been widely used in defense systems, air traffic control systems and surveillance systems.The core of multi-target tracking is data association.Data association is mainly to solve the problem of association between the targets and measurements[1,2].Many data association algorithms have been proposed so far, such as nearest neighbor data association (NNDA),probabilistic data association (PDA), joint PDA (JPDA)algorithm and multiple hypothesis tracking (MHT) [3,4].The NNDA algorithm proposed in[5]selects the measurement which is the closest to the predicted location for status update.The method is simple to calculate.However,it causes associated errors in the dense clutter environment.Bar-Shalom proposed a PDA algorithm in[6].This method considers that the probability of each effective measurement resulting from the target is different although all effective measurements may result from the target.Because the PDA algorithm is mainly used to solve the problem of single target tracking in a clutter environment,Bar-Shalom proposed the JPDA based on PDA in [7], which is considered as the best data association algorithm in the clutter environment.However,with the increase of the target number,the computational complexity also increases exponentially.Therefore,it is difficult to use in the case of real-time tracking especially when the number of the targets is large.The MHT algorithm assumes that each new measurement may originate from an existing target, a new target or a clutter,then establish multiple hypotheses in one time,and finally achieve multi-target tracking by hypothesis evaluation, deletion and merging. However, the calculation amount of the algorithm increases exponentially with the increase of the number of targets and clutters[8].In order to reduce the computation of JPDA,some improved JPDA algorithms have been proposed.Qin et al.proposed a simplified JPDA(SJPDA)algorithm in[9].This method proposes the approximate calculation of the cluster probability matrix in order to reduce the computational complexity.Shi et al.proposed an improved data association algorithm in which the same source observations are classified into the same sets and the relevant confirmation matrix of each area is constructed[1].In recent years,probability hypothesis density(PHD)based on random finite sets(RFS)has received much attention for studying multi-target tracking problems.It transforms the complex multi-target problem into the single-target problem, which not only effectively avoids the complex data association problem in the traditional multi-target tracking method,but also has high realtime performance.However,it still requires solving multidimensional integrals. The Gaussian mixture-PHD (GMPHD)and sequential Monte Carlo-PHD(SMC-PHD)have been proposed to solve the problem. Therefore, the PHD algorithm is widely used in multi-target tracking. However,the GM-PHD algorithm is prone to false alarms and missing detection. The SMC-PHD is computationally in-efficient due to the large number of particles required for approximation,especially in the case of dense clutter[10].

In multi-target tracking, data association is actually a classification problem.Clustering analysis,also known as data segmentation, needs to group a data object, so that the correlation between the objects within each group is closer than that between the objects from groups to groups.Ashraf et al. proposed the fuzzy c-means clustering association algorithm in [11]. It uses fuzzy c-means clustering to calculate the association membership.A possibilistic data association algorithm based on the possibility of fuzzy clustering was proposed in[12].As its simplicity and ease of implementation[13],the Gaussian mixture model(GMM)clustering method was used in multi-target tracking.

We use the GMM to solve the data association problem in this paper.The GMM is mainly used in the field of image processing. As far as we know, the GMM has not been used for data association problems before. It avoids the complex matrix splitting in the JPDA.Compared with the JPDA algorithm, this method reduces the computational load. The method in [13] is mainly used to solve the problem of face recognition. In this paper the GMM is used to solve data association problems.The algorithm processes measurements by GMM clustering.The parameters are calculated by the expectation maximization(EM)algorithm, and the association matrix between measurements and tracks is constructed by the posterior probability.It avoids the complex matrix splitting in the JPDA.Compared with the JPDA algorithm, this method reduces the computational load.

This paper is organized as follows. The signal model is described in Section 2. Section 3 proposes the GMM clustering data association algorithm for multi-target tracking.In Section 4,some simulation results are presented to demonstrate the effectiveness of the proposed association algorithm.Finally,this paper is concluded in Section 5.

2.System model

2.1 Multi-target tracking model

Multi-target tracking plays an important role in military and civil fields. The basic idea of traditional multi-target tracking is to convert the multi-target tracking problem into a single-target tracking problem by matching the measured values and targets. A single-target model only involves a tracking issue, and a multi-target model involves tracking and data association issues. Multi-target tracking corresponds to the procedure of processing the received measurements to maintain the estimation of the current state of multiple targets [14–16]. The basic procedure of the multi-target tracking is shown in Fig.1.

Fig.1 Basic procedure of multi-target tracking

The state model of multi-target tracking can be expressed as

wherext(k) is the state vector,Ft(k) is the state transition matrix,Gt(k) is the noise gain matrix, andwt(k) is the Gaussian noise with zero mean and its covariance matrix is given by

where(·)Trepresents transposition,Q(k)is the variance,andδ(k ?m)is the Kronecker delta function.

The measurement model can be written as wherezt(k)is the measurement vector,H(k)is the measurement matrix,andv(k)is the Gaussian noise with zero mean and its covariance matrix is written as

whereR(k)is the variance.

The predictions of the target state and measurement using the dynamic model are given by

wherePt(k+1|k)is the prediction of the covariance matrix,andSt(k+1)is the innovation covariance matrix.

As seen in Fig.1,the multi-target tracking problem includes many aspects,such as adaptive algorithm,tracking gate,data association,tracking maintain,and tracking initiation and termination[1,17].For multi-target tracking,it is very difficult to determine the correspondence between the targets and the measurements,for the existence of multiple targets and environmental interference [18]. Before filtering,the measurement should be attributed to a certain target,which is the problem of data association.For multitarget tracking cases, data association is the key problem and can be solved by the clustering algorithm.

2.2 GMM

The GMM has been widely used in the fields of pattern recognition, information processing and data mining[19,20]. The probability density function of the GMM is given by

whereyis the classified data,Iis the Gaussian component,μiis ann-dimensional mean vector,Σiis ann×ncovariance matrix, andαiis the mixture coefficient satisfying the condition ofNote thatis a Gaussian probability density function and can be written as

where (·)?1represents the inverse operation, andμiandΣiare the corresponding mean and covariance parameters of the GMM.

In general,the parameters of the mixture model are estimated through the maximum likelihood method.Due to the good performance in solving maximum likelihood estimation of the mixture model,the EM algorithm is an effective method to estimate the parameters of the GMM[21].

The result of GMM clustering is shown in Fig. 2. As can be seen from the figure, the GMM algorithm divides the given data into three categories, and classifies sample points by calculating the probability that each sample point belongs to each class. It can be seen that the GMM has a good clustering result.

Fig.2 GMM clustering result

3.Data association algorithm based on GMM clustering

In multi-target tracking,data association is actually a classification problem. Clustering is the classification of objects with similar properties[22].Clustering analysis needs to group a data object,so that the correlation between the objects within each group is closer than that between the objects from groups to groups. That would be the reason why clustering has been used on data association.

The proposed data association algorithm considers the predicted position of the targetas the initial mean vectorμ1and the innovation covariance of the measurementS(k+1)as the initial covariance matrixΣ1.The initialα1equalswhereMis the number of targets.

Calculate the posterior probability ofβj.

whereβjis the targetandyjis the effective measurement.

Updateμi,Σiandαiparameters as

whereJis the number of effective measurements.

Evaluate the log likelihood

Repeat calculating(14)–(17)until the likelihood function increases little or no more.Then parameters converge.The association matrixUcan be obtained,given by

wherejcorresponds to the measurement andicorresponds the target.The proposed algorithm searches the maximum posterior probability in the association matrixU, and the value is denoted asγjmaxi.Repeat the above steps until all measurements and targets are associated.

The proposed multi-target tracking algorithm based on GMM clustering is summarized as follows.

Step 1Calculate the prediction of target state and measurement via(5)and(6).

Step 2The initialγjiis calculated by(14)and according to(15)–(17),μi,Σiandαiare updated.

Step 3Repeat calculating(14)–(17)and the associated matrixUis obtained when parameters converge.

Step 4Find the maximumγjmaxiin the association matrixUto associatejandi. The search for the largest membership value should be continued, until the last observation and target are associated.

Step 5The Kalman filter is used to track targets.

4.Simulation results

A tracking example with four crossing targets is considered next.The initial target states are in Table 1.The run time is evaluated on a PC, where the specifications are as follows: Windows 7,i7-7700CPU@3.60 GHz and 8 GB RAM.The software platform is Matlab R2015b.

Table 1 Original position and speed of the targets

The sampling intervalTof the sensor is 1 s and the number of Monte Carlo run is 50. The process noise and observation noise are set asRii= 0.022 5 km2andQii= 10?4km2, respectively. The clutter is generated randomly over the whole surveillance region.The number of clutters is assumed to be of Poisson with density and set asλ= 0.625 km?2.The probability of target detection is set toPD= 0.95.The threshold probability of the target tracking range gate is set toPg=0.99.

Fig.3 shows that the tracking trajectories of targets are consistent with the general trend of the real trajectories.The SJPDA was proposed in[9],which approximates calculation of the cluster probability matrix to reduce the computational complexity.The SJPDA algorithm reduces the computation by sacrificing the tracking accuracy.The association matrixUis constructed by posterior probability in the GMM method. As can be seen from Fig. 3, all the three algorithms can track the targets effectively.

Fig.3 Tracking result

Fig.4 shows the root mean square error(RMSE)of the three methods. The RMSE of SJPDA is higher than that of the proposed method. The RMSE of JPDA is slightly larger than that of the GMM.It can be seen that the GMM algorithm can effectively track targets,which is consistent with the theory.

Fig.4 Location RMSE for four targets

Table 2 shows the average RMSE of three algorithms.Because the SJPDA approximates the cluster probability matrix,it causes the tracking accuracy to decrease.The average RMSE of SJPDA is higher than that of the other two methods.The average RMSE of the GMM is slightly lower than that of the JPDA.It can be seen that the GMM algorithm is efficient.

Table 2 Average RMSE of GMM,JPDA and SJPDA algorithms

Table 3 shows the comparison of three algorithms in run time. The average time is the average of multiple Monte Carlo experiments.The operation time of the JPDA algorithm increases sharply with the increase of targets,and its run time is larger than that of the other two methods.Moreover, the time of the GMM algorithm is shorter than that of the SJPDA.In the environment of real-time target tracking,it can be seen that the GMM algorithm is superior to JPDA.

Table 3 Average run time of GMM,JPDA and SJPDA algorithms

5.Conclusions

A new multi-target tracking algorithm based on GMM clustering is proposed. The parameters of GMM are calculated by the EM algorithm. Then the posterior probability is calculated and the association between measurements and tracks is determined by the maximum posterior probability.Compared with the traditional data association algorithm,the proposed algorithm can reduce the computational complexity.Simulation results show that the proposed method is capable of tracking multiple targets efficiently.