Chapter 7 Morphological Image Processing
Agenda
• Introduction to morphological operations
• Set theory preliminaries
• Binary morphological operations: – Erosion, Dilation, Opening, Closing
• Connected components and labelling
• Morphological algorithms
– Boundary extraction, region filling, hit-or-miss transform
• Grayscale morphological operations
2
Morphological Operations
• Morphology= Shape, Form, Structure
• Morphological operations are used to extract image components for representation and description of region shape, such as boundaries and skeletons.
• Based on set theory
• Applicable to both binary and gray-level images. Application to binary (black-and- white) images is more common.
3
Binarization of Images
• Requiresbinarizationof images before applying binary morphological operations.
• Binaryimagescanbe obtained from
– Thresholding gray-level images
• Iff(x,y)>qtheng(x,y)=1 else g(x,y) = 0
– As a result of feature detectors
• Oftenwanttocountor measure shape of 2D binary image regions
4
Applications of Morphological Operations
• Removing Small Objects
– Remove noise as a side effect of thresholding
– Reduce the effect of over-segmentation: small regions erroneously segmented
• Filling Holes
– Remove holes inside the object due to under- segmentation
• Isolating Objects
– Ensure that the objects are separated from each others
5
Morphological Processing Examples
6
7.1 Binary Morphological Operations
7
Set Theory Preliminaries
Definition:
• For a binary image , is the (unordered) set of pairs (, ) such the image value at (, ) is equal to 1:
• Example:
= {(,)| , = 1}
A = { (2,4), (3,4), (4,3), (2,2), (3,2), (1,1), (4,1) }
8
Basic Set Operations
Given= , , =1 and ={(,)| , =1}
• isanelementofsetA:∈
• UnionoftwosetsAandB:
∪ = {| ∈ OR ∈ } • IntersectionoftwosetsAandB
∩ = {| ∈ AND ∈ } • DifferencebetweentwosetsA
and B
− = {| ∈ AND ∉ }
• ComplementofA
={|∉}
9
Reflection and Translation
Reflection
Translation
10
Structuring Element (SE)
• A structuring element (SE) is applied to each pixel of the input image in morphological operations.
• The SE is small set or subimage, used to probe for structure
• Black dot denotes the origin of SE
• Free to design the SE to fit different purposes
• Gray=1
• White = 0
11
Type and Size of SE
• Type and size to use is up to the user to determine
– Box-shaped SE tends to preserve sharp object corners
– Disk-shaped SE tends to round the corners of the objects
12
Basic Morphological Operations
• A SE is applied through either a Fit or a Hit operation.
• Applying these two operations to each pixel in an image are called Erosion and Dilation, respectively.
• Can combine these two operations to come up with compound operations:
– Opening – Closing
13
Fit
• Foreach‘1’intheSE,we investigate whether the pixel at the same position in the image is also a ‘1’.
• IfALLofthe‘1’sintheSE are covered by the image,
– The SE fits the image at the pixel position in question (the one on which the SE is centered).
– This pixel is set to ‘1’ in the output image. Otherwise, it is set to ‘0’ in the output image.
14
Hit
• Foreach‘1’intheSE,we investigate whether the pixel at the same position in the image is also a ‘1’.
• IfanyONEofthe‘1’sinthe SE is covered by the image,
– The SE hits the image at the pixel position in question (the one on which the SE is centered).
– This pixel is set to ‘1’ in the output image. Otherwise, it is set to ‘0’ in the output image.
15
Fit and Hit Examples
16
Erosion
• Erosion is the application of the Fit operation to every pixel of the image.
• TheerosionofthesetbyaSEis defined as:
⊖ = {| ⊆ }
• The result is the set of all points such
that translated by is contained in .
• Equivalently:
⊖ = {| ∩ = ∅}
17
Applications of Erosion
• Erosion mainly shrinks the object.
• It can be used for:
– Shrinking objects
– Removing small objects or noise
– Removing bridges and branches
– Removing protrusions
– Enlarge holes
18
Erosion Example 1
19
Erosion Example 1
20
Erosion Example 2
• Main object gets smaller. Only “core” of the subject remains.
• The size of this core depends on the size (and shape of the SE)
• The small objects disappears.
21
Erosion Example 3
22
Effect of Disk Size on Erosion
23
Erosion: Real Image Example
• Object becomes smaller and fractured. • Small objects disappear.
• Effect more significant with larger SE.
24
Dilation
• Dilation is the application of Hit operation to every pixel of the image.
• ThedilationofasetbyaSEisdefined as:
⊕ = { | ∩ ≠ ∅ }
• The result is the set of all points such that the reflected translated overlap with at least one element.
• Equivalently:⊕={| ∩ ⊆}
25
Applications of Dilation
• Erosion mainly expands the object.
• It can be used for:
– Growing objects
– Repairing intrustions
– Filling gaps
– Filling holes
26
Dilation Example 1
27
Dilation Example 1
28
Dilation Example 2
29
Dilation Example 2
30
Dilation Example 3
• Object gets bigger. • The hole is filled.
31
Dilation Example 4
32
Dilation Example: Text Image
Dilation bridges gaps.
33
Dilation Example: Real Image
• Main object is becoming bigger
• The hole inside the person are filled
• Small object in the background are also enlarged
34
Duality of Dilation and Erosion
• Erosion and dilation are dual operations with respect to set complementation and reflection:
• Also,
⊖ = ⊕ ⊕ = ⊖
• Interpretation when SE is symmetric:
– First equation: The complement of the erosion operation of an image is the dilation of its background
– Second equation: The complement of the dilation operation of an image is the erosion of its background.
35
Duality
Proof:
⊖ = ⊕
36
Example
37
Example
38
Compound Operations
• More interesting morphological operations can be performed by combining erosions and dilations in order to reduce shrinking or thickening.
• The most widely used of these compound operations are:
– Opening: Erosion followed by Dilation – Closing: Dilation followed by Erosion
39
Opening
• The opening of set by structuring element is defined as
∘= ⊖ ⊕
which is an erosion of by followed by a dilation of the result by .
40
Opening
• Geometric interpretation: The opening of by is the union of all translations of so that is fitted entire within .
41
Opening
42
Opening Example 1
43
Opening Example 2
• Only a compact version of the object remains
44
Opening Example: Real Image
• Most noisy objects are removed
• The object preserves its original size
45
Closing
• The closing of set by the SE is defined as:
●
which is a dilation of by followed by an erosion of the result by .
46
Closing
• The closing is the complement of the union of all translations of B that do not overlap with :
●=⋃ ∩=∅
• Geometric Interpretation: Closing results in an area that we cannot paint using a brush with footprint B, when no part of the brush is allowed to overlap with the region .
• Effect: Smoothing of the boundary from the outside.
47
Duality
• Opening and closing are dual operations.
48
Properties of Opening and Closing
• Opening
• Closing
∘⊆ ∘ ∘=∘
⊆ ● ● ● = ●
• The last properties, in each case, indicate that multiple openings or closings have no effect after the first application of the operator (idempotent).
49
Closing Example 1
• Holes and indentations are filled • The object preserves its size
50
Closing Example 2
51
Closing Example: Real Image
• Most internal holes are filled while the human object preserves its original size
• Note: the small objects in the background have not been deleted
52
Closing Example: Segmentation
• A simple segmentation of foreground object from a grayscale image
1. Threshold
2. Closing with disc of size 20
53
Closing and then Opening
• The closing was performed using 7×7 box- shaped SE
• The opening was performed using a 15×15 box-shaped SE
54
Python Examples: Erosion
• These examples are from the package demo6.zip
55
Python Example: Dilation
56
Python Example: Opening
Opening is for removing noise.
57
Python Example: Closing
Closing is useful for removing holes inside foreground objects.
58
7.2 Connected Components and Labelling
59
Connected Components and Labelling
• Adjacency – 4-adjacent – 8-adjacent
• Twopixelsareconnectedinif there is a path between them consisting entirely of pixels in .
• isa(4-or8-)connected component (blob) if there exists a path between every pair of pixels
• Labellingistheprocessof assigning the same label number to every pixel in a connected component
60
Labelling Example
61
A Fast Labelling Algorithm
• One pass through image to assign temporary labels and record equivalent labels
• Second pass to replace temporary labels with final labels
• Let
– B(r,c) is the input binary image
– L(r,c) is the output image of labels
62
A Fast Labelling Algorithm
Here is the pseudo-code for the algorithm labelling 4- connected components:
NUMLABEL = 1
for r = 1 to MAXROW {
for c=1 to MAXCOL {
if B(r,c) == 0 then
else
L(r,c) = 0; % if pixel not white, assign no label
if B(r-1,c)==0 && B(r,c-1)==0 L(r,c) = NUMLABEL++;
else B(r-1,c)==1 && B(r,c-1)==0 L(r,c) = L(r-1,c)
else B(r,c-1)==1 && B(r,c-1)==0 L(r,c) = L(r,c-1)
else B(r-1,c)==1 && B(r,c-1)==1 L(r,c) = L(r-1,c)
record L(r-1,c) and L(r,c-1) as equivalent labels
63
Example
64
Python Implementation
65
7.3 Morphological Algorithms
66
Hit-Or-Miss Transform
• Amethodtofindthelocationofashape in an image
• DefineanSEwiththesamesizeas, called .
• ⊖ gives all places where fits in
• But fits in any sufficiently large shape.
• Addonemorecriteriontosearchfor: Need the background to match , which contains the boundary of .
• Theintersectioncontainspointsthat match both criteria:
67
Hit-Or-Miss Transform
• ⊖ contains the origin of , but also part of , as is larger than .
• ⊖ contains the origin of , but also part of , as is smaller than .
• Intersection gives only the origin of .
68
Boundary Extraction
• To find the boundary of a set , erode it by a small structuring element .
• Then take the set difference between and its erosion:
=−(⊖)
69
Boundary Extraction Example
• The boundary is one pixel thick due to the 3×3 SE. Other SE would result in thicker boundaries.
70
Region Filling
• Given a pixel inside a boundary, region filling attempts to fill the area surrounded by that boundary with 1s.
71
Region Filling
• Let to be an image containing boundaries.
• Form a set with zeros everywhere, except
at the pixel that is confirmed to be a hole.
• Then do the following two operations iteratively:
– Dilation with , a 3×3 cross-shaped SE. – Intersect with
• Mathematically,
= ⊕ ∩, =1,2,3,⋯
• The algorithm terminates when = .
• ∪ contains all the filled holes and their boundaries.
72
Region Filling Example 1
73
Region Filling Example 2
Original image with Output Image white dots required
to start the region-
filling algorithm
74
Skeletonization
• Skeletonisaconciserepresentationofshape.
• Setofallpointsthatareequallydistantfromtwo closest points of the object boundary
• Equivalently,theunionofallmaximaldiskcenters that are contained in the object
• Analogy:
– Start a fire at the boundary, let it burn inward (by repeated erosions)
– Points where fire is quenched are the skeleton
75
Python Example on Skeletonization
76
7.4 Grayscale Morphology
77
Grayscale Morphology
• Instead of binary images, we now have a grayscale image (, ), where , are integer pixels
• (, ) be the gray-level SE.
• SE can be flat or non-flat, but here we only focus on flat SE.
78
Grayscale Erosion
Theerosionofimagef byaSEbatany location (x,y) is defined as the minimum value of the image in the region coincident with b when the origin of b is at (x,y):
⊖ , min, , ∈
79
Grayscale Erosion in Python
80
Grayscale Dilation
Thedilationofimagef byaSEbatany location (x,y) is defined as the maximum value of the image in the window outlined by b:
⊕ , = max{ −,− } , ∈
• The SE is reflected as in the binary case.
81
Grayscale Dilation in Python
82
Examples on Grayscale Erosion and Dilation
Original image
ErosionbyaflatdiskSE of radius 2:
• Darker background,
• Small bright dots
DilationbyaflatdiskSE of radius 2:
• Lighter background, • Small dark dots
reduced
• Dark features grew.
reduced
• Light features grew.
83
Grayscale Opening and Closing
• The opening of image f by SE b is: ∘= ⊖ ⊕
• The closing of image f by SE b is: ● ⊕ ⊖
84
Opening: Geometric Interpretation
• Consider the domain of (SE centered at Point . Red line below) and all candidate SEs that have centres inside the domain of .
• Push all candidate SEs from underneath of (stop when touching the curve)
• There is a SE that attains maximum (Black line for the example below). That maximum is the result of the opening operation at Point .
• Effect:
– –
Upward peak clipped by opening Opening removes small bright details.
Domain of
The SE that attains maximum when pushed from underneath of
85
Grayscale Opening in Python
86
Closing: Geometric Interpretation
• Similar concept as opening
• But here, push SE from top of and take the minimum.
• Effect:
– Valleys clipped by closing
– Closing highlights small dark regions of the image.
87
Grayscale Closing in Python
88
Examples on Grayscale Opening and Closing
Original image
Opening by a flat disk SE of radius 3:
• Intensities of bright
Closing by a flat disk SE of radius 5:
• Intensities of dark
features decreased
• Effects on background
features increased,
• Effects on background
are negligible (as opposed to erosion).
are negligible (as opposed to dilation).
89
Morphological Smoothing
• Opening suppresses light details smaller than the SE and closing suppresses (makes lighter) dark details smaller than the SE.
• Theyareusedincombinationasmorphological filters to eliminate undesired structures.
Cygnus Loop supernova. We wish to extract the central light region.
90
Example on Morphological Smoothing
Opening followed by closing with disk SE of varying size
Original image
Radius 1
Radius 3
Radius 5
91
Morphological Gradient
• The difference of the dilation and the erosion of an image emphasizes the boundaries between regions.
= ⊕ −(⊖)
• Homogeneous areas are not affected and the subtraction provides a derivative-like effect.
• The net result is an image with flat regions suppressed and edges enhanced.
92
Example on Morphological Gradient
Original image
Dilation
Erosion
Difference
93
Top-hat and Bottom-hat Transformations
• Opening suppresses light details smaller than the SE.
• Closing suppresses dark details smaller than the SE.
• Choosing an appropriate SE eliminates image details where the SE does not fit.
• Subtracting the outputs of opening or closing from the original image provides the removed components.
94
Top-hat and Bottom-hat Transformations
• The top-hat transformation of a grayscale image f is defined as f minus its opening:
=− ∘
• The bottom-hat transformation of a grayscale image f is defined as its closing minus f:
= ● −
95
Top-hat and Bottom-hat Transformations
Because the results look like the top or bottom of a hat these algorithms are called top-hat and bottom-hat transformations
An important application is the correction of nonuniform illumination which is a pre- segmentation step.
96
Example on Top-hat Transformation
Original image
Thresholded image (Otsu’s method)
Opened image (disk SE r=40) Does not fit to grains and eliminates them
Top-hat (image-opening) Reduced nonuniformity
Thresholded top-hat
97
Top-Hat Transformation in Python
98
Bottom-Hat Transformation in Python
99