%gmChap10.tex.

\graphicspath{{./figures/}}

\chapter[Asymptotic Behavior
 in ${\mathbb R^2}$]
 {Asymptotic Behavior of $\SMTCII$  Operators, Dimension Two
  \label{Chap10}}


  As we know by Theorem \ref{whoiswho}, a function operator on
  $\mathcal F$ is
   contrast and translation invariant and
standard monotone if and only if it has a  sup-inf, or
equivalently an inf-sup form
\[
Tu(\fxx)=\inf_{B\in\mathcal B} \sup_{\fxy\in\fxx+ B}u(\fxy),
\]
where $\mathcal B$ is a standard subset of $\mathcal L$.
 In case we require such
operators to be isotropic and local, it is enough to take for
$\mathcal B$ any set of sets invariant by rotation and contained
in some $B(0,M)$ by Proposition \ref{localityofT}.


 We
will see, however, that such operators fall into a few  classes
when we make them more and more local. To see this, we introduce a
scale parameter $0<h\leq1$ and define the scaled operators $T_h$
by
\[
T_hu(\fxx)=\inf_{B\in\mathcal B} \sup_{\fxy\in\fxx+ hB}u(\fxy).
\]
We will prove that  in the limit, as $h$ tends to zero, the action
of $T_h$ on smooth functions is not as varied as one might expect
given the possible sets of structuring elements.   As an example,
we will show that if $T_h$ is a scaled median operator, then
\[
T_hu(\fxx)-u(\fxx)=h^2C|Du(\fxx)|{\rm curv}(u)(\fxx)+o(h^2),
\]
where the constant $C$ depends only on  the function $k$ used to
define the median operator. Thus, the operator $|Du|{\rm curv}(u)$
plays the same role for the weighted median filters,  as the
Laplacian $\Delta u$ does for linear operators.  In short, we
shall get contrast invariant analogues of Theorem
\ref{theorem2.2}.




\section{Asymptotic behavior theorem in $\mathbb R^2$}
A simple real function  will describe the asymptotic behavior of
any local contrast invariant filter.
\begin{definition}
 Let $T$ be a $\SMTCII$ local operator.
  Consider the real function
 $H(s)$, $s\in\RR$,
\begin{equation}\label{eq113}
H(s)=T[x+s y^2](0),
\end{equation}
 where $T[x+s y^2]$ denotes ``$Tu$ with $u(x,y)=x+s y^2$.'' $H$
 is called the {\rm structure function}  of $T$.
 \end{definition}
Notice that $u(x,y)=x+sy^2$ is not in $\mathcal F$, so we use here
the extension  described in the introduction. The function  $H(s)$
is well defined by the result of Exercise
\ref{propertiesofextensionofinfsup}.
 \begin{proposition}
The structure function of a local $\SMTCII$ operator is nondecreasing, Lipschitz, and satisfies for $h>0$,
 \begin{equation}\label{eq115}
T_h[x+s y^2](0)=hT[x+hs y^2](0)=hH(hs),
\end{equation}
\begin{equation}\label{eq116}
T_h[x](0)=hT[x](0)=hH(0)
\end{equation}
 \end{proposition}
 \begin{proof} Take $T$ in the inf-sup form with $\mathcal
 B\subset B(0,M)$, $0\leq M<1.$

   Since $T$ is monotone, $H$ is a nondecreasing function. Let
    $B\in\mathcal B$ be one of the structuring
  elements that define $T$ and write $x+s_1y^2=x+s_2y^2 + (s_1-s_2)y^2$. Then
\[
\sup_{(x,y)\in B}(x+s_1y^2)\leq\sup_{(x,y)\in B}(x+s_2y^2)+|s_2-s_1|M^2,
\]
since $B$ is contained in $D(0,M)$. By taking the infimum  over
$B\in\mathcal B$ of both sides and using the definition of $H$, we
see that
\[
H(s_1) - H(s_2)\leq  |s_1-s_2|M^2.
\]
By interchanging $s_1$ and $s_2$ in this last  inequality, we
deduce the Lipschitz relation
\begin{equation}\label{eq114}
|H(s_1)-H(s_2)|\leq |s_1-s_2|M^2.
\end{equation}
\end{proof}


\begin{theorem}\label{theorem10.1}
 Let $T$ be a local $\SMTCII$
operator and $T_h$, $1\geq h>0$ its scaled versions. Call $H$ its
structure function. Then, for any $C^2$ function $u:\RR^2\to\RR$,
\[
T_hu(\fxx)-u(\fxx)=hH(0)|Du(\fxx)|+o(h^2).
\]
 \end{theorem}
\begin{proof} By Propositions \ref{infsupformaswell},
\ref{localityofT} and  \ref{isotropyetB}, we can take $T$ in the inf-sup
 form and assume, for all
