Spatial Filtering

In ISMI-1c-Intensity_Transformation.md we discussed intensity transformations. They are only defined on pixel intensities and do not factor in neighbouring pixels. Spatial filtering does.

Convolution (as in convolutional neural networks) is a form of spatial filtering.

By looking at a neighbourhood around a pixel value, we get a subimage whose values we use in some operation.

This subimage is called:

  • Filter
  • Mask
  • Kernel
  • Template
  • Window

Kernel values are called coefficients instead of pixels. This is because you multiply the filter values with pixel intensities of a subimage and then sum them up; see 'correlation'

Correlation

We have a filter: w(x,y)

  • Recall: usually top left corner is (0,0)
  • If we take center of filter as (0,0) top left corner instead is w(-1,-1), top right is w(1,1)
  • Note that (x,y) corresponds to (column, row), which is a bit counter-intuitive.

Procedure:

  • Apply to image to get subimage
  • Multiply overlapping locations
  • Sum up results so each filter application results in a single value

Correlation:

$$g(x,y) = \sum_{s=-a}^{a} \sum_{t=-b}^b w(s,t)f(x+s,y+t)$$

Correlation vs. Convolution

Cf. convolution:

$$g(x,y) = \sum_{s=-a}^{a} \sum_{t=-b}^b w(s,t)f(x-s,y-t)$$

Notice the sign change. By definition we thus see that convolution is 1) rotating the filter by 180 degrees and 2) then apply correlation.

Correlation and convolution are the same operations when filters are symmetric.

  • Convolution with impulse returns the filter.
  • Correlation with impulse returns filter rotates by 180 degrees.
    • Impulse: image with all zeros except center (so dirac delta sensitive to center of image)

See: https://towardsdatascience.com/convolution-vs-correlation-af868b6b4fb5

Padding

Zero-padding can be used to have output size same as input, i.e. the "same" convolution.

You can also pad more to increase the output size.

Cyclic padding:

  • Append first column after the last column
  • Append first row under last row (notice, this row is now +1 longer than before)
  • Prepend last column before first column
  • Prepend last row before first row

This is apparently useful, but didn't become clear to me when and why. It's mostly a risky operation, because you'll easily introduce artefacts and strong border transitions.

Q: What's the benefit of cyclic padding? When is it applicable?

Types of filters

Common results

  • Image smoothing
  • Edge detection
  • Image derivative
  • Blob detection
  • etc.

Image smoothing

Smoothing can be used for blurring and noise reduction.

The basis of smoothing is using the average over intensity values in some neighbourhood. So a particular pixel intensity can be replaced by the average intensity of its neighbours.

This can be achieved by applying an NxN filter with all coefficients being 1. Convolving implies adding these up, so all we have to do is then divide by NxN to get the average. The higher N, the more smoothing.

The division by NxN is essentially filter normalization. If you skip this step you will heavily saturate the image, as many if not most values will be >255, i.e. you go outside the typical 8-bit range so values will be clipped to 255 i.e. white.

Edge detection

  • To detect edges we should have filters with sign changes, e.g. from -1 to +1.
  • This means the kernel will respond strongly to sharp increases in intensity, i.e. edges (in this case from dark to bright)
  • We usually have a central reference pixel, so a basic edge detection filter would be [-1, 0, 1] and its transposed version, to match edges in x- and y-direction.

Prewitt gradient kernel

Usually we prefer square filters. If we replicate the 1x3 filter three times, for both variants, we get the Prewitt gradient kernel. Looks like this:

1 0 -1
1 0 -1
1 0 -1

What this means is that for this example we have edge detection in the horizontal direction, but smoothing in the vertical direction!

The coefficients sum to zero, so if the filter is applied to an area with constant intensity, the response will be zero. This is exactly what we expect from an edge detector: it only detects edges.

Compared to the 1x3 filter, this results in less noisy output.

Sobel kernel

Small adjustment to Prewitt kernel that emphasizes the neighbouring pixels of the center of the filter. $[h_x]=$

1 0 -1
2 0 -2
1 0 -1

And again, in the y-direction this is just transposed.

Gaussian operators: both for smoothing and edge detection

The family of Gaussian operators serves multiple purposes.

In 2D we usually assume an isotropic Gaussian, so we still only need one $\sigma$ parameter.

Convolving with a 2D Gaussian is yet another form of blurring, where the points close to the filter's center are weighed more heavily. The larger $\sigma$ the more smoothing.

Larger $\sigma$ will effectively lead to a larger kernel size. We know that Gaussians approximate zero for > $3 \times \sigma$ so we can safely cut-off the kernel after that. Remember to insert a 0 as the center of the filter.

If you take the range too short, e.g. only one standard deviation to either side, then you will produce artefacts because you are in a way "cropping".

Deals with noise in edge transitions

Sometimes edge transitions are noisy. Let's say you get a response signal by applying a Prewitt filter (the response being close to 0 if there's no edge and close to 1 if there's an edge). When we take the derivative of the response signal, the derivative will then also be extremely noisy at the edge and basically be useless for determining the edge location.

What we can do instead, is convolve the signal with a Gaussian kernel to smooth the transition. This will allow us to get a useful derivative. We can then say that the maximum of the derivative is the edge location.

Derivative of Gaussian filters

  • We computed derivative of signal after convolution
  • Convolution implies integral over multiplications, so is a linear operation.
  • As a result, we can use the associative law:
  • Convolution of Gaussian G(x) with derivative of image I(x) equals convolution of the image I(x) with the derivative of the Gaussian filter G(x)

So to compute the derivative on an image we convolve the image with the derivative of a Gaussian filter!

Computing the derivative of Gaussian filters extends the Gaussian filters with a new set of filters.

This does introduce the dependency on $\sigma$ in the computation of derivatives. So $\sigma$ is not only used for smoothing anymore, but also used for computing derivatives.

Edges can be found using first order and second order Gaussian derivatives (which was already mentioned above). For the first derivative, we find an edge by looking at the maximum. For the second derivative, we look at the zero-crossing.

The first order derivative is generally preferable, because 1) finding maximum is easier and 2) derivatives are very sensitive to noise; hence this may be more problematic when taking two derivatives.

In 2D, computing the partial derivatives is computing the gradient.

Gradient direction and magnitude

For this gradient we can compute the magnitude (apply Pythagoras) and direction (arctan).

The gradient direction gives the direction of maximum growth of the function from black to white. This means that the edge direction is the gradient direction rotated by -90 degrees.

Edges are the local maxima of the gradient magnitude. Moreover, we can now express strong and weak edges based on the magnitude!

Laplacian of Gaussian (LoG)

Laplacian is the sum of the second derivative gradient components. This is not used for edge detection, but can be used for blob detection.

LoG looks like a "Mexican hat".

How to choose the right $\sigma$? One approach is to have a set of sigmas/features, apply all filters independently, and combine the responses (e.g. by summing or averaging).

Fast Fourier Transform

If you take a large $\sigma$, you'll have a large filter. This slows down convolution.

Working in the frequency domain using fast Fourier transform speeds up.

Convolution in the frequency domain becomes a multiplication of the transformed image and kernel.

$$g(x,y) * h(x,y) <-> G(u,v)H(u,v)$$

Steerable filters

If you want to use a Gaussian filter but do not just use the x- and y-axis as they are, but instead want to use the first derivative in any direction, you can rotate the axes.

$x' <- x cos \alpha - y sin \alpha$

$y' <- x sin \alpha + y cos \alpha$

You can apply the same principle for the second derivative.