Graphics Reference
In-Depth Information
Dynamic programming is highly efficient, finding the optimal solution in poly-
nomial time compared to the worst-case exponential-time problem of evaluating all
possible paths. Many well-known signal processing algorithms in addition to those
we discussed are forms of dynamic programming, including the Viterbi algorithm
for decoding convolutional codes in communication theory and the Baum-Welch
algorithm for maximum likelihood estimation of unknown parameters in a Hid-
den Markov Model. For more information on the general algorithm, see Cormen
et al. [
106
]. An excellent overview of applications of dynamic programming to
computer vision is given by Felzenszwalb and Zabih [
139
].
A.2
BELIEF PROPAGATION
We can think of Equation (
A.1
) as a special case of a
Gibbs energy
E
i
,
j
E
data
(
E
(
L
)
=
L
(
i
))
+
smoothness
(
L
(
i
)
,
L
(
j
))
(A.5)
i
∈
V
(
i
,
j
)
∈
E
where
is a set of undirected edges along which we want
to enforce smoothness. When these edges form a one-dimensional chain, we can
find the labeling
V
is a set of nodes and
E
that minimizes Equation (
A.5
) in polynomial time using
dynamic programming. However, when the edge set
{
L
(
i
)
,
i
∈
V
}
contains cycles, dynamic
programming no longer applies, and there is no higher-dimensional analogy.
In particular, we frequently want to minimize Equation (
A.5
) when
E
V
is the set of
pixels in an image, and
is the set of all adjacent pixels (for example, 4-neighbors).
The resulting graph is planar and contains a large number of cycles. Unfortunately,
there is no efficient algorithm that provably finds the minimal labeling in this sit-
uation. However, the algorithm called
loopy belief propagation
has found great
practical success in the computer vision community for approximately minimizing
Equation (
A.5
) despite its lack of formal guarantees on convergence or exact opti-
mality. For example, we discussed loopy belief propagation's application to matting
problems in Section
2.5
and to stereo correspondence in Section
5.5
.
Minimizing a function like Equation (
A.5
) often arises from a
maximuma posteri-
ori (MAP)
estimation problem on a Markov Random Field, in which we want to find
E
Z
i
1
p
(
L
)
=
φ
(
L
(
i
))
ψ
(
L
(
i
)
,
L
(
j
))
(A.6)
i
ij
∈
V
(
i
,
j
)
∈
E
where
is called the
compati-
bility potential function
, and
Z
is a normalization constant so the probability density
function sums to 1. Comparing Equation (
A.5
) to Equation (
A.6
), we can see that the
data/smoothness terms and evidence/compatibility potential functions can easily be
related by
φ
i
(
k
)
is called the
evidence potential function
,
ψ
ij
(
k
,
l
)
E
data
(
k
)
=−
log
φ
(
k
)
i
(A.7)
E
i
,
j
smoothness
(
)
=−
ψ
ij
(
)
k
,
l
log
k
,
l
1
Technically, this is a probability mass function since the label set is discrete.
