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

Roy Danchick

S. Bentley Ave, Ste 302, Los Angeles, CA 90025, USA.

DOI: 10.4236/oalib.1112173                

Abstract

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.

Keywords

Multi-Target Target Tracking Data Association Global Nearest Neighbor Linear Assignment Problem Jonker-Volgenant Algorithm Kalman Filter

1. Introduction

Based on two disquieting experiences with the application of GNN for ballistic missile tracking data association it comes as a surprise to us that there is still active research on this method.

The first of these experiences occurred at an early 1980’s Denver conference on satellite infrared sensor ballistic missile tracking. One of the conference papers reported a GNN track-to-observation data association accuracy of 22 % in a high fidelity ballistic missile simulation.

In the late 1990’s, we had already written our Multiple Hypotheses Tracking paper [1] and were readying it for submission for publication. In it we introduced the notion of track purity as a basic data association performance metric; it is the maximum of the fractions of the number of observations in an assembled track of observations all of which come from the same sensor-detected object. In that paper we reported that track data association based on a Murty [2] K-best hypotheses algorithm with a Jonker-Volgenant (JV) [3] linear assignment problem solution algorithm as its core solution method was producing track purities in the high 90 percentiles for 200 closely spaced objects over 37 scans in a satellite infrared sensor high fidelity simulation.

In a Government funded Research and Development contract at our company we extended our satellite sensor 2d line-of-sight observation data association algorithm to 3d radar data association and were testing its performance in a radar system simulation. The systems engineer, working for another company hosting the radar simulator, had instrumented track purity performance evaluation with a GNN data association solution, scan-by-scan, as ground truth. Not unexpectedly, our extended algorithm’s track purity results came in at the low 20 percentiles.

So, it comes as a disturbing surprise to us that there is a still significant recent research devoted to GNN algorithms applied to tracking systems. Nowhere in this literature (e.g., references [4]-[9]) is track data association purity or an analogous metric ever mentioned, much less used to evaluate GNN data association performance.

The intent of this paper is to demonstrate, with the simplest of models, the striking, absolute performance dominance of the LAP algorithm over the GNN algorithm in terms of track data association purity, track state estimation accuracy, and timing.

Section 2 below covers definitions and notation. Section 2 provides derivations.

Section 3 supplies our key results.

Section 4 discusses the major conclusions that flow from our results.

Section 5 lists references cited in the paper.

2. Definitions

$n_s$ = number of scans.

$n_t$ = number of tracks.

$n_o$ = number of observations per scan.

$\sigma$ = observation normal error standard deviation.

$\mu ={\left[0,1,2,\cdots ,n_t-1\right]}^{\text{T}}$ is the column vector of state expected values.

$x_{is}$ = i^th track state on scan s at the beginning scan s prior to state update $i=1,2,\cdots ,n_t$ .

$y_{js}$ = j^th observation on the s^th scan., $j=1,2,\cdots ,n_o$ .

$I={\left[1,2,3,\cdots ,n_t\right]}^{\text{T}}$ .

$L$ = $n_t\times n_o$ track-to-observation data assignment matrix.

$C={\left[c_2,c_3,\cdots ,c_{n_s}\right]}^{\text{T}}$ is a column vector of costs for either the GNN or LAP methods.

$J_s$ = the assignment solution permutation column vector for either GNN or LAP methods on the s^th scan.

$P$ = $n_t\times n_s$ track-to-object assignment purity matrix for either GNN or LAP methods.

3. Derivations

3.1. Preliminaries

We first note that the core of our simulation model is a one dimensional Kalman filter with unit transition and measurement matrices, process noise-free, and independent identically distributed normal zero $N\left(0,{\sigma }^2\right)$ measurement error for each observation in each scan. The track-to-observation assignment matrix is square to facilitate the exploitation of the MATLAB JV linear assignment problem solver.

3.2. Initialization

In our simulation we first create the common $n_t\times n_s$ matrix of observations, $Y$ , with $\left(i,s\right)$ element given by

$y_{is}={\mu }_i+e_{is},e_{is}\in N\left(0,{\sigma }^2\right),i=1,2,\cdots ,n_t;s=1,2,\cdots ,n_s$ . (1)

For each of the GNN and LAP methods we set the first column of $P$ to $I$ .

For each $i\le n_t$ we establish a track with single-point initialization by setting

$\begin{array}{l}{x}_{i1}=y_{i1},\\ {\sigma }_{i1}^2={\sigma }^2\end{array}$ (2)

3.3. Recursive Computation

For each s such that $2\le s\le n_s$ .

For each $i\le n_t$ .

For each $j\le n_o$ .

$\begin{array}{l}w=y_{js}-x_{is}\\ {\sigma }_{ji}^2={\sigma }^2+{\sigma }_{is}^2\end{array}$ (3)

