Algorithms for Multiple-Target Tracking

Author(s): Jeffrey K. Uhlmann

Source: American Scientist , March-April 1992, Vol. 80, No. 2 (March-April 1992), pp.
128-141
Published by: Sigma Xi, The Scientific Research Honor Society

Stable URL: [Link]

JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide
range of content in a trusted digital archive. We use information technology and tools to increase productivity and
facilitate new forms of scholarship. For more information about JSTOR, please contact support@[Link].

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at
[Link]

is collaborating with JSTOR to digitize, preserve and extend access to American Scientist

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
 Algorithms for Multiple-Target Tracking
Tracking many moving objects at once is a task whose difficulty grows out of all
proportion to the number of objects. A new method works for thousands of targets

Jeffrey K. Uhlmann

safe separation between the hundreds Over the years there have been
When aruns
major-league
down a long flyoutfielder
ball, the of aircraft that might be operating near many attempts to devise an algorithm
tracking of a moving object looks easy a busy airport. In particle physics, mul? for multiple-target tracking with better
Over a distance of a few hundred feet, tiple-target tracking is needed to make than n2 performance. Some of the pro?
the fielder calculates the ball's trajec? sense of the hundreds or thousands of posals offered significant improve?
tory to within an inch or two, and particle tracks emanating from the site ments in special circumstances or for
times its fall to within milliseconds. of a high-energy collision. There is a certain instances of the multiple-target
But what if an outfielder were asked to similar requirement in studies of tracking problem, but they retained
track 100 fly balls at once? As it turns molecular dynamics. their n2 worst-case behavior. Now my
out, even 100 fielders trying to track The task of following a large num? colleagues and I at the Naval Research
100 balls simultaneously would likely ber of targets turns out to be surpris? Laboratory in Washington have devel?
find the task an impossible challenge. ingly hard. If tracking a single baseball oped a new class of algorithms for the
Problems of this kind do not arise in or warhead or aircraft requires a cer? crucial step of associating reports with
baseball, but they have considerable tain measurable level of effort, then it tracks; if a set of objects can be tracked
practical importance in other realms. might seem that tracking 10 similar ob? at all, these algorithms can be guaran?
The impetus for the studies described jects would require at most 10 times as teed to do it in less than n2 steps. Prac?
in this article was the Strategic Defense much effort. Actually, for the most ob? tical applications are under way. Even
Initiative, the plan conceived a decade vious methods of solving the problem, with the new methods, multiple-target
ago for defending the U.S. against a the difficulty is proportional to the tracking remains a complex task,
large-scale nuclear attack. According to square of the number of objects; thus which strains the capacity of the larg?
the terms of the original proposal, an 10 objects demand 100 times the effort, est and fastest supercomputers, but
SDI system would be required to track and 10,000 objects increase the difficul? important problem instances are now
tens or even hundreds of thousands of ty by a factor of 100 million. This com? within reach.
objects, including missiles, warheads, binatorial explosion is the crux of the
decoys and debris, all of them moving multiple-target-tracking problem. Keeping Track
at speeds of up to eight kilometers per Consider how you might go about The modern need for tracking algo?
second. Another application of multi? following the motion of a single object. rithms began with the development of
ple-target tracking is to air-traffic con? You receive a series of position reports radar during World War II. By the
trol, where the goal is to maintain a from a sensor of some kind, such as a 1950s radar was a relatively mature
radar system. To reconstruct the ob? technology. Systems were installed
Jeffrey K. Uhlmann is at the Naval Research Labora?
ject's trajectory, you plot the successive aboard military ships and aircraft, and
tory in Washington. He performed both his under? positions in sequence and then draw a at airports. The tracking of radar tar?
graduate and his graduate work at the University of line through them. Extending this line gets, however, was still done by manu?
Missouri-Columbia, where his areas of emphasis in? yields a prediction of the object's fu? ally drawing lines through blips on a
cluded philosophy, computer science and discrete ture position. Now suppose you are display screen. The first attempts to au?
mathematics. His present research interest is in the tracking 10 targets simultaneously. At tomate the tracking process were mod?
area of multidimensional search and correlation. intervals you receive 10 new position eled closely on human performance.
Since 1987 he has collaborated with other investiga? reports?but the reports do not come For the single-target case the resulting
tors at NRL on applications of computationally effi?
with labels that would tell you which algorithm was straightforward: The
cient data structures to problems in multiple-target
targets they represent. On the contrary, computer accumulated a series of posi?
tracking. In addition to journal publications, this
work has resulted in five patents and patents pend?
when you plot the 10 new positions, tions from radar reports, and estimated
ing. His hobbies include writing for film and televi? each report could in principle be asso? the velocity of the target in order to
sion, and music composition. A sample of his musi? ciated with any of the 10 existing tra? predict its future position.
cal work will be released in September on Rockit jectories. It is this need to consider ev? Even single-target tracking present?
Records. Address: Code 5570, Naval Research Labo? ery possible combination of reports ed certain challenges connected with
ratory, Washington, DC 20375-5000. Electronic and tracks that makes the difficulty of the uncertainty inherent in all position
mail: uhlmann@[Link]. an rc-target problem proportional to n2. measurements. A first problem is de

