potentials that nevertheless encode important constraints.
For example, the kinematic tracking and sensor localization applications considered in Section 4 both involve
“repulsive” potentials, that encourage pairs of variables to
not take similar values. In such cases, the NBP algorithm
in Figure 4 instead stores the weighted particles needed
to evaluate mji(– xi) at any location – xi of interest. These messages then influence subsequent iterations via importance
weighting.
As illustrated in Figure 2, the BP update of message
mji(xi) is most often expressed as a transformation of the
incoming messages from all other neighboring nodes
k Î G( j )\i. From Equations 2 and 3, however, it can also be
expressed as
This transformation suggests an alternative belief sampling
form of the NBP algorithm, in which the latest belief estimate provides a proposal distribution for auxiliary particles
figure 4. nonparametric BP update for the message mji(xi) sent from
node j to node i, as in figure 2.
Given input messages mkj(xj) for each k Î G( j )\i, which may be either
kernel densities mkj(xj) = {xkj (l), wkj (l), Λkj}L l= 1 or analytic functions, construct an
output message mji(xi) as follows:
1. determine the marginal influence ϕij(xj) of equation ( 11).
2. draw L independent, weighted samples from the product
Optionally resample by drawing L particles with replacement
according to , giving evenly weighted particles.
4. iLLuStRatiVe aPPLicationS
In this section we show several illustrative examples of
applications that use NBP to reason about structured collections of real-valued variables. We first show examples
of kinematic tracking problems in computer vision, in
which the variables represent the spatial position of parts
of an object. We then show how a similar formulation can
be used for collaborative self-localization and tracking
in wireless sensor networks. Other applications of NBP
include deformable contour tracking for medical image
segmentation, 46 image denoising and super-resolution, 38
learning flexible models of dynamics and motor response
in robotic control, 17 error correcting codes defined for
real-valued codewords, 31, 43 and sparse signal reconstruction using compressed sensing principles. 4 NBP has also
been proposed as a computational mechanism for hierarchical Bayesian information processing in the visual
cortex. 32
4. 1. Visual tracking of articulated motion
Visual tracking systems use video sequences from one
or more cameras to estimate object motion. Some of the
most challenging tracking applications involve
articulated objects, whose jointed motion leads to complex
pose variations. For example, human motion capture is
widely used in visual effects and scene understanding
applications. 33 Estimates of human, and especially hand,
motion are also used to build more expressive computer
interfaces. 48
To illustrate the difficulties, we consider a toy 2D object
localization problem in Figure 5. The model consists of
nine nodes: a central circle, and four jointed arms composed of two rectangular links. The circle node’s state x0
encodes its position and radius, while each rectangular
link node’s state xi encodes its position, angle, width, and
height. Each arm prefers one of the four compass directions, arms pivot around their inner joints, and geometry is
loosely enforced via Gaussian pairwise potentials ψij(xi , xj);
for details see Isard. 26
Our goal is to find the object in a sea of clutter (white
shapes in Figure 5) whose elements look exactly like components of the object. This mimics the difficulties faced
in real video sequences: statistical detectors for individual object parts often falsely fire on background regions,
and global geometric reasoning is needed to disambiguate them. Applied to this model, NBP’s particles encode
hypotheses about the pose xi of individual object parts,
while messages use geometric constraints to propagate
information between parts. When all of the true object’s
parts are visible, NBP localizes it after a single iteration. By
using Gaussian mixture potentials ψi(xi , y) that allow occasional outliers in observed part locations, NBP remains
successful even when the central circle is missing. In this
case, however, it takes more iterations to propagate information from the visible arms.
Kinematic tracking of real hand motion poses far
greater challenges. Even coarse models of the hand’s
geometry have 26 continuous degrees of freedom: each
finger’s joints have four angles of rotation, and the palm