Graphics Reference
In-Depth Information
label
α
Figure A.3.
The binary-label graph for one step of
α
-expansion. The source node is identified with the
action “label
α
,” while the sink node is identified with
“keep current label.” The black dots are nodes of the
original problem, while the white dots are auxiliary
nodes introduced between nodes that currently have
different labels.
keep current label
to several possible disparities. We can tackle such problems by decomposing them
into a sequence of binary-label graph cut problems, using the
α
-
expansion
algorithm
proposed by Boykov et al. [
61
].
5
The key idea is to solve a series of minimum-cut subproblems on graphs of the
type illustrated in Figure
A.3
, each starting with an initial labeling. In each problem, a
certain label value
is fixed.We build a newgraph containing all the nodes
and edges of the original problem. In this graph, the source node
α
∈{
1,
...
,
N
}
S
is identified with
α
T
the action “label
is identified with “keep current label.” We
alsomust add an
auxiliary node
a
ij
between every pair of nodes
i
and
j
whose current
labels
L
,” while the sink node
disagree. These auxiliary nodes are only connected to the sink.
Boykov et al. [
61
] defined theweights on the edges for the
(
i
)
and
L
(
j
)
α
-expansion subproblem
as follows:
w
i
T
=∞
if
L
(
i
)
=
α
w
i
T
=
E
data
(
(
)
=
)
(
)
=
α
L
i
current label
if
L
i
w
i
S
=
E
data
(
(
)
=
α)
∈
V
L
i
all
i
E
i
,
j
w
ia
ij
=
smoothness
(
(
)
α)
(
)
∈
E
(
)
=
(
)
L
i
,
if
i
,
j
,
L
i
L
j
(A.15)
E
i
,
j
smoothness
w
a
ij
j
=
(α
,
L
(
j
))
if
(
i
,
j
)
∈
E
,
L
(
i
)
=
L
(
j
)
E
i
,
j
smoothness
w
a
ij
T
=
(
L
(
i
)
,
L
(
j
))
if
(
i
,
j
)
∈
E
,
L
(
i
)
=
L
(
j
)
E
i
,
j
smoothness
w
ij
=
(
L
(
i
)
,
α)
if
(
i
,
j
)
∈
E
,
L
(
i
)
=
L
(
j
)
5
As previously, we require some conditions on the
E
smoothness
term; specifically that it is a metric.
That is, for any labels
L
(
i
)
,
L
(
j
)
,
L
(
h
)
,
E
i
,
j
smoothness
(
L
(
i
)
,
L
(
j
))
=
0
⇐⇒
L
(
i
)
=
L
(
j
)
E
i
,
j
smoothness
(
L
(
i
)
,
L
(
j
))
=
E
i
,
j
smoothness
(
L
(
j
)
,
L
(
i
))
≥
0
(A.14)
E
i
,
j
E
i
,
h
E
h
,
j
smoothness
(
L
(
i
)
,
L
(
j
))
≤
smoothness
(
L
(
i
)
,
L
(
h
))
+
smoothness
(
L
(
h
)
,
L
(
j
))
