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 the 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 significantly improved scaling behavior with discretization resolution. For large problems, the new technique is significantly faster than even an optimized spatial domain implementation.

In this paper, we present a novel algorithm for partial intrinsic symmetry detection in 3D geometry. Unlike previous work, our algorithm is based on a conceptually simple and straightforward probabilistic formulation of partial shape matching: based on a Markov random field model, we obtain a probability distribution over all possible intrinsic matches of a shape to itself, which reveals the symmetry structure of the object. Rather than examining this exponentially sized distribution directly, which is infeasible, we approximate marginals of this distribution using sum-product loopy belief propagation and show how the symmetry information can subsequently be extracted from this condensed representation. Using a parallel implementation on graphics hardware, we are able to extract symmetries of deformable shapes in general poses efficiently. We apply our algorithm on several standard 3D models, demonstrating that a concise probabilistic model yields a practical and general symmetry detection algorithm.