Approximate Belief Propagation by Hierarchical Averaging of Outgoing Messages

Abstract—This paper presents an approximate belief prop-agation algorithm that replaces outgoing messages from a node with the averaged outgoing message and propagates messages from a low resolution graph to the original graph hierarchically. The proposed method reduces the computational time by half or two-thirds and reduces the required amount of memory by 60 % compared with the standard belief propa-gation algorithm when applied to an image. The proposed method was implemented on CPU and GPU, and was evaluated against Middlebury stereo benchmark dataset in comparison with the standard belief propagation algorithm. It is shown that the proposed method outperforms the other in terms of both the computational time and the required amount of memory with minor loss of accuracy. Keywords-belief propagation; stereo; GPU; I