%gmChap08.tex

\graphicspath{{./figures/}}

\chapter{\label{Chap8}Erosions and Dilations}

We are going to study in detail two of the simplest  operators of
mathematical morphology, the erosions and dilations. In fact,
there will be essentially four operators: two set operators and
the two related function operators. These operators will depend on
a scale parameter $t$. We will also study the underlying PDEs
${\partial u}/{\partial t}=c|Du|$, where $c=1$ for dilations and
$c=-1$ for erosions.

\section{Set and function erosions and dilations }

We saw in  Chapter \ref{Chap7} that every contrast-invariant monotone function operator has a sup-inf and an inf-sup
representation  in terms of some set of structuring elements. This is the point of view we take here, and furthermore,
we assume that the set of structuring elements $\mathcal B$ has the simplest possible form, namely, $\mathcal B=\{B\}$.
We actually introduce a parameter $t$ scaling the size of $B$ and therefore consider the two operators of the next
definition.


\begin{definition}For $u\in\mathcal F$, define $D_{tB}u=D_t u$ by
\begin{equation}
D_t u(\fxx)=\sup_{\fxy\in tB}u(\fxx-\fxy),
\end{equation}
the ``dilation of $u$ by $tB$. In the same way,   define $E_{tB}u=E_t u$, the ``erosion of $u$  by $-tB$", by
\begin{equation}
E_t u(\fxx)=\inf_{\fxy\in-tB}u(\fxx-\fxy).
\end{equation}
\end{definition}

  These function operators have associated set operators.


\begin{definition}Let $B$ be a non empty subset of  $\RR^N$ and let $t\geq0$ be a scale parameter.
 The set operators $\mathcal D_{tB}$  and $\mathcal E_{tB}$ are defined on subsets
 $X\in\mathcal M(\RR^N)$ by
\begin{equation}\label{eq8.1}
\mathcal D_{tB}X=\mathcal D_t X=X+tB=\{\fxx\mid \exists b\in B,\fxx-tb\in X\},
\end{equation}
\begin{equation}
\mathcal E_{tB}=\mathcal E_t X=\{\fxx\mid\fxx+tB\subset X\},
\end{equation}
and extended to $\mathcal M(S_N)$ by the standard extension (Definition \ref{defstandardextension}.) $\mathcal D_t X$
is called the dilation of $X$ by $B$ at scale $t$. $\mathcal E_t X$ is called the erosion of $X$ by $B$ at scale $t$.
\end{definition}

\begin{exercise} \label{dualityformulas}(Duality formulas.) Show that
 $E_{tB}u=-D_{-tB}(-u)$ and $\mathcal E_{tB}X=(\mathcal  D_{-tB} X^c)^c.$
\finex
\end{exercise}

\begin{exercise} Show that if $B$ is bounded,
 dilations and erosions  are standard monotone operators. Compute their associated set of structuring
 elements (Proposition \ref{theorem7.1}) and check that it is standard.  \finex
\end{exercise}

\begin{theorem}\label{erosionetdilatation}
The function erosion by $tB$ is the stack filter of the set erosion by $tB$ ;  the function  dilation by $tB$ is the
stack filter of the set dilation by $t\overline{B}$ and the commutation with thresholds holds.   In other terms for
$u\in\mathcal F$ and all $\lambda$ in $\RR$, and calling $\overline{\mathcal D}_t$ the  dilation by $t\overline{B}$,
\begin{equation}\label{E8.7}
D_t u(\fxx)=\sup\{\lambda\mid\fxx\in\mathcal
D_t\levelset_{\lambda}u\},\quad \overline{\mathcal
D}_t\levelset_{\lambda}u=\levelset_{\lambda}D_t u;
\end{equation}
\begin{equation}\label{E8.9}
E_t u(\fxx)=\sup\{\lambda\mid\fxx\in\mathcal
E_t\levelset_{\lambda}u\},\quad \mathcal
E_t\levelset_{\lambda}u=\levelset_{\lambda}E_t u.
\end{equation}
\end{theorem}
\begin{proof}   We
 prove the statement for the dilations, the case of the
