\pagestyle{fancy}
\cleardoublepage\chapter{Morphological Filters\index{morphology}\index{morphological filters|see{morphology}}}\label{morphology}
\Quote{Make everything as simple as possible, but not simpler.}{Albert Einstein}

\noindent Mathematical morphology\index{mathematical morphology} is one of the most successful classes of image analysis methods. It analyzes the shape of objects in an image.

An interesting property is that morphological filters are invariant under monotone increasing grayscale transformations. It holds that
\begin{equation}\label{morphology.grayscale_transformation}
	M G f = G M f
\end{equation}
for an image $f$, where $M$ is any morphological filter and $G$ is any monotonically increasing grayscale transformation. As a consequence, morphological methods do only take into account the \emph{level sets}
\begin{equation}\label{morphology.levelsets}
	L_g(f) := \{(x,y) \; | \; f(x,y) \geq g\}
\end{equation}
of an image $f$. A detailed discussion of mathematical image analysis can be found in \cite{soille99}.

We now investigate the different building blocks of mathematical morphology\index{mathematical morphology}.

\section{Dilation\index{morphology!dilation|see{dilation}}\index{dilation} and Erosion\index{morphology!erosion|see{erosion}}\index{erosion}}\label{morphology.dilation_erosion}
\begin{figure}[htb]
	\centering
	\includegraphics[scale=0.35]{figures/dilation.eps} \quad
	\includegraphics[scale=0.35]{figures/erosion.eps}
	\caption[Visualization of a dilation and an erosion operation.]{\textbf{Left:} The dilation of the dark-blue square by a disk, resulting in the light-blue square with rounded corners. \textbf{Right:} The erosion of the dark-blue square by a disk, resulting in the light-blue square. \textbf{Source:} Wikipedia \cite{mathmorphology}.}
	\label{figure_dilation_erosion}
\end{figure}

Dilation\index{dilation} is one of the basic operations in mathematical morphology\index{mathematical morphology}. It uses a so-called \emph{structuring element}\index{morphology!structuring element|see{structuring element}} (also called mask) for probing and expanding the shapes contained in the input image.

The dilation\index{dilation} operation on a continuous image $f(x,y)$ using a structuring element\index{structuring element} $SE$ is defined by
\begin{equation}\label{dilation_equation}
	(f \oplus SE)(x,y) := \sup\{f(x-x',y-y') \; | (x',y') \in SE\}.
\end{equation}

Erosion\index{erosion} is the opposite operation of dilation\index{dilation}. It uses the structuring element\index{structuring element} to shrink the shapes contained in the input image.

Analogously to the dilation\index{dilation} operation, we can formulate the erosion\index{erosion} of a continuous image $f(x,y)$ using a structuring element\index{structuring element} $SE$ by
\begin{equation}\label{erosion_equation}
	(f \ominus SE)(x,y) := \inf\{f(x+x',y+y') \; | (x',y') \in SE\}.
\end{equation}

In the discrete case, the maximum is used instead of the supremum and the minimum instead of the infimum.

When applying dilation\index{dilation} and erosion\index{erosion} often convex structuring elements\index{structuring element} such as disks or squares are used. Convex structuring elements\index{structuring element} have the advantage that they are scalable. This means that a dilation/erosion\index{dilation}\index{erosion} with a structuring element\index{structuring element} $n \cdot SE$ is equivalent to a dilation/erosion\index{dilation}\index{erosion} with structuring element\index{structuring element} $SE$ applied $n$ times.

Figure \ref{figure_dilation_erosion} shows how a dilation and an erosion with a disk works.

\section{Opening\index{morphology!opening|see{opening}}\index{opening} and Closing\index{morphology!closing|see{closing}}\index{closing}}\label{morphology.opening_closing}
\begin{figure}[htb]
	\centering
	\includegraphics[scale=0.35]{figures/opening.eps} \quad
	\includegraphics[scale=0.35]{figures/closing.eps}
	\caption[Visualization of an opening and a closing operation.]{\textbf{Left:} The opening of the dark-blue square by a disk, resulting in the light-blue square with round corners. \textbf{Right:} The closing of the dark-blue shape (union of two squares) by a disk, resulting in the union of the dark-blue shape and the light-blue areas. \textbf{Source:} Wikipedia \cite{mathmorphology}.}
	\label{figure_opening_closing}
\end{figure}

Opening\index{opening} and closing\index{closing} are morphological low pass filter. To perform the closing\index{closing} operation, a dilation\index{dilation} followed by an erosion\index{erosion} is performed. The operation closes small gaps in bright structures and is defined as
\begin{equation}
	f \bullet SE := (f \oplus SE) \ominus SE.
\end{equation}

The opening\index{opening} is the opposite operation to closing\index{closing} and is an erosion\index{erosion} followed by a dilation\index{dilation}. Mathematically, it is defined as
\begin{equation}
	f \circ SE := (f \ominus SE) \oplus SE.
