Morphological Image Processing
Topics
Once segmentation is complete, morphological operations
can be used to remove imperfections in the segmented
image and provide information on the form and structure of
the image
In this lecture we will consider
– What is morphology?
– Simple morphological operations
– Compound operations
– Morphological algorithms
Amr Abdel-Dayem 2
1, 0, Black, White?
• Throughout all of the following slides whether 0 and 1
refer to white or black is a little interchangeable
• All of the discussion that follows assumes segmentation
has already taken place and that images are made up of
0s for background pixels and 1s for object pixels
• After this it doesn t matter if 0 is black, white, yellow,
green…….
Amr Abdel-Dayem 3
What Is Morphology?
• Morphological image processing (or morphology)
describes a range of image processing techniques that
deal with the shape (or morphology) of features in an
image
• Morphological operations are typically applied to remove
imperfections introduced during segmentation, and so
typically operate on bi-level images
Amr Abdel-Dayem 4
Quick Example
Image after segmentation Image after segmentation and
morphological processing
Amr Abdel-Dayem 5
Structuring Elements, Hits & Fits
B Structuring Element
Fit: All on pixels in the
structuring element cover
on pixels in the image
A
Hit: Any on pixel in the
C structuring element covers
an on pixel in the image
All morphological processing operations are based
on these simple ideas Amr Abdel-Dayem 6
Structuring Elements
Structuring elements can be any size and make
any shape
However, for simplicity we will use rectangular
structuring elements with their origin at the middle
pixel
0 0 1 0 0
1 1 1 0 1 0 0 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 0
0 1 0
0 0 1 0 0
Amr Abdel-Dayem 7
Fitting & Hitting
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1
0 0 0 1 1 0 0 0 0 0 0 0
1 1 1
0 0 1 B
1 1 1 1 0 C
0 0 0 0
1 1 1
0 1 1 1 1 1 1 1 0 0 0 0 Structuring
0 1 1 1 1 1 1 1 0 0 0 0 Element 1
0 0 1 1 1 1 1 1 0 0 0 0 0 1 0
0 0 1 1 1 1 1 1 1 0 0 0 1 1 1
0 0 1 1 1 1 1 A
1 1 1 1 0 0 1 0
0 0 0 0 0 1 1 1 1 1 1 0 Structuring
Element 2
0 0 0 0 0 0 0 0 0 0 0 0 8
Fundamental Operations
• Fundamentally morphological image processing
is very like spatial filtering
• The structuring element is moved across every
pixel in the original image to give a pixel in a
new processed image
• The value of this new pixel depends on the
operation performed
• There are two basic morphological operations:
erosion and dilation
Amr Abdel-Dayem 9
Erosion
• Erosion of image f by structuring element s is
given by f y s
• The structuring element s is positioned with its
origin at (x, y) and the new pixel value is
determined using the rule:
ì 1 if s fits f
g ( x, y ) = í
î0 otherwise
Amr Abdel-Dayem 10
Erosion Example
Original Image Processed Image With Eroded Pixels
Structuring Element
Amr Abdel-Dayem 11
Erosion Example
Original Image Processed Image
Structuring Element
Amr Abdel-Dayem 12
Erosion Example 1
Original image Erosion by 3*3 Erosion by 5*5
square structuring square structuring
element element
Watch out: In these examples a 1 refers to a black pixel!
Amr Abdel-Dayem 13
Erosion Example 2
Amr Abdel-Dayem 14
What Is Erosion For?
Erosion can split apart joined objects
Erosion can split apart
Erosion can strip away extrusions
Watch out: Erosion shrinks objects
Amr Abdel-Dayem 15
Dilation
• Dilation of image f by structuring element s is
given by f Å s
• The structuring element s is positioned with its
origin at (x, y) and the new pixel value is
determined using the rule:
ì1 if s hits f
g ( x, y ) = í
î0 otherwise
Amr Abdel-Dayem 16
Dilation Example
Original Image Processed Image
Structuring Element
Amr Abdel-Dayem 17
Dilation Example
Original Image Processed Image With Dilated Pixels
Structuring Element
Amr Abdel-Dayem 18
Dilation Example 1
Original image Dilation by 3*3 Dilation by 5*5
square structuring square structuring
element element
Watch out: In these examples a 1 refers to a black pixel!
Amr Abdel-Dayem 19
Dilation Example 2
Amr Abdel-Dayem 20
What Is Dilation For?
Dilation can repair breaks
Dilation can repair intrusions
Watch out: Dilation enlarges objects
Amr Abdel-Dayem 21
Compound Operations
More interesting morphological operations can be
performed by performing combinations of erosions
and dilations
The most widely used of these compound
operations are:
– Opening
– Closing
Amr Abdel-Dayem 22
Opening
The opening of image f by structuring element s,
denoted f s is simply an erosion followed by a
dilation
f s = (f ys)Å s
Original shape After erosion After dilation
(opening)
Note a disc shaped structuring element is used
Amr Abdel-Dayem 23
Opening
The opening operation has a simple geometric
interpretation: imagine the structuring element as a flat
“rolling ball” that rolls inside the boundary of A
f s = (f ys)Å s
Original shape opening
Amr Abdel-Dayem 24
Opening Example
Original
Image
Image
After
Opening
Amr Abdel-Dayem 25
Opening Example
Original Image Processed Image
Structuring Element
Opening Example
Original Image Processed Image
Structuring Element
Closing
The closing of image f by structuring element s, denoted f • s
is simply a dilation followed by an erosion
f • s = (f Å s)ys
Original shape After dilation After erosion
(closing)
Note a disc shaped structuring element is used
Amr Abdel-Dayem 28
Closing
The opening operation has a simple geometric interpretation:
imagine the structuring element as a flat “rolling ball” that rolls
outside the boundary of A
f • s = (f Å s)ys
Original shape After erosion
(closing)
Note a disc shaped structuring element is used
Amr Abdel-Dayem 29
Closing Example
Original
Image
Image
After
Closing
Amr Abdel-Dayem 30
Morphological Processing Example
Amr Abdel-Dayem 31
Morphological Algorithms
• Using the simple technique we have looked at so far
we can begin to consider some more interesting
morphological algorithms
• We will look at:
– Boundary extraction
– Region filling
• There are lots of others as well though:
– Extraction of connected components
– Thinning/thickening
– Skeletonisation
Amr Abdel-Dayem 32
Boundary Extraction
Extracting the boundary (or outline) of an object is
often extremely useful
The boundary can be given simply as
β(A) = A – (AyB)
33
Boundary Extraction Example
• A simple image and the result of performing boundary
extraction using a square 3*3 structuring element
Original Image Extracted Boundary
Amr Abdel-Dayem 34
Region Filling
• Given a pixel inside a boundary, region filling attempts
to fill that boundary with object pixels (1s)
Given a point inside
here, can we fill the
whole circle?
Amr Abdel-Dayem 35
Region Filling (cont…)
The key equation for region filling is
X k = ( X k -1 Å B) Ç A c
k = 1,2,3.....
Where X0 is simply the starting point inside the boundary, B is
a simple structuring element and Ac is the complement of A
This equation is applied repeatedly until Xk is equal to Xk-1
Finally the result is unioned with the original boundary
Amr Abdel-Dayem 36
Region Filling (cont…)
37
Extraction of connected components
Amr Abdel-Dayem 38
Example
Amr Abdel-Dayem 39
Hit-and-Miss Transform ⊛ (HMT)
• Brief Description
– General binary morphological operation that can be
used to look for particular patterns in an image.
– A tool for shape detection
– Basic operation for binary morphology
• Almost all the other binary morphological operators can be
derived from Hit-and-Miss Transform.
Common names: Hit-and-miss Transform, Hit-or-miss Transform
Amr Abdel-Dayem 40
Hit-and-Miss Transform ⊛ (HMT)
• How It Works
– The structuring element used in the hit-and-miss can
contain both foreground and background pixels.
– Operations
• If the foreground and background pixels in the structuring
element exactly match foreground and background pixels in
the image, then the pixel underneath the origin of the
structuring element is set to the foreground color.
• If it doesn't match, then that pixel is set to the background
color.
Amr Abdel-Dayem 41
Hit-and-Miss Transform ⊛ (HMT)
• Effect of the hit-and-miss based right angle convex corner
detector
Four structuring elements used for corner finding in binary
images
• After obtaining the locations of corners in each orientation, we can
then simply OR all these images together to get the final result .
Amr Abdel-Dayem 42
Hit-and-Miss Transform ⊛ (HMT)
• Guidelines for Use
– The hit-and-miss transform is used to look for
occurrences of particular binary patterns.
– It can be used to look for several patterns.
• Simply by running successive transforms using different
structuring elements, and then ORing the results together.
– The operations of erosion, dilation, opening, closing,
thinning and thickening can all be derived from the
hit-and-miss transform in conjunction with simple set
operations.
Amr Abdel-Dayem 43
Hit-and-Miss Transform ⊛ (HMT)
• Some structuring elements that can be used for locating
various binary features
Some applications of the hit-and-miss transform
1) is used to locate isolated points in a binary image.
2) is used to locate the end points on a binary skeleton.
– Note that this structuring element must be used in all its orientations,
and thus the four hit-and-miss passes are required.
3a) and 3b) are used to locate the triple points on a skeleton.
– Both structuring elements must be run in all orientations so eight hit-
and-miss passes are required.
Amr Abdel-Dayem 44
Hit-and-Miss Transform ⊛ (HMT)
• The triple points (points where three lines meet) of the skeleton
– The hit-and-miss transform outputs single foreground pixels at each
triple point by structuring elements 3a) and 3b).
Amr Abdel-Dayem 45
Hit-and-Miss Transform ⊛ (HMT)
• The end points of the skeleton
– The hit-and-miss transform outputs single foreground pixels at
each end point by structuring element 2).
Amr Abdel-Dayem 46
Thinning
• Brief Description
– Remove selected foreground pixels from binary
images, somewhat like erosion or opening.
– Thinning is normally applied only to binary images.
Common names: Thinning
Amr Abdel-Dayem 47
Thinning
• How It Works
A Ä B = A – ( A ⊛ B)
A: image, B: structuring element
– Thinning is the dual of thickening.
– Thickening the foreground is equivalent to thinning
the background.
– The operator is normally applied repeatedly until it
causes no further changes to the image.
A Ä {B} = ((…((AÄB1)ÄB2)…) ÄBn
Amr Abdel-Dayem 48
Thinning
• Operation
– The thinning operation is calculated by translating the
origin of the structuring element to each possible pixel
position in the image, and at each such position
comparing it with the underlying image pixels.
– If the foreground and background pixels in the
structuring element exactly match foreground and
background pixels in the image, then the image pixel
underneath the origin of the structuring element is set
to background (zero).
– Otherwise, it is left unchanged.
Amr Abdel-Dayem 49
Thinning
Amr Abdel-Dayem 50
Thinning
Skeletonization by Morphological Thinning
• Skeletons are the medial axes
• Or skeleton S(A) is the set of points that are
centers of maximally inscribed disks in A
• Or skeletons are the set of points situated at
equal distance from at least two boundary
feature points (¶A) of the given shape
S ( A) = { p Î A | $q, r Î ¶A, p - q = p - r }
Amr Abdel-Dayem 51
Thinning
Skeletons
Amr Abdel-Dayem 52
Thinning
Skeletons
Amr Abdel-Dayem 53
Thinning
Skeletonization by Morphological Thinning
Structuring elements for Skeletonization by morphological thinning
• At each iteration, the image is first thinned by the left hand
structuring element, and then by the right hand one, and then with
the remaining six 90°rotations of the two elements.
• The process is repeated in cyclic fashion until none of the thinnings
produces any further change.
Amr Abdel-Dayem 54
Thinning
• Some other common structuring elements
1) Simply finds the boundary of a binary object, the detected boundary
is 8-connected.
2) Does the same thing but produces a 4-connected boundary.
3a) and 3b) are used for pruning
– Note that skeletons produced by this method often contain undesirable
short spike produced by small irregularities in the boundary of the
original object.
– These spikes can be removed by a process called pruning, which is in
fact just another sort of thinning.
Amr Abdel-Dayem 55
Thinning
• The detected lines have all been reduced to a single pixel width.
• Note however that there are still one or two ‘spikes’ present,
which can be removed using pruning.
Amr Abdel-Dayem 56
Thinning
• Character recognition example
Original image Thresholded image Thinning result
• A simple way to obtain the skeleton of the character is to thin the image until
convergence.
• The line is broken at some locations, which might cause problems during the
recognition process. Amr Abdel-Dayem 57
Thinning
– Example: Improve broken line case (dilating twice)
Dilating thresholded image Result of thinning Result of pruning using two
twice with a 3×3 square iterations for each
structuring element orientation of the
structuring element
Amr Abdel-Dayem 58
Thinning
– Example: Improve broken line case (dilating three times)
Dilating thresholded Result of thinning Result of pruning using
image three times with a four iterations for each
3×3 square structuring orientation of the
element structuring element
Amr Abdel-Dayem 59
Thickening
• Brief Description
– Growing selected regions of foreground pixels
in binary images, somewhat like dilation or
closing.
– Normally only applied to the binary images
and produces another binary image as output.
Amr Abdel-Dayem 60
Thickening
• How It Works
A B = A ! (A ⊛ B)
A: image, B: structuring element
• The thickened image consists of the original image plus any
additional foreground pixels switched on by the hit-and-miss
transform.
– Thickening is the dual of thinning.
• Thinning the foreground is equivalent to thickening the
background.
– The operator is normally applied repeatedly until it
causes no further changes to the image.
Amr Abdel-Dayem 61
Thickening
• Operation
– The thickening operation is calculated by translating the
origin of the structuring element to each possible pixel
position in the image, and at each position comparing it
with the underlying image pixels.
– If the foreground and background pixels in the structuring
element exactly match foreground and background pixels
in the image, then the image pixel underneath the origin of
the structuring element is set to foreground (one).
– Otherwise, it is left unchanged.
Amr Abdel-Dayem 62
Convex Hull
• Convex:
An object is convex if for every pair of points within the object, every
point on the straight line segment that joins them is also within the
object. For example, a solid cube is convex, but anything that is
hollow or has a dent in it, for example, a crescent shape, is not
convex.
Amr Abdel-Dayem 63
Convex Hull
• Convex Hull:
The convex hull or convex envelope for a set of points X in a
real vector space V is the minimal convex set containing X.
Amr Abdel-Dayem 64
Convex Hull
Amr Abdel-Dayem 65
Convex Hull
Amr Abdel-Dayem 66
Convex Hull
ymin
ymin
xmin xmax Amr Abdel-Dayem 67
Extension to Gray-Scale Images
• Instead of binary images,
assume we have gray values
f(x,y), where x,y are integer
pixels
• Let b(x,y) be the gray level
structuring element
• We will only focus on flat
(constant value) structuring
elements
Dilation àMax
Erosion àMin
Amr Abdel-Dayem 68
Grayscale Morphology
• Definition of dilation with flat structuring element
( f Å b )( x, y) = (max
s , t )Îb
{ f ( x - s, y - t )}
• Reflect b(s,t), slide it past f(x,y); at each
position, take the maximum of f(x,y) within the
window of b(s,t)
Amr Abdel-Dayem 69
Grayscale Morphology
• Definition of erosion (with flat SE)
( f q b )( x, y) = (min
s , t )Îb
{ f ( x + s, y + t )}
• Slide b(s,t) past f(x,y); at each position, take the
minimum of f(x,y) within that window
Amr Abdel-Dayem 70
Grayscale Morphology
Amr Abdel-Dayem 71
Grayscale Opening and Closing
• Similar to binary case
– Opening is erosion followed f b = ( f θ b) Å b
f • b = ( f Å b) θ b
by dilation
– Closing is dilation followed by
erosion
• Geometric interpretation of
opening
– Push the SE up from below
against the underside of f
– Take the highest values
achieved at every point
Opening removes small,
bright details
Amr Abdel-Dayem 72
Grayscale Opening and Closing
• Geometric interpretation of closing
– Push the SE down from above against the topside of f
– Take the lowest values achieved at every point
Closing removes
small, dark details
Amr Abdel-Dayem 73
Grayscale Opening and Closing
Amr Abdel-Dayem 74
Grayscale Opening and Closing
Morphological smoothing:
• Opening: Suppresses bright details smaller then the
specified SE
• Closing: Suppresses dark details smaller then the
specified SE
Smoothing is achieved by combining opening and
closing operations (sometimes it is preformed in
alternating sequence).
Amr Abdel-Dayem 75
Morphological smoothing
Amr Abdel-Dayem 76
Morphological gradient
gradient = ( f Å b) - ( f Å
y b)
Amr Abdel-Dayem 77
Summary
• The purpose of morphological processing is
primarily to remove imperfections added during
segmentation
• The basic operations are erosion and dilation
• Using the basic operations we can perform
opening and closing
• More advanced morphological operation can
then be implemented using combinations of all
of these
Amr Abdel-Dayem 78