An efficient message passing algorithm for multi-target tracking

Chen, Zhexu (Michael) and Chen, Lei and Çetin, Müjdat and Willsky, Alan S. (2009) An efficient message passing algorithm for multi-target tracking. In: 12th International Conference on Information Fusion, 2009 (FUSION '09), Seattle, WA, USA

[thumbnail of This is a RoMEO green publisher -- author can archive publisher's version/PDF] PDF (This is a RoMEO green publisher -- author can archive publisher's version/PDF)

Download (2MB)


We propose a new approach for multi-sensor multi-target tracking by constructing statistical models on graphs with continuous-valued nodes for target states and discrete-valued nodes for data association hypotheses. These graphical representations lead to message-passing algorithms for the fusion of data across time, sensor, and target that are radically different than algorithms such as those found in state-of-the-art multiple hypothesis tracking (MHT) algorithms. Important differences include: (a) our message-passing algorithms explicitly compute different probabilities and estimates than MHT algorithms; (b) our algorithms propagate information from future data about past hypotheses via messages backward in time (rather than doing this via extending track hypothesis trees forward in time); and (c) the combinatorial complexity of the problem is manifested in a different way, one in which particle-like, approximated, messages are propagated forward and backward in time (rather than hypotheses being enumerated and truncated over time). A side benefit of this structure is that it automatically provides smoothed target trajectories using future data. A major advantage is the potential for low-order polynomial (and linear in some cases) dependency on the length of the tracking interval N, in contrast with the exponential complexity in N for so-called N-scan algorithms. We provide experimental results that support this potential. As a result, we can afford to use longer tracking intervals, allowing us to incorporate out-of-sequence data seamlessly and to conduct track-stitching when future data provide evidence that disambiguates tracks well into the past.
Item Type: Papers in Conference Proceedings
Uncontrolled Keywords: Multi-target tracking; data association; graphical models; message passing; multi-hypothesis tracking; smoothing
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Electronics
Faculty of Engineering and Natural Sciences
Depositing User: Müjdat Çetin
Date Deposited: 04 Dec 2009 16:01
Last Modified: 26 Apr 2022 08:54

Actions (login required)

View Item
View Item