%gmChap16.tex

\graphicspath{{./figures/}}

\chapter[Curvature Equations]{Curvature Equations and Iterated Contrast-Invariant Operators
 \label{CurvatureequationsandIterated}}
 In this chapter, we apply the viscosity solution theory to the main curvature equations.   A
first important consistency  result is that the viscosity solutions are invariant under contrast changes (Proposition
\ref{proposition16.2}): If $u$ is a viscosity solution of a curvature equation, then, for any continuous contrast
change $g$, $g(u)$ is also a viscosity solution of the same equation.  Our second  main focus is to illustrate the
general principle that  ``iterated contrast invariant filters are asymptotically equivalent to a curvature equation."
We shall not prove this  principle in  whole generality. We shall limit ourselves to two cases which were proven of
great interest in image analysis.  The first example is the iterated median filter, which will be showed to converge to
a curvature equation. The second example is the iteration of alternate affine filters, which converges to the AMSS
equation.

\section{The main curvature equations used for image processing}

The curvature equation of most interest to image processing have
the general form
\begin{equation}\label{eq181}
\frac{\partial u}{\partial t}=|Du|\beta({\rm curv}(u))
\end{equation}
in two dimensions and the form
\begin{equation}\label{eq182}
\frac{\partial u}{\partial t}=|Du|\beta(\kappa_1(u),\kappa_2(u),\ldots,\kappa_{N-1}(u))
\end{equation}
in $N$ dimensions. The real-valued function $\beta$ is continuous
and nondecreasing with respect to each of its variables. The
$\kappa_i(u)$ denote the principal curvatures of the level surface
of $u$, defined as the eigenvalues of the
restriction of $\frac{D^2u}{|Du|}$ to the hyperplane orthogonal to $Du$ (see Definition \ref{definition4.19}.)

Here are some specific examples. In two dimensions, we have shown
that the equations
\begin{equation}\label{eq183}
\frac{\partial u}{\partial t}=|Du|{\rm curv}(u)
\end{equation}
and
\begin{equation}\label{eq184}
\frac{\partial u}{\partial t}=|Du|({\rm curv}(u))^{1/3},
\end{equation}
as well as variants like
\begin{equation}\label{eq185}
\frac{\partial u}{\partial t}=|Du|({\rm curv}(u)^+)^{1/3},
\end{equation}
are relevant for image processing. In three dimensions, we will be concerned with
\begin{equation}\label{eq186}
\frac{\partial u}{\partial t}=|Du|(\kappa_1(u)+\kappa_2(u)).
\end{equation}
This is the classical \textit{mean curvature motion} that is
important because it appears as a limit of iterated median
filters. Our assumptions also cover variants like
\begin{equation}\label{eq187}
\frac{\partial u}{\partial t}=|Du|\min(\kappa_1(u),\kappa_2(u)).
\end{equation}
This filter provides a less destructive smoothing of three-dimensional images than the mean curvature motion. Finally,
let us mention affine-invariant curvature motion, which is a particularly important equation in three dimensions:
\begin{equation}\label{eq188}
\frac{\partial u}{\partial t}={\rm
sgn}(\kappa_1)t^{1/2}|Du||G(u)^+|^{1/4}.
\end{equation}
The admissible functions $F$ for these equations were
listed in Section \ref{section15.1} and in the synoptic tables of Section \ref{sec:tables}.

\section{Contrast invariance and viscosity solutions}

We are going to show that the concepts of contrast invariance and viscosity solution are compatible. Proposition
\ref{proposition16.2} will show that f $u$ is a viscosity solution of \eqref{eq181} or \eqref{eq182}, then for all
continuous nondecreasing functions $g$, $g(u)$ is also a viscosity solution of the same equation.

\begin{lemma}\label{lemma16.1}Assume that $(A,p)\mapsto F(A,p)$ is an admissible function
 of the form $F(D^2(u),D(u))=|D(u)|\beta(\kappa_1(u),\kappa_2(u),\ldots,\kappa_{N-1}(u))
$ and that $g:\RR\to\RR$ is $C^2$ with $g'(s)>0$ for all $s\in\RR$.

\medskip

If $Du\not=0$, then
\begin{equation}\label{eq189}
F(D^2(g(u)),D(g(u)))=g'(u)F(D^2u,Du)
\end{equation}
for any $C^2$ function $u:\RR^N\to\RR$.

\medskip

If $D^2u=0$ and $Du=0$, then
\begin{equation}\label{eq1810}
F(D^2(g(u)),D(g(u)))=F(0,0)=0.
\end{equation}
\end{lemma}
\begin{proof}If $D(u)\not=0$, then we know from Proposition
 \ref{proposition4.16} that ${\rm curv}(g(u))={\rm curv}(u)$ in
 two dimensions and that $\kappa_i(g(u))=\kappa_i(u)$ in the
 $N$-dimensional case. Thus,
