Chapter 5 Mathematical Morphology

5.1 Introduction
mathematical morphology works on shape
shape: prime carrier of information in machine vision
morphological operations: simplify image data,
preserve essential shape characteristics, eliminate irrelevancies
shape: correlates directly with decomposition of objects, object features,
object surface defects, assembly defects




5.2 Binary Morphology
set theory: language of binary mathematical morphology
sets in mathematical morphology: represent shapes
Euclidean $N$-space: $E^N$
discrete Euclidean $N$-space: $Z^N$
$N=2$: hexagonal grid, square grid




dilation, erosion: primary morphological operations
opening, closing: composed from dilation, erosion
opening, closing: related to shape representation, decomposition, primitive
extraction




5.2.1 Binary Dilation
dilation: combines two sets by vector addition of set elements
dilation of $A$ by $B$: $A \oplus B$

\begin{displaymath}
A \oplus B = \{ c \in E^N \vert c = a+b {\rm\ for \ some \ } a \in A
{\rm\ and \ } b \in B\}
\end{displaymath}

addition commutative $b$ dilation commutative: $A\oplus B=B \oplus A$
binary dilation: Minkowski addition
=====Fig. 5.1=====
$A$: referred as set, image
$B$: structuring element: kernel




dilation by disk: isotropic swelling or expansion
=====Fig. 5.2=====
dilation by kernel without origin: might not have common pixels with $A$
translation of dilation: always can contain $A$
=====lena.bin.128=====
=====lena.bin.dil=====




$J=I \cap (I \oplus N_4)$ for noise removal
$N_4$: set of four 4-neighbors of (0,0) but not (0,0)
4-isolated pixels removed
only points in $I$ with at least one of its 4-neighbors remain




$A_t$: translation of $A$ by the point $t$

\begin{displaymath}
A_t = \{ c \in E^N \vert c=a+t {\rm\ for \ some \ } a \in A \}
\end{displaymath}

dilation: union of translates of kernel

\begin{displaymath}
A \oplus B = \cup_{a \in A} B_a = \cup_{b \in B} A_b
\end{displaymath}




addition associative $b$ dilation associative

\begin{displaymath}
(A \oplus B) \oplus C = A \oplus (B \oplus C)
\end{displaymath}

associativity of dilation: chain rule: iterative rule




dilation of translated kernel: translation of dilation

\begin{displaymath}
A \oplus B_t = (A \oplus B)_t
\end{displaymath}

dilation distributes over union

\begin{displaymath}
(B \cup C) \oplus A = (B \oplus A) \cup (C \oplus A)
\end{displaymath}




dilating by union of two sets: the union of the dilation

\begin{displaymath}
A \oplus (B \cup C) = (A \oplus B) \cup (A \oplus C)
\end{displaymath}

dilating $A$ by kernel with origin guaranteed to contain $A$
extensive: operators whose output contains input
dilation extensive when kernel contains origin




dilation preserves order

\begin{displaymath}
A \subseteq B \Longrightarrow A \oplus K \subseteq B \oplus K
\end{displaymath}

increasing: preserves order
=====Reader's Digest, Oct. 1994, p. 73=====




5.2.2 Binary Erosion
erosion: morphological dual of dilation
erosion of $A$ by $B$: set of all \begin{displaymath}
A \otimes (J,K) = (A \ominus J) \cap (A^c \ominus K)
\end{displaymath} s.t. $x+b \in A$ for every $b \in B$

\begin{displaymath}
A \ominus B = \{ x \in E^N \vert x+b \in A {\rm\ for \ every \ } b \in B \}
\end{displaymath}

erosion: shrink: reduce
=====Fig. 5.3=====
=====lena.bin.ero=====
erosion of $A$ by $B$: set of all \begin{displaymath}
A \otimes (J,K) = (A \ominus J) \cap (A^c \ominus K)
\end{displaymath} for which $B$ translated to \begin{displaymath}
A \otimes (J,K) = (A \ominus J) \cap (A^c \ominus K)
\end{displaymath} contained in $A$

