Algorithms for discrete energy minimization are of fundamental importance in computer vision.
In this paper we focus on the recent technique proposed by Wainwright et al. [33] -
tree-reweighted max-product message passing (TRW).
It was inspired by the problem of maximizing a lower bound on the energy.
However, the algorithm is not guaranteed to increase this bound - it may actually go down. In addition, TRW does not
always converge. We develop a modification
of this algorithm which we call sequential tree-reweighted message passing. Its main property
is that the bound is guaranteed not to decrease. We also give a weak tree agreement condition
which characterizes local maxima of the bound with respect to TRW algorithms. We prove that
our algorithm has a limit point that achieves weak tree agreement. Finally, we show that our algorithm requires
half as much memory as traditional message passing approaches.
Experimental results demonstrate that on certain synthetic and real problems our algorithm
outperforms both the ordinary belief propagation and tree-reweighted algorithm in [33].
In addition, on stereo problems with Potts interactions we obtain a lower energy than graph cuts.