3 - Artigo Ernesto

Digital Signal Processing 126 (2022) 103481
Contents lists available at ScienceDirect
Digital Signal Processing

www.elsevier.com/locate/dsp
A novel algorithm for tracking a maneuvering target in clutter

Marcelo Lucena de Souza a , Alberto Gaspar Guimarães b,∗ , Ernesto Leite Pinto c
a
Frequentis Comsoft GmbH, Karlsruhe, Germany
b
Department of Telecommunication Engineering, Fluminense Federal University, Niteroi, Brazil
c
Department of Electrical Engineering, Military Institute of Engineering, Rio de Janeiro, Brazil
a r t i c l e i n f o a b s t r a c t
Article history: An algorithm for tracking a maneuvering target under measurement origin uncertainties is derived based
Available online 21 February 2022 on the approximation and propagation of the target state posterior distribution by combining Bayesian
decision theory and suitable hypothesis merging procedures. Simulation results show that the main
Keywords:
feature of this algorithm is its ability to significantly reduce the estimation error during non-maneuvering
Bayesian methods
Maneuvering target tracking
periods, making it quite suitable for tracking low maneuvering aircrafts. At the same time, the proposal
Clutter is able to keep very low levels of track loss rate even for scenarios with high false alarm probability
Data association and trajectories with high degree of maneuverability. This proposal presents overall superiority when
IMMPDAF compared to the Interacting Multiple-Model with Probabilistic Data Filtering (IMMPDAF) solution, with
an affordable increase in computational cost.
© 2022 Elsevier Inc. All rights reserved.
1. Introduction the Gaussian mixture representing possible association events at a

