Fast Generalized Belief Propagation for Binocular Stereo Matching

On one hand, generalized belief propagation (GBP) is highly adapted and successfully introduced into stereo matching problem. GBP is a region based belief propagation algorithm which features a good convergence. This paper proposes an idea of min-sum scheme in GBP to replace the traditional max-product messaging scheme and applies it to solve the stereo matching problem. A caching technique is used to improve the access efficiency. Furthermore, two strategies are found to speed up GBP processing. One is the direction set method which is used to reduce the complexity of computing clique
messages from quartic to cubic. The other is hierarchical state space reduction which is proposed to decrease redundant labels in every hierarchical level. Combining these strategies can greatly increase the processing speed. Beside the paper mainly develops the GBP methoditselfto a new stage, it is also the first attempt to apply GBP for solving the stereo matching problem. Experiments show that the proposed algorithm can speed up by 80+ times for typical stereo images and lead to a more accurate result than the canonical GBP. Furthermore, considering the potential parallel computing capability which is an
advantage of such message passing based algorithms, the speed can be further increased even to real-time.

On the other hand, this paper combines the existing global based and local based methods to strengthen their own advantages and weaken their disadvantages. The global based approach mostly makes the result too smooth to include more details, while the local based method makes the result noisier. This paper proposes a novel method which combines the global and local traits as much as possible to fill the gap between them. Firstly, layered result is obtained by graph cut based algorithms. Secondly, several subpixel local results are obtained under global result’s guidance with window correlation method. Thirdly, these local results are repeatedly merged in the Markov Random Fields (MRFs) model with a second order smooth prior energy function. Experiments show that this method can achieve better results than that of either global or local based method
individually.