# Multiple Extended Target Tracking Algorithm Based on Spatio-Temporal Correlation
## 3 Partition Method Based on Spatio-Temporal Correlation
### Division of Newborn Target Measurement Set
Each row in the matrix \(Y\) is clustered as a new data point in the \(K\) dimensional space, and the K-means++ clustering algorithm is used to obtain the clustering results \(C=\left\{C_{1},\cdots,C_{K}\right\}\). The measurement \(z_{k}^{i}\) belongs to the \(j\)th class, when the \(i\)th row of the matrix \(Y\) is clustered into the \(j\)th class. The set of measurements \(\hat{Z}_{k}\) is then partitioned into \(K\) classes, and \(K\in[K_{l},K_{u}]\), \(K=K+1\). Then, a clustering result \(class(K)\) of the measurement set \(\hat{Z}_{k}\) is obtained. * Repeat the previous step until the condition \(K\in[K_{l},K_{u}]\) is not satisfied, and finally obtain the measurement division result \(P_{k}=\bigcup\limits_{K\in[K_{l},K_{l}]}class(K)\) at time \(k\). * For each partition result \(class(K)\), the Gaussian term \(\left\{w_{k|k-1}^{i},m_{k|k-1}^{i},P_{k|k-1}^{i}\right\}_{i=1}^{I_{kk-1}} \bigcup\limits_{k,B}^{i}m_{k,B}^{i},P_{k,B}^{i}\right\}_{i=1}^{n_{B}}\) is updated in the update step of ET-GM-PHD filtering algorithm, and the updated Gaussian term is given by \(\left\{w_{k}^{i},m_{k}^{i},P_{k}^{i}\right\}_{i=1}^{I_{k}}\). * The union of the updated Gaussian terms is \(\left\{w_{k}^{i},m_{k}^{i},P_{k}^{i}\right\}_{i=1}^{I_{k}+I_{u}}\). After pruning and merging, the target state at time \(k\) is extracted. The proposed algorithm is shown in Figure 1. Firstly, the measurement set is divided into the living target measurement set and the newborn target measurement set, and the computational complexity is \(O(|Z|)\). For the surviving target measurement set, since the number of clusters required is known in advance, the computational complexity of K-means++ is \(O\big{(}n_{k}^{2}\big{)}\), where \(n_{k}\) is the number of surviving targets, and the computational complexity of GM-PHD update step is \(O(J_{k-1}\times n_{k})\), where \(J_{k-1}\) is the number of Gaussian components at the previous time. For the newly born target measurement set, the computational complexity is, at most, \(O\big{(}\big{|}Z_{k}\big{|}^{2}\big{)}\). Suppose that the number of remainingmeasurements in the measurement set \(Z_{\text{L}}\) after processing by DBSCAN algorithm is \(N\), the computational complexity of spectral clustering is, at most, \(O\left(N^{3}\right)\). When the number of measurements is large, the \(k\) of the directed kNN graph is far less than \(N\), and its similarity matrix is the sparse matrix, so the calculation efficiency is high. Assume that the number of edges of the directed kNN graph is \(m\) and the computational complexity of the eigenvector is \(O(m\times N)\). The computational complexity of the ET-GM-PHD update step is \(O\left(J_{k\text{-}1}+n_{x}^{2}\frac{P}{p}\mathrm{P}_{p}\right)\), where \(\mathrm{P}_{p}\) denotes the number of partitions and \(n_{x}\) is the number of iterations, while the time complexity of distance partition is \(O\left(\left|Z\right|^{4}\right)\). **Remark 1**. : _When there are a large number of extended targets in the scene, and the extended targets are close to each other and move in parallel with variable speed, the distance division method only may fail to divide the measurement set. In order to improve the tracking performance, on the basis of the method proposed in this paper, multiple methods can be combined to further accurately divide the target measurement set, including gating, partitioning, assignment, etc. [6; 20; 21; 22]._  
Figure 1: Partitioning method based on spatio-temporal correlation. The flowchart of the computational complexity involved in each block of the proposed tracking method is presented in Figure 2.