%0 Journal Article %A Potetz, Brian %A Lee, Tai Sing %D 1966 %T Efficient Belief Propagation for Higher Order Cliques Using Linear Constraint Nodes %U https://kilthub.cmu.edu/articles/journal_contribution/Efficient_Belief_Propagation_for_Higher_Order_Cliques_Using_Linear_Constraint_Nodes/6605066 %R 10.1184/R1/6605066.v1 %2 https://kilthub.cmu.edu/ndownloader/files/12095492 %K Belief propagation %K Higher order cliques %K Non-pairwise cliques %K Factor graphs %K Continuous Markov Random Fields %X 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. %I Carnegie Mellon University