\begin{displaymath}
A \ominus B = \{ x \in E^N \vert B_x \subseteq A \}
\end{displaymath}

if $B$ translated to \begin{displaymath}
A \otimes (J,K) = (A \ominus J) \cap (A^c \ominus K)
\end{displaymath} contained in $A$, then \begin{displaymath}
A \otimes (J,K) = (A \ominus J) \cap (A^c \ominus K)
\end{displaymath} in $A \ominus B$




erosion: difference of elements $a$ and $b$

\begin{displaymath}
A \ominus B = \{ x \in E^N \vert {\rm\ for \ every \ } b \in...
... \
exists \ an \ } a \in A {\rm\ such \ that \ } x = a - b \}
\end{displaymath}




dilation: union of translates
erosion: intersection of negative translates

\begin{displaymath}
A \ominus B = \cap_{b \in B} A_{-b}
\end{displaymath}

=====Fig. 5.4=====
Minkowski subtraction: close relative to erosion
Minkowski subtraction: $\cap_{b \in B} A_b$




erosion: shrinking of the original image
antiextensive: operated set contained in the original set
erosion antiextensive: if origin contained in kernel
if $0 \in B$ then $A \ominus B \subseteq A$ because:
if $x \in A \ominus B$ then $x+b \in A$ for every $b \in B$, since $0 \in B$ thus $x=x+0 \in A$




eroding $A$ by kernel without origin can have nothing in common with $A$
=====Fig. 5.5=====




possible: $A \ominus B \subseteq A$ and $0 \not\in B$
e.g. $A=\{1,2,3,4\}, B=\{-1, 1\}$, then $A \ominus B = \{2, 3\} \subseteq A$, yet $0 \not\in B$




dilating translated set results in a translated dilation

\begin{displaymath}
A_t \oplus B = (A \oplus B)_t
\end{displaymath}

eroding by translated kernel results in negatively translated erosion

\begin{displaymath}
A \ominus B_t = (A \ominus B)_{-t}
\end{displaymath}

dilation, erosion: increasing

\begin{displaymath}
A \subseteq B \Longrightarrow A \ominus K \subseteq B \ominus K
\end{displaymath}

eroding by larger kernel produces smaller result

\begin{displaymath}
K \subseteq L \Longrightarrow A \ominus L \subseteq A \ominus K
\end{displaymath}




dilation, erosion similar that one does to foreground, the other to background
similarity: duality
dual: negation of one equals to the other on negated variables
DeMorgan's law: duality between set union and intersection

\begin{displaymath}
(A \cup B)^c = A^c \cap B^c
\end{displaymath}

negation of a set: complement

\begin{displaymath}
A^c = \{ x \in E^n \vert x \not\in A \}
\end{displaymath}




negation of a set in two possible ways in morphology




$\check{B}$: reflection about the origin of $B \subseteq E^N$

\begin{displaymath}
\check{B} = \{ x \vert {\rm for \ some \ } b \in B, x = -b \}
\end{displaymath}

$\check{B}$: symmetrical set of $B$ with respect to origin [Matheron 1975]
$\check{B}$: $B$ transpose [Serra 1982]




complement of erosion: dilation of the complement by reflection
Theorem 5.1: Erosion Dilation Duality

\begin{displaymath}
(A \ominus B)^c = A^c \oplus \check{B}
\end{displaymath}

=====Fig. 5.6=====
Corollary 5.1:

\begin{displaymath}
(A \oplus B)^c = A^c \ominus \check{B}
\end{displaymath}




erosion of intersection of two sets: intersection of erosions

\begin{displaymath}
(A \cap B) \ominus K = (A \ominus K) \cap (B \ominus K)
\end{displaymath}

=====Fig. 5.7=====
erosion of a kernel of union of two sets: intersection of erosions

\begin{displaymath}
A \ominus (K \cup L) = (A \ominus K) \cap (A \ominus L)
\end{displaymath}

erosion of kernel of intersection of two sets: contains union of erosions

\begin{displaymath}
A \ominus (B \cap C) \supseteq (A \ominus B) \cup (A \ominus C)
\end{displaymath}

