Additional Remarks on Approximate Marginalization for Symmetry Detection

R. Lasowski, A. Tevs , H.-P. Seidel, M. Wand: A Probabilistic Framework for Partial Intrinsic Symmetries in Geometric Data (ICCV 2009).

Since the publication of the paper, we have studied the problem of finding symmetries by computing marginals in Markov Random Fields more in detail. We have found some important aspects that we were not aware of at the time of publication of the original paper but that might be relevant for applying the technique in practice:

A technical key tool in the paper is using sum-product loopy belief propagation for computing approximate marginals. However, it turns out that this algorithm is susceptible to symmetry breaking. If loopy belief propagation is run for an extended time, it is likely to happen that the marginal distributions converge to a uni-modal distribution with only a single peak, discarding the symmetry information. This problem can often (but not always) be avoided by using a rather large convergence threshold for stopping the LBP algorithm. The implementation described in our ICCV 2009 paper does this implicitly, but we were not yet aware of the importance of doing so.

You can find a detailed analysis of the problems of loopy belief propagation in the context of symmetry detection from marginals in Silke Jansen's master thesis available here. The master thesis examines the problem of detecting symmetries in 2D images, were the mentioned problems are particularly clearly observable. The thesis also proposes some solution strategies that reduce the symmetry breaking issues.

We would like to emphasize that this problem is at the side of the inference algorithm, not the probabilistic model itself. We have verified this by using non-loopy graphs as template that are matched to large quantities of geometry. The resulting marginals are very well peaked and give very useful cues for extracting symmtries in practice. No convergence issues are observed in this case, where exact inference is possible. We are currently preparing a more detailed publication on this approach.

Last modified: Michael Wand, September 3rd 2010.