Graphics Reference
In-Depth Information
(a)
(b)
(c)
Fig. 10.14.
The fast marching algorithm is used to compute the path of a ball
rolling on an inclined plane under the influence of gravity. The path of the ball
will always be a geodesic. (a) Inverse velocity metric, (b) arrival time (surfaces of
minimal action), and (c) geodesic (shortest path).
segmentation in higher dimensions. Although this has been tried in the past
with discrete approximations, Appleton and Talbot [9] proposed a method
based on continuous maximal flows by solving a system of partial differential
equations. It is shown in [7] that this method gives identical results to the
previous GOGAC method in the case of planar images.
10.4.1 Minimum Cuts and Maximum Flows
Minimum cuts are another concept from graph theory that are related to
shortest paths, although the computation is often slower and more compli-
cated. Graph cuts may be used to determine the capacity of a communications
network or to determine the minimum number of links that must fail before a
network becomes disconnected—an important measure of the reliability of a
network. In image analysis they have been proposed for optimally partitioning
an image or volume into two regions. For example, this technique could be
used to determine the most likely shape of a 3D object in an ultrasound or
Magnetic Resonance Imaging (MRI) image.
Consider a finite directed graph
G
where every edge (
u, v
) has a capacity of
c
(
u, v
), which is a non-negative real number. We identify two vertices, known
as the source
s
and the sink
t
. A cut is a partition of the nodes into two sets
S
and
T
, such that
s
∈
S
and
t
∈
T
. The capacity of a cut (S,T) is
c
(
S, T
)=
c
(
u, v
)
,
u∈S,v∈T |
(
u,v
)
is an edge
which is just the sum of the capacity of all edges crossing the cut from region
S
to
T
.
The
max-flow min-cut theorem
[60, 63] states that, the maximal amount
of flow in a network is equal to the capacity of a minimal cut. In other words,
the theorem states that the maximum flow in a network is dictated by its
Search WWH ::
Custom Search