%gmChap06.tex

\graphicspath{{./figures/}}

\chapter[Contrast-Invariant Monotone Operators]
{Contrast-Invariant Monotone  Operators\label{Chap6}}

A function operator $T$ is monotone if $u\geq v\Rightarrow Tu\geq
Tv$.  A set operator $\mathcal T$ is monotone if $X\subset Y$
implies $\mathcal TX\subset \mathcal TY$. We are mainly interested
in monotone function operators, since they are nonlinear
generalizations of linear smoothing using a nonnegative
convolution kernel.
 We have already
argued that  for image analysis to be robust, the operators must
also be contrast invariant.
 The overall theme here will
be to develop the equivalence between monotone contrast-invariant
function operators and monotone set operators.  This equivalence
is based on one of the fundamentals of mathematical morphology
described in Chapter \ref{Chap3}: A real-valued function is
completely described by its level sets.


This  allows one to process an image $u$ by processing separately
its level sets by some monotone set operator $\mathcal T$ and
defining the processed image by the {\it superposition principle}
$$Tu=\sup\{\lambda, \fxx\in  \mathcal T(\levelset_\lambda u)\}.$$
Such an operator is called in digital technology a {\it stack filter}, since it processes an image  as a stack of level
sets. Conversely, we shall associate with any  contrast invariant monotone function operator $T$ a monotone set
operator by setting
$$\mathcal T(\levelset_\lambda u)=\levelset_\lambda (Tu).$$
  Such a construction
is called {\it a level set extension of  $T$}.

Several questions arise, which will be all answered positively
once the functional framework is fixed: Are stack filters contrast
invariant? Conversely, is any monotone contrast invariant operator
a stack filter? Is any monotone set operator  the level set
extension of its stack filter?



   In Section \ref{section6.1} we shall make definitions precise and give
    some
remarkable conservative properties of contrast invariant monotone operators. Section \ref{section6.2}  is devoted to
stack filters and shows that they are monotone and contrast invariant. Section \ref{section6.3} defines the level set
extension and shows the converse statement: Any contrast invariant monotone operator is a stack filter. Section
\ref{section6.4} applies this construction to a remarkable denoising stack filter due to Vincent and Serra, the area
opening.

\section{Contrast-invariance\label{section6.1}}
\subsection{Set monotone operators}

We will be mostly dealing with function operators $T$ defined on $\mathcal F$
 and set operators $\mathcal T$ defined on
$\mathcal L$, but sometimes also defined on $\mathcal M$.
We denote by $\mathcal D(\mathcal T)$ the domain of $\mathcal
T$. Now, all set operators we shall consider
 in practice are
defined first on subsets of $\RR^N$.

\begin{definition}\label{defstandardextension}
Let $\mathcal T$ a monotone operator  defined on a set of subsets of $\RR^N$. We call {\rm standard extension of}
$\mathcal T$ to $S_N$ the operator, still denoted by $\mathcal T$,  defined  by
  $$\mathcal T(X)=\mathcal T (X\setminus\{\infty\})\cup (X\cap \{\infty\}).$$
\end{definition}
In other terms if $X$ doesn't contain $\infty$, $\mathcal T(X)$ is already defined and if $X$ contains $\infty$,
$\mathcal T(X)$ contains it too. Thus a standard extension satisfies $\infty\in \mathcal TX\Leftrightarrow \infty\in
X$.

\begin{remark}\label{standardextensiononclosedsets}Let us examine the case where $\mathcal T$ is initially defined on $\mathcal C$, the set of all closed subsets of
$\RR^N$. There are only two kinds of sets in $\mathcal L$, namely
\begin{itemize}
\item compact sets of $\RR^N$ \item sets of the form $X=C\cup
\{\infty\}$, where $C$ is a closed set of $\RR^N$.
\end{itemize}
Thus the standard  extension of $\mathcal T$ extends $\mathcal T$ to $\mathcal L$,  the set of all  closed (and
therefore compact) subsets of $S_N$.
\end{remark}

 All of the usual monotone set
operators used in shape analysis satisfy a small list of standard
properties which it is best to fix now. Their meaning will come
obvious in examples.

\begin{definition}\label{defstandardmonotone} We say that a set operator $\mathcal T$ defined on its domain
$D(\mathcal T)$ is {\rm standard monotone } if
\begin{itemize}
\item $X\subset Y \,\Longrightarrow\, {\mathcal T} X\subset
{\mathcal T} Y$;

\item $\infty\in \mathcal TX\Longleftrightarrow \infty\in X$;

\item $\mathcal T(\emptyset)=\emptyset,$ $\mathcal T(\SN)=\SN$;

\item $\mathcal T(X)$ is bounded in $\RR^N$ if $X$ is;

\item $\mathcal T(X)^c$ is bounded in $\RR^N$ if $X^c$ is.
\end{itemize}
\end{definition}

\begin{definition} \index{dual set operator} Let $\mathcal T$ be a monotone set operator on its domain $\mathcal
D(\mathcal T)$. We call {\rm dual domain} the set
$$\mathcal D(\tilde{\mathcal T}):=\{X\subset S_N\mid X^c\in \mathcal
D(\mathcal T)\}.$$ We call {\rm dual} of $\mathcal T$ the operator $X\to \tilde{\mathcal T}X=(\mathcal T(X^c))^c$,
defined on $\mathcal D(\tilde {\mathcal T}).$
\end{definition}

\begin{proposition}\label{dualstandardmonotone} $\mathcal T$ is a standard monotone operator if and only if $\tilde{\mathcal T}$ is.
\end{proposition}
\begin{exercise} Prove it!
\finex
\end{exercise}
\subsection{Monotone function operators}

Function operators are usually defined on $\mathcal F$, the set of continuous functions having some limit $u(\infty)$
at infinity. We shall always assume that this limit is preserved by $T$, that is, $Tu(\infty)=u(\infty)$. Think that
images are usually compactly  supported. Thus $u(\infty)$ is the ``color of the frame" for a photograph. There is no
use in changing this color.


\begin{definition}
We say that a function operator $T:\mathcal F\to \mathcal F$ is
    standard monotone if for all $u,v\in\mathcal F$,
\begin{equation}
u\geq v\, \Longrightarrow\, Tu\geq Tv;\quad Tu(\infty)=u(\infty).
\end{equation}
\end{definition}

\begin{exercise} Is the operator $T$ defined by $(Tu)(\fxx)= u(\fxx)+1$ standard monotone?
\finex \end{exercise}
 Recall from Chapter \ref{Chap3} that any nondecreasing continuous  surjection $g:\RR\to \RR$ is
called a contrast change.

\begin{definition}
A function operator $T$: $\mathcal F\to \mathcal F$ is said to be
contrast invariant if for every $u\in \mathcal F$ and every
contrast change $g$,
\begin{equation}
g(Tu)=Tg(u).
\end{equation}
\end{definition}

