An Approach for Stereo Matching Using Pair-wise Sequence Alignment Algorithm Based on Dynamic Programming

We present a practical and efficient stereo matching approach which produces a dense disparity map with the pair-wise sequence alignment algorithm based on dynamic programming in this paper. Firstly, pair-wise sequence alignment algorithm based on the dynamic programming is introduced where the optimal alignment of two sequences could be acquired by tracing back the similarity matrix which is constructed according to characters in two sequences using dynamic programming algorithm. Second, we think of pixel gray value of all homonymy epipolar lines in two images in turn as two string sequences, and then disparity of corresponding point in two images is calculated by the number of gaps inserted the optimal alignment in every two string sequences. Additionally, according to epipolar constraint we can know that homonymy epipolar lines in two images parallel to the scan-lines, so the 2D matching of images is simplified to that of 1D. The experiment result shows that the proposed approach is stable and efficient, and it has a high matching accuracy and low computational complexity.