Efficient Algorithms for the Identification of Potential Track/Observation Associations in Continuous Time Data
by Jeremy Kubica, Andrew Moore, Andrew Connolly, and Robert Jedicke
BibTeX:
@techreport{kubica_2004_0461,
author = "Jeremy Kubica and Andrew Moore and Andrew Connolly and Robert Jedicke",
title = "Efficient Algorithms for the Identification of Potential Track/Observation Associations in Continuous Time Data",
institution = "Robotics Institute, Carnegie Mellon University",
month = "February",
year = "2005",
number = "CMU-RI-TR-05-10",
address = "Pittsburgh, PA"
}
Abstract:
In this paper we examine the problem of spatial
data association - identifying which track/observations pairs could
feasibly be associated. Efficiently and accurately finding these
potential associations is vital for most tracking applications,
because these associations both identify which target caused a given
observation and update the estimate of a target's position and
trajectory. However, previous work on efficiently answering this
query often makes the limiting assumption that observations arrive in
batches at discrete time steps. In many real world applications this
may not be the case. Observations may arrive individually or in small
batches distributed over a range of time. In this paper we focus on
the question of efficiently identifying potential track/observations
pairs in data where the observations can occupy a range of times.
We examine the new data structures and algorithms for efficient
spatial data association on this type of data. We show that it is
possible to adapt algorithms designed for discrete time data,
providing the benefits of continuous time while retaining the
tractability of discrete approaches. We introduce a novel data
structure for dealing with large sets of tracks these queries.
Empirically we show that these data structures provide a significant
benefit both in decreased computational cost and increased accuracy
when contrasted with treating the observations as arriving at a single
time. Further, we show that in some cases it is more efficient to
treat observations that do arrive at discrete time steps as if it were
continuous time data and apply our techniques.
- Download PDF