Optimizing Binary MRFs with Higher Order Cliques

Abstract

Widespread use of efficient and successful solutions of Computer Vision problems based on pairwise Markov Random Field (MRF) models raises a question: does any link exist between the pairwise and higher order MRFs such that the like solutions can be applied to the latter models? This work explores such a link for binary MRFs that allow us to represent Gibbs energy of signal interaction with a polynomial function. We show how a higher order polynomial can be efficiently transformed into a quadratic function. Then energy minimization tools for the pairwise MRF models can be easily applied to the higher order counterparts. Also, we propose a method to analytically estimate the potential parameter of the asymmetric Potts prior. The proposed framework demonstrates very promising experimental results of image segmentation and can be used to solve other Computer Vision problems.