Checking contrast invariance with increasing contrast changes will make our life simpler.
\begin{lemma}\label{reductionastrictecroissance}
A monotone operator   is contrast invariant if and only  if it
commutes with strictly increasing  contrast changes.
\end{lemma}
\begin{proof}
Let  $g$ be a contrast change. We can find strictly increasing
continuous functions $g_n$ and $h_n: \RR\to\RR$ such that
$g_n(s)\to g(s)$, $h_n(s)\to g(s)$ for all $s$ and $g_n\leq g\leq
h_n$ (see Exercise \ref{exercise8.4}.) Thus, by using the
commutation of $T$ with increasing contrast changes, we have
$$T(g(u))\geq T(g_n(u))=g_n(Tu)\to g(Tu)\; \hbox {  and  }$$
$$T(g(u))\leq T(h_n(u))=h_n(Tu)\to g(Tu), $$
which yields  $T(g(u))=g(Tu).$
\end{proof}
Let us give some notable properties entailed by the monotonicity and the contrast invariance.
\begin{lemma} Let $T$ be standard monotone contrast  invariant operator. Then for every constant function $u\equiv c$
one has $Tu\equiv c$.

\end{lemma}\label{Tcegalc}
\begin{proof} Let $g$ be a contrast change such that $g(s)=s$ for $\inf Tu\leq s\leq \sup Tu$.  Since
$Tu(\infty)=u(\infty)=c$, this implies that $\inf Tu\leq c\leq \sup Tu$ and therefore $g(c)=c$, which means $g(u)=u$..
By the contrast invariance we therefore obtain $Tu=Tg(u)=g(Tu)\equiv c.$
\end{proof}


We have indicated several times the importance  of image operators being contrast invariant. In practice, image
operators are also translation invariant. For $\fxx\in\RR^N$ we are going to use the notation $\tau_{\fxx}$ to denote
the translation operator for both sets and functions: For $X\in \mathcal M$, $\tau_{\fxx}X=\{\fxx+\fxy\mid \fxy\in
X\}$, and for $u\in\mathcal F$, $\tau_{\fxx}u$ is defined by $\tau_{\fxx}u(\fxy)=u(\fxy-\fxx)$. Since elements of
$\mathcal M$ can contain $\infty$, we specify that $\infty\pm\fxx=\infty$ when $\fxx\in \RR^N$. This implies that
$\tau_{\fxx} u(\infty)=u(\infty).$

\begin{definition}\label{definition6.4}
A set operator $\mathcal T$ is said to be translation  invariant if its domain is translation invariant and if for all
$X\in\mathcal D(\mathcal T)$ and $\fxx\in\RR^N$,
\[
\tau_{\fxx}{\mathcal T}X={\mathcal T}\tau_{\fxx}X.
\]
A function operator $T$ is said to be translation invariant  if
for all $u\in\mathcal F$ and $\fxx\in\RR^N$,
\[
\tau_{\fxx}Tu=T\tau_{\fxx}u.
\]
We say that a function operator $T$ commutes with the addition of constants if $u\in\mathcal F$ and $c\in\RR$  imply
$T(u+c)=Tu+c$.
\end{definition}
Contrast-invariant operators clearly commute with the addition of constants: Consider the contrast change defined by
$g(s)=s+c$.

% CAREFUL : NADA !
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \nada{ Translation invariance entails a reinforced monotonicity
property for standard monotone operators.

\begin{proposition} Let $\mathcal T$  be a  translation
invariant standard monotone operator. Then for all $X, Y\in
\mathcal L$,
$$X\subset Y^\circ \Longrightarrow \mathcal T(X)\subset \mathcal
T(Y)^\circ.$$
\end{proposition}

\begin{proof}
Assume that $X\subset Y^\circ$. \newline{\bf Case 1:
    $X$ is bounded, and therefore compact in $\RR^N$}.  Then
$X\subset Y^\circ\setminus\{\infty\}$ which is an open set of
$\RR^N.$ We deduce from the compactness of $X$ that there is a
ball $B(0,r)$ such that $X+B(0,r)\subset Y$. This means
$X+\fxz\subset Y$ for all $\fxz\in B(0,r)$ and by translation
invariance, $\mathcal TX +\fxz \subset \mathcal TY$. We conclude
that $\mathcal TX +B(0,r)\subset \mathcal TY$ and therefore
$\mathcal TX\subset \mathcal T(Y)^\circ.$

\medskip \noindent{\bf Case 2: $X$ is not bounded}.  Then $X$
contains $\infty$ and therefore $Y^\circ$ contains $\infty$.  This
implies that $B(0,R)^c\subset Y$ for some $R>0$ and, $\mathcal T$
being standard, $B(0,R')^c\subset \mathcal TY$ for some $R'>0$. In
other terms, $\mathcal TY$ contains a neighborhood of $\infty$ and
therefore $\infty  \in \mathcal T(Y)^\circ$.  In  addition,
$X\subset Y^\circ$ and $B(0,R)^c\subset Y$ imply that $ X
+B(0,r)\subset Y$ for some $r>0$. Indeed, $\fxx+B(0,1)\subset Y$
is trivially true for $|\fxx|> R+2 $ and
 $(X\cap \overline{B(0,R+1)})+B(0,r)\subset Y^\circ$ for some $r>0$ by the compactness
 of $X\cap \overline{B(0,R+1)}$. Finally, $\infty+B(0,r)=\{\infty\}\subset Y$.
  By the same argument as in Case 1, we
deduce that $\mathcal T(X)+B(0,r)\subset Y$, which means
$(\mathcal T X)\cap\RR^N\subset  Y^\circ,$ and we already know
that $\infty\in Y$.   Thus $\mathcal  TX\subset Y^\circ.$
\end{proof}
} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%END OF NADA


\begin{lemma}\label{lemma6.5}  Let $T$ be a translation-invariant
 monotone function
operator
 on $\mathcal F$ that commutes with the addition of
constants. If $u\in\mathcal F$ is $K$-Lipschitz on $\RR^N$, namely $|u(\fxx)-u(\fxy)|\leq K|\fxx-\fxy|$ for all
$\fxx,\;\fxy$ in $\RR^N$, then  so is $Tu$.
\end{lemma}
\begin{proof}  For any $\fxx\in \RR^N$, $\fxy\in\RR^N$, and $\fxz\in \SN$, we
 have
\begin{equation}\label{eq64}
u(\fxy+\fxz )-K|\fxx -\fxy|\leq u(\fxx+\fxz) \leq u(\fxy+\fxz)+K|\fxx-\fxy|.
\end{equation}
 These inequalities work for $\fxz=\infty$ because $u(\fxy+\infty)=u(\fxx+\infty)=u(\infty)$.
Thus we can write them as inequalities between functions on $S_N$:
\begin{equation}\label{eq64bis}
\tau_{-\fxy}u-K|\fxx -\fxy|\leq \tau_{-\fxx}u \leq \tau_{-\fxy}u+K|\fxx-\fxy|.
\end{equation}
   Since $T$ is monotone, we can apply $T$ to the
functions in \eqref{eq64bis} and preserve the inequalities, which yields
$$T(\tau_{-\fxy}u-K|\fxx -\fxy|)\leq T(\tau_{-\fxx}u )\leq T(\tau_{-\fxy}u+K|\fxx-\fxy|).$$
Now use the fact that $T$ commutes with the addition of constants the translation invariance of $T$  to obtain
$$\tau_{-\fxy}(Tu)-K|\fxx -\fxy|\leq \tau_{-\fxx}(Tu))\leq T(\tau_{-\fxy}u)+K|\fxx-\fxy|).$$
Taking the values of these functions at 0 yields
\[
Tu(\fxy)-K|\fxx -\fxy|\leq Tu(\fxx) \leq Tu(\fxy)+K|\fxx-\fxy|,
\]
which is the announced result.
\end{proof}


 We say that an operator is monotone on a set of functions if $u\geq v\Rightarrow Tu\geq Tv$. Clearly
