Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Nine-point stencil
Numerical analysis method

In numerical analysis, given a square grid in two dimensions, the nine-point stencil of a point in the grid is a stencil made up of the point itself together with its eight "neighbors". It is used to write finite difference approximations to derivatives at grid points. It is an example for numerical differentiation. This stencil is often used to approximate the Laplacian of a function of two variables.

Related Image Collections Add Image
Profiles
1 Image
We don't have any YouTube videos related to Nine-point stencil yet.
We don't have any PDF documents related to Nine-point stencil yet.
We don't have any Books related to Nine-point stencil yet.
We don't have any archived web articles related to Nine-point stencil yet.

Motivation

If we discretize the 2D Laplacian by using central-difference methods, we obtain the commonly used five-point stencil, represented by the following convolution kernel:

D C D = [ 0 1 0 1 − 4 1 0 1 0 ] {\displaystyle D_{CD}={\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}}

Even though it is simple to obtain and computationally lighter, the central difference kernel possess an undesired intrinsic anisotropic property, since it doesn't take into account the diagonal neighbours. This intrinsic anisotropy poses a problem when applied on certain numerical simulations or when more accuracy is required, by propagating the Laplacian effect faster in the coordinate axes directions and slower in the other directions, thus distorting the final result.1

This drawback calls for finding better methods for discretizing the Laplacian, reducing or eliminating the anisotropy.

Implementation

The two most commonly used isotropic nine-point stencils are displayed below, in their convolution kernel forms. They can be obtained by the following formula:23

D = ( 1 − γ ) [ 0 1 0 1 − 4 1 0 1 0 ] + γ [ 1 / 2 0 1 / 2 0 − 2 0 1 / 2 0 1 / 2 ] {\displaystyle D=(1-\gamma ){\begin{bmatrix}0&1&0\\1&-4&1\\0&1&0\end{bmatrix}}+\gamma {\begin{bmatrix}1/2&0&1/2\\0&-2&0\\1/2&0&1/2\end{bmatrix}}}

The first one is known by Oono-Puri,45678 and it is obtained when γ=1/2.9

D O P = [ 1 / 4 2 / 4 1 / 4 2 / 4 − 12 / 4 2 / 4 1 / 4 2 / 4 1 / 4 ] = [ 0.25 0.5 0.25 0.5 − 3 0.5 0.25 0.5 0.25 ] {\displaystyle D_{OP}={\begin{bmatrix}1/4&2/4&1/4\\2/4&-12/4&2/4\\1/4&2/4&1/4\end{bmatrix}}={\begin{bmatrix}0.25&0.5&0.25\\0.5&-3&0.5\\0.25&0.5&0.25\end{bmatrix}}}

The second one is known by Patra-Karttunen or Mehrstellen,1011121314 and it is obtained when γ=1/3.15

D P K = [ 1 / 6 4 / 6 1 / 6 4 / 6 − 20 / 6 4 / 6 1 / 6 4 / 6 1 / 6 ] = [ 0.16 0.66 0.16 0.66 − 3.33 0.66 0.16 0.66 0.16 ] {\displaystyle D_{PK}={\begin{bmatrix}1/6&4/6&1/6\\4/6&-20/6&4/6\\1/6&4/6&1/6\end{bmatrix}}={\begin{bmatrix}0.16&0.66&0.16\\0.66&-3.33&0.66\\0.16&0.66&0.16\end{bmatrix}}}

Both are isotropic forms of discrete Laplacian,16 and in the limit of small Δx, they all become equivalent,17 as Oono-Puri being described as the optimally isotropic form of discretization,18 displaying reduced overall error,19 and Patra-Karttunen having been systematically derived by imposing conditions of rotational invariance,20 displaying smallest error around the origin.21

Desired anisotropy

On the other hand, if controlled anisotropic effects are a desired feature, when solving anisotropic diffusion problems for example, it is also possible to use the 9-point stencil combined with tensors to generate them.

Consider the laplacian in the following form:

c ∇ 2 A = c D O P ∗ A {\displaystyle c\nabla ^{2}A=cD_{OP}*A}