no stronger
=====Fig. 5.8=====




chain rule for erosion holds when kernel decomposable through dilation

\begin{displaymath}
A \ominus (B \oplus C) = (A \ominus B) \ominus C
\end{displaymath}

duality does not imply cancellation on morphological equalities

\begin{displaymath}
(B \ominus C) \oplus C \neq B
\end{displaymath}

containment relationship holds

\begin{displaymath}
A \subseteq B \ominus C {\rm\ if \ and \ only \ if \ } B \supseteq A \oplus C
\end{displaymath}




genus $g(I)$: number of connected components minus number of holes of $I$
4-connected for object, 8-connected for background

\begin{displaymath}
g_4(I) = \char93 I - \char93 I \ominus V - \char93 I \ominus H + \char93 I \ominus B
\end{displaymath}

8-connected for object, 4-connected for background

\begin{displaymath}
g_8(I) = \char93 I - \char93 I \ominus V - \char93  I \ominu...
... \ominus C_1 + \char93  I \ominus C_2 + \char93  I \ominus C_3
\end{displaymath}


\begin{displaymath}
+ \char93  I \ominus C_4 - \char93  I \ominus B
\end{displaymath}

=====Fig. 5.9=====




5.2.3 Hit-and-Miss Transform
hit-and-miss: selects corner points, isolated points, border points
hit-and-miss: performs template matching, thinning, thickening, centering
hit-and-miss: intersection of erosions
$J, K$ kernels satisfy $J \cap K = \emptyset $
hit-and-miss of set $A$ by $(J, K)$

\begin{displaymath}
A \otimes (J,K) = (A \ominus J) \cap (A^c \ominus K)
\end{displaymath}

hit-and-miss: to find upper right-hand corner
=====Fig. 5.11=====
$J$ locates all pixels with south, west neighbors part of $A$
\begin{displaymath}
A_t = \{ c \in E^N \vert c=a+t {\rm\ for \ some \ } a \in A \}
\end{displaymath} locates all pixels of $A^c$ with south, west neighbors in $A^c$
$J$ and \begin{displaymath}
A_t = \{ c \in E^N \vert c=a+t {\rm\ for \ some \ } a \in A \}
\end{displaymath} displaced from one another




hit-and-miss: locate particular spatial patterns
$J=\{(0,0)\}, K=\{(0,1), (0, -1), (1,0), (-1,0) \}$ then $I \otimes (J,K)$: set of all 4-isolated pixels
hit-and-miss: to compute genus of a binary image

\begin{displaymath}
g_4(I) = \char93  I \otimes (J_1,K_1) + \char93  I \otimes (J_2,K_2) - \char93  I \otimes(J_3,K_3)
\end{displaymath}


\begin{displaymath}
g_8(I) = \char93  I \otimes (J_1,K_1) - \char93  I \otimes (J_4,K_4)
\end{displaymath}

=====Fig. 5.10=====




hit-and-miss: thickening and thinning
hit-and-miss: counting
hit-and-miss: template matching




5.2.4 Dilation and Erosion Summary
=====dilation and erosion summary, p. 173=====
=====Garfield 17:5=====




5.2.5 Opening and Closing
dilation and erosions: usually employed in pairs
$B \mbox{\Large$\circ$}K$: opening of image $B$ by kernel \begin{displaymath}
A_t = \{ c \in E^N \vert c=a+t {\rm\ for \ some \ } a \in A \}
\end{displaymath}

\begin{displaymath}
B \mbox{\Large$\circ$}K = (B \ominus K) \oplus K
\end{displaymath}

$B \mbox{\Large$\bullet$}K$: closing of image $B$ by kernel \begin{displaymath}
A_t = \{ c \in E^N \vert c=a+t {\rm\ for \ some \ } a \in A \}
\end{displaymath}

\begin{displaymath}
B \mbox{\Large$\bullet$}K = (B \oplus K) \ominus K
\end{displaymath}

