Tightening MRF Relaxations with Planar Subproblems
We describe a new technique for computing 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 constraints are
represented in terms of subproblems 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 outperforms existing methods for some interesting classes
of hard potentials.
Download: pdf
Text Reference
Julian Yarkony, Ragib Morshed, Alex Ihler, and Charless Fowlkes. Tightening mrf relaxations with planar subproblems. In UAI. 2011.BibTeX Reference
@inproceedings{YarkonyMIF_UAI_2011,AUTHOR = "Yarkony, Julian and Morshed, Ragib and Ihler, Alex and Fowlkes, Charless",
TITLE = "Tightening MRF Relaxations with Planar Subproblems",
BOOKTITLE = "UAI",
YEAR = "2011",
TAG = "grouping"
}