# Gating Techniques for Rao-Blackwellized Monte Carlo Data Association Filter

Authors: Yazhao Wang; Peini Zhang
Journal: The Scientific World Journal
 (2014)

---

## Abstract

This paper studies the Rao-Blackwellized Monte Carlo data association (RBMCDA) filter for multiple target tracking. The elliptical gating strategies are redesigned and incorporated into the framework of the RBMCDA filter. The obvious benefit is the reduction of the time cost because the data association procedure can be carried out with less validated measurements. In addition, the overlapped parts of the neighboring validation regions are divided into several separated subregions according to the possible origins of the validated measurements. In these subregions, the measurement uncertainties can be taken into account more reasonably than those of the simple elliptical gate. This would help to achieve higher tracking ability of the RBMCDA algorithm by a better association prior approximation. Simulation results are provided to show the effectiveness of the proposed gating techniques.


---

## Body

## 1. Introduction

Data association plays an important role in filtering methods for multitarget tracking in cluttered (or false alarm) environment. Many approaches have been developed to solve this problem [2–7]. One solution is the Rao-Blackwellized Monte Carlo data association (RBMCDA) [1, 8]. In this approach, particle filter (PF) is only used to evaluate the data association indicators instead of computing everything by pure Monte Carlo sampling. Therefore, the required number of particles can be significantly reduced. This can be a method with good performance for tracking a single target or multiple separated targets in sparsely cluttered environment. Unfortunately, we found in experiments that the time cost of this algorithm is too large even in modest clutter environment. Besides, it will lead to significantly low tracking performance of the algorithm when several targets as well as clutter are present in the same neighborhood. To address these problems, this paper employs gating technique for improvement.In traditional tracking algorithms, a gate (validation region) can be used to guarantee that the target originated measurement falls into it with high (gate) probability [2–4]. The probabilistic data association (PDA) [4] has been thought to be a very good elliptical gate based method for tracking a single target or several isolated targets even in dense cluttered environment. On this basis, many types of gating techniques have been studied [9–12]. Specially, the Voronoi measure is used to select validated measurements for single target tracking in [13]. When several targets are present in the same neighborhood in addition to the random interference from clutter, a more complicated situation should be considered. The joint probabilistic data association (JPDA) can give a joint probability by first enumerating the joint events [3, 14]. In JPDA, not only the number of the validated measurements can be reduced to a low level, but also the problem of measurement uncertainty can be addressed very well. Because enumerating the joint association events is often computationally intensive [15], many time saving suboptimal JPDA filtering methods are available, such as Fitzgerald’s and other ad hoc implementations [2, 16, 17]. Recently, the elliptical gating technique has also been studied and redesigned for reducing the computational cost of the popular Gaussian mixture- cardinalized probability hypothesis density (GM-CPHD) filter [18, 19].The remainder of this paper is organized as follows. Section2 gives a brief introduction on the RBMCDA filter and the validation region. Section 3 presents three different gating strategies according to the framework of the RBMCDA filter. Numerical examples and simulation results are presented in Section 4, followed by conclusions in Section 5.


## 2. Preliminaries

### 2.1. Rao-Blackwellized Monte Carlo Data Association Filter

Consider the following time-varying system:(1)
x
k
1
=
F
k
-
1
x
k
-
1
1
+
w
k
-
1
,
z
k
=
H
k
x
k
1
+
v
k
,
where x
k
1 and z
k are the state and measurement variables in time step k, respectively. w
k
-
1
~
𝒩
(
0
,
Q
k
-
1
) and v
k
~
𝒩
(
0
,
R
k
) are zero mean mutually independent Gaussian noise and F
k
-
1 and H
k are with compatible dimensions and represent the state and measurement transition matrices, respectively. Suppose that we are able to form another variable x
k
2 to describe these matrices, the so-called Rao-Blackwellized particle filter (RBPF) algorithm can be applied to estimate the whole state x
k
=
{
x
k
1
;
x
k
2
} [20]. For space consideration, we omit the details of the RBPF algorithm which can be found in [21–24]. For this conditionally linear-Gaussian system, the Kalman series filter prediction and update steps can be performed for each target in each of the particles separately.In [1], it has been shown that the RBMCDA algorithm can be obtained directly from the above RBPF framework when the latent value x
k
2 is defined to be the data association event indicators c
k,
(2)
x
k
2
=
c
k
,
where the value c
k
=
0 when the measurement is from clutter and c
k
=
j when the measurement is from target j. The predictive probability p
(
c
k
∣
c
1
:
k
-
1
) gives the priors of data association given the data association results {
c
1
:
k
-
1
} in the k
-
1 previous time steps. The calculation of the p
(
c
k
∣
c
1
:
k
-
1
,
z
1
:
k
) (posterior distribution of c
k) is given by
(3)
p
(
c
k
∣
c
1
:
k
-
1
,
z
1
:
k
)
∝
p
(
z
k
∣
c
k
,
c
1
:
k
-
1
,
z
1
:
k
-
1
)
p
(
c
k
∣
c
1
:
k
-
1
)
.
The main difficulty encountered in RBMCDA is the computation of the association prior probabilities p
(
c
k
∣
c
1
:
k
-
1
). In [1], the data association priors are modeled as a recursive Markov chain to make sure of one target per measurement in the same time steps. Accordingly, the p
(
c
k
∣
c
1
:
k
-
1
) in (3) has been replaced by the p
(
c
k
∣
c
k
-
M
:
k
-
1
) and
(4)
p
(
c
k
∣
c
1
:
k
-
1
,
z
1
:
k
)
∝
p
(
z
k
∣
c
k
,
c
1
:
k
-
1
,
z
1
:
k
-
1
)
p
(
c
k
∣
c
k
-
M
:
k
-
1
)
.
The general form of the joint prior model is given by [1]
(5)
p
(
c
k
+
M
-
1
,
…
,
c
k
)
=
∏
m
=
1
M
‍
p
(
c
k
+
m
∣
c
k
,
…
,
c
k
+
m
-
1
)
.
That means if we obtain M measurements in time step k, the calculation of the mth (m
=
2
,
…
,
M) measurement’s association prior p
(
c
k
+
m
-
1
∣
c
k
+
m
-
2
,
…
,
c
k
) only depends on the m
-
1 previous associations {
c
k
+
m
-
2
,
…
,
c
k
} in the kth time step (note that, if m
=
1, c
k has the prior p
(
c
k
)). Assume we track T targets; the detection indicator for the jth (j
=
1
,
…
,
T) target can be given by δ
j
(
m
-
1
). It is a binary indicator to indicate that if the jth target has been assigned a measurement in {
c
k
+
m
-
2
,
…
,
c
k
}, the detection indicator combinations δ
1
:
T
(
m
-
1
) decide the data association priors as
(6)
p
(
c
k
+
m
-
1
∣
δ
1
:
T
(
m
-
1
)
)
=
f
c
(
P
d
(
j
)
)
,
where f
c is a function with definite forms corresponding to the results of δ
1
:
T
(
m
-
1
) [1]. We can see that only the target detection probability P
d
(
j
) (in (6)) needs to be given at the beginning of the Markov recursive calculation procedures. Since P
d
(
j
) is assumed to be a known value [1], data association (the posterior distribution p
(
c
k
∣
c
1
:
k
-
1
,
z
1
:
k
)) is in fact totally determined by the measurement likelihood p
(
z
k
∣
c
k
,
c
1
:
k
-
1
,
z
1
:
k
-
1
) according to (4), (5), and (6).


### 2.2.  Validation Region

A gate is set up for selecting the measurement originated from the target in high probability, and gate can also be called gating region or validation region. In practical tracking algorithms, validation region is often used to reduce the cardinality of measurement set. Measurements outside the validation region can be ignored reasonably because the probabilities of them being from the corresponding targets are quite low according to the statistical characterization. Data association method often incorporates an elliptical validation region [3] as
(7)
Γ
k
(
γ
)
=
{
z
k
:
[
z
k
-
z
^
k
∣
k
-
1
]
′
S
(
k
)
-
1
[
z
k
-
z
^
k
|
k
-
1
]
≤
γ
}
,
where γ is the gate threshold corresponding to the gate probability P
g which is the probability that the gate contains the true measurement and S
(
k
) is the covariance of the innovation corresponding to the true measurement z
k. In this paper, we just consider the elliptical gating technique. For each target (
j
=
1,2
,
…
,
T
), the gate probability P
g
(
j
)
=
0.9997 with γ
=
16 [3].Figure1(a) gives an example of a single target’s measurement validation region. N
=
5 represents the number of validated measurements in this elliptical region. For this 2
D example, a measurement is considered to be validated for target j if it falls inside the elliptical region centered at the predicted measurement Z
^ (“■” represents the location of Z
^). The target originated measurement Z (“∘”) and clutter originated measurement (“×”) are represented by the different symbols, but they actually show no difference from a tracker’s perspective in applications. Thus, each one of the five measurements in the validation region can be originated from the target or clutter.Examples of measurement validation region: (a) for a single target, (b) for two targets.
(a)
(b)Figure1(b) illustrates a case of two targets as well as clutter being present in the same neighborhood. The predicted measurements for target 1 and target 2 are denoted by Z
^
1 and Z
^
2, respectively. There are three measurements in the intersection of their validation regions (n
12
=
3); n
1
=
4 and n
2
=
3 are the number of the validated measurements in the isolated parts of the two elliptical validation regions. N
1
=
7 and N
2
=
6 represent the numbers of validated measurements in their elliptical regions, respectively. This example shows the interdependence of measurement origins. The RBMCDA, like all other data association methods, has also to deal with these uncertainties.