\begin{align*}
F(D^2(g(u)), D(g(u)))=&|D(g(u))|\beta(\kappa_1(g(u)),\kappa_2(g(u)),\ldots,\kappa_{N-1}(g(u)))\\
=&g'(u)|D(u)|\beta(\kappa_1(u),\kappa_2(u),\ldots,\kappa_{N-1}(u))\\
=&g'(u)F(D^2u, Du),
\end{align*}
as announced. In general, $D(g(u))=g'(u)Du$ and $$D^2(g(u))=g'(u)D^2u+g''(u)Du\otimes Du.$$ Thus, if $D^2u=0$
and $Du=0$, then $D^2(g(u))=0$ and $D(g(u))=0$, and
\[
F(D^2(g(u)),D(g(u)))=F(0,0)=0.
\]
\end{proof}
\vspace{-10pt}

\begin{exercise} Check the formula $D^2(g(u))=g'(u)D^2u+g''(u)Du\otimes Du.$
\finex
\end{exercise}

The proof of the next result, the main  one of this section, is slightly more involved because we drop the assumption
that $g'(s)>0$.
\begin{proposition}\label{proposition16.2}
Assume that $u$ is a viscosity solution
 of the equation
\[
\frac{\partial u}{\partial t}=F(D^2(u),D(u)),
\]
where $F$ satisfies the conditions of Lemma \ref{lemma16.1}. If
$g:\RR\to\RR$ is continuous and nondecreasing, then $g(u)$ is also
a viscosity solution of this equation.
\end{proposition}
\begin{proof}We begin by assuming that $g$ is $C^\infty$ and that $g'(s)>0$, and we write $f=g^{-1}$ for convenience. Let $(t,\fxx)$ be a strict local maximum of $g(u)-\varphi$. Without loss of generality, we can assume that $g(u(t,\fxx))-\varphi(t,\fxx)=0$: Just replace $\varphi$ with $\varphi-g(u(t,\fxx))$. Then $(t,\fxx)$ is also a strict local maximum of $u-f(\varphi)$. To see this, note that
\[
g(u(s,\fxy))-\varphi(s,\fxy)< g(u(t,\fxx))-\varphi(t,\fxx)=0
\]
for $(s,\fxy)$ sufficiently close to (but not equal to) $(t,\fxx)$. Thus,
\[
u(s,\fxy)<f(\varphi(s,\fxy))
\]
and
\[
u(s,\fxy)-f(\varphi(s,\fxy))<0=u(t,\fxx)-f(\varphi(t,\fxx)),
\]
again, for $(s,\fxy)$ sufficiently close to (but not equal to) $(t,\fxx)$.

