%gmChap15.tex

\graphicspath{{./figures/}}
%\graphicspath{{./guichard_morel/}}

\chapter{Viscosity Solutions\label{Chapviscositysolutions}}

This book is about  image analysis and PDEs, and one of the main
ideas we wish to convey is that the operators we have studied are
closely associated with certain differential equations. What is
more, we wish to show that whole groups of operators can be
associated with essentially the same equation. For example, in
Theorem \ref{theorem2.3} we proved that there were many linear
operators that converged asymptotically to the heat equation, and
in section \ref{section8.2} we showed how dilations and erosions
are associated with the equations $\partial u/\partial t=\pm|Du|$.
There is, however, a gap to fill. As Figures \ref{figure15.1} and
\ref{figure15.2} illustrate, applying dilations and erosions to
smooth functions can produce functions that are no longer $C^1$
and, hence, cannot satisfy $\partial u/\partial t=\pm|Du|$ in the
usual, or classical, sense. The notion of viscosity solution,
which is a late twentieth-century development, provides a way to
close this gap. In this chapter, we introduce viscosity solutions,
show that classical solutions are viscosity solutions, and quote a
uniqueness theorem. We close the gap in the next chapter by
showing that the approximate solutions generated by the iterated
filters we have studied do indeed converge to viscosity solutions
of their associated PDEs.

\section{Definition and main properties\label{section15.1}}

The functions  $u(t,\fxx)$ defined on $[0,\infty)\times\RR^N$ will always be continuous. If $u$ is $C^2$, then $Du$ and
$D^2u$ denote the first and second derivatives of $u$ with respect to $\fxx\in\RR^N$; $Du$ is an $N$-dimensional vector
and $D^2u$ is an $N\times N$ matrix. The operators $\tilde{D}$ and $\tilde{D}^2$ are the first and second derivatives
of $u$ involving both variables $t$ and $\fxx$.
 If $\fxx\in\RR^N$ is represented in an orthonormal basis by
$\fxx=(x_1,x_2,\ldots,x_N)$, then the elements of $D^2u$ are $u_{ij}=\partial^2u/\partial x_i\partial x_j$, and $D^2u$
is symmetric. Symmetric matrices and their associated quadratic forms play a central role in this chapter because they
can be ordered. A real symmetric matrix $A=(a_{ij})_{1\leq i,j\leq N}$ is said to be nonnegative if its associated
quadratic form is nonnegative, that is, if
\[
A(\fxz,\fxz)=\sum_{i,j=1}^Na_{ij}\fxz_i\fxz_j\geq0
\]
for all $\fxz\in\RR^N$. This is equivalent to saying that all of the eigenvalues of $A$ are greater than or equal to
zero. We say that $A\geq B$ if $A-B\geq0$. The parabolic PDEs that we consider are of the form $$\partial u/\partial
t=F(D^2u, Du, \fxx, t),$$ where $(A,p,\fxx,t)\mapsto F(A,p,\fxx,t)$ is real-valued and continuous on its domain of
definition. We also assume that $F$ is nondecreasing with respect to its first argument. What we mean by this is that,
for all $A$, $B$, $p$, $\fxx$, and $t$ in the domain of definition,
\begin{equation}\label{eq171}
A\geq B \Longrightarrow F(A,p,\fxx,t)\geq F(B,p,\fxx,t).
\end{equation}

The functions $F$  we consider fall into two classes that are
characterized by the domains of definition. In one case, $F$ is
defined for all real-valued $N\times N$ symmetric matrices $A$,
all $p\in\RR^N$, all $\fxx\in\RR$, and all $t\in[0,\infty)$. We
denote this domain by $\mathbb D^N$. If we denote the
$N(N-1)/2$-dimensional space of symmetric $N\times N$ matrices by
${\mathbb S}^N$, then
\[
\mathbb D^N={\mathbb S}^N\times\RR^N\times\RR\times[0,\infty).
\]
In the other case, $F$ is defined on
\[
{\tilde{\mathbb D}}^N={\mathbb S}^N\times(\RR^N\setminus\{0\})\times\RR\times[0,\infty),
\]
where $\RR^N\setminus\{0\}$ is $\RR^N$ with the origin removed. It is important to deal with functions $F$ that are
defined on ${\tilde{\mathbb D}}^N$ rather than ${\mathbb D}^N$ because this is the case for one of the most relevant
equations in the book, namely, the curvature equation $\partial u/\partial t=|Du|{\rm curv}(u)$. (Note that we have
shifted the notation: In this chapter, $p=Du$ rather than $p=|Du|$ as before.) It is this dichotomy of domains that
motivates the following definition.

\begin{figure}[!t] \label{figure15.1}
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig15.01.1.eps}
}
\caption[Erosions and dilations can create singularities]{Erosions and dilations can create singularities. Top-left: original $C^\infty$ image.  Below: representation of the intensity along the horizontal axis. Middle: dilation with a circle of 30 pixels. Below: at the central point, the image is no longer $C^\infty$ or even $C^1$. Right: erosion with the same circle. Below: some loss of regularity; the solution is no longer $C^2$.
}
\end{figure}

\begin{definition} \label{definition15.1}We say that a
function $F$ is admissible if it is defined and continuous on ${\mathbb D}^N$ or ${\tilde{\mathbb D}}^N$, if it satisfies \eqref{eq171}, and if it satisfies the following conditions: There exists two continuous functions $G^+$ and $G^-$ defined on ${\mathbb D}^N$ such that
\begin{equation}\label{eq172}
\begin{aligned}
&G^+(0,0,\fxx,t)=G^-(0,0,\fxx,t)=0,\\
&G^+(A,0,\fxx,t)\geq0\quad \text{and}\quad G^-(-A,0,\fxx,t)\leq0\quad \text{for all}\quad A\geq0,\\
&G^-(A,p,\fxx,t)\leq F(A,p,\fxx,t)\leq G^+(A,p,\fxx,t),
\end{aligned}
\end{equation}
for all $(A,p,\fxx,t)$ in the domain of $F$.
\end{definition}

If $F$ is defined and continuous on ${\mathbb D}^N$, if $F$
satisfies \eqref{eq171}, and if $F(0,0,\fxx,t)=0$, then $F$ is
admissible: Just let $G^\pm=F$. Conversely, if $F$ is admissible
and defined on ${\mathbb D}^N$, then $F$ is continuous at
$(0,0,\fxx,t)$ by definition, and the last line of \eqref{eq172}
implies that $F(0,0,\fxx,t)=0$.

We are going to illustrate this  definition by describing the functions $F$ that are associated with the PDEs that we
have studied and that are of particular interest for image processing. This list will also serve as a reference for
this and the next chapter.

