%gmChap16.tex

\graphicspath{{./figures/chapter16/}}

\chapter{Curvature Equations and Iterated Contrast-Invariant Operators}

We will prove that the set of approximate solutions $\{u_h\}$ generated by scaled contrast-invariant operators $T_h$ contains a sequence $\{u_{h_{n}}\}$ that converges uniformly on compact sets. This is done under conditions that are general enough to include all of the contrast-invariant filters studied in previous chapters. We use this result and the Barles--Souganidis theorem to show that the limit function is a viscosity solution of the PDE associated with the operators, thus closing the gap in the operator-PDE-solution circle. We apply this result to median filters and to affine-invariant filters generated by sets of 1-localizable structuring elements. We also complete another link in the program by showing that viscosity solutions are contrast invariant: If $u$ is a viscosity solution of a curvature equation from a certain class, then, for any continuous contrast change $g$, $g(u)$ is also a viscosity solution of the same 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, and the $\kappa_i(u)$ denote the principal curvatures of the level surface of $u$. In other words, they are the eigenvalues of the restriction of $D^2u$ to the hyperplane orthogonal to $Du$ divided by $|Du|$ (see Definition 4.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 less destructive smoothing of three-dimensional images than the mean curvature motion. Finally, we mention affine-invariant curvature motion, which is a particularly important equation in three dimensions:
\begin{equation}\label{eq188}
\frac{\partial u}{\partial t}=|Du|((\kappa_1(u)\kappa_2(u))^+)^{1/4}.
\end{equation}
The admissible functions $F$ for most of these equations were listed in section 15.1.

\section{Contrast invariance and viscosity solutions}

We are going to show that the concepts of contrast invariance and viscosity solution are compatible: If $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. Of course, we must make some assumptions about $\beta$, but by now the appropriate assumptions should be clear: Assume that the PDEs we consider are of the form 
\[
\partial u/\partial t=F(D^2u,Du),
\]
where $(A,p)\mapsto F(A,p)$ is an admissible function of $A$ and $p$. We showed in section 15.1 that the equations \eqref{eq183}-\eqref{eq188} are of this form. Furthermore, all of the functions $F$ fall into the two classes already described: Either $F$ is defined and continuous on $\mathbb D^N={\mathbb S}^N\times\RR^N$, or $F$ is defined and continuous on ${\tilde{\mathbb D}}^N={\mathbb S}^N\times(\RR^N\setminus\{0\})$, where $\RR^N\setminus\{0\}$ is $\RR^N$ with the origin removed. In this latter case, $F$ cannot be extended continuously to $\mathbb D^N$, and, in fact, these functions should be thought of as being defined on ${\mathbb S}^N\times\{p\mid p\in\RR^N, |p|=1\}$. An examination of the functions described in section 15.1 shows that, for this second case, $p$ enters only as an argument of $A$, so if $A=0$, then $F(0,p)=0$. 

\begin{lemma}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 4.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^2(u), D(u)),
\end{align*} 
as announced.

In general, $D(g(u))=g'(u)D(u)$ and $D^2(g(u))=g'(u)D^2(u)+g''D(u)\otimes D(u)$. Thus, if $D^2(u)=0$ and $D(u)=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.\qedhere
\]
\end{proof}

The proof of the next result, the main one of this section, is a slightly more involved because we drop the assumption that $g'(s)>0$. This assumption was essential for the lemma, but it disappears in the statement of the proposition.

