Skip to main content

Full text of "DTIC ADA534187: Efficient Multiple Hypothesis Tracking by Track Segment Graph"

See other formats


12th International Conference on Information Fusion 
Seattle, WA, USA, July 6-9, 2009 


Efficient Multiple Hypothesis Tracking by 
Track Segment Graph* 


Chee-Yee Chong, Greg Castanon, Nathan Cooprider 
Shozo Mori, Ravi Ravichandran 

BAE Systems 
Burlington, MA, USA 

{chee.chong, greg.castanon, nathan.cooprider, shozo.mori 
balasubramaniam.ravichandran}@baesystems.com 


Robert Macior 

Air Force Research Lab 
RIEA 

Rome, NY, USA 
robert.macior@us.af.mil 


Abstract - Multiple hypothesis tracking (MHT) ad¬ 
dresses difficult tracking problems by maintaining alter¬ 
native association hypotheses until enough good data, 
e.g., features, are collected to select the correct hypothe¬ 
ses. Traditional MHT’s cannot track targets over long 
durations because they frequently generate too many 
hypotheses to maintain the correct ones with the avail¬ 
able processing resources. Track segment graph provides 
a compact and efficient representation of the key ambi¬ 
guities in long term tracking. It is used to generate the 
long term track hypotheses that are evaluated to select 
the best long term global hypothesis. Simulation examples 
demonstrate the efficiency and optimality of the ap¬ 
proach. 

Keywords: Multiple hypothesis tracking, track segment 
graph, long term tracking, feature aided tracking. 

1 Introduction 

Tracking targets over a long period of time is difficult due 
to possible sensing gaps, high target densities, etc. The 
standard approach for addressing such difficult tracking 
problems is multiple hypothesis tracking (MHT) [1, 2]. In 
MHT, association decisions are deferred when there is not 
enough information to make a good decision. Instead, 
multiple association hypotheses are maintained over mul¬ 
tiple frames of data until enough good data are collected. 

There are two main approaches to MHT. The hy¬ 
pothesis-oriented approach, first introduced in [3] and 
generalized in [4, 5], recursively finds a set of (global) 
association hypotheses and their probabilities. On the 
other hand, the track-oriented approach [6-10] is based on 
finding the best multi-dimensional or multi-frame data 
association hypothesis by {0,1} integer programming [6], 
Lagrangian relaxation [9], or other techniques. An exten- 


Approved for public release. The work reported in this 
paper was supported by the Air Force Research Lab. under 
contract FA8750-08-C-0034. However, the information 
provided does not represent the official position of the Air 
Force or the U.S. Government. 


sion of the track-oriented approach to find the K-best 
hypotheses can be found in [11]. 

In order to avoid the combinatorial explosion of 
hypotheses, all MHT’s use hypothesis management tech¬ 
niques to reduce the number of hypotheses. In particular, 
the tracks or track hypotheses in the track-oriented ap¬ 
proach are pruned after a certain window or frame size is 
reached. The result is that outside the pmning window, 
only the tracks in the best association hypothesis are re¬ 
tained as confirmed tracks, and alternative track hypothe¬ 
ses may no longer be available when good data are col¬ 
lected. 

Features can help long term track maintenance by 
moving the association problem into a higher dimensional 
space where there may be enough separation for better 
performance [12, 13]. Maintaining hypotheses for long 
durations is especially critical in feature aided tracking 
because feature data are not always available due to sen¬ 
sor coverage and the resources needed to observe or proc¬ 
ess them. Thus, it is important for a MHT algorithm to 
maintain enough hypotheses until feature reports are col¬ 
lected. 

This paper presents a new multiple hypothesis track¬ 
ing approach that uses an efficient representation of alter¬ 
native long term track hypotheses by a track segment 
graph. This representation is based on three ideas. The 
first is using track segments instead of reports as the basic 
building blocks of track hypotheses. The second is repre¬ 
senting ambiguous track segments of multiple targets in 
addition to pure track segments of single targets. The third 
is using a graph to represent and store possible associa¬ 
tions between track segments instead of generating and 
storing all possible track hypotheses. 

The track segment graph will be used to generate the 
relevant long term track hypotheses only when needed. 
These track hypotheses are scored using the track segment 
association likelihoods. From these track likelihoods, the 
best or K-best (global) association hypotheses are se¬ 
lected. The benefit is a significant reduction in the number 
of track hypotheses so that the alternative hypotheses can 
be maintained for long durations. 