$B$ in $\mathcal B$,  that $B\subset B(0,M)$ and that $\mathcal B$
is invariant under rotations. Set $p=|Du(\fxx)|$. By a suitable
rotation, and since $T$ is isotropic, we may assume that
$Du(\fxx)=(|Du(\fxx)|,0)$, and the first-order Taylor expansion of
$u$ in a neighborhood of $\fxx$ can be written as
\begin{equation}\label{eq117}
u(\fxx+\fxy)=u(\fxx)+px+O(\fxx,|\fxy|^2),
\end{equation}
where $\fxy=(x,y)$ and
$
|O(\fxx,|\fxy|^2)|\leq C|\fxy|^2
$
for $\fxy\in D(0,M)$. Hence,
\begin{equation}\label{eq117a}
u(\fxx+h\fxy)-u(\fxx)\leq phx +Ch^2|\fxy|^2\quad\text{and}\quad phx\leq u(\fxx+h\fxy)-u(\fxx)+Ch^2|\fxy|^2
\end{equation}
for all $\fxy\in D(0,M)$. Since $hB\subset D(0,hM)$, we see from the first inequality of \eqref{eq117a} that
\[
\sup_{\fxy\in B}u(\fxx+h\fxy)-u(\fxx)\leq \sup_{\fxy\in B}[phx]+\sup_{\fxy\in B}Ch^2|\fxy|^2= hp\sup_{\fxy\in B}[x]+CM^2h^2.
\]
This implies that
\[
T_hu(\fxx)-u(\fxx)\leq hp\inf_{B\in\mathcal B}\sup_{\fxy\in B}[x]+ CM^2h^2
\]
for $0<h\leq1$, and since $\inf_{B\in\mathcal B}\sup_{\fxy\in
B}[x]=T[x](0)=H(0)$, we see that
\[
T_hu(\fxx)-u(\fxx)\leq hpH(0)+CM^2h^2.
\]
The same argument applied to the second inequality of \eqref{eq117a} shows that
\[
hpH(0)\leq T_hu(\fxx)-u(\fxx)+CM^2h^2,
\]
so $|T_hu(\fxx)-u(\fxx)-hpH(0)|\leq CM^2h^2$. Since
$p=|Du(\fxx)|$, we see that
\[
T_hu(\fxx)-u(\fxx)=hH(0)|Du(\fxx)|+O(\fxx,h^2),
\]
which proves the result in case $p\not=0$.
\end{proof}
\begin{figure}[!t]
\setkeys{Gin}{width=8cm} \centerline{
\includegraphics{fig10.01.1.eps}
} \caption[Erosion and motion of level lines]{\label{f111}The
result of smoothing with an erosion is independent of the
curvature of the level lines. Left: image of a simple shape.
Right: difference of this image and  its eroded image. Note that
the width of the difference is constant. By Theorem
\ref{theorem10.1}, all filters such that $H(0)\neq 0$ perform such
an erosion, or a dilation.}
\end{figure}
\noindent{\bf Interpretation.}  Theorem \ref{theorem10.1}   tells
us that the behavior of local contrast invariant  operators $T_h$
depends, for small $h$, completely on the action of $T$ on the
test function $u(x,y)=x$. Assume $H(0)=H(0)\not=0$. When $h\to 0$,
$T$ acts like a dilation by a disk $D(0,h)$ if $H(0)>0$ and like
an erosion with $D(0,h)$ if $H(0)<0$ (see Proposition
\ref{proposition8.8}). Thus, if $H(0)\not=0$, there is no need to
define $T$ with a complicated set of structuring elements.
Asymptotically these operators are either dilations or erosions,
and these can be defined with a single structuring element,
namely, a disk. Exercise \ref{exercise10.3} gives the more general
PDE obtained when $T$ is local but not isotropic.




\subsection{The asymptotic behavior of $T_{h}$ when $ T[ x ]( 0 ) = 0$}

If $H(0)=T[x](0)=0$, then Theorem \ref{theorem10.1} is true but
not very interesting. On the other hand, operators for which
$T[x](0)=0$ are interesting. If we consider $Tu(\fxx)$ to be a
kind of average of the values of $u$ in a neighborhood of $\fxx$,
then assuming that $T[x](0)=0$ makes sense. This means, however,
that we must consider the next term in the expansion of $T_hu$; to
do so we need to assume that $u$ is $C^3$. This is the content of
the next theorem, which is the main theoretical result of the
chapter. The proof is more involved than that of Theorem
\ref{theorem10.1}, but at the macro level, they are similar. We
start with some precise Taylor expansion of $u$.

