296 A Computational Introduction to Digital Image Processing, Second Edition
10.8 Grayscale Morphology
The operations of erosion and dilation can be generalized to be applied to grayscale
images. But before we do, we shall reconsider binary erosion and dilation. We have defined
binary erosion, A B, to be the union of the (0, 0) positions of all translations B
x
for which
B
x
⊆ A.
Suppose we take B to be a 3 ×3 square consisting entirely of zeros. Let A be the image
as shown in Figure 10.31. Now suppose we move over the image A, and for each point p we
0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 0
0 1 1 1 1 1 0 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0
0 0 0 1 1 1 1 0
0 0 0 0 0 0 0 0
A
0 0 0
0 0 0
0 0 0
B
FIGURE 10.31: An example for erosion
perform the following steps:
1. Find the 3 × 3 neighborhood N
p
of p
2. Compute the matrix N
p
− B
3. Find the minimum of that result.
We note that since B consists of all zeros, the second and third items could be reduced to
finding the minimum of N
p
. However, we shall see that for generalization it will be more
convenient to have this expanded form. An immediate consequence of these steps is that if
a neighborhood contains at least one zero, the output will be zero. The output is one only
if the neighborhood contains all ones. For example:
0 0 0
0 1 1
0 1 1
−→ 0
If we perform this operation, we will obtain:
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 1 1 0 0 0
0 0 1 1 1 0 0
0 0 1 1 1 0 0
0 0 0 1 1 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
which you can verify is exactly the erosion A B.
For dilation, we perform a sequence of steps very similar to those f or erosion:
Mathematical Morphology 297
1. Find the 3 × 3 neighborhood N
p
of p
2. Compute the matrix N
p
+ B
3. Find the maximum of that result.
We note again that since B consists of all zeros, the second and third items could be reduced
to finding the maximum of N
p
. If the neighborhood contains at least one
1
, then the output
will be
1. The output will be 0 only if the neighborhood contains all zeros.
Suppose A to be surrounded by zeros, so that neighborhoods are defined for all points
in A above. Applying these steps produces:
1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1
which again can be verified to be the dilation A ⊕ B.
If A is a grayscale image, and B is a structuring element, which will be an array of
integers, we define grayscale erosion by using the steps above; for each pixel p in the image:
1. Position B so that (0, 0) lies over p
2. Find the neighborhood N
p
of p corresponding to the shape of B
3. Find the value min(N
p
− B).
We note that there is nothing in this definition which requires B to be any particular shape
or size or that the elements of B be positive. And as for binary dilation, B does not have
to contain the origin (0, 0).
We can define this more formally; let B be a set of points with associated values. For
example, f or our square of zeros we would have:
Point
Value
(−1, −1) 0
(−1, 0)
0
(−1, 1)
0
(0, −1)
0
(0, 0)
0
(0, 1)
0
(1, −1)
0
(1, 0)
0
(1, 1)
0
The set of points forming B is called the domain of B and is denoted D
B
. Now we can
define:
(A B)(x, y) = min{A(x + s, y + t) − B(s, t), (s, t) ∈ D
B
},
(A ⊕B)(x, y) = max{A(x + s, y + t) + B(s, t), (s, t) ∈ D
B
}.
We note that some published definitions use s −x and t −y instead of x + s and y + t. This
just requires that the structuring element is rotated 180
◦
.
298 A Computational Introduction to Digital Image Processing, Second Edition
y
1 2 3 4 5
1 10 20 20 20 30
2 20 30 30 40 50
x 3 20 30 30 50 60
4
20 40 50 50 60
5 30 50 60 60 70
A
t
−1 0 1
−1 1 2 3
s 0 4 5 6
1
7 8 9
B
FIGURE 10.32: An example for grayscale erosion and dilation
An example. Suppose we take A and B as given in Figure 10.32.
In this example (0, 0) ∈ D
B
. Consider (A B) ( 1, 1). By the definition, we have:
(A B)(1, 1) = min{A(1 + s, 1 + t) − B(s, t), (s, t) ∈ D
B
}.
Since D
B
= {(s, t) : −1 ≤ s ≤ 1; −1 ≤ t ≤ 1}, we have
(A B)(1, 1) = min{A(1 + s, 1 + t) − B(s, t) : −1 ≤ s ≤ 1; −1 ≤ t ≤ 1}.
In order to ensure we do not require matrix indices that move outside A, we simply “cut
off” the structuring element so that we restrict it to elements in A.
The values of A(1 + s, 1 + t) −B(s, t) can then be obtained by matrix arithmetic:
10 20
20 30
−
5 6
8 9
=
5 14
12 21
and the minimum of the result is
5. Note that to create the matrices we ensure that the
(0, 0) point of B sits over the current point of A, in this case the point (1, 1). Another
example:
(A B)(3, 4) = min
30 40 50
30 50 60
50 50 60
−
1 2 3
4 5 6
7 8 9
= min
29 38 47
26 45 54
43 42 51
= 26.
Finally, we have
A B =
5 6 14 15 16
8 9 17 18 19
12 13 25 26 39
15 16 28 29 46
18 19 39 48 49
Dilation is very similar to erosion, except that we add B and take the maximum of the
result. As for erosion we restrict the structuring element so that it does not go outside of
A. For example:
(A ⊕B)(1, 1) = max
10 20
20 30
+
5 6
8 9
= max
15 26
28 39
= 39,
(A ⊕B)(3, 4) = max
30 40 50
30 50 60
50 50 60
+
1 2 3
4 5 6
7 8 9
= max
31 42 53
34 55 66
57 58 69
= 69.
Mathematical Morphology 299
After all the calculations, we have
A ⊕B =
39 39 49 59 58
39 39 59 69 68
49 59 59 69 68
59 69 69 79 78
56 66 66 76 75
Note that an erosion may contain negative values, or a dilation value greater than 255.
In order to render the result suitable for display, we have the same choices as for spatial
filtering: we may apply a linear transformation or we may clip values.
In general, and this can be seen from the examples, erosion will tend to decrease and
darken objects in an image, and dilation will tend to enlarge and lighten objects.
Relationship between Grayscale Erosion and Dilation
By definition of maximum and minimum we have, if X and Y are two matrices:
max{X + Y } = −min{−X − Y }.
Since max{X + Y } corresponds to A ⊕ B and min{X −Y } to A B, we have
A ⊕B = −(−A B),
A B = −(−A ⊕ B),
or
−(A ⊕B) = −A B,
−(A B) = −A ⊕ B.
We can use the
imerode and imdilate functions for grayscale erosion and dilation, but
we have to be more careful about the structuring element. To create a structuring element
for use with grayscale morphology, we can either use a binary mask, or we have to provide
both a neighborhoo d D
B
, and its values. To do this we need to use the strel function.
For example, we shall use MATLAB with the previous examples. First we need to create
the structuring element.
MATLAB/Octave
>> str = strel(’arbitrary’,ones(3,3),[1 2 3;4 5 6;7 8 9])
str =
Nonflat STREL object containing 9 neighbors.
Neighborhood:
1 1 1
1 1 1
1 1 1
Height:
1 2 3
4 5 6
7 8 9
300 A Computational Introduction to Digital Image Processing, Second Edition
Here we use the
arbitrary parameter of strel; this allows us to create a structuring
element containing any values we like. The first matrix:
ones(3,3)
provides the neighbor-
hood; the second matrix provides the values. Now we can test it.
MATLAB/Octave
>> A = [10 20 20 20 30;20 30 30 40 50;20 30 30 50 60;20 40 50 50 60;30 50
60 60 70];
>> imerode(A,str)
ans =
5 6 14 15 16
8 9 17 18 19
12 13 25 26 39
15 16 28 29 46
18 19 39 48 49
Python provides this generalized erosion as gray
_
erosion in the ndimage module of scipy:
Python
In : A = np.array([[10,20,20,20,30],[20,30,30,40,50],[20,30,30,50,60],
[20,40,50,50,60],[30,50,60,60,70]]).astype(’uint8’)
In : struct = np.array([[1,2,3],[4,5,6],[7,8,9]])
In : print ndi.gray
_
erosion(A,footprint=mo.square(3),structure=struct)
[[ 5 6 14 15 16]
[ 8 9 17 18 19]
[12 13 25 26 39]
[15 16 28 29 46]
[18 19 39 48 49]]
For dilation MATLAB implements the convention of the structuring element being rotated
by 180
◦
. So to obtain the result we produced before, we need to rotate str to obtain str2.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.