The rest of this paper is structured as follows. Sec¬ 
tion 2 summarizes the basic elements of multiple hypothe- 


978-0-9824438-0-4 ©2009 ISIF 


2177 



Report Documentation Page 


Form Approved 
OMB No. 0704-0188 


Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and 
maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, 
including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington 
VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it 
does not display a currently valid OMB control number. 


1. REPORT DATE 

JUL 2009 


2. REPORT TYPE 


4. TITLE AND SUBTITLE 

Efficient Multiple Hypothesis Tracking by Tracking by Track Segment 
Graph 


6. AUTHOR(S) 


7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 

BAE Systems,,,Burlington,MA 

9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS (ES) 


3. DATES COVERED 

06-07-2009 to 09-07-2009 

5a. CONTRACT NUMBER 

5b. GRANT NUMBER 

5c. PROGRAM ELEMENT NUMBER 

5d. PROJECT NUMBER 

5e. TASK NUMBER 

5f. WORK UNIT NUMBER 

8. PERFORMING ORGANIZATION 
REPORT NUMBER 


10. SPONSOR/MONITOR’S ACRONYM(S) 

11. SPONSOR/MONITOR’S REPORT 
NUMBER(S) 


12. DISTRIBUTION/AVAILABILITY STATEMENT 

Approved for public release; distribution unlimited 

13. SUPPLEMENTARY NOTES 

See also ADM002299. Presented at the International Conference on Information Fusion (12th) (Fusion 
2009). Held in Seattle, Washington, on 6-9 July 2009. U.S. Government or Federal Rights License. 

14. ABSTRACT 

Multiple hypothesis tracking (MHT) addresses difficult tracking problems by maintaining alternative 
association hypotheses until enough good data e.g., features, are collected to select the correct hypotheses. 
Traditional MHT?s cannot track targets over long durations because they frequently generate too many 
hypotheses to maintain the correct ones with the available processing resources. Track segment graph 
provides a compact and efficient representation of the key ambiguities in long term tracking. It is used to 
generate the long term track hypotheses that are evaluated to select the best long term global hypothesis. 
Simulation examples demonstrate the efficiency and optimality of the approach. 


15. SUBJECT TERMS 


16. SECURITY CLASSIFICATION OF: 


a. REPORT 

unclassified 


b. ABSTRACT 

unclassified 


c. THIS PAGE 

unclassified 


17. LIMITATION OF 

18. NUMBER 

ABSTRACT 

OF PAGES 

Public Release 

8 


19a. NAME OF 
RESPONSIBLE PERSON 


Standard Form 298 (Rev. 8-98) 

Prescribed by ANSI Std Z39-18 






sis tracking. Section 3 introduces the track segment graph 
and discusses the formation of long term track hypotheses 
from the track segment graph. Section 4 presents the algo¬ 
rithm for scoring long term track hypotheses. Section 5 
describes an extended duration MHT system based upon 
the track segment graph approach. Section 6 presents 
simulation results to illustrate the approach, and Section 7 
contains the conclusions. 

2 Multiple hypothesis tracking 

The goal of multiple target tracking is to estimate the 
states of moving objects or targets from sensor reports. In 
general, sensor reports do not contain the identity of the 
targets and some may be false returns. Furthermore, tar¬ 
gets may not be observed as sensor reports when the prob¬ 
ability of detection is less than 1. Thus a crucial compo¬ 
nent of any multiple target tracking algorithm is the asso¬ 
ciation of reports to form possible target tracks. 

2.1 Hypotheses formation and selection 

Let y 1 ,y 2 ,..., be a sequence of frames (or scans), where 
each frame y k = (y k i,—,y kmk ) at t k is a set of measure¬ 
ments or reports y kj . Given a cumulative set of frames 

