Fast Stereo Matching Using Rectangular Subregioning and 3D Maximum-Surface Techniques

This paper presents a fast and reliable stereo matching algorithm which produces a dense disparity map by using fast cross correlation, rectangular subregioning (RSR) and 3D maximum-surface techniques in a coarse-to-fine scheme. Fast correlation is achieved by using the box-filtering technique whose speed is invariant to the size of the correlation window and by segmenting the stereo images into rectangular subimages at different levels of the pyramid. By working with rectangular subimages, not only can the speed of the correlation be further increased, the intermediate memory storage requirement can also be reduced. The disparity map for the stereo images is found in the 3D correlation coefficient volume by obtaining the global 3D maximum-surface rather than simply choosing the position that gives the local maximum correlation coefficient value for each pixel. The 3D maximum-surface is obtained using our new two-stage dynamic programming (TSDP) technique. There are two original contributions in this paper: (1) development of the RSR technique for fast similarity measure; and (2) development of the TSDP technique for efficiently obtaining 3D maximum-surface in a 3D volume. Typical running time of our algorithm implemented in the C language on a 512 × 512 image is in the order of a few seconds on a 500 MHz PC. A variety of synthetic and real images have been tested, and good results have been obtained.