Digital Image Processing 2-

lecture 4
By
Dr. Mohannad k. Sabir Al Lami
2019-2020
5- Fundamentals of Spatial Filtering
• Spatial filtering is used in a broad spectrum of
image processing applications, so a solid
understanding of filtering principles is important.
• The name filter is borrowed from frequency domain
processing where “filtering” refers to passing,
modifying, or rejecting specified frequency
components of an image.
• A filter that passes low frequencies is called a
lowpass filter. The net effect produced by a
lowpass filter is to smooth an image by blurring it.
• Spatial filtering modifies an image by replacing the
value of each pixel by a function of the values of the
pixel and its neighbors.
• If the operation performed on the image pixels is
linear, then the filter is called a linear spatial filter.
• Otherwise, the filter is a nonlinear spatial filter. We
will focus attention first on linear filters.
 The Mechanics of Linear Spatial Filtering
• A linear spatial filter performs a sum-of-products
operation between an image f and a filter kernel,
w.
• The kernel is an array whose size defines the
neighborhood of operation, and whose coefficients
determine the nature of the filter.
• Other terms used to refer to a spatial filter kernel
are mask, template, and window. We use the term
filter kernel or simply kernel.
• Observe that the center coefficient of the kernel,
w(0, 0), aligns with the pixel at location (x, y). For a
kernel of size mxn we assume that m=2a+1 and
n=2b+1, where a and b are nonnegative integers.
This means that our focus is on kernels of odd size
in both coordinate directions. In general, linear
spatial filtering of an image of size MxN with a
kernel of size mxn is given by the expression
a b
g(x,y) = ∑ ∑ w(s,t) f(x+s,y+t) ------- (1)
s = -a t = -b
where x and y are varied so that the center (origin) of
the kernel visits every pixel in f once.
• For a fixed value of (x, y), Eq. 1, implements the
sum of products of the form shown below:
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)
• but for a kernel of arbitrary odd size.
• As you will learn in the following section, this
equation is a central tool in linear filtering.
5-1 Spatial Correlation and Convolution
• Spatial correlation is illustrated
graphically in Fig. and it is
described mathematically by Eq.
1.
• Correlation consists of moving
the center of a kernel over an
image, and computing the sum of
products at each location.
• The mechanics of spatial
convolution are the same, except
that the correlation kernel is
rotated by 180⁰.
• Thus, when the values of a kernel
are symmetric about its center,
correlation and convolution yield
the same result.
• The reason for
rotating the kernel
will become clear
in the following
discussion. The
best way to explain
the differences
between the two
concepts is by
example
• We begin with a 1-
D illustration, in
which case Eq. 1.
a
g(x)=∑ w(s)f(x+s) – (2)
S = -a
• The first thing we notice is that part of w lies
outside f, so the summation is undefined in that
area.
• A solution to this problem is to pad function f with
enough 0’s on either side.
• In general, if the kernel is of size 1xm, we need (m-
1)/2 zeros on either side of f in order to handle the
beginning and ending configurations of w with
respect to f.
• In this starting configuration, all coefficients of the
kernel overlap valid values.
• The first correlation value is the sum of products in this
initial position, computed using Eq. 2 with x=0:
2
g(0)=∑ w(s)f(s+0) =0
S =-2
• To obtain the second value of correlation, we shift the
relative positions of w and f one pixel location to the
right [i.e., we let x=1 in Eq. 1] and compute the sum of
products again.
• The result is g(1)=8, as shown in the leftmost, nonzero
location in Fig. above (g). When x=2 we obtain g(2)=2,
When x=3, we get g(3)=4.
• Proceeding in this manner by varying x one shift at a
time, we “build” the correlation result in Fig. above (g)
• Note that it took 8 values of x (i.e., x=0, 1,2,…,7 ) to
fully shift w past f so the center coefficient in w
visited every pixel in f.
• Sometimes, it is useful to have every element of w
visit every pixel in f. For this, we have to start with
the rightmost element of w coincident with the
origin of f, and end with the leftmost element of w
being coincident the last element of f (additional
padding would be required).
• There are two important points to note from the
preceding discussion.
1. Correlation is a function of displacement of the filter
kernel relative to the image.
• In other words, the first value of correlation
corresponds to zero displacement of the kernel, the
second corresponds to one unit displacement, and so
on.
2. That correlating a kernel w with a function that
contains all 0’s and a single 1 yields a copy of w, but
rotated by 180⁰.
• A function that contains a single 1 with the rest being
0’s is called a discrete unit impulse.
• The 1-D concepts just discussed extend
easily to images
• For a kernel of size m x n we pad the
image with a minimum of (m-1)/2 rows of
0’s at the top and bottom and (n-1)/2
columns of 0’s on the left and right. In this
case, m and n are equal to 3, so we pad f
with one row of 0’s above and below and
one column of 0’s to the left and right,
• Figure (c) shows the initial position of
the kernel for performing correlation, and
Fig. (d) shows the final result after the
center of w visits every pixel in f,
computing a sum of products at each
location. As before, the result is a copy of
the kernel, rotated by 180⁰.
• For convolution, we pre-rotate the kernel as
before and repeat the sliding sum of products
just explained. Fig. (f) through (h) show
the result. You see again that convolution of a
function with an impulse copies the function
to the location of the impulse. As noted
earlier, correlation and convolution yield the
same result if the kernel values are
• A discrete impulse of strength (amplitude) A
located at coordinates (x0,y0) is defined as:
A if x=x0 and y=y0
δ(x-x0, y- y0) = ---- (3)
0 otherwise
• Recall that A=1 for a unit impulse.
• Summarizing the preceding discussion in equation
form, the correlation of a kernel w of size m x n
with an image f(x, y), denoted as (w f)(x,y),
• is given by Eq. 1, which we repeat here for
convenience:
 a b
