figure 7. articulated 3D person tracking with nBP. 41 Top: Graphical model
encoding kinematic and dynamic relationships (left), and spatial and
temporal potential functions (right) learned from mocap data. Middle:
Bottom-up limb detections, as seen from two of four camera views.
Bottom: estimated body pose following 30 iterations of nBP.
A small 10-sensor network with 24 edges is shown in
Figure 8, indicating both the true 2D sensor positions
(nodes) and inter-sensor measurements (edges). The
beliefs obtained using NBP are displayed on the right, by
showing 500 samples from the estimated belief; the true
sensor positions are also superimposed (red dots). The
initial beliefs are highly non-Gaussian and often fairly
diffuse (top row). As information propagates through the
graph and captures more of the inter-sensor dependencies, these beliefs tend to shrink to good estimates of the
sensor positions. However, in some cases, the measurements themselves are nearly ambiguous, resulting in a
bimodal posterior distribution. For example, the sensor
located in the bottom right has only three, nearly colin-ear neighbors, and so can be explained almost as well by
“flipping” its position across the line. Such bimodalities
indicate that the system is not fully constrained, and are
important to identify as they indicate sensors with potentially significant errors in position.
The abundance of problems that involve continuous variables
has given rise to a variety of related algorithms for estimating
posterior probabilities and beliefs in these systems. Here we
describe several influential historical predecessors of NBP,
and then discuss subsequent work that builds on or extends
some of the same ideas.
As mentioned in Section 2. 2, direct discretization of
continuous variables into binned “histogram” potentials can be effective in problems with low-dimensional
variables. 4 In higher-dimensional problems, however,
the number of bins grows exponentially and quickly
becomes intractable. One possibility is to use domain
specific heuristics to exclude those configurations that
appear unlikely based on local evidence. 8, 14 However, if
the local evidence used to discard states is inaccurate
figure 8. nBP for self-localization in a small network of 10 sensors. Left: Sensor positions, with edges connecting sensor pairs with noisy
distance measurements. Right: each panel shows the belief of one sensor (scatterplot), along with its true location (red dot). after the first
iteration of message passing, beliefs are diffuse with non-Gaussian uncertainty. after 10 iterations, the beliefs have stabilized near the true
values. Some beliefs remain multimodal, indicating a high degree of uncertainty in that sensor’s position due to near-symmetries that remain
ambiguous given the measurements.