%gmChap06.tex

\graphicspath{{./figures/}}
\begin{slide}
\begin{figure}[!ht]
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig02.08.1.eps}
}    Linear smoothing  can introduce new gray levels in an image.
One of the main properties of contrast-invariant operators is that
they do not create new grey levels in an image. This means in
practice that the contrast in images filtered by
contrast-invariant operators is not degraded.
 }
\end{figure}

\end{slide}
\begin{slide}

\section{Properties of Contrast-invariant function operators}

\begin{definition}
We say that a function operator $T$ is monotone if
\begin{equation}
u\geq v\, \Longrightarrow\, Tu\geq Tv.
\end{equation}
We say that a set operator $\mathcal T$ is monotone if
\begin{equation}
X\subset Y \,\Longrightarrow\, {\mathcal T} X\subset {\mathcal T} Y.
\end{equation}
\end{definition}


\begin{definition}
A function operator $T$ defined  on $\mathcal F$ is said to be
contrast invariant with respect to a set $\mathcal G$ of contrast
changes if $g\in\mathcal G$ and $u\in\mathcal F$ imply that
$g(u)\in\mathcal F$ and that
\begin{equation}
g(Tu)=Tg(u).
\end{equation}
\end{definition}
\end{slide}


\begin{slide}
\begin{proposition}
Let $T$ be a monotone, Lipschitz contrast invariant operator. Then
for every $u\in\mathcal F$, $R(Tu)\subset \overline{Ru}$. In
particular, if $Ru$ is finite, then the range of $Tu$ is a finite
subset of the range $Ru$ of $u$.
\end{proposition}
{\Large Proof:} Given $u\in\mathcal F$, we construct a continuous
contrast change $g$ such that $g(s)=s$ for $s\in\overline{Ru}$ and
$g(s)>s$ otherwise. One such function is given by
\[
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|$.  Function $g$ is nondecreasing  and
$\frac 32$-Lipschitz. Furthermore, $g(s)=s$ if and only if
$s\in\overline{Ru}$. In particular, $g(u)=u$. This and the
contrast invariance of $T$ imply that
\[
Tu=Tg(u)=g(Tu).
\]
Hence, for every $\fxx\in\RR^N$,  $Tu(\fxx)$ is a fixed point of
$g$. This means that $Tu(\fxx)\in\overline{Ru}$.
\end{slide}

\begin{slide}
  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 L$,
$\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)$.

\begin{definition}
A set operator $\mathcal T$ is said to be  translation invariant
if $X\in\mathcal L$ and $\fxx\in\RR^N$ imply that
$\tau_{\fxx}X\in\mathcal L$ and that
\[
\tau_{\fxx}{\mathcal T}X={\mathcal T}\tau_{\fxx}X.
\]

A function operator $T$ is said to  be translation invariant if
$u\in\mathcal F$ and $\fxx\in\RR^N$ imply that
$\tau_{\fxx}u\in\mathcal F$ and that
\[
\tau_{\fxx}Tu=T\tau_{\fxx}u.
\]
\end{definition}
\end{slide}

\begin{slide}
  We say that a function operator $T$ commutes with the
addition of constants if $u\in\mathcal F$ and $c\in\RR$ imply that
$u+c\in\mathcal F$ and that $T(u+c)=Tu+c$. Contrast-invariant
operators clearly commute with the addition of constants: Consider
the contrast change defined by $g(s)=s+c$.

\begin{lemma}
Let $T$ be a translation-invariant monotone  function operator
defined on $\mathcal F$ that commutes with the addition of
constants. If $u\in\mathcal F$ satisfies the  Lipschitz condition
$|u(\fxx)-u(\fxy)|\leq K|\fxx-\fxy|$, then
$|Tu(\fxx)-Tu(\fxy)|\leq K|\fxx-\fxy|$.
\end{lemma}
\end{slide}

