Convergent tree reweighted message passing for energy minimization

V. Kolmogorov, IEEE Transactions on Pattern Analysis and Machine Intelligence 28 (2006) 1568–1583.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Abstract
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. (Nov. 2005)- 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 (M. J. Wainwright, et al., Nov. 2005). In addition, on stereo problems with Potts interactions, we obtain a lower energy than graph cuts.
Publishing Year
Date Published
2006-08-21
Journal Title
IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume
28
Issue
10
Page
1568 - 1583
IST-REx-ID

Cite this

Kolmogorov V. Convergent tree reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2006;28(10):1568-1583. doi:10.1109/TPAMI.2006.200
Kolmogorov, V. (2006). Convergent tree reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(10), 1568–1583. https://doi.org/10.1109/TPAMI.2006.200
Kolmogorov, Vladimir. “Convergent Tree Reweighted Message Passing for Energy Minimization.” IEEE Transactions on Pattern Analysis and Machine Intelligence 28, no. 10 (2006): 1568–83. https://doi.org/10.1109/TPAMI.2006.200.
V. Kolmogorov, “Convergent tree reweighted message passing for energy minimization,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 10, pp. 1568–1583, 2006.
Kolmogorov V. 2006. Convergent tree reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence. 28(10), 1568–1583.
Kolmogorov, Vladimir. “Convergent Tree Reweighted Message Passing for Energy Minimization.” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 10, IEEE, 2006, pp. 1568–83, doi:10.1109/TPAMI.2006.200.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar