Introduction

 

The correspondence problem in stereo vision concerns the matching of points or other kinds of primitives in two images such that the matched points are the projections of the same point in the scene. The disparity map obtained from the matching stage may then be used to compute the 3D position of the scene points given knowledge about the transformation between the two cameras.

Similarity is the guiding principle for solving the correspondence problem. Corresponding features or areas should be similar in the two images. Because of factors such as noise and occlusion, the appearances of the corresponding points will differ in the two images. For a particular feature in one image, there are usually several matching candidates in the other image. It is usually necessary to use additional information or constraints to assist in obtaining the correct match. Some of the commonly used constraints are:

1. Epipolar constraint: Under this constraint, the matching points must lie on the corresponding epipolar lines of the two images;
2. Uniqueness constraint: Matching should be unique between the two images;
3. Disparity gradient constraint: For certain kinds of 3D surfaces, the disparity gradient should be within a certain limit.

Lotti and Giraudon [1, 2] used a correlation based algorithm with an adaptive window-size that is constrained by an edge map extracted from the image. They presented results on real aerial images. Intille and Bobick [3] presented a stereo algorithm that incorporates the detection of the occlusion regions directly into the matching process. They developed a dynamic programming solution that obeys the occlusion and ordering constraints to find a best path through the disparity-space image. They also used ground control points to eliminate sensitivity to occlusion cost. Xiong et al [4] presented a stereo matching approach which integrates area-based and feature-based processes.

In this paper we address some of the efficient and robust implementation aspects of the stereo matching algorithms by using fast correlation and dynamic programming techniques in a multi-resolution scheme.

The rest of the paper is organised as follows: Section 2 reviews the box filtering techniques and derives the fast correlation method. The detailed matching method is described in Section 3. Section 4 shows the experimental results obtained using our stereo matching method. Section 5 contains concluding remarks.