A Comparison of Global Nearest Neighbor and Linear Assignment Problem Solution Methods on a Model Tracking Problem

In this paper we compare track data association purity, accuracy, and timing on a simple, idealized model tracking problem for two data association methods: Global Nearest Neighbor (GNN) and Linear Assignment Problem (LAP). Accurate data association is the central problem of multi-target track assembly. Though simple, the model, a 1d process noise-free Kalman filter, captures the essence of the problem of tracking multiple closely spaced objects: 1) assembly of object sensor measurements into tracks in the space of measurements 2) estimation of the Kalman filter state parameters giving rise to each measurement. We show that a Jonker-Volgenant (JV) LAP method decisively outperforms GNN in all three performance measures. Moreover, our results clearly show that the use of GNN methods for data association is highly problematic. Our basic recommendation is that a Multiple Hypothesis Tracking (MHT) method, which exploits a rectangular matrix extension of the JV algorithm as the core solver of a Murty’s ranked assignment algorithm, should be the preferred method for tracking multiple closely spaced objects.