Since $f(\varphi)$ is $C^\infty$ and $u$ is a viscosity solution, it follows from the definition of viscosity solution that, for $D(f(\varphi)(t,\fxx)\not=0$,
\[
\frac{\partial(f(\varphi))}{\partial t}(t,\fxx)\leq F(D^2(f(\varphi))(t,\fxx),D(f(\varphi))(t,\fxx)).
\]
This implies by Lemma \ref{lemma16.1} that
\[
f'(\varphi)\frac{\partial\varphi}{\partial t}(t,\fxx)\leq f'(\varphi)F(D^2(\varphi)(t,\fxx),D(\varphi)(t,\fxx));
\]
since $f'(s)>0$,
\[
\frac{\partial\varphi}{\partial t}(t,\fxx)\leq F(D^2(\varphi)(t,\fxx),D(\varphi)(t,\fxx)).
\]

If $D(f(\varphi))=0$ and $D^2(f(\varphi))=0$, then, by Definition
\ref{definition15.2}, $(\partial f(\varphi)/\partial
t)(t,\fxx)\leq0$, and so $(\partial\varphi/\partial
t)(t,\fxx)\leq0$. This proves that $g(u)$ is a viscosity
subsolution when $g\in C^\infty$ and $g'(s)>0$.

Now assume that $g$ is simply continuous and nondecreasing. We
replace $g$ with $g_\ve$, $\ve>0$, a $C^\infty$ function such that
$g'_\ve(s)\geq\ve$ and   $g_\ve\to g$ uniformly on compact subsets
of $\RR$ as $\ve\to0$. (See Exercise \ref{exercise16.1}.)

We know from Lemma \ref{lemma15.12} that there is a sequence of
points $(t_{\ve(k)},\fxx_{\ve(k)})$, $k\in\NN$, with the following
properties: $\ve(k)\to0$ as $k\to\infty$,
$(t_{\ve(k)},\fxx_{\ve(k)})\to(t,\fxx)$ as $k\to\infty$, and
$g_{\ve(k)}(u)-\varphi$ has a local maximum at
$(t_{\ve(k)},\fxx_{\ve(k)})$. (Having fixed this sequence, we will
now simplify the notation by writing $\ve(k)=\ve$.)

If $D\varphi(t,\fxx)\not=0$, then $D\varphi(t_\ve,\fxx_\ve)\not=0$ for all sufficiently small $\ve$, that is, all sufficiently large $k$. Since we have shown in the first part of the proof that $g_\ve(u)$ is a viscosity solution of
\[
\frac{\partial u}{\partial t}=F(D^2(u),D(u)),
\]
it follows from Lemma \ref{lemma15.3} that
\[
\frac{\partial\varphi}{\partial t}(t_\ve,\fxx_\ve)\leq F(D^2\varphi(t_\ve,\fxx_\ve),D\varphi(t_\ve,\fxx_\ve))
\]
for all sufficiently small $\ve$. Since both sides of this
inequality are continuous, we can pass to the limit as $\ve\to0$
and conclude that
\[
\frac{\partial\varphi}{\partial t}(t,\fxx)\leq F(D^2\varphi(t,\fxx),D\varphi(t,\fxx)).
\]
In case $D^2\varphi(t,\fxx)=0$ and $D\varphi(t,\fxx)=0$, we call on Lemma \ref{lemma15.4} and write
\[
\frac{\partial\varphi}{\partial t}(t_\ve,\fxx_\ve)\leq G^+(D^2\varphi(t_\ve,\fxx_\ve),D\varphi(t_\ve,\fxx_\ve)),
\]
where $G^+$ satisfies the conditions of Definition
\ref{definition15.1}. By passing to the limit and using the fact
that $G^+(0,0)=0$, we see that
\[
\frac{\partial\varphi}{\partial t}(t,\fxx)\leq0.
\]
This proves that $g(u)$ is a viscosity  subsolution of
$\partial\varphi/\partial t= F(D^2u,Du)$; the same proof adapts to
prove that it is a viscosity supersolution.
\end{proof}


 \section{Uniform continuity of approximate solutions}


\begin{lemma}
\label{continuiteent} Consider scaled monotone  translation invariant operators $T_h$ defined on the set of
Lipschitz functions on $\RR^N$. Assume that they commute with the addition of constants and that
   there exists a continuous real function, $\epsilon(t)$
  satisfying $\epsilon(0)=0$
and such that for $nh\leq t$,  $((T_h)^n(L|x|))(0)\leq
L\epsilon(t)$ and $((T_h)^n(-L|x|))(0)\geq -L\epsilon(t)$.  Then
for every $L$-Lipschitz function $u_0$, one has  $-L\epsilon(t)
\leq ((T_h)^nu_0)(\fxx) - u_0(\fxx) \leq L\epsilon(t)$.
\end{lemma}
\begin{proof} Since the operators $T_h$ commute with translations,
we can prove the statements in the case of $\fxx = 0$ without loss
of generality. Since $u_0$ is $L$-Lipschitz, we have
$$-L|\fxx|\leq u_0(\fxx)-u_0(0)\leq L|\fxx|$$
Applying $(T_h)^n$, using its monotonicity and its commutation
with the addition of
 constants and taking the value at 0,
$$((T_h)^n(-L\fxx))(0)\leq ((T_h)^nu_0)(0)-u_0(0) \leq ((T_h)^n(L\fxx))(0),$$
that is, by assumption if $nh\leq t$,
$$-L\epsilon(t)\leq ((T_h)^nu_0)(0)-u_0(0) \leq L\epsilon(t).$$
\end{proof}
\vspace{-10pt}
\begin{lemma} \index{uniform continuity of approximate solutions}
\label{uniformementequicontinue} Let $u_0(\fxx)$ be a Lipschitz
function on $\RR^N$.
  Let $T_h$ be a family of operators satisfying the assumptions of
Lemma \ref{continuiteent}. Assume in addition that the associated
function $\varepsilon(h)$ is concave near 0.
 Then the approximate solutions
$u_h(t,\fxx)$ associated with $T_h$ are uniformly equicontinuous when we restrict $t$ to the set $h\natural$. More
precisely, for all $n, m \in \natural$ and all $\fxx, \fxy$ in $\RR^N$,
\begin{equation} \label{equicont}
|u_h(nh,\fxx) - u_h(mh,\fxy)|\leq L|\fxx -\fxy| +
 \epsilon(|n-m|h). \end{equation}

We can extend $u_h$ into functions $\tilde u_h$ on $\RR^+\times\RR^N$ which  are uniformly equicontinuous. As a
consequence, there are sequences $u_{h_n}$, with $h_n\to 0$, which converge uniformly on every compact subset of
$\RR^+\times\RR^N$.
 \end{lemma}

\begin{proof}
 Since by definition $u_h (nh,\fxx) =
((T_h)^nu_0)(\fxx)$, the result is a direct consequence of Lemmas \ref{lemma6.5} and
\ref{continuiteent}~: By the first mentioned lemma, $$|u_h(nh,\fxx) -u_h(nh,\fxy)|\leq L|\fxx -\fxy| $$ and by the
second one applied with $(T_h)^{n-m}$,
$$
|u_h(nh,\fxx)-u_h(mh,\fxx)|=|((T_h)^{n-m}u_h(mh, .))(\fxx)
-u_h(mh,\fxx)| \leq \epsilon(|n-m|h).
$$
Thus,  we obtain \eqref{equicont} by remarking that
\begin{equation}\label{triangularinequality}
|u_h(nh,\fxx)-u_h(mh,\fxy)|\!
\leq \!|u_h(nh,\fxx)\!-\!u_h(nh,\fxy)|\! +\! |u_h(nh,\fxy)\!-\!u_h(mh,\fxy)|.\end{equation}

%%%%%%%%%%%%%%%%%
Consider the linear interpolation of $u_h$,
$$\tilde u_h(t,\fxx) = \frac{t-nh}h u_h((n+1)h,\fxx)+
\frac{(n+1)h-t}hu_h(nh,\fxx).$$ Since $\epsilon$ is concave, the function $\frac{\epsilon(h)}h$ is nonincreasing.
It follows that
\begin{equation}\label{inequalityuh1}|\tilde u_h(t,\fxy)-\tilde u_h(s,\fxy)|\leq
  \frac{\epsilon(h)}h |t-s|\leq \epsilon(|t-s|)\leq  \hbox{ for }
|t-s|\leq h\end{equation}
and
\begin{equation}\label{inequalityuh2}
|\tilde u(t,\fxy)-\tilde u(s,\fxy)|\leq 3\epsilon(|t-s|) \hbox{ for }
 |t-s|\geq h.\end{equation}
 (See Exercise \ref{proofofinequalitiesuhi}.)
By using again \eqref{triangularinequality} we conclude that
 the family of functions $\tilde u_h$ is uniformly equicontinuous
 on all of $[0, +\infty[\times\RR^N$.  Notice that
  $\tilde u_h(0,\fxx) = u_0(\fxx)$ is fixed. Thus,
we can apply Ascoli-Arzela Theorem which asserts that under such
conditions, the family of functions $\tilde u_h(t,\fxx)$ has a
subsequence converging uniformly on every compact set of $[0,
+\infty]\times\RR^N$ towards a uniformly continuous function
$u(t,\fxx)$. The same conclusion holds for $u_h(t,\fxx)$.
\end{proof}

\begin{exercise} \label{proofofinequalitiesuhi}Proof of \eqref{inequalityuh1}, \eqref{inequalityuh2}.
\newline a)
Assume first that $t, s$ belong to some $[nh, (n+1)h[$ and prove \eqref{inequalityuh1} in that case.
\newline b) Assume that $|t-s|\leq h$ and $t\leq nh\leq s$. By using $|u(t)-u(s)|\leq |u(t)-u(nh)|+|u(nh)-u(s)|$ prove
again \eqref{inequalityuh1}.
\newline c) If $|t-s|>h$ there are $m, n$ such that $(n-1)h\leq t<nh\leq mh\leq s<(m+1)h.$ By using again the triangular
inequality and the fact that $|(m-n)h|\leq |t-s|$ and $h<|t-s|$, prove \eqref{inequalityuh2}.
\finex
\end{exercise}

\begin{exercise} Consider the assumptions of Lemmas \label{uniformementequicontinue} and
  \ref{continuiteent} and see whether the results of these lemmas can be extended to the case where
$u_0$ is assumed to be uniformly continuous instead of Lipschitz. More precisely, assume
 that there exists a continuous increasing function $\varepsilon: \RR^+\to \RR^+$ such that
$\varepsilon(0)=0$ and $|u_0(\fxx)-u_0(\fxy)|\leq \varepsilon(||\fxx-\fxy||).$
Hint: use Corollary \ref{preservationuniformecontinuite}.

\finex
\end{exercise}


\section[Convergence of iterated median filters]
{Convergence of iterated median filters to the mean curvature motion}


We shall prove in  Theorem \ref{convergencemedianitere} one of the
main practical and theoretical results of this book~: the
iterated median filters converge to the mean curvature motion
equation. The action of iterated  median filters and the action of
the corresponding PDE are illustrated and compared in Figures
\ref{figure16.1} and \ref{figure16.2} and show how true this
theorem is.

\begin{figure}[!ht]
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig16.01.1.eps}
} \caption[Iterated Median Filter]{Scale-space  based on
iterations of the median filter. From left to right and top to
bottom: original shape, size of the disk used for the median
filter, and the results of applying the iterated median filter for
an increasing number of iterations.\label{figure16.1}}
\end{figure}