given time instant into a single Gaussian probability density func-
The problem of tracking a maneuvering target in clutter is cru- tion (pdf). This strategy has been shown to provide good balances
cial for many sensing systems. It basically consists on obtaining a of performance and computational load in several applications [8],
sequence of target state estimates (track) from noisy sensor ob- [9].
servations with data association and target dynamics uncertainties More sophisticated solutions, such as the Multiple Hypothesis
[1]. Tracking (MHT) [10], propagate full data association histories in
Statistical modeling of this problem under a Bayesian estima- consecutive time frames and utilize ad-hoc hypotheses manage-
tion framework can lead to Gaussian mixtures representations of ment strategies to reduce the amount of propagated terms to a
the posterior distribution of the target state, with exponentially practical value. It has been largely accepted that the MHT provides
increasing amount of components. As optimal estimators are in- better performance and requires much more computation than the
tractable in this context, the search for cost-efficient and effective PDA filter [8]. Both PDAF and MHT algorithms assume a single
tracking algorithms has been addressed in several works over the mode non-switching system, so they are not adequate for dealing
last decades [2], [3], [4]. Despite being a mature research topic, with a maneuvering target in clutter.
there is still space for improvements in this field, specially due to The isolated problem of target maneuverability has been tack-
the current interest in tracking a maneuvering target under heavy led by tracking filtering developed on the grounds of some spe-
clutter conditions [5], [6], in which the problem of measurement- cific strategies for state-space modeling. Seminal approaches for
to-target uncertainty is of utmost importance. that are the introduction of variable state dimension [11], the
Assuming a scenario with measurement origin uncertainty, data inclusion of unknown inputs to be estimated [12] and the use
association techniques are usually applied to determine associa- of multiple state-space models [13]. The multiple model frame-
tion events related to sensor measurements that likely have been work, where the Interacting Multiple-Model (IMM) algorithm [14]
originated from the target of interest at a given time [7]. The is largely regarded as the most important and popular solution,
probabilistic data association filter (PDAF) is a well-known algo- has been recognized to be a cost-effective tracking strategy [13].
rithm able to deal with this problem [8]. PDAF merges all terms of The IMM employs a bank of Kalman filters (KF) matched to flight-
models in order to propagate model-conditioned hypotheses. Sev-
eral proposed improvements substitute the traditional KF by other
estimators that have in common the ability to address nonlinear
*
Corresponding author.
E-mail addresses: marcelo.lucenadesouza@frequentis.com (M. Lucena de Souza), systems, such as Extended KF [15], Unscented KF [15], and the Cu-
agaspar@id.uff.br (A. Gaspar Guimarães), ernesto@ime.eb.br (E. Leite Pinto). bature KF [16]. The work in [17] additionally proposes to adjust
https://doi.org/10.1016/j.dsp.2022.103481
1051-2004/© 2022 Elsevier Inc. All rights reserved.
M. Lucena de Souza, A. Gaspar Guimarães and E. Leite Pinto Digital Signal Processing 126 (2022) 103481
the model transition probabilities in real time aiming at improv- is a significant improvement of position estimation performance
ing the filtering accuracy. The same strategy is considered in some for scenarios of low maneuvering target tracking (e.g. civil air-
other references [18], [19]. More recently, the IMM framework is craft). Besides, the proposed algorithm is shown to be more robust
employed with adaptive estimation of the target turn rate at each to dense clutter conditions. For trajectories with intense maneu-
time step [20] and for underwater tracking of a maneuvering tar- vers, our algorithm presents a track loss rate comparable with
get in a complex ocean environment [21]. that of the IMMPDAF algorithm but a position error performance
The IMMPDAF (Interacting Multiple-Model with Probabilistic slightly worse. Despite the fact that the superiority of the pro-
Data Filtering) algorithm [2] simultaneously deals with mode-of- posed method is mainly perceived for non-maneuvering periods,
flight and measurement uncertainties by jointly using the IMM its overall performance is better than the IMMPDAF taking into
algorithm and the PDA filter. This is done by replacing Kalman consideration the position error averaged along trajectories of dif-
by PDA filters in the IMM framework. MHT-based algorithms have ferent types.
also been extended to handle maneuvering targets in clutter with The rest of the paper is organized as follows. Next section
different schemes for reducing the number of propagated mixture presents the problem formulation and the proposed algorithm is
components [22], [23], but these algorithms tend to present com- derived in Section 3. Numerical results are shown in Section 4 fol-
putational complexity orders of magnitude greater than IMMPDAF- lowed by conclusions in Section 5.
based proposals, as shown e.g. in [2]. More recently, algorithms
based on random set theory, or Random Finite Sets (RFS), have 2. Problem statement
emerged in the literature mainly to address multi-target scenarios
[24]. These algorithms provide an elegant way of estimating the The maneuvering target is modeled as a stochastic dynamic sys-
target state as well as the number of targets in a unified frame- tem whose state and observation equations are given by
work [25] which can also be extended to deal with maneuvering
targets [26]. Despite having the possibility of being adapted to the xk+1 = F [ M k ]xk + v [k, M k ], k = 0, 1, . . . , (1)
case of a single maneuvering target in clutter, these algorithms are
usually implemented with particle filters or Gaussian sum filtering zk = H [ M k ]xk + w [k, M k ], k = 1, 2, . . . , (2)
[25], which are computationally very expensive compared to the
where xk , F [ M k ], zk and H [ M k ] are respectively the state vector,
IMMPDAF.
state transition matrix, true (target-originated) measurement vec-
Despite its widespread use in maneuvering target tracking, the
tor and measurement matrix, all defined at the discrete time k. M k
IMM/IMMPDAF estimators present some drawbacks. In particular,
represents the flight model in effect at k and can be any element of
when tuned to track maneuvering targets, they tend to produce
the model-set = {ψi }ri=1 , being r the number of models. The set
high overall estimation error during non-maneuvering phases, as
is assumed to be time-invariant and known, besides containing
pointed out in [27], [28], [29]. Moreover, in scenarios with dense
a single non-maneuvering model denoted as ψ1 , without loss of
clutter and larger radar revisit periods (in the range of 5 sec-
generality. The random sequences v [k, M k ] and w [k, M k ] are Gaus-
onds for instance), the IMMPDAF might perceive clutter as maneu-
sian, zero-mean, white and mutually independent, with covariance
vers [30], thereby increasing the estimation error and track loss
matrices Q [ M k ] and R [ M k ], respectively. Given M k , the matrices
rate.
F [ M k ], H [ M k ], Q [ M k ] and R [ M k ] are assumed to be known, and
Some recent works have proposed modifications to IMMPDAF
the initial state x0 is a Gaussian random vector with known mean
trying to better deal with the spurious measurements of a clut-
and covariance matrix.
tered environment. In [31] multi-sensor data fusion and state aug-
Model switching is modeled as a time-homogeneous Markov
mentation with an amplitude feature are used to improve esti-
chain with r states. Transition probability from state i to state j
mation accuracy and robustness. In [32], following the strategy
denoted by P ( M k = ψ j | M k−1 = ψi ) p i j is the (i , j )-th entry of
adopted for an IMM framework by some of the aforementioned
the r × r transition probability matrix T , which is also considered
references, a multiple model-based algorithm using data associa-
to be known.
tion filters is presented in which the transition probabilities of the
flight modes are updated based on the current as well as a prop- At time k, the set of validated measurements, i.e. those that
νk
erly chosen reference state of the target. fall inside a validation region or gate, is denoted by Z k = { zk, j } j =1,
Despite having produced some improvements in clutter en- being νk the number of validated measurements, and the notation
vironments in comparison to IMMPDAF, these proposals remain
within the borders of the IMM framework and pay the price for
k
Zk Zi (3)
that option, particularly in relation to the performance in peri-
i =1
ods out of maneuvers. Without neglecting the advantages of the
IMM approach, it seems quite reasonable to recognize that the in- stands for the set of validated measurements up to k.
vestigation of target tracking algorithms suitable for applications Considering the measurement uncertainty for handling targets
characterized by maneuvers and spurious measurements should go in clutter, data association hypotheses are formulated.
beyond IMM limits. In the present paper we try to contribute in A measurement association hypothesis at time k is denoted
that sense. by k = j ∈ {0, . . . , νk }, where a value j ≥ 1 corresponds to the
The algorithm here proposed to handle flight model uncer- event that the j-th measurement was originated from the target
tainty and data association, referred to as Model-Detection Based of interest, and j = 0 stands for the hypothesis that none of the
Propagation of Joint Hypotheses (MDetPH), presents a well suited measurements came from the target (the target was not detected
hypothesis propagation scheme conditioned to the outcome of a or its measurement was not validated).
Bayesian hypothesis test that decides whether the target is in uni- The flight model and measurement suppositions can be grouped
form motion or in maneuver. together into a single hypothesis, referred to as the model-
A simulation-based performance comparison with the IMM- measurement joint hypothesis and defined for time instant k as
PDAF scheme is presented. It is shown that our proposal yields
significantly less overall root mean square (RMS) position error Hk,i , j { M k = ψi , k = j }, (4)
during non-maneuvering flight periods at the price of produc-
ing higher peak errors at the start of a maneuver. The net result with 1 ≤ i ≤ r and 0 ≤ j ≤ νk .
2
The l-th sequence of model-measurement joint hypotheses p u (s)i , being ψu (s) the flight model of sequence H k−1,s at time k −
through time k is denoted by H k,l and can be recursively expressed 1.
as Therefore, we see that eq. (6) can be recursively computed
but the problem that arises is that the amount of hypotheses ηk
H k,l Hk,i , j ∪ H k−1,s , (5) presents exponential increase, so any practical algorithm aiming
at evaluating the target state posterior density must rely on some
where H k−1,s is its parent sequence (s refers to the s-th sequence kind of approximation.
propagated until k − 1) and Hk,i , j is its last element. It is worth
to notice that there is a strict one-to-one correspondence between 3. Model-detection based propagation of joint hypotheses
the index l and the triplet (s, i , j ). (MDetPH)
Given the measurement history Z k and the state space model
(1)-(2), we are interested in the calculation of the minimum mean 3.1. Algorithm overview
squared error (MMSE) estimate of xk and its error covariance ma-
trix, which requires the evaluation of expectations with respect to The central idea of the MDetPH algorithm is to carry out at
the target state posterior pdf at time k. Using the total probability each time step a Bayesian hypothesis test to infer if the tracked
theorem this pdf can be expressed as target is maneuvering or not, and choose a strategy for updating
ηk an approximation of (6) according to the test result.
The goal is to preserve the essential information for keeping
p [xk | Z k ] = p [xk | H k,l , Z k ] P ( H k,l | Z k ) , (6)
a good level of accuracy when there is no maneuver and at the
l =1
same time being able to follow sharp turns with a small track loss
k
where ηk rk j =1 ( j + 1).
ν Under the assumptions made here, the rate, at a feasible computational cost. With this aim the amount of
propagated hypotheses1 to the next iteration, denoted as nk , is re-
above distribution is a Gaussian mixture and the term p [xk | H k,l ,
duced to 2 or r, depending on the outcome of the Bayesian model
Z k ] can be recursively computed by using Kalman filter steps.
detector ( M̂ k ).
The term P ( H k,l | Z k ) can be recursively calculated by
An iteration of the proposed algorithm is thus composed of
1 three steps: 1) model-conditioned state prediction, 2) measure-
P ( H k,l | Z k ) = p [ Z k | H k,l , Z k−1 ] ment association-based filtering, and 3) hypothesis reduction to
c (7)
update the approximate posterior pdf of the target state. If M̂ k =
× P (Hk,i , j | H k−1,s , Z k−1 ) P ( H k−1,s | Z k−1 ),
ψ1 (non-maneuvering model contained in as stated before), the
where c denotes a normalization constant. ongoing mixture is reduced by propagating only the highest prob-
Assuming the uniformly spatially distributed and independent ability component evaluated in step 2 and a second term obtained
across time clutter model [1], the likelihood lk p [ Z k | H k,l , Z k−1 ] by merging. Otherwise, the reduced mixture is composed of r pdfs
is given by conditioned to the flight model, in a similar way to what is done
−νk +1 −1
in the classical algorithms GPB2, IMM and IMMPDAF.
P G N ∗ [ zk, j ; ẑk|k−1 , ϒk ],
s ,i s ,i
Vk j = 1, . . . , νk Accordingly, the proposed approximation to (6) is updated as
lk = −νk , (8) follows
Vk , j=0
where V k is the validation region volume, P G is the probability p [xk | Z k ]

