CS401

COMPUTER GRAPHICS

Spatial Convolution and

Correlation
Module VI
The Mechanics of Spatial Filtering
● Spatial domain is simply the plane containing
the pixels of an image.
● Spatial domain techniques operate directly on
the pixels of an image.

2
The Mechanics of Spatial Filtering

3
The Mechanics of Spatial Filtering
● Spatial domain processes will be denoted by
the expression
g(x, y) = T[ f(x,y) ]
where f(x, y) is the input image, g(x, y) is the
processed image, and T is an operator on f
defined over some neighborhood of (x, y).
➔ The principal approach in defining a
neighborhood about a pixel (x, y) is to use a
square or rectangular subimage area centered
at (x, y), as Fig. 3.1 shows.
4
 The Mechanics of Spatial Filtering
● Spatial filters are used for image enhancement. It is
employed for smoothing the image, sharpening the
image, etc.
➔ Spatial filtering involves filtering operations that are
performed directly on the pixels of an image.
➔ If the operation performed on the image pixels is linear,
then the filter is called a linear spatial filter.
Otherwise, the filter is nonlinear.
➔ Spatial filtering involves the usage of a subimage
called a filter, mask, kernel, template, or window. The
values in a filter subimage are referred to as
coefficients, rather than pixels. 5
Image f Filter Mask w

6
The Mechanics of Spatial Filtering
➔ The spatial filtering consists simply of moving
the filter mask from pixel to pixel in the image.
At each pixel (x, y), the response g(x, y) of the
filter at that pixel is calculated using a
predefined relationship.
➔ For linear spatial filtering, the response is given
by a sum of products of the filter coefficients
and the corresponding image pixels in the area
spanned by the filter mask.

7
 The Mechanics of Spatial Filtering
➔ Figure 3.28 illustrates the mechanics of linear
spatial filtering using a 3 x 3 neighborhood. At
any pixel (x, y) in the image, the response g(x, y) of
the filter is the sum of products of the filter
coefficients and the image pixels encompassed by
the filter:
g(x, y) = w(-1, -1) f(x - 1, y - 1) + w(-1, 0) f(x - 1, y)
+ . . . + w(0, 0) f(x, y) + . . . + w(1,1) f(x + 1, y + 1)
Observe that the center coefficient of the filter, w(0,
0), aligns with the image pixel at location (x, y)
indicating that the mask is centered at (x, y) when the
computation of the sum of products takes place. 8
See example in the next slide for better understanding.
 The Mechanics of Spatial Filtering

Input Image

Filter Mask w

Processed Image
9
 The Mechanics of Spatial Filtering

Input Image

Filter Mask w

Processed Image
10
 The Mechanics of Spatial Filtering
● In Fig. 3.1, we explained briefly that a spatial filter
consists of (1) a neighborhood, (typically a small
rectangle), and (2) a predefined operation that is
performed on the image pixels encompassed by the
neighborhood.
● Filtering creates a new pixel with coordinates equal
to the coordinates of the center of the neighborhood,
and whose value is the result of the filtering
operation.
● A processed (filtered) image is generated as the
center of the filter visits each pixel in the input
image. 11
 The Mechanics of Spatial Filtering
● As the center of the mask moves closer to the border, one or
more rows or columns of the mask may be located outside
the image plane. There are several ways to handle this
situation.
➔ The simplest is to limit the excursions of the center of the
mask to be at a distance no less than (n - 1)/2 pixels from
the border. The resulting filtered image will be smaller than
the original, but all the pixels in the filtered image will have
been processed with the full mask.
➔ If the result is required to be the same size as the original,
then the approach typically employed is to filter all pixels
only with the section of the mask that is fully contained in the
image. With this approach, there will be bands of pixels near
the border that will have been processed with a partial filter12
mask.
 The Mechanics of Spatial Filtering
➔ Other approaches include "padding" the image by
adding rows and columns of 0s (or other constant gray
level), or padding by replicating rows or columns. The
padding is then stripped off at the end of the process.
This keeps the size of the filtered image the same as
the original, but the values of the padding will have an
effect near the edges that becomes more prevalent as
the size of the mask increases.
➔ The only way to obtain a perfectly filtered result is to
accept a somewhat smaller filtered image by limiting
the excursions of the center of the filter mask to a
distance no less than (n - 1)/2 pixels from the border of
the original image. 13
 The Mechanics of Spatial Filtering
● For a mask of size m x n, we assume that m = 2a +
1 and n = 2b + 1, where a and b are positive
integers. This means that our focus in the following
discussion is on filters of odd size, with the smallest
being of size 3 x 3. In general, linear spatial filtering
of an image of size M x N with a filter of size m x n is
given by the expression:

where x and y are varied so that each pixel in w