\begin{figure}[!ht]
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig16.02.1.eps}
} \caption[Comparing an iterated median filter with a curvature
motion]{Comparing an iterated median filter with a curvature
motion. Numerically, the iterated median filter and the curvature
motion must be very close, at least when the curvatures of the level lines are
not too small. Indeed, the iterated median filter converges
towards the curvature motion. Left: the initial
 shape of Figure \ref{figure16.1} has been smoothed by a finite difference scheme of the
curvature motion; middle: smoothing with a median filter at the
same scale; right: difference between left and middle images. The
difference is no greater than the width of one pixel. To have  a rigorous comparison,
 scales have been calibrated by ensuring
 that for  both
 schemes and all $r$ a circle with radius $r$ vanishes at scale $r$}
\label{figure16.2}\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{lemma} \index{approximation theory for the mean curvature motion}  \index{mean curvature motion!existence of viscosity solutions}
\label{controledumedianitere} (median filter) Let $k$ be a radial,
nonnegative, non separable, compactly supported function and
$k_h(\fxy) = \frac 1 {h^N}h(\frac \fxx h)$ the associated scaled
function. Assume, without loss of generality, that the support of
$k_h$ is $B(0,h)$ and consider the weighted median filter
associated with $k_h$, $T_hu(\fxx)=\fcnM_{k_h}u(\fxx)$. Set
$v_0(\fxx)=v_0(|\fxx|)=v_0(r)=Lr$. Then, if $nh^2\leq t$,
$$(T_h^nv)(0)\leq L\sqrt{2t} \hbox{ and } T_h^n(-v)(0)\geq -L\sqrt{2t}$$
\end{lemma}

