I don't really follow how they came up with the derivative equation. Could somebody please explain in some details or even a link to somewhere with sufficient math explanation?
Laplacian filter looks like
Asked
Active
Viewed 1.1k times
7
hippietrail
- 15,848
- 18
- 99
- 158
wisdom
- 412
- 2
- 5
- 20
-
2nd row is for x-derivative and 2nd column is y-derivative, so when you add both of them then it becomes above matrix i.e. `f(x+1,y) + f(x-1,y) -2f(x,y) + f(x,y+1) + f(x,y-1) - 2f(x,y)` – user8190410 Nov 29 '18 at 18:30
-
1I know that, my question is why this represents after all the second derivative of Laplacian operator? – wisdom Nov 29 '18 at 18:33
1 Answers
18
Monsieur Laplace came up with this equation. This is simply the definition of the Laplace operator: the sum of second order derivatives (you can also see it as the trace of the Hessian matrix).
The second equation you show is the finite difference approximation to a second derivative. It is the simplest approximation you can make for discrete (sampled) data. The derivative is defined as the slope (equation from Wikipedia):
In a discrete grid, the smallest h is 1. Thus the derivative is f(x+1)-f(x). This derivative, because it uses the pixel at x and the one to the right, introduces a half-pixel shift (i.e. you compute the slope in between these two pixels). To get to the 2nd order derivative, simply compute the derivative on the result of the derivative:
f'(x) = f(x+1) - f(x)
f'(x+1) = f(x+2) - f(x+1)
f"(x) = f'(x+1) - f'(x)
= f(x+2) - f(x+1) - f(x+1) + f(x)
= f(x+2) - 2*f(x+1) + f(x)
Because each derivative introduces a half-pixel shift, the 2nd order derivative ends up with a 1-pixel shift. So we can shift the output left by one pixel, leading to no bias. This leads to the sequence f(x+1)-2*f(x)+f(x-1).
Computing this 2nd order derivative is the same as convolving with a filter [1,-2,1].
Applying this filter, and also its transposed, and adding the results, is equivalent to convolving with the kernel
[ 0, 1, 0 [ 0, 0, 0 [ 0, 1, 0
1,-4, 1 = 1,-2, 1 + 0,-2, 0
0, 1, 0 ] 0, 0, 0 ] 0, 1, 0 ]
Cris Luengo
- 55,762
- 10
- 62
- 120
-
1
-
So going through wikipedia pages it seems that they are taking the "Second-order central" which explains the + and - signs inside the function! – wisdom Nov 29 '18 at 19:20
-
2@wisdom: `h` is the step size. It is set to 1 in the discrete case. The derivative is with respect to `x`. The first order discrete derivative introduces a 1/2-pixel shift right, therefore the second first-order derivative is chosen with a one pixel shift left, leading to a 2nd order derivative without shift. I'll add some text to the answer to explain this. – Cris Luengo Nov 29 '18 at 19:23
-
@CrisLuengo, would you please extend your solution to the 5x5 kernel? – h.nodehi May 31 '22 at 17:51
-
@h.nodehi What is "the 5x5 kernel"? The Laplacian is typically implemented as this 3x3 kernel, or another 3x3 kernel with -8 in the middle, or as the Laplacian of Gaussian, which should be quite a bit larger to be meaningful. – Cris Luengo May 31 '22 at 18:51
-
@CrisLuengo My mistake! Yes! I mean the discrete Laplacian of Gaussian kernels. I need to know how the discrete kernels are calculated, or at least what is the central element's value for each size (order). E.g., the central element for a 9x9 LoG kernel is -40. I know that the kernels are not unique, but I need to know how to calculate the common kernels. – h.nodehi May 31 '22 at 20:06
-
@h.nodehi "the central element for a 9x9 LoG kernel is -40" This depends on what the sigma is, what arbitrary scaling is applied to allow for quantization, and how it's quantized. If I make a 9x9 LoG in my software (sigma=1), then the central element has a value of -0.3186. I suggest you write a new question, if it hasn't been asked before. Here is some more information about computing the LoG: https://stackoverflow.com/a/53665075/7328782 – Cris Luengo May 31 '22 at 20:25