Next Article in Journal
Some Matrix Iterations for Computing Generalized Inverses and Balancing Chemical Equations
Previous Article in Journal
A New Swarm Intelligence Approach for Clustering Based on Krill Herd with Elitism Strategy
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

A Particle Filter Track-Before-Detect Algorithm Based on Hybrid Differential Evolution

Department of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China
*
Author to whom correspondence should be addressed.
Algorithms 2015, 8(4), 965-981; https://0-doi-org.brum.beds.ac.uk/10.3390/a8040965
Submission received: 19 August 2015 / Revised: 24 October 2015 / Accepted: 27 October 2015 / Published: 3 November 2015

Abstract

:
In this paper, we address the problem of detecting and tracking targets with a low signal-to-noise ratio (SNR) by exploiting hybrid differential evolution (HDE) in the particle filter track-before-detect (PF-TBD) context. Firstly, we introduce the Bayesian PF-TBD method and its weaknesses. Secondly, the HDE algorithm is regarded as a novel particle updating strategy, which is proposed to optimize the performance of the PF-TBD algorithm. Thirdly, we combine the systematic resampling approach to enhance the performance of the proposed algorithm. Then, an improved PF-TBD algorithm based on the HDE method is proposed. Experiment results indicate that the proposed method has better performance in detecting and tracking than previous algorithms when the targets have a low SNR.

1. Introduction

The traditional target detection approach is called track-after-detect (TAD); it involves the application of a detection threshold at every scan, which leads to a loss of information, as some sensor responses my fail to pass the detection threshold. Additionally, TAD methods cannot detect the targets with a low signal-to-noise (SNR) under 10 dB [1]. An alternative approach is called track-before-detect (TBD) [2], which jointly processes the raw sensor data (infrared sensor, radar, passive sonar, etc.) without a threshold and jointly declares the presence of a target and its track. This is acceptable if the SNR is low.
A large number of TBD algorithms have been developed in the past several decades including direct maximum likelihood [3], the Hough transform [4], dynamic programming [5,6], and so on. These methods generally require discretization of the state space and are very computationally intensive. Recently, the popularity of the particle filter (PF) method has increased due to its flexibility to handle cases where the dynamic and observation models are non-linear and/or non-Gaussian [7]. Particle filter track-before-detect (PF-TBD) was first proposed by Salmond [8], in parallel with the work by Boers [9]. These algorithms have since been extended in [10,11,12], which form a single target filter for two targets. The literature [10] presents a performance comparison of three particle filters using several different particle proposal densities designed for a single target. In [11], a new model for solving the problem of detecting a single target arrival and tracking its state in a TBD context is presented. The work in [12] shows a modeling setup and algorithm for a multiple target recursive Bayesian TBD application in a radar context. Phase information is used to improve the PF-TBD algorithm in the literature [13]. In [14], the PF is replaced by a cost-reference particle filter (CRPF). However, these proposals have some disadvantages in terms of computational complexity.
In this paper, an improved PF-TBD algorithm is proposed, which exploits a novel particle updating strategy that regards the particle updating process as an optimization problem using the hybrid differential evolution (HDE) algorithm [15,16] before the resampling process. It can be drawn from this strategy that we can reduce effectively the particle impoverishment and optimize the performance of weak target detection. Simulation results are presented to demonstrate the validity of the algorithm.
The remainder of this paper is organized as follows. The TBD system model is introduced in Section 2. In Section 3, first of all, we introduce the Bayesian PF-TBD approach and its weaknesses. Then, the HDE algorithm is given, and an improved PF-TBD algorithm is proposed. We evaluate the performance of the proposed algorithm in Section 4. At last, conclusions and pointers for future research are presented in Section 5.

2. TBD System Setup

In this section, we will describe the models that will be used in the TBD application, the target dynamics models and the measurement models.

2.1. Target Dynamic Model

The target state is represented by a five-dimensional state vector x k = [ x k     x ˙ k     y k     y ˙ k     I k ] T , where ( x k , y k ) , ( x ˙ k , y ˙ k ) and I k represent the position and velocity in the x and y dimensions and the intensity of the target at time k , respectively. k is the time index. A constant-velocity (CV) model is widely used as an example.
The discrete-time system dynamics of this model is of the form:
x k = F x k 1 + w k
where w k is the zero mean Gaussian noise process with covariance Q C V and F C V is the process transition matrix, which are defined by:
F C V = [ 1 T 0 0 0 0 1 0 0 0 0 0 1 T 0 0 0 0 1 0 0 0 0 0 1 ]
Q C V = [ q 1 T C V 3 / 3 q 1 T C V 2 / 2 0 0 0 q 1 T C V 2 / 2 q 1 T C V 0 0 0 0 0 q 1 T C V 3 / 3 q 1 T C V 2 / 2 0 0 0 q 1 T C V 2 / 2 q 1 T C V 0 0 0 0 0 q 2 T C V ]
where T C V is the sampling period, q 1 and q 2 are the power spectral density of the acceleration noise and the noise in the rate of change of target return intensity, respectively.
The presence of a target in the data is denoted by a target existence variable E k , a target existing in the data, E k =   1 , otherwise E k =   0 . The probability of target existence is modeled as a two-state Markov chain, the probability transition matrix of which is defined by:
Π = [ 1 P d P b P d 1 P b ]
where P b and P d denote the probability of target birth and death, respectively.

