An Algorithm for Improved Gating Combinatorics in Multiple-Target Tracking
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 02, 1990
- Accession Number
- ADA224700
Entities
People
- J. K. Uhlmann
- J. Michael Picone
- M. R. Zuniga
Organizations
- United States Naval Research Laboratory