$L_{ij}=\left[\ln \left(2\pi {\sigma }_{ji}^2\right)+w^2/{\sigma }_{ji}^2\right]/2$

The likelihood matrix, $L_s$ on scan s, $2\le s\le n_s$ , is the matrix ${\left\{L_{ij}\right\}}_{1\le i\le n_t,1\le j\le n_o}$ .

The assignment solution vector is $J_s$ and the associated cost is $C_s,s=1,2,\cdots ,n_s$ .

The scan s states, $x_{is},i=1,2,\cdots ,n_t;2\le s\le n_s$ and variances are recursively updated according to

$\begin{array}{l}z=x_{i\left(s-1\right)}\\ {\tau }_{is}^2={\sigma }_{i\left(s-1\right)}^2\\ K={\sigma }^2{\left({\tau }_{is}^2+{\sigma }^2\right)}^{-1}\\ r=y_{J_s\left(i\right)s}-z\\ x_{is}=z+Kr\\ {\sigma }_{is}^2=\left(1-K\right){\tau }_{is}^2,i=1,2,\cdots ,n_t\end{array}$ (4)

$P$ is updated by setting the s^th column of $P$ to $J_s$ .

After $n_s$ scans method Purity, P, is computed as:

$\begin{array}{l}P=\left[{\displaystyle \sum _{1=2}^{n_s}{\displaystyle \sum _{i=1}^{n_t}p\left(i,s\right)}}\right]/\left(n_s{n}_t\right),\\ p_{is}=1\text{if}P\left(i,s\right)=i,\\ p_{is}=0\text{if}P\left(i,i\right)\ne i.\end{array}$ (5)

Track state accuracy, E, is computed as:

$E=\sqrt{\left[{\displaystyle \sum _{i=1}^{n_t}{\left(x\left(i,n_s\right)-\mu \left(i\right)\right)}^2}\right]/n_t}$ (6)

4. Results

We ran three 100 Monte-Carlo 10 scan MATLAB simulations characterized by the number of tracks (objects) and decreasing values of $\sigma$ . The MATLAB code was run on an HP 2.2 GHZ computer. The figures in Tables 1-5 are the average over the 100 samples. The figures in Table 6 and Table 7 are respective GNN and LAP assignment solution costs and on the last of the 100 samples for Case 3, $\sigma =0.25$ .

Case 1: $n_t=n_o=3$

Table 1. Comparative accuracy performance.

$\sigma$	Purity
	GNN	LAP
1.0	0.416	0.600
0.5	0.437	0.871
0.25	0.424	0.997
$\sigma$	Accuracy
	GNN	LAP
1.0	0.940	0.604
0.5	0.871	0.227
0.25	0.880	0.081

Case 2: $n_t=n_o=5$

Table 2. Comparative purity performance

$\sigma$	Purity
	GNN	LAP
1.0	0.305	0.485
0.5	0.322	0.771
0.25	0.346	0.997

Table 3. Comparative accuracy performance.

$\sigma$	Accuracy
	GNN	LAP
1.0	1.560	0.802
0.5	1.542	0.332
0.25	1.525	0.076

Case 3: $n_t=n_o=10$

Table 4. Comparative purity performance

$\sigma$	Purity
	GNN	LAP
1.0	0.206	0.454
0.5	0.230	0.780
0.25	0.269	0.990

Table 5. Comparative accuracy performance.

$\sigma$	Accuracy
	GNN	LAP
1.0	3.39	0.807
0.5	3.26	0.338
0.25	3.26	0.084

Table 6. Case 3 comparative cost.

Scan	GNN	LAP
2	7.497	7.497
3	15.320	1.333
4	8.976	1.836
5	30.356	3.493
6	34.680	3.792
7	27.892	1.489
8	49.460	2.127
9	31.545	-3.089
10	32.554	3.335

Table 7. Case 3 Comparative $Z_s^2$ .

Scan	GNN	LAP
2	5.488	5.488
3	17.738	13.723
4	12.850	3.958
5	133.650	3.022
6	24.214	4.745
7	31.298	17.841
8	180.884	14.128
9	222.726	13.406
10	107.723	6.597

As for comparative assignment problem solution timing, we note that GNN requires $n_t^2+{\left(n-1\right)}^2+\cdots +2^2=n_t\left(n+1\right)\left(2n_t+1\right)/6-1=O\left(n_t^3\right)$ floating point comparisons. This is the same complexity as the LAP JV algorithm but with, as seen from the tables above, far inferior purity and accuracy. We have timed the two methods on Case 3 samples. Typical GNN operating time/per problem/scan is 0.015 sec.; the LAP method solution times did not register above 0 sec.

5. Conclusions