128 American Scientist, Volume 80

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
ciding how to represent this uncertain? A second difficulty in handling un? Such a method would eventually ex?
ty. A crude approach is to define an er? certainty is determining how to inter? ceed all constraints on computation
ror radius surrounding the position es? polate the actual trajectory of the target time and storage space.
timate. This practice implies that the from multiple measurements, each A near-optimal method for a large
with its own error allowance. If the tar? class of tracking problems was devel?
probability of finding the target is uni?
formly distributed throughout the vol? get is known to have constant velocity oped in 1960 by R. E. Kaiman, now of
ume of a three-dimensional sphere. (that is, if it travels in a straight line at the University of Florida at Gainesville.
Unfortunately this simple approach is constant speed), there are methods for His approach, called Kaiman filtering,
far from optimal. The error region as? calculating the straight-line path that can be applied whenever the motion of
sociated with many sensors is highly best fits, by some measure, the series of a target can be assumed to be linear
nonspherical; radar, for example, tends past positions. A desirable property of during the interval between successive
to provide accurate range information this approach is that it should always reports. The Kaiman filter avoids the
but has poorer radial resolution. Fur? converge on the correct path: As the need to preserve past reports. It main?
thermore, one would expect the actual number of reports increases, the differ? tains only an estimate of the current
ence between the estimated velocity state of the object, consisting of the esti?
position of the target to be closer on av?
erage to the mean position estimate and the actual velocity should ap? mated position at the time of the most
than to the perimeter of the error vol? proach zero. On the other hand, it is recent report, estimates of kinematic
ume, which suggests in turn that the impractical to retain all past reports of quantities such as velocity and acceler?
probability density should be greater a target and recalculate the entire tra? ation, and a measure of uncertainty
near the center. jectory every time a new report arrives. for each estimated quantity. Kaiman

Figure 1. Strategic Defense Initiative, the proposed system for repelling a large-scale intercontinental missile attack, was the impetus for extensive
investigation of the automated tracking of multiple targets. Shown here is a simulation of an SDI command center, where the defense against an
attack would be coordinated. The individual consoles and the large displays behind them can show various kinds of information, including the
tracks of incoming missiles. The plotting of these tracks and the identification of targets cannot be left to the human operators, however, because
the system might have to cope with tens of thousands of warheads, decoys and other objects within a period of minutes. Devising algorithms for
tracking vast numbers of targets has turned out to be a surprisingly difficult part of the SDI program. The simulated control center is at the Army
Strategic Defense Command Advanced Research Center in Huntsville, Alabama. (Photograph courtesy of Teledyne Brown Engineering.)

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
 showed that if a few basic conditions
are satisfied, the state estimate can be
updated with each incoming report in
such a way that the calculated trajec?
tory of the target converges to the actu?
al trajectory.
A particularly important feature of
the Kaiman filter is its use of a Gaus?
sian probability distribution to model
uncertainty. The Gaussian distribution
has a single point of maximum proba?
bility, called its mean; moving away
from the mean, probability diminishes
exponentially (although it never falls to
zero). Thus the distribution can be
imagined as a cloud, densest at the cen?
ter and wispy at the edges. A graph of
the probability density along any axis
passing through the mean is a symmet?
rical bell curve. But the bell curves
along different axes can have different
widths, so that the cloud does not have
to be spherical. The cloud is described
as an error ellipse (or ellipsoid in three
dimensions) because contours of equal
probability form an ellipse or ellipsoid.
Hence a sensor report is simply a mean
position with an associated error el?
lipse, and the projection of a track to a
new position can also be represented
by a mean point and an ellipse.
Kalman's work revolutionized the
field of target tracking. By the mid
1960s, Kaiman filtering was a standard
methodology. It is just as central to
multiple-target tracking as it is to sin?
gle-target tracking.
Figure 2. Correlation problem is at the heart of
what makes multiple-target tracking a difficult
task. The information available for plotting a
track consists of position reports (shown here
as colored dots) from a sensor such as a radar
system. In tracking a single target (left), one
can accumulate a series of reports and then fit
a line or curve to these data points in order to
estimate the object's trajectory. With multiple
targets (right) there is no obvious way to
determine which object has generated which
report. Here five reports appear initially, at
t = 1; then five more reports are received at
t = 2. But it is not immediately apparent to the
eye which of the later dots goes with which of
the earlier ones, and a computer program
would find the correlation task just as
difficult (In fact, there need not be a correla?
tion; the five reports at t = 2 could represent
five new targets.) As further reports arrive,
coherent tracks do begin to emerge. The tracks
from which these reports were derived are
shown in the final panels, at t = 5. Here and in
subsequent illustrations all targets move in a
straight line at uniform speed and are
confined to two dimensions; the more realistic
task of following curved paths in three
dimensional space is appreciably more
difficult

130 American Scientist, Volume 80

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
Nearest Neighbors
What multiple targets add to the track? new position
ing problem is the need to assign each
incoming position report to a specific
target track. The earliest mechanism
for classifying reports was the nearest
neighbor rule. The idea of the rule is to
estimate each object's position at the
time of a new position report, and then
assign the report to the nearest such es?
timate. This intuitively plausible ap?
proach is especially attractive because
it decomposes the multiple-target
tracking problem into a set of single
target problems.
Kalman's formulation provided the
foundation for a statistically meaning?
ful version of the nearest-neighbor
rule. Specifically, from Kalman's theo? Figure 3. Uncertainty in position reports and in estimates of a target's trajectory add to the
rems one can derive an equation that difficulty of the correlation problem in multiple-target tracking. No sensor provides an
gives the probability that a report at absolutely accurate or reliable measure of target motion; there is always some uncertainty in
position and velocity. The uncertainty can be represented by a Gaussian distribution, which falls
time t and a track projected to time t
off smoothly with distance from the mean position. The amplitude of the Gaussian distribution
are associated with the same object. at any point?indicated here by darkness of shading?gives the probability of finding the target
Accordingly, the nearest-neighbor rule at that point The distribution is often nonsymmetrical, since sensors may have better resolution
can be redefined to state that a report in some directions than in others; hence the positional uncertainty is often described in terms of
should be assigned to the track with an error ellipse (or, in three dimensions, an error ellipsoid). The extent of overlap between error
which it has the highest probability of ellipses determines the likelihood that a track and a position report are correlated.
association. In this way a multiple-tar?
get problem can still be decomposed
into a set of single-target problems.
The nearest-neighbor rule has strong
intuitive appeal, but doubts and diffi?
culties connected with it soon began to
emerge. For example, early imple
menters of the method discovered
problems in creating initial tracks for
multiple targets. In the case of a single
target, two reports can be accumulated
to derive a velocity estimate, from which
a track can be created. For multiple tar?
gets, however, there is no obvious way
to deduce such initial velocities. The
first two reports received could repre?
sent successive positions of a single ob?
ject or the initial detection of two dis?
tinct objects. Every subsequent report
could be the continuation of a known
track or the start of a new one. To make
matters worse, almost every sensor pro?
duces at least occasional spurious re?
ports, which give rise to spurious
tracks. Thus the tracking system needs
an additional mechanism to recognize
and delete tracks that are never as?
signed reports with a high probability
of association.
Another difficulty with the nearest
Figure 4. Nearest-neighbor rule is perhaps the simplest approach to the correlation problem.
neighbor rule becomes apparent when When a new position report arrives, all existing tracks are projected forward to the time of the
reports are misclassified, as will in? new measurement. (In this diagram, earlier target positions are indicated by colored dots and
evitably happen from time to time if the projected positions by colored circles; the new position report is a black dot.) Then the
the tracked objects are close together. A distance from the report to each projected position is calculated, and the report is associated
misassignment can cause the Kalman with the nearest track. In the situation shown, the report would be assigned to track 1. The
filtering process to converge very slow? main drawback of this scheme is that if the assignment is erroneous, subsequent analysis is
ly, or it may even fail to converge alto severely disrupted.

