n simple and consistent.Workare a variety of different approaches to the problem of track initiation. Below we briefly discuss some of the more common ones. These approaches differ from our own in several important ways. First, we are asking a different type of query. Specifically, we are asking for all sets of observations that could feasibly belong to a path. Second, we provide an exact algorithm for answering this query.Track Initiationcommon approach to track initiation is sequential track initiation [Blackman and Popoli, 1999]. The unassociated points are treated as new tracks and projected to the later time steps where they are associated with other points to form longer tracks. There are many variations to this type of approach. One common and often successful variation is a very simple form of multiple hypothesis tracking. When a tentative track matches multiple observations at a given time step, multiple hypothesizes (tentative tracks) are formed and the decision is delayed to a later time step. This process is illustrated in Figure 5. The single point matches three other points at the second time step. These points are used to create three hypothesized tracks. This process continues to the third and fourth time step with bad hypotheses being pruned away.order to reduce the number of candidate neighbors examined gating is used. As shown in Figure 6, neighbors are first filtered by whether they fall within a window or gate around the track s predicted position. This approach has also been used in conjunction with kd-tree structures to quickly retrieve the candidate observations near the predicted position of a track [Uhlmann, 1992, Uhlmann, 2001] .are several potential disadvantages of this type of approach that arise from the sequential nature of the search itself. It does not use evidence from later time steps to aid early decisions. Early good pairs may be easily pruned using a lack of further points along the track. Further, this approach has the potential of being thrown off by noise early in the track. Multiple hypothesis tracking attempts to mitigate this problem by allowing multiple tentative tracks, but introduces another problem, the possibility of a high branching factor causing a significant computational load.
Figure 5: A multiple hypothesis tracker starts from a tentative track (A) and sequentially checks the later time steps. If multiple points fit a candidate track then several hypothesis are created (B) and (C).
Figure 6: Gating can be used to ignore points that could not be part of the current track. The predicted position of the track is shown as an X and the points that fall within the gate are shaded.
should be noted that sequential track initiation has the advantage that it can be applied to multiple tracks simultaneously. This gives this approach the ability to discount observations that are obviously members of other tracks.
Figure 7: Early noise in a track can significantly throw-off predicted positions. The true points are shown as open circles and the observed points are shown as shaded circles.
Space Methodsapproach to the problem of track initiation is to search for tracks in parameter space. One popular algorithm is the Hough transform [Hough, 1959]. The idea behind these approaches is that for many simple models, individual observations correspond to simple regions or curves in parameter space. An example with a linear model is shown in Figure 8. The points are shown in Figure 8.A and their corresponding lines in parameter space in Figure 8.B. If a series of observations lie along a line, then their lines in parameter space will intersect at a common point. The Hough transform looks for lines by using grid-based counts of the number of lines that go through a particular region of parameter space (Figure 8.C and 8.D) .are several major downsides to the parameter space approach. First, maintaining and querying the parameter space representation can be expensive in terms of both computation and memory. There are many possible intersections to check and storing occurrences in a grid structure may require significant amounts of space. Secondly, the level of discretization of parameter space can drastically affect the accuracy of the algorithm.
Figure 8.
the grid is too tight then a small amount of noise can cause intersections to spread out over several bins and be missed. If the grid is too loose then coincidental occurrences can accumulate and cause false alarms. Although the false alarms can be filtered out in post-processing, this step further increases the computational cost.