(y.)ti - (jT-'-jJT) j a track or track hypothesis on (y.)f =1 
is a function r from {1 ,...,£} to {0,1 ,...,m k } . If j > 0 , 
r(k) = j states that the y-th report in the k -th frame origi¬ 
nates from a target hypothesized by track r . If j - 0 , the 
target is not detected in the &-th frame. A data association 
hypothesis or global hypothesis X on (y )f =1 is a set of 
non-overlapping, non-empty tracks, i.e., track hypotheses 
in a global hypothesis do not share reports. 

Under fairly standard assumptions such as no split or 
merged reports, the posterior probability of each data 
association hypothesis X on (y. )* =1 is given by 



f 


( \ 

PO\{yy M ) = c- l \ 

Ilm 

II r FA ( k J) 


V tgA 

J 

J 


where C > 0 is a normalizing constant, L(r) is the likeli¬ 
hood of the track r , and y FA ( k , j) is the density of false 
alarms contained in the &-th frame evaluated at the value 
y kj of the y-th report. 

By taking the logarithm of (1), the maximization of 
the a posteriori probability P(X \ (y. )* =1 ) is transformed 
into the optimization problem. 

Minimize c T x 

subject to 16 {0,1}" (2) 

and Ax-b 


The vector c contains element c. ’s which are the loga¬ 
rithms of the likelihoods L{z .) for track r .. The con¬ 
straint Ax = b states that tracks in a single hypothesis 
cannot have the same reports. A is a mxn zero-one 
matrix, where m is the number of reports and n is the 
number of tracks plus slack variables for false alarms (the 
set of all the report y kj for which y FA (k,j) > 0). The 

element A ij =1 if the z-th report is included in the y-th 

track or is a false alarm. The vector b is m-dimensional 
with elements that are all l’s. A feasible solution 
ig{0,1}' 1 is a global hypothesis X such that x[j] = 1 if 
and only if the y-th track is included in hypothesis X . 

2.2 Hypothesis management 

In track-oriented MHT, tracks are expanded and 
propagated to recursively process each frame of data. 
However, data association hypotheses are not maintained 
or propagated explicitly, and only constructed from the 
tracks when needed. Thus, the hypothesis space consists 
of tracks on the past cumulative frames. Without hypothe¬ 
sis management, the number of track hypotheses will 
grow at an exponential rate with the number of frames. 

Therefore, track pruning is an essential part of any 
track-oriented MHT algorithm. The set of tracks and 
hypotheses defined on all past cumulative frames of data 
are naturally ordered by the predecessor-successor rela¬ 
tionships. In this partial ordering, the tracks and hypothe¬ 
ses form a tree structure. 

The basic hypothesis management technique in 
track-oriented MHT is N-scan pruning. Suppose hypothe¬ 
ses and tracks are formed on frames up to the frame K . 
Conventional A-scan pruning is based on selecting a sin¬ 
gle best hypothesis X and pruning all the tracks r that do 
not share the predecessor tracks at the ( K-N) - th frame 
with the tracks in the best hypothesis X . Equivalently, 
every hypothesis X formed on frames up to frame K are 
pruned away if the predecessor of X is not the predeces¬ 
sor of the best hypothesis X . Using this pruning strategy, 
any track initiated in frames between frames K-N + l 
and K are protected. However, only confirmed tracks are 
maintained outside the A-scan window. 

3 Track segment graph 

In the traditional track-oriented MHT with A-scan prun¬ 
ing, alternative track hypotheses are only maintained 
within the pruning window, and only confirmed tracks are 
retained outside of the window. Unless the window is 
very large, alternative hypotheses needed to exploit dis¬ 
ambiguating data such as features will be lost. The track 
segment approach addresses this problem by representing 
track hypotheses in terms of track segments so that the 
same A-scan corresponds to longer time duration. 


2178 



3.1 Track segments 

Figure 1 shows an example of three vehicles moving 
through two ambiguous regions (1 and 2) where their 
paths almost overlap, thus making data association diffi¬ 
cult. Measurements consist of initial video reports about 
vehicle color followed by GMTI measurements, and then 
video reports again at the end of the scenario. Because the 
GMTI measurements cannot be used to distinguish be¬ 
tween the tracks in the ambiguous regions, video reports 
are needed to associate the tracks correctly. More specifi¬ 
cally, alternative track hypotheses with features have to be 
maintained until the video reports are collected. This is 
difficult with standard MHT because many track hypothe¬ 
ses will be generated in the ambiguous regions. In fact, 
each possible association of measurement to track will 
generate a new track hypothesis. The result is that the 
correct track hypotheses may be pruned long before the 
feature reports are available. 



Figure 1: Three targets move through ambiguous regions 

A more efficient approach is to use track segments instead 
of reports as the basic building blocks of track hypothe¬ 
ses. The track segment graph is a directed graph where the 
nodes are track segments. There are two types of track 
segments. Pure track segments contain only reports from 
single targets while ambiguous track segments contain 
reports from multiple targets. Edges connect track seg¬ 
ments that can be associated. A directed edge connects 
two segments if the start time of the successor segment is 
larger than the end time of the predecessor segment and 
the two track segments can be associated. A directed path 
of the track segment graph corresponds to a long term 
track hypothesis. The track segment graph representation 
of the problem in Figure 1 is shown in Figures 2 and 3. 
The pure track segments are 1 to 7, and the ambiguous 
track segments are A1 and A2. 



Figure 2: Sensor reports are associated into pure and am¬ 
biguous track segments 



Figure 3: Track segment graph represents possible asso¬ 
ciations 

3.2 Track segment representation 

The representation of a pure or ambiguous track segment 
S t with measurements 7. contains the following informa¬ 
tion: start time f , end time t. , start time state estimate 
p(x. 17) = p{x{tl) \Y f ), end time state estimate 
p(x e i 17) = p{x{t e t ) 17), track segment likelihood 
L(S t ) = p{Y t ) , and state estimates at various sampling 
times in the track segment. 

All the estimates are conditioned on all measure¬ 
ments in the track segment. Thus the start time state esti¬ 
mate is a smoothed estimate while the end time estimate is 
a filtered estimate. Each state estimate has a kinematic and 
a feature component. The feature state estimate is usually 
given by a conditional probability distribution. For a pure 
track segment with a single target, a Kalman filter or 
smoother is used to generate the kinematic state estimate 
and its error covariance from the measurement reports 
associated with the track segment. For an impure track 
segment, we need to generate a state estimate for all the 
ambiguous targets using all the measurement reports. One 
approach is to merge the measurements at a single time 
into a single measurement and use it to update a group 
track with multiple targets. 

There are several ways of representing merged 
measurements. The simplest approach is to use one of the 
measurements as a surrogate for the merged measure¬ 
ments. This is very simple but may introduce some bias 
depending on the measurement selected. Alternatively, a 
convex combination of the probability distribution of the 
measurements retains all the information about the meas¬ 
urements. If each measurement has a Gaussian distribu¬ 
tion, then the merged measurement has a multi-modal 
distribution as a sum of Gaussians. This approach is not 
too practical because the number of modes in the track 
estimate grows with the number of updates with meas¬ 
urements. A more practical approach is to approximate 
the multi-modal distribution with a single Gaussian. This 
is similar to the approach used in probabilistic data asso¬ 
ciation (PDA) filters. 

Another way of representing the state of ambiguous 
track segments is by means of probability hypothesis 
density (PHD) [14]. Probability hypothesis density has 
been a very active area of research for the past few years 
because it solves the multi-target tracking problem with- 


2179 















out trying to associate the measurements to the individual 
targets. Instead of forming tracks for individual targets, 
PHD generates the a posteriori intensity measure density. 
It is not a probability density because its integral over the 
entire state space is not 1. Instead, the integral of the PHD 
over a region is the expected number of targets in the 
region. The benefit of PHD is that it may provide a more 
accurate state estimate for track segments than a single 
Gaussian. 


4.1 Long term track likelihoods 

For simplicity, we assume no false alarms. Consider a 
long term track (hypothesis) T with N track segments, 
S t , z = l,...,A, i.e., T = . The long term 

track likelihood is given by (see Appendix for derivation) 

L(T) = f[L(S t )flm,i-l) (3) 

i =1 i-2 


3.3 Formation of long term track hypothe¬ 
ses from track segment graph 

The track segment graph provides an efficient implicit 
representation for the long term track hypotheses. For the 
example in Figure 1, all the information needed to gener¬ 
ate the long term track hypotheses is contained in the 
track segment graph of Figure 3. In general, only a por¬ 
tion of the track segment graph is used when reports are 
received. For example, when feature reports are received, 
the track segment graph is searched backwards to look for 
track segment nodes with the relevant features. 

For the example of Figure 1, the relevant portion is 
the entire graph shown. Starting with the earliest nodes of 
the graph in Figure 3, the alternative long term track hy¬ 
potheses built from track segments are (1, Al, 5), (1, Al, 
4, A2, 6), (1, Al, 4, A2, 7), etc. In general, pure track 
segments are separated by ambiguous segments, but am¬ 
biguous track segments may be followed by other am¬ 
biguous track segments. In this case, eight long term track 
hypotheses are generated from the graph. 



T1 T2 T3 T4 T5 T6 T7 T8 


Figure 4: Long term track hypotheses are formed from 
track segments graph 

4 Hypothesis evaluation and selection 

After the long term track hypotheses are formed, their 
likelihoods are computed. Then the posterior probability 
of a global hypothesis can be evaluated from these long 
term track likelihoods. The best global hypothesis is 
found by solving an optimization problem to maximize 
the posterior probability. 


where L(S t ) is the likelihood of the track segment S f and 
L(i,i- 1) is the association likelihood between the track 
segment S i and the track S 1 ' 1 - . 

The track segment likelihood L(S t ) is p(Y ), the 
probability of the measurements in 7 . The track segment 
association likelihood is given by 




P«) 


-ClX; 


(4) 


where p(x* \ Y t ) is the smoothed estimate of the start state 
x s . given the track segment S t , and p(x s . 17 1 ,..,T_ 1 ) is the 
prediction of x(t s i ) given the measurements in the long 
term track S l ~ l . The integral of the product 

p(x* | Y j )p(x s i \Y l ,..Y i _ l ) evaluates the similarity between 
the smoothed estimate of the start state x* given the track 
segment S. and the predicted estimate of x. given the 
track segments S 1? ..,5 M . If x is a kinematic state for a 

maneuvering target, the predicted estimate depends 
mostly on the measurements in the most recent track seg¬ 
ment, i.e., p(x. | Y l9 .. 9 Y._^) -p(x. | FJ_j) . In this case, 
L(i,i- 1) depends only on the track segments S. and 
and measures the similarity between the start time state 
estimate of S i and the end time state estimate of S._j. 


4.2 Global hypothesis evaluation/selection 

Just as in traditional MHT, the posterior probability of a 
global (long term) hypothesis A is given by 

P(2\Y) = C-'l[L{T) (5) 

TeA 

where C is again a normalizing constant and L(T) is the 

long term track likelihood given by (3). As before, the 
optimization problem to select the best (global) hypothe¬ 
sis can be converted into the 0-1 integer programming 
problem (2). 

However, the constraint of the problem is different 
because while a report in traditional MHT can only be¬ 
long to one track hypothesis assuming no split reports 
from a target, an ambiguous track segment of two targets 
can belong to two track hypotheses in a single global 
hypothesis. This new constraint can be expressed by 


2180 













modifying the constraint vector b in (2), which is now 
allowed to have values besides 1. For a two-target am¬ 
biguous segment S t , the corresponding element in b is 
b i -2 . Similarly, for a three-target ambiguous track seg¬ 
ment, b i - 3. Thus, hypothesis selection with both pure 

and ambiguous track segments is a multi-assignment 
problem where a single track segment may be assigned to 
multiple long term track hypotheses. 

For the long term track hypotheses shown in Figure 
4, the matrices in the constraint equation are given by 
equation (6). Each of the pure (single target) track seg¬ 
ments 1 to 7 is constrained to belong to a single track in a 
global hypothesis but the impure (two target) track seg¬ 
ments can belong to two tracks. 


Tracks 


1 

2 

3 

4 

5 

6 

7 

8 



"1 

1 

1 

0 

0 

0 

0 

0" 

1 

"f 

0 

0 

0 

1 

1 

1 

0 

0 

2 

1 

1 

1 

1 

1 

1 

1 

0 

0 

A1 

2 

0 

0 

0 

0 

0 

0 

1 

1 

3 

1 

1 

1 

0 

1 

1 

0 

0 

0 

II 

1 

0 

0 

1 

0 

0 

1 

0 

0 

5 

1 

1 

1 

0 

1 

1 

0 

1 

1 

A2 

2 

1 

0 

0 

1 

0 

0 

1 

0 

6 

1 

_0 

1 

0 

0 

1 

0 

0 

1 

7 

_1_ 


5 Extended duration MHT 

The track segment graph representation is used to develop 
an extended duration MHT (EDMHT) system that can 
maintain hypotheses for long periods of time to incorpo¬ 
rate disambiguating data. 

5.1 Architecture 

Figure 5 shows the architecture of the EDMHT system 
based on the track-oriented MHT approach. It consists of 
a standard track-oriented MHT and an extended duration 
addition. The standard MHT performs the hypothesis 
generation and management operations. The extended 
duration addition converts the long term track hypotheses 
into the efficient track segment graph representation for 
storage until they are needed. It also retrieves the relevant 
track segments and generates long term track hypotheses 
for the MHT to process when feature or asynchronous 
reports are received. 

Measurements without feature information are proc¬ 
essed in the standard MHT (bottom portion of Figure 5) 
The Generate / Update Track Hypotheses function initi¬ 
ates new track hypotheses and propagates the states of the 
current (managed) track hypotheses to the time of the 
input measurements. It forms possible associations of the 


measurements to the tracks, resulting in a set of track 
hypotheses. The Manage Track Hypotheses function 
computes the likelihood of each track hypothesis and 
finds the best global hypothesis. For a fixed N-scan prun¬ 
ing window, the tracks in the best global hypothesis above 
the window are the confirmed tracks. The other tracks 
within the window that do not share the same predeces¬ 
sors with the tracks in the best global hypotheses are then 
pruned. Since multiple track hypotheses are not main¬ 
tained outside the pruning window, the standard MHT 
does not represent long term ambiguities. 



Figure 5: Extended duration MHT architecture consists of 
standard MHT and an extended duration addition 


The Generate Track Segment Graph function con¬ 
verts the confirmed (long term) portions of the track hy¬ 
potheses into a track segment graph that summarizes 
alternative associations of track segments. This graph 
allows alternative long term track hypotheses to be stored 
efficiently. Figures 3 and 4 show the (historical) long term 
track hypotheses and an equivalent track segment graph 
that contains the same information. Each branch of the 
tree is a historical track hypothesis and corresponds to one 
path over the graph. 

Note that the extended duration addition is a separate 
process that runs in parallel with the standard MHT to 
store the long term ambiguity information in an efficient 
track segment graph. This ambiguity information is used 
to process feature or asynchronous (out of sequence) 
reports when they are received. 

When feature reports are received, the track segment 
graph is searched for relevant parts of the graph that con¬ 
tains track segments with that feature. For the example of 
Figure 1, these can be the last times that feature reports 
are available. Generate / Update Track Hypotheses then 
forms the long term track hypotheses, each with a current 
portion from measurements in the pruning window and 
historical portion from track segments (Figure 6). 


2181 


































Figure 6: Long term track hypotheses consist of historical 
track hypotheses from track segments and current track 
hypotheses from measurements. 


These long term track hypotheses are scored using 
the individual track segment likelihoods, the track seg¬ 
ment association likelihoods, and the measurement to 
track association likelihoods. Manage Track Hypotheses 
then selects the best global long term hypothesis and 
performs pruning operations. The updated track hypothe¬ 
ses are converted into track segments and stored in the 
track segment graph and the process is repeated. 

Asynchronous or time-late reports may have just 
kinematic information or both kinematic and feature in¬ 
formation. When asynchronous reports are received, the 
Search Track Segment Graph function will again identify 
the relevant part of the track segment graph from the 
temporal and state (kinematic and feature) information in 
the report. This step is similar to the search function per¬ 
formed when feature reports are received. Because the 
time of the report may be different from the start or end 
times of the track segments, finding the state estimate at 
arbitrary times in a track segment is necessary. This is 
easy if the track segment graph retains the state estimates 
at other times between the start and end times. Otherwise, 
the state estimates will be interpolated from the start and 
end state estimates of a track segment. 

Once the relevant track segments are retrieved, the 
Generate / Update Track Hypotheses function forms the 
long term track hypotheses that can be scored to find the 
best global hypothesis by Manage Track Hypotheses. 

6 Simulation results 

In this section we present simulation results to demon¬ 
strate the benefits of the track segment approach for long 
term MHT. 

6.1 Efficiency of long term track hypotheses 
representation 

By using track segments, the number of long term track 
hypotheses is reduced significantly. We considered two 
examples. The first example is that of Figure 1 with only 
three targets and two ambiguous regions. The second 
example consists of 400 vehicles moving in an urban 
environment. There are many ambiguous regions due to 


targets passing each other at low velocity on roads. In 
both examples, the measurement rate is one second. 

In each example, we generate the track hypotheses 
directly from the reports. We also convert the reports into 
track segments (pure and ambiguous) and generate the 
track hypotheses from the track segments. Figure 7 com¬ 
pares the numbers of track hypotheses for the simple 
example. 



/- 


/ 

From 

/ 

Reports 

/ 

/ 

/ 


_/ 


/ 


/ 


/ 

From Track 

/ 

/ 

Segments 

/ 

y - 

/ s 



Time (s) 

Figure 7: Comparison of numbers of track hypotheses for 
3 target example 

The number of track hypotheses using reports (dot¬ 
ted line) grows much more rapidly compared to that using 
track segments. In fact, because there are only two am¬ 
biguous regions, the number of tracks formed from track 
segments (solid line) only changes twice. On the other 
hand, the dotted line always increases because of associa¬ 
tion at the report level. 

Figure 8 contains the comparison for the more com¬ 
plicated scenario. In this case, even though the long term 
hypotheses using the track segment graph (solid line) 
approach grows, its growth rate is much lower than the 
track hypotheses formed from reports (dotted line). The 
solid line always increases because targets are always 
moving into ambiguous regions. 



Figure 8: Comparison of numbers of track hypotheses for 
400 target example 

Both examples show that the EDMHT can maintain 
the crucial alternative hypotheses across the ambiguous 
regions with the track segment approach because there are 
far fewer track hypotheses. On the other hand, there are so 


2182 










many track hypotheses using reports that many alternative 
hypotheses cannot be maintained across the ambiguous 
regions. 

6.2 Optimality of hypothesis scoring 

We conducted experiments to demonstrate that the long 
term track likelihood computed from the individual track 
segment likelihoods and the track segment association 
likelihoods is identical to that computed from the individ¬ 
ual reports. The scenario consists of a target moving in 
two dimensional space and observed by a GMTI radar at 
2 Hz. The measurements are divided into five track seg¬ 
ments as shown in Figure 9. 

For each track segment S., the smoothed estimate of 

the start (kinematic) state and the filtered estimate of the 
end state are computed. The likelihood of the track seg¬ 
ment is also calculated from the measurements in the 
segment to give L(S f ). The track segment association 
likelihood L(i,i- 1) is calculated by assuming that 
p(x. | - p(x. | Y.^) , and then the long term track 

likelihood is computed. 

Figure 10 compares the long term track likelihood 
calculated from the track segment likelihoods and that 
calculated directly from the measurements. The two cur¬ 
ves are basically identical. This illustrates the optimality 
of the long term track likelihood algorithm. 



East (meters) 


Figure 9: Long term track consists of 5 track segments 



Figure 10: Long term likelihood computed from track 
segments is same as that computed from measurements. 


Although not shown, we also computed the exact 
long term track likelihood without using the assumption 
p(x* | Y l ,..,Y i _ l )-p{x s i | Y t _ x ) . The difference of the exact 
likelihood from the approximation is insignificant. This 
shows that track segment association likelihood depends 
only on local measurements in the two track segments to 
be associated when only kinematic states are involved. 

6.3 Benefit for feature aiding tracking 

We used the example of Figure 1 to demonstrate the bene¬ 
fit of the track segment graph approach for feature aided 
tracking. GMTI measurements were simulated for the 
three targets moving through the two ambiguous regions 
at 10 and 20 seconds respectively. In addition, feature 
measurements provided the colors of the targets at the 
beginning and end of the scenario. The measurements 
were processed using the traditional MHT approach and 
track segment based MHT. The association results were 
then compared. 

It is obvious that a pruning window longer than 20 
seconds is needed to maintain the alternative hypotheses 
across the ambiguities in order to use the feature meas¬ 
urements. Because the traditional MHT generates track 
hypotheses at the report level, the number of track hy¬ 
potheses grows very rapidly (Figure 7). Therefore, we had 
to use a pruning window smaller than 20 seconds for the 
MHT to run. The result is that track hypotheses could not 
be maintained for the required 20 seconds to exploit the 
features. 

The number of track hypotheses using the track 
segment graph approach grows much slower (Figure 7). 
Thus we were able to use a pruning window bigger than 
20 seconds to maintain all alternative hypotheses until the 
feature measurements were collected. Since the feature 
were observed with no errors, the association results were 
perfect. 

7 Conclusions 

We have developed an approach for extended duration 
multiple hypothesis tracking (EDMHT) that consists of 
the standard MHT and an extended duration addition. The 
core of the extended duration addition is an efficient rep¬ 
resentation of the long term track hypotheses by the track 
segment graph. An algorithm for evaluating the long term 
track likelihood has been developed. The efficiency and 
optimality of the representation and the likelihood calcu¬ 
lation have been demonstrated with simple examples. We 
plan to conduct experiments with more complicated ex¬ 
amples in the future. 

References 

[1] Y. Bar-Shalom and X-L Li, Multitarget-Multisensor 
Tracking: Principles and Techniques, YBS Publishing, 
Storrs, CT, 1995. 


2183 







[2] S. S. Blackman and R. Popoli, Design and Analysis 
of Modern Tracking Systems, Artech House, Norwood, 
MA, 1999. 

[3] D. B. Reid, “An algorithm for tracking multiple 
targets,” IEEE Trans. Automat. Contr., Vol. AC-24, No. 
6, pp. 843-854, Dec., 1979. 

[4] S. Mori, C. Y. Chong, E. Tse, and R. P. Wishner, 
“Tracking and classifying multiple targets without a priori 
identification,” IEEE Trans. Automat. Contr., Vol. AC- 
31, No. 5, pp. 401-409, May 1986. 

[5] S. Mori and C. Y. Chong, “Evaluation of data asso¬ 
ciation hypotheses: non-Poisson i.i.d. cases,” Proc. 7 th Int. 
Conf. Information Fusion , pp. 1133 - 1140, Stockholm, 
Sweden, July 2004. 

[6] C. L. Morefield, “Application of 0-1 Integer pro¬ 
gramming to multi-target tracking problems,” IEEE 
Trans. Automat. Contr , Vol. AC-22, No. 3, pp. 302-312, 
June 1977. 

[7] T. Kurien, “Issues in the design of practical multi¬ 
target tracking algorithms,” Multitarget-multisensor 
Tracking: Advanced Applications , ed. by Y. Bar-Shalom, 
Chap. 3, pp. 43 - 83, Artech House, 1990. 

[8] S. S. Blackman, “Multiple hypothesis tracking for 
multiple target tracking,” IEEE Aerospace and Electronic 
Systems Magazine , Vol. 19, No. 1, Part 2: Tutorial, pp. 5 
-18, January 2004. 

[9] A. Poore and N. Rijavec, “A Lagrangian relaxation 
algorithm for multidimensional assignment problems 
arising from multitarget tracking,” SIAM Journal of Opti¬ 
mization , Vol. 3, No. 3, pp. 544 - 563, August 1993. 

[10] S. Coraluppi, C. Carthel, M. Luettgen, and S. Lynch, 
“All-Source Track and Identity Fusion,” Proc. National 
Symp. Sensor and Data Fusion , San Antonio, TX, June 
2000. 

[11] E. Fortunato, W. Kreamer, S. Mori, C. Y. Chong, 
and G. Castanon, “Generalized Murty’s algorithm with 
application to multiple hypothesis tracking,” Proc. 11 th 
Int. Conf. on Information Fusion (Fusion 2007), Quebec 
City, 2007. 

[12] P. O. Arambel, J. Silver, M. Antone, and T. Strat, 
“Signature-aided air-to-ground video tracking,” Proc. 9 th 
Int. Conf. on Information Fusion (Fusion 2006), Florence, 
Italy, 10-13 July 2006. 


[14] R. Mahler, Statistical Multisource-Multitarget In¬ 
formation Fusion, Artech House, Norwood, MA, 2007. 


Appendix - Derivation of equation (3) 

The long term track likelihood is defined as 
L(T) = L(S l ,..S i ,..,S N ) = p(Y l ,..Y i ,..,Y N ) given the meas¬ 
urements Y = (Y l ,..Y i ,..,Y N ) . This likelihood can be eva¬ 
luated recursively as 

P(Yi’--’Yi,Y i+l ) = p(Y i+l | Y l ,..,Y i )p(Y l ,..,Y i ) (Al) 

Because 

p(Y i+l \Y l ,..,Y i ) = fp(Y m 

and 

IjkMjkl 


P(Y m \x‘ m ) = - 


p « i) 


(Al) becomes 

PVT,,.., Y„Y m ) 


(A2) 


p( x D 


J p(x i+ 1) 

Similarly, 

J P(Xi ) 

Thus, 

/>(>... > = f] />< i; >| | J /)| v - 1 } 1 ' W (A4) 


i =1 i=2 


which is equation (3). 


[13] O. E. Drummond, “Feature, attribute, and classifica¬ 
tion aided target tracking,” Proc. SPIE, Conf. on Signal 
and Data Processing of Small Targets, vol. 4473, 2001. 


2184