Stereo Matching Algorithm Using a Simplified Trellis Diagram Iteratively and Bi-Directionally

Tran Thai SON  Seiichi MITA  

IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.1   pp.314-325
Publication Date: 2006/01/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.1.314
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Image Recognition, Computer Vision
Viterbi algorithm,  stereo correspondence image,  occlusion region,  disparity,  trellis diagram,  epipolar line,  

Full Text: PDF(1.5MB)>>
Buy this Article

This paper presents an approach that uses the Viterbi algorithm in a stereo correspondence problem. We propose a matching process which is visualized as a trellis diagram to find the maximum a posterior result. The matching process is divided into two parts: matching the left scene to the right scene and matching the right scene to the left scene. The last result of stereo problem is selected based on the minimum error for uniqueness by a comparison between the results of the two parts of matching process. This makes the stereo matching possible without explicitly detecting occlusions. Moreover, this stereo matching algorithm can improve the accuracy of the disparity image, and it has an acceptable running time for practical applications since it uses a trellis diagram iteratively and bi-directionally. The complexity of our proposed method is shown approximately as O(N2P), in which N is the number of disparity, and P is the length of the epipolar line in both the left and right images. Our proposed method has been proved to be robust when applied to well-known samples of stereo images such as random dot, Pentagon, Tsukuba image, etc. It provides a 95.7 percent of accuracy in radius 1 (differing by 1) for the Tsukuba images.