### 2.3.  Problem Statement

In the original RBMCDA approaches [1, 8], all received measurements in the entire measurement space are considered as the validated measurements. From the tracker’s point of view, the target detection probability P
d
(
j
) mentioned in Section 2.1 represents the probability that the target-originated measurement falls into the whole measurement space. When a gating technique is considered, the data association is restricted into the validation regions so that the P
d
(
j
) used in (6) should be replaced by P
e
(
j
) accordingly. That is
(8)
p
(
c
k
+
m
-
1
∣
δ
1
:
T
(
m
-
1
)
)
=
f
c
(
P
e
(
j
)
)
,
where P
e
(
j
) defines the probability that the target-originated measurement falls into a concerned (validation) region. There is no doubt that the number of the validated measurements will be reduced to a low level followed by the possible reduction of the running time [19]. Consequently, the key problem becomes the calculation of P
e
(
j
).


## 2.1. Rao-Blackwellized Monte Carlo Data Association Filter

Consider the following time-varying system:(1)
x
k
1
=
F
k
-
1
x
k
-
1
1
+
w
k
-
1
,
z
k
=
H
k
x
k
1
+
v
k
,
where x
k
1 and z
k are the state and measurement variables in time step k, respectively. w
k
-
1
~
𝒩
(
0
,
Q
k
-
1
) and v
k
~
𝒩
(
0
,
R
k
) are zero mean mutually independent Gaussian noise and F
k
-
1 and H
k are with compatible dimensions and represent the state and measurement transition matrices, respectively. Suppose that we are able to form another variable x
k
2 to describe these matrices, the so-called Rao-Blackwellized particle filter (RBPF) algorithm can be applied to estimate the whole state x
k
=
{
x
k
1
;
x
k
2
} [20]. For space consideration, we omit the details of the RBPF algorithm which can be found in [21–24]. For this conditionally linear-Gaussian system, the Kalman series filter prediction and update steps can be performed for each target in each of the particles separately.In [1], it has been shown that the RBMCDA algorithm can be obtained directly from the above RBPF framework when the latent value x
k
2 is defined to be the data association event indicators c
k,
(2)
x
k
2
=
c
k
,
where the value c
k
=
0 when the measurement is from clutter and c
k
=
j when the measurement is from target j. The predictive probability p
(
c
k
∣
c
1
:
k
-
1
) gives the priors of data association given the data association results {
c
1
:
k
-
1
} in the k
-
1 previous time steps. The calculation of the p
(
c
k
∣
c
1
:
k
-
1
,
z
1
:
k
) (posterior distribution of c
k) is given by
(3)
p
(
c
k
∣
c
1
:
k
-
1
,
z
1
:
k
)
∝
p
(
z
k
∣
c
k
,
c
1
:
k
-
1
,
z
1
:
k
-
1
)
p
(
c
k
∣
c
1
:
k
-
1
)
.
The main difficulty encountered in RBMCDA is the computation of the association prior probabilities p
(
c
k
∣
c
1
:
k
-
1
). In [1], the data association priors are modeled as a recursive Markov chain to make sure of one target per measurement in the same time steps. Accordingly, the p
(
c
k
∣
c
1
:
k
-
1
) in (3) has been replaced by the p
(
c
k
∣
c
k
-
M
:
k
-
1
) and
(4)
p
(
c
k
∣
c
1
:
k
-
1
,
z
1
:
k
)
∝
p
(
z
k
∣
c
k
,
c
1
:
k
-
1
,
z
1
:
k
-
1
)
p
(
c
k
∣
c
k
-
M
:
k
-
1
)
.
The general form of the joint prior model is given by [1]
(5)
p
(
c
k
+
M
-
1
,
…
,
c
k
)
=
∏
m
=
1
M
‍
p
(
c
k
+
m
∣
c
k
,
…
,
c
k
+
m
-
1
)
.
That means if we obtain M measurements in time step k, the calculation of the mth (m
=
2
,
…
,
M) measurement’s association prior p
(
c
k
+
m
-
1
∣
c
k
+
m
-
2
,
…
,
c
k
) only depends on the m
-
1 previous associations {
c
k
+
m
-
2
,
…
,
c
k
} in the kth time step (note that, if m
=
1, c
k has the prior p
(
c
k
)). Assume we track T targets; the detection indicator for the jth (j
=
1
,
…
,
T) target can be given by δ
j
(
m
-
1
). It is a binary indicator to indicate that if the jth target has been assigned a measurement in {
c
k
+
m
-
2
,
…
,
c
k
}, the detection indicator combinations δ
1
:
T
(
m
-
1
) decide the data association priors as
(6)
p
(
c
k
+
m
-
1
∣
δ
1
:
T
(
m
-
1
)
)
=
f
c
(
P
d
(
j
)
)
,
where f
c is a function with definite forms corresponding to the results of δ
1
:
T
(
m
-
1
) [1]. We can see that only the target detection probability P
d
(
j
) (in (6)) needs to be given at the beginning of the Markov recursive calculation procedures. Since P
d
(
j
) is assumed to be a known value [1], data association (the posterior distribution p
(
c
k
∣
c
1
:
k
-
1
,
z
1
:
k
)) is in fact totally determined by the measurement likelihood p
(
z
k
∣
c
k
,
c
1
:
k
-
1
,
z
1
:
k
-
1
) according to (4), (5), and (6).


## 2.2.  Validation Region

A gate is set up for selecting the measurement originated from the target in high probability, and gate can also be called gating region or validation region. In practical tracking algorithms, validation region is often used to reduce the cardinality of measurement set. Measurements outside the validation region can be ignored reasonably because the probabilities of them being from the corresponding targets are quite low according to the statistical characterization. Data association method often incorporates an elliptical validation region [3] as
(7)
Γ
k
(
γ
)
=
{
z
k
:
[
z
k
-
z
^
k
∣
k
-
1
]
′
S
(
k
)
-
1
[
z
k
-
z
^
k
|
k
-
1
]
≤
γ
}
,
where γ is the gate threshold corresponding to the gate probability P
g which is the probability that the gate contains the true measurement and S
(
k
) is the covariance of the innovation corresponding to the true measurement z
k. In this paper, we just consider the elliptical gating technique. For each target (
j
=
1,2
,
…
,
T
), the gate probability P
g
(
j
)
=
0.9997 with γ
=
16 [3].Figure1(a) gives an example of a single target’s measurement validation region. N
=
5 represents the number of validated measurements in this elliptical region. For this 2
D example, a measurement is considered to be validated for target j if it falls inside the elliptical region centered at the predicted measurement Z
^ (“■” represents the location of Z
^). The target originated measurement Z (“∘”) and clutter originated measurement (“×”) are represented by the different symbols, but they actually show no difference from a tracker’s perspective in applications. Thus, each one of the five measurements in the validation region can be originated from the target or clutter.Examples of measurement validation region: (a) for a single target, (b) for two targets.
(a)
(b)Figure1(b) illustrates a case of two targets as well as clutter being present in the same neighborhood. The predicted measurements for target 1 and target 2 are denoted by Z
^
1 and Z
^
2, respectively. There are three measurements in the intersection of their validation regions (n
12
=
3); n
1
=
4 and n
2
=
3 are the number of the validated measurements in the isolated parts of the two elliptical validation regions. N
1
=
7 and N
2
=
6 represent the numbers of validated measurements in their elliptical regions, respectively. This example shows the interdependence of measurement origins. The RBMCDA, like all other data association methods, has also to deal with these uncertainties.


## 2.3.  Problem Statement

In the original RBMCDA approaches [1, 8], all received measurements in the entire measurement space are considered as the validated measurements. From the tracker’s point of view, the target detection probability P
d
(
j
) mentioned in Section 2.1 represents the probability that the target-originated measurement falls into the whole measurement space. When a gating technique is considered, the data association is restricted into the validation regions so that the P
d
(
j
) used in (6) should be replaced by P
e
(
j
) accordingly. That is
(8)
p
(
c
k
+
m
-
1
∣
δ
1
:
T
(
m
-
1
)
)
=
f
c
(
P
e
(
j
)
)
,
where P
e
(
j
) defines the probability that the target-originated measurement falls into a concerned (validation) region. There is no doubt that the number of the validated measurements will be reduced to a low level followed by the possible reduction of the running time [19]. Consequently, the key problem becomes the calculation of P
e
(
j
).


## 3. Gating Techniques for RBMCDA Filter

In this section, three different gating techniques are presented applicable to the framework of the RBMCDA filter, and the requiredP
e
(
j
) is discussed in detail. A simple gating method is first discussed. We then present the joint events (J-) based gating method which takes into account the interference from the neighboring targets. To get a practical solution with low time cost, then a simplified version of the “J-” method (SJ-) is proposed. At last, the main procedure of the gating technique based RBMCDA algorithm is given for clarity.