\begin{proposition}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 16.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 16.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 15.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$, defined by
\[
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$. It is then a straightforward exercise to 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$.

We know from Lemma 15.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 15.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 15.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 15.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 dual proof shows that it is a viscosity supersolution.
\end{proof}

\begin{exercise}Note that we wrote Lemma 15.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{Uniform continuity of approximate solutions}

This section is a direct continuation of section 15.3. The object is to prove that the approximate solutions of operators that satisfy the conditions of Definitions 15.9 and 15.10 converge uniformly on compact sets. We do this in a sequence of three lemmas.

\begin{lemma}Assume that the operators $T_h$, $0<h\leq1$ are monotone, translation invariant, and commute with the addition of constants. Assume also that they are $\alpha$- uniformly consistent with an equation of the form 
\begin{equation}
\frac{\partial u}{\partial t}=F(D^2u,Du,)
\end{equation}
and that they satisfy a $\beta$-uniform local comparison principle with $\beta>\alpha$. Let $K$ be an arbitrary compact subset of $\RR^N$. If $u$ is $L$-Lipschitz and $C^3$, then there are two constants $\kappa>0$ and $C_K>0$ such that 
\begin{equation}\label{eq16}
|T_h^nu(\fxx)-u(\fxx)|\leq C_Knh^\alpha
\end{equation}
for all $\fxx\in K$, all $h<\kappa$, and all $n\in\NN$. Furthermore, $\kappa$ and $C_K$ do not depend on $n$ or $\fxx;$ they depend only on $T$, $u$, and $K$. 
\end{lemma}

\begin{proof}Assume that $K$ is given and define the closed dilation of $K$ by 
\[
K_r={\overline D}_r(K)=\{\fxy\mid d(\fxy,K)\leq r\} 
\]
for some $r>0$. The value of $r$ is not important, so we take $r=1$. By Definition 15.9, there exists a continuous function $G$, an $\epsilon>0$, and a constant $C(K_1)$, which depends only on $K_1$, and hence only on $K$, such that 
\[
|T_hu(\fxx)-u(\fxx)|\leq h^\alpha G(D^2u(\fxx),Du(\fxx))+C(K_1)h^{\alpha +\epsilon}.
\]
Since $G$ is continuous, there is a constant $C(G,K_1)$ such that 
\[
\sup_{\fxx\in K_1}G(D^2u(\fxx),Du(\fxx))=C(G,K_1).
\]
Thus, for $\fxx\in K$ and $\fxy\in D(\fxx,1)$, we have
\begin{equation}\label{eq16a}
 T_hu(\fxy)\leq u(\fxy)+C(G,K_1)h^\alpha +C(K_1)h^{\alpha +\epsilon}.
\end{equation}
We wish to apply $T_h$ to both sides of this inequality and use the fact that the $T_h$ satisfy a $\beta$-uniform local comparison principle. We can do this because the functions on either side of the inequality are $L$-Lipschitz (Lemma 6.5) and because the inequality is true for $\fxy\in D(\fxx,1)$. However, when we apply $T_h$ to both sides, we must add an error term and a caveat regarding the values of $h$. Thus, there is a $\kappa>0$ such that 
\[
 T_h^2u(\fxx)\leq T_hu(\fxx)+C(G,K_1)h^\alpha +C(K_1)h^{\alpha +\epsilon}+C(L,r)h^\beta
\]
for all $h<\kappa$, and the constant $C(L,r)$ ($r=1$) depends only on $u$ and $r$. This relation is true for all $\fxx\in K$. Now use inequality \eqref{eq16a} to deduce that 
\[
 T_h^2u(\fxx)\leq u(\fxx)+2C(G,K_1)h^\alpha +2C(K_1)h^{\alpha +\epsilon}+C(L,r)h^\beta
\]
for all $\fxx\in K$ and all $h<\kappa$. This process can be repeated $n$ times to show that 
\[
T_h^nu(\fxx)\leq u(\fxx)+nC(G,K_1)h^\alpha +nC(K_1)h^{\alpha +\epsilon}+(n-1)C(K_1)h^\beta
\]
for all $\fxx\in K$ and all $h<\kappa$. The important point is that in repeating the process the constants $C(G,K_1)$, $C(K_1)$, $C(K_1)$, and $\kappa$ do not change. Thus we have
\[
T_h^nu(\fxx)\leq u(\fxx)+(C(G,K_1)+C(K_1)+C(K_1))nh^\alpha,
\]
so if we let $C_K=C(G,K_1)+C(K_1)+C(K_1)$ we have half of the inequality \eqref{eq16}. The other half of \eqref{eq16} follows by interchanging $T_hu$ and $u$.
\end{proof}

This result provides a bound for the functions $T_h^nu$ on a given compact set, and this will translate into a bound on the approximate solutions associated with the $T_h$. The next lemma provides a precise statement.

\begin{lemma}Assume that the operators $T_h$ satisfy the conditions given in Lemma 16.3 and let $u_h$ be the approximate solutions associated with the $T_h$. Let $K$ be a compact subset of $\RR^N$ and let $u_0$ be $L$-Lipschitz and $C^3$ on $\RR^N$. Then there are constants $\kappa>0$ and $C_K>0$ such that  
for all $s,t\in\RR^+$, $\fxx,\fxy\in K$, and $h<\kappa$, 
\begin{equation}\label{eq18c}
|{u}_h(s,\fxx)-{u}_h(t,\fxy)|\leq L|\fxx-\fxy|+
\begin{cases}
2C_Kh^\alpha\quad\kern16pt\text{if}\quad |s-t|\leq h^\alpha;\\
2C_K|s-t|\quad\text{if}\quad |s-t|\geq h^\alpha.
\end{cases}
\end{equation}
\end{lemma}

\begin{proof} Approximate solutions are defined in Definition 15.11 by 
$u_h(t,\fxx)=T_h^nu_0(\fxx)$ if $t=nh^\alpha$ and by linear interpolation for $t\in(nh^\alpha,(n+1)h^\alpha)$. Thus,
\begin{equation}\label{eq1612}
{u}_h(t,\fxx)=\frac{t-nh^\alpha}{h}u_h((n+1)h^\alpha,\fxx)+\frac{(n+1)h^\alpha-t}{h}u_h(nh^\alpha,\fxx),
\end{equation}
where $nh^\alpha\leq t\leq (n+1)h^\alpha$.

 
Lemma 6.5 states that $T_h^n$ maps Lipschitz functions into Lipschitz functions without increasing the Lipschitz constant, so we have immediately that 
\[
|u_h(nh^\alpha,\fxx)-u_h(nh^\alpha,\fxy)|\leq L|\fxx-\fxy|
\]
for all $\fxx,\fxy\in\RR^N$. The representation \eqref{eq1612} shows that this is true for all values of $t$:
\begin{equation}\label{eq18a}
|{u}_h(t,\fxx)-{u}_h(t,\fxy)|\leq L|\fxx-\fxy|.
\end{equation}

Now take $m\leq n$ and note that $T_h^{n-m}u_h(mh^\alpha,\cdot)(\fxx)=u_h(nh^\alpha,\fxx)$. Then by Lemma 16.3 we have
\begin{equation}\label{eq1613}
\begin{aligned}
|u_h(mh^\alpha,\fxx)-u_h(nh^\alpha,\fxx)|&=|T_h^{n-m}u_h(mh^\alpha,\cdot)(\fxx)-u_h(mh^\alpha,\fxx)|\\
&\leq C_K|m-n|h^\alpha,
\end{aligned} 
\end{equation}
where this holds for all $h<\kappa$ and all $\fxx\in K$. The next step is to replace $mh^\alpha$ and $nh^\alpha$ with $s$ and $t$ where $mh^\alpha\leq s<(m+1)h^\alpha$ and $nh^\alpha\leq t<(n+1)h^\alpha$. For this, we use \eqref{eq1612} and write
\begin{align*}
h^\alpha[{u}_h(s,\fxx)-{u}_h(t,\fxx)]=&(s-mh^\alpha)[u_h((m+1)h^\alpha,\fxx)-u_h((n+1)h^\alpha),\fxx)]\\
&+((m+1)h^\alpha-s)[u_h(mh^\alpha,\fxx)-u_h(nh^\alpha,\fxx)]\\
&+((s-t)-(m-n)h^\alpha)[u_h((n+1)h^\alpha,\fxx)-u_h(nh^\alpha,\fxx)].
\end{align*}
This representation and \eqref{eq1613} lead directly to the estimate
\[
|{u}_h(s,\fxx)-{u}_h(t,\fxx)|\leq C_K|m-n|h^\alpha+\Big|\frac{s-t}{h^\alpha}-(m-n)\Big|C_Kh^\alpha.
\]
Since $mh^\alpha\leq s<(m+1)h^\alpha$ and $nh^\alpha\leq t<n+1)h^\alpha$, we have 
\[
\Big|\frac{s-t}{h^\alpha}-(m-n)\Big|\leq1, 
\]
and thus
\[
|{u}_h(s,\fxx)-{u}_h(t,\fxx)|\leq C_K(|m-n|+1)h^\alpha.
\]
By analyzing the cases $|s-t|\leq h^\alpha$ and $|s-t|\geq h^\alpha$, one arrives at the following dichotomy:
\begin{equation}\label{eq18b}
|{u}_h(s,\fxx)-{u}_h(t,\fxx)|\leq
\begin{cases}
2C_Kh^\alpha\quad\kern16pt\text{if}\quad |s-t|\leq h^\alpha,\\
2C_K|s-t|\quad\text{if}\quad |s-t|\geq h^\alpha,
\end{cases}
\end{equation}
for $\fxx\in K$ and $h<\kappa$. Inequalities \eqref{eq18a} and \eqref{eq18b} imply \eqref{eq18c}.
\end{proof}

