Belief Propagation Based Stereo Matching with Due Account of Visibility Conditions

Abstract

Belief propagation based stereo matching algorithms are explored with the main focus on taking account of visibility constraints. This approach approximates the minimum energy solution on graphical models such as Markov Chains, or Markov Random Field (MRF) of disparities. Our approach exploits a symmetric Cyclopean matching model, which accounts for visibility conditions, to construct epipolar pro les which are close to the human perception. Unlike traditional asymmetric matching models, this model can construct disparity maps with respect to the left, right or Cyclopean reference frame, as well as a Cyclopean image of a 3D scene depicted in a stereo pair, simultaneously. We focused on both one-dimensional (1D), and two-dimensional (2D) belief propagation. 1D belief propagation has the advantage of fast computation, and low memory usage, but su ers matching errors due to the lack of vertical information. This algorithm was mapped to Graphics Processing Unit (GPU) using CUDA, to achieve real-time stereo. Our research also uncovered one hidden problem of non-unique solutions. Further research into this problem could lead to new ways to improve the matching accuracy. 2D belief propagation is more memory intensive, and has slower computation speed, but it can achieve high quality results using the powerful 2D message passing, where matching information is passed around the MRF, and decisions are made using all the image information.