%gmChap10.tex. 

\graphicspath{{./figures/chapter10/}}

\chapter[Asymptotic Behavior of Contrast-Invariant Operators in ${\mathbb R^2}$]{Asymptotic Behavior of Contrast-Invariant Isotropic Operators, Dimension Two}

We are going to study the inf-sup function operators introduced in section 7.2 defined by
\begin{equation}
Tu(\fxx)=\inf_{B\in\mathcal B} \sup_{\fxy\in\fxx+ B}u(\fxy),
\end{equation}
where $\mathcal B$ is a given set of structuring elements. Theorem 7.3 states that these operators are contrast and translation invariant. Theorem 7.3 also states that function operators that are contrast and translation invariant on a suitable domain $\mathcal F$ can be represented (for almost all $\fxx\in\RR^N$) as inf-sup(or sup-inf) operators. Corollary 7.4 states that these representations hold for all $\fxx\in\RR^N$ if $T$ commutes with the threshold operator $\gamma_\lambda$ for all $\lambda\in\RR$. This means that our asymptotic analysis of contrast-invariant operators using their inf-sup representation is completely general (at least up to a set of measure zero). 

In this chapter and the next, we assume that the set of structuring elements $\mathcal B$ is bounded and isotropic. This means that there is an $M>0$ such that $B\subset D(0,M)$ for all $B\in\mathcal B$ and that $B\in\mathcal B$ implies that  $RB\in\mathcal B$ for all linear isometries $R$ of $\RR^2$. It may seem that these assumptions leave room for a large collection of operators, since they clearly leave room for a large collection of structuring elements. We will see, however, that the operators associated with these structuring elements fall into several large classes. 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. In other words, the process of defining the operators $T_h$ and letting $h$ tend to zero maps the class of bounded isotropic structuring elements into equivalence classes that are simply characterized. This result is 
analogous to Theorem 2.2 for linear filters, which mapped certain Laplacian-consistent kernels into classes based on the value of their second moments. 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 a class of contrast-invariant operators as the Laplacian $\Delta u$ does for linear operators.

\begin{exercise}The purpose of this exercise is to relate invariant properties of the set of structuring elements $\mathcal B$ to properties of $T$. Assume that $\mathcal B$ is invariant under a group $G$ of transformations of $\RR^2$ onto $\RR^2$. This means that, for all $g\in G$,  $B\in\mathcal B$ if and only if $gB\in\mathcal B$. Define the operator $I_g$ on functions $u:\RR^2\to\RR$ by $I_gu(\fxx)=u(g\fxx)$. Show that $TI_g=I_gT$. If $G$ is the group of isometries of $\RR^2$ that leave the origin fixed, then $T$ is by definition an \textit{isometric operator}. \finex
\end{exercise}

\section{Asymptotic behavior theorem in $\mathbb R^2$}

Let $T$ be an inf-sup operator generated by a set of structuring elements $\mathcal B$ that is bounded and isotropic, and define the function $H(s)$, $s\in\RR$, by
\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$.'' Since $T$ is monotone, $H$ is a nondecreasing function; it is also a Lipschitz function. To see this, 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}
We also note the following relations for $0<h\leq1$:
\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}
It is important to keep in mind that $T[x](0)$ is not a function of $x$; it is the result of applying $T$ to the ``test'' function $u(x,y)=x$ and evaluating it at the origin. Thus, $T[x](0)$ is a constant that depends only on $\mathcal B$.