all above proofs do not depend upon the fact that the operator is standard, but just upon its translation invariance
and monotonicity. Thus, by considering  the proof of Lemma \ref{lemma6.5} and the
  definition of uniform continuity (Definition \ref{defuniformcontinuity}),
  one  obtains  the
  following
generalizations.

\begin{corollary}\label{preservationuniformecontinuite}
 Assume that $T$
is a translation-invariant monotone operator on  a set of uniformly continuous functions, that commutes with the
addition of constants. Then $Tu$ is uniformly continuous on $\RR^N$ with the same modulus of continuity. In particular
if $u$ is $L$-Lipschitz on $\RR^N$,  then so is $Tu$.
\end{corollary}
\begin{exercise} Prove corollary \ref{preservationuniformecontinuite}.

\finex
\end{exercise}

\section{Stack filters\label{section6.2}}

\begin{definition}
We say that a function operator $T$ is  obtained from a monotone set operator $\mathcal T$ as a {\rm stack filter} if
\begin{equation}\label{eq66}
Tu(\fxx)=\sup\{\lambda\mid \fxx\in{\mathcal T}(\levelset_\lambda u)\}
\end{equation}
for   every $\fxx\in\SN$.
\end{definition}
The relation \eqref{eq66} has practical implications. It means
that $Tu$ can be computed by applying $\mathcal T$ separately to
each characteristic function of the level sets $\levelset_\lambda
u$. This leads to the following \textit{stack filter} algorithm.
\[
u
\begin{array}{ccccc}
& \levelset_\lambda u & \rightarrow & \mathcal T (\levelset_\lambda u) & \\[-.5ex]
\nearrow & & & & \searrow \\[-.5ex]
&\vdots & & & \\
\searrow & & & & \nearrow \\[-.5ex]
& \levelset_\mu u & \rightarrow & \mathcal T (\levelset_\mu u) & \\[-.5ex]
\end{array}
Tu(\fxx) = \sup\{\lambda\mid \fxx \in \mathcal T(\levelset_\lambda u)\}.
\]

The image $u$ is decomposed into the stack of level sets. Each level set is processed independently by the monotone
operator $\mathcal T$. This  yields a new stack of sets $\mathcal T(\levelset_\lambda u)$ and Formula (\ref{eq66})
always defines a function $Tu$. Now, this construction will be perfect only if
\begin{equation}\label{commutationwiththresholds}
\levelset_\lambda(Tu)=\mathcal T(\levelset_\lambda u).
\end{equation}
\begin{definition} When (\ref{commutationwiththresholds}) holds,
we say that  $T$  ``commutes with thresholds", or that $T$ and $\mathcal T$ satisfy the ``commutation with threshold"
property.
\end{definition}
Of course, this commutation can  hold  only if $\mathcal T$ sends
$\mathcal L$ into itself.  A further condition which turns out to
be  necessary is introduced in the next definition.
%%%%%%%%%%%%%%%%VIENT DE LA VERSION OLD%%%%%%%%%%%%%%%%%
 \begin{definition}\label{definitionuppersemicontinuousoperator}
We say that a monotone set operator $\mathcal T:\mathcal L\to\mathcal L$ is {\rm upper semicontinuous} if for every
sequence of compact sets $X_n \in \mathcal D(\mathcal T)=\mathcal L$ such that $X_{n+1}\subset X_n,$ we have
\begin{equation}
\label{vii.2} \mathcal T(\bigcap_n X_n) = \bigcap_n \mathcal
T(X_n).
\end{equation}
\end{definition}
\begin{exercise} \label{equivalencesemicontinuitydiscreteandcontinous}
Show that a monotone operator $\mathcal T: \mathcal L \to \mathcal L$ is upper semicontinuous if and only if it
satisfies, for every family $(X_\lambda)_{\lambda\in \RR}\subset \mathcal L$ such that $X_\lambda\subset X_\mu$ for
$\lambda>\mu$, the relation $\mathcal T(\bigcap_\lambda X_\lambda) = \bigcap_\lambda \mathcal T(X_\lambda).$ \finex
\end{exercise}

\begin{exercise}\label{reductionofsemicontinuity} Show that
 a monotone operator on $\cal L$ is
upper semicontinuous if and only if it satisfies \eqref{vii.2} for every sequence of compact sets  $X_n$ such  that
$X_{n+1}\subset X_n^\circ.$\newline Hint: Since $\SN$ is the unit sphere in $\RR^{N+1}$, one can endow it with the
euclidian distance $d$ in $\RR^{N+1}$.
 Given a nondecreasing sequence $Y_n$ in $\mathcal L$,
 set $X_n=  \{\fxx, d(\fxx, Y_n)\leq \frac 1n\}.$ Then apply
\eqref{vii.2} to $X_n$ and check that $\bigcap_n X_n=\bigcap_nY_n$. \finex
\end{exercise}
\begin{exercise} \label{equivalencecontinudiscret}
Show that a monotone operator $\mathcal T: \mathcal L \to \mathcal L$ is upper semicontinuous if and only if it
satisfies, for every family $(X_\lambda)_{\lambda\in \RR}\subset \mathcal L$ such that $X_\lambda\subset X_\mu^\circ$
for $\lambda>\mu$, the relation $\mathcal T(\bigcap_\lambda X_\lambda) = \bigcap_\lambda \mathcal T(X_\lambda).$ \finex
\end{exercise}


\begin{theorem} \label{3.5bis}
Let $\mathcal T $: $\mathcal L \to \mathcal M$ be a translation
invariant standard monotone  set operator. Then the associated
stack filter $T$ is translation invariant, contrast invariant and
standard monotone from
  $\mathcal F$ into itself.
 If,  in addition, $\mathcal T$ is upper semicontinuous, then $T$
 commutes with thresholds.
\end{theorem}

\begin{proof}[Proof that $T$ is monotone]

\medskip \noindent One has
$$u\leq v \Leftrightarrow (\forall \lambda, \;\levelset_\lambda
u\subset \levelset_\lambda v).$$ Since $\mathcal T $ is monotone,
we deduce that $$\forall \lambda, \; \mathcal T (\levelset_\lambda
u) \subset \mathcal T (\levelset_\lambda v) $$ which by
\eqref{eq66} implies $Tu\leq Tv.$

\medskip \noindent{\bf Proof that $T$ is contrast invariant.}
\newline
 By Lemma
\ref{reductionastrictecroissance} we can take $g$  strictly increasing and therefore a bijection from $\RR$ to $\RR$.
We notice that :
\newline For $\lambda>g(\sup  u),$
$\levelset_\lambda g(u)=\emptyset$ and therefore $\mathcal
T(\levelset_\lambda g(u))=\emptyset.$
\newline
For $\lambda < g(\inf u)$,  $\levelset_\lambda g(u)=\SN$ and
therefore $\mathcal T(\levelset_\lambda g(u))=\SN.$
\newline Thus using (\ref{eq66}) we can
restrict
  the range of $\lambda$ in the definition
of $T(g(u))(\fxx)$ :
$$T(g(u))(\fxx)=\sup \{\lambda, \; g(\inf u)\leq \lambda\leq g(\sup u), \;
\fxx\in\mathcal T(\levelset_\lambda g(u))\}$$
$$=\sup\{g(\mu),\;  \fxx\in \mathcal T(\levelset_{g(\mu)}g(u))\}$$
$$=\sup\{g(\mu),\; \fxx\in \mathcal T(\levelset_\mu u)\}= g(Tu(\fxx)).$$


