A variational formulation of the fast marching eikonal solver |
In this section, I derive a discrete traveltime computation procedure, based solely on Fermat's principle, and show that on a Cartesian rectangular grid it is precisely equivalent to the update formula (1) of the first-order eikonal solver.
triangle
Figure 3. A geometrical scheme for the traveltime updating procedure in two dimensions. | |
---|---|
For simplicity, let us focus on the two-dimensional case. Consider a line segment with the end points and ,
as shown in Figure 3. Let and denote the
traveltimes from a fixed distant source to points and ,
respectively. Define a parameter such that at ,
at , and changes continuously on the line segment
between and . Then for each point of the segment, we can
approximate the traveltime by the linear interpolation formula
Fermat's principle states that the actual ray to corresponds to a
local minimum of the traveltime with respect to raypath perturbations.
According to our parameterization, it is sufficient to find a local
extreme of with respect to the parameter . Equating the
derivative to zero, we arrive at the equation
square
Figure 4. NR | |
---|---|
To see the connection of formula (13) with the eikonal
difference equation (1), we need to consider the case
of a rectangular computation cell with the edge being a diagonal
segment, as illustrated in Figure 4. In this case,
,
,
, and formula (13) reduces to
What have we accomplished by this analysis? First, we have derived a local traveltime computation formula for an arbitrary grid. The derivation is based solely on Fermat's principle and a local linear interpolation, which provides the first-order accuracy. Combined with the fast marching evaluation order, which is also based on Fermat's principle, this procedure defines a complete algorithm of first-arrival traveltime calculation. On a rectangular grid, this algorithm is exactly equivalent to the fast marching method of Sethian (1996a) and Sethian and Popovici (1997). Second, the derivation provides a general principle, which can be applied to derive analogous algorithms for other eikonal-type (Hamilton-Jacobi) equations and their corresponding variational principles.
A variational formulation of the fast marching eikonal solver |