Particle filters have proven to be an effective tool for visual tracking in non-Gaussian, cluttered environments. Conventional particle filters, however, do not scale to the problem of human motion capture (HMC) because of the large number of degrees of freedom involved. Annealed Particle Filtering (APF), introduced by J. Deutscher et al. (2000), tackled this by layering the search space and was shown to be a very effective tool for HMC. We improve upon and extend the APF in two ways. First we develop a hierarchical search strategy which automatically partitions the search space without any explicit representation of the partitions. Then we introduce a crossover operator (similar to that found in genetic algorithms) which improves the ability of the tracker to search different partitions in parallel. We present results for a simple example to demonstrate the new algorithm's implementation and then apply it to the considerably more complex problem of human motion capture with 34 degrees of freedom.

The main challenge in articulated body motion tracking is the large number of degrees of freedom (around 30) to be recovered. Search algorithms, either deterministic or stochastic, that search such a space without constraint, fall foul of exponential computational complexity. One approach is to introduce constraints: either labelling using markers or colour coding, prior assumptions about motion trajectories or view restrictions. Another is to relax constraints arising from articulation, and track limbs as if their motions were independent. In contrast, we aim for general tracking without special preparation of objects or restrictive assumptions. The principal contribution of the paper is the development of a modified particle filter for search in high dimensional configuration spaces. It uses a continuation principle based on annealing to introduce the influence of narrow peaks in the fitness function, gradually. The new algorithm, termed annealed particle filtering, is shown to be capable of recovering full articulated body motion efficiently.

Some issues in markerless tracking of human body motion are addressed. Extended Kalman filters have commonly been applied to kinematic variables, to combine predictions consistent with plausible motion, with the incoming stream of visual measurements. Kalman filtering is applicable only when the underlying distribution is approximately Gaussian. Often this assumption proves remarkably robust. There are two pervasive circumstances under which the Gaussianity assumption can break down. The first is kinematic singularity and the second is at joint endstops. Failure of Kalman filtering under these circumstances is illustrated. The non-Gaussian nature of the distributions is demonstrated experimentally by means of Monte Carlo simulation. Random simulation (particle filtering or Condensation) proves to provide a robust alternative algorithm for tracking that can also deal with these difficult conditions.