Abstract

Generalized Belief Propagation (gbp) has proven to be a promising technique for performing inference on Markov random fields (mrfs). However, its heavy computational cost and large memory re- quirements have restricted its application to problems with small state spaces. We present methods for reducing both run time and storage needed by gbp for a large class of pairwise potentials of the mrf. Fur- ther, we show how the problem of subgraph matching can be formulated using this class of mrfs and thus, solved efficiently using our approach. Our results significantly outperform the state-of-the-art method. We also obtain excellent results for the related problem of matching pictorial structures for ob ject recognition.