A maximum weight constrained path cover algorithm for graph-based multitarget tracking

In graph-based target tracking, vertices represent measurements and/or tracklets and edges represent allowable associations. Therefore a solution with a set of tracks is simply a vertex-disjoint path cover of the graph. Under certain (path independence) conditions, the tracking problem can be transf...

Full description

Saved in:
Bibliographic Details
Main Authors: Lingji Chen, Ravichandran, Ravi
Format: Conference Proceeding
Language:English
Subjects:
Algorithms
Encyclopedias
Force
Greedy algorithms
Joining processes
Target tracking
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In graph-based target tracking, vertices represent measurements and/or tracklets and edges represent allowable associations. Therefore a solution with a set of tracks is simply a vertex-disjoint path cover of the graph. Under certain (path independence) conditions, the tracking problem can be transformed into one of finding the maximum weight vertex-disjoint path cover of a directed acyclic graph, which can be efficiently solved using maximum weight bipartite matching or minimum cost network flow algorithms. However, attribute information often leads to path dependence. In this paper we consider an associated graph theoretic problem of finding the maximum weight vertex-disjoint path cover under the constraint that a given pair of vertices have to be on the same path. We show that the greedy algorithm is not optimal, and conjecture that the problem is nondeterministic polynomial-time hard (NP-hard). This motivates us to seek efficient algorithms for special classes of graphs that can be used as subroutines in a general algorithm. We present an efficient optimal algorithm for trellis graphs, and indicate how it can be used as a building block in a search algorithm for the general case.