11. Neighborhood (Spatial) Processing¶

Reading Assignment

Please read section 12.5 of [RVC] and chapter 10 of [PIVP].

Video Resources

Peter Corke has a set of short videos on this topic.

This topic is usually called something like neighborhood processing, spatial filtering, or something similar because the value of each output pixel is determined by the corresponding pixel in the input image and the neighboring pixels to it.

11.1. Convolution and Correlation¶

Linear filtering of images apply a sum of products between pixels in a neighborhood and a mask (also called a kernel) of values.

Figure 10.1 from [PIVP]. The value of a pixel in the output image is the sum of products between a neighborhood and a mask.

In signal processing in the time-domain, we can model how filters affect a signal with a process called convolution. In convolution, we fold over the signal and then at each time step shift the signal through the impulse response of the filter. The output for each time step is the sum of the products of the signal and filter response where they overlay each other.

Here is a simulated example of convolution in the time domain.

signal = [0 1 1 0.75 0.5 0 0 0 0 0];
filter = [0.75 0.5 0.25 0 0 0 0 0 0 0];
time = 0:9;

out = zeros(1,10);
for t = 1:10
    for j=0:9
        if t-j > 0
            out(t) = out(t) + signal(t-j)*filter(j+1);
        end
    end
end
figure
subplot(3,1,1), stem(time, filter), title('Filter Response')
subplot(3,1,2), stem(time, signal), title('Input Signal')
subplot(3,1,3), stem(time, out), title('Filtered Signal')

Example of how convolution models time-domain filtering

In the two dimensional spatial domain of images, we model linear neighborhood filters with convolution when the filter mask is not symmetric (mostly for edge detection). When the mask is symmetric, then convolution and correlation yield the same result. Correlation is a sum of products like convolution, but does not require folding the image or mask over.

Spatial domain 2D Convolution:

$\boldsymbol{\mathrm{O}}\left[u,v\right]=\sum_{(i,j)\in \mathcal{W}} {\boldsymbol{\mathrm{I}}\left[u-i,v-j\right]\boldsymbol{\mathrm{K}} \left[i,j\right],\forall (u,v)\in \boldsymbol{\mathrm{I}}} \\ i\in \left[-h\cdots h\right],\ j\in [-h\cdots h]$

Spatial domain 2D Correlation:

$\boldsymbol{\mathrm{O}}\left[u,v\right]=\sum_{\left(i,j\right)\in \mathcal{W}}{\mathrm{I}\left[u+i,v+j\right]\mathrm{K}\left[i,j\right], \forall \left(u,v\right)\in \mathrm{I}} \\ i\in \left[-h\cdots h\right],\ j\in [-h\cdots h]$

Properties of Convolution

commutative: $A * B = B * A$

associative: $A * B * C = (A * B) * C = A * (B * C)$

distributive: $A * (B + C) = A * B + A * C$

linear: $A * (\alpha B) = \alpha (A * B)$

The IPT function for applying a filter mask to an image is imfilter. We will learn about different options to imfilter in the tutorials. The MVTB function for filtering images is iconvolve

11.1.1. Border Geometry¶

Look up the boundary options in the MATLAB documentation for the imfilter and iconvolve functions.

Figure 10.4 from [PIVP].

11.1.2. Common Image Processing Filters¶

So as to not change the brightness of an image, we usually form filter masks such that the elements sum to one.

The IPT has a fspecial function that returns common filter masks. The MVTB also has some functions that return filter masks.

The average or mean filter smooths or blurs an image. Note that the average filter is not symetric with respect to rotation.

>> K = fspecial('average', 3)
K =
    0.1111    0.1111    0.1111
    0.1111    0.1111    0.1111
    0.1111    0.1111    0.1111
>> K = ones(3)/3^2
K =
    0.1111    0.1111    0.1111
    0.1111    0.1111    0.1111
    0.1111    0.1111    0.1111

The ‘disk’ option to fspecial and the kcircle function provide circular averaging filters. A circular averaging filter is symmetric with respect to rotation.

The Gaussian filter also smooths an image, but generally yields better results than the average filters because it has smoother transitions between pixels. It is based on the Gaussian function that is also used to describe a normal probability distribution. The spread of the filter is defined by standard deviation ( $\sigma$ ). Read the documentation in MATLAB for the ‘gaussian’ option to fspecial and the kgauss function. The Gaussian filter is symmetric with respect to rotation and coefficients fall off to (almost) zero at the kernel’s edges.

$h(x, y) = e^{\frac{-(x^2 + y^2)}{2\sigma^2}}$

11.1.3. The Laplacian¶

The Laplacian operator, which is the sum of the second partial derivatives, is described for 2-D discrete valued functions, such as an image. While, not exactly edge detection, it places emphasis on the edges of objects in an image.

$\nabla^2 f(x,y) = \frac{\partial^2 f(x,y)}{\partial x^2} + \frac{\partial^2 f(x,y)}{\partial y^2}$

Let’s take a closer look at the second partial derivative term with respect to $x$ . The first derivative is the difference in adjacent elements.

$\frac{\partial f(x, y) }{\partial x} = f'_x = f(x, y) - f(x - 1, y)$

