Sparse Non-Negative Stencils for Anisotropic Diffusion

Jérôme Fehrenbach (1) , Jean-Marie Mirebeau (2)

1 IMT - Institut de Mathématiques de Toulouse UMR5219
2 CEREMADE - CEntre de REcherches en MAthématiques de la DEcision

We introduce a new discretization scheme for Anisotropic Diffusion, AD-LBR, on two and three dimensional cartesian grids. The main features of this scheme is that it is non-negative, and has a stencil size bounded by 6 in 2D, by 14 in 3D, despite allowing diffusion tensors of arbitrary anisotropy. It also has good spectral properties, which permits larger time steps and avoids e.g. chessboard artifacts. AD-LBR relies on Lattice Basis Reduction, a tool from discrete mathematics which has recently shown its relevance for the discretization on grids of strongly anisotropic Partial Differential Equations. We prove that AD-LBR is in 2D asymptotically equivalent to a finite element discretization on an anisotropic Delaunay triangulation, a procedure more involved and computa- tionally expensive. Our scheme thus benefits from the theoretical guarantees of this procedure, for a fraction of its cost. Numerical experiments in 2D and 3D illus- trate our results.

Mots clés: Non-Negative Numerical Scheme; Lattice Basis Reduction; Anisotropic Diffusion

Domaines: Equations aux dérivées partielles [math.AP]; Traitement des images [eess.IV]

Jérôme Fehrenbach, Jean-Marie Mirebeau. Sparse Non-Negative Stencils for Anisotropic Diffusion. Journal of Mathematical Imaging and Vision, 2013, pp.1-25. ⟨10.1007/s10851-013-0446-3⟩. ⟨hal-00776860v2⟩