visits every pixel in f.
14
Spatial Convolution and Correlation
● There are two closely related concepts that must be
understood clearly when performing linear spatial
filtering. One is correlation and the other is
convolution.
● Correlation is the process of moving a filter mask
over the image and computing the sum of products at
each location.
● The mechanics of convolution are the same, except
that the filter is first rotated by 180 0.
● Correlation and convolution are commutative.
● The best way to explain the differences between the
two concepts is by an example. 15
Spatial Convolution and Correlation
● We begin with a 1-D illustration.
Figure 3.29(a) shows a 1-D function f and a filter
w. Figure 3.29(b) shows the starting position to
perform correlation.
The first thing we note is that there are parts of
the functions that do not overlap. The solution to
this problem is to pad f with enough 0s on either
side to allow each pixel in w to visit every pixel in
f. If the filter is of size m, we need m-1 0s on
either side of f.
Figure 3.29(c) shows a properly padded function.16
See example in slide 18 for better understanding.
w w

17
Fig. 3.29
Spatial Convolution and Correlation

Fig. 3.29

18
Spatial Convolution and Correlation
The first value of correlation is the sum of products of f and w for
the initial position shown in Fig. 3.29(c) (the sum of products is 0).
This corresponds to a displacement of x = 0.
To obtain the second value of correlation, we shift w one pixel
location to the right (a displacement of x = 1) and compute the sum
of products. The result again is 0.
In fact, the first nonzero result is when x = 3, in which case the 8 in
w overlaps the 1 in f and the result of correlation is 8.
Proceeding in this manner, we obtain the full correlation result in
Fig. 3.29(g).
Note that it took 12 values of x (i.e., x = 0, 1, 2, . . . , 11) to fully
slide w past f so that each pixel in w visited every pixel in f.
Often, we like to work with correlation arrays that are the same size
as f, in which case we crop the full correlation to the size of the
original function, as Fig. 3.29(h) shows. 19
 Spatial Convolution and Correlation
● There are two important points to note from the discussion
in the preceding paragraph.
First, correlation is a function of displacement of the filter. In
other words, the first value of correlation corresponds to
zero displacement of the filter, the second corresponds to
one unit displacement, and so on.
The second thing to notice is that correlating a filter w with a
function that contains all 0s and a single 1 yields a result
that is a copy of w, but rotated by 180°.
● We call a function that contains a single 1 with the rest being
0s a discrete unit impulse. So we conclude that correlation
of a function with a discrete unit impulse yields a rotated
version of the function at the location of the impulse. 20
 Spatial Convolution and Correlation
● The preceding concepts extend easily to images, as Fig.
3.30 shows.
➔ For a filter of size m x n, we pad the image with a minimum
of m - 1 rows of 0s at the top and bottom and n - 1 columns
of 0s on the left and right.
➔ In this case, m and n are equal to 3, so we pad f with two
rows of 0s above and below and two columns of 0s to the
left and right, as Fig. 3.30(b) shows.
➔ Figure 3.30(c) shows the initial position of the filter mask for
performing correlation, and Fig. 3.30(d) shows the full
correlation result. Figure 3.30(e) shows the corresponding
cropped result. Note again that the result is rotated by 180°.
21
Spatial Convolution and Correlation

Fig 3.30

22
Spatial Convolution and Correlation

Fig 3.30

23
Spatial Convolution and Correlation
➔ For convolution, we pre-rotate the mask and repeat the
sliding sum of products just explained. Figures 3.30(f)
through (h) show the result. You see again that convolution
of a function with an impulse copies the function at the
location of the impulse.
➔ It should be clear that, if the filter mask is symmetric,
correlation and convolution yield the same result.
➔ If instead of containing a single 1, image f in Fig. 3.30 had
contained a region identically equal to w, the value of the
correlation function (after normalization) would have been
maximum when w was centered on that region of f. Thus,
correlation can be used also to find matches between
images.
➔ Convolution is used in edge detection, filtering etc.
24
Spatial Convolution and Correlation

Fig 3.30

25
Spatial Convolution and Correlation
● Summarizing the preceding discussion in equation
form, we have that the correlation of a filter w(x, y) of
size m x n with an image f(x, y), denoted as w(x, y)
f(x, y), is given by the equation :
w(x,y)

➔ This equation is evaluated for all values of the

displacement variables x and y so that all elements of
w visit every pixel in f, where we assume that f has
been padded appropriately.
➔ As explained earlier, a = (m-1)/2, b = (n-1)/2, and we
assume for notational convenience that m and n are26
odd integers.
Spatial Convolution and Correlation
● In a similar manner, the convolution of w(x, y) and
f(x, y), denoted by w(x, y) f(x, y) is given by the
expression:
w(x,y)

where the minus signs on the right flip f (i.e.. rotate it

by 180°). Flipping and shifting f instead of w is done
for notational simplicity and also to follow
convention. The result is the same. As with
correlation, this equation is evaluated for all values
of the displacement variables x and y so that every
element of w visits every pixel in f, which we assume
27
has been padded appropriately.