**Jianjun Yin**

Department of Electronic Engineering, Fudan University, China

Jianqiu Zhang

Department of Electronic Engineering, Fudan University, China

Department of Electronic Engineering, Fudan University, China

Jianqiu Zhang

Department of Electronic Engineering, Fudan University, China

We present a new multi-target tracking algorithm for nonlinear models, termed as the Central Difference Multi-target Multi-Bernoulli (CD-MeMBer) filter. Sterling’s polynomial interpolation formula is used in deriving the filter under the assumption that state and measurement noises are Gaussian and each probability density during the predict and update recursion is approximated by a Gaussian sum. Furthermore, the proposed CD-MeMBer filter was generalized to nonlinear non-Gaussian models, called as the generalized CD-MeMBer (GCD-MeMBer) filter, where the state and measurement noises are approximated by Gaussian sums. The simulation results of the target tracking verify the effectiveness of the proposed algorithm.

PDF Abstract XML References Citation

Jianjun Yin and Jianqiu Zhang, 2011. The Central Difference Multi-target Multi-bernoulli Filtering Algorithms. *Information Technology Journal, 10: 2168-2174.*

**DOI:** 10.3923/itj.2011.2168.2174

**URL:** https://scialert.net/abstract/?doi=itj.2011.2168.2174

Multi target Tracking (MTT) involves joint estimation of unknown and time varying number of targets as well as their individual states from a sequence of sets of noisy and cluttered observations (Bar-Shalom and Fotman, 1988; Bar-Shalom and Li, 1995). The traditional approach to this problem is to assign a single target stochastic filter, such as a Kalman filter, to each target and use a data association technique to assign the correct measurement to each filter (Bar-Shalom and Fotman, 1988; Clark and Bell, 2007), this is a data association problem and requires various ad hoc methods in practice to stop the associated computation cost from growing exponentially over time (Panta *et al*., 2009). Recently the Probability Hypothesis Density (PHD) and Cardinalized PHD (CPHD) filters have attracted much international interest (Mahler, 2003, 2007; Vo* et al*., 2005; Vo and Ma, 2006). Unlike the PHD/CPHD recursions, which propagate moments and cardinality distributions, Mahler’s new filter the multi target multi Bernoulli (MeMBer) recursion propagates (approximately) the multi target posterior density (Mahler, 2007; Vo *et al*., 2009). Also, the Gaussian Mixture (GM) implementation of the new MeMBer recursion is proposed, which is called GM MeMBer filter. However, since the GM MeMBer filter is based on the linear Gaussian models, it may not be adequate to handle nonlinear non Gaussian models, which are more universal in practice.

In this study, we present a solution to the MeMBer recursion for nonlinear tracking models, called as the Central Difference MeMBer (CD-MeMBer) filter, which give further practical justification for the use of the MeMBer filter in multiple target tracking problems. Provided that the state and measurement noises are Gaussian, Sterling’s polynomial interpolation formula (Van der Merwe, 2004; Ito and Xiong, 2000) is used in deriving the filter under the assumption that the initial prior multi-Bernoulli multi-target density is given and each probability density is comprised of a Gaussian sum. Further more, by the Gaussian sum approximation of the state and measurement noise, we extend the CD-MeMBer recursion to nonlinear non-Gaussian models and propose the generalized CD-MeMBer (GCD-MeMBer) filter. The simulation results of the tracking verify the effectiveness of the proposed CD-MeMBer and GCD-MeMBer filters.

**BACKGROUND**

The MeMBer filter is a tractable approximation to the Bayes multi-target recursion under low clutter density scenarios using multi-Bernoulli RFSs. A multi-Bernoulli RFS X is a union of a fixed number of independent Bernoulli RFSs X^{(i)} with existence probability r^{(i)}∈(0,1) and probability density p^{(i)}, i=1,...,M, where M is the number of Bernoulli. Thus, a multi-Bernoulli RFS is completely described by the multi-Bernoulli parameter set.

The mean cardinality of a multi-Bernoulli RFS is and the probability density is as in Vo *et al*. (2009).

We recall the prediction and update step in Vo *et al*. (2009) which summarized the MeMBer recursion.

**Prediction: **Suppose that at time k-1, the Multi-Bernoulli posterior multi-target density:

is given, then the predicted multi-target density at time k is also a multi-Bernoulli.

**Update:** Suppose that at time k, the multi-Bernoulli predicted multi-target density:

is given, then the posterior multi-target density at time k can be approximated by a multi-Bernoulli.

**THE CD-MEMBER FILTER FOR NONLINEAR MODELS**

We adopt the same assumption on target birth, death and detection as in Vo *et al*. (2009):

• | The survival and detection probabilities are state independent, i.e., |

(1) |

(2) |