\begin{slide}
\begin{proof}
For any $\fxx$, $\fxy$, and $\fxz$, we can write
\begin{equation}\label{eq64}
u(\fxy+\fxz )-K|\fxx -\fxy|\leq u(\fxx+\fxz) \leq u(\fxy+\fxz)+K|\fxx-\fxy|.
\end{equation}
Consider $\fxx$ and $\fxy$ fixed and the terms in \eqref{eq64} to be functions of $\fxz$. Since $T$ is monotone, we can apply $T$ to the functions in \eqref{eq64} and preserve the inequalities. If we do this and evaluate the result at $\fxz=0$, we have
\[
T(u(\fxy+\cdot )-K|\fxx -\fxy|)(0)\leq Tu(\fxx+\cdot)(0) \leq T(u(\fxy+\cdot)+K|\fxx-\fxy|)(0).
\]
Now use the fact that $T$ commutes with the addition of constants to obtain
\[
T(u(\fxy+\cdot )(0)-K|\fxx -\fxy|\leq Tu(\fxx+\cdot)(0) \leq T(u(\fxy+\cdot)(0)+K|\fxx-\fxy|.
\]
Next, use the translation invariance of $T$ to write
\[
Tu(\fxy)-K|\fxx -\fxy|\leq Tu(\fxx) \leq Tu(\fxy)+K|\fxx-\fxy|,
\]
which is the announced result.
\end{proof}
\end{slide}

\begin{slide}
\begin{exercise}
Assume that the function $u:\RR^N\to\RR$ is uniformly continuous and write
\[
|u(\fxx+\fxy)-u(\fxx)|\leq\varepsilon(|\fxy|),
\]
where $\fxx,\fxy\in\RR^N$  are arbitrary and $\varepsilon$ is the
modulus of continuity of $u$. Assume that $T$ is a
translation-invariant monotone operator that commutes with the
addition of constants. Prove that $Tu$ is uniformly continuous and
that the modulus of continuity of $Tu$ is dominated by
$\varepsilon$. (Hint: Adapt the preceding proof.) \finex
\end{exercise}
\end{slide}
\begin{slide}
\begin{exercise}
Let $T$ be a contrast-invariant monotone operator. Prove the following statements:
\begin{enumerate}%[(i)]\setlength\itemsep{2pt}
\item $Tu=c$ for every constant function $u:\RR^N\to c$.
\item $u\geq c$ implies $Tu\geq c$, and $u\leq c$ implies $Tu\leq c$.
\item $\sup|Tu(\fxx)-Tv(\fxx)|\leq\sup|u(\fxx)-v(\fxx)|$, where the supremum is taken over $\fxx\in\RR^N$. (Hint: Write
$-\sup|u(\fxx)-v(\fxx)|\leq u(\fxx)-v(\fxx)\leq\sup|u(\fxx)-v(\fxx)|$.)
\item Show that (i), (ii), and (iii) remain true under the weaker assumption that $T$ is monotone and commutes with the addition of constants. \finex
\end{enumerate}
\end{exercise}
\end{slide}

\begin{slide}
\section[From contrast-invariant function operators to set operators]{From contrast-invariant function operators to set operators: The threshold superposition principle}

We begin with a function operator $T$  defined on a class of
functions  $\mathcal F$, and we assume that $\mathcal F$ contains
the characteristic functions $\bmone_{\levelset_{\lambda}u}$ for
all $u\in\mathcal F$. Then we can associate with $T$ a set
operator $\mathcal T$ defined on $\mathcal L=\{X\mid
X=\levelset_{\lambda}u, u\in\mathcal F, \lambda\in\RR\}$ as
follows:
\begin{equation}\label{eq65}
{\mathcal T}X=\levelset_1T\bmone_X.
\end{equation}
  If $T$ is a monotone function operator, then $\mathcal T$ is
a monotone set operator. Indeed, $X\subset Y$ if and only if
$\bmone_X\leq\bmone_Y$, in which case $T\bmone_X\leq T\bmone_Y$
and $\levelset_1T\bmone_X\subset\levelset_1T\bmone_Y$.
\end{slide}

\begin{slide}
\begin{lemma}
Let $T$ be a monotone function operator  defined on $\mathcal F$
and assume that $T$ is Lipschitz contrast invariant. Consider the
threshold function $\gamma_\lambda$ defined by
$\gamma_\lambda(s)=1$ if $s\geq\lambda$ and $\gamma_\lambda(s)=0$
otherwise. Then, for  $u\in\mathcal F$,
\[
T\gamma_\lambda(u)=\gamma_\lambda(Tu)
\]
almost everywhere, except possibly for at  most a countable number
of $\lambda$'s.
\end{lemma}
\end{slide}

\begin{figure}[!t]
\setkeys{Gin}{width=10cm} \centerline{
\includegraphics{fig06.01.1.eps}
} \caption[Approximation of the threshold function]{\label{fig61}
Approximation of the threshold function $\gamma_\lambda$ from
above and from below}
\end{figure}
\begin{slide}
 {\Large Proof.}
${\gamma}_\lambda^{+\varepsilon}$ and
${\gamma}_\lambda^{-\varepsilon}$ are Lipschitz-continuous
contrast changes, and $
{\gamma}_\lambda^{-\varepsilon}\leq{\gamma}_\lambda\leq{\gamma}_\lambda^{+\varepsilon}$.
Since $T$ is monotone and since $T$ is invariant under
Lipschitz-continuous contrast changes,  for any $u\in\mathcal F$:
\[
{\gamma}_\lambda^{-\varepsilon}(Tu)=T{\gamma}_\lambda^{-\varepsilon}(u)\leq T{\gamma}_\lambda(u)\leq T{\gamma}_\lambda^{+\varepsilon}(u)={\gamma}_\lambda^{+\varepsilon}(Tu).
\]
As $\varepsilon\to0$, ${\gamma}_\lambda^{-\varepsilon}(s)\uparrow{\gamma}_\lambda^{-}(s)$ and ${\gamma}_\lambda^{+\varepsilon}(s)\downarrow{\gamma}_\lambda(s)$ for all $s\in\RR$. Thus, in the limit we have
\[
{\gamma}_\lambda^{-}(Tu)\leq
T{\gamma}_\lambda(u)\leq{\gamma}_\lambda(Tu),
\]
where ${\gamma}_\lambda^{-}(s)=1$ if $s>\lambda$ and ${\gamma}_\lambda^{-}(s)=0$ otherwise.
The crux of the proof is to show that
\[
{\gamma}_\lambda^{-}(Tu(\fxx))={\gamma}_\lambda(Tu(\fxx))
\]
almost everywhere, except possibly  for a countable number of
$\lambda$'s. The only $\fxx$ for which
${\gamma}_\lambda^{-}(Tu(\fxx))\not={\gamma}_\lambda(Tu(\fxx))$
are the points where $Tu(\fxx)=\lambda$. Let $\Lambda=\Lambda(Tu)$
be the (countable) set of $\lambda$ for which
$\text{meas}\,(\{\fxx\mid Tu(\fxx)=\lambda\})>0$.  If
$\lambda\not\in\Lambda$, then
${\gamma}_\lambda^{-}(Tu(\fxx))={\gamma}_\lambda(Tu(\fxx))$.

\end{slide}
 \begin{slide}
\begin{definition}
We say that the function operator $T$ is obtained from the set operator $\mathcal T$ by the threshold superposition principle almost everywhere if
\begin{equation}\label{eq66}
Tu(\fxx)=\sup\{\lambda\mid \fxx\in{\mathcal T}\levelset_\lambda u\}
\end{equation}
for almost every $\fxx\in\RR^N$.
\end{definition}
\end{slide}

\begin{slide}
The relation \eqref{eq68} 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\}.
\]
\end{slide}

