Anisotropic fast-marching on Cartesian grids using lattice basis reduction (Q2927823)

In order to solve the anisotropic eikonal equation associated to an arbitrary continuous Riemann metric \(\mathcal{M}\) on a two- or three-dimensional domain, the author presents a modification of the fast-marching algorithm, the fast-marching using lattice basis reduction (FM-LBR) algorithm which relies on the computation at each grid point \(z\) of a special system of coordinates: a reduced basis of the lattice \(\mathbb{Z} ^{m}\), with respect to the symmetric positive definite matrix \(\mathcal{M} \left( z\right) \) encoding the desired anisotropy at this point. The algorithm has a complexity \(\mathcal{O}\left( M\ln N+N\ln k\left( \mathcal{M} \right) \right) \), where \(N\) is the discrete domain cardinality and \(k\left( \mathcal{M}\right) \) is the maximum anisotropy ratio. The FM-LBR is consistent for the anisotropic eikonal equation and has a complexity comparable to classical isotropic fast-marching, independently of the problem anisotropy. The accuracy of the FM-LBR is striking in test cases related to tubular segmentation in medical images, where the Riemannian metric has a pronounced anisotropy close to and tangentially to a curve. The convergence of the algorithm is proved and its efficiency is illustrated by numerical experiments.