Efficient fast marching with Finsler metrics

DOI10.1007/S00211-013-0571-3zbMATH Open1297.65074arXiv1208.1430OpenAlexW2123698257MaRDI QIDQ2454033FDOQ2454033

Authors: Jean-Marie Mirebeau 

Publication date: 12 June 2014

Published in: Numerische Mathematik (Search for Journal in Brave)

Abstract: We study the discretization of the Escape Time problem: find the length of the shortest path joining an arbitrary point of a domain, to the domain's boundary. Path length is measured locally via a Finsler metric, potentially asymmetric and strongly anisotropic. This Optimal Control problem can be reformulated as a static Hamilton Jacobi, or Anisotropic Eikonal, Partial Differential Equation, as well as a front propagation model. It has numerous applications, ranging from motion planning to image segmentation. We introduce a new algorithm, Fast Marching using Anisotropic Stencil Refinement (FM-ASR), which addresses this problem on a two dimensional domain discretized on a cartesian grid. The local stencils used in our discretization are produced by arithmetic means. The complexity of the FM-ASR, in an average sense over all grid orientations, only depends (poly-)logarithmically on the anisotropy ratio of the metric, while most alternative approaches have a polynomial dependence. Numerical experiments show, in several occasions, that the accuracy/complexity compromise is improved by an order of magnitude or more.

Full work available at URL: https://arxiv.org/abs/1208.1430

Recommendations

• Anisotropic fast-marching on Cartesian grids using lattice basis reduction
• Fast Marching Methods
• Fast marching methods for stationary Hamilton-Jacobi equations with axis-aligned anisotropy
• Some improvements of the fast marching method
• Fast-marching methods for curvature penalized shortest paths

zbMATH Keywords

discretizationcomplexitynumerical experimentsfast marching algorithmanisotropic stencil refinementescape time problemFinsler metric, optimal controlHamilton Jacobi PDEshortest way

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Hamilton-Jacobi equations (35F21) Existence theories for optimal control problems involving partial differential equations (49J20) Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games (49L25) Applications of optimal control and differential games (49N90)

Cites Work

• Title not available (Why is that?)
• Ordered Upwind Methods for Static Hamilton--Jacobi Equations: Theory and Algorithms
• Fast Sweeping Algorithms for a Class of Hamilton--Jacobi Equations
• A fast sweeping method for Eikonal equations
• Efficient algorithms for globally optimal trajectories
• Title not available (Why is that?)
• Geodesic methods in computer vision and graphics
• Title not available (Why is that?)
• An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi equations
• Label-setting methods for multimode stochastic shortest path problems on graphs
• Homogenization of metric Hamilton-Jacobi equations
• Fast marching methods for stationary Hamilton-Jacobi equations with axis-aligned anisotropy
• Remarks on the implementation of the fast marching method

Cited In (23)

• Single pass computation of first seismic wave travel time in three dimensional heterogeneous media with general anisotropy
• Corner cases, singularities, and dynamic factoring
• Monotone discretization of the Monge–Ampère equation of optimal transport
• Adaptive, anisotropic and hierarchical cones of discrete convex functions
• Ordered line integral methods for solving the eikonal equation
• A linear finite-difference scheme for approximating randers distances on cartesian grids
• Minimal stencils for discretizations of anisotropic PDEs preserving causality or the maximum principle
• Monotone and consistent discretization of the Monge-Ampère operator
• Numerical geometric acoustics: an eikonal-based approach for modeling sound propagation in 3D environments
• Robust shortest path planning and semicontractive dynamic programming
• Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis
• Some improvements of the fast marching method
• Augmented Lagrangian methods for degenerate Hamilton-Jacobi equations
• Quantifying and Managing Uncertainty in Piecewise-Deterministic Markov Processes
• A primal-dual algorithm for computing Finsler distances and applications
• Riemannian Fast-Marching on Cartesian Grids, Using Voronoi's First Reduction of Quadratic Forms
• Anisotropic fast-marching on Cartesian grids using lattice basis reduction
• Fast asymmetric fronts propagation for image segmentation
• Fast-marching methods for curvature penalized shortest paths
• Evasive path planning under surveillance uncertainty
• Global minimum for a Finsler elastica minimal path approach
• An efficient jet marcher for computing the quasipotential for 2D SDEs. Enhancing accuracy and efficiency of quasipotential solvers
• Control-Theoretic Models of Environmental Crime

This page was built for publication: Efficient fast marching with Finsler metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2454033)