that the measurement originated from the target falls within the
k α p [xk | H k,lmax , Z k ] + (1 − αk ) p M [xk ], if M̂ k = ψ1 (11)
validation region (gate probability), and N ∗ [.; μ, Q ] is a Gaussian ≈ r
probability density function with parameters (μ, Q ) truncated in j =1 P ( M k = ψ j | Z ) p [xk | M k = ψ j , Z ],
k k
otherwise
s ,i s ,i
V k . The quantities ẑk|k−1 and ϒk are respectively the predicted
where αk P ( H k,lmax | Z k ), being H k,lmax the hypotheses sequence
measurement and the measurement prediction covariance (inno-
with the highest posterior probability at time k, and the pdf
vation covariance) matrix, given the hypotheses sequence H k−1,s
p M [xk ] results from merging of the other pdfs p [xk | H k,l , Z k ], l =
and the flight model M k = ψi .
lmax .
Recalling the definition of the model-measurement joint hy- An example of a cycle of the MDetPH algorithm is graphically
pothesis at time k in (4), its prior probability, given a parent se- depicted in Fig. 1 for r = 2 and νk = 1, assuming that: no ma-
quence H k−1,s , can be evaluated as neuver is detected (i.e. M̂ k = ψ1 ); there are 2 survivor hypotheses
from the previous iteration (nk−1 = 2), and the branch (1,1,1) has
P (Hk,i , j | H k−1,s , Z k−1 )
(9) the highest posterior probability.
= P (k = j | H k−1,s , Z k−1 ) P ( M k = ψi | H k−1,s , Z k−1 ) The reasoning for this approximation is discussed in the follow-
ing.
where it has been considered that k and M k are independent (a
non-parametric clutter model [1] is assumed, which is flight-model
3.2. Rationale
independent).
The assumed a priori probability for the measurement associa-
If we consider just mode-of-flight uncertainty, during non-
tion event k is
maneuver periods most of the target dynamics can be described
by one or very few mixture terms with high posterior probabil-
1
k −1 , s k −1 νk P D P G , j = 1, . . . , νk
P (k = j | H ,Z )= , (10) ity, as it is evidenced by the small estimation errors obtained with
1 − PD PG, j=0 pruning algorithms [28].
where P D is the probability of target detection.
The second term in the right-hand side of (9) corresponds to 1
From this point on the term “hypothesis” will be used in a broader sense than
the model M k prior probability. In view of the Markov property it before, to refer to any component of the reduced mixture calculated within the
is given by P ( M k = ψi | H k−1,s , Z k−1 ) = P ( M k = ψi | M k−1 = ψu (s) ) = MDetPH algorithm to approximate (6).
3
posterior probability evaluation along the time, which is important

to ensure the effectiveness of the detector employed to infer if the
target is out of maneuver. Details on the operation of this detector
are given in what follows.
3.3. Bayesian hypothesis test
The operation rule of the hypothesis test here proposed to de-

cide whether the target at time k is not maneuvering is expressed
as
H0
P ( M k = ψ1 | Z k ) ≷ ξ, (12)
H1
where H0 is the hypothesis that the flight dynamics follows the

non-maneuvering model ψ1 at time k, H1 denotes the opposite al-
ternative, P [ M k = ψ1 | Z k ] is the posterior probability of model ψ1 ,
which can be obtained by marginalization of P (Hk,1, j , H k−1,s | Z k )
(previously evaluated in (7)) as follows
nk−1

νk
P ( M k = ψ1 | Z k ) = P (Hk,1, j , H k−1,s | Z k ). (13)
s =1 j =0
It is worthy to notice that by proper choice of threshold ξ

we may adjust the balance between estimation errors in non-
maneuvering phases and peak errors during start of maneuvers.
For instance, if ξ is larger, the r flight model-conditioned states
shown in the second line of (11) are propagated more often, thus
reducing peak errors at the expense of increasing overall estima-
tion error in non-maneuvering periods.
Fig. 1. An example of MDetPH iteration when non-maneuver hypothesis is detected Next, we present a detailed description of the proposed algo-
( M̂ k = ψ1 ; with r = 2, νk = 1 and nk−1 = 2). rithm.
3.4. MDetPH algorithm in details