\medskip \noindent{\bf Proof that $Tu$ belongs to $\mathcal F$.}
  \newline $T$ is
by construction translation invariant. By Corollary \ref{preservationuniformecontinuite}, $Tu$ is uniformly continuous
on $\RR^N$.  Let us prove that $Tu(\fxx)\to u(\infty)$ as $\fxx\to \infty$. We notice that for $\lambda>u(\infty)$,
$\levelset_\lambda  u$ is bounded. Since $\mathcal T$ is standard monotone $\mathcal T(\levelset_\lambda u)$ is bounded
too. Now, by \eqref{eq66}, $Tu(\fxx)\leq \lambda$ if $\fxx\in \mathcal T(\levelset_\lambda u)^c$. This last condition
is satisfied if $\fxx$ is large enough and we deduce that $\lim\sup_{\fxx\to \infty}Tu(\fxx)\leq u(\infty)$. In the
same way notice that $(\levelset_\lambda u)^c$ is bounded if $\lambda <u(\infty)$. So by the same argument, we also get
$\lim\inf_{\fxx\to \infty}Tu(\fxx)\geq u(\infty).$ $\mathcal T$ being standard, it is easily checked using \eqref{eq66}
that $Tu(\infty)=u(\infty).$ Thus, $Tu$ is continuous on $\RR^N$ and at $\infty$ and therefore on $\SN$.

\medskip \noindent{\bf Proof that $T$ commutes
with thresholds, when
$\mathcal T$ is upper semicontinuous.}
\newline
Let us show that the sets $Y_\lambda=\mathcal T(\levelset_\lambda u)$ satisfy the properties $(i)$ and $(ii)$ in
Proposition \ref{prop32}. By the monotonicity of $\mathcal T$, $Y_\lambda\subset Y_\mu$ for $\lambda>\mu$. Since
$\mathcal T(\emptyset)=\emptyset$, we have
$$Y_\lambda=\mathcal T(\levelset_\lambda  u)=\mathcal
T(\emptyset) =\emptyset$$ for $\lambda>\max u$ and, in the same way $Y_\lambda=\SN$ for $\lambda<\min u$. So $Tu$ has
the same bounds as $u$.   This proves Property $(i)$. As for Property $(ii)$, we have for  every $\lambda$, using the
upper semicontinuity and exercise \ref{equivalencesemicontinuitydiscreteandcontinous},
$$Y_\lambda=\mathcal T(\levelset_\lambda u)=\mathcal
T(\bigcap_{\mu<\lambda}\levelset_\mu
u)=\bigcap_{\mu<\lambda}\mathcal T(\levelset_\mu
u)=\bigcap_{\mu<\lambda}Y_\mu.$$
 So by applying the converse
statement of Proposition  \ref{prop32}, we deduce  that
$$\levelset_\lambda (Tu)=\mathcal T(\levelset_\lambda u).$$

\end{proof}

\begin{exercise}
Check that $Tu(\infty)=u(\infty)$, as claimed in the former proof. \finex
\end{exercise}

 The upper semicontinuity of $\mathcal T$ is necessary to ensure the commutation with thresholds. See Exercise
\ref{contrexemplesemicontinuity}.  The assumption that $\mathcal T$ sends bounded sets of $\RR^N$ on bounded sets of
$\RR^N$ and complementary sets of bounded sets onto complementary sets of bounded sets also is necessary to ensure that
$Tu$ is continuous at $\infty$: see Exercise \ref{boundedtobounded}.


\section{The level set extension\label{section6.3} }

Our aim here  is just the converse as in the former section. We wish to associate a standard monotone set operator
$\mathcal T$ from $ \mathcal L$ to $\mathcal L$ with any contrast invariant standard monotone function operator $T$, in
such a way that the whole machinery works, namely both operators satisfy the commutation with threshold property
$\mathcal T(\levelset_\lambda u)=\levelset_\lambda (Tu)$ and $T$ is the stack filter of $\mathcal T$.

\begin{lemma} \label{lemma7.7}Let  $u\leq 0$ and $v\leq 0\in \mathcal F$  and
 assume that $\levelset_0u=\levelset_0v\,(\ne\emptyset)$. Then there is
  a  contrast change $h$ such that $h(0)=0$ and $u\geq h(v)$.
