Track-Before-Detect Algorithm Based on Optimization Particle Filter

Abstract

An improved track-before-detect (TBD) algorithm based on the Cubature particle filter is an efficient approach for weak target detection and track under low signal to noise radio environment. Under the framework of particle filter, the algorithm which combines the particle filter with cubature kalman filter (CKF) algorithm is presented to generate the important density function of particle filter. The simulation results demonstrate that the improved algorithm can provide stable and reliable detection as well as accurate tracking.

75.1 Introduction

The Track-Before-Detect (TBD) [1] is good for weak target detecting and tracking in low signal to noise radio (SNR) environment. The method uses the original measurement data of the sensor directly to promote SNR by accumulating target information for a period of time. At the same time the target is being joint detected and estimated, the detected results and target track are announcing.

In recent years, beasuce Particle filter (PF) [2] is not the limit of the nonlinear non-Gaussian problem. The Track-Before-Detect algorithm based on PF has been a lot of attention [3–8]. This is a crucial problem, which affect real-time and tracking accuracy of PF-TBD. In the Paper [5, 6], these described that the algorithm, which Rao-Blackwellised particle filter-based track-before-detect algorithm for Over-the-horizon radar target. But The algorithm requires a state-space model for condition of linear Gauss model. In the Paper [7], it could avoid the sample impoverishment problem, but convergence problem can not be well guaranteed and operation time is long time. In the Paper [8], it described that the TBD algorithm based on gauss particle filtering avoided resampling and achieved relatively easy. But It required the posterior probability density for gauss distribution. So it’s application was restricted.

In order to improve the accuracy and the algorithm running time relationship, this article proposed TBD method based on cubature particle filter. In the tracking phase, the algorithm uses CKF (cubature kalman filter) to construct of the particle filter importance proposal function. The simulation results demonstrate that the algorithm can be obtained under higher filtering accuracy in a small number of particles, meet the requirements of real-time control, and strong robustness.

75.2 Problem Description

75.2.1 State Model

Assuming that the target is in uniform motion in X–Y plane. System state equation is as follows.

$$ \text{X}_{k} = \text{F} \text{X}_{k - 1} + \text{w}_{k - 1} $$

(75.1)

Where $\text{X}_{k} = [x_{k} ,\dot{x}_{k} ,y_{k} ,\dot{y}_{k} ,I_{k} ]^{T} ,\,(x_{k} ,y_{k} ),\,(\dot{x}_{k} ,\dot{y}_{k} )$ and $I_{k}$ expresses position, speed and strength of the target. $\text{w}_{k}$ is a i.i.d process noise vector. $\text{Q}_{k}$ is the process noise $\text{w}_{k}$ covariance matrix.

State transition matrix is as follows.

$$ \text{F} = \left[ {\begin{array}{*{20}c} {\text{F}_{x} } & {} & {} \\ {} & {\text{F}_{x} } & {} \\ {} & {} & 1 \\ \end{array} } \right],\;\text{F}_{x} = \left[ {\begin{array}{*{20}c} 1 & T \\ 0 & 1 \\ \end{array} } \right] $$

(75.2)

The process noise covariance is as follows.

$$ Q_{x} = \left[ {\begin{array}{*{20}c} {Q_{x} } & {} & {} \\ {} & {Q_{x} } & {} \\ {} & {} & {q_{2} T} \\ \end{array} } \right],\;Q_{x} = \left[ {\begin{array}{*{20}c} {\frac{{q_{1} }}{3}T^{3} } & {\frac{{q_{1} }}{2}T^{2} } \\ {\frac{{q_{1} }}{2}T^{2} } & {q_{1} T^{{}} } \\ \end{array} } \right] $$

(75.3)

Where $T$ is a sampling period. $q_{1}$ is Process noise power spectral density and $q_{2}$ is the target intensity noise power spectral density.

Definiting $E_{k} \in \{ 0,1\} ,\,1$ is that the target is presence, 0 is that the target is not exist [4]. $\{ E_{k} ,k = 0,1,2 \ldots \}$ is submitted to Markov procedure.

Definiting $P_{b} = P\{ E_{k} = 1|E_{k - 1} = 0\} ,\,P_{d} = P\{ E_{k} = 0|E_{k - 1} = 1\}$

Transfer probability matrix is as follows.