\begin{lemma}\label{Taylorordre3} Let $u(\fxy)$ be $C^3$ around some point
$\fxx\in \RR^2$. By using  adequate Euclidean coordinates
$\fxy=(x,y)$, we can expand $u$ in a neighborhood of $\fxx$ as
\begin{equation}\label{eq119}
u(\fxx+h\fxy)= u(\fxx)+h(px+ahx^2+bhy^2+chxy)+R(\fxx,h\fxy),
\end{equation} where
$|R(\fxx,h\fxy)|\leq Ch^3$ for all $\fxx\in K$,  $\fxy\in D(0,M)$
and $0\leq h\leq 1$.

\end{lemma}
\begin{proof}
Set $p=|Du(\fxx)|$. We define the local coordinate system by
taking $\fxx$ as origin  and  $Du(\fxx)=(p,0)$. Relation
\eqref{eq119} is nothing but a Taylor expansion where $R$ can be
written as
\[
R(\fxx,h\fxy)=\Bigg(\int_0^1(1-t)^2 D^3u(\fxx+th\fxy)\,\rmd
t\Bigg)h^3\fxy^{(3)}.
\] The announced estimate follows because
 the function $\fxx\mapsto\|D^3u(\fxx)\|$ is
 continuous and thus bounded on the compact set $K+D(0,M)$.
\end{proof}

\begin{theorem} \label{theorem10.2} Let $T$ be a local
$\SMTCII$ operator on $\mathcal F$ whose structure function $H$ satisfies $H(0)=0$. Then for every $C^3$ function $u$
on $\RR^2$,

\begin{enumerate}[$(i)$]\setlength\itemsep{2pt}
\item On every compact set $K\subset\{\fxx\mid Du(\fxx)\not=0\}$,
\[
T_hu(\fxx)-u(\fxx)=h|Du(\fxx)|H\Big(\frac1{2}h\;{\rm curv}(u)(\fxx)\Big)+O(\fxx,h^3),
\]
where $|O(\fxx,h^3)|\leq C_Kh^3$ for some constant $C_K$ that
depends only on $u$ and $K$.

\item On every compact set $K$ in $\RR^2$,
\[
|T_hu(\fxx)-u(\fxx)|\leq  C_K'h^2
\]
where the constant $C_K'$ depends only on $u$ and $K$.
\end{enumerate}
\end{theorem}

\begin{proof} We take $T$ in the inf-sup form and  $\mathcal B$ bounded
by $D(0,M)$ and isotropic.  Let us use the Taylor expansion
\eqref{eq119}. For $0<h\leq1$,
\[
u(\fxx+h\fxy)= u(\fxx)+h(px+ahx^2+bhy^2+chxy)+R(\fxx,h\fxy),
\]
and so for any $B\in\mathcal B$,
\[
\sup_{\fxy\in B}u(\fxx+h\fxy)\leq u(\fxx)+h\sup_{\fxy\in
B}[u_h(x,y)]+\sup_{\fxy\in B}|R(\fxx,h\fxy)|.
\]
Thus,
\begin{equation}
T_hu(\fxx)\leq u(\fxx)+hT[u_h(x,y)](0)+\inf_{B\in\mathcal
B}\sup_{\fxy\in B}|R(\fxx,h\fxy)|,
\end{equation}
where $u_h(x,y)=px+ahx^2+bhy^2+chxy$ and $\fxy=(x,y)$. Now let $K$
be an arbitrary compact set. From Lemma \ref{Taylorordre3} we
deduce that
\begin{equation}
T_hu(\fxx)\leq u(\fxx)+hT[u_h(x,y)](0)+Ch^3
\end{equation}
for all $\fxx\in K$. The same analysis shows that
\begin{equation}
u(\fxx)\leq T_hu(\fxx)+hT[u_h(x,y)](0)+Ch^3,
\end{equation}
and we conclude that
\begin{equation}\label{eq1111}
T_hu(\fxx)- u(\fxx)=hT[u_h(x,y)](0)+O(\fxx,h^3)
\end{equation}
for all $\fxx\in K$ where  $|O(\fxx,h^3)|\leq C_Kh^3$.    Relation
\eqref{eq1111} reduces the proof to an analysis of $Tu_h(0)$.

