Efficient belief propagation for higher-order cliques using linear constraint nodes

Brian Potetz, Tai Sing LeeCVIU 2008 · OpenReview

Abstract

Belief propagation over pairwise-connected Markov random fields has become a widely used approach, and has been successfully applied to several important computer vision problems. However, pairwise interactions are often insufficient to capture the full statistics of the problem. Higher-order interactions are sometimes required. Unfortunately, the complexity of belief propagation is exponential in the size of the largest clique. In this paper, we introduce a new technique to compute belief propagation messages in time linear with respect to clique size for a large class of potential functions over real-valued variables. We discuss how this technique can be generalized to still wider classes of potential functions at varying levels of efficiency. Also, we develop a form of nonparametric belief representation specifically designed to address issues common to networks with higher-order cliques and also to the use of guaranteed-convergent forms of belief propagation. To illustrate these techniques, we perform efficient inference in graphical models where the spatial prior of natural images is captured by 2 × 2 cliques. This approach shows significant improvement over the commonly used pairwise-connected models, and may benefit a variety of applications using belief propagation to infer images or range images, including stereo, shape-from-shading, image-based rendering, segmentation, and matting.
BibTeX
@article{potetz2008efficient,
  author = {Brian Potetz and Tai Sing Lee},
  title = {{Efficient belief propagation for higher-order cliques using linear constraint nodes}},
  journal = {Comput. Vis. Image Underst.},
  year = {2008},
  url = {https://openreview.net/forum?id=YAgxn1lDDAb},
}

Loading related content...

Figure