Or, if we want to look ahead of $x$ , instead of behind it, it could also be:

$\frac{\partial f(x, y) }{\partial x} = f'_x = f(x + 1, y) - f(x, y)$

Similarly, the second derivative is calculated from the difference between adjacent first derivatives.

$\frac{\partial^2 f(x,y) }{\partial x^2} = f''_x(x, y) = f'_x(x, y) - f'_x(x - 1, y)$

Or:

$\frac{\partial^2 f(x,y) }{\partial x^2} = f''_x(x, y) = f'_x(x + 1, y) - f'_x(x, y)$

To be centered about $x$ , we will use the former expression for first derivatives and the later expression for the second derivative.

$\begin{array}{ll} f''_x(x, y) & = f'_x(x + 1, y) - f'_x(x, y) \\ & = f(x + 1, y) - f(x, y) - f(x, y) + f(x - 1, y) \\ & = f(x + 1, y) + f(x - 1, y) - 2\,f(x, y) \end{array}$

The above equation is equation (10.13) from the text book. Equation (10.14) with respect to the $y$ values follows likewise.

$\begin{array}{ll} f''_y(x, y) & = f'_y(x, y + 1) - f'_y(x, y) \\ & = f(x, y + 1) - f(x, y) - f(x, y) + f(x, y - 1) \\ & = f(x, y + 1) + f(x, y - 1) - 2\,f(x, y) \end{array}$

$\nabla^2 f(x,y) = f(x + 1, y) + f(x - 1, y) + f(x, y + 1) + f(x, y - 1) - 4\,f(x, y)$

The convolution mask for the Laplacian is:

$\left[ \begin{array}{rrr} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \end{array} \right]$

Note that the signs of the coefficients in the convolution mask might be reversed depending on the need.

11.1.4. Laplacian of Gaussian¶

If the edges in an image are first blurred, the Laplacian filter clearly shows edges. This could be accomplished by two sequential filters, but because of the associative property of convolution, we can used a single filter that is the convolution of Laplacian and Gaussian filters, called Laplacian of Gaussian or simply LoG.

% Demo to show how the Laplacian of Gaussian (log) filter works

% Make a simulated image showing half black and half white.

I = [zeros(256, 128) ones(256, 128)];

% Blurr the edge with a Gaussian filter
h = fspecial('gaussian', 10, 2);
Iblurr = imfilter(I, h);

% 1st and 2nd derivatives along u
deriv1 = [0 0 0; -1 1 0; 0 0 0];
deriv1_2 = [0 0 0; 0 -1 1; 0 0 0];
I1stD = imfilter(Iblurr, deriv1);
I2ndD = imfilter(I1stD, deriv1_2);

% Laplacian of Gaussian filter
hlog = fspecial('log', 10, 2);
Ilog = imfilter(I, hlog);

% plots
figure   % images
subplot(2,3,1), imshow(I), title('original')
subplot(2,3,2), imshow(Iblurr), title('blurred')
subplot(2,3,3), imshow(I1stD, []), title('1st Derivative')
subplot(2,3,4), imshow(I2ndD, []), title('2nd Derivative')
subplot(2,3,5), imshow(Ilog, []), title('LoG')

figure   % a horizontal line
subplot(2,3,1), plot(110:140, I(128,110:140)), title('original')
subplot(2,3,2), plot(110:140, Iblurr(128,110:140)), title('blurred')
subplot(2,3,3), plot(110:140, I1stD(128,110:140)), title('1st Derivative')
subplot(2,3,4), plot(110:140, I2ndD(128,110:140)), title('2nd Derivative')
subplot(2,3,5), plot(110:140, Ilog(128,110:140)), title('LoG')

11.1.5. Unsharp Filter¶

The oddly named unsharp filter is a hi-pass filter that can make fine detail in an image more noticable. Its application is more related to image processing than machine vision, but it is interesting enough to warant brief consideration.

The algorithm consists of computing the subtraction between the input image and a blurred (low-pass filtered) version of the input image with the goal of increasing the amount of high-frequency (fine) detail by reducing the importance of its low-frequency contents. The “unsharp” of the name derives from the fact that the technique uses a blurred, or “unsharp”, negative image to create a mask of the original image. The unsharped mask is then combined with the positive (original) image, creating an image that is less blurry than the original. The technic was first used and named with film photography. The Wikipedia page shows some diagrams that illustrate how the steps change an image.

The ‘unsharp’ option to the fspecial function provides a digital filter mask for this affect. We will briefly demonstrate it in a tutorial.

11.2. Median Filter¶

Images with salt and pepper noise, which is characterized by random white and black pixels in the image, can benefit from the median filter. It sets the target pixel equal to the median value of the neighborhood pixels.

The median filter is a nonlinear operation.

11. Neighborhood (Spatial) Processing¶

11.1. Convolution and Correlation¶

11.1.1. Border Geometry¶

11.1.2. Common Image Processing Filters¶

11.1.3. The Laplacian¶

11.1.4. Laplacian of Gaussian¶

11.1.5. Unsharp Filter¶

11.2. Median Filter¶

Table of Contents

Previous topic

Next topic

This Page