%gmChap06.tex

\graphicspath{{./figures/chapter06/}}

\chapter[Contrast-Invariant Monotone Operators]{Contrast-Invariant Monotone Operators. The Threshold Decomposition Principle}

This chapter is a direct continuation of Chapter 3. We are going to establish the relations between monotone image operators that are contrast invariant and monotone set operators. We first show how to define a set operator from a function operator using the function's level sets, and then we show how to construct a contrast-invariant monotone function operator from a monotone set operator. This development culminates in Theorem 6.12. As a first application of these ideas, we introduce the successful denoising operator due to Vincent and Serra called the extrema killer.

\section{Contrast-invariant function operators}

We will be dealing with operators $T$ defined on a set $\mathcal F$ of real-valued functions on $\RR^N$. We will also be considering set operators $\mathcal T$ defined on a collection of subsets of $\RR^N$, which we denote by $\mathcal L$. We are primarily interested in the duality between a function operator $T$ and a set operator $\mathcal T$ that is established either by beginning with $T$ and defining $\mathcal T$ on the level sets of functions in $\mathcal F$ or by starting with $\mathcal T$ and defining $T$ on functions whose level sets are in $\mathcal L$. With this in mind, when we begin with $T$, we will usually (but not always) assume that $\bmone_{\levelset_{\lambda}u}\in\mathcal F$ whenever $u\in\mathcal F$. On the other hand, if we begin with $\mathcal T$, then we will assume that $\mathcal L$ is closed under descending chains, which means that $\bigcap_{\mu<\lambda}X_\mu\in\mathcal L$ whenever $(X_\lambda)_{\lambda\in\RR}$ is a descending chain in $\mathcal L$. For example, if we begin with $T$ defined on a set  $\mathcal F$ of continuous real-valued functions on $\RR^N$, then $\mathcal L$ is a collection of closed subsets of $\RR^N$. If $\mathcal F$ is a set of Lebesgue-measurable functions on $\RR^N$, then $\mathcal L$ is a set of Lebesgue-measurable subsets of $\RR^N$. If we begin with a $\mathcal T$ defined on all of the compact subsets of $\RR^N$, then the functions in $\mathcal F$ will have compact level sets. There are other examples, but the main point is that the duality between a function operator $T$ and a set operator $\mathcal T$ will depend on a relation between $\mathcal F$ and $\mathcal L$.

We are mainly interested in monotone operators, since they are nonlinear generalizations of linear smoothing using a nonnegative convolution kernel.

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

Recall from Chapter 3, Definition 3.9, that any nondecreasing function $g:\RR\to\RR$ is called a contrast change. In case $g$ is continuous, we call it a continuous contrast change.

\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}
If $\mathcal G$ consists of all continuous contrast changes, we simply say that $T$ is contrast invariant.
\end{definition}

It is important to note that saying that $T$ is contrast invariant with respect to some $\mathcal G$ carries with it the information that the domain of $T$ is invariant with respect to $\mathcal G$. We denote the set of contrast changes that satisfy a Lipschitz condition by $\mathcal G_{Lip}$.

We saw in Figures 2.6, 2.7, and 2.8 that 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 (see Figure 2.7(c)). This is made precise by the next result. The range $Ru$ of a function $u:\RR^N\to\RR$ is the set $\{s\mid u(\fxx)=s\text{ for some }\fxx\in\RR^N\}$.

\begin{proposition}
Let $T$ be an operator on a function space $\mathcal F$ and assume that $T$ is contrast invariant with respect to $\mathcal G_{Lip}$. 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 $Ru$.
\end{proposition}
\begin{proof}
Given $u\in\mathcal F$, we wish to have 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|$. The function $s\mapsto d(s,X)$ is continuous in any complete metric space, and the fact that $g$ is nondecreasing follows directly from the definition of $g$ and the triangle inequality. Thus $g$ is a continuous contrast change. It is not difficult to show that $g\in\mathcal G_{Lip}$, and we leave this as an exercise. Furthermore, $g(s)=s$ if and only if $s\in\overline{Ru}$, and $g(s)>s$ if $s\not\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}$, which proves the result.
\end{proof}

The following exercise is more general than is needed for the proof of Proposition 6.3, however, the result will be used in Chapter 7.

\begin{exercise}Let $X$ be a closed subset of $\RR^N$ and consider the distance function 
\[
d(\fxy)=d(\fxy,X)=\inf_{\fxx\in X}|\fxx-\fxy|.
\]
Show that $d$ satisfies a Lipschitz condition. Outline: Let $Y_\lambda=\{\fxy\mid d(\fxy)\leq\lambda\}$. First, show that $Y_\mu=\{\fxy\mid d(\fxy,Y_\lambda)\leq\mu-\lambda\}$ for $\mu>\lambda$. Next, assume that $d(\fxy_0)<d(\fxy_1)$ and show that $\fxy_0\in Y_{d(\fxy_0)}$ but that $\fxy_1\not\in Y_{(d(\fxy_0)+d(\fxy_1))/2}$. Conclude that $d(\fxy_1,Y_{d(\fxy_0)})\geq (d(\fxy_1)-d(\fxy_0))/2$. \finex
\end{exercise}

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 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)$. Although $\tau_{\fxx}$ denotes two different operators, there should be no confusion because the domains are completely different. We can now define the notion of translation invariance.

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

Translation-invariant operators will play a larger role in Chapter 7 than they do here. We have introduced them now so we can prove Lemma 6.5, but before doing so, we need to define one more invariance. 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|$ and $K'\leq K$.
\end{lemma}  
\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}

The regularity-preserving properties of monotone operators are further developed in the following exercises.

\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 proof of Lemma 6.5.) \finex
\end{exercise}

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

\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}
The first thing to notice is that $\mathcal T$ is well defined in the sense that the right-hand side of \eqref{eq65} is a subset of $\RR^N$. Without further assumptions about $T$, we cannot say much more. 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$.

\begin{exercise}
If $T$ is contrast invariant with respect to $\mathcal G_{Lip}$, then we know from Proposition 6.3 that 
$
RT\bmone_X\subset R\bmone_X\subset\{0,1\}. 
$
Thus, in this case, $T\bmone_X$ is the characteristic function of some set $Y\subset\RR^N$. Prove that $Y={\mathcal T}X$, that is, that $T\bmone_X=
\bmone_{{\mathcal T}X}$, where $\mathcal T$ is defined by \eqref{eq65}. \finex
\end{exercise}

