A multiple tree algorithm for the efficient association of asteroid observations

ABSTRACT

In this paper we examine the problem of efficiently finding sets of observations that conform to a given underlying motion model. While this problem is often phrased as a tracking problem, where it is called track initiation, it is useful in a variety of tasks where we want to find correspondences or patterns in spatial-temporal data. Unfortunately, this problem often suffers from a combinatorial explosion in the number of potential sets that must be evaluated. We consider the problem with respect to large-scale asteroid observation data, where the goal is to find associations among the observations that correspond to the same underlying asteroid. In this domain, it is vital that we can efficiently extract the underlying associations.We introduce a new methodology for track initiation that exhaustively considers all possible linkages. We then introduce an exact tree-based algorithm for tractably finding all compatible sets of points. Further, we extend this approach to use multiple trees, exploiting structure from several time steps at once. We compare this approach to a standard sequential approach and show how the use of multiple trees can provide a significant benefit.

REFERENCES

• 1: Y. Bar-Shalom and X. Li. Multitarget-Multisensor Tracking: Principles and Techniques. Yaakov Bar-Shalom, 1995.
• 2: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 3: S. Blackman and R. Popoli. Design and Analysis of Modern Tracking Systems. Artech House, 1999.
• 4: A. Gray and A. Moore. N-body problems in statistical learning. In T. K. Leen and T. G. Dietterich, editors, Advances in Neural Information Processing Systems. MIT Press, 2001.
• 5: Gísli R. Hjaltason , Hanan Samet, Incremental distance join algorithms for spatial databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.237-248, June 01-04, 1998, Seattle, Washington, United States
• 6: P. V. C. Hough. Machine analysis of bubble chamber pictures. In International Conference on High Energy Accelerators and Instrumentation. CERN, 1959.
• 7: D. Reid. An algorithm for tracking multiple targets. IEEE Transactions on Automatic Control, 24(6):843--854, December 1979.
• 8: V. Salari , I. K. Sethi, Feature Point Correspondence in the Presence of Occlusion, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.1, p.87-91, January 1990 [doi>10.1109/34.41387]
• 9: I. K. Sethi , R. Jain, Finding trajectories of feature points in a monocular image sequence, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.9 n.1, p.56-73, Jan. 1987 [doi>10.1109/TPAMI.1987.4767872]
• 10: S. W. Shaw and J. F. Arnold. Design and implementation of a fully automated oth radar tracking system. In Proceedings of the IEEE International Radar Conference, pages 294--298, May 1995.
• 11: J. K. Uhlmann. Algorithms for multiple-target tracking. American Scientist, 80(2):128--141, 1992.
• 12: J. K. Uhlmann. Introduction to the algorithmics of data association in multiple-target tracking. In D. L. Hall and J. Llinas, editors, Handbook of Multisensor Data Fusion, pages 3.1--3.18. CRC Press, 2001.
• 13: C. Veenman, E. A. Hendriks, and M. Reinders. A fast and robust point tracking algorithm. In Proceedings of the Fifth IEEE International Conference on Image Processing, October 1998.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Astronomy

General Terms:
Algorithms

Keywords:
multiple tree algorithms, track initiation