Information Technology Journal

Year: 2011 | Volume: 10 | Issue: 11 | Page No.: 2168-2174
DOI: 10.3923/itj.2011.2168.2174

The Central Difference Multi-target Multi-bernoulli Filtering Algorithms

Jianjun Yin and Jianqiu Zhang

Abstract: 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.

Keywords: central difference multi-target multi-Bernoulli (CD-MeMBer), gaussian-sum, simulation, random finite sets (RFSs) and Multi-target tracking

INTRODUCTION

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⁽ⁱ⁾ with existence probability r⁽ⁱ⁾∈(0,1) and probability density p⁽ⁱ⁾, 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):

where, are Gaussian mixtures of the form:

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:

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

Where:

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

where, [•]² 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.,

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

then:

Where:

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:

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

Where:

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.,

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

Where:

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

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:

where, denotes the weights of each Gaussian density and:

Then:

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:

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

Where:

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

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:

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

Where:

and

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

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₂ denotes two by two identity matrix:

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

where, r_Γ⁽ⁱ⁾ = 0.03, p_Γ⁽ⁱ⁾ = N (x; m_Γ⁽ⁱ⁾, P_Γ⁽ⁱ⁾), m_Γ^(l) = [0 0 0 0]^T, m_Γ⁽²⁾ = [400 0 -600 0]^T, m_Γ⁽³⁾ = [-800 0 -200 0]^T, m_Γ⁽⁴⁾ = [-200 0 -800 0]^T, P_Γ⁽ⁱ⁾ = 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.

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.

CONCLUSIONS

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.

ACKNOWLEDGMENTS

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).

REFERENCES