### 3.1. The Union Based Method

To reduce the cardinality of the validated measurement set, we can define a union which consists of all the elliptical validation regions (see Figure2(a)). In this example, only the validated measurements in the defined union are depicted. The dotted lines represent the boundaries of the common region of the two elliptical validation regions. This union based RBMCDA algorithm is termed U-RBMCDA for short. In this method, the boundaries of the common region can be omitted and each measurement falling inside the union is assumed to be the validated measurement of both the two targets. Hence, the required P
e
(
j
) can be obtained directly by
(9)
P
e
(
j
)
=
P
d
(
j
)
P
g
(
j
)
.
We can see that, in this union, the P
e
(
j
) will be a fixed value if P
d
(
j
) and P
g
(
j
) are known. The difference between U-RBMCDA and the O-RBMCDA (the original RBMCDA [8]) algorithm is that the former just reserves the measurements within the union as the validated measurements for all targets. However, it is not difficult to find that the validated measurements outside the common region could be possibly originated from only one target according to their locations. For example, as shown in Figure 1(b), the four measurements (n
1
=
4) in the left part of the 1
st target’s region could only be possibly from target 1. That is to say, the union is too big to differentiate the measurements with different possible origins. To address this, the detailed measurement location information is needed to consider, and it will go more reasonable if we get the estimates of the target existent probabilities in the smaller regions.Regulations of measurement validation regions, (a) as a union, (b) in separated forms.
(a)
(b)In fact, the joint validation region can be seen as consisting of several sub-validation-regions (SVRs) according to the possible origins of the validated measurements, and theP
e
(
j
) for a target j could have different values in different subregions. Therefore, we should divide the joint validation region into several SVRs to make sure the validated measurements within a SVR are with the same possible origins. To emphasize this point, Figure 2(b) gives a separated but equivalent form of illustration as that of Figure 1(b). In this example, the numbers of validated measurements in three SVRs are n
1
=
4, n
2
=
3, and n
12
=
3, respectively.


### 3.2.  Joint Events Based Gating Method

In a SVR with identifierr, we need to calculate the probability P
e
r
(
j
) for the jth (j
=
1,2
,
…
,
T) target. If we still want to calculate P
e
r
(
j
) by the way of P
e
r
(
j
)
=
P
g
r
(
j
)
P
d
(
j
) (P
d
r
(
j
)
=
P
d
(
j
)), the target gate probability P
g
r
(
j
) should be known. Although the P
g
(
j
) can be directly obtained according to (7), it is hardly possible to obtain the analytical solutions of the gate probability P
g
r
(
j
) in an arbitrary SVR with identifier r. That is because a SVR is usually one part of the ellipse or the other irregular shape (see Figure 2(b)). In this case, the required measurements statistical information which determines the P
g
r
(
j
) will be extremely difficult to obtain. To solve this problem, we present the joint events based method and use the weights of the probabilities of the feasible events instead.In this process, the possible events can be constructed in a similar way as JPDA does [3, 17]. To build the joint events and derive the joint probabilities, the key information required is the numbers of the measurements in these SVRs. In fact, the validated measurements in different SVRs can be differentiated by using the distance measure from the center points of the corresponding validation regions (see (7)), so that the required measurements numbers are not difficult to obtain. The probability of an event θ
k for all M validated measurements in the joint validation region is given by
(10)
P
{
θ
k
}
=
P
{
θ
k
,
δ
,
n
c
}
=
P
{
θ
k
∣
δ
,
n
c
}
P
{
δ
,
n
c
}
=
n
c
!
M
!
∏
m
=
1
M
‍
(
P
d
(
j
)
)
δ
j
(
1
-
P
d
(
j
)
)
1
-
δ
j
f
p
(
n
c
)
,
where δ indicates from which target the present measurement is originated, while δ
j (δ
j
=
1 or 0) indicates that whether the mth measurement has been considered to be originated from the jth target. Both {
θ
k
} and δ
j are determined by the numbers of the validated measurements in the SVRs. P
d
(
j
) is the detection probability for the jth target, n
c is the number of the measurements considered to be form clutter, and f
p
(
n
c
) represents the nonparametric prior probability of the number of clutter originated measurements in the joint validation region. Note that the f
p
(
n
c
) and M
! can be canceled in a normalizing factor α [3] as
(11)
P
{
θ
k
}
=
n
c
!
α
∏
m
=
1
M
‍
(
P
d
(
j
)
)
δ
j
(
1
-
P
d
(
j
)
)
1
-
δ
j
.
The weighting factor P
k
(
m
j
) represents the probability of the mth measurement being originated from target j and it is given by
(12)
P
k
(
m
j
)
=
∑
θ
k
‍
p
(
θ
k
)
β
(
θ
k
)
,
where β
(
θ
k
) is a binary variable which indicates whether the mth measurement is possibly originated from the jth target. In following discussions, the identifier and k can be omitted without misunderstanding and P
k
(
m
j
) can be rewritten as P
(
m
j
). In a SVR with identifier r, P
e
r
(
j
) is the sum of the weighting factor P
(
m
j
)
(13)
P
e
r
(
j
)
=
∑
m
=
m
1
m
r
‍
P
(
m
j
)
,
where {
m
1
,
…
,
m
r
} is set of the measurements in the rth SVR. If P
e
r
(
j
)
=
1, the jth target originated (true) measurement is certainly in the rth SVR.


### 3.3.  Simplified Joint Events Based Gating Method

To develop a practical suboptimal J-RBMCDA method with less time cost, we present a simplified joint events (SJ-) based gating technique. In J-RBMCDA, the numbers of validated measurements in the SVRs play the key roles to calculate the target existent probability or even determine the results. In fact, they represent the relative importance of these subregions, or the gate weights of the SVRs. So we can use the normalized weights and the target detection probabilityP
d
(
j
) to estimate P
e
(
j
). In each time step k, the computational formulas are as follows:
(14)
N
j
=
n
j
+
∑
C
1
‍
n
j
k
1
+
⋯
+
∑
C
T
-
1
‍
n
j
k
1
k
2
⋯
k
T
-
1
,
P
j
(
j
)
=
n
j
N
j
;
P
j
k
1
(
j
)
=
n
j
k
1
N
j
,
k
1
∈
C
1
;
…
;
P
j
k
1
k
2
⋯
k
T
-
1
(
j
)
=
n
j
k
1
k
2
⋯
k
T
-
1
N
j
,
{
k
1
k
2
⋯
k
T
-
1
}
∈
C
T
-
1
.
In (14), N
j is the number of validated measurements in the elliptical validation region of the jth (j
=
1,2
,
…
,
T) target and n
j
k
1
k
2
⋯
k
t (t
=
1,2
,
…
,
T
-
1) is the number of validated measurements in the SVR with identifier j
k
1
k
2
⋯
k
t. Moreover, C
t defines a SVR set in which each element is related to the jth target itself and other t targets:
(15)
C
1
=
{
k
1
:
1
≤
k
1
≤
T
,
k
1
≠
j
}
;
…
;
C
T
-
1
=
{
(
k
1
k
2
⋯
k
T
-
1
)
:
k
1
,
k
2
,
…
,
k
T
-
1
are
(
T
-
1
)
different
numbers
in
{
1,2
,
…
,
T
}
∖
{
j
}
}
.
As a result, P
j
k
1
k
2
⋯
k
t
(
j
) is the estimated gate weight of the jth target in the j
k
1
k
2
⋯
k
tth SVR. Since the target gate probability P
g
(
j
) in the jth elliptical region and the target detection probability P
d
(
j
) have been assumed to be known, in a SVR with identifier j
k
1
k
2
⋯
k
t, the P
e
j
k
1
k
2
⋯
k
t
(
j
) can be given by
(16)
P
e
j
k
1
k
2
⋯
k
t
(
j
)
=
P
j
k
1
k
2
⋯
k
t
(
j
)
P
g
(
j
)
P
d
(
j
)
.
Note that the SVR identifier (j
k
1
k
2
⋯
k
t) is independent of the order of j
,
k
1
,
k
2
,
…
,
k
t. For example, when j
=
1 and k
1
=
2, there are n
12
=
n
21 and P
e
12
(
1
)
=
P
e
21
(
1
). However, in the SVR with the identifier 12 (or 21), P
e
12
(
1
)
=
(
n
12
/
N
1
)
P
d
(
1
) and P
e
12
(
2
)
=
(
n
12
/
N
2
)
P
d
(
2
) are different values for target 1 and target 2, respectively. Hence, even in the same SVR, P
e
r
(
1
) and P
e
r
(
2
) have different values.This simplified joint events based RBMCDA (SJ-RBMCDA) can be seen as a very simple form of the J-RBMCDA with the joint events being broken up into several isolated events. The significant difference is that, in SJ-RBMCDA, the procedure of enumerating the possible association events is replaced by a simple nonparametric method. Therefore, the requiredP
e
r
(
j
) can be computed by directly using the numbers of the validated measurements in the corresponding SVRs. Logically, less computational time is needed.It should be pointed out that the J-RBMCDA and SJ-RBMCDA algorithms may provide more weights to the right SVRs if the tracker can get the correct target estimates. Like all other gating based algorithms, however, the performance of the proposed gating based RBMCDA algorithms will also be degraded in the cases that the tracker provides incorrect target estimates. Another problem is that, for both J-RBMCDA and SJ-RBMCDA, the number of SVRs seems to increase dramatically with the number of targets to be tracked. Figure3 gives an example of tracking 11 targets, and each of the arrows points to a SVR. We can see that the total number of the SVRs is 20 including the empty SVRs (pointed by dotted arrows), so that the number of the SVRs needed to be computed is 18 (pointed by solid arrows). In fact, the dimension curse occurs only in the extreme case when all tracks are in the same neighborhood and with incomplete coverage. In this cases, when tracking T targets the number of SVRs would be 2
T
-
1. For example, in the up left of Figure 3 the joint validation consists of three elliptical validation regions (centered at z
^
1, z
^
2, and z
^
3, resp.). The total number of the SVRs is 2
3
-
1
=
7 including one empty SVR (n
13
=
0), so that the number of the SVRs needed to be computed is 6 (n
1, n
2, n
3, n
12, n
23, and n
123).Figure 3
An example of measurement validation regions for a large number of targets.