Where c is just a constant coefficient. Now if we replace c by the 2nd rank tensor C:

C = [ c 1 0 0 c 2 ] {\displaystyle C={\begin{bmatrix}c_{1}&0\\0&c_{2}\end{bmatrix}}}

Where c1 is the constant coefficient for the principal direction in x axis, and c2 is the constant coefficient for the secondary direction in y axis. In order to generate anisotropic effects, c1 and c2 must be different.

By multiplying it by the rotation matrix Q, we obtain C', allowing anisotropic propagations in arbitrary directions other than the coordinate axes.2223

Q = [ cos ⁡ θ sin ⁡ θ − sin ⁡ θ cos ⁡ θ ] {\displaystyle Q={\begin{bmatrix}\cos \theta &\sin \theta \\-\sin \theta &\cos \theta \end{bmatrix}}}

C ′ = Q C Q T {\displaystyle C'=QCQ^{\operatorname {T} }}

C ′ = [ c x x c x y c x y c y y ] = [ c 1 cos 2 ⁡ θ + c 2 sin 2 ⁡ θ ( c 2 − c 1 ) cos ⁡ θ sin ⁡ θ ( c 2 − c 1 ) cos ⁡ θ sin ⁡ θ c 2 cos 2 ⁡ θ + c 1 sin 2 ⁡ θ ] {\displaystyle C'={\begin{bmatrix}c_{xx}&c_{xy}\\c_{xy}&c_{yy}\end{bmatrix}}={\begin{bmatrix}c_{1}\cos ^{2}\theta +c_{2}\sin ^{2}\theta &(c_{2}-c_{1})\cos \theta \sin \theta \\(c_{2}-c_{1})\cos \theta \sin \theta &c_{2}\cos ^{2}\theta +c_{1}\sin ^{2}\theta \end{bmatrix}}}

Which is very similar to the Cauchy stress tensor in 2 dimensions. The angle θ {\displaystyle \theta } can be obtained by generating a vector field V = V x i + V y j {\displaystyle \mathbf {V} =V_{x}{\mathbf {i} }+V_{y}{\mathbf {j} }} in order to orientate the pattern as desired.24 Then:

θ = arctan ⁡ ( V y / V x ) {\displaystyle \theta =\arctan(V_{y}/V_{x})}

Or, for different anisotropic effects using the same vector field25

θ = arctan ⁡ ( V y / − V x ) {\displaystyle \theta =\arctan(V_{y}/-V_{x})}

It is important to note that, regardless of the values of θ {\displaystyle \theta } , the anisotropic propagation will occur parallel to the secondary direction c2 and perpendicular to the principal direction c1:.26 The resulting convolution kernel is as follows27

D A n i s o = [ − c x y 2 c y y c x y 2 c x x − 2 ( c x x + c y y ) c x x c x y 2 c y y − c x y 2 ] {\displaystyle D_{Aniso}={\begin{bmatrix}{\frac {-c_{xy}}{2}}&c_{yy}&{\frac {c_{xy}}{2}}\\c_{xx}&-2(c_{xx}+c_{yy})&c_{xx}\\{\frac {c_{xy}}{2}}&c_{yy}&{\frac {-c_{xy}}{2}}\end{bmatrix}}}

If, for example, c1=c2=1, the cxy component will vanish, resulting in the simple five-point stencil, rendering no controlled anisotropy.

If c2>c1 and θ {\displaystyle \theta } =0, the anisotropic effects will be more pronounced in the vertical axis.

If c2>c1 and θ {\displaystyle \theta } =45 degrees, the anisotropic effects will be more pronounced in the upper-right / lower-left diagonal.

References

  1. Patra, Michael; Karttunen, Mikko (2006). "Stencils with isotropic discretization error for differential operators". Numerical Methods for Partial Differential Equations. 22 (4): 3–7. doi:10.1002/num.20129. S2CID 123145969. /wiki/Doi_(identifier) ↩

  2. Fomel, Sergey; Claerbout, Jon F. (9 October 1997). "Constructing an isotropic Laplacian operator". Exploring three-dimensional implicit wavefield extrapolation with the helix transform. Stanford Exploration Project. http://sepwww.stanford.edu/public/docs/sep95/sergey2/paper_html/node12.html ↩

  3. Lindeberg, Tony. "Scale-Space for Discrete Signals" (PDF). Stockholm: Royal Institute of Technology. pp. 22–23. http://kth.diva-portal.org/smash/get/diva2:472968/FULLTEXT01.pdf ↩

  4. Oono, Y.; Puri, S. (1987). "Computationally efficient modeling of ordering of quenched phases" (PDF). Physical Review Letters. 58 (8): 837. Bibcode:1987PhRvL..58..836O. doi:10.1103/PhysRevLett.58.836. PMID 10035049. http://repository.ias.ac.in/31904/1/31904.pdf ↩

  5. Oono, Y.; Puri, S. (1988). "Study of phase-separation dynamics by use of cell dynamical systems. I. Modeling" (PDF). Physical Review A. 38 (1): 436. Bibcode:1988PhRvA..38..434O. doi:10.1103/PhysRevA.38.434. PMID 9900182. http://repository.ias.ac.in/32406/1/32406.pdf ↩

  6. Sevink, G. J. A. (2015). "Rigorous embedding of cell dynamics simulations in the Cahn-Hilliard-Cook framework: Imposing stability and isotropy". Physical Review E. 91 (5): 4. Bibcode:2015PhRvE..91e3309S. doi:10.1103/PhysRevE.91.053309. hdl:1887/3194035. PMID 26066281. https://scholarlypublications.universiteitleiden.nl/access/item%3A3194036/download ↩

  7. "Rotation-invariant Laplacian for 2D grids". 21 March 2021. https://eng.aurelienpierre.com/2021/03/rotation-invariant-laplacian-for-2d-grids/ ↩

  8. "Investigation of Isotropic Laplacian Operators by Computer Simulation for A-B Diblock Copolymers" (PDF). IJCSNS International Journal of Computer Science and Network Security. 18 (5): 102–103. May 2018. http://paper.ijcsns.org/07_book/201805/20180514.pdf ↩

  9. Fomel, Sergey; Claerbout, Jon F. (9 October 1997). "Constructing an isotropic Laplacian operator". Exploring three-dimensional implicit wavefield extrapolation with the helix transform. Stanford Exploration Project. http://sepwww.stanford.edu/public/docs/sep95/sergey2/paper_html/node12.html ↩

  10. Patra, Michael; Karttunen, Mikko (2006). "Stencils with isotropic discretization error for differential operators". Numerical Methods for Partial Differential Equations. 22 (4): 3–7. doi:10.1002/num.20129. S2CID 123145969. /wiki/Doi_(identifier) ↩

  11. "Rotation-invariant Laplacian for 2D grids". 21 March 2021. https://eng.aurelienpierre.com/2021/03/rotation-invariant-laplacian-for-2d-grids/ ↩

  12. "Investigation of Isotropic Laplacian Operators by Computer Simulation for A-B Diblock Copolymers" (PDF). IJCSNS International Journal of Computer Science and Network Security. 18 (5): 102–103. May 2018. http://paper.ijcsns.org/07_book/201805/20180514.pdf ↩

  13. Thampi, Sumesh P.; Ansumali, Santosh; Adhikari, R.; Succi, Sauro (2013), "Isotropic discrete Laplacian operators from lattice hydrodynamics", Journal of Computational Physics, 234: 3–7, arXiv:1202.3299, Bibcode:2013JCoPh.234....1T, doi:10.1016/j.jcp.2012.07.037, S2CID 14633171 /wiki/ArXiv_(identifier) ↩

  14. Lynch, Robert (7 January 1992), "Fundamental Solutions of 9-point Discrete Laplacians; Derivation and Tables", Department of Computer Science Technical Reports: 2 https://docs.lib.purdue.edu/cstech/929 ↩

  15. Fomel, Sergey; Claerbout, Jon F. (9 October 1997). "Constructing an isotropic Laplacian operator". Exploring three-dimensional implicit wavefield extrapolation with the helix transform. Stanford Exploration Project. http://sepwww.stanford.edu/public/docs/sep95/sergey2/paper_html/node12.html ↩

  16. "Investigation of Isotropic Laplacian Operators by Computer Simulation for A-B Diblock Copolymers" (PDF). IJCSNS International Journal of Computer Science and Network Security. 18 (5): 102–103. May 2018. http://paper.ijcsns.org/07_book/201805/20180514.pdf ↩

  17. Provatas, Nikolas; Elder, Ken (2010), Phase-Field Methods in Materials Science and Engineering (PDF), p. 219, doi:10.1002/9783527631520, ISBN 9783527631520 9783527631520 ↩

  18. "Investigation of Isotropic Laplacian Operators by Computer Simulation for A-B Diblock Copolymers" (PDF). IJCSNS International Journal of Computer Science and Network Security. 18 (5): 102–103. May 2018. http://paper.ijcsns.org/07_book/201805/20180514.pdf ↩

  19. Fomel, Sergey; Claerbout, Jon F. (9 October 1997). "Constructing an isotropic Laplacian operator". Exploring three-dimensional implicit wavefield extrapolation with the helix transform. Stanford Exploration Project. http://sepwww.stanford.edu/public/docs/sep95/sergey2/paper_html/node12.html ↩

  20. Thampi, Sumesh P.; Ansumali, Santosh; Adhikari, R.; Succi, Sauro (2013), "Isotropic discrete Laplacian operators from lattice hydrodynamics", Journal of Computational Physics, 234: 3–7, arXiv:1202.3299, Bibcode:2013JCoPh.234....1T, doi:10.1016/j.jcp.2012.07.037, S2CID 14633171 /wiki/ArXiv_(identifier) ↩

  21. Fomel, Sergey; Claerbout, Jon F. (9 October 1997). "Constructing an isotropic Laplacian operator". Exploring three-dimensional implicit wavefield extrapolation with the helix transform. Stanford Exploration Project. http://sepwww.stanford.edu/public/docs/sep95/sergey2/paper_html/node12.html ↩

  22. McGinty, Bob (2012). "Coordinate Transforms". continuummechanics.org. http://www.continuummechanics.org/coordxforms.html ↩

  23. Witkin, Andrew; Kass, Michael (1991), "Reaction-diffusion textures" (PDF), ACM SIGGRAPH Computer Graphics, 25 (4): 3–4, doi:10.1145/127719.122750 http://www.cs.cmu.edu/afs/cs.cmu.edu/user/aw/www/pdf/texture.pdf ↩

  24. Witkin, Andrew; Kass, Michael (1991), "Reaction-diffusion textures" (PDF), ACM SIGGRAPH Computer Graphics, 25 (4): 3–4, doi:10.1145/127719.122750 http://www.cs.cmu.edu/afs/cs.cmu.edu/user/aw/www/pdf/texture.pdf ↩

  25. Sanderson, Allen R.; Kirby, Robert M.; Johnson, Chris R.; Yang, Lingfa (2006), "Advanced Reaction-Diffusion Models for Texture Synthesis" (PDF), Journal of Graphics Tools, 11 (3): 4, doi:10.1080/2151237X.2006.10129222, S2CID 13132043 http://www.sci.utah.edu/~allen/materials/Sanderson_JGT_2006.pdf ↩

  26. Garnier, David-Henri; Schmidt, Martin-Pierre; Rohmer, Damien (2022), "Growth of oriented orthotropic structures with reaction/Diffusion", Structural and Multidisciplinary Optimization, 65 (11): 7–8, doi:10.1007/s00158-022-03395-7, S2CID 253304840 https://hal.science/hal-03842830v1/document ↩

  27. Witkin, Andrew; Kass, Michael (1991), "Reaction-diffusion textures" (PDF), ACM SIGGRAPH Computer Graphics, 25 (4): 3–4, doi:10.1145/127719.122750 http://www.cs.cmu.edu/afs/cs.cmu.edu/user/aw/www/pdf/texture.pdf ↩