erosions being just simpler. Consider some $X\in \mathcal L$ and
$u(\fxx)\leq 0$ a function vanishing on $X$ only. By the
definition \ref{definitionEvansSpruck} of the level set extension
$\tilde{\mathcal D_t}$ of  $D_t$, $\tilde{\mathcal
D}_t(X)=\levelset_0D_t(u).$ Thus, using \eqref{eq8.1},
$$\fxx\in \tilde{\mathcal D}_t(X)\Leftrightarrow
(D_tu)(\fxx)=0\Leftrightarrow \sup_{\fxy\in -tB}
u(\fxx-\fxy)=0\Leftrightarrow $$
$$\exists \fxy\in t\overline{B},\; \fxx-\fxy\in X\Leftrightarrow
\fxx\in X+t\overline{B}\Leftrightarrow \fxx\in\overline{\mathcal
D}_t(X).$$
\end{proof}



 The operators $\mathcal D_t$ and $\mathcal E_t$  are in a
certain sense the inverse of each other. This is clearly the case, for example, if $B=\{\fxx_0\}$. Then $\mathcal D_t$
is just the translation by $t\fxx_0$, and $\mathcal E_t=\mathcal D_t^{-1}$ is the translation by $-t\fxx_0$. If $B$ is
the open ball centered at zero with radius one, then $\mathcal D_t X$ is the set of all points whose distance from $X$
is less than $t$, or the $t$-neighborhood of $X$. When $B$ is symmetric with respect to zero, the operator $\mathcal
D_t\mathcal E_t$ is called an \textit{opening at scale t} and $\mathcal E_t\mathcal D_t$ is called a \textit{closing at
scale t}. These names have a topological origin. If $B$ is the open ball centered at zero with radius one, then the
opening at scale $t$ of a set $X$ is the union of all balls with radius $t$ contained in $X$. The interior of $X$ is
the union of all open balls contained in $X$; it is also the largest open set contained in $X$. If we call the interior
map $\mathcal T^\circ X=X^\circ$ the opening, then an opening at scale $t$ appears as a quantified opening (see
Exercise \ref{openingandclosing}). The topological statement ``the closure of the complement of $X$ is the complement
of the interior of $X$'' has its counterpart for openings and closings at scale $t$, as shown in Exercise
\ref{openingandclosing}. The actions of erosions and dilations are illustrated in Figures \ref{figure8.1},
\ref{figure8.2}, and \ref{figure8.5}; actions of openings and closings are illustrated in Figures \ref{figure8.3},
\ref{figure8.4}, \ref{figure8.6}, \ref{figure8.7}, and \ref{figure8.8}.

\section{Multiscale aspects\label{section8.2}}

\begin{figure}[!t] \label{figure8.1}
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig08.01.1.eps}
}
\caption[Dilation of a set]{\label{Pfig1}Dilation of a set.
 Left to right: A set; its dilation by a ball of radius 20; the difference set.
}
\end{figure}

\begin{figure}[!t] \label{figure8.2}
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig08.02.1.eps}
} \caption[Erosion of a set]{\label{Pfig2} Erosion of a set. Left
to right: A set; its erosion by a ball of radius 20; the
difference set. }
\end{figure}


\begin{figure}[!t]\label{figure8.3}
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig08.04.1.eps}
}
\caption[Opening of a set as a curvature threshold]{Opening of a set as curvature threshold from above. Left to right: A set $X$; its opening by a ball of radius 20; the difference set. This opening transforms $X$ into the union of all balls of radius 20 contained in it. The resulting operation can be understood as a threshold from above of the curvature of the set boundary.
}
\end{figure}