(w f)(x,y) = ∑ ∑ w(s,t) f(x+s,y+t) ---- (4)
s = -a t = -b

• As explained earlier, a=(m-1)/2, b= (n-1)/2, and we

assume that m and n are odd integers.
• In a similar manner, the convolution of a kernel w of
size m x n with an image f(x, y), denoted by (w f)(x,y)
is defined as
a b
(w f)(x,y) = ∑ ∑ w(s,t) f(x-s,y-t) ----- (5)
s = -a t = -b
where the minus signs align the coordinates of f and w
when one of the functions is rotated by 180⁰.
• This equation implements the sum of products process
to which we refer throughout the book as linear spatial
filtering. That is, linear spatial filtering and spatial
convolution are synonymous.
• Because convolution is commutative it is immaterial
whether w or f is rotated, but rotation of the kernel is
used by convention. (see Table below).
• The kernels do not depend on (x, y), a fact that we
sometimes make explicit by writing the left side of Eq.
5, w f(x,y).
• When the meaning is clear, we let the dependence of
the previous two equations on x and y be implied, and
use the simplified notation w f and w f.
• The values of x and y needed to obtain a full convolution are
x=0, 1, 2, …, M-1 and y=0, 1, 2, …, N-1. The size of the result is
M x N.
• We can define correlation and convolution so that every
element of w visits every pixel in f. This requires that the
starting configuration be such that the right, lower corner of
the kernel coincides with the origin of the image. Similarly,
the ending configuration will be with the top left corner of
the kernel coinciding with the lower right corner of the
image. If the kernel and image are of sizes mxn and MxN
respectively, the padding would have to increase to (m-1)
padding elements above and below the image, and (n-1)
elements to the left and right. Under these conditions, the
size of the resulting full correlation or convolution array will
be of size Sv x Sh, where
 Sv= m + M-1 ------- (6)