Much of what follows in this chapter and in Chapter 7 is based on the next result. For this reason, it is important to pay close attention to the assumptions, which are the standard assumptions we will make when proving results about monotone function operators. Our immediate goal is to reconstruct the function operator $T$ from the set operator $\mathcal T$.

\begin{lemma}
Let $T$ be a monotone function operator defined on $\mathcal F$ and assume that $T$ is contrast invariant with respect to $\mathcal G_{Lip}$. Consider the threshold function $\gamma_\lambda$ defined by $\gamma_\lambda(s)=1$ if $s\geq\lambda$ and $\gamma_\lambda(s)=0$ otherwise, and assume that $\gamma_\lambda(u)\in\mathcal F$ for $u\in\mathcal F$ and $\lambda\in\RR$. 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. The inequality $T\gamma_\lambda(u)\leq\gamma_\lambda(Tu)$ holds for all $\lambda\in\RR$.
\end{lemma}
\begin{proof}
Consider the two functions ${\gamma}_\lambda^{+\varepsilon}$ and ${\gamma}_\lambda^{-\varepsilon}$, illustrated in Figure 6.1, that are defined for $\varepsilon>0$ as follows:
\begin{align*}
{\gamma}_\lambda^{+\varepsilon}(s)&=
\begin{cases}
0 &\text{ if } s\leq\lambda-\varepsilon;\\
\displaystyle{\frac{s-(\lambda-\varepsilon)}{\varepsilon}} &\text{ if }\lambda-\varepsilon\leq s\leq\lambda;\\
1 &\text{ if }s\geq\lambda.
\end{cases}\\
{\gamma}_\lambda^{-\varepsilon}(s)&={\gamma}_\lambda^{+\varepsilon}(s-\varepsilon).
\end{align*}
Then ${\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$ and $\mathcal F$ are invariant under Lipschitz-continuous contrast changes, we have the following relations 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 set of $\lambda$ for which $\text{meas}\,(\{\fxx\mid Tu(\fxx)=\lambda\})>0$. We know from Exercise 3.5 that $\Lambda$ is at most countable. ($\Lambda$ may be the empty set.) If $\lambda\not\in\Lambda$, then ${\gamma}_\lambda^{-}(Tu(\fxx))={\gamma}_\lambda(Tu(\fxx))$ almost everywhere. 
\end{proof}

We will usually write ``$\bmone_{\levelset_{\lambda}u}\in\mathcal F$'' rather than ``$\gamma_\lambda(u)\in\mathcal F$,'' but of course they mean the same thing. This is an important assumption about the domain of $T$, and if $\bmone_{\levelset_{\lambda}u}$ is not in $\mathcal F$, we may wish to extend $T$ to these functions, as is done in section 7.3.

\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$. If \eqref{eq66} is true for all $\fxx$, then we say that the threshold superposition principle holds everywhere.
\end{definition}

\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{proposition}
Let $T$ be a monotone function operator defined on $\mathcal F$ and assume that $T$ is contrast invariant with respect to $\mathcal G_{Lip}$. Assume that $\mathcal F$ contains $\bmone_{\levelset_{\lambda}u}$ for $u\in\mathcal F$, and let $\mathcal L$ be the set of all level sets $\levelset_{\lambda}u$, $u\in\mathcal F$. Define the associated set operator $\mathcal T$ on $\mathcal L$ by ${\mathcal T}X=\levelset_1T\bmone_X$. Then we have the following results:
\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}

\begin{proof}By definition, ${\mathcal T}\levelset_\lambda u=\levelset_1 T\bmone_{\levelset_\lambda u}$. We have ${\mathcal T}\levelset_\lambda u=\levelset_1 T\gamma_\lambda(u)$ everywhere, since $\gamma_\lambda(u)=\bmone_{\levelset_\lambda u}$. By Lemma 6.6, we can interchange the order of $T$ and $\gamma_\lambda$, with the possible exception of a countable number of $\lambda$. Call this possible exceptional set $\Lambda=\Lambda(Tu)$. Then for $\lambda\in\RR\setminus\Lambda$,  ${\mathcal T}\levelset_\lambda u=\levelset_1 \gamma_\lambda(Tu)$ almost everywhere. But $\levelset_1 \gamma_\lambda(v)=\levelset_\lambda v$ everywhere, and we conclude that for $\lambda\in\RR\setminus\Lambda$, ${\mathcal T}\levelset_\lambda u=\levelset_\lambda Tu$ almost everywhere, which proves $(i)$.

By Exercise 3.1, we have $Tu(\fxx)=\sup\{\lambda\mid\fxx\in\levelset_\lambda Tu\}$. Using $(i)$ and Lemma 3.8, we can replace $\levelset_\lambda Tu$ with  ${\mathcal T}\levelset_\lambda u$ to obtain the almost-everywhere result $(ii)$.

We have already shown that ${\mathcal T}$ is monotone. The other statements in $(iii)$ follow directly from the definition of $\mathcal T$ and the fact that $T$ is contrast invariant: ${\mathcal T}\emptyset=\levelset_1 T\bmone_\emptyset$. But $\bmone_\emptyset(\fxx)=0$ for all $\fxx$, and by Exercise 6.2(i) $T\bmone_\emptyset(x)=0$ for all $\fxx$. This means that  $\levelset_1 T\bmone_\emptyset=\{\fxx\mid T\bmone_\emptyset(x)\geq1\}=\emptyset$. A similar argument shows that ${\mathcal T}\RR^N=\RR^N$.
\end{proof}

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\}.
\]
The stack-filter method will be developed in Chapter 23 to maintain accurate contrast invariance in numerical schemes for several contrast-invariant PDEs.

\section{From set operators to contrast-invariant function operators}

We have seen in the last section how a contrast-invariant monotone function operator $T$ can be used to define a monotone set operator $\mathcal T$ and how the function operator can be recovered from $\mathcal T$ using the threshold superposition principal. A natural question is, Can a monotone set operator be used to define a contrast-invariant monotone function operator? The positive answer is given by Proposition 6.10, but first we will establish the setting. 

