Event Location: NSH 1507

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 demonstrate this technique in two applications. First,
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. Finally, we
apply these techniques to shape-from-shading and demonstrate significant
improvement over previous methods, both in quality and in flexibility.