@inproceedings{5828,
  title = {Global Connectivity Potentials for Random Field Models},
  journal = {Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2009)},
  booktitle = {CVPR 2009},
  abstract = {Markov random field (MRF, CRF) models are popular in
  computer vision. However, in order to be computationally
  tractable they are limited to incorporate only local interactions
  and cannot model global properties, such as connectedness,
  which is a potentially useful high-level prior
  for object segmentation. In this work, we overcome this
  limitation by deriving a potential function that enforces the
  output labeling to be connected and that can naturally be
  used in the framework of recent MAP-MRF LP relaxations.
  Using techniques from polyhedral combinatorics, we show
  that a provably tight approximation to the MAP solution of
  the resulting MRF can still be found efficiently by solving
  a sequence of max-flow problems. The efficiency of the inference
  procedure also allows us to learn the parameters
  of a MRF with global connectivity potentials by means of a
  cutting plane algorithm. We experimentally evaluate our algorithm
  on both synthetic data and on the challenging segmentation
  task of the PASCAL VOC 2008 data set. We show
  that in both cases the addition of a connectedness prior significantly
  reduces the segmentation error.},
  pages = {818-825},
  publisher = {IEEE Service Center},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Piscataway, NJ, USA},
  month = jun,
  year = {2009},
  slug = {5828},
  author = {Nowozin, S. and Lampert, CH.},
  month_numeric = {6}
}