Tightening MRF Relaxations with Planar Subproblems

Julian Yarkony, Ragib Morshed, Alexander T. Ihler, Charless C. Fowlkes
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:848-855, 2011.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-yarkony11b, title = {Tightening {MRF} Relaxations with Planar Subproblems}, author = {Yarkony, Julian and Morshed, Ragib and Ihler, Alexander T. and Fowlkes, Charless C.}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {848--855}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/yarkony11b/yarkony11b.pdf}, url = {https://proceedings.mlr.press/r9/yarkony11b.html}, abstract = {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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Tightening MRF Relaxations with Planar Subproblems %A Julian Yarkony %A Ragib Morshed %A Alexander T. Ihler %A Charless C. Fowlkes %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-yarkony11b %I PMLR %P 848--855 %U https://proceedings.mlr.press/r9/yarkony11b.html %V R9 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Yarkony, J., Morshed, R., Ihler, A.T. & Fowlkes, C.C.. (2011). Tightening MRF Relaxations with Planar Subproblems. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:848-855 Available from https://proceedings.mlr.press/r9/yarkony11b.html. Reissued by PMLR on 04 October 2026.

Related Material