Survey Paper
Tracking Methods in
a
Multitarget Environment
YAAKOV
BAR-SHALOM,
MEMBER,
IEEE
Abstmet-The objective
of
this
paper
is
to
survey and
put
in
perspeetme
the
existing
methods
of
tracking
in
multitarget
environment.
In
such
an
environment
tbe
origin
of
the
measurements
can
be
uncertain:
they could
have come from the
target@)
of
interest
or
dutter
or
false
alm
or
be
due
to
the
background.
Tbis
compact
and
unified
presentation
of
the
state-
of-art
in
multitarget
traddng
WBS
motivated by the reeent
surge
of
interest
in
this
problem.
It
is
also
hoped
to
be
useful in view
of
the
need
to
adapt
and
madify
existing
techniques
before
using
them
for
specific
problems.
Particular
attention
is
paid
to
the
Bssumptiom
nnderiying
eacb
algorithm
and
its
applicability
to various
situ-
I.
INTRODUCTION
I
T
WAS
recognized as far back as 1964
[26]
that in
tracking targets there can be an uncertainty associated
with the measurements in addition to their inaccuracy,
which is usually modeled by some additive noise. This
additional uncertainty is related to the origm of the
measurements: a measurement, which
is
to be used in the
tracking algorithm, might not have originated from the
target of interest. This situation can occur in a surveil-
lance system when a sensor such as a radar, sonar, or
optical one
is
operating in an environment in which there
is clutter, or the false-alann rate is high. It can also
happen when several targets are in the same neighborhood
and one cannot associate with certainty the observed
detections, (assumed to have been resolved) which yield
the measurements, with the various targets.
A
similar
situation can occur in the track formation problem when
there are several targets but their number is not
known
and some
of
the measurements might be spurious. The
application of standard estimation algorithms which
would use the measurement nearest
in
some sense to the
predicted measurement (“nearest neighbor filter”) can
lead to very poor results in an environment where spuri-
ous measurements occur frequently. This is because such
an algorithm does not account for the fact that the
Manuscript received April 25,
1977;
revised March
9,
1978.
Paper
fecomended
by
R.
Monopo!,,
Past
Chairman
of
the Adaptive,
Learn-
mg
Systems, Pattern
Recogmbon
Committee.
This
research
was
sup
ported
in
part
by
NSF
Grant
ENG
77-08177.
The author
is
with
the
University
of
Connecticut,
Storrs,
CT
06268.
measurement used in the filter might have originated from
a source different from the target of interest.
Recently, with the proliferation of surveillance systems
and their increased sophistication, there has been a great
deal
of
interest in the multitarget tracking problem.
Several algorithms that have been published in the litera-
ture point to the current activity
in
this area. The purpose
of
this paper is to survey and put
in
perspective the recent
work on multitarget tracking and present
in
more detail
the most important algorithms. The (subjective) criterion
of
what is important is based upon what is believed to be
of
general interest and potential usefulness for application
to real problems. Particular attention is given to the
assumptions underlying the various algorithms and to
what problems they can be applied to.
The pioneering work
of
Sittler
[26]
was motivated by
the need to find a reasonable way of incorporating
measurements of uncertain origm into existing tracks. The
estimation algorithm he considered was of the type used
before the Kalman filter became popular. The method
consisted
of
splitting the track whenever more than one
return (detection) was observed in the neighborhood of
the predicted measurement. Then the likelihood function
of each trajectory was computed and those whose likeli-
hood was below a threshold were dropped.
Similar
ap-
proaches were developed within the framework of
Kal-
man filtering
by
Fraser and Meier
[IO]
for active sonar
tracking and
by
Smith and Buechler
[27]
for
radar track-
ing.
This
track split or branching algorithm, described
in
Section
11,
is suitable both for track initiation or track
update but its computational and memory requirements
can become very large in dense environments.
A
method particularly suitable for track formation for
several targets in the same neighborhood was developed
by Morefield [18].
This
method, discussed in Section
111,
is also based upon likelihood functions and converts the
association of measurements to form tracks into
an
in-
teger programming problem.
Both of the above methods are essentially non-Baye-
sian: they make decisions to accept or reject trajectories
and then estimate the state conditioned upon the correct-
0018-9286/78/0800-0618$00.75
01978
IEEE