Algorithms for MAP estimation in MRFs (or, alternatively, for minimizing energy functions of discrete variables) are now routinely used in computer vision. Minimization techniques based on graph cuts are probably the most popular ones; they often outperform other algorithms and give state-of-the art results for many problems.

In this talk I will concentrate on an alternative minimization algorithm tree-reweighted max-product message passing (TRW) introduced recently by Wainwright et al. I will present some new developments which show that TRW is a serious competitor to graph cuts.

The algorithm of Wainwright et al. gives strong results in practice, but unfortunately it is not guaranteed to converge. I will present a new algorithm called TRW-S which is related to TRW but has guaranteed convergence properties. Experimental results demonstrate that on a real stereo problem TRW-S significantly outperforms the algorithm of Wainwright et al. and obtains lower energy than graph cuts and max-product belief propagation.