Efficient Fast Marching with Finsler metrics
Mirebeau, Jean-Marie (2013), Efficient Fast Marching with Finsler metrics, Numerische Mathematik, 126, 3, p. 515-557. http://dx.doi.org/10.1007/s00211-013-0571-3
TypeArticle accepté pour publication ou publié
External document linkhttp://hal.archives-ouvertes.fr/hal-00736431
Journal nameNumerische Mathematik
MetadataShow full item record
Abstract (EN)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 methods. 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.
Subjects / KeywordsAnisotropic Finsler metric; Fast Marching; Hamilton Jacobi
Showing items related by title and author.
Vessel Tree Extraction using Radius-Lifted Keypoints Searching Scheme and Anisotropic Fast Marching Method Chen, Da; Mirebeau, Jean-Marie; Cohen, Laurent D. (2016) Article accepté pour publication ou publié