Graphics Reference
In-Depth Information
approach based on
-expansion that both enforces uniqueness and properly han-
dles occlusions. However, the set of vertices is quite different than that shown earlier.
Instead, each vertex in the graph is a viable correspondence: a match
α
x
,
y
)
}
{
(
x
,
y
)
,
(
y
. An edge connects two vertices if they have
the same disparity, with a small weight if the two pixel pairs have similar intensities
and a large weight otherwise. This encourages pairs of adjacent pixels with simi-
lar intensities to have similar disparities. Edges with infinite weight are also defined
between vertices that contain the same pixel with different disparities, so that cut-
ting such an edge would violate the uniqueness property. Finally, edges are defined
connecting each vertex to two terminals, so that cutting such an edge implies that the
pixel is occluded in one image or the other. They constructed
x
∈{
such that
x
−
0, 1,
...
,
d
max
}
and
y
=
-expansion steps on
a series of such graphs, so that the final labeling approximately minimizes a sum of
data, smoothness, and occlusion penalty terms, while maintaining uniqueness and
allowing some pixels to remain unmatched.
While uniqueness seems like a desirable property, it can be problematic in the
case of horizontally slanted surfaces, as noted by Sun et al. [
480
]. That is, a surface
may extend across many pixels in one image but only a few pixels in the other image
due to foreshortening. They proposed a more general
visibility
constraint that non-
occluded pixels must have at least one match in the other image, while occluded
pixels must have no matches; this required the estimation of an additional occlusion
map (see more in the next section).
α
5.5.3
Optimization with Belief Propagation
An energy function in the form of Equation (
5.50
) can also be approximately mini-
mized using
loopy belief propagation
, an algorithm frequently used for inference on
Markov Random Fields (we discussed an application to matting in Section
2.5
). The
idea is to iteratively update each vertex's
belief
that it should have a certain disparity,
represented as a
d
max
1-dimensional vector. In each iteration, the belief is updated
based on
messages
sent from its neighbors in the graph (also
d
max
+
1-dimensional
vectors). After some number of
message passing
iterations, the vertex chooses the
maximizer of its belief vector as its final disparity. Concretely, we apply the following
+
Initialize
m
ij
=
(
)
∈
E
1.
0 for all
i
,
j
+
∈
V
2. Form the
d
max
1-dimensional message vector from each
i
to each of its
neighbors
j
|
(
i
,
j
)
∈
E
at iteration
t
by:
E
data
m
ij
(
d
)
+
d
,
L
d
)
=
min
d
(
L
(
i
)
=
E
smoothness
(
L
(
i
)
=
(
j
)
=
d
)
m
t
−
1
ki
d
)
+
(
(5.53)
k
|
(
i
,
k
)
∈
E
,
k
=
j
. Effectively, this message conveys vertex
i
's assess-
ment that vertex
j
should have disparity
d
.
3. Repeat Step 2 for
T
iterations.
where
d
∈{
0, 1,
...
,
d
max
}
19
This can be viewed as a version of the
max-product algorithm
.
