Graphics Reference
In-Depth Information
graph. Each entry of the second matrix,
R
(
i
,
k
)
, is defined as the index of the node in
row
i
−
1 of the graph that resulted in the cost
S
(
i
,
k
)
(which we can think of as the
“predecessor” of that node).
Formally, we apply the following algorithm:
E
data
(
1.
Initialize
S
(
1,
k
)
=
k
)
for
k
=
1,
...
,
N
. That is, the first row is initialized
with the data costs of assigning
L
(
1
)
=
1,
...
,
L
(
1
)
=
N
. Initialize
R
(
1,
k
)
=
0
(these entries are arbitrary and won't be used).
2. For
i
=
2,
...
,
M
, iterate the following step:
3. Compute
S
(
i
,
k
)
and
R
(
i
,
k
)
as:
E
data
(
E
i
−
1,
i
smoothness
S
(
i
,
k
)
=
k
)
+
min
l
(
S
(
i
−
1,
l
)
+
(
l
,
k
))
(A.2)
R
(
i
,
k
)
=
argmin
l
(
S
(
i
−
1,
l
)
+
E
smoothness
(
l
,
k
))
That is,
S
is the lowest cost that can be achieved considering the allowable
predecessors in the previous row of the matrix, and
R
(
i
,
k
)
(
i
,
k
)
is the index of the
1 that achieves this cost. The notion of allowability
depends on the application, as illustrated in Figure
A.1
.
4. The matrix has thus been filled in from the first row to the last. In the stereo
correspondence case (or more generally when we require the path to end at
the corner of the matrix), we fix
L
M
=
predecessor in row
i
−
N
. In the seam carving case (or more
generally when the path can end at any point in the last row of the image), we
fix
L
M
=
N
∗
, where
N
∗
=
argmin
k
S
(
M
,
k
)
(A.3)
5. We finally extract the minimal cost path by backtracking from row
M
. That is,
for
i
=
M
−
1:
−
1 : 1, we compute
L
i
=
R
(
i
+
i
,
L
i
+
1
)
(A.4)
M
M
2
2
1
1
12
N
12
N
labels
labels
(a)
(b)
Figure A.1.
Paths for dynamic programming problems. (a) A path for a seam carving problem
must connect the top and bottom edges; adjacent labels can differ by at most 1. (b) A path for
a stereo correspondence problem must have non-decreasing labels and connect the lower left
corner to the upper right corner. The smaller circled pixels in each case indicate the allowable
predecessors of the large circled pixel (each of which may have a different weight specified by
the smoothness term).