\begin{enumerate}[$\bullet$]\setlength\itemsep{2pt}
\item $F(A,p)=|p|$ or $F(A,p)=-|p|$. These functions are related to dilations and erosions and are associated with the equations $\partial u/\partial t=|Du|$ and $\partial u/\partial t=-|Du|$. They are clearly admissible.
\item $F(A,p)={\rm trace}(A)={\rm Tr}(A)$. This is associated with the heat equation $\partial u/\partial t=\Delta u$. $F$ is defined and continuous on $\mathbb D^N$. Since  ${\rm Tr}(A+B)={\rm Tr}(A)+{\rm Tr}(B)$ and ${\rm Tr}(A)\geq0$ for $A\geq0$, it follows that $F$ satisfies \eqref{eq171}. It satisfies \eqref{eq172} by taking $G^\pm=F$.
\item $F(A,p)={A(p^\perp/|p|,p^\perp/|p|)}$, which in two dimensions is
\[
F(A,p)=\frac{p_1^2a_{22}-2p_1p_2a_{12}+p_2^2a_{11}}{|p|^2}.
\]
This function is linked to the curvature equation $\partial u/\partial t=|Du|{\rm curv(u)}$. It is defined and
continuous on $\tilde{\mathbb D}^N$. It clearly satisfies \eqref{eq171}. To see that it satisfies \eqref{eq172}, take
for $G^+(A)$ the largest eigenvalue of $A$ and for $G^-(A)$ the smallest eigenvalue of $A$. \item
$F(A,p)=(A(p^\perp,p^\perp))^{1/3}$. This function is related to affine-invariant smoothing and is associated with the
equation
\begin{equation}\label{eq173}
\frac{\partial u}{\partial t}=|Du|({\rm curv}(u))^{1/3}.
\end{equation}
This function is  defined and continuous on $\mathbb D^N$ and
clearly satisfies \eqref{eq171}. It satisfies \eqref{eq172} by
taking $G^\pm=F$. \item $F(A,p)=((A(p^\perp,p^\perp))^+)^{1/3}$ is
associated with ${\partial u}/{\partial t}=|Du|({\rm
curv}(u)^+)^{1/3}$. Once we note that the operation $f\mapsto f^+$
preserves continuity and order, the argument in the last item
shows that $F$ is admissible. \item $F(A,p)={\rm
Tr}(A)-A(p/|p|,p/|p|)$ is associated with
\[
\frac{\partial u}{\partial t}=|Du|\Big(\sum_{i=1}^{N-1}\kappa_i(u)\Big),
\]
where the $\kappa_i(u)$ are the principal curvatures of $u$ (see Proposition
\ref{linkmeancurvatureprincipalcurvatures}). In other words, this is the equation for mean curvature motion. $F$ is
defined and continuous on $\tilde{\mathbb D}^N$, and it is easy to see that $F(A,p)\geq0$ for $A\geq0$. It follows from
this that $F$ satisfies \eqref{eq171}. To satisfy \eqref{eq172}, we can take $G^+(A)=(N-1)(\text{maximum eigenvalue
of}\, A)$ and $G^-(A)=(N-1)(\text{minimum eigenvalue of}\, A)$.
\item $F(A,p)=\min_{p}A(p^\perp/|p|,p^\perp/|p|)$ is associated with ${\partial u}/{\partial t}=|Du|\min\{\kappa_1,\kappa_2\}$ in three dimensions.
\end{enumerate}

These functions $F$ and their corresponding PDE's and filters are summarized  in the tables of Section
\ref{sec:tables}.
\begin{exercise}
Let $A$ be a symmetric matrix (in $\mathbb S^N$).  Show  that its maximal eigenvalue is equal to
$\lambda_1(A)=\max_{\fxx, |\fxx|=1} A(\fxx, \fxx)$ and its minimal eigenvalue to $\lambda_N=\min_{\fxx,
|\fxx|=1}A(\fxx, \fxx).$ Deduce that $\lambda_1(A)$ and $\lambda_N(A)$ are continuous and monotone functions of $A$.
\finex\end{exercise}

\begin{exercise}
Prove that $F(A,p)={\rm Tr}(A)-A(p/|p|,p/|p|)$ is monotone with respect to  $A$. (Since this function is linear in $A$
it is enough to prove that $A\geq 0\Rightarrow F(A,p)\geq 0.$) \finex
\end{exercise}


\begin{figure}[!t]\label{figure15.2}
\setkeys{Gin}{width=8cm}
\centerline{
\includegraphics{fig15.02.1.eps}
} \caption[Erosion and dilation can generate singularities within
the level lines] {Erosion and dilation can generate singularities
within the level lines. Left: original image where the only
level-line, corresponding to the boundary of the black shape, is
$C^1$. Right: erosion with a circle of radius 10; the resulting
level lines have sharp angles. }
\end{figure}

\medskip\noindent{\bf Solutions to the considered PDE's are not
 classical solutions}
\newline
We are going to define viscosity solutions for these and other PDEs, but before doing so it is useful to say a few
words about solutions in general. It would be convenient to define solutions to the equations listed above by saying
that any $u$ that is $C^2$ on $\RR^N$ and $C^1$ on $[0,\infty)$ and satisfies $\partial u/\partial t=F(D^2u,Du,\fxx,t)$
at all points $(t,\fxx)$ is a solution. Indeed, we call such a $u$ a \textit{classical} solution. This definition works
well, for example, for the heat equation, where we have shown the existence of classical solutions (Chapter
\ref{Chap1}.)

\medskip There are, however, among the equations listed above, those
for which a $C^2$ solution, or even a $C^1$ solution, cannot be expected. Here is an example where an ostensibly
classical solution is not the correct one and violates the comparison principle, which says that $v_0\geq u_0$ implies
that $v\geq u$. Let $u_0(\fxx)=-|\fxx|$ be the initial condition. Then one is tempted to take as a solution for the
equation $\partial u/\partial t=|Du|$ the function $\tilde{u}(t,\fxx)= t-|\fxx|$. Indeed, for all $t\geq0$ and all
$\fxx\not=0$, $\partial\tilde{u}/\partial t=1=|D\tilde{u}|$. However, this ``solution'' violates the comparison
principle. This can be checked by comparing it with the $C^{\infty}$ solution of the same equation with initial
condition $v_0(\fxx)\equiv0$, which is clearly $v(t,\fxx)\equiv0$. The correct comparison-preserving solution is
$u(t,\fxx)=\min\{0,t-|\fxx|\}$.

\medskip Another way in which we can point out  this difficulty is
to invoke  the contrast invariance: Let $g:\RR\to\RR$ be a nondecreasing continuous function that is not $C^1$, and let
$u_0(\fxx)$, $\fxx\in\RR^N$, be the initial data. Assume that we have been able to define a classical solution $u$ for
a curvature equation like \eqref{eq173} (or, in $\RR^N$, a mean curvature motion equation) that satisfies the initial
condition $u(0,\fxx)=u_0(\fxx)$. Then it is reasonable to expect that $g(u)$ will be a solution of the same equation
with initial condition $g(u_0)$. Since $g$ is not $C^1$, we cannot expect  this solution to be $C^1$. The most we can
expect is that it is continuous.

\medskip In order  to define  an irregular function $u$ as a solution of a
PDE, the clever idea is to involve the  local comparison
principle, as was hinted in the example above.  The correct
irregular solution will be defined and singled out thanks to its
comparison with local classical solutions of the PDE. This idea is
made precise in the next definition.

\begin{definition}[viscosity solution]\label{definition15.2}$F$ is assumed to be an admissible function, and $u:[0,\infty)\times\RR^N\to\RR$ is assumed to be continuous. We say that $u$ is a viscosity subsolution of the equation
\begin{equation}\label{eq174}
\frac{\partial u}{\partial t}(t,\fxx)-F(D^2u(t,\fxx),Du(t,\fxx),\fxx,t)=0
\end{equation}
at the point $\fxx_0$ and scale $t_0$ if, for all $\varphi\in C^\infty([0,\infty)\times\RR^N)$ for which $(t_0,\fxx_0)$ is a strict local maximum of $u-\varphi$, the following conditions are true$:$

If $D\varphi(t_0,\fxx_0)\not=0$, then
\begin{equation}\label{eq175}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)-F(D^2\varphi(t_0,\fxx_0),D\varphi(t_0,\fxx_0),\fxx_0,t_0)\leq0.
\end{equation}

If $D\varphi(t_0,\fxx_0)=0$ and $D^2\varphi(t_0,\fxx_0)=0$, then
\begin{equation}\label{eq176}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)\leq0.
\end{equation}


Similarly, $u$ is a viscosity supersolution at $(t_0,\fxx_0)$ if,
for all $\varphi\in C^\infty([0,\infty)\times\RR^N)$ for which
$(t_0,\fxx_0)$ is a strict local minimum of $u-\varphi$, the
following conditions are true$:$

If $D\varphi(t_0,\fxx_0)\not=0$, then
\begin{equation}\label{eq177}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)-F(D^2\varphi(t_0,\fxx_0),D\varphi(t_0,\fxx_0),\fxx_0,t_0)\geq0.
\end{equation}

If $D\varphi(t_0,\fxx_0)=0$ and $D^2\varphi(t_0,\fxx_0)=0$, then
\begin{equation}\label{eq178}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)\geq0.
\end{equation}

The function $u$ is said to be a viscosity solution at the point
$\fxx_0$ and scale $t_0$ if it is both a viscosity subsolution and
supersolution. If $u$ is a viscosity solution of \eqref{eq174} at
every point of $[0,\infty)\times\RR^N$ and if
$u(0,\fxx)=u_0(\fxx)$, we say that $u$ is a viscosity solution of
\eqref{eq174} with initial condition $u_0$.
\end{definition}