2.2. Measurement Model

Generally, we use the results of the sensor signal processing, which are a series of images, and the signal is assumed to be two-dimensional images [8,9,10], each frame consisting of n cells in the x dimension and m cells in the y dimension. The measurement at time k is the intensity of each cell in the image, which is given by z k = { z k ( i , j ) : i = 1 , , n ; j = 1 , , m } . As in Chapter 11 of [7], for each cell, the measurement model can be defined as follows:
z k ( i , j ) = { h k ( i , j ) ( x k ) + v k ( i , j ) E k = 1 v k ( i , j ) E k = 0
where h k ( i , j ) ( x k ) is a contribution from the intensity of the target in the cell ( i , j ) and v k ( i , j ) is the measurement noise in the cell, which is a known Gaussian distribution with zero mean, variance σ 2 . In this work, we adopt the sensor point spread function, a point target of intensity I k at position ( x k , y k ) ; the contribution to cell ( i , j ) can be written as:
h k ( i , j ) ( x k ) = Δ x Δ y I k 2 π Σ 2 exp ( ( x k i Δ x ) 2 + ( y k i Δ y ) 2 2 Σ 2 )
Here, the parameter Σ represents the extent of blurring and Δ x and Δ y denote the size of a cell in the x and y dimensions, respectively. Then, the set of complete measurements up to time k is denoted by Z = { z 1 , , z k } .
Under the assumptions of Gaussian measurement noise, which is independent of cell-to-cell, the likelihood function in the presence and absence of a target can be written as:
p ( z k ( i , j ) | x k , E k = 1 ) = 1 2 π σ 2 exp ( [ z k ( i , j ) h ( i , j ) ( x k ) ] 2 2 σ 2 )
p ( z k ( i , j ) | E k = 0 ) = 1 2 π σ 2 exp ( [ z k ( i , j ) ] 2 2 σ 2 )
Then:
p ( z k | x k , E k ) = i = 1 n j = 1 m p ( z k ( i , j ) | x k , E k )
The likelihood ratio for the cell is:
l ( z k | x k , E k ) = { p ( z k | x k , E k = 1 ) p ( z k | E k = 0 ) E k = 1 1 E k = 0
where:
l ( z k | x k , E k = 1 ) = i = 1 n j = 1 m exp ( h ( i , j ) ( x k ) [ h ( i , j ) ( x k ) 2 z k ( i , j ) ] 2 σ 2 )

3. Hybrid Differential Evolution Particle Filter Track-Before-Detect Algorithm

In this section, we give a derivation of the PF-based TBD algorithm and analyze the weaknesses of the PF-TBD, and then, an improved algorithm based on HDE is proposed.

3.1. Bayesian Particle Filter Track-Before-Detect

The main problem of TBD can be formulated in the framework of recursive Bayesian estimation in different expansion forms. The target state is not defined when the target does not exist in the data, where E k = 0 . Then, target detection and tracking can be implemented based on the posterior density p ( x k , E k | Z k ) when the target does exist, where E k = 1 .
p ( x k , E k = 1 | Z k ) = p ( z k | x k , E k = 1 ) p ( x k , E k = 1 | Z k 1 ) p ( z k | Z k 1 )                                                                                                    l ( z k | x k , E k = 1 ) p ( x k , E k = 1 | Z k 1 )
The predicted target state can be written in terms of the target and existence at the previous time, giving:
p ( x k , E k = 1 / Z k 1 ) = [ p ( x k , E k = 1 / x k - 1 , E k - 1 = 1 ) p ( x k 1 , E k 1 = 1 / Z k - 1 )                                                                                                             + p ( x k , E k = 1 , E k 1 = 0 / Z k - 1 ) ] d x k 1                                                                                            = p ( x k / x k - 1 , E k = 1 , E k - 1 = 1 ) p ( E k = 1 / E k 1 = 1 )                                                                                                             p ( x k 1 , E k 1 = 1 / Z k 1 ) d x k 1                                                                                                   +        p ( x k / x k - 1 , E k = 1 , E k - 1 = 1 , Z k 1 ) p ( E k = 1 / E k 1 = 0 )                                                                                            = p ( x k / x k - 1 , E k = 1 , E k - 1 = 1 ) ( 1 P d ) p ( x k 1 , E k 1 = 1 / Z k 1 ) d x k 1                                                                                                       + p b ( x k ) P b
where p b ( x k ) is the prior density of a target when it has appeared in the data between time k 1 and k . The algorithm proceeds by constructing two sets of particles. The first set, the birth particles, estimate p ( x k / E k = 1 , E k 1 = 0 , Z k ) , that is the case where the target did not exist in the data at time k 1 , but does at time k. The second set, the continuing particles, estimates p ( x k / E k = 1 , E k 1 = 1 ,   Z k ) , which is the case where the target has continued to exist in the data k−1 to k. Both sets of particles require a proposal distribution. For the continuing particles, the target dynamics are used in Equation (4). For the birth particles, a uniform distribution can be used. Then, the former is approximated using interacting sets of particles, and the calculation of the latter is based on the particle weights in these two sets.
Additionally, the estimate of the probability of existence can be calculated by particle weights in these two sets. State estimation can be obtained after resampling from these combined sets. There are three main resampling methods: multinomial resampling, residual resampling and systematic resampling [17].
To a certain extent, the resampling process is introduced to improve the degradation phenomenon of the particles. However, it also brought some problems. Particles that have higher weights will be reproduced many times. Additionally, those that have lower weights will fade away. Then, all particles will collapse to a small area, which will lead to the sample point sets not being sufficient after several iterations. The sample point sets are described the a posteriori probability density function. In the PF-TBD algorithm, if the particles collapse into a small area at time k , most of the particles, after the resampling process, are “the continuing particles”. This leads to these particles, which are produced by the state transition equation at time k + 1 , also collapsing into a small area. Moreover, if the area deviates from the true location, the target will be lost.

3.2. Improved PF-TBD-Based on the HDE Algorithm

In this paper, to improve the particle impoverishment problem, produced by the resampling process, a novel particle updating strategy is proposed before the resampling process to overcome the problem. We regard the particle updating process as an optimization problem using the HDE algorithm to increase the diversity of particles and to avoid the particles collapsing into a small area.
The HDE algorithm based on the simulated annealing (SA) method is utilized for the search capability of the SA to enhance the convergence capability of differential evolution (DE) in later periods and to improve the robustness of the DE algorithm [15,16]. It uses the Metropolis criterion of the SA algorithm to replace the section step of the DE algorithm. It seems that the computation of the HDE step is more complicated than DE. However, the HDE algorithm can achieve better results than DE with much lower iterations [15,16]. The HDE algorithm saves time to make up for its complexity. Therefore, we choose the better optimized performance of HDE to obtain sampling particles that conform more to the true state distribution.

3.2.1. Hybrid Differential Evolution Algorithm

The HDE algorithm relies on the initial population generation, mutation, recombination and the new selection to probe the search space through iterative progress until the termination criteria are met.
Detailed steps are presented accordingly in the sequel.
Step 1: Creating the initial population.
The first step of HDE is to create the initial population samples (the number of generations is g = 0 ) in n dimensional space as follows:
x i j ( 0 ) = x i j L + r a n d i j ( 0 , 1 ) ( x i j U x i j L )
where i = 1 , 2 , , N P ; j = 1 , 2 , , n , and N P is the population size. x i j U and x i j L denote the upper and lower limits of the j-th variable in the population respectively. r a n d i j ( 0 , 1 ) represents a uniformly-distributed random value within [0,1].
Step 2: Mutation operation.
The function of mutation in HDE is to maintain the diversity of a population. A typical HDE mutation sample formulation is:
h i j ( g ) = x i j ( g ) + F m ( x r 1 j ( g ) x r 2 j ( g ) )
where g represents the g-th generation, and h i j ( g ) are the mutated vector samples. r 1   r 2     i and r 1 , r 2 are randomly-selected integers within N P , r 1 , r 2 { 1 , 2 , , N P } . F m is the scaling factor.
Step 3: Crossover operation.
The basic crossover process is a discrete recombination, which employs a crossover constant C [ 0 ,   1 ] to determine if the newly-generated individual samples are to be recombined. The expression of the crossover process is given in Equation (16):
v i j ( g ) = { h i j ( g ) r a n d ( 0 , 1 ) C x i j ( g ) r a n d ( 0 , 1 ) > C
where v i j ( g ) are the trial vector samples.
Step 4: New selection operation.
The HDE algorithm adopts the Metropolis criterion of the SA algorithm to select whether to accept the trial vector samples. We construct the parameter about fitness function values Δ f = f ( v i j ( g ) ) f ( x i j ( g ) ) , and then, we decide the trial vector samples by the Metropolis criterion.
Metropolis criterion: if Δ f < 0 , the trial vector sample is accepted. If Δ f > 0 , we calculate an acceptance probability P ( Δ f ) = exp ( Δ f T S A ) and generate a pseudo-random number r . If P ( Δ f ) r , the trial vector sample is accepted; otherwise, the point is discarded.
Step 5: Cool down operation.
In this step, the cool down operation of the SA algorithm is executed. We defined T S A = T S A ρ ; here, T S A is an annealing temperature, and ρ ( 0 , 1 ) is an annealing control parameter.
When the new population is propagated, Step 2 to Step 5 is repeated until the pre-specified temperature T 0 is reached.

3.2.2. Proposed Method

Firstly, the particle updating process is optimized by the HDE algorithm. The importance-sampling particles are regarded as the initial population of the HDE algorithm, and the corresponding weights are treated as the fitness functions of the target vectors, respectively. The HDE resampling scheme recombines the particles by using an iterative process of mutation, crossover and the simulated annealing operator. Then, a new set of diverse particles is propagated. Secondly, the systematic resampling is chosen to be executed.
The proposed algorithm exploits a hybrid estimation technique, where the state is expanded to include the existence variable s k = [ x k T      E k ] T . Given a set of particles describing the joint posterior density at time k 1 , { s k 1 n , w k 1 n } n = 1 M with uniform weights, N is the particle number. Then, the proposed algorithm contains the following steps:
Step 1: 
Calculate the target existence variable: [ { E k n } n = 1 N ] = [ { E k-1 n } n = 1 N ] .
Step 2: 
Create a set of particles. These are two possible situations.
(i)
Set the ‘birth particle’ state as a sample from the proposal density x k n ~ q b ( x k / E k n = 1 , E k 1 n = 0 , z k ) . The target’s location ( x k n , x k n ) is uniform over the sensor field-of-view. Its velocity and intensity are assumed to be uniform as follows q b ( ( x ˙ k n , y ˙ k n ) / z k ) = U [ v min , v max ] , q b ( I k / z k ) = U [ I min , I max ] , where v min and v max are the minimum and the maximum of the target velocity, respectively. I min and I max are the minimum and the maximum of the target intensity, respectively.
(ii)
Set the “survival particle” state sampled from the proposal x k n ~ q b ( x k / E k n = 1 , E k 1 n = 1 , z k ) . That is, the “survival particle” x k is sampled according to the target state transition Equation (1).
(iii)
For each particle, compute the un-normalized weight w ˜ k n by using the likelihood ratio w ˜ k n = l ( z k / x k n , E k n = 1 ) .
Step 3: 
Optimize the sample particles by HDE. The sampling particles are regarded as the initial population of the HDE algorithm, and the corresponding weights are regarded as the fitness functions. According to the HDE algorithm, the process is iterated until the optimal population is found or a pre-specified condition is reached, then we can get the optimal set of particles { x k n , w ˜ k n } n = 1 N .
Step 4: 
Normalize the weights of each particle: w k n = w ˜ k n / n = 1 N w ˜ k n = l ( z k | x k n , E k n = 1 ) / n = 1 N ( l ( z k | x k n , E k n = 1 ) ) .
Step 5: 
Resample the particles: [ { x k n , 1 / N } n = 1 N ] = s y s t e m a t i c re s a m p l e [ { x k n , w k n } n = 1 N ] .
Step 6: 
Output the state estimation: an estimate of the target state can be made from the set of particles resulting from the time algorithm above.
The posterior density of target existence at time k is P k = Δ P { E k = 1 / Z k } , and then, the probability of existence is given by P ^ k = n = 1 N E k n / N ,          0 P ^ k 1 . Additionally, the target state can be estimated by X ^ k = n = 1 N ( x k n E k n ) / n = 1 N E k n .

4. Simulation Results

We use the following simulated measurement data to test the performance of the proposed algorithm, which is widely used in the current study and some representative PF-TBD algorithms [2,3,4,5,6]. Meanwhile, the CV (constant velocity) and CT (coordinate turn) motion models are used for testing.
The simulated measurement data consists of a total of 30 frames, with the target appearing in the data at Frame 7 and disappearing at Frame 22. Each frame consists of an array of 20 × 20 pixels, n = m = 20 ; each cell has unit dimensions Δ x = Δ y = 1 . The probabilities of birth and death are set as P b = P d = 0.05 . The standard deviation of the target spread function is = 0.7 . The target initial state was given by x 0 = [ 4.2       0.45      7.2       0.25        20 ] T . The birth particles proposal functions x k b ~ U ( 0 , n ) , y k b ~ U ( 0 , m ) , x ˙ k b ~ U ( 1 , 1 ) , y ˙ k b ~ U ( 1 , 1 ) and I k b ~ U ( 10 , 30 ) . Set the observation noise variance σ 2 to get a different SNR, which is defined by S N R = 10 log ( I 2 σ 2 ) . For example, if the SNR is 6 dB, the standard deviation of the background noise level in each pixel is σ = 10 units. The HDE parameters were set according to [16]. F m = 0.9 ; C = 0.6 ; the annealing initial temperature T S A = 100 ; the annealing parameter ρ = 0.9 ; and the pre-specified temperature T 0 = 5 .
For the CV model, the transition matrix F C V is given by Equation (2) and Q C V by Equation (3), with q 1 = 0.001 , q 2 = 0.01 , T C V = 1 and the target detection threshold thr = 0.6 .
For the CT model, the system dynamics model function is given by Equation (1), and the covariances of noise process Q C T and the process transition matrix F C T are defined by:
F C T = [ 1 sin ( w ( k ) T C T ) w ( k ) 0 1 cos ( w ( k ) T C T ) w ( k ) 0 0 cos ( w ( k ) T C T ) 0 sin ( w ( k ) T C T ) 0 0 1 cos ( w ( k ) T C T ) w ( k ) 1 sin ( w ( k ) T C T ) w ( k ) 0 0 sin ( w ( k ) T C T ) 0 cos ( w ( k ) T C T ) 0 0 0 0 0 1 ]
Q C T = [ 2 ( w ( k ) T C T sin ( w ( k ) T C T ) ) · q 1 w ( k ) 3 ( 1 cos ( w ( k ) T C T ) ) · q 1 w ( k ) 2 0 ( w ( k ) T C T sin ( w ( k ) T C T ) ) · q 1 w ( k ) 2 0 ( 1 cos ( w ( k ) T C T ) ) · q 1 w ( k ) 2 q 1 T C T ( w ( k ) T C T sin ( w ( k ) T C T ) ) · q 1 w ( k ) 2 0 0 0 ( w ( k ) T C T sin ( w ( k ) T C T ) ) · q 1 w ( k ) 2 2 ( w ( k ) T C T sin ( w ( k ) T C T ) ) · q 1 w ( k ) 3 ( 1 cos ( w ( k ) T C T ) ) · q 1 w ( k ) 2 0 ( w ( k ) T C T sin ( w ( k ) T C T ) ) · q 1 w ( k ) 2 0 ( 1 cos ( w ( k ) T C T ) ) · q 1 w ( k ) 2 q 1 T C T 0 0 0 0 0 q 2 T C T ]
where w ( k ) is the turn rate, T C T is the sampling period and q 1 and q 2 are the power spectral density of the acceleration noise and the noise in the rate of change of target return intensity, respectively. Here, their values are set the same as in CV model. The turn angle is 4°, T C T = 1 ; and the target detection threshold thr = 0.7 .
For convenience, in the experimental results, the proposed algorithm is marked as HDE PF-TBD; PF-TBD with the systematic resampling method is marked as SystematicR PF-TBD; and that using the multinomial resampling method is marked MultinomialR PF-TBD. We use exactly the same set of data and the same filter parameters. The number of particles used by each algorithm was set to 6000. The algorithm performance is gauged on an average over 100 Monte Carlo simulations.

4.1. Scenario-CV

Two sampled measurement images with SNR 6 dB are shown in Figure 1 in different frames: Frames 15 and 18. This shows that the target exists at Frames 15 and 18, but it is indistinguishable from the background noise. If using the TAD algorithm, this will inevitably lead to a loss of information at low SNR.
Figure 1. (a) Sampled image at Frame 15; (b) sampled image at Frame 18.
Figure 1. (a) Sampled image at Frame 15; (b) sampled image at Frame 18.
Algorithms 08 00965 g001

4.1.1. Detection Performance Analysis

The detection performance of the proposed algorithm (HDE PF-TBD) is evaluated in simulations with the probability of existence. The average of the probability of detection with different SNRs of the three algorithms is compared in Table 1. Figure 2 shows the results in terms of the probability of existence at different frame times.
Table 1. The average of the probability of detection for the constant velocity (CV) model. R, resampling; PF, particle filter; TBD, track-before-detect; HDE, hybrid differential evolution.
Table 1. The average of the probability of detection for the constant velocity (CV) model. R, resampling; PF, particle filter; TBD, track-before-detect; HDE, hybrid differential evolution.
Algorithm9 dB6 dB3 dB1 dB
MultinomialR PF-TBD0.770 0.657 0.423 0.217
SystematicR PF-TBD0.7740.682 0.498 0.300
HDE PF-TBD0.875 0.765 0.628 0.395
Figure 2. (a) Probability of the existence at SNR = 9 dB for the CV model; (b) probability of existence at SNR= 6 dB for the CV model; (c) probability of existence at SNR = 3 dB for the CV model; (d) probability of existence at SNR = 1 dB for the CV model.
Figure 2. (a) Probability of the existence at SNR = 9 dB for the CV model; (b) probability of existence at SNR= 6 dB for the CV model; (c) probability of existence at SNR = 3 dB for the CV model; (d) probability of existence at SNR = 1 dB for the CV model.
Algorithms 08 00965 g002
The target exists if the probability of existence is higher than 0.6, which a tested and sensible value and is plotted as a horizontal line in Figure 2. Moreover, the asterisk signs at the bottom of the figures indicate the time of the presence of the target. It can be seen from Figure 2 that for SNR = 1, 3, 6, 9 dB, three algorithms have target presence and absence declaration delays, and each algorithm follows the true existence of the target much more closely for the higher SNR cases, with performance degrading as SNR reduces. The HDE PF-TBD algorithm provides higher target detection confidence than the other two algorithms. Furthermore, the HDE PF-TBD algorithm performs very well among the four SNR values, in other words with less target presence and absence declaration delays than others. From Figure 2, we also can see that the probability of the existence of the proposed algorithm has a large increase when the SNR is 3 dB and 1 dB. For clarity, the data statistics of Table 1 have proven that the HDE PF-TBD has better detection sensitivity when the SNR is lower.
Figure 3. (a) Probability of existence at SNR = 0 dB for the CV model; (b) probability of existence at SNR = −1 dB for the CV model.
Figure 3. (a) Probability of existence at SNR = 0 dB for the CV model; (b) probability of existence at SNR = −1 dB for the CV model.
Algorithms 08 00965 g003
Moreover, it can be seen from Figure 3 that for SNR = 0, −1 dB, all three algorithms suffer a poor detection performance. However, compared to SystematicR PF-TBD and the MultinomialR PF-TBD, the HDE PF-TBD algorithm can detect the target at the end of the frames where the target exists. It is demonstrated that the proposed approach has a larger detectable and traceable SNR range and is capable of resolving large noise in the target. Meanwhile, it also proves that the improvements in the proposed algorithm can effectively enhance the detection sensitivity and that the proposed algorithm is more suitable for detecting weak targets with low SNR.

4.1.2. Tracking Performance Analysis

To measure the estimation accuracy of the proposed algorithm, we introduce the root mean squared error ( R M S E ) in the position and its mean R M S E for different SNRs. Additionally, the R M S E for M simulations with different frames at time k is defined as:
R M S E = [ 1 M m = 1 M ( ( x ^ k , m x k , m ) 2 + ( y ^ k , m y k , m ) 2 ) ] 1 / 2
where x k , m and y k , m are the true values of the target state and x ^ k , m and y ^ k , m are defined as the estimation of the target state. We only consider the frames in which the target exists, and the period length is L. The R M S E can be shown as:
R M S E = 1 L i = 1 L R M S E i
The results in terms of mean RMSE for the different SNR values of the three algorithms are compared in Table 2. Figure 4 shows the results in terms of RMSE in position with corresponding frames for different SNR values.
Table 2. The average of the RMSE for different SNRs for the CV model.
Table 2. The average of the RMSE for different SNRs for the CV model.
Algorithm9 dB6 dB3 dB1 dB
MultinomialR PF-TBD2.17572.47152.75283.0814
SystematicR PF-TBD1.97712.34272.62223.0622
HDE PF-TBD1.38101.59711.82212.3595
Figure 4. (a) RMSE in position at SNR = 9 dB for the CV model; (b) RMSE in position at SNR = 6 dB for the CV model; (c) RMSE in position at SNR = 3 dB for the CV model; (d) RMSE in the position of existence at SNR = 1 dB for the CV model.
Figure 4. (a) RMSE in position at SNR = 9 dB for the CV model; (b) RMSE in position at SNR = 6 dB for the CV model; (c) RMSE in position at SNR = 3 dB for the CV model; (d) RMSE in the position of existence at SNR = 1 dB for the CV model.
Algorithms 08 00965 g004
As expected, the tracking accuracy of each algorithm degrades as the SNR reduces. Meanwhile, the proposed algorithm shows a better performance on the low SNR target than the other two algorithms in Figure 4. It is can be seen that the proposed algorithm has much lower RMSE when the target began to appear. It is demonstrated that the HDE PF-TBD algorithm can more accurately estimate the initial location of the target appearance. Moreover, from Table 2, it can be clearly seen that the estimation accuracy of the proposed algorithm is always superior to that of the other two algorithms. Although the RMSE of the proposed method approximates the other two algorithms at Frames 16 and 17 when the SNR is 1 dB, the tracking accuracy of the HDE PF-TBD algorithm is still higher than the other two algorithms in the whole frame range where the target exists. Therefore, the proposed algorithm is capable of tracking the target with low SNR, and it outperforms the SystematicR PF-TBD and the MultinomialR PF-TBD.

4.2. Scenario-CT

Similarly, we also analyze detection and tracking performance under the CT model. The average of the detection probability of detection with different SNRs of the three algorithms for 100 Monte Carlo simulations (MC) is compared in Table 3. Figure 5 shows the results in terms of the probability of existence in different frame times for 100 MC.
Table 3. The average detection probability for the CT model.
Table 3. The average detection probability for the CT model.
Algorithm9 dB6 dB3 dB1 dB
MultinomialR PF-TBD0.7470.621 0.378 0.275
SystematicR PF-TBD0.7680.6480.3990.284
HDE PF-TBD0.8270.7430.501 0.367
The target exists if the probability of existence is higher than 0.7, which is plotted as a horizontal line in Figure 5. It can be seen from Figure 5 that, for SNR =1, 3, 6, 9 dB, the three algorithms also have target presence and absence declaration delays, and each algorithm follows the true existence of the target much more closely for the higher SNR cases, with performance degrading as SNR reduces under the CT model. For the CT model, the HDE PF-TBD algorithm provides higher target detection confidence than the other two algorithms. Moreover, the HDE PFTBD algorithm has less target presence delays than the others. Meanwhile, we also can see that the probability of existence of the proposed algorithm has a large increase when the SNR is 3 dB and 1 dB. For clarity, the data statistics of Table 3 have proven that the HDE PF-TBD has better detection sensitivity when the SNR is lower.
Figure 5. (a) Probability of existence at SNR = 9 dB for the coordinate turn (CT) model; (b) probability of existence at SNR = 6 dB for the CT model; (c) probability of existence at SNR = 3 dB for the CT model; (d) probability of existence at SNR = 1 dB for the CT model.
Figure 5. (a) Probability of existence at SNR = 9 dB for the coordinate turn (CT) model; (b) probability of existence at SNR = 6 dB for the CT model; (c) probability of existence at SNR = 3 dB for the CT model; (d) probability of existence at SNR = 1 dB for the CT model.
Algorithms 08 00965 g005aAlgorithms 08 00965 g005b
Table 4. The average RMSE at different SNRs for the CT model.
Table 4. The average RMSE at different SNRs for the CT model.
Algorithm9 dB6 dB3 dB1 dB
MultinomialR PF-TBD1.9102.15562.70442.909
SystematicR PF-TBD1.7451.87392.62582.81
HDE PF-TBD1.4331.44772.38362.3541
The results in terms of mean RMSE for the different SNR values of the three algorithms for the CT model are compared in Table 4. Figure 6 shows the results in terms of RMSE in position with corresponding frames for different SNR values for the CT model.
Figure 6. (a) RMSE in position at SNR = 9 dB for the CT model; (b) RMSE in position at SNR = 6 dB for the CT model; (c) RMSE in position at SNR = 3 dB for the CT model; (d) RMSE in the position of existence at SNR = 1 dB for the CT model.
Figure 6. (a) RMSE in position at SNR = 9 dB for the CT model; (b) RMSE in position at SNR = 6 dB for the CT model; (c) RMSE in position at SNR = 3 dB for the CT model; (d) RMSE in the position of existence at SNR = 1 dB for the CT model.
Algorithms 08 00965 g006aAlgorithms 08 00965 g006b
For the CT model, it can be clearly seen from Table 4 and Figure 6 that the proposed algorithm also shows a better performance on the low SNR target than the other two algorithms. Although the RMSE of the proposed method is a little higher than the other two algorithms at Frame 10 when SNR is 9 dB, the tracking accuracy of the HDE PF-TBD algorithm is still higher than other two algorithms in the whole frame range that the target exists. Therefore, as can be seen from the two aspects of detection and tracking, the proposed algorithm is also capable of tracking the target with the CT motion model and low SNR, and it outperforms SystematicR PF-TBD and MultinomialR PF-TBD.

5. Conclusions

In this paper, a novel particle filter track-before-detect algorithm based on hybrid differential evolution was developed. Firstly, we exploit a hybrid differential evolution as a novel particle updating strategy for overcoming the shortcoming of the particle impoverishment. Secondly, in order to reduce the influence of the particle degeneracy, the systematic resampling method is chosen for the proposed method. Finally, the proposed algorithm combines a more effective particle initiation method, which only places the particles in the highest intensity bins of the data. The proposed algorithm not only can make full use of the data information, but also decreases the particle degeneracy and enhances the diversity of particles. The detection and tracking of the performance advantage of the proposed algorithm have been demonstrated by two cases of a low signal-to-noise point target against a background of Gaussian noise with the CV and CT motion models, respectively. What is more, the proposed method is much more efficient than previous methods. Future work will continue to enhance the detection accuracy of the proposed algorithm and to explore the implementation of multiple targets within this framework.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Grant No. 61172159) and the Fundamental Research Funds for the Central Universities (HEUCFT1101).

Author Contributions

The work presented here was carried out in collaboration between both authors. Chaozhu Zhang and Lin Li defined the research theme. Lin Li designed the methods and experiments, carried out the laboratory experiments, analyzed the data, interpreted the results and wrote the paper. Both authors have contributed to, seen and approved the manuscript.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Hadzagic, M.; Michalska, H.; Lefebvre, E. Track-before-detect methods in tracking low-observable targets: A survey. Sens. Trans. Mag. 2005, 54, 374–380. [Google Scholar]
  2. Rutten, M.; Gordon, N.; Maskell, S. Recursive track-before-detect with target amplitude fluctuations. IEE Proc. Radar Sonar Navig. 2005, 152, 345–352. [Google Scholar] [CrossRef]
  3. Pohlig, S.C. An algorithm for detection of moving optical targets. IEEE Trans. Aerosp. Electron. Syst. 1989, 25, 56–63. [Google Scholar] [CrossRef]
  4. Carlson, B.D.; Evans, E.D.; Wilson, S.L. Search radar detection and track with the hough transform. IEEE Trans. Aerosp. Electron. Syst. 1994, 30, 102–108. [Google Scholar] [CrossRef]
  5. Huang, D.; Xue, A.; Guo, Y. Penalty dynamic programming algorithm for dim targets detection in sensor systems. Sensors 2012, 12, 5028–5046. [Google Scholar] [CrossRef] [PubMed]
  6. Grossi, E.; Lops, M.; Venturino, L. A Novel dynamic programming algorithm for track-before-detect in radar systems. IEEE Trans. Signal. Process. 2013, 61, 2608–2619. [Google Scholar] [CrossRef]
  7. Ristic, B.; Arulampalam, S.; Gordon, N. Beyond the Kalman. Filter-Particle Filters for Tracking Applications; Artech House: London, UK, 2004. [Google Scholar]
  8. Salmond, D.J.; Birch, H. A Particle Filter for Track-Before-Detect. In Proceedings of the American Control Conference, Arlington, VA, USA, 25–27 June 2001; pp. 3755–3760.
  9. Boers, Y.; Driessen, H. Particle Filter Based Detection for Tracking. In Proceedings of the American Control Conference, Arlington, VA, USA, 25–27 June 2001; pp. 4393–4397.
  10. Davey, S.J.; Rutten, M.G. A Comparison of Three Algorithms for Tracking Dim Targets. In Proceedings of the Information, Decision and Control (IDC’07), Queensland, Australia, 12–14 February 2007; pp. 342–347.
  11. Davey, S.; Rutten, M.; Cheung, B. Using phase to improve track before detect. IEEE Trans. Aerosp. Electron. Syst. 2012, 48, 832–849. [Google Scholar] [CrossRef]
  12. Boers, Y.; Driessen, J. Multitarget particle filter track before detect application. IEE Proc. Radar Sonar Navig. 2004, 151, 351–357. [Google Scholar] [CrossRef]
  13. Lepouter, A.; Rabaste, O. A Particle Filter for Target Arrival Detection and Tracking in Track-Before-Detect. In Proceedings of the Workshop on Sensor Data Fusion: Trends, Solutions, Applications (SDF’12), Bonn, Germany, 4–6 September 2012; pp. 13–18.
  14. Lu, J.; Shui, P.-L. Track-before-detect method based on cost-reference particle filter in non-linear dynamic systems with unknown statistics. IET Signal. Process. 2014, 8, 85–94. [Google Scholar] [CrossRef]
  15. Hu, Z.B.; Xiong, S.W. Study of hybrid differential evolution based on simulated annealing. Comput. Eng. Des. 2007, 28, 1989–1992. [Google Scholar]
  16. Zhang, C.; Li, L. Hybrid differential evolution particle filter for nonlinear filtering. Appl. Comput. Electromagn. Soc. 2014, 12, 1133–1139. [Google Scholar]
  17. Douc, R.; Cappe, O. Comparison of Resampling Schemes for Particle Filtering. In Proceedings of the Image and Signal Processing and Analysis, Zagreb, Croatia, 15–17 September 2005; pp. 64–69.

Share and Cite

MDPI and ACS Style

Zhang, C.; Li, L.; Wang, Y. A Particle Filter Track-Before-Detect Algorithm Based on Hybrid Differential Evolution. Algorithms 2015, 8, 965-981. https://0-doi-org.brum.beds.ac.uk/10.3390/a8040965

AMA Style

Zhang C, Li L, Wang Y. A Particle Filter Track-Before-Detect Algorithm Based on Hybrid Differential Evolution. Algorithms. 2015; 8(4):965-981. https://0-doi-org.brum.beds.ac.uk/10.3390/a8040965

Chicago/Turabian Style

Zhang, Chaozhu, Lin Li, and Yu Wang. 2015. "A Particle Filter Track-Before-Detect Algorithm Based on Hybrid Differential Evolution" Algorithms 8, no. 4: 965-981. https://0-doi-org.brum.beds.ac.uk/10.3390/a8040965

Article Metrics

Back to TopTop