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. ()
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];1 Answer
$\begingroup$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,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,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) $$
$\endgroup$