We are given a monotone set operator $\mathcal T$ defined on a family of measurable subsets of $\RR^N$ denoted by $\mathcal L$, and we wish to define a function operator $T$ by superposition on some set of real-valued functions $\mathcal F$. The first question to answer is, How is $\mathcal F$ defined? There are at least two ways to proceed. Since we are given $\mathcal L$, we may be aware of some functions $\mathcal F$ all of whose level sets belong to $\mathcal L$. This means that given $u\in\mathcal F$, there is a closed descending chain $(\levelset_{\lambda}u)_{\lambda\in\barR}$ in $\mathcal L$ identified with $u$. There may, however, be descending chains in $\mathcal L$ that are not the level sets of some $u\in\mathcal F$. Since the focus in on $\mathcal T$ and $\mathcal L$, we prefer to proceed as follows: Let $\mathcal F$ be the set of all functions $u$ defined by
\begin{equation}\label{defF}
u(\fxx)=\sup\{\lambda\mid \fxx\in X_\lambda\},
\end{equation}  
where $(X_\lambda)_{\lambda\in\barR}$ is a closed descending chain in $\mathcal L$. Then $\mathcal F$ contains all of the characteristic function $\bmone_X$ for $X\in\mathcal L$. (To see this, let $(X_\lambda)_{\lambda\in\barR}$ be defined by $X_\lambda=\RR^N$ for $\lambda\leq0$, $X_\lambda=X$ for $0<\lambda\leq1$, and $X_\lambda=\emptyset$ for $\lambda>1$.)

At this point, one might ask, What about the functions $u$ that are generated by descending chains that are not closed? If $u$ is such a function, we know from Proposition 3.2 that $X_\lambda\subset\levelset_{\lambda}u=\bigcap_{\mu<\lambda}X_\mu$. Since we plan to define $T$ on $u$ by superposition,
\begin{equation}\label{defT}
Tu(\fxx)=\sup\{\lambda\mid \fxx\in\mathcal T X_\lambda\},
\end{equation}
where $(X_\lambda)_{\lambda\in\barR}$ is the chain in $\mathcal L$ that generated $u$, we want to be assured that $X_\lambda$ is indeed the level set $\levelset_{\lambda}u$. It is for this reason that we make the further assumption about $\mathcal L$: If $(X_{\lambda})_{\lambda\in\barR}$ is a descending chain in $\mathcal L$, then $\bigcap_{\mu<\lambda}X_\mu\in\mathcal L$. This implies that the functions in $\mathcal F$ are in one-to-one correspondence with the equivalence classes of descending chains in $\mathcal L$.

If we wish to have $T$ contrast invariant with respect to some set $\mathcal G$ of continuous contrast changes, then it would appear that we need to make some assumptions about $\mathcal T$ and $\mathcal L$ that will lead to this result. Clearly, the required assumption should be equivalent to saying that for $g\in\mathcal G$, $u\in\mathcal F$ implies that $g(u)\in\mathcal F$. By Corollary 3.16, this is equivalent to saying that $(X_{g^{-1}(\lambda)})_{\lambda\in\barR}$ is a closed descending chain in $\mathcal L$ whenever $(X_{\lambda})_{\lambda\in\barR}$ is a closed descending chain in $\mathcal L$. It is one of the advantages of starting with $\mathcal T$ and $\mathcal L$ that no further assumptions are needed. Roughly speaking, monotone set operators are contrast invariant.

\begin{lemma}If $(X_{\lambda})_{\lambda\in\barR}$ is closed descending chain in $\mathcal L$, then $(X_{g^{(-1)}(\lambda)})_{\lambda\in\barR}$ is a closed descending chain in $\mathcal L$ for any continuous contrast change $g$.
\end{lemma} 
\begin{proof}We wish to show that $X_{g^{(-1)}(\lambda)}=\bigcap_{\mu<\lambda}X_{g^{(-1)}(\mu)}$ for $\lambda>-\infty$. ($X_{g^{(-1)}(-\infty)}=\RR^N$, since $X_{-\infty}=\RR^N$.) We are going to use Lemma 3.18, so we will first consider $\lambda\in(\lambda^-,\lambda^+)$, where $\lambda^-=g(-\infty)$ and 
$\lambda^+=g(+\infty)$. We also assume that $\lambda^-<\lambda^+$. Let $(\mu_n)_{n\in\NN}$ be an increasing sequence that tends to $\lambda$ as $n\to+\infty$. By Lemma 3.18, we know that $s_n=g^{-1}(\mu_n)$ is a strictly increasing sequence such that $s_n\uparrow g^{(-1)}(\lambda)$. Since
$(X_{\lambda})_{\lambda\in\barR}$ is a closed 
descending chain in $\mathcal L$, 
\[
X_{g^{(-1)}(\lambda)}=\bigcap_{s<g^{(-1)}(\lambda)}X_s=
\bigcap_{s_n}X_{s_n}.  
\]
Similarly, $\bigcap_{\mu<\lambda}X_{g^{(-1)}(\mu)}=\bigcap_{\mu_n}X_{g^{(-1)}(\mu_n)}$, and since $\bigcap_{\mu_n}X_{g^{(-1)}(\mu_n)}=\bigcap_{s_n}X_{s_n}$, we have the result for $\lambda\in(\lambda^-,\lambda^+)$. The points $\lambda\leq\lambda^-$ and $\lambda\geq\lambda^+$ are easily checked using Lemma 3.18 and Exercise 3.13.
\end{proof}

\begin{proposition}
Assume that $\mathcal T$ is a monotone operator defined on a family of sets $\mathcal L$ with the property that $\bigcap_{\mu<\lambda}X_\mu\in\mathcal L$ whenever $(X_\lambda)_{\lambda\in\barR}$ is a descending chain in $\mathcal L$. Assume further that $\emptyset, \RR^N\in\mathcal L$ and that $\mathcal T\emptyset=\emptyset$ and $\mathcal T\RR^N=\RR^N$. Let $\mathcal F$ be the set of all functions $u$ defined by
\[
u(\fxx)=\sup\{\lambda\mid\fxx\in X_\lambda\},
\] 
where $(X_\lambda)_{\lambda\in\barR}$ is a closed descending chain in $\mathcal L$. Define the operator $T$ on $\mathcal F$ by 
\[
Tu(\fxx)=\sup\{\lambda\mid\fxx\in\mathcal T X_\lambda\},
\]
where $(X_\lambda)_{\lambda\in\barR}$ is the chain that generated $u$.
Then the $T$ defined on $\mathcal F$ is monotone and contrast invariant. Furthermore, for $u\in\mathcal F$, 
\begin{equation}\label{eq611}
\levelset_\lambda Tu=\mathcal T \levelset_\lambda u
\end{equation}
almost everywhere, except possibly for at most a countable number of $\lambda$'s.
\end{proposition} 