$$ \Uppi = \left( {\begin{array}{*{20}c} {1 - P_{b} } & {P_{b} } \\ {P_{d} } & {1 - P_{d} } \\ \end{array} } \right) $$

(75.4)

75.2.2 Measurement Model

Assuming that the sensor is scanning for $n \times m$ resolution cell in X–Y plane. Each resolution cell $(i,\,j)$ corresponds to each the matrix region $\Updelta_{x} \times \Updelta_{y} ,\,i = 1,2, \ldots ,n,\,j = 1,2, \ldots ,m.$ The measured value of each resolution cell $(i,\,j)$ in every moment is as follows.

$$ z_{k}^{(i,j)} = \left\{ {\begin{array}{*{20}c} {h_{k}^{(i,j)} (x_{k} ) + v_{k}^{(i,j)} } \\ {\begin{array}{*{20}c} {v_{k}^{(i,j)} }{}{}{} \\ \end{array} } \\ \end{array} } \right. \begin{array}{*{20}c} {\text{Target exist}} \\ {\text{Target not exist}} \\ \end{array} $$

(75.5)

For the remote target, $h_{k}^{(i,j)}$ is the point spread function.

$$ h_{k}^{(i,j)} (\text{x}_{k} ) = \frac{{\Updelta_{x} \Updelta_{y} I_{k} }}{{2\pi \sum^{2} }}\,\exp \left\{ { - \frac{{(i\Updelta_{x} - x_{k} )^{2} + (j\Updelta_{y} - y_{k} )^{2} }}{{2\sum^{2} }}} \right\} $$

(75.6)

Where $\sum^{{}}$ is sensor’s fuzzy degree, as the known quantity.

The measured value of $k$ is $z_{k} = \{ z_{k}^{(i,j)} ,i = 1,2, \ldots n,j = 1,2, \ldots m\} .$

The all measured value in front of all time of $k$ is as follows. $z_{1:k} = \left\{ {z_{n} |n = 1,2, \ldots k} \right\}$

75.2.3 Likelihood Function

Assuming that the every resolution cell is i.i.d. The likelihood function is as follows.

$$ p(\text{z} _{k} |\text{x} _{k} ,E_{k} ) = \left\{ {\begin{array}{*{20}l} {\mathop \prod \limits_{{i = 1}}^{n} \mathop \prod \limits_{{j = 1}}^{m} p_{{s + N}} (z_{k}^{{(i,j)}} |\text{x} _{k} )} \hfill & {E_{k} = 1} \hfill \\ {\mathop \prod \limits_{{i = 1}}^{n} \mathop \prod \limits_{{j = 1}}^{m} p_{N} (z_{k}^{{(i,j)}} ) } \hfill & {E_{k} = 0} \hfill \\ \end{array} } \right. $$

(75.7)

Where $p_{N} (z_{k}^{(i,\,j)} )$ is the likelihood function of the resolution cell $(i,\,j)$ noise. $p_{s + N} (z_{k}^{(i,\,j)} |\text{x}_{k} )$ is the likelihood function of the resolution cell $(i,\,j)$ signal and noise. Because of each resolution element of the noises are independent, and the effects of target to measure the signal intensity is limit. Likelihood ratio is as follows.

$$ \begin{aligned} L(Z_{k} |X_{k} ,E_{k} ) & = \frac{{p(Z_{k} |X_{k} ,E_{k} )}}{{p(Z_{k} |X_{k} ,E_{k} = 0)}} \\ & \approx \left\{ {\begin{array}{*{20}c} {\frac{1}{M}\sum\limits_{{m = 1}}^{M} {\mathop \prod \limits_{{i \in C_{i} (x_{k}^{m} )}} \mathop \prod \limits_{{j \in C_{j} (x_{k}^{m} )}} l(z_{k}^{{(i,j)}} |x_{k}^{m} )} } & {E_{k} = 1} \\ {1 } & {E_{k} = 0} \\ \end{array} } \right. \\ \end{aligned} $$

(75.8)

Where

$$ \begin{aligned} l(z_{k}^{{(i,j)}} |x_{k}^{m} ) & = \frac{{p_{{s + N}} (z_{k}^{{(i,j)}} |\text{x} _{k} )}}{{p_{N} (z_{k}^{{(i,j)}} )}} \\ & = \exp \left\{ { - \frac{{h_{k} ^{{(i,j)}} (x_{k}^{m} )(h_{k} ^{{(i,j)}} (x_{k}^{m} ) - 2z_{k}^{{(i,j)}} )}}{{2\sigma ^{2} }}} \right\} \\ \end{aligned} $$

(75.9)

75.3 Track-Before-Detect Algorithm Based on Cubature Particle Filter

The problem of TBD is a mixed problem. What is the solution to the TBD problem is that the target state $x_{k}$ and the joint posterior probability density $p(x_{k} ,E_{k} = 1|Z_{k} )$ are estimated in $k$ time. There is that the frame of Salmond is used.

The new algorithm that incorporates the latest observation into a prior updating phase develops the importance density function by CKF that is more close to posterior density in Nonlinear and non-Gauss [9, 10]. So a iteration steps used CKF to update particle is as follows

• Step1 Calculation Cubature point

$$ P_{k - 1/k - 1} = S_{k - 1/k - 1} S_{k - 1/k - 1}^{T} $$

(75.10)

$$ X_{i,k - 1/k - 1} = S_{k - 1/k - 1} \xi_{i} + \hat{x}_{k - 1/k - 1} $$

(75.11)

• Step2 One step prediction of state

$$ X_{i,k/k - 1}^{*} = f(X_{i,k - 1/k - 1} ) $$

(75.12)

$$ \hat{x}_{k/k - 1} = \frac{1}{2n}\sum\limits_{i = 1}^{2n} {X_{i,k/k - 1}^{*} } $$

(75.13)

$$ P_{k/k - 1} = \frac{1}{2n}\sum\limits_{i = 1}^{2n} {X_{i,k/k - 1}^{*} } X_{i,k/k - 1}^{*T} - \hat{x}_{k/k - 1} \hat{x}^{T}_{k/k - 1} + Q_{k - 1} $$

(75.14)

• Step3 Measurement update

$$ P_{k/k - 1} = S_{k/k - 1} S_{k/k - 1}^{T} $$

(75.15)

$$ X_{i,k/k - 1} = S_{k/k - 1} \xi_{i} + \hat{x}_{k/k - 1} $$

(75.16)

$$ Z_{i,k/k - 1} = h(X_{i,k/k - 1} ) $$

(75.17)

$$ \hat{z}_{k/k - 1} = \frac{1}{2n}\sum\limits_{i = 1}^{2n} {Z_{i,k/k - 1} } $$

(75.18)

• Step4 Estimated value

$$ \hat{x}_{k/k} = \hat{x}_{k/k - 1} + K_{k} (z_{k} - \hat{z}_{k/k - 1} ) $$

(75.19)

$$ P_{kk} = P_{k/k - 1} - K_{k} P_{zz,k/k - 1} K_{k}^{T} $$

(75.20)

$$ P_{zz,k/k - 1} = \frac{1}{2n}\sum\limits_{i = 1}^{2n} {Z_{i,k/k - 1} } Z_{i,k/k - 1}^{T} - \hat{z}_{k/k - 1} \hat{z}^{T}_{k/k - 1} + R_{k} $$

(75.21)

$$ P_{xz,k/k - 1} = \frac{1}{2n}\sum\limits_{i = 1}^{2n} {X_{i,k/k - 1} } Z_{i,k/k - 1}^{T} - \hat{x}_{k/k - 1} \hat{z}^{T}_{k/k - 1} $$

(75.22)

$$ K_{k} = P_{xz,k/k - 1} P_{zz,k/k - 1}^{ - 1} $$

(75.23)

Assuming that the posterior probability density of the joint target state $(x_{k} ,E_{k} )$ is $p(x_{k} ,E_{k} |z_{1:k} )$. So, the steps of the track-before-detect algorithm based on Cubature particle filter are as follows:

• Step 1 Initialization

$P_{b}$ is as appearance probability of targets. While $E_{k} = 1$, the prior distribution $p(x_{0} )$ samples from $\{ x_{0}^{(i)} \}_{i = 1}^{N}$.

$$ \hat{x}_{0}^{(i)} = E[x_{0}^{(i)} ] $$

(75.24)

$$ \hat{P}_{0}^{(i)} = E[(x_{0}^{(i)} - \hat{x}_{0}^{(i)} )(x_{0}^{(i)} - \hat{x}_{0}^{(i)} )^{T} ] $$

(75.25)

• Step 2 Calculating the predicted particle targets exist variables

According to the transfer probability matrix $\Uppi$ and $\{ E_{k - 1}^{n} \}_{n = 1}^{N}$, to calculate $\{ E_{k}^{n} \}_{n = 1}^{N}$

• Step 3 Forecasting $\hat{x}_{k/k}$ and $P_{kk}$ by CKF

For while “Newborn particle” of $E_{k - 1} = 0,E_{k} = 1$, the prior distribution $p(x_{0} )$ samples from $\{ x_{0}^{(i)} \}_{i = 1}^{N}$.

For while “Survival particle” of $E_{k - 1} = 1,\,E_{k} = 1$, $\hat{x}_{k}^{(i)}$ and $\hat{P}_{k}^{(i)}$ are estimated by CKF.

• Step 4 The normalized weights

$$ \{ \omega_{k}^{n} = \tilde{\omega }_{k}^{n} /\sum\limits_{n = 1}^{N} {\tilde{\omega }_{k}^{n} } \}_{n = 1}^{N} $$

(75.26)

• Step 5 Resampling

If $\hat{N}_{eff} < \hat{N}_{tthreshold}$, weights is $\{ \omega_{k}^{n} = \frac{1}{N}\}_{n = 1}^{N}$.

• Step 6 Statistics the number of $E_{k} = 1$, so the appearance probability of targets is as follows

$$ \hat{p}_{{E_{k} = 1}} (E_{k} = 1|z_{1:k} ) = \frac{{N_{{E_{k} = 1}} }}{N} $$

(75.27)

• Step 7 setting threshold $p_{T}$, if $\hat{p}_{{E_{k} = 1}} > p_{T}$, this describes the target appears The target state estimation value is as follows

$$ \hat{x}_{k} = \sum\limits_{n = 1}^{N} {x_{k}^{n} \cdot \omega_{k}^{n} } $$

(28)

75.4 Simulation Result

In order to verify the performance of the algorithm, there has 30 frame radar simulation data in 20 × 20 area. Every resolution cell is $\Updelta_{x} \times \Updelta_{y} = 1\times 1,\,p = 2.$ Radar located at the origin of coordinates. Scanning time of a frame is 1 s. Assuming that the target appears from 5 to 25 s for uniform motion. The initial location is (4.2,7.2), The initial velocity is (0.45,0.25). The target signal strength $I = 20,\,\Upsigma = 0.7.\,P_{b} = 0.1.\,P_{d} = 0.1$.

In order to evaluate the effect of the target tracking, this algorithm compares to UPF-TBD which is introducted in paper [14]. To definine the root mean square error is as follows:

$$ RMSE = \frac{1}{N}\sum\limits_{i = 1}^{N} {\sqrt {(x_{k} - \hat{x}_{k}^{i} )^{2} + (y_{k} - \hat{y}_{k}^{i} )^{2} } } $$

(75.30)

From Fig. 75.1, while the same number of particles (N = 4,000) is used, the performance of CPF-TBD is better than UPF-TBD in the latter tracking part in low SNR conditions(SNR = 6 dB). As shown in Table 75.1, position RMSE improves about 20 % and velocity RMSE improves about 23 %. At the same time, execution time is relatively less.

Fig. 75.1

Curve while the same number of particles (SNR = 6 dB). a The curve of the real and estimated values. b Target appearance probability. c Position RMSE. d Velocity RMSE

Table 75.1 The performance comparison in PF-TBD and CPF-TBD

From Fig. 75.2 while the different number of particles is used, the performance of CPF-TBD is nearly as same as UPF-TBD in low SNR conditions(SNR = 6 dB). while particles number of CPF-TBD (N_CPF-TBD = 3,000) is only one third of UPF-TBD N_UPF-TBD = 10,000. As shown in Table 75.1, position RMSE only worsens about 4.3 % and velocity RMSE about 0.86 % while the execution time of CPF-TBD is relatively 38.2 % of UPF-TBD.

Fig. 75.2

Curve while the different number of particles (SNR = 6 dB). a The curve of the real and estimated values. b Target appearance probability. c Position RMSE. d Velocity RMSE

75.5 Conclusion

The track-before-detect algorithm based on Cubature particle filter is proposed. The new algorithm that incorporates the latest observation into a prior updating phase develops the importance density function by CKF that is more close to posterior density in nonlinear and non-Gauss. The simulation results demonstrate that the improved algorithm can provide stable and reliable detection as well as accurate tracking, and balances the relationship between the precision of the filter and the algorithm running time.