\begin{slide} We assume that
 $\mathcal F$ contains $\bmone_{\levelset_{\lambda}u}$
for $u\in\mathcal F$,  $\mathcal L$ is the set of all level sets
$\levelset_{\lambda}u$, $u\in\mathcal F$.
\begin{proposition}
Let $T$ be a monotone contrast  invariant function operator
defined on $\mathcal F$. Define the associated set operator
$\mathcal T$ on $\mathcal L$ by ${\mathcal
T}X=\levelset_1T\bmone_X$. Then
\begin{enumerate}%[$(i)$]\setlength\itemsep{2pt}
\item If $u\in \mathcal F$, then
\begin{equation}
\label{eq67}
{\mathcal T}\levelset_\lambda u = \levelset_\lambda Tu
\end{equation}
almost everywhere, except possibly for at most a countable number of $\lambda$'s.
\item The threshold superposition principle holds almost everywhere:
\begin{equation}\label{eq68}
Tu(\fxx)= \sup\{\lambda\mid \fxx \in {\mathcal T}\levelset_\lambda u\}\quad \text{for a.e. $\fxx\in\RR^N$.}
\end{equation}
\item $\mathcal T$ is monotone,  $\mathcal T \emptyset=\emptyset$,
and ${\mathcal T}\RR^N=\RR^N$.
\end{enumerate}
\end{proposition}
\end{slide}