\begin{proof}The assumptions about $\mathcal L$ allow us to identify the level sets of functions in $\mathcal F$ directly with the sets (chains) in $\mathcal L$ that were used to generate them. Thus, we have a choice: We can write either $\levelset_{\lambda}u$ or $X_\lambda$, where $X_\lambda$ is in the chain that generated $u$. 

The proof of \eqref{eq611} is read from Corollary 3.7 by taking $X_\lambda=\mathcal T\levelset_\lambda u$ and checking that $X_{-\infty}=\RR^N$. The latter follows from the assumption that $\mathcal T\RR^N=\RR^N$ and the fact that $\levelset_{-\infty}u=\RR^N$ (recall that $u:\RR^N\to\RR$).

If $u\geq v$, then $\levelset_\lambda v\subset\levelset_\lambda u$; thus  $\mathcal T\levelset_\lambda v\subset\mathcal T\levelset_\lambda u$, since $\mathcal T$ is monotone. If, for some $\fxx\in\RR^N$, $Tu(\fxx)<Tv(\fxx)$, then there is a $\lambda$ such that $Tu(\fxx)<\lambda\leq Tv(\fxx)$ and $\fxx\in\mathcal T \levelset_\lambda v$ but $\fxx\not\in\mathcal T\levelset_\lambda u$. This is a contradiction. Thus, $u\geq v$ implies that $Tu\geq Tv$.

To prove that $T$ is contrast invariant, we are going to show that $Tg(u)$ and $g(Tu)$ have the same level sets whenever $g$ is any continuous contrast change. This follows from the monotonicity of $\mathcal T$ and the properties of $g^{(-1)}$ given in Lemmas 3.18 and 6.9. As before, we use the notation $\lambda^+=g(+\infty)$ and $\lambda^-=g(-\infty)$, and we assume that $\lambda^+>\lambda^-$. (The case $\lambda^+=\lambda^-$ is easily checked.) Thus, assume that $\lambda\in(\lambda^-,\lambda^+)$. For this $\lambda$, $g^{(-1)}(\lambda)<+\infty$, so we know from Corollary 3.16 that $g(s)\geq\lambda$ if and only if $s\geq g^{(-1)}(\lambda)$. Thus,
\begin{equation}\label{eq612}
\levelset_{\lambda}g(Tu)=\{\fxx\mid g(Tu(\fxx))\geq\lambda\}=\{\fxx\mid Tu(\fxx)\geq g^{(-1)}(\lambda)\}=\levelset_{g^{(-1)}(\lambda)}Tu.
\end{equation}
The function $Tu$ is generated by the descending chain $(\mathcal T X_s)_{s\in\barR}$, and although we may not be able to write $\levelset_{g^{(-1)}(\lambda)}Tu=\mathcal T X_{g^{(-1)}(\lambda)}$, we can always write
\[
\levelset_{\lambda}g(Tu)=\levelset_{g^{(-1)}(\lambda)}Tu=\bigcap_{s<g^{(-1)}(\lambda)}\mathcal T X_s.
\] 

Now consider $g(u)$. The function $u$ was generated by the closed descending chain $(X_s)_{s\in\barR}$, and the same reasoning used to produce \eqref{eq612} tells us that the closed descending chain $(X_{g^{(-1)}(\lambda)})_{\lambda\in\barR}$ yields $g(u)$. Thus the descending chain $(\mathcal T X_{g^{(-1)}(\lambda)})_{\lambda\in\barR}$ defines $Tg(u)$, and we can write
\[
\levelset_{\lambda}Tg(u)=\bigcap_{\mu<\lambda}\mathcal T X_{g^{(-1)}(\mu)}.
\]
We have thus reduced the proof to showing that 
\begin{equation}\label{eq613}
\bigcap_{s<g^{(-1)}(\lambda)}\mathcal T X_s=\bigcap_{\mu<\lambda}\mathcal T X_{g^{(-1)}(\mu)}.
\end{equation}
The argument should be familiar by now, since it is essentially the one used to prove Lemma 6.9. The intersection on the left-hand side of \eqref{eq613}
contains all of the sets $\mathcal T X_s$ for $s<g^{(-1)}(\lambda)$, while the intersection on the right-hand side contains only those $\mathcal T X_s$ for which $s=g^{(-1)}(\mu)$ for some $\mu<\lambda$. This is enough, however, since by Lemma 3.17 every neighborhood of $g^{(-1)}(\lambda)$ contains infinitely many points $s=g^{(-1)}(\mu)$, $\mu<\lambda$. We leave it as an exercise to check that \eqref{eq613} is true for $\lambda\leq\lambda^-$ and $\lambda\geq\lambda^+$.

This completes the proof, but perhaps we should mention that the monotonicity was used when we used $\mathcal T$ to map a closed descending chain like $(X_s)_{s\in\barR}$ into a descending chain $(\mathcal T X_s)_{s\in\barR}$. The latter is not necessarily closed, and in fact, the condition on $\mathcal T$ that ensures that $(\mathcal T X_s)_{s\in\barR}$ is closed is introduced in Definition 6.11.  
\end{proof}

\begin{exercise}
Show that \eqref{eq613} is true for $\lambda\leq\lambda^-$ and $\lambda\geq\lambda^+$. \finex
\end{exercise}

\begin{exercise}
The proof of Proposition 6.10 is simpler if $g$ is assumed to be strictly increasing. 
\begin{enumerate}[(i)]\setlength\itemsep{2pt}    
\item Prove Proposition 6.10 for this case.
\item Given a continuous contrast change $g$, show that there exist functions $f_\varepsilon$ and $h_\varepsilon$, $\varepsilon>0$, that are strictly increasing contrast changes such that $ f_\varepsilon\leq g\leq h_\varepsilon$ and such that $ f_\varepsilon(x)\uparrow g(x)$ and $h_\varepsilon(x)\downarrow g(x)$ for each $x\in\RR$ as $\varepsilon\to0$.
\item Use (i) and (ii), along with the fact that $T$ is monotone, to prove Proposition 6.10. \finex
\end{enumerate}
\end{exercise}

