Quasi-Random Sampling for Condensation

Abstract

The problem of tracking pedestrians from a moving car is a challenging one. The Condensation tracking algorithm is appealing for its generality and potential for real-time implementation. However, the conventional Condensation tracker is known to have difficulty with high-dimensional state spaces and unknown motion models. This paper presents an improved algorithm that addresses these problems by using a simplified motion model, and employing quasi-Monte Carlo techniques to efficiently sample the resulting tracking problem in the high-dimensional state space. For N sample points, these techniques achieve sampling errors of O(N ^-1), as opposed to O(N ^-1/2) for conventional Monte Carlo techniques. We illustrate the algorithm by tracking objects in both synthetic and real sequences, and show that it achieves reliable tracking and significant speed-ups over conventional Monte Carlo techniques.