A self-adaptive hierarchical belief propagation algorithm

doi:10.7523/j.issn.2095-6134.2011.5.010

Abstract

Abstract:

We propose a self-adaptive algorithm with convergence detection to reduce the computational complexity of HBP. In the conventional HBP, the computational complexity linearly increases with specified iteration upper bound. We introduce convergence detection to stop the iteration of messages which have already converged to optimal values. Experimental results show that the self-adaptive algorithm reduces computational time by 38% or more, and the computational time is insensitive to iteration upper bound. The convergence detection methodology can be used in other HBP-related applications.

Key words: belief propagation, self-adaptive, stereo match, restoration

CLC Number:

TP391.4

CHI Ling-Hong, GUO Li, YU Li, CHEN Yun-Bi. A self-adaptive hierarchical belief propagation algorithm[J]. , 2011, 28(5): 630-635.

References

[1] Szeliski R, Zabih R, Scharstein D, et al. A comparative study of energy minimization methods for Markov random fields with smoothness-based priors
[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008,30(6): 1068-1080.

[2] Felzenszwalb P F, Huttenlocher D P. Efficient belief propagation for early vision
[J]. International Journal of Computer Vision, 2006,70(1):41-54.

[3] Brunton A, Chang S, Roth G. Belief propagation on the GPU for stereo vision //the 3rd Canadian Conference on Computer and Robot Vision, 2006:76-82.

[4] Yang Q, Wang L, Yang R, et al. Real-time global stereo matching using hierarchical belief propagation //British Machine Vision Conference(BMVC). 2006:989-998.

[5] Grauer-Gray S, Kambhamettu C, Palaniappan K. GPU implementation of belief propagation using CUDA for cloud tracking and reconstruction // IAPR Workshop on Pattern Recognition in Remote Sensing (PRRS 2008). 2008:1-4.

[6] Liang C K, Cheng C C, Lai Y C, et al. Hardware-efficient belief propagation // IEEE Conference on Computer Vision and Pattern Recognition(CVPR 2009). 2009:80-87.

[7] Grauer-Gray S, Kambhamettu C. Hierarchical belief propagation to reduce search space using CUDA for stereo and motion estimation //2009 Workshop on Applications of Computer Vision (WACV). 2009:1-8.

[8] Ihler A, Fisher J, Willsky A, Loopy belief propagation: Convergence and effects of message errors
[J]. Journal of Machine Learning Research, 2006,6(1): 905-936.

[9] Sun J, Zheng N N, Shum H Y. Stereo matching using belief propagation
[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003,25(7): 787-800.

[10] Scharstein D, Szeliski R. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms
[J]. International Journal of Computer Vision, 2002,47(1-3): 7-42.

[11] Yu L, Guo L, Yuan H X, A novel method of stereo matching based on hierarchical belief-propagation
[J]. Journal of Image and Graphics, 2011,16(1):103-109(in Chinese). 郁理,郭立,袁红星. 基于分级置信度传播的立体匹配新方法
[J]. 中国图像图形学报, 2011,16(1):103-109.