The assumptions that $\mathcal T\emptyset=\emptyset$ and $\mathcal T\RR^N=\RR^N$ were used at least twice in the proof of Proposition 6.9. The next exercise illustrates why these assumptions are necessary to cover all cases.

\begin{exercise}\leavevmode 
\begin{enumerate}[(i)]\setlength\itemsep{2pt}
\item Assume that $g(x)=\lambda_0$ for all $x\in\RR$. Prove that $Tg(u)=g(Tu)$ in this case. Notice where that assumptions $\mathcal T\emptyset=\emptyset$ and $\mathcal T\RR^N=\RR^N$ are used.
\item Let $X_0$ be a fixed subset of $\RR^N$ and consider the mapping $\mathcal T X =X_0$ for all $X\in\mathcal L$. Check that $Tu(\fxx)=+\infty$ if $\fxx\in X_0$ and that $Tu(\fxx)=-\infty$ otherwise. Let $g$ be any bounded, continuous contrast change. Show that $Tg(u)\not=g(Tu)$.
\item Take $X_1\subset X_0$, where $X_1\not=\emptyset$ and $X_0\not=\RR^N$. Define the set operator $\mathcal T$ by $\mathcal T \RR^N=X_0$, $\mathcal T X=X_1$ if $X\not=\RR^N$ and $X\not=\emptyset$, and $\mathcal T\emptyset=\emptyset$. Show that $Tu(x)=-\infty$ if $x\not\in X_0$ and deduce again that $Tg(u)\not=g(Tu)$ if $g$ is bounded.
\item Let $\mathcal T$ be a monotone set operator, without further assumptions. Show that the corresponding function operator $T$ commutes with any continuous contrast change for which $g(-\infty)=-\infty$ and $g(+\infty)=+\infty$. \finex
\end{enumerate}
\end{exercise}

The next exercise is a converse of Proposition 6.8. It states what the previous exercise suggested: $\mathcal T$ monotone implies $T$ contrast invariant if and only if $\mathcal T\emptyset=\emptyset$ and $\mathcal T\RR^N=\RR^N$.

\begin{exercise}
Assume that the set operator $\mathcal T$ is monotone and that the associated function operator $T$ is contrast invariant. Prove that $\mathcal T\emptyset=\emptyset$ and that $\mathcal T\RR^N=\RR^N$. Hint: Assume that $\mathcal T\RR^N\not=\RR^N$ and compute $T\bmone_{\RR^N}$ using its definition (6.9) and separately using the assumption that $T$ is contrast invariant. \finex
\end{exercise}

So far, we have considered set operators $\mathcal T$ that are monotone and such that $\mathcal T\emptyset=\emptyset$ and $\mathcal T\RR^N=\RR^N$. These conditions are ``compatible'' with the structural properties of level sets announced in Proposition 3.2$(i)$, but we have made no assumption that is related to the property in Proposition 3.2$(ii)$. This lack of a continuity assumption meant that relation (6.11) is not completely satisfying, since it is an almost-everywhere statement. We will use the condition in the following definition to correct this. We assume, as usual, that $\mathcal L$ is closed under the intersections $\bigcap_{n\in\NN}$ indexed by $\NN$, which is equivalent to being closed under the intersections $\bigcap_{\lambda\in\barR}$ indexed by $\barR$.

\begin{definition}
A set operator $\mathcal T$ defined on $\mathcal L$ is said to be upper semicontinuous (u.s.c.) on $\mathcal L$ if for every descending sequence $(X_n)_{n\in\NN}$ in $\mathcal L$,
\begin{equation}
\mathcal T\big(\bigcap_{n\in\NN}X_n\big)=\bigcap_{n\in\NN}\mathcal T X_n.
\end{equation}
We also say that $\mathcal T$ is continuous on descending sequences in $\mathcal L$.
\end{definition}

The first thing to notice is that if $\mathcal T$ is u.s.c., then it is monotone. To see this assume that $X\subset Y$ and consider the sequence defined by $X_1=X$, $X_n=Y$ for $n>1$. Then $\bigcap_{n\in\NN}X_n=X$ and $\bigcap_{n\in\NN}\mathcal T X_n=\mathcal T X\cap\mathcal T Y$, and we conclude that $\mathcal T X\subset\mathcal T Y$. The next two exercises develop equivalent properties for an operator $\mathcal T$ to be upper semicontinuous.


\begin{exercise}
Show that a set operator $\mathcal T$ is upper semicontinuous if and only if \[
\mathcal T\big(\bigcap_{\mu<\lambda}X_\mu\big)=\bigcap_{\mu<\lambda}\mathcal T(X_\mu)
\]
for every descending chain $(X_\lambda)_{\lambda\in\barR}$ in $\mathcal L$. \finex
\end{exercise}

We introduce one more notion of continuity for set operators: Given a closed descending chain $(X_\lambda)_{\lambda\in\barR}$ in $\mathcal L$, we say that $\mathcal T$ is \textit{upper semicontinuous on closed descending chains} in $\mathcal L$ if $\mathcal T X_\lambda=\bigcap_{\mu<\lambda}\mathcal T X_\mu$ whenever $(X_\lambda)_{\lambda\in\barR}$ is a closed chain in $\mathcal L$. 

It is clear that $\mathcal T$ is upper semicontinuous on closed chains if it is upper semicontinuous. The content of the next exercise is to show that the converse is true.

\begin{exercise}
Prove the following: If the set operator $\mathcal T$ is upper semicontinuous on closed chains, then it is upper semicontinuous. Hint: First show that $\mathcal T$ is monotone. Then, for any descending chain $(X_\lambda)_{\lambda\in\barR}$, consider the closed descending chain defined by $Y_\lambda=\bigcap_{\mu<\lambda}X_\mu$. \finex
\end{exercise}

The next result is Proposition 6.10 with the additional assumption that $\mathcal T$ is continuous on closed descending chains. For convenience, we restate all of the hypotheses.

