Exact and Approximate Inference in Associative Hierarchical Random Fields using Graph-Cuts

Chris Russell, Lubor Ladicky, Philip Torr, Pushmeet Kohli
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:500-507, 2010.

Abstract

Markov Networks are widely used through out computer vision and machine learning. An important subclass are the Associative Markov Networks which are used in a wide variety of applications. For these networks a good approximate minimum cost solution can be found efficiently using graph cut based move making algorithms such as alpha- expansion. Recently a related model has been proposed, the associative hierarchical net- work, which provides a natural generalisation of the Associative Markov Network for higher order cliques (i.e. clique size greater than two). This method provides a good model for object class segmentation problem in com- puter vision. Within this paper we briefly describe the associative hierarchical network and provide a computationally efficient method for ap- proximate inference based on graph cuts. Our method performs well for networks con- taining hundreds of thousand of variables, and higher order potentials are defined over cliques containing tens of thousands of vari- ables. Due to the size of these problems stan- dard linear programming techniques are in- applicable. We show that our method has a bound of 4 for the solution of general as- sociative hierarchical network with arbitrary clique size noting that few results on bounds exist for the solution of labelling of Markov Networks with higher order cliques.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-russell10a, title = {Exact and Approximate Inference in Associative Hierarchical Random Fields using Graph-Cuts}, author = {Russell, Chris and Ladicky, Lubor and Torr, Philip and Kohli, Pushmeet}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {500--507}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/russell10a/russell10a.pdf}, url = {https://proceedings.mlr.press/r8/russell10a.html}, abstract = {Markov Networks are widely used through out computer vision and machine learning. An important subclass are the Associative Markov Networks which are used in a wide variety of applications. For these networks a good approximate minimum cost solution can be found efficiently using graph cut based move making algorithms such as alpha- expansion. Recently a related model has been proposed, the associative hierarchical net- work, which provides a natural generalisation of the Associative Markov Network for higher order cliques (i.e. clique size greater than two). This method provides a good model for object class segmentation problem in com- puter vision. Within this paper we briefly describe the associative hierarchical network and provide a computationally efficient method for ap- proximate inference based on graph cuts. Our method performs well for networks con- taining hundreds of thousand of variables, and higher order potentials are defined over cliques containing tens of thousands of vari- ables. Due to the size of these problems stan- dard linear programming techniques are in- applicable. We show that our method has a bound of 4 for the solution of general as- sociative hierarchical network with arbitrary clique size noting that few results on bounds exist for the solution of labelling of Markov Networks with higher order cliques.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Exact and Approximate Inference in Associative Hierarchical Random Fields using Graph-Cuts %A Chris Russell %A Lubor Ladicky %A Philip Torr %A Pushmeet Kohli %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-russell10a %I PMLR %P 500--507 %U https://proceedings.mlr.press/r8/russell10a.html %V R8 %X Markov Networks are widely used through out computer vision and machine learning. An important subclass are the Associative Markov Networks which are used in a wide variety of applications. For these networks a good approximate minimum cost solution can be found efficiently using graph cut based move making algorithms such as alpha- expansion. Recently a related model has been proposed, the associative hierarchical net- work, which provides a natural generalisation of the Associative Markov Network for higher order cliques (i.e. clique size greater than two). This method provides a good model for object class segmentation problem in com- puter vision. Within this paper we briefly describe the associative hierarchical network and provide a computationally efficient method for ap- proximate inference based on graph cuts. Our method performs well for networks con- taining hundreds of thousand of variables, and higher order potentials are defined over cliques containing tens of thousands of vari- ables. Due to the size of these problems stan- dard linear programming techniques are in- applicable. We show that our method has a bound of 4 for the solution of general as- sociative hierarchical network with arbitrary clique size noting that few results on bounds exist for the solution of labelling of Markov Networks with higher order cliques. %Z Reissued by PMLR on 04 October 2026.
APA
Russell, C., Ladicky, L., Torr, P. & Kohli, P.. (2010). Exact and Approximate Inference in Associative Hierarchical Random Fields using Graph-Cuts. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:500-507 Available from https://proceedings.mlr.press/r8/russell10a.html. Reissued by PMLR on 04 October 2026.

Related Material