Fast and Robust Track Initiation Using Multiple Trees

In this paper we examine a fundamental problem in many tracking tasks: track initiation (also called linkage). This problem consists of taking sets of point observations from different time steps and linking together those observations that fit a desired model without any previous track estimates. In general this problem suffers from a combinatorial explosion in the number of potential tracks that must be evaluated. We introduce a new methodology for track initiation that exhaustively considers all possible linkages. We then introduce an exact multiple kd-tree algorithm for tractably finding all of the linkages. We compare this approach to an adapted version of multiple hypothesis tracking using spatial data structures and show how the use of multiple trees can provide a significant benefit.