Graphics Reference
In-Depth Information
F
U
Figure 2.17. Random-walk matting methods are
based on estimating the probability that a random
walk starting at a pixel in the unknown region (black
pixel) ends up in the foreground region. The illus-
trated instance of the random walk ends up in the
foreground (white pixel).
E
and the set of undirected edges
represents connections between pixels (typically,
4-neighbor adjacency). Each edge e ij E
is associated with a nonnegative weight w ij .
As discussed later, different random-walk-based algorithms use different formu-
lations for the weights w ij , but the common intuition is that w ij should be large
for pixels that are “similar” and near zero for pixels that are dissimilar. As in the
algorithms shown earlier, the user provides prior information about foreground and
background regions in the form of a trimap or scribbles. Random walk algorithms
estimate
i at a pixel i in the unknown region as the probability that a randomwalker
starting at i and choosing edges according to the weights w ij will first encounter a
foreground pixel rather than a background pixel, as illustrated in Figure 2.17 .
While this approach lacks the mathematical model for how intensities and
α
's
are related through the matting equation that underlies Bayesian and closed-form
matting, it turns out to work well in practice and be computationally efficient. It
additionallymatches our intuition; if there exists a path containing similar intensities
between an unknown pixel i to the labeled foreground region
α
F
, while paths from
i to the background region
need to cross dissimilar pixels, pixel i is more likely
to be foreground. However, we should note that the random-walk algorithm isn't
evaluating the shortest or most likely path, it's evaluating the probability over all
possible paths the random walker may take. It may seem that this probability is
intractable to estimate; however, Grady showed how it could be computed using a
similar linear system.
Let the degree d i of node i be the sum of edge weights coming into it, that is:
B
d i
=
w ij
(2.61)
j
|
e ij E
The graph Laplacian matrix is defined as
d i
if i
=
j
L ij
=
w ij
if e ij
E
(2.62)
0
otherwise
Search WWH ::




Custom Search