How was the 2D discrete Laplacian matrix calculated

laplacian

If I convolute a 2D signal with the L4 kernel, I get the discrete Laplacian. But how was the L4 kernel calculated?

Wikipedia isn't very clear on this and I haven't found other information.
(https://en.wikipedia.org/wiki/Discrete_Laplace_operator#Implementation_via_operator_discretization)

I've also read this but it's still unclear how the convolution of [1, -2, 1] is L4 transposed.

L4 being this:

 L4 =
  [ 0 -1  0;
   -1  4 -1;
    0 -1  0];

EDIT:
Also, how is the L8 produced?

 L8 =
  [-1 -1 -1;
   -1  8 -1;
   -1 -1 -1];

Best Answer

Basically the 2D "L4" discrete Laplacian operator is constructed by using 4 surrounding points from a central stencil point. These stencil points are north, south, east and west from the central point. In space these 5 stencil points are then given by: $$ (x,y), (x+h,y), (x,y+h), (x-h,y), (x,y-h)$$

Remembering that $$\nabla^{2} f = f_{xx}+f_{yy} $$ and that a 2D Taylor expansion (up to a point) may be seen as: $$f(x+\delta x,y+\delta y)=f(x,y)+(f_{x}\delta x + f_{y}\delta y)+ \frac{1}{2}(f_{xx}(\delta x)^{2}+2f_{xy} \delta x \delta y + f_{yy}(\delta y)^{2})+O((\delta x)^{3}+(\delta y)^{3})$$ We can then find that $$f(x\pm h, y)= f(x,y) \pm f_{x}h+\frac{1}{2}f_{xx}h^{2}+O(h^{3})$$

$$f(x, y\pm h)= f(x,y) \pm f_{y}h+\frac{1}{2}f_{yy}h^{2}+O(h^{3})$$

By summing expressions we may obtain $$(1) \qquad f(x+h,y)+f(x-h,y)=2f+f_{xx}h^{2}+O(h^{3})$$

$$(2) \qquad f(x,y+h)+f(x,y-h)=2f+f_{yy}h^{2}+O(h^{3})$$ Calculating (1) + (2): $$ f(x,y+h)+f(x,y-h)+f(x+h,y)+f(x-h,y) = 4f +h^{2}(f_{xx}+f_{yy})$$ Then using our very first equation (Cartesian Laplacian definition) we are certain that we approximated our Laplacian up to 2nd order: $$\nabla^{2} f = f_{xx}+f_{yy}= \frac{1}{h^{2}} \Big[f(x,y+h)+f(x,y-h)+f(x+h,y)+f(x-h,y) -4f(x,y) \Big]$$

As indeed we want to see this in a discrete 2D space, we may correspond the coefficients of our stencils onto a matrix where $h=1$ $$ L4 = \frac{1}{h^2}\begin{pmatrix} c_{f(x-h,y+h)} & c_{f(x,y+h)} & c_{f(x+h,y+h)}\\ c_{f(x-h,y)} & c_{f(x,y)} & c_{f(x+h,y)}\\ c_{f(x-h,y-h)} & c_{f(x,y-h)} & c_{f(x+h,y-h)}\\ \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0\\ 1 & -4 & 1\\ 0 & 1 & 0\\ \end{pmatrix} $$

One can follow a similar procedure to obtain L8 by using a 9-stencil configuration where the stencils would be $$ f(x,y), f(x+h,y+h),f(x+h,y),f(x+h,y-h), f(x,y-h), f(x,y+h), f(x-h,y-h),f(x-h,y+h),f(x-h,y) $$

Related Question