\begin{theorem}Let $\mathcal B$ be a set of structuring elements that is invariant under the group of linear isometries of $\RR^2$ and assume that $\mathcal B$ is bounded by $M$. Define the operator $T$ by $Tu(\fxx)=\inf_{B\in\mathcal B} \sup_{\fxy\in\fxx+ B}u(\fxy)$, and define the scaled operators $T_h$, $0<h\leq1$, by $T_hu(\fxx)=\inf_{B\in\mathcal B} \sup_{\fxy\in\fxx+ hB}u(\fxy)$. Then, for any $C^2$ function $u:\RR^2\to\RR$,  
\[
T_hu(\fxx)-u(\fxx)=hT[x](0)|Du(\fxx)|+O(\fxx,h^2).
\]
Furthermore, $|O(\fxx,h^2)|\leq C_{\fxx}h^2$, where $C_{\fxx}$ depends only on $u$ and $\fxx$.
\end{theorem}
\begin{proof}
The invariance of $\mathcal B$ under the action of linear isometries implies by Exercise 10.1 that all of the $T_h$ are invariant under rotations. Now suppose that $p=|Du(\fxx)|>0$. Then by a suitable rotation, we may assume that $Du(\fxx)=(|Du(\fxx)|,0)$, and  the first-order 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)$. Define $C=\sup_{|\fxy|\leq M}|u(\fxx+\fxy)-u(\fxx)-px|/|\fxy|^2$ and deduce from \eqref{eq117} that 
\[
|u(\fxx+\fxy)-u(\fxx)-px|\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)$,
we see that
\[
T_hu(\fxx)+u(\fxx)\leq hpT[x](0)+CM^2h^2.
\]
The same argument applied to the second inequality of \eqref{eq117a} shows that 
\[
hpT[x](0)\leq T_hu(\fxx)-u(\fxx)+CM^2h^2,
\]
so $|T_hu(\fxx)-u(\fxx)-hpT[x](0)|\leq CM^2h^2$. Since $p=|Du(\fxx)|$, we see that 
\[
T_hu(\fxx)-u(\fxx)=hT[x](0)|Du(\fxx)|+O(\fxx,h^2),
\] 
which proves the result in case $p\not=0$. If $p=|Du(\fxx)|=0$, equation \eqref{eq117} remains true, as does the following argument, so the result is true for this case as well. Finally, to finish the proof, take $C_{\fxx}=CM^2$. 
\end{proof}

\subsection{Proof strategy and types of results}

The statement and proof of Theorem 10.1 are models for similar results and arguments presented in this and this following five chapters, including the next theorem. Since it is so typical, it is useful to review and comment on the steps of the proof and the results. The purpose is to demystify the more complex results and arguments that follow.

Invariably, the operators $T_h$ are inf-sup (or sup-inf) operators and are thus always translation invariant and commute with the addition of constants. (In abstract cases, we will assume these properties.) This means that it is always possible to assume, without loss of generality, that the point of interest is $\fxx=0$ and that $u(\fxx)=0$. (We chose not to do this in the proofs of Theorems 10.2 and 10.2, since to do so may have obscured the argument.)

