Performance comparison of 2D assignment algorithms for assigning truth objects to measured tracks

Mark Levedahl

doi:10.1117/12.392018

13 July 2000 Performance comparison of 2D assignment algorithms for assigning truth objects to measured tracks

Mark Levedahl

Proceedings Volume 4048, Signal and Data Processing of Small Targets 2000; (2000) https://doi.org/10.1117/12.392018
Event: AeroSense 2000, 2000, Orlando, FL, United States

Abstract

The processing time requirements of several algorithms for solving the 2-d (also called single frame) linear assignment problem are compared, along with their accuracy given either random or biased measurement errors. The specific problem considered is that of assigning measurements to truth objects using costs that are the chi-squared distances between them. Performance comparisons are provided for the algorithms implemented both in a compiled language C or FORTRAN) as well as the interpretive MatLab language. Accuracy considerations show optimal assignment algorithm is preferred if biased measurement errors are present. The Jonker-Volgenant-Castanon (JVC) algorithm is the preferred approach considering both average and maximum solution time. The Auction algorithm finds favor due to being both efficient as well as easy to understand, but is never faster and often much slower than the JVC algorithm. Both algorithms are dramatically faster than the Munkres algorithm. The greedy nearest neighbor algorithm is an ad hoc solution to provide a sub-optimal but unique solution more cheaply than the optimal assignment algorithms. However, the JVC algorithm is as fast as the greedy for simple problems, marginally slower at hard problems, and is vastly more accurate in the presence of measurement biases.

Citation Download Citation

Mark Levedahl "Performance comparison of 2D assignment algorithms for assigning truth objects to measured tracks", Proc. SPIE 4048, Signal and Data Processing of Small Targets 2000, (13 July 2000); https://doi.org/10.1117/12.392018

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available