\begin{figure}[!t]\label{figure8.4}
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig08.05.1.eps}
} \caption[Closing of a set as a  curvature threshold]{Closing of
a set as a curvature threshold from below. Left to right: A set
$X$; its closing by a ball of radius 20; the difference set. The
closing of $X$ is just the opening of $X^c$. It can be viewed as a
threshold from below of the curvature of the set boundary. }
\end{figure}


We say that the family of dilations $\{D_t\mid t>0\}$ associated with a structuring element $B$ is \textit{recursive}
if $D_tD_s=D_{t+s}$ for all $s,t>0$, and similarly for the family $\{E_t\mid t>0\}$. (A recursive family is also called
a \textit{semigroup}.) Being recursive is a very desirable property for any family of scaled operators used for image
analysis.  Having $D_t=(D_{t/n})^n$ is   useful for practical computations. $\{D_t\mid t>0\}$ and $\{E_t\mid t>0\}$
will be recursive if and only if $B$ is convex, but before proving this result we need the condition for $B$ to be
convex given in the next lemma. The proof of the next statement is an easy exercise.
\begin{lemma}
$B$ is convex if and only if $(s+t)B=sB+tB$ for all $s,t\geq0$.
\end{lemma}

\begin{figure}[!t]\label{figure8.5}
\setkeys{Gin}{width=12cm} \centerline{
\includegraphics{fig08.06.1.eps}
}
\caption[Erosion and dilation of a natural image]{Erosion and dilation of a natural image. First row: a sea bird image and its level lines for all
levels multiple of 12. Second row: an erosion with radius 4 has been  applied. On the right, the resulting level lines where the circular shape of the structuring element (a disk with radius 4) appears around each local
minimum of the original image. Erosion removes local maxima (in
particular, all small white spots) but expands minima. Thus,
all dark spots, like the eye of the bird, are expanded. Third row: the effect of a dilation with radius 4 and the resulting level
lines. We see how local minima are removed (for example, the eye of the
bird) and how white spots on the tail expand. Here, in turn, circular
level lines appear around all local maxima of the original image.
}
\end{figure}

\begin{proposition}\label{proposition8.7}
The dilations  $\mathcal D_t$ and the erosions $\mathcal E_t$  are recursive if and only the structuring element $B$ is
convex.
\end{proposition}
\begin{proof}
 Taking for simplicity $B$ closed, we have
\[
\mathcal D_t\mathcal D_s X=(X+sB)+tB=X+sB+tB
\]
and
\[
\mathcal D_{s+t}X=X+(s+t)B.
\]
If $(t+s)B=tB+sB$, then  clearly $\mathcal D_t\mathcal D_s X=\mathcal D_{s+t}X$. Conversely, if $\mathcal D_t\mathcal
D_s X=\mathcal D_{s+t}X$, then by taking $X=\{0\}$ we see that $(t+s)B=tB+sB$. One can deduce the corresponding
equivalence for erosions from the duality formula (Exercise \ref{dualityformulas}).
\end{proof}

\begin{figure}[!t]\label{figure8.6}
\setkeys{Gin}{width=12cm} \centerline{
\includegraphics{fig08.07.1.eps}
} \caption[Openings and closings of a natural image]{Openings and closings of a natural image. First row: the original
image and its level lines for all levels multiple of 12. Second row: an opening with radius 4 has been applied. Third
row: a closing with radius 4 has been applied. We can recognize the circular shape of the structuring element in the
level lines displayed on the right. }
\end{figure}

\section{The PDEs associated with erosions and dilations\label{sec:pdeerosiondilation}}

As indicated in the introduction to the chapter, scaled dilations and erosions are associated with the equations
${\partial u}/{\partial t}=\pm|Du|$. To explain this connection, we begin with a bounded convex set $B$ that contains
the origin, and we define the gauge $\|\cdot\|_B$ on $\RR^N$ associated with $B$ by $\|\fxx\|_B=\sup_{\fxy\in
B}(\fxx\cdot\fxy)$. If $B$ is a ball centered at the origin with radius one, then $\|\cdot\|_B$ is the usual Euclidean
norm, which we write simply as $|\cdot|$.

