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

@article{citeulike:3158181, 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.}, author = {Potetz, Brian and Lee, Tai S.}, citeulike-article-id = {3158181}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.cviu.2008.05.007}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S1077314208000878}, citeulike-linkout-2 = {http://www.sciencedirect.com/science/article/B6WCX-4SNGMBD-3/2/978d4220a957b7f9e728fdeb995ba0fc}, doi = {10.1016/j.cviu.2008.05.007}, journal = {Computer Vision and Image Understanding}, keywords = {bayesian, beliefpropagation, graphicalmodels}, posted-at = {2008-08-27 12:38:05}, priority = {2}, title = {Efficient belief propagation for higher-order cliques using linear constraint nodes}, url = {http://dx.doi.org/10.1016/j.cviu.2008.05.007}, volume = {In Press, Corrected Proof} }

TY - JOUR ID - citeulike:3158181 L3 - citeulike-article-id:3158181 N2 - 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. JF - Computer Vision and Image Understanding TI - Efficient belief propagation for higher-order cliques using linear constraint nodes VL - In Press, Corrected Proof KW - bayesian KW - beliefpropagation KW - graphicalmodels AU - Potetz, Brian AU - Lee, Tai UR - http://dx.doi.org/10.1016/j.cviu.2008.05.007 ER -