A fast marching algorithm for the factored eikonal equation
Preprint
Abstract
The eikonal equation is instrumental in many applications in several fields ranging from computer vision to geoscience. This equation can be efficiently solved using the iterative Fast Sweeping (FS) methods and the direct Fast Marching (FM) methods. However, when used for a point source, the original eikonal equation is known to yield inaccurate numerical solutions, because of a singularity at the source. In this case, the factored eikonal equation is often preferred, and is known to yield a more accurate numerical solution. One application that requires the solution of the eikonal equation for point sources is travel time tomography. This inverse problem may be formulated using the eikonal equation as a forward problem. While this problem has been solved using FS in the past, the more recent choice for applying it involves FM methods because of the efficiency in which sensitivities can be obtained using them. However, while several FS methods are available for solving the factored equation, the FM method is available only for the original eikonal equation. In this paper we develop a Fast Marching algorithm for the factored eikonal equation, using both first and second order finite-difference schemes. Our algorithm follows the same lines as the original FM algorithm and requires the same computational effort. In addition, we show how to obtain sensitivities using this FM method and apply travel time tomography, formulated as an inverse factored eikonal equation. Numerical results in two and three dimensions show that our algorithm solves the factored eikonal equation efficiently, and demonstrate the achieved accuracy for computing the travel time. We also demonstrate a recovery of a 2D and 3D heterogeneous medium by travel time tomography using the eikonal equation for forward modelling and inversion by Gauss-Newton.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Fast Huygens sweeping methods for Helmholtz equations in inhomogeneous media in the high frequency regimeJournal of Computational Physics, 2014
- Factored singularities and high-order Lax–Friedrichs sweeping schemes for point-source traveltimes and amplitudesJournal of Computational Physics, 2011
- A fast method for the solution of the Helmholtz equationJournal of Computational Physics, 2011
- Fast sweeping method for the factored eikonal equationJournal of Computational Physics, 2009
- A Fast Sweeping Method for Static Convex Hamilton–Jacobi EquationsJournal of Scientific Computing, 2007
- Statistical and Computational Inverse Problems2005
- Lax–Friedrichs sweeping scheme for static Hamilton–Jacobi equationsJournal of Computational Physics, 2004
- Computing geodesic paths on manifoldsProceedings of the National Academy of Sciences, 1998
- A fast marching level set method for monotonically advancing fronts.Proceedings of the National Academy of Sciences, 1996
- Nonlinear total variation based noise removal algorithmsPhysica D: Nonlinear Phenomena, 1992