Tightening MRF relaxations with planar subproblems
Julian Yarkony, Ragib Morshed, Alexander Ihler, Charless C. Fowlkes · 2011
We describe a new technique for comput-ing lower-bounds on the minimum energy configuration of a planar Markov Random Field (MRF). Our method successively adds large numbers of constraints and enforces consistency over binary projections of the original problem state space. These con-straints are represented in terms of subprob-lems in a dual-decomposition framework that is optimized using subgradient techniques. The complete set of constraints we consider enforces cycle consistency over the original graph. In practice we find that the method converges quickly on most problems with the addition of a few subproblems and outper-forms existing methods for some interesting classes of hard potentials. 1