Interpreting Images by Propagating Bayesian Beliefs

Yair WeissNeurIPS 1996 · OpenReview

Introduction

In computer vision, local information is frequently ambiguous. Consider the "aperture problem": if you observe the straight edge of a moving object through a small hole, you cannot determine its true velocity—only the component of motion perpendicular to the edge. To build a globally consistent interpretation of a scene, vision systems must "propagate" these local, ambiguous measurements across the entire image.

Historically, researchers have tackled this using relaxation methods, such as gradient descent or Successive Over-Relaxation (SOR). In these architectures, every pixel iteratively updates its "best guess" based on the guesses of its neighbors. However, these methods suffer from two major flaws: they are excruciatingly slow to converge, and they frequently get trapped in local minima, resulting in solutions that appear correct locally but are globally flawed.

This paper proposes a paradigm shift: solving vision problems orders of magnitude faster by propagating Bayesian beliefs (probability distributions) rather than single numerical estimates.

The Bayesian Belief Propagation (BBP) Architecture

The core innovation introduced by author Yair Weiss is moving from propagating rigid estimates to propagating probabilities. By treating image interpretation as a statistical inference problem on a graph, the proposed architecture reaches optimal solutions as soon as information physically reaches a pixel.

From Estimates to Probabilities

Instead of a node communicating a hard estimate (e.g., "I think the value here is 5"), it passes a message to its neighbor representing a full probability distribution (e.g., "I think the value is 5, with a variance of 0.2").

1D Interpolation and BBP Message Passing

This approach adapts to the nature of the problem:

  • Continuous Problems: For tasks like surface interpolation, messages are represented by means and variances. The resulting update rules resemble a distributed Kalman Filter.
  • Discrete Problems: For tasks like labeling a region as "foreground" or "background," the messages are vectors of probabilities.

Non-Iterative Convergence

BBP leverages a critical distinction in network iterations: some iterations are necessary simply for information to travel across the network's physical distance, while others are spent "refining" an estimate. BBP is non-iterative in the sense that once information from a distant pixel reaches a node, that node's estimate is immediately optimal given the available data. No additional "settling" time is required.

Experimental Validation

The paper evaluates BBP on specific vision tasks, focusing on 1D structures where the mathematical guarantees of the algorithm shine.

Hand Video Sequence and Extracted Contour

The datasets include:

  • Synthetic Sparse Data: Used to test prototypical function interpolation.
  • Hand Video Sequence: A real-world video of a hand translating laterally. This was used to test motion propagation and "Direction of Figure" (DOF) estimation along the extracted contours of the hand.

Key Results and Insights

The performance gains demonstrated by BBP are dramatic, driven by the algorithm's ability to maintain uncertainty. Traditional methods fail because they force a node to commit to a single estimate too early. By passing full probability distributions, BBP allows a pixel to remain "undecided" until sufficient evidence arrives from elsewhere in the image.

  • Unprecedented Speed: In motion estimation tasks, BBP reached the correct, globally consistent solution in just 3 iterations. In stark contrast, SOR—a standard "fast" traditional method—still exhibited significant errors after 500 iterations.
  • Bypassing Local Minima: In the discrete "Direction of Figure" task (deciding which side of a curve is the object), traditional relaxation algorithms (Hopfield, Rosenfeld, and Gradient Descent) all converged to a local minimum, yielding incorrect answers. BBP was the only method that successfully found the global minimum. For 1D structures like contours, BBP is mathematically guaranteed to converge to the correct posterior after $N$ iterations (where $N$ is the network diameter).

Limitations and Future Directions

While highly effective on 1D structures, BBP faces challenges when applied to full 2D images. Propagating beliefs in 2D corresponds to Markov Random Fields (MRFs) that contain loops. In these loopy graphs, the simple mathematical guarantees of BBP do not hold perfectly, complicating the inference process.

To address this, the author points toward hierarchical, "multi-resolution" pyramidal models as a promising way to approximate 2D BBP efficiently. Preliminary results suggest that this hierarchical approach yields encouraging improvements over traditional 2D relaxation schemes, paving the way for faster, more robust computer vision systems.

Summary updated

Abstract

A central theme of computational vision research has been the re(cid:173) alization that reliable estimation of local scene properties requires propagating measurements across the image. Many authors have therefore suggested solving vision problems using architectures of locally connected units updating their activity in parallel. Unfor(cid:173) tunately, the convergence of traditional relaxation methods on such architectures has proven to be excruciatingly slow and in general they do not guarantee that the stable point will be a global mini(cid:173) mum. In this paper we show that an architecture in which Bayesian Be(cid:173) liefs about image properties are propagated between neighboring units yields convergence times which are several orders of magni(cid:173) tude faster than traditional methods and avoids local minima. In particular our architecture is non-iterative in the sense of Marr [5]: at every time step, the local estimates at a given location are op(cid:173) timal given the information which has already been propagated to that location. We illustrate the algorithm's performance on real images and compare it to several existing methods.
BibTeX
@inproceedings{weiss1996interpreting,
  author = {Yair Weiss},
  title = {{Interpreting Images by Propagating Bayesian Beliefs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1996},
  url = {https://openreview.net/forum?id=HyVxCd-dbS},
}
Figure