1992 March-April 131

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
 Track Splitting
A robust Solution to the problem of as?
signment ambiguities is to create mul?
tiple "hypothesis tracks." Under this
scheme, the tracking system does not
have to commit itself immediately or
irrevocably to a single assignment of
Ap08tD0n .
each report. If a report is highly corre?
lated with more than one track, an up?
dated copy of each track can be creat?
ed; subsequent reports can be used to
determine which assignment is correct.
? , ? :-vv r:-,^: .? '. -.7.-; ? i_.---.-c 7 ?: -,. As more reports come in, the track as?
;: "" Vv- 'V: ?'^?'?.A:?..^s..i^s.;v ? - sociated with the correct assignment
will rapidly converge on the true target
trajectory, whereas the falsely updated
tracks are unlikely to be correlated
with any subsequent reports.
This basic technique is called track
? * X^ ?' hyp(rt?)e8laB

.^^^^ ^^^^
splitting. One of its worrisome conse?
quences is a proliferation in the num?
ber of tracks mat a program must keep
tabs on. The proliferation can be con?
trolled with the same track-deletion
mechanism used in the nearest-neigh?
bor algorithm, which scans through all
the tracks from time to time and elimi?
nates those that have a low probability
of association with recent reports. A
more sophisticated approach to track
splitting, called multiple-hypothesis
tracking, maintains a history of track
branchings, so that as soon as one
branch is confirmed, the alternative
branches can be pruned away.
Track sphtting in its various forms is
widely regarded as the best strategy
for handling the ambiguities inherent
in correlating tracks with reports from
multiple targets. It is even used to min?
imize the effects of spurious reports
when tracking a single target. Never?
theless, some serious difficulties re?
main. First, track splitting does not
completely decompose a multiple-tar?
get tracking problem into independent
single-target problems, in the way the
nearest-neighbor strategy was intend?
ed to do. For example, two hypothesis
tracks may lock onto the trajectory of
a single object. Since both tracks are
valid, the standard track-deletion mech?
Figure 5. Multiple-hypothesis tracking is a more sophisticated scheme for following target tracks anism cannot eliminate either of them;
in the presence of measurement uncertainty. The idea is that whenever a report (black dot) could
plausibly be associated with two tracks, both candidate tracks are retained by the system. The
the deletion procedure has to be modi?
two hypotheses are re-evaluated when another position report arrives. In the case shown here the
fied to detect redundant tracks, and so
second report favors hypothesis B, which is therefore confirmed. A program implementing the it cannot look at just one track at a time.
multiple-hypothesis algorithm requires a mechanism for identifying and deleting hypotheses This coupling between multiple tracks
that fail to be supported by subsequent measurements, such as hypothesis A. is theoretically troubling, but experi?
ence has shown that it can be managed
gether?in which case the track cannot may therefore be mistaken as spurious in practice at low computational cost.
be predicted. Moreover, tracks updat? by the track-deletion mechanism. Mis? A second problem is the difficulty of
ed with misassigned reports (or not takenly deleted tracks then necessitate deciding when a position report and a
updated at all) will tend to correlate subsequent track initiations and a pos? projected track are correlated closely
poorly with subsequent reports and sible repetition of the process. enough to justify creating a new hy
132 American Scientist, Volume 80

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
pothesis track. If the correlation thresh? kilometers per second, it is probably elaborate gating techniques, every re?
old is set too high, correct assignments safe to assume that a track and report port still must be compared with every
may be missed so often as to prevent more than 50 kilometers apart are not track. If there are n reports and n tracks,
convergence of the Kaiman filter. If the correlated. (A larger distance may be re? then n2 comparisons are required to de?
threshold is too low, the number of hy? quired to take into account the uncer? termine which pairs are correlated. Sim?
potheses may grow exponentially. The tainty measures associated with both ple gating can reduce the average cost
usual practice is to set the threshold the tracks and the reports.) of each comparison, but what is really
low enough to ensure convergence, Gating algorithms are successful in needed is a method to reduce the sheer
and then add another mechanism to reducing the numerical overhead of number of comparisons. Some structure
limit the rate of hypothesis generation. the correlation process and in increas? must be imposed on the set of tracks
A simple strategy is to select the n hy? ing the number of targets that can be that will allow correlated track-report
pothesis candidates with the highest tracked in real time. Unfortunately, the pairs to be identified without having to
probabilities of association, where n is benefits of simple gating diminish as compare every report with every track.
the maximum number of hypotheses the number of targets increases. Specif? A corollary is that the long history of at?
that computational resource constraints ically, implementers of gating algo? tempts to maintain tracks of multiple
will allow. This "greedy" method usual? rithms have found that increasing the targets as if they were independent
ly yields good performance. number of targets by a factor of 20 in? tracking problems must be abandoned.
Even with these enhancements, the creases the computational burden by a The new correlation problem is diffi?
tracking algorithm makes such prodig? factor of 100. Moreover, it turns out cult conceptually because it demands
ious demands on computing resources that the largest percentage of computa? that most pairs of tracks and reports be
that large problems remain beyond tion time is still spent in the correlation excluded from consideration without
practical reach. Monitoring the compu? process, although now the bulk of the ever examining them. At the same
tation to see how much time is spent in demand is for simple distance calcula? time, no track-report pair whose prob?
various subtasks shows that calculat? tions within the gating algorithm. ability of association exceeds the cor?
ing probabilities of association is by far Clearly the expense of the correlation relation threshold can be disregard?
the biggest expense. The program gets process involves more than numerical ed. For some time, these constraints
bogged down projecting target tracks overhead; there is a combinatorial as? seemed impossible to satisfy simulta?
to the time of a position report, calcu? pect as well. neously. Often, the latter constraint
lating error ellipses, and then looking A cursory examination of the corre? was relaxed to say that few track-report
for intersections of the ellipses. Since lation process reveals that even with pairs whose probability of association
this is the critical section of the algo?
rithm, further effort has focused on im?
proving performance here.

