Efficient Bayesian inference using fully connected conditional random fields with stochastic cliques

Conditional random fields (CRFs) are one of the most powerful frameworks in image modeling. However practical CRFs typically have edges only between nearby nodes; using more interactions and expressive relations among nodes make these methods impractical for large-scale applications, due to the high computational complexity. Recent work has shown that fully connected CRFs can be tractable by defining specific potential functions. In this paper, we present a novel framework to tackle the computational complexity of a fully connected graph without requiring specific potential functions. Instead, inspired by random graph theory and sampling methods, we propose a new clique structure called stochastic cliques. The stochastically fully connected CRF (SFCRF) is a marriage between random graphs and random fields, benefiting from the advantages of fully connected graphs while maintaining computational tractability. The effectiveness of SFCRF was examined by binary image labeling of highly noisy images. The results show that the proposed framework outperforms an adjacency CRF and a CRF with a large neighborhood size.