\begin{figure}[!t]\label{figure8.7}
\setkeys{Gin}{width=12cm} \centerline{
\includegraphics{fig08.08.1.eps}
} \caption[Denoising based on openings and closings I]{\label{operaun}Denoising based  on openings and closings. First
row: scanned picture of the word ``operator'' with black dots and a black line added; a dilation with a $2 \times 5$
rectangle; an erosion with the same structuring element applied to the middle image. The resulting operator is a
closing. Small black structures are removed by such a process. Second row: the word ``operator'' with  a white line and
white dots inside the letters; erosion with a rectangle $2 \times 5$; a dilation with the same structuring element
applied to the middle image. The resulting operator is an opening. This time, small white structures are removed. }
\end{figure}

\begin{proposition} \label{proposition8.8}[Hopf--Lax formula \cite
{Evans:1998:PDE,Lax:1965:NSP}]. Assume that $B$ is a bounded
convex set in $\RR^N$ that contains the origin. Given
$u_0:\RR^N\to\RR$, define $u:\RR^+\times\RR^N\to\RR$ by
$u(t,\fxx)=D_tu_0(\fxx)$. Then $u$ satisfies the equation
\[
\frac{\partial u}{\partial t}=\|Du\|_{-B}
\]
at each point $(t,\fxx)$ where $u$ has continuous derivatives in $t$ and $\fxx$. One has an analogue result with $E_t$
and the equation ${\partial u}/{\partial t}=-\|Du\|_{-B}$.
\end{proposition}
\begin{proof}We begin by proving the result for $D_t$ at $t=0$. Thus assume that $u_0$ is $C^1$ at $\fxx$. Then
\[
u_0(\fxx-\fyx)-u_0(\fxx)=-Du_0(\fxx)\cdot\fxy+o(|\fxy|),
\]
and we have by applying $D_h$,
\[
u(h,\fxx)-u(0,\fxx)=\sup_{\fxy\in hB}(-Du_0(\fxx)\cdot\fxy+o(|\fxy|)).
\]
Since $B$ is bounded, the term $o(|\fxy|)$ is $o(|h|)$ uniformly for $\fxy\in hB$, and we get
\[
u(h,\fxx)-u(0,\fxx)=h\sup_{\fxz\in B}((-Du_0(\fxx)\cdot\fxz)+o(|h|).
\]
We can divide both sides by $h$ and pass to the limit as $|h|\to0$ to obtain
\[
\frac{\partial u}{\partial t}(0,\fxx)=\|Du_0(\fxx)\|_{-B},
\]
which is the result for $t=0$. For an arbitrary $t>0$, we have $D_{t+h}=D_tD_h=D_hD_t$, and we can write
\[
u(t+h,\fxx)-u(t,\fxx)=D_hu(t,\cdot)(\fxx)-u(t,\fxx).
\]
By repeating the argument made for $t=0$ with $u_0$ replaced with $u(t,\cdot)$, we arrive at the general result. The proof for $E_t$ is similar.
\end{proof}
\begin{exercise}
Prove the above result for $E_t$.

\finex \end{exercise}

\begin{figure}[!t]\label{figure8.8}
\setkeys{Gin}{width=12cm} \centerline{
\includegraphics{fig08.09.1.eps}
} \caption[Denoising based on opening and closing (II)]{\label{POPERATORDEUX}Examples of denoising based on opening or
closing, as in Figure \ref{operaun}. Perturbations made with both black and white lines or dots have been added to the
``operator'' image. First column, top to bottom: original perturbed image; erosion with a $1 \times 3$ rectangle; then
dilation with the same structuring element. (In other words, opening with this rectangle.) Then a dilation is applied
with a rectangle $3 \times 1$, and finally an erosion with the same rectangle. Second column: The same process is
applied,  but with erosions and dilations exchanging their roles. It does not work so well because closing expands
white perturbations and opening expands black perturbations. These operators do not commute. See Figure
\ref{medianofoperatorimage}, where an application of the median filter is more successful. }
\end{figure}


\section{Exercises}

\begin{exercise}   A straightforward adaptation on a grid $\ZZ\times \ZZ$ of the formulas
$u(t,x):=\sup_{y\in B(x,t)}u_0(y)$ for dilation  and  $u(t,x):=\inf_{y\in B(x,t)}u_0(y)$ for erosion  leads to the
zero-order schemes
$$u^{n+1}(i,j)=\sup_{(k,l)\in B((i,j),t)\cap \ZZ^2} u^n(k,l)$$
and
 $$u^{n+1}(i,j)=\inf_{(k,l)\in B((i,j),t)\cap \ZZ^2} u^n(k,l), \;\; u^0(i,j)=u_0(i,j).$$
 Unfortunately, the
zero-order schemes are strongly grid dependent. They do not make any difference between two balls which contain the
same discrete pixels. In particular, such schemes only permit discrete motions of the shape boundaries. Thus, they are
efficient only when $t$ is large. Section \ref{sec:pdeerosiondilation} suggests that we can implement erosion and
dilations on a finite image grid by more clever  numerical schemes. One can try to discretize the associated PDE's
${\partial u}/{\partial t}=\pm|Du|$ by the Rouy-Tourin scheme:
 $$u^{n+1}_{ij}\!=\!u^n_{ij}\!+ \!\Delta t\left(\max(0,
u^{n}_{i+1,j}-u^n_{ij}, \!u^n_{i-1,j}\!-\!u^n_{ij})^2 \!+ \!\max(0, u^{n}_{i,j+1}\!-\!u^n_{ij},\!
u^n_{i,j-1}\!-\!u^n_{ij})^2\right)^\frac 12$$ for dilation and
$$u^{n+1}_{ij}\!=\!u^n_{ij}\!-\!\Delta t\left(\max(0,
u^{n}_{ij}-u^n_{i+1,j}, \!u^n_{ij}\!-\!u^n_{i-1,j})^2 \!+ \!\max(0, u^{n}_{ij}\!-\!u^n_{i,j+1},\!
u^n_{ij}\!-\!u^n_{i,j-1})^2\right)^\frac 12$$
 for erosion.
 In both cases if
$t=n\Delta t$ then $u^n(i,j)$ is a discrete version of $u(t, (i,j))$.

\medskip 1) Explain why  the schemes are consistent with their underlying partial differential equation. Check that
with this clever scheme local maxima of $u^n$ do not go up by dilation and local minima do not go down by erosion. Show
that for example the following scheme would be a catastrophe at extrema (you'll have to try it anyway):
$$u^{n+1}_{ij}\!=\!u^n_{ij}\!+ \!\Delta t\left(\max(|u^{n}_{i+1,j}-u^n_{ij}|, \!|u^n_{i-1,j}\!-\!u^n_{ij}|)^2 \!+
\!\max(|u^{n}_{i,j+1}\!-\!u^n_{ij}|,\! |u^n_{i,j-1}\!-\!u^n_{ij}|)^2\right)^\frac 12.$$

 \medskip 2)
