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