\documentstyle[12pt]{article}
\usepackage{html}
\begin{document}
\begin{center}
{\Large \bf Mathematical Morphology}
\end{center}

\section*{Morphology}

{\bf Language of set theory}

Let $Z$ denote the set of all integers, and $Z^2=Z\times Z$ denote the
set of integer pairs $(i,j)\in Z^2$. The coordinates of a pixel 
$v[i][j]$ in an image can therefore be considered as a component of $Z^2$.

Let $A$ and $B$ be two white regions in a black and white binary image.
Then they can be considered as two sets in $Z^2$ space, and their 
components $a=(a_1,a_2)\in A$ and $b=(b_1,b_2)\in B$ are just a pixel 
inside each of the regions.

In a binary image, an object of a certain shape can be represented by a 
set of either 4- or 8-connected white pixels in white background. To carry
out certain operations on the shape of the object, the object and its back 
ground are mathematically represented as sets. 

In general, a set is defined as a group of components all having certain
properties or satisfying certain conditions:
\[	A=\{ a\;|\;\mbox{property(a)==TRUE} \}	\]

\begin{itemize}
\item {\bf Object: } 
\[ A=\{a\;|\; v[a_1][a_2]==1,\;\mbox{and all $a=(a_1,a_2)$'s are connected}\} \]
\item {\bf Background:}
\[ B=\{b\;|\; b \neg \in A \}	\]
	where $\neg \in$ means ``not belong to''.
\end{itemize}


{\bf Basic definitions:}
\begin{itemize}
\item {\bf Translation: } The translation of $A$ by $x=(x_1,x_2)$ is
\[	A_x=\{c\;|\;c=a+x, \;\;\mbox{for all }\;\; a\in A \}		\]
where $c=(c_1,c_2)=(a_1+x_1,a_2+x_2)=a+x$.
\item {\bf Reflection: } The reflection of $A$ is 
\[	\hat{A}=\{-a\;|\;a \in A \}		\]
Here the reflection is with respect to a specific origin, such as a point 
center in the shape, e.g., the center of the shape.
\item {\bf Complement: } The complement of $A$ is
\[	A^c=\{c\;|\;c \; \neg \in A \}		\]
\item {\bf Difference: } The difference between $A$ and $B$ is
\[	A-B=\{a\;|\;a\in A, a\in B^c \}=A\cap B^c	\]
\end{itemize}

\htmladdimg{../figures/morphology1.gif}

Below, a {\em structuring element} $B$ is a binary object used in varioius
morphology operators. All elements $b \in B$ are measured with respect to the 
origin $(0,0)$ located at the center of the object. For example, if $B$ is a 
$5\times 5$ square, then for any $b=(b_1,b_2) \in B$, $-2\le b_1,b_2,\le 2$.

{\bf Dilation}

\[	D(A,B)=A\oplus B=\{ x\;|\;(\hat{B}_x \cap A) \ne \Phi \}	\]
where $\Phi$ represents empty set. Alternatively,
%\[	D(A,B)=A\oplus B=\{ x\;|\;(\hat{B}_x \cap A) \subseteq A \}	\]
\[	D(A,B)=A\oplus B=\bigcup_{b\in B} A_b=\bigcup_{a\in A} B_a \]

\begin{itemize}
\item Find reflection $\hat{B}$ of set $B$ by flipping it about its origin.
	If $B$ is central symmetric, this step makes no difference;
\item Translate (shift, slide) $\hat{B}$ by displacement $x$ over $A$;
\item $A\oplus B$ is the set of all displacements $x$'s that keep the 
	intersect (overlap) of $\hat{B}_x$ and $A$ non-empty (keep them 
	``in touch''). 
\item Dilation of a binary image shape $A$ by $B$ expands the shape by 
	half of the size of $B$.
\end{itemize}

\htmladdimg{../figures/morphology2.gif}

As typically the structuring element $B$ is symmetric (either central 
symmetric or symmetric with respect to its vertical or horizontal axis),
the reflection part of the dilation definition will be dropped in the 
following. 

\htmladdimg{../figures/constructing_elements_examples.gif}

For these simplest structuring elements, dilation can be carried out 
by setting all background pixels (with value "0") 4- or 8-connected to
each object pixel (with value "1") to the value "1".

{\bf Erosion}

\[	E(A,B)=A\ominus B=\{ x\;|\;B_x \subseteq A \}	\]
Alternatively,
\[ 	E(A,B)=A\ominus B=\bigcap_{b\in B} A_b \]
\begin{itemize}
\item Translate (or slide) $B$ by $x$ over $A$;

\item $A\ominus B$ is the set of all translations $x$'s that will keep 
	the translated version of $B$ to be entirely contained in $A$.
\item Erosion of a binary image shape $A$ by $B$ shrinks the shape by 
	half of the size of $B$.
\end{itemize}

\htmladdimg{../figures/morphology3.gif}

If the same simple structuring elements are used, erosion can be carried
out by setting each object pixel (with value "1") 4- or 8-connected to a
background pixel (with value "0") to the value "0".

\htmladdimg{../figures/morphology5.gif}

{\bf Properties of dilation and erosion}
\begin{itemize}
\item Commutative:
\[	A\oplus B=B\oplus A	\]
\item Non-commutative:
\[	A\ominus B\ne B\ominus A	\]
\item Associative:
\[	A\oplus (B\oplus C)=(A\oplus B)\oplus C	\]
\item 
\[	A\oplus (B\cup C)=(A\oplus B)\cup(A\oplus C)	\]
\item 
\[	A\ominus (B\cup C)=(A\ominus B)\cap(A\ominus C)	\]
\item 
\[	(A\ominus B)\ominus C=A\ominus (B\oplus C)	\]
\item The complement of the erosion of $A$ by $B$ is the same as the
dilation of complement of $A$ by $B$:
\[	{(A\ominus B)}^c = A^c \oplus B	\]
\item
The complement of the dilation of $A$ by $B$ is the same as the
erosion of complement of $A$ by $B$. 
\[	{(A\oplus B)}^c = A^c \ominus B	\]
\end{itemize}

{\bf Proof:} 
\[	(A\ominus B)^c=(\{x\;|\;B_x \subseteq A \})^c	\]
Since set $B_x$ is contained in $A$, i.e., $B_x \subseteq A$, it has
no overlap with the complement of $A$, i.e., $B_x \cap A^c=\Phi$,
and the above equation can be written as:
\[	(A\ominus B)^c=(\{x\;|\;(B_x \cap A^c) = \Phi \})^c	\]
But the complement of this set of all $x's$ satisfying the condition
$B_x \cap A^c = \Phi$ is the set of all $x's$ not satisfying the
condition, i.e., 
\[	(A\ominus B)^c=(\{x\;|\;B_x \cap \bar{A} = \Phi \})^c
	=\{x\;|\;(B_x \cap A^c) \ne \Phi \}=A^c \oplus B	\]
Taking complement on both sides above, and replacing $A$ by $A^c$, we
get the second relation.

{\bf Opening}
\[	O(A,B)=D(E(A,B),B),\;\;\;\;\;\;\;A \circ B=(A\ominus B)\oplus B	\]
The opening of $A$ and $B$ is the dilation of the erosion of $A$ by $B$.
\begin{itemize}
\item Dilation and erosion are not a pair of opposite operations in
	the sense that their effects do not cancel each other. 
\item The erosion carried out first eliminates small shapes (assumed to
  be noise) as well as shrinking the object shape, while the following 
  dilation grows the object back (but not the noise).
\end{itemize}

{\bf Closing}
\[ C(A,B)=E(D(A,B),B),\;\;\;\;\;\;\;A \bullet B=(A\oplus B)\ominus B \]
The closing of $A$ and $B$ is the erosion of the dilation of $A$ by $B$.
\begin{itemize}
\item The effect of dilation and erosion do not cancel each other. 
\item The dilation carried out first eliminates small holes inside the 
  object shape (assumed to be noise) as well as expanding the object 
  shape, while the following erosion shrinks the object back (but not 
  the noise).
\end{itemize}

{\bf Grayscale dilation and erosion}

Morphological operations can be generalized to grayscale images. Here
neither the image nor the structuring element is binary any more, and the 
Boolean operations (AND and OR, union and intersect) used for binary images
are replaced by addition, subtraction, maximum and minimum operations.

\begin{itemize}
\item Dilation:
\[	D[m,n]=max_{i,j} ( A[m-i,n-j]+B[i,j] )	\]
where the maximum value is taken in the neighborhood of pixel $[m,n]$ defined
by the structuring element $B$. Dilation tends to grow the white regions of 
an image. If the structuring element has positive values, the resulting image 
tends to be brighter.
\item Erosion:
\[	E[m,n]=min_{i,j} ( A[m-i,n-j]-B[i,j] )	\]
where the minimum value is taken in the neighborhood of pixel $[m,n]$ defined 
by the structuring element $B$. Erosion tends to shrink the white regions of 
an image. If the structuring element has positive values, the resulting image 
tends to be darker.

\end{itemize}

\htmladdimg{../figures/DilationErosionCode.gif}

{\bf Applications:}

\begin{itemize}
\item Extracting boundaries : The boundary of $A$, denoted by $\beta(A)$, can be 
  obtained as the difference of $A$ and its erosion $A\ominus B$ or dilation
$A\oplus B$:
  \[ \beta(A)=A-(A\ominus B)\;\;\;\;\;\mbox{or}\;\;\;\;\;\beta(A)=A-(A\oplus B) \]

\item Filling holes:

\item Thinning:

\end{itemize}

{\bf Example:}

\htmladdimg{../figures/GumbyMorph.gif}




\htmladdimg{../figures/morphology4.gif}

\htmladdimg{../figures/morphology7.gif}

\htmladdimg{../figures/morphology8.gif}

{\bf Example:}  

\htmladdimg{../figures/MorphologyDemo.gif}

{\bf Binary morpohology} (top):     original image, histogram, binary image (threshold 160), erosion, dilation;

{\bf Gray-scale morphology} (bottom): original image, erosion, dilation, histogram, binary image (threshold 130).



\section*{A Thinning Algorithm}

{\bf Purpose:} Convert binary shapes obtained from edge/boundary detection 
or thresholding to 1-pixel wide lines. For example, the thresholded version
of hand written or printed alphanumerics can be thinned for better represetation
and further processing.

{\bf Method:} iteratively delete pixels inside the shape to shrink it without
shortening it or breaking it apart.

{\bf Some Definitions:}  To decide whether an edge pixel $P_1$ should be deleted,
consider its 8 neighbors in the 3 by 3 neighborhood, $P_2$, $P_3$, $P_4$, 
$P_5$, $P_6$, $P_7$, $P_8$ and $P_9$, and define:

\begin{itemize}
\item $N(P_1)$: number of non-zero neighbors:
  \[N(P_1)=P_2+P_3+\cdots+P_9\]
\item $S(P_1)$: number of 0 to 1 (or 1 to 0) transitions in the sequence 
$(P_2,P_3,\cdots, P_9)$.
\end{itemize}

{\bf The Algorithm:} This is a 2-pass process:

\begin{itemize}
\item Pass 1: Mark any edge pixel $P_1=1$ not satisfying at least one
of the following conditions (to be deleted in second step):

\begin{itemize}
  \item $N(P_1)=0$ (an isolated point)
  \item $N(P_1)=1$ (tip of a line)
  \item $N(P_1)=7$ (located in concavity)
  \item $N(P_1)=8$ (not a boundary point)
  \item $S(P_1)\ge 2$ (on a bridge connecting two or more edge pieces)
\end{itemize}
\item Pass 2: Deleted all marked edge points.
\end{itemize}

{\bf A problem: } When part of the shape is only 2-pixel wide, all pixels 
are boundary points and will be marked and then deleted. We want to delete
only one side at a time. 

{\bf The Solution: } A two-step process:
\begin{itemize}
\item Step 1: Delete all deletable point in the S, E, NW and NE boundaries.
\item Step 2: Delete all deletable point in the N, W, SE and SW boundaries.
\end{itemize}

\htmladdimg{../figures/thinning.gif}

{\bf Modified Algorithm:} Repeat until no more change can be made:

\begin{itemize}
\item 1: Mark all pixels satisfying ALL of the following:
$(P_1=1)$ and $(2\le N(P_1) \le 6)$ and $(S(P_1)=1)$ and 
$(P_2\cdot P_4\cdot P_6=0)$ and $(P_4\cdot P_6\cdot P_8=0)$ and $(P_7\ne 0)$.
\item 2: Delete all marked pixels.

\item 3: Mark all pixels satisfying the following:
  \[ [P_1=1]\;\wedge\;[2\le N(P_1)\le 6]\;\wedge\;[S(P_1)=1]\;\wedge\;[P_2\cdot P_4\cdot P_8=0]\;\wedge\;[P_2\cdot P_6\cdot P_8=0]\;\wedge\;[P_7\ne 0] \]
\item 4: Delete all marked pixels.
\end{itemize}

Let $A_i$ represent the event ``$P_i=0$''. Then 
$[P_2\cdot P_4\cdot P_6=0]\;\wedge\;[P_4\cdot P_6\cdot P_8=0]$ above
can be represented by:
\[  (A_2\vee(A_4\vee A_6))\wedge((A_4\vee A_6)\vee A_8)
    =A_4\vee A_6\vee(A_2\wedge A_8)\]
i.e.,
\[ (P_4=0) \vee (P_6=0) \vee (P_2=P_8=0)  \]
This is either an E edge ($P_4=0$), an S edge ($P_6=0$), 
an NW edge ($P_2=P_8=0$), an NE edge ($P_4=P_2=0$), or an SW edge 
($P_6=P_8=0$). However, the additional condition $P_7\ne 0$ excludes
an SW edge.

Similarly, we see hat edges on N, W, SW, or SE side will be deleted in
the second pass. 

\section*{A Skeletonization Algorithm}

{\bf The Purpose: } To find medial axis of a 2D shape, the set of points
where the ``fire lines'' meet.

{\bf The Algorithm:} 
\begin{itemize}
\item Step 1: Represent shape in binary form,  initialize $k=0$.

  \[ x_0[m,n]=\left\{ \begin{array}{ll}
    1 & \mbox{if pixel $[m,n]$ is inside the shape} \\
    0 & \mbox{otherwise}
    \end{array} \right. \]

\item Step 2: Repeat the following until no more change can be made:
  $k=k+1$,
  
  for each $x_{k-1}[m,n]=k$, do $x_k[m,n]=min\{x_{k-1}[i,j] \}+1$,
  here $[i.j]$ is the four closest neighbors of $[m,n]$.

\item Step 3: The skeleton is the set of points given below:
  \[\{ [m,n]\; |\; x_k[m,n]=max\{ x_k[i,j] \} \} \]

\htmladdimg{../figures/skeloton.gif}

The full 2D shape can be recostructed from the skeleton pixels as the 
union of all circules with center at $[m,n]$ and radius of $x[m,n]-1$.

\end{itemize}


\section*{Hit-and-Miss Algorithm}

The purpose of the hit-and-miss algorithm is to detect certain patterns in
a binary image, using a structuring element containing 1's, 0's and blanks
for don't cares. The structuring element is used as a template that slides
over the binary image (similar to a convolution kernel) and the pixel 
corresponding to the center of the template is set to 1 if the template 
matches the image, or 0 otherwise. For example, the following four 
structuring elements can detect corners of four different orientations. 
The final result is an OR of four images each obtained by one of the four
structuring elements.

\htmladdimg{../figures/hit_and_miss.gif}

Hit-and-miss algorithm can be used to thin and skeletonize a shape in a
binary image. This is an iterative process containing repeated steps to 
thin the shape by hit-and-miss method. In each iteration, some different 
structuring elements are used to identify the edge pixels to be removed,
followed by the actual removal of them:
\[	I'_k=O_i(I_k),\;\;\;\;\;I_{k+1}=I_k -I'_k, \;\;\;\;k=k+1 \]
where $I_k$ is the image after k iterations, $O_i(I_k)$ is the application 
of a structuring element $O_i$ to $I_k$, and $I_k-I'_k$ is a set
subtraction $A-B=A\cap \bar{B}$. After each such iteration, the elements 
are rotated to identify and remove other edge pixels in different orientations.
The process continues until no further edge pixels can be identified, and 
the shape has been thinned to a skeleton. 

\htmladdimg{../figures/hit_and_miss_thin.gif}

\end{document}





\end{document}











