Depth Discontinuities by Pixel-to-Pixel Stereo: Algorithm Description

In order to provide some intuition regarding the various parts of the stereo algorithm, below is a step-by-step, informal description of computation, using two pairs of images as examples. The details can be found in the paper or technical report.

NOTE: The steps below are given to facilitate understanding the necessity of each aspect of the computation and do not necessarily describe the sequence of steps through which the algorithm proceeds. For example, steps 1, 2, and 3 are all combined into a single step in the final implementation.

INPUT: TWO STEREO IMAGES (Here only the left images are shown).

PART 1: MATCHING SCANLINES INDEPENDENTLY

Step 1. First we match each pair of scanlines independently, using dynamic programming. The cost function attempts to minimize the dissimilarity of the pixel intensities and the number and length of the occlusions:

Step 2. Because of the untextured background, the locations of the changes in disparity are determined largely by noise. To solve this problem, we note that the assumption that depth discontinuities are accompanied by intensity variation necessarily implies that an occlusion in the left (right) scanline must lie immediately to the left (right) of an intensity variation. Adding this constraint yields the following:

Step 3. Although the changes in disparity are now properly placed, there still remain large splotches in the disparity map due to image sampling. Imagine taking the intensity function, shifting it by half a pixel, and resampling -- unless the function is nearly constant the resulting intensities will be quite different (In the situation above, the textured surface of the Clorox bottle is shifted by approximately 7.4 pixels between the two images). To solve this problem we have devised a measure of pixel dissimilarity that is insensitive to image sampling because it compares the intensity of a pixel with the linearly interpolated intensity function surrounding its matching pixel. Using this dissimilarity measure, the disparity maps become clean:

These results are about as good as one can hope to achieve by processing the scanlines independently.

PART 2: PROPAGATING INFORMATION BETWEEN SCANLINES

Step 4. After the scanlines are processed independently, the columns in the disparity map are post-processed independently (this keeps the computation fast). The basic idea is to propagate reliable disparities into regions where the disparity is unreliable, where reliability is determined by the number of contiguous pixels in the column agreeing on their disparity. Propagation stops when an intensity variation is reached. Here is the result:

However, the disparity maps are still incorrect, because they contain long horizontal disparity boundaries where there is no corresponding change in intensity. Such situations violate our assumption that depth discontinuities are accompanied by intensity variation. To solve this problem, we propagate reliable regions into their neighbors until an intensity variation is found, as long as the following condition is met: The disparity of the neighbor must be greater than the disparity of the propagating region by at least two levels. This threshold of two helps to preserve slanted surfaces.

Finally, propagation is repeated in the horizontal direction, followed by median filtering.

FINAL OUTPUT

Here are the final disparity maps

and the depth discontinuities (which are defined as those pixels that border a change of at least two disparity levels):

We see that good results are achieved on difficult images containing untextured, slanted surfaces (The middle Clorox bottle is not found because of the inevitable threshold). For more results, see the image gallery.