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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Globally optimal solutions for energy minimization in stereo vision using reweighted belief propagation


    Contributors:
    Meltzer, T. (author) / Yanover, C. (author) / Weiss, Y. (author)


    Publication date :

    2005-01-01


    Size :

    471835 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Globally Optimal Solutions for Energy Minimization in Stereo Vision Using Reweighted Belief Propagation

    Meltzer, T. / Yanover, C. / Weiss, Y. et al. | British Library Conference Proceedings | 2005



    Fast pixelwise road inference based on Uniformly Reweighted Belief Propagation

    Passani, Mario / Yebes, J. Javier / Bergasa, Luis M. | IEEE | 2015


    Dense photometric stereo using tensorial belief propagation

    Kam-Lun Tang, / Chi-Keung Tang, / Tien-Tsin Wong, | IEEE | 2005


    Acyclic belief propagation for stereo matching

    Piovano, L. / Balossino, N. / Lucenteforte, M. et al. | British Library Online Contents | 2009