On the Accuracy of Anisotropic Fast Marching
For researchers using eikonal equations in anisotropic settings (e.g., image processing), this work provides theoretical guarantees for a robust algorithm.
The paper proves that a lattice basis reduction-based fast marching variant maintains accuracy independent of anisotropy ratio for constant metrics, and extends the algorithm to higher dimensions.
The fast marching algorithm, and its variants, solves numerically the generalized eikonal equation associated to an underlying riemannian metric. A major challenge for these algorithms is the non-isotropy of the riemannian metric. Applications of the eikonal equation to image processing often involve pronounced anisotropies, which motivated the design of new algorithms. A recently introduced variant of the fast marching algorithm addresses the problem of large anisotropies using an algebraic tool named lattice basis reduction. The numerical complexity of this algorithm is insensitive to anisotropy, under weak assumptions. We establish in this paper, in the simplified setting of a constant riemannian metric, that the accuracy of this algorithm is also extremely robust to anisotropy : in an average sense, it is independent of the anisotropy ratio. We also extend this algorithm to higher dimension.