Graphics Reference
In-Depth Information
Fast Marching Algorithm
Initialization:
For all grid points
x
in
P
0
:
•
Set
U
(
x
)=0
•
Label
x
as Trial and insert into
Q
For all other grid points
x
:
•
Set
U
(
x
)=
∞
•
LabelxasFar
Main loop:
•
If Q is empty, halt
•
Otherwise remove the Trial point of minimum value from the priority queue:
U
(
x
)
x
∈
x
=argmin
x
{
|
Q
}
•
Label x as Known
•
For each neighbor
n
of
x
in the grid:
- f
n
is Known, continue to next neighbor
- f
n
is Far, change label to Trial and insert into
Q
-
Update
U
(
n
) by solving (10.5). Only use the values at neighboring grid points
which are labeled Known.
Fig. 10.12.
Pseudocode for the fast marching algorithm to find the surfaces of
minimal action and geodesics (i.e., shortest paths)(from [7]).
function, from the starting set
P
0
to all points in the space. It finds the
surface of minimal action by considering it as the first time-of-arrival of a
wavefront emanating from the starting set
P
0
and traveling with speed
1
g
,
where
g
is usually the image gradient as before. This wavefront sweeps the
grid beginning with the starting set
P
0
and proceeds in order of arrival time
U
.
The algorithm is identical to Dijkstra's shortest distance algorithm [59]
from Section 9.5 apart from the need to update
g
. On a rectangular two-
dimensional grid in with grid step
h
, we may use the discrete gradient operator
defined by
g
2
(
i, j
)=
1
2
h
2
max
{
U
[
i, j
]
−
U
[
i
−
1
,j
]
,U
[
i, j
]
−
U
[
i
+1
,j
]
,
0
}
1
h
2
max
2
.
(10.5)
{
U
[
i, j
]
−
U
[
i, j
−
1]
,U
[
i, j
]
−
U
[
i, j
+1]
,
0
}
+
During the course of the algorithm, points that have not been considered
yet are labeled
Far
. Points that have been assigned a temporary value for
U
are labeled
Trial
. Points for which
U
has been finalized are labeled
Known
.
Search WWH ::
Custom Search