Share Email Print

Proceedings Paper

Efficient cluster management algorithm for multiple-hypothesis tracking
Author(s): Jean Roy; Nicolas Duclos-Hindie; Dany Dessureault
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

This paper presents a detailed discussion of clustering as applied to multiple hypothesis tracking (MHT). The combinatorial problem associated with forming multiple data association hypotheses can be reduced significantly by partitioning the entire set of system tracks and input data elements into separate clusters. Cluster management, a process that deals with cluster formation, merging, splitting and deletion, is thus motivated by the idea that a large tracking problem can be divided into a number of smaller problems that can be solved independently. The paper emphasizes on the cluster splitting process since it is the most difficult aspect of clustering while being an often neglected issue in the target tracking literature. The hypothesis dependencies that must be taken into account when one attempts to split the hypothesis tree of a cluster into two or more independent trees are discussed. This is an important issue since the hypotheses within a cluster must not interact with the hypotheses contained within other clusters for the MHT technique to remain consistent. A very efficient algorithm is described that performs a combined split-merge process simultaneously for all the clusters. The algorithm has been designed to avoid a waste of computer resources that may happen when splitting clusters that should have been kept merged according to the most recent input data set. The dynamic data structure that is used to implement the hypothesis tree is described as a key element of the approach efficiency. An example of cluster management is presented.

Paper Details

Date Published: 29 October 1997
PDF: 13 pages
Proc. SPIE 3163, Signal and Data Processing of Small Targets 1997, (29 October 1997); doi: 10.1117/12.279526
Show Author Affiliations
Jean Roy, Defence Research Establishment Valcartier (Canada)
Nicolas Duclos-Hindie, Groupe Informission Inc. (Canada)
Dany Dessureault, Groupe Informission Inc. (Canada)

Published in SPIE Proceedings Vol. 3163:
Signal and Data Processing of Small Targets 1997
Oliver E. Drummond, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?