$B$ open under \begin{displaymath}
A_t = \{ c \in E^N \vert c=a+t {\rm\ for \ some \ } a \in A \}
\end{displaymath}: $B$ open w.r.t. \begin{displaymath}
A_t = \{ c \in E^N \vert c=a+t {\rm\ for \ some \ } a \in A \}
\end{displaymath}: $B=B \mbox{\Large$\circ$}K$
$B$ closed under \begin{displaymath}
A_t = \{ c \in E^N \vert c=a+t {\rm\ for \ some \ } a \in A \}
\end{displaymath}: $B$ closed w.r.t. \begin{displaymath}
A_t = \{ c \in E^N \vert c=a+t {\rm\ for \ some \ } a \in A \}
\end{displaymath}: $B=B \mbox{\Large$\bullet$}K$
morphological opening, closing: no relation to topologically open, closed sets




opening characterization theorem

\begin{displaymath}
A \mbox{\Large$\circ$}K = \{ x \in A \vert {\rm for \ some \ } t \in A \ominus K, x \in K_t
{\rm\ and \ } K_t \subseteq A \}
\end{displaymath}

$A \mbox{\Large$\circ$}K$: selects points covered by some translation of \begin{displaymath}
A_t = \{ c \in E^N \vert c=a+t {\rm\ for \ some \ } a \in A \}
\end{displaymath}, entirely contained in $A$
=====lena.bin.open=====
opening with disk kernel: smoothes contours, breaks narrow isthmuses
opening with disk kernel: eliminates small islands, sharp peaks, capes
=====lena.bin.close=====
closing by disk kernel: smoothes contours, fuses narrow breaks, long, thin gulfs
closing with disk kernel: eliminates small holes, fill gaps on the contours




unlike erosion and dilation: opening invariant to kernel translation

\begin{displaymath}
A \mbox{\Large$\circ$}K = A \mbox{\Large$\circ$}K_x
\end{displaymath}

opening antiextensive

\begin{displaymath}
A \mbox{\Large$\circ$}K \subseteq A
\end{displaymath}

like erosion and dilation: opening increasing

\begin{displaymath}
A \subseteq B \Longrightarrow A \mbox{\Large$\circ$}K \subseteq B \mbox{\Large$\circ$}K
\end{displaymath}




$A \mbox{\Large$\circ$}K$: those pixels covered by sweeping kernel all over inside of $A$

\begin{displaymath}
A \mbox{\Large$\circ$}K = \bigcup_{y \in A \ominus K} K_y = \bigcup_{K_y \subseteq A} K_y
\end{displaymath}

$F$: shape with body and handle
$L$: small disk structuring element with radius just larger than handle width
extraction of the body and handle by opening and taking the residue
=====Fig. 5.16=====
extraction of trunk and arms with vertical and horizontal kernels
=====Fig. 5.17=====
extraction of base, trunk, horizontal and vertical areas
=====Fig. 5.18=====
noisy background line segment removal
=====Fig. 5.19=====
decomposition into parts
=====Fig. 5.20==========Fig. 5.21=====




closing: dual of opening

\begin{displaymath}
A \mbox{\Large$\bullet$}K = \{ x \vert x \in \check{K}_t {\rm\ implies \ } \check{K}_t \cap A \neq \emptyset \}
\end{displaymath}

like opening: closing invariant to kernel translation

\begin{displaymath}
A \mbox{\Large$\bullet$}K_x = A \mbox{\Large$\bullet$}K
\end{displaymath}

closing extensive

\begin{displaymath}
A \subseteq A \mbox{\Large$\bullet$}K
\end{displaymath}

like dilation, erosion, opening: closing increasing

\begin{displaymath}
A \subseteq B \Longrightarrow A \mbox{\Large$\bullet$}K \subseteq B \mbox{\Large$\bullet$}K
\end{displaymath}




opening idempotent

\begin{displaymath}
(A \mbox{\Large$\circ$}K) \mbox{\Large$\circ$}K = A \mbox{\Large$\circ$}K
\end{displaymath}

closing idempotent

\begin{displaymath}
(A \mbox{\Large$\bullet$}K) \mbox{\Large$\bullet$}K = A \mbox{\Large$\bullet$}K
\end{displaymath}




