5th September 2005 — Vladimir Kolmogorov: Tree-reweighted message passing
Vladimir Kolmogorov is our guest speaker.
Tree-reweighted message passing: advances in discrete energy minimization for computer vision
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. In the first part of the talk I will give 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.
Then I will discuss some optimality properties of max-product TRW, and I’ll show how they relate to graph cuts. This part of the talk is a joint work with M. Wainwright.