\begin{proof} Let  us first estimate $T_hv(r)$ when
$v(\fxx)=v(|\fxx|)=v(r) $ is any radial nondecreasing function. To
this aim, let $\fxx$ be such that $|\fxx|=r$.  By the triangular
inequality, the sphere with center 0 and radius $\sqrt{r^2+h^2}$
divides the ball $B=B(\fxx, h)$ into two parts such that
\begin{equation} \label{median1} \hbox{meas}_{k_h}(\{\fxy,
|\fxy|\geq \sqrt{r^2+h^2}\}\cap B-\fxx)\leq
\hbox{meas}_{k_h}(\{\fxy, |\fxy|\leq \sqrt{r^2+h^2}\}\cap B-\fxx).
\end{equation}


\begin{figure}
\centerline{\hbox{ \epsfxsize=6cm \epsfbox{MedianItere.ps} }} \caption[Fig : Illustrating the inequality
(\ref{median1})]{ Illustrating the inequality (\ref{median1}). }
\end{figure}

\noindent As a consequence, $v$ being nondecreasing, we have
\begin{equation}
 \hbox{med}_{k_h} v(\fxx) \leq v(\sqrt{r^2+h^2}).
\label{median2} \end{equation} Let us set for brevity
$f_h(r)=\sqrt{r^2+h^2}$ and $r_{n+1}(r)=f_h(r_n)$, $r_0=r$. Then
we obviously have from (\ref{median2}) and the monotonicity of
$T_h$ \begin{equation} \label {median3} (T_h^nv)(r) \leq
v(r_n(r)).
\end{equation} In addition, since $\sqrt{r^2+h^2} \leq r+\frac
1{2r}h^2$ and $r_n$ is an increasing sequence, we obtain
$r_{n+1}\leq r_n + \frac {h^2}{2r_n} \leq r_n+\frac {h^2}{2r_0}$
and therefore \begin{equation}
 r_n\leq r+\frac{nh^2}{2r}.\label{median4}
\end{equation} Let us assume that $nh^2\leq t$.  Taking into account that
$v$ is a nondecreasing function, (\ref{median3}-\ref{median4})
yield \begin{equation} \label{median5} (T_h^nv)(r)\leq v(r+\frac
t{2r}).
\end{equation} Since $(T_h^nv)(r)$ is a nondecreasing function of
$r$, we deduce that $(T_h^nv)(r)\leq v(\sqrt{2t})$ if $r\leq
\sqrt{\frac t 2}$. Thus, if $v(r)=Lr$, we have for $nh^2\leq t$
$$(T_h^nv)(0) \leq L \sqrt {2t}.$$  The kernel $k_h$ being non separable,
the  second announced inequality comes from the self-duality of
the median, namely $T_h(-v)=-T_h(v)$.  Applying this iteratively
we deduce that $(T_h^n(-v))(0)=-T_h^nv(0)\geq - L(\sqrt{2t}).$

\end{proof}

\begin{exercise} Fill in the details of the arguments leading to Equations \eqref{median2} and \eqref{median3}.

\finex
\end{exercise}


\begin{theorem}\label{convergencemedianitere}  {\rm Convergence of iterated weighted median filter}.
 Let $k_h$ be either a $C^\infty$ compactly supported non separable radial
 function (in any dimension), or  the
uniform distribution on the unit disk in $\RR^2$.
   and  $(T_hu) =