One of the first things we must do is to show that a classical solution of \eqref{eq174} is a viscosity solution. This
will be done in Proposition \ref{proposition15.6}, but before tackling this issue, we present several lemmas that
significantly simplify the task of showing that a function is a viscosity solution. We will prove these lemmas for
subsolutions; all of the statements and proofs regarding subsolutions are true for supersolutions with the obvious
modifications. The first step is to drop the requirement that the extrema be strict.

\begin{lemma}\label{lemma15.3}
A continuous function $u:[0,\infty)\times\RR^N\to\RR$ is a
viscosity subsolution of \eqref{eq174} at $(t_0,\fxx_0)$ if and
only if the following condition is true. If $\varphi$ is in
$C^\infty([0,\infty)\times\RR^N)$ and $u-\varphi$ has a local
maximum $($not necessarily strict$)$ at $(t_0,\fxx_0)$, then
\eqref{eq175} and \eqref{eq176} hold. A similar statement is true
for viscosity supersolutions.
\end{lemma}
\begin{proof}
Assume that $u$ is a viscosity subsolution and that $u-\varphi$
has a local maximum at $(t_0,\fxx_0)$. Replace $\varphi$ with
$\psi$, where
$\psi(t,\fxx)=\varphi(t,\fxx)+(t-t_0)^4+|\fxx-\fxx_0|^4$. Then
$u-\psi$ has a strict local maximum at $(t_0,\fxx_0)$, and  $\psi$
satisfies \eqref{eq175} and \eqref{eq176} by definition. Since the
first and second derivatives of $\varphi$ and $\psi$ agree at
$(t_0,\fxx_0)$, $\varphi$ satisfies \eqref{eq175} and
\eqref{eq176}. The implication in the other direction is just a
matter of noting that ``local maximum'' includes ``strict local
maximum.''
\end{proof}

The relations \eqref{eq175}-\eqref{eq178} do not ask for a bound of $\partial\varphi/\partial t$ in case $D\varphi=0$
and $D^2\varphi\not=0$.  This is due to the possibility that $F$ is defined on ${\tilde{\mathbb D}}^N$ and cannot be
continued continuously at $p=0$. The next lemma provides an equivalent and useful definition of a viscosity solution.

\begin{lemma}\label{lemma15.4}Assume that $F$ is admissible and that $G^+$ and $G^-$ are any two continuous functions that satisfy
 the conditions of \eqref{eq172}. A continuous function $u$ is a viscosity subsolution of \eqref{eq174} at a point $(t_0,\fxx_0)$
 if and only if, for all $\varphi\in C^\infty([0,\infty)\times\RR^N)$ for which $(t_0,\fxx_0)$ is a strict local maximum of $u-\varphi$,
  $\varphi$ satisfies \eqref{eq175} if $D\varphi(t_0,\fxx_0)\neq 0$ and
\begin{equation}\label{eq179}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)-G^+(D^2\varphi(t_0,\fxx_0),D\varphi(t_0,\fxx_0),\fxx_0,t_0)\leq0.
\end{equation}
Similarly, $u$ is a viscosity supersolution of \eqref{eq174} at a point $(t_0,\fxx_0)$ if and only if, for all $\varphi$
 for which $(t_0,\fxx_0)$ is a strict local minimum of $u-\varphi$, $\varphi$ satisfies \eqref{eq177} if $D\varphi(t_0,\fxx_0)\neq 0$ and
\begin{equation}\label{eq1710}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)-G^-(D^2\varphi(t_0,\fxx_0),D\varphi(t_0,\fxx_0),\fxx_0,t_0)\geq0.
\end{equation}
Thus when $F$ is continuous \eqref{eq175} and \eqref{eq177} are true even if $D\varphi(t_0,\fxx_0)=0$.
\end{lemma}
\begin{proof}
The last statement is an immediate consequence of the other parts
of the lemma. We will prove only the ``subsolution'' half of the
lemma. In one direction, we assume \eqref{eq175} and
\eqref{eq179}. Then to show that the lemma implies the definition,
we need only show that \eqref{eq176} holds. But this follows
immediately from \eqref{eq179} and the fact that
$G^+(0,0,\fxx,t)=0$.

To  prove the converse, assume that $u$ is a viscosity subsolution in the sense of Definition \ref{definition15.2},
that is, it satisfies \eqref{eq175} and \eqref{eq176}, and assume that $\varphi$ is a $C^\infty$ function such that
$u-\varphi$ has a strict maximum at $(t_0,\fxx_0)$. We must prove that \eqref{eq179} is true for any continuous $G^+$
that satisfies conditions \eqref{eq172}. We assume that $D\varphi(t_0,\fxx_0)=0$ and $D^2\varphi(t_0,\fxx_0)\not=0$,
since the other cases follow immediately.

Consider the function $\psi_\ve$ defined by
\[
\psi_\ve(t,\fxx,\fxy)=u(t,\fxx)-\varphi(t,\fxy)-\frac{|\fxx-\fxy|^4}{\ve},\quad\ve>0.
\]
Since $u-\varphi$ has a strict maximum at $(t_0,\fxx_0)$, it is possible to show that, for every sufficiently small
$\ve$, there is a $(t_{\ve},\fxx_{\ve},\fxy_{\ve})$ where the function $\psi_\ve$ has a local maximum (Exercise
\ref{exercise15.1}). Furthermore, $(t_{\ve},\fxx_{\ve},\fxy_{\ve})\to(t_0,\fxx_0,\fxx_0)$ as $\ve\to0$. (The points
$(t_{\ve},\fxx_{\ve},\fxy_{\ve})$ may not be unique, so assume that we have selected one for each sufficiently small
$\ve$.)


If we fix $\fxx=\fxx_{\ve}$, then the function
$\psi_{\ve,\fxx_{\ve}}:(t,\fxx_{\ve},\fxy)\mapsto
\psi_{\ve}(t,\fxx_{\ve},\fxy)$ is $C^\infty$ with respect to
$\fxy$ and has a local maximum at the point
$(t_{\ve},\fxy_{\ve})$.

This implies that
$D\psi_{\ve,\fxx_{\ve}}(t_{\ve},\fxx_{\ve},\fxy_{\ve})=0$ and that
$D^2\psi_{\ve,\fxx_{\ve}}(t_{\ve},\fxx_{\ve},\fxy_{\ve})\leq0$. By
computing $D\psi_{\ve,\fxx_{\ve}}$ and $D^2\psi_{\ve,\fxx_{\ve}}$
and using these relations, we see that
\[
D\varphi(t_\ve,\fxy_\ve)=\frac{4(\fxx_\ve-\fxy_\ve)|\fxx_\ve-\fxy_\ve|^2}{\ve}
\]
and
\begin{equation}\label{inequalitypowerfour}
D^2\varphi(t_\ve,\fxy_\ve)\geq-\frac1{\ve}(4|\fxx_\ve-\fxy_\ve|^2{I}+8A),
\end{equation}
where ${I}$ is the identity matrix and
$A=(\fxx_\ve-\fxy_\ve)\otimes(\fxx_\ve-\fxy_\ve)$. (If we write
$A=(a_{ij})$, then  $a_{ij}=(\fxx_{\ve i}-\fxy_{\ve i})(\fxx_{\ve
j}-\fxy_{\ve j})$.) We now consider two cases.

\medskip

\noindent {\bf Case (1):} $D\varphi(t_\ve,\fxy_\ve)=0$.
\medskip

This means that $\fxx_\ve=\fxy_\ve$, which in turn implies that
$D^2\varphi(t_\ve,\fxy_\ve)\geq0$. Thus, for any $G^+$ that
satisfies \eqref{eq172},
$G^+(D^2\varphi(t_\ve,\fxy_\ve),0,\fxy_\ve,t_\ve)\geq0$.

