\documentstyle[12pt]{article}
\setlength{\textwidth}{9.75 in}
\setlength{\evensidemargin}{-0.4 in}
\setlength{\oddsidemargin}{-0.4  in}
\setlength{\textheight}{7.2 in}
\setlength{\topmargin}{-1.05 in}
\setlength{\arraycolsep}{9pt}
\renewcommand{\baselinestretch}{1.0}
\newcommand{\psfuh}    {/u/vision/fuh/document/}
\newcommand{\open}{\mbox{\Large $\circ$}}
\newcommand{\close}{\mbox{\Large $\bullet$}}
% \input{psfig}
\newcommand{\epsfig}[1]{\psfig{#1}}
\begin{document}
\bibliographystyle{plain}

\Huge
\begin{center}
Chapter 5 Mathematical Morphology
\end{center}

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

\vspace{1cm}
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

\vspace{1cm}
\noindent
dilation, erosion: primary morphological operations \\
opening, closing: composed from dilation, erosion  \\
opening, closing: related to shape representation, decomposition, primitive \\
\hspace*{1cm}     extraction

\vspace{1cm}
5.2.1 Binary Dilation \\
dilation: combines two sets by vector addition of set elements \\
dilation of $A$ by $B$: $A \oplus B$
\[
A \oplus B = \{ c \in E^N | c = a+b {\rm \ for \ some \ } a \in A 
     {\rm \ and \ } b \in B\}
\]
addition commutative $\rightarrow$ dilation commutative: $A\oplus B=B \oplus A$\\
binary dilation: Minkowski addition \\
=====Fig. 5.1===== \\
$A$: referred as set, image \\
$B$: structuring element: kernel 

\vspace{1cm}
\noindent
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===== 

\vspace{1cm}
\noindent
$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 

\vspace{1cm}
\noindent
$A_t$: translation of $A$ by the point $t$
\[
A_t = \{ c \in E^N | c=a+t {\rm \ for \ some \ } a \in A \}
\]
dilation: union of translates of kernel
\[
A \oplus B = \cup_{a \in A} B_a = \cup_{b \in B} A_b
\]

\vspace{1cm}
\noindent
addition associative $\rightarrow$ dilation associative
\[
(A \oplus B) \oplus C = A \oplus (B \oplus C)
\]
associativity of dilation: chain rule: iterative rule


\vspace{1cm}
\noindent
dilation of translated kernel: translation of dilation 
\[
A \oplus B_t = (A \oplus B)_t
\]
dilation distributes over union
\[
(B \cup C) \oplus A = (B \oplus A) \cup (C \oplus A)
\]

\vspace{1cm}
\noindent
dilating by union of two sets: the union of the dilation
\[
A \oplus (B \cup C) = (A \oplus B) \cup (A \oplus C)
\]
dilating $A$ by kernel with origin guaranteed to contain $A$ \\
extensive: operators whose output contains input \\
dilation extensive when kernel contains origin 

\vspace{1cm}
\noindent
dilation preserves order
\[
A \subseteq B \Longrightarrow A \oplus K \subseteq B \oplus K
\]
increasing: preserves order \\
====={\em Reader's Digest,} Oct. 1994, p. 73=====

\vspace{1cm}
5.2.2 Binary Erosion \\
erosion: morphological dual of dilation \\
erosion of $A$ by $B$: set of all $x$ s.t. $x+b \in A$ for every $b \in B$
\[
A \ominus B = \{ x \in E^N | x+b \in A {\rm \ for \ every \ } b \in B \}
\]
erosion: shrink: reduce \\
=====Fig. 5.3===== \\
=====lena.bin.ero===== \\
erosion of $A$ by $B$: set of all $x$ for which $B$ translated to $x$ contained 
    in $A$ 
\[
A \ominus B = \{ x \in E^N | B_x \subseteq A \}
\]
if $B$ translated to $x$ contained in $A$, then $x$ in $A \ominus B$

\vspace{1cm}
\noindent
erosion: difference of elements $a$ and $b$
\[
A \ominus B = \{ x \in E^N | {\rm \ for \ every \ } b \in B, {\rm \ there \
   exists \ an \ } a \in A {\rm \ such \ that \ } x = a - b \}
\]

\vspace{1cm}
\noindent
dilation: union of translates \\
erosion: intersection of negative translates 
\[
A \ominus B = \cap_{b \in B} A_{-b}
\]
=====Fig. 5.4===== \\
Minkowski subtraction: close relative to erosion \\
Minkowski subtraction: $\cap_{b \in B} A_b$ 

\vspace{1cm}
\noindent
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$ 

\vspace{1cm}
\noindent
eroding $A$ by kernel without origin can have nothing in common with $A$ \\
=====Fig. 5.5===== 

\vspace{1cm}
\noindent
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$

\vspace{1cm}
\noindent
dilating translated set results in a translated dilation 
\[
A_t \oplus B = (A \oplus B)_t
\]
eroding by translated kernel results in negatively translated erosion 
\[
A \ominus B_t = (A \ominus B)_{-t}
\]
dilation, erosion: increasing
\[
A \subseteq B \Longrightarrow A \ominus K \subseteq B \ominus K
\]
eroding by larger kernel produces smaller result 
\[
K \subseteq L \Longrightarrow A \ominus L \subseteq A \ominus K
\]

\vspace{1cm}
\noindent
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
\[
(A \cup B)^c = A^c \cap B^c
\]
negation of a set: complement
\[
A^c = \{ x \in E^n | x \not\in A \}
\]

\vspace{1cm}
\noindent
negation of a set in two possible ways in morphology
\begin{itemize}
\item logical sense: set complement
\item geometric sense: reflection: reversing of set orientation
\end{itemize}

\vspace{1cm}
\noindent
$\check{B}$: reflection about the origin of $B \subseteq E^N$
\[
\check{B} = \{ x | {\rm for \ some \ } b \in B, x = -b \}
\]
$\check{B}$: symmetrical set of $B$ with respect to origin [Matheron 1975] \\
$\check{B}$: $B$ transpose [Serra 1982]

\vspace{1cm}
\noindent
complement of erosion: dilation of the complement by reflection \\
Theorem 5.1: Erosion Dilation Duality
\[
(A \ominus B)^c = A^c \oplus \check{B}
\]
=====Fig. 5.6===== \\
Corollary 5.1: 
\[
(A \oplus B)^c = A^c \ominus \check{B}
\]

\vspace{1cm}
\noindent
erosion of intersection of two sets: intersection of erosions 
\[
(A \cap B) \ominus K = (A \ominus K) \cap (B \ominus K)
\]
=====Fig. 5.7===== \\
erosion of a kernel of union of two sets: intersection of erosions 
\[
A \ominus (K \cup L) = (A \ominus K) \cap (A \ominus L)
\]
erosion of kernel of intersection of two sets: contains union of erosions 
\[
A \ominus (B \cap C) \supseteq (A \ominus B) \cup (A \ominus C)
\]
no stronger \\
=====Fig. 5.8=====

\vspace{1cm}
\noindent
chain rule for erosion holds when kernel decomposable through dilation 
\[
A \ominus (B \oplus C) = (A \ominus B) \ominus C
\]
duality does not imply cancellation on morphological equalities
\[
(B \ominus C) \oplus C \neq B
\]
containment relationship holds
\[
A \subseteq B \ominus C {\rm \ if \ and \ only \ if \ } B \supseteq A \oplus C
\]

\vspace{1cm}
\noindent
genus $g(I)$: number of connected components minus number of holes of $I$ \\
4-connected for object, 8-connected for background
\[
g_4(I) = \#I - \#I \ominus V - \#I \ominus H + \#I \ominus B
\]
8-connected for object, 4-connected for background
\[
g_8(I) = \#I - \#I \ominus V - \# I \ominus H - \# I \ominus D_1 
   - \# I \ominus D_2 + \# I \ominus C_1 + \# I \ominus C_2 + \# I \ominus C_3
\]
\[
   + \# I \ominus C_4 - \# I \ominus B
\]
=====Fig. 5.9===== 

\vspace{1cm}
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)$ 
\[
A \otimes (J,K) = (A \ominus J) \cap (A^c \ominus K)
\]
hit-and-miss: to find upper right-hand corner \\
=====Fig. 5.11===== \\
$J$ locates all pixels with south, west neighbors part of $A$ \\
$K$ locates all pixels of $A^c$ with south, west neighbors in $A^c$ \\
$J$ and $K$ displaced from one another

\vspace{1cm}
\noindent
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 
\[
g_4(I) = \# I \otimes (J_1,K_1) + \# I \otimes (J_2,K_2) - \# I \otimes(J_3,K_3)
\]
\[
g_8(I) = \# I \otimes (J_1,K_1) - \# I \otimes (J_4,K_4) 
\]
=====Fig. 5.10=====

\vspace{1cm}
\noindent
hit-and-miss: thickening and thinning \\
hit-and-miss: counting \\
hit-and-miss: template matching 

\vspace{1cm}
5.2.4 Dilation and Erosion Summary \\
=====dilation and erosion summary, p. 173===== \\
=====Garfield 17:5=====
% associativity of dilation
% \[
% (A \oplus B) \oplus C = A \oplus (B \oplus C)
% \]
% dilation distributes over union
% \[
% (A \cup B) \oplus C = (A \oplus C) \cup (B \oplus C)
% \]
% \[
% A \oplus B = \bigcup_{b \in B} A_b
% \]
% \[
% A \subseteq B \Longrightarrow A \oplus C \subseteq B \oplus C
% \]
% \[
% (A \cap B) \oplus C 
% \]
% \[
% A \oplus (B \cup C) = (A \oplus B) \cup (A \oplus C)
% \]

\vspace{1cm}
5.2.5 Opening and Closing \\
dilation and erosions: usually employed in pairs \\
$B \open K$: opening of image $B$ by kernel $K$
\[
B \open K = (B \ominus K) \oplus K
\]
$B \close K$: closing of image $B$ by kernel $K$
\[
B \close K = (B \oplus K) \ominus K
\]
$B$ open under $K$: $B$ open w.r.t. $K$: $B=B \open K$ \\
$B$ closed under $K$: $B$ closed w.r.t. $K$: $B=B \close K$ \\
morphological opening, closing: no relation to topologically open, closed sets

\vspace{1cm}
\noindent
opening characterization theorem
\[
A \open K = \{ x \in A | {\rm for \ some \ } t \in A \ominus K, x \in K_t
   {\rm \ and \ } K_t \subseteq A \}
\]
$A \open K$: selects points covered by some translation of $K$, 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 

\vspace{1cm}
\noindent
unlike erosion and dilation: opening invariant to kernel translation
\[
A \open K = A \open K_x
\]
opening antiextensive
\[
A \open K \subseteq A
\]
like erosion and dilation: opening increasing
\[
A \subseteq B \Longrightarrow A \open K \subseteq B \open K
\]

\vspace{1cm}
\noindent
$A \open K$: those pixels covered by sweeping kernel all over inside of $A$ 
\[
A \open K = \bigcup_{y \in A \ominus K} K_y = \bigcup_{K_y \subseteq A} K_y
\]
$F$: shape with body and handle \\
$L$: small disk structuring element with diameter 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===== 

\vspace{1cm}
\noindent
closing: dual of opening 
\[
A \close K = \{ x | x \in \check{K}_t {\rm \ implies \ } \check{K}_t \cap A \neq \emptyset \}
\]
like opening: closing invariant to kernel translation
\[
A \close K_x = A \close K
\]
closing extensive
\[
A \subseteq A \close K
\]
like dilation, erosion, opening: closing increasing
\[
A \subseteq B \Longrightarrow A \close K \subseteq B \close K
\]

\vspace{1cm}
\noindent
opening idempotent
\[
(A \open K) \open K = A \open K
\]
closing idempotent
\[
(A \close K) \close K = A \close K
\]

\vspace{1cm}
\noindent
if $L \subseteq K$ not necessarily follows that $A \open L \supseteq A\open K$\\
=====Fig. 5.22===== 

\vspace{1cm}
\noindent
closing may be used to detect spatial clusters of points \\
=====Fig. 5.23=====

\vspace{1cm}
5.2.6 Morphological Shape Feature Extraction \\
morphological pattern spectrum: shape-size histogram [Maragos 1987] 
\[
S(A; K)(m) = \# A \open K(m-1) - \# A \open K(m), \ \ \ m \geq 1
\]
\[
S(A; K)(-m) = \# A \close K(m+1) - \# A \close K(m), \ \ \ m \geq 0
\]

\vspace{1cm}
5.2.7 Fast Dilations and Erosions \\
decompose kernels to make dilations and erosions fast

\vspace{1cm}
5.3 Connectivity \\
morphology and connectivity: close relation

\vspace{1cm}
5.3.1 Separation Relation \\
$S$ separation if and only if $S$ symmetric, exclusive, hereditary, extensive

\vspace{1cm}
5.3.2 Morphological Noise Cleaning and Connectivity \\
images perturbed by noise can be morphologically filtered to remove some noise

\vspace{1cm}
5.3.3 Openings, Holes, and Connectivity \\
opening can create holes in a connected set that is being opened \\
=====Fig. 5.25=====

\vspace{1cm}
5.3.4 Conditional Dilation \\
select connected components of image that have nonempty erosion \\
conditional dilation $J \oplus |_I D $, defined iteratively $J_0 = J$ \\
$J$ are points in the regions we want to select
\[
J_n = (J_{n-1} \oplus D) \cap I
\]
conditional dilation $J \oplus |_I D = J_m$ where $m$ is the smallest index
$J_m = J_{m-1}$ \\
=====Fig. 5.26=====

\vspace{1cm}
5.4 Generalized Openings and Closings \\
generalized opening: any increasing, antiextensive, idempotent operation \\
generalized closing: any increasing, extensive, idempotent operation \\
=====Oldie 33:18=====

\vspace{1cm}
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

\vspace{1cm}
5.5.1 Gray Scale Dilation and Erosion \\
top: top surface of $A$: denoted by $T[A]:  F \rightarrow E$:
\[
T[A](x) = \max \{ y | (x, y) \in A \}
\]
umbra of $f$: denoted by $U[f], U[f] \subseteq F \times E$
\[
U[f] = \{ (x, y) \in F \times E | y \leq f(x) \}
\]
=====Fig. 5.28===== \\
gray scale dilation: surface of dilation of umbras \\
dilation of $f$ by $k$: denoted by $f \oplus k$
\[
f \oplus k = T \{ U[f] \oplus U[k] \}
\]
=====Fig. 5.29===== \\
=====Fig. 5.30===== 

\vspace{1cm}
\noindent
$ f: F \rightarrow E$ and $k: K \rightarrow E$, then $f \oplus k: F \oplus K
     \rightarrow E$
\[
(f \oplus k)(x) = \max \{ f(x-z)+k(z) | z \in K, x-z \in F \}
\]
=====Fig. 5.31===== \\
=====lena.im===== \\
=====lena.im.dil=====

\vspace{1cm}
\noindent
gray scale erosion: surface of binary erosions of one umbra by the other umbra
\[
f \ominus k = T \{ U[f] \ominus U[k] \}
\]
=====Fig. 5.32===== 

\vspace{1cm}
\noindent
$ f: F \rightarrow E$ and $k: K \rightarrow E$, then $f \ominus k: F \ominus K
     \rightarrow E$
\[
(f \ominus k)(x) = \min_{z \in K} \{ f(x+z)-k(z) \}
\]
=====Fig. 5.33===== \\
=====lena.im.ero===== \\
=====Fig. 5.34=====

\vspace{1cm}
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
\[
T \{ U[f] \} = f
\]
Proposition 5.1
\[
f \oplus k = k \oplus f
\]
Proposition 5.2
\[
k_1 \oplus (k_2 \oplus k_3) = (k_1 \oplus k_2) \oplus k_3
\]
Proposition 5.3
\[
(f \ominus k_1) \ominus k_2 = f \ominus (k_1 \oplus k_2)
\]


\vspace{1cm}
5.5.3 Gray Scale Opening and Closing \\
gray scale opening of $f$ by kernel $k$: denoted by $f \open k$
\[
f \open k = (f \ominus k) \oplus k
\]
=====lena.im.open=====

\vspace{1cm}
\noindent
gray scale closing of $f$ by kernel $k$: denoted by $f \close k$
\[
f \close k = (f \oplus k) \ominus k
\]
=====lena.im.close=====

\vspace{1cm}
\noindent
duality of gray scale dilation, erosion $\Longrightarrow$ duality of opening, 
     closing 
\[
-(f \open k)(x) = [(-f) \close \check{k}](x)
\]
=====Fig. 5.37=====

\vspace{1cm}
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

\vspace{1cm}
5.7 Bounding Second Derivatives \\
opening or closing a gray scale image: simplifies the image complexity

\vspace{1cm}
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=====

\vspace{1cm}
5.9 Generalized Distance Transform 

\vspace{1cm}
5.10 Medial Axis \\
medial axis transform: medial axis with distance function

\vspace{1cm}
5.10.1 Medial Axis and Morphological Skeleton \\
morphological skeleton of a set $A$ by kernel $K$, where $A \ominus_0 K = A$
\[
S_0, ..., S_N, {\rm \ where \ } S_n = A \ominus_n K - (A \ominus_n K) \open K
\]
skeleton of $A$ given by $ \bigcup_{n=0}^N S_n$ \\
=====Fig. 5.40===== \\
=====Fig. 5.41=====

\vspace{1cm}
5.11 Morphological Sampling Theorem 

\vspace{1cm}
5.11.1 Set-Bounding Relationships 

\vspace{1cm}
5.11.2 Examples

\vspace{1cm}
5.11.3 Distance Relationships \\
=====Garfield 17:7=====

\vspace{1cm}
5.12 Summary \\
morphological operations: shape extraction, noise cleaning, thickening \\
morphological operations: thinning, skeletonizing

\vspace{1cm}
Project due Nov. 2 \\
Write programs which do binary morphological dilation, erosion, opening,
closing, and hit-and-miss transform on a binary image.

\vspace{1cm}
Project due Nov. 9 \\
Write programs which do gray scale morphological dilation, erosion, opening,
and closing on a gray scale image.










\end{document}
