%gmChap08.tex

\graphicspath{{./figures/chapter08/}}

\chapter{Erosions and Dilations}

We are going to study in detail two of the simplest operators of mathematical morphology. These are 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{Erosions and dilations as multiscale contrast-invariant monotone operators}

We saw in the last chapter that every contrast-invariant monotone function operator has a sup-inf and an inf-sup representation. We also saw that it was possible to define a contrast-invariant function operator in terms of a given 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 then consider the two operators
\[
T_d u(\fxx)=\sup_{\fxy\in\fxx+B}u(\fxy)\quad\text{ and }\quad T_e u(\fxx)=\inf_{\fxy\in\fxx+B}u(\fxy).
\]
The operator $T_d$ is called a dilation, and $T_e$ is called an erosion. These function operators have associated set operators, and in fact we are going to define the set operators first.

\begin{definition}Let $B$ be a subset of $\RR^N$ and let $t\geq0$ be a scale parameter. The set operators $\mathcal D_t$ and $\mathcal E_t$ are defined on subsets $X\in\mathcal P(\RR^N)$ by 
\begin{equation}\label{eq8.1}
\mathcal D_t X=X+tB=\{\fxz\mid\fxz=\fxx+\fxy, \fxx\in X, \fxy\in tB\}=\bigcup_{\fxy\in tB}(X+\fxy),
\end{equation}
and
\begin{equation}
\mathcal E_t X=\{\fxx\mid\fxx+tB\subset X\}=\bigcap_{\fxy\in-tB}(X+y).
\end{equation}
$\mathcal D_t X$ is called the dilation of $X$ with structuring element $B$ at scale $t$. $\mathcal E_t X$ is called the erosion of $X$ with structuring element $B$ at scale $t$.
\end{definition}

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 translation by $t\fxx_0$, and $\mathcal E_t=\mathcal D_t^{-1}$ is 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$ (see Exercise 7.3) the opening, then an opening at scale $t$ appears as a qualified opening. The topological statement ``the closure of the complement of $X$ is the complement of the interior of $X$'' has its counter part for openings and closings at scale $t$, as shown by the next exercise. The actions of erosions and dilations are illustrated in Figures 8.1, 8.2, and 8.5; actions of openings and closings are illustrated in Figures 8.3, 8.4, 8.6, 8.7, and 8.8.

\begin{figure}[!t]
\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{exercise}\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}

We are going to define the function operators that correspond to $\mathcal D_t$ and $\mathcal E_t$, but first we represent these set operators in the form given by equation \eqref{eq81}. This will give us more direct access to  results in Chapter 7. For this, we define $\mathcal B\,'=\{\{-\fxx\}\mid \fxx\in B\}$. Then,
\begin{equation}\label{eq8.3}
\mathcal D_t X=\bigcup_{C\in t\mathcal B\,'}\bigcap_{\fxy\in C}(X-\fxy)=\bigcup_{\fxy\in tB}(X+\fxy),
\end{equation}
and
\begin{equation}
\mathcal E_t X=\bigcup_{C\in t\mathcal B}\bigcap_{\fxy\in C}(X-\fxy)=\bigcap_{\fxy\in -tB}(X+\fxy).
\end{equation}

We now have at hand some of the machinery of Chapter 7. In particular, we can apply Proposition 7.2 and Exercise 7.5 to $\mathcal E_t$ and conclude that $\mathcal E_t$ is upper semicontinuous on $\mathcal P(\RR^N)$. On the other hand, we have evidence from Exercises 7.7 that $\mathcal D_t$ cannot be u.s.c.\ without restrictions on $B$ and $\mathcal L$. The first restriction we make is that both $\mathcal D_t$ and $\mathcal E_t$ map measurable sets into measurable sets. Without this assumption, or an assumption that implies this, much of the theory developed in Chapters 3, 6, and 7 is not available to us. Thus, we are going to assume that $\mathcal D_t$ and $\mathcal E_t$ are defined on a family of measurable sets $\mathcal L$ that is closed under descending chains. We further assume that $B$ is such that $\mathcal D_t X$ and $\mathcal E_t X$ are measurable when $X\in\mathcal L$. Now let $\mathcal F$ be the functions $u$ defined by $u(\fxx)=\sup\{\lambda\mid\fxx\in X_\lambda\}$, where $(X_\lambda)_{\lambda\in\RR}$ is a closed descending chain in $\mathcal L$. 

\begin{figure}[!t]
\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}