### 3.4.  RBMCDA Algorithm with Gating Technique

The gating technique based RBMCDA algorithm is presented in Algorithm1. This algorithm includes four major parts: prediction, finding validation regions and calculating P
e
r
(
j
), calculating data association probabilities and updating the state of particles, and finally a particle weights calculation step. It should be pointed out that only the second part is fundamentally different from the original RBMCDA algorithm. In this algorithm, the target state priors can be represented as a weighted importance samples set
(17)
p
(
x
0
(
j
)
)
=
∑
i
=
1
N
p
‍
w
i
,
0
𝒩
(
x
0
(
j
)
∣
x
i
,
0
(
j
)
,
P
i
,
0
(
j
)
)
,
where i is the identifier of particle with N
p being the number of particles employed. The dynamics and measurements for target j (j
=
1
,
…
,
T) are assumed to be linear Gaussian
(18)
p
(
x
k
(
j
)
∣
x
k
-
1
(
j
)
)
=
𝒩
(
x
k
(
j
)
∣
F
k
-
1
(
j
)
x
k
-
1
(
j
)
,
Q
k
-
1
(
j
)
)
,
p
(
z
k
∣
x
k
(
j
)
,
c
k
=
j
)
=
𝒩
(
z
k
∣
H
k
(
j
)
x
k
(
j
)
,
R
k
(
j
)
)
.Algorithm 1:RBMCDA using gating techniques.
For  k
=
1  to
n  do
For
i
=
1
to
N
p
do
For
j
=
1
to
T
do
x
^
i
,
k
∣
k
-
1
(
j
)
=
F
k
-
1
(
j
)
x
^
i
,
k
-
1
∣
k
-
1
(
j
),                                (i)
P
i
,
k
∣
k
-
1
(
j
)
=
F
k
-
1
(
j
)
P
i
,
k
-
1
∣
k
-
1
(
j
)
[
F
k
-
1
j
]
′
+
Q
k
-
1
(
j
).                            (ii)
End for
j
End for
i
For
j
=
1
to
T
do
z
^
k
∣
k
-
1
(
j
)
=
H
k
(
j
)
[
∑
i
=
1
N
p
‍
w
i
,
k
-
1
x
^
i
,
k
∣
k
-
1
(
j
)
],                                  (iii)
S
k
(
j
)
=
H
k
(
j
)
[
∑
i
=
1
N
p
‍
w
i
,
k
-
1
P
i
,
k
∣
k
-
1
(
j
)
]
[
H
k
(
j
)
]
′
+
R
k
(
j
),                            (iv)
where z
^
k
∣
k
-
1
(
j
) and S
k
(
j
) are the predicted measurement and innovation, respectively.
For
m
=
1
to
N
m
e
a
s
u
r
e
m
e
n
t
s
(number of the measurements) do
Choose z
k
(
m
) that satisfies the following condition as the validated measurement of the jth target:
[
z
k
(
m
)
-
z
^
k
∣
k
-
1
(
j
)
]
′
[
S
k
(
j
)
]
-
1
[
z
k
(
m
)
-
z
^
k
∣
k
-
1
(
j
)
]
≤
γ.                          (v)
End for
m
End for
j
For  r
=
1
to
N
S
V
R
s
(number of the SVRs) do
For
j
=
1
to
T
Calculate P
e
r
(
j
) using gating techniques.
End for
j
For
m
=
1
to
N
r
For
i
=
1
to
N
p
Calculate data association priors p
(
c
i
,
k
∣
c
i
,
k
-
m
:
k
-
1
) by (8) based on the Markov chain
model described in [1].
For
j
=
1
to
T do
z
^
i
,
k
(
j
)
=
H
k
(
j
)
x
^
i
,
k
∣
k
-
1
(
j
),                              (vi)
S
i
,
k
(
j
)
=
H
k
(
j
)
P
i
,
k
∣
k
-
1
(
j
)
[
H
k
(
j
)
]
′
+
R
k
(
j
).                            (vii)
Calculate the marginal measurement likelihood
p
(
z
k
∣
c
i
,
k
=
j
,
c
i
,
1
:
k
-
1
,
z
1
:
k
-
1
)
=
𝒩
(
z
k
(
m
)
∣
z
^
i
,
k
(
j
)
,
S
i
,
k
(
j
)
).                   (viii)
End for
j
Calculate the clutter likelihood
p
(
z
k
∣
c
i
,
k
=
0
,
c
i
,
1
:
k
-
1
,
z
1
:
k
-
1
)
=
V
-
1.                             (ix)
Calculate the posterior distribution of c
i
,
k
p
(
c
i
,
k
∣
c
i
,
1
:
k
-
1
,
z
1
:
k
)
=
p
(
z
k
∣
c
i
,
k
,
c
i
,
1
:
k
-
1
,
z
1
:
k
-
1
)
p
(
c
i
,
k
∣
c
i
,
k
-
m
:
k
-
1
).                (x)
Sample an association indicator c
i
,
k
=
j with probability ρ
i
(
j
)
ρ
i
(
j
)
=
ρ
^
i
(
j
)
∑
j
′
=
0
T
ρ
^
i
(
j
′
), j
=
0
,
…
,
T,                           (xi)
where
ρ
^
i
(
0
)
=
p
(
c
i
,
k
=
0
∣
c
i
,
1
:
k
-
1
,
z
1
:
k
),                            (xii)
ρ
^
i
(
j
)
=
p
(
c
i
,
k
=
j
∣
c
i
,
1
:
k
-
1
,
z
1
:
k
).                             (xiii)
If
j
≠
0
, update the
j
th target using the measurement
z
k
(
m
)
K
i
,
k
=
P
i
,
k
∣
k
-
1
(
j
)
[
H
k
(
j
)
]
′
S
i
,
k
(
j
),                             (xiv)
x
^
i
,
k
∣
k
(
j
)
=
x
^
i
,
k
∣
k
-
1
(
j
)
+
K
i
,
k
[
z
k
(
m
)
-
z
^
i
,
k
(
j
)
],                        (xv)
P
i
,
k
∣
k
(
j
)
=
P
i
,
k
∣
k
-
1
(
j
)
-
K
i
,
k
S
i
,
k
(
j
)
(
K
i
,
k
)
′.                           (xvi)
End if
Calculate the new weight
w
i
,
k
∝
w
i
,
k
-
1
p
(
z
k
∣
c
i
,
k
,
c
i
,
1
:
k
-
1
,
z
1
:
k
-
1
)
p
(
c
i
,
k
∣
c
i
,
k
-
m
:
k
-
1
)
p
(
c
i
,
k
∣
c
i
,
1
:
k
-
1
,
z
1
:
k
).                   (xvii)
End for
i
Resample the particles if needed.
End for
m
Calculate the target state vectors
For
j
=
1
to
x
^
k
∣
k
(
j
)
=
∑
i
=
1
N
p
‍
w
i
,
k
x
^
i
,
k
∣
k
(
j
).                               (xviii)
End for
j
End for
r
End for
k


## 3.1. The Union Based Method

To reduce the cardinality of the validated measurement set, we can define a union which consists of all the elliptical validation regions (see Figure2(a)). In this example, only the validated measurements in the defined union are depicted. The dotted lines represent the boundaries of the common region of the two elliptical validation regions. This union based RBMCDA algorithm is termed U-RBMCDA for short. In this method, the boundaries of the common region can be omitted and each measurement falling inside the union is assumed to be the validated measurement of both the two targets. Hence, the required P
e
(
j
) can be obtained directly by
(9)
P
e
(
j
)
=
P
d
(
j
)
P
g
(
j
)
.
We can see that, in this union, the P
e
(
j
) will be a fixed value if P
d
(
j
) and P
g
(
j
) are known. The difference between U-RBMCDA and the O-RBMCDA (the original RBMCDA [8]) algorithm is that the former just reserves the measurements within the union as the validated measurements for all targets. However, it is not difficult to find that the validated measurements outside the common region could be possibly originated from only one target according to their locations. For example, as shown in Figure 1(b), the four measurements (n
1
=
4) in the left part of the 1
st target’s region could only be possibly from target 1. That is to say, the union is too big to differentiate the measurements with different possible origins. To address this, the detailed measurement location information is needed to consider, and it will go more reasonable if we get the estimates of the target existent probabilities in the smaller regions.Regulations of measurement validation regions, (a) as a union, (b) in separated forms.
(a)
(b)In fact, the joint validation region can be seen as consisting of several sub-validation-regions (SVRs) according to the possible origins of the validated measurements, and theP
e
(
j
) for a target j could have different values in different subregions. Therefore, we should divide the joint validation region into several SVRs to make sure the validated measurements within a SVR are with the same possible origins. To emphasize this point, Figure 2(b) gives a separated but equivalent form of illustration as that of Figure 1(b). In this example, the numbers of validated measurements in three SVRs are n
1
=
4, n
2
=
3, and n
12
=
3, respectively.