And
Sh= n + N-1 ------- (7)
• Often, spatial filtering algorithms are based on correlation
and thus implement Eq. (4) instead.
• To use the algorithm for correlation, we input w into it; for
convolution, we input w rotated by 180⁰.
• The opposite is true for an algorithm that implements Eq. (5).
• Thus, either Eq. (4) or Eq. (5) can be made to perform the
function of the other by rotating the filter kernel.
• Keep in mind, however, that the order of the functions input
into a correlation algorithm does make a difference, because
correlation is neither commutative nor associative (see Table
above).
• Figure shows two
kernels used for
smoothing the
intensities of an
image.
• To filter an image
using one of these
kernels, we perform a
convolution of the
kernel with the image
in the manner just
described. When
talking about filtering
and kernels, you are a box kernel a Gaussian kernel
likely to encounter the
terms convolution Because the values of these kernels are
filter, convolution symmetric about the center, no rotation is
mask, or convolution
kernel to denote filter required before convolution.
kernels of the type we
have been discussing.
• Sometimes an image is filtered (i.e., convolved)
sequentially, in stages, using a different kernel in
each stage. For example, suppose than an image f is
filtered with a kernel w1, the result filtered with
kernel w2, that result filtered with a third kernel,
and so on, for Q stages.
• Because of the commutative property of
convolution, this multistage filtering can be done in
a single filtering operation,
• Where
w= w1 w2 w3 ….. wq ----- (8)
• We could not write a similar equation for
correlation because it is not commutative.
• The size of w is obtained from the sizes of the
individual kernels by successive applications of Eqs.
(6) and (7).
• If all the individual kernels are of size mxn it follows
from these equations that w will be of size Wv x Wh
Where
Wv = Q x (m-1) + m ---- (9)
And
Wh = Q x (n-1) + n ---- (10)
5-2 Separable Filter Kernels
• A spatial filter kernel is a matrix, and a separable
kernel is a matrix that can be expressed as the outer
product of two vectors. For example, the 2x3 kernel
w = 11 11 11
is separable because it can be expressed as the outer
product of the vectors:
1
c = 1 and r = 1
1
1
That is
1 1 1 1
cr = 1
T 1 1 1 = 1 1 1 =w
• A separable kernel of size mxn can be expressed as the
outer product of two vectors, v and w:
w = v wT --------- (11)
where v and w are vectors of size mx1 and nx1,
respectively. For a square kernel of size mxm we write
w = vvT --------- (12)
• The importance of separable kernels lies in the
computational advantages that result from the
associative property of convolution. If we have a
kernel w. that can be decomposed into two simpler
kernels, such that w = w1 w2, then it follows from the
commutative and associative properties in Table above:
• The importance of separable kernels lies in the
computational advantages that result from the
associative property of convolution.
• If we have a kernel w. that can be decomposed into
two simpler kernels, such that then it follows from
the commutative and associative properties in Table
before that:
w f = (w1 w2) f = (w2 w1) f=w2 (w1 f) =(w1 f) w2 --(13)
• This equation says that convolving a separable kernel with an image is
the same as convolving w1 with f first, and then convolving the result
with w2.
• Thus, the computational advantage of performing
convolution with a separable, as opposed to a
nonseparable, kernel is defined as:
MN mn mn
C= = ------ (14)
MN( m+n) m+n
•For a kernel of modest size, say 11x11 the
computational advantage (and thus execution-time
advantage) is a respectable 5.2.
For kernels with hundreds of elements, execution
times can be reduced by a factor of a hundred or
more, which is significant.
5.3 Smoothing (Lowpass) Spatial Filters
• Smoothing (also called averaging) spatial filters are
used to reduce sharp transitions in intensity.
• Because random noise typically consists of sharp
transitions in intensity, an obvious application of
smoothing is noise reduction.
• Smoothing prior to image resampling to reduce
aliasing, is also a common application.
• Smoothing is used to reduce irrelevant detail in an
image, where “irrelevant” refers to pixel regions that
are small with respect to the size of the filter kernel.
• Another application is for smoothing the false contours
that result from using an insufficient number of
intensity levels in an image.
• Linear spatial filtering consists of convolving an image
with a filter kernel.
• Convolving a smoothing kernel with an image blurs the
image, with the degree of blurring being determined
by the size of the kernel and the values of its
coefficients.
• Lowpass filters are fundamental, in the sense that
other important filters, including sharpening
(highpass), bandpass, and bandreject filters, can be
derived from lowpass filters.
• We discuss in this section lowpass filters based on box
and Gaussian kernels, both of which are separable.
 Box Filter Kernels

