|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.
Associated Lab(s) / Group(s):
Associated Project(s): Auton Project
Number of pages: 23
|Jeremy Martin Kubica, Andrew Moore, Andrew J. Connolly, and Robert Jedicke, "Efficient Algorithms for the Identification of Potential Track/Observation Associations in Continuous Time Data," tech. report CMU-RI-TR-05-10, Robotics Institute, Carnegie Mellon University, February, 2005|
author = "Jeremy Martin Kubica and Andrew Moore and Andrew J Connolly and Robert Jedicke",
title = "Efficient Algorithms for the Identification of Potential Track/Observation Associations in Continuous Time Data",
booktitle = "",
institution = "Robotics Institute",
month = "February",
year = "2005",
address= "Pittsburgh, PA",
|The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.|
Contact Us | Update Instructions