|M. Pawan Kumar|
ENERGY MINIMIZATION FOR LINEAR ENVELOPE MRFs
P. Kohli and M. Pawan Kumar
In Proceedings of Conference on Computer Vision and Pattern Recognition (CVPR), 2010
Markov random fields with higher order potentials have emerged as a powerful model for several problems in computer vision. In order to facilitate their use, we propose a new representation for higher order potentials as upper and lower envelopes of linear functions. Our representation concisely models several commonly used higher order potentials, thereby providing a unified framework for minimizing the corresponding Gibbs energy functions. We exploit this framework by converting lower envelope potentials to standard pairwise functions with the addition of a small number of auxiliary variables. This allows us to minimize energy functions with lower envelope potentials using conventional algorithms such as BP, TRW and $\alpha$-expansion. Furthermore, we show how the minimization of energy functions with upper envelope potentials leads to a difficult min-max problem. We address this difficulty by proposing a new message passing algorithm that solves a linear programming relaxation of the problem. Although this is primarily a theoretical paper, we demonstrate the efficacy of our approach on the binary (fg/bg) segmentation problem.