An Algorithm for Improved Gating Combinatorics in Multiple-Target Tracking

In this paper we describe a method for significantly reducing the computational complexity required for observations-track gating in multiple target tracking. We define the gating process as follows: given a set of N(R) observations and N(T) tracks, identify all observation-track pairs whose scores fall above a chosen threshold. The score for observation-track pair (i,j) is defined as the function: In our analysis and numerical simulations we employ algorithms which find near neighbors of points in l-dimensional position space, where nearness is defined by the Euclidean metric. They are used, for example, to find the tracks with mean positions near a given observation position. Essential is that: (1) these algorithms find all the neighbors in some expected optimal or near optimal time, and (2),that their performance be relatively insensitive to spatial distributions. After examining several search algorithms, we selected a BLD-enhanced k-d search tree for our tests.