354
L. Pan and X. Chen
Fig. 12.6 Illustration of graph construction on a 2D example. a Final constructed graph G which
consists of three sub-graphs G SS , G R and G SI . b Geometric constraints between surfaces G SS and
G R . c Geometric constraints between surfaces G R and G SI
respectively, d is a pre-defined distance threshold (here, d 1), w v is a penalty
weight for v and f v 1 if v ∈ region R.
12.3.2.2 Graph Construction
Three sub-graphs are constructed for superior surface S s , inferior surface S I and
region R. These three sub-graphs are merged together to form as a single s-t graph
G which can be solved by a min-cut/max-flow technique [13].
For the surface S s , a sub-graph G SS (V SS , A SS ) is constructed by following the
method in [12]. Each node in V SS corresponds to exactly one voxel in the image.
Two types of arcs are added to the graph: (1) The inter-column arcs incorporating the
penalties h p,q between the neighboring columns p and q; and (2) The intra-column
arcs with +∞ weight, which enforces the monotonicity of the target surface. A weight
w n is assigned to each node such that the total weight of a closed set in the graph
G SS equals to the edge-cost term of E(Surface). Following the method in [36], each
node is connected to either the sink T with the weight w n if w n > 0 or the source S
with the weight −w n if w n < 0.
For the surface S I , the same graph construction method is applied creating another
sub-graph G SI (V SI , A SI ).
For the region term cost function, the graph cut method in [13] is used to construct
the third sub-graph G R (V R , A R ). Here, each node in V R is also corresponding to
exactly one voxel in the image. The two terminal nodes: sink T and source S are the
same nodes already used in G SS and G SI. Each node has t-links to the sink and source,
which encode the data term. N-link connect each pair of neighboring nodes, which
encodes the boundary term. Figure 12.6 shows the graph construction. The nodes in
V R , V SS and V SI are all corresponding, so these three sub-graphs can be merged into
a single graph G.
Additional inter-graph arcs are added between G SS and G R , as well as between
G R and G SI to incorporate geometric interaction constraints. For G SS and G R , if a
node (x, y, z) in the sub-graph G R is labeled as “source” and the node (x, y, z + d) in
L. Pan and X. Chen
Fig. 12.6 Illustration of graph construction on a 2D example. a Final constructed graph G which
consists of three sub-graphs G SS , G R and G SI . b Geometric constraints between surfaces G SS and
G R . c Geometric constraints between surfaces G R and G SI
respectively, d is a pre-defined distance threshold (here, d 1), w v is a penalty
weight for v and f v 1 if v ∈ region R.
12.3.2.2 Graph Construction
Three sub-graphs are constructed for superior surface S s , inferior surface S I and
region R. These three sub-graphs are merged together to form as a single s-t graph
G which can be solved by a min-cut/max-flow technique [13].
For the surface S s , a sub-graph G SS (V SS , A SS ) is constructed by following the
method in [12]. Each node in V SS corresponds to exactly one voxel in the image.
Two types of arcs are added to the graph: (1) The inter-column arcs incorporating the
penalties h p,q between the neighboring columns p and q; and (2) The intra-column
arcs with +∞ weight, which enforces the monotonicity of the target surface. A weight
w n is assigned to each node such that the total weight of a closed set in the graph
G SS equals to the edge-cost term of E(Surface). Following the method in [36], each
node is connected to either the sink T with the weight w n if w n > 0 or the source S
with the weight −w n if w n < 0.
For the surface S I , the same graph construction method is applied creating another
sub-graph G SI (V SI , A SI ).
For the region term cost function, the graph cut method in [13] is used to construct
the third sub-graph G R (V R , A R ). Here, each node in V R is also corresponding to
exactly one voxel in the image. The two terminal nodes: sink T and source S are the
same nodes already used in G SS and G SI. Each node has t-links to the sink and source,
which encode the data term. N-link connect each pair of neighboring nodes, which
encodes the boundary term. Figure 12.6 shows the graph construction. The nodes in
V R , V SS and V SI are all corresponding, so these three sub-graphs can be merged into
a single graph G.
Additional inter-graph arcs are added between G SS and G R , as well as between
G R and G SI to incorporate geometric interaction constraints. For G SS and G R , if a
node (x, y, z) in the sub-graph G R is labeled as “source” and the node (x, y, z + d) in