Implement the schemes and compare their performance with the discrete zero order schemes for several shapes and images.

\medskip 3) Compute on some well-chosen images the ``top hat transforms" $u-O_tu$ and $F_tu -u$. The first transform
aims at extracting all structures from an image which are thinner than $t$ and have brightness above the average. The
second transform does the same job for dark structures. These transforms can be successfully applied on aerial images
for extracting roads or rivers, and in many biological applications.
 \finex
\end{exercise}

\begin{exercise} Show that $E_t(u)=-D_t(-u)$ if $B$ is symmetric
with respect to zero.\finex
\end{exercise}

\begin{exercise} \label{openingandclosing}\leavevmode
\begin{enumerate}[(i)]\setlength\itemsep{2pt}
\item Let $B=\{\fxx\mid |\fxx|<1\}$. Show that  $\mathcal
D_t\mathcal E_t X$ is the union of all open balls with radius $t$
contained in $X$. \item Let $B$ be any structuring element that is
symmetric with respect to zero. Write $X^c=\RR^N\setminus X$. Show
that $\mathcal D_t X^c=(\mathcal E_t X)^c$. Use this to show that
$\mathcal E_t\mathcal D_t X^c=(\mathcal D_t\mathcal E_t X)^c$.
\finex
\end{enumerate}
\end{exercise}