\fcnM_{k_h}u$.  Let $u_0\in \mathcal F$. Then the approximate
solutions $u_h$ associated with $u_0$ and $\fcnM_{k_h}$ converge
to a viscosity solution $u$ of
    \begin{equation}\label{curvaturemotion}\frac {\partial u}{\partial t} =\frac 12
c_k|Du|{\rm curv}(u),\end{equation}
 where $c_k=\frac 13$ if $k$ is
the uniform measure on unit disk in $\RR^2$ and $c_k$ is the
constant specified in Lemma \ref{lemma11.2} otherwise.
Incidentally, this proves the existence of a (unique) viscosity
solution to the curvature equation.
\end{theorem}
\begin{proof}
  We know by Theorems \ref{theorem10.4} and \ref{theorem11.3} that
  the weighted median is
  uniformly  consistent
 with  \eqref{curvaturemotion}.   Bounds for the result of the
iterated filter $(T_h)^n$ applied to $+L|\fxx|$ and $-L|\fxx|$ have been computed in Lemma \ref
{controledumedianitere}, so that the assumption of Lemma \ref{continuiteent} is true. In addition, we know that
$\fcnM_{k_h}$ is monotone, satisfies the local comparison principle  \eqref{localmaximumprinciple}, commutes with
translations and the addition of constants. Thus, we can apply Lemma \ref {uniformementequicontinue} which asserts that
a subsequence of the approximate solutions $u_h$ converges uniformly on compact sets of $\RR^+\times\RR^N$ to a
function $u$. In addition, by Proposition \ref{limitedeuhestsolution},  $u$ is a viscosity solution of
\eqref{curvaturemotion}. Since by Theorem \ref{theorem15.14}, this solution is unique, we deduce that the whole
sequence  $u_h$ converges to $u$.  We have thus proved both existence of a viscosity solution for the mean curvature
motion and the convergence of the iterated median filters.
\end{proof}


\section[Convergence of iterated affine-invariant operators]{Convergence of iterated affine-invariant operators to affine-invariant curvature motion}
 \index{AMSS!existence of viscosity solutions}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In this section we consider any affine invariant contrast
invariant filter associated with an affine invariant,
1-localizable structuring set $\mathcal B$. Let
\[
IS_hu(\fxx)=\inf_{B\in h^\frac 32\mathcal
B}\sup_{\fxy\in\fxx+B}u(\fxy)\quad\text{and}\quad
SI_hu(\fxx)=\sup_{B\in h^\frac 32\mathcal
B}\inf_{\fxy\in\fxx+B}u(\fxy),
\]
and let $T_h$ denote one to the operators $IS_h$, $SI_h$, or
$SI_hIS_h$. We recall that we have defined  $u_h$, the approximate
solutions generated by $T_h$ with an initial function
$u_0\in\mathcal F$, by
$$ u_h(\fxx, (n+1)h) = T_h u_h(\fxx, nh),\quad
u_h(\fxx, 0) = u_0(\fxx).$$




\begin{theorem}\label{theorem2}
Let $\mathcal B$ an affine invariant, 1-localizable structuring
set  such that $c_{\mathcal B}^+>0$ and that  every $B\in \mathcal
B$ contains 0. Then the sequence $\{u_h\}$ converges, when $h\to
0$, uniformly on compact sets of $\RR^+\times \RR^2$ to the unique
viscosity solution $u$ of
\[
\frac{\partial u}{\partial t}=c_{\mathcal B}|Du|g({\rm curv}(u)),
\]
where
\begin{equation}\label{eq16x}
g(r)=
\begin{cases}
(r^+/2)^{1/3}\quad\text{if}\quad T_h=IS_h,\\
(r^-/2)^{1/3}\quad\text{if}\quad T_h=SI_h,\\
(r/2)^{1/3}\quad\text{ \;\,if}\quad T_h=SI_hIS_h,\\
\end{cases}
\end{equation}
and $c_{\mathcal B}=c_{\mathcal B}^+$.
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



By Barles-Souganidis principle, Theorem \ref{theorem2} essentially
is a consequence of Lemma \ref{lemma14.3?} and Theorem
\ref{Theorem14.4?}, which state a consistency result for the
schemes $SI_h$, $IS_h$, $SI_hIS_h$. In order to achieve the proof
of Theorem \ref{theorem2}, we need to check that the assumptions
of Lemma \ref{continuiteent} are satisfied.

\begin{lemma}
\label{iteratedaffinefilterbound} Consider any radial
nondecreasing   function $v(\fxx)=v(|\fxx|)=v(r)\geq 0$. Then for
$nh\leq t$,
$$0\leq ((IS_h)^nv)(0)\leq v(at+2a\sqrt t).$$

\end{lemma}