• | The birth model is a multi-Bernoulli with parameter set: |

where, are Gaussian mixtures of the form:

(3) |

where, denotes a Gaussian density with mean m and covariance P.

**Proposition 1 (CD-MeMBer Prediction): **Suppose that at time k-1, the (multi-Bernoulli) posterior multi-target density:

is given and each probability density , i = 1,..., M_{k-1} is a Gaussian sum of the form:

(4) |

Then, the predicted multi-target density at time k is also a multi-Bernoulli:

(5) |

(6) |

(7) |

Where:

are the parameters of the multi-Bernoulli RFS of births at time k and:

(8) |

where, [•]^{2} denotes [•]x[•]^{T}, L_{x} andL_{n} are the dimensions of the state and process noise, respectively and are the products of h and the l th column of the matrix square roots of and Q_{k}, respectively, i.e.,

(9) |

(10) |

**Proof:** From the prediction step of the MeMBer filter in Vo *et al*. (2009), we have:

(11) |

then:

(12) |

Where:

(13) |

Using the Sterling’s polynomial interpolation formula (Van der Merwe, 2004), we may obtain the results of proposition 1.

**Proposition 2 (CD-MeMBer Update): **Suppose that at time k, the predicted multi-Bernoulli multi-target density:

is given and each probability density , is a Gaussian sum of the form:

(14) |

Then, the multi-Bernoulli approximation of the posterior multi-target density at time k can be given by:

(15) |

Where:

(16) |

(17) |

(18) |

(19) |

(20) |

where, L_{v} is the dimension of the measurement noise, and are the products of h and the lth column of the matrix square roots of and R_{k}, respectively, i.e.,

(21) |

(22) |

**Proof: **By substituting (14) into prediction steps of the MeMBer filter in Vo *et al*. (2009), we have:

(23) |

(24) |

(25) |

Where:

(26) |

(27) |

where, by using the Sterling’s polynomial interpolation formula (Van der Merwe, 2004) we have:

(28) |

(29) |

(30) |

**EXTENSION TO NONLINEAR NON-GAUSSIAN MODELS**

We now considers extensions of the CD-MeMBer filter to non-Gaussian models, i.e., the process noise n_{k} and measurement noise v_{k} are not Gaussian any more. Due to the fact that any density can be approximated as close as required by a linear combination of Gaussian densities (Anderson and Moore, 1979; Alspach and Sorenson, 1972), the distribution of n_{k} and v_{k} can be expressed in terms of the following Gaussian sums:

(31) |

(32) |

where, denotes the weights of each Gaussian density and:

(33) |

Then:

(34) |

(35) |

The following two propositions present the generalized CD-MeMBer (GCD-MeMBer) recursion for the nonlinear non-Gaussian multi-target models. The proofs are the combination of those of proposition 1, 2 and the Gaussian sum property (Anderson and Moore, 1979; Alspach and Sorenson, 1972), thus omitted.

**Proposition 3 (GCD-MeMBer prediction): **Suppose that at time k-1, the posterior multi-target density is a multi-Bernoulli with the form:

and each probability density , i = 1,..,M_{k-1} is a Gaussian sum of the form:

(36) |

Then, the predicted multi-target density is still a multi-Bernoulli:

(37) |

(38) |

(39) |

Where:

(40) |

(41) |

(42) |

where, and are the products of h and the qth column of the matrix square roots of and , respectively i.e.,

(43) |

(44) |

**Proposition 4 (GCD-MeMBer update): **Suppose that at time k, the predicted multi-Bernoulli multi-target density:

is given and each probability density , is a Gaussian sum of the form:

(45) |

Then, the multi-Bernoulli approximation of the posterior multi-target density at time k can be given by:

(46) |

Where:

(47) |

(48) |

(49) |

(50) |

and

(51) |

and are the products of h and the qth column of the matrix square roots of and , respectively i.e.,

(52) |

(53) |

From the above propositions, it can be concluded that the CD-MeMBer filter is a special case of the GCD-MeMBer filter when N_{n,k}=N_{v,k}=1. Similar to the GM-MeMBer filter, the CD-MeMBer and GCD-MeMBer filters also suffer from computational troubles caused by the increasing number of Gaussian components. We apply the similar way as in Vo *et al*. (2009) to reduce the number of components, at each time step pruning of hypothesized tracks is performed by discarding those with existence probabilities below a threshold. For each of the remaining tracks, we eliminate components with weights below a threshold and merge components within a distance of each other.

**SIMULATION RESULTS**

**Nonlinear gaussian model:** Consider the following MTT model in a two dimensional situation (Vo *et al*., 2005):