At this point there are two ways to proceed: We can define the corresponding functions operators directly as $T_d$ and $T_e$, or we can define them by superposition. We take the former definitions and then show their connection with superposition in the next theorem.

\begin{definition}For $u\in\mathcal F$, define $D_t u$ by
\begin{equation}
D_t u(\fxx)=\sup_{\fxy\in tB}u(\fxx-\fxy)
\end{equation}
and define $E_t u$ by
\begin{equation}
E_t u(\fxx)=\inf_{\fxy\in-tB}u(\fxx-\fxy).
\end{equation}
\end{definition}

\begin{theorem}For $u\in\mathcal F$,
\begin{equation}\label{E8.7}
D_t u(\fxx)=\sup\{\lambda\mid\fxx\in\mathcal D_t\levelset_{\lambda}u\}\; \text{ for a.e. }\fxx\in\RR^N,
\end{equation}
and
\begin{equation}\label{E8.8}
\mathcal D_t\levelset_{\lambda}u=\levelset_{\lambda}D_t u
\end{equation}
almost everywhere, except possibly for at most a countable number of $\lambda$'s. Similarly,
\begin{equation}\label{E8.9}
E_t u(\fxx)=\sup\{\lambda\mid\fxx\in\mathcal E_t\levelset_{\lambda}u\}\; \text{ for all }\fxx\in\RR^N,
\end{equation}
and
\begin{equation}\label{E8.10}
\mathcal E_t\levelset_{\lambda}u=\levelset_{\lambda}E_t u
\end{equation}
for all $\lambda\in\RR$.
\end{theorem}
\begin{proof}
Beginning with $\mathcal D_t$, let ${\tilde D}_t u(\fxx)=\sup\{\lambda\mid\fxx\in\mathcal D_t\levelset_{\lambda}u\}$. Then we know from equation \eqref{eq8.3} and Proposition 7.6 that
\begin{equation}\label{E8.11}
{\tilde D}_t u(\fxx)=\sup_{C\in\fxx+t\mathcal B\,'}\inf_{\fxy\in C}u(\fxx) 
\end{equation}
for a.e. $\fxx\in\RR^N$. The right-hand side of \eqref{E8.11} is easily seen to be the definition of $D_t$, so we have ${\tilde D}_t u(\fxx)=D_t u(\fxx)$ for a.e.\ $\fxx\in\RR^N$. This proves \eqref{E8.7}. This also implies that  $\levelset_{\lambda}{\tilde D}_t u=\levelset_{\lambda}{D}_t u$ almost everywhere. By Proposition 6.10, $\levelset_{\lambda}{\tilde D}_t u=\mathcal D_t\levelset_{\lambda}u$ almost everywhere, except possibly for at most a countable number of $\lambda$'s, and this proves \eqref{E8.8}.

The proofs of equations \eqref{E8.9} and \eqref{E8.10} follow the same arguments, except in this case the operator ${\mathcal E}_t$ is u.s.c.\ and we invoke Theorem 6.12 and Corollary 7.4.
\end{proof}
\begin{figure}[!t]
\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{exercise}
Show that $E_t(-u)=-D_t(u)$ if $B$ is symmetric with respect to zero. \finex
\end{exercise}

\begin{exercise}
Combine the results of Exercise 8.1 with the fact that $\mathcal E_t$ is u.s.c.\ to reveal a continuity property of $\mathcal D_t$. \finex
\end{exercise}

\begin{exercise}Let $u$ be a continuous real-valued function defined on $\RR^N$ and consider the dilation $\mathcal D_t$ associated with $B=\{\fxx\mid |\fxx|<1\}$. Check to be sure that $\mathcal D_t$ and $\mathcal E_t$ map measurable sets to measurable sets. Then Theorem 8.3 applies, and we know that $\mathcal D_t\levelset_{\lambda}u=\levelset_{\lambda}D_t u$ almost everywhere, except possibly for at most a countable number of $\lambda$'s. Show that $\mathcal D_t\levelset_{\lambda}u$ is open and that $\levelset_{\lambda}D_t u$ is closed. Deduce from this that the relation can hold for all $\fxx\in\RR^N$ only if both sets are equal to $\RR^N$ or are empty. \finex
\end{exercise}

We have by now seen plenty of evidence that $\mathcal D_t$ is not in general u.s.c., or equivalently, that $D_t$ does not commute with thresholds. There are, however, two simple restrictions on $B$ and $\mathcal L$ that ensure the upper semicontinuity of $\mathcal D_t$ on $\mathcal L$.

\begin{proposition}If either of the two conditions hold, then $\mathcal D_t$ is u.s.c.\ on $\mathcal L$.
\begin{enumerate}[$(i)$]\setlength\itemsep{2pt}
\item $B$ is compact and $\mathcal L$ is the set of closed subsets of $\RR^N$.
\item $B$ is closed and $\mathcal L$ is the set of compact subsets of $\RR^N$.
\end{enumerate}
\end{proposition}
\begin{proof}We are going to use Proposition 7.2. Thus assume that $(i)$ holds and that $(X_n)_{n\in\mathbb N}$ is a decreasing sequence in $\mathcal L$ such that $\bigcap_{n\in\mathbb N}\mathcal D_t X_n\ne\emptyset$. Let $\fxx$ be any element in $\bigcap_{n\in\mathbb N}\mathcal D_t X_n$. Then $\fxx\in\mathcal D_t X_n$ for all $n\in\mathbb N$, and so by definition there is a $b_n\in B$ such that $\fxx-tb_n\in X_n$. This means that $(\fxx-tB)\cap X_n$ is not empty for all $n$. Since $(\fxx-tB)\cap X_n$ is a decreasing sequence of compact sets, the intersection $\bigcap_{n\in\mathbb N}((\fxx-tB)\cap X_n)=(\fxx-tB)\cap\bigcap_{n\in\mathbb N}X_n$ is not empty. Thus there is a $b\in B$ such that $\fxx-tb\in\bigcap_{n\in\mathbb N}X_n$, and this, by Proposition 7.2, proves the result for $(i)$. The same argument proves the result for $(ii)$.
\end{proof}

The two conditions $(i)$ and $(ii)$ above are of course that same in case we replace $\RR^N$ with $\mathbb T^N$ or $\RR^{N*}$, which are the most interesting cases for image analysis. 

If $B$ is not symmetric with respect to zero, then there are in general two other function operators related naturally to $D_t$ and $E_t$. These are the operators $\displaystyle{D_t^-}$ and $\displaystyle{E_t^-}$ defined by
\begin{equation}
D^-_t u(\fxx)=-D_t(-u)(\fxx)=\inf_{\fxy\in tB}u(\fxx-\fxy)
\end{equation}
and
\begin{equation}
E^-_t u(\fxx)=-E_t(-u)(\fxx)=\sup_{\fxy\in -tB}u(\fxx-\fxy).
\end{equation}
Note that $D^-_t$ is an erosion and $E^-_t$ is a dilation. When $B$ is symmetric with respect to zero, we have $\displaystyle{D_t^-}=E_t$ and $\displaystyle{E_t^-}=D_t$.

\begin{figure}[!t]
\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}