The next most important invariant in isotropy. Without exception, the sets of structuring elements we consider will be isotropic, and so, by Exercise 10.1, the associated operators are isotropic. It is this invariant that allows us, without loss of generality, to rotate the coordinate system so $Du(\fxx)=(|Du(\fxx),0)$. This, in turn, allows us to expand $u$ at $\fxx$ (or at the origin after a translation) as
\[
u(\fxx+\fxy)=u(\fxx)+P(\fxx,\fxy)+R(\fxx,\fxy).
\]
$P$ is a polynomial (usually of degree two) whose linear term is $|Du(\fxx)|x$. The variable $\fxy=(x,y_1,\ldots,y_{N-1})$, and $R$ is an error term for which we have estimates in terms of the derivatives of $u$. In this chapter and the next, we assume that the structuring elements are bounded by a constant $M$. This allows us to make the following kind of estimate when $P$ is of order two:
\[
\sup_{\fxy\in B}u(\fxx+h\fxy)-u(\fxx)\leq \sup_{\fxy\in B}P(\fxx,h\fxy)+\sup_{|\fxy|\leq M}|R(\fxx,\fxy)|\leq\sup_{\fxy\in B}P(\fxx,h\fxy)+CM^3h^3,
\]
for all $\fxx$ is some set and all $\fxy\in D(0,M)$. This inequality and the one obtained by interchanging $u(\fxx+\fxy)-u(\fxx)$ and $P(\fxx,\fxy)$ imply a relation of the form
\begin{equation}\label{eq10x}
T_hu(\fxx)-u(\fxx)=T_h[P(\fxx,h\fxy)](0)+O(\fxx,|\fxy|^3).
\end{equation}
Once a formula like this is established, further analysis focuses on investigating  
$T_h[P(\fxx,h\fxy)](0)$ using more specific properties of $\mathcal B$. We will see this in the proof of Theorem 10.2. There we consider $\mathcal B$ for which $T[x](0)=0$. Theorem 10.1 is also a case in point. It tells us that the behavior of the inf-sup operators $T_h$ generated by bounded isotropic structuring elements depends, for small $h$, completely on the action of $T$ on the test function $u(x,y)=x$. If $T[x](0)\not=0$, then, informally, we see that 
\[
\frac{T_hu(\fxx)-u(\fxx)}{h}=hT[x]|Du(\fxx)|+O(h),
\]
so in the limit as $h\to0$, $T$ acts like a dilation if $T[x]>0$ and like an erosion if $T[x]<0$ (see Proposition 8.8). Thus, if $T[x](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.

Equations like \eqref{eq10x} relate the operators $T_h$ to a PDE. On the other hand, there are results like Theorem 10.2$(ii)$ that provide estimates on the size of $|T_hu(\fxx)-u(\fxx)|$, and these result are used to relate the viscosity solutions of the PDEs to functions generated by the $T_h$ called approximate solutions (Chapters 15 and 16). Other kinds of results are developed to support the analysis of $T_h[P(\fxx,h\fxy)](0)$ for special classes of structuring elements $\mathcal B$, including median filters and affine-invariant sets of structuring elements.

We have stated and demonstrated Theorem 10.1 for inf-sup operators. The result is also true for sup-inf operators, and this is the subject of the next exercise.

\begin{exercise}Assume that the set of structuring elements $\mathcal B$ is isometric and bounded, as in Theorem 10.1. Define $T$ by $Tu(\fxx)=\inf_{B\in\mathcal B} \sup_{\fxy\in\fxx+ B}u(\fxy)$. Prove that $T[-x](0)=T[x](0)$. Use this and the relation $T^-u=-T(-u)$ to show that the results of Theorem 10.1 hold for sup-inf operators. \finex
\end{exercise}

\begin{exercise}Assume that $T$ is defined as an inf-sup operator and that the structuring elements are bounded but not necessarily isotropic. Show that 
\[
T_hu(\fxx)=u(\fxx)+hT[Du(\fxx)\cdot\fxx](0) + O(h^2).\; \finex
\]
\end{exercise}

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

If $T[x](0)=0$, then Theorem 10.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 and leads to interesting results. 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 10.1, but at the macro level, they are similar.

\begin{theorem}Let $\mathcal B$ be a set of structuring elements that is isometric and bounded, and let $M$ denote the bound. Define the operator $T$ by $Tu(\fxx)=\inf_{B\in\mathcal B} \sup_{\fxy\in\fxx+ B}u(\fxy)$, and define the scaled operator $T_h$, $0<h\leq1$, by $T_hu(\fxx)=\inf_{B\in\mathcal B} \sup_{\fxy\in\fxx+ hB}u(\fxy)$. Also assume that $T[x](0)=0$. Then for any $C^3$ function $u:\RR^2\to\RR$ we have the following results$:$
\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 \frac{h^2M^2}{2}\|D^2u(\fxx)\|+C_Kh^3
\]
where the constant $C_K$ depends only on $u$ and $K$.
\end{enumerate}
\end{theorem}

\begin{proof}For the meanings of $p$, $a$, $b$, and $c$ see section 4.5. In particular, $p=|Du(\fxx)|$. We are not going to set $\fxx=0$ and $u(\fxx)=0$, but we will define the local coordinate system by taking $Du(\fxx)=(p,0)$. Using this notation, we expand $u$ for $\fxy=(x,y)$ in a neighborhood of $\fxx$:
\begin{equation}\label{eq119}
u(\fxx+\fxy)= u(\fxx)+px+ax^2+by^2+cxy+R(\fxx,\fxy).
\end{equation}

