Stereo Matching with Transparency and Matting.
This paper formulates and solves a new variant of the stereo correspondence problem: simultaneously recovering the disparities, true colors, and opacities of visible surface elements. This problem arises in newer applications of stereo reconstruction, such as view interpolation and the layering of real imagery with synthetic graphics for special effects and virtual studio applications. While this problem is intrinsically more difficult than traditional stereo correspondence, where only the disparities are being recovered, it provides a principled way of dealing with commonly occurring problems such as occlusions and the handling of mixed (foreground/background) pixels near depth discontinuities. It also provides a novel means for separating foreground and background objects (matting), without the use of a special blue screen. We formulate the problem as the recovery of colors and opacities in a generalized 3D (x, y, d) disparity space, and solve the problem using a combination of initial evidence aggregation followed by iterative energy minimization.
Introduction
Stereo matching has long been one of the central research problems in computer vision. Early
work was motivated by the desire to recover depth maps and shape models for robotics and
object recognition applications. More recently, depth maps obtained from stereo have been
painted with texture maps extracted from input images in order to create realistic 3-D scenes
and environments for virtual reality and virtual studio applications [MB95, SK95, K
96]. Unfortunately, the quality and resolution of most stereo algorithms falls quite short
of that demanded by these new applications, where even isolated errors in the depth map
become readily visible when composited with synthetic graphical elements.
One of the most common errors made by most stereo algorithms is a systematic "fatten-
ing" of depth layers near occlusion boundaries. Algorithms based on variable window sizes
[KO94] or iterative evidence aggregation [SS96] can in many instances mitigate such errors.
Another common problem is that disparities are only estimated to the nearest pixel, which is
typically not su#ciently accurate for tasks such as view interpolation. Di#erent techniques
have been developed for computing sub-pixel estimates, such as using a finer set of disparity
hypotheses or finding the the analytic minimum of the local error surface [TH86, MSK89].
Unfortunately, for challenging applications such as z-keying (the insertion of graphics
between di#erent depth layers in video) [PW94, K 96], even this is not good enough.
Pixels lying near or on occlusion boundaries will typically be mixed, i.e., they will contain
blends of both foreground and background colors. When such pixels are composited with
other images or graphical elements, objectionable "halos" or "color bleeding" may be visible.
The computer graphics and special e#ects industries faced a similar problem when extracting
foreground objects using blue screen techniques [SB96]. A variety of techniques
were developed for this matting problem, all of which model mixed pixels as combinations
of foreground and background colors (the latter of which is usually assumed to be known).
Practitioners in these fields quickly discovered that it is insu#cient to merely label pixels as
foreground and background: it is necessary to simultaneously recover both the true color of
each pixel and its transparency or opacity [PD84, Bli94a].
In this paper, we develop a new, multiframe stereo algorithm which simultaneously recovers
depth, color, and transparency estimates at each pixel. Unlike traditional blue-screen
matting, we cannot use a known background color to perform the color and matte recovery.
Instead, we explicitly model a 3-D (x, y, d) disparity space, where each cell has an associated
color and opacity value. Our task is to estimate the color and opacity values which best
predict the appearance of each input image, using prior assumptions about the (piecewise-)
continuity of depths, colors, and opacities to make the problem well posed. To our knowl-
edge, this is the first time that the simultaneous recovery of depth, color, and opacity from
stereo images has been attempted.
We begin this paper with a review of previous work in stereo matching. In Section 3, we
discuss our novel representation for accumulating color samples in a generalized disparity
space. We then describe how to compute an initial estimate of the disparities (Section 4),
and how to refine this estimate by taking into account occlusions (Section 5). In Section
6, we develop a novel energy minimization algorithm for estimating disparities, colors and
opacities. We present some experiments on both synthetic and real images in Section 7. We
conclude the paper with a discussion of our results, and a list of topics for future research.
Previous Work
Stereo matching (and the more general problem of stereo-based 3-D reconstruction) are
fields with very rich histories [BF82, DA89]. In this section, we focus only on previous work
related to our central topics of interest: pixel-accurate matching with sub-pixel precision,
the handling of occlusion boundaries, and the use of more than two images. We also mention
techniques used in computer graphics to composite images with transparencies and to recover
matte (transparency) values using traditional blue-screen techniques.
In thinking about stereo algorithms, we have found it useful to subdivide the stereo
matching process into three tasks: the initial computation of matching costs, the aggregation
of local evidence, and the selection or computation of a disparity value for each pixel [SS96].
The most fundamental element of any correspondence algorithm is a matching cost that
measures the similarity of two or more corresponding pixels in di#erent images. Matching
costs can be defined locally (at the pixel level), e.g., as absolute [K + 96] or squared intensity
di#erences [MSK89], using edges [Bak80] or filtered images [JJT91, JM92]. Alternatively,
matching costs may be defined over an area, e.g., using correlation [RGH80] (this can be
viewed as a combination of the matching and aggregation stages). In this paper, we use
squared intensity di#erences.
Aggregating support is necessary to disambiguate potential matches. A support region
can either be two-dimensional at a fixed disparity (favoring fronto-parallel surfaces), or
three-dimensional in (x, y, d) space (allowing slanted surfaces). Two-dimensional evidence
aggregation has been done using both fixed square windows (traditional) and windows with
adaptive sizes [Arn83, KO94]. Three-dimensional support functions include limited disparity
gradient [PMF85], Prazdny's coherence principle [Pra85] (which can be implemented using
two di#usion processes [SH85]), local winner-take-all [YYL93], and iterative (non-linear)
evidence aggregation [SS96]. In this paper, our initial evidence aggregation uses an iterative
technique, with estimates being refined later through a prediction/adjustment mechanism
which explicitly models occlusions.
The easiest way of choosing the best disparity is to select at each pixel the minimum
aggregated cost across all disparities under consideration ("winner-take-all"). A problem
with this is that uniqueness of matches is only enforced for one image (the reference image),
while points in the other image might get matched to multiple points. Cooperative algorithms
employing symmetric uniqueness constraints are one attempt to solve this problem [MP76].
In this paper, we will introduce the concept of a virtual camera which is used for the initial
winner-take-all stage.
Occlusion is another very important issue in generating high-quality stereo maps. Many
approaches ignore the e#ects of occlusion; others try to minimize them by using a cyclopean
disparity representation [Bar89], or try to recover occluded regions after the matching by
cross-checking [Fua93]. Several authors have addressed occlusions explicitly, using Bayesian
models and dynamic programming [Arn83, OK85, BM92, Cox94, GLY92, IB94]. However,
such techniques require the strict enforcement of ordering constraints [YP84]. In this pa-
per, we handle occlusion by re-projecting the disparity space into each input image using
traditional back-to-front compositing operations [PD84], and eliminating from consideration
pixels which are known to be occluded. related technique, developed concurrently with
ours, traverses the disparity space from front to back [SD97].)
Sub-pixel (fractional) disparity estimates, which are essential for applications such as
view interpolation, can be computed by fitting a curve to the matching costs at the discrete
disparity levels [LK81, TH86, MSK89, KO94]. This provides an easy way to increase the
resolution of a stereo algorithm with little additional computation. However, to work well,
the intensities being matched must vary smoothly. In this paper, we present two di#erent
representations for fractional disparity estimates.
Multiframe stereo algorithms use more than two images to increase the stability of the
algorithm [BBM87, MSK89, KWZK95, Col96]. In this paper, we present a new framework
for formulating the multiframe stereo problem based on the concept of a virtual camera and
a projective generalized disparity space, which includes as special cases the multiple baseline
stereo models of [OK93, KWZK95, Col96].
Finally, the topic of transparent surfaces has not received much study in the context
of computational stereo [Pra85, SH85, Wei89]. Relatively more work has been done in
the context of transparent motion estimation [BBHP92, SM91b, SM91a, JBJ96, DP91].
However, these techniques are limited to extracting a small number of dominant motions or
planar surfaces. None of these techniques explicitly recover a per-pixel transparency value
along with a corrected color value, as we do in this paper.
Our stereo algorithm has also been inspired by work in computer graphics, especially in
image compositing [PD84, Bli94a] and blue screen techniques [VT93, SB96]. While traditional
blue-screen techniques assume that the background is of a known color, we solve for
the more di#cult case of each partially transparent surface pixel being the combination of
two (or more) unknown colors.
3 Disparity space representation
To formulate our (potentially multiframe) stereo problem, we use a generalized disparity
space which can be any projective sampling (collineation) of 3-D space. More concretely, we
first choose a virtual camera position and orientation. This virtual camera may be coincident
with one of the input images, or it can be chosen based on the application demands and
the desired accuracy of the results. For instance, if we wish to regularly sample a volume
of 3-D space, we can make the camera orthographic, with the camera's (x, y, d) axes being
orthogonal and evenly sampled (as in [SD97]). As another example, we may wish to use a
skewed camera model for constructing a Lumigraph [GGSC96].
Having chosen a virtual camera position, we can also choose the orientation and spacing
of the disparity planes, i.e., the constant d planes. The relationship between d and 3-D
space can be projective. For example, we can choose d to be inversely proportional to
depth, which is the usual meaning of disparity [OK93]. The information about the virtual
camera's position and disparity plane orientation and spacing can be captured in a single
which represents a collineation of 3-D space. The matrix -
M 0 can also
capture the sampling information inherent in our disparity space, e.g, if we define disparity
space (x, y, d) to be an integer valued sampling of the mapping -
point in 3-D (Euclidean) space.
An example of a possible disparity space representation is the standard epipolar geometry
for two or more cameras placed in a plane perpendicular to their optical axes, in which case
a natural choice for disparity is inverse depth (since this corresponds to uniform steps in
displacements, i.e., the quantity which can be measured accurately) [OK93].
Other choices include the traditional cyclopean camera placed symmetrically between two
verged cameras, or a uniform sampling of 3-D which is useful in a true verged multi-camera
environment [SD97] or for motion stereo. Note that in all of these situations, integral steps
in disparity may correspond to fractional shifts in displacement, which may be desirable for
optimal accuracy.
Regardless of the disparity space selected, it is always possible to project each of the input
images onto the through a simple homography (2-D perspective transform),
and to work with such re-projected (rectified) images as the inputs to the stereo algorithm.
What are the possible advantages of such a rectification step? For two or more cameras whose
optical centers are collinear, it is always possible to find a rectification in which corresponding
epipolar lines are horizontal, greatly simplifying the stereo algorithm's implementation. For
three or more cameras which are coplanar, after rectification, displacements away from the
(i.e., changes in disparity) will correspond to uniform steps along fixed directions
for each camera (e.g., horizontal and vertical under a suitable camera geometry). Finally,
for cameras in general position, steps in disparity will correspond to zooms (scalings) and
sub-pixel shifts of the rectified images, which is quicker (and potentially more accurate)
than general perspective resampling [Col96]. A potential disadvantage of pre-rectification is
a slight loss in input image quality due to multiple re-samplings, but this can be mitigated
using higher-order (e.g., bicubic) sampling filters, and potentially re-sampling the rectified
images at higher resolution. Appendix A derives the equations for mapping between input
image (both rectified and not) and disparity space.
In this paper, we introduce a generalization of the (x, y, d) space. If we consider each
of the images as being samples along a fictitious "camera" dimension, we end
up with a 4-D (x, y, d, space. In this space, the values in a given (x, y, d) cell as k varies
can be thought of as the color distributions at a given location in space, assuming that this
location is actually on the surface of the object. We will use these distributions as the inputs
to our first stage of processing, i.e., by computing mean and variance statistics. A di#erent
slice through (x, y, d, k) space, this time by fixing k, gives the series of shifted images seen
by one camera. In particular, compositing these images in a back-to-front order, taking into
account each voxel's opacity, should reconstruct what is seen by a given (rectified) input
image (see Section 5). 1

Figure

1 shows a set of sample images, together with an (x, d, slice through the 4-D
1 Note that this 4-D space is not the same as that used in the Lumigraph [GGSC96], where the description
is one of rays in 3-D, as opposed to color distributions across multiple cameras in 3-D. It is also not the same
as an epipolar-plane image (EPI) volume [BBM87], which is a simple concatenation of warped input images.
space (y is fixed at a given scanline), where color samples varying in k are grouped together.
4 Estimating an initial disparity surface
The first step in stereo matching is to compute some initial evidence for a surface existing
at (or near) a location (x, y, d) in disparity space. We do this by conceptually populating
the entire 4-D (x, y, d, space with colors obtained by resampling the K input images,
c(x, y, d,
where c k (u, v) is the kth input image, 2 H k +t k [0 0 d] is the homography mapping this image
to disparity plane d (see Appendix A), W f is the forward warping operator, 3 and c(x, y, d,
is the pixel mapped into the 4-D generalized disparity space. Algorithmically, this can be
achieved either by first rectifying each image onto the plane, or by directly using a
homography (planar perspective transform) to compute each (d, Note that at this
stage, not all (x, y, d, cells will be populated, as some of these may map to pixels which
are outside some of the input images.
Once we have a collection of color (or luminance) values at a given (x, y, d) cell, we can
compute some initial statistics over the K (or fewer) colors, e.g., the sample mean - and
variance #. 5 Robust estimates of sample mean and variance are also possible (e.g., [SS96]).
Examples of the mean and variance values for our sample image are shown in Figures 1d
and 1e, where darker values indicate smaller variances.
After accumulating the local evidence, we usually do not have enough information to
determine the correct disparities in the scene (unless each pixel has a unique color). While
2 The color values c can be replaced with gray-level intensity values without a#ecting the validity of our
analysis.
3 In our current implementation, the warping (resampling) algorithm uses bi-linear interpolation of the
pixel colors and opacities.
4 For certain epipolar geometries, even more e#cient algorithms are possible, e.g., by simply shifting along
epipolar lines [K
5 In many traditional stereo algorithms, it is common to e#ectively set the mean to be just the value in one
image, which makes these algorithms not truly multiframe [Col96]. The sample variance then corresponds
to the squared di#erence or sum of squared di#erences [OK93].
x
(a) (b) (c)
x
x
x
(d) (e) (f)

Figure

1: Sample slices through a 4-D disparity space: (a-b) sample input images (arranged
slice for scanline 17, (d) means and (e) variances as a function
of (x, d) (smaller variances are darker), (f) variances after evidence accumulation, (g) results
of winner-takes-all for whole image (undecided columns in white), (h-i) colors and opacities
at disparities 1 and 5. For easier interpretation, all images have been composited over an
opaque white background.
pixels at the correct disparity should in theory have zero variance, this is not true in the
presence of image noise, fractional disparity shifts, and photometric variations (e.g., specu-
larities). The variance may also be arbitrarily high in occluded regions, where pixels which
actually belong to a di#erent disparity level will nevertheless vote, often leading to gross
errors. For example, in Figure 1c, the middle (red) group of pixels at should all have
the same color in any given column, but they do not because of resampling errors. This
e#ect is especially pronounced near the edge of the red square, where the red color has been
severely contaminated by the background blue. This contamination is one of the reasons
why most stereo algorithm make systematic errors in the vicinity of depth discontinuities.
To help disambiguate matches, we can use local evidence aggregation. The most common
form is averaging using square windows, which results in the traditional sum of squared
di#erence (SSD and SSSD) algorithms [OK93]. To obtain results with better quality near
discontinuities, it is preferable to use adaptive windows [KO94] or iterative evidence accumulation
[SS96]. In the latter case, we may wish to accumulate an evidence measure which
is not simply summed error (e.g., the probability of a correct match [SS96]). Continuing our
simple example, Figure 1f shows the results of an evidence accumulation stage, where more
certain depths are darker. To generate these results, we aggregate evidence using a variant
of the algorithm described in [SS96],
i is the variance of pixel i at iteration t, - # t
i is a robustified (limited) version of the
variance, and N 4 are the usual four nearest neighbors. For the results in Figure 1, we use
At this stage, most stereo matching algorithms pick a winning disparity in each (x, y)
column, and call this the final correspondence map. Optionally, they may also compute a
fractional disparity value by fitting an analytic curve to the error surface around the winning
disparity and then finding its minimum [MSK89, OK93]. Unfortunately, this does nothing
to resolve several problems: occluded pixels may not be handled correctly (since they have
"inconsistent" color values at the correct disparity), and it is di#cult to recover the true
(unmixed) color values of surface elements (or their opacities, in the case of pixels near
discontinuities).
Our solution to this problem is to use the initial disparity map as the input to a refinement
stage which simultaneously estimates the disparities, colors, and opacities which best match
the input images while conforming to some prior expectations on smoothness. To start this
procedure, we initially pick only winners in each column where the answer is fairly certain,
i.e., where the variance ("scatter" in color values) is below a threshold and is a clear winner
with respect to the other candidate disparities. 6 A new (x, y, d) volume is created, where
each cell now contains a color value, initially set to the mean color computed in the first
stage, and the opacity is set to 1 for cells which are winners, and 0 otherwise. 7
Computing visibilities through re-projection
Once we have an initial (x, y, d) volume containing estimated RGBA (color and 0/1 opac-
ity) values, we can re-project this volume into each of the input cameras using the known
transformation
(see (14) in

Appendix

A), where - x 0 is a (homogeneous) coordinate in (x, y, d) space, -
M 0 is the
complete camera matrix corresponding to the virtual camera, M k is the kth camera matrix,
and x k are the image coordinates in the kth image. There are several techniques possible for
performing this projection, including classical volume rendering techniques [Lev90, LL94]. In
our approach, we interpret the (x, y, d) volume as a set of (potentially) transparent acetates
stacked at di#erent d levels. Each acetate is first warped into a given input camera's frame
6 To account for resampling errors which occur near rapid color or luminance changes, we set the threshold
proportional to the local image variation within a 3 - 3 window. In our experiments, the threshold is set to
7 We may, for computational reasons, choose to represent this volume using colors premultiplied by their
opacities (associated colors [PD84, Bli94a]), in which case voxels for which alpha (opacity) is 0 should have
their color or intensity values set to 0. See [Bli94a, Bli94b] for a discussion of the advantages of using
premultiplied colors.
using the known homography
and the layers are then composited back-to-front (this is called a shear-warp algorithm
[LL94]). 8
The resampling procedure for a given layer d into the coordinate system of camera k can
be written as
y,
is the current color and opacity estimate at a given location (x, y, d), - c k
is the resampled layer d in camera k's coordinate system, and W b is the resampling operation
induced by the homography (4). 9 Note that the warping function is linear in the colors and
opacities being resampled, i.e., the - c k (u, v, d) can be expressed as a linear function of the
c(x, y, d), e.g., through a sparse matrix multiplication.
Once the layers have been resampled, they are then composited using the standard over
operator [PD84],
where f and b are the premultiplied foreground and background colors, and # f is the opacity
of the foreground [PD84, Bli94a]. Using the over operator, we can form a composite image
d min
(note that the over operator is associative but not commutative, and that d max is the layer
closest to the camera).
After the re-projection step, we refine the disparity estimates by preventing visible surface
pixels from voting for potential disparities in the regions they occlude. More precisely, we
build an (x, y, d, visibility map, which indicates whether a given camera k can see a voxel
at location (x, y, d). A simple way to construct such a visibility map is to record the disparity
8 If the input images have been rectified, or under certain imaging geometries, this homography will be a
simple scale and/or shift (Appendix A).
9 This is the inverse of the warp specified in (1).
value d top for each (u, v) pixel which corresponds to the topmost opaque pixel seen during
the compositing step. 10 The visibility value can then be defined as
The visibility and opacity (alpha) values taken together can be interpreted as follows:
voxel visible in image k
voxel not visible in image k
A more principled way of defining visibility, which takes into account partially opaque
voxels, uses a recursive front-to-back algorithm
with the initial visibilities all being set to 1, V k (u, v, d 1. We now have a very simple
(linear) expression for the compositing operation,
d=d min
Once we have computed the visibility volumes for each input camera, we can update the
list of color samples we originally used to get our initial disparity estimates. Let
be the input color image multiplied by its visibility at disparity d. If we substitute c k (u, v, d)
for c k (u, v) in (1), we obtain a distribution of colors in (x, y, d, each color has an
associated visibility value (Figure 2c). Voxels which are occluded by surfaces lying in front in
a given view k will now have fewer (or potentially no) votes in their local color distributions.
We can therefore recompute the local mean and variance estimates using weighted statistics,
where the visibilities V (x, y, d, provide the weights (Figures 2d and 2e).
Note that it is not possible to compute visibility in (x, y, d) disparity space, as several opaque pixels in
disparity space may potentially project to the same input camera pixel.
x
(a) (b) (c)
x
x
x
(d) (e) (f)

Figure

2: After modifying input images by visibility V k (u, v, d): (a-b) re-synthesized views
of sample images, (c) (x, d, slice for scanline 17, (d) means and (e) variances as a function
of (x, d), (f) variances after evidence accumulation, (g) results of winner-takes-all for
whole image, and (h-i) colors and opacities at disparities 1 and 5 after one iteration of the
reprojection algorithm.
With these new statistics, we are now in position to refine the disparity map. In partic-
ular, voxels in disparity space which previously had an inconsistent set of color votes (large
may now have a consistent set of votes, because voxels in (partially occluded) regions
will now only receive votes from input pixels which are not already assigned to nearer
surfaces (Figure 2c-f). Figure 2g-i show the results after one iteration of this algorithm.
6 Refining color and transparency estimates
While the above process of computing visibilities and refining disparity estimates will in
general lead to a higher quality disparity map (and better quality mean colors, i.e., texture
maps), we have not yet addressed the issue of recovering true colors and transparencies in
mixed pixels, e.g., near depth discontinuities, which is one of the main goals of this research.
A simple way to approach this problem is to take the binary opacity maps produced by
our stereo matching algorithm, and to make them real-valued using a low-pass filter. Another
possibility might be to recover the transparency information by looking at the magnitude
of the intensity gradient [MYT95], assuming that we can isolate regions which belong to
di#erent disparity levels.
In our work, we have chosen instead to adjust the opacity and color values - c(x, y, d)
to match the input images (after re-projection), while favoring continuity in the color and
opacity values. This can be formulated as a non-linear minimization problem, where the
cost function has three parts:
1. a weighted error norm on the di#erence between the re-projected images - c k (u, v) and
the original (or rectified) input images c k (u, v)
where the weights w k (u, v) may depend on the position of camera k relative to the
virtual camera; 11
More precisely, we may wish to measure the angle between the viewing ray corresponding to (u, v) in
the two cameras. However, the ray corresponding to (u, v) in the virtual camera depends on the disparity d.
2. a (weak) smoothness constraint on the colors and opacities,
(x,y,d)
y, d)); (10)
3. a prior distribution on the opacities,
(x,y,d)
#(x, y, d)). (11)
In the above equations, # 1 and # 2 are either quadratic functions or robust penalty functions
[Hub81], and # is a function which encourages opacities to be 0 or 1, e.g.,
The smoothness constraint on colors makes more sense with non-premultiplied colors.
For example, a voxel lying on a depth discontinuity will be partially transparent, and yet
should have the same non-premultiplied color as its neighbors. An alternative, which allows
us to work with premultiplied colors, is to use a smoothness constraint of the form
(x,y,d)
y, d)c(x # , y # , d #(x # , y # , d # )c(x, y, d)). (12)
To minimize the total cost function
we use a preconditioned gradient descent algorithm. Appendix B contains details on how to
compute the required gradients and Hessians.
7 Experiments
To study the properties of our new stereo correspondence algorithm, we ran a small set of
experiments on some synthetic stereo datasets, both to evaluate the basic behavior of the
algorithm (aggregation, visibility-based refinement, and energy minimization), and to study
its performance on mixed (boundary) pixels. Being able to visualize opacities/transparencies
is very important for understanding and validating our algorithm. For this reason, we chose
All color and opacity values are, of course, constrained to lie in the range [0, 1], making this a constrained
optimization problem.
color stimuli (the background is blue-green, and the foreground is red). Pixels which are
partially transparent will show up as "pale" colors, while fully transparent pixels will be
white. We should emphasize that our algorithm does not require colored images as inputs
(see

Figure

5), nor does it require the use of standard epipolar geometries.
The first stimulus we generated was a traditional random-dot stereogram, where the
choice of camera geometry and filled disparity planes results in integral pixel shifts. This
example also contains no partially transparent pixels. Figure 3 shows the results on this
stimulus. The first eight columns are the eight disparity planes in (x, y, d) space, showing
the estimated colors and opacities (smaller opacities are shown as lighter colors, since the
RGBA colors are composited over a white background). The ninth and tenth column are two
re-synthesized views (leftmost and middle). The last column is the re-synthesized middle
view with a synthetic light-gray square inserted at disparity d = 3.
As we can see in Figure 3, the basic iterative aggregation algorithm results in a "perfect"
reconstruction, although only one pixel is chosen in each column. For this reason, the re-synthesized
leftmost view (ninth column) contains a large "gap".
Figure 3b shows the results of using only the first C 1 term in our cost function, i.e., only
matching re-synthesized views with input images. The re-synthesized view in column nine is
now much better, although we see that a bit of the background has bled into the foreground
layers, and that the pixels near the depth discontinuity are spread over several disparities.
Adding the smoothness constraint C 2 (Figure 3c) ameliorates both of these problems.
Adding the (weak) 0/1 opacity constraint C 3 (Figure 3d-e) further removes stray pixels
at wrong disparity levels. Figure 3d shows a "softer" variant of the opacity constraint
being filled in, but the re-synthesized views are
very good. Figure 3e shows a "harder" constraint
adjacent to initial estimates are filled in, at the cost of a gap in some re-synthesized views.
For comparison, Figure 3f shows the results of a traditional winner-take-all algorithm (the
same as Figure 3a with a very large # min and no occluded pixel removal). We can clearly see
the e#ects of background colors being pulled into the foreground layer, as well as increased
errors in the occluded regions.

Figure

3: Traditional synthetic RDS results: (a) after iterative aggregation but before
gradient descent, (b) without smoothness or opacity constraint, #
(c) without opacity constraint, # (d) with all three constraints,
simple winner-take-all (shown for comparison). The first eight columns are the disparity
layers, 7. The ninth and tenth columns are re-synthesized sample views. The last
column is a re-synthesized view with a synthetic gray square inserted at disparity d = 3.

Figure

4: More challenging synthetic RDS results: (a) after iterative aggregation but before
gradient descent, (b) without smoothness or opacity constraint, #
simple winner-take-all (shown for comparison). The first eight columns are
the disparity layers, 7. The ninth and tenth columns are re-synthesized sample
views. The last column is the re-synthesized view with a synthetic gray square inserted at
Our second set of experiments uses the same synthetic stereo dataset as shown in Figures
1 and 2. Here, because the background layer is at an odd disparity, we get significant re-sampling
errors (because we currently use bilinear interpolation) and mixed pixels. The
stimulus also has partially transparent pixels along the edge of the top half-circle in the
foreground shape. This stereo dataset is significantly more di#cult to match than previous
random-dot stereograms.
Figure 4a shows the results of applying only our iterative aggregation algorithm, without
any energy minimization. The set of estimated disparities are insu#cient to completely
reconstruct the input images (this could be changed by adjusting the thresholds # min and
several pixels are incorrectly assigned to the layer (due to di#culties in
disambiguating depths in partially occluded regions).
Figure 4b shows the results of using only the first C 1 term in our cost function, i.e., only
matching re-synthesized views with input images. The re-synthesized view in column nine is
now much better, although we see that a bit of the background has bled into the foreground
layers, and that the pixels near the depth discontinuity are spread over several disparities.
Adding the smoothness constraint C 2 (Figure 4c) ameliorates both of these problems.
Adding the (weak) 0/1 opacity constraint C 3 (Figure 4d) further removes stray pixels at
wrong disparity levels, but at the cost of an incompletely reconstructed image (this is less
of a problem if the foreground is being layered on a synthetic background, as in the last
column). As before, Figure 4e shows the results of a traditional winner-take-all algorithm.

Figure

5 shows the results on a cropped portion of the SRI Trees multibaseline stereo
dataset. A small region (64 - 64 pixels) was selected in order to better visualize pixel-level
errors. While the overall reconstruction is somewhat noisy, the final reconstruction with a
synthetic blue layer inserted shows that the algorithm has done a reasonable job of assigning
pixel depths and computing partial transparencies near the tree boundaries.
From these examples, it is apparent that the algorithm is currently sensitive to the choice
of parameters used to control both the initial aggregation stage and the energy minimization
phase. Setting these parameters automatically will be an important area for further research.
(a) (b) (c) (d) (e) (f) (g)

Figure

5: Real image example: (a) cropped subimage from SRI Trees data set, (b) depth
map after initial aggregation stage, (c-l) disparity layers re-synthesized input
image, (n) with inserted
While our preliminary experimental results are encouraging, the simultaneous recovery of
accurate depth, color, and opacity estimates remains a challenging problem. Traditional
stereo algorithms search for a unique disparity value at each pixel in a given reference image.
Our approach, on the other hand, is to recover a sparsely populated volume of colors and
opacities. This has the advantage of correctly modeling mixed pixels and occlusion e#ects,
and allows us to merge images from very disparate points of view. Unfortunately, it also
makes the estimation problem much more di#cult, since the number of free parameters often
exceeds the number of measurements, hence necessitating smoothness constraints and other
prior models.
Partially occluded areas are problematic because very few samples may be available to
disambiguate depth. A more careful analysis of the interaction between the measurement,
smoothness, and opacity constraints will be required to solve this problem. Other problems
occur near depth discontinuities, and in general near rapid intensity (albedo) changes, where
the scatter in color samples may be large because of re-sampling errors. Better imaging and
sensor models, or perhaps working on a higher resolution image grid, might be required to
solve these problems.
8.1 Future work
There are many additional topics related to transparent stereo and matting which we plan to
investigate. For example, we plan to try our algorithm on data sets with true transparency
(not just mixed pixels), such as traditional transparent random dot stereograms [Pra85,
Wei89] and reflections in windows [BBHP92].
Estimating disparities to sub-integer precision should improve the quality of our recon-
structions. Such fractional disparity estimates can be obtained by interpolating a variance
vs. disparity curve #(d), e.g., by fitting a parabola to the lowest variance and its two
neighbors [TH86, MSK89]. Alternatively, we can linearly interpolate individual color errors
c(x, y, d, y, d) between disparity levels, and find the minimum of the summed
squared error (which will be a quadratic function of the fractional disparity).
Instead of representing our color volume - c(x, y, d) using colors pre-multiplied by their
opacities [Bli94a], we could keep these quantities separate. Thus, colors could "bleed" into
areas which are transparent, which may be a more natural representation for color smoothness
(e.g., for surfaces with small holes). Di#erent color representations such as hue, satura-
tion, intensity (HSV) may also be more suitable for performing correspondence [GB95], and
they would permit us to reason more directly about underlying physical processes (shadows,
shading,etc.
We plan to investigate the relationship of our new disparity space model to more traditional
layered motion models [BBHP92, SM91b, SM91a, DP91, JBJ96, SA96]. We also
plan to make more principled use of robust statistics, and investigate alternative search algorithms
such as multiresolution (pyramidal) continuation methods and stochastic (Monte
Carlo) gradient descent techniques.
9 Conclusions
In this paper, we have developed a new framework for simultaneously recovering disparities,
colors, and opacities from multiple images. This framework enables us to deal with many
commonly occurring problems in stereo matching, such as partially occluded regions and
pixels which contain mixtures of foreground and background colors. Furthermore, it promises
to deliver better quality (sub-pixel accurate) color and opacity estimates, which can be used
for foreground object extraction and mixing live and synthetic imagery.
To set the problem in as general a framework as possible, we have introduced the notion
of a virtual camera which defines a generalized disparity space, which can be any regular
projective sampling of 3-D. We represent the output of our algorithm as a collection of color
and opacity values lying on this sampled grid. Any input image can (in principle) be re-synthesized
by warping each disparity layer using a simple homography and compositing the
images. This representation can support a much wider range of synthetic viewpoints in view
interpolation applications than a single texture-mapped depth image.
To solve the correspondence problem, we first compute mean and variance estimates at
each cell in our (x, y, d) grid. We then pick a subset of the cells which are likely to lie on the
reconstructed surface using a thresholded winner-take-all scheme. The mean and variance
estimates are then refined by removing from consideration cells which are in the occluded
(shadow) region of each current surface element, and this process is repeated.
Starting from this rough estimate, we formulate an energy minimization problem consisting
of an input matching criterion, a smoothness criterion, and a prior on likely opacities.
This criterion is then minimized using an iterative preconditioned gradient descent algorithm.
While our preliminary experimental results look encouraging, there remains much work
to be done in developing truly accurate and robust correspondence algorithms. We believe
that the development of such algorithms will be crucial in promoting a wider use of stereo-based
imaging in novel applications such as special e#ects, virtual reality modeling, and
virtual studio productions.



--R

Automated stereo perception.
A virtual studio for live broadcasting: The Mona Lisa project.
Edge based stereo correlation.
Stochastic stereo matching over scale.
A three-frame algorithm for estimating two-component image motion

Computational stereo.
Compositing
Compositing
A Bayesian treatment of the stereo correspondence problem using half-occluded regions
A space-sweep approach to true multi-image matching
A maximum likelihood n-camera stereo algorithm
Structure from stereo-a review
Robust estimation of a multi-layered motion represen- tation
A parallel stereo algorithm that produces dense depth maps and preserves image features.
Motion from color.
The lumigraph.
In Second European Conference on Computer Vision (ECCV'92)
Robust Statistics.

Skin and bones: Multi-layer
Techniques for disparity measure- ment
A computational framework for determining stereo correspondence from a set of linear spatial filters.
A stereo machine for video-rate dense depth mapping and its new applications
A stereo matching algorithm with an adaptive win- dow: Theory and experiment
A multibaseline stereo system with active illumination and real-time image acquisition

An iterative image registration technique with an application in stereo vision.
Fast Volume
Plenoptic modeling: An image-based rendering system
Cooperative computation of stereo disparity.
Kalman filter-based algorithms for estimating depth from image sequences
Human assisted key extrac- tion
Stereo by intra- and inter-scanline search using dynamic pro- gramming
A multiple baseline stereo.

Numerical Recipes in C: The Art of Scientific Computing.
PMF: A stereo correspondence algorithm using a disparity gradient limit.
Detection of binocular disparities.
Image Processing for Broadcast and Video Production
Prediction of correlation errors in stereo-pair images
Compact representation of videos through dominant multiple motion estimation.
Blue screen matting.
Photorealistic scene reconstrcution by space coloring.
Solving random-dot stereograms using the heat equation
Direct methods for visual scene reconstruction.
Principle of superposition: A common computational frame-work for analysis of multiple motion
A unified computational theory of motion transparency and motion boundaries based on eigenenergy analysis.
Stereo matching with non-linear di#usion
Algorithms for subpixel registration.
Traveling matte composite photography.
Perception of multiple transparent planes in stereo vision.
A generalized ordering constraint for stereo correspon- dence

"voting"
--TR
Algorithms for subpixel registration
Efficient ray tracing of volume data
Techniques for disparity measurement
A Three-Frame Algorithm for Estimating Two-Component Image Motion
Numerical recipes in C (2nd ed.)
Fast volume rendering using a shear-warp factorization of the viewing transformation
Disparity-space images and large occlusion stereo
Plenoptic modeling
AutoKey
Compact Representations of Videos Through Dominant and Multiple Motion Estimation
The lumigraph
Blue screen matting
Layered depth images
Computational Stereo
Compositing, Part 1
Compositing, Part 2
A Multiple-Baseline Stereo
A Stereo Matching Algorithm with an Adaptive Window
A Computational Framework for Determining Stereo Correspondence from a Set of Linear Spatial Filters
Occlusions and Binocular Stereo
Photorealistic Scene Reconstruction by Voxel Coloring
A Unified Mixture Framework for Motion Segmentation
Skin and Bones
A Stereo Machine for Video-Rate Dense Depth Mapping and Its New Applications
Stereo Matching with Non-Linear Diffusion
A Space-Sweep Approach to True Multi-Image Matching
A Layered Approach to Stereo Reconstruction
Compositing digital images
Direct Method for Visual Scene Reconstruction
A multibaseline stereo system with active illumination and real-time image acquisition

--CTR
Steven Seitz , Richard Szeliski, From the guest editors, ACM SIGGRAPH Computer Graphics, v.33 n.4, p.35-37, Nov.2000
Yen-Hsiang Fang , Hong-Long Chou , Zen Chen, 3D shape recovery of complex objects from multiple silhouette images, Pattern Recognition Letters, v.24 n.9-10, p.1279-1293, 01 June
C. Lawrence Zitnick , Sing Bing Kang , Matthew Uyttendaele , Simon Winder , Richard Szeliski, High-quality video view interpolation using a layered representation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
Antonio Criminisi , Sing Bing Kang , Rahul Swaminathan , Richard Szeliski , P. Anandan, Extracting layers and analyzing their specular properties using epipolar-plane-image analysis, Computer Vision and Image Understanding, v.97 n.1, p.51-85, January 2005
Yin Li , Heung-Yeung Shum , Chi-Keung Tang , Richard Szeliski, Stereo Reconstruction from Multiperspective Panoramas, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.1, p.45-62, January 2004
Mi-Suen Lee , Grard Medioni , Philippos Mordohai, Inference of Segmented Overlapping Surfaces from Binocular Stereo, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.6, p.824-837, June 2002
Silvio Savarese , Marco Andreetto , Holly Rushmeier , Fausto Bernardini , Pietro Perona, 3D Reconstruction by Shadow Carving: Theory and Practical Evaluation, International Journal of Computer Vision, v.71 n.3, p.305-336, March     2007
Evren mre , Sebastian Knorr , Burak zkalayc , Uur Topay , A. Aydn Alatan , Thomas Sikora, Towards 3-D scene reconstruction from broadcast video, Image Communication, v.22 n.2, p.108-126, February, 2007
C. Lawrence Zitnick , Sing Bing Kang, Stereo for Image-Based Rendering using Image Over-Segmentation, International Journal of Computer Vision, v.75 n.1, p.49-65, October   2007
Sing Bing Kang , Richard Szeliski, Extracting View-Dependent Depth Maps from a Collection of Images, International Journal of Computer Vision, v.58 n.2, p.139-163, July 2004
Daniel Scharstein , Richard Szeliski, A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms, International Journal of Computer Vision, v.47 n.1-3, p.7-42, April-June 2002
transparency;matting problem;stereo correspondence;3D representations;occlusions;3D reconstruction