\bigskip
\noindent{\bf Step 1: Estimating ${\bm T}{\bm u}_{\bm h}\bm(\bm0\bm)$.} If $\fxx\in K$ and $\fxy=(x,y)\in B$, then $|\fxy|\leq M$ and
\[
px-h(|a|+|b|+|c|)M^2\leq u_h(x,y)\leq px+h(|a|+|b|+|c|)M^2.
\]
We write this as
\[
px-\frac{hM^2}{2}\|D^2u(\fxx)\|\leq u_h(x,y)\leq
px+\frac{hM^2}{2}\|D^2u(\fxx)\|.
\]
By assumption $T[x](0)=0$ (hence $T[px](0)=0$), so after applying $T$ to the inequalities, we see that
\begin{equation}%\label{eq1112}
|T[u_h(x,y)](0)|\leq \frac{hM^2}{2}\|D^2u(\fxx)\|.
\end{equation}
This and equation \eqref{eq1111} show that
\begin{equation}\label{eq1112}
|T_hu(\fxx)-u(\fxx)|\leq \frac{h^2M^2}{2}\|D^2u(\fxx)\|+C_Kh^3
\end{equation}  for
  $\fxx\in K$ and   $0<h\leq1$. This proves part $(ii)$.  Let us
  now prove $(i)$.  We just recall the meaning of $p$ and $b$, namely
$b=(1/2){\rm curv}(u)(\fxx)|Du(\fxx)|$  and $p=|Du(\fxx)|$. Those
terms are the only terms appearing in the main announced result
$(i)$. So the proof of $(i)$  consists of getting rid of $a$ and
$c$ in the asymptotic expansion $(Tu_h)(0)$. This elimination is
performed in Steps 2 and 3.