\end{lemma}
\begin{proof}
Define $$\tilde{h}(r)= \left\{
  \begin{array}{ll}
    \min\{u(\fxx)\mid \fxx\in\levelset_r v\} & \hbox{ if } \min v\leq r\leq 0; \\
    r & \hbox{ if } r>0; \\
    \min u-\min v+r & \hbox{ if } r\leq \min v.
  \end{array}
\right.$$
 Notice that $\tilde{h}(0)=0$ and that $\tilde{h}$ is nondecreasing. The following relation holds for all
$\fxx\in\RR^N$ by the definition of $\tilde{h}$ and because $u(\fxx)$ belongs to the set $\{u(\fxy)\mid v(\fxy)\geq
v(\fxx)\}$:
\[
u(\fxx)\geq\min\{u(\fxy)\mid v(\fxy)\geq
v(\fxx)\}=\tilde{h}(v(\fxx)).
\]
We now use the compactness  in  $S_N$ of the level sets of $v$ to show that $\tilde{h}$ is continuous at zero. Let
$(r_k)_{k\in\NN}$ be an arbitrary increasing sequence tending to zero. Choose $\fxx_k\in\levelset_{r_k}v$ such that
$\tilde{h}(r_k)=u(\fxx{_k})$. This is possible because $u$ is continuous and the $\levelset_{r_k}v$ are compact and
nonempty. Since $\tilde{h}$ is nondecreasing, $\tilde{h}(r_k)\to \tilde{h}^-(0)$.

Let $\fxx$ be any accumulation point of the set $\{\fxx_{k}\}_{k\in\NN}$. Since the $\levelset_{r_k}v$ are compact, all
the accumulation points of the set $\{x_k\}_{k\in\NN}$ are contained in $\levelset_0
v=\bigcap_{k\in\NN}\levelset_{r_k}v$. This means that $u(\fxx)=0$. But $\lim u(\fxx_k)=u(\fxx)$ by the continuity of
$u$, and we conclude that $\tilde{h}^-(0)=0$. At this point $\tilde{h}$ satisfies the announced requirements for $h$,
except that it is not always continuous for all $r<0$. This is easily fixed by choosing a continuous nondecreasing
function $h$ such that $\tilde h\geq h$ and $h(0)=0$. One way to do this is to take $h(r)=(1/|r|)\int_{2r}^r\tilde
h(s)\,\rmd s$ for $r<0$. Then $u(\fxx)\geq\tilde h(v(\fxx))\geq h(v(\fxx))$ as announced.
\end{proof}

\begin{exercise}Prove that $h(r)=(1/|r|)\int_{2r}^r\tilde h(s)\,\rmd s$ is
 indeed nondecreasing and continuous for $r\leq0$ and that $\tilde h\geq h$. Find examples
 of functions $u$ and $v$ defined on $S_1$ for which $\tilde h$ is not
 continuous. \finex
\end{exercise}

\begin{definition}[and proposition (Evans-Spruck)]\label{definitionEvansSpruck}
  \footnote{What we are doing
   here is related to the scheme originally introduced by Osher
   and Sethian as a numerical method for front propagation
   \cite{Osher:1988:FPCb}. We briefly described their work in the
   Introduction (see page \pageref{OS}).}
   Given a contrast
   invariant  monotone operator $T$ on $\mathcal F$, we call level
   set extension of $T$ the set operator defined in the  following
   way : for any $X\in\mathcal L$, take $u\leq 0$ such that
   $\levelset_0 u=X$ and set $$\mathcal T(X)=\levelset_0T(u).$$
   Then $\mathcal T(X)$ does not depend
   upon the particular  choice of $u$.
\end{definition}
\begin{proof}
The proof follows directly from Lemma \ref{lemma7.7}: Take $u$ and $v\in \mathcal F$ such that $u\leq 0$, $v\leq 0$,
and $\levelset_0u=\levelset_0v$. Let $h$ be a  contrast
 change such that $h(0)=0$ and $u\geq h(v)$. Since $T$ is monotone and contrast
 invariant one has by Lemma \ref{Tcegalc} $Tu\leq0$, and $Tu\geq Th(v)=h(Tv)$. Using the fact that $h(0)=0$,
  we obtain that $Tv(\fxx)=0$ implies that $Tu(\fxx)=0$. By interchanging the roles
   of $u$ and $v$,  $Tu(\fxx)=0$ implies that $Tv(\fxx)=0$. We conclude
    that $\levelset_0 Tu=\levelset_0 Tv$.
\end{proof}


\begin{exercise} Definition \ref{definitionEvansSpruck} would'nt
be complete if we did not prove that for any $X\in \cal L$ we can find $u\leq 0$ in $\mathcal F$ such that $\levelset_0
u= X$. Hint: Since $\SN$ is the unit sphere in $\RR^{N+1}$, one can endow it with the euclidian distance $d$ in
$\RR^{N+1}$. Use the distance function $d(\fxx, X)$ to define $u$. This distance function is continuous: see Exercise
\ref{continuitydistancefunction}. \finex
\end{exercise}

\begin{theorem}[Evans--Spruck] \label{evansspruckextension}Let
$T$ be a contrast-invariant monotone operator on    $\mathcal F$
and  $\mathcal T$ its level set extension on $\mathcal L$. Then
$\mathcal T$ is monotone,
    $T$ and $\mathcal T$
   satisfy the commutation with thresholds
$ \mathcal T \levelset_{\lambda}u=\levelset_{\lambda}Tu $ for all
$\lambda\in\RR$,  $T$ is the stack filter associated  with
$\mathcal T$ and $\mathcal T$ is upper semicontinuous on $\mathcal
L$. In addition, if $T$ is standard, then so is $\mathcal T$.
\end{theorem}
\begin{proof}
 {\bf Commutation with thresholds:} Given   $u$ and
$\lambda$, let $g$ be a continuous contrast change such that
$g(s)= \min (s, \lambda)-\lambda$ on the range of $u$, which is a
compact interval of $\RR$. We then have
$\levelset_{0}g(u)=\levelset_{\lambda}u$. Using this relation, the
level set extension and the contrast invariance of $T$,
$$\mathcal T(\levelset_\lambda u)=\mathcal T(\levelset_0g(u))=
\levelset_0(T(g(u)))=\levelset_0(g(Tu))=\levelset_\lambda(Tu).$$

\medskip \noindent{\bf Proof of the stack filter property:}
This is  an immediate consequence of the superposition principle
and the commutation with thresholds :
$$Tu(\fxx)=\sup\{\lambda\mid  \fxx\in \levelset_\lambda Tu\}=
\sup\{\lambda\mid  \fxx\in \mathcal T(\levelset_\lambda u)\}.$$

\medskip\noindent{\bf  Proof that $\mathcal T$ is upper
semicontinuous on $\mathcal L$:} By the result of Exercise
\ref{reductionofsemicontinuity}, it is  enough to consider a
sequence $(X_n)_{n\geq 1}$  in $\mathcal L$ such that
$X_{n+1}\subset X_n^\circ$. By Lemma \ref{Urysohn} below there is
a function $u\in \mathcal F$ such that $\levelset_{1-\frac
1n}u=X_n$ and $\levelset_1u=\bigcap_nX_n$. Finally, using twice
the just proven commutation of thresholds,
$$\mathcal
T(\bigcap_nX_n)= \mathcal
T(\levelset_1u)=\levelset_1(Tu)=\bigcap_n\levelset_{1-\frac 1n}Tu
=\bigcap_n\mathcal T(\levelset_{1-\frac 1n}u)=\bigcap_n\mathcal
T(X_n).$$

\medskip \noindent {\bf Proof that $\mathcal T$ is standard if $T$
is:}  Recall that $T$ is standard if $Tu(\infty)=u(\infty)$. By
using the commutation with thresholds, all of the  standard
properties for $\mathcal T$ are straightforward. For instance,
taking some $u\in \mathcal F$,
$$\mathcal T(\emptyset)=\mathcal T(\levelset_{\max
u+1}u)=\levelset_{\max u+1} Tu=\emptyset.$$ Indeed, by the monotonicity,  the  contrast invariance, and Lemma
\ref{Tcegalc}, $u\leq C\Rightarrow Tu\leq C$.\newline  In the same way, let $X\in \mathcal L$ and $u$ a function such
that $\levelset_{0}u=X$. If $X$ is bounded, then $u(\infty)<0$, so that $Tu(\infty)=u(\infty)<0$. Thus $\mathcal
T(X)=\levelset_0 Tu$ is bounded.  If $X^c=\{\fxx\mid u(\fxx)<0\}$ is bounded, then $Tu(\infty)=u(\infty)\geq 0$.  Thus
$\mathcal T(X)^c=(\levelset_0Tu)^c$ is bounded.  Finally by  the commutation with thresholds,
  $$\infty\in X\Leftrightarrow u(\infty)\geq 0\Leftrightarrow Tu(\infty)\geq 0
  \Leftrightarrow \infty\in \levelset_0(Tu)=\mathcal T(X).$$
\end{proof}

\begin{exercise}
Prove that the level set extension $\mathcal T$ is  monotone. The argument is not given in the above proof. \finex
\end{exercise}
\begin{lemma}\label{Urysohn} Let $(X_n)_{n\geq 1}$ be a
 sequence in $\mathcal L$ such
that $X_{n+1}\subset X_n^\circ$. There is a function  $u\in
\mathcal F$ such that $\levelset_{1-\frac 1n}u=X_n$ for $n\geq 1$
and $\levelset_1u=\bigcap_{n\geq 1}X_n$.
\end{lemma}

\begin{proof} Let us use the euclidian distance $d$
of $\RR^{N+1}$ restricted to $\SN$  considered as a subset of
$\RR^{N+1}$. Set
  $u(\fxx)=1$ if $\fxx\in \bigcap_nX_n$,
$$u(\fxx)=(1-\frac
1n)\frac{d(\fxx,X_{n+1})}{d(\fxx,X_n^c)+d(\fxx,X_{n+1})}+(1-\frac
1{n+1})\frac{d(\fxx,X_{n}^c)}{d(\fxx,X_n^c)+d(\fxx,X_{n+1})}$$ for $\fxx\in X_{n}\setminus X_{n+1}$ and $n\geq 1$,
$u(\fxx)=-\sup(-1,-d(\fxx,X_1))$ if $\fxx\notin X_1$. It is easily checked that $u$ belongs in $\mathcal F$ and
satisfies the announced properties.
\end{proof}

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


\section{A first application: the extrema killer\label{section6.4}}

This section is devoted to the study of  operators that remove
``peaks,'' or extreme values, from an image. Such peaks are often
created by impulse noise, that is, local destruction of pixel
values and their replacement by a random value. Old movies present
this kind of noise and it also occurs by transmission failure in
satellite imaging. The operators we study are called \textit{area
opening}, or \textit{extrema killer} operators, and they have been
shown to be very effective at removing this kind of noise. The
action of these operators is illustrated in Figures
\ref{figure6.2} and \ref{figure6.3}.

    The following definitions are
standard, but we include them here for completeness.

\begin{definition}
Consider a closed  subset $X$ of $\SN$. $X$ is disconnected if it can be written as $ X=(A\cap X)\cup(B\cap X)$, where
$A$ and $B$ are disjoint open sets and both $A\cap X$ and $B\cap X$ are not empty. $X$ is connected if it is not
disconnected. The connected component of $\fxx$ in $X$, denoted by $cc(\fxx,X)$, is the maximal connected subset of $X$
that contains $\fxx$.
\end{definition}

We wish to define a denoising operator  on   $\mathcal L$ ; since some sets therein contain $\infty$, we need an
extension of the Lebesgue measure on  $\RR^N$ to $\SN$. This is immediately fixed by setting
$\text{meas}(\{\infty\})=+\infty$.
 The only property of this extended measure that we need to check is following:
\begin{lemma} \label{mesureinfinie} if $Y_n$ is a nonincreasing sequence of
compact sets of $S_N$, then  $\text{meas}(\cap_n  Y_n)=\lim_n \text{meas}(Y_n)$.
\end{lemma}

\begin{proof}
 If the compact sets $Y_n$  do not
contain $\infty$ for $n$ large enough, then they are bounded in $\RR^N$ for $n$ large and the result just follows from
Lebesgue theorem. If instead the sets $Y_n$ all contain $\infty$, then $\cap_n Y_n$ contains it too and all sets have
infinite measure.
\end{proof}

\begin{definition} Let $a>0$ a scale parameter and denote for
every   $X\in\mathcal
L$ by  $X_i$ its connected components,  so that $X=\bigcup_i X_i$.
We call \textit{small component killer} the operator on $\mathcal
L$ which removes from $X$ all connected components with area
stricly less than $a$ :
\begin{equation}
\mathcal T_a X=\bigcup_{\text{meas}\,(X_i)\geq a}X_i.
\end{equation}
\end{definition}
Theoretically, $X$ can have an uncountable number of  components; take, for example, the Cantor set. However, $X$ can
have only a countable number of components with positive measure. The assumption $\text{meas}(\{\infty\})=+\infty$
implies that all connected components of $X$ containing $\infty$ stay in $\mathcal T_aX$. We are going to prove that
the small component killer is upper semicontinuous and this uses some elementary topological lemmas.

\begin{lemma}\label{topology}
Consider an arbitrary  nonincreasing sequence of nonempty compact
sets $(Y_n)_{n\in\NN}$ of $\SN$ and its limit $Y=\bigcap_{n\in\NN}
Y_n$. Then $Y$ is not empty and compact. In addition, for any open
set $Z$ that contains $Y$, there is an index $n_0$ such that
$Y_n\subset Z$ for all $n\geq n_0$.
\end{lemma}
\begin{proof}
 The first property is a classical property of  compact sets.
 Assume by contradiction that the  second property is not true.
 Then $Y_{n}\cap(\SN\setminus
Z)\neq\emptyset$ infinitely often. This implies that
$(Y_n\cap(\SN\setminus Z))_{n\in\NN}$ is a nonincreasing sequence
of nonempty compact sets. But this means that $Y\cap (\SN\setminus
Z)\neq\emptyset$, which is a contradiction.
\end{proof}

\begin{lemma}\label{lemma6.14}
Let $(Y_n)_{n\in\NN}$ be a nonincreasing  sequence of nonempty
compact subsets of $\SN$ and consider the intersection
$Y=\bigcap_{n\in\NN}Y_n$. If the $Y_n$ are connected, then $Y$ is
connected.
\end{lemma}
\begin{proof}
We know that $Y$ is not empty and compact.   Suppose, by
contradiction, that $Y$ is not connected. Then we can represent
$Y$ by $Y=(Y\cap Z_1)\cup(Y\cap Z_2)$, where $Z_1$ and $Z_2$ are
disjoint open sets, $Y\cap Z_1\neq\emptyset$, and $Y\cap
Z_1\neq\emptyset$. Since $Y\subset Z_1\cup Z_2$, by Lemma
\ref{topology} there exists an $n_0$ such that $Y_n\subset Z_1\cup
Z_2$ for all $n\geq n_0$, and for these $n$ we have
\[
Y_n= Y_n\cap( Z_1\cup Z_2)=(Y_n\cap Z_1)\cup(Y_n\cap Z_2).
\]
Furthermore, $Y_n\cap Z_1\neq\emptyset$ and $Y_n\cap
Z_1\neq\emptyset$. This contradicts the fact  that the $Y_n$ are
connected.
\end{proof}

\begin{figure}[!t]
\setkeys{Gin}{width=12cm} \centerline{
\includegraphics{fig06.02.1.eps}
} \caption[Extrema killer]{ Extrema killer:  maxima killer
followed by minima killer. The extrema killer removes all
connected components of upper and lower level sets with area less
than some threshold, which here equals 20 pixels. Notice how
texture disappears in the second image. All other features seem
preserved.   On the second row, we see for both the original and
the processed image the level lines at 16 equally spaced levels.
The level lines on the right hand side are a subset of the level
lines of the left hand. All level lines surrounding extremal
regions with area smaller than 20 have been removed and the other
ones are untouched.  }\label{figure6.2}
\end{figure}

\begin{exercise} Show that
$\mathcal T_a$ is idempotent: ${\mathcal T_a}^2 X=\mathcal T_a X$ and that it is a contraction mapping: $\mathcal T_a
X\subset X$. \finex
\end{exercise}
 With the extrema killer we have a prime example of  a theory
that begins with a set operator $\mathcal T_a$ defined on
$\mathcal L$.
\begin{lemma}\label{semicontinuityofTa}
The small component killer  $\mathcal T_a$ is upper semicontinuous
on $\mathcal L$.
\end{lemma}
\begin{proof}
We first prove that $\mathcal T_a$  is monotone. Assume $X\subset Y$. Then for every $\fxx\in X$, $cc(\fxx,X)\subset
cc(\fxx,Y)$. If $\text{meas}\,(cc(\fxx,X))\geq a$, then $\text{meas}\,(cc(\fxx,Y))\geq a$, and we conclude that
$\mathcal T_a X\subset \mathcal T_a Y$. Now let $(X_n)_{n}$  be any nonincreasing sequence of nonempty compact sets and
$X=\cap_n X_n$. We wish to show that $\mathcal T_a X=\bigcap_{n}\mathcal T_a X_n$. By monotonicity of $\mathcal T_a$,
$$\mathcal T_a X\subset \bigcap_n \mathcal T_a(X_n).$$
Let us show the converse inclusion. Let $\fxx\in \cap_n \mathcal T_a(X_n)$. Then $Y_n:=cc(x, X_n)$ has measure larger
than $a$ for all $n$. In addition if $m<n$ then $Y_n\subset Y_m.$ By Lemmas \ref{topology} and \ref{lemma6.14},
$Y:=\cap_n Y_n$ is a connected compact set that contains $\fxx$. In addition by Lemma \ref{mesureinfinie},
${\rm{measure}}(Y)=\lim_{n} {{\rm measure}}(Y_n)\geq a.$  Since $Y=\cap_n Y_n\subset \cap_n X_n=X$, we have $cc(\fxx,
X)\supseteq Y$ and therefore $\fxx\in \mathcal T_a(X).$
\end{proof}

 We can now build a stack filter from $\mathcal T_a$.


\begin{definition} [and proposition]
The stack filter $T_a$ of $\mathcal T_a$  is called a maxima killer.  $\mathcal T_a$ and $T_a$ satisfy the commutation
with thresholds. As a consequence, no connected component of a level set of $T_au$ has measure less than $a$.
Furthermore, $T_a$ is standard monotone, translation and contrast invariant from $\mathcal F$ into $\mathcal F$.
\end{definition}

\begin{proof}    We just
have to check that all assumptions of  Theorem \ref{3.5bis} are
satisfied.
 $\mathcal T_a$ is obviously translation invariant,
monotone and is upper semicontinuous by Lemma
\ref{semicontinuityofTa}.  It satisfies $ \mathcal T_a(\emptyset)
= \emptyset$, $\mathcal T_a(\SN)= \SN$. $\mathcal T_a(E)$ is
compact if $E$  is.  Indeed, it is  the union of a finite set of
compact connected components. If $E$ is bounded in $\RR^N$, then
so is $\mathcal T_a E\subset E$.
 $(\mathcal T_a E)^c$ is bounded in
$\SN$ if $E^c$ is. Indeed, if $E^c$ is bounded, then $E$ has a connected component $Y$ containing $B(0,R)^c$ for some
$R>0$. This connected component has infinite measure. Then $\mathcal T_a (E)$ still contains $Y$ and $\mathcal
T_a(E)^c$ is contained in $B(0,R)$.  By construction, $\infty$ belongs to $\mathcal T_aX$ if and only if it belongs to
$X$. Thus, $\mathcal T_a$ is standard monotone.
\end{proof}

A maxima killer $T_a$ cuts off the maxima  of continuous
functions, but it does nothing for the minima.   We can
immediately define a minima killer $T_a^-$ as the dual operator of
$T_a$,
\[
T^-_a u=-T_a(-u).
\]
  A good denoising process is to alternate $T_a$ and
$T_a^-$, as illustrated in Figures \ref{figure6.2} and
\ref{figure6.3} . We note, however, that $T_a$ and $T_a^-$ do not
necessarily commute, as is shown in  Exercise
\ref{noncommutationTa}.



\section{Exercises}

\begin{exercise}\label{exercise8.4}
Let $g:\RR\to\RR$ be a contrast change.  Construct increasing
 contrast changes $g_n$ and $h_n$ such that $g_n(s)\to g(s)$,
$h_n(s)\to g(s)$ for all $s$ and $g_n\leq g\leq h_n$. Hint :
define first an increasing continuous function $f(s)$ on $\RR$
such that $f(-\infty)=0$ and $f(+\infty)=\frac 1n$. \finex
\end{exercise}

\begin{exercise}Let  $u:\RR^N\to\RR$.
 Show that
  $\tau_{\fxx}\levelset_\lambda u=\levelset_\lambda\tau_{\fxx}u$,
  $\fxx\in\RR^N$.\finex
\end{exercise}

\begin{exercise} Prove that a  translation
 invariant operator $\mathcal T$ from $\mathcal L$ to $\mathcal L$
satisfies one of the three possibilities : $\mathcal
T(\{\infty\})=\{\infty\}$, $\mathcal T(\{\infty\})=\SN$ or
$\mathcal T(\{\infty\})=\emptyset$. \finex
\end{exercise}

 \begin{exercise}\label{preservationbornes}
Let $T$ be a  translation invariant standard monotone operator on $\mathcal F$. Prove the following statements:
\begin{enumerate}[(i)]\setlength\itemsep{2pt}
\item $Tu=c$ for every constant function $u:\SN\to c$. \item
$u\geq c$ implies $Tu\geq c$, and $u\leq c$ implies $Tu\leq c$.
\item If in addition $T$ commutes with the addition of
constants, $\sup_{\fxx\in\RR^N}|Tu(\fxx)-Tv(\fxx)|\leq\sup_{\fxx\in\RR^N}|u(\fxx)-v(\fxx)|.$
\newline(Hint: Write $-\sup|u(\fxx)-v(\fxx)|\leq
u(\fxx)-v(\fxx)\leq\sup|u(\fxx)-v(\fxx)|$.)
\end{enumerate}
\finex
\end{exercise}

\begin{exercise}\label{boundedtobounded}$\;$

\skipaline 1) In dimension 1, consider the set operator defined on
$\mathcal L$ by $\mathcal T X=[\inf X, \infty]$ if $\inf
(X\cap\RR)\in\RR$, $\mathcal T X=S_1$ if $\inf (X\cap
\RR)=-\infty$, $\mathcal T(\{\infty\})=\{\infty\}$, $\mathcal
T(\emptyset)=\emptyset$. Check that $\mathcal T$ satisfies all
assumptions of Theorem \ref{3.5bis} except one. Compute the stack
filter associated with $\mathcal T$ and show that it satisfies all
conclusions of the mentioned theorem except one : $Tu$ does not
belong  to $\mathcal F$ and more specifically $Tu(\fxx)$ is not
continuous at $\infty$.