if $L \subseteq K$ not necessarily follows that $A \mbox{\Large$\circ$}L \supseteq A\mbox{\Large$\circ$}K$
=====Fig. 5.22=====




closing may be used to detect spatial clusters of points
=====Fig. 5.23=====




5.2.6 Morphological Shape Feature Extraction
morphological pattern spectrum: shape-size histogram [Maragos 1987]

\begin{displaymath}
S(A; K)(m) = \char93  A \mbox{\Large$\circ$}K(m-1) - \char93  A \mbox{\Large$\circ$}K(m), \ \ \ m \geq 1
\end{displaymath}


\begin{displaymath}
S(A; K)(-m) = \char93  A \mbox{\Large$\bullet$}K(m+1) - \char93  A \mbox{\Large$\bullet$}K(m), \ \ \ m \geq 0
\end{displaymath}




5.2.7 Fast Dilations and Erosions
decompose kernels to make dilations and erosions fast




5.3 Connectivity
morphology and connectivity: close relation




5.3.1 Separation Relation
$\cap_{b \in B} A_b$ separation if and only if $\cap_{b \in B} A_b$ symmetric, exclusive, hereditary, extensive




5.3.2 Morphological Noise Cleaning and Connectivity
images perturbed by noise can be morphologically filtered to remove some noise




5.3.3 Openings, Holes, and Connectivity
opening can create holes in a connected set that is being opened
=====Fig. 5.25=====




5.3.4 Conditional Dilation
select connected components of image that have nonempty erosion
conditional dilation $J \oplus \vert _I D $, defined iteratively $J_0 = J$
$J$ are points in the regions we want to select

\begin{displaymath}
J_n = (J_{n-1} \oplus D) \cap I
\end{displaymath}

conditional dilation $J \oplus \vert _I D = J_m$ where $m$ is the smallest index $J_m = J_{m-1}$
=====Fig. 5.26=====




5.4 Generalized Openings and Closings
generalized opening: any increasing, antiextensive, idempotent operation
generalized closing: any increasing, extensive, idempotent operation
=====Oldie 33:18=====




5.5 Gray Scale Morphology
binary dilation, erosion, opening, closing naturally extended to gray scale
extension: uses min or max operation
gray scale dilation: surface of dilation of umbra
gray scale dilation: maximum and a set of addition operations
gray scale erosion: minimum and a set of subtraction operations




5.5.1 Gray Scale Dilation and Erosion
top: top surface of $A$: denoted by $T[A]: F \rightarrow E$:

\begin{displaymath}
T[A](x) = \max \{ y \vert (x, y) \in A \}
\end{displaymath}

umbra of $A \ominus B = \{2, 3\} \subseteq A$: denoted by $U[f], U[f] \subseteq F \times E$

\begin{displaymath}
U[f] = \{ (x, y) \in F \times E \vert y \leq f(x) \}
\end{displaymath}

=====Fig. 5.28=====
gray scale dilation: surface of dilation of umbras
dilation of $A \ominus B = \{2, 3\} \subseteq A$ by \begin{displaymath}
A \subseteq B \Longrightarrow A \ominus K \subseteq B \ominus K
\end{displaymath}: denoted by $f \oplus k$

\begin{displaymath}
f \oplus k = T \{ U[f] \oplus U[k] \}
\end{displaymath}

=====Fig. 5.29=====
=====Fig. 5.30=====




$ f: F \rightarrow E$ and $k: K \rightarrow E$, then $f \oplus k: F \oplus K
\rightarrow E$

\begin{displaymath}
(f \oplus k)(x) = \max \{ f(x-z)+k(z) \vert z \in K, x-z \in F \}
\end{displaymath}

=====Fig. 5.31=====
=====lena.im=====
=====lena.im.dil=====




gray scale erosion: surface of binary erosions of one umbra by the other umbra

\begin{displaymath}
f \ominus k = T \{ U[f] \ominus U[k] \}
\end{displaymath}

=====Fig. 5.32=====