Inequality \eqref{eq18c} allows us to prove the following lemma, which is an application of the Ascoli--Arzela Theorem. This is the result that was announced in the introduction to the section.

\begin{lemma}Let $\{h_n\mid n\in\NN\}$ be any decreasing sequence such that $h_n\to0$ as $n\to\infty$. Then there is a subsequence of $\{{u}_{h_n}\}$ that converges uniformly to a continuous function $u$ on every compact subset $\RR^+\times\RR^N$.
\end{lemma}

\begin{proof}Consider the compact sets $K_m=[0,m]\times{\overline D}(0,m)$, $m\in\NN$. We will prove the result for $K=K_1$ and leave the rest of the proof as an exercise. 

To apply the Ascoli--Arzela Theorem, we must show that the functions $\{{u}_{h_n}\}$ are equicontinuous on $K$. This means that, given $\epsilon>0$, we must exhibit a $\delta=\delta(\epsilon)$ such that $|\fxx-\fxy|+|s-t|\leq\delta$ implies that $|{u}_{h_n}(s,\fxx)-{u}_{h_n}(t,\fxy)|\leq\epsilon$ uniformly for all $n\in\NN$ and $(s,\fxx), (t,\fxy)\in K$. Since equicontinuity in the spatial variable is obvious, we will concentrate on the time variable. To simplify the notation and thus to exhibit the ideas better, we set up the following situation. Suppose we have continuous functions $v_n$ ($v_n=u_{h_n})$ such that, for $h<\kappa$, 
\begin{equation*}\label{eq18d}
|v_n(s)-v_n(t)|\leq 
\begin{cases}
2C_Kh_n^\alpha\quad\kern16pt\text{if}\quad |s-t|\leq h_n^\alpha;\\
2C_K|s-t|\quad\text{if}\quad |s-t|\geq h_n^\alpha.
\end{cases}
\end{equation*}

