@InProceedings{Kohli-Shekhovtosv-Rother-Kolmogorov-Torr-08-ICML,
  IS = { zkontrolovano 19 Jan 2009 },
  UPDATE  = { 2008-06-24 },
  author =      {Kohli, Pushmeet and Shekhovtsov, Alexander and 
                 Rother, Carsten and Kolmogorov, Vladimir and 
                 Torr, Philip},
  title =       {On Partial Optimality in Multi-label {MRF}s},
  pages =       {8},
  booktitle =   {ICML 2008: Proceedings of the 25th International
                 Conference on Machine Learning},
  venue =       {Helsenki, Finland},
  year =        {2008},
  month =       {July},
  day =         {5--9},
  publisher =   {ACM},
  address =     {New York, USA},
  isbn =        {978-1-60558-205-4},
  book_pages=   {1203},
  annote = {We consider the problem of optimizing multi-label MRFs,
    which is in general NP-hard and ubiquitous in low-level computer
    vision. One approach for its solution is to formulate it as an
    integer linear programming and relax the integrality
    constraints. The approach we consider in this paper is to first
    convert the multi-label MRF into an equivalent binary-label MRF
    and then to relax it. The resulting relaxation can be efficiently
    solved using a maximum flow algorithm. Its solution provides us
    with a partially optimal labelling of the binary variables. This
    partial labelling is then easily transferred to the multi-label
    problem. We study the theoretical properties of the new relaxation
    and compare it with the standard one. Specifically, we compare
    tightness, and characterize a subclass of problems where the two
    relaxations coincide. We propose several combined algorithms
    based on the technique and demonstrate their performance on
    challenging computer vision problems.},
  keywords =    {Energy minimization, MRF, Partial CSP, labeling, 
                 min-sum, persistency, partial optimality},
  authorship =  {40-40-5-10-5},
  project =     {ICT-215078 DIPLECS, MSM6840770038, EPSRC, PASCAL},
  prestige    = { important },
  note        = { CD-ROM },
 }