\begin{theorem}
Assume that $\mathcal T$ is a set operator defined on a family of sets $\mathcal L$ with the property that $\bigcap_{\mu<\lambda}X_\mu\in\mathcal L$ whenever $(X_\lambda)_{\lambda\in\barR}$ is a descending chain in $\mathcal L$. Assume further that $\emptyset, \RR^N\in\mathcal L$ and that $\mathcal T\emptyset=\emptyset$ and $\mathcal T\RR^N=\RR^N$, and assume also that $\mathcal T$ is u.s.c. on $\mathcal L$. Let $\mathcal F$ be the set of all functions $u$ defined by
\[
u(\fxx)=\sup\{\lambda\mid\fxx\in X_\lambda\},
\] 
where $(X_\lambda)_{\lambda\in\barR}$ is a closed descending chain in $\mathcal L$. Define the operator $T$ on $\mathcal F$ by 
\[
Tu(\fxx)=\sup\{\lambda\mid\fxx\in\mathcal T X_\lambda\},
\]
where $(X_\lambda)_{\lambda\in\barR}$ is the chain that generated $u$.
Then the $T$ defined on $\mathcal F$ is monotone and contrast invariant. Furthermore, for $u\in\mathcal F$, 
\begin{equation}\label{eq616}
\levelset_\lambda Tu=\mathcal T \levelset_\lambda u
\end{equation}
for every $\lambda\in\barR$.
\end{theorem}
\begin{proof}
We have seen that if $\mathcal T$ is u.s.c., then it is monotone. 
That $T$ is monotone and contrast invariant is part of the content of Proposition 6.10. Thus, we need only to prove equation \eqref{eq616}. This, however, is read directly from Proposition 3.2. With the notation of Proposition 3.2, let $\mathcal T\levelset_\lambda u=X_\lambda$. The first part of condition 3.2$(i)$ is satisfied because $\mathcal T$ is monotone. The second part is also satisfied: $\levelset_{-\infty} u=\RR^N$, and thus $X_{-\infty}=\mathcal T\levelset_{-\infty} u=\RR^N$. Condition 3.2$(ii)$ follows from the assumption that $\mathcal T$ is upper semicontinuous: $\bigcap_{\mu<\lambda}\mathcal T\levelset_\mu u=\mathcal T\bigcap_{\mu<\lambda}\levelset_\mu u$ (by upper semicontinuity of $\mathcal T$), and $\levelset_\lambda u=\bigcap_{\mu<\lambda}\levelset_\mu u$ (by 3.2$(ii)$ applied to $u$). Thus, $\bigcap_{\mu<\lambda}\mathcal T\levelset_\mu u=\mathcal T\levelset_\lambda u$. Since 3.2$(ii)$ is thus satisfied, we conclude that $\levelset_{\lambda}Tu=\mathcal T\levelset_\lambda u$ for all $\lambda\in\RR$.
\end{proof}

Before ending this section with an example, we summerize what has been proven: Starting with a monotone set operator $\mathcal T$ defined on $\mathcal L$, and assuming that $\mathcal L$ satisfies certain conditions, we were able to define a set of functions $\mathcal F$ and operator $T$ on $\mathcal F$. The assumptions on $\mathcal L$ implied that $\bmone_{\levelset_{\lambda}}u\in\mathcal F$ whenever $u\in\mathcal F$. The monotonicity of $\mathcal T$ implied that $\mathcal F$ was closed under continuous contrast changes and that $T$ was monotone and contrast invariant. And, finally, the assumption that $\mathcal T$ is continuous on closed descending chains in $\mathcal L$, implies that
\begin{equation}\label{eq617}
\levelset_{\lambda}Tu=\levelset_1 T\bmone_{\levelset_{\lambda}u}
\end{equation}
for all $\lambda\in\barR$. 

There is, of course, a dual theory that starts with a contrast-invariant monotone function operator $T$ defined on a set of functions $\mathcal F$ that contains $\bmone_{\levelset_{\lambda}}u$ for all $u\in\mathcal F$ and all $\lambda\in\barR$. Much of this dual theory has already been developed, mainly in Proposition 6.8. If we know that \eqref{eq617} holds for $T$ and $\mathcal F$, then it is easy to show that superposition (equation \eqref{eq68}) holds everywhere and that $\mathcal T$ is continuous on the closed chains $(\levelset_{\lambda}u)_{\lambda\in\barR}$, where $u\in\mathcal F$. There is so far, however, an obvious gap in the duality between $(\mathcal T, \mathcal L)$ and $(T, \mathcal F)$: Starting with $T$, we have $\mathcal T$ defined on the level sets $\levelset_{\lambda}u$ of functions $u\in\mathcal F$. Thus $\mathcal L$ consists of level sets of $\mathcal F$, and we can recover $u$ and $Tu$ by superposition. But what happens when we consider $v(\fxx)=\sup\{\lambda\mid \fxx\in X_\lambda\}$ and $Tv(\fxx)=\sup\{\lambda\mid \fxx\in\mathcal T X_\lambda\}$, where $(X_\lambda)_{\lambda\in\barR}$ is an arbitrary descending chain of sets in $\mathcal L$? This creates an enlargement of $\mathcal F$ to, say, ${\mathcal F}'$ and an extension of $T$ to $T'$ on ${\mathcal F}'$. The question is, How are properties preserved as one goes from $(T, \mathcal F)$ to $(\mathcal T, \mathcal L)$ and back? We are not going to treat the general issue, but we do deal with a special case---where $\mathcal L$ consists of the compact subsets of $\RR^N$---in Chapter 7.

\begin{exercise}
Prove that if \eqref{eq617} holds, then \eqref{eq68}) holds everywhere and $\mathcal T$ is continuous on the closed chains $(\levelset_{\lambda}u)_{\lambda\in\barR}$, where $u\in\mathcal F$. \finex
\end{exercise}

Theorem 6.12 and the converse, Exercise 6.11, show that a monotone set operator $\mathcal T$ must be upper semicontinuous on $\mathcal L$ to ensure that it and its associated function operator satisfy the commutation relation \eqref{eq616} for every $\lambda$. Here is a simple example that illustrates this necessity. Define $\mathcal T$ on measurable subsets of $\RR$ as follows: For $a>0$, let $\mathcal T X=X$ if $\text{meas}\,(X)>a$, and $\mathcal T X=\emptyset$ otherwise. Let $u:\RR\to\RR$ be defined by $u(x)=-|x|$. Then 
\[
Tu(x)=\sup\{\lambda\mid x\in\mathcal T\levelset_\lambda u\}=\min\{-|x|,-a/2\}.
\]
Thus $\levelset_{-a/2}Tu=[-a/2,a/2]$, and $\levelset_{-a/2}u=[-a/2,a/2]$. Since $\text{meas}\,(\levelset_{-a/2}u)=a$, $\mathcal T \levelset_{-a/2}u=\emptyset$ and $\levelset_{-a/2}Tu\not=\mathcal T \levelset_{-a/2}u$.

