ETH Zurich - D-INFK - IVC - CVG - People - PhD Students

PhD Students

Christopher Zach
Microsoft Research Cambridge, UK
Christian Häne
ETH Zürich, Switzerland
Marc Pollefeys
ETH Zürich, Switzerland

IEEE Int. Conf. on Computer Vision and Pattern Recognition 2012


In this work we present a unified view on Markov random fields and recently proposed continuous tight convex relaxations for multi-label assignment in the image plane. These relaxations are far less biased towards the grid geometry than Markov random fields. It turns out that the continuous methods are non-linear extensions of the local polytope MRF relaxation. In view of this result a better understanding of these tight convex relaxations in the discrete setting is obtained. Further, a wider range of optimization methods is now applicable to find a minimizer of the tight formulation. We propose two methods to improve the efficiency of minimization. One uses a weaker, but more efficient continuously inspired approach as initialization and gradually refines the energy where it is necessary. The other one reformulates the dual energy enabling smooth approximations to be used for efficient optimization. We demonstrate the utility of our proposed minimization schemes in numerical experiments.


  • Paper and supplementary Material: [PDF]
  • Poster: [PDF]
  • Extended and continuously updated TR: [PDF]


We provide sample code for stereo matching, solving the tight model with the following optimization strategies:

  • First-order primal-dual algorithm on the tight model
  • First-order primal-dual algorithm with iterative refinement of the fast model
  • Fast iterative shrinkage-thresholding algorithm (fista) on the smoothed version of the dual energy
  • Simultaneous-direction method of multipliers (sdmm) on the dual energy

The code is released under the terms of the GNU GPLv3 License. If you use the code for your research please cite the following paper:

C. Zach, C. Häne, M. Pollefeys, What Is Optimized in Tight Convex Relaxations for Multi-Label Problems?, Proc. IEEE Int. Conf. on Computer Vision and Pattern Recognition 2012

  • Sample code for the optimizations: [TAR.GZ]

© CVG, ETH Zürich