## 3.2.  Joint Events Based Gating Method

In a SVR with identifierr, we need to calculate the probability P
e
r
(
j
) for the jth (j
=
1,2
,
…
,
T) target. If we still want to calculate P
e
r
(
j
) by the way of P
e
r
(
j
)
=
P
g
r
(
j
)
P
d
(
j
) (P
d
r
(
j
)
=
P
d
(
j
)), the target gate probability P
g
r
(
j
) should be known. Although the P
g
(
j
) can be directly obtained according to (7), it is hardly possible to obtain the analytical solutions of the gate probability P
g
r
(
j
) in an arbitrary SVR with identifier r. That is because a SVR is usually one part of the ellipse or the other irregular shape (see Figure 2(b)). In this case, the required measurements statistical information which determines the P
g
r
(
j
) will be extremely difficult to obtain. To solve this problem, we present the joint events based method and use the weights of the probabilities of the feasible events instead.In this process, the possible events can be constructed in a similar way as JPDA does [3, 17]. To build the joint events and derive the joint probabilities, the key information required is the numbers of the measurements in these SVRs. In fact, the validated measurements in different SVRs can be differentiated by using the distance measure from the center points of the corresponding validation regions (see (7)), so that the required measurements numbers are not difficult to obtain. The probability of an event θ
k for all M validated measurements in the joint validation region is given by
(10)
P
{
θ
k
}
=
P
{
θ
k
,
δ
,
n
c
}
=
P
{
θ
k
∣
δ
,
n
c
}
P
{
δ
,
n
c
}
=
n
c
!
M
!
∏
m
=
1
M
‍
(
P
d
(
j
)
)
δ
j
(
1
-
P
d
(
j
)
)
1
-
δ
j
f
p
(
n
c
)
,
where δ indicates from which target the present measurement is originated, while δ
j (δ
j
=
1 or 0) indicates that whether the mth measurement has been considered to be originated from the jth target. Both {
θ
k
} and δ
j are determined by the numbers of the validated measurements in the SVRs. P
d
(
j
) is the detection probability for the jth target, n
c is the number of the measurements considered to be form clutter, and f
p
(
n
c
) represents the nonparametric prior probability of the number of clutter originated measurements in the joint validation region. Note that the f
p
(
n
c
) and M
! can be canceled in a normalizing factor α [3] as
(11)
P
{
θ
k
}
=
n
c
!
α
∏
m
=
1
M
‍
(
P
d
(
j
)
)
δ
j
(
1
-
P
d
(
j
)
)
1
-
δ
j
.
The weighting factor P
k
(
m
j
) represents the probability of the mth measurement being originated from target j and it is given by
(12)
P
k
(
m
j
)
=
∑
θ
k
‍
p
(
θ
k
)
β
(
θ
k
)
,
where β
(
θ
k
) is a binary variable which indicates whether the mth measurement is possibly originated from the jth target. In following discussions, the identifier and k can be omitted without misunderstanding and P
k
(
m
j
) can be rewritten as P
(
m
j
). In a SVR with identifier r, P
e
r
(
j
) is the sum of the weighting factor P
(
m
j
)
(13)
P
e
r
(
j
)
=
∑
m
=
m
1
m
r
‍
P
(
m
j
)
,
where {
m
1
,
…
,
m
r
} is set of the measurements in the rth SVR. If P
e
r
(
j
)
=
1, the jth target originated (true) measurement is certainly in the rth SVR.


## 3.3.  Simplified Joint Events Based Gating Method

To develop a practical suboptimal J-RBMCDA method with less time cost, we present a simplified joint events (SJ-) based gating technique. In J-RBMCDA, the numbers of validated measurements in the SVRs play the key roles to calculate the target existent probability or even determine the results. In fact, they represent the relative importance of these subregions, or the gate weights of the SVRs. So we can use the normalized weights and the target detection probabilityP
d
(
j
) to estimate P
e
(
j
). In each time step k, the computational formulas are as follows:
(14)
N
j
=
n
j
+
∑
C
1
‍
n
j
k
1
+
⋯
+
∑
C
T
-
1
‍
n
j
k
1
k
2
⋯
k
T
-
1
,
P
j
(
j
)
=
n
j
N
j
;
P
j
k
1
(
j
)
=
n
j
k
1
N
j
,
k
1
∈
C
1
;
…
;
P
j
k
1
k
2
⋯
k
T
-
1
(
j
)
=
n
j
k
1
k
2
⋯
k
T
-
1
N
j
,
{
k
1
k
2
⋯
k
T
-
1
}
∈
C
T
-
1
.
In (14), N
j is the number of validated measurements in the elliptical validation region of the jth (j
=
1,2
,
…
,
T) target and n
j
k
1
k
2
⋯
k
t (t
=
1,2
,
…
,
T
-
1) is the number of validated measurements in the SVR with identifier j
k
1
k
2
⋯
k
t. Moreover, C
t defines a SVR set in which each element is related to the jth target itself and other t targets:
(15)
C
1
=
{
k
1
:
1
≤
k
1
≤
T
,
k
1
≠
j
}
;
…
;
C
T
-
1
=
{
(
k
1
k
2
⋯
k
T
-
1
)
:
k
1
,
k
2
,
…
,
k
T
-
1
are
(
T
-
1
)
different
numbers
in
{
1,2
,
…
,
T
}
∖
{
j
}
}
.
As a result, P
j
k
1
k
2
⋯
k
t
(
j
) is the estimated gate weight of the jth target in the j
k
1
k
2
⋯
k
tth SVR. Since the target gate probability P
g
(
j
) in the jth elliptical region and the target detection probability P
d
(
j
) have been assumed to be known, in a SVR with identifier j
k
1
k
2
⋯
k
t, the P
e
j
k
1
k
2
⋯
k
t
(
j
) can be given by
(16)
P
e
j
k
1
k
2
⋯
k
t
(
j
)
=
P
j
k
1
k
2
⋯
k
t
(
j
)
P
g
(
j
)
P
d
(
j
)
.
Note that the SVR identifier (j
k
1
k
2
⋯
k
t) is independent of the order of j
,
k
1
,
k
2
,
…
,
k
t. For example, when j
=
1 and k
1
=
2, there are n
12
=
n
21 and P
e
12
(
1
)
=
P
e
21
(
1
). However, in the SVR with the identifier 12 (or 21), P
e
12
(
1
)
=
(
n
12
/
N
1
)
P
d
(
1
) and P
e
12
(
2
)
=
(
n
12
/
N
2
)
P
d
(
2
) are different values for target 1 and target 2, respectively. Hence, even in the same SVR, P
e
r
(
1
) and P
e
r
(
2
) have different values.This simplified joint events based RBMCDA (SJ-RBMCDA) can be seen as a very simple form of the J-RBMCDA with the joint events being broken up into several isolated events. The significant difference is that, in SJ-RBMCDA, the procedure of enumerating the possible association events is replaced by a simple nonparametric method. Therefore, the requiredP
e
r
(
j
) can be computed by directly using the numbers of the validated measurements in the corresponding SVRs. Logically, less computational time is needed.It should be pointed out that the J-RBMCDA and SJ-RBMCDA algorithms may provide more weights to the right SVRs if the tracker can get the correct target estimates. Like all other gating based algorithms, however, the performance of the proposed gating based RBMCDA algorithms will also be degraded in the cases that the tracker provides incorrect target estimates. Another problem is that, for both J-RBMCDA and SJ-RBMCDA, the number of SVRs seems to increase dramatically with the number of targets to be tracked. Figure3 gives an example of tracking 11 targets, and each of the arrows points to a SVR. We can see that the total number of the SVRs is 20 including the empty SVRs (pointed by dotted arrows), so that the number of the SVRs needed to be computed is 18 (pointed by solid arrows). In fact, the dimension curse occurs only in the extreme case when all tracks are in the same neighborhood and with incomplete coverage. In this cases, when tracking T targets the number of SVRs would be 2
T
-
1. For example, in the up left of Figure 3 the joint validation consists of three elliptical validation regions (centered at z
^
1, z
^
2, and z
^
3, resp.). The total number of the SVRs is 2
3
-
1
=
7 including one empty SVR (n
13
=
0), so that the number of the SVRs needed to be computed is 6 (n
1, n
2, n
3, n
12, n
23, and n
123).Figure 3
An example of measurement validation regions for a large number of targets.