\skipaline 2)  Consider the function operator on $\mathcal F$,
$Tu(\fxx)=\sup_{\fxx\in \SN}u(\fxx)$. Check that $T$ is monotone,
contrast invariant, and sends $\mathcal F$ to $\mathcal F$.
Compute the level set extension $\mathcal  T$ of $T$.\finex
\end{exercise}

\begin{exercise}\label{noncommutationTa}
Let $N=1$ and take $u(x)=\sin x$ for $|x|\leq 8\pi$, $u(x)=0$ otherwise. Compute $T_a u$ and $T_a^- u$ and show that
they commute on $u$ if $a\leq\pi$ and do not commute if $a>\pi$. Following the same idea, construct a function $u\in
\mathcal F$ in dimension two such that $T_aT_a^- u\neq T_a^- T_a u$. \finex
\end{exercise}

\begin{exercise}\label{continuitydistancefunction}Let $X$ be a closed subset of a metric space endowed
with a distance $d$ and
 consider the distance function to $X$,
\[
d(\fxy)=d(\fxy,X)=\inf_{\fxx\in X}d(\fxx,\fxy).
\]
Show that $d$ is 1-Lipschitz, that is, $|d(\fxx,X)-d(\fxy,X)|\leq
d(\fxx,\fxy).$   \finex
\end{exercise}