However, when we consider the target changing from an uni-
form motion to maneuver, the posterior density terms with highest
The task of the MDetPH algorithm is to continuously update
weights in the mixture no longer reflect well the target dynamics.
the target track over time by recursively evaluating the state vec-
If a pruning approach is adopted, it may take several iterations
tor estimate (x̂k|k ) and the associated covariance matrix (k|k ). It
until hypotheses conditioned to maneuver models become signif-
is assumed that a confirmed track exists at k = 0 with initial state
icant in the propagated mixture. This is the reason why pruning
x0 distributed according to a Gaussian pdf with parameters (x̂0|0 ,
algorithms yield high estimation errors during mode changes [33].
0|0 ), both given as input to the algorithm by some track initiation
Merging-only algorithms perform better in these situations be-
algorithm [1].
cause they do not completely discard hypotheses, so some infor-
A cycle of the algorithm at time k is presented next, assuming
mation of maneuver models is always present in the propagated
that nk−1 surviving hypotheses have been generated in the pre-
mixture.
vious iteration and the associated parameters x̂ks −1|k−1 , ks −1|k−1
Furthermore, taking the measurement origin uncertainty also
into consideration, we see that false alarms may wrongly be per- and P ( H k−1,s | Z k−1 ), s = 1, . . . , nk−1 are available. The state esti-
ceived as maneuvers or may inhibit perception of actual tar- mate and covariance at time k − 1 (x̂k−1|k−1 , k−1|k−1 ) are also
get maneuvers. In such scenario, direct propagation of model- assumed to be on hand.
measurement association hypotheses must be considered judi-
ciously, since it could create in the next iteration a new branch 3.4.1. Measurement validation
of hypotheses that have been deviated from the true target, possi- The set of validated measurement Z k is obtained using the pro-
bly resulting in a track loss. cedure explained in [1, pg. 107], so a detected observation z∗ at
Our proposal is to maintain a specific model-measurement as- time k is considered valid if
sociation hypothesis without merging with any other hypothesis
only when the target is considered not in maneuver ( M̂ k = ψ1 ( z∗ − ẑki |k−1 ) (ϒki )−1 ( z∗ − ẑki |k−1 ) ≤ γ , (14)
in (11)), that is, when there is sufficiently strong evidence that
where γ is the validation region threshold which depends on the
the non-maneuvering flight mode properly reflects the actual tar-
gate probability P G , and ( ẑki |k−1 , ϒki ) are the model-conditioned
get dynamics. We also propose to build a second hypothesis in
predicted measurement and covariance matrix computed by
these cases, obtained by merging all the remaining terms of the
ongoing Gaussian mixture, to preserve information from maneuver
ẑki |k−1 = H [ψi ]x̂ki |k−1 , (15)
models that will be useful when a mode change occurs.
On the other hand, when the target is considered to be in ma- ϒki = H [ψi ]ki |k−1 H [ψi ] + R [ψi ], (16)
neuver ( M̂ k = ψ1 ) we propose to adopt a conservative approach by
merging the nk−1 r (νk + 1) branches into r model-conditioned hy- being (x̂ki |k−1 , ki |k−1 ) the model-conditioned predicted state and
potheses. The intention is to keep the accuracy of the flight model the state prediction covariance given by
4
nk−1
x̂ki |k−1 = F [ψi ]x̂k−1|k−1 , (17) (i ) 1
νk
( s ,i , j )
x̂k|k = x̂k|k P ( H k,(s,i , j ) | Z k ) (23)
ki |k−1 = F [ψi ]k−1|k−1 F [ψi ] + Q [ψi ]. (18) P ( M k = ψi | Z k )
s =1 j =0
nk−1
Following [1], the flight model ψi considered in eqs (15)-(18)
1
νk
( s ,i , j ) ( s ,i , j )
is the one with largest variance for the acceleration parameter k(i|)k = k|k + (x̂k|k
(largest uncertainty). P ( M k = ψi | Z k ) (24)
s =1 j =0
( s ,i , j )
(i ) (i )
3.4.2. Model-conditioned state and covariance prediction − x̂k )(x̂k|k − x̂k ) P ( H k,(s,i , j ) | Z k ).
For all s = 1, . . . , nk−1 surviving hypothesis from time k − 1 and
( s ,i )
models ψi ∈ (i = 1, . . . , r), the predictions of the state (x̂k|k−1 ) 3.4.7. State estimation update
( s ,i ) Target state estimate is updated as follows:
and covariance (k|k−1 ) are evaluated using eqs. (17) and (18) with
(x̂ks −1|k−1 , ks −1|k−1 ) available at k − 1. a) if M̂ k = ψ1
l k,M k M
3.4.3. Likelihood evaluation x̂k|k = P ( H k,lmax | Z k )x̂kmax
|k + P ( H | Z )x̂k|k (25)
( s ,i , j )
For each triple (s, i , j), likelihood functions k are calcu-
with covariance
lated for each model ψi and validated measurement zk, j as stated
in eq. (8).

k|k = P ( H k,lmax | Z k ) lkmax lmax lmax
|k + (x̂k|k − x̂k|k )(x̂k|k − x̂k|k ) +
3.4.4. Posterior probabilities computation

P ( H k,M | Z k ) kM M M
|k + (x̂k|k − x̂k|k )(x̂k|k − x̂k|k )
The posterior probabilities of the hypotheses sequences H k,l ≡
H k,(s,i , j ) = { M k = ψi , k = j , H k−1,s } are evaluated using eqs. (26)
(7)-(10).
b) if M̂ k = ψ1
3.4.5. Model-measurement hypothesis conditioned filtering

r
( s ,i ) ( s ,i ) ( s ,i , j ) ( s ,i , j ) (i )
From x̂k|k−1 and k|k−1 one computes x̂k|k and k|k for each x̂k|k = x̂k|k P ( M k = ψi | Z k ) (27)
validated measurement zk, j by performing hypothesis-conditioned i =1
Kalman filtering. For j = 0 (event that none of the measurements
(s,i ,0) ( s ,i ) (s,i ,0) ( s ,i ) with covariance
were validated), x̂k|k = x̂k|k−1 and k|k = k|k−1 .