We now take another point of view: Fix $\fxy=\fxy_\ve$ and
consider the function
\[
\psi_{\ve,\fxy_\ve}(t,\fxx,\fxy_\ve)=u(t,\fxx)-\varphi(t,\fxy_\ve)-\frac{|\fxx-\fxy_\ve|^4}{\ve}=u(t,\fxx)-\varphi_\ve(t,\fxx).
\]
This function has a local maximum at $(t_\ve,\fxx_\ve)$.
Furthermore,
$D\varphi_\ve(t_\ve,\fxx_\ve)=D\varphi(t_\ve,\fxx_\ve)=0$, and
$D^2\varphi_\ve(t_\ve,\fxx_\ve)=0$. Thus, Lemma \ref{lemma15.3}
applies, and \eqref{eq176} holds:
\[
\frac{\partial\varphi}{\partial t}(t_\ve,\fxx_\ve)\leq0.
\]
Since $\fxx_\ve=\fxy_\ve$ and $G^+(D^2\varphi(t_\ve,\fxy_\ve),0,\fxy_\ve,t_\ve)\geq0$, it follows that
\[
\frac{\partial\varphi}{\partial t}(t_\ve,\fxy_\ve)\leq G^+(D^2\varphi(t_\ve,\fxy_\ve),0,\fxy_\ve,t_\ve).
\]
Both ${\partial\varphi}/{\partial t}$ and $G^+$ are continuous in all of their variables, so by letting $\ve$ tend to zero we arrive at the inequality \eqref{eq179}.

\medskip

\noindent {\bf Case (2):} $D\varphi(t_\ve,\fxy_\ve)\not=0$.
\medskip

Note that the function
\[
(t,\fxx)\mapsto u(t,\fxx)-\varphi(t,\fxx-(\fxx_\ve-\fxy_\ve))-\frac{|\fxx-\fxy_\ve|^4}{\ve}=u(t,\fxx)-\vartheta_\ve(t,\fxx)
\]
has a local maximum at $(t_\ve,\fxx_\ve)$. This means that Lemma \ref{lemma15.3} applies to $\vartheta_\ve$. Since
$D\varphi_\ve(t_\ve,\fxy_\ve)=D\vartheta_\ve(t_\ve,\fxy_\ve)\not=0$ and
$D^2\varphi(t_\ve,\fxy_\ve)=D^2\vartheta_\ve(t_\ve,\fxy_\ve)$, we have

\begin{eqnarray*}
% \nonumber to remove numbering (before each equation)
 \frac{\partial\varphi}{\partial t}(t_\ve,\fxy_\ve)
 &\leq& F(D^2\varphi(t_\ve,\fxy_\ve),D\varphi(t_\ve,\fxy_\ve),\fxy_\ve,t_\ve) \\
  &\leq& G^+(D^2\varphi(t_\ve,\fxy_\ve),D\varphi(t_\ve,\fxy_\ve),\fxy_\ve,t_\ve),
\end{eqnarray*}
using \eqref{eq175} and \eqref{eq172}. Again, letting $\ve$ tend to zero gives \eqref{eq179}.
\end{proof}

\begin{exercise}
Prove the inequality \eqref{inequalitypowerfour}. \finex
\end{exercise}

The next lemma provides another very useful simplification for
verifying that a function $u$ is a viscosity solution of
\eqref{eq174}.

\begin{lemma}\label{lemma15.5}
To show that $u$ is a viscosity subsolution (or supersolution), it suffices to use test functions $\varphi\in C^\infty([0,\infty)\times\RR^N)$ of the form $\varphi(t,\fxx)=f(\fxx)+g(t)$.
\end{lemma}
\begin{proof}
This is the assumption: If a function of the form $\varphi(t,\fxx)=f(\fxx)+g(t)$ is such that $u-\varphi$ attains a
local maximum at $(t_0,\fxx_0)$, then \eqref{eq175} and \eqref{eq179} follow. From this assumption, we must prove: If
$\varphi$ is any function in $C^\infty([0,\infty)\times\RR^N)$ such that $u-\varphi$ attains a local maximum, then
\eqref{eq175} and \eqref{eq179} follow. The technique for doing this is to develop $\varphi$ as a Taylor series and
separate the variables. To keep the notation manageable, we will assume without loss of generality that
$(t_0,\fxx_0)=(0,0)=0$.  With this assumption, the Taylor expansion of $\varphi$ is
\[
\varphi(t,\fxx)= a+bt+\langle p,\fxx\rangle+ct^2+\langle Q\fxx,\fxx\rangle+t\langle q,\fxx\rangle+o(|\fxx|^2+t^2),
\]
where $a=\varphi(0)$, $b=\partial\varphi/\partial t(0)$, $c=(1/2)\partial^2\varphi/\partial t^2(0)$, $Q=(1/2)D^2\varphi(0)$, and
\[
q=\Big(\frac{\partial^2\varphi}{\partial x_1\partial t}(0),\ldots,\frac{\partial^2\varphi}{\partial x_N\partial t}(0)\Big).
\]
For $\ve>0$, we define
\[
f(\fxx)=a+\langle p,\fxx\rangle+\langle Q\fxx,\fxx\rangle+\ve|\fxx|^2+\ve|q||\fxx|^2
\]
and
\[
g(t)=bt+\frac{|q|}{\ve}t^2+\ve t^2+ct^2.
\]
This means that
\[
\varphi(t,\fxx)=f(\fxx)+g(t)-\Big(\ve|q||\fxx|^2+\frac{|q|}{\ve}t^2-t\langle q,\fxx\rangle+\ve(|\fxx|^2+t^2)\Big)+o(|\fxx|^2+t^2).
\]
Since, by the Cauchy--Schwartz inequality, $\ve|q||\fxx|^2+(|q|/\ve)t^2-t\langle q,\fxx\rangle\geq0$, we have
$\varphi(t,\fxx)\leq f(\fxx)+g(t)$ for all sufficiently small $(t,\fxx)$. Thus, in some neighborhood of $(0,0)$,
$u(t,\fxx)-\varphi(t,\fxx)\geq u(t,\fxx)-f(\fxx)-g(t)$ and this inequality is an equality for $(t,\fxx)=(0,0)$. The
assumption is that $u-\varphi$ has a local maximum at $(0,0)$.  Hence this last inequality implies that $u-f-g$ has a
local maximum at $(0,0)$. Thus, by assumption, \eqref{eq175} and \eqref{eq179} hold for $f+g$. More precisely, we have
the following two cases.
\medskip

\noindent {\bf Case (1):} $D(f+g)(0)\not=0$.
\medskip

From \eqref{eq175},
\[
\frac{\partial (f+g)}{\partial t}(0)\leq F(D^2(f+g)(0),D(f+g)(0),0,0).
\]
It is easy to see that $$D\varphi(0)=D(f+g)(0)\not=0 \hbox{ and }(\partial\varphi/\partial t)(0)=(\partial
(f+g)/\partial t)(0),$$
 and a short computation shows that $D^2(f+g)(0)=D^2\varphi(0)+2\ve(1+|q|)I)$. Substituting these values in the expression above shows that
\[
\frac{\partial\varphi}{\partial t}(0)\leq F(D^2\varphi(0)+2\ve(1+|q|)I,D\varphi(0),0,0).
\]
We let $\ve\to0$ and use the continuity of $F$ to see that \eqref{eq175} holds for $\varphi$.
\medskip

\noindent {\bf Case (2):} $D(f+g)(0)=0$.
\medskip

In this case, \eqref{eq179} is true for $f+g$:
\[
\frac{\partial (f+g)}{\partial t}(0)\leq G^+(D^2(f+g)(0),D(f+g)(0),0,0).
\]
Letting $\ve\to0$ and using the continuity of $G^+$ yields  \eqref{eq179} for $\varphi$.
\end{proof}



We are now in position to see how classical and viscosity
solutions are related. The next two propositions show that the
notion of viscosity solution is indeed a generalization of that of
classical solution.

\begin{proposition}\label{proposition15.6}Let $F$ be an admissible function that is continuous everywhere, and assume $u:[0,\infty)\times\RR^N\to\RR$ is $C^2$ with respect to $\fxx$ and $C^1$ with respect to $t$. If $u$ is a classical solution of
\[
\frac{\partial u}{\partial t}(t,\fxx)=F(D^2u,Du,\fxx,t)
\]
at $(t_0,\fxx_0)$, then $u$ is a viscosity solution at $(t_0,\fxx_0)$.
\end{proposition}