\begin{slide}
\section{From set operators to contrast invariant function
operators. \label{setoptoimop}}
\def\setT{\mathcal T}
\def\real{\RR}


Can we extend a set monotone operator into a contrast invariant
and monotone operator defined on an adequate set of functions ? We
start from a set operator $\setT $, defined on a subset $\cal L$
of ${\cal P}(\real^N)$ and with values  in $\cal L$.  We assume
that $\setT $ is a {\it monotone} operator, that is, $X \subset Y
\Rightarrow \setT (X) \subset \setT (Y)$.   We define $\cal F$  as
the set of all real functions defined on $\real^N$ whose level
sets $\levelset_\lambda u$ belong to $\cal L$. As a consequence,
$\cal F$ contains the characteristic functions of elements of
$\cal L$.

\end{slide}

\begin{slide}
 A natural definition for the function operator $T$
associated with $\setT$ is given  by the threshold superposition
principle,
$$
Tu(\fxx) = \sup\{ \lambda, \fxx \in \setT(\levelset_\lambda u)\}
$$
 We have now to check whether $T$ is contrast invariant.
\end{slide}
\begin{slide}
\begin{proposition} \label{setoperatortoimageoperatorfaible}
Let $\setT$, ${\cal T} \rightarrow {\cal T}$ be a monotone
operator satisfying
$$ T(\emptyset) = \emptyset,  \setT(\real^N)= \real^N $$
Then the operator $T$ defined on $\cal F$ by superposition
principle, $$  \label{superpositionprinciple2}
 Tu(\fxx) = \sup \{\lambda, \fxx \in \setT(\levelset_\lambda u) \}
 $$
 satisfies,  for almost every $\lambda \in \real$,
$$ \levelset_\lambda (Tu) = \setT(\levelset_\lambda(u)) \hbox{
almost everywhere in }  \fxx $$ and for any nondecreasing
continuous contrast change  $g$, $$ g(Tu) = T(g(u)). $$
\end{proposition}
\end{slide}
\begin{slide}
\paragraph{Proof}

The relation  $$  \label{superpositionprinciple2}
 Tu(\fxx) = \sup \{\lambda, \fxx \in \setT(\levelset_\lambda u) \}
 $$ implies that  for almost every $\lambda$
$$ \levelset_\lambda (Tu) = \setT(\levelset_\lambda u) \hbox{
almost everywhere} \label{ae1} $$ that is for all $\lambda$ in a
subset $\Lambda$ of $\real$ such that $\meas(\real \setminus
\Lambda) = 0$. We notice that $u \leq v$ if and only if
$\levelset_\lambda u \subset \levelset_\lambda v$ for all
$\lambda$ in a dense countable subset of $\real$.  We deduce
immediately that $T$ is monotone, ie $u \geq v \; \Rightarrow Tu
\geq Tv$.
\end{slide}

\begin{slide}
 Let us now  show that $T$ commutes with contrast changes.
Assume first that $g$ is strictly increasing. By  the
superposition principle:
$$T(g(u(\fxx)))=\sup \{\lambda, \; g(-\infty)\leq \lambda\leq g(+\infty), \; \fxx\in\setT(\levelset_\lambda g(u))\}$$
$$=\sup\{g(\mu),\;  \fxx\in \setT(\levelset_{g(\mu)}g(u))\}$$
$$=\sup\{g(\mu),\; \fxx\in \setT(\levelset_\mu u)\}= g(Tu(\fxx)).$$
Then, approximate uniformly nondecreasing $g$'s by increasing ones
and use the preceding result and the commutation of $T$ with
constants. \end{slide}

\begin{slide}

We shall now examine stronger conditions on $\setT$, which ensure
commutation of $T$ with all thresholds $\levelset_\lambda$ (and
not only with almost all of them).

\begin{definition}\label{definitionuppersemicontinuousoperator}
We say that a set operator $\setT$ is upper semicontinuous if for
every nonincreasing sequence of sets $X_n \in \cal T$, we have
$$ \label{vii.2} \setT(\bigcap_n X_n) = \bigcap_n \setT(X_n).
$$
\end{definition}

\begin{theorem} \label{3.5bis}
Let $\setT $: $\cal T$ $\to \cal T$ be a monotone upper
semicontinuous set operator satisfying $ \setT(\emptyset) =
\emptyset$ and  $\setT(\real^N)= \real^N.$ Then the function
operator defined by