Test pattern 1024 x1024

box kernels 3 x3
• The simplest,
separable lowpass
filter kernel is the box
kernel, whose
coefficients have the
same value (typically
1).
• The name “box

box kernels 11 x11

box kernels 21 x21

kernel” comes from a
constant kernel
resembling a box
when viewed in 3-D.
• Example 1: a test
pattern image of size
1024x1024 pixels.
box kernel

Filtered by box filter of

size m x m.
Lowpass Gaussian Filter Kernels
• In applications involving images with a high level of
detail, or with strong geometrical components, the
directionality of box filters often produces
undesirable results.
• The kernels of choice in applications such as those
just mentioned are circularly symmetric (also called
isotropic, meaning their response is independent of
orientation). As it turns out, Gaussian kernels of the
form
---- (15)
• 2-D Gaussian functions in general have elliptical
shapes, which are separable only in special cases,
such as Eq. (15) , or when they are aligned with the
coordinate axes.
• Eq. (15) as,

----- (16)
• This form also reminds us that the function is
circularly symmetric.
• Variable r is the distance from the center to any
point on function G.
• Figure shows values of r for several kernel sizes
using integer values for s and t. Because we work
generally with odd kernel sizes, the centers of such
kernels fall on integer values, and it follows that all
values of r2 are integers also.
• Note in particular that the distance squared to the
corner points for a kernel of size m x m is:
------ (17)
Sampling a
Gaussian function
to obtain a discrete
Gaussian kernel.

For k=1 and σ =1,

Resulting
3 x 3 kernel Distances from the center for various sizes of square kernels
• Separability is one of many fundamental properties of
circularly symmetric Gaussian kernels.
• The values of a Gaussian function at a distance larger
than 3σ from the mean are small enough that they can
be ignored.
• This means that if we select the size of a Gaussian
kernel to be ɾ6σɿ x ɾ6σɿ (the notation ɾcɿ is used to
denote the ceiling of c; that is, the smallest integer not
less than c).
• This property tells us that there is nothing to be gained
by using a Gaussian kernel larger than ɾ6σɿ x ɾ6σɿ for
image processing.
• We would use the smallest odd integer that satisfies
this condition.
• Two other fundamental properties of Gaussian
functions are that the product and convolution of
two Gaussians are Gaussian functions also.
• Table below shows the mean and standard
deviation of the product and convolution of two 1-D
Gaussian functions, f and g. (remember, because of
separability, we only need a 1-D Gaussian to form a
circularly symmetric 2-D function).
• The mean and standard deviation completely define
a Gaussian, so the parameters in Table below tell us
all there is to know about the functions resulting
from multiplication and convolution of Gaussians.
• Table

The convolution result is of particular importance in filtering.