\begin{proof}  $(SI_h)^nv$ is easily shown to be radial and nondecreasing,
 like
 $v$.  Since $\mathcal B$ is localizable, it can be assumed to contain,
  by Lemma
 \ref{bornedanslocalisable},
    a square with area
 $a^2.$
   Set $\fxx= (r,0)$. Since $\mathcal B$ is affine invariant, $\mathcal
B_h=h^{\frac 32}\mathcal B$ contains a rectangle $R_h$ with sides
parallel to the axes, the side parallel to the $x$-axis having
length $ah$ and the other one $a^2h^{1\over 2}$.  Then
$$IS_hv(\fxx) \leq   \sup_{\fxx + R_h}v(\fxy).$$
Thus
\begin{equation} \label{iteratedaffine1} IS_hv(\fxx)\leq
v((r+{ah\over 2})^2+a^2h)^{\frac 1 2})
\end{equation}


\begin{figure}
\centerline{\hbox{ \epsfxsize=6cm \epsfbox{affi.ps} }} \caption[Fig : Illustration of the proof of the inequality
(\ref{ iteratedaffine1})]{Illustration of the proof of the inequality (\ref{ iteratedaffine1}).}
\end{figure}


We set for conciseness $f_h(r)=((r+{ah\over 2})^2+a^2h)^{\frac 1
2}$ and $r_{n+1}(r) = f_h(r_n), $ $r_0=r$. Since $IS_hv$ is a
radial nondecreasing function,  we can replace $v$ by $IS_hv$ in
(\ref{iteratedaffine1}). By the monotonicity of $IS_h$, we obtain

\begin{equation} \label{iteratedaffine2}
(T_h^nv)(r)\leq v(r_n(r))
\end{equation}
In addition, since
$(r^2+\varepsilon)^{\frac 1 2}\leq r + \frac 1 {2r}\varepsilon$
for all $r, \varepsilon > 0$, we have for $h\leq 1$
$$f_h(r)\leq (r^2+ ahr+ a^2h + \frac 1 4 a^2h^2)^{\frac 1 2}\leq (r^2+ 2a^2h + ahr)^{\frac 1
2}\leq r + \frac 1   {2r}(2a^2h+ahr),$$ which yields
\begin{equation}
\label{iteratedaffine3} f_h(r)\leq r+ah+{a^2h\over r}.
\end{equation}
Thus $r_{n+1}=f_h(r_n)\leq r_n+ah+ {a^2h\over
r_n}\leq r_n+ ah+{a^2h\over r}$, because $r_n$ is an increasing
sequence. Finally, $r_n\leq r + n(ah+ {a^2h\over r})$ and, by
(\ref{iteratedaffine2}),
$$(SI_h^nv)(r)\leq v(r+ n(ah + {a^2h\over r})).$$
Let us assume that $nh\leq t$.  Then
$$(SI_h^nv)(r)\leq v(r+ (a + {a^2\over r})t).$$
Considering that the minimum value of $r\to r+ (a+{a^2\over r})t$
is attained at $r=a\sqrt t$ and that $r\to (IS_h)^nv(r)$ is
nondecreasing, we obtain for $nh\leq  t$,
$$0\leq (IS_h^nv)(0) \leq v(2a\sqrt t + at).$$

\end{proof}
\begin{corollary} The operators $T_h=IS_h$, $SI_h$, $IS_hSI_h$ all
satisfy $$-v(at+2a\sqrt{t})\leq (T_h^nv)(0)\leq v(at+2a\sqrt{t})$$
for every continuous radial  nonincreasing function $v\geq 0$.
\end{corollary}

\begin{proof}  We claim
 that $SI_hv=v$. By Lemma \ref{bornedanslocalisable}, for
 every $\varepsilon$, $\mathcal B_h$ contains a
 rectangle whose side parallel to the $x$ axis has length
 $\varepsilon$. Thus
$$SI_hv(\fxx)\geq \inf_{\fxy\in\fxx+R_h}v(\fxy)=v(r-\frac
{\varepsilon}2)\to v(\fxx)\hbox{ as } \varepsilon \to 0.$$ Since
every $B\in\mathcal  B$ contains 0, we also have $SI_hv(\fxx)\leq
v(\fxx)$, which proves the claim.

Since $IS_hv$ is a radial nondecreasing continuous function like
$v$, we also have $SI_h(IS_hv)=IS_hv$ and by iterating and using
Lemma \ref{iteratedaffinefilterbound},
$$((SI_hIS_h)^nv)(0)= ((IS_h)^n)v(0)\leq v(at+2a\sqrt{t}).$$
 We also have by the same lemma,
