None

UAI2001

395

ORMONEIT ET AL.

Lattice Particle Filters

Dirk Ormoneit
Computer Science Dept.,
Stanford University,
Stanford, CA 94305

Christiane Lemieux
Mathematics and Statistics Dept.,
University of Calgary,
Alberta, Canada

Abstract

A promising approach to approximate infer­
ence in state-space models is particle filter­
ing. However, the performance of particlefilters often varies significantly due to their
stochastic nature. We present a class of al­
gorithms, called lattice particle filters, that
circumvent this difficulty by placing the par­
ticles deterministically according to a Quasi­
Monte Carlo integration rule. We describe a
practical realization of this idea, discuss its
theoretical properties, and its efficiency. Ex­
perimental resultswith a synthetic 2D track­
ing problem show that the lattice particle fil­
ter is equivalent to a conventional particle fil­
ter that has between 10 and 60% more par­
ticles, depending on their "sparsity" in the
state-space. We also present results on in­
ferring 3D human motion from moving light
displays.

This paper proposes the Lattice Particle Filter (LPF)
as an alternative, whereparticles are placed deter­
ministically according to a lattice rule. Lattice rules
are a subclass of Quasi-Monte Carlo (QMC) meth­
ods, which have been used successfully for high­
dimensional integration in computer graphics and fi­
nance [2, 12, 17]. An important theoretical advan­
tage of QMC methods is that for N samples the error
converges at the rate O(N-1log8 N), where s is the
statespace dimension, versus O(N-112) for conven­
tional Monte Carlo (MC). From a practical viewpoint,
randomized QMC methods can be used to construct
unbiased estimators that have smaller variance than
MC estimators.
After a brief introduction to the PF, we introduce
QMC methods and then describe the lattice particle
filter. We show quantitative results on two problems,
namely, tracking 2D imagepatterns, and the inference
of 3D human pose from a 2D binocular sequence of
projected limb positions.
2

1

-;

Introduction

The Particle Filter (PF) has become a popular method
for approximate inference in dynamical systems, with
applications such as visual tracking [1, 11, 15, 18, 20]
and robot localization [8]. The PF approximates a
marginal probability distribution overunknown state
variables with a weighted particle set, and thereby
provides a convenient approach to dealing with multi­
modal distributions, and nonlinear dynamics and ob­
servation equations [6, 9, 11, 14]. But despite its suc­
cesses, the PF can be unstable. Statistically speak­
ing, even though the PF produces properly weighted
samples, the random variation of predictions based on
thesesamples may be excessive and therefore the pre­
dictions may be unreliable. For visual tracking, this
results in poor estimates of object location; in some
situations it causes the algorithm to lose track of the
object altogether.

David J. Fleet
Xerox PARC,
3333 Coyote Hill Rd,
Palo Alto, CA 94304

Previous Work

In Bayesian filtering we are interested in computing a
probabilitydistribution over the unknown state vari­
able Xt at time t, conditioned on the observation his­
tory, Yt :::: (yt, ..., y1). This distribution, denoted
p(x1 I Yt), is called the filtering distribution. The PF
is a method for approximating p(xt I Yt) with a set of
weighted states (or p articles) . This approximation is
updated recursively from one time step to the next as
new observations becomeavailable. Gordon et al. [9]
provide a clear description of the method which they
call the Bootstrap Algorithm. In computer vision it is
often called the Condensation Algorithm [11]. Other
descriptions of the method, along with some important
generalizations are given by Liu et al. [14], Doucet et
al. [6], and Pitt and Shepard [19].
The goal of the particle filter is to approximate the fil­...