Here is another way to look at the example. Let the nonincreasing family of sets $(X_\lambda)_{\lambda\in\barR}$ be defined by $X_\lambda=[-|\lambda|,|\lambda|]$ for $\lambda\leq0$ and $X_\lambda=\emptyset$ for $\lambda>0$. Then, for all $\lambda$, $X_\lambda=\bigcap_{\mu<\lambda}X_\mu$, but $\mathcal T X_{-a/2}\not=\bigcap_{\mu<-a/2}\mathcal T X_\mu$. Note that $\lambda=-a/2$ is the only place where $\mathcal T$ is discontinuous.



\section{The extrema killer: An application}

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. The operators we study are called \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 6.2 and 6.3.

We apply the methods developed in section 6.3 that allow us to define operators on sets and then to extend them to functions, which in this case are images. We will be working with closed, connected sets and connected components of closed sets. The definitions are standard, but we include them here for completeness.

\begin{definition}
Consider a closed subset $X$ of $\RR^N$. $X$ is disconnected if, when it is considered to be a topological space with the topology inherited from $\RR^N$, it can be represented as two disjoint open sets. $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}

Here is an equivalent definition: $X$ is connected if it cannot 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. 

We wish to define a denoising operator on the set $\mathcal L$ of all compact subsets of $\RR^N$. We begin by fixing a scale parameter $a>0$. If $X\in\mathcal L$, then its connected components $X_i$ are uniquely determined, and thus $X$ can be represented uniquely as $X=\bigcup_i X_i$. We want the operator $\mathcal T$ to remove all of the connected components of $X$ that have measure strictly less than $a$. We therefore define the \textit{small component killer} by
\begin{equation}
\mathcal T_a X=\bigcup_{\text{meas}\,(X_i)\geq a}X_i.
\end{equation}
(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, and in practice, everything is finite.)

We are going to prove that the small component killer is upper semicontinuous on descending sequences of compact subsets, and for this we need to consider an arbitrary descending sequence of nonempty compact sets $(Y_n)_{n\in\NN}$ and its limit $Y=\bigcap_{n\in\NN} Y_n$. The most important comment here is that $Y$ is not empty. Indeed, if $Y$ were empty then the opens sets $X_n=\RR^N\setminus Y_n$, $n>1$, cover $Y_1$, but there is no finite collection of the $X_n$ that covers $Y_1$. This contradicts the assumption that $Y_1$ is compact. Thus, $Y$ is nonempty, and of course it is compact. The next most important observation is that the convergence $Y_n\downarrow Y$ is continuous in the following sense: Given any open set $Z$ that covers $Y$, there is an index $n_0$ such that $Y_n\subset Z$ for all $n\geq n_0$. If this were not the case, then $Y_{n}\cap(\RR^N\setminus Z)\neq\emptyset$ infinitely often. This implies that $(Y_n\cap(\RR^N\setminus Z))_{n\in\NN}$ is a descending sequence of nonempty compact subsets of $Y_1$. But this means that $Y\cap (\RR^N\setminus Z)\neq\emptyset$, which is a contradiction.  

\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}
\begin{proof}
We know that $Y$ is not empty and compact. We will prove that it is connected by contradiction. Thus suppose 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$, 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, and we conclude that $Y$ must be connected.
\end{proof}

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

With the extrema killer we have a prime example of a theory that begins with a set operator $\mathcal T_a$ defined on a collection of subsets $\mathcal L$ of $\RR^N$. What we have done in section 6.3 requires that $\RR^N$ and $\emptyset$ belong $\mathcal L$ and that $\mathcal T_a\RR^N=\RR^N$ and $\mathcal T_a\emptyset=\emptyset$. This presents no problem: We add $\RR^N$ to $\mathcal L$ and extend $\mathcal T_a$ to $\RR^N$ by $\mathcal T_a\RR^N=\RR^N$. Technically, this is equivalent to extending $\mathcal T_a$ to the one-point compactification of $\RR^N$. The other property of $\mathcal L$ that was always assumed was that $\bigcap_{\mu<\lambda}X_\mu$ was in $\mathcal L$ for all descending chains $(X_\lambda)_{\lambda\in\barR}$ in $\mathcal L$. Our discussion shows that this is true if $\mathcal L$ is the family of all compact subsets of $\RR^N$. 

Based on what we have already done, it is now quite easy to show that $\mathcal T_a$ is continuous on descending chains of compact sets.

\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{proof}
We first prove that $\mathcal T_a$ is monotone. Thus, 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$. Another important property of $\mathcal T_a$ is that it is idempotent: ${\mathcal T_a}^2 X=\mathcal T_a X$. And finally, $\mathcal T_a$ is a contraction mapping: $\mathcal T_a X\subset X$.

