Graphics Reference
In-Depth Information
Optimization Algorithms for
Computer Vision
A
A.1
DYNAMIC PROGRAMMING
We discussed dynamic programming in several contexts: finding the lowest-cost
seam in seam carving (Section
3.5
), computing the best correspondence between
a pair of conjugate epipolar lines (Section
5.5
), and aligning two motion capture
sequences (Section
7.5
). Here we give a brief description of how to set up and solve
these types of dynamic programming problems.
We can think of each problem as assigning each of
M
nodes one of
N
labels. For
example, if we want to carve a vertical seam in an image, the nodes index the rows,
and the labels specify the column of the pixel to remove from each row. In the stereo
correspondence problem, the nodes index the pixels of one epipolar line, and the
labels specify the pixels of the other epipolar line (or the corresponding disparities).
Our goal is to find the labeling
L
=
(
L
(
1
)
,
...
,
L
(
M
))
with the lowest cost, where the
cost function is of the form
M
M
−
1
E
i
,
i
+
1
E
data
(
C
(
L
)
=
L
(
i
))
+
smoothness
(
L
(
i
)
,
L
(
i
+
1
))
(A.1)
i
=
1
i
=
1
where
E
data
(
k
)
represents the cost of assigning label
k
to node
i
(the data term) and
E
i
,
i
+
1
smoothness
(
k
,
l
)
represents the cost of assigning labels
k
and
l
to adjacent nodes
i
and
i
1 (the smoothness term). The data term usually involves the intensities of
image pixels (for example, in seam carving, it's related to the gradient at the pixel
corresponding to the label). The smoothness termreflects constraints or assumptions
about how similar adjacent labels should be. For example, in seam carving, a vertical
seam must separate the image into left and right parts; thus, the label at node
i
is
constrained to be within the range
+
. Similarly, in the stereo
correspondence problem, we usually impose the monotonicity constraint that
L
i
{
L
i
−
1
−
1,
L
i
−
1
,
L
i
−
1
+
1
}
>
L
i
−
1
, and may further weight the allowable disparities at each pixel, for example
by assigning higher costs to larger disparities. We can think of a labeling as a
path
through a graph of
M
N
vertices, as illustrated in Figure
A.1
.
To find theminimum-cost labeling, we apply a recursive algorithm, building tables
of incrementally optimal costs and corresponding minimizers. That is, we fill in the
entries of two
M
×
, is defined as
the minimum cost of the path that begins in row 1 and ends at vertex
×
N
matrices. Each entry of the first matrix,
S
(
i
,
k
)
(
)
i
,
k
of the
353
