Exact and Approximate Inference in Associative Hierarchical Networks using Graph Cuts
Chris Russell, L'ubor Ladicky, Pushmeet Kohli, Philip Torr
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.
PDF Link: /papers/10/p501-russell.pdf
AUTHOR = "Chris Russell
and L'ubor Ladicky and Pushmeet Kohli and Philip Torr",
TITLE = "Exact and Approximate Inference in Associative Hierarchical Networks using Graph Cuts",
BOOKTITLE = "Proceedings of the Twenty-Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-10)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2010",
PAGES = "501--508"