Gating
The various geometric calculations in?
volved in estimating a probability of
association are numerically intensive
and inherently time-consuming. Thus
one approach to speeding up the track?
ing procedure is to streamline or fine
tune these calculations?to encode
them more efficiently without chang?
ing their fundamental nature. This is
what computer scientists generally
have in mind when they speak of "op?
timizing" a program. Careful optimiz?
ing can be important, but in this case it
is not enough. It is necessary to actual?
ly reduce the number of calculations
being performed.
An appealing approach to reducing
the number of probability calculations
is to do a preliminary screening of
tracks and position reports; only if a
track-report pair passes a computation?
ally inexpensive feasibility check is
Figure 6. Combinatorial bottleneck afflicts all of the most straightforward algorithms for
there any need to complete the full
multiple-target tracking. In these algorithms every incoming position report must be compared
probability calculation. This process is with every candidate track, in order to see whether or not they might be associated. Here there
called gating. Several geometric tests are 10 reports (black dots) and 10 tracks (colored circles, representing new projected positions); thus
could serve as gating criteria. For exam? 100 comparisons are needed. More generally, the effort that must be expended to solve a
ple, if on average each track is updated correlation problem for n tracks and n reports is proportional to n2. For large values of n, these n2
every five seconds, and the targets are steps are the dominant factor in determining the performance and the maximum capacity of a
known to have a maximum speed of 10 tracking program.

1992 March-April 133

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
 heavily on the distributio
gets. A common approach
fy clusters of targets that
ly separated that reports
in one cluster will never h
cant probability of asso
tracks from another cluste
the correlation process t
from which cluster a par
.. s':; could have originated
compare the report only
in that cluster. The probl
approach is that the numbe
ly separated clusters dep
distribution of the targets
cannot be controlled by t
algorithm. If n tracks ar
into n clusters, each consis
gle track, or into a single
tracks, the method stil
computational cost equi
comparison of every rep
track. Unfortunately,
Figure 7. Clustering methods attempt to avoid the n2 bottleneck by grouping tracks mo i
clusters. Then an incoming report can be compared only tracking problems
with the tracks in the tend
neares
Such methods work well only if the data fall readily into onewell-separated
of these extremes.
clusters. If th
are evenly dispersed, they may form either n clusters of one track each or one giant c
A correlation strategy
n tracks; in either case, the algorithm reverts to the original n2 performance.
some of the distribution
sociated with clustering i
o the space in which the t
into grid cells. Each track
assigned to a cell acco
mean projected position
the tracks that might
with a given report can
examining only those t
within close proximity t
cell. The problem with
is that its performance d
ily on the size of the grid
as on the distribution of t
the grid cells are large an
are densely distributed i
gion, every track will
nearby cell. Conversely
cells are small, the algo
spend as much time exa
(most of which may b
would be required to sim
each track. In a three-d
grid, there are 26 cells
adjacent to each cell. If
extended to a radius of t
Figure 8. Grid algorithms offer another mechanism for confining
number of attention
cells that to tracks
mu
immediate neighborhood of a position report. All space is divided into a grid of cell
ined on each query rises t
report is compared only with the tracks in its own grid cell and in neighboring cell
tracks are eligible for association with a report if they lie within a radius of two gri
with clustering methods, the distribution of tracks can Binary Search
confound a grid strategy. If
The deficiencies
tracks are in a single cell, or if all the cells must be examined toof be
gridsure
methods
ofsug?
assigning
to the correct track, the algorithm bogs down. gest the need for a more flexible data
structure. The main requirement im?
exceeds the threshold of
could be mistak?or failed to adequately
comparisons posed on the data stmcture has already
enly disregarded. This limit the number
seemingly rea? of been
missed
mentioned:correla?
It must allow all prox?
sonable compromise, however, led to
tions. Some approaches imatewere suscepti?
track-report pairs to be identified
numerous ad hoc schemesble tothat
both either
[Link] having to compare every report
failed to adequately limit
Mostthe
ofnumber
the ad hoc strategies
with every track (unless,
depend of course, ev

134 American Scientist, Volume 80

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
ery track is within the prescribed prox? are given a sorted list of n numbers (when q is the last number or else is
imity to every report). and asked to find out whether or not a not present at all), the search requires n
A clue to how this trick might be ac? specific number, q, is included in the comparisons. There is a much better
complished comes from one of the list. The most obvious search method way. Because the list is sorted, if you
best-known algorithms in computer is simply to compare q with each num? find that q is greater than a particular
science: binary search. Suppose you ber in sequence; in the worst case element of the list, you can exclude

Figure 9. Multidimensional search tree divides space in a way that allows a correlation problem to be solved in fewer than n2 steps for any
reasonable distribution of tracks. Shown here is a method of building the data structure required for such a search; Figures 10 and 11 illustrate
actual search procedures. The first step is to identify the track whose x coordinate is the median value of all the x coordinates; in this case there
are 25 tracks, and so the median track is the 13th one counting from the left. A vertical line is drawn through the median track, partitioning the
space into left and right rectangles. In step 2 the same procedure is applied in each of the left and right rectangles, except that now each
subspace is divided horizontally through the track with the median value of the y coordinate. In step 3 the resulting rectangles are further
subdivided, using a vertical partition through the track with the median x coordinate in each rectangle. The procedure continues in this way,
alternating x and y coordinates, until the subspaces are empty. For the 25 tracks, five iterations are needed. In three dimensions, the algorithm
would cycle repetitively through x, y and z coordinates.

1992 March-April 135

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
from further consideration not only which point the procedure terminates specified range of values, (mm, max).
that element but all those that precede and reports that q is not present in the Specifically, the above procedure can be
it in the list. This principle is applied list. applied to find the position in the list of
optimally in binary search. The algo? The efficiency of this process can be the largest element less than min and
rithm is recursive: First compare q to analyzed as follows. At every step, half the position of the smallest element
the median value in the list of numbers of the remaining elements in the list are greater than max. The elements between
(by definition, the median will be eliminated from consideration. Thus the these two positions then represent the
found in the middle of a sorted list). If total number of comparisons is equal to desired set. Finding the positions associ?
q is equal to the median value, then the number of halvings, which in turn is ated with min and max requires log2 n
stop, and report that the search was equal to the base-two logarithm of n. In comparisons. Assuming that some op?
successful. If q is greater than the medi? the standard notation of computer sci? eration will be carried out on each of the
an value, then apply the same proce? ence, the performance of the algorithm k elements of the solution set, the over?
dure recursively to the sublist greater is said to scale as 0(log2 n). If n is a mil? all scaling law for satisfying a range
than the median; otherwise apply it to lion, for example, only 20 comparisons query is 0(log2 n + k).
the sublist less than the median. Even? are needed to determine if a given num? Applying this principle to the corre?
tually either q will be found?it will be ber is in the list. lation problem in multiple-target track?
equal to the median of some sublist? Binary search can also be used to find ing is very appealing. After all, the task
or a sublist will turn out to be empty, at all elements of the list that are within a of a gating algorithm can be seen as
finding the subset of a list of n tracks
step 1: qx< x step 2: qy > y
i n n CT i n m
that lie within some plausible range of
a new position report, which is directly
analogous to searching a list for a
range of numbers. If the gating could
-rh-U -
- T \ f } -I
be done with only log2 n + k compar?

