A DYNAMIC-PROGRAMMING APPROACH TO LINE SEGMENT MATCHING IN STEREO VISION

The main purpose of stereo vision analysis is to recover the range (depth) information of objects in a three-dimensional (3D) scene based on a binocular image pair taken from two distinct views. Stereo matching (correspondence) is the key step in stereo vision analysis. There exist two general types of stereo matching, namely, intensity-based (area-based) matching and feature-based matching. In this study, by the use of the idea of searching relational graphs, a dynamic programming approach to line segment (feature-based) matching in stereo vision is proposed. Incorporating the divide-and-conquer strategy and the feature stability concept, the proposed approach is simple, but effective, as compared with the other existing approaches. In the proposed approach, by the use of the divide-and-conquer strategy, the line segments in the left image L are first partitioned, based on their orientations, into two sets: L(nh) (nonhorizontal) and L(h) (nearly horizontal), and then the nonhorizontal line segments in L(nh) and their potential matching line segments in the right image R are clustered into K similar groups, L(nh)(k) and R(nh)(k), k = 1, 2,..., K, respectively. The stereo matchings of the nonhorizontal line segments between L(nh)(k) and R(nh)(k) are determined by finding the maximal weighted path on the associated potential matching multistage graph PMMG. And by the use of the feature stability concept, the stereo matchings of the nearly horizontal line segments in L(h) are similarly determined based on the structural relationships between the matched nonhorizontal line segments and the nearly horizontal line segments. Some experimental results show the feasibility of the proposed approach.