PaperlayerView exact revision on arXiv

Source-linked AI summary

Anisotropic Fast-Marching on cartesian grids using Lattice Basis Reduction

Jean-Marie Mirebeau

arXiv:1201.1546v3math.NAcs.NA

TL;DR

High-resolution medical imaging motivates solving anisotropic eikonal equations on Cartesian grids at a computational cost compatible with user interaction. FM-LBR combines Fast Marching with lattice basis reduction to construct sparse causal stencils. The paper reports consistency for arbitrary continuous Riemannian metrics and quasi-linear complexity comparable to classical isotropic Fast Marching.

  • Problem

    Medical image analysis can require high-resolution solutions of highly anisotropic generalized eikonal equations on Cartesian grids at a cost compatible with user interaction.

    Source: Introduction · p. 1

  • Method

    FM-LBR combines Fast Marching with lattice basis reduction to construct sparse causal stencils for the anisotropic eikonal equation.

    Source: Introduction · p. 1

  • Results

    FM-LBR is consistent for any continuous Riemannian metric, has numerical cost comparable to classical isotropic Fast Marching, and has competitive accuracy in general.

    Source: Conclusion · p. 20

  • Takeaways & Limitations

    Its stencil construction has numerical cost O(1 + ln κ(M)), supporting the paper's aim of handling large or extreme anisotropies at reduced numerical cost.

    Source: Introduction · p. 1, §2.2 · p. 12

    FM-LBR is specialized to Riemannian metrics on Cartesian grids in dimensions two or three, rather than general Finsler metrics.

    Source: Conclusion · p. 20

Abstract

from arXiv · show

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.

Introduction

The paper introduces FM-LBR for solving anisotropic eikonal equations on two- or three-dimensional Cartesian grids, motivated in part by high-resolution medical imaging that requires user-interaction-compatible computation. It combines consistency for arbitrary continuous Riemannian metrics with complexity designed to remain manageable under extreme anisotropy.

Introduction

  • FM-LBR uses lattice basis reduction to construct sparse causal stencils for anisotropic eikonal equations on two- or three-dimensional Cartesian grids.The construction uses the interplay between the Riemannian geometry of the PDE and the arithmetic structure of the grid.Source: Introduction · p. 1
  • FM-LBR is a Dijkstra-inspired solver with static stencils, and its stencil cardinality is uniformly bounded independently of the Riemannian metric.Dijkstra-inspired methods solve the discrete system in a single non-iterative pass when their stencils satisfy causality conditions.Source: Introduction · pp. 2–3
  • O(N ln N + N ln κ(M)) is the FM-LBR complexity, compared with O(κ(M)^m N ln N) for OUM and MAOUM.OUM's complexity is asymptotically O(κ(M)^(m−1)N ln N); the FM-LBR stencil-construction cost accounts for the logarithmic anisotropy term.Source: Introduction · p. 3
  • FM-LBR combines consistency for arbitrary continuous Riemannian metrics with quasi-linear complexity, while some fast-marching variants are consistent only for restricted metrics.The paper notes that FM-8 lacks a convergence guarantee for arbitrary metrics.Source: Introduction · pp. 3–4
  • For intended applications, where ln(N) ≲ κ(M) ≤ Υ(M) ≪ N, FM-LBR's complexity is comparable to O(N ln N) and smaller than O(Υ(M)N).The paper presents this as the typical regime for its intended applications.Source: Introduction · p. 4
  • FM-LBR's stencil specialization limits generalization, static adaptive stencils affect memory, and stencil choice makes the discrete solution and its accuracy scheme-dependent.The paper reports competitive accuracy in application-inspired test cases.Source: Introduction · p. 4

1 Sparse causal stencils for the anisotropic eikonal equation

FM-LBR constructs causal stencils of uniformly bounded cardinality for anisotropic eikonal equations, enabling a single-pass Fast Marching solve. In dimensions two and three, its lattice-reduction construction is consistent and has complexity that grows logarithmically with anisotropy.

