Reformulating Reid's MHT method with generalised Murty K-best ranked linear assignment algorithm

Reformulating Reid's MHT method with generalised Murty K-best ranked linear assignment algorithm

For access to this article, please select a purchase option:

Buy article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IEE Proceedings - Radar, Sonar and Navigation — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

The authors reformulate Reid's multiple hypothesis tracking algorithm to exploit a K-best ranked linear assignment algorithm for data association. The reformulated algorithm is designed for real-time tracking of large numbers of closely spaced objects. A likelihood association matrix is constructed that, for each scan, for each cluster, for each cluster hypothesis, exactly and compactly encodes the complete set of Reid's data association hypotheses. The set of this matrix's feasible assignments with corresponding non-vanishing products is shown to map one-to-one respectively onto the set of Reid's data association hypotheses and their corresponding probabilities. The explicit structure of this matrix is a new result and leads to an explicit hypothesis counting formula. Replacement of the likelihood association matrix elements by their negative natural logs then transforms the data association matrix into a linear assignment problem matrix and recasts the problem of data association into efficiently finding sets of ranked assignments. Fast polynomial time Murty ranked assignment algorithms can thus replace Reid's original NP-hard exhaustive hypothesis identification, probability evaluation, and branch-and-prune methods and can rapidly determine the maximally likely data association hypothesis, the second most likely, etc. Results from two high fidelity surveillance sensor simulations show the validity of the proposed method.


    1. 1)
      • D.B. Reid . An algorithm for tracking multiple targets. IEEE Trans. Autom. Control , 843 - 854
    2. 2)
      • C.L. Morefield . Application of 0-1 integer programming for multitarget tracking problems. IEEE Trans. Autom. Control , 302 - 311
    3. 3)
      • V. Nagarajan , M.R. Chidambara , R.N. Sharma . Combinatorial problems in multitarget tracking – a comprehensive solution. IEE Proc. F, Commun. Radar Signal Process. , 1 , 113 - 118
    4. 4)
    5. 5)
      • I. Cox , M. Miller . On finding ranked assignments with application to multitarget tracking and motion correspondence. IEEE Trans. Aerosp. Electron. Syst. , 1 , 486 - 489
    6. 6)
      • K.G. Murty . An algorithm for ranking all the assignments in order of increasing cost. Oper. Res. , 682 - 687
    7. 7)
      • M. Miller , H. Stone , I. Cox . Optimizing Murty's ranked assignment method. IEEE Trans. Aerosp. Electron. Syst. , 3 , 851 - 862
    8. 8)
    9. 9)
    10. 10)
      • J.B. Collins , J.K. Uhlmann . Efficient gating in data association with multivariate distributed states. IEEE Trans. Aerosp. Electron. Syst. , 3 , 909 - 916

Related content

This is a required field
Please enter a valid email address