\begin{proof}We prove this for the case $Du(t_0,\fxx_0)\not=0$. (The other cases follow immediately.) Thus, let $\varphi\in C^\infty([0,\infty)\times\RR^N)$ be such that $u-\varphi$ has a local maximum at $(t_0,\fxx_0)$. This implies that $(\partial u/\partial t, Du)(t_0,\fxx_0)=(\partial\varphi/\partial t, D\varphi)(t_0,\fxx_0)$ and that $D^2(u-\varphi)(t_0,\fxx_0)\leq0$, so
\[
D^2u(t_0,\fxx_0)\leq D^2\varphi(t_0,\fxx_0).
\]
Hence,
\begin{align*}
\frac{\partial\varphi}{\partial t}(t_0,\fxx_0)=\frac{\partial u}{\partial t}(t_0,\fxx_0)&=F(D^2u(t_0,\fxx_0),Du(t_0,\fxx_0),\fxx_0,t_0)\\
&\leq F(D^2\varphi(t_0,\fxx_0),D\varphi(t_0,\fxx_0),\fxx_0,t_0).
\end{align*}
This proves that $u$ is a viscosity supersolution. A similar argument shows that it is a viscosity subsolution.
\end{proof}

\begin{proposition}\label{proposition15.7}Assume that $F$ is admissible and continuous everywhere. Let $u$ be a $C^2(\RR^+\times\RR^N)$ viscosity solution of $\partial u/\partial t=F(D^2u,Du,\fxx,t)$. Then $u$ is a classical solution of the same equation.
\end{proposition}
\begin{proof}Assume that $u$ is a viscosity solution at the point $(t_0,\fxx_0)$. We write the second-order Taylor expansion of $u$ in the $N+1$ variables near $(t_0,\fxx_0)$ as
\begin{align*}
u(t,\fxx)=&\,u(t_0,\fxx_0)+\langle\tilde{D}u(t_0,\fxx_0),(t-t_0,\fxx-\fxx_0)\rangle\\
&+\langle\tilde{D}^2u(t_0,\fxx_0)(t-t_0,\fxx-\fxx_0),(t-t_0,\fxx-\fxx_0)\rangle+o(|t-t_0|^2+|\fxx-\fxx_0|^2),
\end{align*}
where the operators $\tilde{D}$ and $\tilde{D}^2$ involve all $N+1$ variables. For $\ve>0$, define $\varphi_\ve$ by
\begin{align*}
\varphi_\ve(t,\fxx)=u(t_0,\fxx_0)&+\langle\tilde{D}u(t_0,\fxx_0),(t-t_0,\fxx-\fxx_0)\rangle\\
&+\langle(\tilde{D}^2u(t_0,\fxx_0)+\ve I)(t-t_0,\fxx-\fxx_0),(t-t_0,\fxx-\fxx_0)\rangle.
\end{align*}
Thus,
\[
u(t,\fxx)-\varphi_\ve(t,\fxx)=-\ve(|t-t_0|^2+|\fxx-\fxx_0|^2)+o(|t-t_0|^2+|\fxx-\fxx_0|^2)
\]
and the point $(t_0,\fxx_0)$ is a local maximum of $u-\varphi_\ve$ for all $\ve>0$. Similarly, $(t_0,\fxx_0)$ is a local minimum of $u-\varphi_{-\ve}$. The test functions $\varphi_\ve$ and $\varphi_{-\ve}$ are $C^\infty$, so we can apply Definition 15.2 directly. Thus,
\begin{align*}
\frac{\partial u}{\partial t}(t_0,\fxx_0)=\frac{\partial\varphi_\ve}{\partial t}(t_0,\fxx_0)&\leq F(D^2\varphi_\ve(t_0,\fxx_0),D\varphi_\ve(t_0,\fxx_0),\fxx_0,t_0)\\
&=F((D^2u+\ve I)(t_0,\fxx_0),Du(t_0,\fxx_0),\fxx_0,t_0),
\end{align*}
and
\begin{align*}
\frac{\partial u}{\partial t}(t_0,\fxx_0)=\frac{\partial\varphi_{-\ve}}{\partial t}(t_0,\fxx_0)&\geq F(D^2\varphi_{-\ve}(t_0,\fxx_0),D\varphi_\ve(t_0,\fxx_0),\fxx_0,t_0)\\
&=F((D^2u-\ve I)(t_0,\fxx_0),Du(t_0,\fxx_0),\fxx_0,t_0).
\end{align*}
Letting $\ve\to0$ and using the continuity of $F$ shows that
\[
\frac{\partial u}{\partial t}(t_0,\fxx_0)=F(D^2u(t_0,\fxx_0),Du(t_0,\fxx_0),\fxx_0,t_0).\qedhere
\]
\end{proof}

Before discussing several examples, we need a useful further restriction on the test functions $\varphi$.