## 3.4.  RBMCDA Algorithm with Gating Technique

The gating technique based RBMCDA algorithm is presented in Algorithm1. This algorithm includes four major parts: prediction, finding validation regions and calculating P
e
r
(
j
), calculating data association probabilities and updating the state of particles, and finally a particle weights calculation step. It should be pointed out that only the second part is fundamentally different from the original RBMCDA algorithm. In this algorithm, the target state priors can be represented as a weighted importance samples set
(17)
p
(
x
0
(
j
)
)
=
∑
i
=
1
N
p
‍
w
i
,
0
𝒩
(
x
0
(
j
)
∣
x
i
,
0
(
j
)
,
P
i
,
0
(
j
)
)
,
where i is the identifier of particle with N
p being the number of particles employed. The dynamics and measurements for target j (j
=
1
,
…
,
T) are assumed to be linear Gaussian
(18)
p
(
x
k
(
j
)
∣
x
k
-
1
(
j
)
)
=
𝒩
(
x
k
(
j
)
∣
F
k
-
1
(
j
)
x
k
-
1
(
j
)
,
Q
k
-
1
(
j
)
)
,
p
(
z
k
∣
x
k
(
j
)
,
c
k
=
j
)
=
𝒩
(
z
k
∣
H
k
(
j
)
x
k
(
j
)
,
R
k
(
j
)
)
.Algorithm 1:RBMCDA using gating techniques.
For  k
=
1  to
n  do
For
i
=
1
to
N
p
do
For
j
=
1
to
T
do
x
^
i
,
k
∣
k
-
1
(
j
)
=
F
k
-
1
(
j
)
x
^
i
,
k
-
1
∣
k
-
1
(
j
),                                (i)
P
i
,
k
∣
k
-
1
(
j
)
=
F
k
-
1
(
j
)
P
i
,
k
-
1
∣
k
-
1
(
j
)
[
F
k
-
1
j
]
′
+
Q
k
-
1
(
j
).                            (ii)
End for
j
End for
i
For
j
=
1
to
T
do
z
^
k
∣
k
-
1
(
j
)
=
H
k
(
j
)
[
∑
i
=
1
N
p
‍
w
i
,
k
-
1
x
^
i
,
k
∣
k
-
1
(
j
)
],                                  (iii)
S
k
(
j
)
=
H
k
(
j
)
[
∑
i
=
1
N
p
‍
w
i
,
k
-
1
P
i
,
k
∣
k
-
1
(
j
)
]
[
H
k
(
j
)
]
′
+
R
k
(
j
),                            (iv)
where z
^
k
∣
k
-
1
(
j
) and S
k
(
j
) are the predicted measurement and innovation, respectively.
For
m
=
1
to
N
m
e
a
s
u
r
e
m
e
n
t
s
(number of the measurements) do
Choose z
k
(
m
) that satisfies the following condition as the validated measurement of the jth target:
[
z
k
(
m
)
-
z
^
k
∣
k
-
1
(
j
)
]
′
[
S
k
(
j
)
]
-
1
[
z
k
(
m
)
-
z
^
k
∣
k
-
1
(
j
)
]
≤
γ.                          (v)
End for
m
End for
j
For  r
=
1
to
N
S
V
R
s
(number of the SVRs) do
For
j
=
1
to
T
Calculate P
e
r
(
j
) using gating techniques.
End for
j
For
m
=
1
to
N
r
For
i
=
1
to
N
p
Calculate data association priors p
(
c
i
,
k
∣
c
i
,
k
-
m
:
k
-
1
) by (8) based on the Markov chain
model described in [1].
For
j
=
1
to
T do
z
^
i
,
k
(
j
)
=
H
k
(
j
)
x
^
i
,
k
∣
k
-
1
(
j
),                              (vi)
S
i
,
k
(
j
)
=
H
k
(
j
)
P
i
,
k
∣
k
-
1
(
j
)
[
H
k
(
j
)
]
′
+
R
k
(
j
).                            (vii)
Calculate the marginal measurement likelihood
p
(
z
k
∣
c
i
,
k
=
j
,
c
i
,
1
:
k
-
1
,
z
1
:
k
-
1
)
=
𝒩
(
z
k
(
m
)
∣
z
^
i
,
k
(
j
)
,
S
i
,
k
(
j
)
).                   (viii)
End for
j
Calculate the clutter likelihood
p
(
z
k
∣
c
i
,
k
=
0
,
c
i
,
1
:
k
-
1
,
z
1
:
k
-
1
)
=
V
-
1.                             (ix)
Calculate the posterior distribution of c
i
,
k
p
(
c
i
,
k
∣
c
i
,
1
:
k
-
1
,
z
1
:
k
)
=
p
(
z
k
∣
c
i
,
k
,
c
i
,
1
:
k
-
1
,
z
1
:
k
-
1
)
p
(
c
i
,
k
∣
c
i
,
k
-
m
:
k
-
1
).                (x)
Sample an association indicator c
i
,
k
=
j with probability ρ
i
(
j
)
ρ
i
(
j
)
=
ρ
^
i
(
j
)
∑
j
′
=
0
T
ρ
^
i
(
j
′
), j
=
0
,
…
,
T,                           (xi)
where
ρ
^
i
(
0
)
=
p
(
c
i
,
k
=
0
∣
c
i
,
1
:
k
-
1
,
z
1
:
k
),                            (xii)
ρ
^
i
(
j
)
=
p
(
c
i
,
k
=
j
∣
c
i
,
1
:
k
-
1
,
z
1
:
k
).                             (xiii)
If
j
≠
0
, update the
j
th target using the measurement
z
k
(
m
)
K
i
,
k
=
P
i
,
k
∣
k
-
1
(
j
)
[
H
k
(
j
)
]
′
S
i
,
k
(
j
),                             (xiv)
x
^
i
,
k
∣
k
(
j
)
=
x
^
i
,
k
∣
k
-
1
(
j
)
+
K
i
,
k
[
z
k
(
m
)
-
z
^
i
,
k
(
j
)
],                        (xv)
P
i
,
k
∣
k
(
j
)
=
P
i
,
k
∣
k
-
1
(
j
)
-
K
i
,
k
S
i
,
k
(
j
)
(
K
i
,
k
)
′.                           (xvi)
End if
Calculate the new weight
w
i
,
k
∝
w
i
,
k
-
1
p
(
z
k
∣
c
i
,
k
,
c
i
,
1
:
k
-
1
,
z
1
:
k
-
1
)
p
(
c
i
,
k
∣
c
i
,
k
-
m
:
k
-
1
)
p
(
c
i
,
k
∣
c
i
,
1
:
k
-
1
,
z
1
:
k
).                   (xvii)
End for
i
Resample the particles if needed.
End for
m
Calculate the target state vectors
For
j
=
1
to
x
^
k
∣
k
(
j
)
=
∑
i
=
1
N
p
‍
w
i
,
k
x
^
i
,
k
∣
k
(
j
).                               (xviii)
End for
j
End for
r
End for
k


## 4. Numerical Examples and Simulation Results

### 4.1. Numerical Examples

