Graphics Reference
In-Depth Information
Since some pixels in the image have been labeled by the trimap or a scribble, we
can re-index the pixels into a known set
K
and an unknown set
U
and partition the
graph Laplacian as
L
K
R
L
=
(2.63)
R
L
U
where the
L
K
block corresponds to the set of known pixels and the
L
U
block to the
unknown set.
Grady showed that the desired random walker probabilities described earlier
correspond to minimizing the functional
L
K
R
α
k
α
u
α
L
α
=[
α
k
α
u
]
(2.64)
R
L
U
using results fromcombinatorial graph theory. Taking the gradient of Equation (
2.64
)
with respect to the unknown values
α
u
and setting it equal to 0 leads to the linear
system
R
α
k
L
U
α
u
=−
(2.65)
This is generally an extremely sparse system; for example, if 4-neighbors are used
for adjacency there are only five nonzero elements per row. As a bonus, all elements
of the solution of Equation (
2.65
) are guaranteed to be in the range [0,1] by the
maximum modulus principle (i.e., the interpolated harmonic function must take its
minimumandmaximum values on its boundary, which are 0 and 1 respectively from
the trimap/scribbles).
The key issue is thus how to choose the weights for random-walk matting. Grady
[
176
] originally proposed to simply use
2
e
−
β
I
i
−
I
j
w
ij
=
(2.66)
2
with
β
=
900 assuming the images are normalized so
I
i
−
I
j
∈[
0, 1
]
, and later
proposed a more general weight
e
−
β(
I
i
−
I
j
)
Q
Q
(
I
i
−
I
j
)
w
ij
=
(2.67)
where
Q
is a linear transformation of RGB space defined by the locality-preserving
projections algorithm [
178
,
193
].
Note that the derivation of closed-form matting based on the matting equation
and color line assumption leads to a minimization in exactly the same form as
Equation (
2.64
), except that the weights that form
L
arise from the matting Laplacian
in Equation (
2.36
) instead; that is, for closed formmatting we would use
1
I
i
−
µ
k
)
W
I
3
×
3
−
1
1
W
w
ij
=
+
(
k
+
(
I
j
−
µ
k
)
(2.68)
k
|
(
i
,
j
)
∈
w
k
where
k
are the mean and covariance matrix of the colors in the window
w
k
centered around pixel
k
. These are exactly the values of the matting affinity in
Equation (
2.38
).
µ
k
and