\begin{lemma}\label{fonctionstestsdansF}
To show that $u$ is a viscosity subsolution (or supersolution), it suffices to use test functions $\varphi\in
C^\infty([0,\infty)\times\RR^N)$ that satisfy $\fxx\to \varphi(t,\fxx)\in \mathcal F(\RR^N)$ for all $t\geq 0$ and are
globally Lipschitz on $\RR^N$.
\end{lemma}
\begin{proof}
In fact the properties we deal with are all local around a point $(t_0, \fxx_0)$. Thus we can  replace $\varphi$ by
another  $C^\infty$ function $\psi$ which coincides with $\varphi$ on a ball $B(0,(t_0,\fxx_0)$, belongs to $\mathcal
F$ for all $t$, and is globally Lipschitz on $\RR^N$.
\end{proof}

\begin{exercise} Give a detailed construction of $\psi$ from $\varphi$.
\finex
\end{exercise}

\section{Application to mathematical morphology}

In Proposition \ref{proposition8.8}, we showed that
$u(t,\fxx)=D_tu_0(\fxx)$ is a solution of $\partial u/\partial
t=|Du|$ at each point $(t_0,\fxx_0)$ where $u$ is $C^1$. We are
now going to prove that $u$ is a viscosity solution of this
equation at all points.

\begin{theorem} \label{theorem15.8}
Assume that $u_0\in \mathcal F(\RR^N)$. Let $D(0,1)$ be the unit ball in $\RR^N$ and let $u$ be defined by
\[
u(t,\fxx)=D_tu_0(\fxx)=\sup_{\fxy\in tD(0,1)}u_0(\fxx+\fxy).
\]
Then $u$ is a viscosity solution of
\begin{equation}\label{eq1711}
\frac{\partial u}{\partial t}=|Du|,\quad u(0,\fxx)=u_0(\fxx).
\end{equation}
\end{theorem}

\begin{proof}
We will use the fact that the dilation $D_t$ is recursive, that
is, $D_{s+t}=D_sD_t$ (see Proposition \ref{proposition8.7}). In
particular, for $t>0$, $D_t=D_hD_{t-h}$, so
\begin{equation}\label{eq1712}
u(t,\fxx)=\sup_{|\fxy|<h}u(t-h,\fxx+\fxy).
\end{equation}

Let $\varphi$ be a $C^\infty$ test function and assume that $u-\varphi$ has a local maximum at $(t_0,\fxx_0)$. To prove
that $u$ is a viscosity subsolution of \eqref{eq1711}, we must show that
\[
\frac{\partial  \varphi}{\partial t}(t_0,\fxx_0)-|D\varphi(t_0,\fxx_0)|\leq 0.
\]
Since $u-\varphi$ has a local maximum at $(t_0,\fxx_0)$, we have for sufficiently small $h$ and $|\fxy|$,
\[
u(t_0-h,\fxx_0+\fxy)-\varphi(t_0-h,\fxx_0+\fxy)\leq u(t_0,\fxx_0)-\varphi(t_0,\fxx_0)
\]
It follows that
\[
\sup_{|\fxy|<h}u(t_0-h,\fxx_0+\fxy)\leq u(t_0,\fxx_0)-\varphi(t_0,\fxx_0)+\sup_{|\fxy|<h}\varphi(t_0-h,\fxx_0+\fxy),
\]
and using \eqref{eq1712} shows that
\[
u(t_0,\fxx_0)\leq u(t_0,\fxx_0)-\varphi(t_0,\fxx_0)+\sup_{|\fxy|<h}\varphi(t_0-h,\fxx_0+\fxy).
\]
Thus,
\[
\varphi(t_0,\fxx_0)\leq\sup_{|\fxy|<h}\varphi(t_0-h,\fxx_0+\fxy).
\]
Subtracting $\varphi(t_0-h,\fxx_0)$ from both sides yields
\[
\varphi(t_0,\fxx_0)-\varphi(t_0-h,\fxx_0)\leq\sup_{|\fxy|<h}\big(\varphi(t_0-h,\fxx_0+\fxy)-\varphi(t_0-h,\fxx_0)\big).
\]
By writing $\varphi(t_0-h,\fxx_0+\fxy)-\varphi(t_0-h,\fxx_0)=\langle\tilde{D}\varphi(t_0,\fxx_0),(0,\fxy)\rangle+o(h+|\fxy|)$, we see that
\[
\varphi(t_0,\fxx_0)-\varphi(t_0-h,\fxx_0)\leq |D\varphi(t_0,\fxx_0)|h+o(h).
\]
Dividing both sides by $h$ and letting $h$ tend to zero leads to
\[
\frac{\partial \varphi}{\partial t}(t_0,\fxx_0)-|D\varphi(t_0,\fxx_0)|\leq0.
\]
We have proven this under the assumption that $t_0>0$ and $h>0$ is sufficiently small. But by continuity, the last inequality is true for $t_0=0$. This proves that $u$ is a subsolution of \eqref{eq1711}; the proof that it is a supersolution is similar. The fact that $u(0,\fxx)=u_0(\fxx)$ is a direct consequence of the assumption that $u_0$ is continuous.
\end{proof}

\section{Approximation theory of viscosity solutions}

For simplicity, we consider slightly  less general PDEs, namely,
those of the form
\begin{equation}
%\label{eq1713}
\label{equationgeneralesanst} \frac{\partial u}{\partial t}(t,\fxx)-F(D^2u(t,\fxx),Du(t,\fxx),\fxx)=0,
\end{equation}
where $(A,p,\fxx)\mapsto F(A,p,\fxx)$  is admissible, but independent of $t$. This is the case for the functions listed
at the beginning of the chapter. For these equations, it is reasonable to expect that the operator $S_t:u_0\mapsto
u(t,\cdot)$ could be approximated by iterations of an operator $T_h$, by which we mean that $(T_h)^n\to S_t$ in some
sense as $h\to0$, $n\to\infty$. We have seen this in Theorem \ref{theorem2.3}, where it was shown that a large class of
iterated linear operators converge asymptotically to the heat equation. We have promised to show that whole classes of
nonlinear operators converge asymptotically to other PDEs. We are mainly interested in operators that have been shown
to be useful for image analysis and that have been studied in previous chapters. To include all of these operators in
the theory, we shall  first state three abstract properties which were proven under various forms for scaled
morphological operators $T_h$.

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

\begin{definition}\label{definition15.9}
  \index{operator!consistency} \index{consistency with an equation}
We say that a family of operators $T_h, \;h>0$ is  {\rm uniformly consistent with Equation
\eqref{equationgeneralesanst}} if for every $C^3$, Lipschitz function $u$ we can assert that
\begin{equation} \label{consistencywithequationgenerale} \hbox{if
} Du(\fxx) \neq 0,
 (T_hu)(\fxx)-u(\fxx) = h F(D^2u, Du, \fxx) + o_{\fxx}(h),
\end{equation} where the convergence of $ o_{\fxx}(h)$ is uniform for $\fxx$
in every compact set contained in the set $\{\fxx, Du(\fxx)\neq 0 \}$ and
 \begin{equation} \hbox{if } Du(\fxx) = 0 , |
(T_hu)(\fxx)-u(\fxx)| \leq h G( D^2u,0,\fxx) + o_{\fxx}(h)
\end{equation} for a continuous functions $G$, with $G(0,0,\fxx) =
0$, and where the convergence of $o_{\fxx}(h)$ is uniform for
$\fxx$ in every compact set. \index{uniform consistency}
\end{definition}

\begin{definition}\label{definition15.10} \index{operator!local comparaison principle}
\index{local comparaison principle} \index{uniform local
comparaison principle} We say that a family of operators $T_h,
h>0$ satisfies a uniform local comparison principle  if for every
L and all L-Lipschitz functions $u$ and $v$ such that $u(\fxy)\geq
v(\fxy)$ on a disk $D(\fxx,r)$,
\begin{equation}
 \label{localmaximumprinciple}
(T_hu)(\fxx)\geq (T_hv)(\fxx) - o(h), \end{equation} where the
function $o(h)$ only depends upon the Lipschitz constant $L$ and
$r$.

\end{definition}
Notice that if $T$ is a local morphological operator like the median on a ball and $T_h$ its rescaled version, then
(\ref{localmaximumprinciple}) is trivially satisfied, with $o(h)=0$ for $h$ small enough.

\begin{definition}
\label{definitionu-h} Let $T_h$, $h>0$, be a family of operators:  $\mathcal F\to \mathcal F$ which is uniformly
consistent with Equation (\ref{equationgeneralesanst}). We call {\bf approximate solutions} of
(\ref{equationgeneralesanst}) with initial condition $u_0(\fxx)$ the functions $u_h(t, \fxx)$ defined for every $h>0$
by
$$
\forall n\in \natural,\quad u_h(nh, \fxx) = (T_h^nu_0)(\fxx).
$$

\end{definition}
The functions $u_h$ are only defined on $(h\NN)\times \RR^N$.  All the same, we are interested in their limit on
$\RR^+\times \RR^N = [0, +\infty)\times \RR^N$.

\begin{definition}\label{uniformconvappsol} We say that approximate solutions  $u_h$
converge uniformly on compacts sets  to a function $u$ defined on
$\RR^+\times \RR^N$ if for every compact subset $K$ of
$\RR^+\times \RR^N$  and every $\varepsilon>0$, there is $h_0$
such that    $|u(t,\fxx)-u_h(t,\fxx)|<\varepsilon$ for all $h\leq
h_0$ and all $(t,\fxx)\in K\cap (h\NN)\times\RR^N$.
\end{definition}




 \index{approximate solutions}
\begin{proposition} [Barles-Souganidis]  \label{limitedeuhestsolution}
 \index{convergence lemma towards viscosity solutions.}
 \index{Barles-Souganidis principle}
Let $(T_h)_{h\geq 0}$ be a family of translation invariant operators uniformly consistent with
(\ref{equationgeneralesanst}), satisfying a uniform comparison  principle and commuting with the addition of constants.
Let $u_0\in \mathcal F$ be Lipschitz. Assume that a sequence of approximate solutions $u_{h_k}$ converges uniformly on
every compact set to a function $u$, with $h_k\to 0$. Then $u$ is a viscosity solution of
(\ref{equationgeneralesanst}).
\end{proposition}

Before starting with the proof, let us state two obvious but useful lemmas.

\begin{lemma}\label{conservationdumaximumstrict}\label{lemma15.12} Consider $u_h$
converging to $u$ uniformly on compact sets, as in Definition
\ref{uniformconvappsol}.  Assume that $u$ is continuous on a ball
$B_r=B((t,\fxx),r)$ and that  it attains its strict maximum on
$B_r$ at $(t,\fxx)$. Then if  $(t_h,\fxx_h)$ is a maximum point of
$u_h$ on $B_r$, one has $(t_h,\fxx_h)\to (t,\fxx)$.

\end{lemma}
\begin{proof} For every $\varepsilon>0$, there is $\eta >0$ such
that  $\sup_{B_r\setminus B_\varepsilon} u<\sup_{B_r}u-\eta.$ Take
$h$ small enough so that $\sup_{B_r}|u-u_h|<\frac{\eta}2.$ Then
$\sup_{B_r}|u_h|>\sup_{B_r}u-\frac\eta 2. $   On the other hand,
$\sup_{B_r\setminus B_\varepsilon}|u_h|<\sup_{B_r}u-\eta+\frac\eta
2$,  which proves that the maximum  of $u_h$ is attained on
$B_\varepsilon$ only.

\end{proof}

\begin{lemma} \label{uhlipschitzinx} Assume that $u_0$ is $L$-Lipschitz. Then for every $n$, $u_h(nh, \fxx)$ is $L$-Lipschitz in $\fxx$.
\end{lemma}
\begin{proof}
This is a straightforward consequence of the definition of $u_h$ and Lemma \ref{lemma6.5}.
\end{proof}

\begin{proof}[Proof of Proposition \ref{limitedeuhestsolution}] Without
risk of ambiguity, we shall write $u_h$ instead of $u_{h_k}$. Let $B=B((\fxx, t), r)$ be a closed ball and $\varphi (s,
\fxy)$ a $C^\infty$ and Lipschitz function such that $(u-\varphi)(s, \fxy)$ attains its strict maximum on $B$ at $(t,
\fxx)$. Without loss of generality, we can assume by Lemma \ref{lemma15.5} that $\varphi(t, \fxy) = f(\fxy)+g(t).$
Notice that the functions $\fxx\to u_n(nh,\fxx)$ are in $\mathcal F$ and therefore continuous. The maximum of
$u_h-\varphi$
 on $B\cap (h\NN)\times\RR^N$ is attained, because this function is discrete in time and continuous  in $\fxx$.
 Since $u_h-\varphi\to u-\varphi$ uniformly on $B\cap(h\NN)\times\RR^N$, we know by Lemma \ref{conservationdumaximumstrict}
that a sequence $(n_hh,\fxx_h)$ of maxima of $u_h-\varphi$ on $B$ converges to $(t,\fxx)$. By the maximum property of
$(n_hh, \fxx_h)$, we have
$$
u_h((n_h-1)h, \fxy)-\varphi((n_h-1)h, \fxy)\leq u_h(n_hh,
\fxx_h)-\varphi(n_hh, \fxx_h).
$$
for every $\fxy$ such that $((n_h-1)h, \fxy)\in B$ and therefore
$$u_h((n_h-1)h, \fxy)\leq  u_h(n_hh, \fxx_h)-\varphi(n_hh, \fxx_h)+\varphi((n_h-1)h, \fxy)$$
for $h$ small enough (i.e. $k$ large enough) and every $\fxy \in B(\fxx, \frac r 2)$.  Applying on both sides $T_h$ and
using the local comparison principle and the commutation of $T_h$ with the addition of constants,
$$T_h(u_h((n_h-1)h,.))(\fxx_h)\leq
u_h(n_hh, \fxx_h)-\varphi(n_hh, \fxx_h)+(T_h\varphi((n_h-1)h),
.)(\fxx_h) + o(h).$$ Since $\varphi(t,\fxy)=f(\fxy)+g(t)$ and
$T_h(u((n_h-1)h),.)(\fxx)=u_h(n_hh, \fxx)$, we get
$$
0\leq -f(\fxx_h)-g(n_hh)+T_hf(\fxx_h)+g((n_h-1)h) + o(h),
$$
where we have used again the commutation of $T_h$ with the
addition of constants.


Let us first assume that $Df(\fxx) \neq 0$. By the uniform
consistency assumption (\ref{consistencywithequationgenerale}),
since for $h$ small enough $Df(\fxx_h)\neq 0$,
$$
(T_hf)(\fxx_h)=f(\fxx_h)+hF(D^2f(\fxx_h), Df(\fxx_h), \fxx_h)+o_{\fxx_h}(h).
$$
Thus
$$
g(n_hh)-g((n_h-1)h)\leq hF(D^2f(\fxx_h), Df(\fxx_h), \fxx_h) + o_{\fxx_h}(h).
$$
Dividing by $h$, letting $h\to 0$ so that $(\fxx_h, n_hh)\to
(\fxx,t)$ and using the continuity of $F$, we get
$$\frac{\partial g}{\partial t}(t)\leq F(D^2f(\fxx), Df(\fxx), \fxx),$$
that is to say
$$\frac{\partial \varphi}{\partial t}(t)\leq F(D^2\varphi(\fxx), D\varphi(\fxx), \fxx).$$

We treat now the case where $Df(\fxx)=0$ and $D^2f(\fxx)=0$. The
uniform consistency yields
$$
|\frac{(T_hf)(\fxx_h)-f(\fxx_h)}{h}| \leq G(D^2f(\fxx_h),
Df(\fxx_h), \fxx_h)+o(1).
$$
The right term, by continuity of $G$, tends to zero, when $h$
tends to 0. Thus
$$\frac{\partial \varphi}{\partial t}(t)\leq 0$$
Thus $u$ is a subsolution of Equation
(\ref{equationgeneralesanst}) and we prove in exactly the same way
that it is a supersolution and therefore a viscosity solution.
\end{proof}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%
At this point it  should be clear that the last important step in
our program is to show that the approximate solutions converge
uniformly on compact sets. It should also be clear that
Definitions 15.9 and 15.10 were fashioned to abstract from
previous results about inf-sup operators, conditions that are
sufficient to prove the Barles--Souganidis theorem. We will see in
the next chapter that these conditions are also sufficient to
prove that the approximate solutions converge. This then will
close the gap and show that the iterated operators converge to
viscosity solutions of their associated equations.





\section{A uniqueness result for viscosity solutions}

Proving uniqueness is technically quite difficult, and we are
going to fudge by quoting a uniqueness result without proof. Our
statement has been simplified to cover only those admissible
functions $F$ that are associated with image operators. References
where one can find this and more general results are given in the
next section.

\begin{theorem}[Uniqueness]
\label{theorem15.14} Assume that $(A,p)\mapsto F(A,p)$ is
admissible. Let $u(t,\fxx)$ and $v(t,\fxx)$ be two continuous
functions for $(t,\fxx)\in \RR^+\times\SN$, such that for all
$t\in \RR^+$, $\fxx\to u(t,\fxx)$ and $\fxx\to v(t,\fxx)$ belong
to $\mathcal F$.   If $u$ and $v$ are continuous viscosity
solutions of
\begin{equation}\label{eq1719}
\frac{\partial\varphi}{\partial t}=F(D^2u,Du)
\end{equation}
  then
\begin{equation}\label{eq1720}
\sup_{t\in R^+,\fxx\in\RR^N}(u(t,\fxx)-v(t,\fxx)) \leq
\sup_{\fxx\in\RR^N}(u(0,\fxx)-v(0,\fxx)).
\end{equation}
As a consequence, if $u(0,\fxx)=v(0,\fxx)$ for all $\fxx$, then
$u(t,\fxx)=v(t,\fxx)$ for all $\fxx$ and $t$.
\end{theorem}

\section{Exercises}

\begin{exercise}\label{exercise15.1}
The exercise refers to  the proof of Lemma \ref{lemma15.4}.
Consider  $u-\varphi$, continuous and having a strict maximum at
$(t_0,\fxx_0)$. Set
\[
\psi_\ve(t,\fxx,\fxy)=
u(t,\fxx)-\varphi(t,\fxy)-\frac{|\fxx-\fxy|^4}{\ve},\quad\ve>0.
\]
Prove the existence of the points $(t_\ve,\fxx_\ve,\fxy_\ve)$
where $\psi_\ve$ has local maxima and that tend to
$(t_0,\fxx_0,\fxy_0)$ as $\ve\to0$. Hints: Since $u-\varphi$ has a
local maximum at $(t_0,\fxx_0)$, we can choose an $r$ such that
$u(t,\fxx)-\varphi(t,\fxx)\leq
u(t_0,\fxx_0)-\varphi(t_0,\fxx_0)=\lambda$ for
$(t,\fxx)\in\overline{D}((t_0,\fxx_0),r)=\overline{D}$. For any
$(t,\fxx),(t,\fxy)\in \overline{D}$ we have
\[
u(t,\fxx)-\varphi(t,\fxy)-\frac{|\fxx-\fxy|^4}{\ve}\leq\sup_{(t,\fxx),(t,\fxy)\in
\overline{D}}\Big(u(t,\fxx)-\varphi(t,\fxy)-\frac{|\fxx-\fxy|^4}{\ve}\Big).
\]
Let $\fxx=\fxy=\fxx_0$ on the left-hand side, so
\[
\lambda\leq\sup_{(t,\fxx),(t,\fxy)\in
\overline{D}}\Big(u(t,\fxx)-\varphi(t,\fxy)-\frac{|\fxx-\fxy|^4}{\ve}\Big).
\]
For each $\ve>0$, there is some point $(t_\ve,\fxx_\ve,\fxy_\ve)$
where the supremum is attained. Now argue that these points must
tend to  $(t_0,\fxx_0,\fxy_0)$ as $\ve\to0$. (This is where the
fact that $(t_0,\fxx_0,\fxy_0)$ is ``strict'' is used.) Hence, for
small enough $\ve$ the points $(t_\ve,\fxx_\ve,\fxy_\ve)$ must all
be in the interior of $\overline{D}$ and are therefore
\textit{local} maximum points.  \finex
\end{exercise}
\begin{exercise}We have seen in Lemma \ref{lemma15.5} that
the test functions in Definition \ref{definition15.2} can be
replaced with
 functions of the form $\varphi(t,\fxx)=f(\fxx)+g(t)$.
  Prove that the requirement can be weakened
 further by only requiring that $f$ belongs to any class
 $\mathcal C$ of $C^2$ functions that has the following property:
 For any $\fxx\in\RR^N$, any $a\in\RR$, any $p\in\RR^N$, and any
 symmetric $N\times N$ matrix $A$, there exists $f\in\mathcal C$
 such that
\[
f(\fxx-\fxy)=a+\langle p,\fxx-\fxy\rangle +\frac1{2}\langle
A(\fxx-\fxy),(\fxx-\fxy)\rangle+o(|\fxx-\fxy|^2).
\]
Hint: use the techniques used to prove Lemma \ref{lemma15.5}. \finex
\end{exercise}

%\begin{exercise}Note that we wrote Lemma \ref{lemma15.4}
%assuming that the local maximum was strict, but that we used it in the last part of the proof in a situation where the
%local maxima
% were not necessarily strict. Show that this is not a problem. \finex
%\end{exercise}

\section{Comments and references}

The simple definition of viscosity solution given in this chapter
was originally proposed by Michael G. Crandall and Pierre-Louis
Lions \cite{???} for first-order PDEs associated with control
theory. It was then shown to be applicable to second-order
equations, in particular the so-called geometric equations like
mean curvature motion. The first complete treatise is
\textit{User's guide to viscosity solutions of second order
partial differential equations} by Crandall, Ishii, and Lions
\cite{Crandall:1992:UGV}. First-order equations are treated
extensively in Barles \cite{Barles:1994:SVE}. An elementary
account for first-order equations is given in the textbook by
Evans \cite{Evans:1998:PDE}. Crandall's later presentation of the
theory for both first- and second-order equations, published in
\cite{???}, is a masterpiece of simplicity and brevity. This book
contains a rather complete overview of the techniques, results,
and applications, although it does not include applications to
image analysis.

The approximation theory for  viscosity solutions presented here
is based on the seminal paper by Barles and Souganidis
\cite{Barles:1991:CAS}.

Proving uniqueness for viscosity  solutions of second-order
parabolic or elliptic equations is the technically difficult part
of the theory. The key step that leads to the uniqueness results
was made by Robert Jensen in his 1988 paper
\cite{Jensen:1988:MPV}. See also \cite{Changhe:1998:UVS} and
\cite{Zhu:1994:EUR} for  general uniqueness proofs in the
parabolic case. Some alternative (or related) existence and
uniqueness theories, namely, the nonlinear semigroup theory and De
Giorgi's theory of barriers, are discussed in
\cite{Evans:1987:NST} and \cite{Bellettini:1998:CRB}.

\newpage

\section[]{ Tables of multiscale differential operators and equations\label{sec:tables}}

\begin{itemize}
\item All equations  have a unique viscosity solution starting from a Lipschitz initial image $u_0$;
\vspace{-8pt}
\item all iterated radial convolutions converge to the heat equation;
\vspace{-8pt}
\item  iterated monotone contrast invariant isotropic filters converge to a curvature  motion or an erosion or a dilation;\vspace{-8pt}

\item  iterated contrast invariant affine invariant self-dual filters converge to an affine curvature motion;\vspace{-8pt}

\item  iterated medians converge to a mean curvature or curvature (dim. 2) motion.\vspace{-8pt}

\end{itemize}
\begin{figure}[!ht]
\begin{center}
\begin{tabular}{|c|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
   operator & $\frac{\partial u}{\partial t}=$ & $F(A,p)$   \\
  Laplacian & $\Delta u$ & $trace(A)$    \\
    gradient & $|Du|$ & $|p|$   \\
  curvature & $|Du|curv(u)$ & $A(\frac{p^\perp}{|p|},\frac{p^\perp}{|p|})$  \\
  affine curvature & $|Du|curv(u)^\frac 13$ & $A(p^\perp,p^\perp)^\frac 13$
    \\
  snake & $g.|Du|curv(u) + (Dg.Du)$ & $gA(\frac{p^\perp}{|p|},\frac{p^\perp}{|p|})+Dg.p$   \\
  mean curvature & $|Du|(\kappa_1(u)+\kappa_2(u))$& ${\rm Tr}(A)-A(p/|p|,p/|p|)$  \\
  affine curvature & ${\rm sgn}(\kappa_1)t^{1/2}|Du||G(u)^+|^{1/4}$&  \\
  acceleration & $\vert Du \vert curv(u)^{\frac{1-q}{3}}(\hbox{sgn}(curv(u)) accel(u)^q )^{+}$ \\
  \hline
\end{tabular}
\end{center}
\end{figure}

\vspace{-20pt}
\begin{figure}[!ht]
\begin{center}
\begin{tabular}{|c|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
   {\it operator} & {\it finite difference scheme} & {\it structuring elements} $\mathcal B$ \\
  Laplacian & $u_{xx}+u_{yy}$ & gaussian convolution  \\
  gradient & $(u_x^2+u_y^2)^\frac 12$ & ball \\
  curvature & $\frac{u_{xx}u_y^2-2u_{xy}u_xu_y+u_{yy}u_x^2}{u_x^2+u_y^2}$ & median\\
  affine curv. & ${\small(u_{xx}u_y^2-2u_{xy}u_xu_y+u_{yy}u_x^2)^\frac 13}$ &  affine inv.   \\
  snake & \!$g.\frac{u_{xx}u_y^2-2u_{xy}u_xu_y+u_{yy}u_x^2}{u_x^2+u_y^2}\!+ \!(g_xu_x\!+\!g_yu_y)\!$ & $\fxx$-dependent median, dilation   \\
  mean curv. &  $div\left(\frac{Du}{|Du|}\right)$ & median (BMO)  \\
  affine curv. & ${\rm sgn}(\kappa_1)t^{1/2}|Du||G(u)^+|^{1/4}$&  affine inv. \\
  acceleration &\! $\vert Du \vert curv(u)^{\frac{1-q}{3}} (\hbox{sgn}(curv(u)) accel(u)^q )^{+}\!$ & galilean invariant   \\

  \hline
\end{tabular}
\end{center}
\end{figure}
\vspace{-15pt}
\begin{itemize}
\item $k_i(A, p)=\frac{\mu_i}{|p|}$ where $\mu_i$ is the $i$-th eigenvalue of  $Q_pAQ_p$ of $A$ to  $p^\perp$, with
$Q_p=p\otimes p$. In other terms $\mu_i$ is the $i$-th eigenvalue of the restriction of $A$ to $p^\perp$, the
hyperplane orthogonal to $p$.\vspace{-8pt}

\item $k_i(u)=k_i(D^2u, Du)$.\vspace{-8pt}


\item $g(\fxx)=\frac{1}{1+|Du_0(\fxx)|}$ is small on edges of $u_0$ and large otherwise;\vspace{-8pt}


\item affine invariant structuring elements (dim. 2) computed by Moisan scheme;\vspace{-8pt}


\item curvature motion implemented by BMO (iterated median) or finite difference scheme;\vspace{-8pt}


\item alternatively mean curvature and mean curvature motion computed by {\it diffusion (heat equation) on the
hyperplane orthogonal to the gradient}; \vspace{-8pt}


\item $accel(u)$ is a bit long to write but the galilean invariant set of structuring elements leads to an easy
$\inf\sup$ computation;  $q\in  ]0,1[$.\vspace{-8pt}


\end{itemize}


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