The remainder term $R$ is going to follow us throughout the proof (and indeed throughout the next six chapters), so it is useful to deal with it now. $R$ can be written as 
\[
R(\fxx,\fxy)=\Bigg(\int_0^1(1-t)^2 D^3u(\fxx+t\fxy)\,\rmd t\Bigg)\fxy^{(3)},
\] 
which gives the estimate
\[
|R(\fxx,\fxy)|\leq\Bigg(\sup_{t\in[0,1]}\sum_{(i_1,i_2,i_3)}\Bigg|\frac{\partial^3 u}{\partial x_{i_1}\partial x_{i_2}\partial x_{i_3}}(\fxx+t\fxy)\Bigg|\Bigg)|\fxy|^3. 
\]
We will write
\[
\|D^3u(\fxx)\|=\sum_{(i_1,i_2,i_3)}\Bigg|\frac{\partial^3 u}{\partial x_{i_1}\partial x_{i_2}\partial x_{i_3}}(\fxx)\Bigg|
\]
and $\|D^2u(\fxx)\|=\sum_{i,j}|u_{ij}(\fxx)|$. Since $u$ is assumed to be $C^3$, the two functions 
\[
\fxx\mapsto\|D^2u(\fxx)\|\quad\text{ and }\quad\fxx\mapsto\|D^3u(\fxx)\|
\]
are continuous and thus bounded on any compact set $K$. With this notation, we have
\[
|R(\fxx,h\fxy)|\leq\sup_{\fxx\in K, |\fxy|\leq M}\|D^3u(\fxx+h\fxy)\|h^3M^3. 
\]
If we define $K_M=\{\fxx\mid d(\fxx,K)\leq M\}$, then we can write this inequality as 
\[
|R(\fxx,h\fxy)|\leq\sup_{\fxz\in K_M}\|D^3u(\fxz)\|h^3M^3
\]
for all $\fxx\in K$ and $\fxy\in D(0,M)$, and we have a uniform bound on $K\times D(0,M)$. 

Now return to equation \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 our analysis of $R$, we deduce that
\begin{equation}
T_hu(\fxx)\leq u(\fxx)+hT[u_h(x,y)](0)+\sup_{\fxz\in K_M}\|D^3u(\fxz)\|h^3M^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)+\sup_{\fxz\in K_M}\|D^3u(\fxz)\|h^3M^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$. Furthermore, $|O(\fxx,h^3)|\leq C_Kh^3$, with $C_K=\sup_{\fxz\in K_M}\|D^3u(\fxz)\|M^3$, and $C_K$ depends only on $K$ and $u$. (Of course, it depends also on $\mathcal B$, but that is understood.) At this point, we have now reduced the proof to an analysis of $Tu_h(0)$.

We are now going to show that $a$ and $c$ have no role in the asymptotic behavior of $Tu_h(0)$. To make the proof as clear as possible, we break it into several steps.

\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
\[
p(\fxx)x-\frac{hM^2}{2}\|D^2u(\fxx)\|\leq u_h(x,y)\leq p(\fxx)x+\frac{hM^2}{2}\|D^2u(\fxx)\|
\]
to highlight the dependence on $\fxx$, even though $\fxx$ is fixed.
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}
We can take $C_K=\sup_{\fxz\in K_M}\|D^3u(\fxz)\|M^3$. Thus, \eqref{eq1112} holds uniformly for $\fxx\in K$ and for all $h$, $0<h\leq1$. This proves part $(ii)$.

\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=(1/2)\|D^2u(\fxx)\|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
\[
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|
\]
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 estimated for 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 approximation 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
\begin{align*}
|\varepsilon(x,y)|&\leq h^3|a|C'^2+h^2|c||C'|M\\
&=\frac{h^2}{|Du(\fxx)|^2}\Bigg[\frac{h}{2}|u_{xx}(\fxx)|\|D^2u(\fxx)\|^2+|u_{xy}(\fxx)||Du(\fxx)|\|D^2u(\fxx)\|M\Bigg].
\end{align*}
Since $u$ is $C^3$, all of the functions on the right-hand side of this relation are continuous on $K$; in particular, $|Du(\fxx)|$ is bounded away from zero 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)$ and the proof of the theorem. 
\end{proof}