$ f: F \rightarrow E$ and $k: K \rightarrow E$, then $f \ominus k: F \ominus K
\rightarrow E$

\begin{displaymath}
(f \ominus k)(x) = \min_{z \in K} \{ f(x+z)-k(z) \}
\end{displaymath}

=====Fig. 5.33=====
=====lena.im.ero=====
=====Fig. 5.34=====




5.5.2 Umbra Homomorphism Theorems
surface and umbra operations: inverses of each other, in a certain sense
surface operation: left inverse of umbra operation

\begin{displaymath}
T \{ U[f] \} = f
\end{displaymath}

Proposition 5.1

\begin{displaymath}
f \oplus k = k \oplus f
\end{displaymath}

Proposition 5.2

\begin{displaymath}
k_1 \oplus (k_2 \oplus k_3) = (k_1 \oplus k_2) \oplus k_3
\end{displaymath}

Proposition 5.3

\begin{displaymath}
(f \ominus k_1) \ominus k_2 = f \ominus (k_1 \oplus k_2)
\end{displaymath}




5.5.3 Gray Scale Opening and Closing
gray scale opening of $A \ominus B = \{2, 3\} \subseteq A$ by kernel \begin{displaymath}
A \subseteq B \Longrightarrow A \ominus K \subseteq B \ominus K
\end{displaymath}: denoted by $f \mbox{\Large$\circ$}k$

\begin{displaymath}
f \mbox{\Large$\circ$}k = (f \ominus k) \oplus k
\end{displaymath}

=====lena.im.open=====




gray scale closing of $A \ominus B = \{2, 3\} \subseteq A$ by kernel \begin{displaymath}
A \subseteq B \Longrightarrow A \ominus K \subseteq B \ominus K
\end{displaymath}: denoted by $f \mbox{\Large$\bullet$}k$

\begin{displaymath}
f \mbox{\Large$\bullet$}k = (f \oplus k) \ominus k
\end{displaymath}

=====lena.im.close=====




duality of gray scale dilation, erosion $\Longrightarrow$ duality of opening, closing

\begin{displaymath}
-(f \mbox{\Large$\circ$}k)(x) = [(-f) \mbox{\Large$\bullet$}\check{k}](x)
\end{displaymath}

=====Fig. 5.37=====




5.6 Openings, Closings, and Medians
median filter: most common nonlinear noise-smoothing filter
median filter: for each pixel, the new value is the median of a window
median filter: robust to outlier pixel values, leaves edges sharp
median root images: images remain unchanged after median filter




5.7 Bounding Second Derivatives
opening or closing a gray scale image: simplifies the image complexity




5.8 Distance Transform and Recursive Morphology
Fig. 5.39 (b) fire burns from outside but burns only downward and right-ward
=====Fig. 5.39=====




5.9 Generalized Distance Transform




5.10 Medial Axis
medial axis transform: medial axis with distance function




5.10.1 Medial Axis and Morphological Skeleton
morphological skeleton of a set $A$ by kernel \begin{displaymath}
A_t = \{ c \in E^N \vert c=a+t {\rm\ for \ some \ } a \in A \}
\end{displaymath}, where $A \ominus_0 K = A$

\begin{displaymath}
S_0, ..., S_N, {\rm\ where \ } S_n = A \ominus_n K - (A \ominus_n K) \mbox{\Large$\circ$}K
\end{displaymath}

skeleton of $A$ given by $ \bigcup_{n=0}^N S_n$
=====Fig. 5.40=====
=====Fig. 5.41=====




5.11 Morphological Sampling Theorem




5.11.1 Set-Bounding Relationships




5.11.2 Examples




5.11.3 Distance Relationships
=====Garfield 17:7=====




5.12 Summary
morphological operations: shape extraction, noise cleaning, thickening
morphological operations: thinning, skeletonizing




Project due Nov. 6
Write programs which do binary morphological dilation, erosion, opening, closing, and hit-and-miss transform on a binary image.




Project due Nov. 13
Write programs which do gray scale morphological dilation, erosion, opening, and closing on a gray scale image.



2001-09-19
Counter:

FastCounter by bCentral