1 Sparse causal stencils for the anisotropic eikonal equation

  • Causality makes the fixed-point system solvable in a single pass by ordering grid points so each dependency has a smaller distance value.The Fast Marching algorithm traces these dependencies to determine the run-time ordering.Source: §1 · pp. 4–5
  • The algorithm has complexity O(N ln N + N ln κ(M)), combining quasi-linear grid-size cost with logarithmic dependence on metric anisotropy.Each causal stencil costs O(ln κ(M)) to construct.Source: §1 · p. 5
  • Lattice basis reduction constructs M-obtuse superbases, yielding FM-LBR meshes whose stencils are causal and have uniformly bounded cardinality.The superbase construction costs O(ln κ(M)); in 3D the FM-LBR stencil has 14 nonzero vertices, compared with 12 for AD-LBR.Source: §1 · pp. 6–7
  • For dimensions two and three, the FM-LBR mesh family is admissible, and the resulting discrete solutions converge uniformly to the viscosity solution as the grid scale tends to zero.The stated boundedness constants are R = C_mκ(M), with C_2 = 2 and C_3 = 4.Source: §1 · p. 8
  • FM-LBR is restricted to Riemannian metrics, Cartesian grids, and its causal-stencil construction in dimensions two and three.Its stencil specialization limits generalization; large stencils also complicate extending non-null Dirichlet data near boundaries.Source: §1 · pp. 8–9
  • In outflow-boundary experiments, strongly anisotropic corner stencils could leave four grid values infinite, which were excluded from numerical error estimates.The reported case occurred for the rotated square-domain test with θ ∈ [0.56, 0.61] radians.Source: §1 · p. 9
  • FM-LBR uses more memory than AGSI or OUM on grids: by factors of 2–9 in 2D and 2.6–24 in 3D, depending on storage choices.The additional storage is for the non-empty reverse stencils.Source: §1 · p. 10

2 Analysis of the FM-LBR

The analysis uses low-dimensional lattice basis reduction to construct FM-LBR meshes, establish their properties and construction cost, and prove convergence of the discrete solutions to the anisotropic eikonal PDE.

2.1 Introduction to Lattice Basis Reduction

  • For dimensions m ≤ 4, lattice basis reduction produces an M-reduced basis at numerical cost O(1 + ln κ(M)).The iterative reduction takes O(1 + ln κ(M)) steps, each with O(1) elementary-operation cost.Source: §2.1 · p. 11

2.2 Properties of M-acute meshes

  • The FM-LBR stencil construction costs O(1 + ln κ(M)), while its mesh vertices have Euclidean radius bounded by C_mκ(M), with C_2 = 2 and C_3 = 4.The meshes have small radius in the metric norm but can be large in Euclidean distance, with consequences for accuracy.Source: §2.2 · pp. 12–14
  • When M and N are sufficiently close, an N-reduced mesh contains each M-reduced basis vector and its opposite as vertices.The mesh vertices therefore include a basis for the lattice associated with M.Source: §2.2 · p. 14

2.3 Convergence of the FM-LBR

  • Under Proposition 1.9’s assumptions, the bilinear interpolants of the discrete solutions converge uniformly to the anisotropic eikonal PDE solution as the grid scale tends to zero.The proof uses precompactness of the interpolants, identifies subsequential limits as viscosity solutions, and invokes uniqueness.Source: §2.3 · pp. 14–15

3 Numerical experiments

The experiments compare FM-LBR with AGSI, FM-8, and MAOUM on application-inspired anisotropic distance and path problems. FM-LBR shows strong accuracy and runtime results in the tubular-structure tests, while outcomes vary with test geometry and orientation.

Experimental scope

  • The application-inspired tests include outflow boundaries and, in cases 3 and 4, discontinuous metrics, violating some assumptions used in the convergence analysis.The first test also shows that accuracy depends on grid orientation for some methods: AGSI and FM-8 vary more than FM-LBR and MAOUM.Source: §3 · p. 16

First test case

  • At θ = π/6, FM-LBR was unaffected by rotation and became the most accurate method; AGSI and FM-8 errors increased by more than 5×.FM-LBR reduced L∞ and L1 errors by 40% versus AGSI and MAOUM and CPU time by 85%; FM-8 produced larger errors.Source: §3 · p. 16

Third test case, in 2D

  • At 1000×1000, FM-LBR cuts L∞ error by 80% and L1 error by 75% versus AGSI, while reducing CPU time from 11 minutes to 2.5 seconds.In this third, 2D test, FM-8 is not consistent, and FM-LBR’s improved accuracy yields better minimal-path extraction.Source: §3 · pp. 18–19, Figure 8 · p. 18, Figure 9 · p. 19

Fourth test case, in 3D

  • In the 3D test with κ(M) = 50 and over 10 million grid points, FM-LBR took 105s; AGSI took 480s and failed to recover the minimal path.The reported problem is a strongly anisotropic 3D shortest-path computation on a standard laptop.Source: §3 · pp. 18–19, Figure 10 · p. 20

Conclusion

