english >> deutsch Home | UdS | MPI | SB

Wavelet Belief Propagation for Large Scale Inference Problems

WBP Paper


Loopy belief propagation (LBP) is a powerful tool for approximate inference in Markov random fields (MRFs). However, for problems with large state spaces, the runtime costs are often prohibitively high. In this paper, we present a new LBP algorithm that represents all beliefs, marginals, and messages in a wavelet representation, which can encode the probabilistic information much more compactly. Unlike previous work, our algorithm operates solely in the wavelet domain. This yields an output-sensitive algorithm where the running time depends mostly on the information content rather than discretization resolution. We apply the new technique to typical problems with large state spaces such as image matching and wide-baseline optical flow where we observe a signicantly improved scaling behavior with discretization resolution. For large problems, the new technique is signicantly faster than even an optimized spatial domain implementation.

Keywords: belief propagation, wavelet, inference, compression, optimization

Read Paper Paper [preprint version] (~2MB) - 11500 times clicked


R. Lasowski, A. Tevs, M. Wand, H.-P. Seidel "Wavelet Belief Propagation for Large Scale Inference Problems" , CVPR, 2011 [bibtex]