Data Association by Loopy Belief Propagation
Abstract
Data association, or determining correspondence between targets and measurements, is a very difficult problem that is of great practical importance. In this paper we formulate the classical multi-target data association problem as a graphical model and demonstrate the remarkable performance that approximate inference methods, specifically loopy belief propagation can provide. We apply it to calculating marginal association weights (e.g., for JPDA) for single scan and multiple scan problems, and to calculating a MAP hypothesis (i.e., multi-dimensional assignment). Through computational experiments involving challenging problems we demonstrate the remarkable performance of this very simple, polynomial time algorithm; e.g., errors of less than 0.026 in marginal association weights and finding the optimal 5D assignment 99.4% of the time for a problem with realistic parameters. Impressively the formulation commits smaller errors in association weights in challenging environments, i.e., in problems with low Pd and/or high false alarm rates. Our formulation paves the way for the expanding literature on approximate inference methods in graphical models to be applied to classical data association problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 2010
- Accession Number
- ADA564803
Entities
People
- Jason L. Williams
- Roslyn A. Lau
Organizations
- Defence Science and Technology Group