Graphics Reference
In-Depth Information
(a)
(b)
(c)
(d)
Figure 5.18.
An example stereo result using graph cuts. (a), (b) An original stereo image pair.
(This is the “Tsukuba” dataset frequently used for benchmarking stereo algorithms, originally
created and ground-truthed by Nakamura et al. [
344
].) (c) The ground-truth disparity map, in
which the disparity labels
{
}
are mapped from black to white. Objects closer to the cam-
eras (e.g., the lamp) have higher disparities. (d) The stereo result using graph-cut optimization
as described by Boykov et al. [
61
].
0, 1,
...
,14
As mentioned in Section
3.3
, minimizing a function like Equation (
5.50
) using
α
-expansion proceeds by cyclically iterating over the possible disparity labels
d
∈
{
. For a given disparity label, we form an auxiliary minimum-cut problem
in which each node will either be associated with the label it had in the previous
iteration, or the new label
d
, which corresponds to a two-terminal graph (i.e.,
d
or
not-
d
). That is, at each step, the region of pixels labeled
d
is allowed to expand by
solving anewminimum-cut problem. The algorithmstops after a cycle through all the
labels fails to decrease the cost function. Boykov et al. showed that while we are not
guaranteed to find a global minimum of Equation (
5.50
), the cost of the
0,
...
,
d
max
}
-expansion
result will be within a factor of 2 of the global minimum if the smoothness term is
given by the Potts model. Appendix
A.3
gives details on the algorithm.
18
Figure
5.18
illustrates an example stereo result using a data term based on the
Birchfield-Tomasi measure and a smoothness term based on the intensity-adaptive
Potts model. We can see that the result reflects many of the underlying smooth-
and constant-intensity regions in the ground-truth disparity map, and contains no
“streaking” artifacts.
Kolmogorov and Zabih [
246
] noted that despite its good performance in practice,
the graph-cut formulation does not enforce
uniqueness
; that is, two pixels in the first
image might be matched to the same pixel in the second image. More important,
every pixel in the first image must be assigned a disparity, meaning that the method
is not able to deal with occlusions. Kolmogorov and Zabih proposed a graph-cut
α
18
Technically, the truncated quadratic can't be used in the
α
-expansion algorithm since it's not a
metric.