In some extreme cases (such as that all elliptical validation regions are separated, or coincide exactly), theP
e
(
j
) obtained by different gating techniques will have the same value as P
e
(
j
)
=
P
g
(
j
)
P
d
(
j
).This section just concerns with the general cases. SinceP
g
(
j
) is very close to unity (see Section 2.2), the results illustrated in the tables use P
g
(
j
)
=
1 (j
=
1
,
…
,
T) for convenience. Without loss of generality, these examples do not consider the missed detection and assume P
d
(
j
)
=
1. In these examples, the clutter is modeled as independent and identically distributed with uniform spatial distribution. Examples 1 and 2 are about tracking two targets; Example 3 is about tracking three targets.Example 1.
As shown in Figure4, the numbers of the validated measurements in three SVRs will have four possible cases if clutter does not exist, (a) n
1
=
1, n
2
=
1, n
12
=
0, (b) n
1
=
1, n
2
=
0, n
12
=
1, (c) n
1
=
0, n
2
=
1, n
12
=
1, and (d) n
1
=
0, n
2
=
0, n
12
=
2. Table 1 gives the P
e
r
(
j
) obtained by different gating techniques, where “O-" represents the original RBMCDA and “U-," “J-," and “SJ-" represent the “U-RBMCDA,” “J-RBMCDA,” and “SJ-RBMCDA" algorithms, respectively. The results denoted as “-” mean that the corresponding subregions do not consist of any measurement. In this example, “O-” and “U-” have the same results because both of them do not consider the interrelations of the validated measurements. It can be seen that only the “J-” gives the correct results as expected. As a simplified version of the “J-,” the “SJ-” gives the trade-off results.Table 1
TheP
e
r
(
j
) obtained by four different methods: two-target situation.
(a)/(b)/(c)/(d)
P
e
1
(
1
)
P
e
2
(
2
)
P
e
12
(
1
)
P
e
12
(
2
)
O-
1/1/—/—
1/1/—/—
1/1/—/—
1/0.5/—/—
U-
1/—/1/—
1/—/1/—
1/—/1/—
1/—/0.5/—
J-
—/1/1/1
—/1/1/1
—/0/1/1
—/0.5/1/1
SJ-
—/1/1/1
—/1/1/1
—/1/0/1
—/1/0.5/1All possible hypotheses for measurements that fall inside two validation regions on condition thatP
d
=
1.
(a)
(b)
(c)
(d)Example 2.
In cluttered environment (see Figure1(b)), two cases are studied, (e) n
1
=
1, n
2
=
1, n
12
=
3 and (f) n
1
=
1, n
2
=
8, n
12
=
2. In this example, “J-" and “SJ-" can give the similar results as shown in Table 2. Note that, “U-" still gives the result P
e
r
(
j
)
=
1 in each SVR r.Table 2
TheP
e
r
(
j
) obtained by “U”, “J-”, and “SJ-”: two-target situation.
(e)/(f)
P
e
1
(
1
)
P
e
2
(
2
)
P
e
12
(
1
)
P
e
12
(
2
)
U-
1/1
1/1
1/1
1/1
J-
0.3077/0.1220
0.3077/0.2195
0.6923/0.8780
0.6923/0.7805
SJ-
0.25/0.1111
0.25/0.2
0.75/0.8889
0.75/0.8Example 3.
In Figure5, the numbers of validated measurements in three elliptical regions are N
1
=
9, N
2
=
8, and N
3
=
6, respectively. The numbers of validated measurements in the SVRs are (g) n
1
=
5, n
2
=
3, n
3
=
3, n
12
=
2, n
13
=
0, n
23
=
1, and n
123
=
2. Table 3 gives the P
e
r
(
j
) obtained by “J-" and “SJ-." In this three-target example, the “J-" and “SJ-" can also give the similar results. Next, we will give tracking examples to verify the performance of the algorithms.Table 3
TheP
e
r
(
j
) obtained by “J-” and “SJ-”: three-target situation.
(g)
P
e
1
(
1
)
P
e
2
(
2
)
P
e
3
(
3
)
P
e
12
(
1
)
P
e
12
(
2
)
P
e
23
(
2
)
P
e
23
(
3
)
P
e
123
(
1
)
P
e
123
(
2
)
P
e
123
(
3
)
J-
0.61
0.42
0.55
0.21
0.25
0.12
0.16
0.18
0.21
0.29
SJ-
0.56
0.38
0.5
0.22
0.25
0.13
0.17
0.22
0.25
0.33Figure 5
Example of measurement validation regions for tracking three targets.


### 4.2.  Simulation Results

In the simulations, we model each target with constant velocity model in2-dimensional Cartesian coordinates. The discrete-time state dynamic and measurement models for targets are given by (18), where
(19)
F
k
-
1
(
j
)
=
(
1
0
Δ
0
0
1
0
Δ
0
0
1
0
0
0
0
1
)
,
H
k
(
j
)
=
(
1
0
0
0
0
1
0
0
)
,
G
=
(
1
2
Δ
2
0
Δ
0
0
1
2
Δ
2
0
Δ
)
′
,
Q
k
-
1
(
j
)
=
G
G
′
with the sample interval Δ
=
1. The clutter is modeled as independent and identically distributed with uniform spatial distribution in a rectangular region of the coordinate plane, [
0,500
]
×
[
0,500
]. The number of clutter measurements obeys a Poisson distribution with the Poisson random number λ (clutter rate). Three tracking examples are studied to illustrate the performance and efficiency of the proposed gating techniques based RBMCDA algorithms. The first one involves a situation where two targets are crossing as shown in Figure 6. We want to compare the performance of the algorithms by the tracking position errors. The total number of time steps is set to be 30, the number of particles N
p
=
100, the Poisson number λ
=
50, the measurement variance R
k
(
j
)
=
diag
⁡
(
[
20,20
]
), and the detection probability P
d
(
j
)
=
0.99 (j
=
1
,
…
,
2). Figures 7 and 8 show the average root mean square errors (RMSE) of the four algorithms from 100 different runs. Here, the RMSE is referring to the average position estimation error. At time step k, the RMSE of the jth target is given by
(20)
1
100
∑
j
=
1
2
‍
∑
m
c
=
1
100
‍
(
x
^
j
,
k
(
m
c
)
-
x
j
,
k
)
2
+
(
y
^
j
,
k
(
m
c
)
-
y
j
,
k
)
2
,
where (
x
^
j
,
k
(
m
c
)
,
y
^
j
,
k
(
m
c
)
) are the corresponding position estimation in the m
cth Monte Carlo run.Figure 6
Example of tracking two crossing targets.Figure 7
The average position estimation errors for target 1.Figure 8
The average position estimation errors for target 2.The simulation results show that the tracking process can be divided into two stages: before and after the happening of target crossing. In the first stage, the RMSE curves by all the algorithms have the similar values. It indicates that the proposed gating methods do not have an impact on the performance of the RBMCDA algorithm for tracking separated targets. In the second half of the tracking process, the significant arising of the RMSE curves by “O-" and “U-" algorithms indicates that, when target crossing happens, the “O-" and “U-" algorithms have more times of tracking failures (or mistracking) than “S-" and “SJ-" algorithms. This is because “S-" and “SJ-" can provide more accurate targets’ origins than the “O-" and “U-" algorithms. In this example, the performance of “SJ-" is approximate to that of the “J-." This also supports the results obtained in the previous numerical examples.In the second example, we consider a three-target-crossing situation (as shown in Figure9) to compare the time costs of the algorithms. The total number of time steps is set to be 25, the measurement variance R
k
(
j
)
=
diag
⁡
(
[
10,10
]
), and the detection probability P
d
(
j
)
=
0.8. We repeat each experiment 100 times and the average running times are listed in Tables 4 and 5, where we set a fixed clutter rate λ
=
20 and a fixed number of particles N
p
=
20. All simulations are performed on a PC with a 2.8-GHz Intel processor.Table 4
Computational time (sec) using different numbers of particles.
Numbers of particles
20
40
60
80
100
O-
12.1373
18.2593
25.3149
31.7860
38.4171
U-
1.1085
2.2064
3.3344
4.4614
5.6046
J-
1.2446
2.5641
4.0014
5.3252
6.5214
SJ-
1.1248
2.3910
3.6465
4.8110
5.8696Table 5
Computational time (sec) in different clutter rates.
Clutter rates (λ)
20
40
60
80
100
O-
12.0975
17.5701
22.9209
28.4144
34.0663
U-
1.0522
1.1306
1.2546
1.3155
1.3967
J-
1.1965
1.2832
1.4081
1.4914
1.6091
SJ-
1.0925
1.2024
1.3330
1.4350
1.5127Figure 9
Example of tracking three crossing targets.In Table4, for all the four algorithms, the increases in time cost are proportional to the increases in the number of particles. In Table 5, only the computational time of “O-" is increased apparently with the clutter rate λ. This is because all added clutter should be considered in the data association procedures without using gating technique. The time costs of the proposed gating based algorithms grow moderately because only a small number of the added clutters can fall into the validation regions.In both Tables4 and 5, we can find that “U-" is the most efficient one. In the three gating based algorithms, “J-" needs the most computational time for its dealing with the joint events. Since “SJ-" uses a simple but more direct way, it needs less computational time than that of “J-." From the two tables, the gating technique based RBMCDA algorithms are much more efficient than the original RBMCDA algorithm because of the reduction of validated measurements. The relative efficiencies between these gating techniques can be summarized by “U-" > “SJ-" > “J-." In practice, although “U-" needs less computational time than “J-" and “SJ," but “U-" is not suitable for the use to track multiple closely spaced targets. In this situation, both the “J-" and “SJ-" can yield desirable results because of the rational consideration of the intersection regions.


## 4.1. Numerical Examples

