Track Initialization in the Multiple-Object Tracking Problem

摘要

The track initialization problem is to estimate the n most probable trajectories that may give rise to the given set of consecutive frames of the same scene. It is called track initialization problem because no 'history' of the previous tracks' evolution is given. The multiple-object tracking problem involves extraction of the trajectories of n moving points from (three) successive motion picture frames. A definition of a 'three-point metric' functional (analogous to the classical definition of distance is put forward. For the best estimate of the trajectories, we partition the points from the frames into n triplets (based on the three successive frames) so that the average three-point 'distance' is minimized. The physical intuition behind this approach is discussed and several equivalent mathematical programming formulations are given. A practical method proposed for solving of the problem is based on a Lagrangean relaxation technique, and, to a lesser degree, on the 'pruning' of the tree of 'subpartitions'. On the basis of empirical evidence and experience from related work, we conjecture that, on average, O (n cu) arithmetic operations are needed to obtain a solution. The problem of missing and spurious points in the images is also briefly discussed. A short summary and examples from simulated data experiments are given. Keywords: Multiple object tracking problem; Inertial three point metric; Multilinear programming; Lagrangean relaxation; Moving targets. (edc)