8

I am trying to understand the four 1D convolution operations involved in implementation of Laplacian of Gaussian(LoG). I have read the answers to What Is the Difference between Difference of Gaussian, Laplace of Gaussian, and Mexican Hat Wavelet?, and I am also reading ME5286 - Lecture 7 (2017) - Edge Detection (See slide# 62 and 63). My current understanding is:

  1. Pre-compute LoG and separate to 1D filters in x and y: gxx(x) and gyy(y).

  2. Take Gaussian (g) and separate to: g(x) and g(y).

  3. First apply g(y) and gyy(y) to the image. That makes two 1D convolutions.

  4. Then apply g(x) to the result from gyy(y) and gxx(x) to the result from g(y). That adds two more 1D convolutions, making the total four.

Questions:

  1. Is the above understanding correct?

  2. How is this same as LoG?

  3. Also, the diagram in slide #62 contradicts slide #63, in the pdf (Saad J. Bedros - ME5286 Lecture 7 2017 Edge Detection). Which one is correct?

Edit:

It's actually slide#61 and slide#62.

Edit2:

Please see the very last comment, posted Dec 19, 2018, on the first answer.

Royi
  • 19,608
  • 4
  • 197
  • 238
skr
  • 283
  • 2
  • 13
  • 1
    Slide #62 is terrible. It not only switches some x-es and y-s around, but it also shows $\Delta^2$ where it should say $\nabla^2$ (noting that $\Delta = \nabla^2$ is the Laplace operator). – Cris Luengo Dec 20 '18 at 05:06

2 Answers2

6

There are two ways to compute the Laplace of Gaussian operator:

  1. As Royi suggests, by computing $f * \nabla^2 * g$,where we take the operator $\nabla^2$ as a convolution kernel created using the finite difference approximation to the derivative.

  2. As the slides linked by OP suggest, by computing $$ f * \nabla^2 g = f * \left(\frac{\partial^2}{\partial x^2}g+\frac{\partial^2}{\partial y^2}g\right) = f * g_{xx} + f * g_{yy} $$

Approach 1 is computationally cheaper: convolution with the Gaussian $g$ is separable, and thus takes two 1D convolutions. The discrete Laplace operator is a 3x3 matrix, this third convolution is cheap to compute.

Approach 2 is more precise: it doesn't use any discrete approximations to the derivative, instead using a sampled Gaussian derivative as a kernel. This approach takes two convolutions (which are both separable into two 1D convolutions, for a total of four 1D convolutions) and an addition. Note that there is one extra intermediate image to deal with, it uses more memory.

Approach 1: convolve image with $g(x)$, then with $g(y)$, then with the discrete 3x3 Laplace kernel.

Approach 2: convolve image with $g(x)$, then with $g_{yy}(y)$, store result; convolve image with $g(y)$ then with $g_{xx}(x)$; sum the two results.

Cris Luengo
  • 2,484
  • 1
  • 11
  • 25
2

I think Chris Luengo's answer is perfect.
The trick is that you can calculate the 2nd derivative of the image (Using Finite Differences -> Convolution) and then blur it with Gaussian Filter.
Since both are seperable kernels you can do that by 4 1D convolutions.

If the input image is given by I

  1. Calculate Ixx (The 2nd derivative on x direction) using convolution.
  2. Filter Ixx with 1D Gaussian Kernel along the x direction.

Do the above for the y direction as well.
The LoG image is the sum of both.

To answer your questions:

  1. See my explanation above. I think it matches your understanding.
  2. This is the very definition (The Discrete) of the LoG.
  3. I don't see the contradiction between #62 and #63.
Royi
  • 19,608
  • 4
  • 197
  • 238
  • But isn't slide #62 saying LoG = gyy * gx + gy * gxx while slide #63 is saying LoG = gxx * gx + gyy * gy? The terms that are getting added up are different because individual terms that are getting multiplied form different combinations. – skr Sep 17 '18 at 08:55
  • For what I see #62 says the log is the sum of 1D filtered 2nd Derivative of the image. Slide #63 only mentions the Separability property of the Gaussian Kernel. – Royi Sep 17 '18 at 09:00
  • @ I am talking about the diagrams at the bottom of slide #62 and #63. – skr Sep 17 '18 at 09:02
  • 1
    Could it be that you're talking about #61 and #62? – Royi Sep 17 '18 at 09:08
  • Yes. Sorry. My bad. I will make an edit in the question. – skr Sep 17 '18 at 09:09
  • 1
    I think he author just wanted to show that since all operations are Linear and Spatially Invariant you can do them in any order and combination you want. So you can do differentiation on x with Blur on y and the other way around and sum and the result is the same. – Royi Sep 17 '18 at 09:27
  • This is exactly what I am trying to confirm. – skr Sep 17 '18 at 09:32
  • Update: The slide #61 is correct. The slide #62 actually has a small correction. It should be gxx(y) * g(x) + gyy(x) * g(y), NOT gxx(x) * g(x) + gyy(y) * g(y). – skr Dec 19 '18 at 17:04