i-rr J- ~i???ir^-^^
isons rather than n comparisons, the
benefits would be appreciable. The
trouble is, tracks of moving targets can?
not be sorted into a simple one-dimen?
sional list; they exist in a three-dimen?

-I?o- 0 -I?o- 0 ^^^^H

sional space. A three-dimensional range
query must identify all the points in a
data set whose x coordinate is in the

?I?o? ?o?'? ?I-?~ range (xmin, Xmax), whose y coordinate is

in the range (ymin, x/max) and whose z co?

step 3: <7x>* step 4: qy-y_ ordinate is in the range (zmin, Zmax)>

In 1975 Jon Louis Bentley, now of
AT&T Bell Laboratories, devised a sim?
ple but clever extension of the binary
search method to solve the general
multidimensional range-query prob?
lem. To see how Bentley's method
works, imagine a set of tracks repre?
sented by points distributed through?
out a three-dimensional volume. The
first step is to list the x coordinates of
the points and choose the median val?
ue; then partition the volume by draw?
ing a plane perpendicular to the x axis
through this point. The result is to cre?
ate two subvolumes, one containing all
the points whose x coordinates are less
Figure 10. Searching for a specific track in the subdivided space proceeds through a than the median and the other contain?
progressive
narrowing of focus. The question to be answered by the search is whether a point q, with ing the points whose x coordinates are
coordinates qx and qy/ is present in the set of tracks recorded in the data structure. Thegreater
search than the median. The same
begins by examining the highest-level partition (step 1) and comparing qx with the x coordinate of
procedure is then applied recursively
the partition (which is, of course, the median x coordinate, designated here x). If qx and x are
to the two subvolumes, except that
equal, the search ends, since q has been found: It is the track that lies along the partition. If qx is
now the partitioning planes are drawn
greater than x, the subspace to the right of the partition is examined next, and the left subspace is
perpendicular
excluded from further consideration; if qx is less than x (as is the case here), attention turns instead to the y axis, and they
pass through points that have median
to the left subspace. Next (step 2) qy is compared with the median y value in the remaining
values
subspace, and a similar decision is made: Either the median value is returned as the result of a of the y coordinate. The next
successful search or else one of the subspaces is eliminated. The next bisection (step 3) round uses
is based on the z coordinate, and then
the value of qx again; finally in step 4 qy is found to be equal to y, and the circled pointthe
is procedure returns cyclically to the
identified as the subject of the search. With this procedure the number of steps needed x to
coordinate.
find The recursion continues
one of n points is no greater than log2 n; for the 25 points shown, at most five steps areuntil
needed.
the subvolumes are empty.

136 American Scientist, Volume 80

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
 Searching Bentley's subdivided vol? step1:xm/n> x xmax>x step2^w^^n||^^^