\begin{exercise} In the following questions,
we explain the necessity of the assumptions $\mathcal T(\emptyset)=\emptyset$, $\mathcal T(\SN)=\SN$  for defining
 function monotone operators from $\mathcal F$ to $\mathcal F$.
\newline\newline
1) Set $\mathcal T(X)=X_0$ for all $X\in \mathcal L$, where
$X_0\neq \emptyset$ is a fixed set. Check that the associated
stack filter satisfies $Tu(\fxx)=+\infty$ if $\fxx\in X_0$,
$Tu(\fxx)=-\infty$ otherwise.
\newline\newline
2) Let $\mathcal T$ be a  monotone set operator, without further assumption.  Show that its associated stack filter $T$
is, however, monotone and
 commutes with all
 contrast changes. (We extend each contrast change $g$ by setting $g(\pm \infty)=\pm  \infty.$) \finex
\end{exercise}


\begin{exercise} \label{3.5bismesurable}  Take an operator $\mathcal T$
satisfying  the same assumptions as in Theorem \ref{3.5bis}, but defined on $\mathcal M$ and apply the arguments of the
proof of Theorem \ref{3.5bis}. Check that the stack filter associated with $\mathcal T$ is a contrast invariant,
translation invariant monotone operator on the set of all bounded measurable functions, $L^\infty(\RR^N)$. If in
addition $\mathcal T$ is upper semicontinuous on $\mathcal M$, then the commutation with thresholds holds. \finex
\end{exercise}