where, x_{k} and y_{k} denote the state and measurement at time k respectively; Xk = [X_{k,1}, X_{k,2}, X_{k,3}, X_{k,4}]^{T}, where, X_{k,1} and X_{k,3} denote the x and y positions, respectively; X_{k,2} and X_{k,4} denote the x and y velocities, respectively; S=[S_{x} S_{y}]^{T} and ∇T are the sensor position and sampling interval, respectively; wk = [w_{1,k} w_{2,k}]^{T} and vk = [v_{1,k} v_{2,k}]^{T} are state and measurement noises, respectively. And , I_{2} denotes two by two identity matrix:

s = [0 -100]^{T} (Clark and Bell, 2007). The birth process is multi-Bernoulli with density:

where, r_{Γ}^{(i)} = 0.03, p_{Γ}^{(i)} = N (x; m_{Γ}^{(i)}, P_{Γ}^{(i)}), m_{Γ}^{(l)} = [0 0 0 0]^{T}, m_{Γ}^{(2)} = [400 0 -600 0]^{T}, m_{Γ}^{(3)} = [-800 0 -200 0]^{T}, m_{Γ}^{(4)} = [-200 0 -800 0]^{T}, P_{Γ}^{(i)} = diag ([10 10 10 10]^{T}). The probability of the survival and detection are p_{s,k }= 0.99 and p_{D,k }= 0.98, respectively. Clutter is modeled on a Poisson RFS over the surveillance region with an average of 10 clutter points per scan. At each time step, the number of Gaussian components is capped to a maximum of 100 components, the pruning is performed with a weight threshold of 10^{-5} and merging is performed with a threshold of 4.

Fig. 1(a-b): | Results of the CD-MeMBer filter |

Fig. 2(a-b): | Results of the GCD-MeMBer filter |

Additionally, pruning of the hypothesized tracks is performed with a weight threshold of 10^{-3} and a maximum of 100 tracks (Vo *et al*., 2009).

Figure 1 shows the results of the proposed CD-MeMBer filter, where the tracks in x and y coordinates are given separately with the solid line for the true and the dots for the estimated. It can be seen that the CD-MeMBer filter is capable of providing accurate tracking performances.

**Nonlinear non-gaussian model:** Consider the MTT model in (83), the same parameters are used except that the state and measurement noises and are both expressed by gaussian sums:

where,

Figure 2 shows the results of the proposed GCD-MeMBer filter, where the tracks in x and y coordinates are given separately. The solid line denote the true tracks and the add signs denote the estimated tracks. We can see that the GCD-MeMBer filter is capable of providing good tracking performances.

A couple of new MeMBer filters, namely, the Central Difference MeMBer (CD-MeMBer) filter and the Generalized Central Difference MeMBer (GCD-MeMBer) filter are presented. They can be applied to nonlinear or/and non-Gaussian tracking models. Using Sterling’s polynomial interpolation formula, we derive the recursions for the weights, means and covariances of the constituent Gaussian components of each probability density in the multi-Bernoulli posterior multi-target density. The tracking performances verify the effectiveness of the proposed CD-MeMBer and GCD-MeMBer filters.

The work reported in this study was funded under the National Natural Science Foundation of China under Grant No. 60872059 and the National Basic Research Program of China (2011CB302900).

- Clark, D.E. and J. Bell, 2007. Multi-target state estimation and track continuity for the particle PHD filter. IEEE Trans. Aerospace Elect. Syst., 43: 1441-1453.

CrossRef - Panta, K., D.E. Clark and B.N. Vo, 2009. Data association and track management for the Gaussian mixture probability hypothesis density filter. IEEE Trans. Aerospace Elect. Syst., 45: 1003-1016.

CrossRef - Mahler, R.P.S., 2003. Multitarget Bayes filtering via first-order multitarget moments. IEEE Trans. Aerospace Electron. Syst., 39: 1152-1178.

CrossRefDirect Link - Vo, B.N., S. Singh and A. Doucet, 2005. Sequential Monte Carlo methods for multi-target filtering with random finite sets. IEEE Trans. Aerospace Electronic Syst., 41: 1224-1245.

CrossRef - Vo, B.N. and W.K. Ma, 2006. The Gaussian mixture probability hypothesis density filter. IEEE Trans. Signal Process., 54: 4091-4094.

CrossRef - Vo, B.T., B.N. Vo and A. Cantoni, 2009. The cardinality balanced multi-target multi-Bernoulli filter and its implementations. IEEE Trans. Signal Processing, 57: 409-423.

CrossRef - Ito, K. and K.Q. Xiong, 2000. Gaussian filters for nonlinear filtering problems. IEEE Trans. Automatic Control, 45: 910-927.

CrossRef - Alspach, D.L. and H.W. Sorenson, 1972. Nonlinear bayesian estimation using gaussian sum approximations. IEEE Trans. Autouatic Control, 17: 439-448.

Direct Link