Now let $(X_\lambda)_{\lambda\in\barR}$ be any closed descending chain of nonempty compact sets. We wish to show that $\mathcal T_a X_\lambda=\bigcap_{\mu<\lambda}\mathcal T_a X_\mu$. For any $\lambda>-\infty$ we have $\mathcal T_a X_\lambda\subset X_\lambda$, and hence 
\begin{equation}\label{eq618}
\mathcal T_a X_\lambda\subset\bigcap_{\mu<\lambda}\mathcal T_a X_\mu\subset\bigcap_{\mu<\lambda} X_\mu=X_\lambda.
\end{equation}
By applying $\mathcal T_a$ to \eqref{eq618} we see that 
\begin{equation}\label{eq619}
\mathcal T_a^2 X_\lambda\subset\mathcal T_a\Big(\bigcap_{\mu<\lambda}\mathcal T_a X_\mu\Big)\subset\mathcal T_a\bigcap_{\mu<\lambda} X_\mu=\mathcal T_a X_\lambda.
\end{equation}
Since $\mathcal T_a^2 X_\lambda=\mathcal T_a X_\lambda$, we see from \eqref{eq619} that $\mathcal T_a\big(\bigcap_{\mu<\lambda}\mathcal T_a X_\mu\big)=\mathcal T_a X_\lambda$, and thus we have reduced the proof to showing that$\mathcal T_a\big(\bigcap_{\mu<\lambda}\mathcal T_a X_\mu\big)=\bigcap_{\mu<\lambda}\mathcal T_a X_\mu$. This last equality can only be false if $\bigcap_{\mu<\lambda}\mathcal T_a X_\mu$ contains connected components with measure less than $a$. Intuitively, this cannot happen because any such component has already been killed, and here is the proof. Assume that $\bigcap_{\mu<\lambda}\mathcal T_a X_\mu$ is not empty and let $Y$ denote one of its connected components. (If $\bigcap_{\mu<\lambda}\mathcal T_a X_\mu$ is empty the result is clearly true.) Then $Y\subset\mathcal T_a X_\mu$ for every $\mu<\lambda$. Let $Y_\mu$ denote the unique connected component of $\mathcal T_a X_\mu$ that contains $Y$. If $\nu<\mu$, then $Y_\mu$ is contained in a unique connected component of $\mathcal T_a X_\nu$. This component must be $Y_\nu$, since both $Y_\nu$ and $Y_\mu$ contain $Y$. Thus, $\nu<\mu$ implies that $Y_\mu\subset Y_\nu$, so by Lemma 6.14 (which clearly is true for chains as well as sequences), $\bigcap_{\mu<\lambda}Y_\mu$ is a connected compact set that contains $Y$. Since $Y$ is a maximal connected subset of $\bigcap_{\mu<\lambda}\mathcal T_a X_\mu$, it must be that $Y=\bigcap_{\mu<\lambda}Y_\mu$, and since $\mathrm{meas}\,(Y_\mu)\geq a$, $\mathrm{meas}\,(Y)\geq a$. Thus, as per intuition, all of the components of $\bigcap_{\mu<\lambda}\mathcal T_a X_\mu$ have measure greater than or equal to $a$, and hence $\mathcal T_a\big(\bigcap_{\mu<\lambda}\mathcal T_a X_\mu\big)=\bigcap_{\mu<\lambda}\mathcal T_a X_\mu$, and $\mathcal T_a X_\lambda=\bigcap_{\mu<\lambda}\mathcal T_a X_\mu$.
\end{proof}

We wish to use $\mathcal T_a$ to define a function operator $T_a$ on a family of functions $\mathcal F$. If we apply Theorem 6.12 directly, we obtain a function operator $T_a$ defined on the set of functions $\mathcal F$ that is characterized by the fact that $u\in\mathcal F$ if and only if $\levelset_{\lambda}u$ is compact for all $\lambda\in\RR$. In particular, $\mathcal F$ contains all the continuous functions whose level sets are compact. Furthermore, $T_a$ is monotone and contrast invariant and $\mathcal T_a\levelset_{\lambda}u=\levelset_{\lambda}T_{a}u$ for all $\lambda$. The operators $T_a$ and $\mathcal T_a$ are also translation invariant. 

There is, however, another setting that is more appropriate for image analysis. This is the situation described in Chapter 1, where we started with a function $u$ (an image) defined on $[0,1]^N$ and extended $u$ by symmetry and periodicity to a symmetric $C$-periodic function $u$ defined on all of $\RR^N$. We denote these functions by $L_{Cs}$, where the ``s'' is to remind us that the functions are symmetric as well as $C$-periodic. Of course, $L_{Cs}\subset L_{C}$, the set of all $C$-periodic functions. We could focus on functions defined on $[0,1]^N$ without extending them, but this would have the disadvantage that the space of functions is not translation invariant. For this reason, we prefer to work with $L_{C}$. To do this, we replace $\RR^N$ with the $N$-dimensional torus, $\mathbb T^N$. All of the results developed in Chapter 3 and this chapter remain true if $\RR^N$ is replaced with the compact space $\mathbb T^N$, but the results must be interpreted in this new setting. For example, if we replace $\RR^N$ with $\mathbb T^N$ in Theorem 6.12, then we have the same results, but the functions are defined on $\mathbb T^N$. The functions defined on $\mathbb T^N$ are in one-to-one correspondence with the $C$-periodic functions on $\RR^N$, and thus one can consider either $C$-periodic functions on $\RR^N$ or functions on $\mathbb T^N$. We prefer to interpret these as $C$-periodic functions on $\RR^N$. On the other hand, it is perhaps easier to think of the level sets of these functions as subsets of $\mathbb T^N$ rather than ``periodized'' subsets of $C=[-1,1]^N$. With this as background, the next definition makes sense.
 
\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{exercise}
Show that $T_a$ maps $L_{Cs}$ into $L_{Cs}$. \finex
\end{exercise}

\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}
\begin{proof}
The proof that $T_a$ is monotone, contrast invariant, and satisfies \eqref{eq620} is read directly from Theorem 6.12 and Lemma 6.15. Clearly, $\mathcal T_a$ and $T_a$ are translation invariant. Knowing that $T_a$ satisfies these condition, we see from Exercise 6.2(iii) that $T_a$ is a contraction mapping:
\begin{equation}\label{eq621}
\sup_{\fxx\in\RR^N}|T_a u(\fxx)-T_a v(\fxx)|\leq\sup_{\fxx\in\RR^N}|u(\fxx)-v(\fxx)|
\end{equation}
for $u,v\in\mathcal F$. If $u\in L_C$ is continuous, then it is uniformly continuous and we can write $|u(\fxx+\fxy)-u(\fxx)|\leq \varepsilon(|\fxy|)$, where $\varepsilon$ is the modulus of continuity of $u$. Then from Exercise 6.2 and \eqref{eq621} we have
\[
|T_a u(\fxx+\fxy)-T_a u(\fxx)|\leq|u(\fxx+\fxy)-u(\fxx)|\leq\varepsilon(|\fxy|).\qedhere 
\]
\end{proof}

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\}$. This would lead to a different set of functions $\mathcal F^-$ and a different function operator $T_a^-$, but the set operator $\mathcal T_a$ would be the same. 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}
\begin{exercise}
[A major project] Outline the dual theory based on lower level sets. Begin with Proposition 3.2. Pay particular attention to the definitions and key results that must be recast. Give a reformulation of Theorem 6.12, and finally, show that the resulting minima killer is the operator defined above as $T^-$ . \finex

\end{exercise}

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

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