Globally optimal solutions for energy minimization in stereo vision using reweighted belief propagation
- 1 January 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (15505499) , 428-435 Vol. 1
- https://doi.org/10.1109/iccv.2005.110
Abstract
A wide range of low level vision problems have been formulated in terms of finding the most probable assignment of a Markov random field (or equivalently the lowest energy configuration). Perhaps the most successful example is stereo vision. For the stereo problem, it has been shown that finding the global optimum is NP hard but good results have been obtained using a number of approximate optimization algorithms. In this paper, we show that for standard benchmark stereo pairs, the global optimum can be found in about 30 minutes using a variant of the belief propagation (BP) algorithm. We extend previous theoretical results on reweighted belief propagation to account for possible ties in the beliefs and using these results we obtain easily checkable conditions that guarantee that the BP disparities are the global optima. We verify experimentally that these conditions are typically met for the standard benchmark stereo pairs and discuss the implications of our results for further progress in stereo.Keywords
This publication has 11 references indexed in Scilit:
- Efficient belief propagation for early visionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- On the Uniqueness of Loopy Belief Propagation Fixed PointsNeural Computation, 2004
- What energy functions can be minimized via graph cuts?Published by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- High-accuracy stereo depth maps using structured lightPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Comparison of graph cuts with belief propagation for stereo, using identical MRF parametersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A taxonomy and evaluation of dense two-frame stereo correspondence algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Fast approximate energy minimization via graph cutsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2001
- Fast approximate energy minimization via graph cutsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1999
- A pixel dissimilarity measure that is insensitive to image samplingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1998
- Advanced Inference in Bayesian NetworksPublished by Springer Nature ,1998