\begin{exercise}
Prove that the dilation  and erosion set operators associated with $B$  are standard monotone if and only if $B$ is
bounded. If $B$ is bounded and isotropic, prove that the associated erosion and dilation function  operators are local
{\it $\SMTCII$} operators. \finex
\end{exercise}


\section{Comments and references}

\paragraph*{Erosions and dilations.}Matheron introduced dilations and erosions as useful tools for set and shape
analysis in his fundamental book \cite{Matheron:1975:RSI}. A full account of the properties of dilations, erosions,
openings, and closings, both as set operators and function operators, can be found in Serra's books
\cite{Serra:1982:IAM,Serra:1988:IAM}. We also suggest the introductory paper by Haralick, Sternberg, and Zhuang
\cite{Haralick:1987:IAU} and an earlier paper by Nakagawa and Rosenfeld \cite{Nakagawa:1978:NUL}. An axiomatic
algebraic approach to erosions, dilations, openings, and closings has been developed by Heijmans and Ronse
\cite{Heijmans:1990:ABM,Ronse:1991:ABM}. We did not develop this algebraic point of view here. The obvious relations
between the dilations and erosions of a set and the distance function have been exploited numerically in
\cite{Huang:1994:EDT}, \cite{Kimmel:1993:SOL}, and \cite{Shih:1992:MMA}. The skeleton of a shape can be defined as the
set of points where the distance function to the shape is singular. A numerical procedure for computing the skeleton
this way is proposed in \cite{Kimmel:1995:SDM}.

\paragraph*{The PDEs.}The connection between the PDEs $\partial u/\partial t=\pm|Du|$ and multiscale dilations and
erosions comes from the work of Lax, where it is used to give stable and efficient numerical schemes for solving the
equations \cite{Lax:1965:NSP}. Rouy and Tourin \cite{rouy1992vsa} have shown that the distance function to a shape is a
viscosity solution of $1-|Du|=0$ with the null boundary condition (Dirichlet condition) on the boundary of the shape.
To define efficient numerical schemes for computing the distance function, they actually implement the evolution
equation $\partial u/\partial t=1-|Du|$ starting from zero and with the null boundary condition on the boundary of the
shape. The fact that the multiscale dilations and erosions can be computed using the PDEs $\partial u/\partial
t=\pm|Du|$ has been rediscovered or revived, thirty years after Lax's work, by several authors: Alvarez et.\ al.\
\cite{Alvarez:1993:AFE}, van den Boomgaard and Smeulders \cite{Boomgaard:1994:MSI}, Maragos
\cite{Maragos:1996:DMI,Maragos:1998:PDE}.  See also \cite{vandenboomgaard1999nss} for a numerical review. For an
implementation using curve evolution, see \cite{Sapiro:1993:ICS}. Curiously, the link between erosions, dilations, and
their PDEs seems to have remained unknown or unexploited until 1992. The erosion and dilation PDEs can be used for
shape thinning, which is a popular way to compute the skeleton. Pasquignon developed an erosion PDE with adaptive
stopping time that  allows one to compute directly a skeleton that does not look like barbed wire
\cite{Pasquignon:1995:CSP}.


\ifodd\count0
    \clearpage
    \leavevmode
    \thispagestyle{empty}
    \clearpage
\else\relax \fi