\bigskip
\noindent{\bf Step 2: First reduction.} We now focus on proving
$(i)$,  and for this we assume that $p=|Du(\fxx)|\not=0$. Define
$C=(|a|+|b|+|c|)M^2$. By Step 1, for every $B\in\mathcal B$, we
see that
\[
\sup_{\fxy\in B} u_h(x,y)\geq \inf_{B\in\mathcal B}\sup_{\fxy\in B} u_h(x,y) = T[u_h(x,y)](0)\geq-Ch.
\]
If $\fxy=(x,y)\in B$ and $x<-2Ch/p$, then
\[
u_h(x,y)=px+ahx^2+bhy^2+chxy<-2Ch + h(|a|+|b|+|c|)M^2=-Ch.
\]
Thus, if we let $C'=2C/p$, then for any $B\in\mathcal B$ we have
\[
\sup_{\fxy\in B} u_h(x,y)=\sup_{\fxy\in B\cap\{(x,y)\mid x\geq-C'h\}} u_h(x,y)
\]

\bigskip
\noindent{\bf Step 3: Second reduction.}  Since
$T[u_h(x,y)](0)\leq Ch$ (Step 1), it is not necessary to consider
sets $B$ for which $\sup_{\fxy\in B} u_h(x,y)\geq Ch$. If
$\sup_{\fxy\in B} u_h(x,y)\leq Ch$, then for all $(x,y)\in B$
\[
px +ahx^2+bhy^2+chxy\leq Ch,
\]
and hence
\[
x\leq\frac1{p}(Ch+(|a|+|b|+|c|)M^2h)\leq \frac{2Ch}{p}=C'h.
\]
This means that we can write
\begin{equation}\label{eq1113}
T[u_h(x,y)](0)=\inf_{B\in\mathcal B, B\subset\{(x,y)\mid x\leq C'h\}}\sup_{\fxy\in B} u_h(x,y),
\end{equation}
and by the result of Step 2,
\begin{equation}\label{eq1114}
T[u_h(x,y)](0)=\inf_{B\in\mathcal B, B\subset\{(x,y)\mid x\leq C'h\}}\sup_{\fxy\in B\cap\{(x,y)\mid x\geq-C'h\}} u_h(x,y).
\end{equation}
This relation is true if we replace $u_h(x,y)$ with $px+bhy^2$ and leads directly to the inequality
\begin{eqnarray*}
% \nonumber to remove numbering (before each equation)
  T[u_h(x,y)](0) &\leq& T[px+bhy^2](0) \\
   &+& h\inf_{B\in\mathcal B, B\subset\{(x,y)\mid x\leq C'h\}}\sup_{\fxy\in
B\cap\{(x,y)\mid x\geq-C'h\}}|ax^2+cxy|
\end{eqnarray*}

and, by interchanging $u_h(x,y)$ and $px+bhy^2$, to the equation
\begin{equation}
T[u_h(x,y)](0)=T[px+bhy^2](0) + \varepsilon(x,y).
\end{equation}
The error term is
\[
|\varepsilon(x,y)|\leq h^3|a|C'^2+h^2|c|C'M.
\]

\bigskip
\noindent{\bf Step 4: Conclusion.} We now return to equation \eqref{eq1111},
\[
T_hu(\fxx)- u(\fxx)=hT[u_h(x,y)](0)+O(\fxx,h^3),
\]
and replace $T[u_h(x,y)](0)$ with $T[px+bhy^2](0) +
\varepsilon(x,y)$ to obtain
\[
T_hu(\fxx)-u(\fxx)=hT[px+bhy^2](0) + h\varepsilon(x,y)+O(\fxx,h^3).
\]
By definition $H(s)=T[x+sy^2](0)$, so the last equation can be written as
\[
T_hu(\fxx)-u(\fxx)=hpH(bh/p) + h\varepsilon(x,y)+O(\fxx,h^3),
\]
or, by replacing $p$ and $b$ with $|Du(\fxx)|$  and $(1/2){\rm
curv}(u)(\fxx)|Du(\fxx)|$, as
\begin{equation}\label{eq1116}
T_hu(\fxx)-u(\fxx)=h|Du(\fxx)|H\Big(h\frac{1}{2}{\rm curv}(u)(\fxx)\Big) + h\varepsilon(x,y)+O(\fxx,h^3).
\end{equation}

To finish the proof, we must examine the error  term $\varepsilon$
to establish a uniform bound on compact sets where
$Du(\fxx)\not=0$. Thus, let $K$ be any compact subset of $\RR^2$
such that $K\subset\{\fxx\mid Du(\fxx)\not=0\}$. For $\fxy\in
D(0,M)$ (hence for $\fxy\in B\in B\in\mathcal B$), we have
$|\varepsilon(x,y)|\leq h^3|a|C'^2+h^2|c||C'|M$. Now,
$|a|C'^2+|c||C'|M$  is a continuous function of $Du(\fxx)$ and
$D^2u(\fxx)$ at each point $\fxx$ where $Du(\fxx)\neq 0$. Since
$u$ is $C^3$, all of the functions on the right-hand side of this
relation are continuous on $K$. Thus there is a constant $C_K'$
that depends only on $u$ and $K$ such that $|\varepsilon(x,y)|\leq
h^2C'_K$. By combining and renaming the constants $C_K$ and
$C'_K$, this completes the proof of $(i)$.
\end{proof}

\begin{exercise} Returning to the meaning in the preceding proof
 of $a$, $b$, $c$, $p$
and $C'$ in term of derivatives of $u$, check that $|a|C'^2+|c||C'|M$ is, as announced, a continuous function at each
point where $Du(\fxx)\neq 0$.
\end{exercise}




\section{Median filters and curvature motion in $\mathbb R^2$}

Recall that the median filter, $\fcnM_k$, defined in Chapter
\ref{Chap9} can be written by Proposition \ref{proposition9.4} as
\begin{equation}\label{eq1117}
\fcnM_ku(\fxx)=\sup_{B\in\mathcal B}\inf_{\fxy\in\fxx+B}u(\fxy),
\end{equation}
where $\mathcal B=\{B\in \mathcal  M\mid |B|_k=1/2\}$. The first
example we examine is $k=\bmone_{D(0,1)}/\pi$. This function is
not separable  in the sense of Definition \ref{separable}. So, by
Proposition \ref{egalitedemedianmoinsetplus},
$\fcnM_ku=\fcnM_k^-u$ and the median also has the inf-sup form
\begin{equation}
\fcnM_ku(\fxx)=\inf_{B\in\mathcal B}\sup_{\fxy\in\fxx+B}u(\fxy).
\end{equation}
 From Proposition \ref{localityofT} follows that the
set of structuring elements $\mathcal B'=\{B\in \mathcal B\mid
B\subset D(0,1)\}$ generates the same median filter. Thus we
assume in what follows that $B\subset D(0,1)$. There is one more
point that needs to be clarified, and we relegate it to the next
exercise.

\begin{exercise}\label{exercise10.5}
The scaled median filter $(\fcnM_k)_h$, $h<1$, is defined by
\begin{equation}
(\fcnM_k)_hu(\fxx)=\inf_{B\in h\mathcal B}\sup_{\fxy\in\fxx+B}u(\fxy).
\end{equation}
At first glance, it is not clear that this is  a median filter,
but, in fact, it is: Show that $(\fcnM_k)_h=\fcnM_{k_h}$, where
$k_h=\bmone_{D(0,h)}/\pi h^2$. \finex
\end{exercise}

The actions of median filters and comparisons  of these filters with other simple filters are illustrated in Figures
\ref{f111}, \ref{f112}, \ref{f114}, \ref{f115}, and \ref{f116}. Everything is now in place to investigate the
asymptotic behavior of the scaled median filter $\fcnM_{k_h}$,  which is represented by
\[
\fcnM_{k_h}u(\fxx)=\inf_{B\in h\mathcal B}\sup_{\fxy\in\fxx+B}u(\fxy),
\]
where $h\mathcal B=\{B\mid |B|_{k_h}=1/2, B\subset D(0,h)\}$.  The main result of this section, Theorem
\ref{theorem10.4}, gives an infinitesimal interpretation of this filter. We know that the median is a $\SMTCII$
operator, and it is local in our case. The proof of the next lemma is quite special, having no immediate generalization
to $\RR^N$.

\begin{lemma}\label{lemma10.3}
\[
\fcnM_k[x+s y^2](0)=\frac{s }{3}+O(|s|^3).
\]
\end{lemma}
\begin{proof}Represent $\fcnM_k$ by
$\fcnM_ku(\fxx)=\sup\{\lambda\mid \fxx\in \setM_k\levelset_\lambda
u\}$. Then
\[\fcnM_k[x+s y^2](0)=\sup\{\lambda\mid 0\in \setM_k\levelset_\lambda[x+s y^2]\,\}.
\]
By definition, $0\in \setM_k\levelset_\lambda[x+s y^2]$ if and
only if $|\levelset_\lambda[x+s y^2]|_k\geq 1/2$. This implies
that $\fcnM_k[x+s y^2](0)=m(s )$, where $|\levelset_{m(s)}[x+s
y^2]|_k=1/2$, and this is true if and only if the graph of $x+s
y^2=m(s)$ divides $D(0,1)$ into two sets that have equal area. Of
course, we are only considering small $s$, say $|s|\leq 1/2$. The
geometry of this situation is illustrated in Figure \ref{f113}.
The signed area between the $y$-axis and the parabola $P(s)$ for
$|y|\leq1$ is
\[
\int_{-1}^1(m(s )-s y^2)\,\rmd y=2m(s )-\frac{2s }{3}.
\]
Thus, $m(s )$ is the proper value if and only if
\begin{equation}\label{eq1118}
m(s )-\frac{s }{3}=\text{ Area}(ABE),
\end{equation}
where $ABE$ denotes the curved triangle  bounded by the parabola,
the circle, and the line $y=-1$. This area could be computed, but
it is sufficient to bound it by $\text{Area}(ABCD)$. The length of
 the base $AB$ is $|m(s )-s |$, and an easy computation shows that the
length of the height $BC$ is less than $(m(s )-s )^2$. This and
\eqref{eq1118} imply that
\[
\Bigg|m(s )-\frac{s }{3}\Bigg|\leq|m(s )-s |^3.
\]
From this we conclude that $m(s )=s /3+O(|s|^3)$, which proves the lemma.
\end{proof}
\begin{figure}[!t]
\setkeys{Gin}{width=8cm} \centerline{
\includegraphics{fig10.02.1.eps}
} \caption[Median filter and the curvature of level
lines]{\label{f112}Median filter and the curvature of level lines.
Smoothing with a median filter is related to the curvature of the
level lines. Left: image of a simple shape. Right: difference of
this image with itself after it has been smoothed by one iteration
of the median filter. We see, in black, the points which have
changed. The width of the difference is proportional to the
curvature, as indicated by Theorem \ref{theorem10.4}.}
\end{figure}

\begin{theorem}\label{theorem10.4} If $u:\RR^2\to\RR$ is $C^2$, then we  have the following expansions:
\begin{enumerate}[$(i)$]\setlength\itemsep{2pt}
\item On every compact set $K\subset\{\fxx\mid Du(\fxx)\not=0\}$,
\[
\fcnM_{k_h}u(\fxx)=u(\fxx)+\frac1{6}|Du(\fxx)|{\rm curv}(u)(\fxx)h^2+O(\fxx,h^3),
\]
where $|O(\fxx,h^3)|\leq C_Kh^3$ for some constant $C_K$ that depends only on $u$ and $K$.
\item On every compact set $K$ in $\RR^2$,
\[
|\fcnM_{k_h}u(\fxx)-u(\fxx)|\leq C_Kh^2
\]
where the constant $C_K$ depends only on $u$ and $K$.
\end{enumerate}
\end{theorem}
\begin{proof}We have shown (or it is immediate)
that the operator $T_h=\fcnM_{k_h}$ satisfies all of the
hypotheses of Theorem \ref{theorem10.2}. In particular,
$H(0)=\fcnM_k[x+s y^2](0)=0$ by Lemma \ref{lemma10.3}. Also by
Lemma \ref{lemma10.3}, $H(s)=s/3+O(|s|^3)$. This means that we
have
\[
H\Big(\frac1{2}h\;{\rm curv}(u)(\fxx)\Big)=\frac1{6}h\;{\rm
curv}(u)(\fxx)+O(h^3\;|{\rm curv}(u)(\fxx)|^3).
\]
The first result is now read directly  from Theorem
\ref{theorem10.2}$(i)$. Relation $(ii)$ follows immediately from
Theorem \ref{theorem10.2}$(ii)$.
\end{proof}

Our second example is called the Catt\'e--Dibos--Koepfler scheme.
It involves another application of Theorem \ref{theorem10.2}.

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig10.03.1.eps}
} \caption{\label{f113}When $s$ is small, the parabola $P(s)$ with
equation $x+ sy^2 = m$ divides $D(0,1)$ into two components. The
median value $m(s)$ of $x+ sy^2$ on $D(0,1)$ simply is the value
$m$ for which these two components have equal area.}
\end{figure}

\begin{theorem}\label{theorem10.5}
Let $\mathcal B$ be the set of all line segments of
length 2 centered at the origin of $\RR^2$. Define the operators
$SI_h$ and $IS_h$ by
\[
SI_hu(\fxx)=\sup_{B\in h\mathcal B}\inf_{\fxy\in\fxx+B}u(\fxy)\quad\quad\text{and}\quad\quad IS_hu(\fxx)=\inf_{B\in h\mathcal B}\sup_{\fxy\in\fxx+B}u(\fxy).
\]
If $u:\RR^2\to\RR$ is $C^2$ and $|Du(\fxx)|\not=0$, then
\[
\frac1{2}(IS_h+SI_h)u(\fxx)=u(\fxx)+h^2\frac{1}{4}{\rm curv}(u)(\fxx)|Du(\fxx)|+O(h^3).
\]
\end{theorem}
\begin{proof}The first step is to compute the action of the operators on $u(x,y)=x+s y^2$. Define $H(s)=IS[x+s y^2](0)$ and write $(x,y)=(r\cos\theta,r\sin\theta)$. Then
\[
H(s)=\inf_{-\frac{\pi}{2}\leq\theta\leq\frac{\pi}{2}}\sup_{-1\leq r \leq1}(r\cos\theta+s r^2\sin^2\theta).
\]
For $s\geq0$ and $r\geq0$,   the function $r\mapsto r\cos\theta+s
r^2\sin^2\theta$ is increasing. Hence,
\[
H(s)=\inf_{-\frac{\pi}{2}\leq\theta\leq\frac{\pi}{2}}(\cos\theta+s \sin^2\theta)=s
\]
for sufficiently small $s$, say, $s<1/2$. If $s\leq0$, then $H(0)=0$, since
\[
0\leq\sup_{-1\leq r \leq1} (r\cos\theta+s r^2\sin^2\theta)\leq\cos\theta.
\]
If $H^-(s)=SI[x+s y^2](0)$, then it is an easy check that $H^-(s)=-H(-s)$. Thus we have
\begin{equation*}
H(s)=
\begin{cases}
s, &\text{if $s\geq0$};\\
0, &\text{if $s<0$};
\end{cases}
\quad\quad\text{and}\quad\quad
H^-(s)=
\begin{cases}
0, &\text{if $s\geq0$};\\
s, &\text{if $s<0$}.
\end{cases}
\end{equation*}
Thus, $H(s)+H^-(s)=s$ for all small $s$. Since $H(0)=H^-(0)=0$,
the conclusions of Theorem \ref{theorem10.2} apply. By applying
Theorem \ref{theorem10.2}$(i)$ to $IS_h$ and $SI_h$ and adding, we
have
\begin{align*}
(IS_h+SI_h)u(\fxx)&=2u(\fxx)+h(H+H^-)\Big(\frac{h}{2}{\rm curv}(u)(\fxx)\Big)+O(h^3)\\
&=2u(\fxx)+\frac{h^2}{2}{\rm curv}(u)(\fxx)+O(h^3).
\end{align*}
Dividing both sides by two gives the result.
\end{proof}
\begin{exercise}
Prove the relation $H^-(s)=-H(-s)$ used in the above proof. \finex
\end{exercise}



\section{Exercises}


\begin{exercise}\label{exercise10.3} Assume that $T$ is a local
translation and contrast invariant operator, but not necessarily
isotropic. Show that
\[
T_hu(\fxx)=u(\fxx)+hT[Du(\fxx)\cdot\fxx](0) + O(h^2).\; \finex
\]
\end{exercise}

\begin{exercise}Let $\mathcal B$ be the set of all rectangles in the plane with length two, width $\delta<1$, and centered at the origin. Define the operators $IS_h$ and $SI_h$ by
\[
IS_hu(\fxx)=\inf_{B\in h\mathcal B}\sup_{\fxy\in\fxx+B}u(\fxy)
\quad\quad \text{and}\quad\quad SI_hu(\fxx)=\sup_{B\in h\mathcal
B}\inf_{\fxy\in\fxx+B}u(\fxy).
\]
\begin{enumerate}[(i)]\setlength\itemsep{2pt}
\item Let $u:\RR^2\to\RR$ be $C^2$. Compute the expansions of
$IS_hu(\fxx)$, $SI_hu(\fxx)$, and $(1/2)(IS_h+SI_h)u(\fxx)$ in
terms of small $h>0$. \item Take $\delta=h$ and compute the same
expansions. \item Take $\delta=h^\alpha$ and interpret the
expansions for $\alpha>0$ and for $\alpha<0$. \finex
\end{enumerate}
\end{exercise}

\section{Comments and references}

Merriman, Bence, and Osher \cite{Merriman:1992:DGM} discovered, and gave some heuristic arguments to prove, that a
convolution of a shape with a Gaussian followed by a threshold at $1/2$ simulated the mean-curvature motion given by
$\partial  u/\partial t=|Du|{\rm curv}(u)$. The consistency of their arguments was checked by Mascarenhas
\cite{Mascarenhas:1992:DGM}. Barles and Georgelin \cite{Barles:1995:SPC} and Evans \cite{Evans:1993:CAM} also gave
consistency proofs; in addition, they showed that iterated weighted Gaussian median filtering converges to the mean
curvature motion. An extension of this result to any iterated weighted median filter was given by Ishii in
\cite{Ishii:1994:GBM}. An interesting attempt to generalize this result to vector median filters was made Caselles,
Sapiro, and Chung in \cite{Caselles:2000:VMF}.  Catt\'e, Dibos, and Koepfler \cite{Catte:1995:MSM} related mean
curvature motion to the classic morphological filters whose structuring elements are one-dimensional sets oriented in
all directions (see \cite{Nagao:1979:EPS} and \cite{Soille:1996:RIE} regarding these filters.)

The importance of the function $H$ in the main expansion theorem raises the following question: Given an increasing continuous function $H$, are there structuring elements $\mathcal B$ such that $H(s)=\inf_{B\in\mathcal B}\sup_{(x,y)\in B}(x+sy^2)$? As we have seen is this chapter, the function $H(s)=s$ is attained by a median filter. Pasquignon \cite{Pasq1999} has studied this question extensively and shown that all of the functions of the form $H(s)=s^\alpha$ are possible using sets of simple structuring elements.

The presentation of the main results of this chapter is mainly original and was announced in the tutorials \cite{Guichard:1995:PDE} and \cite{Guichard:1996:PDE}. An early version of this work appeared in \cite{Guichard:1994:AAM}.


\begin{figure}[!ht]
\setkeys{Gin}{width=12cm}
\centerline{
\includegraphics{fig10.04.1.eps}
} \caption[Fixed point property of the digital median filter]{\label{f114} Fixed point property of the discrete median
filter, showing its grid-dependence. Left: original image. Right: result of  46 iterations of the median filter with a
radius of 2. The resulting image turns out to be a fixed point of this median filter. This is not in agreement with
Theorem \ref{theorem10.4}, which shows that median filters move images by their curvature : The image on the right
clearly has nonzero curvatures! Yet, the discrete median filter that we have applied here operating on a discrete image
is grid-dependent and blind to small curvatures.}
\end{figure}

\begin{figure}[!ht]
\setkeys{Gin}{width=12cm} \centerline{
\includegraphics{fig10.05.1.eps}
} \caption[Median filter and iterated median filter II]{\label{f115} Comparing an iterated median filter and a median
filter. Top-left: original image. Top-middle: 16 iterations of the median filter with a radius 2, Top-right: one
iteration of the same median filter with a radius 8. Below each image are the level-lines for grey levels equal to
multiples of 16. This shows that iterating a small size median filter provides more accuracy and less shape mixing than
applying a large size median filter. Compare this with the Koenderink--Van Doorn shape smoothing and the
Merriman--Bence--Osher iterated filter in Chapter \ref{chapfourways}, in particular Figures \ref{fig29}, \ref{fig210},
and \ref{fig212}.}
\end{figure}

\begin{figure}[!t]
\setkeys{Gin}{width=12cm} \centerline{
\includegraphics{fig10.06.1.eps}
} \caption[Consistency of the median  filter and of the
Catt\'{e}--Dibos--Koepfler scheme ]{\label{f116}Consistency of the
median filter and of the Catt\'{e}--Dibos--Koepfler numerical
scheme. Top row: the sea bird image and its level lines for all
levels equal to multiples of 12. Second row: a median filter on a
disk with radius 2 has been iterated twice. Third row: an inf-sup
and then a sup-inf filter based on segments have been applied. On
the right: the corresponding level lines of the results, which,
according to the theoretical results (Theorems \ref{theorem10.4}
and \ref{theorem10.5}), must have moved at a speed proportional to
their curvature. The results are very close. This yields a cross
validation of two very different numerical schemes that implement
curvature-motion based smoothing.}
\end{figure}


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