r
(i )
k|k + (x̂k|k − x̂k|k )(x̂k|k − x̂k|k ) P ( M k = ψi | Z k ). (28)
(i ) (i )
3.4.6. Hypothesis propagation k|k =
Hypothesis propagation is conducted as outlined in eq. (11). i =1
The hypothesis test is initially performed on the basis of eqs.
(12)-(13) and the following alternatives are considered: 4. Numerical results
a) if M̂ k = ψ1 two hypotheses are propagated, H k,lmax and H k,M . A thorough performance investigation of the proposed algo-
The first corresponds to the branch with highest posterior proba- rithm has been performed by simulation, taking the IMMPDAF as
bility (i.e. P ( H k,lmax | Z k ) = max P ( H k,(s,i , j ) | Z k )) whereas the second reference. Some results are presented in the following, as well as
( s ,i , j ) numerical results of computational load evaluation.
is originated from the merging of all other possibilities by moment
matching, so its parameters are computed as follows:
4.1. Simulated conditions
k,M k k,lmax k
P (H | Z ) = 1 − P (H |Z ) (19)
4.1.1. Radar and clutter parameters
nk−1
1
r
νk
Radar parameters were set based on an L-band long-range
x̂kM
( s ,i , j )
|k = x̂k|k P ( H k,(s,i , j ) | Z k ) surveillance radar with mechanically rotating antenna. The mod-
P ( H k,M | Z k )
s =1 i =1 j =0 eling described in [7] and [34] was assumed to generate target
((s,i , j )=lmax )
observations. The signal-to-noise ratio (S N R) for a target at range
(20) R is calculated as S N R = ( R 0 / R )4 , where R 0 is the nominal range
nk−1
1
r
νk
( s ,i , j ) from which the radar yields S N R = 0 dB for a target with a par-
kM
( s ,i , j )
|k = k|k + (x̂k|k ticular radar cross section (RCS) value. Thus, R 0 summarizes the
P ( H k,M | Z k )
s =1 i =1 j =0 (21) radar figure of merit relative to the considered target. It has been
((s,i , j )=lmax )
calculated by using the radar range equation [7].

− x̂kM − x̂kM
( s ,i , j ) k,(s,i , j ) k
|k )(x̂k|k |k ) P ( H |Z ) The SNR jointly with a specified probability of false alarm ( P F A )
and the number of integrated pulses (n p ) were used to calculate
the target probability of detection at a given instant, assuming
b) if M̂ k = ψ1 hypothesis branches H k,l are combined for each
coherent integration and Swerling type I model for RCS fluctua-
flight mode with moment matching, and the following parameters
tion [34]. Then a Bernoulli trial was performed to simulate the
are computed2 for i = 1, . . . , r
target detection outcome. Clutter was assumed to be uniformly
nk −1