$$((SI_hIS_h)^n(-v))(0)=-((IS_hSI_h)^nv)(0)=-((IS_h)^nv)(0)\geq
-v(at+2a\sqrt{t}.$$ Finally, $(SI_h)^nv=-(IS_h)^n(-v)$, which
yields the same inequalities for $(SI_h)^nv(0)$ as for
$(IS_h)^nv(0).$
\end{proof}



Figures \ref{figure16.3} and \ref{figure16.4} illustrate numerical
results showing that affine-invariant filters really are affine
invariant. A finite difference scheme is used to compute the
action of the PDE in Figure \ref{figure16.3}. Figure
\ref{figure16.4} illustrates the same invariance using an
iterated. inf-sup operator.
\begin{figure}[!h]
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig16.03.1.eps}
} \caption[Affine invariance of (AMSS)]{Affine invariance of
(AMSS). We check the affine invariance of the affine and
morphological scale space (AMSS). A simple shape (top-left) is
smoothed using a finite differences discretization of (AMSS)
followed by thresholding (bottom-left). We apply an affine
transform, with determinant equal to 1,  on the same shape
(top-right), then the same smoothing process (middle-right), and
finally the inverse of the affine transform (down-right). The
final results of both processes are experimentally equal.
\label{affineamss}}\label{figure16.3}
\end{figure}

\begin{figure}[!h]
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig16.04.1.eps}
} \caption[Affine inf-sup]{Checking the invariance of an
affine-invariant inf-sup operator. The images are the final
outcomes of the same comparison process shown in Figure
\ref{affineamss}, with $T$ replaced with an affine-invariant
inf-sup operator. The structuring  set $\mathcal B$ is an
approximately affine-invariant set of 49 ellipses, all with same
area. The inf-sup computation is costly and proves to be less
affine invariant than the one obtained by a finite difference
scheme. This is due to grid effects.}\label{figure16.4}
\end{figure}



\begin{proof} [of Theorem \ref{theorem2}]

 By Lemma \ref{consistenceaffine1}, Theorem
\ref{consistenceaffine2} and Theorem \ref{affinelocalcomparison} the
operators $T_h$ are consistent with their corresponding partial
differential equations $\frac{\partial u}{\partial t}=c_{\mathcal
B}|Du|g({\rm curv}(u))$,
 and satisfy  a uniform local
maximum principle.  Being  contrast invariant, they commute with
the addition of constants. Thus, by Proposition
\ref{limitedeuhestsolution}, if a sequence of approximate
uniformly continuous solutions $u_{h_n}$ converges uniformly on every
compact set to a function $u$,  then $u$ is a viscosity solution
of  (\ref{equationgeneralesanst}).
\newline
By Lemmas \ref{uniformementequicontinue} and
\ref{iteratedaffinefilterbound}, the approximate solutions $u_h$
are  equicontinuous on every compact set of $\RR^+\times\RR^N$ and
therefore
 have subsequences which
  converge uniformly to a function $u$ on every compact subset of
$\RR^+\times\RR^N$. Thus, $u$  is a viscosity solution. In
addition, we know that a viscosity solution of \eqref{eq16x} is
unique (Theorem \ref{theorem15.14}).  Thus the limit $u$ does not
depend on the particular considered subsequence and the whole
sequence $u_h$ converges to $u$.  So we have  proven both the
existence of a viscosity solution for the affine invariant equations
and the convergence of $u_h$ to this solution.
\end{proof}

\section{Exercises}


\begin{exercise}\label{exercise16.1}
Let  $g:\RR\to  \RR$ be  continuous and nondecreasing and set
\[
g_\ve(s)=\int_\RR\psi_\ve(s-t)(g(t)+\ve t)\,\rmd t,
\]
where the support of  $\psi_\ve$ is in $[-\ve,\ve]$, $\psi_\ve$ is
$C^\infty$, $\psi_\ve(s)\geq0$, and $\int_\RR\psi_\ve(t)\,\rmd
t=1$. Show that $g_\ve$ is $C^\infty$, that $g'_\ve(s)\geq\ve$,
and that $g_\ve\to g$ uniformly on compact subsets of $\RR$ as
$\ve\to0$. \finex
\end{exercise}

\section{Comments and references}

The existence and uniqueness theory for the viscosity solutions of
mean curvature motion and the relations of these solutions with
other kinds of solutions (classical, variational) was developed
independently by Evans and Spruck
\cite{Evans:1991:MLS,C:1992:MLSa,C:1992:MLSb,C:1995:MLS} and by
Chen, Gigo, and Goto \cite{Chen:1989:UEV,Chen:1991:UEV}. We do not
follow their existence proofs, but rather the elegant numerical
approximation schemes invented  by Merriman, Bence, and Osher
\cite{Merriman:1992:DGM} and the subsequent convergence proof to
the viscosity solution by Barles and Georgelin
\cite{Barles:1995:SPC}. Other proofs of the convergence of the iterated Gaussian
median filter toward the mean curvature equation are given in
\cite{Evans:1993:CAM} using semigroups and by Ishii
\cite{Ishii:1994:GBM}. Finally, we note the importance of iterated
median filters for denoising applications \cite{Arce:1988:SAR} and
\cite{Ip:1983:INC}.


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