Multinsor Track-to-Track Association for Tracks with Dependent Errors
Y.BAR-SHALOM
University of Connecticut
H.CHEN
University of New Orleans
The problem of track-to-track association has been considered until recently in the literature only for pairwi associations.In view of the extensive recent interest in multinsor data fusion,the need to associate simultaneously multiple tracks has arin.This is due primarily to bandwidth constraints in real systems,where it is not feasible to transmit detailed measurement information to a fusion center but,in many cas,only local tracks.As it has been known in the literature,tracks of the same target obtained from independent nsors are still dependent due to the common process noi[2]. This paper derives the exact likelihood function for the track-to-track association problem from multiple sources,which forms the basis for the cost function ud in a multidimensional assignment algorithm that can solve such a large scale problem where many nsors track many targets.While a recent work
[14]derived the likelihood function under the assumption that the track errors are independent,the prent paper incorporates the(unavoidable) dependence of the errors.
Manuscript received November11,2004;revid September21, 2005;recommended by Editor Dr.Shozo Mori.
Authors’adress:Y.Bar-Shalom,Dept.of Electrical and Com-puter Engineering,University of Connecticut,Storrs,CT06269-2157, E-mail:(ybs@ee.uconn.edu);H.Chen,Dept.of Electrical Engineer-ing,University of New Orleans,New Orleans,LA70148,E-mail: (hchen2@uno.edu).
1557-6418/06/$17.00c°2006JAIF 1.INTRODUCTION
In this paper we consider the problem of associ-ating tracks reprented by their local estimates and covariances from S sources.The sources are proces-sors that u data from corresponding local nsor sys-tems.While different nsors have,typically,indepen-dent measurement errors,the local state estimation er-rors for the same target will be dependent due to the common prior or process noi.This dependence is characterized by the crosscovariances of the local es-timation errors–e[2],Sec.8.4.The association pre-nted in[2],while accounting for the crosscovariances of the track errors,is limited to pairs of , it is suitable for the situation of two lists(sources)of tracks.
Conquently,if this is ud when there are more than two lists of local tracks,the results will depend on the order in which the lists are considered.This order-dependence can be avoided only by simultaneous con-sideration of all S-tuples when there are S lists.
While a recent work[14]derived the likelihood function under the assumption that the state estimation errors are independent,the prent paper incorporates the(unavoidable)dependence of the errors.Earlier work on fusion of multiple tracks can be found in [13].This work also addresd the issue of dependence among tracks due to prior communication.The general fusion of crosscorrelated tracks was derived in[11].A recent comparison of different fusion techniques can be found in[15].
The goal of this paper is to derive a likelihood-ratio bad cost function suitable for the u of a multidi-mensional assignment(S-D,,[3],Ch.2)to de-cide which tracks should be fud.The cost function should allow simultaneous consideration of S tracks cor-responding to the same target(one from each source) or any subt of this.
First we shall derive the likelihood function of the hypothesis that S tracks are from the same , that they have a common origin.This derivation is bad on[17]where it was prented for
the purpo of n-sor bias estimation for S=2nsors and it accounted for the dependence of the track estimation errors across nsors.More recently[14]developed the likelihood function for the association of tracks from an arbi-trary number of nsors,but under the assumption that their track(local state estimation)errors are indepen-dent.This assumption,however,is not satisfied when the target state equations have process noi which is necessary to model motion uncertainty.
The likelihood functions are,however,not di-mensionless since they are joint pdfs(probability den-sity functions)of state vectors.As indicated in[4], Sec. 1.4.2,the pdf of a vector consisting of posi-tion and velocity in an n-dimensional Cartesian space has its physical dimension given by the inver of the product of the physical dimensions of its ,(length)¡n¢(length/time)¡n.Conquently,
the joint pdf of S such vectors has physical dimension of (length)¡2Sn¢(time)Sn.Therefore,one cannot compare the likelihood functions of the hypothesis that S tracks have a common origin with the hypothesis that,say,a subt of them,consisting of M<S tracks,have a com-mon origin,i.e,one has an incompatibility.The remedy for this incompatibility problem is to u dimensionless likelihood ratios obtained by dividing a common-origin likelihood function with the likelihood function of the hypothesis that the tracks are all of different origin. The latter likelihood function will consist of a dif
fu pdf(a uniform distribution in the augmented(product) state space–e[4],Sec.2.3.4),as detailed later.Using the likelihood ratios one can compare all the hypothe-s regardless of how many tracks of common origin are assumed in them.
The methodology of this paper,bad on likelihood ratios and a diffu prior for the target state estimates,al-lows for a systematic way of handling incomplete track-to-track associations across nsors and was prented in preliminary form in[6].Subquently,an application to a practical problem was given in[1].
The rest of the paper is organized as follows.The likelihood function of a t of tracks is derived in Sec-tion2.The likelihood ratios for the track-to-track asso-ciation are prented in Section3.The assignment with the negative log-likelihood ratios as cost function is dis-cusd in Section4.An investigation of the assignment accuracy,the nsitivity to the crosscorrelation,and a tracking example are prented in Section5.Conclu-sions are in Section6.
2.THE LIKELIHOOD FUNCTION OF A SET OF
TRACKS
Consider the situation where there are S nsors, each with its list of tracks reprented by the estimates ˆx j i
i
in the same state space,with errors that are zero-mean
jointly Gaussian with covariances P j i
i ,i=1,:::,S,per-
taining to a common time(not indicated for simplicity), where subscript i denotes the nsor bad on who data the(local)track has been obtained and superscript j i=1,:::,N i denotes the indices of the tracks at nsor i.The error crosscovariances for tracks reprenting the same target are discusd later.
The likelihood function of the common origin hy-
pothesis H l
1,:::,l S
for the tracks reprented by the lo-
cal estimatesˆx l i
i ,i=1,:::,,that they reprent the
same target is the joint pdf of the“track data”condi-tioned on the hypothesis
¤(H l
1,:::,l S
)=p(ˆx l S
S
,:::,ˆx l1
1j H l1,:::,l S):(1)
Note that in the above we u the fact that the track estimates are sufficient statistics–a conquenc
e of the Gaussian assumption.On the other hand,there is no assumption of independence of the track estimation errors.As it is known,the estimation errors for the same target obtained at independent nsors(with the measurement nois independent across the nsors)are correlated and this is quantified by the crosscovariance matrices(e[2],Sec.8.4.2).Otherwi,the errors are assumed independent.
The likelihood function(1)can be rewritten by moving the first(or any other)track estimate into the conditioning t,as follows
¤(H l
1
,:::,l S
)=p(ˆx l S
S
,:::,ˆx l2
2j H l1,:::,l S,ˆx l11)p(ˆx l11j H l1,:::,l S):
(2)
Since H l
1
,:::,l S
does not contribute any information to the marginal pdf of a single track,it can be dropped from the last term above.Furthermore,the marginal pdf of a track estimate can be taken as diffu(uniformly distributed in a region of the state space V,who volume is V,assumed large enough to qualify for a diffu prior),i.e.,
p(ˆx l1
1j H l1,:::,l S)=p(ˆx l11)=
1
(3)
becau,in the abnce of any information(which is our assumption),a track estimate can be anywhere in the state space.This is in accordance to Bayes’pos-tulate[8,10].The diffu prior has to have a support only“sufficiently larger”than the estimates’pdf.Fur-thermore,this diffu prior assumption is only for the marginal(unconditional)pdf of a track estimate.The conditional pdf of any track estimate given another es-timate with the same origin is not diffu anymore and is determined by the statistical properties of their estima-tion errors which are not assumed independent–their correlation can be due to the common process noi as well as to a common prior.
With this,(2)becomes
¤(H l
1
,:::,l S
)=
1
V
p(ˆx l S
S
,:::,ˆx l2
2j H l1,:::,l S,ˆx l11):(4) Note that V¡1,while having a physical dimension(that makes(4)have the same dimension as(1)),is really a constant who exact value only scales the final result.
Consider first the ca of common origin of two tracks,l i and l j from nsors i and j,respectively.
Now,under the Gaussian assumption,ifˆx l i
i
originated
from the same target asˆx l j
j
,then,with the diffu prior assumption,one has(e Appendix;this result was prented in[2],Sec.8.3.3,but without proof)
E[ˆx l i
i j H l i,l j,ˆx l j j]=ˆx l j j(5) and
E[(ˆx l i
i¡ˆx l j j)(ˆx l j j¡ˆx l j j)0j H l i,l j,ˆx l j j]
=E[(ˆx l i
i¡x l¡(ˆx l j j¡x l))(ˆx l i i¡x l¡(ˆx l j j¡x l))0j H l i,l j]
=P l i
i
+P l j
j¡P l i,l j i,j¡(P l i,l j i,j)0(6)
where x l is the common true state of the tracks, which is irrelevant.The crosscovariance P l i,l j
i,j
is given by a Lyapunov type recursion(e[2],Sec.8.4).1
Thus for tracks l i and l j one has
p(ˆx l i
i j H l i,l j,ˆx l j j)=N[ˆx l i i;ˆx l j j,P l i i+P l j j¡P l i,l j i,j¡(P l i,l j i,j)0]
=N[ˆx l i
i¡ˆx l j j;0,P l i i+P l j j¡P l i,l j i,j¡(P l i,l j i,j)0]
(7) where N[x;¯x,P]denotes the Gaussian pdf with argu-ment x,mean¯x and covariance P.Then the joint likeli-hood function of common origin for the tracks l i and l j is
¤(H l
i ,l j
)=
1
p(ˆx l i
i j H l i,l j,ˆx l j j)
=
1
N[ˆx l i i¡ˆx l j j;0,P l i i+P l j j¡P l i,l j i,j¡(P l i,l j i,j)0]:
(8)
Note that the test statistic(normalized distance squared)
D(ˆx l i
i ,ˆx l j
j
)=(ˆx l i
i¡ˆx l j j)0[P l i i+P l j j¡P l i,l j i,j¡(P l i,l j i,j)0]¡1(ˆx l i i¡ˆx l j j)
(9)
has been known in the literature for some , [2],Sec.8.4.3)for the association of pairs of tracks.2 While originally this distance was introduced heuris-tically,it can be en to follow directly from(8) as a likelihood test.The first rigorous derivation of (9)was given in[17]in the context of nsor bias estimation.The derivation given above is,however, much simpler and,more importantly,it generalizes to S tracks.
1Previous communication is difficult to account for in the correlation but not impossible–this would require restarting(after every com-munication)the iteration of the Lyapunov equation(8.4.2-3)in[2] that yields the crosscovariance.
2The importance of using the crosscovariances is twofold:ignoring the crosscorrelations(which are positive,as discusd in Section5) the distance(9)is smaller than it should be and the covariance of t
he fud estimate is optimistic(e[2],Sec.8.4.5).
The general likelihood function(4)for common origin of the tracks l1,:::,l S is obtained as follows.The pdf from(4)can be written as
p(ˆx l S
S ,:::,ˆx l2
2j H l1,:::,l S,ˆx l11)=N
B B@
2
664ˆ
ˆx l S
S
3
775;
2
664ˆ
ˆx l1
1
3
775,
2
64E[(ˆx l22¡ˆx l11)(ˆx l22¡ˆx l11)0j H l1,:::,l S]¢¢¢E[(ˆx l22¡ˆx l11)(ˆx l S S¡ˆx l11)0j H l1,:::,l S]
¢¢¢¢¢¢¢¢¢
E[(ˆx l S
S¡ˆx l11)(ˆx l22¡ˆx l11)0j H l1,:::,l S]¢¢¢E[(ˆx l S S¡ˆx l11)(ˆx l S S¡ˆx l11)0j H l1,:::,l S]
3
75
1
C C A:
(10)
Then,similarly to(7),the mean is shifted into the
argument and this yields the likelihood function
¤(H l
1
,:::,l S
)
=
1
N[ˆx1,S;0,P1,S](11)
where
ˆx
1,S
¢=
2
664ˆx l22¡ˆ
ˆx l S
S¡ˆx l11
3
775(12)
is a stacked(S¡1)n x vector(with n x the dimension
of x),who covariance,defined within(10)has the
diagonal blocks
(P1,S)i¡1,i¡1=E[(ˆx l i
i¡ˆx l11)(ˆx l i i¡ˆx l11)0j H l1,:::,l S]
=P l1
1
+P l i
i¡P l1,l i1,i¡(P l1,l i1,i)0,
i=2,:::,S(13)
and the offdiagonal blocks
(P1,S)i¡1,j¡1=E[(ˆx l i
i¡ˆx l11)(ˆx l j j¡ˆx l11)0j H l1,:::,l S]
=P l1
1¡P l1,l j1,j¡(P l1,l i1,i)0+P l i,l j i,j,
i,j=2,:::,S.(14)
Note that with the(invertible)transformation
ˆy
1,S
=
2
666
666
4
1¡10¢¢¢
01¡10
¢¢¢¢¢¢¢¢¢¢¢¢
¢¢¢01¡1
¢¢¢001
3
777
777
5
ˆx
1,S
=
2
666
666
664
ˆx l2
2¡ˆx l33
ˆx l3
3¡ˆx l44
..
.
ˆx l S¡1
S¡1¡ˆx l S S
ˆx l S
S¡ˆx l11
3
777
777
775
(15)
one can e that(11)is really symmetric in the n that
it has an equivalent symmetric form even if it appears
not to be symmetric at first sight.This is due to the
fact that the determinant of the above transformation is
unity.
R EMARKS Note that the expression of the likelihood function(11)follows from the way in which(4)is written,namely as the joint pdf of the local track estimates from nsors S,:::,2(written for convenience with the indices decreasing)conditioned on the track estimate from nsor1.Equation(4)can be rewritten in the chain rule form as
¤(H l
1,:::,l S
)=
1S Y
i=2
p(ˆx l i
i jˆx l i¡1i¡1,:::,ˆx l22,ˆx l11)
=
1S Y
i=2
p(ˆx l i
i jˆx F i¡1)(16)
whereˆx F i¡1is the fud state estimate from the first i¡1 local tracks.
It was this last form that was derived in[14]un-der the assumption that the local track errors are un-correlated.While(16)holds also for correlated tracks since no uncorrelatedness assumption was needed in its derivation above,its evaluation is relatively simple only under the assumption that the local track errors are un-correlated.Otherwi,for the realistic situation of cor-related track errors it becomes quite complicated.Con-quently,expression(11)is believed to be the practical one when the crosscovariances are taken into consider-ation.
Note that the local track estimate from nsor1is chon in the conditioning of(2)only for notational simplicity.One can u any local estimate as the refer-ence track to obtain(11)with similar derivation.
3.THE LIKELIHOOD RATIOS FOR GENERAL
TRACK-TO-TRACK ASSOCIATION
The likelihood ratio of the common origin hypoth-
esis H l
1,:::,l S
for the tracks reprented by the local esti-
matesˆx l i
i ,i=1,:::,,that all the tracks reprent
the same target is obtained next.The numerator is given by(11)while the denominator,which is the likelihood of all being of different origin(hypothesis¯H l1,:::,l M),is obtained in a similar manner to(2)as follows
¤(¯H l1,:::,l S)=p(ˆx l S S,:::,ˆx l22j¯H l1,:::,l S,ˆx l11)p(ˆx l11j¯H l1,:::,l S)
=
S
Y
s=2
p(ˆx l s s j¯H l1,:::,l S,ˆx l11)p(ˆx l11j¯H l1,:::,l S):
(17)
Analogously to(3),
p(ˆx l1
1j¯H l1,:::,l S)=p(ˆx l11)=1
:(18)
As shown in[7],[10],the role of the pdf of a fal/extraneous measurement in the likelihood ratio is played by the spatial density of the measurements un-der the assumption that they are Poisson distributed. This was obtained from the rigorous Bayesian deriva-tion of the Multiple Hypothesis Tracker.Conquently, assuming the extraneous tracks in the prent problem to be Poisson distributed in the state space with spatial density3¹ex,one has
p(ˆx l s s j¯H l1,:::,l S,ˆx l11)=¹ex:(19) Using(18)and(19)in(17)yields
¤(¯H l1,:::,l S)=¹S¡1ex V:(20) Finally,combining the above with(11)yields the like-lihood ratio
L(H l1,:::,l S:¯H l1,:::,l S)=¤(H l1,:::,l S)
¤(¯H l1,:::,l S)=
1
V N[ˆx1,S;0,P1,S]
1
¹S¡1
ex
=
N[ˆx1,S;0,P1,S]
ex
(21)
which is,clearly,a dimensionless quantity.
Next consider the likelihood ratio of an incomplete assignment consisting of tracks from the lists cor-responding to the subt of nsors with indices S i=f s1,s2,:::,s M g,where1·s1<s2<¢¢¢<s M·S. The entire t of list(nsor)indices is denoted as S.
Assume that the probability of a target having a (“detected”)track in the list of nsor s is P D
s
and that the track detection events are independent across nsors.4
Then the likelihood ratio of this assignment is[7]
L(H l s1,:::,l s M:¯H l s1,:::,l s M)
=V¡1N[ˆx S i;0,P S i]
"Y
s2S i
P D
s
#
¹¡S+M
ex
£
2
4Y
s2¯S i
(1¡P D
s
)
3
5[V¡1¹¡S+1ex]¡1
=¹M¡1
ex N[ˆx S i;0,P S i]
"Y
s2S i
P D
s
#2
4Y
s2¯S i
(1¡P D
s
)
3
5:
(22) The above follows by including in the numerator the probabilities of the events(assumed independent)that the tracks belonging to the hypothesized target have been detected by the nsors in S i but not by the
3Since the true targets are typically not homogeneously distributed in the space,this should be taken as the local density of the extraneous (true and fal)tracks.
4This is clearly only a convenient mathematical assumption–in prac-tice the situation can be much more complex:the probabilities de-pend on the target locations,nsor modes,their fields of view,ob-scuration conditions,etc.
nsors in¯S i.For the tracks corresponding to the nsors in¯S i,their pdfs are the“extraneous”ones,¹ex.In the denominator we have the probability densities of the tracks assuming they are not of common origin, modeled as having pdfs¹ex.The pdfs of the tracks corresponding to the nsors in¯S i cancel between the numerator and denominator.
The first argument of the Gaussian density in(22) is,similarly to(12),given by
ˆx S i ¢=
2
664ˆx
l s
2
s2¡ˆx l s1s1
..
.
ˆx l s M s
M¡ˆx
l s
1
s1
3
775(23)
and P S
i is its covariance matrix with blocks given by
expressions similar to(13)—(14).
4.THE USE OF THE LIKELIHOOD RATIOS IN
ASSIGNMENT
We first consider the assignment formulation for track-to-track association from two nsors.Assume nsor1has a list of N1tracks and nsor2has a list of N2tracks.Define the binary assignment variableÂij as
Âij =
8<
:
1track i from nsor1and track j
from nsor2are from the same target, 0otherwi.
(24)
Denote by L ij the likelihood ratio of the two tracks be-ing from the same target vs.from two different targets which is the two nsor ca of(22).If we assume that the track association events among dif
ferent track pairs are independent,then the2-D assignment formulation finds the most likely(joint)track-to-track association hypothesis by solving the following constrained opti-
mization5
min
Âij
N1
X
i=0
N2
X
j=0
c ijÂij(25)
subject to
N1
X
i=0
Âij=1,j=1,:::,N2(26)
N2
X
j=0
Âij=1,i=1,:::,N1(27)Âij2f0,1g,i=0,1,:::,N1,j=0,1,:::,N2
(28)
5Each list of tracks from a nsor is augmented by a“dummy element”with index0,which stands for“n
o track,”to allow for incomplete associations,while keeping the assignment problem complete.where
c ij=¡ln L ij:(29) This can be solve
d using th
e Auction or JVC algorithm [19].As shown in[12]this can also be solved opti-mally using linear programming by relaxing the integer constraint.
The extension to multidimensional assignment (S-D)is as follows.Assume there are S sources(S¸3) where source S i has a list of N i tracks.Define the binary assignment variableÂi
1
i2:::i S
as
Â
i1i2:::i S
=½1tracks i1,i2,:::,i S are from the same target, 0otherwi.
(30) We allow a subt of indices f i1,i2,:::,i s g to be zero in the assignment variable meaning that no track will be from the target in the corresponding list of the sources. Denote by L i
1
i2:::i S
the likelihood ratio of the track as-sociation hypothesis vs.all tracks being from different targets which is given by(22).The S-D assignment for-mulation finds the most likely hypothesis by solving the following constrained optimization
min
Âi
1i2:::i S
N1
X
i1=0
N2
X
i2=0
¢¢¢
N S
X
i S=0
c i
1
i2:::i S
Âi
1
i2:::i S
(31)
subject to
N2
X
i2=0
¢¢¢
N S
X
i S=0
Âji
2
:::i S
=1,j=1,:::,N1
N1
X
i1=0
N3
X
i3=0
¢¢¢
N S
X
i S=0
Âi
1
ji3:::i S
=1,j=1,:::,N2
¢¢¢
N1
X
i1=0
¢¢¢
N S¡1
X
i S¡1=0
Âi
1
i2:::i S¡1j
=1,j=1,:::,N S
(32)
and
Â
i1i2:::i S2f0,1g,
i
1
=0,1,:::,N
1
,i
2
=0,1,:::,N
2
,
:::,i
S
=0,1,:::,N
S
:
(33) In(31)the assignment cost is
c i
1
i2:::i S
=¡ln L i
1
i2:::i S
(34)
where the likelihood ratio L i
1
i2:::i S
(written here with a simpler index-only notation)can be computed using (22).The above constrained integer programming is, in general,NP hard.However,efficient algorithms exist to find a suboptimal solution via Lagrangian relaxation (,[19]).
5.SIMULATION RESULTS
5.1Evaluation of the Association Accuracy and
Sensitivity
We want to study the track association accuracy for a different number of local nsors with various
cross-correlation coefficients.To make it simple,we assume that the local estimates are scalars with unity variances. The crosscorrelation coefficients between two local es-timates is denoted by½.We choo various values of ½,namely,0,0.1,0.3,0.5,when the local tracks corre-spond to the same target.
The null hypothesis H0is that all the local estimates correspond to the same target with its location uniformly distributed within the surveillance region of length V= 10
H0=f“same target”g:(35)
The hypothesis H1is that all local estimates correspond to different targets with their locations uniformly dis-tributed within the surveillance region
H1=f“different targets”g:(36)
In this ca,the paration of two targets is random and it depends on the volume of the surveillance region and no further prior knowledge is assumed.
Note that with the relatively small region V the targets,even if they are different,can be clo enough to appear as they were the ,it is difficult to discriminate between the two hypothes becaus
e they are not easily distinguishable.Conquently,even the most powerful test will not be very powerful is this situation.
The test bad on(22)is ud to compute the receiver operating characteristic(ROC)curves for the cas of N local tracks from the same ,the curves of the power of the test
P D=P f“H0”j H0g(37) where“H0”denotes“accept H0,”vs.the fal alarm probability
P FA=P f“H0”j H1g:(38) Fig.1shows the ROC curves for the track as-sociation test with2,3,and4local track estimates and various crosscorrelation coefficients.One thou-sand random realizations are ud for each hypothe-sis with fixed½and N to compute the curves.We can e that the test power increas as N increas for fixed V since the H0hypothesis becomes more distin-guishable when more targets are uniformly distributed within the surveillance region.The crosscorrelation be-tween the local track estimates is beneficial in terms of the test power under a given fal alarm rate for all cas.As½increas,the alternative hypothesis (“different targets”)becomes more distinguishable from the null hypothesis(“same target”)becau common origin tracks will then be clor to each other(in
terms
Fig.1.ROC curves for the track association test with a different number of local estimates and various crosscorrelation coefficients. of their normalized distance–e(9),which improves the decision accuracy.However,once H0is declared,the variance of the fud track estimate is larger than when they are uncorrelated[11].
Consider a ca where one us the test assuming ½=0.The threshold is determined for a certain max-imum allowed miss probability of H0,that is,1¡P D. If the true crosscorrelation coefficient ,½=0:5, the actual P D will be higher than the one calculated un-der½=0.At the same time,the actual P FA will also be higher.
For two tracks(each with unity variance,for simplic-ity)assuming½=0,the(chi-square)test statistic ud is
D0=(ˆx1¡ˆx2)2=2(39) and the“design”probability of fally rejecting the null hypothesis is
P f D0>¿0j H0g=1¡P0D(40) bad on the chi-square distribution with one degree of freedom
D0»Â21:(41) However,since½=0:5,(41)does not hold,Instead, under H0,
D=(ˆx1¡ˆx2)2=[2(1¡½)]»Â21:(42) Thus the test statistic ud,D0,is
D0=D=2(43) i.e.,half of what it should have been.Conquently, the statistic D0will be more inclined to accept the “same target”hypothesis than the correct statistic D, i.e.,P FA,as well as P D,will increa.Becau the test statistic ud is a scaled version of the correct one,the test assuming½=0us effectively a threshold that is