ume for the presence of a specific
point, with given x, y and z coordi? ? I?o? <J> ^? y
nates, is a straightforward extension of
standard binary search. As in the one
dimensional case, the search proceeds
??rM^r ^^^?-^A
as a series of comparisons with median
values, but now attention alternates
among the three coordinates. First the
x coordinates are compared, then the y,
then the z, and so on. At the end either
the chosen point will be found lying on
one of the median planes, or else the
??? I ^^^^^^^^H
procedure will come to an empty sub
volume. ?I?0? ?o?I? ^?o?'?
Searching for all the points that fall
within a specified interval is somewhat
more complicated. The search pro?
ceeds as follows: If Xmin is less than the
median-value x coordinate, then the
left subvolume must be examined. If
Xmax is greater than the median value of
x, the right subvolume must be exam?
ined. Since the median could well lie
between Xmin and Xmax, it is possible that
neither subvolume is eliminated from
consideration; this possibility does not
come up in the one-dimensional
search. At the next level of recursion,
the comparison is done using ymm and
ymax, then Zmin and Zmax. ^?o?'? ^?o?I?
A detailed analysis of the algorithm
reveals that for d dimensions (provid?
ed that d is greater than 1), the number
of comparisons performed during the
search can be as high as 0(n1_1/d + fc);
thus in three dimensions the perfor?
mance is proportional to 0(n2^3 + k). In
the task of matching n reports with n
tracks, the range query must be repeat?
ed n times, and so the performance is
given by 0(n x n1^ + k), or 0(n5/3 + k).
This scaling is better than quadratic
but not nearly as good as the logarith?
mic scaling observed in the one-di?
mensional case, which works out, for n
range queries, to 0(n log2 n + k). The
reason for the penalty in searching a
Figure 11. Searching for all points that lie within a range of coord
multidimensional tree is the possibility complicated and less efficient than searching for a single specified
at each step that both subtrees will search is to find all the tracks within a rectangle bounded by the coor
have to be searched. In practice, how? ymax. Step 1 compares xmiw and xmax with x, the median value of x; it
ever, this seldom happens, and the Xtnax are greater than x, and so the left subspace is eliminated. Sim
worst-case scaling for Bentley's tech? subspace is excluded. In step 3, however, xmin and xmax are found t
nique is rarely seen. A variety of en? subspace can be neglected in further search operations. The left a
hancements have been devised over step 3 are examined separately in steps 4a and 4b; after yet another
the years that further improve its aver? (not shown), the area defined by the range query is exhibited in step
kind can be used in multiple-target tracking to find all the tracks th
age-case behavior. (Other data struc?
of a specified position report.
tures have been developed that can
satisfy multidimensional range queries
in 0(log2d n) time. But due to their high other is
ing Bentley's search strategy nodes.
with In
a a binary tree
can include
data structure called a binary an aitem of data as w
tree,
computational overhead, these data
structures are of more theoretical inter? structure made up of nodes
actlylinked by
two pointers, which speci
est than practical value.) and right
"pointers," which are computer children of the no
memo?
The most natural way of implement root
ry addresses specifying the of the tree
location of is a node whos

1992 March-April

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
ment is the point with the median value gorithm, is a recursive one: Each of the Multidimensional Trees in Gating
of the x coordinate; the left pointer of subtrees also has a root node whose data In the late 1980s, my colleagues and I at
this root node leads to a subtree made element is a median value and whose the Naval Research Laboratory began
up of nodes representing all the points left and right pointers designate sub? studying ways of applying advances in
with x coordinates less than the median; trees where all the values are either less computer science to various problems
similarly the right pointer designates the than or greater than the median. At the in tracking and correlation. Experi?
subtree in which all points have x coor? "leaves" of the tree are empty nodes, ments with multidimensional tree
dinates greater than the median. The signaling that no further subdivision of structures produced our most encour?
data structure, like the corresponding al the space is needed or possible. aging results. Unlike methods based on

stepi_ step 2

Figure 12. Allowing for uncertainty in both tracks and

tree, which at each level divides space into three areas
occupy a rectangular area. Step 1 identifies the object
lie entirely to the left of this object, points that lie entir
In step 2 each of these three regions is subdivided in tu
values of the y coordinate. Another level of vertical div
additional horizontal trisections of step 4.

138 American Scientist, Volume 80

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
 clustering or grids, the performance of antee that every track correlated with a An error ellipse is calculated for each