Given $\epsilon>0$, choose $n'=n'(\epsilon)$ such that $2C_Kh_{n'}^\alpha\leq\epsilon$ and $h_{n'}<\kappa$. Now choose $\delta'=\delta'(\epsilon)$ such that $|s-t|\leq\delta'$ implies that $|v_n(s)-v_n(t)|\leq\epsilon$ for $n\geq n'$. (There are only a finite number of these $n$, so this is possible.) Finally, let $\delta=\min\{h_{n'}^\alpha,\delta'\}$. If $|s-t|\leq\delta$ and $n\leq n'$, then, by the definition of $\delta$, $|v_n(s)-v_n(t)|\leq\epsilon$. On the other hand, if $|s-t|\leq\delta$ and $n>n'$, then there are two cases: If $|s-t|\leq h_n^\alpha$, then
\[
|v_n(s)-v_n(t)|\leq\ 2C_Kh_n^\alpha\leq 2C_Kh_{n'}^\alpha\leq\epsilon;
\]
if $|s-t|\geq h_n$, then
\[
|v_n(s)-v_n(t)|\leq 2C_K|s-t|\leq2C_K\delta\leq2C_Kh_{n'}^\alpha\leq\epsilon.
\]
This proves the result, once we restore the space variable and the original notation.
\end{proof}

\begin{exercise}We have just shown that there is a sequence $\{{u}_{h_n}\}$ that converges uniformly (hence to a continuous function) on the compact set 
$K_1=[0,1]\times{\overline D}(0,1)$. The same argument shows that there is a subsequence of $\{{u}_{h_n}\}$ that converges uniformly on $K_2=[0,2]\times{\overline D}(0,2)$, and so on for all $K_n$. Use a diagonal process to show that there is a subsequence of $\{{u}_{h_n}\}$ that converges uniformly on any compact subset of $\RR^+\times\RR^N$. \finex
\end{exercise}

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

The study of median filters has been a major theme of the book. They were introduced in Chapter 9, first as set operators $\setM_k$ and then as function operators $\fcnM_k$. These filters were defined in terms of a nonnegative measurable weight function $k:\RR^N\to\RR$ that is normalized by
\[
\int_{\RR^N}k(\fxy)\,\rmd\fxy=1.
\]
It was shown in Proposition 9.4 that $\fcnM_k$ can be represented as
\[
\fcnM_ku(\fxx)=\sup_{|B|_k=1/2}\inf_{\fxy\in\fxx+B}u(\fxy),
\]
where $|B|_k=\int_Bk(\fxy)\,\rmd\fxy$. One of the main results, Proposition 9.7, was that, if $k$ is not separable and if $u$ is continuous, then $\fcnM_ku$ is continuous and
\[
\fcnM_ku(\fxx)=\inf_{|B|_k\geq1/2}\sup_{\fxy\in\fxx+B}u(\fxy).
\]
Theorem 10.4 provided an infinitesimal interpretation of $\fcnM_k$ in the case $k$ is the uniform measure on the unit disk in $\RR^2$. It was shown there how the scaled operator $(\fcnM_k)_h$ was related to curvature motion. This result was extended to $\RR^N$ in Theorem 11.3; there we assumed that $k$ was radial, was in the Schwartz class, and had connected compact support; the last assumption ensured that $k$ was not separable. Along the way, we showed that $(\fcnM_k)_h=\fcnM_{k_h}$, where $k_h(\fxx)=(1/h^N)k(\fxx/h)$. 

All of the pieces are now in place to prove that the approximate solutions of iterated median filters converge to viscosity solutions of mean curvature equations. Before we do this, it is important to be quite precise about the assumptions we have made to fashion the various components:
\begin{enumerate}[$\bullet$]\setlength\itemsep{2pt}
\item $k$ is radial, it has compact, connected support, and it belongs to the Schwartz class (Theorem 11.3), or $k$ is the uniform distribution on the unit disk in $\RR^2$ (Theorem 10.4). 
\item Theorem 10.4 was proved under the assumption that $u$ is $C^2$, and Theorem 11.3 was proved assuming that $u$ is $C^3$.
\end{enumerate}

\begin{theorem}[Convergence of iterated median filters] Assume that the weight function $k$ satisfies the conditions listed above. Let $u_0$ be a Lipschitz function that is also $C^3$. Let $\{u_h\}$, $h\leq1$, be the set of approximate solutions associated with the operators $T_h^n$, where $T= \fcnM_k$. Then $\{u_h\}$ has a limit point $u$ in the sense of convergence on compact sets and $u$
is a viscosity solution of the PDE
\[
\frac{\partial u}{\partial t}=\frac1{6}|Du|{\rm curv}(u)
\] 
in the case $k$ is the uniform measure on the unit disk in $\RR^2$, and $u$ a viscosity solution of
\[
\frac{\partial u}{\partial t}=\frac1{2}c_k|Du|{\rm curv}(u)
\] 
in the $N$-dimensional case. In this case, ${\rm curv}(u)$ is the mean curvature of $u$ and $c_k$ is the constant given in Lemma 11.2.
\end{theorem}
\begin{proof}The first thing to note is that the operators we are considering are $\alpha$-uniformly consistent with their associated equations, where $\alpha=2$. This is the content of Theorem 10.4 in case $k$ is the uniform measure on the unit disk in $\RR^2$, and it is the content of Theorem 11.3 in case $k$ is radial, has compact, connected support, and belongs to the Schwartz class. These operators have bounded structuring elements so they clearly satisfy a $\beta$-uniform local comparison principle with $\beta=+\infty$.

Since median filters and $u_0$ satisfy all of the other hypotheses of the lemmas of section 16.3, Lemma 16.5 ensures that the set of approximate solutions $\{u_h\}$, for any one of these filters, has a limit point $u$ in the following sense: There is a sequence $h_n$ such that $h_n\to0$ as $n\to\infty$ and such that $u_{h_n}\to u$ uniformly on compact subsets of $\RR^+\times\RR^N$. The hypotheses being satisfied, the Barles--Souganidis theorem (Proposition 15.13) states that $u$ is a viscosity solution of the PDE associated with the operators $T_h$.
\end{proof}

The action of iterated median filters and the action of the corresponding PDE are illustrated and compared in Figures 16.1 and 16.2.

\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.}
\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 are very close, when the
curvatures of the level lines are not too large. Indeed, the iterated median filter converges towards the viscosity solution of the curvature motion. Left: simple shape 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.}
\end{figure}

\section[Convergence of iterated affine-invariant operators]{Convergence of iterated affine-invariant operators to affine-invariant curvature motion}

The plan is to prove a theorem for iterated affine-invariant operators like the one we have just demonstrated for median filters. We will do this in $\RR^2$. 
 

\begin{theorem}Assume that the set of structuring elements $\mathcal B$ is affine invariant and 1-localizable and that $c_{\mathcal B}^+>0$. Let
\[
IS_hu(\fxx)=\inf_{B\in h\mathcal B}\sup_{\fxy\in\fxx+B}u(\fxy)\quad\text{and}\quad
SI_hu(\fxx)=\sup_{B\in h\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$. Let $u_h$ be the approximate solutions generated by $T_h$ with an initial function $u_0$ that is $C^3$ and Lipschitz on $\RR^2$. Then the set $\{u_h\}$ has a unique limit point $u$ in the sense of uniform convergence on compact sets, and $u$ is a viscosity solution 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}
\begin{proof}We saw in Lemma 14.4 that 1-localizability and affine invariance imply that $c_{\mathcal B}^-=0$. On the other hand, we have shown that $c_{\mathcal B}^+>0$ for only two cases (again Lemma14.4). Thus, we need the assumption that $c_{\mathcal B}^+>0$ to avoid the possibility of a vacuous result.

From Lemma 14.3 and Theorem 14.4 we know that the operators $IS_h$ and $SI_h$ are $\alpha$-uniformly consistent with the first two equations of \eqref{eq16x}. Lemmas 14.5 and 14.6 state that $SI_hIS_h$ is $\alpha$-uniformly consistent with the third equation in \eqref{eq16x}. For each case, $\alpha=4/3$.

Lemma 13.3 states that $IS_h$ and $SI_h$ satisfy a $\beta$-uniform local comparison principle with $\beta=2$. Although it is not specifically stated there, Lemma 13.4$(iv)$ implies immediately that $SI_hIS_h$ also satisfies $\beta$-uniform local comparison principle in case $u$ is Lipschitz on $\RR^2$, which is part of the assumptions for Theorem 16.7. 

Since the hypotheses of Lemmas 16.3--16.5 are satisfied by all three operators, we know from Lemma 16.5 that the approximate solutions have a limit point $u$. That is, for each case: $IS_h$, $SI_h$, and $SI_hIS_h$, there is a sequence $u_{h_n}$ of approximate solutions that converge uniformly on compact subsets of $\RR^+\times\RR^2$ to a continuous function $u$. Finally, Proposition 15.13, the Barles--Souganidis theorem, states that $u$ is a viscosity solution of the appropriate PDE in \eqref{eq16x}.
\end{proof}

Figures 16.3 and 16.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 16.3. Figure 16.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}}
\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.}
\end{figure}