\end{equation}
It closes small gaps in dark structures. A visualization of these operations is given in Figure \ref{figure_opening_closing}.

\section{Nonflat Morphology}\label{morphology.nonflat}
%In Section \ref{morphology.skeletonization}, we introduced a version of the skeletonization\index{skeletonization} algorithm that can handle grayscale images. We modify the algorithm in such a way that it uses a parabola which is a nonflat structuring element, see also van den Boomgaard \cite{vdBoomgaard92}. To this end, we introduce a modified version of dilation\index{dilation} and erosion\index{erosion} where we stick to the discrete case, only.
In the previous sections, we saw examples of morphological operations with a disk which is a flat structuring element.
In the context of grayscale images also nonflat structuring elements can be used. Motivated by van den Boomgaard \cite{vdBoomgaard92}, we present modified versions of dilation\index{dilation} and erosion\index{erosion} that use a parabola as structuring element (to be more precise a \emph{structuring function}) where we stick to the discrete case.

The \emph{parabolic dilation\index{dilation}} reads as
\begin{equation}\label{eq_pardil}
	f_d (x,y) := \max_{i,j} \Big(f(i,j) - \big(s_x \cdot (x-i)^2 + s_y \cdot (y-j)^2\big)\Big)
\end{equation}
and the \emph{parabolic erosion\index{erosion}} as
\begin{equation}\label{eq_parero}
	f_e (x,y) := \min_{i,j} \Big(f(i,j) + \big(s_x \cdot (x-i)^2 + s_y \cdot (y-j)^2\big)\Big),
\end{equation}
where $(x,y), (i,j) \in I$ and $s_x$ and $s_y$ are scaling parameters.

Using a parabolic structuring element introduces some challenges. Nonflat morphological methods do not operate on level sets as given in \eqref{morphology.levelsets}. In other words, equation \eqref{morphology.grayscale_transformation} is not satisfied anymore. %Second, dilation and erosion is not scalable in the discrete case, meaning that a dilation/erosion with a structuring element $n \cdot SE$ is \emph{not} equivalent to a dilation/erosion with a structuring element $SE$ applied $n$ times. We propose a remedy to this issue in Section \ref{modifications.morphology}.
Another practical difficulty with nonflat morphological operations arises with spatial discretization. While parabolic dilation and erosion in their continuous formulation retain the property that dilating or eroding $n$ times with the same structuring element is equivalent to dilating or eroding once with a structuring element rescaled to $n$ times its horizontal size, the same does not even approximately hold when parabolic dilation and erosion are carried out on a spatial grid. We will have to be considerate of this circumstance when applying nonflat morphology for skeletonization in Section \ref{modifications.morphology}.

\section{Skeletonization\index{skeletonization}}\label{morphology.skeletonization}
Skeletonization\index{skeletonization} was already investigated in 1968 by Calabi and Hartnett \cite{calabi68} and is still a topic of active research (e.g.\ Kimmel et al.\ \cite{kimmel95}) where people are also interested in fast algorithms \cite{zou03}. Skeletons\index{skeleton} are frequently used as shape descriptors, e.g.\ in character recognition.

We can think of the skeletonization\index{skeletonization} as follows. Imagine some arbitrary shape. We set the boundary of this shape afire. Then, the fire moves from the boundary into the shape where the \emph{Huygens wavefronts} of the boundary points meet at the \emph{skeleton\index{skeleton} point}. In other words, the skeleton\index{skeleton} point is located at the intersection of the normals to the two boundary points and each skeleton\index{skeleton} point corresponds to at least two boundary points. The distance between the skeleton\index{skeleton} point to both boundary points is equal. Figure \ref{figure_skeletonization} shows two shapes and their corresponding skeletons given as a thick black line.

\begin{figure}[htb]
	\centering
	\includegraphics[scale=0.2]{figures/skel1.eps}
	\includegraphics[scale=0.2]{figures/skel2.eps}
	\caption[Examples of a skeletonization.]{Two shapes and their corresponding skeletons. Each skeleton is given as a thick black line. \textbf{Source:} \cite{skeletonexamples}.}
	\label{figure_skeletonization}
\end{figure}

After having some intuition, let us formulate the skeletonization\index{skeletonization} more mathematically. The skeleton of a set can be expressed by erosions\index{erosion} and openings\index{opening}. We have
\begin{equation}\label{eq_skeletonization}
	S(f) := \bigcup_{k=0}^K \Big\{(f \ominus k \cdot SE) - \big[(f \ominus k \cdot SE) \circ SE\big]\Big\},
\end{equation}
where $SE$ is the structuring element and $K$ is the last iterative step before $f$ erodes to an empty set. Please note that equation \eqref{eq_skeletonization} works on binary images only.