(9) Morphological Image Processing
- Morphology
A branch of biology that deals with the form and structure of
animals and plants
- Mathematical morphology
A tool to extract image components for representing and describing
region shapes
y E.g.: boundary, skeleton, convex hull
(a) Basic set operations
- Definitions
y If w is an element of set A: w A
y If w is not an element of A: w A
y If set B of pixel coordinates satisfies a condition: B = {w | condition}
y Complement of A: Ac = {w | w A}
9-1
y Union of A and B: A B
y Intersection of A and B: A B
y Difference of A and B: A B = {w | w A, w B} = A Bc
y Reflection of B: B = {w | w = b, for b B}
y Translation of A by point z = (z1, z2): (A)z = {c | c = a + z, for a A}
- MATLAB set operations on binary images
Set Operation
A B
A B
c
A
A B
MATLAB Expression
A&B
A|B
~A
A & ~B
Name
AND
OR
NOT
DIFFERENCE
(b) Dilation
- Dilation: grow or thicken an object in a binary image
y Extent of thickening controlled by a structuring element
9-2
y Dilation of image A and structuring element B: A B
A B = {z | ( B ) z A }
with A is
The set of all points z such that the intersection of ( B)
z
nonempty
y E.g., a five-pixel-long diagonal line with the origin at the center
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
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
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
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
When the structuring element overlaps 1-valued pixels, the pixel at the
origin is marked 1
y Commutative: A B = B A
9-3
y Associative: A (B C) = (A B) C
* If B = (B1 B2), then A B = A (B1 B2) = (A B1) B2
Dilate A by B1, and then dilate the result by B2 (decomposition)
* E.g., decomposing a structuring element saves computational cost
MATLAB decomposes structuring element automatically
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 1
1
1
y MATLAB: use dilation to bridge gaps
A = imread('text.tif'); B = [0 1 0; 1 1 1; 0 1 0]; A2 = imdilate(A, B); imshow(A2);
9-4
y strel function: create morphological structuring elements
SE = strel(shape, parameters)
* shape: 'arbitrary', 'diamond', 'disk', 'line', 'square', 'rectangle'
(c) Erosion
- Erosion: shrink or thin an object in a binary image
y Extent of shrinking controlled by a structuring element
y Erosion of image A and structuring element B: A \ B
c
A \ B = {z | (B)z A }
c
The set of all points z such that the intersection of (B)z with A is
nonempty
y E.g., a three-pixel-long vertical line with the origin at the center
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
1
1
1
0
0
1
1
1
0
0
1
1
1
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
9-5
When the structuring element overlaps only 1-valued pixels, the pixel at
the origin is marked 1 (i.e., does not overlap background)
y MATLAB: use erosion to eliminate irrelevant details
A = imread('dots.tif'); B = ones(7);
A1 = imerode(A, B); A2 = imdilate(A1, B);
A1
A2
(d) Opening and closing
- Opening: smooths the contour, breaks narrow isthmuses, and eliminates thin
protrusions
(A B) = (A \ B) B = {(B)z | (B)z A}
Erosion followed by dilation (: union of all the sets inside the braces),
9-6
MATLAB: imopen( )
- Closing: smooths the contour, fuses narrow breaks and long thin gulfs, and
eliminates small holes
(A B) = (A B) \B = {z | (B)z A }
Dilation followed by erosion, MATLAB: imclose( )
9-7
(e) Hit-or-miss transformation
- Hit-or-miss transformation: identify special configuration of pixels
A B = (A \ B1) (Ac \ B2)
y E.g., identify
0 1 0
1 1 1
0 1 0
1
1 1 1
1
B2 1
A \ B1:
A:
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
1
0
0
0
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
Ac:
1
1
1
1
1
1
1
B1
1
1
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
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
1
0
1
0
1
0
0
0
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
1
1
1
0
1
0
1
Ac \ B2:
1
0
0
0
0
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
0
0
0
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
0
0
1
1
1
0
1
0
0
0
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
1
0
0
0
0
0
0
1
1
1
0
1
0
1
1
0
0
0
0
0
0
1
A B1:
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9-8
y MATLAB: C = bwhitmiss(A, B1, B2);
(f) Basic morphological operations
- Boundary extraction: extract the boundary of an object
(A) = A (A \ B)
y MATLAB
A = imread('A.tif'); B = ones(3); A1 = A - imerode(A, B);
- Region filling
Xk = (Xk1 B) Ac
k = 1, 2, 3
y X0: a background point inside the object; converged when Xk = Xk1
9-9
y MATLAB
A = im2bw(imread('eye.tif')); B = [0 1 0; 1 1 1; 0 1 0];
Xk = zeros(size(A)); Xk1 = Xk; Xk(85, 70) = 1;
while any(Xk(:) ~= Xk1(:))
Xk1 = Xk;
Xk = imdilate(Xk1, B) & ~A;
end
A1 = Xk | A;
eye.tif
Region filled
* Problem: need to find the initial point
Solution?
- Extraction of connected components
9-10
Xk = (Xk1 B) A
k = 1, 2, 3
y X0: a point of the object; converged when Xk = Xk1
y MATLAB
A = im2bw(imread('a.tif')); B = ones(3);
Xk = zeros(size(A)); Xk1 = Xk; Xk(30, 40) = 1;
while any(Xk(:) ~= Xk1(:))
Xk1 = Xk;
Xk = imdilate(Xk1, B) & A;
end
A1 = Xk;
a.tif
One component found
y MATLAB bwlabel: find all connected components
9-11
[label number] = bwlabel(im, 4); or [label number] = bwlabel(im, 8);
* label: output image with labeled objects (4- or 8-connectivity)
* number: the number of labeled objects
- Convex hull
y A set A is convex if the straight line segment joining any two points
in A lies entirely within A
y Convex hull H of set S is the smallest convex set containing S
y H S: convex deficiency of S
y Four structuring elements: Bi, i = 1, 2, 3, 4, (: dont care)
9-12
1
B
2
B
B3
B4
y Convex hull of A: C(A)
X ki = ( X ki 1 B i ) A, i = 1, 2, 3, 4
4
D =X
i
i
conv
C ( A) = U D i
i =1
- Thinning
A ~ B = A (A B) = A (A B)c
where {B} = {B1, B2, , Bn}
y Eight structuring elements: Bi, i = 1, 2, , 8
2
B
B1
B3
B4
B5
6
B
B7
B8
9-13
y Problem: connectivity not guaranteed
- Thickening
A } B = A (A B)
where {B} = {B1, B2, , Bn}
y Eight structuring elements are the same as those of thinning
- Skeletonization
y Repeatedly delete the contour points provided the following
conditions are satisfied
* End points are not deleted
* Connectivity are not broken
* Do not cause excessive erosion of the region
y Algorithm: repeat following steps until no contour points
(1) Delete all contour points according to Definition 1
(2) Delete all contour points according to Definition 2
y Definition 1: right, bottom, and upper left corner contour points
9-14
(a) 2 N(p1) 6
(b) T(p1) = 1
(c) p2 p4 p6 = 0
(d) p4 p6 p8 = 0
p9
p2
p3
p8
p1
p4
p7
p6
p5
* N(p1): number of 1s in the neighborhood of p1
N ( p1 ) = i = 2 pi
9
* T(p1): number of 0-1 transitions in the ordered sequence p2, p3, ,
p8, p9, p2 (clockwise)
# E.g.:
0 0 1
N(p1) = 4, T(p1) = 3
1 p1 0
p2 p4 p6 = 0
p4 p6 p8 = 0
1 0 1
y Definition 2: left, top, and lower right corner contour points
(a) and (b) are the same as those in definition 1
(c') p2 p4 p8 = 0;
9-15
(d') p2 p6 p8 = 0;
y Description:
* (a): if there is only one 1 in the neighborhood, p1 is an end point and
should not be deleted; if there are seven 1s, deleting p1 would cause
erosion; if there are eight 1s, p1 is not a contour point
* (b): T(p1) 1: p1 is an arc point and deleting p1 would break the
connectivity
If the mask consists of only two connected regions, T(p1) = 1
p1
p1
p1
* (c) and (d): p4 = 0 or p6 = 0 or p2 = p8 = 0
Right, bottom, and upper left corner contour points
9-16
p2
p4
p8
p6
* (c') and (d'): p2 = 0 or p8 = 0 or p4 = p6 = 0
Top, left, and lower right corner contour points
p2
p8
p4
p6
y Examples of contour definitions 1 and 2:
(Def. 1)
(Def. 2)
9-17
y E.g.:
Image
Thinning
bwmorph(, 'thin', Inf) bwmorph(, 'skel', Inf)
9-18
- MATLAB morphing function
bwmorph(bw, operation)
or bwmorph(bw, operation, n)
y bw: binary image, n: number of repeations of the operation
y operation:
'bothat' Bottom hat operation using a 33 structuring element; use imbothat for other
structuring elements
'erode' Erosion using a 33 structuring element; use imerode for other structuring
elements
'shrink' Shrink objects with no holes to points; shrink objects with holes to rings
'bridge' Connect pixels separated by single-pixel gaps
Fill in single-pixel holes; use imfill for larger holes
'fill'
Skeletonize an image
'skel'
'clean' Remove isolated foreground pixels
'hbreak' Remove H-connected foreground pixels
Remove spur pixels
'spur'
'close' Closing using a 33 structuring element; use imclose for other structuring
elements
'majority' Makes pixel p a foreground pixel if N8(p) 5; otherwise make p a background
pixel
9-19
'thicken' Thicken objects without joining disconnected 1s
Fill in around diagonally connected foreground pixels
'diag'
'open' Opening using a 33 structuring element; use imopen for other structuring
elements
Thin objects without holes to minimally connected strokes; thin objects with
'thin'
holes to rings
'dilate' Dilation using a 33 structuring element; use imdilate for other structuring
elements
'remove' Remove interior pixels
'tophat' Top hat operation using a 33 structuring element; use imtophat for other
structuring elements
(g) Gray-scale morphology
- Morphology
y Binary image: change the shape of the foreground objects
y Gray-scale image: change the shape of the image surface (3D)
- Gray-scale dialtion and erosion
y Dialtion: f b(x, y) = max{f(xx', yy') + b(x', y') | (x', y') Db}
9-20
where Db is the domain of b, and f(x, y) is assumed to equal
outside the domain of f
y Erosion: f \ b(x, y) = min{f(x+x', y+y') b(x', y') | (x', y') Db}
where Db is the domain of b, and f(x, y) is assumed to equal +
outside the domain of f
- Opening and closing
Original
Opening
Closing
9-21
- Example: using opening to compensate for nonuniform background
illumination
y Fig. 1: rice grains on nonuniform background (darker towards
bottom), f = imread('rice.tif')
y Fig. 2: simple thresholding: fbw = im2bw(f, graythresh(f)) causes grains
improperly separated at the bottom portion
y Fig. 3: opening with se = strel('disk', 10); fo = imopen(f, se): since the size
of se is set to be larger than the grains, only background remains
y Fig. 4: subtracting from the original f2 = imsubtract(f, fo): results in a
more uniform background
y Fig. 5: thresholding with fbw = im2bw(f2, graythresh(f2)) obtains a better
result
y Subtracting an opened image from the original is called the top-hat
transformation, a single step in Matlab: f2 = imtophat(f, se)
9-22
Fig. 1
Fig. 2
Fig. 4
Fig. 5
Fig. 3
9-23
