In this paper, a parallel stereo matching algorithm is proposed based on belief propagation algorithm to accelerate the matching speed. Firstly, the edge of the image is calculated using an optimized edge computing method, then the image to be matched is cut into several segments by the edge information, and every segment is matched based on belief propagation algorithm in parallel time. Finally, all the segment are assembled into a whole disparity image. The experimental results show that the matching speed has accelerated by 3.51 times that of traditional one in the same disparity quantity, and this method can lay the foundation for the further real-time application.