# Multiple Extended Target Tracking Algorithm Based on Spatio-Temporal Correlation
## 3 Partition Method Based on Spatio-Temporal Correlation
### Division of Newborn Target Measurement Set  
It is assumed that the location of the newborn target and the living target are far apart in the sensor monitoring area, so that the measurements of the living target and the newborn target are less correlated. Under this assumption, the measurements of the newborn target do not exist in the set \(\tilde{Z}_{k}\), so \(Z_{\mathrm{L}}=Z_{k}-\tilde{Z}_{k}\) will only include the measurements of the newborn target (if there is a newborn target at the current time) and clutter measurements. The steps of measurement set division for newborn targets are as follows:  
1. The measurement set \(Z_{\mathrm{L}}\) is brought into the processing step of the DBSCAN clustering algorithm for preprocessing. The purpose of this step is to remove the clutter, where \(M=4\) is the minimum number of measurements contained in the neighborhood \(\varepsilon\) (\(\varepsilon=100\)) of the measurement. Furthermore, determine whether there is a cluster unit in the set; if so, go to step 2; otherwise, go to step 4. 2. The set of measurements processed by the DBSCAN clustering algorithm is \(\tilde{Z}_{k}\), the number of clusters is \(K_{p}>0\), and \(\tilde{Z}_{k}\) only consists of measurements generated by extended targets. To this end, a novel SNN method based on directed k-nearest neighbors (kNN) graph is used to cluster, for \(\tilde{Z}_{k}=\left\{z_{k}^{i}\right\}_{i=1}^{n}\), \(k=8\). The SNN of a directed kNN graph is defined as follows: \[N_{i}\cap N_{j}=\left\{ \begin{array}{ll}N_{i}\cap N_{j}\cup\left\{z^{ij} \right\}&\text{ if }z^{i}\leftrightarrow z^{j}\\ N_{i}\cap N_{j}&\text{ otherwise}\end{array} \right.\] (4) Following the above definition, the similarity between two centers of mass in a directed kNN graph is calculated as follows: \[w_{ij}=\sum_{z^{i}\in N_{i}\cap N_{j}}\left(k-i_{s}^{th}+1\right)\left(k-j_{s }^{th}+1\right)\] (5) The specific method is described as follows:  
* Calculate the similarity matrix \(W\) of the measurement set \(\tilde{Z}_{k}\) according to the similarity defined in Equation (5), i.e., \[W= \begin{pmatrix}w_{11}&w_{12}&\cdots&w_{1n}\\ w_{21}&w_{22}&\cdots&w_{2n}\\ \vdots&\vdots&\cdots&\vdots\\ w_{n1}&w_{n2}&\cdots&w_{nn}\end{pmatrix} \] (6) Then, the dimension of \(W\) is \(n\times n\), and \(W\) is an asymmetric matrix. * Spectral clustering is used to solve the graph partition problem for the calculated similarity matrix \(W\). First, we compute the unnormalized Laplacian matrix \(L\), as follows: \[L=D-W\]where  
\[D=\left( \begin{array}{cccc}d_{1}&0&\cdots&0\\ 0&d_{2}&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&d_{n}\end{array} \right)=\left( \begin{array}{cccc}\sum\limits_{j=1}^{ n}w_{1j}&0&\cdots&0\\ 0&\sum\limits_{j=1}^{n}w_{2j}&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&\sum\limits_{j=1}^{n}w_{nj}\end{array} \right) \tag{8}\]
* Calculate the normalized Laplacian matrix \(L^{s}=D^{-1/2}LD^{-1/2}\). * Build the matrix \(U\). Since the matrix \(U\) is not a binary representation, we treat it as a new data matrix, which is denoted by the following: \[U=\left( \begin{array}{cccc}|&|&&|\\ u_{n}&u_{n-1}&\cdots&u_{n-K+1}\\ |&&|&&|\end{array} \right)=\left( \begin{array}{cccc}u_{n,1}&u_{n-1,1}&\cdots &u_{n-K+1,1}\\ u_{n,2}&u_{n-1,2}&\cdots&u_{n-K+1,2}\\ \vdots&\vdots&\ddots&\vdots\\ u_{n,n}&u_{n-1,n}&\cdots&u_{n-K+1,n}\end{array} \right)\] (9) where \(K\) denotes the number of clusters, \(K\in[K_{l},K_{u}]\), \(K=K+1\), \(K_{l}=K_{p}\), \(K_{u}=K_{l}+\left[\frac{n}{\beta}\right]\), \(n\) is the number of measurements in the measurement set \(\hat{Z}_{k}\), and \(\beta\) is the measurement rate of the extended target. * Normalize each row of the matrix \(U\) as follows: \[y_{i}=\frac{1}{\sqrt{\sum\limits_{j=1}^{K}\mu_{n-j+1,j}^{2}}}(u_{n,i},u_{n-1,j},\ldots,u_{n-K+1,j})^{T}\] (10) \(Y=\left\{y_{1}^{T},\ldots,y_{n}^{T}\right\}\in\mathbb{R}^{n\times K}\) is obtained.