Tracking Group Targets Using Hypergraph Matching in Data Association

Abstract

Group moving targets are a number of targets independently moving in a physical space but keeping their relative order or pattern invariant. The up to date state-of-the-art multi-target tracking (MTT) data association methods (GNN,JPDA,MHT) easily fail on group targets tracking problems, since the tracker-to-observation ambiguity cannot be resolved if only using the individual track to observation information. A hypergraph G is represented by G = {V,E}, where V is a set of elements called nodes or vertices, E is a set of non-empty subsets containing d-tuple of vertices called hyperedges. It can be used as a new mathematic tool to represent a group of moving targets if we let each target be a vertex and a d-target subset be an hyperedge. Under this representation, this paper reformulates the traditional MTT data association problem as an hypergraph matching one between the hypergraphs formed from tracks and observations, and shows that the traditional approach (only uses the vertex-to-vertex information) which is a special case under the proposed framework. In addition to the vertex-to-vertex information, since the hyperedge-to-hyperegde information is also used in building the assignment matrix, the hypergraph matching based algorithms give better performance than that from the traditional methods in group target tracking problems. We demonstrate the declaration from simulations as well as video based geotracking examples.

Keywords: Group targets tracking, data association, hypergraph matching.