$$ Tu(\fxx) = \sup \{\lambda, \fxx \in \setT (\levelset_\lambda
u) \}. $$ is contrast invariant and satisfies, for every
$\lambda,$ $$ \label{FGencore2} \levelset_\lambda (Tu) =
\setT(\levelset_\lambda(u)). $$
\end{theorem}
\end{slide}


\begin{slide}
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) =
\setT(\levelset_\lambda(u)) $ holds for every $\lambda$. Let us
choose for example the following set operator $\setT $,
$$ \setT (X) = X   \; \hbox{ if meas}(X)>a \hbox{ and } \setT (X) = \emptyset \hbox{
otherwise }.
$$
Let  $u$ be the function from $\real$ into $\real$ defined by
$u(x) = -|x|$.  Then
$$T(u)(x) = \sup\{\lambda, x \in \setT (\levelset_\lambda u)\} = \min( -|x|, -a/2) $$
Therefore
$$\levelset_{-a/2} T(u) = [-a/2,a/2]. $$
Now, $\levelset_{-a/2} u = [-a/2,a/2]$ ; its measure is $a$. Thus
$$T(\levelset_{-a/2} u) = \emptyset \neq \levelset_{-a/2} T(u),$$
which means that $T$ is not contrast invariant.

\end{slide}




\begin{slide}
\section{The extrema killer: An application}

 \begin{equation}
\mathcal T_a X=\bigcup_{\text{meas}\,(X_i)\geq a}X_i.
\end{equation}

We are going to prove that  the small component killer is upper
semicontinuous on descending sequences of compact subsets.

\begin{lemma}
Let $(Y_n)_{n\in\NN}$ be a  descending sequence of nonempty
compact subsets of $\RR^N$, and consider the intersection
$Y=\bigcap_{n\in\NN}Y_n$. If the $Y_n$ are connected, then $Y$ is
connected.
\end{lemma}
\end{slide}

\begin{figure}[!t]
\setkeys{Gin}{width=7cm} \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.}
\end{figure}


\begin{slide}
\begin{lemma}
The small component killer $\mathcal T_a$ is upper semicontinuous on $\mathcal L$, the set of all compact subsets of $\RR^N$.
\end{lemma}




\begin{definition}
The function operator $T_a$ defined by
\[
T_a u(\fxx)=\sup\{\lambda\mid \fxx\in \mathcal T_a\levelset_\lambda u\}
\]
on the set $\mathcal F$ of functions in $L_C$ whose level sets are compact (as subsets of $\mathbb T^N$) is called a maxima killer.
\end{definition}

\begin{theorem}
The maxima killer $T_a$ is monotone, contrast invariant, and translation invariant, and
\begin{equation}\label{eq620}
\levelset_\lambda T_a u=\mathcal T_a\levelset_\lambda u
\end{equation}
for all $\lambda$. As a consequence of \eqref{eq620}, no connected component of a level set of $Tu$ has measure less than $a$. Furthermore, $T_a$ maps
the continuous $C$-periodic functions into continuous $C$-periodic functions.
\end{theorem}
\end{slide}



\begin{slide}
A maxima killer $T_a$  cuts off the peaks of continuous functions,
but it does nothing for the ``valleys.'' We could define a minima
killer to fill the valleys by developing a dual theory based on
lower level sets $\levelset_{\lambda}^-u=\{\fxx\mid
u(\fxx)\leq\lambda\}$.   It is, however, simpler to define a
minima killer $T_a^-$ in terms of $T_a$ as
\[
T^-_a u=-T_a(-u).
\]

It is clear that both of these  operators have the same continuity
properties. A good denoising process is to alternate $T_a$ and
$T_a^-$, as illustrated in Figures 6.2 and 6.3 . We note, however,
that $T_a$ and $T_a^-$ do not necessarily commute, as is shown in
the next exercise.

\begin{exercise}
Let $N=1$ and take $u(x)=\sin x$. 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 function $u$ defined on $[-\pi,\pi]^2$ such that $T_aT_a^-  u\neq T_a^- T_a u$. \finex
\end{exercise}
\end{slide}

\begin{figure}[!t]
\setkeys{Gin}{width=4.5cm}
\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 removes connected components of 20 pixels or less. Below: level lines (levels of multiples of 4) of the image before and after the application of the extrema killer.}
\end{figure}