We apply these results to median filters in the next section, but before doing this, we pause to check that the results of Theorem 10.2 hold for operators represented in their sup-inf form. This is the content of the next exercise.

\begin {exercise}Let $\mathcal B$ be a set of structuring elements that is bounded and invariant under linear isometries. Define $T^-u(\fxx)=\sup_{B\in\mathcal B}\inf_{\fxy\in\fxx+ B}u(\fxy)$, and define $H^-(s)=T^-[x+s y^2](0)$.
\begin{enumerate}[$(i)$]\setlength\itemsep{2pt}
\item Show that $H^-(s)=-H(-s)$.
\item Use (i) and the relation $T^-u=-T(-u)$ to show that the results of Theorem 10.2 are true for sup-inf operators. \finex
\end{enumerate}
\end{exercise} 

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

Recall that the median filter, $\fcnM_k$, defined in Chapter 9 can be written 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\mid B \text{ is measurable}, |B|_k=1/2\}$ (Proposition 9.4). The first example we examine is the case $k=\bmone_{D(0,1)}/\pi$, that is, $k$ is the uniform measure on the unit disk. We know by Proposition 9.7 that $\fcnM_ku=\fcnM_k^-u$ if $u$ is continuous, so by restricting the domain of $\fcnM_k$ to continuous functions $u:\RR^2\to\RR$ it can be represented by the inf-sup form
\begin{equation}
\fcnM_ku(\fxx)=\inf_{B\in\mathcal B}\sup_{\fxy\in\fxx+B}u(\fxy),
\end{equation}
where $\mathcal B=\{B\mid B \text{ is measurable}, |B|_k=1/2\}$. By using the results of Exercise 7.4, it is easy to show that the set of structuring elements $\mathcal B'=\{B'\mid B'= B\cap D(0,1), B\in\mathcal B \}$ is equivalent to $\mathcal B$, in the sense that they both generate 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}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 10.4, gives an infinitesimal interpretation of this filter. This result will be extended in the next chapter to a general weighted median filter in $\RR^N$. Theorem 10.4 can be deduced directly from Theorem 10.2 once we have the following lemma. This lemma is an example of the kind of detailed analysis of $T_h[P(\fxx,h\fxy)](0)$ that we spoke about in section 10.1.1, and characteristically, the proof is quite special, having no immediate generalization to $\RR^N$. 

\begin{lemma}
\[
\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 base $AB$ is $|m(s )-s |$, and an easy computation shows that the length of the hight $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}
\pagebreak

\begin{theorem}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 \frac{1}{2}\|D^2u(\fxx)\|h^2+C_Kh^3
\]
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 10.2. In particular, $H(0)=\fcnM_k[x+s y^2](0)=0$ by Lemma 10.3. Also by Lemma 10.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 10.2$(i)$. Relation $(ii)$ follows immediately from Theorem 10.2$(ii)$.
\end{proof}

Our second example is called the Catt\'e--Dibos scheme. It involves another application of Theorem 10.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}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 we know from Exercise 10.4 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 10.2 apply. By applying Theorem 10.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{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.}
\end{figure}

\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}[!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 10.4.}
\end{figure}

\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 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 10.4, which shows that median filters move images by their curvature: The image on the right clearly has nonzero curvatures!  However, 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=10cm}
\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 Bence--Merriman--Osher iterated filter in Chapter 2, in particular Figures 2.9, 2.10, and 2.12.}
\end{figure}

\begin{figure}[!t]
\setkeys{Gin}{width=10cm}
\centerline{
\includegraphics{fig10.06.1.eps}
}
\caption[Consistency of the median filter and of the Catt\'{e}--Dibos scheme ]{\label{f116}Consistency of the median filter and of the Catt\'{e}--Dibos. 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 10.4 and 10.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}
