
\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}
 