\begin{exercise} \label{contrexemplesemicontinuity}
The upper semicontinuity is necessary to ensure that a monotone
set operator defines a function operator such that the commutation
with thresholds $\levelset_\lambda (Tu) = \mathcal
 T(\levelset_\lambda(u)) $ holds for every $\lambda$. Let us choose
for example the following set operator $\mathcal T $,
$$ \mathcal T (X) = X   \; \hbox{ if meas}(X)>a \hbox{ and }
\mathcal T (X) = \emptyset \hbox{ otherwise }.
$$
(We  use the Lebesgue measure  on $\RR^N$, with the  completion $\text{meas}(\{\infty\})=+\infty$)

\skipaline 1) Prove that $\mathcal T$ is standard monotone.

\skipaline 2)
  Let $u$ be the function from $S_1$ into $S_1$ defined
by $u(x) = max(-|x|, -2a)$ for some $a>0$, with $u(\infty)=-2a$.
Check that u belongs to $\mathcal F$.  Then, applying the  stack
filter $T$ of $\mathcal T$, check that
$$T(u)(x) = \sup\{\lambda, x \in \mathcal T (\levelset_\lambda u)\}
= max(\min( -|x|, -a/2), -2a). $$

\skipaline 3) Deduce that $\levelset_{-a/2} T(u) = [-a/2,a/2]$, $\levelset_{-a/2} u = [-a/2,a/2]$ and therefore
$$\mathcal T(\levelset_{-a/2} u) = \emptyset \neq \levelset_{-a/2} T(u),$$ which means that $T$ does not commute with
thresholds.\finex
\end{exercise}



\begin{exercise} \label{necreepasdenouveauxniveaux} Like in the preceding exercise, we consider
here contrast invariant operators defined on all measurable
bounded functions of $\RR^N$. The aim of the exercise is to show
that such operators send images with finite range into images with
finite range. More precisely, denote by $R(u)=u(\RR^N)$ the range
of $u$. Then we shall prove that for every $u$, $R(Tu)\subset
\overline{Ru}$. In particular, if $R(u)$ is finite, then the range
of $Tu$ is a finite subset of $Ru$. If $u$ is binary, $Tu$ is,
etc.  This shows that contrast invariant operators preserve sharp
contrasts. A binary image is transformed into a binary image. So
contrast invariant operators create no blur, as opposed to linear
operators, which always create new intermediate grey levels.

\medskip\noindent 1) Consider
\[
g(s)=s+\frac1{2}d(s,\overline{Ru})
\]
where $d(s,X)$ denotes  the distance from $s$ to $X$, that is,
$d(s,X)=\inf_{x\in X}|s-x|$. Show that $g$ is   a contrast change
satisfying $g(s)=s$ for $s\in\overline{Ru}$ and $g(s)>s$
otherwise.

 \medskip\noindent 2) Check that $g(s)=s$ if and only
 if $s\in\overline{Ru}$.
In particular, $g(u)=u$. Deduce from this and from  the contrast
invariance of $T$  that for every $\fxx\in\RR^N$, $Tu(\fxx)$ is a
fixed point of $g$. Conclude. \finex
\end{exercise}







\begin{figure}[!t]
\setkeys{Gin}{width=6cm} \centerline{
\includegraphics{fig06.03.1.eps}
\includegraphics{fig06.03.2.eps}
}
\centerline{
\includegraphics{fig06.03.3.eps}
\includegraphics{fig06.03.4.eps}
} \caption[Extrema killer]{Extrema killer:  maxima killer followed by minima killer. Above, left: original image.
Above, right: image after extrema killer removed connected components of 20 pixels or less. Below: level lines (levels
of multiples of 16) of the image before and after the application of the extrema killer.}\label{figure6.3}
\end{figure}

\section{Comments and references}

\paragraph*{Contrast invariance and stack filters.} Image operators that commute with thresholds have been popular because, among other reasons, they are easily implemented in hardware (VLSI). This led to very simple patents being awarded in signal and image processing as late as 1987 \cite{Coyle:1987:DFT}. These operators have been given four different names, although operators are equivalent: \textit{stack filters} \cite{Butz:1986:CRO,Hardie:1994:RCR,Wendt:1986:SF}; \textit{threshold decomposition} \cite{Hereford:1988:NOI}; \textit{rank filters} \cite{Chen:1996:ODR,Kim:1986:RAP,Wilburn:1998:DGR}; and \textit{order filters} \cite{Tagare:1985:OF}. The best known of these are the sup, inf, and median operators. The implementation of the last named has received much attention because of its remarkable denoising properties \cite{Fitch:1984:MFT,Ochoa:1987:OMF,Yli-Harja:1991:APM}.

Maragos and Shafer \cite{Maragos:1987:MFPb,Maragos:1987:MFPa} and Maragos and Ziff \cite{Maragos:1990:TSM} introduced the functional notation and established the link between stack filters and the Matheron formalism in ``flat'' mathematical morphology. The complete equivalence between contrast-invariant operators and stack filters, as developed in this chapter, does not seem to have appeared elsewhere; at least we do not know of other references. A related classification of rank filters with elegant and useful generalizations to the so-called \textit{neighborhood filters} can be found in \cite{Kim:1986:RAP}.

\paragraph*{The extrema killer.} The extrema killer is probably the most efficient denoising filter for images degraded by impulse noise, which is manifest by small spots. In spite of its simplicity, this filter has only recently seen much use. This is undoubtedly due to the nontrivial computations involved in searching for the connected components of upper and lower level sets. The first reference to the extrema killer that we know is \cite{Cheng:1992:AMF}. The filter in its generality was defined by Vincent in \cite{Vincent:1993:GAO}. This definition fits into the general theory of connected filters developed by Salembier and Serra \cite{Salembier:1995:FZF}. Masnou defined a variant called the \textit{grain filter} that is both contrast invariant and invariant under reverse contrast changes \cite{Masnou:1998:IRI}. Monasse and Guichard developed a fast implementation of this filter based on the so-called \textit{fast level set transform} \cite{MnsseGchrd3}.

We will develop in Chapter 19 a theory of scale space that is based on a family of image smoothing operators $T_t$, where $t$ is a scale parameter. We note here that the family $(T_a)_{a\in\RR^+}$ of extrema killers does not constitute a scale space because it does not satisfy one of the conditions, namely, what we call the local comparison principle. That this is so, is the content of Exercise 19.1.