FM-LBR is consistent for anisotropic eikonal equations with continuous Riemannian metrics and offers competitive accuracy, especially in some tubular-segmentation tests. Its scope is limited to Cartesian grids in two or three dimensions and Riemannian metrics.

Conclusion

  • FM-LBR is consistent for continuous Riemannian metrics of arbitrary anisotropy, with numerical cost comparable to classical isotropic Fast Marching.Its accuracy is competitive generally and striking in some tubular-segmentation tests.Source: Conclusion · p. 20
  • The method requires a Cartesian grid, a two- or three-dimensional domain, and a Riemannian rather than general Finsler metric.The paper notes an adaptation to Finsler metrics in 2D.Source: Conclusion · p. 20
  • Figure 11 includes a minimal-path construction, while a hard case with strong anisotropy, metric discontinuity, and low resolution shows zig-zag artifacts.The artifact example is shown at resolution n = 200.Source: Conclusion · p. 21, Figure 11 · p. 21

A Robust extraction of minimal paths

The paper replaces black-box ODE path tracing with a parameter-free procedure that uses the discrete eikonal solution. It trades high-order accuracy for robustness and, with a Dijkstra-inspired eikonal solver, does not get stuck.

A Robust extraction of minimal paths

  • Standard ODE tracing can get stuck, and its expected high-order accuracy is limited by the first-order eikonal discretization and discontinuous vector fields.The vector field is discontinuous at caustics and metric discontinuities.Source: A Robust extraction of minimal paths · p. 21
  • The proposed parameter-free path method uses the discrete eikonal solution instead of black-box interpolation and ODE routines, trading high-order accuracy for robustness.It never gets stuck when paired with a Dijkstra-inspired eikonal solver.Source: A Robust extraction of minimal paths · p. 22
  • At each step, the method selects a grid point and correction offset by minimizing distance to the current point advanced along the discrete direction field.The direction field is evaluated at grid points, which remain close to the extracted piecewise-linear path.Source: A Robust extraction of minimal paths · p. 22
  • Causality makes the sampled distance values strictly decrease, guaranteeing termination of the path-extraction loop.The path is piecewise linear through corrected grid points.Source: A Robust extraction of minimal paths · p. 22
  • Under the stated boundedness assumptions in two dimensions, the correction offsets are bounded by C R^3.The bound follows by bounding each successive offset and induction.Source: A Robust extraction of minimal paths · pp. 22–23

B Stencil size, discretization errors and metric regularity

The section explains how stencil geometry and metric regularity affect FM-LBR accuracy relative to AGSI. The heuristic analysis identifies both conditions favoring FM-LBR and cases where anisotropy can make its accuracy worse.

B Stencil size, discretization errors and metric regularity

  • FM-LBR stencils adapt their orientation and aspect ratio to the metric while keeping constant volume, and are localized in the intrinsic Riemannian geometry.The AGSI stencils are localized with respect to Euclidean distance.Source: B Stencil size, discretization errors… · pp. 23–24
  • The heuristic favors AGSI when metric regularity is better in Euclidean distance, and FM-LBR when it is better in the normalized intrinsic distance.The fifth test uses the ratio K0/K1 to predict which stencil is more accurate.Source: B Stencil size, discretization errors… · p. 24
  • In tubular-structure tests, the metric varies slowly along the tube and quickly across it; despite discontinuities, this behavior is heuristically close to the regularity condition favoring FM-LBR.The authors connect this pattern to FM-LBR’s exceptional performance on those examples.Source: B Stencil size, discretization errors… · p. 24
  • FM-LBR has the best accuracy for a constant metric, where the piecewise-constant metric approximation is exact and interpolation accounts for all error.Source: B Stencil size, discretization errors… · p. 25
  • For the special constant-metric test, AGSI converges in one pass with a suitably initialized priority queue and takes half the FM-LBR CPU time.The queue sorts upwind boundary points by their scalar product with the characteristic direction.Source: B Stencil size, discretization errors… · p. 25
  • In the fifth test, the authors vary anisotropy direction and metric-gradient angle; the favored method changes with their alignment.FM-LBR is favored for ϕ = θ, while AGSI is favored for ϕ = −π/4.Source: B Stencil size, discretization errors… · p. 25
  • For the last parameter set, AGSI’s accuracy advantage exceeds a factor of 6 and may grow unboundedly with anisotropy, so anisotropy can reduce FM-LBR accuracy.The table caption says the more accurate method can often be predicted from K0/K1, but identifies an exception.Source: B Stencil size, discretization errors… · p. 26, Table 1 · p. 26
Loading 1201.1546v3…