If the kernels are Gaussian, we can use the result in Table above (which, as
noted, generalizes directly to more than two functions) to compute the
standard deviation of the composite kernel (and thus completely define it)
without actually having to perform the convolution of all the individual kernels.
• Example 2: Lowpass
filtering with a Gaussian
kernel.
• To compare Gaussian and
box kernel filtering, we
repeat Example 1, using a
Gaussian kernel.
• Gaussian kernels have to A test pattern 1024 x 1024 Gaussian kernel 21 x 21
be larger than box filters to
standard deviations σ=3.5
achieve the same degree of
blurring.
• This is because, whereas a
box kernel assigns the
same weight to all pixels, We used k=1 in all
the values of Gaussian cases.
kernel coefficients
decreases as a function of
distance from the kernel Gaussian kernel 43 x 43
center. standard deviations σ=7
• To demonstrate that there is little to be gained by
using a Gaussian kernel larger than ɾ6σɿ x ɾ6σɿ.
• We filtered the test pattern of size 1024 x 1024
using a Gaussian kernel with again, but of size 85 x
85, As you can see, not discernible additional
blurring occurred, from the one filtered by Gaussian
kernel of size 43 x 43.
• In fact, the difference image below indicates that
the two images are nearly identical, their maximum
difference being 0.75, which is less than one level
out of 256.
Gaussian kernel 43 x 43
standard deviations σ=7
Gaussian kernel 85 x 85
standard deviations σ=7
Difference image.
• Example 3: Comparison of Gaussian and
box filter smoothing characteristics. The
• Shows the different behavior between image and rectangle
box and Gaussian kernels more clearly. are of sizes
• The image of the rectangle was 1024x1024 and
smoothed using a box and a Gaussian
768x128 pixels,
kernel the parameters were selected to
give blurred rectangles of approximately
respectively.
the same width and height, in order to
show the effects of the filters on a Image of a white rectangle on a black
comparable basis. background
• The box filter produced linear
smoothing, with the transition from
black to white (i.e., at an edge) having
the shape of a ramp. The important
features here are hard transitions at the
onset and end of the ramp. We would
use this type of filter when less
smoothing of edges is desired.
• Conversely, the Gaussian filter yielded
significantly smoother results around the smoothing this image smoothing the image
edge transitions. We would use this type with a box kernel of size using a Gaussian kernel of
of filter when generally uniform 71x71 and corresponding size 151x151 with K=1
smoothing is desired. intensity profile and σ=25.
• As the results in Examples 1 , 2 , and 3 show, zero padding an
image introduces dark borders in the filtered result, with the
thickness of the borders depending on the size and type of
the filter kernel used.
• when discussing correlation and convolution, we mentioned
two other methods of image padding
1. Mirror (also called symmetric) padding, in which values
outside the boundary of the image are obtained by mirror-
reflecting the image across its border; mirror padding is
more applicable when the areas near the border contain
image details. and
• Replicate padding, in which values outside the boundary are
set equal to the nearest image border value. The latter
padding is useful when the areas near the border of the
image are constant.
• Figure
illustrates these A Gaussian
padding methods, and kernel of size 187x187,
also shows the effects
of more aggressive with K=1 and σ=31 was
smoothing. used in all three cases.
• The differences
between the borders zero padding
of the results with the
zero-padded image
and the other two are
obvious, and indicate
that mirror and
replicate padding
yield more visually
appealing results by
eliminating the dark
borders resulting mirror padding replicate padding
from zero padding.
• The amount of relative
blurring produced by a Mirror
smoothing kernel of a
given size depends padding was used
directly on image size. throughout.
• After the fact, this may
seem like a trivial
observation, but you
Test pattern of size
would be surprised at 4096x4096 pixels.
how frequently not
understanding the
relationship between
kernel size and the size
of objects in an image
can lead to ineffective
performance of spatial
filtering algorithms.
Gaussian kernel of size Gaussian kernel of size
187x187 with K=1 and 745x745 elements, with
σ=31 K=1 and σ=124.
• Example 4: Using
lowpass filtering and Filtering the original
thresholding for image with a Gaussian
region extraction. kernel of size 151x151
• Our objective is to (approximately 6% of the
illustrate lowpass image width) and
filtering combined standard deviation σ=25. A Hubble Telescope
with intensity image of the Hickson
Compact Group.
thresholding for
eliminating irrelevant
detail in this image. In
the present context,
“irrelevant” refers to
pixel regions that are
small compared to
kernel size. Lowpass filtering with thresholding the filtered
a Gaussian kernel. image (intensities were
scaled to the range [0, 1]).
• Example 5: Shading correction The 2048x2048 checkerboard
image whose inner squares
using lowpass filtering.
are of size 128x128 pixels.
• One of the principal causes of The result of lowpass
image shading is nonuniform filtering the image with
512x512 a Gaussian kernel
illumination. Shading
(four times the size of the
correction (also called flat- squares), K=1
field correction) is important and σ=128 (equal to the size
because shading is a common of the squares, is just large Image shaded by a
enough to blur-out the shading pattern oriented
cause of erroneous
squares in the -45⁰ direction.
measurements, degraded
performance of automated
image analysis algorithms,
and difficulty of image
interpretation by humans.
• We corrected a shaded image
by dividing it by the shading
pattern. Lowpass filtering is a
Estimate of the shading Result of dividing the
rugged, simple method for patterns obtained using image by the shading
estimating shading patterns. lowpass filtering. pattern.