\begin{proposition}Assume that $B$ is a compact subset of $\RR^N$ and let$\mathcal L$ be the family of closed subsets of $\RR^N$. Let $\mathcal F^+$ denote the set of upper semicontinuous function on $\RR^N$ and let $\mathcal F^-$ denote the set of lower semicontinuous function on $\RR^N$. Then for $u\in\mathcal F^+$, $\mathcal D_t\levelset_{\lambda}u=\levelset_{\lambda}D_t u$ and $\mathcal E_t\levelset_{\lambda}u=\levelset_{\lambda}E_t u$. If $u\in\mathcal F^-$, then  $\mathcal D_t\levelset_{\mu}^- u=\levelset_{\mu}^- D_t^- u$ and $\mathcal E_t\levelset_{\mu}^- u=\levelset_{\mu}^- E_t^- u$.
\end{proposition}
\begin{proof}We know from Proposition 8.4 that $\mathcal D_t$ is u.s.c.\ on $\mathcal L$. (That $\mathcal E_t$ is u.s.c.\ on $\mathcal L$ follows from Proposition 7.2.) The functions $u$ defined by $u(\fxx)=\sup\{\lambda\mid\fxx\in X_\lambda\}$ where $(X_\lambda)_{\lambda\in\RR}$ is a closed descending chain in $\mathcal L$ are exactly the u.s.c.\ functions $\mathcal F^+$, and the results for $u\in\mathcal F^+$ follow directly from Theorem 6.12. The results for $u\in\mathcal F^-$ are quickly obtained by applying the first results to $-u\in\mathcal F^+$.
\end{proof}

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 $\{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. For example, we have already seen in Chapters 2 the interest in studying that asymptotic behavior of operators $T_h$ that satisfy $(T_h)^n=T_{hn}$. Having $T_t=(T_{t/n})^n$ is also 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.

\begin{lemma}
$B$ is convex if and only if $(s+t)B=sB+tB$ for all $s,t\geq0$.
\end{lemma}
\begin{proof}Assume that $B$ is convex and take $\fxx,\fxy\in B$. Then $(s/(s+t))\fxx+(t/(s+t))\fxy\in B$, and this implies that $sB+tB\subset (s+t)B$. The inclusion in the other direction is obvious. Now assume that $(s+t)B=sB+tB$ and that $\fxx,\fxy\in B$. Then one can find $\fxz\in B$ such that $(s+t)\fxz=s\fxx+t\fxy$. This implies that $(s/(s+t))\fxx+(t/(s+t))\fxy\in B$. Since $s,t\geq0$ are arbitrary, it follows that $B$ is convex. 
\end{proof}

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\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}The dilations $\mathcal D_t$ and $D_t$ and the erosions $\mathcal E_t$ and $E_t$ are recursive if and only the structuring element $B$ is convex.
\end{proposition}
\begin{proof}We begin with the dilations $\mathcal D_t$. Using the definition \eqref{eq8.1}, 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$. This implies immediately that the dilations ${\tilde D}_t$ defined by superposition are recursive. However, since the $\mathcal D_t$ are not necessarily u.s.c., we can only conclude that $D_t D_s u(\fxx)= D_{s+t}u(\fxx)$ for a.e. $\fxx\in\RR^N$. Thus, we are going to prove that $D_t D_s=D_{s+t}$ directly from Definition 8.2.
\[
D_t D_s u(\fxx)=\sup_{\fxz\in tB}D_s u(\fxx-\fxz)=\sup_{\fxz\in tB}(\sup_{\fxy\in sB}u(\fxx-\fxz-\fxy))=\sup_{a\in B,b\in B}u(\fxx-(sa+tb)),
\]
and
\[
D_{s+t}u(\fxx)=\sup_{y\in(s+t)B}u(\fxx-\fxy)=\sup_{c\in B}u(\fxx-(s+t)c).
\]
If $(t+s)B=tB+sB$, then $D_t D_s u(\fxx)=D_{s+t}u(\fxx)$ for all $\fxx\in\RR$. Conversely, if $D_t D_s u(\fxx)=D_{s+t}u(\fxx)$, then by taking $u=\bmone_{\{0\}}$ we have see that $(t+s)B=tB+sB$.

A similar argument, this time taking $u=-\bmone_{\{0\}}$, shows that $E_t E_s=E_{s+t}$ if and only if $(t+s)B=tB+sB$. Since $\mathcal E_t$ is u.s.c., it follows directly from the relation $\mathcal E_t\levelset_{\lambda}u=\levelset_{\lambda}E_t u$ that $\mathcal E_t\mathcal E_s=\mathcal E_{s+t}$ if and only if $(t+s)B=tB+sB$. 
\end{proof}

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\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 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}

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]
\setkeys{Gin}{width=10cm}
\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}[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$. The same result hold when $D_t$ is replaced with $E_t$ and the equation is replaced with ${\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
\[
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|)$ for $\fxy\in hB$, and we have
\[
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{figure}[!t]
\setkeys{Gin}{width=10cm}
\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{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 among 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 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}. 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}.