In some extreme cases (such as that all elliptical validation regions are separated, or coincide exactly), theP
e
(
j
) obtained by different gating techniques will have the same value as P
e
(
j
)
=
P
g
(
j
)
P
d
(
j
).This section just concerns with the general cases. SinceP
g
(
j
) is very close to unity (see Section 2.2), the results illustrated in the tables use P
g
(
j
)
=
1 (j
=
1
,
…
,
T) for convenience. Without loss of generality, these examples do not consider the missed detection and assume P
d
(
j
)
=
1. In these examples, the clutter is modeled as independent and identically distributed with uniform spatial distribution. Examples 1 and 2 are about tracking two targets; Example 3 is about tracking three targets.Example 1.
As shown in Figure4, the numbers of the validated measurements in three SVRs will have four possible cases if clutter does not exist, (a) n
1
=
1, n
2
=
1, n
12
=
0, (b) n
1
=
1, n
2
=
0, n
12
=
1, (c) n
1
=
0, n
2
=
1, n
12
=
1, and (d) n
1
=
0, n
2
=
0, n
12
=
2. Table 1 gives the P
e
r
(
j
) obtained by different gating techniques, where “O-" represents the original RBMCDA and “U-," “J-," and “SJ-" represent the “U-RBMCDA,” “J-RBMCDA,” and “SJ-RBMCDA" algorithms, respectively. The results denoted as “-” mean that the corresponding subregions do not consist of any measurement. In this example, “O-” and “U-” have the same results because both of them do not consider the interrelations of the validated measurements. It can be seen that only the “J-” gives the correct results as expected. As a simplified version of the “J-,” the “SJ-” gives the trade-off results.Table 1
TheP
e
r
(
j
) obtained by four different methods: two-target situation.
(a)/(b)/(c)/(d)
P
e
1
(
1
)
P
e
2
(
2
)
P
e
12
(
1
)
P
e
12
(
2
)
O-
1/1/—/—
1/1/—/—
1/1/—/—
1/0.5/—/—
U-
1/—/1/—
1/—/1/—
1/—/1/—
1/—/0.5/—
J-
—/1/1/1
—/1/1/1
—/0/1/1
—/0.5/1/1
SJ-
—/1/1/1
—/1/1/1
—/1/0/1
—/1/0.5/1All possible hypotheses for measurements that fall inside two validation regions on condition thatP
d
=
1.
(a)
(b)
(c)
(d)Example 2.
In cluttered environment (see Figure1(b)), two cases are studied, (e) n
1
=
1, n
2
=
1, n
12
=
3 and (f) n
1
=
1, n
2
=
8, n
12
=
2. In this example, “J-" and “SJ-" can give the similar results as shown in Table 2. Note that, “U-" still gives the result P
e
r
(
j
)
=
1 in each SVR r.Table 2
TheP
e
r
(
j
) obtained by “U”, “J-”, and “SJ-”: two-target situation.
(e)/(f)
P
e
1
(
1
)
P
e
2
(
2
)
P
e
12
(
1
)
P
e
12
(
2
)
U-
1/1
1/1
1/1
1/1
J-
0.3077/0.1220
0.3077/0.2195
0.6923/0.8780
0.6923/0.7805
SJ-
0.25/0.1111
0.25/0.2
0.75/0.8889
0.75/0.8Example 3.
In Figure5, the numbers of validated measurements in three elliptical regions are N
1
=
9, N
2
=
8, and N
3
=
6, respectively. The numbers of validated measurements in the SVRs are (g) n
1
=
5, n
2
=
3, n
3
=
3, n
12
=
2, n
13
=
0, n
23
=
1, and n
123
=
2. Table 3 gives the P
e
r
(
j
) obtained by “J-" and “SJ-." In this three-target example, the “J-" and “SJ-" can also give the similar results. Next, we will give tracking examples to verify the performance of the algorithms.Table 3
TheP
e
r
(
j
) obtained by “J-” and “SJ-”: three-target situation.
(g)
P
e
1
(
1
)
P
e
2
(
2
)
P
e
3
(
3
)
P
e
12
(
1
)
P
e
12
(
2
)
P
e
23
(
2
)
P
e
23
(
3
)
P
e
123
(
1
)
P
e
123
(
2
)
P
e
123
(
3
)
J-
0.61
0.42
0.55
0.21
0.25
0.12
0.16
0.18
0.21
0.29
SJ-
0.56
0.38
0.5
0.22
0.25
0.13
0.17
0.22
0.25
0.33Figure 5
Example of measurement validation regions for tracking three targets.


## 4.2.  Simulation Results

In the simulations, we model each target with constant velocity model in2-dimensional Cartesian coordinates. The discrete-time state dynamic and measurement models for targets are given by (18), where
(19)
F
k
-
1
(
j
)
=
(
1
0
Δ
0
0
1
0
Δ
0
0
1
0
0
0
0
1
)
,
H
k
(
j
)
=
(
1
0
0
0
0
1
0
0
)
,
G
=
(
1
2
Δ
2
0
Δ
0
0
1
2
Δ
2
0
Δ
)
′
,
Q
k
-
1
(
j
)
=
G
G
′
with the sample interval Δ
=
1. The clutter is modeled as independent and identically distributed with uniform spatial distribution in a rectangular region of the coordinate plane, [
0,500
]
×
[
0,500
]. The number of clutter measurements obeys a Poisson distribution with the Poisson random number λ (clutter rate). Three tracking examples are studied to illustrate the performance and efficiency of the proposed gating techniques based RBMCDA algorithms. The first one involves a situation where two targets are crossing as shown in Figure 6. We want to compare the performance of the algorithms by the tracking position errors. The total number of time steps is set to be 30, the number of particles N
p
=
100, the Poisson number λ
=
50, the measurement variance R
k
(
j
)
=
diag
⁡
(
[
20,20
]
), and the detection probability P
d
(
j
)
=
0.99 (j
=
1
,
…
,
2). Figures 7 and 8 show the average root mean square errors (RMSE) of the four algorithms from 100 different runs. Here, the RMSE is referring to the average position estimation error. At time step k, the RMSE of the jth target is given by
(20)
1
100
∑
j
=
1
2
‍
∑
m
c
=
1
100
‍
(
x
^
j
,
k
(
m
c
)
-
x
j
,
k
)
2
+
(
y
^
j
,
k
(
m
c
)
-
y
j
,
k
)
2
,
where (
x
^
j
,
k
(
m
c
)
,
y
^
j
,
k
(
m
c
)
) are the corresponding position estimation in the m
cth Monte Carlo run.Figure 6
Example of tracking two crossing targets.Figure 7
The average position estimation errors for target 1.Figure 8
The average position estimation errors for target 2.The simulation results show that the tracking process can be divided into two stages: before and after the happening of target crossing. In the first stage, the RMSE curves by all the algorithms have the similar values. It indicates that the proposed gating methods do not have an impact on the performance of the RBMCDA algorithm for tracking separated targets. In the second half of the tracking process, the significant arising of the RMSE curves by “O-" and “U-" algorithms indicates that, when target crossing happens, the “O-" and “U-" algorithms have more times of tracking failures (or mistracking) than “S-" and “SJ-" algorithms. This is because “S-" and “SJ-" can provide more accurate targets’ origins than the “O-" and “U-" algorithms. In this example, the performance of “SJ-" is approximate to that of the “J-." This also supports the results obtained in the previous numerical examples.In the second example, we consider a three-target-crossing situation (as shown in Figure9) to compare the time costs of the algorithms. The total number of time steps is set to be 25, the measurement variance R
k
(
j
)
=
diag
⁡
(
[
10,10
]
), and the detection probability P
d
(
j
)
=
0.8. We repeat each experiment 100 times and the average running times are listed in Tables 4 and 5, where we set a fixed clutter rate λ
=
20 and a fixed number of particles N
p
=
20. All simulations are performed on a PC with a 2.8-GHz Intel processor.Table 4
Computational time (sec) using different numbers of particles.
Numbers of particles
20
40
60
80
100
O-
12.1373
18.2593
25.3149
31.7860
38.4171
U-
1.1085
2.2064
3.3344
4.4614
5.6046
J-
1.2446
2.5641
4.0014
5.3252
6.5214
SJ-
1.1248
2.3910
3.6465
4.8110
5.8696Table 5
Computational time (sec) in different clutter rates.
Clutter rates (λ)
20
40
60
80
100
O-
12.0975
17.5701
22.9209
28.4144
34.0663
U-
1.0522
1.1306
1.2546
1.3155
1.3967
J-
1.1965
1.2832
1.4081
1.4914
1.6091
SJ-
1.0925
1.2024
1.3330
1.4350
1.5127Figure 9
Example of tracking three crossing targets.In Table4, for all the four algorithms, the increases in time cost are proportional to the increases in the number of particles. In Table 5, only the computational time of “O-" is increased apparently with the clutter rate λ. This is because all added clutter should be considered in the data association procedures without using gating technique. The time costs of the proposed gating based algorithms grow moderately because only a small number of the added clutters can fall into the validation regions.In both Tables4 and 5, we can find that “U-" is the most efficient one. In the three gating based algorithms, “J-" needs the most computational time for its dealing with the joint events. Since “SJ-" uses a simple but more direct way, it needs less computational time than that of “J-." From the two tables, the gating technique based RBMCDA algorithms are much more efficient than the original RBMCDA algorithm because of the reduction of validated measurements. The relative efficiencies between these gating techniques can be summarized by “U-" > “SJ-" > “J-." In practice, although “U-" needs less computational time than “J-" and “SJ," but “U-" is not suitable for the use to track multiple closely spaced targets. In this situation, both the “J-" and “SJ-" can yield desirable results because of the rational consideration of the intersection regions.


## 5. Conclusion

This paper has studied the gating techniques in the application of the RBMCDA filter to multitarget tracking. Three different gating methods are presented and compared by computing both the tracking errors and time cost. “U-" incorporates a very simple gate into the framework of the RBMCDA approach. “J-" can take the measurement uncertainties into account reasonably by calculating the joint events. As a simplification of “J," “SJ-" is more efficient than “J" and the tracking performance loss incurred is not significant in the experimental examples. Therefore, “SJ-" can be a time-saving choice for practical applications. It should be pointed out that the gating techniques discussed in this paper may eliminate all measurements outside the validation regions of the targets that have already been detected, which will make it difficult to detect newly appearing targets. To address this, the proposed gating techniques could be started after the initialization periods of the RBMCDA filter to avoid impairing the tracks initiation.



---

*Source: 960857-2014-03-03.xml*