Graphics Reference
In-Depth Information
Goldberg-Tarjan Preflow Push Algorithm
Initialization:
•
Set
F
= 0 on each edge
•
Set
H
to be the length of the shortest (unweighted) path to the sink
t
,and
H
(
s
)=
|
V
|
•
Set the source
s
as active and place it in the
Q
Main loop:
•
If
Q
is empty, halt
•
Otherwise, retrieve an active vertex
v
from
Q
•
For all neighboring vertices u of v:
- If the edge (
v, u
) is unsaturated and
H
(
v
)=
H
(
u
) + 1, push more flow along
edge (
v, u
) until it is saturated or
v
has excess 0
- If this increased the flow to
u
,set
u
as active and place in
Q
.Note:
u
may
already be active
- f
v
still has positive excess, increment
H
(
v
) and place
v
in
Q
•
Otherwise, set v as inactive
Fig. 10.16.
Pseudocode for Goldberg-Tarjan Preflow Push algorithm (from [7]).
10.4.2 Development of the GMS Algorithm
It is well known that maximum flow techniques work well in a discrete do-
main of a network, but the imposition of a coarse discretization grid on a
natural image leads to quite unnatural grid-biases in the segmentation. The
segmentation contours tend to follow the artificially imposed discretization
grid rather than the following smooth curves in the image itself, leading to
unacceptable staircase artifacts. The goal here is to develop an algorithm that
works directly in the continuous image domain.
It is not at all clear how the augmenting path algorithm can be extended
from the continuous to the discrete domain. On the other hand, the preflow
push method is much better suited to the problem. One advantage is that the
updates on vertices require only local information from the neighbors rather
than global knowledge of the image. This suggests a method based on solving
a system of partial differential equations—indeed in much the same way, the
solution of Maxwell's equations leads to the solutions for electromagnetic fields
and traveling electromagnetic waves such as light.
We relax the flow conservation constraint at each vertex by adding an
additional variable at each point. This results in a scalar potential field,
P
,
which will keep track of the inflow-outflow imbalance (i.e., divergence) in the
(compressible) flow and provides a restoring force to drive this imbalance to
zero at convergence.
One way to visualize the potential function is to think of a network of water
pipes connected to an underground junction. When water initially surges down
the pipes and meets at the junction, enormous pressures are generated, which
Search WWH ::
Custom Search