Graphics Reference
In-Depth Information
4. Form the final belief vector at each
i
∈
V
and
d
∈{
0, 1,
...
,
d
max
}
as:
m
ji
(
b
i
(
d
)
=
E
data
(
L
(
i
)
=
d
)
+
d
)
(5.54)
j
|
(
i
,
j
)
∈
E
5. Assign vertex
i
to have the disparity label that maximizes
b
i
(
d
)
.
Felzenszwalb and Huttenlocher [
138
] described several simple modifications to
the basic loopy belief propagation algorithm that dramatically speed up its conver-
gence for the graphs and cost functions typically encountered in computer vision
applications like stereo. Consequently, we can put any of the data/smoothness term
combinations that would work with
-expansion into a belief-propagation frame-
work. Even though there are no guarantees that the result of loopy belief propagation
achieves the global minimum of the cost function, in practice its performance is very
good. Appendix
A.2
gives more details on belief propagation.
Szeliski et al. [
485
] concluded that the stereo results obtained by minimizing
an energy function using graph cuts were generally better than those obtained
by minimizing the same function using belief propagation. However, many of the
currently-top-performing stereo algorithms use some type of belief propagation, pos-
sibly because it more naturally results from a probabilistic interpretation of the data
and smoothness terms and is amenable to parallelization.
Sun et al. [
482
] proposed a early belief-propagation-based algorithm for stereo,
using a Birchfield-Tomasi data term and a smoothness term related to the truncated
absolute function in Table
5.2
. A key innovation was the introduction of a separate
occlusionmap
. Ideally, this is a binary map
α
defined over the vertices that equals 0
at visible pixels and 1 at occluded pixels; then the cost function becomes
O
(
)
=
E
L
E
data
(
L
(
i
))
+
E
occlusion
+
E
smoothness
(
L
(
i
)
,
L
(
j
))
(5.55)
∈
V
∈
O
∈
V
∈
O
(
)
∈
E
i
,
i
i
,
i
i
,
j
That is, we only compute disparities for unoccluded pixels, and add a constant
penalty
E
occlusion
for each occluded pixel. In practice, the computation is simplified
by allowing the values in the occlusion map to range continuously between 0 and
1, resulting in a soft combination of the data and occlusion terms in the cost func-
tion. Sun et al. also proposed a binary
discontinuity map
defined over the edges,
which explicitly encodes the presence or absence of a discontinuity. Similar to how
Equation (
5.55
) differs from Equation (
5.50
), the smoothness term is decomposed
into a term for edges along continuous surfaces and a penalty for discontinuities.
Sun et al. [
480
] later refined the approach to a symmetric stereo model, where con-
sistent disparities, occlusions, and discontinuities for the left and right images are
computed simultaneously (instead of just computing these quantities for the left
image). Xu and Jia [
557
] took a similar approach, using a data term inspired by robust
matting ([
532
], Section
2.6.1
).
5.5.4
Incorporating Segmentation
Top-performing stereo algorithms usually involve some type of reasoning about
groups of pixels with similar colors. A common assumption is that the disparity inside
a similar-colored region iswellmodeledby a planar patch; that is,
d
(
)
≈
+
+
x
,
y
ax
by
c
,
