Anisotropic Fast-Marching on cartesian grids using Lattice Basis Reduction

Abstract

We introduce a modification of the Fast Marching Algorithm, which solves the generalized eikonal equation associated to an arbitrary continuous riemannian metric, on a two or three dimensional domain. The algorithm has a logarithmic complexity in the maximum anisotropy ratio of the riemannian metric, which allows to handle extreme anisotropies for a reduced numerical cost. We prove the consistence of the algorithm, and illustrate its efficiency by numerical experiments. The algorithm relies on the computation at each grid point of a special system of coordinates: a reduced basis of the cartesian grid, with respect to the symmetric positive definite matrix encoding the desired anisotropy at this point.

28 pages, 12 figures

References in corpus (1)

• Finite-Element Discretization of Static Hamilton-Jacobi Equations Based on a Local Variational Principle

Cited by in corpus (8)

• Global Minimum for a Finsler Elastica Minimal Path Approach
• Geometrical Optical Illusion via Sub-Riemannian Geodesics in the Roto-Translation Group
• Minimal Paths for Tubular Structure Segmentation with Coherence Penalty and Adaptive Anisotropy
• A Generalized Asymmetric Dual-front Model for Active Contours and Image Segmentation
• Tracking of Lines in Spherical Images via Sub-Riemannian Geodesics on SO(3)
• Fast Asymmetric Fronts Propagation for Image Segmentation
• A cortical-inspired sub-Riemannian model for Poggendorff-type visual illusions
• Numerical geometric acoustics: an eikonal-based approach for modeling sound propagation in 3D environments