We first observe that the LAP observation-to-track assignment solution is the maximally likely assignment solution among all the permutations on $n_t$ letters. It is obvious from the results above that the GNN solution ranks low in minimizing assignment problem cost among the Case 3 $n_t!=3628880$ possible assignments and is far from optimal. It is also interesting to note that GNN purity and accuracy performance essentially do not improve as $\sigma$ decreases while LAP performance increases sharply as $\sigma$ decreases.

Moreover, Table 4 confirms our two previous experiences with GNN performance, i.e., purity performances in the 20 percentiles. While we have relied on a simple idealized model, the results here and in [1], which exploited a more sophisticated Multi Hypothesis Tracking (MHT) data association algorithm, are mutually supportive.

Table 5 tells us that GNN error is more than an order of magnitude larger than LAP error. We can also infer from Table 4 and Table 5 that high track purity and accuracy are inextricably linked. High purity is necessary for state estimation accuracy; state estimation accuracy, based on first physical principles-based trajectory dynamics for the sensor-detected objects, is necessary for high purity to accurately predict where object observations will be in the space of measurements on the next scan.

Table 6 and Table 7 are taken from taking the last of the Case 3 100 Monte Carlo samples as a typical result.

Table 6 emphasizes the assignment cost superiority of LAP over the GNN solutions. Except for the first row entries, where the GNN and LAP algorithms both produced exact assignment solutions, we see that GNN costs are many times higher than LAP costs.

Given LAP perfect purity, as was the case with this particular sample, the statistics $Z_s^2=2c_s-n_t\left[\ln \left(2\pi {\sigma }^2/s\right)\right]$ , $s\ge 2$ , appearing in the third column of Table 7 is ${\chi }^2$ distributed with $n_t$ degrees-of-freedom. The expected value of such a random variable is $n_t=10$ because, for each $i\le n_t$ and $s\ge 2$ , the residual $r=y_{J_S\left(i\right),i}-x_{is}$ , appearing in Equation (4) is $N\left(0,{\sigma }^2\left(s/\left(s-1\right)\right)\right)$ distributed.

It is also clear that when it is not practical, in a real satellite infrared or radar sensor tracking system, to drive sensor detection measurement line-of-sight and/or range variances down beyond certain physical limits an MHT K-best hypotheses algorithm is required.

Finally, we come to the inescapable conclusion that the use of GNN for data association in tracking systems is highly problematic. It is reasonable to assume that GNN performance will degrade when dynamics and measurement equations, as functions of time evolving states of several dimensions and sensor-to-observed object geometry, are far more complicated than in our simple model. The far more likely inference is that GNN data association real world performance will be significantly worse than is shown above.

Conflicts of Interest

The author declares no conflicts of interest.

Conflicts of Interest

The author declares no conflicts of interest.

References

[1]	Danchick, R. and Newnam, G.E. (2006) Reformulating Reid’s MHT Method with Generalised Murty K-Best Ranked Linear Assignment Algorithm. IEE Proceedings—Radar, Sonar and Navigation, 153, 13-22.[CrossRef]
[2]	Jonker, R. and Volgenant, A. (1987) A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing, 38, 325-340.[CrossRef]
[3]	Murty, K.G. (1968) Letter to the Editor—An Algorithm for Ranking All the Assignments in Order of Increasing Cost. Operations Research, 16, 682-687.[CrossRef]
[4]	Han, Z., Wang, F. and Li, Z. (2020) Research on Nearest Neighbor Data Association Algorithm Based on Target “Dynamic” Monitoring Model. 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC), Chongqing, 12-14 June 2020, 665-668.[CrossRef]
[5]	Konstantinova, P., Udvarev, A. and Semerdjiev, T. (2003) A Study of a Target Tracking Algorithm Using Global Nearest Neighbor Approach. Proceedings of the 4th International Conference on Computer Systems and Technologies E-Learning, Rousse Bulgaria, 19-20 June 2003, 290-295.[CrossRef]
[6]	Sinha, A., Ding, Z., Kirubarajan, T. and Farooq, M. (2012) Track Quality Based Multitarget Tracking Approach for Global Nearest-Neighbor Association. IEEE Transactions on Aerospace and Electronic Systems, 48, 1179-1191.[CrossRef]
[7]	Shi, M., Ling, Z. and Zu, J. (2003) Association Using Modified Global Nearest Neighbor in the Presence of Bias. Proceedings of the Chinese Control Conference, Xi’an, 26-28 July 2013, 4688-4691.
[8]	Fukunaga, K. and Flick, T.E. (1984) An Optimal Global Nearest Neighbor Metric. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6, 314-318.[CrossRef] [PubMed]
[9]	Bahata, N. and Vandana, A. (2010) Survey of Nearest Neighbor Techniques. International Journal of Computer Science and Information Security, 8, 302-305.