techniques based on tree structures is given report will be found; however, a track and each report, and then a box is
relatively independent of the distribu? few tracks with large error ellipses can constructed around each ellipse. Now
tion of the targets. In particular, the result in such large query regions that the boxes representing the track pro?
computation time required for a given an intolerable number of uncorrelated jections are organized into a multi?
range query depends more on the num? tracks will also be identified. dimensional ternary tree. Each box rep?
ber of points that satisfy the query than The solution we ultimately found resenting a report becomes the subject
on the extent of the range. was to devise a new multidimensional of a complete tree search; the result of
In these experiments we stored a set tree structure that can represent uncer? the search is the set of all track boxes
of projected track positions as points in tainty in the stored data. The new form that intersect the given report box.
a multidimensional tree structure. Then of tree still cannot accommodate error Track-report pairs whose boxes do not
for each position report we defined a ellipses, but it allows for error boxes, and intersect are excluded from all further
gating range, and searched the tree for that has turned out to be an acceptable consideration. Next the set of track-re?
all track points that fell within the range. approximation. A box is defined as the port pairs whose boxes do overlap is ex?
As noted above, each such search re? smallest cuboidal shape, with sides amined more closely to see whether the
quires at most ri2-/3 + k operations, and in parallel to the coordinate axes, that can inscribed error ellipses also overlap.
many instances the actual performance entirely surround the error ellipse. Since Whenever this calculation indicates a
is appreciably better. After this gating the axes of the ellipse may not corre? correlation, the track is extended to the
pass, a full-scale calculation of the prob?
spond to those of the coordinate system, position of the new report. Tracks that
ability of association is needed only for
the box may differ significantly in size consistently fail to be associated with
the k track-report pairs that pass the and shape from the ellipse it encloses. any reports are eventually deleted; re?
range test. With these methods we were The new data structure is needed in ports that cannot be associated with
able to simulate the correlation process order to allow searches in which one any existing track initiate new tracks.
with more than a million targets. range of coordinate values is compared
The problem with this scheme is that with another range, rather than the The Strategic Defense Initiative
it cannot readily account for uncertain? simpler case where a range is com? The birth of SDI in 1983 established the
ty in the track projections, because ob? pared with a single point. A binary tree most challenging and focused set of
jects in the tree structure are treated as will not serve this purpose because it is engineering and scientific funding pri?
points. Uncertainty in the position re? not always possible to say whether one orities since the space program of two
ports is accommodated by the use of a interval is greater than or less than an? decades before. The goal was to develop
range query; that is, the gating range other; the intervals may well be inter? a space-based system to defend against
can be adjusted to encompass the en? secting and yet not identical. What is a full-scale missile attack against the
tire error ellipse associated with a posi? needed is a ternary tree, with three de? United States. Some of the most critical
tion report. Indeed, even the shape of scendants per node. At each stage in a problems were the design and deploy?
the report's error ellipse can be taken search of the tree, the maximum value ment of sensors to detect the launch of
into account, since the range query can of one interval is compared with the missiles at the earliest moment possi?
be performed with different x, y and z minimum of the other, and vice versa. ble in their 20-minute flight, and the
ranges. But ignoring the error in the These comparisons can potentially design and deployment of weapons
track projections is unacceptable; it eliminate either the left subtree or the systems capable of destroying the de?
could lead to missed correlations and a right subtree, but whatever their out? tected missiles. Although an automatic
failure of the tracking algorithm to come, it will be necessary to examine tracking facility would clearly be an in?
converge. the middle subtree?the one made up tegral component of any SDI system, it
One approach to solving this prob? of nodes representing boxes that might was not generally considered a "high
lem is to shift all the uncertainty associ? intersect the query interval. In three di? risk" technology. Tracking, especially
ated with the tracks onto the reports. mensions, the extra search effort de? of aircraft, had been widely studied
The nature of this transfer is easy to manded by the added subtrees is usu? for more than 30 years, and so the track?
understand in the simple case of a ally not great unless there are many ing of noiuTianeuvering ballistic missiles
track and a report whose error ellip? intersections among the boxes stored seemed to be a relatively simple engi?
soids are spherical and just touching. in the tree. Although more sophisticat? neering exercise. The principal constraint
Reducing the radius of the track error ed tree variants provide better worst imposed by SDI was that the tracking be
sphere to zero while increasing the ra? case scaling, the simplicity of ternary precise enough to predict a missile's fu?
dius of the report error sphere by an trees tends to translate into relatively ture position to within a few meters, so
equal amount leaves the enlarged re? low computational overhead and com? that it could be destroyed by a high-en?
port sphere just touching the point rep? petitive performance in practice. ergy laser or a particle-beam weapon.
resenting the track, so that the correla? At this point it is possible to summa? The high-precision tracking require?
tion is preserved. Unfortunately, when rize our entire tracking algorithm. ment led to the development of highly
this idea is applied to multiple tracks Tracks are recorded by storing the in? detailed models of ballistic motion that
and reports, the query region for every formation?such as current positions, took into account the effects of atmo?
report must be enlarged in all direc? velocities and accelerations?that a spheric drag and various gravitational
tions by an amount large enough to ac? Kaiman filter needs to estimate the fu? perturbations over the earth. By far the
commodate the largest error ellipse as? ture position of each candidate target. most significant source of error in the
sociated with any track. Techniques When a new batch of position reports tracking process, however, resulted
have been devised to find the mini? arrives, the existing tracks are project? from the limited resolution of existing
mum enlargement necessary to guar ed forward to the time of the reports. sensors. This fact reinforced the widely

1992 March-April 139

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
 r

Figure 13. Intersection of error boxes offers a preliminary indication that a track and a report are probably correlated. A definitive test of correlation
requires a computation to determine the extent to which the error ellipses overlap, but this computation is a time-consuming one. Furthermore,
there is no convenient way to store ellipses in a multidimensional search tree. A useful alternative strategy is to draw a box drcumscribing each
ellipse; if the sides of the boxes are parallel to the coordinate axes, the boxes are readily stored in a search tree. If two boxes do not intersect (left), it
is safe to assume that the inscribed ellipses do not intersect either. When the boxes do overlap, in most instances the ellipses also touch (center).
There are a few cases where the boxes overlap but the ellipses do not (right); these false positives must be weeded out in subsequent processing.