νk distributed over the radar surveillance area and the number of
P ( M k = ψi | Z k ) = P ( H k,(s,i , j ) | Z k ) (22) false alarms was modeled as a Poisson random variable [1] with
s =1 j =0
mean P F A × ncells , being ncells the number of detection cells.
Given an input trajectory, the radar model has been used to
generate 3D measurements in spherical coordinates with added
2
We remark that P ( M̂ k = ψ1 | Z k ) has already been evaluated for performing the Gaussian noise of zero mean and standard deviations σr , σθ and
hypothesis test, so (22) is computed only for the r − 1 remaining models. σφ (range, azimuth and elevation respectively). Tracking algorithms
5
Fig. 2. RMS position error for trajectories 1 to 3.
performed standard conversion [1] from spherical to Cartesian co- cal miles) away from the radar. The target performs 4 horizontal
ordinates (unbiased conversion was not necessary since the stan- maneuvers with acceleration levels of 2g to 7g separated by non-
dard conversion validity limits are attained). Radar model parame- maneuvering periods of approximately 200 seconds, and remains
ters used in the simulations are: sampling period = 5 s, σr = 120 at an altitude of 1.5 km during the entire flight.
m, σθ = 0.15◦ , σφ = 0.15◦ , n p = 16 to 46 and ncells = 221184000.
The radar model generates clutter uniformly in a sphere of radius 4.1.3. Algorithm and flight model parameters
of 180 NM and a bounding box is used to select the clutter mea- Both algorithms were implemented with 2 flight-models similar
surements that might interfere with the tracking of the true target. to those adopted in [36], [7]: a nearly-constant velocity model (ψ1 )
This box has horizontal half-width of 42.5 km, and vertical half- and a discrete white-noise acceleration model (ψ2 ) with high pro-
width of 5 km centered at the true position of the target. cess noise variance (acceleration noise variance is (7 × 9.8 m/s2 )2
for ψ2 and (0.1 × 9.8 m/s2 )2 for ψ1 ).
4.1.2. Trajectories The adopted model transition probabilities are p 11 = p 22 = 0.8
The 6 target trajectories described in the radar tracking bench- and p 12 = p 21 = 0.2. Track initiation algorithms were not imple-
mark evaluated in [35] and their corresponding RCS were used for mented in the simulations. Target originated measurements were
performance evaluation in 3D space. In short, the first trajectory employed to yield initial track estimates to IMMPDAF and MDetPH
represents a large aircraft (e.g. military cargo), the second can be following the two-point differencing method [36].
associated to a smaller and more maneuverable target, the third Additional parameters for both algorithms were P D = 0.95 and
and fourth ones represent bombers flying at high speeds with good P G = 0.99, with its corresponding gate threshold γ = 11.34. Re-
maneuverability, and trajectories 5 and 6 reproduce fight/attack garding the false alarm probability, the values P F A = 10−4 and
aircraft movements. P F A = 2 × 10−3 have been addressed.
Since those trajectories were composed mainly of maneuvers, Performance has been evaluated in terms of RMS estimation
an extra trajectory was implemented with larger periods of non- position error and track loss rate, by averaging over 3000 simula-
maneuvering phases, labeled here as Trajectory 7. It has a duration tion runs. A track has been considered to be lost when the distance
of 900 seconds and a 1 m2 RCS target that starts 40 NM (nauti- between the true target position and its estimate became greater
6
Fig. 3. RMS position error for trajectories 4 to 7.
than 7 km. MDetPH was simulated with two threshold values for ues. As a reference, the linearized 3D measurement error standard
the hypothesis testing, ξ = 0.8 and 0.9, for sensitivity investigation. deviation is also included in the figures (curve labeled as σ w ).
The following observations can be drawn from the simulation
4.2. Simulation results results:
4.2.1. Performance evaluation • During non-maneuvering phases MDetPH algorithm presented

Figs. 2(a)-(f) and 3(a)-(h) show RMS position error curves and much better results, with error levels significant lowers than
Tables 1(a)-(g) summarize position error values, track loss rates the produced by IMMPDAF. This behavior is quite pronounced
and computational load, for all trajectories and for both P F A val- for trajectories 1 and 7 where aircrafts present low maneu-
7
Table 1
Performance results for trajectories 1 to 7.
P F A = 10−4 P F A = 2 × 10−3
IMMPDAF MDetPH MDetPH IMMPDAF MDetPH MDetPH
(ξ = 0.8) (ξ = 0.9) (ξ = 0.8) (ξ = 0.9)
RMS position error (m) (entire trajectory avg) 225.1 221.9 221.4 251.3 251.6 249
RMS position error (m) (non-maneuver periods avg) 210.9 206.0 205.5 226.0 222.9 221.8
RMS position error (m) (maneuver periods avg) 255.7 251.7 252.2 303.0 303.1 299.5
Peak position error (m) 265.7 258.7 257.7 314.8 344.1 335.4
Computational cost 1 2.2 2.2 1 3.6 3.6
Track loss (%) 0.1 0.1 0.1 0.1 0.1 0.1
(a) Trajectory 1
P F A = 10−4 P F A = 2 × 10−3
(ξ = 0.8) (ξ = 0.9) (ξ = 0.8) (ξ = 0.9)
RMS position error (m) (entire trajectory avg) 237.7 234 233.8 279.7 284.3 283.8
RMS position error (m) (maneuver periods avg) 252.7 252 251.8 315.0 326.3 326.1
Track loss (%) 0.2 0.2 0.2 0.1 0.1 0.1
(b) Trajectory 2
P F A = 10−4 P F A = 2 × 10−3
(ξ = 0.8) (ξ = 0.9) (ξ = 0.8) (ξ = 0.9)
RMS position error (m) (entire trajectory avg) 234.3 231 230.3 300.7 289.9 287.4
Track loss (%) 0.5 0.5 0.5 0.4 0.4 0.4
(c) Trajectory 3
P F A = 10−4 P F A = 2 × 10−3
(ξ = 0.8) (ξ = 0.9) (ξ = 0.8) (ξ = 0.9)
RMS position error (m) (entire trajectory avg) 143.8 143.2 142.7 174.4 175.8 175.1
Track loss (%) 0 0 0 0 0 0
(d) Trajectory 4
P F A = 10−4 P F A = 2 × 10−3
(ξ = 0.8) (ξ = 0.9) (ξ = 0.8) (ξ = 0.9)
Track loss (%) 0.4 0.4 0.4 0.6 0.6 0.5
(e) Trajectory 5
P F A = 10−4 P F A = 2 × 10−3
(ξ = 0.8) (ξ = 0.9) (ξ = 0.8) (ξ = 0.9)
Track loss (%) 0.3 0.3 0.3 2.9 2.4 2.2
(f) Trajectory 6
8
Table 1 (continued)
P F A = 10−4 P F A = 2 × 10−3
IMMPDAF MDetPH(ξ = 0.8) MDetPH(ξ = 0.9) IMMPDAF MDetPH(ξ = 0.8) MDetPH(ξ = 0.9)
Track loss (%) 0.8 0.9 0.9 3.8 4.1 3.9
(g) Trajectory 7
verability with longer periods of uniform motion. It can be 5. Conclusion

explained by the direct propagation of term p [xk | H k,lmax , Z k ]
in (11), which is well suited to target dynamics in non- A new algorithm for tracking a maneuvering target in the pres-
maneuvering phases. Moreover, this result demonstrates that ence of clutter has been presented in this work. The proposed
the hypothesis test to detect maneuvering motion worked MDetPH algorithm effectively approximates the instantaneous pos-
properly, improving the overall MDetPH performance. terior distribution of target state by a Gaussian mixture with few
• MDetPH algorithm yielded larger estimation errors during ma- components. This is achieved by using a hypothesis reduction
neuvers, mainly for a low value of P F A and for highly ma- strategy based on Bayesian decision to determine the mixture com-
ponents to be propagated to the next iteration. Simulation-based
neuvering targets (trajs. 5 and 6 @P F A = 10−4 ). Peak errors of
results of performance investigation using a radar model with large
MDetPH tracking reached amplitudes nearly 50% higher than
target revisit period demonstrated that the MDetPH algorithm ex-
IMMPDAF’s for some of these scenarios.
hibits significantly superior performance compared to IMMPDAF
• If we consider the average position error evaluated for the en-
during non-maneuvering periods, but tends to produce larger peak
tire trajectories (first row of Tables 1(a)-(g)), the performance errors when maneuvers arise. However, it was observed that this
of MDetPH is significantly better than IMMPDAF for low ma- behavior has non-noticeable impact on track loss rate and our pro-
neuvering targets (traj. 7), practically the same when there are posal showed in general better results regarding the overall error
medium-intensity maneuvers (trajs. 2, 3 and 4), and slightly performance, taking into consideration several types of trajectories.
worse only for a high maneuvering target in a scenario of low Additionally, it was verified that our proposal presented robustness
clutter (trajs. 5 and 6 @ P F A = 10−4 ). to changes in the false alarm probability, and has average computa-
• Even though MDetPH algorithm is less robust to sudden tional cost around three times that of IMMPDAF in the considered
changes in target motion, this has no noticeable impact on scenarios of application.
track loss. Indeed, it can be observed from Tables 1(a)-(g) (last
row) that no matter the scenario, the algorithms presented CRediT authorship contribution statement
satisfactory and similar performances regarding this metric. In
addition, comparing the performance results considering solely Marcelo Lucena de Souza: Conceptualization, Formal analysis,
maneuvering periods (third row of the tables), one may see Software, Writing – original draft. Alberto Gaspar Guimarães: Con-
that MDetPH error is only 5 - 10% greater than that verified ceptualization, Formal analysis, Writing – original draft. Ernesto
for IMMPDAF, and for some (few) trajectories and false alarm Leite Pinto: Conceptualization, Formal analysis, Writing – original
probabilities, the error is even smaller. draft.
• In general MDetPH is more robust than IMMPDAF for clut-
Declaration of competing interest
tered scenarios. Comparing the position error results presented
in the tables for the two values of P F A , it can be observed
The authors declare that they have no known competing finan-
that the error increase for IMMPDAF is proportionally greater.
cial interests or personal relationships that could have appeared to
One of the consequences is that the difference between al-
influence the work reported in this paper.
gorithms performances under abrupt maneuver conditions is
significantly reduced with the increase of P F A , as can be seen
References
in trajectories 5 and 6.
• The difference in performance of the MDetPH algorithm with [1] Y. Bar-Shalom, P. Willet, X. Tian, Tracking and Data Fusion: A Handbook of
threshold values ξ = 0.8 or 0.9 is actually very small, leading Algorithms, YBS Publishing, 2011.
to the conclusion that the algorithm is not that sensitive to [2] T. Kirubarajan, Y. Bar-Shalom, W.D. Blair, G.A. Watson, IMMPDAF for radar man-
agement and tracking benchmark with ECM, IEEE Trans. Aerosp. Electron. Syst.
this parameter. 34 (4) (Oct 1998) 1115–1134.
[3] Y. Bar-Shalom, T. Kirubarajan, X. Lin, Probabilistic data association techniques
4.2.2. Computational load for target tracking with applications to sonar radar and EO sensors, IEEE Trans.
Aerosp. Electron. Syst. 20 (2005) 37–56.
To evaluate the computational cost of each algorithm the num-
[4] C. Ting, H. Zishu, L. Yaxing, Adaptive-update-rate tracking based on modified
ber of floating point operations performed at each iteration was IMM-PDA, in: Proceedings of the 2011 IEEE CIE International Conference on
recorded. Since this index depends on the amount of validated Radar, 2011.
measurements, different iterations may require different numbers [5] N. Amrouche, A. Khenchaf, D. Berkani, Detection and tracking targets under
low SNR, in: 2017 IEEE International Conference on Industrial Technology, ICIT,
of operations. The averaged results presented in Table 1 are nor- March 2017, pp. 992–996.
malized in relation to the results obtained for IMMPDAF. It was [6] S.A. Memon, T.L. Song, K.H. Memon, I. Ullah, U. Khan, Modified smoothing data
observed that on average, independently of the considered trajec- association for target tracking in clutter, Elsevier Expert Syst. Appl. 141 (2020).
[7] S. Blackman, R. Popoli, Design and Analysis of Modern Tracking Systems, Artech
tory, the computational cost of MDetPH is around 2.2 times that
House Radar Library, Artech House, 1999.
of IMMPDAF when P F A = 10−4 , and around 3 to 4 times when [8] Y. Bar-Shalom, F. Daum, J. Huang, The probabilistic data association filter, IEEE
P F A = 2 × 10−3 . Control Syst. Mag. 29 (6) (Dec 2009) 82–100.
9
[9] R. Esmzad, R. Mahboobi Esfanjani, Modified likelihood probabilistic data asso- [30] J.D. Glass, W.D. Blair, Y. Bar-Shalom, Optimizing radar signal to noise ratio for
ciation filter for tracking systems with delayed and lost measurements, Digit. tracking maneuvering targets, in: 2014 17th International Conference on Infor-
Signal Process. 76 (2018) 66–74. mation Fusion, FUSION, July 2014, pp. 1–7.
[10] S. Blackman, Multiple hypothesis tracking for multiple target tracking, IEEE [31] B. Vondra, Overview of the multisensor IMMPDA filter with an amplitude fea-
Trans. Aerosp. Electron. Syst. 19 (1) (Jan 2004) 5–18. ture for tracking maneuvering target in cluttered environment, in: Proceedings
[11] Y. Bar-Shalom, K. Birmiwal, Variable dimension filter for maneuvering target of the 2013 International Conference on Applied Electromagnetics and Com-
tracking, IEEE Trans. Aerosp. Electron. Syst. AES-18 (5) (1982) 621–629. munications, ICECom, 2013.
[12] P. Bogler, Tracking a maneuvering target using input estimation, IEEE Trans. [32] R. Manish, D. Kim, An improved maneuvering target tracking using state de-
Aerosp. Electron. Syst. AES-23 (3) (1987) 298–310. pendent adaptive estimation with probabilistic data association, in: Proceed-
[13] X. Li Rong, V. Jilkov, Survey of maneuvering target tracking. Part V. Multiple- ings of the 2019 AIAA Scitech 2019 Forum, 2019.
model methods, IEEE Trans. Aerosp. Electron. Syst. 41 (4) (2005) 1255–1321. [33] X. Li, V. Jilkov, Survey of maneuvering target tracking. Part V. Multiple-model
[14] H. Blom, Y. Bar-Shalom, The interacting multiple model algorithm for sys- methods, IEEE Trans. Aerosp. Electron. Syst. 41 (4) (2005) 1255–1321.
tems with Markovian switching coefficients, IEEE Trans. Autom. Control 33 (8) [34] B. Mahafza, Radar Systems Analysis and Design Using MATLAB, third edition,
(1988) 780–783. Taylor & Francis, 2013.
[15] L. Gao, J. Xing, Z. Ma, J. Sha, X. Meng, Improved IMM algorithm for nonlinear [35] W.D. Blair, G.A. Watson, T. Kirubarajan, Y. Bar-Shalom, Benchmark for radar
maneuvering target tracking, Aerosp. Sci. Technol. 2 (2012) 4117–4123. allocation and tracking in ECM, IEEE Trans. Aerosp. Electron. Syst. 34 (4) (Oct
[16] W. Zhu, W. Wang, G. Yuan, An improved interacting multiple model filtering 1998) 1097–1114.
algorithm based on the cubature Kalman filter for maneuvering target tracking, [36] Y. Bar-Shalom, X. Li, T. Kirubarajan, Estimation with Applications to Tracking
Sensors 17 (6) (2016). and Navigation: Theory, Algorithms and Software, Wiley-Interscience Publica-
[17] B. Han, H. Huang, L. Lei, C. Huang, Z. Zhang, An improved IMM algorithm based tion, Wiley, 2001.
on STSRCKF for maneuvering target tracking, IEEE Access 7 (2019) 795–57 804.
[18] D. Zheng, S. Wang, A new interacting multiple model algorithm for maneu-
vering target tracking based on adaptive transition probability updating, in: Marcelo Lucena de Souza received in 2009 the degree in computer en-
Proceedings of the 2015 IET International Radar Conference, 2015. gineering from the Federal University of Pernambuco (UFPE), Brazil, and
[19] S. Zhang, Y. Guo, Z. Lu, S. Wang, Z. Liu, Cooperative detection based on the the MSc degree in electrical engineering from the Military Institute of En-
adaptive interacting multiple model-information filtering algorithm, Aerosp.
gineering (IME), Brazil, in 2016. From 2009 until 2018 he worked as a
Sci. Technol. 93 (2019).
System Engineer at the Brazilian Air Force. Since 2018 he joined Frequentis
[20] M. Eltoukhy, M.O. Ahmad, M.N.S. Swamy, An adaptive turn rate estimation for
tracking a maneuvering target, IEEE Access 8 (2020) 94176–94189.
Comsoft GmbH, Germany, where he works as a Software Engineer devel-
[21] W. Ali, Y. Li, M.A.Z. Raja, N. Ahmed, Generalized pseudo Bayesian algorithms oping tracking systems for Air Traffic Management (ATM) solutions. His
for tracking of multiple model underwater maneuvering target, Elsevier Appl. research interests include target tracking, data fusion and statistical signal
Acoust. 166 (2020). processing.
[22] P.S. Maybeck, M.C. Kozak, B.D. Smith, Mixed-model multiple-hypothesis track-
ing of targets in clutter, IEEE Trans. Aerosp. Electron. Syst. 44 (4) (2008)
Alberto Gaspar Guimarães received the DSc degree from Pontifical
1402–1415.
[23] H.L. Kennedy, Mixture reduction techniques and probabilistic intensity models
Catholic University of Rio de Janeiro (PUC-Rio), Brazil, in 2004, and spent
for multiple hypothesis tracking of targets in clutter, Comput. Electr. Eng. 40 (3) a post-doctoral period in TELECOM SudParis, France, in 2006-2007. He is
(2014) 884–896. currently an Assistant Professor at the Department of Telecommunications
[24] W. Wu, H. Sun, Y. Cai, S. Jiang, J. Xiong, Tracking multiple maneuvering targets Engineering at Fluminense Federal University, Brazil. His research inter-
hidden in the DBZ based on the MM-GLMB filter, IEEE Trans. Signal Process. 68 ests are in statistical signal processing, particularly in estimation methods
(2020) 2912–2924. for Hidden Markov chain models (HMM), including Monte Carlo methods,
[25] B. Ristic, B.-T. Vo, B.-N. Vo, A. Farina, A tutorial on Bernoulli filters: theory, with applications to communications, radiolocation, and target tracking.
implementation and applications, IEEE Trans. Signal Process. 61 (13) (2013)
3406–3430.
[26] W. Yi, M. Jiang, R. Hoseinnezhad, The multiple model Vo–Vo filter, IEEE Trans. Ernesto Leite Pinto earned the electrical engineer degree from the Fed-
Aerosp. Electron. Syst. 53 (2) (2017) 1045–1054. eral University of Paraiba (UFPB), Brazil, in 1983. He received the MSc and
[27] M. Lucena, A. Guimaraes, E. Pinto, Highly maneuverable target tracking based DSc degrees in communication systems from the Pontifical Catholic Uni-
on efficient propagation of model hypotheses, in: Proceedings of the 2014 IEEE versity of Rio de Janeiro, Brazil, in 1986 and 1998, respectively. He is a
Radar Conference, May 2014, pp. 255–259. Professor at the Military Institute of Engineering (IME), in Brazil, where
[28] R.R. Pitre, V.P. Jilkov, X.R. Li, A comparative study of multiple-model algorithms
he has been working since 1987. His main research interests include per-
for maneuvering target tracking, in: Proceedings of the 2005 SPIE Conference
formance evaluation of digital transmission systems and advanced modu-
Signal Processing, Sensor Fusion, and Target Recognition XIV, vol. 5809, 2005,
pp. 549–560 [Online]. Available: https://doi.org/10.1117/12.609681.
lation techniques for doubly-selective channels, as well as statistical signal
[29] X. Li, Y. Bar-Shalom, Multiple-model estimation with variable structure, IEEE processing and target tracking. Dr. Pinto is a senior member of the Brazil-
Trans. Autom. Control 41 (4) (1996) 478–493. ian Telecommunications Society (SBrT).
10

3 - Artigo Ernesto

Uploaded by

Copyright:

Available Formats

3 - Artigo Ernesto

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

3 - Artigo Ernesto

Uploaded by

Copyright:

Available Formats

Digital Signal Processing 126 (2022) 103481

Contents lists available at ScienceDirect

Digital Signal Processing

A novel algorithm for tracking a maneuvering target in clutter

1. Introduction the Gaussian mixture representing possible association events at a

where V k is the validation region volume, P G is the probability p [xk | Z k ]

posterior probability evaluation along the time, which is important

3.3. Bayesian hypothesis test

The operation rule of the hypothesis test here proposed to de-

where H0 is the hypothesis that the ﬂight dynamics follows the

It is worthy to notice that by proper choice of threshold ξ

3.4. MDetPH algorithm in details

3.4.5. Model-measurement hypothesis conditioned ﬁltering

Fig. 2. RMS position error for trajectories 1 to 3.

Fig. 3. RMS position error for trajectories 4 to 7.

4.2.1. Performance evaluation • During non-maneuvering phases MDetPH algorithm presented

verability with longer periods of uniform motion. It can be 5. Conclusion

You might also like