Efficient fast marching with Finsler metrics
From MaRDI portal
Publication:2454033
discretizationcomplexitynumerical experimentsfast marching algorithmanisotropic stencil refinementescape time problemFinsler metric, optimal controlHamilton Jacobi PDEshortest way
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)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3783507 (Why is no real title available?)
- scientific article; zbMATH DE number 53999 (Why is no real title available?)
- scientific article; zbMATH DE number 976936 (Why is no real title available?)
- A fast sweeping method for Eikonal equations
- An ordered upwind method with precomputed stencil and monotone node acceptance for solving static convex Hamilton-Jacobi equations
- Efficient algorithms for globally optimal trajectories
- Fast Sweeping Algorithms for a Class of Hamilton--Jacobi Equations
- Fast marching methods for stationary Hamilton-Jacobi equations with axis-aligned anisotropy
- Geodesic methods in computer vision and graphics
- Homogenization of metric Hamilton-Jacobi equations
- Label-setting methods for multimode stochastic shortest path problems on graphs
- Ordered Upwind Methods for Static Hamilton--Jacobi Equations: Theory and Algorithms
- Remarks on the implementation of the fast marching method
Cited in
(23)- Corner cases, singularities, and dynamic factoring
- Robust shortest path planning and semicontractive dynamic programming
- Numerical geometric acoustics: an eikonal-based approach for modeling sound propagation in 3D environments
- Some improvements of the fast marching method
- An efficient jet marcher for computing the quasipotential for 2D SDEs. Enhancing accuracy and efficiency of quasipotential solvers
- Evasive path planning under surveillance uncertainty
- Monotone discretization of the Monge-Ampère equation of optimal transport
- 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
- Single pass computation of first seismic wave travel time in three dimensional heterogeneous media with general anisotropy
- A primal-dual algorithm for computing Finsler distances and applications
- Quantifying and Managing Uncertainty in Piecewise-Deterministic Markov Processes
- Anisotropic fast-marching on Cartesian grids using lattice basis reduction
- Control-theoretic models of environmental crime
- Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis
- Monotone and consistent discretization of the Monge-Ampère operator
- Augmented Lagrangian methods for degenerate Hamilton-Jacobi equations
- Fast asymmetric fronts propagation for image segmentation
- Fast-marching methods for curvature penalized shortest paths
- Adaptive, anisotropic and hierarchical cones of discrete convex functions
- Riemannian fast-marching on cartesian grids, using Voronoi's first reduction of quadratic forms
- Global minimum for a Finsler elastica minimal path approach
- Ordered line integral methods for solving the eikonal equation
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)
