A variational formulation of the fast marching eikonal solver

Next: Solving the eikonal equation Up: Fomel: Fast marching Previous: The theoretic grounds of

# Variational principles on a grid

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

 (9)

Now let us consider an arbitrary point in the vicinity of . If we know that the ray from the source to passes through some point of the segment , then the total traveltime at is approximately
 (10)

where is the local slowness, corresponds to the projection of to the line (normalized by the length ), and is the length of the normal from to .

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

 (11)

which has (as a quadratic equation) the explicit solution for :
 (12)

Finally, substituting the value of from (12) into equation (10) and selecting the appropriate branch of the square root, we obtain the formula
 (13)

where , , , angle corresponds to , and angle corresponds to in the triangle (Figure 3).

square
Figure 4.
NR

A geometrical scheme for traveltime updating on a rectangular grid.

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

 (14)

We can notice that (14) is precisely equivalent to the solution of the quadratic equation (13), which in our new notation takes the form
 (15)

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

Next: Solving the eikonal equation Up: Fomel: Fast marching Previous: The theoretic grounds of

2013-03-03