Report Number: CS-TR-96-1573
Institution: Stanford University, Department of Computer Science
Title: Depth Discontinuities by Pixel-To-Pixel Stereo
Author: Birchfield, Stan
Author: Tomasi, Carlo
Date: July 1996
Abstract: This report describes a two-pass binocular stereo algorithm
that is specifically geared towards the detection of depth
discontinuities. In the first pass, introduced in part I of
the report, stereo matching is performed independently on
each epipolar pair for maximum efficiency. In the second
pass, described in part II, disparity information is
propagated between the scanlines.
Part I. Our stereo algorithm explicitly matches the pixels in
the two images, leaving occluded pixels unpaired. Matching is
based upon intensity alone without utilizing windows. Since
the algorithm prefers piecewise constant disparity maps, it
sacrifices depth accuracy for the sake of crisp boundaries,
leading to precise localization of the depth discontinuities.
Three features of the algorithm are worth noting: (1) unlike
most stereo algorithms, it does not require texture
throughout the images, making it useful in unmodified indoor
settings, (2) it uses a measure of pixel dissimilarity that
is provably insensitive to sampling, and (3) it prunes bad
nodes during the search, resulting in a running time that is
faster than that of standard dynamic programming.
Part II. After the scanlines are processed independently, the
disparity map is postprocessed, leading to more accurate
disparities and depth discontinuities. Both the algorithm and
the postprocessor are fast, producing a dense disparity map
in about 1.5 microseconds per pixel per disparity on a
workstation. Results on five stereo pairs are given.