held belief that the main obstacle to ef? In response to a heightened interest way; reports would arrive in a continu?
fective tracking was the poor quality of in scaling issues, the Naval Research ing stream and would be distributed
sensor reports. The impact of large Laboratory developed prototype sys? over time. In order to determine the
numbers of targets seemed manage? tems based on efficient search struc? probability that a given track and re?
able: One had only to build larger, tures. One of these systems demon? port correspond to the same object, the
faster computers. Although many in strated that 65 to 100 missiles could be track must be projected to the mea?
the research community thought other? tracked in real time with a program surement time of the report. If every
wise, the prevailing attitude among running on a personal workstation. track has to be projected to the mea?
funding agencies was that if 100 ob? These results were based on the as? surement time of every report, the
jects could be tracked in real time, then sumption that a good-resolution radar combinatorial advantages of the tree
it should be little trouble to build a ma? report would be received every five search algorithm will be lost.
chine 100 times faster?or simply have seconds for every missile, which is un? A simple way to avoid multiple pro?
100 machines run in parallel?to han? realistic in the context of SDI; neverthe? jections for each track is to increase the
dle 10,000 objects. less, the demonstration did provide search radius in the gating algorithm
Among the challenges facing the convincing evidence that SDI trackers to account for the maximum distance
SDI program, multiple-target tracking could be adapted to avoid quadratic an object could travel during the maxi?
seemed far simpler than what would scaling. A tracker developed for the mum time difference between any
be required to further improve sensor SDI National Testbed in Colorado track and report. For example, if the
resolution. This belief led to the award? Springs achieved significant perfor? maximum speed of a missile is 10 kilo?
ing of contracts to build tracking sys? mance improvements after a tree meters per second, and the maximum
tems in which the emphasis was based search structure was installed in time difference between any report
placed on high precision at any cost in its correlation routine; the new algo? and track is five seconds, then 50 kilo?
terms of computational efficiency. rithm was superior for as few as 40 meters would have to be added to each
These systems did prove valuable for missiles. Stand-alone tests showed that search radius to assure that no correla?
determining bounds on how accurate? the search component could process tions are missed. For boxes used to ap?
ly a single cluster of three to seven mis? 5,000 to 10,000 range queries in real proximate ellipsoids, this means that
siles could be tracked in an SDI envi? time on a modest computer worksta? each side of the box must be increased
ronment, but ultimately pressures tion. These results suggested that the by 100 kilometers.
mounted to scale up to more realistic problem of correlating vast numbers of As estimates of what constitutes a
numbers. In one case, a tracker that tracks and reports had been solved. realistic SDI scenario became more ac?
had been tested on five missiles was Unfortunately, a new difficulty was curate, members of the tracking com?
scaled up to track 100, causing the pro? soon discovered. munity learned that successive re?
cessing time to increase from a couple Up to now I have adopted the sim? ports of a particular target often
of hours to almost a month of nonstop plifying assumption that all position would be separated by as much as 30
computation for a simulated 20-minute reports arrive in batches, with all the to 40 seconds. To account for time dif?
scenario. It was later determined that reports in a batch reflecting measure? ferences this large would require box?
the bulk of the computations took ments made at the same instant. A real es so immense that the number of
place in the correlation step. sensor system would not work this spurious returns would negate the
140 American Scientist, Volume 80

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]
benefits of efficient search. Demands
for a sensor configuration that would
report on every target at intervals of 5
to 10 seconds were considered unrea?
sonable for a variety of practical rea?
sons. It seemed that the use of sophis?
ticated correlation algorithms had
finally reached its limit. Several
heuristic "fixes" were considered, but
none solved the problem.
A detailed scaling analysis of the
problem ultimately pointed the way to
a solution: Simply accumulate sensor
reports until the difference between the
measurement time of the current re?
port and the earliest report exceeds a
threshold. A search structure is then
constructed from this set of reports; the ^ v*^ :;' '?-.?v ? .trod, Bflpiffiiii^ ?'? 0, jj
tracks are projected to the mean time of
the reports; and the correlation process
is performed with the maximum time
difference being no more than half of
the chosen time-difference threshold.
The subtle aspect of this deceptively
simple approach is the selection of the ^- ? - ;>v^ v^^^>;i:v-->;^^i::. \ ? ? i ?r- i t
threshold. If it is too small, every track
will be projected to the measurement
time of every report. If it is too large, ev? Figure 14. Performance of tree-based association algorithms is clearly superior to that of
ery report will fall within the search vol? methods that have n2 efficiency. Even for as few as 1,000 targets, the tree-based algorithm has a
ume of every track. A formula has been considerable advantage: Execution time on a personal workstation is less than three seconds for
the tree-based search, and almost eight minutes for a brute-force search. For 128,000 targets, the
derived that, with only modest assump?
tree-based program takes a little more than 10 minutes, whereas the execution time of the brute
tions about the distribution of targets,
force algorithm has grown to 12 weeks. In the test data that generated these results, the density
assures the optimal trade-off between of targets was such that five error boxes, on average, would intersect. (Not all of the tests plotted
these two extremes. Empirical results were actually run; some data were extrapolated or estimated.)
confirm that the approach essentially
solves the time-difference problem.
plicable only to a very restricted class Bibliography
Conclusion of tracking problems. Other problems, Bar-Shalom, Y, and T. E. Fortmann. 1988. Tracking
and Data Association. San Diego: Academic Press.
The correlation of reports with tracks such as the tracking of military forces,
demand more sophisticated approach? Bentley, J. L. 1975. Multidimensional binary trees
numbering in the thousands can now
for associative searching. Communications of
be performed in real time on many es. Not only does the mean position of the ACM 18:509-517.
currently available computers. More a military force change, but so also Blackman, Samuel S. 1986. Multiple-Target Track?
research on large-scale correlation re? does its shape. Moreover, reports of its ing with Radar Applications. Dedham, Mass.:
mains to be done, but work has al? position are really only reports of the Artech House.
ready begun on implementing efficient positions of its parts, and various parts Uhlmann, Jeffrey K., and Miguel R. Zuniga.
correlation modules that can be incor? may be moving in different directions 1991. Results of an efficient gating algorithm
for large-scale tracking scenarios. Naval Re?
porated into existing tracking systems. at any given instant. Filtering out the search Reviews 1:24-29.
Ironically, by hiding the intricate de? local deviations in motion to determine
Collins, Joseph B., and Jeffrey K. Uhlmann. 1990.
tails and complexities of the correlation the net motion of the whole is beyond Efficient gating in data association for multivari
process, these modules give the ap? the capabilities of a simple Kaiman fil? ate Gaussian distributions. Accepted by IEEE
pearance that multiple-target tracking ter. Other difficult tracking problems Transactions on Aerospace and Electronic Systems.
involves little more than the concur? include the tracking of weather phe? Uhlmann, Jeffrey K. 1991. Adaptive partitioning
nomena and soil erosion. The history strategies for ternary tree structures. Pattern
rent processing of several single-target
Recognition Letters 12:537-541.
problems. Thus a paradigm with deep of multiple-target tracking suggests
Zuniga, Miguel R., J. M. Picone and Jeffrey K.
historical roots in the field of target that, in addition to new mathematical
Uhlmann. 1990. Efficient algorithm for im?
tracking is at least partially preserved. techniques, new algorithmic techniques proved gating combinatorics in multiple-tar?
It should be noted that the tech? will certainly be required for any practi? get tracking. Submitted to IEEE Transactions
niques described in this article are ap cal solution to these problems. on Aerospace and Electronic Systems.

1992 March-April 141

This content downloaded from

[Link] on Tue, 07 Feb 2023 14:10:45 UTC
All use subject to [Link]