COMP9517: Computer Vision
Image Segmentation Part 2
Week 5 COMP9517 2021 T1 1
How to improve image segmentation results? Processing using mathematical morphology
How to clean up background noise? How to clean up object noise?
How to separate touching objects? How to close holes in objects?
How to extract object contours? How to compute distances?
…
Binary mathematical morphology (applies to binary images)
Gray-scale mathematical morphology (applies to gray-scale images)
Nonlinear image processing based on set-theory rather than on calculus
Week 5 COMP9517 2021 T1 2
Binary image representations
x
0123456789 0
1 2 3
y4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0
Week 5
COMP9517 2021 T1
3
Binary image
white = foreground black = background
Image as matrix
1 = foreground 0 = background
0010000000
I ={(1,1),(2,1), (7,1),(2,2),
(5, 5), (5, 6), (6, 6), (6, 7), (2,8),(3,8)}
Image as set
0000000000
0000000000 0000010000
0000011000
0000001000 0011000000
0000000000
Basic set operations
NA NB n Givensets A= ai i=1 and B= bi i=1,withai,bi∈,wehave
{} {}
Translation: A = c |c=+a x∈,a A foranygiven x∈n
x{iiii} Reflection: A=−x=|x∈ a,a A
r Complement:A=xi|xi A ∉
{}
c
U n i o n : A ∪ B = x i | x i A ∈x i ∨ B ∈
ii ii
A
Ax
A∪B
{} {}
Intersection: A∩B= xi |xi A ∈xi ∧B ∈ {}
B
A−B
A∩B
A−B={xi|xi A∈xi ∧B}∉
Difference:
Cardinality: |A|=N and |B|=N
AB
Week 5 COMP9517 2021 T1
4
Ac
Dilation of binary images
Definitionofbinarydilation: I⊕S= x|Sx I ∩ ≠∅ {r}
That is, the set of points x∈n for which the intersection of the imageI with the reflected version of a structuring element S translated to x , is not empty
I
I⊕S Added
⊕
S
=
(0,0)
Week 5
COMP9517 2021 T1
5
Erosion of binary images
Definition of binary erosion: I S = x | Sx I ⊆ {}
That is, the set of points x∈n for which the structuring element S translated over x is completely contained in the image I
I
IS Removed
S
=
(0,0)
Week 5
COMP9517 2021 T1
6
Structuring elements
In principle a structuring element can have any shape …
… but the symmetric 3 x 3 structuring element is used most often
Week 5 COMP9517 2021 T1 7
Dimensional decomposition
Decomposition of the basic structuring element
I⊕ =(I⊕ )⊕ I =(I )
Dilation
I⊕ =I⊕
Week 5 COMP9517 2021 T1 8
Erosion
Iterative decomposition
⊕⊕⊕
Applies to dilation and erosion
Opening of binary images
Definitionofbinaryopening: IS=(I S)⊕S
That is, an erosion followed by a dilation using the same structuring element Example using the basic 3 x 3 structuring element:
IISIS
Eliminates details smaller than the structuring element outside the main object
Week 5 COMP9517 2021 T1 9
Closing of binary images
Definition of binary closing: I • S = (I ⊕S ) S
That is, a dilation followed by an erosion using the same structuring element Example using the basic 3 x 3 structuring element:
I I⊕S I•S
Eliminates details smaller than the structuring element inside the main object
Week 5 COMP9517 2021 T1 10
Morphological edge detection
Difference between the dilated and the eroded image
I⊕S I
I S
I⊕S−I S
outer edge + inner edge COMP9517 2021 T1 11
–
Week 5
Binary object outlines
How to get a one-pixel thick outline of all objects in the image?
I I⊕S−I
Week 5 COMP9517 2021 T1 12
Reconstruction of binary objects
How to create an image containing selected objects only?
Create a marker image R0 containing seed pixels from each selected object of image I and then iteratively compute R = R S⊕ I∩until R = R
I Objects of interest
R
i R0
()
i−1 i i−1
Week 5
COMP9517 2021 T1
13
Reconstruction of binary objects
How to remove objects that are only partly in the image?
Take the boundary pixels B of input image I as the seeds, compute the reconstruction R from those seeds, and subtract the result from the input
IBR
–
O
Week 5 COMP9517 2021 T1
14
Reconstruction of binary objects
How to fill all holes in all of the objects in the image?
Take the complement I c of image I , take the boundary pixels of I c as seeds, compute reconstruction R of I c from those seeds, take the complement Rc
I Ic R Rc
Week 5 COMP9517 2021 T1 15
Distance transform of binary images
How to compute the distance of object pixels to the background?
Denote input image I as I0 and iteratively compute Ii = Ii−1 S for i =1,2,… while setting all pixels eroded in iteration i to value i in the output image D
ID
Week 5 COMP9517 2021 T1 16
Ultimate erosion of binary images
How to find representative center points for all the objects?
Compute the distance transform of the image and find all the local maxima This is the same as keeping only the last object pixels before final erosion
IDM
Week 5 COMP9517 2021 T1 17
Ultimate erosion and reconstruction
How to separate objects that are touching each other?
Perform ultimate erosion and then perform a reconstruction of the result with the additional constraint that objects may not merge
IDMR
Since elongated objects may result in multiple local maxima this approach works best for objects that are more or less circular
Week 5 COMP9517 2021 T1 18
Ultimate dilation of binary images
How to find the background points equidistant to the objects?
Iteratively dilate the image while imposing the non-merging constraint The result is called the Voronoi (or Dirichlet) tessellation of the objects
IV
Week 5 COMP9517 2021 T1 19
Ultimate dilation of binary images
How to find the background points equidistant to the objects?
Iteratively dilate the image while imposing the non-merging constraint The result is called the Voronoi (or Dirichlet) tessellation of the objects
IV
Week 5 COMP9517 2021 T1 20
Skeletonization of binary images
How to find a representative centerline of the objects?
Iteratively apply conditional erosion (thinning) that does not break the connectivity of the result and does not remove single pixels or end-pixels
The resulting one-pixel thick structure is called the skeleton of the object
Week 5 COMP9517 2021 T1 21
Binary morphology of nD images
The presented concepts extend to any dimensionality
Example of a 3D binary image
Volumetric pixels (“voxels”)
3 x 3 x 3 voxel structuring element
3D dilation 3D opening 3D erosion 3D closing And all algorithms based on it
Week 5
COMP9517 2021 T1
22
Gray-scale mathematical morphology
Consider nD gray-scale images as (n+1)D binary images…
U
U−1
2D gray-scale image I
3D binary image U(I)
The landscape surface with the volume below is called the umbra of the image
Week 5 COMP9517 2021 T1 23
Dilation of gray-scale images
Definition of gray-scale dilation: I ⊕ S =U U(I) U(S) ⊕ −1[ ]
That is, the binary dilation of the umbra U(I) of gray-scale image I with the umbra U(S) of gray-scale structuring element S, turned back into gray-scale
Example in 1D
I
(0,0)
S
U(I)
Added
⊕
U(S)
I⊕S
Any gray-scale S is possible but the flat one (as shown here) is used most often
Week 5 COMP9517 2021 T1 24
Dilation of gray-scale images
Equivalent definition: I ⊕ S (x) = maxp I(x p) S(−p)
(){}
+
For a flat and symmetrical structuring element this is simply local max-filtering
ISI⊕S 7 x 7 pixels
⊕
Week 5 COMP9517 2021 T1 25
Erosion of gray-scale images
Definition of gray-scale erosion: I S =U U(I) U(S) −1[ ]
That is, the binary erosion of the umbra U ( I ) of gray-scale image I with the umbra U(S) of gray-scale structuring element S, turned back into gray-scale
Example in 1D
I
(0,0)
S
U(I)
Removed
IS
U(S)
Any gray-scale S is possible but the flat one (as shown here) is used most often
Week 5 COMP9517 2021 T1 26
Erosion of gray-scale images
Equivalent definition: I S (x) = minp I (x p) S+(p)
(){}
−
For a flat and symmetrical structuring element this is simply local min-filtering
ISIS 7 x 7 pixels
Week 5 COMP9517 2021 T1 27
Opening of gray-scale images
Definitionofgray-scaleopening: IS=(I S)⊕S
Gray-scale erosion and then gray-scale dilation with same structuring element
ISIS 3 x 3 pixels
Week 5 COMP9517 2021 T1 28
Closing of gray-scale images
Definition of gray-scale closing: I • S = (I ⊕S ) S
Gray-scale dilation and then gray-scale erosion with same structuring element
ISI•S 3 x 3 pixels
•
Week 5 COMP9517 2021 T1 29
Morphological smoothing of gray-scale images
Suppressing image structures of specific size (and shape)
High-valued (bright) image structures are removed by gray-scale opening Low-valued (dark) image structures are removed by gray-scale closing
I I S (radius = 7 pixels) I S (radius = 25 pixels)
Behold the power of nonlinear filtering (not possible with linear filtering)
Week 5 COMP9517 2021 T1 30
Morphological gradient of gray-scale images Difference between the dilated and the eroded image
D = I ⊕S I
G=D E− –
Week5
E=I S COMP95172021T1 31
Morphological gradient of gray-scale images
Outer gradient and inner gradient
32
D D−I
I
Week 5
COMP9517 2021 T1 E I − E
Morphological gradient of gray-scale images
Sum of outer gradient and inner gradient
D−I
+
Week 5
I − E COMP9517 2021 T1 33
Morphological Laplacean of gray-scale images
Difference between outer gradient and inner gradient
D−I
L = D +E −2I
–
EID
GL
0
Week 5
I − E
COMP9517 2021 T1
34
Top-hat filtering of gray-scale images
I
⊕S
(Radius 10 pixels)
S
Closing
O
Week 5
COMP9517 2021 T1
35
̶̶̶
Top-hat filtering of gray-scale images
Notice that the profiles are 1D but the filtering was performed in 2D
36
I ⊕S S
Week 5 COMP9517 2021 T1 Position along scan line
Image intensity
Top-hat filtering of gray-scale images
37
I O+255
Week 5 COMP9517 2021 T1 Position along scan line
Image intensity
Summary of mathematical morphology
Powerful toolbox of methods around image segmentation
Gray-scale morphology for pre-processing Removal of gray-scale noise
Removal of background shading
Removal of unwanted image structures
Binary morphology for post-processing
Closing holes in objects and background
Finding the inner or outer outline of objects Detecting and separating touching objects Extracting representative shapes of objects Computing distances within and between objects
Before segmentation
Week 5 COMP9517 2021 T1
38
After segmentation