Performance Comparison of Max Product and Minimum Sum Belief Propagation

  • Chitra Suresh Research Scholor Ram Rao Adik Institute of Technology Nerul, Navi Mumbai – 400 706 Adjunct Professor IIT Bombay & AGV Systems Mumbai – 400 076
Keywords: Performance Comparison of Max Product, Max Product, Sum Belief Propagation


The stereo pair image consists of two images of same scene or object taken slightly horizontally separated points from left and right view. The phenomena of parallax effect present in stereo pair image due to above shift object near to the camera appears more to the right in left image whereas more left in right image. The stereo matching / stereo correspondence  technique, finds the horizontal matching pixel in stereo pair is known as disparity whereas for each pixel coordinates is’ Disparity Map’ .There are local and global methods to find ‘Disparity Map’. The global method is based on Bayesian approach which computes ‘Disparity Map’ as minimum energy formulation.

To optimize energy minimization formulation, “Belief Propagation (BP)†method is one of many available inference methods which can be used efficiently. The Belief Propagation (BP) method is based on probability theory ,finds beliefs or marginal probability by passing the messages around possible unknown disparity values. The beliefs or marginal probability can be evaluated either by Maximum A Posteriori (MAP) assignment or using log space. The beliefs or marginal probability findings  based on Maximum A Posteriori(MAP)  estimation is known as Max product  Belief Propagation(BP) whereas based on log space is known as Minimum Sum Belief Propagation(BP).

In this paper we are comparing and analyzing computational parameters of Mean Square Error per pixel and Peak signal Noise Ratio in dB of Disparity Map using Max product Belief Propagation (BP) as well as by Minimum Sum Belief Propagation (BP).Further runtime also analyzed and objects in stereo pair due to depth discontinuities are detected efficiently by Minimum Sum Belief Propagation


[1] Olofsson, Anders. (2010). Modern Stereo Correspondence Algorithms: Investigation and evaluation. Linköping University, Department of Electrical Engineering, Information Coding. (English).
[2] Dan Yuan, F. (2004) Understanding Belief Propagation and it’s Applicatons, Department Of Computer Engineering , University Of California
[3] Patrik Kamencay, Martina Zachariasova ,Martin Brezman ,Roman Jarina, Robert Hudec, Miroslav Benco & Slavomir Matuska. (2012). A New Approach for Disparity Map Estimation from stereo Image Sequences using Hybrid Segmentation Algorithm., International Journal of Modern Engineering Research,2(5),3201-3206.
[4] kuk-Jin Yoon, L. &In Sokweon. (2006). Adaptive support -weight approach for correspondence search.IEEE Transactions on pattern analysis and machine Intelligence, 28(4),650-651.
[5] Zeng-Fu Wang & Zhi-Gang Zheng. (2008). A region based stereo matching algorithm using cooperative optimization.IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, AK,2008,1-8.doi: 10.1109/CVPR.2008.4587456.
[6] Li Cheng &TerryCaellu. Bayesian Stereo matching,Computer vision and Image understanding
[7] Colin Doutre & Panos Nasiopoulos. (2010). A Stereo matching Data cost Robust to Blurring, IEEE 17th International conference on ImageProcessing, Hong Kong.
[8] Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M.F. & Rother, C. (2008). A Comparative Study of Energy Minimization Methods for Markov Random Fields, IEEE Transactions on Pattern Analysis and machine Intelligence, 30(6), 1068-1080.
[9] Nghia Kien Ho. (2017). Notes/Markov Random Field. Loopy Belief Propagation,
[10] Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers,San Mateo, California
[11] Tappen,M.F.& Freeman,W.T. (2003). Comparision of graph cuts with BP for Stereousing identical MRF parameters. CONFERENCE,Date Added to IEEE Xplore: 03 April 2008, Nice, France.doi 10.1109/ICCV.2003.123844410.10007/1234567890
[12] Pedro F.Felzenszwalb, Daniel P.Huttenlocher, F. (2006). A Efficient Belief Propagation For Early Vision. International Journal Of Computer Science,70(1), 41–54.
[13] Sun, J., Shum, H.-Y. & Zheng, N.-N. (2002). Stereo matching using belief propagation. In A. Heyden, G. Sparr, M. Nielsen, and P. Johansen, editors, Computer Vision - ECCV 2002, number 2351 in Lecture Notes in Computer Science, pages 510–524.
[14] Colin Doutre & Panos Nasiopoulos. (2010). A Stereo matching Data cost Robust to Blurring, IEEE 17th International conference on ImageProcessing, Hong Kong.
[15] Somon Hermann& Reinhard Klette, T. (2009). he Naked Truth about cost functions for stereo matching. The enpeda Project, The University of Auckland Auckland, New Zealand.
[16] Birchfield, S. &Tomasi, C. (1998). A pixel dissimilarity measure that is insensitive to image sampling. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(4), 401-406.
[17] Baek, Eu-Tteum & Ho, Yo-Sung. (2016). Occlusion and Error Detection for Stereo Matching and Hole-Filling Using Dynamic Programming. Electronic Imaging, 1-6. 10.2352/ISSN.2470-1173.2016.5.SDA-449.
[18] Gil Ja So, Sang Hyun Kim& Jun Yeop Kim. (2014). The Extraction of Depth Discontinuities Using Disparity Map for Human Visual Fatigue.IJCTE, 6(4), 330-335 ISSN: 1793-8201 DOI: 10.7763/IJCTE.2014.V6.884
[19] Brad Hiebert.Treuer, Sarri.Al Nashashibi & Daniel Scharstein. (2006).