To the extent that we know viscosity solutions are unique (see Theorem 15.14), we have also shown that the set of approximate solutions $\{u_h\}$, $0<h\leq1$, has only one limit point (or accumulation point) in the topology of uniform convergence on compact sets.

This completes Part IV, and with it a large part of the overall program. But before moving to new topics, we add a few comments about scaling. We chose to define \textit{uniformly consistent} and \textit{approximate solutions} in terms of a parameter $\alpha$. This has the advantage that it agrees directly with the asymptotic results in Theorems  11.3 and 14.4. For example, Theorem 14.4 states that 
\[
T_hu(\fxx)-u(\fxx)=h^{4/3}c_{\mathcal B}|Du(\fxx)|\Big(\frac1{2}{\rm curv}(u)(\fxx)^+\Big)^{1/3}+o(\fxx,h^{4/3}),
\]
so the $T_h$ are $\alpha$-uniformly consistent with the PDE, where $\alpha=4/3$. Another approach is to define a new set of operators $S_h$ by $S_h=T_{h^{3/4}}$. Then the $S_h$ are 1-uniformly consistent with the PDE. The approximate solutions for $S_h$ are defined with $\alpha=1$, they converge, and the limit point is a viscosity solution of the PDE. This approach has the advantage that the notation is simpler. In either case, $\alpha=1$ or $\alpha>1$, the definition of the approximate solutions must be properly scaled.

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

